Как malloc () реализована внутри? [duplicate]
На этот вопрос уже есть ответ:
- Как сделать malloc () и free () work? 13 ответов
Кто-нибудь может объяснить, как malloc () работает внутри?
Я иногда делал программу strace и вижу Многие системные вызовы sbrk , в которых man sbrk говорит о том, что он используется в malloc () , но не намного.
2 ответа
Системный вызов sbrkперемещает "границу" сегмента данных. Это означает, что он перемещает границу области, в которой программа может читать/записывать данные (позволяя им увеличиваться или уменьшаться, хотя AFAIK ни один malloc не возвращает сегменты памяти ядру этим методом). Кроме того, есть еще mmap, который используется для отображения файлов в память, но также используется для выделения памяти (если вам нужно выделить общую память, mmap - это то, как вы это делаете).
Таким образом, у вас есть два способа получить больше памяти от ядра: sbrk и mmap. Существуют различные стратегии того, как организовать память, полученную от ядра.
Один из наивных способов - разделить ее на зоны, часто называемые "ведрами", которые отводятся под определенные размеры структур. Например, реализация malloc может создать ведра для 16, 64, 256 и 1024 байтовых структур. Если вы попросите malloc предоставить вам память заданного размера, он округлит это число до следующего размера ведра и затем предоставит вам элемент из этого ведра. Если вам нужна область большего размера, malloc может использовать mmap для выделения непосредственно ядром. Если ведро определенного размера пусто, malloc может использовать sbrk, чтобы получить больше места для нового ведра.
Существуют различные конструкции malloc, и, вероятно, нет единственно верного способа реализации malloc, поскольку вам нужно найти компромисс между скоростью, накладными расходами и избеганием фрагментации/эффективностью использования пространства. Например, если в ведре закончились элементы, реализация может получить элемент из большего ведра, разделить его и добавить в ведро, в котором закончились элементы. Это было бы достаточно эффективно с точки зрения экономии места, но это возможно не для каждого проекта. Если просто получить другое ведро через sbrk/mmap, это может быть быстрее и даже проще, но не так эффективно с точки зрения экономии места. Кроме того, при проектировании, конечно, нужно учитывать, что "free" должен как-то освободить место для malloc. Вы не можете просто раздать память, не используя ее повторно.
Если вам интересно, OpenSER/Kamailio SIP proxy имеет две реализации 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 байт, куча менеджер может сразу перейти к ОС и выделить полную страницу памяти.
- Куча может указать минимальный размер распределение для предотвращения больших сумм фрагментации.
- Куча также может делиться на ячейки: одна для небольших выделений, а другая - для более крупных, чтобы быстрее выполнять большие выделения.
- Существуют также умные механизмы для оптимизации распределения многопоточной кучи.