expanding the heap

[yemista]

Hey, I was wondering on whats the best way to expand the heap, and I have some ideas, but I was wondering how others do it and if these seem decent enough. The problem with expanding the heap is, the heap is where you get your memory from. So when you realize the heap is full, you need to allocate a page table to expand it, but you cant do that with the heap being full.

One solution I thought of is to save the last 4kb on the heap, and make the heap think it ends right before then, so that when it comes time to expand it, there is 4 kb already mapped and we just have to assign frames to the pages, and then our heap is expanded by 4 mb. Problem with this is whenever its done, heap is expanded by 4 mb, and God forbid something goes afoul and overwrites that page table, which is located in practically the middle of the heap, all sorts of other nasty things might go wrong.

The next solution is to have something like 4 page tables already allocated and held in reserve, not in the heap, so that when heap needs to be expanded, you allocate frames, and set the address in the page directory. Doing this again means you expand the heap 4mb at a time, but also means that the heap can only ever grow to a maximum of 20mb(16 additional plus 4 original). But thats not so bad because how big will kernel data really get?

The third solution is to have the kernel directory contain page tables for all of memory, but not to fill those tables, or at least to have tables covering all heap space(0xD0000000-0xDFFFFFFF in my case), and when you need to expand the heap, you can do it a minimum 4kb at a time, and it would just be a matter of allocating a frame to a page in the table entry. I actually think this is the best solution, but it does mean that you will probably have wasted page tables that will cover the address range, however, you wont really be wasting actually RAM by allocating it unnecessarily.

[frank]

I think the easiest way to avoid the problems with expanding the heap is to not allocate page tables and page directories from the heap. Always use the physical page allocator to get new pages for the page tables. That way you don't end up with circular dependencies.

In my kernel I use the classic sbrk approach. I use Doug Lea's dlmalloc for the heap. When it needs more space it calls sbrk with the amount of pages it requires. Then the function allocates the required pages from the physical memory allocator and then asks the virtual memory manager to map those pages to the end of the current heap. sbrk then returns with a pointer to the newly allocated memory and dlmalloc manages it.

[MikeP]

My X86 page table management just keeps a spare allocated page at all times. When I find that the kernel needs a new page table, I can just use the spare page, satisfy the original allocation, and then allocate a new spare page to use next time round.