Desarrollo de un sistema operativo monolítico similar a Unix - Heap (4)

En el artículo anterior, implementamos el registro del sistema del núcleo. Ahora es el momento de implementar un administrador de memoria dinámico.

Tabla de contenidos

1. Sistema de construcción (marca, gcc, gas). Arranque inicial (arranque múltiple). Lanzamiento (qemu). Biblioteca C (strcpy, memcpy, strext).
2. Biblioteca C (sprintf, strcpy, strcmp, strtok, va_list ...). Creación de la biblioteca en modo kernel y modo de aplicación de usuario.
3. El registro del sistema del núcleo. Memoria de video Salida a la terminal (kprintf, kpanic, kassert).
4. Memoria dinámica, montón (kmalloc, kfree).
5. Organización de memoria y manejo de interrupciones (GDT, IDT, PIC, syscall). Excepciones
6. Memoria virtual (directorio de páginas y tabla de páginas).
7. Proceso. Planificador Multitarea Sistema de llamadas (kill, exit, ps).
8. El sistema de archivos del kernel (initrd), elf y sus componentes internos. Sistema de llamadas (exec).
9. Controladores de dispositivos de caracteres. Llamadas del sistema (ioctl, fopen, fread, fwrite). Biblioteca C (fopen, fclose, fprintf, fscanf).
10. Shell como un programa completo para el kernel.
11. Modo de protección del usuario (anillo3). Segmento de estado de la tarea (tss).

Memoria dinámica del núcleo. Un montón

La interfaz del montón del núcleo se verá así:

void *kmalloc(size_t size); void kfree(void *addr); 

Como todavía no hay montones, los registros de las regiones de memoria ocupada y libre deberán almacenarse.
en una variedad de tamaño limitado. Cuanto menor es la dimensión, menor es la capacidad de almacenamiento dinámico en
pequeños fragmentos En Linux, por ejemplo, muchas estructuras de kernel se almacenan en reutilizables.
memoria que no cambia de tamaño cuando se libera (losa). Pero todavía estamos lejos de esto,
porque el desarrollo es un proceso iterativo.

Cualquier elemento que intente ser un elemento de una lista organizada a través de una matriz
requerido para implementar una interfaz.

 struct slist_head_t { struct slist_head_t *prev; struct slist_head_t *next; bool is_valid; void *data; } attribute(packed); 

No hay interfaces en C, pero no son necesarias. Simplemente lanzamos el puntero de cualquier objeto al tipo struct slist_head_t * si este objeto tiene el siguiente aspecto físico:

 struct my_list_entry_t { struct slist_head_t list_head; ... } 

Pero para que el algoritmo generalizado conozca la dimensión de la matriz en la que se almacenará la lista
y el tamaño de su elemento, el primer y último elemento de la lista y la dirección de la matriz en la que
se almacena una lista, cada función de la lista operativa necesitará otro puntero
a la estructura de definición de lista:

 struct slist_definition_t { size_t base; u_int slots; size_t slot_size; struct slist_head_t *head; struct slist_head_t *tail; }; 

Las funciones para operar la lista se verán así:

 struct slist_head_t *slist_insert_entry_after(struct slist_definition_t *list, struct slist_head_t *pos); struct slist_head_t *slist_insert_entry_before(struct slist_definition_t *list, struct slist_head_t *pos); void slist_delete_entry(struct slist_definition_t *list, struct slist_head_t *entry); 

Insertar algoritmo de función:
Encuentre una ranura libre en la matriz.
Llénalo con un nuevo elemento.
Corrija los punteros de elementos de lista adyacentes lógicamente (no físicamente).
Marque la ranura como ocupada.
Ajuste el principio y el final de la lista.

El algoritmo de la función para eliminar de la lista:
Corrija los punteros de elementos de lista adyacentes lógicamente (no físicamente).
Ajuste el principio y el final de la lista.
Marcar ranura como libre.

La memoria dinámica se describe mediante una lista con los siguientes elementos:

 struct kheap_entry_t { struct slist_head_t list_head; /* should be at first */ size_t addr; /* physical address */ size_t size; /* memory block size */ bool is_buzy; /* whether block used */ } attribute(packed); 

Una matriz que describe la memoria dinámica de dichos registros se ve así:

 struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES]; 

La definición de una lista de regiones de memoria se ve así:

 struct slist_definition_t kheap_list = { .head = null, .tail = null, .slot_size = sizeof(struct kheap_entry_t), .slots = KHEAP_MAX_ENTRIES, .base = (size_t)kheap_blocks}; 

Entonces, hemos descrito la memoria dinámica. Toda la memoria dentro de un cierto rango
se divide en bloques de tamaño arbitrario, cada uno de los cuales puede estar vacío,
ya sea ocupado Además, cada bloque se describe mediante un elemento de matriz con el indicador is_valid = true,
que es un elemento de la lista

Ahora considere el algoritmo de asignación de montón más simple (kmalloc):
Si no hay bloques libres, seleccione un nuevo bloque del tamaño requerido (pero no más que el tamaño máximo de almacenamiento dinámico).

