A bitmap based allocation technique

[seraph9]

Hi,
as an amateur os developer, I'm still stuck in the world of memory management, confused as to what would be a reasonably good design and implementation method. Nevertheless, I decided to implement basic memory management using bitmaps just so that I could get a jump start and probably switch to something better as the code matures. My question is regarding my implemetation of a bitmap based allocation technique as shown below. I am using this function to allocate 4k slots in the kernel virtual address space which will be mapped to physical pages.

Code: Select all

static void*  mp_bitmap;
static uint32 mp_bitmap_i32 =0;
static uint16 mp_bitmap_i16 =0;
static uint8  mp_bitmap_i8  =0;

uint32 get_slot() 
{
  uint8 b, bit;

  if ( ((uint32*)(mp_bitmap))[mp_bitmap_i32] == 0xFFFFFFFF)
   for(mp_bitmap_i32 = 0; 
      ((uint32*)(mp_bitmap))[mp_bitmap_i32] == 0xFFFFFFFF; ++mp_bitmap_i32);
  if ( ((uint16*)(mp_bitmap))[mp_bitmap_i16] == 0xFFFF)
   for(mp_bitmap_i16 = mp_bitmap_i32*4; 
      ((uint16*)(mp_bitmap))[mp_bitmap_i16] == 0xFFFF; ++mp_bitmap_i16);
  if ( ((uint8*)(mp_bitmap))[mp_bitmap_i8] == 0xFF)
   for(mp_bitmap_i8  = mp_bitmap_i16*2; 
      ((uint8*)(mp_bitmap))[mp_bitmap_i8] == 0xFF; ++mp_bitmap_i8);
  
  b = ((uint8*)mp_bitmap)[mp_bitmap_i8];  
 
  for(bit = 7; b & 1; b = b >> 1) 
   bit--;

  ((uint8*)mp_bitmap)[mp_bitmap_i8] |= (0x80 >> bit);

   
  return ((mp_bitmap_i8) * 8) + (bit);
}

Its a function which returns an index (of an unset bit) in a bit map. It uses three static variables which keep track of free slots. There are three loops. The first one could loop a maximum of N/4 times, where N = size of bitmap in bytes. The second and the third, a maximum of 2 times. The idea is, once a 32bit word with free bits is tracked, the first loop won't execute at all, till the bits in it are used up. This narrows the subsequent searches down to 4 loops. Following this, the second loop won't enter till the 16bit word is not used up narrowing the search to 2 loops and so on to zero loops. Apart from the fact that there may be amazingly fast/good/efficient techniques out there, is there any reason why I shouldn't use "my" technique (as in, any pitfalls / design flaws / inefficiency / worst case) ?

Vivek

[ohboy]

It will be quite slow when you've allocated alot
There's another quite neat way; use a stack which contains all the free pages.
When you need a page you just pop one off of the stack, and when you're done with it you just push it back. This way the only inefficiency is when loading all the pages onto the stack the first time.
You could do some sort of combining of these two techniques, the bitmap one and the stack one, so at start you push, let's say 1024 pages onto the stack and when the stack's empty (allocated all the 1024 pages) you just get another 1024 pages using the bitmap.

[Pype.Clicker]

well, one reason i would not like to use it is its readability (all those casts everywhere !!)

i'm not sure either that those tests on 16 bits then 8 bits really help over scanning the 32 bits in a row, and performing a 'loop' on 'x:16 == 0xFFFF' just when you discovered that x:32!=FFFFFFFF seems useless to me (e.g. the most you will advance is 1 so why not simply have

Code: Select all

    if ((bm & 0xFFFF) == 0xFFFF) {
        bm=bm>>16; i+=16;
    }

also, your initial test if(bm == 0xFFFFFFFF) is useless and executes nothing.

