HW5
released: 11/2, 21:00
due: 11/9, 13:00

Answer the following questions.
Submit your answers to Canvas assignments. There is an entry for this homework.


1. Bit-addressable memory

As mentioned in class, x86 is byte-addressable, which supports accessing
individual bytes. For example, address 0x0 and 0x1 differ by 1 byte.
Imagine you're designing a new CPU architecture x97-64 which uses bit-addressable
addresses, meaning a program can directly access each bit in an address space,
and address 0x0 and 0x1 differ by 1 bit.

1.a. Assume you will still use paging with a page size of 4KB.
     What's the offset length to access all *bits* in a page?
     Write down the offset length.


1.b. If x97-64 still uses 40-bit to represent physical page number (PPN),
     how many bits does a physical address have? (was 52 bits for x86-64)


1.c. Given 40-bit PPN, how many bits does a page table entry need?
     (was 64 bits in x86-64)


1.d. Will this bit-addressable design affect L1/L2/L3/L4 index length in one
     virtual address? (was 9bit each in x86-64)
     Why and why not? Explain in 1-2 sentences.



2. Simulate CPU and walk page tables

   -- This is the standard x86 32-bit two-level page table structure
       (not x86-64; we use 32-bit for simplicity).
   -- The permission bits of page directory entries and page table entries are set to 0x7.
      (what does 0x7 mean? 
       answer: page present, read-write, and user-mode; see handout week8.b.
       This means that the virtual addresses are valid, and that user programs
       can read (load) from and write (store) to the virtual address.)

   -- The memory pages are listed below.
      On the left side of the pages are their addresses.
      (For example, the address of the "top-left" memory block (4 bytes) is
      0xf0f02ffc, and its content is 0xf0f03007.)

  %cr3:  0xffff1000

              +------------+            +------------+            +------------+            +------------+
  0xf0f02ffc  | 0xf00f3007 | 0xff005ffc | 0xbebeebee | 0xffff1ffc | 0xd5202007 | 0xffff5ffc | 0xdeadbeef |
              +------------+            +------------+            +------------+            +------------+
              | ...        |            | ...        |            | ...        |            | ...        |
              +------------+            +------------+            +------------+            +------------+
  0xf0f02800  | 0xff005007 | 0xff005800 | 0xf00f8000 | 0xffff1800 | 0xef005007 | 0xffff5800 | 0xff005000 |
              +------------+            +------------+            +------------+            +------------+
              | ...        |            | ...        |            | ...        |            | ...        |
              +------------+            +------------+            +------------+            +------------+
  0xf0f02000  | 0xffff5007 | 0xff005000 | 0xc5201000 | 0xffff1000 | 0xf0f02007 | 0xffff5000 | 0xc5202000 |
              +------------+            +------------+            +------------+            +------------+

Question:

2.a. Split the 32bit virtual address "0x00200ffc" into L1 index (10bit), L2 index
     (10bit), and offset (12bit).
     Write them down in _decimal_ numbers:

       L1 index:
       L2 index:
       offset:

2.b. When accessing virtual address "0x00200ffc" using the above %cr3,
     what L1/L2 page tables are used and where is the physical data page?
     Write down L1/L2 and data page starting addresses (namely, the physical
     address of the first byte on these pages).

       L1 page table addr:
       L2 page table addr:
       data page addr:

2.c. What's the output of the following code?
     (hint: (1) because of this is x86-32, there are 1024 PT entries in a PT
     page (4KB = 32bit x 1024); (2) notice the L2 index in the question 2.a.)

      #include "stdio.h"
      int main() {
         int *ptr2 = (int *) 0x00200ffc;
         printf("%x\n", *ptr2);
      }

2.d. Copy the above code to a ".c" file, compile, and run.
     What do you see? and why? (explain in 1 sentence)



3. TLB and page faults

Assume that the assembly code below is executed after a context switch. Make
the following additional assumptions:

 -- The TLB is flushed (emptied) after context switch (this is how the x86 works).
    (hint: the instruction TLB is flushed as well.)
 -- Suppose all data pages (i.e. 0x200000, 0x300000) are stored on disk when instruction 0x500 is executing.
 -- There is no prefetching.

[clarification 11/5: TLB's mappings are in the granularity of pages; meaning
that if one TLB miss happened, TLB will learn the mapping between a VPN
(virtual page number) and a PPN (physical page number).]

  [context switch]
  0x500     movq 0x200000, %rax    # move data in address 0x200000 to register %eax
  0x508     incq %rax, 1           # add one to %eax
  0x510     movq %rax, 0x300000    # move register %eax to memory location 0x300000

Answer the following questions:

3.a. How many TLB misses will happen, and for which pages?

3.b. How many page faults will happen, and for which pages?