Как работают malloc () и free ()?

Я хочу знать, как mallocи freeработать.

int main() {
    unsigned char *p = (unsigned char*)malloc(4*sizeof(unsigned char));
    memset(p,0,4);
    strcpy((char*)p,"abcdabcd"); // **deliberately storing 8bytes**
    cout << p;
    free(p); // Obvious Crash, but I need how it works and why crash.
    cout << p;
    return 0;
}

Я был бы очень признателен, если бы ответ был глубоко на уровне памяти, если это возможно.

Хорошо, некоторые ответы о malloc уже были опубликованы.

Более интересной частью является то, как free работает (и в этом направлении malloc тоже можно понять лучше).

Во многих реализациях malloc / free free обычно не возвращает память операционной системе (или, по крайней мере, только в редких случаях). Причина в том, что вы получите пробелы в своей куче, и, таким образом, может случиться, что вы просто заделаете свои 2 или 4 ГБ виртуальной памяти пробелами. Этого следует избегать, поскольку, как только виртуальная память закончится, у вас будут действительно большие проблемы. Другая причина в том, что ОС может обрабатывать только фрагменты памяти, которые имеют определенный размер и выравнивание. Чтобы быть конкретным: обычно ОС может обрабатывать только блоки, которые может обрабатывать менеджер виртуальной памяти (чаще всего кратно 512 байт, например, 4 КБ).

Поэтому возврат 40 байт в ОС просто не будет работать. Так что же делать бесплатно?

Свободный помещает блок памяти в свой собственный список свободных блоков. Обычно он также пытается объединить смежные блоки в адресном пространстве. Список свободных блоков - это просто циклический список блоков памяти, в начале которых есть некоторые административные данные. Это также причина, по которой управление очень маленькими элементами памяти со стандартным malloc / free неэффективно. Каждый блок памяти требует дополнительных данных, а при меньших размерах происходит большая фрагментация.

Free-list - это также первое место, на которое malloc смотрит, когда нужен новый кусок памяти. Он сканируется, прежде чем вызывает новую память из ОС. Когда найден фрагмент, который больше необходимой памяти, он разделяется на две части. Один возвращается вызывающей стороне, другой возвращается в свободный список.

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

Почему ваш код падает:

Причина в том, что, записав 9 символов (не забывая завершающий нулевой байт) в область размером 4 символа, вы, вероятно, перезапишете административные данные, хранящиеся в другой части памяти, которая находится «позади» вашей части данных ( поскольку эти данные чаще всего хранятся «перед» кусками памяти). Когда free затем пытается поместить ваш чанк в список free, он может коснуться этих административных данных и, следовательно, наткнуться на перезаписанный указатель. Это приведет к краху системы.

Это довольно изящное поведение. Я также видел ситуации, когда беглый указатель где-то перезаписывал данные в списке свободной памяти, и система не сразу падала, но некоторые подпрограммы позже. Даже в системе средней сложности такие проблемы могут быть действительно очень сложными для отладки! В одном случае, в котором я участвовал, нам (большой группе разработчиков) потребовалось несколько дней, чтобы найти причину сбоя, поскольку она находилась в совершенно другом месте, чем указано в дампе памяти. Это как бомба замедленного действия. Вы знаете, ваш следующий "free" или "malloc" потерпит крах, но вы не знаете почему!

Это некоторые из худших проблем C / C ++, и одна из причин, почему указатели могут быть такими проблемными.

Как говорит aluser в этой ветке форума :

У вашего процесса есть область памяти, от адреса x до адреса y, называемая кучей. Все ваши данные malloc'd живут в этой области. malloc () хранит некоторую структуру данных, скажем, список всех свободных кусков пространства в куче. Когда вы вызываете malloc, он просматривает список для достаточно большого для вас чанка, возвращает указатель на него и записывает тот факт, что он больше не является бесплатным, а также его размер. Когда вы вызываете free () с тем же указателем, free () проверяет, насколько велик этот чанк, и добавляет его обратно в список свободных чанков (). Если вы вызываете malloc (), и он не может найти достаточно большой кусок в куче, он использует системный вызов brk () для увеличения кучи, то есть увеличения адреса y и вызова всех адресов между старым y и новым y в быть действительной памятью. brk () должен быть системным вызовом;

malloc () зависит от системы / компилятора, поэтому сложно дать конкретный ответ. Однако, в основном, он отслеживает, какая память выделена, и в зависимости от того, как он это делает, ваши вызовы на освобождение могут быть неудачными или успешными.

malloc() and free() don't work the same way on every O/S.

Одна реализация malloc / free делает следующее:

1. Получить блок памяти из ОС через sbrk () (вызов Unix).
2. Создайте заголовок и нижний колонтитул вокруг этого блока памяти с некоторой информацией, такой как размер, разрешения и где находится следующий и предыдущий блоки.
3. Когда поступает вызов malloc, делается ссылка на список, который указывает на блоки соответствующего размера.
4. Затем этот блок возвращается, а верхние и нижние колонтитулы обновляются соответствующим образом.

