Page 1 of 1

Unusable areas in the memory map.

Posted: Sat Mar 24, 2012 9:43 pm
by sandras
So I almost finished my memory detection code. Needs some polishing, some finishing touches, more comments. As suggested, I'm managing overlapping free and non free areas in various combinations - merging adjacent free areas, splitting a free area into two smaller areas, if an unusable area is in the middle of it, shrinking/truncating a free area, if a non free area partially overlaps it. And my question is about those unusable areas. Is it necessary to keep track of them? Currently I extract only the usable ram areas. Though keeping track of unusable areas should not be hard to implement having current functionality. I mean I understand perfectly clear why I need to know usable ram areas and not write to areas, that are not free for use. But what would I use the non free areas for? Do I really need to know where they are, if I can't use them? Because it seems that I know where certain devices are mapped. I could use vga text mode memory as an example. It's location is standardized, it is always at the same address. Or so I think. It's memory is not available for use in the sense, that you can't allocate an area that it uses, for other purposes, but the kernel's vga text mode driver uses it for it's own good. While it does not have it's memory zone marked as unusable, it assumes the area is meant to manipulate the text on screen. Then, AFAIK there are devices that can be mapped by kernel to areas it chooses. Correct me if I'm wrong, but PCI would be one case of that. But I thought, that the kernel could allocate an area of known usable ram for that. So again, i can't see the purpose of tracking unusable ram areas. Then there's the simple matter, that it's logical, that areas, that are not mapped as usable, are unusable. And perhaps the kernel could track which device uses which area (like the PCI) of memory by tracking those areas in the memory map - marking them as unusable, but again, I think that the addresses for memory mapped devices are either assumed (IOW hard coded), and don't need to be tracked, or allocated by means of memory management. And maybe it is because some areas are marked as "reclaimable"? This is the only reason I can think of right now. And I read http://forum.osdev.org/viewtopic.php?f= ... 01#p140080 and http://wiki.osdev.org/Memory_Map_(x86) , which are mostly the same, but still. These two pages don't seem to make it clearer for me. I also tried searching the net, but either there is little to no such information, or Google just can't find it, or I was using the wrong keywords. Oh, and the stuff about PCI in this Brendan's post http://forum.osdev.org/viewtopic.php?f= ... ap#p206397 indicates that memory mapped PCI devices' memory ranges should in fact be marked as unusable ram? If so, is it possible to do it the way I mentioned, which I'd prefer, at least with the current knowledge, or are there some sort of barriers for that, maybe some sort of reason, why the other way is better?

Re: Unusable areas in the memory map.

Posted: Sat Mar 24, 2012 11:51 pm
by Rudster816
What you do is a design decision IMO, and there really isn't one preferred way to keep track of the physical memory range. For the purpose of simplicity, I'll pretend the lower 1MB of the physical address space doesn't exist, because that really blurs things up. Just remember to keep in mind that things below 1MB include the BIOS ROM area, ACPI\MP Tables, real mode IDT, BDA, EBDA, etc.


Basically you have three types of address ranges. One maps to main memory, and is available for you to use as RAM\storage\whatever. Another would be memory mapped hardware, which should obviously only be referenced when trying to control that particular piece of hardware or not at all. The last would obviously address's that map to absolutely nothing and should never be referenced. With this in mind you can break your physical memory manager into two parts, a page frame allocator and a hardware I\O manager. It's easiest to just keep track of which physical ranges exist according to the BIOS, and what they are for according to the BIOS. Anything not mentioned by the BIOS should be treated as non existent.

The page frame allocator only needs to be aware of free RAM regions. It can just assume everything else is off limits. Things get a little trickier when you get into DMA, where hardware needs access to contiguous physical memory. So it might not matter weather or not page frames are contiguous for the virtual memory manager (which would assign those non contiguous physical frames to contiguous virtual memory), it does matter for DMA. You'll need to keep this in mind when writing your page frame allocator, because if your physical memory becomes highly fragmented, it will be difficult to allocate buffers for DMA transfers of significant sizes.

