OSDev.org

This may seem like an odd question, but how does one best go about tracking regions of the physical address space that are not physical RAM?

Looking at the different ways of tracking physical memory, none of them seem to be quite appropriate. Bitmaps would be wasteful since most of the physical addresses may be unused (particularly in the PAE or 64-bit cases). Free "non-RAM page" stacks would be wasteful for the same reason. What sort of data structures and algorithms do you all use or recommend?

A side question -- I'm using GRUB. Some physical address regions are not present in the Multiboot memory map (i.e. -- they are actually not there, as opposed to entries that are present but whose type indicates that they are not usable RAM). Are these regions that aren't in the map guaranteed to be utterly useless (i.e. -- not mapped to any I/O devices ever)? I suspect the answer is "no" because of something to do with PCI, which I know nothing about yet... have mercy.

Hi,

I call this a "physical address space manager".

The thing is, the physical address space doesn't change often, so performance doesn't matter too much. I use a sorted table of entries, which involves copying data when an entry is inserted or removed. A better idea would be a sorted linked list (to avoid the copying), but anything more complicated (or anything with better performance) isn't necessary.

Colonel Kernel wrote:A side question -- I'm using GRUB. Some physical address regions are not present in the Multiboot memory map (i.e. -- they are actually not there, as opposed to entries that are present but whose type indicates that they are not usable RAM). Are these regions that aren't in the map guaranteed to be utterly useless (i.e. -- not mapped to any I/O devices ever)? I suspect the answer is "no" because of something to do with PCI, which I know nothing about yet... have mercy.

AFAIK GRUB just returns whatever the BIOS told it (e.g. int 0x15, eax = 0xE820). This won't include memory mapped devices - you'd have to scan the PCI buses (and possibly detect ISA cards) to find out which areas they use.

If the computer doesn't support int 0x15, eax = 0xE820 then I think GRUB will only report RAM areas (from other BIOS functions), so you won't know which areas are "system areas".

I'd also be carefull with both Bochs and QEMU - the standard BIOS won't return "system areas" from int 0x15, eax = 0xE820 like it should, so if you're looking for an address range to map a PCI device you could overwrite something that should have been reported (e.g. ROMs or APICs just below 4 GB, or anything between 0x000A0000 to 0x000FFFFF).

To avoid these problems, I'd assume that everything below 16 MB is not unused, and everything above 0xFEC00000 is also not unused (regardless of what GRUB says). This would also mean that memory mapped ISA devices (which use the areas between 15 MB and 16 MB) aren't a problem.

Also, the "ACPI reclaimable" area normally reported by int 0x15, eax = 0xE820 can be "reclaimed" and used as normal RAM when you've finished using the ACPI tables (or if you never use the ACPI tables).


Cheers,

Brendan

Thanks for the details -- this helps. Based on your suggestion, I'm thinking maybe of using a binary search tree of region descriptors stored in an array -- sounds like that would do the trick.

I realize that GRUB just reports what the BIOS told it. There is a bit of a problem however, in that the Multiboot spec only defines two types of regions in the memory map -- RAM (type == 1), and not RAM (type != 1). This is frustrating, as I can plainly see that there are a few types other than 1 (lots of 2s, a few 3s and 4s when running on VMWare). But if I want to follow the letter of the Multiboot spec, I can't rely on any particular interpretation of these values, other than the fact that they are "not RAM" (once again, making me want to strangle the folks who wrote the spec... and most other specs too).

This begs the question -- how can I go about populating my list of non-RAM regions without using the GRUB memory map or the BIOS (I don't plan to support V8086 mode)?

Hi,

Colonel Kernel wrote:This begs the question -- how can I go about populating my list of non-RAM regions without using the GRUB memory map or the BIOS (I don't plan to support V8086 mode)?

Of course the alternative to not using GRUB or the BIOS would be detecting which chipset is present and using raw I/O ports to figure out what is where - I wouldn't recommend it .

First, explain your problem to the people responsible for the Multiboot Spec, and try to get the specification changed so that it reflects reality (or so it includes every area type defined by ACPI that may be returned by the BIOS/GRUB). This doesn't solve the problem on older BIOSs though.

Then use assumption. For example, you could assume that any area that isn't reported as usable RAM by GRUB is unusable space. This means the ACPI reclaimable area won't be reclaimed (wasted RAM), you won't know the difference between faulty RAM and ROM, etc. Then, make sure that the area between 0x000A0000 and 0x000FFFFF and the area above 0xFEC00000 is also marked as unusable (even if it's not).

After this you'll have a basic map that works (even if it's not "perfect"), and you can add other areas to it (e.g. PCI devices).

