# CS300 Final Exam Notes

### Resources:
- [Two's complement calculator.](https://www.exploringbinary.com/twos-complement-converter/])
- [2022 Midterm](https://cs.brown.edu/courses/csci0300/2022/quizzes/s22-midterm.html)
- [2021 Midterm](https://cs.brown.edu/courses/csci0300/2021/quizzes/s21-midterm.html)
- [Repl Compiler](https://replit.com/~)
- [Binary Convertor](https://www.binaryhexconverter.com/binary-to-decimal-converter)
- [Assembly Stuff](https://cs.brown.edu/courses/csci0300/2023/notes/l10.html)
- [All PLQs](https://edstem.org/us/courses/32619/discussion/3076975)

#### Data Representation:
- Strings can have characters that are more than 1 byte
- `6869 2c20 6373 3330 3021 0a00`
- We know this hex dump is a string because it ends with the null byte!
- ==All strings are terminated by null byte!!==
- Alignment
- Something of size x must divide it's address in memory by x
:::info
- Example:

             struct T { // Starts at 0
                struct Inner { // At 8
                    char* name; // Still 8 aligned, 16
                    long l; // still 8 aligned, 24
                    short s; // still divides, 26
                } inner;
                char* str; // needs + 6 padding, 8 aligned
            };

Structs will end their padding to align with their biggest member
- Memory Segmentation
:::info
- The heap can have holes in it, not continous
- Stack is continous, only allows memory objects with sizes known at compile time.
- The code segment (also referred to as .text) contains the compiled machine code. (like the code of built-in functions)
- Dynamic Memory
- `malloc` allows us to assign dynamic memory, stored on the heap
- Best used for something that we don't know the size of, like a linked-list that we don't know the length of past compilation!
- In Snake: Instances: allocating space for the game board, allocating linked list elements. Reason: ==neither size of the board nor length of the Snake linked list are known at compile time.==

- `DMalloc`
- Limitations:
- DMalloc allocator can only detect wild writes, not wild reads.
- The padding/secrets aren't large enough to detect overflowing by great amounts much. (remember we only had two special characters at the end).

#### Pointer arithmetic:
- Remember we go up by the size of the ==pointer type==:
:::success

char* func(char* str) {
  char* ret = (char*) ((long*) ((int*) str + 2) + 1) + 3;
  return ret;
}

`(int*) str + 2` Moves us to str + 8 position (int size * 2)
`(long*) (whatever) + 1` Moves us to str + 16 position (long size * 1)
`(char*) (whatever) + 3` Moves us to str + 19 position (char size * 3)

:::

#### Types of Undefined Behavior
- UB: accessing ==uninitialized== memory.
- UB: deferencing a NULL pointer.
- UB: global/data buffer overflow. (reaching beyond an array memory).
- UB: accessing uninitialized memory for array element 1. (trying to grab an uninitialized spot in an array)

> Biggest thing to look for with UB is uninitialized things! Not all UB is under compiler control, e.g., the contents of uninitialized memory aren't determined by the compiler, so we can't always determine what will happen.

#### Assembly
- Register Tables:
:::info
:::
- Assembly instructions often have a suffix that indicates what input data size and register width they're operating on.
- `-4(%rbp)` denotes a position of "4" in the `rpb` register (a place on the stack)
- Data Control:

         cmp    $300, %eax // compare 300 and value in eax
         jle    .L2 // jump to some function `L2`
             // jle means jump if less than, if 300 < eax , jump

- `eax` is always our return!!!!!
- `rsp` holds our next address right before returning
- Overwriting, we need to find distance from function to the `rsp` register (plus size of the address, which is `8`):
- `push %rbp` implicitly decrements %rsp by `8`
- `sub $0x20, %rsp` decrements it by another ==32== because we are in hexadecimal

#### Operating System
- Standard APIs for applications (syscall API)
- Mediating access to hardware (syscall API)
- Fair resource sharing (kernel scheduling, timer interrupt)
- Avoid starvation (timer interrupt, kernel memory protection)
- isolation of processes

        
    struct linkEd_Lizt {
        short jam_short; // 2B
        // 6B of padding (8 aligned)
        struct linkEd_Lizt* next_jam; // 8B
        char name[15]; // 15B
        // 1B of padding (8 aligned)
        struct linkEd_Lizt* previous_jam; // 8B
        int ranking; // 4B
        // 4B of padding
        char* description; // 8B
    }

- Ways to switch between Kernel and Userspace
- Interrupts
- System Calls
- This is why need to also have our kernel mapped, the `syscall` wants to put us in kernel space, but wont change the active page table, so the kernel code must be in our active pagetable
- File descriptors, (file metadata) is kept in Kernel memory
- In the `%cs` register, `0` means privileged, `3` means unprivileged

#### Virtual Memory and PageTables
- For each user-space process, we create an *illusion* that it runs alone on the computer and has access to the full memory, faking out an equivalent abstraction over some hardware without changing the interface.
- VM protects the kernel code from uncontrolled access, and protects userspace through abstracted isolation
- Everything has a VM address, which maps to a real place on the hardware in physical memory
- A VA goes to one PA, but a PA can have multiple shared VA to it
- Non-identity mapping is not necessarily more efficient, nor is it necessary for process isolation
- Page Tables : Mapping VA to PA
- A bit slow, need 3 lookups for a translation
- The bigger the page, the less tables we need, and the more data we can fit within a contextual locality
- The page tables aren't accessible for writing by userspace code
- 64 Bit virtual address,
- Bottom 12 bits 0 - 11 are offset. ==0 indexed==!!!
- To find an offset, do log_2 (pagesize) and choose something big enough
- An entry in a page table is 8 bytes - divide pagetable size by 8 bytes to figure out how many indexes there are
- To find how many bits you need for each level, do log_2 (num of indexes).
- Structure:
:::info
L4 Page tables contain 512 8 byte entries, either empty, or contain the address of an L3 page tables.

So:
- 1 L4
- up to 512 L3
- up to 512^2 L2
- up to 512^3 L1

L1 pagetables supply the actual information to translate a physical address intoa. virtual one, instead of storing a ptable address, the L1 entries contain part of a phsical address that a VA translate into, and also the permission bits that control it.

Lowest 12 bits of the PTE are garbage, always 0.


> **Note** To translate a virtual address, we need to split the middle bits of the address into groups of 9 and then convert those to decimal to decide which page table indices to use. **Once we've found an entry in the L1 page table, we need to remember to mask out the last 12 bits and replace them with the offset from the original virtual address.**

:::

#### Processes

To create a process, which is something the computer uses to get things done (using `ls` in the terminal starts and exits a process), we use `fork()`.

A call to `fork()` enters the kernel, which clones the process, then continues user-space execution in *both* clones. So, both execute the rest of the program.

> They have different process IDs (return value of `fork()`):
- **Parent Process**: return value of the new process PID.
- **Child Process**: return value of 0.
In fork(), all registers except` %rax` are copied, as `%rax` holds the return value of fork(), which is different for the parent and child process.

Same VM, but different mapped PA.
- Using forks in for loops is weird - fork in a loop of iteration 3 will create 2^3, 8 processes.

Running other programs, using `execv()`:
- Blows away the current process's virtual address
- Blows away the current page table, and the value in `%rip`, maintains VA of stack!
- Don't make local variables before exec, they will go away (dynamically allocate them on the heap!)
- Executes the specified program in the current process. Destroys the current process and replaces it
- `fork()` -> `execv()`, we create a child process, then use exec to run a program inside it, replacing the original process that fork copied.
- After a successful `exec()`, the parent code WON'T RUN.

`wait()` call:
- waits for the child process to finish executing all it needs to execute, before continuing on

- A zombie process is when the kernel retains the process id and exit status of the child process.
Pipes:
- Unidirectional, in-order transport between child and parent processes
- processes can't access the memory of other processes directly
- `int pipe(int pfd[2]);`, an array, with two file descriptors:
- `pfd[0]`: read end of the pipe
- `pfd[`1`]`: write end of the pipe

- Remember - pipe then fork!, we write to the pipe in the fork, and then from the other pipe array in the parent!
- Data from the pipe is held in a memory buffer in the kernel

#### Concurrency and Parallelism
- **Concurrency** means that multiple processes are active concurrently
- **Parallelism** means that the *actual* execution of instructions go on truly at the same time.

#### Threads
- execute concurrently like processes, but share the single virtual address space of their parent process!
- 
- a process can contain multiple threads, same file descriptor tables, but their own registers and stack
- Race conditions:
- when multiple threads access the same memory location and least one of these accesses is a write - leads to undefined behavior because things with original values get screwed up
- Solved with synchronization!
- Data races cause **memory leaks**.
- **Basic rule of synchronization**: if two or more threads can concurrently access an object, and at least one of the accesses is a write, a race condition can occur and synchronization is required.
- The main thread does not call `join()`, so it’s possible that the main thread finishes before the other threads do, be sure to finish all the threads first before returning!!
- The code segment of memory is read only, and thus no race condition may occur, since a race condition requires at least one thread to mutate the shared state in question.

#### Synchronization
- Atomics
- special instructions that always execute without racing with any other processor's accesses
- Synchronization Objects
- `std::atomic` only works on integers that are word-sized or smaller
- Sync objects are types whose methods can be used to achieve synchronization and atomicity on normal objects
- `mutex`
- `mutual exclusion` property

            mutex.lock();
            *x += 1;
            mutex.unlock();

- Creates an enforced code region between the `lock` and `unlock` called the critical section
- Waits for one thread to go through the entire critical section before the next enters - one enters at a time
- Condition Variables
- some condition needs to become true before
- `wait` unlocks the lock and blocks until another thread calls `notify_all()`
- `notify_all()` wakes up all threads blocked by calling wait to re-check the condition variable
- block a thread until a condition is satisfied, notify all unblocks them to try to execute again
- Deadlock
- occurs whenever an operation requires multiple mutexes to be locked, take locks in a consistent order across threads (like unique numbers in order)
- When a thread blocks on acquiring a lock that is already held and never given up, when two threads try to mutually take locks on resources that have already been locked