Защита памяти имеет гранулярность страницы и требует взаимодействия с ядром

Ваш пример кода по существу спрашивает, почему пример программы не перехватывает, и ответ заключается в том, что защита памяти является функцией ядра и применяется только к целым страницам, тогда как распределитель памяти является функцией библиотеки, и он управляет ... без применения ... произвольно размерные блоки, которые часто намного меньше, чем страницы.

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

calloc (3) и malloc (3) взаимодействуют с ядром, чтобы получить память, если это необходимо. Но большинство реализаций free (3) не возвращают память ядру ¹ , они просто добавляют ее в свободный список, который calloc () и malloc () будут использовать позже, чтобы повторно использовать освобожденные блоки.

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

Так что ваш блок там, в свободном списке. Почти всегда вы можете получить к нему доступ и к памяти, как если бы она была еще выделена. C компилируется прямо в машинный код, и без специальных механизмов отладки не выполняется проверка работоспособности загрузок и хранилищ. Теперь, если вы попытаетесь получить доступ к свободному блоку, поведение не определено стандартом, чтобы не предъявлять необоснованные требования к разработчикам библиотек. Если вы попытаетесь получить доступ к освобожденной памяти или памяти за пределами выделенного блока, есть несколько вещей, которые могут пойти не так:

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

Теория Операции

Итак, работая в обратном направлении от вашего примера к общей теории, malloc (3) получает память от ядра, когда это необходимо, и обычно в единицах страниц. Эти страницы разделены или объединены в соответствии с требованиями программы. Malloc и свободно сотрудничают, чтобы поддерживать каталог. Они объединяют смежные свободные блоки, когда это возможно, чтобы обеспечить большие блоки. Каталог может включать или не включать использование памяти в освобожденных блоках для формирования связанного списка. (Альтернатива - немного более совместная память и дружественная подкачка, и она включает в себя выделение памяти специально для каталога.) У Malloc и free практически отсутствует возможность принудительного доступа к отдельным блокам, даже если специальный и дополнительный код отладки скомпилирован в программа.

^{1. Тот факт, что очень немногие реализации free () пытаются вернуть память в систему, необязательно из-за ослабления работы разработчиков. Взаимодействие с ядром намного медленнее, чем простое выполнение библиотечного кода, и выгода будет небольшой. Большинство программ имеют постоянный или увеличивающийся объем памяти, поэтому время, потраченное на анализ кучи в поисках возвратной памяти, будет полностью потрачено впустую. Другие причины включают тот факт, что внутренняя фрагментация делает блоки, выровненные по страницам, маловероятными, и, вероятно, возвращение блока приведет к фрагментации блоков с любой стороны. Наконец, те немногие программы, которые возвращают большие объемы памяти, скорее всего, будут обходить malloc () и в любом случае просто выделять и освобождать страницы.}

Теоретически, malloc получает память от операционной системы для этого приложения. Однако, поскольку вам может потребоваться только 4 байта, а ОС должна работать на страницах (часто 4 КБ), malloc делает немного больше. Он берет страницу и помещает туда свою собственную информацию, чтобы она могла отслеживать, что вы выделили и освободили от этой страницы.

Например, когда вы выделяете 4 байта, malloc дает вам указатель на 4 байта. Чего вы не можете понять, так это того, что malloc использует память за 8-12 байтов до того, как ваши 4 байта используются для создания цепочки всей выделенной памяти. Когда вы звоните бесплатно, он берет ваш указатель, выполняет резервное копирование туда, где находятся данные, и обрабатывает их.

Когда вы освобождаете память, malloc снимает этот блок памяти с цепочки ... и может возвращать или не возвращать эту память операционной системе. Если это произойдет, то доступ к этой памяти, вероятно, потерпит неудачу, поскольку ОС лишит вас разрешений на доступ к этому местоположению. Если malloc сохраняет память (потому что на этой странице выделены другие объекты или для некоторой оптимизации), доступ будет работать. Это все еще неправильно, но это может сработать.

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: То, что я описал, является распространенной реализацией malloc, но ни в коем случае не единственно возможной.

Ваша строка strcpy пытается сохранить 9 байтов, а не 8, из-за ограничителя NUL. Это вызывает неопределенное поведение.

Призыв к свободе может или не может дать сбой. Память «после» 4 байтов вашего выделения может быть использована для чего-то еще вашей реализацией C или C ++. Если это используется для чего-то другого, то каракули по всему этому приведут к тому, что это «что-то еще» пойдет не так, но если это не будет использовано для чего-то другого, то вы можете сойти с рук. «Сойти с рук» может звучать хорошо, но на самом деле это плохо, поскольку это означает, что ваш код будет работать нормально, но в будущем вы, возможно, с этим не справитесь.

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

