Virtual Memory Mananger Design

[FlashBurn]

I´have just programed my VMM, but came across a big problem. To keep a long story short the failure in my design is that I need my slab allocator to make my VMM work, but the slab allocator needs the VMM and I can not call the VMM if I am working on it's structure.

So here I am. My actual VMM system is that I have an AVL tree where I put in memory regions which are sorted by the base address and then I have a second AVL tree where the regions are sorted by size. I use 2 AVL trees, because I can merge 2 or 3 regions by searching the bases and endings and I can allocate a region by searching by size.

My question now is what are you using for your VMM? I need a new design and do not know a good way so that I can allocate memory, but also address ranges.

[madeofstaples]

I've been very interested in the two-level segregated fit (TLSF) algorithm, although it's discussed usually as a heap allocator; I've been thinking about whether or not it would be beneficial to apply the same idea to the virtual memory manager.

If you have access to scientific journals (e.g, via a University library), this paper is very good (with access, can be downloaded from http://portal.acm.org/citation.cfm?id=1394967):
Masmano M, Ripoll I, Real J, Crespo A, Wellings AJ. Implementation of a constant-time dynamic storage allocator. Software: Practice and Experience. 2008;38(10).

Otherwise, I'm sure you could find more information via google.

As for your issue of needing your vmm to be complete in order to write it in the first place: I'm not exactly sure how you're going about this, so I can't tell if you're simply having a brain fart or not, but could you (or shouldn't you) keep critical parts of your vmm code at a designated virtual and physical address, probably identity-mapped (i.e, virtual address=physical address, at least to start off)? Then this would all be set up from the vmm initialization...

Hope that helps and good luck

[FlashBurn]

The problem with my vmm is that it could happen that I need to call my slab allocator (out of the vmm) to get an object and that this slab has no free mem and needs to alloc new mem and he is doing this with calling the vmm, but this can´t work, because I´m working on the vmm structures and waiting for the mem from the slab, so I have a race condition

I will have a look at this paper if I can find something through google.

It would help if someone could point me at a design could manage areas of memory (I mean allocaing/deallocating and merging an area).

[madeofstaples]

It would help if someone could point me at a design could manage areas of memory (I mean allocaing/deallocating and merging an area).

Puaut I. Real-time performance of dynamic memory allocation algorithms. In: Real-Time Systems, 2002. Proceedings. 14th Euromicro Conference on.; 2002:41–49.

Gives a comprehensive overview and analysis of different dynamic memory allocation algorithms, also discusses what you call merging (they use the term coalescing).

Seems to be freely available here (download link)

[FlashBurn]

Yeah I´ve found it, but I have to reread it sometimes before I really get the point.

[Combuster]

My memory management is just a bunch of reference counting tables. Userspace can define the implementation exokernel style.

To avoid deadlocks due to unmapped structures, I reserve an unmapped region where the pagetable for it is guaranteed to exist (and use algorithms that use fixed amounts of address space to complete) - which is essentially equivalent to granting access to physical memory without tripping the VMM into recursion. You may find a way to fix your implementation based on this concept.