i thought i'd mention my technique for page allocation to see what people think
It is generally a linked list of stacks. See in my opinion, the one and only downside to a stack is that the store has to be in linear memory (at least until you turn on paging i guess).
Anyway, the algorythm is simple really. I have a structure which is somthing like this:
Code:
class PageEntryHeader {
public:
PageEntry *next;
uint32 stack_top;
};
#define STACK_PAGE_ENTRIES ((PAGE_SIZE / sizeof(void *)) - (sizeof(PageEntryHeader) / sizeof(void *)))
// this should always total to exactly one page in size
class PageEntry : public PageEntryHeader {
public:
void *entries[STACK_PAGE_ENTRIES];
};
this is C++ but you get the point. it is a small header followed by the "stack" of entries.
when initializing memory i do the following. I make sure that i have not previously setup the region current being setup, and that it doesn't overlap with some things (such as the kernel). if it does, i simply adjust the numbers to make it not.
then i loop through the pages.
when i find one, i do one of 3 things.
if my pointer to a stack is null, this page is a stack page, i set it up
if my pointer to a stack contains a full stack page, this is a stack page, i link it in, and set it up
else i simply push this entry onto the stack.
during setup, i keep a pointer to the last page (since all previous ones are full) so this should be no slower than a standard stack on setup.
allocation is almost as simple as a stack:
Code:
PageEntry *page_ptr = m_PageStore;
void *ptr = 0;
while(page_ptr != 0) {
// this page has a free one!
if(page_ptr->stack_top != 0) {
--page_ptr->stack_top;
ptr = page_ptr->entries[page_ptr->stack_top];
break;
}
// move on to the next page store
page_ptr = page_ptr->next;
}
return ptr;
and as you can imagine freeing is very similar..
I came up with this last night and it seems to work very well, so far. what do you guys think?
proxy