Synchronization 5: Pulling it together

Overview

This is the last lecture.

WeensyDB internals

Hash table
Hash function: bucket number = first character of key

`dbmap` API

db.bucket(KEY)
- Return bucket number containing KEY
db.bbegin(B), db.bend(B)
- Iterators to beginning and end of bucket B
db.bfind(B, KEY)
- Return iterator to item with key KEY
db.binsert(B, KEY)
- Insert new item with key KEY, return iterator to it
db.berase(B, IT)
- Erase item *IT

Synchronization issues

Parallelism
- Only one client can access the database at a time
Data races
- Multiple threads can conflict on concurrent memory access
Lock granularity
- Unnecessarily strict locking reduces parallelism
Denial of service
- A misbehaving client can block out all other clients indefinitely
Deadlock
- Circular locking: a client block itself (and all other clients)
- Lock ordering
Resource exhaustion
- Too many clients can crash the server

Let’s talk about a deadlock-based denial of service

HotCRP

USENIX Security ’22 home page

Submission form

Example submission form

Format checking

Analyze PDF for problems
PDF analysis is expensive, so do it in background helper processes

Example submission form with format checking error

Format checker code

        $banal_run = "command line to run format checker on $filename";
        $tstart = microtime(true);
        $banal_proc = proc_open($banal_run, [1 => ["pipe", "w"], 2 => ["pipe", "w"]], $pipes, SiteLoader::$root, $env);
        // read stderr first -- if there are warnings, we must or banal might
        // block forever!
        $this->banal_stderr = stream_get_contents($pipes[2]);
        $this->banal_stdout = stream_get_contents($pipes[1]);
        fclose($pipes[1]);
        fclose($pipes[2]);
        $this->banal_status = proc_close($banal_proc);

Attack

paper.pdf, 45,622,148 bytes, 4,512 pages

Output

Think for 7 seconds, then

