OSDev.org

For the last week or so I am trying to write a PFA(Page Frame Allocator) and I through of one algorithm, but I think it is a bit messy and reading some other posts on the forum I think maybe I even have wrong understanding of what PFA should do.

So here is my understanding of PFA, please correct me if i am wrong - the pages that are used to manage the virtual memory should be mapped to physical memory and the task of the PFA is to give out pointer to 4096 bytes that are free so the page can be mapped to them. Also the PFA should take into account that the kernel area and areas that are marked as reserved in memory map should not be used, also I have thought that there should be a function that would let drivers to also reserve space in the physical RAM so PFA won't touch it.

NOTE: I use a byte map not a bitmap, so for each page there are 8 status bits and so 8 flags could be used for each page(flags like free/reserved...)
Now here is my algorithm:
-- Initialization
1. Receive the start address for the first frame(start of page frame allocation memory space - -0x0 on x86)
2. Receive the end address of the last frame(end of PFA allocation space)
* The end address should be rounded DOWN(if it is not 4096 aligned) to the nearest number that is 4096 aligned
3. Mark all of the frames in which unfree zones are located as reserved(using the memory map and driver requests)
4. Mark frames where kernel is located as reserved using variables in the linker script(start and end)
5. Find an address to store the bitmap
1. Calculate the amount of frames needed to store the bitmap; The bitmap should be the size of - `RAM / PAGE_FRAME_SIZE`
2. Search for the first place where the right amount of frames is free(they should be one after another)
3. Mark frames as used by PMM and record the address of the byte/bitmap
4. Zero out all of the frames where the bit/byte map is located
-- Functionality
1. palloc()
1. Search for the first status that equals to FRAME_TYPE_FREE in the bytemap
2. Find the address of the frame that correspond to the bit/bytemap entry
3. Mark found page frame as FRAME_TYPE_ALLOCATED
4. Return the start address of the page frame
2. pfree(address_tt frame_start_address)
1. Use the start address of the page frame supplied to function to find the entry in byte/bitmap(using formulas)
2. Change the entry status to FRAME_TYPE_FREE
3. And also there would be functions for allocating pages that are reserved, freeing pages that are reserved, function to allocate RAM for PMM use

To allocate multiple frames one after another at a time I thought of just putting a special bit flag in the byte-map entry for the page frame that would indicate that the frame is a part of several frames(so they are counted as one space) in a row so the pfree would free all of them

