Virtual Memory Manager: AVL tree with duplicate entries?

[sebihepp]

Dear Forum,

I want to implement a virtual memory manager next and decided to use an avl tree to save free chunks of memory by address and size - just as the example in the wiki says. But AFAIK a bsp tree must not have duplicate entries, which I cannot guarantee for a tree by size. How to proceed here? Would it be possible to overcome this issue by using size and address together as value, so that same sizes will be ordered by address?

Its a long time since I last worked with bsp trees and I want to make sure its theoretically possible before I implement it (and find out I am completely wrong).

Best regards
Sebi

[nullplan]

You are completely correct, a binary tree must have unique keys for all nodes. The solution here is to view the tuple (size, address) as key. That is, when comparing keys, if the size is equal, compare the address instead.

[sebihepp]

Thanks @nullplan.

Then there is another problem: Without (k)malloc I can't allocate memory for the avl tree structures. So here are my thoughts, based on my virtual memory manager (which can allocate x pages of virtual memory and free x pages again):

I would implement a very simple memory manager, which just allocates 1 phyiscal page with a structure like

Code: Select all

struct SimpleMemoryChunk_t {
    SimpleMemoryChunk_t *Prev;
    SimpleMemoryChunk_t *Next;
    uint32_t Bitmap[x]; //Each bit represents one Entry in Data: 1 - used, 0 - free
    AVLTree_t Data[];
};

In case I want to allocate a new AVL tree node, I search the first SimpleMemoryChunk_t for a free space in .Bitmap. If its full, I allocate a physical page again and add it to the list. I could either never release the SimpleMemoryChunk_t pages or free them in case the Bitmap show fully free.

This generates some overhead if the actual SimpleMemoryChunk_t page is full. I could speed it up by only checking the last entry in the list and directly allocate a new page, freeing the previous ones only in the free() function.

Do I think to complicated? How do you implement a bsp tree without malloc or new?

Best regards
Sebi

[nullplan]

Ah yes, the old problem. Can't allocate memory to initialize the memory manager. A simple solution here might be to statically allocate a bunch of nodes to use for a start. Your virtual memory will not be overly complicated until you can get the allocator running, right? Just add a panic for if you run out of nodes before then. That's how I do it for my physical memory manager.

[nzmjx]

I don't know how you are planning to implement (k)malloc, but if you use dlmalloc for kernel heap management, its mspace API allows creating a heap instance with preallocated memory chunk.

In our kernel, we are reserving two pages for initial space and map to the kernel space. With those two mapped pages, we are creating kernel heap. As long as total allocated memory is less than two pages, dlmalloc serve allocation requests from preallocated space. In our situation, two pages are enough to allocate required data structures for initialising the physical frame allocator.