Распределитель памяти — простое раздельное хранилище: как определить размер выделенного блока по его адресу?
Я читаю книгу по CS:APP и наткнулся на Simple Segregated Storage в главе Dynamic Memory Allocation.
В книге упоминается, что одним из преимуществ Simple Segregated Storage является то, что блоки памяти не нуждаются в заголовке. Он упоминает
Поскольку каждый фрагмент состоит только из блоков одинакового размера, размер выделенного блока можно определить по его адресу.
Изображение из книги - CS:APP - Простое отдельное хранилище
Я не понимаю, как это работает. Я понимаю, что, поскольку размер блоков одинаков для одного свободного списка, адрес каждого блока будет сначала увеличиваться на ту же сумму, когда большой блок запрашивается из ядра и делится, но как мы можем вывести размер из адреса ? Он должен быть кратен размеру блока, но если начальный начальный адрес не кратен, то он никогда не будет кратен размеру блока. Более того, если классы размера идут, 2, 4, 8, 16, адрес может быть кратен многим другим классам размера?
Программное обеспечение для выделения памяти просто устанавливает области памяти. Например, от 0x1000000 до 0x2000000 используются для восьмибайтовых блоков, от 0x2000000 до 0x3000000 — для 16-байтовых блоков, от 0x3000000 до 0x4000000 — для 32-байтовых блоков и т. д. Или, возможно, более реалистично, каждый раз, когда программному обеспечению требуется новый регион памяти, либо потому, что был запрошен новый размер, либо из-за того, что старый регион заполнен, он выделяет кучу памяти, запоминает, где он начинается и для какого размера он предназначен, и использует его только для блоков такого размера. Затем free ищет возвращенные блоки в запомненных начальных адресах.
Далее идет речь о связанном списке свободных (доступных) блоков. Когда требуется блок памяти, он берется из головы связанного списка (для этого размера блока), а когда он освобождается, он становится головным блоком связанного списка.
@EricPostpischil единственное, что Simple Segregated Storage не встраивает эту информацию в блоки памяти. В книге упоминается, что ей не нужен верхний или нижний колонтитул. В нем говорится, что это возможно, потому что «размер выделенного блока можно определить по его адресу», что меня сбивает с толку. Как узнать размер по адресу?
Ответы 2
Распределитель, использующий этот подход, получает большие блоки (фрагменты) памяти от ОС. Он определяет размер блока, используемый для выделения блоков из каждого фрагмента, и ключом к «простому раздельному хранилищу» является то, что каждое выделение из данного фрагмента будет точно такого же размера. Это может быть больше, чем запрошенный размер для любого данного запроса, но это не редкость для распределителей в целом. Таким образом, чтобы определить (истинный) размер данного распределения, распределителю нужно только определить, в каком фрагменте он находится. Ему не нужна какая-либо информация о распределении.
Я понимаю, что распределителю нужно только знать, к какому фрагменту (свободному списку) должен вернуться выделенный блок при освобождении, но как он узнает об этом из адреса выделенного блока? Я знаю, что блоки в одном и том же чанке имеют одинаковый размер, но я не уверен, как это помогает, когда чанк (свободный список) может начинаться со случайного места в памяти.
@ BSE10, где-то у него есть записи базового адреса и размера каждого фрагмента на уровне фрагментов. Или, что то же самое, начальный и конечный адреса каждого фрагмента. Ему не нужны заголовки для каждого распределения, но ему все же нужны некоторые метаданные.
Если это так, то блоки могут быть любого размера в пределах диапазона размера класса, и вы все равно можете узнать, к какому фрагменту принадлежит блок, если вы просто сравниваете адрес блока с начальным и конечным адресами фрагмента. В книге конкретно упоминается причина в том, что блоки в одном фрагменте имеют одинаковые размеры, и поэтому размер можно определить по адресу блока. Это та часть, которую я пытаюсь понять
@ BSE10, да, все дело в том, что адрес выделенного блока говорит вам, к какому фрагменту он принадлежит. И поскольку все блоки, выделенные из данного фрагмента, имеют одинаковый (истинный) размер, это говорит вам о размере выделения. И именно поэтому с этой схемой вам не нужно вести записи размера выделения для каждого выделения.
Ах хорошо. Теперь это имеет гораздо больше смысла! Большое спасибо! :)
Я полностью понимаю, что вы имеете в виду, потому что я пытаюсь использовать этот метод в malloclab и найти эту проблему.
Я согласен, что мы не можем вычислить размер блока по адресу, если адрес &(4KB-1) равен 32, это может быть 5-й для 8, 3-й для 16 или 1-й для 32. А если адрес равен 0, он может быть первым блоком для любого размера.
Поэтому мы должны использовать дополнительное пространство для записи некоторой информации.
Одним из решений является запись начального адреса каждого фрагмента и того, к какому свободному списку он принадлежит, а затем, если мы получим свободный адрес void* ptr, выполните поиск (ptr & ~ 4 КБ) в списке фрагментов, чтобы найти соответствующий размер блока. Но это так глупо и трудно кодировать.
Другим решением является добавление заголовка. И я выбираю закончить таким образом.
В нем говорится ... блоки одинакового размера в каждом фрагменте ... Если у вас есть все блоки размера M в одном выделенном фрагменте памяти, вы можете узнать из адреса блока, в каком фрагменте памяти он находится, и поэтому он его размер М.