Dynami c Memory Allocator

Question

С учетом следующего вопроса с приведенными ниже ответами:

Как я могу вычислить значения в зеленых выделенных областях? Я полагаю, что у меня есть solid понимание того, как функция free() в C работает и как она работает: очищает блок памяти, динамически выделяемый в стеке кучи (либо полностью удаляя его, либо освобождая для использования , на будущее выделяет).

Что я не понимаю, так это то, как вызов free(0x400b010) изменяет только некоторые другие блоки кучи выше? (те, что я выделил зеленым цветом). Я получаю, что адрес 0x400b010 (с двоичным значением: 01000000 00001011 01100000 00011100 не изменяется, согласно присвоению, которое он уже освободил, имея 0 в его bit 0.

Может кто-нибудь объяснить мне это Например, блок по адресу 0x400b00c:0x000000013 меняет свое значение (второй аргумент после :) на 0x00000022, когда free вызывается для блока выше. Этот пример является лишь одним из нечетных случаев, когда блок ранее выделенные (1 in bit 0) изменения будут свободными, даже если по этому адресу не было вызвано free.

Аналогично некоторые блоки меняют свои значения, а другие нет.

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

Answer 1

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

Поэтому, когда вызывается free(0x400b010), первое, что нужно вычесть 4 и получите заголовок блока 0x400b00 c - 0x13. Это говорит о том, что блок составляет 16 байтов (0x10) и используется (установлен бит 0), а предыдущий блок используется (установлен бит 1). Чтобы освободить его, вам нужно проверить, свободен ли какой-либо из соседних блоков. Значение бита 1 говорит о том, что предыдущий блок не свободен, но чтобы проверить следующий блок, вам нужно его найти. Для этого вы добавляете размер (0x10) к адресу заголовка (0x400b00 c), чтобы получить адрес заголовка следующего блока (0x400b01 c), который возвращает значение заголовка 0x12. Этот блок свободен, поэтому вы добавляете его размер к текущему блоку и помечаете текущий блок как свободный, устанавливая заголовок текущего блока равным 0x22 (так что теперь он является свободным 32-байтовым блоком). Теперь вам также нужно найти нижний колонтитул этого нового объединенного блока (по адресу заголовка + размер - 8 == 0x400b024) и также изменить его на 0x22.

Нет необходимости менять старый нижний колонтитул block или старый заголовок следующего свободного блока, находящегося в связке, поскольку теперь они являются частью содержимого свободного блока (значения которого «пофиг»). Также нет необходимости прикасаться к предыдущему блоку, так как он (все еще) используется.

В этой настройке есть несколько странных вещей.

• запись состояния free / in use предыдущего блока в бите 1 является ненужным осложнением. Вы также можете проверить это, посмотрев на нижний колонтитул предыдущего блока. Если бы он был свободным, вам понадобилось бы значение нижнего колонтитула предыдущего блока, чтобы найти его размер (и заголовок).
• вам действительно нужно знать начало и конец кучи, чтобы не случайно go с конца проверяем предыдущий или следующий блок. Если это был последний блок в куче, попытка получить заголовок следующего блока привела бы к ошибкам при запуске конца кучи.

Answer 2

Я пытался найти фигуру, но не смог найти ничего удовлетворительного. Я просто попытаюсь объяснить словами.

Если вы сравните таблицу слева и справа, вы увидите, что измененные поля равны 0x400b00 c и 0x400b028, соответственно от 13 и 12 до 22 .

Обратите внимание, что каждый блок памяти имеет верхний и нижний колонтитулы. Поскольку free было выполнено в 0x400b010, это указывает, что 0x400b00 c является заголовком. Поэтому все записи ниже (400aff c ~ 400b008) останутся без изменений, так как на них не повлияет свободная операция.

Если посмотреть с 0x400b00 c, ранее было 2 блока:

• блок 1: 0x400b00 c ~ 0x400b018
• блок 2: 0x400b01 c ~ 0x400b028

Обратите внимание, что блок 2 не используется, поскольку bit 0 indicates the use of current block, но значение 0x0000012 является четным. Поэтому, если блок 1 освобожден, блок 1 и блок 2 будут объединены, чтобы сформировать новый неиспользованный блок в целом.

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

Таким образом, единственные изменения, которые необходимо сделать, - это новый заголовок и нижний колонтитул нового блока , который находится в позициях 0x400b00 c, и 0x400b028.

Обратите внимание, что между новым верхним и нижним колонтитулами (включительно) имеется 8 блоков, что приводит к 8 * 4 = 32 байта. 32 в двоичном виде - 100000, но поскольку используется предыдущий блок (неизмененный блок), бит 1 устанавливается на 1. В результате получается 100010, то есть шестнадцатеричное число 22.

Извините, если это объяснение сбивает с толку, спросите, не можете ли вы понять какую-либо часть этого ответа.