Реализации К&Р Танос


Это одна из реализаций файл из K&Р Танос. Она прошла все тесты я проводил на нем, поэтому я хотел бы попросить пересмотреть код.

my_malloc.с

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>


void insert_into_free_list(void* ptr);
void* my_malloc(size_t size);
void my_free(void* ptr);
void coalesce_free_list();
void* free_list_begin();
void* free_list_next(void* node);

void* malloc(size_t size);
void free(void* ptr);

/**
 * A single chunk in the free list that my_malloc uses to dole out memory.
 */
struct malloc_chunk {
    size_t size; /*!< The size of the chunk in bytes. This includes the bookkeeping bytes, the block presented to the user, and any necessary padding. Valid for both free and allocated chunks.*/
    struct malloc_chunk* next_chunk; /*!< A pointer to the next chunk in the free list. Should always be NULL for the tail of the free list. Valid for free chunks only. */
};

/**
 * The head of the free list.
 */
static struct malloc_chunk* head_of_free_list = NULL;

/**
 * A memory allocator which acts as a buffered interface to the sbrk system call.
 * Given a number of bytes, it returns a pointer to a block of memory whose size is greater than or equal to the number given aligned by eight bytes or NULL if the user requested 0 bytes.
 * It will also return NULL on failure of sbrk. The user is trusted to check for this failure condition.
 * It will include an additional eight bytes at the start of every block of memory allocated to be used for bookkeeping.
 * Those eight bytes should NOT be presented to the user.
 *
 * @param size The size in bytes of the memory block to be presented to the user.
 * @return The pointer to the beginning of the memory block that is presented to the user.
 */
void* my_malloc(size_t size) {
    size_t size_to_allocate;
    struct malloc_chunk* chunk;
    struct malloc_chunk** chunk_pointer;

    if(size == 0) {
        return NULL;
    }

    /* Round size up to the nearest multiple of eight */
    size = (size + 7) & ~0x07;

    /* Add eight bytes for bookkeeping */
    size += 8;

    /* If we can find a chunk in our free list that is large enough to accommodate the user's request, take it out of our free list and give it to the user. */
    chunk = head_of_free_list;
    chunk_pointer = &head_of_free_list;
    while(chunk != NULL) {
        if(chunk->size >= size) {
            struct malloc_chunk* return_ptr = (struct malloc_chunk*) ((char*) chunk + chunk->size - size);
            /**
             * We either found an exact match or one that's close enough.
             * To avoid fragmentation, we simply give the user the entire chunk if it's close enough.
             */
            if(chunk->size - size <= 16) {
                return_ptr = chunk;
                *chunk_pointer = chunk->next_chunk;

            /* In this case, the chunk is more than big enough for the requested amount of memory, so we just decrease the chunk's size. */
            } else {
                chunk->size -= size;
                return_ptr->size = size;
            }
            return (char*) return_ptr + 8;
        }

        chunk_pointer = &chunk->next_chunk;
        chunk = chunk->next_chunk;
    }

    /* my_malloc should not call sbrk with a value lower than 8192. */
    size_to_allocate = size > 8192 ? size : 8192;
    chunk = sbrk(size_to_allocate);

    if(chunk == (void*) -1) {
        perror("my_malloc");
        return NULL;
    }

    /**
     * This covers the case that the user requested a large amount of memory.
     * Since they requested such a large amount, we don't attempt to add a buffer of extra memory to the free list and give them everything instead.
     */
    if(size_to_allocate > 8192) {
        chunk->size = size;
        return (char*) chunk + 8;
    }

    chunk->size = size_to_allocate - size;
    struct malloc_chunk* ptr = (struct malloc_chunk*) ((char*) chunk + size_to_allocate - size);

    insert_into_free_list(chunk);


    ptr->size = size;
    return (char*) ptr + 8;
}

/**
 * A memory de-allocator which returns memory to the free list used by my_malloc.
 * Given a pointer which indicates a chunk of memory that was previously presented to the user by my_malloc, it uses information found in the eight bookkeeping bytes
 * found before the chunk specified by the pointer to add the chunk to the free list. * It can safely be called with NULL.
 * It will also coalesce the chunks in the free list to keep the number of chunks in the list to a minimum.
 * @param ptr A pointer to the beginning of a chunk of memory that was presented to the user by my_malloc.
 */
void my_free(void* ptr) {
    if(ptr == NULL) {
        coalesce_free_list();
        return;
    }

    /* Back up by eight bytes, so that we can easily access the bookkeeping bytes. */
    ptr = ((char*) ptr) - 8;

    insert_into_free_list(ptr);
    coalesce_free_list();
}

/**
 * Returns the head of the free list or NULL if the free list is empty.
 * @return Head of the free list used by my_malloc.
 */
void* free_list_begin() {
    return head_of_free_list;
}

/**
 * Given a pointer to a node in the free list, it returns the next node in the list or NULL if node points to the tail of the list.
 * @param node A pointer to a node in the free list.
 * @return A pointer to the next node in the free list or NULL if @node points to the tail of the list.
 */
void* free_list_next(void* node) {
    return ((struct malloc_chunk*) node)->next_chunk;
}

