OSDev.org

So, I'm ready to put my physical memory manager to work but I need to allocate some space for use by the manager before the manager is running. This is a very typical chicken-and-egg problem, I'm just wondering how other people handle this?

My first thought is to use a buddy bitmap system (with the bitmaps statically allocated) managing only the first say 16MB of physical memory, but I want to avoid an error when there is no free space before 16MB but tonnes after 16MB (maybe caused by a multiboot module for a 32MB ramdisk being placed immediately after the kernel).

Since there is no way of knowing where a multiboot loader is going to place modules and other such datas, I can't see any foolproof answer to this problem. Any ideas?

EDIT: I call this sort of thing a "bootmem" system. I think it's called that by most people and I've searched the forums for that, but are there any other words or phrases I should search for?

I have a stack for my physical memory manager. It has a static area of kernel addressspace reserved, but no pages mapped initially. When you free a page, if there's stackspace, it's put into stack, if not, the free'd page is mapped for use as more stack space.

I also used to have the reverse in previous iteration of my kernel, but haven't added it to current yet: if there's full page worth stack space when a page is allocated, unmap the stack page, and give it instead of taking one from the stack.

With the above, when all memory is in use, the physical memory manager doesn't need a single page for it's stack. So in a sense, it doesn't need any memory at all, because it only needs part of the free memory, and only when it's free.

To start the whole thing, I just use statically allocated pages (in kernel BSS, page-size aligned page sized arrays) for the initial page directory/tables that I need to get paging started, and then just iterate the memory map (given to me by GRUB), freeing any pages that fall outside kernel and modules (actually, I keep the memory below 1MB reserved).

Ofcourse it means that my physical memory manager can't even run without paging, but since getting paging up and running doesn't depend on physical memory manager, there's no chicken and egg.

edit: ok, it does use 4k, because the page table for the space is statically allocated, because messing up with that would be a bit too complicated, since kernel space is present in any user context; not worth the trouble

Wow... great idea . I'll add this to my todo list.

What I did was statically manage the lower 1 MB, which is actually where my kernel resides (my kernel is very small should be no more then 62KB to fit into a ROM for later). As of now its booting from a floppy which then loads boot.sys that will reside at address 001000h - 007BFFh (27KB). Since boot sector is located at 7C00h this should assure theres memory in the location. And the area 800h - 1000h (2KB) was reserved for the boot.sys stack. Boot.sys will then get a map of available memory using part of the reserved stack space and make appropiate checks to validate memory areas of kernel to reside in. If all checks are passed it loads kernel and run kernel which the kernel then takes the map information given by boot.sys and maps them into the manager, so no second manager is needed.

Ofcourse boot.sys is technically not working as a multi-boot loader but can very easily be one and I find 27KB and 2KB reserved stack to be plenty enough.

Thanks for the input .

I like the idea of a stack for the regions of memory where allocations will only be 1 page at a time. For DMA memory I'll use a buddy-bitmap allocator.

The way my allocation system works it is not really possible to allocate the management structures (bitmaps, stacks, etc.) staticly (or is that statically?). This would require the arch-dependent bootup code to have access to the internal data structures of the memory manager which is not allowed.

I need to think more on the stack vs. bitmap question for non-DMA memory areas, but for now I have a partial answer to my own question: If enough free memory is not found in the first 16MB, clear the buddy bitmaps and retry with the bitmaps managing the area from 16MB to 32MB, and so on if it keeps failing. Once the necessary amount of memory has been found, this initial bitmaps can be scrapped and the real memory manager started up.

This bootmem system is arch-dependent for several reasons. The only real pain here is factoring in all the multiboot memory areas since any dynamic allocation done before they are factored in could overwrite critical data.

paulbarker wrote: This bootmem system is arch-dependent for several reasons. The only real pain here is factoring in all the multiboot memory areas since any dynamic allocation done before they are factored in could overwrite critical data.

Do you mean the multiboot loader memory area that it resides or modules that the multiboot loader has set aside for?

In the case if its the multiboot loader, you always going to have to reserved a memory area for it to run on.

In the case if its the modules then there needs to be some kind of protocall specification before you jump into the module, inorder for the module to know exactly what is the state of available memory ranges. Or you can possible hook some interrupt calls (ex. BIOS INT 15h AX=0E820h) to make it transparent.

I'm personally confused now where your current state is, are writting a multi-boot loader and concern about reserving DMA memory? Or are you writting a module concerning what multi-boot loader had reserved?

Personally I don't like using bitmaps to manage memory, because they will end up large, it has some good sides but if you ever think about multi-tasking envioment and want to track each task's memory usage, inorder for you to deallocate them, bitmaps will in my opinion make the manager much more complicated. But I'm no expert.

Hi,