On the other hand a hardware I\O manager only needs to be aware of what regions of the physical address space is mapped to hardware, however it's probably beneficial for it to be aware of everything. The way you manage the hardware is highly design specific and depends on your driver model (or lack thereof)\etc. Basically if a device driver requests some region of the physical address space to control its device, you have a major design decision. You could just unconditionally grant its request, map the address space, mark it as uncachable and be done with it. Obviously this could very easily lead to some serious errors, e.g. the device driver errenously requests an address space that's in RAM (and hence not hardware) which might be being used as such by the page frame allocator. You should probably check if the address falls into 'available' ranges and always give an error if it does. It's also probably best to make sure that the requested range is marked as 'reserved' by the BIOS and error out if it isnt. While there might arise a situation where you actually have an address range that is physically mapped, but not marked so by the BIOS, but by far the most likely scenario is that the driver is wrong, not the BIOS. Design considerations for a hardware I\O manager would be rather or not to always grant exclusive access to an address range, or to allow two or more drivers to share it. You might also restrict certain types of device drivers from being able to request physical address space at all (e.g. a file system driver should never access any hardware directly).


With all of this in mind, I think it's a lot easier to decide on how to decide how to keep track of all address ranges. Your page frame allocator needs to have a page by page view of physical memory, and be able to mark any given page as free\used. If you use bitmaps, you might consider only mapping 'available' pages from the BIOS, having a bitmap for each 'available' region. The hardware I\O manager only needs to be aware of regions of address space, and doesn't need a page by page view. I think the easiest way to implement this would be a linked list of all regions of possible address space. Marking each region as non-existent\main memory\hardware mapped\etc. Then when you decide its time to allocate a portion of the space, just mark that region as 'in use by driver foo' or something.

Re: Unusable areas in the memory map.

Posted: Sun Mar 25, 2012 2:57 am
by sandras
Rudster816 wrote:What you do is a design decision IMO, and there really isn't one preferred way to keep track of the physical memory range.
First off, this is primarily what I needed to know. This is my first time implementing a kernel, so sometimes I'm not quite sure if doing things one way or another won't lead me to a dead end further down the road, so I try to check things out. After all, I'd prefer to do it as good as possible the first time, even if reimplementing parts of the kernel or changing it's aspects of design may be inevitable at some point.
Rudster816 wrote:Just remember to keep in mind that things below 1MB include the BIOS ROM area, ACPI\MP Tables, real mode IDT, BDA, EBDA, etc.
Just to be sure. The BIOS int 0x15, eax = 0x0000e820 reports area from 0 to about 650kb free on two of my machines (haven't tested the third, last one, as that requires reconnecting monitor/keyboard/power supply) and in QEMU, so I'm assuming it is usable once I'm in protected mode, but should stay intact if I wan't to return to real mode later? I just want to be sure, that overwriting content's there wont result in broken hardware or something, and that I can trust all the information that this memory detection method gives me. It's probably silly, but I somehow, without a real good reason had the assumption, that IVT, BDA, EBDA and whatever else is in that area is unusable from power on to shutdown. The first time I got the results from the mentioned BIOS function I was surprised because of that assumption. Whether to use that area or no, is still in consideration. I suppose it would slow down the physical memory manager to have to take into account an extra separate usable memory range for not that much memory. Maybe the kernel could decide whether to use that memory or not depending on the total amount of memory in the system. Though I should probably delay such implementation details, and concentrate on more important and central stuff.

While reading your post one question arose. I know, that hardware can be memory mapped before my boot loader starts. But what about when the system is up and running. My question is - are there cases, when you try to access/initialize a device, and it reports it has to be mapped, or simply does map itself to, some memory region it picks itself? Wait... Now that I wrote it, I realize, that would break pretty much any OS. Or maybe not, if the system is required to clear the required memory area and give it to the device. But that still sounds quite idiotic. So I can assume that any device is either memory mapped before control passes to my boot loader, or I can tell it where I want it to be mapped? And maybe that's too much to ask, but, as I care for portability, is that valid on any architecture/platform?

While I did take your thought's on managing the memory into account, I still prefer and would like to try designing and implementing the model, where there is one central physical memory management system and everything that wants to get some memory to use, go through it - caching, buffers, chunks given out to processes, pretty much anything else I'll need. In other words, as many cases as possible, should be handled by physical memory manager. Getting any memory that's marked as usable goes through it. That will demand some sort of identification system for what kind of owner it is, not just pid, I think. But all that sub-system is still in ideas and design stage, so I can't say for sure how I'm going to do things. I'm reading up on malloc's/free's, to give me some insight on it, and generally thinking about what subsystems may need to allocate memory.

Also, while writing the sanitizing code for memory map, I converted the 'length of region' into 'region end address' as it was more convenient to work with and I think made the algorithms shorter, and am thinking, what would malloc and friends prefer? Both maybe? Maybe I'll find that out when implementing, that shouldn't be too hard to change on the run, I suppose.

And hey, the note on MDA is really important, I think. I imagine, the kernel might want to allocate some memory for DMA right from the start? As writing to disk may be just painful having very little space for DMA buffer, you know, in case all the memory is clogged up by some processes.

Sorry if there were some silly question, but I want to be 100% sure about some stuff, and not regret later, that I did not double check. And thanks for taking the time to give so much info.

Edit: Note: I'm thinking of having managed language user space and if I'm going to use paging, that will most likely be much later. In case that matters.

Re: Unusable areas in the memory map.

Posted: Sun Mar 25, 2012 3:42 am
by gerryg400
I'd just like to point out that the ACPI tables are normally above 1MB and some of the ACPI memory is reclaimable after the information is read.

Also it's actually not very difficult to implement a memory defragmenter that can find enough pages to satisfy a request for DMA memory if there is no contiguous memory available. It's a very simple matter to replace the physical pages in a process with other physical pages.

Re: Unusable areas in the memory map.

Posted: Sun Mar 25, 2012 5:13 am
by Brendan
Hi,
Sandras wrote:Then, AFAIK there are devices that can be mapped by kernel to areas it chooses. Correct me if I'm wrong, but PCI would be one case of that. But I thought, that the kernel could allocate an area of known usable ram for that.
No. In this case the kernel would need to allocate an area for the memory mapped device that isn't used by *anything*. This would be an area that is not usable RAM, not used by firmware/ROM, not used by any PCI device, not used by any other device (e.g. APIC), and not reserved (e.g. for "hot-plug RAM" or something).

That's where the problem is - if you only know where usable RAM is (and don't know where anything else is) then you can't find an area that is suitable for the memory mapped device.

