OSDev.org

The Place to Start for Operating System Developers
It is currently Fri Mar 29, 2024 3:21 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 14 posts ] 
Author Message
 Post subject: Initializing Page Frames
PostPosted: Thu Aug 31, 2017 2:55 am 
Offline

Joined: Sat Aug 05, 2017 12:23 pm
Posts: 3
I've been working on trying to set up my physical memory manager and I'm having some questions about it.

First, I have a memory map from GRUB. Right now what I'm doing is creating a struct with a start/end address for each block of free memory, and only dealing with those chunks of memory (not using reserved ones). This array of structs tells my PMM everything about the memory it has available to work with.

My most pressing question, though, is how to deal with my data structures. Whether I'm using a bitmap or a stack, I need some memory place to put that in. My question is, where do I put my stack/bitmap? I know where my kernel's end address is, but should I manually reserve physical memory to store the stack/bitmap, and then use everything after the stack/bitmap's end address for the allocating pages? Or should the stack/bitmap be part of a page frame too? How would I put it in a page frame if I can only allocated page frames after the stack/bitmap has been initialized?

My second question has to do with the page frames themselves. When I return a page frame, I am just returning a memory address, correct? The reason I ask is because I see many people talk about having a pointer to the next frame in each frame, which means that it would be a struct or what?


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Thu Aug 31, 2017 3:05 am 
Offline
Member
Member

Joined: Wed Sep 19, 2012 3:43 am
Posts: 91
Location: The Netherlands
Quote:
How would I put it in a page frame if I can only allocated page frames after the stack/bitmap has been initialized?

What I do is get a pointer to the kernel's end (actually, the top of the kernel's stack) and put my PMM's bitmap right after that address.
When the bitmap has been initialized I mark everything from kernel start to kernel stack top + the size of the bitmap as used.

Quote:
When I return a page frame, I am just returning a memory address, correct?

If you mean "return a pointer to a memory address" then yes.

Quote:
which means that it would be a struct or what?

A page frame is basically a 4Kib piece of aligned address space, what you use to represent it is up to you.
I search through the bitmap for a large enough "hole" but you could also use a linked list, stack, array of structs or whatever you like best.


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Thu Aug 31, 2017 4:24 am 
Offline
Member
Member

Joined: Thu Aug 13, 2015 4:57 pm
Posts: 384
horizon wrote:
My most pressing question, though, is how to deal with my data structures. Whether I'm using a bitmap or a stack, I need some memory place to put that in. My question is, where do I put my stack/bitmap? I know where my kernel's end address is, but should I manually reserve physical memory to store the stack/bitmap, and then use everything after the stack/bitmap's end address for the allocating pages? Or should the stack/bitmap be part of a page frame too? How would I put it in a page frame if I can only allocated page frames after the stack/bitmap has been initialized?

For a bitmap you could allocate the bitmap right after the kernel ends, but since that's just normal memory as any other memory, I wouldn't bother trying to put it at the kernel end. Instead, calculate how much memory the bitmap itself requires then find a contiguous memory range that is large enough.

horizon wrote:
My second question has to do with the page frames themselves. When I return a page frame, I am just returning a memory address, correct? The reason I ask is because I see many people talk about having a pointer to the next frame in each frame, which means that it would be a struct or what?

What you return is up to you, this is your OS. Generally speaking, yes, "everyone" returns the memory address.

The pointer to the next _free_ frame is likely related to stack implementation, and because the stack utilizes the _free_ page frames it ends up effectively using zero memory during load. So the pointer inside the page frame is not something that is returned to the process that requested memory, and indeed you should scrub it off (clear to zero).

Regardless of the memory manager algorithm (stack, bitmap, etc) you should clear the page frame before the VMM makes it available to some process. You can either put the pages into a "dirty pool" when they are released and then at idle time scrub them (clear to zero) or you can do it when a page is being allocated.


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Thu Aug 31, 2017 4:26 am 
Offline
Member
Member

Joined: Thu Aug 13, 2015 4:57 pm
Posts: 384
FusT wrote:
What I do is get a pointer to the kernel's end (actually, the top of the kernel's stack) and put my PMM's bitmap right after that address.
When the bitmap has been initialized I mark everything from kernel start to kernel stack top + the size of the bitmap as used.

Where is your kernel loaded in physical memory? For instance, if your kernel is loaded in low memory (under 1MiB), then how much contiguous space is there for a bitmap? Or do you somehow handle splitting the bitmap into multiple pieces if there isn't a large enough contiguous space for the bitmap?


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Thu Aug 31, 2017 4:29 am 
Offline
Member
Member
User avatar

