Do I need a page frame allocator?

[MarkD]

Hi,
I’m building a 32 bit x86 OS. Currently, I’m following the Linux model of mapping all of physical memory into the kernel VM space. I’ve given my kernel heap all virtual memory from kernel end to the highest point in virtual mem backed by physical mem. I plan to use the kernel heap for all allocations, including file buffers, page tables, etc. I could optimize it for specific request sizes like 4KB and could create pools of memory types if I need to. So far everything is working, but it’s early days.

Is there a reason to have a separate page frame allocator in the setup I have? Am I missing something? The heap already has all the memory and it is already mapped into VM. Anything that needs memory can get it from the heap.

Is there a reason not to have the kernel heap, assuming it has optimizations for zones and specific block sizes, handle all requests for memory?

In the future, I plan to avoid mapping all physical mem into the kernel VM space and I expect to use a page frame allocator then.

Thanks.

[rdos]

You should not map all physical memory, particularly not if you are building a 32-bit OS. Basically every modern PC has 4GB or more of physical memory, and with this design you will not be able to use all of it. It's also a security risk (what you cannot access, you cannot corrupt).

You might do this as the first approach, but then make sure you encapsulate it in a private interface so you can modify the design later.

I have both a byte-aligned allocator (heap) and a page-aligned allocator. Small requests often use the byte-aligned allocator while large use the page-aligned. The page aligned allocator has a much larger linear address area than the byte-aligned.

[songziming]

If your OS run userspace programs, then page allocator is required. Since user programs usually have their own heap allocator, and OS can reclaim all pages when process exits.

But if your OS only runs in kernel mode, all threads share common address space, then page allocator is optional. A lot of embedded OS works fine without paging, some even doesn't support malloc.

I use page allocator to allocate stacks, heaps, page tables, and others. And I map them to discontinuous vm ranges, leaving a guard page between each area, so overflows can be caught.

[MarkD]

Thanks @rdos. I definitely plan to not map all physical memory into kernel space, but it seemed a simple half step for this week. Plus, it got me thinking about what I truly needed and what are choices.

Why do you have two allocators rather than one allocator with a "sub" allocators. I'm using C++ and have a strong Java background so I naturally think in terms of interfaces. My Heap class can use the request size (and I might add a zone argument) to determine which "sub" allocator to use. Then there is just a single interface for all the kernel needs,

Thanks @songziming. I don't understand your first point. I haven't yet implemented user mode, but I'm thinking that when I want to load a user program the kernel will request all the pages it needs from the kernel heap and then set up an extra mapping to map user address space to the allocated pages. (Since I use a simple translation map for physical memory to kernel space, the physical address = the (kernel space) virtual address - 0xC0000000.) The process structure would hold pointers to the allocated areas and they would be freed when the process terminates. Am I missing something?

Thanks.

[thewrongchristian]

Why do you have two allocators rather than one allocator with a "sub" allocators. I'm using C++ and have a strong Java background so I naturally think in terms of interfaces. My Heap class can use the request size (and I might add a zone argument) to determine which "sub" allocator to use. Then there is just a single interface for all the kernel needs,

A man after my own heart! I too was very influenced by the use of interfaces, and my kernel I think has quite a Java feel. I use monitors, for example, for synchronization, and even use a garbage collected heap.

Thanks @songziming. I don't understand your first point. I haven't yet implemented user mode, but I'm thinking that when I want to load a user program the kernel will request all the pages it needs from the kernel heap and then set up an extra mapping to map user address space to the allocated pages. (Since I use a simple translation map for physical memory to kernel space, the physical address = the (kernel space) virtual address - 0xC0000000.) The process structure would hold pointers to the allocated areas and they would be freed when the process terminates. Am I missing something?

It's all about layering. In my OS, all memory is mapped, all referenced memory is managed in an address space using segments (not x86 segments) using a base/size:

• Static kernel text and bootstrap data are direct mapped at bootstrap time. These are represented in the address space using a segment
• Heap allocations use a heap segment that allocate and map to physical pages on demand. As the heap is extended, it will reference new unmapped memory, and the page fault handler will allocate a new physical page to back the heap memory and map it.
• All other kernel memory use the same generic demand page segments used by user segments, which like the heap segment, will demand load a page in the page fault handler.

So, my kernel heap operates like a normal user space heap. Allocations use a slab allocator, using page sized slabs split into individual objects of the same size. The only restriction is that my heap can't handle objects of arbitrarily large size, the biggest object size I can allocate on the heap is the size of a page minus the slab overhead (I can't remember the exact size I handle.)

For segment mappings used by heap and general purpose kernel and user segments, memory is allocated at the page frame level on demand. Pages are allocated in response to the need for mapped memory. So all page frame allocation is in response to page faults.

The benefit of splitting allocations of heap items from page frames is that the meta data used to manage them can be more suited to the task.

For example, the general purpose heap allocator have little in the way of alignment requirements, being primarily software defined and managed structures. The management meta data can be adjacent to the memory being managed,

By contrast, anything that represents data used or defined by hardware tends to have alignment issues. Obviously, mapped pages need to be page aligned, and be entire pages. So page management data cannot be adjacent to the page itself, it has to be out of band. Page data may also benefit from buddy allocation, to more easily allow allocation of contiguous physical pages. For example it might be beneficial to allocate a large contiguous multi-page buffer to assign to a high speed network device to write received packet data (though scatter/gather DMA or IOMMU probably negates the requirement for contiguous physical pages.)

[rdos]

If your OS run userspace programs, then page allocator is required. Since user programs usually have their own heap allocator, and OS can reclaim all pages when process exits.

The OS is only needs to be involved in userspace allocators by providing an interface to set access rights on pages. It doesn't need to support allocation as userspace owns it's address space. Generally, userspace will inform the OS that a page is allocated, and then the pagefault handler will assign a physical page to it on access.

[rdos]

Why do you have two allocators rather than one allocator with a "sub" allocators. I'm using C++ and have a strong Java background so I naturally think in terms of interfaces. My Heap class can use the request size (and I might add a zone argument) to determine which "sub" allocator to use. Then there is just a single interface for all the kernel needs,

My kernel is mostly written in assembly. The heap allocator (byte aligned allocator) generally is used to allocate space for various driver objects, and is always mapped to a selector. This provides protection to the heap structures that could corrupt the heap if a driver overwrites the allocated space.

[MarkD]

Thanks all.

I love how diverse everyone’s OS is.

I don’t store heap meta data “in-band” and I’ve already added alignment code to my heap. So for fun, I’ve decided to try using a single Heap class for all kernel allocations and see how far I get. I will adjust to not mapping all of physical memory into kernel space. I could just incrementally extend the simple translation map on demand, but I’ve decided to use a page frame allocator to provide the heap with more space to learn about managing space with a non-trivial virtual to physical address mapping. I will pass the allocator in at construction time so I can reuse the heap code for user code with a different allocator that does a system call to get more space. Wish me luck!

Cheers.