Выделение памяти в системе с помощью подсистемы malloc

Для приложений память выделяется с помощью подсистемы malloc.

Подсистема malloc - это API управления памятью, состоящий из следующих функций:

• malloc
• calloc
• realloc
• free
• mallopt
• mallinfo
• alloca
• valloc
• posix_memalign

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

Функции mallopt и mallinfo поддерживаются для совместимости c System V. Функция mallinfo может применяться для получения информации о куче, с которой работает функция malloc, во время создания программы. С помощью функции mallopt можно освобождать память блоками, кратными размеру страницы и выровненными по границе страницы, а также отключить стандартную стратегию выделения памяти. Функция valloc аналогична функции malloc и поддерживается для совместимости со стандартом Berkeley Compatibility Library.

Дополнительная информация приведена в следующих разделах:

Работа с кучей процесса

Адрес первого байта, следующего после последнего байта инициализированных данных программы, - это адрес символьной переменной _edata. Переменная _edata указывает на начало кучи процесса, увеличиваемой подсистемой malloc при размещении первого блока данных. Подсистема malloc расширяет кучу процесса, увеличивая значение brk, обозначающее конец кучи. Для этого вызывается функция sbrk. Последующие вызовы функций подсистемы malloc расширяют кучу в соответствии с требованиями приложения.

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

Адресное пространство 32-разрядных приложений

Адресное пространство 32-разрядных прикладных программ разделяется в системе на следующие сегменты:

Адресное пространство процесса 64-разрядных приложений

Адресное пространство 64-разрядных прикладных программ разделяется в системе на следующие сегменты:

Описание стратегии выделения памяти в системе

Стратегия выделения памяти связана с набором структур данных и алгоритмов, на основе которых моделируется куча и реализуются операции выделения, освобождения и изменения размера области памяти. Подсистема malloc поддерживает следующие стратегии выделения памяти: стратегия по умолчанию, стратегия watson, стратегия malloc 3.1 и пользовательская стратегия. API доступа к подсистеме malloc не зависит от стратегии; меняется только реализация стратегии.

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

Некоторые опции стратегии выделения памяти можно использовать совместно с другими опциями. Для этого при задании переменных среды MALLOCOPTIONS и MALLOCDEBUG опции следует указывать, разделяя их запятыми.

MALLOCALIGN=16;  export MALLOCALIGN

Кроме того, программа с помощью процедуры mallopt(M_MALIGN, 16) можно изменить значение malloc() по умолчанию, применив 16-байтовое выравнивание. Процедура mallopt(M_MALIGN) позволяет программе управлять операциями выделения памяти malloc по умолчанию в динамическом режиме.

Описание стандартной стратегии выделения памяти

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

В стандартной стратегии предусмотрены следующие дополнительные возможности:

Выделение

Обслуживание любых операций выделения памяти требует дополнительных затрат. Они обусловлены необходимостью создавать префикс метаданных и выравнивать блоки памяти по границе. Для любой операции размещения размер префикса метаданных составляет 8 и 16 байт для 32- и 64-разрядных программ соответственно. Фрагменты памяти выравниваются по границе 16 или 32 байт. Отсюда общая память, расходуемая при выделении области памяти размером n байт составляет:

размер = округление_вверх(n + размер_префикса, выравнивание)

Например, для размещения 37 байт 32-разрядной программой потребуется округление_вверх(37 + 8, 16), то есть 48 байт.

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

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

Освобождение

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

Изменение размера

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

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

Ограничения

Описание стратегии выделения памяти watson

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

Выделение

Дополнительные затраты стратегии выделения памяти Watson такие же, как у стратегии выделения памяти по умолчанию.

В дереве размера ищется блок наименьшего размера, но не меньший, чем размер запрошенной области памяти. Затем этот блок удаляется из дерева размера. Если найденный блок больше запрошенного, то он делится на два блока: второй блок - запрошенного размера, а первый - остаток - выделяется в отдельный блок. Первый блок runt возвращается в дерево размера. Второй блок передается инициатору. Если размер блока в дереве размера в точности соответствует запросу, то блок удаляется из обоих деревьев и передается инициатору.

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

Освобождение

