Using a bitmap for paging

[t0xic]

Hello everyone,

I was wondering how to implement a bitmap for paging. Should I use something to this effect:

Code: Select all

char bitmap[128];

Since each char stores 8 bits? How could I turn on/off an individual bit in the character to mark a page as alloc'ed or not? etc:

Code: Select all

before_alloc:
0100 0010
after_alloc:
0100 0011
reclaim:
0000 0011

I've tried bitwise shifts and one's complement (~). Should I use xor (^), or something else completely?

Thanks,

--t0xic

[Combuster]

To be honest, I think the ability to solve this kind of binary math is definately part of the minimum requirement of an os developer

As for the problem itself, here are today's hints:
to set bits: x |= bits;
to clear bits: x &= ~(bits);
to test bits: (x & bits) == bits
to pick one bit: 1 << bit_no (bit_no ranges from 0..7)
I leave the rest up to you.

[t0xic]

Thanks combuster,

I didn't know C until I started os-deving, so I have been reading and learning C as I go... binary operations was (is?) the one part I am having trouble on

Thanks,

--t0xic

[Bughunter]

128 bytes = 1024 bits, meaning you'd have 1024 pages? Is this what you want?

I myself, use a stack for my Physical Memory Manager, which I completed yesterday

[t0xic]

@Bughunter,

I wanted 1024 pages for the bitmap so I can switch the bitmap along with the pagetable. I figured out how to imlement the bitmap, but could I see an example of your stack code? I know it would be faster, I just have no idea how to do it

Thanks,

--t0xic

[Bughunter]

Okay, but I first have fix a little bug in it, probably something with incorrectly scanning the memory map (I'm using GRUB at the moment). On a real PC, my code crashes, so I definitely don't want anybody to use it before it's stable.

I might post it within 10 minutes, maybe one day or within a week

[t0xic]

Ok thanks, just learning how paging works =)

--t0xic

[Bughunter]

Ok thanks, just learning how paging works =)

--t0xic

Please check my post about paging and linear address translation:

http://www.osdev.org/phpBB2/viewtopic.php?p=99581#99581

Btw I think I almost tracked down my bug and I'm soon releasing the source code of my Physical Memory Manager here.

[t0xic]

Ah thanks, that helps a lot

[JJeronimo]

I figured out how to implement the bitmap, but could I see an example of your stack code? I know it would be faster, I just have no idea how to do it

It's simpler than a bitmap, imho, so why don't you put your neurones in the way to invent your own code?!

Basically, you need a "mark_as_free" function that acts as a stack push operation, and a "get_free_page" function that acts as a stack pop. If you know how stacks work, then you already undestood the idea.


Enable paging before anything else. Use some sort of lazy allocation (for example, start allocating pages for the paging structures just above the last page used by the kernel) in this early environment.

Now, I suggest that you make the last PDE point to the page directory itself. This will enable you to access all the page tables in the correct order starting at 4GB-4MB, and the page directory starting at 4GB-4KB. Beware that accessing to missing page tables will cause a page fault, so either you perform extra tests to avoid them or you design everything to accordingly catch the kernel mode exceptions and allocate pages.

Then, write a function that returns information about a page's address (present_page, page_not_present, page_table_not_present, etc).

Then write the functions to work over the stack. Take care that you need to have present pages where you are going to write the stack contents when you do a push operation. My strategy was testing if the page at which the stack pointer points exists (using a function that you should have already written), and allocate the page that you were intended to push, instead of pushing it (but don't forget to blank the page before allocating it)... When poping, you do the same thing the backwards way and return the page that was allocated to the stack if the stack pointer is alligned *and* the page exists...

Then, write functions that play all the necessary work to map physical page X on linear address Y. Use the previous stack functions to get free pages if you need to allocate new page tables, and don't forget to clear them before usage.

JJ

[Bughunter]

I think you're overloading him with stuff. First you start with a Physical Memory Manager.

The PMM (Physical Memory Manager) does:

1. Initializes itself, which includes finding some space to store the addresses of pages (if you're using a stack) or finding some space to store a bitmap.
2. Then initialize your data structure (the stack or the bitmap). I used a stack, so after booting I use GRUB's memory map info (I'm using GRUB at the moment) to select the pages that are available. The pages that are available are pushed onto the stack.
3. You write a function allocpage() that can pop an address of a free page off the stack.
4. You write a function freepage() that can push an address of a used page back onto the stack (which makes that page available for use again).

The PMM itself has _nothing_ to do with page directories or page tables itself.

You just initialize your PMM and then you create a page directory to map the kernel and page stack pages into memory, then you enable paging.

EDIT: Let's clarify my explanation with an example:
This example assumes you are using GRUB.

1. GRUB boots, loads your kernel and jumps to it.
2. Your kernel stub starts executing.
3. While in the kernel stub, you find an address to store the page stack at, you find the address using GRUB's memory map info.
4. You find all pages that are not in use by the kernel and not in use by the page stack of free pages, all of these pages you find are free for use and should be pushed onto your stack.
For example:
4. A) You find the address 0x00500000 (using GRUB's memory map) to store your page stack at.
4. B) For example, your kernel starts below that address.
4. C) Your stack has 0x00100000 elements, which makes it 0x00400000 in size (sizeof(uintptr_t)*0x00100000).
4. D) You start with address 0x00500000 in a loop, and add 0x1000 (4096 bytes) to this address each loop. In each loop iteration, you push the calculated address onto the page stack.

[t0xic]

Ok... that makes a little sense I'll go read the intel manuals or somthing, and keep re-reading yor post until I understand

Thanks
--t0xic

[Bughunter]

Ok... that makes a little sense I'll go read the intel manuals or somthing, and keep re-reading yor post until I understand

Thanks
--t0xic

Great! If you have any questions, feel free to post them here. We all know what it is to be confused and get lost

[Bughunter]

Hey,

I'm done with my PMM for now, it uses the memory map given by GRUB. You could easily write your own bootloader and call the BIOS to get information about the memory (which I'll be doing too when I'm done with my MM) and provide that to your PMM initialization functions.

Below is my code for my current PMM. It is by no means the best solution, I'm sure it won't be, there's always room for optimization and expansions. Please use your mind to imagine what particular variable types might mean, like "uintptr_t", as because I didn't include my header files. Because I left out my header files, you should be stimulated to use this as reference, and create your own code for your PMM.

Questions are of course welcome too...

EDIT: I've updated my source code.
Bugfix: a virtual address should be assigned to the stack

[t0xic]

I have already written my own bootloader that retrieves system memory, but it is always about 2 mb reported more than there actually is . Today Ijust made the switch over to elf32-i386 and grub, and so far I like it

Thanks for the code I'll have to look over it,
--t0xic