Coalescing memory managers?

[indigo256]

I've written a physical page allocator using the buddy system. It took me a stupidly long time, as I'm currently managing collage, a degree change, etc. As such, I'd like to use it to it's full capability.

This would imply using an allocator for my kernel heap that can coalesce free chunks less then a page, so that if a page is filled with completely free chunks it can be used later for larger allocations over a page.

What could I use for this? I was thinking I could use the buddy system again for managing chunks in a page, putting the bitmaps on the front of each page used for small allocations, but that would lead to some memory overhead.

I really liked the concept of the fixed size allocator described here, however coalescing would probably be a pain in the @$$ performance wise.

[indigo256]

While my post was getting approved I found I think would be best.
I'm going to have each chunk contain a header with a forward and backwards pointer to the last of that size, plus 8 more bytes to let free() know if it's allocated, the chunk size, and flags.
The last 8 bytes feels like a major waste, but I'm guessing it's best to be align to 8 bytes on my 64 bit system.
The chunk sizes are going be 2^n, from 32 bytes to 1 page. This size constraint is not only for quick access, but also helps split up larger chunks without wasted space at the end of page if need be.
Obviously, this solves my problem because I can simply check if the next chunk is free or not. There's 8 bytes of overhead per page when allocated, but I think that's fine.

I'm going to go forward with this, but if anyone sees this and thinks it's terrible, let me know.

[nexos]

Your method doesn't seem bad, but most allocations will be 4K for your VMM to use, and 64K for ISA DMA usage. Having granularity less then 4K is typically not in a PMM. I plan on ignoring ISA DMA, and using a free stack. That will be very fast, yet super simple.

[indigo256]

This would imply using an allocator for my kernel heap that can coalesce free chunks less then a page

Hopefully I'm not getting confused on what a VMM's purpose is, but I was meaning to say that this new allocator that splits up chunks is part of my (kernel space) VMM.

My idea of a VMM is this: you ask for memory using malloc, and it gives you about the size that you need, mapped into usable virtual address space.

On an unrelated note, is there any reason the kernel heap should be virtually continuous?
Right now, while things like my kernel code and stack are mapped somewhere else, I have all physical ram mapped linearly at 0xfffffff800000000. That way, I can do things like search the ACPI tables easily.

What could go wrong if my virtual allocator got the chunk it needed, and simply returned the address of the chunk in my mapping of physical ram?

[bzt]

You might want to take a look at the big picture.

For example I use the same allocator for both the kernel heap and userspace, the only difference is the callback. From userspace, it calls mmap (through libc with a syscall), and when used in the kernel, it calls a function to map into kernelspace (direct function call).

On an unrelated note, is there any reason the kernel heap should be virtually continuous?

No, kernel heap does not need to be contiguous. Mine is, but only because my kernel never frees memory. Being a microkernel, it does not store lists that could change (device lists, process list, open file lists etc.), so all it needs is allocated on boot, hence kernel memory never gets fragmented and remains contiguous. But it could be fragmented, there's no constraint that would require contiguous kernel heap.

What could go wrong if my virtual allocator got the chunk it needed, and simply returned the address of the chunk in my mapping of physical ram?

For example that chunk isn't page aligned or not multiple of page size.

Cheers,
bzt