Week 8.b
CS 5600
03/01 2023

1. Intro to Virtual memory
2. bit manipulation
3. Paging
    --intro
    --page table
    --multilevel page table
    --alternatives & tradeoffs
-------------------------------------------------

Admin

- Midterm
  -- will grade this Thursday
  -- grade doesn't sound right? challenge us:
    -- private challenge
    -- public challenge
    -- detailed instructions will release soon

---

1. Virtual memory intro

    --very important idea in computer systems

    --virtual address translation:
      VA (virtual address)
        =>
      PA (physical address)

    --setup

      draw picture:

          heap, stack, program text.


      draw picture:

          * program:

           0x500     movq 0x200000, %rax
           0x508     incq %rax, 1
           0x510     movq %rax, 0x300000

          [CPU ---> translation box --> physical addresses]

        Question: how many virtual memory translations happen when the lines
        above are executed?

        (answer: 5.
                3 for the instructions
                1 for the load
                1 for the store)

    --"to virtualize" means "to lie" or "to fool". we'll say how this is
    implemented in a few moments. for now, let's look at the benefits of
    being interposed on memory accesses.

    --benefits:

      (a) programmability (book calls this "transparency"):

        --programs use addresses like 0, 0x200000, etc. (see example
        above)

        --three benefits, at least:

          (i) program *thinks* it has lots of memory, organized in a
          contiguous space

          (ii) programs can use "easy-to-use" addresses like 0,
          0x20000, whatever. compiler and linker don't have to worry
          about where the program actually lives in physical memory
          when it executes.
           -- good for modularization

          (iii) multiple instances of same program foo are each loaded,
          each thinks its using memory addresses like 0x50000,
          whatever, but of course they're not using the same physical
          cells in RAM

      (b) protection:

        --processes cannot read or write each other's memory

        --this protection is at the heart of the isolation among
        processes that is provided by the OS

            --prevents bug in one process from corrupting another
            process. (non-adversarial scenarios)

            --don't even want a process to observe another
            process's memory (like if that process has secret or
            sensitive data). (adversarial scenarios)

        --the idea is that:
           if you cannot name something, you cannot use it.
          this is a deep idea.

        --Question: can you think of another example of this naming idea?
          (answer: file descriptor)

        --"using daemon names to control them"
          --daemon world and human world (two processes)
          --if somehow a daemon comes to human world (a shared mem/fd)
          --if a human knows the daemon's name (a piece of code having the mem-address/fd)
          --then the human can kill/control (?) the daemon (the code can use the mem/fd)
          [https://warhammerfantasy.fandom.com/wiki/Daemon_Names]


      (c) effective use of resources:

        --programmers don't have to worry that the sum of the memory
        consumed by all active processes is larger than physical
        memory.

      (d) sharing:

        --processes share memory under controlled circumstances,
        but that physical memory may show up at very different
        virtual addresses
        --that is, two processes have a different way to refer
        to the same physical memory cells


    --how is this translation implemented?

       --software(OS)-hardware(MMU) co-design

       --in modern systems, hardware does it. this hardware is
       configured by the OS.

       --this hardware is called the MMU, for memory management unit,
       and is part of the CPU

       --why doesn't OS just translate itself? similar to asking why we
       don't execute programs by running them on an emulation of a
       processor (too slow)

    --things to remember in what follows:

        --OS is going to be setting up data structures that
        the hardware sees

        --these data structures are *per-process* 

2. Crash course: bit manipulation

  -- 0s and 1s are basics of computer

    [aside: there is ternary computers
      "optimal coding of numbers"
      https://en.wikipedia.org/wiki/Ternary_computer]

  -- hexadecimal numbers (or hex numbers)
    -- integer with base of 16
    -- an example: 0x123456789abcdef
    -- other examples: 0xdeadbeef, 0xbebeebee

  -- binary vs. hex
     -- 0000 == 0x0
     -- 1111 == 0xf

  -- why "0x" for hex?
    --short answer: a convention, an arbitrary choice
    [see: https://stackoverflow.com/questions/2670639/why-are-hexadecimal-numbers-prefixed-with-0x]

  -- 32-bit vs. 64-bit CPU
    -- the length of a memory address

    -- Question: how much memory can a 32-bit CPU address?
       (answer: 2^32 = 4GB)

  -- get comfortable mapping between
     "number of bits" and "size of the space".
     (will see them soon)

     -- 5 bits => 32 different numbers (size of the space)
     -- 10 bits => 1024 different numbers

  [aside:
      2^10: kilo ~1000
      2^20: mega, ~1 million
      2^30: giga, ~1 billion
      2^40: tera, ~1 trillion
      2^50: peta, ~1 quadrillion]


3. Paging

   [virtual memory -> paging -> page table -> x86-64]

    A. Intro

    --Basic concept: divide all of memory (physical and virtual)
    into *fixed-size* chunks.

        --these chunks are called *PAGES*.

        --they have a size called the PAGE SIZE.
        (different hardware architectures specify different sizes)

        --in the traditional x86, the PAGE SIZE
        will be
        4096 B = 4KB = 2^{12}

    --Warm-up:

    --Question: how many pages are there on a 32-bit architecture?

        2^{32} bytes / (2^{12} bytes/page) = 2^{20} pages

    --Question: what about if there are 48 bits used to address memory?

        2^{48} bytes / (2^{12} bytes/page) = 2^{36} pages
                                           = 64 billion pages

    --Each process has a separate mapping

      --And each page separately mapped

      --we will allow the OS to gain control on certain operations

        --Read-only pages trap to OS on write (store)

        --Invalid pages trap to OS on read (load) or write (store)

        --OS can change mapping and resume application

    --it is proper and fitting to talk about pages having **NUMBERS**. 

    --page 0:   [0,4095]
    --page 1:   [4096, 8191]
    --page 2:   [8192, 12277]
    --page 3:   [12777, 16384]
    ...
    --page 2^{20}-1 [ ..., 2^{32} - 1]

    --unfortunately, it is also proper and fitting to talk about _both_
    virtual and physical pages having numbers.

    --sometimes we will try to be clear with terms like:
        VPN: virtual page number
        PPN: physical page number

    [aside:
        the "math" of virtual memory: get comfortable mapping between
        "number of bits required to represent something" and "size of the
        space". The latter is two-raised-to-the-power-of-the-former.
        Examples: 

          a virtual address is 32 bits, means the virtual address space is
              2^32 = 4 GB.

          the VPN is 20 bits, means there are 2^{20} virtual pages, and
              and the offset is 12 bits, which means page size of 2^12,
              or 4KB.
    ]

    B. Key data structure: page table

        page table conceptually implements a map from 
            VPN --> PPN

        NOTE: VPN and PPN need not (and do not, in our case study) have
        the same number of bits

        page table is conceptually an index. 

         the address is broken up into bits:

                 [.............|........]

                 [ VPN         | offset ]
                    |             |
                    |             +
                    |             |
                    --> TABLE --> PPN
                                   =
                                 address

         top bits index into page table. contents at that index are the PPN.

         bottom bits are the offset. not changed by the mapping

         physical address = PPN + offset

           (note: "+" here means "concatenate":
              for example, 123 "+" 456 => 123456)

         result is that each page table entry expresses a mapping about a
         contiguous group of addresses.


    --another way to look at it:

        (assume 48-bit addresses and 4KB pages)

    there is in the sky a 2^{36} sized array that maps the
    virtual address to a *physical* page

    table[36-bit virtual page number] = 20-bit physical page #

      EXAMPLE: 

        if OS wants a program to be able to use address 0x00402000
        to refer to physical address 0x00003000, then the OS
        conceptually adds an entry:

            table[0x00402] = 0x00003

        (this is the 1026th virtual page being mapped to the 3rd
        physical page.). in decimal: table[1026] = 3

        next class, we will see how this is actually implemented

      NOTE: top 36 bits are doing the indirection. bottom 12 bits just
      figure out where on the page the access should take place.

          --bottom bits are called _offset_.


    --Question: do offset and page size have anything to do with each other?
      (answer: yes. The page size decides the offset bits:
        if page size is 4KB, then offset needs to be 12bit;
        if page size is 16KB, then offset needs to be 14bit;)

    --Question: can a VA 0x123456 be mapped to PA 0xab9876 with page size=4KB?
      (answer: no; the offset cannot be changed between VA and PA)

    --Question: can a VA 0x123456 ever be able to map to PA 0xab9876?
      (answer: yes, if the page size <= 16B.)

    --so now all we have to do is create this mapping

    --why is this hard? why not just create the mapping?

    --Question: how large is this table?
    --answer: then you need, per process, roughly 512GB (2^{36}
    entries * 8 bytes per entry).

        [why 8 bytes per entry? in practice, it's convenient to have
        the entry size be the same as a data type on the machine]

    --too much! let's deal with this...

    [draw on bard a black-box MMU: inputs are VAs; outputs are PAs;]

    --Question: if you were MMU designer, how would you design the table?
      --neural network? ;-)