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)
> 

    [Ans:  16 bits offset for both virtual as well as physical address as 2^16=64k
    so we use lowest 16 bits for offset.]
> 
> 
> 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)
> 

    [Ans: 16+3=19, because one page has 2^6 * 2^10 ^ 2*3 bits]

> 
> 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)
> 

    [Ans: 28-19= 9 bits for PPN]
> 
> 
> 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)
> 

   [Ans: 128kB or 2 pages
   (as 1st level page table will need 64kB and we will need minimum
   one more level that is 2nd level page table of 64kB as we are using
   multi-level page tables. So 64kB+64kB=128kB is the minimum necessary page
   table size).]


> 
> 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.]
> 
> 

    [Ans: all answers below are correct.
      the first is calculated from virtual memory;
      the second is from physical memory. 
      the third considers page table pages.
    The question hasn't been clear about what we mean. Apologize.

      1) 2^33 bit / 2^19 bit  = 2^14 = 16*1024 pages

      2) 2^28 bit / 2^19 bit = 2^9 pages

      3) 2^9 (or 2^14) - X
        [** X is the number of page table pages.
         ** X will depend on the size of PTE which we haven't defined for CS5600-VMem.]
    ]
> 
> 
> 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)
> 
    [Answer:
        L1 index:   0
        L2 index:   512
        offset:     4092]
> 
> 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)
> 

    [Answer:
    L1 page table addr:  0xffff1000
    L2 page table addr:  0xf0f02000
    data page addr:      0xff005000
    ]
> 
> 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);
>       }
> 

    [Answer: 0xbeebebee]
> 
> 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)

    [Answer:
        You should get a segfault (it's very unlikely you will see something else)
        because 0x200ffc is a invalid address.
        (why? a process only uses a tiny portion of the entire address space (2^48=>256TB!).
        When you randomly choose one address, it is very very likely that the page
        hasn't been mapped to anything, which will trigger a page fault and then kernel
        will kill the process without knowing what to do.)]