Pregunta malloc implementación?


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

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

Mi malloc Se ve como esto:

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, solo marcaría la dirección como 0 (eso indicaría que es gratis). En mi malloc, Usaría un ciclo for para buscar cualquier valor en la matriz para igualar 0 y luego asignar memoria a esa dirección. Estoy un poco confundido sobre cómo implementar esto.


26
2018-03-24 16:04


origen


Respuestas:


La forma más fácil de hacerlo es mantener una lista vinculada de bloques libres. En mallocSi la lista no está vacía, busque 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 sbrk para asignar algo de memoria del sistema operativo. en 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 eso es más grande que n. Esto solo funciona cuando align_to es un poder de dos y depende de la representación binaria de los números.

Cuando align_to es una potencia de dos, solo tiene un bit configurado, y por lo tanto 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) Asi que x & ~ (align_to - 1) pondrá a cero todos los bits bajos de x y redondearlo al múltiplo más cercano de align_to.

Finalmente, agregando align_to - 1 a size asegúrese de redondear al múltiplo de align_to (a no ser que size ya es un múltiplo de align_to en cuyo caso queremos obtener size)


20
2018-03-24 16:33



No quieres configurar el size campo de la entrada del diccionario a cero: necesitará esa información para volver a usarla. En cambio, establecer freed=1 solo cuando el bloque es liberado

No puede unir bloques adyacentes porque puede haber habido llamadas intermedias sbrk(), así que eso hace que esto sea más fácil. Solo necesitas una for loop 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;
        }
    }
}

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


8
2018-03-24 16:17



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

5
2017-10-07 23:16