It could be much simpler than that though - you could assume that the firmware correctly configured all PCI devices and that the OS will never need to allocate space for a memory mapped device. However, I would expect that the firmware in lots of different computers screw it up in a lot of different ways (and that nobody has actually noticed because most/all mainstream OSs set up PCI devices themselves instead of assuming the firmware did it correctly).

To be perfectly honest, I'm not even sure if the firmware (e.g. PC BIOS) is actually meant to configure all PCI devices. It will need to configure devices it uses during boot (e.g. the hard disk controller, the first video card, etc) but for things like sound cards, the second video card, network cards, etc it could just disable them all (and leave the OS to set them up properly).

On top of that, most devices that the BIOS does use during boot are likely to be configured in a legacy mode for compatibility, and not configured how the OS wants them.

Finally (at the extremes of "complexity") there's hot-plug PCI devices to worry about, where it's completely impossible for the firmware to configure them during boot (where the OS has no choice but to configure them, and find areas for any memory mapped IO).

Now, don't get me wrong here. It is a very good idea to have a complete memory map (including everything the firmware can tell you) because it helps to prepare you for things you might implement in the future; but it's probably not a good idea to start messing about with PCI device configuration until you've gained some experience writing device drivers, etc. Basically, assuming the firmware configured PCI devices correctly will be "good enough" for now (but get a complete memory map anyway). ;)


Cheers,

Brendan

Re: Unusable areas in the memory map.

Posted: Sun Mar 25, 2012 7:04 am
by Rudster816
For dealing with memory below 1MB, this page is very useful

http://wiki.osdev.org/Memory_Map_(x86)

The simplest way of dealing with memory below 1MB is to treat it all as read only once you're done with all real mode stuff. The most memory you could lose is 640KB, which in modern PC's is insignificant, and IMO worth the added simplicity.

Storing both the region length\end will make a lot of code easier to read. You wont have to constantly do (region_start + region_length) or (region_end - region_start). Just be sure to update both values if anything changes for any reason ;).

