Где находится само пространство в распределителе памяти, описанном в конце книги K&R?

В самом конце книги Кернигана и Ритчи Язык программирования C описывается распределитель памяти. Это говорит

Каждый блок содержит размер, указатель на следующий блок и само пространство.

Но я не вижу этого в коде:

typedef long Align;  /* for alignment to long boundary */

union header {       /* block header */
   struct {
      union header *ptr; /* next block if on free list */
      unsigned size;     /* size of this block */
   } s;
   Align x;          /* force alignment of blocks */
};

typedef union header Header;

Указатель на следующий блок — *ptr, а размер — unsigned size, но какой переменной является само пространство? Является ли само пространство переменной x?


c memory-management kernighan-and-ritchie
person Niklas R.    schedule 15.09.2015    source источник
comment
Скорее всего, пробел следует сразу после самого заголовка.   -  person sashoalm    schedule 15.09.2015
comment
Вы уверены, что это не просто заголовок блока? То есть, когда пространство выделено, вы должны выделить байты size+sizeof(header), поместить заголовок в первые байты sizeof(header), а затем оставить байты size в выделенной памяти?   -  person Joshua Taylor    schedule 15.09.2015
comment
K&R довольно древний и не учитывает функции C99, такие как гибкие элементы структуры.   -  person too honest for this site    schedule 15.09.2015
comment
Предполагая, что ваш компьютер не из 80-х, размер ptr плюс размер size будет больше, чем x. Исправление выравнивания отсутствует, и весь сегмент, скорее всего, будет содержать байты заполнения. Все, что делает этот код, — это бессмысленно запутывает вещи. Только не читайте эту чушь, 30 лет спустя это бредовый код.   -  person Lundin    schedule 15.09.2015
comment
Сообщите об этом самом примере. В случае, если вам еще не было очевидно, насколько плохой код.   -  person Lundin    schedule 15.09.2015

Ответы (2)


arrow_upward
3
arrow_downward

Это всего лишь заголовок для блока. То есть, когда пространство выделено, вы должны выделить некоторое количество места, кратное sizeof(header), поместить заголовок в первые байты sizeof(header), а затем оставить байты size в выделенной памяти. Из текста (я думаю, это то, к чему я пришел, когда я погуглил часть текста, который вы цитировали, и неожиданно появился на сайте учебных пособий по Java), добавлено выделение:

Свободный блок содержит указатель на следующий блок в цепочке, запись размера блока, а затем само свободное место; управляющая информация в начале называется "заголовок". Чтобы упростить выравнивание, все блоки кратны размеру заголовка, и заголовок выравнивается правильно. Это достигается объединением, которое содержит желаемую структуру заголовка и экземпляр наиболее ограничительного типа выравнивания, который мы произвольно сделали long[.]

стр. 186, глава 8, Язык программирования C, второе издание

Позже, на с. 187 пример реализации malloc() показывает, что память всегда выделяется несколькими заголовками с дополнительным заголовком в начале для управляющей информации:

void *malloc(unsigned nbytes)
{
    /* ... */
    nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;

стр. 187, глава 8, Язык программирования C, второе издание

Возможно полезные ссылки

person Joshua Taylor    schedule 15.09.2015

arrow_upward
1
arrow_downward

В книге говорится о распределителе памяти. Выдержка (выделено мной):

8.7 Пример — распределитель памяти

[…]

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

Автор просто имеет в виду место, выделенное для запроса. Допустим, приходит запрос на 20 КиБ на выделение, под этот запрос создается блок. Он будет содержать размер запроса в виде int, который будет иметь значение 20 * 1024 * 1024, за которым следует указатель на следующий такой выделенный блок, а затем 20 КиБ свободного места (это также относится к этому термину), чей первый байтовый адрес передается обратно вызывающему абоненту.

На следующей странице показан код

void *malloc(unsigned nbytes)
{
    …
    nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;

Это показывает, что объединение охватывает только пространство для управляющей информации (Header), а не само свободное пространство, которое позже добавляется к подсчету выделенных единиц.

person legends2k    schedule 15.09.2015
comment
Я думаю, что путаница OP в каждом блоке содержит размер, указатель на следующий блок и само пространство. заключается в том, что структура заголовка, упомянутая в вопросе, не является всем блоком, а просто заголовком для блока. - person Joshua Taylor; 15.09.2015
comment
Правильно, добавил эту деталь. Спасибо! - person legends2k; 15.09.2015