Imagine we'll stress-test your technique: it start from a fully-free array, and a loop requests slots. At the Nth iteration, you'll need N/32 checks before you find a free dword for allocation. It might worth the effort to remember where was the last dword where you found a 'free' slot and start the search there at the next step.

Also, i may have got it wrong, but you're not using this to allocate *virtual addresses*, are you ? bitmaps are a technique to allocate *physical* frames (because any frame fits any use), but in the case of virtual addresses, you'll need rows of k consecutive pages, which a bitmap can hardly offer...

[seraph9]

well, one reason i would not like to use it is its readability (all those casts everywhere !!)

=)

i'm not sure either that those tests on 16 bits then 8 bits really help over scanning the 32 bits in a row, and performing a 'loop' on 'x:16 == 0xFFFF' just when you discovered that x:32!=FFFFFFFF seems useless to me (e.g. the most you will advance is 1 so why not simply have

Code: Select all

    if ((bm & 0xFFFF) == 0xFFFF) {
        bm=bm>>16; i+=16;
    }

Yes, you are right.

also, your initial test if(bm == 0xFFFFFFFF) is useless and executes nothing.

Oops! The semicolon wasn't supposed to be there. I have corrected it. This check is there because the first index once determines a free (32bit) slot stays there till all bits are used up. So the loop only needs to be executed once it becomes 0xFFFFFFFF.

Imagine we'll stress-test your technique: it start from a fully-free array, and a loop requests slots. At the Nth iteration, you'll need N/32 checks before you find a free dword for allocation. It might worth the effort to remember where was the last dword where you found a 'free' slot and start the search there at the next step.

