malloc implementation?

Question

Estoy tratando de implementar malloc y free para C, y no estoy seguro de cómo volver a utilizar la memoria. Actualmente tengo un struct que tiene este aspecto:

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

Mi malloc se parece a 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 la memoria libre, me acaba de marcar la dirección como 0 (que indicaría que se trata de gratis). En mi malloc, utilizaría un bucle for para buscar cualquier valor en la matriz igual a 0 y luego asignar memoria a esa dirección. Estoy un poco confundido sobre cómo implementar esto.

Answer 1

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

No se pueden combinar los bloques adyacentes porque es posible que haya habido llamadas intermedias al sbrk(), por lo que esto es más fácil. Sólo se necesita un bucle for la que busca para 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 una gran malloc() aplicación. De hecho, la mayoría de las implementaciones malloc/free 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 a la entrada mem_dictionary que posee 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. Considere usar un binomial montón, con tamaño de bloque como el índice.

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 al sbrk para asignar parte de la 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 implementación de ejemplo (que no se ha probado, y, obviamente, no es seguro para subprocesos, utilice a 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 es más grande que n. Esto solo funciona cuando align_to tiene una potencia de dos y depende de la representación binaria de los números.

Cuando align_to es una potencia de dos, que sólo tiene un conjunto de bits, y por lo tanto align_to - 1 tiene todos los conjuntos de bits más bajas (es decir. align_to es de la forma 000 ... 010 ... 0, y es de align_to - 1 el formulario 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 el formato 111...110...0).Así x & ~ (align_to - 1) se pone a cero todos los bits bajos de x y se redondea al múltiplo más próximo de align_to.

Por último, la adición de align_to - 1 a size asegurar que rodeo al múltiplo más cercano de align_to (a menos size ya es un múltiplo de align_to en cuyo caso queremos obtener size).

Answer 3

Tomo prestado código de 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 esta free_block como cabecera 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 libre que se llama, la dirección de la partida de la cabecera para el bloque se calcula (restando el tamaño de la cabecera de la dirección de bloque) y que se añade a la piscina bloque libre.

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