Memory Manager

[KemyLand]

Hi!

I have a GREAT problem with Memory Management. I've tried to implement sbrk and (k)malloc myself, but I always get problems when trying to (k)free and test efficiency. I know this is a common OSDev-ing problem, but I simply can't resolve it. I've already tried porting simple memory allocation libraries, but they're just too simple. I wanna a MM that can:

• void *KAlloc(size_t)
  size_t KFree(void*)
  size_t KRealloc(void*, size_t)
  size_t KVTP(PID, void*) /* VIRTUAL TO PHYSICAL */
  size_t KMap(PID, void*, void*) /* MAP PHYSICAL TO VIRTUAL */

My syscall interface would have:

• // DO NOT USE brk(void*), I see it too dangerous
  size_t sbrk(ssize_t)

But, I don't have any ideas of the actual implementation. Hash tables, VFS virtualization? The most important problem here is the chicken-or-egg problem that the Memory Manager theory comes beautifully packaged with. If the MM needs to remember the system memory map, how does it reserves memory, for recording reserving memory? That's at least double the allocation in a single call, an would be really inefficient.

Please help me with this. I know this forum has great information, an this is a relatively too simple question

[Combuster]

You're actually mixing up the three memory systems here, and since they are almost separate, you are not going to find them together in any package
1: The VMM manages the virtual-to-physical mapping. It can modify page tables and give you the physical address for a virtual address. This essentially provides the last two functions of your list
2: The PMM manages which chunks (pages) of physical memory are in use, and which aren't.
There are a few chicken-and-egg dependencies between these two: the PMM needs mapped memory to store and access it's structures, and the VMM needs to be able to request memory to allocate fresh page tables or directories. This is usually fixed by hardcoding the minimal set of page tables and data structures, and afterwards let the PMM figure out what areas have been used before it actually got put in charge. Because these are heavily kernel-dependent parts, forget about grabbing an implementation for these.

Similarly, implement and test these before you continue with point...

3: The heap manager. Separates large chunks in smaller bits. This is what actually implements *alloc and free. It needs a PMM to get bits of available memory, and it needs a VMM to make sure it can access that memory. Consequently, this is a separate package and you might better treat it as such.

Of course, there's a wealth more detail to all of this if you search the wiki for "Memory"

[alexfru]

The most important problem here is the chicken-or-egg problem that the Memory Manager theory comes beautifully packaged with. If the MM needs to remember the system memory map, how does it reserves memory, for recording reserving memory?

The system map is usually very small. You can have a statically allocated array of, say, 128 memory ranges. Take at most 128 ranges returned from the BIOS and store them there as address & size pairs. This little array alone is sufficient to start making physical memory allocations for the page directory and page tables. Use this array as a stack. Pop a page when you need one, push it back when you don't need it any more. Initially you're only going to pop and so it can't grow at first. In 32-bit mode for 4GB of physical RAM there's 1M of 4KB pages. IOW, if you keep pushing and popping into and off this stack, the stack can expand (due to fragmentation, which you can just leave to be) and in the worst case contain ~1M of entries each containing a 32-bit physical address and a 32-bit count of 1, 8 bytes, or 8MB in total. So, after the initial page tables are set up for the kernel image, move that initially small stack into specially dedicated 8MB so it can expand there if and as needed. On top of that you can implement an address space allocator, carving out ranges for (k)malloc(), which you'd then map to physical memory using the pages popped off the stack. Think about this.

That's at least double the allocation in a single call, an would be really inefficient.

You need different allocators for different purposes. But under the hood there must be an allocator that can allocate 4KB of the address space and map a physical page there. So you begin with this and build everything else on top of it.