First Step in Understanding Paged Virtual Memory: Creating Page Table Entry upon Initial Page Fault

I am trying to understand virtual memory paging. I have the following code snippet that represents the first step in the process. Here search_tbl is called from the main program for each logical address in order to check if the page table already has an entry that maps the provided logical address to a location in physical memory. vfn is the virtual frame number.

EDITED: Does this implementation make any sense? Or am I going down the wrong road?

Any help/suggestion would be greatly appreciated. Thank you.

uint vfn_bits;//virtual frame number
static tbl_entry **tbl;
uint page_bits = log_2(pagesize);
vfn_bits = addr_space_bits - page_bits;
tbl = calloc(pow_2(vfn_bits), sizeof (tbl_entry*));

tbl_entry *search_tbl(uint vfn) {

    uint index = vfn;
    if (tbl[index] == NULL) {
        /* Initial miss */
        tbl[index] = create_tbl_entry(vfn);
    }
    return tbl[ind开发者_StackOverflowex];
}

tbl_entry *create_tbl_entry(uint vfn) {
    tbl_entry *te;
    te = (tbl_entry*) (malloc(sizeof (tbl_entry)));

    te->vfn = vfn;
    te->pfn = -1;
    te->valid = FALSE;
    te->modified = FALSE;
    te->reference = 0;

    return te;
}

The only real issue I can see with it is that search_tbl()'s return type is tbl_entry* but it is actually returning a tbl_entry. That could be a major issue though, thinking about, it if the page table is really an array of pointers to page table entries. Also, if sizeof(tbl_entry) > sizeof(tbl_entry*) you are not allocating enough space for the table.

Another issue might be getbits(). It's normal practice to number the bits of an n-bit integer type with 0 as the least significant bit and n - 1 as the most significant bit. If that is the case for the getbits() API, you are calculating the index based on the wrong part of the address.

Edit

The above was true for the original version of the code in the question which has been edited out.

As for the getbits question in the comment, if the following is used (assuming 32 bit addresses)

uint32_t getbits(uint32_t x, unsigned int p, unsigned int n)
{
    return (x >> (p + 1-n)) & ~(~0 << n);
}

That assumes that the most significant bit is the one with the highest number i.e. bit 31 is the highest bit. So, if you assume a page size of 4096 bytes, the frame number of an address can be obtained like this:

vfn = getbits(x, 31, 20); // 31 is the top bit, number of bits is 32 - log2(4096)