# Demand Paging

In Pintos, we assume that all allocated pages fit into memory. In this question, we remove that assumption and try to implement demand paging. For simplicity, we do this in an abstracted version of the code.

As a reminder, demand paging is where pages in memory are moved onto disk if they become inactive and more memory space is needed. If we need a page on disk, it causes a page fault, and we must bring that page back into memory.

You can assume that a page is 2^12 bytes and that there are 2^20 entries in a page table. Note that this isn't realistic - 2^20 is many more entries than usual.

Each page table entry is in the following format (0th bit is valid/invalid, 12th to 32nd are PPN):
`20 bits PPN, 11 bits unused, 1 bit valid/invalid`

Implement the lines below.

#define PGSIZE (1 << 12) // 2^12
#define PG_TABLE_SIZE (1 << 20) // 2^20

/*
 * Returns the physical address of a free frame. Handles page replacement under the hood. Implementation not shown. You
 * can assume this function succeeds.
 */
uint32_t get_free_physical_page();

/*
 * Returns the a-th to (b-1)-th bits in the bottom-most positions.
 * Example: get_bit_range(0b11110000, 2, 8) = 0b111100
 */
uint32_t get_bit_range(uint32_t in, int a, int b);

struct process {
  /*
   * Other fields omitted for clarity.
   */

  uint32_t page_table[PG_TABLE_SIZE];
}

void page_fault(uint32_t fault_addr) {
  /*
   * You can assume the fault is due to accessing a page in disk but not in memory. Code to handle other types of page
   * faults are omitted. You can also assume fault_addr is a valid address.
   */
  struct process *pcb = thread_current()->pcb;
  
  // Convert address to page boundary.
  uint32_t fault_page_addr = ______[A]______;
  
  // Get index of page table.
  uint32_t index = ______[B]______;

  // Get current page table entry.
  uint32_t pte = ______[C]______;

  // Only load page from disk if current page is invalid.
  if (______[D]______) {
    ______[E]x4______
  }
}

**Solution:**

#define PGSIZE (1 << 12) // 2^12
#define PG_TABLE_SIZE (1 << 20) // 2^20

/*
 * Returns the physical address of a free frame. Handles page replacement under the hood. Implementation not shown. You
 * can assume this function succeeds.
 */
uint32_t get_free_physical_page();

/*
 * Returns the a-th to (b-1)-th bits in the bottom-most positions.
 * Example: get_bit_range(0b11110000, 2, 8) = 0b111100
 */
uint32_t get_bit_range(uint32_t in, int a, int b);

struct process {
  /*
   * Other fields omitted for clarity.
   */

  uint32_t page_table[PG_TABLE_SIZE];
}

void page_fault(uint32_t fault_addr) {
  /*
   * You can assume the fault is due to accessing a page in disk but not in memory. Code to handle other types of page
   * faults are omitted. You can also assume fault_addr is a valid address.
   */
  struct process *pcb = thread_current()->pcb;
  
  // Convert address to page boundary.
  uint32_t fault_page_addr = fault_addr - fault_addr % PGSIZE;
  
  // Get index of page table.
  uint32_t index = get_bit_range(fault_page_addr, 12, 32);

  // Load page from disk.
  uint32_t pte = pcb->page_table[index];

  // Only load page from disk if current page is invalid.
  if (get_bit_range(pte, 0, 1) == 1) {
    uint32_t new_page = get_free_physical_page();
    uint32_t phys_page_num = new_page - new_page % PGSIZE;
    uint32_t new_pte = phys_page_num | 1;
    pcb->page_table[index] = pte;
  }
}