Как malloc() реализован внутри?
Может кто-нибудь объяснить, как malloc() работает внутри?
Я иногда делал strace program и я вижу много sbrk системные вызовы, делать man sbrk говорит об этом используется в malloc() но не намного
3 ответа
sbrk Системный вызов перемещает "границу" сегмента данных. Это означает, что он перемещает границу области, в которой программа может читать / записывать данные (позволяя им расти или уменьшаться, хотя AFAIK нет malloc действительно возвращает сегменты памяти ядру этим методом). Помимо этого, есть также mmap который используется для отображения файлов в память, но также используется для выделения памяти (если вам нужно выделить общую память, mmap как ты это делаешь).
Итак, у вас есть два способа получить больше памяти из ядра: sbrk а также mmap, Существуют различные стратегии организации памяти, которую вы получаете из ядра.
Один наивный способ состоит в том, чтобы разделить его на зоны, часто называемые "ведрами", которые предназначены для определенных размеров конструкции. Например, malloc Реализация может создать сегменты для 16, 64, 256 и 1024 байтовых структур. Если вы спросите malloc чтобы дать вам память определенного размера, она округляет это число до следующего размера корзины, а затем выдает элемент из этого сегмента. Если вам нужна большая площадь malloc мог бы использовать mmap выделить непосредственно с ядром. Если ведро определенного размера пусто malloc мог бы использовать sbrk чтобы получить больше места для нового ведра.
Есть разные malloc дизайн и, вероятно, нет единственно верного способа реализации malloc так как вам нужно найти компромисс между скоростью, накладными расходами и избеганием фрагментации / эффективности пространства. Например, если в корзине заканчиваются элементы, реализация может получить элемент из большей корзины, разделить его и добавить в корзину, в которой заканчиваются элементы. Это было бы довольно экономно, но не было бы возможно с каждым дизайном. Если вы просто получите еще одно ведро через sbrk / mmap это может быть быстрее и даже проще, но не так эффективно. Кроме того, дизайн должен, конечно, принимать во внимание, что "свободное" необходимо сделать пространство доступным для malloc опять как-то. Вы не просто раздаете память, не используя ее повторно.
Если вам интересно, у SIP-прокси OpenSER/Kamailio есть два malloc реализации (им нужны свои, потому что они интенсивно используют общую память и систему malloc не поддерживает общую память). Смотрите: https://github.com/OpenSIPS/opensips/tree/master/mem
Тогда вы также можете взглянуть на GNU libc malloc реализация, но это очень сложно, IIRC.
Упрощенно, malloc и free работают так:
malloc обеспечивает доступ к куче процесса. Куча - это конструкция в базовой библиотеке C (обычно libc), которая позволяет объектам получать эксклюзивный доступ к некоторому пространству в куче процесса.
Каждое выделение в куче называется ячейкой кучи. Обычно он состоит из заголовка, который содержит информацию о размере ячейки, а также указателя на следующую ячейку кучи. Это делает кучу эффективно связанным списком.
Когда запускается процесс, куча содержит одну ячейку, которая содержит все пространство кучи, назначенное при запуске. Эта ячейка существует в свободном списке кучи.
Когда кто-то вызывает malloc, память берется из большой ячейки кучи, которую возвращает malloc. Остальное формируется в новую ячейку кучи, которая состоит из всей остальной памяти.
Когда освобождается память, ячейка кучи добавляется в конец свободного списка кучи. Последующие мальлоки берут свободный список в поисках ячейки подходящего размера.
Как и следовало ожидать, куча может быть фрагментирована, и менеджер кучи может время от времени пытаться объединить смежные ячейки кучи.
Когда в свободном списке не осталось памяти для требуемого выделения, malloc вызывает brk или sbrk, которые являются системными вызовами, запрашивающими больше страниц памяти из операционной системы.
Теперь есть несколько модификаций для оптимизации операций с кучей.
- Для больших выделений памяти (обычно> 512 байт, менеджер кучи может перейти прямо к ОС и выделить страницу полной памяти.
- Куча может указывать минимальный размер выделения для предотвращения большого количества фрагментации.
- Куча может также делиться на бины, один для небольших выделений и один для больших выделений, чтобы ускорить выделение больших.
- Есть также умные механизмы для оптимизации многопоточного выделения кучи.
Также важно понимать, что простое перемещение указателя разрыва программы с помощью brk а также sbrk на самом деле не выделяет память, он просто устанавливает адресное пространство. Например, в Linux память будет "поддерживаться" фактическими физическими страницами при обращении к этому диапазону адресов, что приведет к ошибке страницы и в конечном итоге приведет к тому, что ядро вызовет распределитель страниц, чтобы получить резервную страницу.