Después de leer los pasos básicos para escribir los núcleos de Hello World a partir de la serie de artículos disponibles en Habré, es hora de comenzar un desarrollo serio de las herramientas más básicas: el asignador y el planificador de almacenamiento dinámico.
Importante :
1. Esta serie de lecciones para principiantes. El objetivo es formar una imagen holística del mundo. Durante mucho tiempo tuve la teoría de Tanenbaum en mi cabeza y no pude conectarla con la práctica. Para aquellos que tienen lo mismo, les dedico este artículo.
2. El código es el más simple y tonto, pero lo más claro posible. Mi objetivo es darle una comprensión para que pueda escribir su propio núcleo, mucho más genial que eso.
3. Publicaré el repositorio tan pronto como lo considere listo para una amplia gama. Escribo una pequeña parte, depuro y grabo un video tutorial. No tengo un producto terminado.
Honestamente, pensé durante mucho tiempo si valía la pena comenzar a escribir artículos y hacer tutoriales en video sobre un tema tan candente. Pero la pasión por la programación del sistema y la falta de información estructurada en ruso, sin embargo, me empujaron a este experimento. Por lo tanto, si mi trabajo está en demanda, planeo publicar artículos al menos una vez al mes y no más de una vez a la semana.
Soñé con escribir mi sistema operativo en el décimo grado. El libro de Tanenbaum tiene una propiedad increíble. Cualquiera que lo toque tarde o temprano comienza a soñar con escribir su propio sistema operativo. Pero no escribí nada entonces, después de darme cuenta de que es imposible compilar y vincular un binario limpio con un código en un mastday. Tenía que estudiar Linux, ir a la universidad, ir a trabajar. Todo sería nada. Sí, solo un sueño se hizo realidad solo diez años después. Ahora, inventando moldes aburridos en React, miro hacia atrás, recuerdo la pasión con la que pasé horas por el desensamblador y el depurador, quité los empacadores, rompí las cajas de crack, leí muchos artículos de novelas escolares por la noche ... y entiendo que mi vida podría haber sido diferente. Muy diferente Si tan solo tuviera una persona que pudiera ayudarme desde el principio. Pero el tiempo se ha ido. Los programas se han vuelto difíciles de romper. El kernel de Linux ha crecido a tamaños increíbles. Aparecieron hipervisores. El ensamblador de Intel se ha vuelto tan grande que al mirar una lista de comandos en el manual, desaparece cualquier entusiasmo por aprender al respecto. Teníamos que ganar pan en la web. Si El mundo de la programación de sistemas ha sobrevivido a sus años dorados.
Por lo tanto, a todos los estudiantes cuyo entusiasmo no se ha agotado, les dedico un tutorial detallado sobre cómo tomar y escribir desde cero el núcleo de microkernel multitarea más simple con su propio caparazón. Y quiero advertir a todos que todavía no ha aparecido que se trata de un asunto ingrato e inútil, aunque terriblemente interesante. Y la juventud, como saben, tiene sus propias preocupaciones.
Vamos!
Este
artículo contiene un video tutorial filmado en mi estudio casero. Está dedicado directamente al código.
Comencemos a desarrollar un administrador de almacenamiento dinámico.
extern void *kmalloc(size_t size); extern void kfree(void *addr);
Para escribir un asignador de almacenamiento dinámico, debe almacenar las regiones de direcciones libres y ocupadas. Esto es más fácil de implementar como una lista direccional. La implementación de una lista dirigida en sí tendrá que hacerse a través de una matriz estática.
struct slist_head_t { struct slist_head_t *prev; struct slist_head_t *next; bool is_valid; void *data; } attribute(packed); struct slist_definition_t { size_t base; u_int slots; size_t slot_size; struct slist_head_t *head; struct slist_head_t *tail; };
Los elementos de una lista tan limitada serán registros de regiones de memoria. Además, entre regiones adyacentes no puede haber agujeros. Si hay memoria libre, se describe mediante un elemento de lista separado.
struct kheap_entry_t { struct slist_head_t list_head; size_t addr; size_t size; bool is_buzy; } attribute(packed); struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES]; 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 };
Al comienzo de la estructura kheap_entry_t es slist_head_t, que le permite convertir sin problemas el tipo de registro de montón en 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).
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.
El siguiente artículo se centrará en la implementación del algoritmo de almacenamiento dinámico.
Escribamos el planificador más simple. La tarea se verá así:
struct task_t { struct clist_head_t list_head; u_short tid; struct gp_registers_t gp_registers; struct op_registers_t op_registers; struct flags_t flags; u_int time; bool reschedule; u_short status; int msg_count_in; struct message_t msg_buff[TASK_MSG_BUFF_SIZE]; void *kstack; void *ustack; } attribute(packed); struct clist_definition_t task_list = { .head = null, .slot_size = sizeof(struct task_t) };
Ya sabemos cómo asignar memoria y, por lo tanto, organizar las tareas como una lista de anillo. Por lo tanto, es más conveniente realizar la siguiente tarea en relación con la actual con el estado deseado (usaremos el estado TASK_RUNNING si se realiza la tarea). Para comenzar, asumiremos que todas las tareas se realizan en el anillo de protección del núcleo (es más fácil depurar el programador) y nos las arreglamos con una pila. En el futuro fijaremos TSS.
Resolvimos las tareas, ahora la planificación misma. Agregue un controlador de temporizador al IDT y habilite la interrupción de la línea IRQ deseada en el PIC. Al interrumpir el temporizador (y al final del código de inicialización del núcleo), transferimos el control al planificador, pasando la dirección de retorno y la dirección de los registros guardados previamente desde la interrupción del temporizador:
/* * Handle IRQ0 * void asm_ih_timer(unsigned long *addr) */ asm_ih_timer: cli pushal mov %esp,%ebp mov %ebp,%ebx pushl %ebx # ® add $32,%ebx pushl %ebx # &ret addr call ih_timer mov %ebp,%esp popal sti iretl
En el planificador, verificamos si se realizó alguna tarea en este momento. Si es así, aumentamos el contador de su tiempo de ejecución y vemos si excede la cuota. Si no, regresa con calma. Si excede, necesita reprogramar la tarea. Guardamos su estado (la dirección de los registros guardados y la dirección de retorno almacenada en la pila al interrumpir el temporizador serán útiles).
current_task->op_registers.eip = *ret_addr; current_task->op_registers.cs = *(u16 *)((size_t)ret_addr + 4); *(u32 *)(¤t_task->flags) = *(u32 *)((size_t)ret_addr + 6) | 0x200; current_task->op_registers.u_esp = (size_t)ret_addr + 12; current_task->gp_registers.esp = current_task->op_registers.u_esp; memcpy(¤t_task->gp_registers, (void *)reg_addr, sizeof(struct gp_registers_t));
Tomamos la dirección de pila de la nueva tarea y formamos un marco de retorno para el comando iret allí. Luego llamamos a la función ensamblador para cambiar el contexto.
next_task->op_registers.u_esp -= 4; *(u32 *)(next_task->op_registers.u_esp) = (*(u16 *)(&next_task->flags)) | 0x200; next_task->op_registers.u_esp -= 4; *(u32 *)(next_task->op_registers.u_esp) = next_task->op_registers.cs; next_task->op_registers.u_esp -= 4; *(u32 *)(next_task->op_registers.u_esp) = next_task->op_registers.eip; next_task->gp_registers.esp = next_task->op_registers.u_esp; next_task->op_registers.u_esp -= sizeof(struct gp_registers_t); memcpy((void *)next_task->op_registers.u_esp, (void *)&next_task->gp_registers, sizeof(struct gp_registers_t)); current_task = next_task; asm_switch_context(next_task->op_registers.u_esp);
El cambio de contexto en sí se ve así:
# # Switch context # void asm_switch_context(u32 esp) # asm_switch_context: mov 4(%esp),%ebp # ebp = esp mov %ebp,%esp popal sti iretl
El planificador está listo.
Vea el código completo
en el video tutorial adjunto al artículo. Considera no solo el planificador, sino también el proceso de carga, compilación y configuración de IDT para aquellos que han olvidado: