bootmem

[paulbarker]

I prefer a system of freelists (one for blank pages and one for normal free pages, so user code only gets blank pages for security reasons). For 0-16MB, a buddy bitmap will be used to support power of 2 allocations from 4k to 64k (for DMA). This buddy allocator may have a fixed size list (maybe 16 entries) acting as a cache for the most recently free'd pages so the bitmap doesn't have to be searched if a page is found on the cache.

A static bitmap will be used for initialization because it is very inefficient to allocate a static list (requiring 4 or 8 bytes per page) and dynamically allocating the list is not possible until we know which pages are free (thats where the bootmem bitmap comes in). It is also faster to initialize a bitmap by marking regions as free or allocated (without caring about the initial value), than searching thru a list (ordered or not) and adding or removing pages as appropriate and making sure a page is not listed twice. The static bitmap will be free'd when finished with.

So, I will end up with a buddy allocator for 0-16MB, a set of lists for 16MB to 4GB and a set of lists for 4GB+. This is obviously just for x86 systems, for portability all this is hidden behind a region manager and the VM system, which can be best explained by looking at the code:

rgn.h
rgn_group.h

The VM system has not been written yet, but I do have a basic working type for bitmap managed memory which you can find by looking thru the SVN repository.

[Ryu]

The list requires 4 or 8 bytes per contigous block of free memory, pages or not. It would be inefficent when your allocating every other page in the address space, however that won't be typical. The usual allocation algorithms would be to find this size at some alignment starting from lowest to highest, or same thing but highest to lowest. Which really is just clipping the first entry, or last in the list on most occassions. The down sides are when they are freed, your contigous blocks multiply, and so does your entry count. Which is also the reason I've tried to come up with an algorithm that involves not having to keep this list as sequently used entries, rather they themselves would produce holes of available entries within the list, while maintaining them sorted lowest to highest.

You have a point that initializing a memory bitmap would be far easier, but my other point is if your going to implement a list then why not have it here too. So in terms what I'm saying it would be easier in the end if you have the same set of calls to rely on then come up with a new approach with new routines.

[paulbarker]

The problem with a dynamic list of contigous regions is that regions may be merged or split, which is a real pain (requiring allocation within the allocator). I have a working implementation of this and I'm not very happy with it. It has several nasty hacks to stop it becoming recursive.

It was the way my entire kernel became tied in knots to support the physical memory manager that caused me to restart from scratch.

I can implement a list of pages pretty easily, with a separate list for free 4MB ranges it becomes pretty efficient as well.

[mystran]

Say I want to support upto 64GB RAM (I think thats the maximum with PAE enabled). Using a bitmap, that would require reserving 2MB of space or 4MB for a buddy allocator. Thats just not acceptable.

Or reserve 128MB of address space for (64bit) free pages stack that shrinks itself (free's it's own pages into itself) when it gets smaller (because of allocations) so that you really don't waste any more than what the code and a pointer or two take.

Seriously though, think in terms of ratios. On a computer with 64GB of RAM, nobody really cares if (actuall when) a few hundred megabytes are used by the operating system memory management.

[JoeKayzA]

Say I want to support upto 64GB RAM (I think thats the maximum with PAE enabled). Using a bitmap, that would require reserving 2MB of space or 4MB for a buddy allocator. Thats just not acceptable.

Or reserve 128MB of address space for (64bit) free pages stack that shrinks itself (free's it's own pages into itself) when it gets smaller (because of allocations) so that you really don't waste any more than what the code and a pointer or two take.

Seriously though, think in terms of ratios. On a computer with 64GB of RAM, nobody really cares if (actuall when) a few hundred megabytes are used by the operating system memory management.

Furthermore, you could use slight paging tricks to keep the amount of virtual memory used for the free pages stack constant, while it's size varies depending on the amount of physical memory. _In theory_ you could keep it down to a single page of virtual memory even for 1 Terabyte of physical memory - not saying that this would be a good idea though....;P

cheers Joe

[Brendan]

Hi,

Furthermore, you could use slight paging tricks to keep the amount of virtual memory used for the free pages stack constant, while it's size varies depending on the amount of physical memory. _In theory_ you could keep it down to a single page of virtual memory even for 1 Terabyte of physical memory - not saying that this would be a good idea though....;P

In theory, you can use one 4 byte "physical address pointer" in linear memory to manage up to 4 GB of free memory, and a single 8 byte "physical address pointer" in linear memory to manage up to 16777216 TB of free memory.

In practice this is exactly what I do, except I have more than one free page stack and each free page stack has a re-entrancy lock and a count of pages on the stack. This adds up to 8 bytes of linear memory per free page stack (for pages with 32 bit physical addresses), and 16 bytes of linear memory per free page stack (for pages with 64 bit physical addresses).

I have lots of free page stacks though (up to 2048 of them), so it still costs up to 24 KB of linear memory (plus another 4 KB for the bitmap I use for memory below 16 MB).


Cheers,

Brendan

[paulbarker]

Or reserve 128MB of address space for (64bit) free pages stack that shrinks itself (free's it's own pages into itself) when it gets smaller (because of allocations) so that you really don't waste any more than what the code and a pointer or two take.

Seriously though, think in terms of ratios. On a computer with 64GB of RAM, nobody really cares if (actuall when) a few hundred megabytes are used by the operating system memory management.

You seem to miss what I'm trying to say. I'm talking about statically allocated memory which is part of the kernel's .bss (which is the only space thats guarenteed to be usable until you work out where all the multiboot stuff is).

Now, say I compile the image to use a static 128MB stack. If bochs cannot allocate that much physically contiguous memory starting at exactly the point specified in the ELF header it fails to load the image. Theres no paging during boot, the memory must be physically contiguous.

As far as why sizes as low as 1MB are not acceptable, my kernel is supposed to be quite small and light on resources with all optional extras disabled. Lets say I try to run the kernel on a system with 4MB RAM, that 1MB doesnt look so small anymore.

[mystran]

Don't reserve 128MB of memory. Reserver 128MB of address space.

You only need a few pages in bss, namely one for page directory and one page table for identity mapping kernel when you enable paging. Even the identity mapping table isn't necessary if system can do large pages. 8k (with 4k alignment) in .bss isn't problem.

Then you first enable paging, and only then start filling the stack. Now you never need more pages for mapping the stack than you have free pages anyway.

[paulbarker]

So my stack/list starts empty with no pages for storage, where do I store the first entry?

I cannot allocate a page to store the stack as I do not know where the multiboot loader has put its data. This is the reason for a bootmem system.

A bitmap is more suited than a stack or list to this task because it is easy to implement commands like "The multiboot info is at address x and of size y, mark from x to x+y as allocated".

[Ryu]

Paul, It really is that easy for me, map this base and limit and unmap that, take first 16MB out into this list.

For bitmaps you need to set aside some space, so for the question where do I store the first entry?, same place where you would of put your memory bitmap. I don't find anything terrible about bitmaps really just a preference of avoiding having to do seperate two managers.

[paulbarker]

I do see the need for a separate bootmem allocator, which is designed for marking regions as allocated or free and the main allocator, which is designed for very fast allocs and frees.

For example, we may have 2 pointers on one page to consider at boot time. With a stack, this means checking thru the stack on every free to check if the page is already on the free list but with a bitmap we simply clear the bit not caring about its original value.

I trust the main system not to free a page twice therefore a stack without the above checks is a good implementation. The bootmem system is required to silently ignore double allocating or freeing a page (since the page might contain both the multiboot info structure and the command line and so get marked as allocated twice).

As to choosing a stack or a bitmap for the main allocator, the choice is pretty much arbitraty. If the bitmap is allowed to be non-contiguous (implemented as a list of bitmaps each a page in length) then the bootmem allocator never has to allocate more than a page at a time, which is good.

I honestly don't know whether to choose a bitmap or a stack. I'm planning to implement both and then choose whichever is simplest.

[Colonel Kernel]

I do see the need for a separate bootmem allocator, which is designed for marking regions as allocated or free and the main allocator, which is designed for very fast allocs and frees.

Me too, but my bootmem allocator is a watermark allocator by design.

Let me try to explain the reasoning behind this scheme in my kernel, and maybe the others will understand better.

First, it's important to point out that I'm not advocating having a bootmem allocator for everyone -- it just happens to be necessary in my kernel design (and I guess in paulbarker's too). I happen to like mystran's suggestion of a free page stack that can use its own free pages to grow -- it's a really elegant solution. The problem is that it can't handle all the requirements of my kernel. My "real" PMM looks somewhat like NT's mainly due to my support for shared memory (no need to go deeper than that for now). It's neither a stack nor a bitmap -- more a fusion of both.

My PMM has two distinct uses -- for managing kernel memory and for implementing my kernel's memory management-related system calls. It also has three states -- uninitialized, "bootmem" initialized, and fully initialized. It can handle requests for physical memory from the rest of the kernel after entering the second state, but it cannot handle requests from user processes until it enters the third state. In order to move from state 2 to 3, it needs some external agent to allocate and map a region large enough for it to hold its "page frame database" (the bitmap/stack hybrid structure I mentioned before). This external agent is the initialization code responsible for managing the Multiboot memory map. Since it is just another part of the kernel, it can use the PMM normally to allocate the required memory. It will also use the VMM to map that memory, and the VMM will in turn use the PMM to allocate memory for page tables.

The key point in this initialization sequence is that the VMM has no idea that the PMM is in a partially-initialized state -- it uses it as it always does. In order for this to work, the PMM needs its "sliding window" bootmem allocator, which lives in a static page allocated in my kernel's .bss. It's a watermark allocator because once the sliding window moves, the information about what was allocated in the previous window is lost. This is ok, because it is only going to be used to allocate memory for the rest of the PMM and for the page tables required to map it in. This memory will never be freed.

I hope this makes sense...

[paulbarker]

Right, I've had an hours sleep and some caffeine now.

I think the best way of sorting this out is to stop and go back to square one. I'm going to treat this the way I was taught in electronics at college: aim, specification (of requirements), list of possible solutions, choice of solution and reasons for this choice. In this document I can also explain the API and so have a good starting point for writing the final documentation (which doesn't need all the info about how I got to the design).

I'm going to spend about a week on this and will post a .pdf on my website for anyone thats interested (its mostly for my own benefit though).

[Colonel Kernel]

I'm going to spend about a week on this and will post a .pdf on my website for anyone thats interested (its mostly for my own benefit though).

Were your reasons for needing a bootmem allocator the same as mine? I've always suspected that I'm doing things the hard way, and I'm curious if you arrived at the same conclusion.

[Ryu]

Right, I've had an hours sleep and some caffeine now.

I think the best way of sorting this out is to stop and go back to square one. I'm going to treat this the way I was taught in electronics at college: aim, specification (of requirements), list of possible solutions, choice of solution and reasons for this choice. In this document I can also explain the API and so have a good starting point for writing the final documentation (which doesn't need all the info about how I got to the design).

I'm going to spend about a week on this and will post a .pdf on my website for anyone thats interested (its mostly for my own benefit though).

I think this is a good choice (I hope I wasn't part of the reason why you lost sleep over). I follow pretty much the same rule, my choices are made to follow the specification or my main objective of my kernel, not to make it most versatile, which I know I can easily be off course over. Anyway I look forward to reading what choices you made, and is only for my benefits really.