BTW are you sure a binary search tree isn't more hassle than it's worth? After boot, how often will this tree be searched or modified? AFAIK, hot plug RAM and hot plug PCI devices are the only reason it'd be needed after normal PCI devices have been detected/configured. Of course I'm assuming you'd have an entirely seperate "physical memory manager" for managing free RAM...


Cheers,

Brendan

Brendan wrote:Of course the alternative to not using GRUB or the BIOS would be detecting which chipset is present and using raw I/O ports to figure out what is where - I wouldn't recommend it .

Bleah... I totally agree.

First, explain your problem to the people responsible for the Multiboot Spec, and try to get the specification changed so that it reflects reality (or so it includes every area type defined by ACPI that may be returned by the BIOS/GRUB). This doesn't solve the problem on older BIOSs though.

I may have found a loophole. From the Multiboot spec:

In reference to bit 6 of the flags parameter in the Multiboot information structure, it is important to note that the data structure used there (starting with BaseAddrLow) is the data returned by the INT 15h, AX=E820h -- Query System Address Map call. See See Query System Address Map, for more information. The interface here is meant to allow a boot loader to work unmodified with any reasonable extensions of the BIOS interface, passing along any extra data to be interpreted by the operating system as desired.

I guess this means I can rely on all values of the Type field that can be returned by int 15h, and then a Fancy BootLoader of the Future might give me Type values I don't recognize, in which case I would have to find some other means of identifying what they are.

BTW are you sure a binary search tree isn't more hassle than it's worth? After boot, how often will this tree be searched or modified? AFAIK, hot plug RAM and hot plug PCI devices are the only reason it'd be needed after normal PCI devices have been detected/configured. Of course I'm assuming you'd have an entirely seperate "physical memory manager" for managing free RAM...

I don't think a BST that lives in an array is any more of a hassle than a sorted array where you have to copy elements around. However, you've made me think about what I'm using the data structure for... I think what you're talking about is a map, which is still important since I'd like to prevent drivers from mapping regions of the physical address space that are empty (i.e. -- backed by neither RAM nor ROM nor a device).

However, I also need a structure that can help track whether a driver process has mapped a certain non-RAM region of the physical address space into its virtual address space. I want to enforce exclusive ownership of these physical address regions so that one driver can't interfere with another's device(s). While I can imagine that such a structure would be much more static than the free RAM list, it seems to me it would be more dynamic than the physical address map, since drivers do start and stop (and therefore map and unmap physical address regions) now and then. Does this make more sense?

Hi,

Colonel Kernel wrote:I don't think a BST that lives in an array is any more of a hassle than a sorted array where you have to copy elements around. However, you've made me think about what I'm using the data structure for... I think what you're talking about is a map, which is still important since I'd like to prevent drivers from mapping regions of the physical address space that are empty (i.e. -- backed by neither RAM nor ROM nor a device).

However, I also need a structure that can help track whether a driver process has mapped a certain non-RAM region of the physical address space into its virtual address space. I want to enforce exclusive ownership of these physical address regions so that one driver can't interfere with another's device(s). While I can imagine that such a structure would be much more static than the free RAM list, it seems to me it would be more dynamic than the physical address map, since drivers do start and stop (and therefore map and unmap physical address regions) now and then. Does this make more sense?

That does make some sense .

For me, exclusive device driver ownership of physical address space areas is controlled by a "device manager", which isn't part of the kernel. The reason for this is that you will also probably want exclusive device driver ownership of I/O port ranges and controlled ownership of IRQs. Physical address space areas, I/O ports and IRQs form a related set of resources, where access to all resources for a specific device is granted in one operation.

The device manager discovers the devices and detects/configures which resources they use (e.g. PCI bus scan, etc) and then starts any device drivers needed. The device manager tells the kernel which resources the device driver can use when starting the process/driver, and also sends a message to the device driver telling it what resources it can use. The kernel itself just records the resource information in the process's data area and checks this information when the device driver tries to allocate any resource.

As you can imagine the device manager itself is a large complicated thing, which (IMHO) is too large and ugly to belong inside a micro-kernel. Seperating it from the kernel means that it can run in user space (better protection) and that the OS can have several device managers - e.g. one for modern PCs (without ISA support), one for old PCs (with ISA), one for Xbox, one for PowerPC and some more for specific embedded devices.


Cheers,

Brendan

Brendan wrote: I call this a "physical address space manager".

The thing is, the physical address space doesn't change often, so performance doesn't matter too much. I use a sorted table of entries, which involves copying data when an entry is inserted or removed. A better idea would be a sorted linked list (to avoid the copying), but anything more complicated (or anything with better performance) isn't necessary.

I have universal address space manager which I can use to track free address space for kernel moduls & heap, process space for IPC & librarys...