released: 03/24, 11:00
due: 03/31, 23:59

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

1. Byte-addressable vs. Bit-addressable memory

Imagine we have a CS5600-VMem machine whose virtual address is 33bits
and it uses 64kB pages.

1.a. Assume CS5600-VMem is byte-addressable like x86, meaning the machine can
access individual bytes (i.e., two addresses 0x1 and 0x2 point to **adjacent**
two bytes). Then, how many bits will the offset (in VA and PA) need to access all
bytes in a 64KB page? (1 point)



1.b. Now, assume CS5600-VMem is bit-addressable: it can access every **bit** in
memory, meaning two addresses 0x1 and 0x2 point to adjacent two bits. Then, how
many bits will the offset (in VA and PA) need to access all bits in a 64KB page? (1 point)



1.c. Again, the machine is bit-addressable. If the physical address is of 28
bits, how many bits does the PPN (physical page number) have? (1 point)



2. Two-level page table

Our current CS5600-VMem has:
  - bit-addressable memory,
  - 64KB pages,
  - 33bit VA,
  - and 28bit PA.
Now, we decide to use 2-level page table (similar to x86-32 we studied as
practice) for address translation.

2.a. What is the minimum memory consumed by a program's page table? (1 point)


2.b. How many pages a program can use at most? (1 point)
[notice that CS5600-VMem is bit-addressable, meaning 8 VAs access one byte.]




3. 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 | 0xbeebebee | 0xffff1ffc | 0xd5202007 | 0xffff5ffc | 0xdeadbeef |
              +------------+            +------------+            +------------+            +------------+
              | ...        |            | ...        |            | ...        |            | ...        |
              +------------+            +------------+            +------------+            +------------+
  0xf0f02800  | 0xff005007 | 0xff005800 | 0xf00f8000 | 0xffff1800 | 0xef005007 | 0xffff5800 | 0xff005000 |
              +------------+            +------------+            +------------+            +------------+
              | ...        |            | ...        |            | ...        |            | ...        |
              +------------+            +------------+            +------------+            +------------+
  0xf0f02000  | 0xffff5007 | 0xff005000 | 0xc5201000 | 0xffff1000 | 0xf0f02007 | 0xffff5000 | 0xc5202000 |
              +------------+            +------------+            +------------+            +------------+

Question:

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


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


3.c. What's the output of the following code?  (1 point)
     (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 3.a [update 03/24: was "1.a", a typo].)

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


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