For me, the real mode boot code has it's own physical memory manager that uses static areas. When paging is being setup, pages are allocated for the kernel (including pages for the kernel's physical memory manager data) using the real mode physical memory manager. Once the system is in protected mode (or long mode) and paging the data used by the real mode physical memory manager (and anything else that isn't needed) is freed. This won't help with your problem though...

For the multiboot specification (which isn't necessarily limited to GRUB), any time you use RAM you have to worry about overwriting extra boot modules, the kernel's stack or the multi-boot information (system memory map, etc). This is because none of these have set addresses.

AFAIK the only safe RAM that you can use (before initialization) is the kernel's ".bss" section. The first thing I'd do is set the kernel's stack to somewhere in the .bss, then make a copy of any multi-boot information that you don't want to overwrite. After that I'd initialize the physical memory manager (also using the .bss section for data storage), being careful not to treat the extra boot modules as free RAM. Lastly I'd setup paging using the physical memory manager and making sure that any extra boot modules are mapped into sane linear addresses (so that you can free parts of the linear address space when you're finished using the extra boot modules).

paulbarker wrote:I need to think more on the stack vs. bitmap question for non-DMA memory areas, but for now I have a partial answer to my own question: If enough free memory is not found in the first 16MB, clear the buddy bitmaps and retry with the bitmaps managing the area from 16MB to 32MB, and so on if it keeps failing. Once the necessary amount of memory has been found, this initial bitmaps can be scrapped and the real memory manager started up.

For ISA DMA you have to be able to allocate contiguous pages of RAM that are below 16 MB and don't cross 64 KB boundaries. Because of this I manage all memory below 16 MB using a bitmap, and all memory above 16 MB using "free page stacks".

This solves the ISA DMA problem. For 32 bit PCI devices (and for the page directory pointer table if you use PAE) you need to be able to allocate pages that are below 4 GB. Because of this I have 3 physical memory managers - one for "low memory" (below 16 MB), one for "middle memory" (between 16 MB and 4 GB) and one for "high memory" (above 4 GB). This means that if a single page is needed where the physical address must be 32 bit I can use "middle memory", and if I need contiguous pages with 32 bit physical addresses I can use "low memory".

If I'm allocating pages and the physical address doesn't matter, I use memory above 4 GB before I use "middle memory", and I only use "low memory" if I have to. The idea is to keep the most useful pages free so that it is still available when a device driver has specific requirements. I also relocate everything out of low memory during boot (if possible) so that low memory isn't used unnecessarily - for a computer with several GB of RAM and heaps of devices, the first 16 MB are a precious resource.


Cheers,

Brendan

I wonder, how much of the first 16MB you typically will be needing for device drivers? There aren't that many ISA devices in a typical modern computer, and they are mostly legacy anyway, and hence shouldn't need such a large amount of memory buffers, right?

Ofcourse if one wants to avoid memory copying at all cost, then fine, but...

I wouldn't think there would be a lot of devices required lower 16MB on modern computers as well, but I also was thinking to make use of memory -> memory DMA operations, so the lower 16MB is precious to me. I'm not sure wher, when and how I'm going to use it, just a opening for the future. :-\

Hi,

mystran wrote:I wonder, how much of the first 16MB you typically will be needing for device drivers? There aren't that many ISA devices in a typical modern computer, and they are mostly legacy anyway, and hence shouldn't need such a large amount of memory buffers, right?

In theory for ISA DMA you should never need more than about 1 MB. For a real system you'd probably only need about 256 KB (e.g. floppy, parallel port and sound card).

For me this 16 MB area is the only place where contiguous buffers can be allocated (everything else uses faster "free page stacks"), so the real problem is allocating contiguous buffers for PCI devices.

Of course I'm a little bit paranoid too (which can be a good thing)...


Cheers,

Brendan

Right, so in theory I should be safe with 1MB allocated separately.

As for continuous buffers, I'm going to solve that problem the hard way I guess: take a continuous set of pages that aren't part of a continuous buffer (and hence safe to relocate), allocate some random other places, do replacement, and give the freed range to PCI device.

This naturally required knowing each and every mapping, but I need it for other purposes anyway (in a structure that's easy to travel in constant space), it seems. Ofcourse that's also slow to do, so if it proves too slow, I have to consider keeping separate reserve for such buffers.

Ofcourse I could do that for ISA devices too, I guess.

Not that it's terribly hard to switch to another policy later, since all physical memory allocation goes through the same interface.

paulbarker wrote:If enough free memory is not found in the first 16MB, clear the buddy bitmaps and retry with the bitmaps managing the area from 16MB to 32MB, and so on if it keeps failing. Once the necessary amount of memory has been found, this initial bitmaps can be scrapped and the real memory manager started up.

That's almost exactly what I do, although you have to take heed of Brendan's warning:

Brendan wrote:For the multiboot specification (which isn't necessarily limited to GRUB), any time you use RAM you have to worry about overwriting extra boot modules, the kernel's stack or the multi-boot information (system memory map, etc). This is because none of these have set addresses.

I resolve this by initializing each "window" of the "sliding window bitmap" with the contents of two lists. The "free" list is applied first, and includes all regions reported as available by the Multiboot memory map. The "used" list is applied second, since it contains extra information not included in the Multiboot memory map, such as the kernel's load address and end address (i.e. -- the end of its .bss section), as well as the contents of the Multiboot module map.

The solution to the multiboot problem is allocating enough memory into kernel .bss section, that you can live without more memory, until you've processed the memory map, and module lists. As long as the bootloader can do the right thing with bss, you're safe; you can copy the multiboot structures into that memory if you want, and you know from them where your modules are, so there's no problem with overwriting anything.

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.

Using a static bitmap which can manage 16MB and moving the "window" which the bitmap refers to is probably the best way of initializing the memory manager. The map for each window would then be converted to a free list. With some optimizations this could be acceptably fast, although it will never be very efficient (re-checking all pointers for each window).

Hmm why create a free list and a memory bitmap? In the end I'm just seeing twice the work to store whats used or free, and ofcourse more space to map memory. The only real benifits I see with bitmaps is the lookup is incredibly fast, however can be really slow when your trying to find that one bit representing a page or so (I guess thats where the free list comes along). I just use a free list for the entire 4GB address, no complications and execptions even for the first 16MB. Lookups are also fast if you arrange the list, allocations would be faster then bitmaps, simply take the base address align it to your aligning needs and take the limit subtract that, you can now tell if your contigious needs meets the requirments. But ofcourse this is just my preference.