Find how many free and used page there are in a address range

Question

I'm trying to port liballoc on a small kernel that I'm writing for my thesis. In order to do that, I need a function that scan a range of address to find free (and used) pages. I wrote that function that scan from and address (it should be pagetable aligned) and print if a page is free or is used:

uint32_t check_pages(uint32_t startAddr,uint32_t length){
    pdirectory* dir = vmm_get_directory ();
    pd_entry* pagedir = dir->m_entries;
    int cfreepage = 0;
    int cusedpage = 0;
    uint32_t x = 0, y = 0;
    for(x = startAddr; x < (startAddr+length) ; x+=4096*1024){ // check 1 pagetable at a time
        if(pagedir[x>>22] != 0){   // check if pagetable exist
            ptable* table =(ptable*) pagedir[x>>22]; 
            for(y=x;;y+=4096){ // scan every single pages in the pagetable
                pt_entry* page = (pt_entry*)table->m_entries [ PAGE_TABLE_INDEX (y) ]; 
                if(((uint32_t)(page)>>22) != 0){ // check if a page is present FIXME this might be the problem
                    cusedpage++;
                    kernelPrintf("Found used page number: %d\n",PAGE_TABLE_INDEX (y));
                }
                else{
                    cfreepage++;
                    kernelPrintf("Found free page number: %d\n",PAGE_TABLE_INDEX (y));
                }
                if(PAGE_TABLE_INDEX (y)==1023) break;
            }
        }
        else{ // if a pagetable doesn't exist add 1024 free pages to the counter
            kernelPrintf("found free pagetable! (1024 free pages)\n");
            cfreepage+=1024;

        }
    }
    kernelPrintf("Used Pages Found: %d\n",cusedpage);   
    kernelPrintf("Free Pages Found: %d\n",cfreepage);   
    return 0;
}

This code works, but have one issue: some pages that are used, will result free.. I think that the problem is this if:

if(((uint32_t)(page)>>22) != 0)

There might be a better way to check if a page is used or not.. Thanks for the help

Answer 1

if (x >> 22) checks if any bit higher than 21th is set. I have no clue why you shift by 22 (looks like an arbitrary number - why the heck do you do it this way?). If you want to check if an entry is present (in a paging structure of any level), check bit 0 of that entry. Note that checking the highest bits would only work if the entry was assigned with high address (wouldn't catch, say, 0x100000).

Also note that if present bit is 0, all the other bytes are ignored, hence the OS can store any values in them, which might also be an information that will come handy one day.

Answer 2

This maybe not what you want but it might help. I had once a similar task to do (memory allocator for an embedded system), here is what I did:

1. Define and align the allocable pages
2. Define elsewhere an array that references all the pages: I update the arry[idx] value when I allocate/release a page and it makes the count easy