Developing a monolithic Unix-like OS - Heap (4)

In the previous article, we implemented the kernel system log. Now it's time to implement a dynamic memory manager.

Table of contents

1. Build system (make, gcc, gas). Initial boot (multiboot). Launch (qemu). C library (strcpy, memcpy, strext).
2. C library (sprintf, strcpy, strcmp, strtok, va_list ...). Building the library in kernel mode and user application mode.
3. The kernel system log. Video memory Output to the terminal (kprintf, kpanic, kassert).
4. Dynamic memory, heap (kmalloc, kfree).
5. Organization of memory and interrupt handling (GDT, IDT, PIC, syscall). Exceptions
6. Virtual memory (page directory and page table).
7. Process. Scheduler. Multitasking. System calls (kill, exit, ps).
8. The file system of the kernel (initrd), elf, and its internals. System calls (exec).
9. Character device drivers. System calls (ioctl, fopen, fread, fwrite). C library (fopen, fclose, fprintf, fscanf).
10. Shell as a complete program for the kernel.
11. 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; /* should be at first */ size_t addr; /* physical address */ size_t size; /* memory block size */ bool is_buzy; /* whether block used */ } 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).

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

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.

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

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.