Блоки памяти освобождаются с помощью функции free и помещаются в корень дерева адресов. Для всех узлов, расположенных в дереве выше позиции вставки нового узла, выполняется проверка, не являются ли они смежными с добавляемым блоком. Если да, то два узла объединяются, и в дерево размера добавляется узел, соответствующий объединенному блоку. Если смежные блоки не найдены, то узел просто размещается в соответствующей позиции деревьев размера и адресов.

После вставки в обоих деревьях проводится проверка правильности структуры.

Изменение размера

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

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

Ограничения

Описание стратегии выделения памяти malloc версии 3.1

Для применения стратегии выделения памяти malloc 3.1 следует перед запуском процесса указать значение MALLOCTYPE=3.1. В результате все 32-разрядные программы, запущенные из данной оболочки, будут применять стратегию выделения памяти malloc 3.1 (63-разрядные по-прежнему будут использовать стандартную стратегию).

size = 2 i + 4

Выделение

Перед выделением блока из пула свободных блоков число запрошенных байт преобразуется в индекс массива хэш-блоков по следующей формуле:

требуется = запрошено + 8

Если требуется <= 16,
то
bucket = 0

Если требуется > 16,
то
bucket =
(log(требуется)/log(2) округленное в
меньшую сторону до ближайшего целого числа) - 3

Размер блоков в списке, на который ссылается хэш-блок, можно вычислить по формуле: размер блока = 2 ^{хэш-блок + 4}. Если список, на который ссылается хэш-блок, пустой, то в него добавляются блоки путем выделения памяти с помощью функции sbrk. Если размер блока меньше страницы, то функция sbrk выделяет страницу. При этом число блоков, добавленных в список, равно размеру страницы, поделенному на размер блока. Если размер блока больше либо равен размеру страницы, необходимый объем памяти выделяется с помощью функции sbrk, и к списку свободных блоков хэш-блока добавляется всего один блок. Если список свободных блоков не пуст, то инициатору возвращается первый блок списка. При этом указатель на начало списка связывается со следующим блоком.

Освобождение

При освобождении блока памяти, как и при выделении, подсчитывается индекс хэш-блока. После этого освобожденный блок добавляется в начало списка свободных блоков хэш-блока.

Изменение размера

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

Ограничения

Настройка MALLOCTYPE=3.1 только включит стратегию malloc 3.1 для 32-разрядных программ. Для того чтобы 64-разрядные программы использовали стратегию malloc 3.1 переменной среды MALLOCTYPE должно быть явно задано значение MALLOCTYPE=3.1_64BIT. Данная стратегия размещения менее эффективна, чем стандартная, и в большинстве случаев не рекомендуется.

Ниже перечислены доступные опции стратегии выделения памяти malloc 3.1:

• Опция malloc Disclaim
• Описание опции no_overwrite

Описание стратегии выделения пулов

Пул Malloc - это высокопроизводительная команда-клиент функций libc malloc, calloc, free, posix_memalign и realloc для управления объектами хранения меньше, чем 513 байт. Быстродействие достигается за счет значительно более коротких путей и лучшего использования кэша данных. Есть также дополнительное преимущество для приложений со многими нитями. Оно состоит в том, что метки локальных пулов нитей используются вместо атомарных операций. Данную команду-клиент можно использовать вместе с любой из схем управления хранением, предоставляемой в настоящий момент в libc (yorktown и watson).

export MALLOCOPTIONS=pool<:max_size>

При указании этой опции при инициализации malloc создается набор пулов, в котором каждый пул - это связанный список объектов фиксированного размера. Самый маленький пул может содержать объекты, имеющие размер указателей (например, 8 байт для 32-разрядных приложений или 16 байт для 64-разрядных). Последующие пулы содержит объекты, имеющие размер больше на величину размера указателя. Это означает, что есть 128 пулов для 32-разрядных приложений и 64 пула для 64-разрядных приложений. Набор пулов представлен как массив указателей, которые "отмечают" связанные списки.

