Desenvolvendo um sistema operacional monolítico semelhante a Unix - Heap (4)

No artigo anterior, implementamos o log do sistema do kernel. Agora é hora de implementar um gerenciador de memória dinâmico.

Sumário

1. Construa o sistema (marca, gcc, gás). Inicialização inicial (inicialização múltipla). Iniciar (qemu). Biblioteca C (strcpy, memcpy, strext).
2. Biblioteca C (sprintf, strcpy, strcmp, strtok, va_list ...). Construindo a biblioteca no modo kernel e no modo de aplicativo do usuário.
3. O log do sistema do kernel. Memória de vídeo Saída para o terminal (kprintf, kpanic, kassert).
4. Memória dinâmica, heap (kmalloc, kfree).
5. Organização da memória e manipulação de interrupções (GDT, IDT, PIC, syscall). Exceções
6. Memória virtual (diretório e tabela de páginas).
7. Processo. Planejador Multitarefa. Chamadas do sistema (interrupção, saída, ps).
8. O sistema de arquivos do kernel (initrd), elf e seus internos. Chamadas do sistema (exec).
9. Drivers de dispositivo de caracteres. Chamadas do sistema (ioctl, fopen, fread, fwrite). Biblioteca C (fopen, fclose, fprintf, fscanf).
10. Shell como um programa completo para o kernel.
11. Modo de proteção do usuário (anel3). Segmento de status da tarefa (tss).

Memória dinâmica do kernel. Um monte

A interface de heap do kernel terá a seguinte aparência:

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

Como ainda não existem pilhas, os registros das regiões de memória livre e ocupada deverão ser armazenados
em uma matriz de tamanho limitado. Quanto menor a dimensão, menor a capacidade da pilha
pequenos fragmentos. No Linux, por exemplo, muitas estruturas do kernel são armazenadas em
memória que não muda de tamanho quando liberada (placa). Mas ainda estamos longe disso,
porque o desenvolvimento é um processo iterativo.

Qualquer elemento que pretenda ser um elemento de uma lista organizada através de uma matriz
necessário para implementar uma interface.

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

Não há interfaces em C, mas elas não são necessárias. Simplesmente convertemos o ponteiro de qualquer objeto no tipo struct slist_head_t * se esse objeto se parecer fisicamente com isso:

 struct my_list_entry_t { struct slist_head_t list_head; ... } 

Mas para que o algoritmo generalizado conheça a dimensão da matriz na qual a lista será armazenada
e o tamanho do seu elemento, o primeiro e o último elemento da lista e o endereço da matriz na qual
uma lista é armazenada, cada função da lista de operações precisará de outro ponteiro
à estrutura de definição da 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; }; 

As funções para operar a lista ficarão assim:

 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); 

Algoritmo da função de inserção:
Encontre um espaço livre na matriz.
Preencha com um novo elemento.
Corrija os ponteiros dos itens de lista adjacentes logicamente (e não fisicamente).
Marque o slot como ocupado.
Ajuste o início e o fim da lista.

O algoritmo da função a ser removido da lista:
Corrija os ponteiros dos itens de lista adjacentes logicamente (e não fisicamente).
Ajuste o início e o fim da lista.
Marque o slot como livre.

A memória dinâmica é descrita por uma lista com os seguintes itens:

 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); 

Uma matriz que descreve a memória dinâmica desses registros se parece com isso:

 struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES]; 

Definir uma lista de regiões de memória é assim:

 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}; 

Então, nós descrevemos a memória dinâmica. Toda a memória dentro de um determinado intervalo
é dividido em blocos de tamanho arbitrário, cada um dos quais pode estar vazio,
quer ocupado. Além disso, cada bloco é descrito por um elemento da matriz com o sinalizador is_valid = true,
que é um item da lista.

Agora considere o algoritmo mais simples de alocador de heap (kmalloc):
Se não houver blocos livres, selecione um novo bloco do tamanho necessário (mas não mais que o tamanho máximo da pilha).

Caso contrário, examinamos todos os blocos livres. Se encontrarmos um bloco livre, observe seu tamanho. Se for o suficiente, pegue. Se houver um excedente, crie um novo bloco vazio do tamanho do excedente. Caso contrário, se for insuficiente e o último, expandiremos o limite do heap (mas não mais que o 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; } 

O algoritmo sem memória será semelhante (kfree):
Encontre um bloco cujo endereço comece com o endereço a ser liberado. Verifique se ele está ocupado. Marcar como livre.

Se houver um vizinho livre à direita ou esquerda para se unir a ele em um quarteirão.

 /* * 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); } 

Só isso. Até a próxima!

Referências

Agora, abra o tutorial em vídeo
E assista o repositório git em paralelo (você precisa de um ramo da lição4)

Referências

1. James Molloy. Role seu próprio sistema operacional clone do UNIX de brinquedo.
2. Dentes. Assembler para DOS, Windows, Unix
3. Kalashnikov. Assembler é fácil!
4. Tanenbaum. Sistemas operacionais. Implementação e desenvolvimento.
5. Robert Love. Kernel Linux Descrição do processo de desenvolvimento.