Joined: Fri Aug 07, 2015 6:13 am
Posts: 1134
FusT wrote:
Quote:
How would I put it in a page frame if I can only allocated page frames after the stack/bitmap has been initialized?

What I do is get a pointer to the kernel's end (actually, the top of the kernel's stack) and put my PMM's bitmap right after that address.
When the bitmap has been initialized I mark everything from kernel start to kernel stack top + the size of the bitmap as used.

Quote:
When I return a page frame, I am just returning a memory address, correct?

If you mean "return a pointer to a memory address" then yes.

Quote:
which means that it would be a struct or what?

A page frame is basically a 4Kib piece of aligned address space, what you use to represent it is up to you.
I search through the bitmap for a large enough "hole" but you could also use a linked list, stack, array of structs or whatever you like best.


Please be cautious and add 512 bytes to your kernel end. I've seen people (including me) having problems with kernel_end because there was data right after it, if you want to avoid overwriting your kernel data/code do this first.
You can put your bitmap right after kernel_end + 512 bytes of padding, make sure to map your entire bitmap or else you will see triple faults.
Make sure every bit that your bitmap physically uses is reserved inside your PMM, you do not want to overwrite your bitmap.
As suggested, you should mark everything from kernel_start to kernel_end + 512 bytes of padding + "size_of"(bitmap) as used.
4 KB aligned = addresses that are 4096 bytes apart, such as 0x1000 0x2000 0x3000 0x4000 and your will recognize page aligned address by the last 3 digits being zero.
It can but doesn't need to be a pointer, it can be just a number that could later become anything. You can just return uint32_ts and uint64_ts respectively. (easier to cast in C++, that is how I do it)

I am really curious about your struct + array technique. How do you handle different area counts? One computer can have 3 free chunks and the other can have 333 free chunks. What about that? Dynamic allocation I guess, no?

I would suggest you waiting for @LtG to reply. He has some some experience and knowledge about stack based implementations, so you can ask him more about that. There was an ongoing memory discussion recently, feel free to check it out, it can give you some ideas.

_________________
OS: Basic OS
About: 32 Bit Monolithic Kernel Written in C++ and Assembly, Custom FAT 32 Bootloader


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Thu Aug 31, 2017 7:48 am 
Offline
Member
Member

Joined: Wed Sep 19, 2012 3:43 am
Posts: 91
Location: The Netherlands
LtG wrote:
FusT wrote:
What I do is get a pointer to the kernel's end (actually, the top of the kernel's stack) and put my PMM's bitmap right after that address.
When the bitmap has been initialized I mark everything from kernel start to kernel stack top + the size of the bitmap as used.

Where is your kernel loaded in physical memory? For instance, if your kernel is loaded in low memory (under 1MiB), then how much contiguous space is there for a bitmap? Or do you somehow handle splitting the bitmap into multiple pieces if there isn't a large enough contiguous space for the bitmap?

My kernel is currently loaded at the 1MB mark but i'm planning on making it higher-half in the near future.
Bitmaps do use a lot of space but it's not that much when you think about it: 1 bit per 4Kib of memory, 32 bits per byte. So for 4Gib of memory that equates to 32Kib for the PMM bitmap.

Octacone wrote:
Please be cautious and add 512 bytes to your kernel end.

I'm curious (never tried it), Does this applies even when you add a symbol at the very end of the kernel image like so?:

Code:
ENTRY (start)

SECTIONS
{
    . = 0x00100000;

    .__mbHeader : {
        *(.__mbHeader)
    }

    .text ALIGN (0x1000) :
    {
        *(.text)
    }

    .rodata ALIGN (0x1000) :
    {
        *(.rodata*)
    }

    .data ALIGN (0x1000) :
    {
        *(.data)
    }

    .bss ALIGN (0x1000) :
    {
        sbss = .;
        *(COMMON)
        *(.bss)
   *(.bootstrap_stack)
        ebss = .;
    }

    end = .; _end = .; __end = .;
}


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Thu Aug 31, 2017 9:30 am 
Offline
Member
Member

Joined: Thu Aug 13, 2015 4:57 pm
Posts: 384
Octacone wrote:
Please be cautious and add 512 bytes to your kernel end. I've seen people (including me) having problems with kernel_end because there was data right after it, if you want to avoid overwriting your kernel data/code do this first.

I would actually advise against that. There's a few things that are critical, the OS/kernel and for example a compiler, because they are critical I would advise you always dot your i's and cross your t's. In other words, find out why your kernel_end is _wrong_, and fix it.