{
  "at": 1764786794,
  "papersize": [792,612],
  "margin": [0,0,0,0],
  "bodyfontsize": null,
  "leading": null,
  "columns": 0,
  "pages": [
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"papersize": [6000,4000], "pagetype": "blank"},
    {"papersize": [6000,4000], "pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"papersize": [6000,4000], "pagetype": "blank"},
    {"papersize": [6000,4000], "pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},
    {"papersize": [6000,4000], "pagetype": "blank"},
    {"papersize": [6000,4000], "pagetype": "blank"},
    {"pagetype": "blank"},
    {"pagetype": "blank"},

How is this a deadlock?

        $banal_run = "command line to run format checker on $filename";
        $tstart = microtime(true);
        $banal_proc = proc_open($banal_run, [1 => ["pipe", "w"], 2 => ["pipe", "w"]], $pipes, SiteLoader::$root, $env);
        // read stderr first -- if there are warnings, we must or banal might
        // block forever!
        $this->banal_stderr = stream_get_contents($pipes[2]);
        $this->banal_stdout = stream_get_contents($pipes[1]);
        fclose($pipes[1]);
        fclose($pipes[2]);
        $this->banal_status = proc_close($banal_proc);

How would would you solve the deadlock?

One solution: nonblocking file descriptors

    static function run_command_safely($cmd, $dir, $env) {
        $descriptors = [["file", "/dev/null", "r"], ["pipe", "w"], ["pipe", "w"]];
        $pipes = null;
        $proc = proc_open($cmd, $descriptors, $pipes, $dir, $env);
        stream_set_blocking($pipes[1], false);
        stream_set_blocking($pipes[2], false);
        $stdout = $stderr = "";
        while (!feof($pipes[1]) || !feof($pipes[2])) {
            $x = fread($pipes[1], 32768);
            $y = fread($pipes[2], 32768);
            $stdout .= $x;
            $stderr .= $y;
            if ($x === false || $y === false) {
                break;
            }
            $r = [$pipes[1], $pipes[2]];
            $w = $e = [];
            stream_select($r, $w, $e, 5);
        }
        fclose($pipes[1]);
        fclose($pipes[2]);
        $status = proc_close($proc);
        return [$status, $stdout, $stderr];
    }

In the meantime

Let’s talk about you

What should you do next?

CS 1610: Operating Systems
CS 1650: Data Systems
CS 2620: Distributed Systems
CS 2630: Systems Security
CS 2650: Big Data Systems
CS 1520: Programming Languages
CS 1530: Compilers
CS 1410: Computing Hardware
CS 1480/2480: Design of VLSI Circuits and Systems
CS 1450/2450: Networking at Scale
CS 96: System Design Projects: Machine Learning for Social Impact
CS 1240: Data Structures and Algorithms
CS 1430: Networks
CS 1750: Computer Graphics
CS 1810: Machine Learning
CS 2420: Computing at Scale
CS 2241: Algorithms at the Ends of the Wire (future)

Do you check your work on the grading server?

Grading server runs per repository

What should a commit message contain?

Commit messages by length

Commits by length of subject line

Longest subject line is 526 characters
- phase4 finished. we added support for pipes. general overview is that we used a recursive process where for every command we have the previous pipe's read open (stdin for 1st command) and then make a pipe after it (unless it is the last command). we then make the child, assign fd's properly in the child and close there as appropriate and then do same in parent. this starts all children at the same time, then we run waitpid in the order command's were given, clean up the command struct's, and return status of last command.

There are many ways to be a good software engineer

ImageMagick is a suite of programs for controlling images
Used globally
Written by John Cristy starting in 1987
Git repository goes back to 2009
Top commit messages since then:
- 8464 totally blank
- 3325 ... (three dots)

A sampler

6852511 Wicked Part2 this week. AAAAAAAHHH
faa9902 zombies be like *minecraft zombie sound*
631207b RRAAAAH INDOMITABLE SPIRITTTT
b312815 top 3 most agonizing assignments ive ever experienced as a human
a4770ab phase 4 kidnapped my family.
5718b75 KISS MY BIG BEAUTIFUL A** PHASE 7. WAAAR IS OOOOVER
ce3c3c2 commenting out boundary check like the way you cut estranged partners out of photos

Again

83e3e21 decreasing buffer size again
def613f try again???
f3217c4 try again
427537d fix 1 off error for test 18 to pass again ?
48a17f4 trying rnd stuff again :p
97baed1 test10 try again
5057598 walk w me again
fc168c7 again
3eae78a again again
f75d716 again^3
c37bfa8 again for 19 and 20
c284a2a okay u had a lil error try again
cd07fd9 again
95c5885 again
2841486 again!!
2e92f55 M again
384f027 and not or again lol
2f7f459 walk w me (again)
71f77e3 gets test for extra credit working again
7694758 gets mpn1 working again
120d40e trying large buffer size again
aae7c38 trying large buffer size again
d9876dc test 46 draft again
17e7681 test 46 draft again 2
ee9ab38 test 46 draft again 3
36d7898 test 46 draft again 4
90780d3 test 46 draft again 5
021d241 trying again
668eb04 trying again 2
bb0ee25 trying again 3
957b881 testing 46 again
61318e9 testing 46 again 1
f951d35 trying test28 again
6d0dc8b trying test28 again 2
801b4a5 trying test28 again 3
356bd42 redrafted with comments again
91b0f7c redrafted with comments again 2
1aea815 redrafted with comments again 3

Steady wins the race

3e82278 adding stuff
7d58793 testing
7bb12d8 try again
553a4ca now??
54ef0c5 Revert "now??"
154b8ed please
e6fdcf8 pleek
c8828af pleek again
c10c438 pleek again 2
7719245 Revert "pleek again 2"
a4391e3 Revert "pleek again"
fe58538 Revert "pleek"
6ba3eca Revert "please"
288f0a8 if this works i will be upset
d2b7dc7 retry
b787353 Revert "retry"
4bbac4f Revert "if this works i will be upset"
691d384 my last straw and attempt
7db8f2a Revert "my last straw and attempt"

Relatable

5833687 idk dev/zero ???
a877d8b very sketchy?
5ec77c9 this is now w0orkin????
a47a306 phase 8 git add . zombies dont work now tho???
25116db 8kb cache?
98f03e5 phase 5 actually i think?
ece5a21 phase 4/5? I guess?
67d6d33 should be passing all phases now? committing before fixing up code
582233c I think I've finally got up to phase7 to work? committing to move onto phase8 now
06fa126 phase 5 appears to be working?
5252c27 Complete?
d5abd28 Did I change anything?
a3bf1fa finally done ?
651ee1c finally done??
e22ef53 done????
733a265 done???
646571b done?!?!?
cd7da96 fixed ??
23846b7 Fix?
5633567 Now?
e27cef2 Maybe this is faster?
5438852 finish?
7f8d0a4 almost done?
7bae842 final?:
acd8694 ??
f214b02 ??
64bba79 ?
4cc0b7c ...bad :(

What the flip flops

73b9e68 what the flip flops
    what i dont understand is why didnt this trigger the sanitizer yesterday
    because its not like i got a new computer today or something so in theory
    everything was the same because it was literally also working like 2 hours ago
    when i started working on the next phase and then suddenly stopped working
    without me even restarting docker or anything!! and also why couldnt the
    sanitizer error at least have a stacktrace even when i compiled with debuginfo
    because i thought this was a problem with my new code 🤬😤

🤣

3d882b6 phase 1: I only added one line lol
ba9c0fb something happenedlol
411b2cc Merge branch 'main' of https://github.com/cs61/cs61-f25-psets i need the pset lol
049468d fixed memory mapping lolololololololol
3c997ca phase 3, 4 5 !!!!! i love this sooooo much lolololololololololololoo
fd52927 zombies done lololol
3e3bcc8 forgot static for scope lol
f88fbd7 just added my name lol
d8ea499 trying smt funky for test08 (blindly using std::align...) lol
e6343b4 lol forgot to update values
246a1dd lol u called malloc too early
d1d6ccc lol shadows
0bb0482 nactive lol
6f5edf2 lol
8fa3c09 brackets lol
384f027 and not or again lol
5ed140b okay don't do that lol
ee13624 setup is basically a constructor lol
c1fa388 multicache but it doesn't work lol
e199376 removed debug printfs but kept clarifying comments. check last commit to see all the debug prints i had to do lol
95423e5 phase 4 lol
71a84e3 phase 5 lol
e2b92ac added a comment lol
459e516 ok a different 63/65 are working loll
c69a690 actually finished phase 2 lol
b294886 lol
89e2e58 lol

𝔉, 𝓢

cf4c37a process isolation done! phase 2 done! won't skip phases from now on because combining it with kalloc of pages really 𝔉ed me over... bwahaha
94260a6 𝔉!
a15f09c same 𝓢 but diff

LFG

311c024 phase 5 LFG
d69a72c LFGGGGG 65/65 TESTS PASSED
748f87d alignment success! on to wild writes lfg
dde67ec wait...that's it for phase 2? Lfg bb
799c6c9 finish all phases (lfg)
0c6743b l..fg? lfg? ig??

Delightful tools

b21fe0d ai generated phase 3 lol
d407165 chat infused redirect helpers after pipe didn't work
9bb3c35 annoying vscode thing, nothing relevant
419693c WHY IS VSCODE TWEAKING

89454ec Merge branch 'main' of https://github.com/cs61/cs61-f25-psets merge :wq# the commit.
26a3a30 phase1 :wq

09f035d Merge branch 'main' of github.com:cs61/cs61-f25-psets-XXX # Please enter a commit message to explain why this merge is necessary, # especially if it merges an updated upstream into a topic branch. # # Lines starting with '#' will be ignored, and an empty message aborts # the commit.
f882518 Merge branch 'main' of https://github.com/cs61/cs61-f25-psets # Please enter a commit message to explain why this merge is necessary, # especially if it merges an updated upstream into a topic branch. # # Lines starting with '#' will be ignored, and an empty message aborts # the commit.
e8c8ca8 Merge branch 'main' of https://github.com/cs61/cs61-f25-psets # Please enter a commit message to explain why this merge is necessary, # especially if it merges an updated upstream into a topic branch. # # Lines starting with '#' will be ignored, and an empty message aborts # the commit.

a3a47bd bug foundgit add . gotta make sure you only zero out the pages when the refcount is truly 0, not every time free is called
06b9c26 tests completegit add .
ba4055a DONE WITH ALL PHASESgit add .git add .git add .!
4590798 phase 2 workinggit add .git add .
bb3cca1 WE MIGHT BE DONE git add .git add .!
6bd466b comments and formattinggit add .
bf9d178 phase 8git status
50bdfe4 phase 5 worksgit status
146e5b2 Phase 5 is done thanks to lecturegit add .!
499e2c9 Phase 5 is done thanks to lecturegit add .!
8fe10fb Phase 5 is done thanks to lecturegit add .!
5ba91c6 all donegit add .
1d56df5 Passed Phase 1git add .
da6e56a PHASE 8git add -A!
d0943d5 phase 7git add -Agit add -A
9ec6466 WAHOOgit add -Agit add -A! PHASE 4git add -Agit add -A!
6ae39ae phase 3git add -A!
9a8ee54 pass cd checksgit add .
44880d2 p4git push
7aa4c43 PSETDONEgit add .LFG
8fe10fb Phase 5 is done thanks to lecturegit add .!
5ba91c6 all donegit add .
1d56df5 Passed Phase 1git add .
da6e56a PHASE 8git add -A!
d0943d5 phase 7git add -Agit add -A
9ec6466 WAHOOgit add -Agit add -A! PHASE 4git add -Agit add -A!
6ae39ae phase 3git add -A!
3b59fd0 phase 8git add pset5/AUTHORS.md
9a8ee54 pass cd checksgit add .
44880d2 p4git push
7aa4c43 PSETDONEgit add .LFG
9014683 330am phase 2git add . <3
ec7153b ALL TESTS PASSED + COMMENTS git push origin main ! :)
ad4c4f2 ALL TESTS PASSEDgit add .
5181de4 phase 8git add . yay!
64bc7bf all tests passedgit add .
a47a306 phase 8 git add . zombies dont work now tho???

Signoff

-s, --signoff

Add a Signed-off-by trailer by the committer at the end of the commit log message. The meaning of a signoff depends on the project to which you’re committing. For example, it may certify that the committer has the rights to submit the work under the project’s license or agrees to some contributor representation, such as a Developer Certificate of Origin. (See https://developercertificate.org for the one used by the Linux kernel and Git projects.) Consult the documentation or leadership of the project to which you’re contributing to understand how the signoffs are used in that project.

568c64a appenderr extra credit
    Signed-off-by: Student McStudent <student@studentstudent.com>

4181c2b actually respond to feedback

76fd7b0 add kill syscall
    Most of this code is copied from forking. pretty similar syscalls
    afterall.
    
    Signed-off-by: Student McStudent <student@studentstudent.com>

52ab174 respond to pset 4 feedback

a4f61c7 phase 1

e00308f add append redirections
    EC
    
    Signed-off-by: Student McStudent <student@studentstudent.com>

34d4d3a environment variables extra credit
    Signed-off-by: Student McStudent <student@studentstudent.com>

c350410 final cleanup I think
    Signed-off-by: Student McStudent <student@studentstudent.com>

Location tracking

e2da7ce i went to valhalla
b2129dc i went to valhalla twice
987eb9c i went to valhalla twice
8f7c0c1 i went to valhalla
e2636eb i went to valhalla
d012ee7 not sure how serious these notes are supposed to be
fc4b6a1 I deadah basically restarted
69465df for future me
890b486 test
8a4988b i in florida
315767a Back in Bos

Self-love

4362b08 a;eofij;awoifj
d6615f7 fawjef
f3e902d lala
cfa7449 slight update, so afriad of breaking things asdhjajd
14e614f phase 4 working but ugly, need to push before I break it asdhjahskdj
ec55717 asd

8ccd176 losing my mind
091abd3 losing my mind
e5b92d0 losing my mind
f9cddb7 losing my mind

c5ec43c revert
94fdf78 bruh idk
986fca4 bruh
d34f62e fix maybe
18e634b ruigfi
903820e help
89e2e58 lol
82bfec2 ckeanup
b790a2f revert
e98d306 BROKED

ba9c0fb something happenedlol
e4dae2a i did something with section code
e1fe47f yay everything works but is very slowowowowo
a634362 okay bruh so reverse order should be fast but bruh i dont want to do this anymore lowkey like bruh
07123b0 we go sonic speed now

471f250 Add checks of Tagger functionality. Some fail atm because idiot.
a2bbbb6 𝔉ing idiot
a036a76 Fix response-round bug. 𝔉ing case syntax idiot.
1b7769b 𝔉ing idiot
3a51f7c Shut up, idiot
6cd7a24 𝔉ing idiot
5f7d4b1 Hey, idiot, stop spamming moi
f644af2 Derpty derpty flipped the meaning like an idiot
2b8d1f7 de-idiot
bf58fb2 Wow, what the hell, how did this ever work.
5454641 Dear idiot, correct signature
83d350b Dear idiot moron, please get the direction of comment anonymity correct.

dd56532 Hyperderp
84e8820 Derpderp
2072e3d Dederp
8ecc6ac Type derp
0055818 Fix derpo.
c24691f Fix hyperderp in wstorage.site_key: Include siteinfo.base if it is nontrivial.
f60c464 Fix derpo in new optgroup style.
9c53e38 Hyperderp
f841e3c Updates to required score fields and dropdowns.
b105a75 Herpsy derpsy doodle
41401e3 Automatic tag derpo.
4b352c2 Fix derpo with double-quoted topic names.
4f9663c Fix a derpo.
fe8d800 Fix test derp.
a9ae96b Message derp.
d6f98e6 derpsy doodle
78e582e Procrastination derplet.
4ca2f9c Dederp
da4a70d derpo
91302b0 derp
882c752 derp
efcf74f derp
83d2992 Welcome 2 derptown
f5536f9 Hyperderp
f41d737 Herpty derpty doo
a958f00 Fixaderp
d6144bd Derp rederp
931708a Derp rederp
11e8911 Wow, derp city
13ffbc1 Longer titles because derp
7ed0500 Some derps
4c464cd Herpty derpty doo
6c8f753 Agh derp: Fix JS-generated links to incomplete reviews
f1fc019 derp
6ba68f2 Fix derp (Nic Lane)
d332c96 De-@, and thereby fixaderp
00196c5 Add a separate message if deadline for updating final versions passes
7ebbc2c Fix derps.
18e1801 derpderpderpderp
85d10ac derpderpderp
95ccabb derpderp
c577425 derp
5467843 Miniderp
6265a6c derplet
12aee93 derp
22b353e Another derp
1917fd1 morederp
1eab47e Fix derp, thanks Michele Nelson
c1fa4ca Compare-and-swap(x, x) should succeed immediately, derp
f644af2 Derpty derpty flipped the meaning like an idiot
19e3c6a Fix popup on scrolled window, derp.
e0afe66 Daderpderp daderp daderpderpderp
6e5eda1 Rederp
b3a4a83 Agh derp
950d420 Fix word wrap, derp, and add tests.
ebb1b5a Typoderp
855518b Don't error on deleting comment derp.
b0d3ee2 Miniderp
1de47e7 Ugh, derp
079d58c No more derple quotes
ce492ec Another derp
b37ec80 Some derps
fee9463 Helpoderp
3946e41 Fix sort derp
44c9936 Uninitialized derp
3b857d6 Autoassignment fold derp: showed both 'Override conflicts' + user
9d2abe3 Major derp: If Apache, need to require_once navigation.
bd36caa Json derp: Correct encode/decode_escape for preg_replace_callback.
54a545f Set ConfSitePATH, not Base, derp.
caea084 Another crashderp
4463529 Onready derp
11356f9 Dederp
ce8982c derp
f4c561a Minor derp
a7493bc HTML derp
58a607e Rederp
d195cc0 Derp derp derp derp
229f24f Fixaderp
9297b71 Miniderp
f17b575 Triple salchow derp
6f154c6 Double plus derp
28f10a8 Rederp
ebe512f Miniderp
067bd62 Style derplet.
93a1a95 Derp derp
e59bd30 Derp & derp
4d6ec0f Derp derp
564db1a Derpderp
fb1ba26 Derp derp
d0a14f6 Syntax derp
946593a Herp, derp

Hooray!

6ddc69b finished yay
110bdb8 phase 1 yay
244a7cc yay!!!! no more failed tests or timeouts
684dd88 YAY WE ARE DONE
e60ad1b phase 4 is pretty yay
76d0a33 yay finally no errors
ab7bb29 DONE YAY!
34bf833 done with pset 0 and adding code. YAY
c41ca4d test 1-17. Yay!
c0dd7ee YAY PHASE 5
8bc996e done! yay!
ec548b0 phase 5 done!!! yay
5181de4 phase 8git add . yay!
26b0f22 Phase 1-3 Complete YAYAYAYS
e1fe47f yay everything works but is very slowowowowo
c750246 yay
1eefb26 WOOHOO WE ARE DONE AND INFO IS FILLED IN
5e8ea8b PHASE 3 WOOO
b5158b9 did phase 7 woohoo
327ec86 fix timeout tests. hooray. phase 3 done!
15606ea phase 5 hooray! not too bad Giving more space to each process's heap
2483f01 phase 3 hooray!
33b8106 free from test 28 hooray

Thank you for taking the class

Heart pulse