como - malloc implementación?

malloc sizeof

Question

Estoy intentando implementar malloc y free C, y no estoy seguro de cómo reutilizar la memoria. Actualmente tengo una struct que se ve así:

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

Mi malloc ve así:

void *malloc(size_t size) {
    void *return_ptr = sbrk(size);
    if (dictionary == NULL) 
        dictionary = sbrk(1024 * sizeof(mem_dictionary));

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

    return return_ptr;
}

Cuando libere memoria, simplemente marcaría la dirección como 0 (eso indicaría que es libre). En mi malloc , usaría un ciclo for para buscar cualquier valor en la matriz para que sea igual a 0 y luego asignar memoria a esa dirección. Estoy un poco confundido sobre cómo implementar esto.

Answer 1

Estoy tomando prestado el código de la respuesta de Sylvain. Parece haber perdido el cálculo del tamaño del free_block * ini calculando la sobrecarga.

En general, el código funciona anteponiendo este free_block como un encabezado a la memoria asignada. 1. Cuando el usuario llama a malloc, malloc devuelve la dirección de la carga, justo después de este encabezado. 2. Cuando se llama a free, la dirección del inicio del encabezado del bloque se calcula (restando el tamaño del encabezado de la dirección del bloque) y se agrega al grupo de bloques libres.

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;
}

Answer 2

La forma más fácil de hacerlo es mantener una lista vinculada de bloques libres. En malloc , si la lista no está vacía, busca un bloque lo suficientemente grande como para satisfacer la solicitud y devolverla. Si la lista está vacía o si no se puede encontrar dicho bloque, llame a sbrk para asignar algo de memoria del sistema operativo. en forma free , simplemente agrega el fragmento de memoria a la lista de bloques libres. Como bonificación, puede intentar combinar un bloque libre contiguo, y puede cambiar la política para elegir el bloque a devolver (primer ajuste, mejor ajuste, ...). También puede elegir dividir el bloque si es más grande que la solicitud.

Algunos ejemplos de implementación (no está probado, y obviamente no es seguro para subprocesos, use bajo su propio riesgo):

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;
}

Nota: (n + align_to - 1) & ~ (align_to - 1) es un truco para redondear n al múltiplo más cercano de align_to que sea mayor que n . Esto solo funciona cuando align_to es una potencia de dos y depende de la representación binaria de los números.

Cuando align_to tiene una potencia de dos, solo tiene un bit configurado, y así align_to - 1 tiene todos los conjuntos de bits más bajos (es decir, align_to tiene la forma 000 ... 010 ... 0, y align_to - 1 es de la forma 000...001...1 ). Esto significa que ~ (align_to - 1) tiene todo el bit alto establecido, y el bit bajo no está configurado (es decir, tiene la forma 111...110...0 ). Entonces x & ~ (align_to - 1) establecerá en cero todos los bits bajos de x redondeará al múltiplo más cercano de align_to .

Finalmente, agregando align_to - 1 al size asegura que redondeamos al múltiplo más cercano de align_to (a menos que el size ya sea un múltiplo de align_to en cuyo caso queremos obtener el size ).

Answer 3

No desea establecer el campo de size de la entrada del diccionario en cero; necesitará esa información para volver a utilizarla. En cambio, configure freed=1 solo cuando se libere el bloque.

No puede unir bloques adyacentes porque es posible que haya habido llamadas intermedias a sbrk() , por lo que esto es más fácil. Solo necesita un bucle for que busca un bloque liberado suficientemente grande:

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;
        }
    }
}

Esta no es una gran implementación de malloc() . De hecho, la mayoría de free implementaciones malloc / free asignará un encabezado pequeño para cada bloque devuelto por malloc. El encabezado podría comenzar en la dirección ocho (8) bytes menos que el puntero devuelto, por ejemplo. En esos bytes, puede almacenar un puntero a la entrada mem_dictionary posee el bloque. Esto evita la operación O (N) en forma free . Puede evitar el O (N) en malloc() implementando una cola de prioridad de bloques liberados. Considere usar un montón binomial, con tamaño de bloque como índice.