Как реализуется malloc() внутри?

Ответ 1

Системный вызов sbrk перемещает "границу" сегмента данных. Это означает, что он перемещает границу области, в которой программа может читать/записывать данные (позволяя ей расти или сокращаться, хотя AFAIK no malloc действительно возвращает сегменты памяти обратно в ядро ​​с помощью этого метода). Кроме того, там также mmap, который используется для сопоставления файлов в память, но также используется для выделения памяти (если вам нужно выделить общую память, mmap - как вы это делаете).

Итак, у вас есть два способа получить больше памяти из ядра: sbrk и mmap. Существуют различные стратегии по организации памяти, которую вы получили от ядра.

Один наивный способ состоит в том, чтобы разбить его на зоны, часто называемые "ведрами", которые посвящены определенным размерам структуры. Например, реализация malloc может создавать ведра для структур с 16, 64, 256 и 1024 байтами. Если вы попросите malloc предоставить вам память определенного размера, округлите это число до следующего размера ковша, а затем вы получите элемент из этого ведра. Если вам нужна большая область malloc, вы можете использовать mmap для прямого размещения ядра. Если ведро определенного размера пуста, malloc может использовать sbrk, чтобы получить больше места для нового ведра.

Существуют различные конструкции malloc, и нет возможности реализовать malloc один истинный способ, поскольку вам нужно сделать компромисс между скоростью, накладными расходами и избегать эффективности фрагментации/пространства. Например, если в ведре заканчиваются элементы, реализация может получить элемент из большего ведра, разбить его и добавить в ведро, которое закончилось из элементов. Это было бы достаточно пространственно эффективным, но было бы невозможно с каждым дизайном. Если вы просто получите еще один ковш через sbrk/mmap, который может быть быстрее и проще, но не как пространство эффективно. Кроме того, дизайн должен, конечно, учитывать, что "свободный" должен сделать пространство доступным для malloc снова каким-то образом. Вы не просто раздаете память без повторного использования.

Если вам интересно, прокси-сервер OpenSER/Kamailio SIP имеет две реализации malloc (им нужно их собственное, потому что они активно используют общую память, а система malloc не поддерживает разделяемую память). См.: https://github.com/OpenSIPS/opensips/tree/master/mem

Тогда вы могли бы также взглянуть на GNU libc malloc реализация, но это очень сложно, IIRC.

Ответ 2

Упрощенно malloc и свободная работа:

malloc обеспечивает доступ к куче процесса. Куча представляет собой конструкцию в основной библиотеке C (обычно libc), которая позволяет объектам получать эксклюзивный доступ к некоторому пространству в куче процесса.

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

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

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

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

Как и следовало ожидать, куча может быть фрагментирована, и менеджер кучи может время от времени пытаться объединить соседние ячейки кучи.

Если в свободном списке нет памяти для требуемого выделения, malloc вызывает brk или sbrk, которые являются системными вызовами, запрашивающими больше страниц памяти из операционной системы.

Теперь есть несколько модификаций для оптимизации операций кучи.

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

Ответ 3

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