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

Question

Я хочу знать, как работают 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;
}

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

Answer 1

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

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

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

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

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

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

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

Почему происходит сбой кода:

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

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

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

Теория работы

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

---

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

Answer 5

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

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

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

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я описал общую реализацию malloc, но отнюдь не единственно возможную.

Answer 6

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

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

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

Answer 7

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

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

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

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

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

Answer 8

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

Answer 9

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

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

Answer 10

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

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

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

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

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