This is what the mp_bitmap_i32 does. But in a slighlty different manner than what you suggested. As per the condition you stated, starting from a fully free array, the dword search loop will not execute till 32 bits are allocated. Also, keping track of the current position is somewhat like "next fit" (isn't it?). I have heard that its inefficient (?).

Also, i may have got it wrong, but you're not using this to allocate *virtual addresses*, are you ? bitmaps are a technique to allocate *physical* frames (because any frame fits any use), but in the case of virtual addresses, you'll need rows of k consecutive pages, which a bitmap can hardly offer...

Yes I am using it for virtual addresses, but for a special purpose. This routine is for allocating pages for mapping the physical pages used as tables or directories so I can keep track of them and modify them (without having to identity map them). So I don't see any need for consecutive pages or using the malloc routine which returns va from the kernel heap. I thought of the stack method for this, but it turned out to be inefficient in terms of freeing.

How have you guys managed to modify page tables? How do you keep track of them ? I have seen many people id mapping a portion of physical memory but is this recommended ?

[Pype.Clicker]

hmm ... i see. A kind of "page frame viewer" service ...
If this is the case, i have a superb trick for you (which you can look at http://cvs.sourceforge.net/viewcvs.py/c ... pfviewer.c :

use the page table itself to store a list of free pages each 'free' page table entry is tagged not present and a few bits in the 'flags' area tells the rest of your system that this page is part of a list.

You then simply use the 'frame #' part as the index of the next free page in the table.

With proper implementation, this will give you O(1) allocation and free operations instead of O(N)...

[seraph9]

Hey, thats neat. :).
One of the initial things that baffled me in mm using pages was mapping tables into directories and using them. For example, if getpage() is a function which returns the physical address of an allocated page, adding an entry into the page dir would look something like,

Code: Select all

   pa = getpage();
   pagedir[dir_index(va)] = pa | 3;

now the table is ready, but the question was how was I to add entries into the table. Obviously,

Code: Select all

  pa[tab_index(va)] = another_page | 3;

is not going to work. Certain threads in alt.os.dev suggested using id mapping, but that would mean a whole lot of vm allocated if the RAM size is huge. I finally decided on creating a translation map for each pgdir. ie, every page directory has an accompanying translation map (4k) the entries of which are the virtual addresses of the table corresponging to the va (rather than the pa as in the page dir). So this enables me to modify the table (provided that I have mapped the va to the pa of the table).

How have you managed to do it ? Is this what you use the "page frame viewer" for ?

[Pype.Clicker]

indeed, pa[anything] will not work.

The trick i use (as many other do) is to have one of the entries in the Page Directory to point at the Page Directory itself. Let PD_SELF be the number of that entry, then

Code: Select all

    pgEntry* pt=(pgEntry*) (PD_SELF<<22)|(page_table_number<<12)

is the virtual address for accessing a given page table.

You can then use

Code: Select all

    pt[tab_index(va)] = another_frame | flags

as wished.

[seraph9]

Hey, that makes sense ! ;D Sheesh, all this time I was thinking of complex techniques to the solve the problem when all the while it was as simple as this.

Thanks a lot.

[Pype.Clicker]

that's what learning is all about, no ? ;D

[Brendan]

Hi,

Mapping the page directory as if it's a page table (self-mapping) is a good trick. Any suggestions for doing the same thing for PAE?

Please note that with AMD's extensions PAE now supports up to 52 bit physical addresses (in legacy mode). Self mapping (at any level) doesn't work as the page directory pointer table is much smaller than a page directory, the U/S & R/W flags in page directory entries must be zero in page directory pointer entries and the PAT flag in page table entries must be 0 in page directory entries (and self-mapping at this level would result in many holes in the address space).

I'm currently emulating the self-mapping trick by using a virtual copy of each page table and page directory. This method works but it doubles overhead (RAM used for paging structures), which is already twice as much due to the 8 byte PD/PT entry format (total of 4 times as much overhead as non-PAE). Also it gets incredibly confusing:

Code: Select all

add_page {
    if(page_not_present) {
        if(page_table_not_present) {
            allocate_page
            map_page_into_page_directory
            map_page_into_page_directory_mapping
            allocate_page
            map_page_into_page_table_mapping
        }
        allocate_page
        map_page_into_page_directory
        map_page_into_page_directory_mapping
    }
}

Can you imagine this algorithm used to create the first address space, before paging is enabled and before the virtual mappings can actually be used? My head overflows with physical addresses and (PDPT, PDPT entry, PD, PD entry etc.) abbreviations


Cheers,

Brendan

[Candy]

Hi,

Mapping the page directory as if it's a page table (self-mapping) is a good trick. Any suggestions for doing the same thing for PAE?

Please note that with AMD's extensions PAE now supports up to 52 bit physical addresses (in legacy mode). Self mapping (at any level) doesn't work as the page directory pointer table is much smaller than a page directory, the U/S & R/W flags in page directory entries must be zero in page directory pointer entries and the PAT flag in page table entries must be 0 in page directory entries (and self-mapping at this level would result in many holes in the address space).

If you put it at the top of the top PD, and place the entire page table (all of it, all 8M in 32-bit mode) you're all set.

You put the lower two (or three) entries on everybody-read-write, and put the top one on supervisor-only-write. Because this inherits, the user cannot write to the top 1GB, so you're essentially protected. This also puts your top 4 PD's in the top of your PT's, essentially mapping them too.

I'm currently emulating the self-mapping trick by using a virtual copy of each page table and page directory. This method works but it doubles overhead (RAM used for paging structures), which is already twice as much due to the 8 byte PD/PT entry format (total of 4 times as much overhead as non-PAE). Also it gets incredibly confusing:
...
Can you imagine this algorithm used to create the first address space, before paging is enabled and before the virtual mappings can actually be used? My head overflows with physical addresses and (PDPT, PDPT entry, PD, PD entry etc.) abbreviations

You forgot PML4 and PML4E's and PT's and PTE's ::)

[proxy]

i thought i'd mention my technique for page allocation to see what people think It is generally a linked list of stacks. See in my opinion, the one and only downside to a stack is that the store has to be in linear memory (at least until you turn on paging i guess).

Anyway, the algorythm is simple really. I have a structure which is somthing like this:

Code: Select all

   class PageEntryHeader {
   public:
      PageEntry *next;
      uint32 stack_top;
   };
   #define STACK_PAGE_ENTRIES ((PAGE_SIZE / sizeof(void *)) - (sizeof(PageEntryHeader) / sizeof(void *)))
   
   // this should always total to exactly one page in size
   class PageEntry : public PageEntryHeader {
   public:
      void *entries[STACK_PAGE_ENTRIES];
   };

this is C++ but you get the point. it is a small header followed by the "stack" of entries.

when initializing memory i do the following. I make sure that i have not previously setup the region current being setup, and that it doesn't overlap with some things (such as the kernel). if it does, i simply adjust the numbers to make it not.

then i loop through the pages.

when i find one, i do one of 3 things.

if my pointer to a stack is null, this page is a stack page, i set it up
if my pointer to a stack contains a full stack page, this is a stack page, i link it in, and set it up
else i simply push this entry onto the stack.

during setup, i keep a pointer to the last page (since all previous ones are full) so this should be no slower than a standard stack on setup.

allocation is almost as simple as a stack:

Code: Select all

   PageEntry *page_ptr = m_PageStore;
   void *ptr = 0;
   while(page_ptr != 0) {
   
      // this page has a free one!
      if(page_ptr->stack_top != 0) {
         --page_ptr->stack_top;
         ptr = page_ptr->entries[page_ptr->stack_top];
         break;
      }
   
      // move on to the next page store
      page_ptr = page_ptr->next;
   }
   
   return ptr;

and as you can imagine freeing is very similar..

I came up with this last night and it seems to work very well, so far. what do you guys think?

proxy

[Pype.Clicker]

i remember of talking about a similar (if not identical) scheme on this board a couple of monthes ago ...

iirc, it uses some 'being freed' pages for maintaining the further 'freed' pages. It thus has the nice O(1) allocation of a list/stack without having the inconvenient of requiring a large, fixed amount of physical memory for managing pages.

somehow, it's very close to a stack that would use virtual memory (reclaiming unused and empty pages of stack, or allocating new frames when a pagefault occur while freeing a page).

Don't forget you'll also need to allocate a virtual page for storing that page-of-stack and update the mapping ...


** this page is now referenced through the WikiFAQ

[Brendan]

Hi,

If you put it at the top of the top PD, and place the entire page table (all of it, all 8M in 32-bit mode) you're all set.

You put the lower two (or three) entries on everybody-read-write, and put the top one on supervisor-only-write. Because this inherits, the user cannot write to the top 1GB, so you're essentially protected. This also puts your top 4 PD's in the top of your PT's, essentially mapping them too.

You're right! I was thinking the PT flags end up in the PD, but they don't it's the other way around (and I wasted 2 days trying to emulate it ::)).

Thanks Candy ;D

Brendan

[Brendan]

Hi,

i thought i'd mention my technique for page allocation to see what people think It is generally a linked list of stacks. See in my opinion, the one and only downside to a stack is that the store has to be in linear memory (at least until you turn on paging i guess).

I was using something very similar, but every 1023 (or 511) pages popped of the stack you need to flush the TLBs (because the top stack page is mapped into linear memory). Flushing the TLBs is expensive, especially on multi-processor systems when the page is in all address spaces, as the CPUs TLBs all need to be kept consistant.

Now I'm using a straight stack, where the first dword in a physical page points to the next physical page in the stack (or NULL if it's the last). I keep the physical address for the top page in the stack. When I allocate a page I insert this address into the paging structures, flush the TLB and then get the next physical page from where-ever the page was in linear memory and adjust the top of stack address. This way I never need to flush the TLB because of physical memory allocations/de-allocations.

The only downside is that it makes the code to allocate a linear page harder to write because it needs to update the top of a stack instead of this being done when the physical page is first allocated.

Cheers,

Brendan