/**
 * Used by my_free to coalesce the free list and keep the number of chunks present in the free list to a minimum.
 */
void coalesce_free_list() {
    struct malloc_chunk* node = head_of_free_list;

    if(node == NULL) {
        return;
    }

    while(node != NULL) {
        /* If two chunks are right next to each other in memory, then we can coalesce them. */
        while((char*) node + node->size == (char*) node->next_chunk) {
            node->size += node->next_chunk->size;
            node->next_chunk = node->next_chunk->next_chunk;
        }

        node = node->next_chunk;
    }
}

void insert_into_free_list(void* ptr) {
    struct malloc_chunk* chunk_in_free_list;
    struct malloc_chunk* new_chunk;

    new_chunk = ptr;

    /**
     * The head of the free list being NULL means one of two things:
     * 1.) The user has called my_free without a corresponding call to my_malloc. We trust that they won't do this.
     * 2.) All chunks in the free list have been allocated.
     *
     * If the head isn't NULL, it could also be the case that ptr needs to be inserted before the head of the free list.
     * Either way, we make ptr the new head of the free list.
     */
    if(head_of_free_list == NULL || head_of_free_list >= new_chunk) {
        new_chunk->next_chunk = head_of_free_list;
        head_of_free_list = new_chunk;
    } else {
        chunk_in_free_list = head_of_free_list;

        /**
         * We try to insert into our free list at the point where ptr->previous_chunk < ptr < ptr->next_chunk.
         * This will make coalescing the free list easier.
         */
        while(chunk_in_free_list->next_chunk != NULL && chunk_in_free_list->next_chunk < new_chunk) {
            chunk_in_free_list = chunk_in_free_list->next_chunk;
        }
        new_chunk->next_chunk = chunk_in_free_list->next_chunk;
        chunk_in_free_list->next_chunk = new_chunk;
    }
}

/**
 * Alias of my_malloc, so it can be used with LD_PRELOAD
 */
void* malloc(size_t size) {
    return my_malloc(size);
}

/**
 * Alias of my_free, so it can be used with LD_PRELOAD
 */
void free(void* ptr) {
    my_free(ptr);
}


394
4
задан 26 марта 2018 в 12:03 Источник Поделиться
Комментарии
2 ответа

Некоторые быстрые идеи:

Маскирование с int не является безопасным. Считают, что size_t может быть шире, чем unsigned/intтогда нужные ~ маски будет недостаточно.

// size = (size + 7) & ~0x07; // Avoid
size = (size + 7) & ~((size_t)0x07); // Better


Указатель математика ботфорты на тонком льду. Предполагается, что совмещение до 8 вполне достаточно.

struct malloc_chunk* return_ptr = 
(struct malloc_chunk*) ((char*) chunk + chunk->size - size); // Iffy

Лучше использовать sizeof (max_align_t) от <stddef.h> и / с:

#define ALIGNMENT_N (sizeof (max_align_t))
#define PRE_N (sizeof (union { size_t size; max_align_t dummy;}))
size = (size + ALIGNMENT_N - 1) & ~ALIGNMENT_N; // Better

Возможно заменить магическим числом 16 тоже.

Также обертывание 8192 в макро

#define MY_MALLOC_BIG 8192

Продумайте заранее в ожидании данных с хорошо выровнены size. Это выравнивает данных и исключает необходимость для не-так-волшебный 8 закодированные в очень многих местах.

struct malloc_chunk {
union {
size_t size;
max_align_t dummy;
} u;
union {
struct malloc_chunk* next_chunk;
max_align_t dummy;
} v;
};


Надежный код будет также проверить против большие запросы

if (size > SIZE_MAX - ALIGNMENT_N - PRE_N) {
return NULL; // Fail
}
...
// else the following code is problematic.
size = (size + ALIGNMENT_N - 1) & ~ALIGNMENT_N;
size += PRE_N;


sbrk() не из стандартной библиотеки C.


Использовать (void) при объявлении функции для обеспечения параметра проверки, еще как free_list_begin(42) не флаг ошибки.

// void* free_list_begin();
void* free_list_begin(void);

4
ответ дан 26 марта 2018 в 11:03 Источник Поделиться


  1. Горизонтальная прокрутка-это смерть для читабельности. На самом деле, это дело с длинными линиями, даже если они не проходят этот порог.
    Итак, почему вы силой 194 символов на одной линии, большинство это замечание?

  2. Избавиться от всех магических чисел. И особенно эти цифры как-то производным от первоначального магия чисел, а может и нет, кто знает.
    Вместо этого, используют хорошо им препроцессора-определяет разумные значения по умолчанию, полученные из стандартных типов.

  3. Отметить все функции, реализация-детали static. Не нужно подавлять встраивания, имя-риск столкновения, или загрязнять экспорт - и импорт-столы.

  4. На самом деле, поставить публичный API в собственном заголовке.

  5. Кто-нибудь LD_PRELOADтвой код будет в для неприятный сюрприз, как вы ни calloc() ни realloc(). Используя две разных памяти-менеджеров-если они были то же не самая хорошая идея.

4
ответ дан 27 марта 2018 в 12:03 Источник Поделиться