Kernel Heaps and Page Managment

[proxy]

So my operating system has been moving along well.

In my current implementation I have reserved a 64 MB region for my kernel heap which is not physically contiguous. The page tables are pre-allocated but the actual pages are allocated on an on demand basis.

In addition to this, I have the first 768 MB of RAM mapped contiguously starting at 0xc0000000 - 0xf0000000. This is for speed of access and simplicity of code. Basically the idea (as I'm sure most people here know) is that to get a usable virtual address of any physical address <= 768 MB, i can just add 0xc0000000.

This results in the following memory map:

Code: Select all

0x0000000000000000 - 0x0000000000001000     : (unaccesible/null pointer detection)
0x0000000000001000 - 0x00000000c0000000     : (user space, to be divided up more)
        0x00000000bfffd000 - 0x00000000c0000000 : primary thread stack of current process
0x00000000c0000000 - 0x00000000f0000000     : Identity map of lower 768 megs of mem including kernel
        0x00000000c0000000 - 0x00000000c0000400 : Real Mode IVT (Interrupt Vector Table)
        0x00000000c00b8000 - 0x00000000c00c0000 : Video RAM
        0x00000000c00c0000 - 0x00000000c00cd000 : Video Bios
        0x00000000c0100000 - ?                                  : Kernel (code/data/bss)
0x00000000f0000000 - 0x00000000f4000000     : Kernel Heap (64 megs)
0x00000000f5000000 - 0x00000000fd000000     : Video Linear Frame Buffer
0x00000000fe000000 - 0x00000000fe010000     : Temp page mapping
0x00000000ffc00000 - 0x00000000fffff000     : Page Tables as mapped by active page directory
0x00000000fffff000 - 0x0000000100000000     : Page Directory

To manage pages, I use a simple linked list that is used like a stack. The first 4MB are reserved and not in the free list ever.

Now, on to my question

I would like my Heap to not be hard coded to a 64 MB region. What I would like is to have the heap also co-exist in this 768 MB of "low memory" where i adjust the kernel "brk" value as the heap needs to grow. This would have some benefits.

#1 Heap is physically contiguous, makes it more often suitable for 32-bit DMA
#2 Heap has limit which is relative to ability to allocate more pages, not some arbitrary number.
#3 I could use the 64MB for other purposes .

I believe that this is what linux does, because kmalloc by definition returns physically contiguous memory (as apposed to vmalloc which doesn't have to be, but can handle much larger blocks).

So my question is, how do I do this well and efficiently. I can think of 2 methods off hand, but neither seem good to me.

#1 Heap is primary allocator, pages are allocated from Heap by asking for a page sized block aligned by page size. This has the downsides of being slower to allocate pages AND wastes a few bytes per page allocated for the heap meta-data.

#2 have the page "stack" be sorted. Favor allocating for general use from high end of list, and only extend the heap by increasing "brk" value and taking the pages between old brk and new brk from page list, if this can't be done, heap cannot be extended at this time. This has the down side of being more complicated and in addition heap allocation can fail even when there are pages available since general page allocation and the heap are basically fighting for pages.

What do you guys think? I've tried sorting out what linux does and to be honest, it is VERY confusing.

Thanks,
proxy

[JamesM]

Hi,

I'm afraid I don't have time right now to reply to your post in full, but I will say this:

What do you guys think? I've tried sorting out what linux does and to be honest, it is VERY confusing.

Linux uses a similar system on the MIPS architecture. It has its kernel heap in KSEG0 which is a hardware-enforced windowed region looking onto the first 512MB of physical memory (just like your own system).

It might be worth looking in the arch/mips directory for the heap stuff.

[jnc100]

Linux uses what is called a 'zoned buddy allocator' as its primary physical memory management system. Put simply, this divides the physical memory into three regions: under 16MB (for ISA DMA), up to 4GB (for 32-bit PCI DMA) and high memory (above 4GB) and allocation from each is via a buddy system (for a description, see here). This means it can simply and quickly allocate large contiguous regions of physical memory for DMA on demand.

I think you need to distinguish this allocation of contiguous physical memory from the idea of a heap, which is a region of virtual memory from which malloc requests are made. It is this region which is resized on demand by brk.

The general idea of using regions for virtual memory management is you define a region for each part of the userspace process and kernel in that particular address space, e.g. .text, .data, .bss, one stack per thread and a heap. As long as you ensure the heap has sufficient unallocated space after it, you can change its size on demand with brk. Then, all your page fault handler needs to do is check if the faulting address is within a defined region, and if it is then allocate a physical page and map it to the faulting address. If not then a process has tried to access memory outside a defined region (which is obviously an error) and you should handle it accordingly.

Regards,
John.

[proxy]

John,

Thank you for the reply, but unfortunately I think you missed my question :-/.

I am definitely not talking about the user space heap. In fact, my question doesn't really involve user space at all! My question relates to the kernel space heap and only that.

So, if we are to draw a comparison to linux, then it would kmalloc/kfree which are contiguous by definition and is taken from the "low memory" zone (which functions exactly like my 0-768 MB zone in my question. To clear things up, I do have zones (like linux i have DMA/low/high), I just didn't mention them because they didn't pertain to my question .

For Me: DMA = 4MB-16MB, LOW = 16MB - 768 MB, HIGH = 768+

Once again, thanks for the responce, but I think JamesM was on the mark when he suggested I look at the mips linux source as I think linux does what I want to accomplish.

proxy