Класс allocator
Шаблон класса описывает объект, который управляет выделением и освобождением памяти для массивов объектов типа Type . Объект класса allocator является объектом распределителя по умолчанию, указанным в конструкторах для нескольких шаблонов классов контейнеров в стандартной библиотеке C++.
Синтаксис
Параметры
Type
Тип объекта, для которого выполняется выделение и освобождение памяти.
Комментарии
Все контейнеры стандартной библиотеки C++ имеют параметр шаблона, который по умолчанию имеет значение allocator . Создание контейнера с пользовательским распределителем дает возможность управлять выделением и освобождением памяти для элементов контейнера.
Например, объект распределителя может выделить память в закрытой куче или в общей памяти. Он также может выполнить оптимизацию для крупных или мелких объектов. Он может также указывать, посредством определения типов, которые он предоставляет, что доступ к элементам возможен только через специальные объекты метода доступа, управляющие общей памятью или выполняющие автоматическую сборку мусора. Таким образом, класс, который выделяет память с использованием объекта распределителя, должен использовать эти типы для объявления указателя и объектов ссылок, как это делают контейнеры в библиотеке стандартов C++.
(Только C++ 98/03) При наследовании от класса распределителя необходимо предоставить структуру повторной привязки , typedef которой ссылается на вновь производный класс.
Таким образом, распределитель определяет следующие типы:
указатель ведет себя как указатель на .
const_pointer ведет себя как Константный указатель на .
ссылка ведет себя как ссылка на .
const_reference ведет себя как Константная ссылка на .
Они Type указывают форму, которую должны принимать указатели и ссылки для выделенных элементов. ( распределитель::p оинтер не обязательно такой же, как и для всех объектов распределителя, хотя он имеет это очевидное определение для класса allocator .)
C++ 11 и более поздних версий: Чтобы включить операции перемещения в распределителье, используйте интерфейс минимального распределителя и реализуйте конструктор копий, = = и! = операторы, выделение и освобождение. Дополнительные сведения и пример см. в статье Распределители.
Члены
Конструкторы
| Имя | Описание |
|---|---|
| allocator | Конструкторы, используемые для создания объектов allocator . |
Определения типов
| Имя | Описание |
|---|---|
| const_pointer | Тип, предоставляющий постоянный указатель на тип объекта, управляемого распределителем. |
| const_reference | Тип, предоставляющий постоянную ссылку на тип объекта, управляемого распределителем. |
| difference_type | Тип целого числа со знаком, который может представлять разницу между значениями указателей на тип объекта, управляемого распределителем. |
| вид | Тип, предоставляющий указатель на тип объекта, управляемого распределителем. |
| reference | Тип, предоставляющий ссылку на тип объекта, управляемого распределителем. |
| size_type | Целочисленный тип без знака, который может представлять длину любой последовательности, которую allocator может выделить объект типа. |
| value_type | Тип, управляемый распределителем. |
Функции
| Имя | Описание |
|---|---|
| address | Находит адрес объекта, значение которого задано. |
| allocate | Выделяет блок памяти, достаточный для хранения по крайней мере некоторого указанного числа элементов. |
| создания | Создает определенный тип объекта по указанному адресу, инициализированный с использованием заданного значения. |
| deallocate | Освобождает указанное число объектов из памяти, начиная с заданной позиции. |
| удаление | Вызывает деструктор объектов без освобождения памяти, в которой хранился объект. |
| max_size | Возвращает число элементов типа Type , которые могут быть выделены объектом класса allocator в пределах имеющейся свободной памяти. |
| повторно привязать | Структура, позволяющая распределителю, предназначенному для объектов одного типа, выделять память для объектов другого типа. |
Операторы
| Имя | Описание |
|---|---|
| Оператор = | Назначает один объект allocator другому объекту allocator . |
address
Находит адрес объекта, значение которого задано.
Параметры
Val
Константное или неконстантное значение объекта, адрес которого ищется.
Возвращаемое значение
Константный или неконстантный указатель на найденный объект соответственно константного или неконстантного значения.
Комментарии
Функции элементов возвращают адрес Valв форме, которую указатели должны принимать для выделенных элементов.
Пример
allocate
Выделяет блок памяти, достаточный для хранения по крайней мере некоторого указанного числа элементов.
Параметры
count
Количество элементов, для которых необходимо выделить достаточный объем памяти.
_Hint
Константный указатель, который может помочь объекту allocator удовлетворить запрос хранилища, найдя адрес объекта, выделенного до запроса.
Возвращаемое значение
Указатель на выделенный объект или значение null, если память не была выделена.
Комментарии
Функция-член выделяет хранилище для массива элементов count типа Type , вызывая оператор New ( Type ). Она возвращает указатель на выделенный объект. Аргумент hint помогает некоторым распределителям улучшить расположение ссылок; недопустимый вариант — это адрес объекта, выделенный ранее тем же объектом allocator, который еще не был освобожден. Чтобы не предоставлять подсказок, используйте аргумент пустого указателя.
Пример
allocator
Конструкторы, используемые для создания объектов allocator.
Параметры
Правильно
Объект allocator для копирования.
Комментарии
Конструктор не выполняет никаких действий. Однако в целом объект allocator, построенный из другого объекта allocator, должен оцениваться как эквивалентный ему, и должно быть разрешено перемешивание выделения и освобождения объектов между этими двумя объектами allocator.
Пример
const_pointer
Тип, предоставляющий постоянный указатель на тип объекта, управляемого распределителем.
Комментарии
Тип указателя описывает объект, ptr который может обозначать через выражение *ptr любой объект const, который может быть выделен объектом типа allocator .
Пример
const_reference
Тип, предоставляющий постоянную ссылку на тип объекта, управляемого распределителем.
Комментарии
Ссылочный тип описывает объект, который может обозначать любой объект const, который может быть выделен объектом типа allocator .
Пример
construct
Создает определенный тип объекта по указанному адресу, инициализированный с использованием заданного значения.
Параметры
ptr
Указатель места, в котором должен создаваться объект.
Val
Значение, с которым создаваемый объект будет инициализирован.
Комментарии
Первая функция-член эквивалентна new ((void *) ptr) Type(val) .
Пример
deallocate
Освобождает указанное число объектов из памяти, начиная с заданной позиции.
Параметры
ptr
Указатель на первый объект, который должен быть освобожден из хранилища.
count
Количество объектов для освобождения из хранилища.
Комментарии
Функция-член освобождает хранилище для массива объектов счетчика типа Type , начиная с Type , путем вызова operator delete(ptr) . Указатель ptr должен быть возвращен ранее путем вызова метода allocate для объекта распределителя, который сравнивает равенство с * this, выделяя объект массива такого же размера и типа. deallocate никогда не создает исключений.
Пример
Пример использования этой функции-члена см. в разделе allocator::allocate.
удаление
Вызывает деструктор объектов без освобождения памяти, в которой хранился объект.
Параметры
ptr
Указатель, обозначающий адрес уничтожаемого объекта.
Комментарии
Функция-член уничтожает объект, обозначенный ptr, путем вызова деструктора .
Пример
difference_type
Тип целого числа со знаком, который может представлять разницу между значениями указателей на тип объекта, управляемого распределителем.
Комментарии
Тип целого числа со знаком описывает объект, который может представлять разницу между адресами любых двух элементов в последовательности, которую может выделить объект типа allocator .
Пример
max_size
Возвращает количество элементов типа Type , которые могут быть выделены объектом класса в пределах имеющейся свободной памяти.
Возвращаемое значение
Количество элементов, которые могут быть выделены.
Пример
operator=
Назначает один объект allocator другому объекту allocator.
Параметры
Правильно
Объект allocator для назначения другому такому объекту.
Возвращаемое значение
Ссылка на объект allocator
Комментарии
Оператор присваивания шаблона не выполняет никаких действий. Однако в целом объект allocator, назначенный другому объекту allocator, должен оцениваться как эквивалентный ему, и должно быть разрешено перемешивание выделения и освобождения объектов между этими двумя объектами allocator.
Пример
указатель
Тип, предоставляющий указатель на тип объекта, управляемого распределителем.
Комментарии
Тип указателя описывает объект, ptr который может обозначать через выражение ptr любой объект, который может быть выделен объектом типа allocator .
Пример
rebind
Структура, позволяющая распределителю, предназначенному для объектов одного типа, выделять память для объектов другого типа.
Параметры
иной
Тип элемента, для которого выделяется память.
Комментарии
Эту структуру удобно использовать для выделения памяти для типа, который отличается от типа элемента реализуемого контейнера.
Шаблон класса Member определяет тип other. Его единственная цель — предоставить имя типа с allocator<_Other> учетом имени типа allocator<Type> .
Например, при наличии объекта распределителя al типа A можно выделить объект типа _Other с помощью выражения:
Кроме того, можно дать имя его типу указателя, написав тип:
Пример
reference
Тип, предоставляющий ссылку на тип объекта, управляемого распределителем.
Комментарии
Ссылочный тип описывает объект, который может обозначать любой объект, который может быть выделен объектом типа allocator .
Пример
size_type
Целочисленный тип без знака, который может представлять длину любой последовательности, которую allocator может выделить объект типа.
Аллокаторы памяти
Для начала, хотелось бы сразу отметить, что если кто-то впервые слышит термины «аллокатор», «алгоритмы распределения памяти» и не понимает, для чего это все нужно, то тогда, прежде чем читать данную статью, я рекомендую ознакомиться с данным источником. В данной статье достаточно хорошо рассказывается, какие существуют проблемы в стандартных аллокаторах памяти, и для каких целей стоит использовать другие способы распределения памяти, помимо стандартных. Здесь же я буду рассказывать только о самих алгоритмах распределения, ну и, конечно же, в конце приведу реализацию одного из аллокаторов, которая может быть без проблем использована в стандартных контейнерах С++.
Основы
Концептуально выделяется пять основных операции, которые можно осуществить над аллокатором (хочется отметить, что не все аллокаторы могут явно соответствовать этому интерфейсу):
- create – создает аллокатор и отдает ему в распоряжение некоторый объем памяти;
- allocate – выделяет блок определенного размера из области памяти, которым распоряжается аллокатор;
- deallocate – освобождает определенный блок;
- free – освобождает все выделенные блоки из памяти аллокатора (память, выделенная аллокатору, не освобождается);
- destroy – уничтожает аллокатор с последующим освобождением памяти, выделенной аллокатору.
Linear Allocator
Linear Allocator, он же «линейный» — это самый простой вид аллокаторов. Идея состоит в том, чтобы сохранить указатель на начало блока памяти выделенному аллокатору, а также использовать другой указатель или числовое представление, которое необходимо будет перемещать каждый раз, когда выделение из аллокатора завершено. В этом аллокаторе внутренняя фрагментация сведена к минимуму, потому что все элементы вставляются последовательно (пространственная локальность), и единственная фрагментация между ними — выравнивание.
Дальше предлагаю рассмотреть несколько примеров, в которых будет наглядно показано в деталях, как работает данный аллокатор. Возьмем некоторый блок памяти равный 14 байтам и отдадим его в управление аллокатору. Как видно из картинки ниже, мы сохраняем указатель на начало памяти (start), а также храним два указателя, либо два числовых представления, которые содержат информацию об общем (end) и используемом (used) размерах памяти.
Представим, что в аллокатор поступил запрос на выделение 4 байт памяти. Действия аллокатора на исполнения этого запроса будут следующие:
- проверить достаточно ли памяти для выделения;
- сохранить текущий указатель used, который в дальнейшем будет отдан пользователю, как указатель на блок выделенной памяти из аллокатора;
- сместить указатель used на величину равную объему выделенного блока памяти, т.е. на 4 байта.
Дальше, например, приходит запрос на выделение 8 байт и, соответственно, действия аллокатора будут точно такими же вне зависимости от размера выделяемого блока памяти.
А вот здесь уже будет немного интереснее, например, если приходит запрос на выделение только 1 байта, и если мы не хотим выравнивать блоки в памяти (например адреса кратные 2, 4, …), то действия аллокатора останутся точно такими же.
Но, если нам нужно выделять блоки памяти с определенным выравниванием (например выравнивание адресов кратных 2), то здесь действие аллокатора немного меняется. Меняется оно не в плане реализации, а в том, что помимо самих данных равных объему одного байта, мы еще забираем и один дополнительный байт из памяти аллокатора для выравнивания, который не несет никакой смысловой нагрузки. Как раз-таки это и есть та самая возможная минимальная фрагментация памяти внутри линейного аллокатора.
Отлично, теперь самое время поговорить об освобождении памяти. Как уже отмечалось ранее, данный вид аллокоторов не поддерживает выборочное освобождение определенных блоков памяти. То есть, если провести тонкую аналогию с malloc/free, имея указатель, скажем, на 0xFFAA00, мы могли бы освободить этот блок памяти, но вот линейный аллокатор нам этого позволить не может.
Все, что мы можем сделать, это освободить всю занятую память целиком внутри аллокатора и продолжить работать с ним, как с совершенно пустым.
Pool Allocator
Идея блочного аллокатора заключается в том, что он разделяет некоторый большой участок памяти на более мелкие участки одинакового размера. По своей сути он также является очень простым аллокатором, так как, когда запрашивается выделение, он просто возвращает один из свободных участков памяти фиксированного размера, а когда запрашивается освобождение то, он просто сохраняет этот участок памяти для дальнейшего использования. Таким образом, распределение работает очень быстро, а фрагментация все еще очень мала.
Дальше, также, как и с линейным аллокатором, предлагаю рассмотреть все на примере, чтобы детальнее понять, как он работает, поэтому возьмем некоторый блок памяти равный 12 байт и отдадим его в управление аллокатору. Как видно из картинки ниже, мы сохраняем указатель на начало (start) и конец (end) памяти, которой управляет аллокатор, а также список (freeblocks) из адресов свободных блоков в аллокаторе. В качестве средства для хранения данных о том, что блок занят или свободен, можно использовать много средств, например массив из булевых значений, но я именно решил остановиться на выборе односвязного списка, так как он наиболее просто и наглядно характеризует данную концепцию (кстати, сами звенья списка можно хранить в свободных блоках памяти, тем самым убрав дополнительные расходы с памятью).
Если приходит запрос на выделение одного блока памяти, то действия аллокатора очень примитивные. Сначала он проверяет, есть ли звенья в списке свободных блоков, если их там нет, то не трудно догадаться, что память в аллокаторе уже закончилась. Если же там есть хотя бы одно звено, то он просто достает корневое или хвостовое (в данной реализации отдаются хвостовые звенья) звено списка и отдает его адрес пользователю.
Если приходит запрос на выделение нескольких блоков памяти, то аллокатор точно так же по очереди проделывает те же действия, описанные на предыдущем шаге.
Что касается освобождения блока, если приходит запрос на освобождение, то тогда аллокатор просто добавляет этот адрес в один из концов односвязного списка. Стоит отметить такой момент, что в качестве адреса блока для освобождения может прийти, например адрес, несоответствующий адресу памяти аллокатора, например 0xEFAB12, и тогда будет возможна такая ситуация, что мы в дальнейшем отдадим пользователю тот участок памяти, который нам не принадлежит (конечно же, это приведет к undefined behavior или если очень сильно повезет, то просто к краху программы). Для избегания этой возможной проблемы как раз-таки и используются begin и end, которые позволяют проверить, не ошибся ли пользователь адресом во время запроса на операцию освобождения.
Помимо выхода за пределы памяти, которой не управляет аллокатор, есть еще одна возможная проблема. Пользователь может прийти с запросом освободить совершенно любой адрес, находящийся в области памяти аллокатора, но не равный адресу начала какого-либо из блоков, допустим блока с адресом 0xFFAA07. Эта операция, конечно же, приведет к undefined behavior. Если есть необходимость дополнительно проверять, все ли правильно делает пользователь, то есть возможность это отслеживать. Для отслеживания этого существует множество решений, например хранить также адреса и занятых блоков или вообще проверять адрес на кратность размеру блоков в аллокаторе (все зависит от фантазии и от конкертной ситуации, в которой используется аллокатор).
Stack Allocator
На самом деле, это умная эволюция линейного распределителя, которая позволяет управлять памятью, как стеком. Все так же, как и раньше, мы сохраняем указатель вместе с «header» блоком (в дальнейшем будет употребляться, как заголовок) на текущий адрес памяти и перемещаем его вперед для каждого выделения. В отличие от линейного аллокатора, мы также можем переместить его назад, то есть выполнить операцию deallocate, которая линейным аллокатором не поддерживается. Как и прежде, сохраняется принцип пространственной локальности, а фрагментация все еще минимальная.
Предлагаю рассмотреть несколько примеров все с тем же блоком памяти в 14 байт. Как и с линейным аллокатором, мы точно также сохраняем указатели на начало памяти (start) и конец (end), а также указатель на конец используемой памяти (used).
Когда приходит запрос на выделение памяти, помимо выделения некоего ее объема памяти, запрашиваемого пользователем, мы еще дополнительно выделяем заголовок (пользователь с ним никак не будет взаимодействовать), в котором храним сведения о том, сколько было выделено байт (в данном примере размер заголовка составляет 2 байта). Например, если пришел запрос на выделение 2 байт, то состояние аллокатора будет точно таким же, как на рисунке ниже. Важно отметить то, что пользователю будет отдан указатель не на заголовок, а на блок, следующий сразу за заголовком, то есть в данном примере это блок с адресом 0xFFAA02.
Аналогичная ситуация будет и, например с выделением 6 байт.
А вот с освобождением все немного поинтереснее (как уже обсуждалось ранее, выделять и освобождать память мы можем только с использованием алгоритма LIFO). Для начала от указателя, который пользователь просит освободить, нужно отнять размер заголовка, после чего разыменовать значение и уже только после этого сдвинуть указатель used на размер заголовка вместе с размером блока, полученного из заголовка. Здесь так же, как и с блочным аллокатором, возможна ситуация освобождения «рандомных» блоков памяти, которая также приведет к undefined behavior. Дополнять аллокаторы дополнительными проверками или нет – дело каждого. Самое главное — не забывать об этом моменте.
Теперь, разобравшись в основах, самое время освоить что-то более серьезное.
«Примитивный стандартный аллокатор»
Дальше будет представлена реализация аллокатора, который можно будет без проблем использовать с STL. Алгоритм распределения памяти в этом аллокаторе будет схож с алгоритмом, который используется стандартным аллокатором. Хочу сразу отметить, что не претендую на полноту реализации malloc, мною были взяты лишь основные концепции из него c добавлением в некоторых местах своей логики. Все его тонкости и нюансы, конечно же, не были учтены в этой реализации…
В основе алгоритма лежит взаимодействие с «chunks» (дальше будет употреблено, как участок, в данной реализации их размер статичен и должен быть кратен четырем, а также все выделения памяти из памяти аллоктора выравниваются на размер, кратный четырем), о которых дальше и пойдет речь. В качестве примера возьмем участок c размером 16 байт. Внутри себя он будет содержать указатели на начало (start) и конец (end) памяти, указатель на максимальный блок памяти (maxblock) и множество (freeblocks), в котором будут храниться заголовки свободных блоков. Размер заголовка в данной реализации занимает 4 байта, но он может без проблем варьироваться в размере для нужных вам целей. Например, если вы точно знаете, что размер выделяемых блоков памяти будет не больше, чем максимальное числовое значение, которое можно представить в одно или двухбайтной переменной, то можно будет использовать заголовок в размере 1 или 2 байт.
При операции выделения памяти из участка, прежде всего нужно проверить, достаточно ли памяти (в данной реализации, это константная операция, мы просто сравниваем с maxblock заголовком и, если размер аллоцируемой памяти меньше, чем максимальный блок, то значит у нас достаточно памяти для этого выделения). Если памяти достаточно, то мы просто отдаем адрес памяти, следующий за заголовком, как и в стековом аллокаторе, а также удаляем прошлый заголовок из множества свободных блоков и уже только после этого добавляем туда новый заголовок, только что выделенного блока памяти. Важно отметить, что если мы аллоцировали память из максимального блока, то нам нужно будет обновить значение максимального блока.
При последующих выделениях все происходит точно также, как и на предыдущем шаге.
Но вот как только память в участке закончилась, аллокатор берет и просто создает еще один участок того же или большего размера (в данной реализации все участки одинакового размера). Стоит также следить за тем, чтобы размер возможного блока для выделения не превышал размер участка с вычетом размера заголовка.
Дальше уже в новом участке можно без проблем выделять нужные блоки памяти. Выделение памяти будет происходить по точно такому же сценарию, как и в предыдущем участке.
Теперь немного о том, почему именно в данной реализации размер участка должен быть кратен четырем. Ответ очень просто – это делается для простоты реализации и восприятия алгоритма. Так как возможна такая ситуация, что в конце участка может остаться некоторая область памяти, в которой просто на просто не поместится заголовок (пример этого продемонстрирован на следующем рисунке). Чтобы решить эту проблему, можно будет заполнять эту память дополнительным выравниваем, либо делать размер заголовка меньшим или же использовать дополнительные средства для отслеживания этой возможной проблемы, иначе эта память будет потеряна и самая главное, что в дальнейшем потерянная память сможет накапливаться!
Прежде, чем освободить память, нужно определить, в каком участке находится блок (в текущей реализации эта операция с линейной сложностью относительно общего количества участков, если подразумевается, что будет большое количество участков, то ее можно будет сделать константной, добавив в заголовок индекс участка, в котором была выделена память). В последующем операция освобождения идентична со стековым аллокатором, за исключением того, что нужно будет добавить адрес заголовка освобожденного блока во множество свободных блоков, а также обновить maxblock, если размер только что освобожденного блока больше, чем maxblock.
Важно отметить, что в данной реализации, при каждом последующем освобождении памяти происходит попытка дефрагментации в том участке из которого была освобождена память. Дефрагментация нужна для того, чтобы объединять свободные блоки в большие по размеру. Например, в данной ситуации, как на рисунке ниже, мы не сможем выделить 6 байт, пусть даже размер свободной памяти нам и позволяет это сделать, но зато фрагментация говорит нам твердое и решительное «нет»!
Операция дефрагментации очень примитивная. Суть ее заключается в том, что после операции освобождения памяти идет проверка, не свободны ли два соседних блока слева и справа от освобожденного. Если два соседствующих блока свободны, то они объединяются в один единый.
Еще хотелось бы отметить, что данная реализация будет катастрофически ужасно работать с выделением маленьких блоков памяти, например равных 1 байту. В такой ситуации мы получаем +7 лишних байт на выделение всего лишь одно байта памяти из-за того, что размер заголовка равен 4 байтам и еще плюс 3 байта для вырывания адресов, которые должны быть кратны четырем. Этим я хочу сказать, что не стоит слепо использовать какой-либо алгоритм распределения памяти, так как вместо долгожданной оптимизации иногда можно получить только лишь дополнительные затраты.
Думаю, теории будет достаточно и поэтому, как сказал Линус Торвальдс: «Болтовня ничего не стоит. Покажите мне код». Ну что ж, приступаем…
Реализация
Требования к аллокаторам приведены в стадарте С++ в главе «Allocator requirements [allocator.requirements]«. Исходя из тех требований самый примитивный интерфейс аллокатора, который может использоваться в STL, должен выглядеть примерно вот так:
Предполагается, что STL контейнеры обращаются к аллокатору не напрямую, а через шаблон std::allocator_traits, который предоставляет значения, такие как:
Отлично, с требованиями разобрались, теперь наконец приступаем к написанию аллокатора. Для начала напишем некоторый интерфейс или адаптер, на самом деле это трудно назвать и тем, и другим, поэтому пусть это будет некая «прослойка», в которой при помощи стратегий мы сможем без проблем менять алгоритм аллоцирования памяти для определенных целей:
Благодаря стратегии для распределения памяти, мы сможем делать примерно вот так:
То есть мы можем гибко менять алгоритмы распределения для необходимых целей в той или иной ситуации. Единственное требование к AllocationStrategy — у них должны быть операции allocate и deallocate.
Здесь и дальше используются стандартные контейнеры. Согласен, что будет очень много выделений из кучи. Думаю, что для тех, кто будет писать свои аллокаторы, это будет неприемлемо. В качестве альтернативы, конечно же, можно писать свои контейнеры или использовать чужие, заточенные под определенные нужды, но в данной реализации я старался как можно проще преподнести материал, поэтому мой выбор лег именно на стандартные контейнеры.
Теперь немного о том, как можно украсить использование аллокаторов вместе со стандартными контейнерами:
Можно также использовать аллокаторы и с умными указателями, но для этого придется написать небольшую прослойку:
Ну и теперь, наконец, пример использования всего этого:
Хотелось бы заострить внимание на том, что данная реализация является самой примитивной, но она может быть без проблем расширена в ту сторону, которая вам необходима, поэтому все в ваших руках!
Заключение
Спасибо за внимание, очень надеюсь, что данная статья оказалась кому-то полезной. Также желаю всем успехов в тесном взаимодействии с памятью, и самое главное, не забывать очень важные слова Дональда Кнута: «Преждевременная оптимизация — корень всех зол».
C2017/Аллокаторы
Для программиста malloc() — это функция выделения блоков памяти в программе на C. Большинство людей не знают, как оно работает. Некоторые думают, что это специальное ключевое слово языка или системный вызов.
Фактически malloc() — это не что иное, как простая функция, реализованная в стандартной библиотеке.
Аллокатор
Под аллокатором будем понимать реализацию стандартных функций работы с динамической памятью в C:
Популярные аллокаторы
- dlmalloc (расшифровывается Doug Lea malloc)
- ptmalloc2 (расшифровывается pthreads malloc) – форк предыдущего, используется в glibc
- jemalloc – используется в FreeBSD и Firefox
- tcmalloc – от Google
- аллокатор MSVC, использующий WinAPI-функции HeapAlloc/HeapFree.
Системные вызовы
В UNIX используются два системных вызова для запроса памяти у операционной системы. Аллокатор использует их для запроса памяти у ОС, а уже затем управляет этой памятью в пользовательском режиме, отдавая нужные участки на запросы malloc и пр.
- Системные вызовы работают относительно медленно (так как это переход в режим ядра), каждый раз к ним обращаться неразумно.
- ОС распределяет память страницами (по 4 КБ), на более мелкие фрагменты их разбивает аллокатор.
brk() и sbrk()
Системные вызовы brk() и sbrk() изменяют местоположение границы под названием program break, которая определяет конец сегмента данных процесса (т. е. program break — адрес окончания сегмента неинициализированных данных). Увеличение program break даёт эффект увеличения памяти процесса; уменьшение program break освобождает память.
brk() устанавливает границу в указанное значение, если это значение является разумным, система имеет достаточно памяти и процесс не превышает максимальный размер данных (см. ulimit -d и RLIMIT_DATA).
sbrk() перемещает границу на заданное число байт. Вызов sbrk() с аргументом 0 может быть использован для определения текущей границы.
С флагом MAP_ANONYMOUS эта функция позволяет выделить регион памяти заданного размера.
Это более гибкий и современный системный вызов. Так, mmap даёт возможность выделять память из многих потоков. sbrk не рекомендуют пользоваться, потому что у sbrk может быть только один пользователь.
Поэтому новые реализации malloc предпочитают mmap, например jemalloc.
Как работает malloc в glibc
Литература
Основные понятия
Арена (arena)
Структура, которая разделяется между одним или несколькими потоками, содержит ссылки на одну или несколько куч, а также связанные списки чанков в этих кучах, которые являются «свободными». Потоки, назначенные каждой арене, будут выделять память из свободных списков арены.
Куча (heap)
Непрерывная область памяти, которая подразделяется на чанки. Каждая куча принадлежит ровно одной арене.
Чанк (chunk)
Небольшой диапазон памяти, который может быть выделен приложению (передан ему во владение), освобожден приложением (возвращён обратно к glibc) или объединен с соседними чанками в более крупные диапазоны. Обратите внимание, что чанк представляет собой обёртку вокруг блока памяти, который предоставляется приложению. Каждый чанк существует в одной куче и принадлежит к одной арене.
Память
Участок адресного пространства приложения, который обычно связан с физической RAM или свопом. Для рассмотрения принципа работы аллокатора не важно, как именно ОС отображает эту виртуальную память на физическую.
Что же такое чанк?
Большой последовательный кусок памяти (куча) разделяется на чанки разных размеров.
Каждый чанк содержит метаданные о том, насколько он большой (поле размера в заголовке) и где расположены смежные чанки.
- Когда чанк используется приложением, единственными данными, которые хранятся, является размер чанка. Размер всегда делится на 8, поэтому три младших бита размера используются для хранения трёх флагов.
- Когда чанк освобождён, память, которая использовалась для данных приложения, повторно используется для дополнительной информации, связанной с ареной, такой как указатели в связанных списках, так что подходящие куски можно быстро найти и повторно использовать, когда это необходимо. Кроме того, последние байты размером в машинное слово в свободном чанке содержат копию размера (с тремя младшими битами, выставленными в нули).
Внутри библиотеки «указатель на чанк» или mchunkptr не указывает на начало чанка, но указывает на последнее слово в предыдущем чанке, то есть первое поле в mchunkptr недействительно, если вы не знаете, что предыдущий чанк свободен.
Для флагов могут использоваться три младших разряда размера чанка. Эти три флага определяются следующим образом:
- A (0x04) — Allocated Arena. Основная арена использует кучу приложения. Другие арены используют кучи, полученные с помощью mmap. Если этот бит равен 0, чанк входит в основную арену. Если этот бит равен 1, местоположение арены может быть вычислено по адресу чанка.
- M (0x02) — Mmap’d chunk. Этот кусок был выделен одним вызовом mmap и вообще не является частью кучи.
- P (0x01) — Previous chunk is in use. Если он установлен, предыдущий чанк всё ещё используется приложением, поэтому поле prev_size недействительно. Примечание: некоторые чанки, например, в fastbins (см. далее), будут иметь этот бит, несмотря на то, чанк освобождён. Этот бит на самом деле означает, что предыдущий чанк не должен рассматриваться как кандидат на слияние — он «используется» либо приложением, либо какой-либо другой логикой библиотеки.
Чтобы гарантировать, что полезная область чанка достаточно велика, чтобы вмещать служебную информацию, минимальный размер чанка составляет 4 * sizeof(void *), это 32 байта (!) на x86-64.
Общий размер чанка округляется вверх до кратного 16 байтам.
Пример
Выделяем много мелких кусочков памяти и измеряем потребление через htop.
Многопоточность
Для однопоточного приложения достаточно было бы использовать только одну кучу, которая росла бы в сторону увеличения виртуальных адресов при необходимости при помощи sbrk().
Что если у нас несколько потоков? Простое решение — блокировать кучу с помощью мьютекса так, чтобы всегда работал один поток. В древних версиях dlmalloc так и было сделано. Но такой подход приводит к низкой производительности, особенно если потоков много.
Так появилась идея дать каждому потоку свою область памяти для распределения, свои списки свободных блоков, чтобы выделение памяти осуществлялось независимо. Таким образом, различные потоки могут обращаться к различным областям памяти, не мешая друг другу.
Эти области памяти называются «аренами».
- «Основная арена» — соответствует начальной куче приложения. В коде аллокатора есть статическая переменная, указывающая на эту арену. Память для основной арены выделяется через brk().
- Дополнительные арены — создаются для уменьшения конкуренции между потоками. У каждой арены есть указатель следующую арену, то есть они связаны в список. Для дополнительных арен непрерывные области памяти, называемые кучами, выделяются с помощью mmap.
Количество дополнительных арен ограничено числом процессоров (точнее ядер) N.
- для 32-битной системы: 2N;
- для 64-битной системы: 8N.
Это означает, что приложение с многими потоками всё ещё будет испытывать коллизии, но компромисс заключается в том, что нельзя допускать большой фрагментации адресного пространства.
Каждая структура арены содержит в себе мьютекс, который используется для контроля доступа к этой арене.
Кроме того, каждый поток имеет thread-local переменную, которая запоминает, какая арена использовалась в последний раз. Если эта арена сейчас залочена, поток выберет другую доступную арену или, если её нет, создаст новую (если лимит не превышен).
Пример
Рассмотрим пример. Предположим, что многопоточное приложение (4 потока — основной поток + 3 пользовательских потока) работает на 32-битной системе, которая содержит 1 ядро. Здесь число потоков (4) больше, чем два умножить на число ядер (2). Следовательно, в таком случае какие-то арены будут использоваться из нескольких потоков.
- Когда начинает работать основной поток, вызовы malloc используют свежесозданную арену без конфликтов.
- Когда поток 1 и поток 2 в первый раз вызывают malloc, для них создается новая арена и она используется без каких-либо конфликтов. До этого момента потоки и арены имеют взаимно однозначное отображение.
- Когда поток 3 вызывает malloc в первый раз, вычисляется предел на число арен. Новую арену создавать уже нельзя, поэтому аллокатор пытается повторно использовать существующие арены (главную арену или арену 1 или арену 2).
- Повторное использование:
- Цикл по доступным аренам, на каждой итерации пытаемся захватить эту арену.
- Если удалось (допустим, главная арена захвачена), используем эту арену.
- Если прошлись по всем имеющимся аренам и свободная арена не найдена, блокируемся в ожидании освобождения арены.
Теперь, когда поток 3 вызывает malloc (второй раз), malloc попытается использовать последнюю доступную арену (основная арена). Если основная арена свободна, она используется else thread3 блокируется до тех пор, пока основная арена не освободится. Таким образом, теперь основная арена распределяется между основной нитью и потоком 3.
Арены и кучи
Итак, каждая арена располагает памятью от одной или нескольких куч — непрерывных областей памяти. Основная арена использует только одну начальную кучу программы (начиная сразу после сегмента .bss и далее до program break’а). Дополнительные арены выделяют память для своих куч через mmap, добавляя новые кучи в свой список куч, когда старые кучи израсходованы.
Куча описывается структурой типа heap_info.
Каждая арена отслеживает специальный top-чанк, который обычно является самым большим доступным чанком. Это чанк, который находится на верхней границе памяти, запрошенной у ОС.
Также арена хранит ссылку на самую недавно выделенную кучу.
Заголовок арены описывается структурой malloc_info. Память для хранения полей самой структуры обычно берётся из начальной кучи для этой арены.
Корзины
В каждой арене чанки либо используются в приложении, либо они свободны (доступны). Используемые куски не отслеживаются ареной. Свободные куски хранятся в разных списках на основе размера и истории, поэтому библиотека может быстро найти подходящие чанки для удовлетворения запросов на аллокацию.
«Корзиной» называется список (односвязный или двусвязный) свободных чанков.
Корзины бывают такими.
fastbinsY — быстрые корзины
Маленькие чанки хранятся в контейнерах согласно их размеру. Чанки, добавленные в быструю корзину (fastbin), не объединяются с соседними чанками — логика минимальна для обеспечения максимальной производительности (отсюда и название). Чанки в fastbins могут быть перемещены в другие корзины по мере необходимости. Чанки fastbin хранятся в односвязном списке, так как они имеют одинаковый размер и чанки из середины списка никогда не надо удалять. Список действует по принципу LIFO.
Всего есть 9 быстрых корзин, которые хранят чанки по 32, 48, 64, 80, 96, 112, 128, 144, 160 байт (с шагом 16).
bins — обычные корзины
Обычные корзины делятся на «маленькие» корзины, где каждый кусок имеет одинаковый размер, и «большие» корзины, где куски бывают разные. Кроме того, есть одна особая «несортированная» корзина.
Каждая обычная корзина образует уже не односвязный, а двусвязный список, так как чанки могут быть удалены из середины (например, когда они объединяются с новыми свободными чанками).
Small
Маленьких корзин всего 62, там лежат чанки с размерами 32, 48, . 1008. В каждой корзине — один размер.
Обратите внимание, что размеры тут пересекаются с размерами fast-чанков.
Large
Эти корзины могут содержать чанки, имеющие разные размеры. Для маленьких корзин вы можете брать первый чанк и просто использовать его. Для больших корзин вам нужно найти «лучший» чанк и, возможно, разбить его на два (один размер — который вам нужен, а другой — оставшийся кусок). Под лучшим понимается самый маленький подходящий по размеру чанк (best fit).
Больших корзин всего 63. Чанки в них сложены отсортированными по размеру.
- [1024, 1088) — шаг 64
- [1088, 1152) — шаг 64
- [3072, 3136) — шаг 64
- [3136, 3584) — шаг 512
Из-за необходимости найти «лучший» вариант для больших чанков, большие чанки дополнительно провязаны в двусвязный список, связывающий первый чанк каждого размера.
Unsorted
Когда освобождается fast-чанк, он складывается в соответствующую fast-корзину. Когда не-fast чанк освобождается, он обычно помещается в специальную unsorted-корзину. Чанки сортируются позже, в malloc, при выполнении некоторых условий:
- не удалось найти точно подходящий fast- или small-чанк,
- не удалось слить какой-то fast-чанк с другим свободным, чтобы получить нужный размер.
Получается, что логика сортировки реализована только в одном месте — все остальные ветви кода аллокатора просто кладут свободные чанки в эту корзину, и они будут отсортированы позже.
Top Chunk
Если идеальный чанк для запроса на malloc не найден в корзинах, чанк берётся из специального крайнего чанка арены, который называется top.
- Он не включается ни в какую корзину.
- Используется, только если нет другого подходящего чанка.
Алгоритм malloc
- Запрошенный размер модифицируется в соответствии с возможностями аллокатора на данной платформе. Так, на 64-битных системах к размеру будет добавлено 8 байт (они нужны для поля размера чанка и флагов), а затем выполнено округление вверх до числа, кратного 16 байтам. Кроме того, минимальный размер чанка составляет 32 байта.
- Если просят достаточно много памяти (по умолчанию порог 128 КиБ), для запроса памяти непосредственно у операционной системы используется системный вызов mmap(). Обратите внимание, что в текущей версии glibc порог является динамическим, и может существовать ограничение на количество таких маппингов.
- Если в соответствующей fast-корзине есть чанк нужного размера, извлечь его из списка и вернуть его.
- Если в соответствующей small-корзине есть чанк, вернуть его.
- Если запрошен достаточно большой блок (от 1024), то делается «консолидация». Выполняется проход по всем fast-чанкам, для каждого чанка анализируются его соседние (по расположению в памяти, а не по fast-корзине). Если возможно, выполняется объединение чанков, результирующий добавляется в unsorted-корзину.
- Выполнить проход по unsorted-чанками, раскладывая их по small- и large-корзинам и выполняя объединения. Если будет найден чанк нужного размера, вернуть его. Обратите внимание, что это единственное место алгоритма, где чанки попадают в small- и large-корзины.
- Если запрос «большой», найти соответствующую большую корзину и последующие большие корзины, пока не будет найден достаточно большой чанк.
- Для маленьких запросов, если всё ещё есть быстрые чанки, сделать «консолидацию» снова и повторить предыдущие два шага.
- Наконец, обратиться к top-чанку и отрезать от него часть.
Алгоритм free
Обратите внимание, что, вообще говоря, «освобождение» памяти фактически не возвращает её в операционную систему для использования другими приложениями. Вызов free() отмечает чанк памяти как «свободный для повторного использования» приложением, но с точки зрения операционной системы память все еще «принадлежит» приложению. Однако, если top-чанк в куче — участок, смежный с неиспользованным (unmapped) адресным пространством — становится достаточно большим, часть этой памяти может быть возвращена операционной системе.