Problem set 6: Flockchain
In this problem set, you’ll implement synchronization for your buffered I/O library.
- Due Thursday 12/3 at 11:59pm EST, but you can have an extension until 12/9.
Get the code
Start with the cs61-psets Git repository you used for Problem Set
5 and run git pull --no-rebase handout main to
merge our code, which is in the pset6 subdirectory, with
your previous work. If you have any “conflicts” from Problem Set 5, resolve
them before continuing further. Run git push to save your
work back to GitHub.
Goal
Your IO61 library from Problem Set 5 works great (hopefully) for
single-threaded processes—congratulations! Unfortunately, it does not work
well for multi-threaded processes. When two threads in the same process try to
read from or write to the same io61_file, those threads will cause data
races and undefined behavior.
In this problem set, we provide you with a new IO61 library—a single-slot cache—that you will modify to:
- Add support for file range locks, or “flocks” for short. A flock allows a thread to lock a specific range of bytes within a file.
- Implement thread safety for all operations.
Crypto crypto crypto
Famous billionaire Scam Bilkman-Fleed runs a high-frequency crypto trading
exchange. Our handout code contains accounts.fdb, an example of the kind of
account database used in his exchange:
SBF 1002034
Alameda 291573
FTX 52180
Aaliyah 3193
Aaron 650
Abel 3351
Abigail 2510
Abraham 5635
Ace 8555
...
Each line contains the account owner’s name, one or more spaces, and then the balance, and must be exactly 16 characters long (including the terminating newline).
Scam’s trading platform runs in a single multithreaded process. (See
ftxunlocked.cc.) To make a trade, a worker thread:
- Picks two accounts to trade using a proprietary Liquidity Engine (i.e., a random number generator).
- Reads the accounts’ current balances using positioned I/O calls in the IO61 library.
- Transfers money from one account to the other.
- Writes the accounts’ new balances back to the underlying file, again using positioned I/O.
Then it repeats. All of these trades just move money between accounts, so the total amount of money in the exchange should remain constant.
Unfortunately, ftxunlocked.cc is unsynchronized and doesn’t work. You can
see this by running ./ftxunlocked; ./diff-ftxdb.pl (shown below). The ./diff-ftxdb.pl
script checks that two account files (by default accounts.fdb, the original
database, and /tmp/newaccounts.fdb, the modified database) have the same accounts
and the same total assets. ./ftxunlocked violates this assumption:
$ make TSAN=0
$ ./ftxunlocked; ./diff-ftxdb.pl
[0;31m/tmp/newaccounts.fdb:[01;31m Incorrect exchange total 4017050[m
[0;31maccounts.fdb: Expected 4000000[m
Note that we disabled the thread sanitizer to show this result. By default, make has the thread sanitizer enabled. If you make and run the above programs, you will see that the thread sanitizer detects this data race, which is pretty helpful for debugging!
Your work
All your code for this pset will go in io61.cc, though you should
look at some of the other files to see what’s going on—especially ftxdb.hh
and ftxxfer.cc.
In Phases 1–3, you will change the struct io61_file definition and the
io61_lock, io61_try_lock, and io61_unlock functions. In Phase 4, you
will change many of the IO61 functions.
Each phase description says which tests check that phase, such as
make check-lock check-xfer for Phase 1. You can also run the ftx programs
directly at a command shell.
By default, make compiles with the thread sanitizer and undefined behavior sanitizer enabled. These are incredibly helpful for debugging, but compiling with sanitizers does slow down your program. As you work through each phase of the problem set, we recommend that you first compile with sanitizers enabled (make). Once your code is correct (correct output, no data races, and no undefined behavior), you can disable the sanitizers (make SAN=0) and run again for a better sense of your program's runtime.
Docker can slow down your program, too. You might try running your code locally, or on the grading server (ideally at a time when few other students are also submitting to the grading server.)
You should commit your code after each phase to save your work!
Testing
Pset 6 uses the same test framework as Problem Set 5. Each test
is a C++ program that uses io61_tester, declared in
iotest.hh. A
test creates an account database, runs a command that uses the ftx
programs, and checks the results. For example:
int main(int argc, char* argv[]) {
io61_tester t(argc, argv);
t.accounts_file("accounts.fdb", 512);
t.run("ftxxfer -n 2000 accounts.fdb new.fdb");
t.check_accounts("accounts.fdb", "new.fdb");
}
This test creates a 512-account database, accounts.fdb, and runs ftxxfer,
which copies accounts.fdb to new.fdb and then performs 2,000 transfers in
each of 4 threads. t.check_accounts then checks that new.fdb has the same
accounts and the same total balance as accounts.fdb, much like
./diff-ftxdb.pl. (All the ftx programs take optional arguments that name
the original database and the copy to modify; without them, they use
accounts.fdb and /tmp/newaccounts.fdb.) The tester also fails a test if
the command exits with a nonzero status, crashes, causes a sanitizer error, or
runs longer than its time limit (30 seconds unless the test calls
t.set_time_limit).
Tests live in the t/, tt/, and torture/ subdirectories, one test per
file. Each test is named after the phase it checks:
| Phase | Tests | What they check |
|---|---|---|
| 1 | lock, xfer |
Locks exclude overlapping locks; ftxxfer is correct |
| 2 | fine, rocket |
Locks on distant ranges don’t exclude each other; ftxrocket is correct |
| 3 | blocking |
Threads waiting for a lock block, rather than poll |
| 4 | chain, audit, big |
io61_write, io61_writec, and io61_read are thread-safe; ftxxfer works on databases larger than the cache |
| — | perf |
Performance |
The lock, fine, and blocking tests use the
ftxlocktest
program, which calls io61_lock, io61_try_lock, and io61_unlock
directly. The audit tests use
ftxaudit,
which reads a ledger from many threads at once with io61_read.
To build and run tests, use make check-NAME, which runs
every test in t/, tt/, and torture/ whose name starts with
NAME. For example, make check-lock runs the lock tests, and make check-xfer-001 runs just one test. make check runs all the tests in t/
and torture/, in phase order, stopping at the first failure. You can also
run a built test directly, as in t/xfer-001. A test that passes prints
nothing (unless it reports timing); a test that fails says why:
$ t/xfer-001
xfer-001 FAILED: new.fdb is incorrect
new.fdb: incorrect exchange total 2504001, expected 2503468
--- command
ftxxfer -n 2000 accounts.fdb new.fdb
--- stdout (empty)
--- stderr
4 threads, 8000 operations, 0.011699s CPU time, 0.011994s real time
(Run with `-d DIR` to keep the command's files.)
Each test runs its command in its own directory, which is removed when the
test exits. To see the command’s files after a test runs, give the test an
existing directory to use instead, as in t/xfer-001 -d mydir.
Performance tests call t.report_timing() after checking their results.
This runs the command again and prints how long it took, in real time and in
CPU time:
$ t/perf-001
perf-001: 1.0622s real time, 1.9574s CPU time (27 MiB)
Sanitizers slow programs down a lot, so use make SAN=0 check-perf to measure
performance. Timing varies from run to run; to time several runs and report
the median, set TRIALS, as in TRIALS=5 t/perf-001.
The handout includes our torture tests, in torture/, as well as the tests
in t/. You can add your own tests to t/ or tt/; see the README.md file
in each directory.
Phase 1: Coarse-grained file range locks
ftxxfer.cc
attempts to transfer money safely, even in multithreaded situations, by
locking accounts before making transfers. These locks are implemented as
file range locks, which are like mutexes for a specific range of offsets
in a file. Before performing a transfer, ftxxfer.cc locks the file ranges
corresponding to the two relevant accounts; this should prevent concurrent
access to the accounts involved in the transfer. Unfortunately, the library
calls that implement file range locks are currently unimplemented! In this
phase you will implement them.
IO61 file range locks use these function calls:
int io61_try_lock(io61_file* f, off_t off, off_t len, int locktype)-
Try to obtain a range lock for offsets [
off,off + len) of filef. Return0if the range lock was obtained, and-1(witherrnoset toEAGAIN) if it could not be obtained. This function does not block; if a range lock is already held overlapping that range, it returns-1right away. In the pset, thelocktypeargument is alwaysLOCK_EXto signify an exclusive lock. int io61_lock(io61_file* f, off_t off, off_t len, int locktype)-
Like
io61_try_lock, but retry the range lock until it is obtained. Return0on success. (Your solution will likely always return0, but if you implement additional error detection, serious errors may causeio61_lockto return-1.) int io61_unlock(io61_file* f, off_t off, off_t len)-
Unlock the current thread’s range lock for offsets [
off,off + len) of filefand return0. It is undefined behavior if this thread doesn’t hold a lock on that specific range.
In Phase 1, implement these functions using a single std::recursive_mutex
per file. A std::recursive_mutex is required because ftxxfer.cc locks both
accounts involved in the transfer.
You will also need to fix one data race in io61_pwrite, on the line that sets
f->dirty = true; you can use the same std::recursive_mutex for this, or,
even simpler, give the dirty member an atomic type.
This should make ./ftxxfer; ./diff-ftxdb.pl report no
errors—though it may take a long time, especially in Docker. You will improve the runtime in the next few phases. Test your work with sanitizers (make) to check for data races. When make check-lock check-xfer passes, move on to the next phase.
$ make clean
$ make
$ make check-lock check-xfer
t/lock-001 passed
torture/lock-901 passed
torture/lock-902 passed
torture/lock-903 passed
t/xfer-001 passed
torture/xfer-901 passed
torture/xfer-902 passed
torture/xfer-903 passed
$ ./ftxxfer && ./diff-ftxdb.pl
4 threads, 400000 operations, 0.681209s CPU time, 2.484973s real time
[01;32m/tmp/newaccounts.fdb OK[m
$ ../cs61-run-docker
cs61-user@aea282d44262:~/cs61-psets/pset6$ make clean
cs61-user@aea282d44262:~/cs61-psets/pset6$ make && ./ftxxfer && ./diff-ftxdb.pl
...
4 threads, 400000 operations, 6.199521s CPU time, 44.704464s real time
[01;32m/tmp/newaccounts.fdb OK[m
Notes on file range locks
File range locks are advisory, as opposed to mandatory, with respect to the underlying file data. This means that holding a lock on a range of offsets does not prevent other threads from reading or writing that range! For instance, a rogue thread can
io61_writea locked range without acquiring the lock. File range locks provide correct synchronization only when all threads use them. This resembles the way thatstd::mutexworks. Locking a mutex does not prevent other threads from accessing the protected data—synchronization is correct only when all threads use the mutex correctly.The
offandlenarguments must be ≥0. Iflen == 0, the requested range is empty, and any attempt to lock or unlock the range succeeds (returns0) without making any changes.Actual operating systems support process-based file locks and file range locks with a similar API. That is, at most one process can acquire a lock on a particular range. On Unix variants,
flockmanages file locks andfcntl’sF_SETLK/F_SETLKWcommand manages file range locks; on Windows,LockFilemanages file and file range locks. Unix’s file locks are purely advisory (normalreadandwritesystem calls ignore locks). In Windows, file locks are semi-advisory: they prevent normal reads and writes, but notmmap.
Phase 2: Fine-grained file range locks
Your coarse-grained file range lock implementation provides correctness, but
it reduces performance by restricting parallelism: only one transfer can ever
proceed at a time. Since accounts are independent, transactions that access
disjoint sets of accounts should be allowed to execute in parallel: one thread
transferring funds between Alice and Adonis should be allowed to execute
in parallel with another thread transferring funds between Hendrix and
Malakai.
In Phase 2, replace your coarse-grained file range lock implementation with finer-grained locks. This should speed up the exchange; for example:
$ ./ftxxfer # coarse-grained lock
4 threads, 400000 operations, 0.681209s CPU time, 2.484973s real time
$ ./ftxxfer # finer-grained locks
4 threads, 400000 operations, 0.519218s CPU time, 0.753223s real time
(In Docker, all these times will be much higher.) Remember that make compiles with sanitizers, so make SAN=0 will yield better performance.
Improvements are visible for ftxxfer, which trades among randomly-selected accounts. However, fine-grained synchronization becomes even more important when some accounts or
objects are busier than others. The ftxrocket.cc program trades more often with certain important accounts.
[Run ./ftxrocket and look at /tmp/newaccounts.fdb to see how big crypto exchanges
work in reality.] With ./ftxrocket, fine grained synchronization matters even more:
$ ./ftxrocket # coarse-grained lock
4 threads, 400000 operations, 0.674707s CPU time, 2.465647s real time
$ ./ftxrocket # finer-grained locks
4 threads, 400000 operations, 0.538521s CPU time, 1.288776s real time
$ ./ftxrocket # finest-grained locks
4 threads, 400000 operations, 0.629610s CPU time, 0.799237s real time
When your fine-grained locking implementation passes make check-lock check-xfer check-fine check-rocket, move on to the next phase. (The fine
tests check that threads can lock distant accounts at the same time, so a
coarse-grained implementation fails them.)
Implementation notes
There are several ways to implement finer-grained locking. For example, you
can divide the file into multiple regions (say, 128 regions per file), and
lock just the regions that overlap the lock request. Or you could add an
auxiliary data structure to track currently-locked ranges. You could have one
mutex per region as different mutexes, or instead use a single mutex in
io61_file plus one or more condition variables.
As you implement your design, be aware that mutexes and condition variables
are special objects and cannot be used in some ways. Your io61_file may
contain an array of mutexes (as std::mutex ms[1024];), or a
dynamically-allocated array of mutexes (as std::mutex* ms; ... f->ms = new std::mutex[nmutexes];), or a list or map of mutexes or data structures
containing mutexes (as std::list<std::mutex> mlist;). It may not,
however, have a std::vector of mutexes or of any structures containing one
or more mutexes or condition variables. This is because mutexes and condition
variables cannot be copied or moved to different addresses once they are
created, and vectors inherently copy their contents when they grow.
The ftx test programs always obtain locks on 16-byte-aligned units of 16
bytes. Your locking design may work fastest for such lock requests, but it
must provide correct mutual exclusion for any lock requests—including
overlapping lock requests, and requests for ranges past the end of the file.
The lock tests check this. [For example, if a thread has an exclusive range lock
on offsets [12,27) in file f, then io61_try_lock(f, 25, 40) must return
-1 because the requested range [25,65) overlaps with the locked range
[12,27).]
If you’re confused about how to get started, check out the hints on fine-grained locking—but try to design your own solution first!
Phase 3: Blocking
Your solution should block, not poll, if a lock cannot be acquired. You may have already implemented blocking if you got some ideas from hints on fine-grained locking.
Run make check-blocking to check your work. The blocking tests hold a
lock for one second while other threads wait for it, and fail if the waiting
threads use more than half a second of CPU time. You can also look at CPU time
on ./ftxrocket -J2. If CPU time is far below real time, you’ve got a
blocking solution.
$ ./ftxrocket -J2 # coarse-grained lock, polling
4 threads, 400000 operations, 6.487076s CPU time, 2.028060s real time
$ ./ftxrocket -J2 # coarse-grained lock, blocking
4 threads, 400000 operations, 0.684149s CPU time, 2.450396s real time
$ ./ftxrocket -J2 # finest-grained locks, polling
4 threads, 400000 operations, 1.720757s CPU time, 1.819443s real time
$ ./ftxrocket -J2 # finest-grained locks, blocking
4 threads, 400000 operations, 1.066815s CPU time, 1.828140s real time
(In Docker, all these times will be much higher.) Our finest-grained solution
used a std::condition_variable_any to implement blocking.
When your fine-grained locking implementation passes the tests for Phases 1–3
(make check-lock check-xfer check-fine check-rocket check-blocking), move on
to the next phase.
Phase 4: File operation locks
You’ve now fixed the operation of the exchange—nice job! Unfortunately, your IO61 library is still not thread-safe for normal use (rather than special use with small-file positioned I/O).
You can see this by running ./ftxblockchain. This version of the exchange
modifies the accounts database, but as it runs, it also creates an immutable
public ledger /tmp/ledger.fdb of all transactions as they happen. For instance:
Rose -87
Camila +87
Crew -89
Jasmine +89
Adrian -93
Elena +93
Madelyn -107
Marley +107
David -85
Malia +85
Journee -95
Hazel +95
Eli -103
Aurora +103
...
This ledger is implemented with normal io61_write system calls:
char report[128];
size_t n = snprintf(report, sizeof(report),
"%-7s %+7ld\n%-7s %+7ld\n",
name1, -delta, name2, +delta);
assert(n == db.asize * 2 && n < sizeof(report));
ssize_t np;
if (args.write_bytewise) {
np = io61_write_bytewise(ledgerf, report, n);
} else {
np = io61_write(ledgerf, report, n);
}
assert(np == ssize_t(n));
But since io61_write is not properly synchronized, running ./ftxblockchain
with multiple threads will cause data races and output garbage to
/tmp/ledger.fdb, such as:
...
Zoe 2623
Zoey 9946
Zuri 6531
^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@ ^@^@^@^@^@^@^A^A^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@p^K^^@<EC><DF>^?^@^@<E0>^K^@<EC><DF>^?^@^@<F0>^K^@<EC><DF>^?^@^@ ^@^@^@^@^@^@^@^^^@^@^@^@^@^@^@^@^@^@^@^B^@^@^@^@^@^@^@^@^@^@^@^D^@^@^@^H^@^@^@^@^@^@^@^B^@^@^@^@<B0>^B<86><D0>U^@^@<F0><AF>^B<86><D0>U^@^@^@^@^@^@^@^@^@^@A^@^@^@^@^@^@^@<F0>:<D0>U^@^@^B^@^@^@^A^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^A^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@^@1^@^@^@^@^@^@^@0<8F>^B<86><D0>U^@^@^@^B^@^@^@^@^@^@^P^@^@^@^@^@^@^@^H^@^@^@^@^@^@^@^G^@^@^@^@^@^@^@<C1> ^@^@^@^@^@^@^D^@^@^@^A^@^@^@^AMax -94
Gemma +94
Israel -97
Jude +97
...
In Phase 4, you should add synchronization to all IO61 methods that
read and write data, so that ./ftxblockchain runs safely and without data
races.
We recommend coarse-grained synchronization: all methods that read or
write data should acquire exclusive access to the whole io61_file structure.
Since the normal reading and writing methods (io61_read, io61_write,
io61_flush, io61_seek) all read and write the position pos_tag, there is
no point in implementing fine-grained synchronization. The positioned methods
io61_pread and io61_pwrite do not access the shared pos_tag;
nevertheless, in our experience, implementing fine-grained synchronization for
io61_pread and io61_pwrite is not worthwhile for the benchmarks in this
problem set.
Note that the io61_fdopen and io61_close functions do not require
synchronization.
When you have completed this phase, ./ftxblockchain should complete without
error, even under sanitizers, and ./diff-ftxdb.pl -l should report no
errors.
$ ./ftxblockchain && ./diff-ftxdb.pl -l
4 threads, 400000 operations, 19.116283s CPU time, 16.751274s real time
[01;32m/tmp/newaccounts.fdb and /tmp/ledger.fdb OK[m
Furthermore, ./ftxxfer should be able to handle account databases that don’t
fit entirely in the io61_file cache—though it may be slow.
$ ./ftxxfer bigaccounts.fdb && ./diff-ftxdb.pl bigaccounts.fdb
4 threads, 400000 operations, 5.065556s CPU time, 10.230461s real time
[01;32m/tmp/newaccounts.fdb OK[m
The chain tests run ftxblockchain and check its ledger, including with
-W, which writes the ledger one byte at a time with io61_writec. The
audit tests run ftxaudit, which reads a ledger from many threads at once
with io61_read, and the big tests use databases larger than the cache. Run
make check-chain check-audit check-big to check this phase, then make check to run all the tests.
Troubleshooting. If, after adding synchronization, the test programs appear to hang forever, it’s likely you’ve got a deadlock!
To debug a deadlock, run the program under
gdb. When you think the deadlock has happened, press Ctrl-C to interrupt the program. Then thegdbcommandinfo threadswill report how many threads there are. Usethread 1; btto look at thread 1’s backtrace,thread 2; btto look at thread 2’s backtrace, and so forth. The deadlock can be found by looking at the blocked threads’ backtraces, which show which functions are blocked on which mutexes.The
io61_flushfunction is a common source of deadlock, because it can be called internally, from other IO61 functions, as well as externally, from user code. You may want to introduce an internal function, with a name like__io61_flushorlocked_io61_flush, that performs a flush under the assumption that its caller has already locked theio61_file.
Positioned I/O
Normal file descriptor system calls like read
and write use and modify the kernel-maintained file position. Other
system calls, however, act on specific offsets and ignore the file position.
These positioned I/O system calls are especially useful when accessing a
complex shared file, like a database, since one system call can do the work of
two—and since different threads (or processes) can access different parts of
the file independently, without getting in one another’s way.
The positioned I/O system calls are:
ssize_t pread(int fd, void* buf, size_t sz, off_t off)-
Read up to
szbytes from file descriptorfdinto bufferbuf, starting at file offsetoff. Does not affect the file position. Returns-1on error and0on end of file; otherwise returns the number of bytes read, which (as withread) might be less thansz. ssize_t pwrite(int fd, const void* buf, size_t sz, off_t off)-
Write up to
szbytes to file descriptorfdfrom bufferbuf, starting at file offsetoff. Does not affect the file position. Returns-1on error, or the number of bytes written.
Turnin
You will turn in your code by pushing your git repository to github.com and updating the grading server with your repository.
Don’t forget to fill out README.md and AUTHORS.md.
This pset was originally created for CS61.