Problem set 6: Flockchain

In this problem set, you’ll implement synchronization for your buffered I/O library.

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:

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:

  1. Picks two accounts to trade using a proprietary Liquidity Engine (i.e., a random number generator).
  2. Reads the accounts’ current balances using positioned I/O calls in the IO61 library.
  3. Transfers money from one account to the other.
  4. 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
/tmp/newaccounts.fdb: Incorrect exchange total 4017050
accounts.fdb: Expected 4000000

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 file f. Return 0 if the range lock was obtained, and -1 (with errno set to EAGAIN) if it could not be obtained. This function does not block; if a range lock is already held overlapping that range, it returns -1 right away. In the pset, the locktype argument is always LOCK_EX to 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. Return 0 on success. (Your solution will likely always return 0, but if you implement additional error detection, serious errors may cause io61_lock to 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 file f and return 0. 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
/tmp/newaccounts.fdb OK
$ ../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
/tmp/newaccounts.fdb OK

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_write a locked range without acquiring the lock. File range locks provide correct synchronization only when all threads use them. This resembles the way that std::mutex works. 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 off and len arguments must be ≥0. If len == 0, the requested range is empty, and any attempt to lock or unlock the range succeeds (returns 0) 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, flock manages file locks and fcntl’s F_SETLK/F_SETLKW command manages file range locks; on Windows, LockFile manages file and file range locks. Unix’s file locks are purely advisory (normal read and write system calls ignore locks). In Windows, file locks are semi-advisory: they prevent normal reads and writes, but not mmap.

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
/tmp/newaccounts.fdb and /tmp/ledger.fdb OK

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
/tmp/newaccounts.fdb OK

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 the gdb command info threads will report how many threads there are. Use thread 1; bt to look at thread 1’s backtrace, thread 2; bt to 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_flush function 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_flush or locked_io61_flush, that performs a flush under the assumption that its caller has already locked the io61_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 sz bytes from file descriptor fd into buffer buf, starting at file offset off. Does not affect the file position. Returns -1 on error and 0 on end of file; otherwise returns the number of bytes read, which (as with read) might be less than sz.

ssize_t pwrite(int fd, const void* buf, size_t sz, off_t off)

Write up to sz bytes to file descriptor fd from buffer buf, starting at file offset off. Does not affect the file position. Returns -1 on 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.