computing physical addresses from virtual addresses in C

Question

I'm struggling to write a function that translates virtual memory address to physical ones. I want the function to return the physical memory address of a virtual 16-bit address.

I'm just using 16-bit long virtual addresses that ignore permission bits (read,write, etc.). There are 256 pages in the page table so the base table register, which is BTR, just points to the table.

I want the function to either return:

    Success: the physical address (a void*)
    Page Fault: the virtual page number (an integer)
    Protection Fault: a copy of the PTE

Here is the page table entry:

    31    30..28 27..............................................4 3 2 1 0
   +-----+------+-------------------------------------------------+-+-+-+-+
   |Valid|unused| 24-bit Physical Page Number                     |P|R|W|X|
   +-----+------+-------------------------------------------------+-+-+-+-+

I'm trying to learn how virtual memory works. I'm confused on how I would take a 16-bit virtual address and map it to a 32-bit page table entry, and then how to get the physical address from there. I've defined result_t and a union of the page table entry below, but I'm unsure how to use them. I've gotten a lot of help from looking online but everything is getting muddle together, I just want to learn how everything works straightforwardly.

Here are some necessary definitions:

  extern void* BTR;

  typedef struct result_st {
     enum {SUCCESS, PAGEFAULT,
                PROTFAULT, NOTIMPLEMENTED} status;
     union {
         void* pa;
         unsigned vpn;
         unsigned pte;
     } value;

    } result_t;
  static result_t success(void* pa) {

      result_t res;
      res.status=SUCCESS;
      res.value.pa = pa;
      return res;
    }

  typedef union {
      unsigned All;
      struct {
        unsigned Valid               :1;
        unsigned Unused              :3;
        unsigned PhysicalPageNumber  :24;
        unsigned SupervisoryMode     :1;
        unsigned Read                :1;
        unsigned Execute             :1;
        unsigned Write               :1;

      };
    } PageTableEntry;

  static int is_valid (unsigned pte) {

        return 1 & (pte >> 31);
      }

Here is the function I am writing:

result_t legacy(unsigned short va)
{
  result_t result;
  unsigned pte = va << 8;
  result.value.pte = pte;
  // This is my attempt so far.
  // I want to use is_Valid() somewhere

  void* pa = pte >> 8 | (va & 255);
    return success(pa);
}

Thanks for any advice you can provide!

there may be different types of page tables, two-level, three-level, etc. — mangusta
Isn't it quite platform dependent? I would expect yes, so you ought to put platform tag and bitness. It cannot be just generic C question — Severin Pappadeux
I provided the page table entry, bitness, and bit-length for the address. This isn't specific to a platform, I'm defining the platform. — slippeel
@slippeel: Then it's probably badly designed. If I assume 32-bit virtual addresses and 32-bit physical address then your page number needs to be shifted left because its in the wrong place (e.g. phys = ((entry & mask) << 8) + offset and not phys = (entry & mask) + offset) and the page number should be bits 12 to 31 of the page table entry instead. In addition to that every single process/virtual address space will need a full page table that would cost 4 MiB (even if they only use a tiny fraction of their virtual address space); so ~100 processes = ~400 MiB of RAM that's mostly wasted. — Brendan

kaylum kaylum · Accepted Answer · 2015-06-05T06:04:50

You are missing the definition of the actual page table. I assume it's like this (assuming I have understood your question correctly):

#define PAGE_TABLE_SIZE 256
PageTable page_table[PAGE_TABLE_SIZE];

Then your code would look something like this:

#define VIRT_PAGE_SIZE_BITS 8

/* Get virtual page number by dividing by the virt page size */
unsigned int virt_page_num = va >> VIRT_PAGE_SIZE_BITS;

assert(virt_page_num < PAGE_TABLE_SIZE); // Or do proper error handling

/* Use virtual page number to index into page table */
PageTableEntry pte = page_table[virt_page_num];
if (is_valid(pte)) {
    if (is_access_ok(pte)) {
        unsigned int phys_page_num = pte.PhysicalPageNumber;
        return success(phys_page_num);
    } else {
        /* Protection fault code goes here */
    }
} else {
    /* Page fault code goes here */
}

computing physical addresses from virtual addresses in C

1 Answers