I have nothing against padding in general, I just think you should fix the underlying issue, and you should know _exactly_ where your kernel ends. Adding 512B and hoping for the best isn't a good strategy in critical systems. And usually you'll end up learning something along the way.

Of course for some osdev is just a "tiny" hobby, where they don't care if there's underlying issues and they just do what's easiest, and that's ok too, so long as you know that that is what you're doing. I prefer to ensure correctness when I can.

Octacone wrote:
I am really curious about your struct + array technique. How do you handle different area counts? One computer can have 3 free chunks and the other can have 333 free chunks. What about that? Dynamic allocation I guess, no?

Not sure who this was addressed to.. Didn't really understand the question.


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Thu Aug 31, 2017 9:38 am 
Offline
Member
Member

Joined: Thu Aug 13, 2015 4:57 pm
Posts: 384
FusT wrote:
LtG wrote:
Where is your kernel loaded in physical memory? For instance, if your kernel is loaded in low memory (under 1MiB), then how much contiguous space is there for a bitmap? Or do you somehow handle splitting the bitmap into multiple pieces if there isn't a large enough contiguous space for the bitmap?

My kernel is currently loaded at the 1MB mark but i'm planning on making it higher-half in the near future.
Bitmaps do use a lot of space but it's not that much when you think about it: 1 bit per 4Kib of memory, 32 bits per byte. So for 4Gib of memory that equates to 32Kib for the PMM bitmap.

Umm, there's _8_ bits per byte, not 32.. Interestingly enough, I think Octacone did the same mistake a while back. So I think the correct size for your bitmap 128KiB for 4GiB of RAM, but these days 8GiB seems to be the standard and I wouldn't be surprised if 16GiB became the standard soon-ish.

Personally I would consider the lowest parts of the memory special (for example below 16MiB) and also possibly the first 4GiB (peripheral devices may only be able to access 32-bit addresses). I'm talking physical here, not virtual.

There may be some advantages keeping the kernel in the first 4GiB if you plan to support 32-bit execution with 64-bit, it might make things easier.

Note, higher half doesn't mean you have to put your kernel in the higher half physically, just virtually. My main point with the size of the bitmap was that you'll want to make sure there's enough room, and for example under 1MiB it's reasonable to expect that there isn't, but really you'll need to consult your BIOS provided memory map to find a suitable place, this adds some complexity.


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Thu Aug 31, 2017 10:45 am 
Offline
Member
Member
User avatar

Joined: Fri Aug 07, 2015 6:13 am
Posts: 1134
FusT wrote:
Octacone wrote:
Please be cautious and add 512 bytes to your kernel end.

I'm curious (never tried it), Does this applies even when you add a symbol at the very end of the kernel image like so?:

Code:
--snip--


Yes indeed. That (at the very end) was the exact way I encountered.

LtG wrote:
I would actually advise against that. There's a few things that are critical, the OS/kernel and for example a compiler, because they are critical I would advise you always dot your i's and cross your t's. In other words, find out why your kernel_end is _wrong_, and fix it.

I have nothing against padding in general, I just think you should fix the underlying issue, and you should know _exactly_ where your kernel ends. Adding 512B and hoping for the best isn't a good strategy in critical systems. And usually you'll end up learning something along the way.

Of course for some osdev is just a "tiny" hobby, where they don't care if there's underlying issues and they just do what's easiest, and that's ok too, so long as you know that that is what you're doing. I prefer to ensure correctness when I can.

Not sure who this was addressed to.. Didn't really understand the question.


There is not way to fix it. It cannot be fixed. One guy suggested adding some padding and the other one suggested page aligning the address (effectively padding it). There was a topic a way way way back about that problem.
@horizon was supposed to answer that question.

Actually I am experiencing some problems and not being able to see replies as the naturally go in, for example I couldn't see your reply, etc... That is why you thought I quoted you.

uint32_t has 32 bits in it. Where is the problem? I think there is some miscommunication going on.
Look like @FusT and I are not wrong. We just use uint32_t. :wink: That solves the problem!

_________________
OS: Basic OS
About: 32 Bit Monolithic Kernel Written in C++ and Assembly, Custom FAT 32 Bootloader


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Thu Aug 31, 2017 11:17 am 
Offline
Member
Member

Joined: Mon Mar 25, 2013 7:01 pm
Posts: 5103
horizon wrote:
How would I put it in a page frame if I can only allocated page frames after the stack/bitmap has been initialized?

When the stack is empty, like when you're first initializing your kernel, it doesn't take up any space, so it doesn't need any page frames. Adding free pages to the stack works the same way as freeing previously used pages, so you avoid the circular dependency of needing the physical memory manager to be ready before you can initialize it. When a page is freed and there's no room in the stack to store it, use that page to extend the stack.


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Thu Aug 31, 2017 11:38 am 
Offline
Member
Member