В противном случае вы можете обнаружить, что следующие 5 байтов содержат часть узла связи, принадлежащую другому блоку памяти, который еще не был выделен. Освобождение вашего блока может включать добавление его в список доступных блоков, и, поскольку вы набросали узел списка, эта операция может разыменовать указатель с недопустимым значением, что приведет к сбою.

Все зависит от распределителя памяти - разные реализации используют разные механизмы.

Принцип работы malloc () и free () зависит от используемой библиотеки времени выполнения. Обычно malloc () выделяет кучу (блок памяти) из операционной системы. Каждый запрос к malloc () затем выделяет небольшой фрагмент этой памяти, возвращая указатель вызывающей стороне. Процедуры выделения памяти должны будут хранить некоторую дополнительную информацию о выделенном блоке памяти, чтобы иметь возможность отслеживать используемую и свободную память в куче. Эта информация часто хранится в нескольких байтах непосредственно перед указателем, возвращаемым функцией malloc (), и это может быть связанный список блоков памяти.

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

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

Это не имеет ничего общего с malloc и free. Ваша программа демонстрирует неопределенное поведение после копирования строки - это может привести к сбою в этой точке или в любой точке впоследствии. Это было бы верно, даже если вы никогда не использовали malloc и free и размещали массив char в стеке или статически.

malloc и free зависят от реализации. Типичная реализация включает в себя разбиение доступной памяти на «свободный список» - связанный список доступных блоков памяти. Многие реализации искусственно делят его на маленькие и большие объекты. Свободные блоки начинаются с информации о том, насколько большой блок памяти и где следующий, и т. Д.

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

Ну, это зависит от реализации распределителя памяти и ОС.

Например, в Windows процесс может запросить страницу или больше оперативной памяти. Затем ОС назначает эти страницы процессу. Однако это не память, выделенная вашему приложению. Распределитель памяти CRT помечает память как непрерывный «доступный» блок. Распределитель памяти CRT будет затем пробегать список свободных блоков и найдет наименьший возможный блок, который он может использовать. Затем он займет столько блока, сколько ему нужно, и добавит его в «распределенный» список. К заголовку фактического выделения памяти будет прикреплен заголовок. Этот заголовок будет содержать различный бит информации (например, он может содержать следующий и предыдущий выделенные блоки для формирования связного списка. Скорее всего, он будет содержать размер выделения).

Free затем удалит заголовок и вернет его обратно в список свободной памяти. Если он образует больший блок с окружающими свободными блоками, они будут добавлены вместе, чтобы получить больший блок. Если вся страница теперь свободна, распределитель, скорее всего, вернет страницу в ОС.

Это не простая проблема. Часть распределителя ОС находится вне вашего контроля. Я рекомендую вам прочитать что-то вроде Malloc от Doug Lea (DLMalloc), чтобы понять, как будет работать довольно быстрый распределитель.

Изменить: Ваш сбой будет вызван тем, что при записи больше, чем выделение вы перезаписали следующий заголовок памяти. Таким образом, когда он освобождается, он очень сбивается с толку относительно того, что именно он освобождает, и как слить в следующий блок. Это не всегда может вызвать сбой сразу на свободе. Это может вызвать сбой позже. Вообще избегайте перезаписи памяти!

Ваша программа падает, потому что она использовала память, которая не принадлежит вам. Он может быть использован кем-то другим или нет - если вам повезет, что вы потерпите крах, если нет, проблема может оставаться скрытой в течение долгого времени и возвращаться и кусать вас позже.

Что касается реализации malloc / free - этой теме посвящены целые книги. По сути, распределитель получит большие объемы памяти из ОС и будет управлять ими за вас. Некоторые из проблем, которые должен решить распределитель:

• Как получить новую память
• Как его сохранить - (список или другая структура, несколько списков для фрагментов памяти разного размера и т. Д.)
• Что делать, если пользователь запрашивает больше памяти, чем доступно в данный момент (запросить больше памяти у ОС, объединить некоторые из существующих блоков, как их точно соединить, ...)
• Что делать, когда пользователь освобождает память
• Распределители отладки могут дать вам больший кусок, который вы запросили, и заполнить его некоторым байтовым шаблоном, когда вы освобождаете память, которую распределитель может проверить, записано ли вне блока (что, вероятно, происходит в вашем случае) ...

Трудно сказать, потому что фактическое поведение отличается в разных компиляторах / времени выполнения. Даже сборки отладки / выпуска имеют различное поведение. Отладочные сборки VS2005 будут вставлять маркеры между выделениями для обнаружения повреждения памяти, поэтому вместо сбоя он будет утвержден в free ().

Также важно понимать, что простое перемещение указателя разрыва программы с помощью brkи sbrkфактически не выделяет память, а просто устанавливает адресное пространство. Например, в Linux память будет «поддерживаться» фактическими физическими страницами при обращении к этому диапазону адресов, что приведет к сбою страницы и в конечном итоге приведет к тому, что ядро ​​вызовет распределитель страниц, чтобы получить резервную страницу.