Можно ли написать согласованную реализацию malloc в C?

Это продолжение Может ли массив char использоваться с любым типом данных?

Я знаю о динамической памяти и общих реализациях malloc, ссылки можно найти на wikipedia. Я также знаю, что указатель, возвращаемый malloc, может быть отброшен на все, что хочет программист, даже не предупредив, поскольку стандартные состояния в 6.3.2.3 Указатели §1

Указатель на void может быть преобразован в указатель или из указателя на любой неполный или объект тип. Указатель на любой неполный или тип объекта может быть преобразован в указатель на void и обратно; результат сравнивается с исходным указателем.

Вопрос заключается в том, что у меня есть автономная среда без malloc и free, как я могу построить в согласованном C реализацию этих двух функций?

Если я беру некоторую свободу относительно стандарта, это легко:

начать с массива больших символов
используйте достаточно большое выравнивание (8 должно быть достаточно для многих архитектур)
реализовать алгоритм, возвращающий адреса из этого массива, при этом выравнивании, отслеживание того, что было выделено, - хорошие примеры можно найти в реализации malloc?

Проблема заключается в том, что эффективный тип указателей, возвращаемых этой реализацией, будет char *

И стандарт говорит в том же параграфе § 7

Указатель на объект или неполный тип может быть преобразован в указатель на другой объект или неполный тип. Если результирующий указатель неправильно выровнен для по типу, поведение undefined. В противном случае при обратном результат сравнивается с исходным указателем.

Это, похоже, не позволяет мне притворяться, что то, что было объявлено как простые символы, может магически содержать другой тип и даже разные типы в разных частях этого массива или в разные моменты в той же части. Говорят, что различие в разыменовании таких указателей кажется undefined поведением со строгой интерпретацией стандарта. Вот почему общие идиомы используют memcpy вместо сглаживания, когда вы получаете байтовое представление объекта в строковом буфере, например, когда вы читаете его из сетевого потока.

Итак, как я могу построить совместимую реализацию malloc в чистом C???

Ответ 1

Авторы стандарта C приложили гораздо больше усилий, чтобы определить поведение, которое явно не было желательным, чем те, которые были, поскольку они ожидали, что разумные авторы компиляторов будут поддерживать полезные поведения независимо от того, санкционировал ли это Стандарт или нет, из-за тупых компиляторов авторы могли создавать "совместимые" реализации, которые были полностью совместимы, но совершенно бесполезны (*).

На момент появления C89 на многих платформах можно было писать надежные и эффективные эквиваленты malloc(), и я не вижу оснований полагать, что авторы предполагали, что люди, пишущие компиляторы C89 для платформы, которые могли обрабатывать Ранее аналогичные эквиваленты malloc() не могли сделать эти реализации такими же способными, как и их предшественники. К сожалению, язык, который был популярен в 1990-х годах (который был объединенным надмножеством C89 и его предшественников) был заменен некачественным диалектом, который пропускает функции, которые авторы C89 приняли бы как должное, и ожидали, что другие сделают то же самое.

Даже вне вопроса о том, как человек приобретает память, более серьезной проблемой является то, что malloc() promises, что вновь выделенная память, в худшем случае, будет удерживаться Неопределенная стоимость; потому что типы структуры не имеют ловушечных представлений, чтение такого хранилища с использованием указателя типа структуры будет определено поведение. Если память ранее была написана с использованием какого-либо другого типа, однако чтение типа структуры должно иметь Undefined Поведение, если только free() или malloc() физически стирает все содержимое, о котором идет речь, тем самым отрицая преимущество производительности при использовании malloc(), а не просто calloc().

(*) Если существует хотя бы один набор исходных файлов, которые процессы реализации совместимы без UB, для реализации может потребоваться произвольное (возможно, невероятно большое) количество пространства стека при предоставлении любого другого набора исходных файлов, и вести себя произвольно, если это пространство недоступно.

Ответ 2

Этот ответ является лишь интерпретацией стандарта, потому что я не смог найти явный ответ в проекте C99 n1256 или в C11 n1570.

Обоснование исходит из стандарта С++ (проект С++ 14 n4296). 3.8. Срок жизни объекта [basic.life] говорит (подчеркивайте мое):

§ 1 Время жизни объекта типа T начинается, когда:

хранилище с правильным выравниванием и размером для типа T получено, а

Если объект имеет незапамятную инициализацию, его инициализация завершена.
Время жизни объекта типа T заканчивается, когда:

если T - тип класса с нетривиальным деструктором (12.4), начинается вызов деструктора или

хранилище, которое объект занимает, повторно используется или освобождается.

§ 3 Свойства, приписываемые объектам в рамках этого международного стандарта, применяются только к данному объекту при его жизни.

Я знаю, что C и С++ - разные языки, но они связаны друг с другом, и выше это только здесь, чтобы объяснить следующую интерпретацию

Соответствующая часть в стандарте C - 7.20.3 Функции управления памятью.

... Указатель возвращается, если выделение successs соответствующим образом выравнивается, так что ему может быть присвоен указатель на любой тип объекта а затем используется для доступа к такому объекту или массиву таких объектов в выделенном пространстве (пока пространство явно не освобождено). Время жизни выделенного объекта продолжается от выделения до освобождения. Каждое такое распределение должно указывать указатель на объект, не связанный с каким-либо другим объектом. Указатель возвращает точки в начало (младший байт адрес) выделенного пространства...

Моя интерпретация заключается в том, что при условии, что у вас есть зона памяти с правильным размером и выравниванием, например часть большого массива символов, но здесь можно использовать любой тип массива типа, здесь вы можете притворяться, что это указатель на неинициализированный объект или массив другого типа (скажем T) и преобразовать указатель char или void в первый байт зоны указателю нового типа (T). Но для того, чтобы не нарушать правило строгого сглаживания, эта зона больше не должна быть доступна через любое предыдущее значение или указатель или начальный тип - если начальный тип был символом, он все равно будет разрешен для чтения, но запись может привести к ловушке представление. Поскольку этот объект не инициализирован, он может содержать представление ловушки и считать его до его инициализации undefined. Этот объект T и связанный с ним указатель будут действительны до тех пор, пока вы не решите использовать зону памяти для любого другого использования, и указатель на T становится висящим в это время.

TL/DR: правило строгого псевдонижения требует только, чтобы зона памяти могла содержать только объект одного эффективного типа за один момент. Но вам разрешено повторно использовать зону памяти для объекта другого типа:

размер и выравнивание совместимы
вы инициализируете новый объект с правильным значением перед его использованием.
вы больше не получаете доступ к исходному объекту

Таким образом, вы просто используете зону памяти в качестве выделенной памяти.

В соответствии с стандартом C, время жизни исходного объекта не будет прекращено (статические объекты сохраняются до конца программы и автоматически до конца их области объявления), но вы больше не сможете получить к ней доступ из-за строгое правило сглаживания