Paging on Intel x86-64

This article gives a rough overview on how paging on Intel x86-64 works, covering what you need to know for working with it and where to find it in SWEB.

In /arch/x86/64/include/ you will find the file paging_definitions.h which holds the structs used for Intel x86-64 Memory Management Unit (MMU). The MMUuses virtual addresses and maps them to physical ones. That makes it possible to use the same address region in different processes. But what is a virtual address?

Virtual address on Intelx86-64 are actually only 48 bits (the upper 16 bits cannot be used and have a defined value). These 48 bit virtual addresses look like this:

On x86-64 systems we have 4kB pages so we need 12 bit in order to address a page 2^12 = 4096 = 4kB). In these paging tables (PML4, PDPT, PD, PT), every entry has 8 bytes and each table has a size of 4kB. This means each table has 512 entries which is why we need to have 9 bits to be able to address each entry (2^9 = 512).

If we want to get the physical address out of the virtual one, the highest 9 bits (called x in our illustration) are taken in order to get the corresponding PML4entry. This entry holds, amongst other things, the physical address of the PDPTpage holding the PDPTentry we are trying to find. We are using the next 9 bits (= y) to find the right PDPTentry. On the next level we use the next 9 bits to find the right PDentry on the PD page. On the last level we use the next 9 bits to find the right PD entry on the PT page, The PT entry tells us the physical base address of the page mapped. If one of these steps fail a PageFault occurs.

So now let us have a look on the different structs used for the mapping, which can be found in /arch/x86/64/include/paging_definitions.h. Firstly the page directory entry:

typedef struct
{
  uint64 present                   :1;
  uint64 writeable                 :1;
  uint64 user_access               :1;
  uint64 write_through             :1;
  uint64 cache_disabled            :1;
  uint64 accessed                  :1;
  uint64 ignored_3                 :1;
  uint64 size                      :1; // must be 0
  uint64 ignored_2                 :4;
  uint64 page_ppn                  :28;
  uint64 reserved_1                :12; // must be 0
  uint64 ignored_1                 :11;
  uint64 execution_disabled        :1;
} __attribute__((__packed__)) PageMapLevel4Entry;

Here you find several bits used by the MMU. Some of them are set and deleted by the OS (which means YOUR CODE) some of them the MMUwill set itself.

• present: the present bit is set in order to show that the mapping in this entry is valid. The OS sets and deletes it.
• writeable: Used to control the access to this page. If not set, writing on this page will result in a pagefault. The OS sets and deletes it.
• user_access: Used to control the access to this page. If set the page is accessable from userspace, else it is only accessable from within the kernel. Controlled by the OS.
• write_through: Used to choose the caching strategy, which is either write-through or write-back. Controlled by the OS.
• cache_disabled: If this page is set the page will not be cached. Controlled by the OS.
• accessed: Set by the MMU when the page is either read from or written on. Has to be deleted by the OS.
• reserverd: This bit is not used in page directories.
• size: If set 2 MiB pages (instead of 4 KiB pages) are used. Normally not set. Controlled by the OS.
• global_page: This bit is not used in page directories.
• ignored bits: are also not used.
• page_ppm: contains the physical page number of the PDPT. Has to be multiplied with the page size in order to get the physical start address of the page. The OS has to set and reset this value.

All of the ignored bits can be set to any value you’d like to store in the page directory entry. We suggest you start with renaming the three available bits to names that describe what you store in this bit.

struct PageDirPointerTablePageDirEntry
{
  uint64 present                   :1;
  uint64 writeable                 :1;
  uint64 user_access               :1;
  uint64 write_through             :1;
  uint64 cache_disabled            :1;
  uint64 accessed                  :1;
  uint64 ignored_3                 :1;
  uint64 size                      :1; // 0 means page directory mapped
  uint64 ignored_2                 :4;
  uint64 page_ppn                  :28;
  uint64 reserved_1                :12; // must be 0
  uint64 ignored_1                 :11;
  uint64 execution_disabled        :1;
} __attribute__((__packed__));

struct PageDirPageTableEntry
{
  uint64 present                   :1;
  uint64 writeable                 :1;
  uint64 user_access               :1;
  uint64 write_through             :1;
  uint64 cache_disabled            :1;
  uint64 accessed                  :1;
  uint64 ignored_3                 :1;
  uint64 size                      :1; // 0 means page table mapped
  uint64 ignored_2                 :4;
  uint64 page_ppn                  :28;
  uint64 reserved_1                :12; // must be 0
  uint64 ignored_1                 :11;
  uint64 execution_disabled        :1;
} __attribute__((__packed__));

typedef struct
{
  uint64 present                   :1;
  uint64 writeable                 :1;
  uint64 user_access               :1;
  uint64 write_through             :1;
  uint64 cache_disabled            :1;
  uint64 accessed                  :1;
  uint64 dirty                     :1;
  uint64 size                      :1;
  uint64 global                    :1;
  uint64 ignored_2                 :3;
  uint64 page_ppn                  :28;
  uint64 reserved_1                :12; // must be 0
  uint64 ignored_1                 :11;
  uint64 execution_disabled        :1;
} __attribute__((__packed__)) PageTableEntry;

Here we will only describe the bits that do something different than the bits in the page directory entry.

• dirty: Is set by the MMUwhen the the page is written on. Has to be deleted by the OS.
• global_page: If set the Translation Lookaside Buffer (TLB) won’t update this address during the next context switch. Shouldn’t be used in this course. Controlled by the OS.
• page_ppn: contains the physical page number of the page mapped to the virtual address (i.e. physical address of the page divided by 4096).