Проблема в реализации функции malloc с нуля

Question

Итак, я думал о создании собственного сборщика мусора на языке Си, и я наткнулся на этот учебник, который начинается с реализации функции malloc с нуля. Идея учебника состоит в том, чтобы иметь связанный список свободных блоков памяти, и всякий раз, когда вы используете malloc, он проверяет этот список и дает вам память, которую вы хотите:

typedef struct header {
    unsigned int    size;
    struct header   *next;
} header_t;

{
    size_t num_units;
    header_t *p, *prevp;

    num_units = (alloc_size + sizeof(header_t) - 1) / sizeof(header_t) + 1; 

.....
}

Переменная alloc_size - это блоки памяти, которые мы хотим выделить; переменная num_units - это количество «узлов» списков, которые у вас будут. Моя проблема с формулой, которую они использовали, я понял идею (alloc_size) / sizeof (header_t), но почему они добавили sizeof (header_t) - 1 & +1.

Answer 1

Это общий механизм округления до следующего кратного значения данного значения.

Целочисленное деление - это просто отбрасывание любой дробной части, т. Е. Округление вниз.

Это означает

alloc_size / unit_size 

приведет к точному количеству единиц (если остаток равен 0) или к 1 единице меньше (во всех других случаях).

Пример:

   8 / 4 => 2  OK  |   ( 8 + (4-1)) / 4 == 11/4 => 2  OK
   9 / 4 => 2 NOK  |   ( 9 + (4-1)) / 4 == 12/4 => 3  OK
  10 / 4 => 2 NOK  |   (10 + (4-1)) / 4 == 13/4 => 3  OK
  11 / 4 => 2 NOK  |   (11 + (4-1)) / 4 == 14/4 => 3  OK
  12 / 4 => 3  OK  |   (12 + (4-1)) / 4 == 15/4 => 3  OK

Простое добавление 1 к результату означало бы потерю 1 единицы всякий раз, когда размер уже кратен.

Наконец, они добавляют еще один +1, чтобы иметь место для самого заголовка.

Таким образом, выразмер выделения для 1 header_t, используемый для хранения информации о выделенном блоке + память для самого запроса на выделение.