Почему эта программа выделяет 8 страниц, но может вместить только 2048 узлов, размер которых составляет 8 байт?

Question

Узел определяется следующим образом:

    struct node{
      int value;
      struct node *next;
    };

Используя sizeof(struct node) Я узнал, что узел составляет 8 байтов (в xv6). Поэтому я использую malloc выделить некоторое пространство памяти для хранения некоторых узлов. Одна страница в xv6 составляет 4096 байт, если у меня есть 8 страниц, я могу хранить 4096 таких узлов. Однако, это не то, что происходит после того, как я malloc 2048 таких узлов, если я malloc еще один, больше страниц выделено для текущего процесса, почему это так?

    // Now display how many pages are allocated to the process
    // Suppose there is a system call named memcount(), it is given by
    // my professor, I wouldn't think there's any problem with that
    //
    memcount(); // which prints 3, meaning that initially, without
                // allocaing anything, 3 pages = 12288 bytes of memory allocated

    for(i = 0; i < 2048; ++i){
      struct node *nd = (struct node *)malloc(sizeof(struct node));
    }

    memcount(); // which prints 11, so 8 more pages are allocated

    // If we allocated 1 more node
    struct node *nd = (struct node *)malloc(sizeof(struct node));
    memcount(); // which prints 19, another 8 pages are allocated

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

Answer 1

На вопрос уже ответили в комментарии: malloc() нужно немного места для хранения, как используется память.

Обработчик памяти видит кучу как один большой массив байтов (потому что ОЗУ - это один большой массив в большинстве моделей памяти). (Существуют также другие модели памяти, или менеджер памяти может хранить некоторые данные на дополнительных страницах, но для простоты мы игнорируем такие случаи)

В качестве примера мы могли бы подумать о системе, где первые 4 байта используются в качестве указателя (p0), где начинаются следующие действительные блоки и следующие 4 байта для переменной (size_t, s0) сколько байтов используется для этого блока (нам нужно 2 переменные, чтобы определить, когда освобождается блок между 2 блоками). Следующий блок также имеет указатель (p1) к следующему (следующему из следующего) блоку и переменной для размера блока (s1)

После этого заголовка находятся данные, которые вы можете использовать, malloc() вернуть указатель на первый байт после этого заголовка. Переменная s0 будет хранить сколько байтов вы запросили. После нового malloc()после первого блока будет создан новый заголовок, и p0 будет указывать на этот заголовок:

Address:   0x10    0x14    0x18    0x1B    0x20    0x24    0x28 ...
Name:      p0      s0      value   next    p1      s1      value...
Value:     0x20    8       ??      0x28    0       8       ??

Вот ситуация после того, как вы выделите 2 блока, p1 а также s1 переменные для заголовка второго блока. Вы можете использовать только переменную next а также value, Указатель, который malloc() вернулся 0x18 а также 0x28,

Чтобы избежать использования половины пространства для обработчика памяти, вы можете выделить больший массив за один шаг. Вы могли бы использовать struct как это:

struct Node_T
  {
    int values[512];
    size_t usedValues;  
    struct Node_T *next;
  }

Then you would need 4*4 = 16 Bytes total overhead (including the overhead of the memoryhandler, and assumed the memoryhandler need 8 bytes header per block and int, pointers and size_t are 4 bytes). But you need extra copy or move overhead when you remove or add a value between other values.