Реализация malloc?

Ответ 1

Самый простой способ сделать это - сохранить связанный список свободного блока. В malloc, если список не пуст, вы ищете блок, достаточно большой, чтобы удовлетворить запрос и вернуть его. Если список пуст или если такой блок не найден, вы вызываете sbrk для выделения некоторой памяти из операционной системы. в free, вы просто добавляете блок памяти в список свободного блока. В качестве бонуса вы можете попытаться объединить смежный освобожденный блок, и вы можете изменить политику для выбора возвращаемого блока (сначала подойдет, лучше всего подходит,...). Вы также можете разделить блок, если он больше, чем запрос.

Некоторые примеры реализации (он не проверен и, очевидно, не является потокобезопасным, используйте на свой страх и риск):

typedef struct free_block {
    size_t size;
    struct free_block* next;
} free_block;

static free_block free_block_list_head = { 0, 0 };
static const size_t overhead = sizeof(size_t);
static const size_t align_to = 16;

void* malloc(size_t size) {
    size = (size + sizeof(size_t) + (align_to - 1)) & ~ (align_to - 1);
    free_block* block = free_block_list_head.next;
    free_block** head = &(free_block_list_head.next);
    while (block != 0) {
        if (block->size >= size) {
            *head = block->next;
            return ((char*)block) + sizeof(size_t);
        }
        head = &(block->next);
        block = block->next;
    }

    block = (free_block*)sbrk(size);
    block->size = size;

    return ((char*)block) + sizeof(size_t);
}

void free(void* ptr) {
    free_block* block = (free_block*)(((char*)ptr) - sizeof(size_t));
    block->next = free_block_list_head.next;
    free_block_list_head.next = block;
}

Примечание: (n + align_to - 1) & ~ (align_to - 1) - это трюк для округления n до ближайшего кратного align_to, который больше, чем n. Это работает только тогда, когда align_to является степенью двух и зависит от двоичного представления чисел.

Когда align_to является степенью двух, он имеет только один бит, и, следовательно, align_to - 1 имеет все младшие битовые множества (т.е. align_to имеет вид 000... 010... 0, а align_to - 1 имеет вид 000...001...1). Это означает, что ~ (align_to - 1) имеет весь набор высоких бит, а низкий бит не установлен (т.е. Имеет вид 111...110...0). Итак, x & ~ (align_to - 1) установит нулевое значение всех младших бит x и округляет его до ближайшего кратного align_to.

Наконец, добавив align_to - 1 в size, мы округлим до ближайшего кратного align_to (если size уже не кратно align_to, в этом случае мы хотим получить size).

Ответ 2

Вы не хотите устанавливать поле size словаря в ноль - вам понадобится эта информация для повторного использования. Вместо этого установите freed=1 только при освобождении блока.

Вы не можете объединить соседние блоки, потому что, возможно, были промежуточные вызовы на sbrk(), поэтому это упрощает. Вам просто нужен цикл for, который ищет достаточно большой освобожденный блок:

typedef struct _mem_dictionary
{
    void *addr;
    size_t size;
    int freed;
} mem_dictionary;


void *malloc(size_t size)
{
     void *return_ptr = NULL;
     int i;

     if (dictionary == NULL) {
         dictionary = sbrk(1024 * sizeof(mem_dictionary));
         memset(dictionary, 0, 1024 * sizeof(mem_dictionary));
     }

     for (i = 0; i < dictionary_ct; i++)
         if (dictionary[i].size >= size
          && dictionary[i].freed)
     {
         dictionary[i].freed = 0;
         return dictionary[i].addr;
     }

     return_ptr = sbrk(size);

     dictionary[dictionary_ct].addr = return_ptr;
     dictionary[dictionary_ct].size = size;
     dictionary[dictionary_ct].freed = 0;
     dictionary_ct++;

     return return_ptr;
}

void free(void *ptr)
{
    int i;

    if (!dictionary)
        return;

    for (i = 0; i < dictionary_ct; i++ )
    {
        if (dictionary[i].addr == ptr)
        {
            dictionary[i].freed = 1;
            return;
        }
    }
}

Это не большая реализация malloc(). Фактически, в большинстве реализаций malloc/free выделяется небольшой заголовок для каждого блока, возвращаемого malloc. Например, заголовок может начинаться с адреса на восемь (8) байтов меньше, чем возвращаемый указатель. В этих байтах вы можете сохранить указатель на запись mem_dictionary, владеющую блоком. Это позволяет избежать операции O (N) в free. Вы можете избежать O (N) в malloc(), реализовав приоритетную очередь освобожденных блоков. Рассмотрим использование биномиальной кучи с размером блока в качестве индекса.

Ответ 3

Я заимствую код из ответа Сильвена. Кажется, он пропустил вычисление размера free_block * ini, вычисляющего накладные расходы.

В целом код работает, добавив этот free_block в качестве заголовка в выделенную память.  1. Когда пользователь вызывает malloc, malloc возвращает адрес полезной нагрузки сразу после этого заголовка.  2. Когда вызывается free, вызывается адрес начала заголовка для блока (путем вычитания размера заголовка из адреса блока) и который добавляется в пул свободных блоков.

typedef struct free_block {
    size_t size;
    struct free_block* next;
} free_block;

static free_block free_block_list_head = { 0, 0 };

// static const size_t overhead = sizeof(size_t);

static const size_t align_to = 16;

void* malloc(size_t size) {
    size = (size + sizeof(free_block) + (align_to - 1)) & ~ (align_to - 1);
    free_block* block = free_block_list_head.next;
    free_block** head = &(free_block_list_head.next);
    while (block != 0) {
        if (block->size >= size) {
            *head = block->next;
            return ((char*)block) + sizeof(free_block);
        }
        head = &(block->next);
        block = block->next;
    }

    block = (free_block*)sbrk(size);
    block->size = size;

    return ((char*)block) + sizeof(free_block);
}

void free(void* ptr) {
    free_block* block = (free_block*)(((char*)ptr) - sizeof(free_block ));
    block->next = free_block_list_head.next;
    free_block_list_head.next = block;
}