Joined: Thu Aug 13, 2015 4:57 pm
Posts: 384
Octacone wrote:
There is not way to fix it. It cannot be fixed. One guy suggested adding some padding and the other one suggested page aligning the address (effectively padding it). There was a topic a way way way back about that problem.

In computing in general there are very few (if any) problems that can't be fixed, it's usually a question of how hard it is to fix something properly. If you have a link to the topic I would appreciate it.

Octacone wrote:
uint32_t has 32 bits in it. Where is the problem? I think there is some miscommunication going on.
Look like @FusT and I are not wrong. We just use uint32_t. :wink: That solves the problem!

But 32 bits is _not_ a _byte_, it is in fact 4 bytes, so the number was 4 times smaller than it should have been.

32k uint32_t's = 32k*4B = 128 kB.


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Fri Sep 01, 2017 1:22 am 
Offline
Member
Member

Joined: Wed Sep 19, 2012 3:43 am
Posts: 91
Location: The Netherlands
LtG wrote:
But 32 bits is _not_ a _byte_, it is in fact 4 bytes, so the number was 4 times smaller than it should have been.

32k uint32_t's = 32k*4B = 128 kB.

You're correct, I got my terminology mixed up a bit (pun intended). Sorry about the confusion.

Octacone wrote:
Yes indeed. That (at the very end) was the exact way I encountered.

Interesting, I've never encountered this issue. I'm tempted to do some investigation on the subject though.


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Fri Sep 01, 2017 3:43 am 
Offline
Member
Member
User avatar

Joined: Fri Aug 07, 2015 6:13 am
Posts: 1134
LtG wrote:
Octacone wrote:
uint32_t has 32 bits in it. Where is the problem? I think there is some miscommunication going on.
Look like @FusT and I are not wrong. We just use uint32_t. :winxk: That solves the problem!

But 32 bits is _not_ a _byte_, it is in fact 4 bytes, so the number was 4 times smaller than it should have been.

32k uint32_t's = 32k*4B = 128 kB.


Oh sorry!
This entire time I couldn't figure out what were you saying. That make sense. Actually my code was correct just not the way I was thinking of it.
I think I've found a way to think about it: size_of_bitmap_in_bytes = (all_blocks * bytes_in_your_type) / bits_in_your_type;

FusT wrote:
Octacone wrote:
Yes indeed. That (at the very end) was the exact way I encountered.

Interesting, I've never encountered this issue. I'm tempted to do some investigation on the subject though.


That would be great. Because nobody knows the cause of this sort of buggy state.
Simply put your kernel_end symbol at the end of your linker script. See its address not its value, check the address in Bochs and see if there is any data after it. Make sure you don't use modules and stuff, GRUB can put them anywhere in the memory and I don't think they would be counted for. I've personally never used GRUB modules and never will probably, so that can be ruled out as a cause.
Maybe something GCC related? Probably not, but still.

_________________
OS: Basic OS
About: 32 Bit Monolithic Kernel Written in C++ and Assembly, Custom FAT 32 Bootloader


Top
 Profile  
 
 Post subject: Re: Initializing Page Frames
PostPosted: Fri Sep 01, 2017 8:15 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,

FusT wrote:
What I do is get a pointer to the kernel's end (actually, the top of the kernel's stack) and put my PMM's bitmap right after that address.
When the bitmap has been initialized I mark everything from kernel start to kernel stack top + the size of the bitmap as used.


There is no guarantee that there's RAM at the end of the kernel, and even if there is there is no guarantee that it's usable. For a common example, typically GRUB puts any "modules" immediately after the kernel.

For multiboot; the only RAM that can be "assumed safe to use" is space in your own .bss. For all other RAM you have to check the memory map and do multiple other checks (if the RAM is used by kernel, if the RAM is used by any modules, if the RAM is used by multiboot information).

What I'd do is have a (possibly temporary) small fixed size bitmap in your ".bss" (e.g. 512 bytes is enough for 4096 pages/the first 16 MiB of the physical address space); initialise that (using memory map and all the other checks); and then use it to allocate any physical pages needed to initialise the final physical memory management.

I'd also reserve space in the .bss for kernel stack; plus any page tables, page directories, etc; plus space to copy information you want from the multiboot information structure (because it's messy - there's no guarantee that its information isn't scattered everywhere so it's easier to get rid of it and avoid the need to worry about it when initialising a physical memory manager).


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 14 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: Bing [Bot], DotBot [Bot] and 184 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group