Пул Malloc использует свою собственную память - кучу пула, которая не используется совместно со стандартным malloc. Если указана опция max_size, то она округляется до ближайшего большего значения с шагом 2 МБ и используется для управления размером кучи пула. Опцию max_size можно указывать как десятичное или шестнадцатеричный число, перед которым указано 0x или 0X (например, export MALLOCOPTIONS=pool:0x1700000 приравняет max_size к 24 МБ после округления.

Для 32-разрядных приложений размер кучи пула начинается с 2 МБ. Если требуется дополнительное пространство для хранения и общий размер хранилища кучи пула меньше, чем max_size, то добавляется 2 МБ. Зоны 2 МБ не должны соседствовать друг с другом. Для 64-разрядных приложений размещается одна куча пула, размером max_size во время инициализации malloc. Ее размер не увеличивается. Если max_size не указан, он равен 512 МБ для 32-разрядных приложений и 32 МБ для 64-разрядных. Для 32- и 64-разрядных режимов max_size будет равен 512 МБ, если задан больший размер. В 32-разрядном режиме в переменной max_size указывается значение 512 МБ, а в 64-разрядном режиме - значение 3.7 ГБ, если задан больший размер.

Использование хранилища

Все метки пула первоначально пусты или равняются NULL. При обработке запроса к пулу malloc в случае, если соответствующий пул пуст, вызывается процедура, которая размещает данные кучи пула в смежном куске, размером 1024 байт на границе 1024 байт. "Создаются" множественные объекты требуемого размера. Адрес первого возвращается как ответ на запрос, а остальные объекты соединены вместе и расположены на метке пула. Для каждого куска программы длинной 1024 байт в дополнительный таблице есть запись, размером 2 байта, используемая функцией free для определения размера возвращаемого объекта.

Когда объект освобождается пулом malloc он "вталкивается" в соответствующую метку пула. Попыток объединить блоки для создания объектов большего размера не делается.

Вследствие данного поведения, пул malloc может использовать больше места для хранения, чем другие формы malloc.

Выравнивание

Стандартное выравнивание для функций malloc(), calloc() и realloc() должно быть задано с помощью переменных среды MALLOCALIGN. Функция posix_memalign() работает, даже если не задана переменная среды MALLOCALIGN. Если MALLOCALIGN больше 512, пул malloc не используется.

Эффективность кэша

Объекты памяти, размещенные в пуле malloc не имеют приставок и суффиксов. Линии данных кэша более плотно упакованы данными приложений. Так как размер всех объектов памяти выровнен по значению 2, каждый объект содержится в минимальном количестве линий кэша. Функции malloc и free не сканируют деревья или связанные списки и, поэтому, не “загрязняют” кэш.

Поддержка нескольких нитей

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

Поддержка распределения нагрузки

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

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

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

export MALLOCOPTIONS=pool:0x80000000,pool_balanced

export MALLOCFREEPOOL=min_size<-max_size>:threshold_value<,min_size<-max_size>:
threshold_value, ... >,default:threshold

export MALLOCFREEPOOL=0-16:256,32:512,default:128

Поддержка отладки

Не существует версии отладки данной высокопроизводительного команды-клиента. Если задана переменная среды MALLOCDEBUG, опция пула игнорируется. Подразумевается, что приложения будут отлаживаться с помощью "нормального" malloc до активации использования пула.

Описание пользовательской стратегии выделения памяти

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

Описание опции no_overwrite

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

Для отключения этой функции оптимизации задайте перед запуском процесса MALLOCOPTIONS=no_overwrite.

Сравнение различных стратегий выделения памяти

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

Различия между стандартной стратегией и стратегией malloc 3.1

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

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

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

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

Отладка ошибок приложений в управлении кучей

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

Сводная таблица переменных среды и параметров malloc

Описание стратегии выделения памяти Watson2

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

Выделение

Выделение управляется посредством комбинации механизмов. Эти механизмы зависят от параметров, таких как число активных нитей, размер запроса и хронология освобождения ресурсов для процесса. Набор механизмов происходит от кэширования для нитей и использует переменное число куч, имеющих привязку нити к структуре Double-red-black и объединение на основе страниц.

Освобождение

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

Изменение размера

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

Ограничения

Подсистема malloc Watson2 является адаптивной к приложениям и не требует дополнительных опций, но подсистема malloc Watson2 поддерживает следующие функции отладки, управляемые переменной MALLOCDEBUG: validate_ptrs, report_allocations и trace. Относящиеся к выделениям отчеты могут быть перенаправлены в файл с помощью опции output:<имя_файла>. Более подробная информация о переменной MALLOCDEBUG находится в разделе Отладчик malloc.