Hi,
shadow wrote:
Maybe I'm just misinterpreting your post, but I don't see how I could put the stack below the kernel because it could be too large to fit there.
I think Rob meant the CPU's stack (SS:ESP) rather than a free page stack.
shadow wrote:
If you have 4GB of physical memory, that's 1,048,576 pages. Each page address takes 4 bytes, so that's 4,194,304 bytes or 4MB. So I would need 4MB to hold the stack at it's maximum possible size for 4GB. The problem is that most computers don't have nearly 4GB, so I would be wasting lots of memory if I just reserved 4MB no matter what instead of making it dynamic. Maybe I missed something, though...
That isn't how free page stacks are normally implemented.
Normally you'd have a pointer to the top of the stack somewhere, which points to the address of the first free page. The address of the second free page is stored in the first free page, the address of the third free page is stored in the second free page, etc. This consumes 4 bytes regardless of how much memory is present. For e.g.:
Code:
void *alloc_page(void) {
void *freePage;
freePage = currentPageStackTop;
currentPageStackTop = currentPageStackTop->nextFreePage;
return freePage;
}
There are some variations on this though, like using a stack of "free page index tables". In this case each index page contains the address of the next index page, a count and the addresses for up to 1022 free pages. When you allocate a page you get the last entry in the index page and reduce the count. If the count reaches zero then you'd take the index page itself and find the address of the next index page from it. For e.g.:
Code:
struct INDEX_PAGE {
void *next_index;
unsigned int count;
void *free_pages[1022];
}
void *alloc_page(void) {
void *freePage;
int entry;
entry = currentIndex->count;
currentIndex->count--;
if( entry == 0) {
freePage = currentIndex;
currentIndex = currentIndex->next;
} else {
freePage = currentIndex->free_pages[entry];
}
return freePage;
}
The first method (plain free page stack) looks simple but it isn't because "currentPageStackTop" is a physical address and "currentPageStackTop->nextFreePage;" doesn't work. You have to map "currentPageStackTop" into linear memory before you can get the next free page. This usually means combining it with the linear memory manager - when you're allocating a linear page you'd store "currentPageStackTop" into the page table, then use INVLPG to flush the TLB entry, then get the address of the next free page from whereever you mapped "currentPageStackTop".
The second method (stack of index pages) has the same problem - you have to map the current index page into linear memory before you can access it. Because of the way it works you can get 1022 free pages easily, but when an index page becomes a free page you need map the next index page into linear memory.
Cheers,
Brendan