I wouldn't get caught up too much in the grand scheme of things right now. There really is only so much planning you can do, because a lot of what you need to do depends on what you haven't done. You could spend weeks working on a super good\production quality memory manager (or other component), but this would kind of corner yourself as far as changing your design (as well as being incredibly boring). I'm personally going about it in a completely different manner. For example I currently have a very simple kmalloc, which I can use in other, perhaps more interesting, parts of my kernel, knowing I can always return and improve upon it. So long as you follow good abstraction\ encapsulation techniques, making major changes to one area of your kernel should only lead to trivial (and probably tedious) changes to other areas.

You'll blind yourself trying to look at the big picture. Just pick something you want to work towards, and implement everything you need to be able to do that, and than write whatever your goal is.

Re: Unusable areas in the memory map.

Posted: Sun Mar 25, 2012 10:33 am
by brain
According to the pci specification (2.1 iirc) it does state that the bios should set sane values for all io ports, mmio and interrupts for all pci devices and then leave them in a disabled state. if a bios did not do this it would be broken and non-conforming...

Re: Unusable areas in the memory map.

Posted: Mon Mar 26, 2012 7:57 am
by sandras
gerryg400 wrote:I'd just like to point out that the ACPI tables are normally above 1MB and some of the ACPI memory is reclaimable after the information is read.
Yes, that's a good argument for having the full memory map, not just for usable areas.
gerryg400 wrote:Also it's actually not very difficult to implement a memory defragmenter that can find enough pages to satisfy a request for DMA memory if there is no contiguous memory available. It's a very simple matter to replace the physical pages in a process with other physical pages.
That will go into my considerations. : )
Brendan wrote:
Sandras wrote:Then, AFAIK there are devices that can be mapped by kernel to areas it chooses. Correct me if I'm wrong, but PCI would be one case of that. But I thought, that the kernel could allocate an area of known usable ram for that.
No. In this case the kernel would need to allocate an area for the memory mapped device that isn't used by *anything*. This would be an area that is not usable RAM, not used by firmware/ROM, not used by any PCI device, not used by any other device (e.g. APIC), and not reserved (e.g. for "hot-plug RAM" or something).
I see, it's the non-usable non-non-usable space that I did not take into account. The space where there is nothing mapped. It's free, but it's not free ram, it's free memory address space. I think I got it.
Brendan wrote:That's where the problem is - if you only know where usable RAM is (and don't know where anything else is) then you can't find an area that is suitable for the memory mapped device.
Yes, indeed, now I do see the problem.
Brendan wrote:It could be much simpler than that though - you could assume that the firmware correctly configured all PCI devices and that the OS will never need to allocate space for a memory mapped device. However, I would expect that the firmware in lots of different computers screw it up in a lot of different ways (and that nobody has actually noticed because most/all mainstream OSs set up PCI devices themselves instead of assuming the firmware did it correctly).

To be perfectly honest, I'm not even sure if the firmware (e.g. PC BIOS) is actually meant to configure all PCI devices. It will need to configure devices it uses during boot (e.g. the hard disk controller, the first video card, etc) but for things like sound cards, the second video card, network cards, etc it could just disable them all (and leave the OS to set them up properly).

On top of that, most devices that the BIOS does use during boot are likely to be configured in a legacy mode for compatibility, and not configured how the OS wants them.

Finally (at the extremes of "complexity") there's hot-plug PCI devices to worry about, where it's completely impossible for the firmware to configure them during boot (where the OS has no choice but to configure them, and find areas for any memory mapped IO).
Valid argument's. For me to change my mind having in mind hot-plug is enough.
Brendan wrote:Now, don't get me wrong here. It is a very good idea to have a complete memory map (including everything the firmware can tell you) because it helps to prepare you for things you might implement in the future; but it's probably not a good idea to start messing about with PCI device configuration until you've gained some experience writing device drivers, etc. Basically, assuming the firmware configured PCI devices correctly will be "good enough" for now (but get a complete memory map anyway). ;)
Don't get me wrong - I'm not trying to mess with PCI now. Really, I just read up on it so I know what that may require. Actually, I'm not even interested in PCI now.
brain wrote:if a bios did not do this it would be broken and non-conforming...
I would not be surprised, if things are broken and non-conforming.