In the
previous article, we implemented the kernel system log. Now it's time to implement a dynamic memory manager.
Table of contents
- Build system (make, gcc, gas). Initial boot (multiboot). Launch (qemu). C library (strcpy, memcpy, strext).
- C library (sprintf, strcpy, strcmp, strtok, va_list ...). Building the library in kernel mode and user application mode.
- The kernel system log. Video memory Output to the terminal (kprintf, kpanic, kassert).
- Dynamic memory, heap (kmalloc, kfree).
- Organization of memory and interrupt handling (GDT, IDT, PIC, syscall). Exceptions
- Virtual memory (page directory and page table).
- Process. Scheduler. Multitasking. System calls (kill, exit, ps).
- The file system of the kernel (initrd), elf, and its internals. System calls (exec).
- Character device drivers. System calls (ioctl, fopen, fread, fwrite). C library (fopen, fclose, fprintf, fscanf).
- Shell as a complete program for the kernel.
- User protection mode (ring3). Task Status Segment (tss).
Dynamic kernel memory. A bunch
The kernel heap interface will look like this:
void *kmalloc(size_t size); void kfree(void *addr);
Since there is still no heap, records about occupied and free memory regions will have to be stored.
in an array of limited size. The smaller the dimension, the lower the heap capacity by
small fragments. On Linux, for example, many kernel structures are stored in reusable
memory that does not change size when released (slab). But we are still far from that,
because development is an iterative process.
Any element that intends to be an element of a list organized through an array
required to implement an interface.
struct slist_head_t { struct slist_head_t *prev; struct slist_head_t *next; bool is_valid; void *data; } attribute(packed);
There are no interfaces in C, but they are not needed. We simply cast the pointer of any object to the type struct slist_head_t * if this object physically looks like this:
struct my_list_entry_t { struct slist_head_t list_head; ... }
But so that the generalized algorithm knows the dimension of the array in which the list will be stored
and the size of its element, the first and last element of the list and the address of the array in which
a list is stored, each function of the operating list will need another pointer
to the list definition structure:
struct slist_definition_t { size_t base; u_int slots; size_t slot_size; struct slist_head_t *head; struct slist_head_t *tail; };
The functions for operating the list will look like this:
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);
Insert Function Algorithm:
Find a free slot in the array.
Fill it with a new element.
Correct the pointers of logically (not physically) adjacent list items.
Mark slot as busy.
Adjust the beginning and end of the list.
The algorithm of the function to remove from the list:
Correct the pointers of logically (not physically) adjacent list items.
Adjust the beginning and end of the list.
Mark slot as free.
Dynamic memory is described by a list with the following items:
struct kheap_entry_t { struct slist_head_t list_head; size_t addr; size_t size; bool is_buzy; } attribute(packed);
An array describing dynamic memory from such records looks like this:
struct kheap_entry_t kheap_blocks[KHEAP_MAX_ENTRIES];
Defining a list of memory regions looks like this:
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};
So, we have described dynamic memory. All memory within a certain range
is divided into blocks of arbitrary size, each of which can be either empty,
either busy. In addition, each block is described by an array element with the flag is_valid = true,
which is a list item.
Now consider the simplest heap allocator algorithm (kmalloc):
If there are no free blocks, select a new block of the required size (but no more than the maximum heap size).
Otherwise, we look through all the free blocks. If we find a free block, look at its size. If it is enough, take it. If there is a surplus then create a new empty block of the size of the surplus. Otherwise, if it is insufficient and the last one, we expand the heap boundary (but not more than the maximum).
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); for (current = head; current != null; current = current->next) { current_data = (struct kheap_entry_t*)current->data; if (current_data->is_buzy) { continue; } if (current_data->size < size) { if (current->prev != null) { struct slist_head_t* sibling = current->prev; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; if (!sibling_data->is_buzy) { size_t lack = size - current_data->size; sibling_data->size -= lack; current_data->addr -= lack; current_data->size += lack; assert(current_data->size == size); if (sibling_data->size == 0) { slist_delete_entry(&kheap_list, sibling); } current_data->is_buzy = true; assert(current_data->addr >= KHEAP_START_ADDR); assert(current_data->addr < KHEAP_END_ADDR); return (void*)current_data->addr; } } if (current->next == null) { size_t heap_end_addr = current_data->addr + current_data->size; size_t lack = size - current_data->size; if (heap_end_addr + lack < KHEAP_END_ADDR) { 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; } } } else { current_data->is_buzy = true; size_t surplus = current_data->size - size; bool is_sibling_bizy = false; if (current->next != null) { struct slist_head_t* sibling = current->next; struct kheap_entry_t* sibling_data = (struct kheap_entry_t*)sibling->data; is_sibling_bizy = sibling_data->is_buzy; if (!is_sibling_bizy) { current_data->size -= surplus; sibling_data->addr -= surplus; sibling_data->size += surplus; assert(current_data->size == size); } } 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) { 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; } } size_t heap_end_addr = KHEAP_START_ADDR; 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; } if (heap_end_addr + size >= KHEAP_END_ADDR) { abort("heap size exceeded\n"); } 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; }
The memory free algorithm will be similar (kfree):
Find a block whose address begins with the address to be freed. Check that he is busy. Flag as free.
If there is a free neighbor to the right or left to unite with him in one block.
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; current_data->is_buzy = false; if (prev != null && !prev_data->is_buzy) { prev_data->size += current_data->size; slist_delete_entry(&kheap_list, (struct slist_head_t*)current); } 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); }
That's all. Until next time!
References
Now, open the
video tutorial
And watch the
git repository in parallel
(you need a lesson4 branch)
Bibliography
1. James Molloy. Roll your own toy UNIX-clone OS.
2. Teeth. Assembler for DOS, Windows, Unix
3. Kalashnikov. Assembler is easy!
4. Tanenbaum. Operating Systems. Implementation and development.
5. Robert Love. Linux kernel Description of the development process.