Physical memory management

[Echo]

Hey everyone I'm new here, and I have a good history of C and assembly programming (x86 of course) along with others.

Anyway lately, I've become interested in OS design and I have gotten the majority of the basic kernel functions done, but now I'm at the memory management part, which from what I've heard is the hardest part of OS design. Basically I understand the concept and of course I'll need to start with a physical memory manager to allocate 4kb pages to stuff, so then I can finally get to work on paging.

The problem is that there is almost no documentation on creating a physical memory manager, so here I am.
My idea of how its supposed to work is finding the end of your kernel and starting a stack of memory address there, and from there just push/pop to allocate/free pages, but when I started looking at some other Operating System sources I starting 4K align macros, masking stuff, and other completly foreign things, so I was hoping for some advice.

One last thing, how would I get the size of the physical memory on board? I'm using GRUB but I definitely don't want to rely on the mem_lower and mem_upper as I want to get a 100% accurate memory size.

Thanks, Echo.

[CodeCat]

The stack method is pretty common from what I've seen here, but it has a rather severe drawback: You can only allocate single pages with it in O(1). So if you need a larger amount of contiguous memory, you're down to O(n) or worse as you have to search the whole stack for contiguous blocks.

[Echo]

Thanks, I forgot to mention that I'm using a bitmap for the first 16 MB and a stack for the rest. Thus the bitmap will cover contiguous memory (I think O(n/2) ?!?).

But this doesn't really help me with my above questions , thanks though .

[CodeCat]

The bitmap will be O(n) (O(n/2) is the same as O(n) because of the way O works), but there are some tricks you can use to speed it up. A simple way is to keep an index where the last successful allocation was made, so that it can be the starting point for subsequent allocations. A more elaborate way is by using a buddy system, which splits the bitmap into several 'layers' where each higher layer doubles the amount of pages a single bit specifies. That way, if you ever need say 4 pages, you can simply look in the layer for 4-page blocks. You need to do some further sanitising when you allocate/deallocate, but I'll leave it to you to read more if you're interested.

As for your memory size question: GRUB passes you a memory map as it gets it from the BIOS. The map isn't exactly trustworthy when it comes to integrity (i.e. overlapping areas, gaps, etc) so you have to sanitise it somewhat. But the map WILL be correct. So once you have the map, you only need to count all the regions it marks as type 1 (= available RAM). However you will also need to account for areas which the map might not include, such as the (E)BDA and the ISA memory hole.

A possible way of sanitising (the way I did it) is to convert the map into an ordered linked list of 'change points'. You build a second map, which starts off empty. Then you add the BIOS map's regions one by one. For each region added, you add two change points: at the start and end of the new region. Every change point also has a region type (as given by the BIOS map) associated with it. So when inserting all you have to do is make sure that the change points are ordered with respect to one another (which is easy if you order each point as it's inserted). You also have to account for overlap, which means in my case that if the region to be inserted overlaps with an existing region, then the region types all change points between the start and end are set to the highest of either their current value or the type of the new region. It might seem a bit messy but it works like a charm, and it also allows you to insert regions that aren't in the BIOS map. You must however 'fixup' the map after inserting all the regions before using it, which means that you must delete repeated points of the same type occurring in a row, so that the region becomes a single contiguous one. You could also account for any gaps that may have been left in the map, and mark them as reserved.

[pcmattman]

I solved the contiguous memory problem by writing a function that would allocate and map memory at the same time, so you would have what appeared to be a contiguous set of pages but thanks to paging there can be pages from all over the address space at work.

And I use the memory map GRUB gives me to find out the usable and unusable regions of RAM, which works very well.

[CodeCat]

That doesn't work if the pages need to be physically contiguous, as is the case with DMA. So his solution of not using a stack for that region of memory is the better one (though a buddy allocator would do even better, as it would avoid crossing a 64 kB boundary automatically as well).

The map GRUB gives you is the BIOS map. And as I said, that map may not be ordered, may contain overlapping regions and may contain gaps with unspecified memory. In particular, the Bochs BIOS leaves a gap at the top of the low memory area below 1 MB, which is simply left unspecified.

[Brendan]

Hi,

That doesn't work if the pages need to be physically contiguous, as is the case with DMA. So his solution of not using a stack for that region of memory is the better one (though a buddy allocator would do even better, as it would avoid crossing a 64 kB boundary automatically as well).

