Статья Выделение памяти (Memory Allocation)

[baykal]

Оригинальная статья https://samwho.dev/memory-allocation/
Перевод baykal
Специально для xss.pro


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

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

# malloc и free​

Чтобы понять работу распределителя памяти, необходимо понять, как программы запрашивают и возвращают память. malloc и free - это функции, впервые представленные в узнаваемой форме в UNIX v7 в 1979(!). Давайте взглянем на короткую программу на C, демонстрирующую их использование.

Если вы знакомы с другим языком, например JavaScript, Python или C#, на начальном уровне, у вас не должно возникнуть проблем. Вам не нужно понимать каждое слово, если вы понимаете общую идею. Я обещаю, что это единственный код C в статье.

#include <stdlib.h>

int main() {
  void *ptr = malloc(4);
  free(ptr);
  return 0;
}

В приведенной выше программе мы запрашиваем 4 байта памяти, вызывая malloc(4), мы сохраняем возвращаемое значение в переменной с именем ptr, затем мы указываем, что мы закончили с памятью, вызывая free(ptr).

Эти две функции позволяют почти всем программам управлять используемой ими памятью. Даже если вы не пишете C, код, выполняющий ваши Java, Python, Ruby, JavaScript и т. д., использует malloc и free.

# Что такое память?​

Наименьшая единица памяти, с которой работают распределители, называется «байт». В байте может храниться любое число от 0 до 255. Вы можете думать о памяти как о длинной последовательности байтов. Мы собираемся представить эту последовательность в виде сетки квадратов, где каждый квадрат представляет собой байт памяти.

В предыдущем коде C malloc(4) выделяет 4 байта памяти. Мы собираемся представить выделенную память более темными квадратами.

Затем free(ptr) сообщает распределителю, что мы закончили с этой памятью. Он возвращается обратно в пул доступной памяти.

Подождите секунду... Что mallocна самом деле возвращается как значение? Что значит «дать» память программе?

То, что malloc возвращается, называется «указателем» или «адресом памяти». Это число, которое идентифицирует байт в памяти. Обычно мы записываем адреса в форме, называемой «шестнадцатеричной». Шестнадцатеричные числа записываются с 0x префиксом, чтобы отличить их от десятичных чисел. Переместите ползунок ниже, чтобы увидеть сравнение десятичных и шестнадцатеричных чисел.

Вот наша знакомая сетка памяти. Каждый байт аннотируется своим адресом в шестнадцатеричной форме. Из соображений экономии места я опустил 0x префикс.

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

# Самый простой malloc​

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

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

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

# Самый простой универсальный malloc​

Для того, чтобы free память, мы должны лучше отслеживать память. Мы можем сделать это, сохранив адрес и размер всех аллокаций, а также адрес и размер блоков свободной памяти. Мы будем называть их «allocation list» и «free list» соответственно.

Мы представляем записи free list в виде двух серых квадратов, соединенных линией. Вы можете представить, что эта запись представлена в коде как address=0 и size=32. Когда наша программа запускается, вся память помечается как свободная. Когда malloc вызывается, мы просматриваем наш free list, пока не найдем достаточно большой блок, чтобы вместить его. Когда мы находим его, мы сохраняем адрес и размер выделения в нашем allocation list'e и соответствующим образом уменьшаем запись в free list.

Где мы сохраняем allocation\free list? Разве мы не притворяемся, что наш компьютер имеет только 32 байта памяти?

Ты поймал меня. Одним из преимуществ распределителя памяти является то, что вы отвечаете за память. Вы можете сохранить свой allocation/free list в зарезервированной области, предназначенной только для вас. Или вы можете хранить его в строке, в нескольких байтах, непосредственно предшествующих каждому выделению. А пока предположим, что мы зарезервировали часть невидимой памяти для себя и используем ее для хранения allocation list и free list.

Так что насчет free? Поскольку мы сохранили адрес и размер выделения в нашем allocation list, мы можем выполнить поиск в этом списке и переместить выделение обратно в free list. Без информации о размере мы бы не смогли этого сделать.

Мы выделили 8 блоков памяти, каждый размером 4 байта. Затем мы free сделали их все, в результате чего в списке осталось 8 свободных записей. Проблема, которая у нас есть сейчас, заключается в том, что если мы попытаемся сделать malloc(8), в нашем free list'e нет элементов, которые могут содержать 8 байтов, и это malloc(8) не удастся.

