Для приложений память выделяется с помощью подсистемы malloc. Подсистема malloc - это API для управления памятью, состоящий из следующих функций:
Подсистема malloc управляет объектом логической памяти, который называется кучей. Куча - это область памяти в адресном пространстве приложения, расположенная после последнего байта данных, размещенного компилятором. Память кучи выделяется и освобождается с помощью API подсистемы malloc.
Подсистема malloc выполняет три базовые операции с памятью: выделение, освобождение и изменение размера области памяти. Для выделения памяти служат функции malloc и calloc, для освобождения - функция free, а для изменения размера - функцияrealloc. Функции mallopt и mallinfo поддерживаются для совместимости c System V. Функция mallinfo может применяться для получения информации о куче, с которой работает функция malloc, во время создания программы. С помощью функции mallopt можно освобождать память блоками, кратными размеру страницы и выровненными по границе страницы, а также отключить стандартную процедуру распределения памяти. Функция valloc аналогична malloc и поддерживается для совместимости со стандартом Berkeley.
Дополнительные сведения приведены в следующих разделах:
Адресное пространство
32-разрядных прикладных программ разделяется в системе на семь
сегментов:
Адресное пространство 64-разрядных приложений разделяется в системе на семь
сегментов:
| С 0x0000 0000 0000 0000 по 0x0000 0000 0fff ffff | Содержит ядро. |
| С 0x0000 0000 d000 0000 по 0x0000 0000 dfff ffff | Содержит информацию общей библиотеки. |
| С 0x0000 0000 e000 0000 по 0x0000 0000 efff ffff | Содержит данные ядра. |
| С 0x0000 0000 f000 0000 по 0x0000 0000 0fff ffff | Зарезервировано. |
| С 0x0000 0001 0000 0000 по 0x07ff ffff ffff ffff | Содержит текст, данные и стек прикладной программы, а также общую память и память служб mmap. |
| С 0x0800 0000 0000 0000 по 0x08ff ffff ffff ffff | Защищенные объекты. |
| С 0x0900 0000 0000 0000 по 0x09ff ffff ffff ffff | Текст и данные общей библиотеки. |
| С 0x0f00 0000 0000 0000 по 0x0fff ffff ffff ffff | Стек приложения. |
На первый байт, следующий после последнего байта данных программы, указывает переменная _edata. Подсистема malloc создает кучу при размещении первого блока данных. Функция malloc создает кучу путем перемещения указателя _edata и освобождения области памяти для кучи с помощью функции sbrk. После этого функция malloc расширяет кучу в соответствии с требованиями приложения. Размер области памяти, добавляемой при расширении кучи, задается переменной BRKINCR. Для просмотра этого значения предназначена функция mallinfo.
Куча разделяется на занятые и свободные блоки. Свободные блоки могут быть выделены приложению. При выделении блока он удаляется из пула свободных блоков, в который возвращается указатель на этот блок. При изменении размера памяти выделяется блок памяти другого размера, данные перемещаются в новый блок, а исходный блок освобождается. Выделенные блоки состоят из областей памяти кучи, связанной с приложением. Поскольку блоки памяти физически не удаляются из кучи (изменяется только их состояние со свободного на занятый), размер кучи не уменьшается при освобождении памяти приложением.
Стратегия выделения памяти связана с набором структур данных и алгоритмов, на основе которых моделируется куча и реализуются операции выделения, освобождения и изменения размера области памяти. Подсистема malloc поддерживает две стратегии выделения памяти: стандартную стратегию и стратегию, применявшуюся вплоть до версии 3.1. В обеих стратегиях выделения памяти используется один и тот же интерфейс подсистемы malloc.
Стандартная стратегия более эффективна для большинства типичных приложений. Отдельные особенности стратегии 3.1 могут дать выигрыш в ряде нестандартных ситуаций. Подробные сведения об этом приведены в разделе Различия между стандартной стратегией и стратегией 3.1. Стратегию 3.1 можно применять только с 32-разрядными приложениями. Она не работает в 64-разрядной среде.
В стандартной стратегии распределения памяти свободная память кучи представляется в виде дерева свободных блоков. Дерево свободных блоков - это двоичное дерево, узлы которого отсортированы по вертикали в соответствии с размером блоков и по горизонтали - в соответствии с адресом. Такая структура данных не накладывает ограничения на размер блоков, поддерживаемых деревом, позволяя работать с блоками любого размера. Алгоритмы реорганизации дерева позволяют оптимизировать время поиска, вставки и удаления узлов, а также решают проблему фрагментации.
В стандартной стратегии предусмотрены следующие дополнительные возможности:
С помощью функции roundup подсчитывается размер запрошенного блока в байтах. Формат:
Если x mod y = 0, то Roundup(x,y) = x иначе Roundup(x,y) = (x/y округленное вниз до ближайшего целого числа + 1)y p = sizeof(prefix)=8 pad = Roundup(len + p,16)
Из дерева удаляется самый левый узел, размер которого больше либо равен значению параметра len функции malloc. Если найденный блок больше запрошенного, его остаток выделяется в отдельный блок. Этот блок возвращается в дерево свободных блоков. Основная часть блока возвращается инициатору.
Если в дереве свободных блоков нет блока достаточного размера, куча расширяется, и блок, образованный в результате расширения, добавляется в дерево свободных блоков. После этого выполняется описанная выше операция выделения.
Блоки памяти освобождаются с помощью функции free и помещаются в корень дерева свободных блоков. Для всех узлов, расположенных в дереве выше позиции вставки нового узла, выполняется проверка, не являются ли они смежными с добавляемым блоком. Если да,то два узла объединяются, и в дерево добавляется узел для объединенного блока. Уровень, на котором будет расположен узел в дереве, зависит от его размера. Если смежные узлы не найдены, то узел просто располагается в соответствующей позиции дерева. Объединение смежных блоков позволяет значительно снизить степень фрагментации кучи.
Если размер запрошенного блока больше размера исходного блока, то исходный блок возвращается в дерево свободных блоков с помощью функции free. В результате он объединяется со всеми свободными смежными блоками. После этого выделяется новый блок запрошенного размера, данные копируются из исходного блока в новый, после чего он возвращается инициатору.
Если размер запрошенного блока меньше размера исходного блока, блок усекается, и его остаток возвращается в дерево свободных блоков.
Для применения стратегии распределения памяти 3.1 нужно выполнить следующие команды:
MALLOCTYPE=3.1; export MALLOCTYPE
После этого все 32-разрядные программы, запущенные из данной оболочки, будут применять стратегию распределения памяти 3.1 (63-разрядные по-прежнему будут пользоваться стандартной стратегией). Если переменной MALLOCTYPE будет присвоено любое другое значение, то будет применяться стандартная стратегия.
В стратегии 3.1 куча представляет собой набор из 28 хэш-блоков, каждый из которых указывает на список. Хэширование - это способ преобразования ключа поиска в адрес с целью чтения или записи элемента данных. Такой способ позволяет минимизировать среднее время поиска. Хэш-блок содержит одно или несколько полей, хранящих результат операции. Каждый список содержит блоки определенного размера. Индекс хэш-блока определяет размер блоков в связанном с ним списке. Размер блока вычисляется по следующей формуле:
size = 2i + 4
где i - это номер хэш-блока. Это означает, что нулевой хэш-блок ссылается на список из блоков 20+4= 16 байт длиной. Если предположить, что префикс занимает 8 байт, такие блоки могут применяться для запросов на область памяти размером от 0 до 8 байт. В приведенной ниже таблице показана взаимосвязь между размером запрошенной области памяти и хэш-блоками.
Примечание: Для такого алгоритма может потребоваться вдвое больше памяти, чем было запрошено приложением. Для хэш-блока размером более 4096 байт потребуется дополнительная страница, так как данные, объем которых больше либо равен странице, размещаются в блоках памяти размером со страницу. Поскольку префикс расположен непосредственно перед блоком, он займет всю страницу.
| Стратегия 3.1 | |||
| Хэш-блок | Размер блока | Диапазон запросов | Число требуемых страниц |
| 0 | 16 | 0 ... 8 |
|
| 1 | 32 | 9 ... 24 |
|
| 2 | 64 | 25 ... 56 |
|
| 3 | 128 | 57 ... 120 |
|
| 4 | 256 | 121 ... 248 |
|
| 5 | 512 | 249 ... 504 |
|
| 6 | 1 Kб | 505 ... 1 Кб - 8 |
|
| 7 | 2 Кб | 1 Кб - 7 ... 2 Кб - 8 |
|
| 8 | 4 Кб | 2 Кб - 7 ... 4 Кб - 8 | 2 |
| 9 | 8 Кб | 4 Кб-7 ... 8 Кб - 8 | 3 |
| 10 | 16 Кб | 8 Кб - 7 ... 16 Кб - 8 | 5 |
| 11 | 32 Кб | 16 Кб - 7 ... 32 Кб - 8 | 9 |
| 12 | 64 Кб | 32 Кб - 7 ... 64 Кб - 8 | 17 |
| 13 | 128 Кб | 64 Кб-7 ... 128 Кб-8 | 33 |
| 14 | 256 Кб | 128 Кб-7 ... 256 Кб-8 | 65 |
| 15 | 512 Кб | 256 Кб-7 ... 512 Кб-8 | 129 |
| 16 | 1 Мб | 256 Кб-7 ... 1 Мб-8 | 257 |
| 17 | 2 Мб | 1 Мб-7 ... 2 Мб-8 | 513 |
| 18 | 4 Мб | 2 Мб-7 ... 4 Мб-8 | 1 Кб + 1 |
| 19 | 8 Мб | 4 Мб-7 ... 8 Мб-8 | 2 Кб + 1 |
| 20 | 16 Мб | 8 Мб-7 ... 16 Мб-8 | 4 Кб + 1 |
| 21 | 32 Мб | 16 Мб-7 ... 32 Мб-8 | 8 Кб + 1 |
| 22 | 64 Мб | 32 Мб-7 ... 64 Мб-8 | 16 Кб + 1 |
| 23 | 128 Мб | 64 Мб-7 ... 128 Мб-8 | 32 Кб + 1 |
| 24 | 256 Мб | 128 Мб-7 ... 256 Мб-8 | 64 Кб + 1 |
| 25 | 512 Мб | 256 Мб-7 ... 512 Мб-8 | 128 Кб + 1 |
| 26 | 1024 Мб | 512 Мб-7 ... 1024 Мб-8 | 256 Кб + 1 |
| 27 | 2048 Мб | 1024 Мб-7 ... 2048 Мб-8 | 512 Кб + 1 |
Перед выделением блока из пула свободных блоков число запрошенных байт преобразуется в индекс массива хэш-блоков по следующей формуле:
требуется = запрошено + 8 Если требуется <= 16, то bucket = 0 Если требуется > 16, то bucket = (log(needed)/log(2) округленное вниз до ближайшего целого числа) - 3
Размер блоков в списке, на который ссылается хэш-блок, можно вычислить по формуле: размер блока = 2 хэш-блок + 4. Если список, на который ссылается хэш-блок, пустой, то в него добавляются блоки путем выделения памяти с помощью функции sbrk. Если размер блока меньше страницы, то функция sbrk выделяет страницу. При этом число блоков, добавленных в список, равно размеру страницы, поделенному на размер блока. Если размер блока больше либо равен размеру страницы, необходимый объем памяти выделяется с помощью функции sbrk, и к списку свободных блоков хэш-блока добавляется всего один блок. Если список свободных блоков не пуст, то инициатору возвращается первый блок списка. При этом указатель на начало списка связывается со следующим блоком.
При освобождении блока памяти, как и при выделении, подсчитывается индекс хэш-блока. После этого освобожденный блок добавляется в начало списка свободных блоков хэш-блока.
При изменении размера блока требуемый размер блока сравнивается с его текущим размером. Поскольку один и тот же хэш-блок применяется для выделения областей памяти различного размера, новый блок часто относится к тому же хэш-блоку, что и старый. В этом случае длина префикса обновляется в соответствии с новым размером, и инициатору запроса возвращается тот же блок. Если требуется увеличить размер блока, текущий блок освобождается и выделяется новый блок, связанный с другим хэш-блоком. При этом данные копируются из старого блока в новый.
Стратегию 3.1 можно применять только с 32-разрядными приложениями. Даже если для 64-разрядной программы будет указано значение MALLOCTYPE=3.1, для нее будет применяться стандартная стратегия.
Стратегия 3.1 не поддерживает следующие функции:
Стратегия 3.1 широко применяется в системах UNIX. Ее существенный недостаток заключается в том, что при выделении памяти размер запрошенной области округляется вверх до ближайшего числа, являющегося степенью числа 2. Это приводит к существенной фрагментации виртуальной и оперативной памяти и ряду других проблем. В стандартной стратегии отводится ровно столько памяти, сколько было запрошено, и применяются усовершенствованные средства контроля освободившихся областей памяти.
К сожалению, некоторые программы пользуются особенностями реализации стратегии 3.1, и поэтому применение другой стратегии может снизить их производительность или даже нарушить нормальную работу. Например, программа, в которой возникает выход за границы массива, может нормально работать со стратегией 3.1 только потому, что в результате округления память под этот массив будет выделена с запасом. Применение стандартной стратегии памяти с большой вероятностью нарушит работу такой программы, поскольку под массив будет выделаться ровно столько памяти, сколько запрошено.
Другой характерный пример заключается в том, что из-за особенностей алгоритма контроля освободившихся блоков памяти в стратегии 3.1 программы почти всегда получают память, в которой всем ячейкам присвоены нулевые значения (страница обнуляется при первом обращении процесса к ней). Работа некоторых программ может зависеть от этого побочного эффекта. В действительности функция malloc не обязана осуществлять обнуление памяти, и выполнение этой операции только снижает производительность программ, которые выполняют инициализацию памяти самостоятельно. Поскольку стандартная стратегия более активно использует высвободившиеся области памяти, она может нарушить работу программ, рассчитывающих на обнуление выделяемой памяти со стороны функции malloc.
Если программа регулярно увеличивает размер выделенной области памяти с помощью функции realloc, то в стратегии 3.1 с меньшей вероятностью потребуется перемещать эту область. Во многих случаях функции realloc будет достаточно "избыточной" памяти, которая была выделена с самого начала за счет округления запрошенного размера области. В стандартной стратегии в таких случаях область памяти почти всегда перемещается, потому что с большой вероятностью вся память вокруг увеличиваемой области будет занята. В таких ситуациях стратегия 3.1 будет выигрывать по производительности у стандартной стратегии. На самом деле такой выигрыш будет обеспечиваться только за счет характерных недостатков в алгоритме программы.
Адресное пространство программы - Обзор.
Требования программ к пространству подкачки.
Отображение памяти - Основные сведения.
Пользовательские аналоги функции Malloc.
Функции malloc, free, realloc, calloc, mallopt, mallinfo и alloca.