Is my understanding of PFA correct?
Is my algorithm very bad, because I certainly think there are much easier and cleaner ways to do it(especially when OS is only at the start of it's life like mine)?

I heard there is a linked list method of page frame allocation, but can't really understand the algorithm and also how would I make sure that reserved areas aren't touched when using this method?
What methods could I use for PFA(they should be fairly easy to implement as I have only started with OSdev)?

I don't know why the memory map only comes into things in the third step. The memory map contains all places where there may be physical RAM the firmware isn't currently using, and that RAM is not guaranteed to be contiguous. For maximum portability (even other architectures; I see nothing arch-specific here), assume as little as possible. Integrate the entire memory map into your view of memory.
Depends on how leaky you want your abstractions to be. My main (stage 2) kernel is only used with virtual memory, and therefore independent of its physical address. The stage 1 kernels (UEFI and GRUB adapters, respectively) load the stage 2 kernel however they want and add the physical addresses used for that into the "reserved" range. This way, I don't even depend on all of it being contiguous. Though it seems unnecessary in this age of multi GB RAM sizes, I am quite prepared to have my kernel hacked into page-sized blocks all over memory. Virtual memory means I don't have to care. Of course, the stage 1 kernels are unlikely to do that at this time.

The page tables are special. Those are added to the reserved ranges in stage 2, in order to make it easier on the stage 1 kernels. Stage 2 can discover all addresses those tables are using, after all.

But then, I am building a 64-bit kernel and can just map all physical memory to one place and map a logical view of the kernel to another. In a 32-bit kernel you likely don't have that luxury.

Seems about right. But what is "RAM" here? It ought to be the span of possible addresses, so last address plus one minus first address. Remember there can be large holes in the middle.
Those who search have to deal with not finding it. You might want to choose a more granular approach, like a linked list of bitmaps. That way you can have multiple places to store the information, rather than requiring one large block.
And then set all the bytes representing reserved memory areas. Wouldn't want to overwrite the kernel now, would we?
Virtual or physical? If physical, how to map it into address space?
Unless you mean something else, you are describing a PMM (physical memory manager) here. What you will need is a function map fixed addresses, reserved or not, into address space. Those are needed by drivers that want to talk to MMIO.
Bad idea. For one, there is precious little need to ever allocate more than one contiguous page of physical RAM. You can always use virtual memory to make it look contiguous in virtual space, and having bigger blocks just gives you fragmentation problems (if someone wants to allocate 4MB, and all you have left is 3MB here and 2MB there, you have to decline the request. But if they make the same request in pages, you can fulfill it).

Plus, what if multiple multi-page allocations happen to be adjacent at pfree() time? Then pfree() is going to free both allocations after being called on just the first one, right? You could conceivably try to limit this problem by using multiple bits to form a sort of allocation ID, so that only pages with the same ID become freed. But you would need to ensure that no two adjacent spots end up with the same ID if you did that. That is possible, as long as you don't allow resizing. Then you can solve the problem with only 3 IDs (when allocating a block, only at most two IDs can be already adjacent, namely in the block before and after the one you are allocating, so you only need a third to be unique).

But it does make the whole thing more complicated. Easier might be to put the burden of tracking the number of pages allocated on the caller. You get "phys_addr_t palloc(size_t);" and "void pfree(phys_addr_t, size_t);". Caller gives number of pages in both cases. Ought to be simple enough, especially when starting out.

Easier? Barely. Cleaner? Eh, what is dirty about this one? You may in future need to add constrained allocation (some devices cannot deal with addresses beyond a certain point. For instance, for additional CPU startup on x86, you will likely need a page in the low 1MB of address space for the trampoline.). Unlike with a stack algorithm, constrained allocation is at least possible with a bitmap allocator.

And yes, faster algorithms exist. Your algorithm will spend a lot of time skipping over already allocated memory. You can mitigate this by keeping track of the lowest free address, but under high allocator pressure, you will still be skipping over already allocated memory a lot. But it will probably work, and when starting out, that is the most important thing.

That's basically correct, but some memory mapped devices might want (or work better) with serveral continous 4k physical pages, but it is the exception, not a rule. In that case, it's often permanent allocation at startup, and so no need to optimize for this.

Thanks for your answer, but I haven't understood a few things:


What do you mean by assume as little as possible? And what do you mean by "I integrate the entire memory map", what else could be done except using entire map?


How can the kernel be used only with virtual memory, it certainly should be mapped somewhere and what is wrong with what I am doing here?


How could there be a hole in RAM, I only know about a whole in virtual memory? And also why should I care about the hole - isn't it marked as reserved by the memory map?


The page frame allocator gives out physical addresses that are just then used for mapping the page to, so it is a physical address that would be mapped to the to some virtual by VMM


Isn't it what I said - called gives amount of pages and they are allocated. Yes the algorithm is a bit messy, but how would I fix this problem(what is the better way of allocating multiple pages then I wrote)?

For instance, don't assume there is RAM at address zero. There likely is, in fact it is impossible to have PC compatibility without it, but you still never know what manufacturers come up with next.
Sounded like you were only using parts of the memory map (specifically, only the reserved ranges). I apologize if I misunderstood you there. The firmware memory map will contain address ranges for where the physical RAM is, and where access is restricted, and you should take in all of that information.

In 64-bit mode it is actually quite easy to only be using virtual memory. My kernel is linked with the "kernel" code model and has a base address of -2GB (0xffff'ffff'8000'0000). But there is a linear mapping of all of physical memory starting at the start of kernel space (0xffff'8000'0000'0000). This mapping can at most extend to 0xffff'bfff'ffff'ffff, because of limitations in the architecture. In 32-bit mode you don't have that luxury.

I always found the approach taken in so many tutorials to be hacky: You'd always get a portion of the kernel linked at 1MB, and then somewhere there would be a jump forward by 3GB. So the linker script would be mixing virtual and physical addresses and you would get that in the same executable at the end. This looked wrong to me, and it is also very error-prone, for you can reference a variable that was linked to the 1MB portion from the 3GB portion. Which you probably don't want. So I decided early on to have two completely separate executables: One linked at 1MB that prepares the page tables and jumps to the entry of the other, and one that is linked solely with virtual addresses. It is fortunate for me that this approach is also required if you want to load a 64-bit kernel with GRUB legacy. And then UEFI came along, and I am even more glad, since I now have the infrastructure in place to abstract the precise means of loading the kernel away from the kernel.

Now, if you are in 32-bit mode, it is likely that your linear address space mapping is covering all of kernel space. Or most of it, and your kernel must execute out of the linear mapping. In that case there is nothing wrong with using link-time addresses. But it does mean your kernel is limited to being loaded to one particular address in physical memory. And if that address is taken already, your kernel cannot boot. Then again, I see little choice in 32-bit mode. Pure virtual mappings would boil down to constantly temporarily remapping stuff, which is unlikely to scale in the age of SMP, since you also need to shoot down the TLBs.

The caller should also give the number of pages when freeing, that is my point. That ought to be easier than tracking allocation IDs in a byte map.

So I should find the end and start address if RAM using the memory map?


The memmap has free and reserved regions, so do you mean I also should take into account the free ranges, what should I do with them - with reserved, I mark them as reserved, but free are free and should be left free?


What I was doing in the post you answered the first time is saying that I should reserve the physical addresses where the kernel is located, how does this do me architecture dependent or physical address dependent - I could still map kernel to any virtual address


So first executable has an elf(or whatever executable format you are using ) parser, or how do you load the second one; I only know the hacky method you said about with linking at certain addresses and then loading to others...?


Can't really understand what you meant here - does the uefi load you at the address which your executable is linked at, and does it switch to 64-bit mode automatically?


So you mean that I should not use link time addresses to find the kernel, but how should I find the kernel then?


What is a pure virtual mapping?


I map my kernel at 0xffffffff80100000, and to calculate physical address start I just subtract 0xffff'ffff'8000'0000. This is probably dependant on kernel being at 1MB, but how do I fix it?


What if the caller gives a wrong number, then I could free stuff that I shouldn't?


Also I wanted to ask about the page frame allocation methods - I know there is bitmap(what i use), stack and linked list method. I don't really like the stack one but I think linked list method is quite good, but I don't really understand how it should work?

The memory map has gaps in it. If you mark everything free except the reserved ranges, then the gaps will also be marked free even though they're not memory.

How should I find the gaps if nothing tells about them and why do they even exist?

Think about a machine with 8GB memory. On a PC, for legacy compatibility reasons, some of the 32-bit physical address space has to be given over to PCI memory mapped IO, and the APIC registers are also mapped into the 32-bit physical address space. All in all, this puts a whole load of non-RAM physical address space in the middle of what otherwise could be contiguous RAM.

So the chipset remaps some of the RAM, mapping the lower 3.5GB of RAM to 0-3.5GB physical address space. Then you have the hole is used to map PCI and APIC devices, then at physical 4GB , the rest of the RAM is mapped beyond the reach of 32-bit addressing (you now need PAE to map this memory in 32-bit kernels.)

You will also have a RAM hole at 0x000A0000-0x000fffff, which is the even more legacy original PC hardware memory mapped IO region (the DOS 640k barrier).

The end result is the memory map will contain several non-contiguous regions. 0-640k, 1MB-3.5GB, 4GB-8.5GB, plus other reserved regions.

You don't. Your allocator should start with all addresses marked reserved, and then you use the free ranges in the memory map to mark some of the memory as free.


Some of them are for backwards compatibility, some of them are to make the memory controller cheaper. There might be other reasons too.

Yes.
Every address not explicitly listed in the memmap as free cannot be assumed to contain RAM. So the free regions tell you where your RAM even is. Then the reserved regions limit this down further.
Yes, there is a simple ELF parser inside the stage 1 kernel. Since the stage 2 kernel is a rather simple statically linked executable, there complexity is limited. Though I did run into one unexpected hiccup: Apparently, when you have no initialized data in the data section, p_filesz is set to 0, but so is p_offset on that segment. Result in my case was that kernel code ended up being mapped twice, and then it was overwritten. Well, you live and learn.
No. The physical address my kernel ends up in is completely unpredictable, in both the GRUB and UEFI cases. For GRUB, I use the "module" mechanism to have GRUB load the stage 2 kernel as well. In that case stage 1 gets a predefined address, but stage 2 is still unpredictable. In case of UEFI, even stage 1 has an unpredictable address. But UEFI loaders are position independent PE executables, anyway, so it doesn't much matter. And yes, UEFI will do the switch to 64-bit mode for me. Not that it helps a lot, since it identity maps all memory, so the work is near enough the same for both loaders.
Have the bootloader tell you. The bootloader must know where it loaded the kernel. In my case, the stage 1 kernels need to hand all the info they got from their environments to the stage 2 kernel anyway. Once stage 2 starts up, it will remove the identity mapping, and then all the info given will be lost. So I invented a parameter passing scheme that allows these kernels to pack up all the pertinent information and put it on the stage 2 stack. Part of that information is the memory map. So the stage 1 kernels just add the physical addresses where stage 2 is loaded to the reserved areas. Stage 2 doesn't even know where it was loaded, because it could be in any of the reserved blocks.
Some 32-bit kernels (e.g. Linux) choose to make the largest part of kernel space into a linear mapping of physical address space, and run the kernel out of that linear mapping. What I mean by a pure virtual mapping is the exact opposite of that: A system where you'd link the kernel to some high address and then just map the kernel according to the ELF header. In that case, virtual memory space and physical memory space have nothing (predictable) to do with each other, so I call that "pure". But you'd still need to access arbitrary physical memory even with that, so you'd constantly need to change mappings. If memory maps remain around for any length of time, then they might migrate to other cores, and that means when you finally do delete those mappings, you have to do a TLB shootdown, which is where you send an IPI to all processors and tell them to invalidate a certain TLB. That procedure is horrible, it wakes up all cores, it is error prone, it doesn't scale.
You map the kernel logically according to what it needs, rather than adding a linear mapping to -2GB.
The caller is always able to call the free() function with the wrong arguments. Nothing can really protect you from that, except maybe error checking (like marking some addresses as important in your allocator, and throwing a panic if someone tries to free them). However, that only shifts the problem around: You still end up with a non-functioning computer after a kernel panic. Since you already depend on the caller not messing up the arguments, adding another argument to track is probably reasonable.
A linked list can be used to implement a stack (push == adding to front of the list, pop == removing from front of the list). The topic was recently discussed on this board (wasn't it with you?): You keep a pointer to the first free page around. In every free page, you use the first machine word in there to hold a pointer to the next free page. Takes a while to initialize. Allocating a page means removing the first page from the list (updating the head pointer to point to the first node's successor). Freeing a page means adding it back to the front of the list.

The problem with this approach is that constrained allocation becomes harder. You don't even know from looking at the list if any memory fulfilling the requirements even can exist. You can iterate over the list to find a suitable page, but given today's humongous memory sizes, that would take a while. Even then, since nothing imposes any order on the list, you might end up having to traverse pretty much the entire list to find a suitable page. Whereas, with a bitmap allocator, you at least know the right region to look at.

You're certainly right, but to clarify the context of when I suggested this method, I meant that I believed it to be simpler and more efficient *for me*. It's going to be a very long time before I have to worry about constrained allocation, or separate NUMA memory pools, or per-CPU allocations.

Using a linked list (yes, it's effectively a stack) works for me for now. I like that I don't need additional space, because managing memory to manage memory is the kind of meta that gives me a headache. Somewhere down the road I may have to throw it all out in favor of something else, but as the entire thing is hidden behind generic allocate and free calls, the design is contained and easily modified. I think I just wasn't in the mood to write a bunch of bit manipulation and counting code to do it in a bitmap. I have a linked list, and a running count of free frames. It's perhaps not very efficient (though the extra second of boot time it takes to construct the free list is no big deal) but performance is hardly my biggest priority at this stage.

I made something work so I could move on to more interesting things. But keep an eye out for my post in General Ramblings if and when I realize I should have designed it differently.

A bitmap allocator wastes less linear memory, which is important for 32-bit kernels that want to use PAE paging to use all available memory. Actually, it's the only reasonable solution in that environment that only requires one bit in linear address space per 4k of physical memory. 1G of physical memory only requires 32k of linear memory. My 32-bit kernel can handle 256G at the moment, which is handy given that I have a PC with 100G.

A bitmap allocator also makes it easier to allocate continuous blocks and blocks that fit at the page directory level (2M or 4M).

Another definite advantage is that it is possible to make a bitmap allocator lock-free, something that makes locking far less complex if you allocate memory on-demand with the page fault handler or in IRQs.

Thanks for all of your answears, I edited my bitmap algorithm to be much better, but the thing I don't know how to do the best way is - where should I store my bitmap, because I don't have an allocator to allocator space for it so I need to give it pointer some location, but where?

A simple bump allocator should be sufficient for bootstrap. Just start the pointer at the end of your uninitialized data, then when you allocate something, just advance that pointer over whatever you're allocating, and return the old pointer.

My design is described in this thread.