Чтобы решить эту проблему, нам нужно проделать еще немного работы. Когда мы free запоминаем, мы должны убедиться, что если блок, который мы возвращаем в free list, находится рядом с любыми другими свободными блоками, мы объединяем их вместе. Это называется «слияние».

# Фрагментация​

Идеально составленный free list не решает всех наших проблем. В следующем примере показана более длинная последовательность выделений. Посмотрите на состояние памяти в конце.

Мы заканчиваем эту последовательность, когда 6 из наших 32 байтов свободны, но они разбиты на 2 блока по 3 байта. Если бы нам пришлось обслуживать a malloc(6), пока у нас теоретически достаточно свободной памяти, мы бы не смогли этого сделать. Это называется «фрагментация».

Не могли бы мы перераспределить память, чтобы получить блок из 6 непрерывных байтов? Какой-то процесс дефрагментации?

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

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

Один из способов борьбы с фрагментацией — это, как ни странно, чрезмерное выделение ресурсов. Если мы всегда выделяем минимум 4 байта, даже когда запрос на 1 байт, смотрите, что происходит. Это точно такая же последовательность распределений, что и выше.

Теперь мы можем обслуживать malloc(6). Стоит иметь в виду, что это всего лишь один пример. Программы будут вызывать malloc и free по очень разным шаблонам в зависимости от того, что они делают, что усложняет разработку распределителя, который всегда работает хорошо.

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

Нет, это побочный эффект чрезмерного распределения. Визуализация показывает «истинное» использование памяти, тогда как free list обновляется с точки зрения распределителя. Поэтому, когда происходит первое malloc, выделяется 1 байт памяти, но запись в free list перемещается вперед на 4 байта. Мы обмениваем неиспользуемое пространство на меньшую фрагментацию.

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

Еще один способ борьбы с фрагментацией — разделение памяти на пространство для небольших выделений и пространство для больших. В этой следующей визуализации мы начинаем с двух free list. Светло-серый — для выделений размером 3 байта или меньше, а темно-серый — для выделений размером 4 байта или больше. Опять же, это та же самая последовательность распределений, что и раньше.

Круто! Это также уменьшает фрагментацию. Если мы строго разрешаем выделять только 3 байта или меньше в первом сегменте, то мы не можем обслуживать это malloc(6). Компромисс здесь заключается в том, что резервирование сегмента памяти для меньших выделений дает вам меньше памяти для работы с большими.

Эй, первое выделение в темно-сером свободном списке — 3 байта! Вы сказали, что это для распределения 4 байта и выше. Что дает?

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

Распределители, которые разделяют память в зависимости от размера выделения, называются «slab allocators.». На практике у них гораздо больше классов размера, чем 2 в нашем примере.

# Быстрая malloc головоломка​

Что произойдет, если вы malloc(0)? Подумайте об этом, прежде чем играть с ползунком ниже.

Это использует нашу реализацию free list, которая требует минимального размера 4 байта для распределения. Вся память выделяется, но на самом деле ни одна из них не используется. Вы считаете это правильным поведением?

Оказывается, что происходит, когда вы malloc(0) различаетесь между реализациями. Некоторые из них ведут себя, как описано выше, выделяя пространство, которое им, вероятно, не нужно. Другие вернут так называемый «нулевой указатель», специальный указатель, который приведет к сбою вашей программы, если вы попытаетесь прочитать или записать память, на которую он указывает. Другие выбирают одно конкретное место в памяти и возвращают одно и то же место для всех вызовов malloc(0), независимо от того, сколько раз оно вызывалось.

Мораль истории? Не malloc(0).

# Встроенный подсчет​

Помните, ранее, когда вы спросили о том, где хранится информация о allocation list и free list, я дал неудовлетворительный ответ о том, как она хранится в какой-то другой области памяти, которую мы зарезервировали для себя?

Да...

Это не единственный способ сделать это. Многие аллокаторы хранят информацию рядом с блоками памяти, к которым они относятся. Посмотри на это!

Здесь у нас есть память без выделений, но информация о free list хранится в этой памяти. Каждый блок памяти, свободный или используемый, получает 3 дополнительных байта бухгалтерской информации. Если address это адрес первого байта выделения, вот расположение блока:

1. address + 0 это размер блока
2. address + 1 свободен ли блок (1) или занят (2)
3. address + 2 где начинается полезная память
4. address + 2 + size-- снова размер блока