A buddy allocator easily handles aligned areas, but isn't capable of handling unaligned areas. This means that if you want a 32 KiB DMA buffer and the only free area this large is from 0x00014000 to 0x001C000, then the buddy allocator will call it 2 separate 16 KiB areas and won't let you allocate it even though it's perfect for what you want.


Cheers,

Brendan

[egos]

may contain overlapping regions

Are you sure? I just check range type, align ranges on page boundaries and trim ranges staying between 1 mb and 4 gb boundaries.
I reserve 1st mb for hardware buffers controlling this memory region by using bitmap. I control other memory by using special table with stack structure named Free Page Table. Current top value of FPT defines the number of free pages. But I also use two variables for saving total number of page tabs used by FPT after kernel is loaded and number of that page tabs which still mapped when FPT is empty.

[Brendan]

Hi,

may contain overlapping regions

Are you sure?

I've never come across a system with overlapping areas; but the Linux kernel has special code to handle overlapping areas:

/*
* Sanitize the BIOS e820 map.
*
* Some e820 responses include overlapping entries. The following
* replaces the original e820 map with a new one, removing overlaps.
*
*/
int __init sanitize_e820_map(struct e820entry * biosmap, char * pnr_map)

I'm not entirely sure if Linux does this because some BIOSs do return overlapping areas; or if Linux does this because it might receive a memory map with overlapping areas for other reasons (e.g. overlapping areas created by the user with "memmap = " kernel parameters).

For each area returned by the BIOS, I check the type and if it's an unknown value I change it to "TYPE_UNKNOWN", so that I can define my own area types and use them for anything I like. I check for overlapping areas, and if 2 areas overlap I change the type of the overlapping area to "TYPE_MIXED". I also remove areas with "size = 0", combine adjacent areas of the same type (so 2 entries become one entry), and sort the list.


Cheers,

Brendan

[egos]

I only use address ranges with the type AR_MEMORY (1) and ignore other types. The regions that have zero or "subzero" (it is possible if alignment was done) size are ignored too.

[CodeCat]

But you have to take into account that areas with type 3 (ACPI reclaimable) can be freed after you're done with them, and then they become type 1.

[egos]

I know.

[Brendan]

Hi,

I only use address ranges with the type AR_MEMORY (1) and ignore other types. The regions that have zero or "subzero" (it is possible if alignment was done) size are ignored too.

But you have to take into account that areas with type 3 (ACPI reclaimable) can be freed after you're done with them, and then they become type 1.

I know.

That'd be a little hard after you've gone and aligned things.

For example, imagine a memory map that initially has 2 entries like this:

Code: Select all

Address    Size       Type
0x08000000 0x07FFE800 Usable RAM
0x0FFFE800 0x00001800 ACPI Reclaimable

Then you go and align the RAM area and end up with:

Code: Select all

Address    Size       Type
0x08000000 0x07FFE000 Usable RAM
0x0FFFE800 0x00001800 ACPI Reclaimable

Then (much later on) you reclaim the ACPI reclaimable area:

Code: Select all

Address    Size       Type
0x08000000 0x07FFE000 Usable RAM
0x0FFFE800 0x00001800 Usable RAM

And probably align that too:

Code: Select all

Address    Size       Type
0x08000000 0x07FFE000 Usable RAM
0x0FFFF000 0x00001000 Usable RAM

Now a page of RAM has gone missing, and there's a nice hole in the memory map where it should've been!

I only use address ranges with the type AR_MEMORY (1) and ignore other types.

When you're initializing PCI devices (and setting BARs for unconfigured devices) and looking for somewhere in the physical address space to put some memory mapped I/O (e.g. 1 GiB of video display memory from the second video card that, unlike the first video card, the BIOS didn't configure), how do you find out which parts of the physical address space are still unused?


Cheers,

Brendan

[CodeCat]

I solved that problem by storing both the real memory address and the page-aligned memory address of a memory region. The pages don't overlap either, because the addresses are either rounded up or down depending on the type and the type of surrounding regions. I.e. a partially free page is reserved. When a region is freed up, its type is simply changed and the list is re-fixed to remove any sequential areas of the same type, and the page boundaries are recalculated. Seems like a lot of work, but memory regions are rarely reserved/freed (if at all) so it works quite well.