#c
#c
Вопрос:
Я могу отчасти понять цель наличия только заголовка в каждом блоке, но я не могу понять цель наличия как верхнего, так и нижнего колонтитула. Согласно http://www.cs.cornell.edu/courses/cs3410/2016fa/slides/15-allocation.pdf , слайд 25, нижний колонтитул позволяет также перемещаться по списку в обратном направлении. Какова цель обхода списка как вперед, так и назад?
Комментарии:
1. Пожалуйста, включите любой код для контекста в тело вопроса, а не в качестве внешних ссылок.
2. @tadman: Я сомневаюсь, что OP владеет авторскими правами на упомянутый слайд.
3. @AndreasWenzel Это добросовестное использование. Не применимо.
Ответ №1:
Я реализовал довольно много реализаций malloc() . Причина, по которой вы хотите пройти назад, заключается в том, чтобы прикрепить блок к предыдущему включенному блоку free() . Но я не могу представить себе использование нижнего колонтитула. Я просто использую заголовок, который выглядит следующим образом.
struct block {
struct block *next;
struct block *prev;
uintptr_t size;
uintptr_t blocksize;
};
Я мог бы использовать size_t для размера, но на платформах, где они отличаются, uintptr_t с большей вероятностью будет работать правильно, поэтому я менее склонен что-то исправлять. Я отслеживаю размер , который был выделен , а также размер блока для ускорения realloc() .
Если бы мы каким-то образом избавились от необходимости перемещаться назад free() , мы могли бы уменьшить заголовок до двух элементов.
struct block {
struct block *next;
uintptr_t size;
};
Младший бит size является бесплатным на любой разумной платформе, поэтому вы можете установить там флаг is_allocated.
Комментарии:
1. Это довольно расточительно, используя 4 слова для заголовка. С верхним / нижним колонтитулом вам нужно только по одному слову для каждого. Еще лучше схема bibop, в которой вы не используете верхние или нижние колонтитулы, а только дескриптор на страницу.
2. Нет необходимости в дополнительных словах для недовольной кучи, если каждый прерывистый фрагмент выровнен (поскольку обычно он выравнивается по странице, это не проблема). Но, как правило, если вам требуется выравнивание по n байтам, минимальный размер верхнего и нижнего колонтитулов составляет n байт, что обычно отдает предпочтение механизмам на основе страниц, а не на основе списков.
3. Каждое слово имеет размер блока плюс 2 бита для обозначения неиспользуемого / свободного / не являющегося частью состояния кучи. Первый блок кучи начинается с нижнего колонтитула из 1 слова, обозначающего начало кучи (без предыдущего фрагмента или блока), затем заголовок из 1 слова для первого фрагмента (свободного или используемого) в этом блоке. Последним словом блока кучи будет заголовок, указывающий размер промежутка до следующего блока кучи, указывающий, что он не является частью кучи. Пока все блоки кучи выровнены по 2 словам, все выделения также будут выровнены по 2 словам.
4. @ChrisDodd: я исправлен. Если ваше ограничение выравнивания является указателем, а ваша система не 16-разрядная, это решение.
5. Таким образом, куча становится «непрерывной» от самого низкого адресного блока до самого высокого, она просто может содержать фрагменты, которые не являются частью кучи. Если хотите, вы могли бы рассматривать это как заголовок из двух слов, а не как заголовок из 1 слова нижний колонтитул из 1 слова, где заголовок содержит размер текущего блока и размер предыдущего блока, а также статус выделения обоих.