Can kernel write to arbitrary physical memory?

[HyperAssembler]

Hello all,

I am writing an upper-half kernel. The kernel is loaded at 1MB and I map that to 0xFFFFFFFFC010000.
I plan to write a modified buddy allocator for my physical memory manager for its O(highest order) time complexity.

However, the "common" implementation requires in-place linked list where the list head is stored at the beginning of each physical page, since O(highest order) time complexity assumes that the block addr is also the addr for the list head, so that coalescing blocks does not traverse the linked list.

I've considered only mapping the kernel to some virtual address and 1-1 mapping others. However, let's say I have a stupid amount of memory so that physical address space = virtual address space. If the kernel is mapped to 0xC010000 and the kernel wants to write to physical address 0xC010000, then the kernel would be overwriting itself.

I could allocate list heads on my heap and use an AVL tree to keep track of free lists for each order. Then the time complexity for both alloc and free becomes O(highest order) + O(log(# of free blocks for that order)). Still much better than linear time but I wonder if I could do better.

Or furthermore, does it make sense for kernel to write to arbitrary physical memory, even if unallocated?

Thanks!

[neon]

Personally, if you ever have to write to arbitrary physical addresses, I would rethink the design. The buddy allocator isn't the best allocator to use for physical memory management - you can get O(1) allocation and freeing with a free stack. It also doesn't make sense to identity map most of the address space - not only is that dangerous it also defeats the purpose of paging. In any case, you would want to initialize the underlying structures before enabling paging. You can quickly build the list structures during this time - I don't see the problem here.

Your question though is not entirely clear. I.e. how do you have a heap yet don't have a frame allocator? Are you just hard coding its physical location and mapping it? Is that what you are wanting to do?

[HyperAssembler]

Personally, if you ever have to write to arbitrary physical addresses, I would rethink the design. The buddy allocator isn't the best allocator to use for physical memory management - you can get O(1) allocation and freeing with a free stack. It also doesn't make sense to identity map most of the address space - not only is that dangerous it also defeats the purpose of paging. In any case, you would want to initialize the underlying structures before enabling paging. You can quickly build the list structures during this time - I don't see the problem here.

Your question though is not entirely clear. I.e. how do you have a heap yet don't have a frame allocator? Are you just hard coding its physical location and mapping it? Is that what you are wanting to do?

Thanks for the reply!

My current "HEAP" is hard coded as "char heap[HEAP_SIZE];" I use a in-place heap allocator for that. Well, since managing physical memory requires some metadata, and allocating the metadata requires a heap/allocator. Therefore it becomes a chicken and egg problem unless metadata is stored in-place, which comes back to my original question.

Out of curiosity, does the kernel normally need to write to arbitrary physical address? Also can you elaborate on the "free stack" allocator?

[neon]

Hello,

The basic idea of the free stack is that you link together free frames in the system (so you still have "metadata" that is stored within the free frames themselves.) The kernel has a pointer, "top_of_stack" that points to the first free frame. To allocate -- read the frame at "top_of_stack" to get the next link, set "top_of_stack" to this link and return the original "top_of_stack" value. To free, write "top_of_stack" to the frame to free, get the address of that frame and store it in "top_of_stack." That is really are there is to it - no searching needed and both operations can be done in constant time. The frames are not contiguous. However this is not a problem with paging since you can map them to contiguous addresses.

In our system, the kernel starts up with paging disabled. This way it can write the links to the free physical frames in the system (starting at 16MB.) It then enables paging and relocates itself. This works well which is why I suggested it if you still plan to use the buddy system (or free stack.)

This resolves the chicken and egg problem since the pages are now linked together and can be used later by the allocation and freeing functions of the frame allocator.

With that in mind though, I have seen some members here use a method similar to what you described -- using a temporary heap to allocate data structures used by a frame allocator to eventually build a proper heap later on - so it certainly is an option.

Kernel's don't normally need to write to specific physical addresses -- except, perhaps, I/O space, but that isn't managed by your allocators so isn't a problem. There are a few other cases, but in 99% of the time there really is no need.

[HyperAssembler]

Hello,

The basic idea of the free stack is that you link together free frames in the system (so you still have "metadata" that is stored within the free frames themselves.) The kernel has a pointer, "top_of_stack" that points to the first free frame. To allocate -- read the frame at "top_of_stack" to get the next link, set "top_of_stack" to this link and return the original "top_of_stack" value. To free, write "top_of_stack" to the frame to free, get the address of that frame and store it in "top_of_stack." That is really are there is to it - no searching needed and both operations can be done in constant time. The frames are not contiguous. However this is not a problem with paging since you can map them to contiguous addresses.

In our system, the kernel starts up with paging disabled. This way it can write the links to the free physical frames in the system (starting at 16MB.) It then enables paging and relocates itself. This works well which is why I suggested it if you still plan to use the buddy system (or free stack.)

This resolves the chicken and egg problem since the pages are now linked together and can be used later by the allocation and freeing functions of the frame allocator.

With that in mind though, I have seen some members here use a method similar to what you described -- using a temporary heap to allocate data structures used by a frame allocator to eventually build a proper heap later on - so it certainly is an option.

My idea is to have a generic allocator that allocates both contiguous and non-contiguous physical pages with certain limits such as the highest acceptable physical address (for DMA). Essentially something like MmAllocateContiguousMemory, which takes a "highest acceptable address" parameter. For this reason, I think I'm sticking to the buddy allocator.

I really like the idea of storing metadata in free frames themselves, however, once you enable paging, you cannot access those "top of stack" pointers the same way as paging disabled. The kernel needs to somehow read from a physical address and write to a physical address. Can you give me some insights on this?


EDIT:
I just realized how it works. For allocation: you map the first physical page to a virtual address first, and then read and modify the pointers (works since it's already mapped).
For deallocation: you write the page header to the virtual page first, then you translate the virtual page to physical page and call it good.
That was pretty stupid of me lol.

[neon]

If you want to be able to allocate contiguous frames anywhere, then the buddy allocator is a good idea. Referencing MmAllocateContiguousMemory probably isn't the best comparison since Windows doesn't use a buddy allocator; rather it uses many different allocators -- a bitmap, lists of free lists, PTE free list, and we have not gotten to the heap yet. As your system grows you'll probably end up using multiple allocators as well.

When paging is enabled, the free function can easily access the block of memory since we are given it. We get its physical address from the paging tables, write "top_of_stack" to the block and write its physical address to "top_of_stack." Allocating is a little harder - we have two functions for that (which can actually be made into one) which is abstracted away by a general alloc_page function. The first function just returns "top_of_stack" and the second function is given a mapped page for the address that we returned. So we just read the link from the given block into "top_of_stack" to complete the allocation request.

Keep in mind, even with the buddy system, you only ever need to access it when allocating (in which case you already have the physical address - you just need to map it) and freeing (in which case you already have all the info you need.) And in a buddy system, you don't need to link every page. You just need to link the largest zones (by order) and don't worry about splitting them yet - that should be done in alloc.

[HyperAssembler]

If you want to be able to allocate contiguous frames anywhere, then the buddy allocator is a good idea. Referencing MmAllocateContiguousMemory probably isn't the best comparison since Windows doesn't use a buddy allocator; rather it uses many different allocators -- a bitmap, lists of free lists, PTE free list, and we have not gotten to the heap yet. As your system grows you'll probably end up using multiple allocators as well.

When paging is enabled, the free function can easily access the block of memory since we are given it. We get its physical address from the paging tables, write "top_of_stack" to the block and write its physical address to "top_of_stack." Allocating is a little harder - we have two functions for that (which can actually be made into one) which is abstracted away by a general alloc_page function. The first function just returns "top_of_stack" and the second function is given a mapped page for the address that we returned. So we just read the link from the given block into "top_of_stack" to complete the allocation request.

Keep in mind, even with the buddy system, you only ever need to access it when allocating (in which case you already have the physical address - you just need to map it) and freeing (in which case you already have all the info you need.) And in a buddy system, you don't need to link every page. You just need to link the largest zones (by order) and don't worry about splitting them yet - that should be done in alloc.

Are contiguous physical memory blocks only needed within some fixed memory regions? I wonder if I could use a free stack allocator for some regions and something else for others, since the free-stack allocator isn't specifically good at allocating memory with constrains.

[neon]

If you look at physical memory as zones or regions, you can certainly use different allocators for different regions. For example, we have two regions - one for the first 16MB and another for the rest of memory. The first zone uses a buddy system and is only used by certain drivers for legacy hardware (i.e. ISA DMA.) The second zone uses the free stack.

Contiguous physical memory blocks are only needed by legacy hardware.

[HyperAssembler]

Thanks for clearing things up! Now I have a much better idea of the memory layout.

Two more unimportant questions, feel free to not answer .
1). Is 16MB a fixed range for all those legacy hardwares? (Are there exceptions?)
2). Does your buddy system for the first 16MB use free page memory or kernel stack?

[neon]

If interested, I believe what Windows does is that it stores a list of PHYSICAL_MEMORY_DESCRIPTOR objects it obtains from the boot loader. It also uses a PFN bitmap that it uses with the list that it allocates frames from. If it finds a free descriptor with enough free frames in the bitmap, it allocates them as contiguous physical memory. It does this if there is not enough free frames in the non-paged pool.

You can certainly add this type of extra layer under an existing frame allocator. E.g. in the case of a stack allocator, you would have to provide functionality to remove and add new elements to the free stack which will increase its complexity a little.

1. Most legacy hardware is limited by that 16MB barrier.
2. We store them as a list of free frames (multiple lists by its order), where the links are stored within the free pages themselves.

[HyperAssembler]

I see. Physical memory layout should be part of the info passed to the kernel by the HAL.
For me, the kernel runs in identity-mapped/paging disabled environment; sets up PMM/interrupt stuff and then relocates itself to the higher half (thanks for your advice).

Thanks so much for helping!

[Boris]

Hi,

I use a buddy allocator in my OS.
It manages a number of 2^16 pages, which in my case, means 128Mb.
At boot time, I allocate a numbers of allocators depending on how much physical RAM I have. On a 4Gb machine, I will create 32 of them which will take about 3 Mo
When I will implement NUMA, I will make a per CPU sort list of them so I won't have to iterate through them in order to quickly find a free page.

[gerryg400]

... I will create 32 of them which will take about 3 Mo

3 months ? That'll boot slower than windows