OSDev.org

So I trying to imagine how can I implement MM with this tutorial
https://wiki.osdev.org/Writing_a_memory_manager

And I wonder if I can use doubly linked list instead of header/bitmap thingy, I'm stupid , I guess my IQ only has 2 numbers so please be kind (optional)

The tutorial implements a linked list. Sure you can use a doubly linked list if you need to traverse the blocks backwards.

ChuMeoEThen wrote: ↑Wed Jan 29, 2025 10:50 pm And I wonder if I can use doubly linked list instead of header/bitmap thingy[...]

You can. musl's oldmalloc holds all managed blocks in a doubly linked list to be able to join neighboring free blocks. It also holds all free blocks in another doubly linked list called a bin to be able to quickly identify free chunks that fulfill a request.

ChuMeoEThen wrote: ↑Wed Jan 29, 2025 10:50 pm I'm stupid , I guess my IQ only has 2 numbers so please be kind (optional)

Don't do that. Don't deprecate yourself like that. You lack knowledge, but nobody was born all-knowing. We are all only human, we all only cook with water.

iansjack wrote: ↑Thu Jan 30, 2025 5:10 am The tutorial implements a linked list. Sure you can use a doubly linked list if you need to traverse the blocks backwards.

A doubly linked list has the advantage of being able to remove a block in constant time. For this reason, it is preferable to a singly-linked list for tasks that require efficient removal of nodes, and not so much efficient iteration (because cache misses wreck your performance). Iterating backwards is a mostly useless ability you also get along with that.

Though neither a linked list not a doubly linked list is the most efficient way of allocating memory. But it is probably the easiest to implement.

Memory management is a bit unprecise. Bitmaps are only used for objects of the same size, like for physical memory pages, and possibly can also be used for linear memory pages. Linked lists, including doubly linked lists, work well for malloc, which requests arbitrary size memory chunks.

You can but it is pretty inefficient except for small memory systems. Bit maps are more useful even in cases where you deal with variable-sized allocations. One approach I've used is to fix a size for your smallest allocation. For example, I pick a number like 32. Then your bit map has a bit representing 32 bytes.

Now when a request comes in for N byte, I round N up to a multiple of 32. Let's say it is some number like M. I search the bit map table for M 0 bits in a row, and that is my address. I set these bits to 1 to indicate the memory is allocated.

On the reverse side, when I am going to be given memory returned, I figure out the 'M" and given the address, locate the bits in the bit map and turn them to 0.

Of course, I do a bit more checking them blindly set bits to 0 (I need to make certain those M bits are 1's), and so on.

Hope this helps.

Let me give you a word of warning, when I started out I implemented a really bad allocator in my kernel that would just keep everything as a linked list basically. I kept it for way too long, since it was always „good enough“, but when I at some point started running into very weird performance problems, I didn‘t think much of the allocator at all.

Implementing a proper allocator will save you lots of trouble and you‘ll learn a lot doing it, so do yourself a favor and put the time in

The kernel needs several types of memory allocators. It needs a physical memory allocator, a linear (page based) memory allocator, allocator of same size objects, and a byte aligned allocator. The physical memory allocator is best implemented with a bitmap, and it makes things much easier if it is lockfree. Linear memory allocator could scan page tables, and can be used both for kernel and user mode. An allocator for same-sized objects can be implemented with a bitmap, but perhaps the byte aligned is best implemented with a linked list.

In short, a kernel doesn't just need one type, it requires several to operate in an optimal way.