Physical memory manager, multiboot and paging

[Alpha]

Hello everyone,

I'm building a x86 32bit micro-kernel and therefore, I have to implement a physical memory manager. However i'm confused about how to do this.
My kernel currently works as follows:

1. the kernel is loaded by grub together with a memory map.
2. Basic paging is enabled, mapping the kernel at 3GB and identity mapping the first 4MB
3. a very basic display driver is initialized

So the next thing to do is to set-up the physical memory manager. I am planning to build a bitmap that is proportional to the size of the physical memory. I will use the bitmap to mark each used or reserved page frame.
In order to know the reserved area's and the total memory, i have to read the multiboot data. however this confuses me.

First of all, I have to find a place to store my bitmap without overwriting (parts of) the multiboot data. I am planning to use boot modules in the future, so i have to be extra careful not to overwrite them. since those modules could be loaded anywhere, and not necessarily next to each other. But i am not sure about the best way to do this.

Second, since i have a higher-half kernel and paging enabled, i must ensure that the multiboot data is mapped-in correctly.

So my question is: What is a good way to do this? Could somebody maybe give me an example or something?

Thanks a lot!

[thomtl]

The simplest way is probably to place it directly after your kernel, the end address of your kernel can be gotten using linker script values.

[dseller]

First of all, I have to find a place to store my bitmap without overwriting (parts of) the multiboot data. I am planning to use boot modules in the future, so i have to be extra careful not to overwrite them. since those modules could be loaded anywhere, and not necessarily next to each other. But i am not sure about the best way to do this.

Second, since i have a higher-half kernel and paging enabled, i must ensure that the multiboot data is mapped-in correctly.

The multiboot info structure tells you where it loaded the modules, and what its lengths are. Easiest would be to take the end address of the module that was loaded farthest in memory, and start from there. At least, that's how I do it.

P.S. Leuk om nog een Nederlander te zien

[thomtl]

Er is nog een Nederlander hoor.

[JAAman]

others have already answered your question (its for you to decide if those answers are good enough...) so I will only ask 1 question, and give 1 warning:


1) warning:
don't forget that memory needs not be contiguous -- in fact it is quite common for there to be many holes in memory (and not just at known and fixed locations), so for a bitmap that extends with the size of installed physical memory, you will need some method of determining the physical address of the frames in your bitmap

2) question:
are you sure you want to use a bitmap for this rather than a stack?
bitmaps are slower
bitmaps take more memory
bitmaps are harder to setup
bitmaps are more complicated (harder to implement)

if your sure this is the method you want to take, that is your decision, I just want to be sure you properly understand the decision

[Octacone]

2) question:
are you sure you want to use a bitmap for this rather than a stack?
bitmaps are slower
bitmaps take more memory
bitmaps are harder to setup
bitmaps are more complicated (harder to implement)

there are ways to speed them up
doesn't really matter on modern systems
they are quite easy to set up
they are definitely one of the easiest structures to work with

I agree that using the stack would be faster, but what about DMA? You'll need contiguous physical pages for that purpose, which a stack cannot provide.

To OP:
As others suggested,
You can use your linker script to tell you where the kernel end is and then place all of your structures after that point and map them accordingly.
When it comes to accessing your multiboot data there shouldn't be any problems, if you mapped everything correctly.
I personally prefer bitmaps over stacks, but that is just my pp. I've been using them for my PMM and there weren't any difficulties so far.

[Alpha]

Thanks for all the replies.

I have chosen the bitmap because of its simplicity. However now i think of it, it would indeed have a lot of overhead when there are a lot of gaps. However, worst case it would consume 128 kB when it has to map the full address space.
When i choose for a stack or linked-list based manager. how do i choose the space it requires? Because it will grow when the memory becomes segmentated, resulting in small area's of free space.

You can use your linker script to tell you where the kernel end is and then place all of your structures after that point and map them accordingly.

You mean reserve some space in the .bss section? such that grub would reserve this area and won't place any stuff there?

[FusT]

You mean reserve some space in the .bss section? such that grub would reserve this area and won't place any stuff there?

Not quite. You can use the linker script to create a "label" at the end of the kernel which you later reference in your C code.
Put something like the "end =" in below code at the very end of your linker script:

Code: Select all

ENTRY(start)

SECTIONS 
{
    ........
    end = .; _end = .; __end = .;
}

And then you can reference it from C like so (there are probably better ways to do this):

Code: Select all

extern uint32_t end; // Defined in linker script
uintptr_t kernel_end = (uintptr_t) &end;

Er is nog een Nederlander hoor.

Nog wel meer dan 1 zelfs

[JAAman]

Thanks for all the replies.

I have chosen the bitmap because of its simplicity. However now i think of it, it would indeed have a lot of overhead when there are a lot of gaps. However, worst case it would consume 128 kB when it has to map the full address space.

36-bit physical address space has been standard for almost 25 years now, even on stricktly 32-bit PMode systems

When i choose for a stack or linked-list based manager. how do i choose the space it requires? Because it will grow when the memory becomes segmentated, resulting in small area's of free space.

this is not how a stack system works, a stack keeps a list of all frames (not a list of free regions)

the stack-based system will never take more than 8 bytes of memory (4bytes if you only support 32-bit physical addresses) -- those 8 bytes of memory should be a static variable in your code

for your simplest setup, after processing your memory map (to remove duplicate, overlapping, or incomplete frames and non-available types) you would do something like this: (note: pseudo code, do not attempt to actually use -- this code doesn't account for large stack requiring multiple frames)

Code: Select all

for (auto frame: memMap)
{
    if(IsInUse(frame)) continue;

    if(stackPointer == nullptr)
    {
          stackPointer == frame;
    }
    *stackPointer = frame;
    stackPointer++
}

this will allow you to build your initial stack -- once paging is enabled, you should map all the frames holding this stack consecutively in a reserved region of your address space, and modify your stackPointer to point to the paging-enabled address

then your allocate function looks like this:

Code: Select all

if(stackPointer < STACK_BASE)     //this indicates soft OOM
{
    if(ZeroFrames())
    {
        return AllocateFrame;
    }
    else
    {
        goto BSOD;           // hard OOM: more sophisticated systems will do other things to free memory
    }
}
stackPointer--;
if (stackPointer & FRAME_SIZE-1 == FRAME_SIZE-1)
{
    UnmapPage(stackPointer+1);
}
return *stackPointer;

and your de-allocate code:

Code: Select all

if (stackPointer & FRAME_SIZE-1 == FRAME_SIZE-1)
{
    MapPage (stackPointer+1, frame)
}
*stackPointer = frame
stackPointer++;

[Alpha]

the stack-based system will never take more than 8 bytes of memory (4bytes if you only support 32-bit physical addresses) -- those 8 bytes of memory should be a static variable in your code

Ah right, i am leaning things here. so if i am correct, the stack maintains a list of free pageframes, and the stack itself is stored inside some of them. When more pages are being allocated, the stack shrinks and therefore releases some of its own pageframes.
I assume you place the stack just after your kernel in the virtual address space?

I think i should consider this stack-based approach for now, since it seems to make thing much easier for now.
However, when i start using DMA (which i guess won't be soon) i will need to find other methods to reserve a continuous areas of physical memory.