New posts: umich/w24_wrapup and umich/w24_482

5 files changed, 373 insertions, 0 deletions

diff --git a/docs/umich/img/w24_wrapup/482_submission.png b/docs/umich/img/w24_wrapup/482_submission.png
new file mode 100644
index 0000000..969a11a
--- /dev/null
+++ b/docs/umich/img/w24_wrapup/482_submission.png
diff --git a/docs/umich/img/w24_wrapup/482_website.png b/docs/umich/img/w24_wrapup/482_website.png
new file mode 100644
index 0000000..dc80170
--- /dev/null
+++ b/docs/umich/img/w24_wrapup/482_website.png
diff --git a/docs/umich/index.md b/docs/umich/index.md
index ecb443b..9174997 100644
--- a/docs/umich/index.md
+++ b/docs/umich/index.md
@@ -5,3 +5,4 @@ so basically i live in ann arbor now
 - [Lessons in the US of A](us_lessons.md)
 - [Fall 2023 Wrapup](f23_wrapup.md)
 - [Fall 2023 winter break wrapup](f23_winter_break.md)
+- [Winter 2024 Wrapup](w24_wrapup.md)
diff --git a/docs/umich/w24_482.md b/docs/umich/w24_482.md
new file mode 100644
index 0000000..5fb6d2b
--- /dev/null
+++ b/docs/umich/w24_482.md
@@ -0,0 +1,356 @@
+# Winter 2024 Course Review: EECS 482 (4 credit)
+
+2024-04-30
+
+Course Title: Introduction to Operating Systems
+
+Rating: 4/5
+
+## Instructor (Brian Noble)
+
+Pros:
+
+- Talks clearly
+- Has a schedule
+- Lots of interesting stories so you learn something even if you fail 482
+  (see [Trivia](#trivia)
+
+Cons:
+
+- Practically none?
+
+## What did I learn?
+
+Course topics:
+
+- Threads and concurrency
+    - Mutexes & condition variables
+    - Semaphores
+    - CPU scheduling
+- Virtual memory
+    - Address spaces
+    - Page tables
+    - Page replacement (swapping)
+- Filesystems
+    - inodes
+    - Consistency after crashing
+- Network
+    - Sockets
+    - Client-server model
+    - Distributed systems
+- Miscellaneous
+    - RAID
+    - LFS (log-structured filesystem)
+
+Brian constantly brought up the five tools of computer science:
+
+1. Caching
+2. Hashing
+3. Indirection
+4. Replication
+5. Encryption
+
+482 discusses 1 and 3 in great detail, 2 and 4 occasionally. The
+philosophical takeaway is:
+
+- Whenever you have something to protect, add a layer of indirection (e.g.
+  using virtual addresses for user programs)
+- If there's too much data to copy, also use indirection
+- It can't be indirection all the way down; there must be something fixed
+  by convention (e.g. the first sector being the bootloader)
+- If indirection gets slow, add caching
+- If you want consistency, use replication (e.g. RAID with redundancy)
+
+The course is all about abstraction:
+
+- Threads are abstractions for CPUs
+- Virtual memory is an abstraction for physical memory
+- Filesystems are abstractions for disks
+- Sockets are abstractions for network interfaces
+
+Part of abstraction design is to provide user programs with the illusion
+that resource is infinite. A process can spawn thousands of threads on an
+8-core machine, and they take turns to execute, thanks to the OS
+scheduler. Of course, at some point the context switching overhead
+overshadows the benefits of parallelism, but you _could_.
+
+Another job of the OS is to protect a program from other programs. You
+can't trust user programs. Therefore you must build a layer of abstraction
+so that the user program can never "control" the machine. The three things
+a user program is allowed to do:
+
+- Touch its own property, e.g. address space, open files
+- Touch property that another process explicitly shared with it
+- Transfer control back to the OS with a syscall
+
+The point is that the OS is an absolute tyrant. A user program can never
+run for as long as it likes, nor can it touch anything other than what
+it's explicitly allowed to. To achieve this, the OS conspires with the
+hardware so that it can intervene when certain things happen:
+
+- Every few milliseconds, the timer interrupt fires, transferring control
+  over the CPU to the OS
+- The program issues a load/store marked unreadable/unwritable, and the
+  MMU triggers a page fault, also handled by the OS
+
+Although the timer and the MMU are technically part of hardware, they
+always hand over control to the OS. They're part of the abstraction.
+Without the timer, it would be up to a user program to give up the CPU,
+which makes it really easy to freeze a machine. Without the MMU, user
+programs would use direct addressing, enabling anyone to tamper with
+anyone's memory.
+
+However, the OS can bypass either restriction, and it is the only one
+allowed to do so. When a timer interrupt fires and hands control over to
+the OS, the first thing the OS does is to disable the interrupt, so the OS
+itself gets to run for as long as it likes. Once its job is done, it
+re-enables the interrupt, and hands control back to a user program (may
+not be the same one). We don't give user programs the ability to control
+interrupts; not MMU either.
+
+We just discussed the first half of the course. The second half was less
+mind-bending and more optimization trickery with "make the common case
+fast" heuristics. However we did make a big deal about consistency.
+
+The disk only guarantees block writes are atomic. Therefore, if you need
+to write two blocks to disk and you lose power halfway, you could have
+written zero, one, or two blocks. That basically means you just lost two
+blocks of data, because you're unsure either block is the right version.
+Worst case is you end up breaking essential metadata, which corrupts the
+entire filesystem.
+
+We can play clever tricks like careful ordering of block writes so the
+last block we write "commits" the changes. But when this is not possible,
+due to cyclical dependencies, we came up with the notion of journaling,
+which doubles the cost of writes because we always keep a copy of the data
+we're writing in the journal until we're sure these data made it where
+they belong. Where is the journal? On disk. At this point I was convinced
+that disks just suck. We're paying 100% overhead just to handle the 0.001%
+chance that the machine crashes. But to deliver the "persistent storage"
+promise, we have to pay that cost.
+
+The disk is just a big pool of zeroes and ones — and as such there is no
+way to distinguish a block of metadata and a block of data. You have to
+allocate a static location as the "boss of metadata"; for example, writing
+the root inode to block 0, from which we can discover every descendent, as
+we did in project 4.
+
+### Personal reflections
+
+The reason why I enrolled in the course is all my friends did it. It was
+taught by Manuel, one of the "signature" professors we had at JI,
+Shanghai. It's one of the most challenging courses there ever was, so
+being the arrogant boy, I took it. Peer pressure except it was me who
+pressured myself into taking it.
+
+The most mind-blowing chapter, also the one I once had the most incorrect
+understanding about, is virtual memory.
+
+Rewind to 2021, when I was taking VG151, intro to CS. I had no idea what
+virtual memory was, and was amazed that `malloc` always handed me roughly
+the same address every time, beginning with `0x7fff` or something, as if
+that part of the RAM was always free. I had mistakenly thought that all
+processes share one big heap on the physical memory, and `malloc` had
+a global table of free chunks. It does not. Each process has its own
+address space, and the user program does not know, nor does it care, where
+it lives on physical memory.
+
+The MMU also explains a gap in my brain. Prior to this course, I thought
+the OS would translate memory addresses of a program before it ran (which
+is not possible because you can dynamically allocate memory). Now it
+became clear that there is a dedicated piece of hardware that does the
+translation.
+
+## Projects
+
+Project 1 is solo, 2-4 are done in a group of two or three; mine was
+three. We were enrolled in the 4-credit version of 482, which means we're
+only required to do the core version, which is supposedly less work.
+
+We met Mondays and/or Wednesday mornings at 10 AM at the Duderstadt. It
+was a great excuse to spend money on muffins and coffee at the cafe.
+Nearly every time we sat at the same table with a giant screen. There was
+an HDMI cable but it doesn't work. I ended up opening a Zoom meeting.
+
+Of the three autograders I've used at UMich, this is the least visually
+interesting one, besides only allowing one submit per day with feedback,
+plus three bonus submissions for each project.
+
+![Plain HTML website titled "Project
+4 submission"](img/w24_wrapup/482_submission.png)
+
+It does fit in the brutalist aesthetic of the website.
+
+![Plain HTML website with very little CSS and an embedded google
+calendar](img/w24_wrapup/482_website.png)
+
+### Project 1: Multithreaded disk scheduler
+
+Given mutexes and condition variables, build a disk scheduler.
+
+Not that hard, took me a few tries to get used to the paradigm of
+signaling _after_ work is done.
+
+### Project 2: Thread library
+
+We built our own threads, mutexes, and condition variables. We also get to
+decide what happens in a timer interrupt.
+
+The hardest part was taking care of all the `ucontext_t` objects, which
+can't be moved because they contain pointers to themselves. We had trouble
+keeping track of which stacks and which `ucontext_t`s we could delete,
+because the lifetime of the `thread` object is unrelated to that of the
+thread's execution flow. We ended up playing pointer tricks, which is
+basically shared pointers with extra steps.
+
+Here is a snippet of code I wrote at 2024-02-20 00:30:
+
+```
+void thread::delete_context(ucontext_t *context) {
+	auto it = cpu::self()->stacks.find(context);
+	assert(it != cpu::self()->stacks.end());
+	// delete stack of thread that previously died
+	// like burying your sibling's bones
+	// pour one out for the binary spirits
+	// freed from deallocated homes
+	delete[] cpu::self()->stack_to_delete;
+	// we cannot simply delete the stack
+	// of the thread that is running
+	// for a ghastly segfault taketh us aback
+	// with a coredump equally alarming
+	cpu::self()->stack_to_delete = it->second;
+	cpu::self()->stacks.erase(it);
+	delete context;
+}
+```
+
+Another design mistake is how we used the `ucontext_t` pointer in the
+mutex as a unique identifier for threads. It turns out the instructors
+were so cunning that they managed to make our library allocate
+a `ucontext_t` exactly where one was just deleted, tricking our library
+into thinking the new thread owned the mutex. I still have a hard time
+believing it was possible. They probably overloaded `operator new` on
+a modded version of `ucontext_t`.
+
+I was very involved in project 2; I wrote more than half of the code, and
+thus knew it like the back of my hand.
+
+### Project 3
+
+Virtual memory pager. Manages memory address translation, paging, and
+swapping. Lots of data structures needed, even a state diagram.
+
+I grossly underestimated the complexity. The first time I read the specs,
+I was like, "pfft! single level page tables?" But it was the hardest
+project for me.
+
+Unlike project 2, project 3 had much less effort from me. All I did was
+draw the state diagram and propose the data structures and their names.
+Then I got consumed by 373 and the workload shifted to Samuel who
+basically did it all on his own. Therefore I don't understand it as
+thoroughly as project 2. By the end of project 3 I was completely lost.
+
+The data structures were a complete mess. Here is a list of structs we
+defined:
+
+- `shadow_table_entry_t`
+- `filename_block_t`
+- `page_occupant_t`
+- `file_occupant_t`
+- `swap_occupant_t`
+- `page_status_t`
+
+which are distinct and redundant in a chaotic way. It's a miracle we
+passed all the test cases.
+
+The lack of involvement resulted in a relatively poor understanding of the
+pager, so I devoted more energy to project 4.
+
+### Project 4
+
+Network filesystem. Listens on a TCP port and handles concurrent
+read/write/create/delete requests from clients.
+
+I think I did a pretty good job at factoring out just the redundant code
+while handling special cases in respective functions. Fortunately we just
+have four request types (endpoints) to handle, so a little redundancy is
+ok.
+
+My least favorite part of this project is how strictly we had to enforce
+the one request string format. The request string is delimited with _one
+space_. No leading or trailing whitespace. All this while claiming that
+parsing is "is amenable for processing by `istringstream` (e.g.,
+`operator>>`)". My sibling in heaven, `istringstream` is not the one you
+want if whitespace is significant. I ended up using regexes, because it's
+preferable to having to read one character at a time while constantly
+checking whether you've exhausted the string stream. I regret nothing.
+
+Project 4 was the first time I actually used RAII in a productive way.
+Because every filesystem access is a traversal down a tree, and we want to
+prevent race conditions, every descent requires that we grab a lock and
+release a lock. Some are reader locks and some are writer locks. This is
+cumbersome to manage manually, so I wrote an RAII wrapper that keeps track
+of what locks we are currently holding and what type of locks they are. At
+the end of the object lifetime, the destructor simply goes over the list
+and unlocks them one by one. If we call a function that needs to
+lock/unlock, we simply pass the wrapper by reference. Easy!
+
+I'm not sure if this is healthy, but I cringe whenever someone optimizes
+code to "fit the scenario at hand". In the early stage of the project,
+I wrote a function called `alloc_block()`, which takes void and returns
+the block number just taken out of a pool. Later we realized that if an
+operation needs two allocs, but failed in between, then the first one
+would never be freed. We thought it would be better if we could atomically
+alloc two blocks, so I suggested my teammate to generalize the function to
+take one optional parameter and return potentially more than one block.
+
+When the function was reimplemented, I found that it was not quite what
+I meant. I was thinking something along the lines of
+
+```
+std::vector<uint32_t> alloc_block(uint32_t count = 1);
+```
+
+What it ended up being was
+
+```
+std::pair<uint32_t, uint32_t> alloc_block(uint32_t count = 1);
+```
+
+which returns the allocated block # in the _second_ element of the pair if
+`count == 1` (because it kinda fits our semantics better), and returns two
+valid block #s if `count != 1`.
+
+I feel uncomfortable that `count` did not function as advertised; it
+behaved more like a bool. But since we're using our late days (it's the
+first time I ever used a late day) and we're tired, I let it slide.
+
+## Verdict
+
+Now that I've taken the course, done the projects and sit through the
+exams, I do not regret taking this course. I do, however, regret taking it
+with two more workload EECS courses, one of which (373) is also
+heavy-workload.
+
+I would recommend Brian Noble to anyone, no questions asked. He is my GOAT
+professor of the semester. The slides follow the
+motivation-solution-problem-remedy train, which tightly model the actual
+evolution of real systems in the e.g. 1980s. It's interesting to know what
+came before modern systems and what Linus Torvalds et al. needed to take
+care of when they crafted the revolutionary kernel.
+
+## Trivia
+
+Brian always has stories to tell. My favorite story is how when he was
+young, his advisor talked to him about his unnecessarily complex wording
+in his paper. I personally do believe the doctrine, "why many word when
+few word do trick".
+
+Later on a lecture on log-based filesystems, he had a callback to the
+story. He goes (paraphrased):
+
+> What I lament about project 2 is, the right way to identify who owns the
+> mutex is to add something to your data structure. But you never do that.
+> What you do is you add another map. So what you end up with a lot of
+> suprooflo- su- sur- (waves hand) I can't say it. Uhh… extra. My advisor
+> would be happy about that. Extra maps.
diff --git a/docs/umich/w24_wrapup.md b/docs/umich/w24_wrapup.md
new file mode 100644
index 0000000..0f4baf7
--- /dev/null
+++ b/docs/umich/w24_wrapup.md
@@ -0,0 +1,16 @@
+# Winter 2024 wrapup
+
+2024-04-30
+
+My second semester at UMich is just over, and I will recount major things
+that happened. I will continuously update this blogpost.
+
+## Course reviews
+
+The biggest mistake that I made is that I elected three EECS courses, two
+of which are extra heavy in workload. The rest are not trivial either. It
+is impossible to cover all of them in one single blogpost, so I will split
+them up into individual articles, listed below.
+
+- [EECS 482, Intro to OS](w24_482.md)
+- Other courses WIP