I'm trying to write a physical memory manager, but my brain throws an exception everytime i think about the design.
If i'm writing a memory allocator, before i have a memory allocator, where shall i keep my data structure?
i mean, suppose i have a stack that keeps pages in it. where shall i keep it? stack is dynamic; also its size isn't constant, it will be changed according to the RAM's size / available memory..
I have my kernel's start and end addresses, and i thought about allocating a fixed size after my kernel end address, yet, again..
A paradox in my physical memory manager.
-
glauxosdever
- Member
- Posts: 501
- Joined: Wed Jun 17, 2015 9:40 am
- Libera.chat IRC: glauxosdever
- Location: Athens, Greece
Re: A paradox in my physical memory manager.
Hi,
This is a common question, but it has not a well-defined answer.
Basically, you have to obtain the memory map, so you know at which ranges there is usable memory. From your previous post I see that you use GRUB as your bootloader, so it should not be hard to get the memory map. Check the multiboot/multiboot2 specification (depending on which you are using to boot your kernel) for more information.
Then, you have to enumerate (write down on some piece of paper, or in some text file outside of the source tree) what structures you need. After this, write code to get the start and end addresses of these structures. Whatever pages are outside of these addresses and are contained in usable memory, are free for further use.
Now to your real question. Where to store the data structure describing free physical memory? You can have a linked list of free pages. There can be two variables in the kernel, containing the physical address of the first free page, and the physical address of the last free page. Then, at the start of the first free page, you can have the physical address of the second free page. At the start of the second free page, you can have the physical address of the third free page, etc, until you get to the last free page, which doesn't point anywhere. In this case, I'd suggest marking the top of this last page with 0xFFFFFFFF, which is indeed not a valid page-aligned address.
To allocate a physical page, (supposing you are going to use the above way), you can get the physical address of the first free page (the address is stored in a variable, as I already described). Then get the address of the second free page (stored at the start of the first free page), and put it in the variable containing the address of the first free page. Make sure you can handle the case when no more free pages are left.
To free a physical page, (supposing you are going to use the above way), you can write the address of the currently first free page at the start of the page you are going to free. Then put the address of the page you are going to free into the variable describing the first free page.
Hope this helps.
Regards,
glauxosdever
This is a common question, but it has not a well-defined answer.
Basically, you have to obtain the memory map, so you know at which ranges there is usable memory. From your previous post I see that you use GRUB as your bootloader, so it should not be hard to get the memory map. Check the multiboot/multiboot2 specification (depending on which you are using to boot your kernel) for more information.
Then, you have to enumerate (write down on some piece of paper, or in some text file outside of the source tree) what structures you need. After this, write code to get the start and end addresses of these structures. Whatever pages are outside of these addresses and are contained in usable memory, are free for further use.
Now to your real question. Where to store the data structure describing free physical memory? You can have a linked list of free pages. There can be two variables in the kernel, containing the physical address of the first free page, and the physical address of the last free page. Then, at the start of the first free page, you can have the physical address of the second free page. At the start of the second free page, you can have the physical address of the third free page, etc, until you get to the last free page, which doesn't point anywhere. In this case, I'd suggest marking the top of this last page with 0xFFFFFFFF, which is indeed not a valid page-aligned address.
To allocate a physical page, (supposing you are going to use the above way), you can get the physical address of the first free page (the address is stored in a variable, as I already described). Then get the address of the second free page (stored at the start of the first free page), and put it in the variable containing the address of the first free page. Make sure you can handle the case when no more free pages are left.
To free a physical page, (supposing you are going to use the above way), you can write the address of the currently first free page at the start of the page you are going to free. Then put the address of the page you are going to free into the variable describing the first free page.
Hope this helps.
Regards,
glauxosdever
Re: A paradox in my physical memory manager.
Are you using multi boot ?
If yes, then you already have an allocator:
you have an array of memory zones.
You can alter this array to allocate a new memory allocator, then use the altered array to feed your physical memory free areas.
If yes, then you already have an allocator:
you have an array of memory zones.
You can alter this array to allocate a new memory allocator, then use the altered array to feed your physical memory free areas.
-
Octocontrabass
- Member
- Posts: 5587
- Joined: Mon Mar 25, 2013 7:01 pm
Re: A paradox in my physical memory manager.
Storing data in free pages is a pretty bad idea. In order to access that free page, you have to map it, and then once you're done accessing it, you have to unmap it again. That's a humongous waste of time.glauxosdever wrote:You can have a linked list of free pages.
There are two ways you can handle initializing your physical memory manager; which one works best depends on how your physical memory manager keeps track of free pages.
The first option is to set up the data structures for paging before you enable paging. For example, if you're using a bitmap, you would pick some pages to reserve for your bitmap, and prevent those pages from being marked free when you initialize the bitmap. (This is what Boris suggested.)
The second option is to initialize your physical memory manager in a state where it's storing no free pages at all, and let it set up its data structures as you "free" all of the available memory. For example, if you're using a stack, whenever the stack is too small to hold a page being freed, you could map that page to increase the size of the stack instead of attempting to put it on the stack. If you want to be clever, you can also free empty pages as the stack gets smaller.
Re: A paradox in my physical memory manager.
I didn't quite understand the second option(stack).Octocontrabass wrote:Storing data in free pages is a pretty bad idea. In order to access that free page, you have to map it, and then once you're done accessing it, you have to unmap it again. That's a humongous waste of time.glauxosdever wrote:You can have a linked list of free pages.
There are two ways you can handle initializing your physical memory manager; which one works best depends on how your physical memory manager keeps track of free pages.
The first option is to set up the data structures for paging before you enable paging. For example, if you're using a bitmap, you would pick some pages to reserve for your bitmap, and prevent those pages from being marked free when you initialize the bitmap. (This is what Boris suggested.)
The second option is to initialize your physical memory manager in a state where it's storing no free pages at all, and let it set up its data structures as you "free" all of the available memory. For example, if you're using a stack, whenever the stack is too small to hold a page being freed, you could map that page to increase the size of the stack instead of attempting to put it on the stack. If you want to be clever, you can also free empty pages as the stack gets smaller.
The first option is clear, but what i don't understand is how do i determine the bitmap size.. i don't know the free RAM size in compile time.
Also, keeping a linked list within the free pages is that poor in performence?
-
onlyonemac
- Member
- Posts: 1146
- Joined: Sat Mar 01, 2014 2:59 pm
Re: A paradox in my physical memory manager.
I use a bitmap allocator (probably not the most efficient), so after I've read the memory map I find and reserve an area to store my bitmap, store the address of the bitmap in a global variable in my memory manager module, and mark the memory occupied by the bitmap as in use. If/when I implement paging, I'll keep the page(s) containing the bitmap in real memory at all times.
When you start writing an OS you do the minimum possible to get the x86 processor in a usable state, then you try to get as far away from it as possible.
Syntax checkup:
Wrong: OS's, IRQ's, zero'ing
Right: OSes, IRQs, zeroing
Syntax checkup:
Wrong: OS's, IRQ's, zero'ing
Right: OSes, IRQs, zeroing
Re: A paradox in my physical memory manager.
The Free Stack is probably the best approach since allocation and freeing are O(1). This is the method we use, but it cannot handle contiguous physical memory. With paging, this isn't a problem since you can just grab any physical block and map them to contiguous addresses. You do have to be a little careful with memory < 16MB though since ISA DMA and some ancient hardware do require contiguous physical memory. This can be resolved by using a separate allocator (e.g. Bitmap, Buddy, etc) for < 16MB.
OS Development Series | Wiki | os | ncc
char c[2]={"\x90\xC3"};int main(){void(*f)()=(void(__cdecl*)(void))(void*)&c;f();}
char c[2]={"\x90\xC3"};int main(){void(*f)()=(void(__cdecl*)(void))(void*)&c;f();}
-
Combuster
- Member
- Posts: 9301
- Joined: Wed Oct 18, 2006 3:45 am
- Libera.chat IRC: [com]buster
- Location: On the balcony, where I can actually keep 1½m distance
- Contact:
Re: A paradox in my physical memory manager.
You can calculate the exact length of the memory stack/bitmap without allocations: you just go through the memory map you got from GRUB, count the number of pages of RAM in there. Then you multiply/divide it to get the amount of space you need. Now you know how much you will have to allocate.
Next you get the location and size of the kernel - those values can be calculated for you at compile time. Go through your memory map again and find a piece of RAM that's large enough to contain the size needed for your memory management, and does not overlap with your kernel (and anything else you want to preserve). The method you can use here is to pick a start location, and check if you have any overlap. If you do, move the start until after the object you need to avoid, and retry. If the remaining area became too small, you move to the next entry of your memory map. Eventually you'll find a place or your computer doesn't have enough RAM for your world domination plans. At any rate, you now know where your structure is going to be.
Now that you know where it is, you simply fill it out. For each piece of RAM that could go in there, you check if it overlaps with your kernel or your designated structure location, then drop it in as either free or occupied - you know all the locations now. After that, your structure is built, filled with the correct free/occupied settings, and you can finally call the functions of your memory allocator without having to worry about paradoxes.
All it takes is two global variables and a small number of locals which you can leave on the stack.
Next you get the location and size of the kernel - those values can be calculated for you at compile time. Go through your memory map again and find a piece of RAM that's large enough to contain the size needed for your memory management, and does not overlap with your kernel (and anything else you want to preserve). The method you can use here is to pick a start location, and check if you have any overlap. If you do, move the start until after the object you need to avoid, and retry. If the remaining area became too small, you move to the next entry of your memory map. Eventually you'll find a place or your computer doesn't have enough RAM for your world domination plans. At any rate, you now know where your structure is going to be.
Now that you know where it is, you simply fill it out. For each piece of RAM that could go in there, you check if it overlaps with your kernel or your designated structure location, then drop it in as either free or occupied - you know all the locations now. After that, your structure is built, filled with the correct free/occupied settings, and you can finally call the functions of your memory allocator without having to worry about paradoxes.
All it takes is two global variables and a small number of locals which you can leave on the stack.