¿Implementación malloc?

8 minutos de lectura

avatar de usuario
usuario675257

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 parece a esto:

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 mallocluego usaría un bucle for para buscar cualquier valor en la matriz para igualar 0 y luego asigne memoria a esa dirección. Estoy un poco confundido sobre cómo implementar esto.

avatar de usuario
Sylvain Defresne

La forma más fácil de hacerlo es mantener una lista enlazada de bloques libres. En malloc, si la lista no está vacía, busca un bloque lo suficientemente grande como para satisfacer la solicitud y lo devuelve. 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 beneficio adicional, puede intentar fusionar bloques liberados contiguos, y puede cambiar la política para elegir el bloque para devolver (primer ajuste, mejor ajuste, …). También puede elegir dividir el bloque si es más grande que la solicitud.

Alguna implementación de muestra (no está probada y obviamente no es segura para subprocesos, utilícela 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 mas grande que n. Esto solo funciona cuando align_to es una potencia de dos y depende de la representación binaria de los números.

Cuándo align_to es una potencia de dos, solo tiene un bit establecido, y por lo tanto align_to - 1 tiene todos los conjuntos de bits más bajos (es decir, align_to es de la forma 000…010…0, y align_to - 1 es de la forma 000...001...1). Esto significa que ~ (align_to - 1) tiene todos los bits altos activados y los bits bajos desactivados (es decir, tiene la forma 111...110...0). Entonces x & ~ (align_to - 1) pondrá a cero todos los bits bajos de x y redondear hacia abajo al múltiplo más cercano de align_to.

Finalmente, agregando align_to - 1 para size asegurarnos de que redondeamos al múltiplo más cercano de align_to (a no ser que size ya es múltiplo de align_to en cuyo caso queremos obtener size).

  • ¿Qué hace la magia en la primera línea de la función malloc?

    – Igbanam

    4 de noviembre de 2012 a las 1:07


  • se redondea (size + sizeof(size_t)) al múltiplo más cercano de align_to eso es mas grande que (size + sizeof(size_t)). Esto solo funciona si align_to es una potencia de dos.

    – Sylvain Defresne

    4 de noviembre de 2012 a las 19:19

  • En la primera parte de la Columna 9, se usa como ejemplo una técnica similar de usar un caché de lista enlazada para mantener la memoria asignada (en lugar de asignarla de nuevo) para acelerar un programa de gráficos (que está gastando demasiado tiempo en malloc). : Code Tuning en el libro Programming Pearls de Jon Bentley. Lamentablemente, el libro no contiene código en su ejemplo, por lo que ver un código como este fue especialmente útil para mí.

    – Draco Sobania

    2 de febrero de 2015 a las 1:14


avatar de usuario
heath hunnicutt

No desea configurar el size campo de la entrada del diccionario a cero; necesitará esa información para reutilizarla. En su lugar, establecer freed=1 sólo cuando se libera el bloque.

No puede fusionar bloques adyacentes porque puede haber habido llamadas intermedias para sbrk(), por lo que hace esto más fácil. solo necesitas un for bucle que busca un bloque liberado lo 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 pequeño encabezado 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 mem_dictionary Entrada propietaria de la manzana. 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 binomio montóncon el tamaño de bloque como índice.

  • Lo siento, soy relativamente nuevo en C, pero ¿cuál es la variable del diccionario en malloc()?

    – no92

    11 de septiembre de 2013 a las 10:46


  • @ no92: debería haber llamado “diario” en lugar de “diccionario”. Recuerda, este es mi ejemplo y la implementación trivial de malloc. Tiene al menos un defecto obvio: nunca puede haber más de 1024 bloques asignados a la vez. El único propósito de dar este ejemplo es dar al lector una punto de partida por implementar su propia malloc. Esta es solo una base conceptual para implementar un malloc/free Biblioteca. Ni siquiera implementa realloc como otra deficiencia flagrante. Puede que ni siquiera sea el mejor ejemplo. 🙂

    –Heath Hunnicutt

    12 de septiembre de 2013 a las 17:12

Estoy tomando prestado el código de la respuesta de Sylvain. Parece que no calculó el tamaño de free_block* ini al calcular la sobrecarga.

En general, el código funciona anteponiendo este free_block como encabezado a la memoria asignada. 1. Cuando el usuario llama a malloc, malloc devuelve la dirección de la carga útil, justo después de este encabezado. 2. Cuando se llama a free, se calcula la dirección de inicio del encabezado del bloque (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;
}

  • Gracias, creo que esta respuesta es un poco más correcta que la respuesta de Sylvain, ya que solo me preguntaba sobre esto. La variable de gastos generales es una muy buena idea, solo que no se calculó correctamente ni se usó.

    – bill

    18/10/2014 a las 22:05

  • ¿Alguien puede decirme el uso de la cabeza en la función malloc? (free_block** head = &(free_block_list_head.next);) No veo que se use en ninguna parte. Además, ¿por qué añadimos sizeof(free_block) ¿antes de volver?

    – usuario1719160

    8 de marzo de 2016 a las 6:22


  • head es un puntero a una dirección que contiene un puntero. Se utiliza en el ciclo while para desvincular el bloque de memoria devuelto al usuario. Sumar y restar sizeof(free_block) es un truco común y ordenado para “ocultar” los metadatos de la persona que llama.

    –Björn Lindqvist

    13 de abril de 2016 a las 4:34

  • También hay un pequeño error en la implementación de free() como free(NULL) fallará en el segmento.

    –Björn Lindqvist

    13 de abril de 2016 a las 4:35

  • Hola, puedes agregar adecuado realloc función para esta implementación?

    – Felipe

    30 de julio de 2018 a las 10:11

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad