KAIST CS431 — Concurrent Programming (Rust)

Lock-based and lock-free concurrent data structures in Rust — an independent, from-skeleton implementation of CS431 — Concurrent Programming (KAIST), part of a csdiy.wiki full-catalog build.

Overview

KAIST CS431 (Jeehoon Kang) is a graduate course on the theory and practice of shared mutable state. This repository implements every programming homework of the course from the official skeleton: fine-grained lock-coupling structures, an atomically reference-counted Arc, a parallel web-server backend (thread pool + cancellable listener + cache), hazard-pointer memory reclamation, a lock-free split-ordered hash map, and a Behavior-Oriented Concurrency (BoC) runtime. Every todo!() in the skeleton is filled in and verified against the course's own test suites, including the concurrency stress tests.

The workspace vendors the official cs431 support library (the seqlock and the Harris/Harris-Michael lock-free list) as a local path dependency so the project builds offline and reproducibly.

Results (measured on Windows, stable rustc 1.96.1, x86_64-pc-windows-gnu, CPU-only)

Every homework passes its full test module (the numbers in parentheses are the official grade-script point weights). Runner used: plain cargo test/cargo test --release. The grade scripts additionally run the LLVM AddressSanitizer/ThreadSanitizer runners (cargo_asan/cargo_tsan), which are nightly-Linux-only and therefore not runnable on this Windows box — the plain-cargo runner is the first runner in every grade script and is what is reported here.

Homework	What it does	Result (measured)
linked_list (40)	doubly-linked list w/ cursor & mutable iterator	18 integration + 19 doctests pass
list_set / fine_grained (45)	sorted set, Mutex lock-coupling (hand-over-hand)	stress_sequential, stress_concurrent, log_concurrent, iter_consistent pass
list_set / optimistic (55)	sorted set, SeqLock optimistic reads + epoch reclaim	4 stress + read_no_block + iter_invalidate_end/deleted pass
arc (40)	atomic reference counting (SeqCst)	13 tests + doctests pass; 5/5 loom correctness models pass
hello_server (100)	thread pool + cancellable TCP + non-blocking cache	cache 4/4, tcp 1/1, thread_pool 4/4
hazard_pointer (70)	hazard-pointer reclamation	hazard 3, retire 1, counter/stack/queue/stack_queue 5 pass
hash_table (140)	GrowableArray + lock-free split-ordered hash map	growable_array 6/6, split_ordered_list 6/6
boc (100)	Behavior-Oriented Concurrency runtime (2PL)	basic 5/5 + stress 3/3 (fib(28)=317811, 100k bank txns, 1024-elem sorts)

Aggregate: 89 integration/unit tests + 33 doctests + 5 loom models — all green. Raw cargo test logs are in results/ (test-*.txt, cargo-test-summary.txt).

Implemented homeworks

• linked_list — push_back/pop_back, prepend, back, push_front, mutable iterator, insert_next/peek_next.
• list_set (fine-grained) — Mutex-per-node lock-coupling set: cursor find, insert, remove, iterator, drop.
• list_set (optimistic) — SeqLock-per-node optimistic set with read-validation and crossbeam-epoch deferred reclamation.
• arc — Arc without Weak: clone/drop/get_mut/make_mut/try_unwrap/count, verified under the loom model checker.
• hello_server — ThreadPool (crossbeam MPMC + join-on-drop), CancellableTcpListener, and a non-blocking Cache.
• hazard_pointer — Shield/HazardBag grow-only slot list with recycling, and threshold-triggered retire/collect.
• hash_table — GrowableArray (height-tagged lock-free segment tree) and SplitOrderedList (recursive split-ordered lock-free map).
• boc — Behavior-Oriented Concurrency runtime: two-phase-locking enqueue over per-cown request queues, thunks run on rayon.
• elim_stack (ungraded, part of the crate) — elimination-backoff layer over Treiber's stack.

Project structure

kaist-cs431-concurrent-rust/
├── Cargo.toml                 # cargo workspace
├── cs431/                     # vendored official support library (path dep)
│   └── src/{lock,lockfree}/   #   seqlock, MCS/CLH locks, Harris list, Treiber stack, MS queue
├── homework/
│   ├── src/
│   │   ├── linked_list.rs
│   │   ├── list_set/          # fine_grained.rs, optimistic_fine_grained.rs
│   │   ├── arc.rs
│   │   ├── hello_server/      # cache.rs, tcp.rs, thread_pool.rs, ...
│   │   ├── hazard_pointer/    # hazard.rs, retire.rs
│   │   ├── hash_table/        # growable_array.rs, split_ordered_list.rs
│   │   ├── elim_stack/        # elimination-backoff stack
│   │   └── boc.rs
│   ├── tests/                 # the course's own test suites (unmodified)
│   ├── doc/                   # per-homework specs
│   └── scripts/               # the course's grade-*.sh scripts
└── results/                   # captured cargo-test output

How to run

Rust ≥ 1.85 (edition 2024). The repo builds on stable:

# Build everything
cargo build --release

# Run any homework's test module (release recommended for the stress tests):
cargo test -p cs431-homework --release --test linked_list
cargo test -p cs431-homework --release --test arc
cargo test -p cs431-homework --release --test hazard_pointer
cargo test -p cs431-homework --release --test boc

# The concurrent list_set / hash_table test harnesses use the nightly-gated
# `cfg_sanitize` attribute. On a stable toolchain, enable it with RUSTC_BOOTSTRAP=1
# and pin single-threaded test execution (as the grade scripts do):
RUSTC_BOOTSTRAP=1 RUST_TEST_THREADS=1 \
  cargo test -p cs431-homework --release --test list_set
RUSTC_BOOTSTRAP=1 RUST_TEST_THREADS=1 \
  cargo test -p cs431-homework --release --test growable_array
RUSTC_BOOTSTRAP=1 RUST_TEST_THREADS=1 \
  cargo test -p cs431-homework --release --test split_ordered_list

# Arc under the loom model checker (exhaustive interleaving check):
cargo test -p cs431-homework --features check-loom --test arc

# Doctests:
cargo test -p cs431-homework --doc

Verification

• Every homework was verified against the course's own tests/ suites, unmodified — including the concurrency stress tests (stress_concurrent, log_concurrent, iter_consistent, etc.) run under --release. Captured logs live in results/.
• arc additionally passes all 5 loom correctness models (count_sync, get_mut_sync, try_unwrap_sync, drop_sync, clone_drop_atomic), which exhaustively check every legal interleaving/reordering permitted by the memory model.
• The implementation code passes cargo fmt --check and cargo clippy -- -D warnings (library target). For hazard_pointer, the grade scripts diff the test tails to detect tampering; those tails are preserved byte-for-byte.
• Sanitizer note. The grade scripts also run cargo_asan/cargo_tsan, which require a nightly toolchain + -Zbuild-std + the x86_64-unknown-linux-gnu target and thus only run on Linux. This build is on Windows (CPU-only), so those runners are out of scope here; the plain-cargo runner (first in every grade script) is fully green. The lock-free code is written to be data-race free by construction (SeqCst atomics per the 2024 spec, epoch-based reclamation).

Tech stack

Rust 2024, crossbeam-epoch (epoch-based reclamation), crossbeam-channel (MPMC channels), rayon (BoC task pool), loom (model checking Arc). No unsafe-free claims: the lock-free and pointer-heavy structures use unsafe deliberately, guarded by the documented invariants.

Key ideas / what I learned

• Lock-coupling vs. optimistic locking. The fine-grained set hands locks over node-by-node; the optimistic set replaces locks with a sequence lock, reads speculatively, and validates — trading reader blocking for retry-on-conflict, with epoch-based deferral to reclaim safely.
• Release-acquire reference counting. Arc::drop only needs the last decrement to synchronize with all prior accesses; the loom models pin down exactly which orderings are required.
• Hazard pointers. Publish-then-validate protects a node from reclamation; retire/collect frees only pointers absent from the global hazard set.
• Recursive split-ordering. Keys live in one lock-free list sorted by bit-reversed order; buckets are lazily-initialized sentinel nodes cached in a growable segment tree, giving O(1) expected ops without ever rehashing existing items.
• Behavior-Oriented Concurrency. A two-phase-locking enqueue over per-cown MCS-style queues gives atomic, deadlock-free acquisition of multiple resources; behaviors run asynchronously once all their cowns are held.

Credits & license

Based on the homework assignments of KAIST CS431: Concurrent Programming by Jeehoon Kang and the KAIST Concurrency & Parallelism Lab (kaist-cp/cs431). This repository is an independent educational reimplementation; all course materials, the skeleton code, and the vendored cs431 support library belong to their original authors. Original implementation code in this repo is released under the MIT License.