De lo contrario, miramos a través de todos los bloques libres. Si encontramos un bloque libre, mira su tamaño. Si es suficiente, tómalo. Si hay un excedente, cree un nuevo bloque vacío del tamaño del exceso. De lo contrario, si es insuficiente y el último, ampliamos el límite de almacenamiento dinámico (pero no más que el máximo).

 /* * Api - Kernel memory alloc */ extern void* kmalloc(size_t size) { struct kheap_entry_t* current_data = null; struct slist_head_t* current = null; struct slist_head_t* head = kheap_list.head; assert(size > 0); /* try to use free block */ for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->is_buzy) { continue; } /* check size is not enough */ if (current_data->size < size) { /* try to ask contribution from free left sibling */ if (current->prev != null) { /* left sibling has found */ struct slist_head_t* sibling = current->prev; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether left sibling is free */ if (!sibling_data->is_buzy) { /* ask lack from left sibling */ size_t lack = size - current_data->size; sibling_data->size -= lack; current_data->addr -= lack; current_data->size += lack; assert(current_data->size == size); /* whether left sibling is collapsed */ if (sibling_data->size == 0) { slist_delete_entry(&kheap_list, sibling); } /* occupy block */ current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to extend borders */ if (current->next == null) { size_t heap_end_addr = current_data->addr + current_data->size; size_t lack = size - current_data->size; /* check free memory size is enought */ if (heap_end_addr + lack < KHEAP_END_ADDR) { /* occupy block */ current_data->size += lack; current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } } else { /* occupy block */ current_data->is_buzy = true; size_t surplus = current_data->size - size; bool is_sibling_bizy = false; /* try to contribute free right sibling */ if (current->next != null) { /* sibling has found */ struct slist_head_t* sibling = current->next; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; /* check whether sibling is free */ is_sibling_bizy = sibling_data->is_buzy; if (!is_sibling_bizy) { /* give surplus to right sibling */ current_data->size -= surplus; sibling_data->addr -= surplus; sibling_data->size += surplus; assert(current_data->size == size); } } /* try to give surplus to new right sibling */ if (current->next == null || is_sibling_bizy) { { struct slist_head_t* new_sibling; new_sibling = slist_insert_entry_after(&kheap_list, current); struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)new_sibling->data; if (new_sibling != null) { /* give surplus to new right sibling */ assert((size_t)new_sibling == (size_t)sibling_data); current_data->size -= surplus; assert(current_data->size > 0); sibling_data->is_buzy = false; sibling_data->addr = current_data->addr + current_data->size; sibling_data->size = surplus; } } } assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; /* suitable block has found */ } } /* try to alloc new block */ size_t heap_end_addr = KHEAP_START_ADDR; /* calculate heap end address */ if (kheap_list.tail) { current = kheap_list.tail; current_data = (struct kheap_entry_t*)current->data; heap_end_addr = current_data->addr + current_data->size; } /* check free memory size is enought */ if (heap_end_addr + size >= KHEAP_END_ADDR) { abort("heap size exceeded\n"); } /* allocate new heap memory block */ struct slist_head_t* tail = kheap_list.tail; current = slist_insert_entry_after(&kheap_list, kheap_list.tail); current_data = (struct kheap_entry_t*)current->data; assert((size_t)current == (size_t)current_data); current_data->addr = heap_end_addr; current_data->size = size; current_data->is_buzy = true; assert(current->next == null); assert(current->prev == tail); assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; } 

El algoritmo sin memoria será similar (kfree):
Encuentre un bloque cuya dirección comience con la dirección que se va a liberar. Comprueba que esté ocupado. Marcar como gratis.

Si hay un vecino libre a la derecha o izquierda para unirse con él en una cuadra.

 /* * Api - Kernel memory free */ extern void kfree(void* addr) { struct slist_head_t* current = null; struct kheap_entry_t* current_data = null; struct slist_head_t* head = kheap_list.head; for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->addr == (size_t)addr && current_data->is_buzy) { struct slist_head_t* prev = current->prev; struct slist_head_t* next = current->next; struct kheap_entry_t* prev_data = prev != null ? (struct kheap_entry_t*)prev->data : null; struct kheap_entry_t* next_data = next != null ? (struct kheap_entry_t*)next->data : null; /* free block */ current_data->is_buzy = false; /* try to merge with free left sibling */ if (prev != null && !prev_data->is_buzy) { prev_data->size += current_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)current); } /* try to merge with free right sibling */ if (next != null && !next_data->is_buzy) { current_data->size += next_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)next); } return; } } abort("invalid address to free\n", addr); } 

Eso es todo. ¡Hasta la próxima!

Referencias

Ahora, abra el video tutorial
Y mire el repositorio de git en paralelo (necesita una rama de lección4)

Referencias

1. James Molloy. Haga rodar su propio sistema operativo de clones UNIX de juguete.
2. Dientes. Ensamblador para DOS, Windows, Unix
3. Kalashnikov. ¡Ensamblador es fácil!
4. Tanenbaum. Sistemas operativos Implementación y desarrollo.
5. Robert Love. Kernel de Linux Descripción del proceso de desarrollo.