Virtual Address Space Allocation

[davem]

What is a good technique for handling this? I read the wiki and I understand how the AVL tree and the linked list approaches work. However, I do not understand how to implement these nicely without implementing dynamic memory for them first. Is there a way to do this without dynamic memory or is there another technique to do this statically? Or potentially another approach?

[JohnnyTheDon]

You can allocate the entries in the trees/linked lists along with the data. For example, if you're using a linked list approach and you need to allocate 20 bytes, you can actually allocate 20 bytes plus however large your linked list structure is, and then prepend the data with the linked list structure. This also makes freeing easy, because all you need to do is subtract the size of your linked list structure from the pointer being freed to find the linked list structure. You could also prepend free areas with the linked list structure associated with them. This might work somehow with AVL trees, but I imagine it would be more complicated.

[davem]

Eh? I am not allocating memory, just address space.

The reason why I am avoiding dynamic memory is that I then have to figure in the cost of allocating and deallocating memory which harms runtime performance.

[JohnnyTheDon]

What are you allocating address space for?

[davem]

I am allocating address space for various things. Sometimes I just want to make it so that it cannot be allocated by anybody else and then use it later. Also, things like mmap can request arbitrary address space or anonymous address space. An address space allocator makes it so that I can allocate anonymous address space without linearly walking the page tables.

[JohnnyTheDon]

Oh okay. You will either need to statically allocate a table or bitmap describing all virtual memory (possibly in blocks of more than one page) in blocks or use some sort of dynamic memory. Since all the entries in the linked list/AVL tree will be the same size, I recommend cache-based allocation. It is dynamic memory, but it is much more efficient than malloc()-type allocation because it only opperates on items of the same size. You should be able to find some info about it on the web.