Итак, в приведенном выше примере байт at 0x0 хранит значение 29. Это означает, что это блок, содержащий 29 байтов памяти. Значение 1 at 0x1 указывает, что в блоке есть свободная память.

Мы сохраняем размер дважды? Разве это не расточительно?

Поначалу это кажется расточительным, но это необходимо, если мы хотим объединиться в какой-либо форме. Давайте посмотрим на пример.

Здесь мы выделили 4 байта памяти. Для этого наша malloc реализация начинает с начала памяти и проверяет, используется ли там блок. Он знает, что address + 1 найдет либо 1, либо 2. Если он найдет 1, он может проверить значение address на предмет размера блока. Если он достаточно большой, он может выделить в него. Если он недостаточно велик, он знает, что может добавить найденное значение address, чтобы address перейти к началу следующего блока памяти.

Это привело к созданию используемого блока (обратите внимание на 2, хранящиеся во втором байте), и сдвинуло начало свободного блока вперед на 7 байтов. Давайте сделаем то же самое еще раз и выделим еще 4 байта.

Далее, давайте free наш первый malloc(4). Реализация — free это то, где встроенное хранение информации начинает сиять. В наших предыдущих аллокаторах нам приходилось искать в allocation list, чтобы узнать размер free -блока. Теперь мы знаем, что найдем его по адресу address. Что еще лучше, так это то free, что для этого нам даже не нужно знать, насколько велико распределение. Мы можем просто установить address + 1 на 1!

Насколько это здорово? Просто, быстро.

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

Когда мы объединяемся, мы проверяем состояние блоков непосредственно перед и сразу после блока, которому мы делаем free. Мы знаем, что можем перейти к следующему блоку, добавив значение address к address, но как мы перейдем к предыдущему блоку? Мы берем значение address - 1 и вычитаем его из address. Без этой дублированной информации о размере в конце блока было бы невозможно найти предыдущий блок и невозможно было бы правильно объединиться.

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

Что мешает программе изменить бухгалтерскую информацию? Разве это не сломает память?

Удивительно, но ничто не мешает этому. Мы, как отрасль, сильно полагаемся на правильность кода. Возможно, вы уже слышали об ошибках «переполнение буфера» или «использовать после освобождения». Это когда программа изменяет память после конца выделенного блока или случайно использует блок памяти после freе обработки. Это действительно катастрофа. Они могут привести к немедленному сбою вашей программы, они могут привести к сбою вашей программы через несколько минут, часов или дней. Они даже могут привести к тому, что хакеры воспользуются этой ошибкой, чтобы получить доступ к системам, к которым у них не должно быть доступа.

Мы наблюдаем рост популярности «безопасных для памяти» языков, например Rust. Эти языки вкладывают много сил в то, чтобы исключить такие ошибки. Как именно они это делают, выходит за рамки этой статьи, но если вас это интересует, я настоятельно рекомендую попробовать Rust.

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

Чтобы обойти это, некоторые распределители вводят «магические» значения как часть бухгалтерской информации. Они хранятся, скажем, 0x55 в address + 2. Это приведет к потере дополнительного байта памяти на выделение, но позволит им узнать, когда была допущена ошибка. Чтобы уменьшить влияние этого, распределители часто отключают это поведение по умолчанию и позволяют включать его только во время отладки.

# Тестовая площадка​

Если вы хотите использовать свои новые знания и попробовать свои силы в написании собственных распределителей, вы можете щелкнуть здесь , чтобы перейти на мою тестовую площадку. Вы сможете написать код JavaScript, реализующий malloc/free API, и визуализировать его работу!

# Заключение​

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

 

[weaver]

Хорошая статья, надо больше статей про аллокаторы. Вот только лучше смотреть её в оригинале, т.к. там есть ползунки чтобы смотреть как распределяется память (макет). Единственный момент это то, что слова "allocation list" и "free list" надо оставлять в оригинале, иначе тереяется смысл.

"allocation list"
хранит адрес выделенной памяти
хранит размер выделенной памяти

"free list"
хранит адрес свободной памяти
хранит размер свободной памяти


Вызывается malloc
Просмотр "free list"a
Поиск блока памяти
Сохраняем адрес и размер выделения в "allocation list"
Обновляем запись в "free list"

Из минусов это то что автор заикнулся про "slab allocators", тем самым сбивает с толку.