Что такое аллокатор c

Что за зверь — Allocator?

Заметил, что vector можно создавать, используя некий «аллокатор». Задался вопросом, пошёл в интернет. Но по запросам, которые, казалось бы, должны давать ответ, я получил лишь сухие статьи, а стаковерфлоу показывает мне вопросы типа «как написать аллокатор» и т.д.

Все, что я понял — это то, что аллокатор используется для управления памятью. Можно написать свой, который будет управлять ей как-то по-умному.

А в чем тогда суть? Что, я могу, к примеру, написать аллокатор, который будет выделять память не последовательно, а кусочками в разных уголках памяти? И если я создам вектор с таким аллокатором, то почему в справке по контейнеру vector написано, что, мол, он хранит все данные последовательно и непрерывно в памяти? Или я чего-то не понимаю? Единственное, что я, кажется, понял — так это то, что стандартный аллокатор выделяет память через оператор new , используя стандартный конструктор, что «не особо эффективно, учитывая, что не всегда нужно инициализировать все объекты, под которые мы выделяем место».

Так для чего же на самом деле нужны аллокаторы? Можно объяснить как-то кратко и на пальцах, почему и зачем?

Name already in use

notes / cpp / allocators.md

• Go to file T
• Go to line L
• Copy path
• Copy permalink

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Работать с памятью напрямую через операторы new, delete не принято. Принято выполнять все подобные операции через класс-прослойку под названием аллокатор.

Что такое аллокатор?

Аллокатор — это шаблонный класс, предназначенный для выделения и удаления памяти под объекты данного типа.

Аллокатор должен представлять два метода: allocate, deallocate .

allocate принимает параметр n — кол-во штук объектов, на которые надо выделить память, а deallocate принимает указатель и по историческим причинам ещё параметр size_t (позже разберёмся, что за он).

Стандартный аллокатор( std::allocator<T> ) — просто прослойка, чтобы напрямую не писать new .

В большинстве контейнеров в шаблоне вы могли видеть аллокатор как параметр, т.е. его можно подменить своей реализацией с указанными методами.

Зачем это может быть нужно?

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

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

Приведём примерную реализацию стандартного аллокатора:

В принципе это почти все нужные методы для аллокатора, но на данном этапе мы только выделяем память, а надо бы ещё вызывать конструктор. Т.к. контейнер напрямую не может работать с new , то у аллокатора ещё может быть метод construct :

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

Также стоит отметить, что реализация метода construct (как и destroy ) необязательна. И если вы не напишете его, контейнер некоторым образом проверит, реализован ли данный метод, и если нет, вызовет стандартный. Этим занимается std::allocator_traits с помощью техники SFINAE.

По аналогии есть метод destroy :

1. С точки зрения стандартного аллокатора все эти методы можно пометить const .

1. В аллокаторе должен быть определён value_type :

Это нужно, чтобы пользователь аллокатора мог узнать, от чего данный аллокатор. Множество других typedef’ов реализует std::allocator_traits .

Мы рассмотрели 4 метода аллокаторов, 2 из которых обязательны, а 2 нет. Однако с С++17 construct и destroy у стандартного аллокатора уже не реализованы, т.к. они реализованы на ещё одном уровне прослойки, которая занимается тем, чтобы дореализовывать методы за аллокатором, которые нереализованны в нём самом.

Что такое traits в С++? Это такой класс, который содержит определение вещей для какого-то метатипа. Т.е. allocator traits — это такая «штука», которая определяет за аллокатор всё то, что он не доопределил.

Давайте улучшим push_back .

Помним, что у вектора есть шаблонный параметр Alloc alloc (а также нужные поля size_t size, capacity; T* arr .

Что делать с аллокатором, если мы хотим скопировать, например, вектор?

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

В случае кастомного аллокатора копирование может быть нетривиальным. Например что делать, если аллокатор выделяет огромный пулл памяти заранее, а потом как-то выдаёт небольшими кусками? Как тут стоит поступить: выделять такой же пулл или просто давать один пулл обоим аллокаторам. И вот чтобы различать копирование аллокатора и контейнера на аллокаторе существует вот такая методология. Иногда мы не хотим копировать весь аллокатор, копируя контейнер, ведь может нам нужна та же сущность аллокатора, что бы на ней же выделять память. И вот чтобы решить в момент копирования контейнера, хотим ли мы копировать ещё и аллокатор, существует такой метод, который должен быть определён у аллокатора, который либо возвращает копию аллокатора, либо ссылку на изначальный. Т.е. в момент копирования вектора аллокатор инициализируется не alloc(other.alloc) , а alloc(alloc.select_on_container_copy_construction()) . И стоит понимать, что аллокатор не обязан определять этот метод, тогда вызов делается так:

И если метод неопределён, то аллокатор будет просто скопирован.

Предположим, что мы пишем свой std::list , который хранит int . И соответственно отдаём ему allocator<int> . Но list же не хранит числа, он хранит ноды, а аллокатор у нас создан для чисел. Что делать?

На самом деле allocator может предоставлять typedef под названием rebind . Т.е. имея аллокатор, мы можем захотеть получить точно такой же аллокатор, но для другого типа. И можем написать:

Это нужно для того, когда кто-то пользуется вашим аллокатором, мог попросить allocator::rebind<U>::other . Опять же можно не определять, и allocator_traits это доопределит.

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) адресным пространством — становится достаточно большим, часть этой памяти может быть возвращена операционной системе.

  Аллокаторы памяти

  Для начала, хотелось бы сразу отметить, что если кто-то впервые слышит термины «аллокатор», «алгоритмы распределения памяти» и не понимает, для чего это все нужно, то тогда, прежде чем читать данную статью, я рекомендую ознакомиться с данным источником. В данной статье достаточно хорошо рассказывается, какие существуют проблемы в стандартных аллокаторах памяти, и для каких целей стоит использовать другие способы распределения памяти, помимо стандартных. Здесь же я буду рассказывать только о самих алгоритмах распределения, ну и, конечно же, в конце приведу реализацию одного из аллокаторов, которая может быть без проблем использована в стандартных контейнерах С++.

  Основы

  Концептуально выделяется пять основных операции, которые можно осуществить над аллокатором (хочется отметить, что не все аллокаторы могут явно соответствовать этому интерфейсу):

  • 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.

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

  Теперь немного о том, как можно украсить использование аллокаторов вместе со стандартными контейнерами:

  Можно также использовать аллокаторы и с умными указателями, но для этого придется написать небольшую прослойку:

  Ну и теперь, наконец, пример использования всего этого:

  Хотелось бы заострить внимание на том, что данная реализация является самой примитивной, но она может быть без проблем расширена в ту сторону, которая вам необходима, поэтому все в ваших руках!

  Заключение

  Спасибо за внимание, очень надеюсь, что данная статья оказалась кому-то полезной. Также желаю всем успехов в тесном взаимодействии с памятью, и самое главное, не забывать очень важные слова Дональда Кнута: «Преждевременная оптимизация — корень всех зол».

  Читать:

  Как сохранить фото в питоне