Writing your own good memory manager

Good time of day, reader. Perhaps you have already read my previous articles, and you know that I am writing my own OS. Today we will talk and consider a simple and fast enough memory management algorithm - a memory manager is a critical part of the OS, because fast, reliable and non-memory memory is a pledge of a good OS.
I was looking for simple and adequate ideas for the manager in RuNet, and on English-language sites - I still could not find any good articles about adequate, not working for O (N) allocator. Well, today we are going to consider a better idea for the memory manager, I’m going to continue the text under cat.

Theory

From a wiki: A memory manager is a part of a computer program (both an application and an operating system) that processes requests for allocating and freeing RAM or (for some computer architectures) requests for the inclusion of a given memory area in the processor’s address space.

I suggest also to read this article before continuing.

Watermak Allocator

Well, probably the easiest of all the allocators is the Watermark Allocator. Its essence is approximately the following: the whole memory is divided into blocks, the block has a header containing the size of this and the previous block, the block status (busy / free), knowing the block address, we can get the address of the next and previous block for O (1).
')

Memory allocation

To allocate memory, we simply need to run in blocks, and look for a block whose size is greater than or equal to the size required for allocating memory. As you already understood, the asymptotic behavior of O (N) is bad.

Memory release

To free up memory, we just need to set the block status as “free” - O (1) - super!

But, as you understand, holes can start to form, in which 2 or more free blocks - the memory is defragmented, when released, you can view the next blocks, and in the case when one or two are free - merge them into one.

Allocator for logarithmic speed

We know that we need to search only among the free blocks. Running only for free improves speed on average twice, but it's still a line. Well, why should we run through all the blocks, looking for size, if we can organize a tree of free blocks! Initially, we have only one free block, and then we add free blocks to the binary search tree, the key will be the block size. Thus, to allocate memory, it is enough for us to find a block in a tree whose size is greater than or equal to what we need. We calmly do this for O (log N), just going down the tree. Then we either cut the block in two, or completely give it to the one who requested the memory. Next we remove the block from the tree in O (1). And, if necessary, insert the rest of the block back for O (log N). For release, we just need to insert the block back, and do not forget about fragmentation.

It is logical that you do not need to use a simple tree, you must use a self-balancing tree, Red-Black or AVL. You can store a tree of blocks in a static array, or figure out how to do it differently.

Actually, the code:

char * malloc(size_t size) { if (!size) { return 0; } char * addr = 0; int i; for (i = 0; i < allocationAvlTree.size; ) { int r; node_t *n; n = &allocationAvlTree.nodes[i]; /* couldn't find it */ if (!n->key) { return NULL; } r = allocationAvlTree.cmp(n->key, size); if (r <= 0) { //We're lucky today. //Get memory block header alloc_t * block = (size_t)n->val - sizeof(alloc_t); //Set to used block->status = 1; //Set size block->size = size; alloc_t * next = (size_t)n->val + size; next->prev_size = size; next->status = 0; next->size = n->key - size - 16; avltree_remove(&allocationAvlTree, n->key, n->val); if (n->key - size - 16) avltree_insert(&allocationAvlTree, next->size, (size_t)next + sizeof(alloc_t)); memset((size_t)block + sizeof(alloc_t), 0, block->size); block->signature = 0xDEADBEEF; unlockTaskSwitch(); return (size_t)block + sizeof(alloc_t); } else if (r > 0) i = __child_r(i); else assert(0); } return 0; } void free(void * mem) { if (!mem) return; //Get current alloc alloc_t * alloc = ((unsigned int)mem - sizeof(alloc_t)); if (alloc->signature != 0xDEADBEEF) return; alloc->status = 0; alloc_t * left = ((unsigned int)alloc - sizeof(alloc_t) - alloc->prev_size); if (left->signature == 0xDEADBEEF&&left->status == 0&&left->size==alloc->prev_size) { //Merge blocks if (avltree_remove(&allocationAvlTree, left->size, (uint)left + sizeof(alloc_t))) { left->size += sizeof(alloc_t) + alloc->size; alloc = left; } else assert(0); } alloc_t * right = (uint)alloc + sizeof(alloc_t) + alloc->size; if (right->prev_size&&right->status == 0&&right->signature == 0xDEADBEEF) { if (avltree_remove(&allocationAvlTree, right->size, (uint)right + sizeof(alloc_t))) alloc->size += sizeof(alloc_t) + right->size; else assert(0); } avltree_insert(&allocationAvlTree, alloc->size, (uint)alloc + sizeof(alloc_t)); } 

Good luck and ethical hacking! Any objective criticism is welcome, the purpose of the article is not to say that it is a wah which allocator, but simply to tell about the allocator, which will be better than the stupid implementations of simple allocators.