usar - Función libre de C(no usa malloc)

malloc sizeof

Question

Estoy escribiendo mi propio programa de asignación de memoria (sin utilizar malloc) y ahora estoy atascado con la función gratuita (sin cargo en mi código). Creo que la funcionalidad para la asignación está allí, el único problema reside en la función gratuita. Entonces, ejecutando el código a continuación puedo asignar 32 bloques: cada bloque tiene un tamaño de 48 + 16 (tamaño del encabezado). Entonces, ¿cómo puedo desasignar / liberar todos ellos justo después de que los haya asignado? ¿Podrías echar un vistazo a mi función gratuita y señalarme en la dirección correcta?

PD: Esto es para fines de aprendizaje. Estoy tratando de entender las estructuras, las listas enlazadas, las asignaciones de memoria. Gracias por adelantado.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define BUFFER_SIZE 2048
typedef struct blk_struct
{
size_t size_blk;
struct blk_struct *next;
char data[0];
}blk_struct;
struct blk_struct *first = NULL;
static char buffer[BUFFER_SIZE];
void *asalloc(size_t size)
{
int nunits = (size + sizeof(blk_struct));
static int val = 1;
blk_struct *block, *current;
//locate position for block
if(first == NULL)
{
block = (blk_struct *)&buffer[0];
// Sanity check size.
if(nunits > BUFFER_SIZE)
return NULL;
// Initialise structure contents.
block->size_blk = size;
block->next = NULL;
// Add to linked list.
first = block;
// Give user their pointer.
return block->data;
}
//create a free list and search for a free block
for(current = first; current != NULL; current = current->next)
{
// If this element is the last element.
if(current->next == NULL)
{
block = (blk_struct *) (current->data + current->size_blk);
// Check we have space left to do this allocation
if((blk_struct *) &block->data[size] >
(blk_struct *) &buffer[BUFFER_SIZE])
{
printf("No more space/n");
return NULL;
}
// Initialise structure contents.
block->size_blk = size;
block->next = NULL;
// Add to linked list.
current->next = block;
// Give user their pointer.
return block->data;
}
}
printf("List Error/n");
return NULL;
}
// ''Free'' function. blk_ptr = pointer to the block of memory to be released
void asfree(void *blk_ptr)
{
struct blk_struct *ptr = first;
struct blk_struct *tmp = NULL;
while(ptr != NULL)
{
if(ptr == blk_ptr)
{
printf("Found your block/n");
free(blk_ptr);
break;
}
tmp = ptr;
ptr = ptr->next;
}
}
// Requests fixed size pointers
int test_asalloc(void)
{
void *ptr = NULL;
int size = 48;
int i = 1;
int total = 0;
do
{
ptr = asalloc(size);
if(ptr != NULL)
{
memset(ptr, 0xff, size);
printf("Pointer %d = %p%s", i, ptr, (i % 4 != 0) ? ", " : "/n");
// each header needs 16 bytes: (sizeof(blk_struct))
total += (size + sizeof(blk_struct));
i++;
}
asfree(ptr); // *** <--- Calls the ''free'' function ***
}
while(ptr != NULL);
printf("%d expected %zu/nTotal size: %d/n", i - 1,
BUFFER_SIZE / (size + sizeof(blk_struct)), total);
}
int main(void)
{
test_asalloc();
return 0;
}

Answer 1

Puedo ver algunos problemas con tu asfree.

Debes restar sizeof(blk_struct) cuando buscas la cabeza del bloque. Como los datos asignados que el usuario quiere liberar están justo detrás del encabezado y usted tiene un puntero a esos datos, no el encabezado.

El segundo problema es qué hacer cuando obtienes el encabezado. No puedes simplemente llamar gratis a los datos. Debe tener alguna bandera en el encabezado y marcar el bloque como libre. Y la próxima vez que trates de asignar un bloque, debes ser capaz de reutilizar bloques libres, no solo crear bloques nuevos al final. También es bueno poder dividir un bloque libre grande en dos más pequeños. Para evitar la fragmentación es necesario fusionar los bloques libres vecinos a uno más grande.

Actualmente estoy escribiendo un sistema operativo como un proyecto escolar. Te recomiendo que uses un alocator simple que funcione así:

• Los bloques de memoria tienen encabezados que contienen enlaces a bloques vecinos y bandera libre.
• Al principio hay un bloque grande con bandera libre que cubre toda la memoria.
• Cuando se llama a malloc, los bloques se buscan de principio a fin. Cuando se encuentra un bloque lo suficientemente grande, se divide en dos (asignado uno y un recordatorio gratuito). Se devuelve el puntero a los datos asignados del bloque.
• Cuando se invoca a libre, el bloque de coincidencia se marca como libre. Si los bloques vecinos también son gratuitos, se fusionan.

Creo que este es el básico para poder hacer malloc y liberar sin fragmentación y perder memoria.

Así es como se ve una estructura de encabezados y pie de página:

// Header of a heap block
typedef struct {
// Size of the block including header and footer
size_t size;
// Indication of a free block
bool free;
// A magic value to detect overwrite of heap header.
uint32_t magic;
} heap_block_head_t;
// Footer of a heap block
typedef struct {
// A magic value to detect overwrite of heap footer.
uint32_t magic;
// Size of the block
size_t size;
} heap_block_foot_t;

El montón de bloques con encabezados y pies de página como el anterior es muy parecido a una lista vinculada. Los bloques no describen explícitamente a sus vecinos, pero mientras tú estés allí, puedes encontrarlos fácilmente. Si tiene una posición de un encabezado, puede agregar el tamaño de bloque a esa posición y tiene una posición de encabezado del próximo bloque.

// Get next block
heap_block_head_t *current = ....
heap_block_head_t *next = (heap_block_head_t*)(((void*) current) + current->size);
// Get previous block
heap_block_head_t *current = ....
heap_block_foot_t *prev_foot = (heap_block_foot_t*)(((void*) current) - sizeof(heap_block_foot_t));
heap_block_head_t *prev = (heap_block_head_t*)(((void*) prev_foot) + sizeof(heap_block_foot_t) - prev_foot->size);
// Not sure if this is correct. I just wanted to illustrate the idea behind.
// Some extra check for heap start and end are needed

Espero que esto ayude.