Cómo implementar malloc
Antes de poder implementar malloc, se debe definir de manera relativamente formal.
Según la definición de funciones estándar de la biblioteca C, el prototipo de malloc es el siguiente:
void* malloc(size_t size);
Esta función es diseñado para asignar espacio disponible en el sistema. Los requisitos para una parte contigua de memoria son los siguientes:
El tamaño de memoria asignado por malloc es al menos el mismo que el número de bytes especificado por el parámetro de tamaño
El valor de retorno de malloc es un puntero al bloque de memoria disponible continuo. Puntero a la dirección inicial
Las direcciones asignadas por múltiples llamadas a malloc no deben superponerse a menos que se libere la dirección asignada por malloc. en una llamada específica
malloc debe completar la asignación de memoria y regresar lo antes posible (no se utiliza el algoritmo de asignación de memoria NP-hard)
Malloc debe implementarse utilizando tanto el tamaño de la memoria como la memoria funciones de desasignación (es decir, utilizando el algoritmo de asignación de memoria dura NP). e.,
Escriba el siguiente comando en la línea de comando para ver más instrucciones para malloc:
man malloc
Primero, necesitamos determinar los datos que Quiero usar estructura. Una solución simple es organizar el espacio de memoria del montón en bloques, donde cada bloque consta de una metaárea y un área de datos. La metaárea registra la metainformación del bloque (tamaño del área de datos, bandera libre, puntero, etc.). , data El área es el área de memoria asignada real y el primer byte del área de datos es la dirección devuelta por malloc.
Puedes utilizar la siguiente estructura para definir bloques:
typedef struct s_block *t_block;
struct s_block {
size_t size; /*tamaño del área de datos*/
t_block next; /*Puntero al siguiente bloque*/
int free /*Si el bloque está libre*/
int padding ;/* Relleno de 4 bytes para garantizar que la longitud del bloque de metadatos sea un múltiplo de 8*/
char data[1] /* Este es un campo virtual que representa la primera palabra de la sección del bloque de datos, cuya longitud no debe contarse en los metadatos*/
};
Dado que solo estamos considerando máquinas de 64 bits, por conveniencia rellenamos un int al final de la estructura, de modo que la estructura en sí se convierta en un múltiplo de 8 para facilitar la alineación de la memoria. El diagrama esquemático es el siguiente:
Ahora considere cómo encontrar el bloque correcto en una serie de bloques. Hay dos algoritmos generales para encontrar el bloque correcto:
El más adecuado: desde el principio, utilice el primer bloque con un área de datos mayor que el tamaño requerido para llamar al bloque asignado
Más adecuado para: comenzar desde el principio, iterar a través de todos los bloques, usar el bloque con el área de datos mayor que el tamaño y la diferencia más pequeña. El bloque de datos con la diferencia más pequeña que sea mayor que el tamaño requerido se utilizará como bloque de datos asignado.
Ambos métodos tienen sus ventajas: el mejor ajuste es más eficiente en memoria (mayor carga útil), mientras que el La primera adaptación se realiza de forma más eficiente. Aquí utilizamos el algoritmo del primer ajuste.
/*Primera adaptación*/
t_block find_block(t_block *last, size_t tamaño) {
t_block b = first_block;
while(b && !(b->libre && b->talla >= talla)) {
*último = b;
b = b->siguiente;
}
return b;
}
find_block A partir de frist_block, busque el primer bloque que cumpla con los requisitos y devuelva el punto de partida del block La dirección inicial, si no se encuentra, devuelve NULL.
last_block se actualiza durante el recorrido y siempre apunta al bloque de código atravesado actualmente. Si no se encuentra un bloque de código adecuado, se utilizará para abrir un nuevo bloque de código.
Si ninguno de los bloques existentes cumple con el requisito de tamaño, se creará un nuevo bloque al final de la lista vinculada. La clave aquí es cómo crear una estructura usando solo sbrk:
#define BLOCK_SIZE 24 /* sizeof no puede calcular correctamente la metalongitud debido a la presencia de campos de datos ficticios.
t_block extend_heap(t_block último, size_t s) {
t_block b;
b = sbrk(0);
if( sbrk(BLOCK_SIZE + s) == (void *)-1)
return NULL;
b->tamaño = s;
b->siguiente = NULL;
si(último)
último->siguiente = b;
b->gratis = 0;
regresar b;
}
El primer ajuste tiene un defecto fatal, es decir, puede hacer que datos pequeños ocupen un bloque de datos grande. En este momento, para mejorar la carga útil, si el área de datos restante es lo suficientemente grande, se debe dividir en un nuevo bloque de datos. El diagrama esquemático es el siguiente:
Código de implementación:
void split_block(t_block b, size_t. s) {
t_block nuevo;
nuevo = b->datos + s;
nuevo->tamaño = b->tamaño - s - BLOCK_SIZE;
nuevo->tamaño = b->tamaño - s - BLOCK_SIZE;
nuevo->siguiente = b->siguiente;
nuevo->gratis = 1;
b->talla = s;
b->next = new;
}
Con el código anterior, podemos integrarlos en el código. Tenga en cuenta que primero tenemos que definir el encabezado de la lista de bloques, es decir, first_block, e inicializarlo en NULL, y necesitamos al menos BLOCK_SIZE + 8 para realizar la división.
Dado que queremos que el área de datos asignada por malloc esté alineada en 8 bytes, cuando el tamaño no es múltiplo de 8, debemos ajustar el tamaño al múltiplo más pequeño mayor que 8:
size_t align8(size_t s) {
if(s & 0x7 == 0)
return s;
return ((s >> 3) + 1) << 3;
}
#define BLOCK_SIZE 24
void *first_block=NULL;
/* Otras funciones.
..*/
void *malloc(size_t size) {
t_block b, último;
size_t s;
/* alineadas_addresses *
s = align8(size);
if(first_block) {<
/* Encuentra el bloque correcto */
last = first_block;
b = find_block(&last, s);
if(b) {
/* Dividir si es posible*/
if ((b->tamaño - s) >= ( BLOCK_SIZE + 8))
split_block(b, s);
b->libre = 0;
} else {
/* No hay bloque adecuado, abre uno nuevo */
b = extend_heap(last, s);
if(!b)
return NULL;
}
}} else {
b = extend_heap(NULL, s );
if(!b)
return NULL;
first_block = b;
}
devolver b->datos;
}