OSDev.org

I'm using a simple bitmap to allocate single pages (which I might extend to a buddy system in the future to allocate larger chunks). Allocating and freeing works. At initialisation, it uses the BIOS E820 map to initialise the bitmap and mark pages as used, and afterwards it also reserves a few more areas (page 0, EBDA etc.). However, there is the problem of the case when something goes wrong and it ends up trying to free one of these unallocatable areas. Of course this should never happen, but I'd rather be able to catch it anyway (you know, the more impossible it is, the more it hurts when it does happen).

What are possible ways to catch whenever an unallocatable page is freed? I've thought of simply using a second bitmap which acts as a mask, but this seems like a huge waste of space to me. Any ideas?

I'm not sure, but can some implementation of a search tree be used? Or maybe a sparse index? There are a lot of data structures for different purposes and a bitmap might now be the most efficient in terms of memory usage as you said yourself. It has a O(1) access time, but it might not be worth it if it is only used in case of an error that shouldn't happen. I wouldn't spend a lot of memory on it. It doesn't matter that the data structure has a slow access time. Maybe even a linked list can do it?

Hmm now that you say that... I could turn the BIOS memory map into a linked list, where the nodes contain both a link to the next entry and to the next entry of the same type. That would save a few iterations if all you want are the RAM regions. And although it would need to be checked every time a page is freed, would hardly slow things down. Thanks for the idea!

Hi,

CodeCat wrote:What are possible ways to catch whenever an unallocatable page is freed? I've thought of simply using a second bitmap which acts as a mask, but this seems like a huge waste of space to me. Any ideas?

There's at least 3 "available" bits in each page table entry that can be used by the OS. I use these bits to store the type of page when the page is mapped into the address space - for e.g. values 0 to 3 might be normal RAM, while values 4 to 7 might be special mappings (memory mapped I/O, a ROM mapping, etc).

When a page is freed I know if it's normal RAM or not by checking the value in these "available" bits in the page table entry. When page tables and page directories are freed I know they're normal RAM without checking because it doesn't make any sense for them to be anything else. There isn't any thing else that allocated RAM pages can be used for.


Cheers,

Brendan

That's a good solution, but I want to keep physical page allocation and page mapping separate as much as possible. In the interest of doing it the proper OO way, with encapsulation and information hiding and all that (yeah I like C++ a lot ).