Bitmap or stack based memory manager

[DarylD]

What is everyone's thoughts on use a bitmap for the free space map or using a stack or list.

I am currently using a stack (well, table basically) with a list of physical memory pages available for allocation.

*But* I know a lot of people are using bitmaps, with one bit per 4K page. Obviously this uses less memory but surely scanning for a 0 bit will take a lot longer.

Or am I getting confused?

[pskyboy]

Yeah im at that stage too. Im trying to create the most efficent way of lookign after the physical memory.

In my view the speed at which the memory is allocated is most important as this routine will be callled alot and could slow down the whole OS if it isn't very fast.

Another question is when malloc is called or a kernel version is it not better to allocate a linear range of memory to the size requested rather then random pages dotted all over memory. This would then allow for better locality of memory and surely faster operation as memory can be read better in burst modes.

For this reason wouldn't a linked list be best as it could automatically arrange memory in to continous chunks.

Peter

[pskyboy]

Okay This is the way i see it at the moment,

Your physical memory manager should provide a set of functions to the kernel allowing it to allocate pages of memory. The functions i think i need are as follows if i have missed any or you have any ideas for ones you think might be good here let me know.

void* AllocPage() - Allocates one page of memory and returns a void pointer to it

void DeAllocPage() - Deallocates a page of memory

void* AllocRun(UINT uiSize) - Allocates a continous run of pages to the size of uiSize

Peter

[elias]

so with a stack, what you do is pop the next available address, for a block? i dont see how a bitmap would be faster, but it might be better in case your stack gets overflowed. i still havnt decided on my memory manager yet

[DarylD]

The bitmap will take less memory though as it will be one bit per address rather than 32 for a stack (although in theory less bits can be used, maybe 20, but that will make things more difficult)

But a bitmap will be slower to scan I think.

[Whatever5k]

I think I will use a linked list that contains the holes of memory.
Something like this:

Code: Select all

struct hole
{
char *prev;
char *next;
u_int length;
};

[pskyboy]

yeah im with you abless, i think i will used a linked list as the most important thing here is speed as a slow up here will slow everything on your OS down. So i think if i can make this as fast as possible that would be the best idea.

I will probably implement a thread to also do houskeeping like defragment the memory and stuff.

Peter

[K.J.]

I use the stack-based approch as it's super fast. I can allocate and dellocate 256MBs of RAM with it in less than a second on a 333mhz PC... I tried doing the same with a bitmap, but couldn't even come close to the speed.

K.J.

[DarylD]

Yeah, I think I will stick with the stack, it seems to be the best choice.

Oh and abless/pskyboy, I wouldn't recommend using a stack for the memory management, for instance, how will you allocate memory for the linked list if your memory manager uses linked lists, bit of a chicken and egg situation...at least with a stack, its possible to calculate its (fixed) size early on. Its simple, fast and easy.

[pskyboy]

No, you just pick an address and start sticking the first link in there. you then do ++ on that pointer for the next link. I tell you its the weirdest type of programming you have ever done when you just pick a location and shove the structure there. Im not sure how long it takes to do allocation, how did you time it did u use a clock?


Peter

[DarylD]

I don't need to time it as it will take two instructions to get the next free page from the stack

First instruction is a mov to return register, the current uint32 at the top of the stack.

Another instruction to decrement the stack pointer.

Nice and fast.

Obviously in real life there will be a few instructions either side handling error checks, returning and the like but its about as fast as it will get.

Maybe if allocating large chunks of memory at once a linked list will be faster but most of the time a page allocator will be working with single pages when pages fault.

[pskyboy]

I think mine is only a couple intstructions two.

All its got to do is get the pointer out of memory. Reassign another pointer and return the pointer.

Peter

[pskyboy]

Hey guys

I ditched my linked list memory manager and wrote a nice stack based one as the linked list was taking up to much memory and wasn't that much faster.

Anyway how do you guys allocate your memory on the stack do you count down ie adding the last physical address to your stack first or count up and therfore do the opposite.

Also how do you defrag your stack or do you not bother.

Peter

[Tim]

A linked list of holes (better: a tree of holes) is better for a virtual address allocator.

With physical memory, you don't care (much) where the page is located; you just have a load of addresses. So it makes sense to make allocation of one page quick and efficient. You could use a bitmap or stack for this. A bitmap makes allocation slower (you have to search the bitmap) but takes less space (one bit per page, or 1/32768th of total memory for 4KB pages). A stack is much quicker to allocate (you just subtract from a pointer) but takes up slightly more space (1/1024th of total memory for 32-bit pointers).

With 256MB of RAM, a bitmap will occupy 8KB and a stack will occupy a maximum of 256KB. However, the stack will be much faster.

When it comes to allocating chunks of address space for applications, you're worried about where the memory is located (an application might want to allocate at a fixed address), how much is allocated, and the fact that it's contiguous. So here you need to keep track of potentially huge regions (you could allocate several gigabytes efficiently) while avoiding collisions. You still need to keep track of every byte in each 4GB address space, but for each one, you need to record whether it's allocated, what protection is applied, etc. Clearly you can't have a structure for every byte, or even page, so you need to keep track of ranges of pages.

Something like this would work:

Code: Select all

struct vm_range
{
    addr_t start;
    size_t num_pages;
    uint32_t flags;
    vm_page *left, *right;
};

The left and right pointers create the tree data structure. That's a topic for the Programming board, or a programming book, so I won't describe it here.

[pskyboy]

I understand what your saying and this is what i am doing. My main concern is i have a stack based physical memory allocator which works brilliantly. The problem is when i deallocate memory. At the moment i just push the pages back on to the stack and i was wondering how you go about defrag this memory so you have a nice run of continuous memory on the stack? Or do you just not bother in which case what happens when you need a run of memory.

The reason i am concerned with runs of memory is my kernel uses the physical allocator directly.

Peter