Problem class: sh-20261006-cgroup-aware-build-cache-invalidation
The solution is implemented and verified. The markdown-extracted code was re-run independently and passes 29/29 tests. The deliverable is saved at ~/bcache/SOLUTION.md; the full document follows.
Problem class: sh-20261006-cgroup-aware-build-cache-invalidation
Environment: bash 5.x, GNU/uutils coreutils, Linux cgroup v2
Status: reference implementation + 29/29 passing verification tests
A cache assembled from shell primitives fails in six distinct ways, each a design defect mapping to one clause in the problem statement.
| # | Symptom | Root cause |
|---|---|---|
| 1 | Deep-header edits not rebuilt; unrelated outputs rebuilt | Keys derived from path + mtime, or only direct inputs. The key must be a Merkle digest over the full transitive prerequisite closure, command, toolchain, allow-listed env, and cgroup limits. |
| 2 | Collisions/corruption with odd filenames | Newline-delimited manifests hashed via argv where the filename leaks into the digest. All path I/O must be NUL-delimited and hashed from stdin. |
| 3 | Torn/empty artifacts after a kill | In-place writes with no fsync. Publish must be: staging dir → fsync → atomic rename(2). |
| 4 | Symlink swapped between check and read | TOCTOU. Resolve, enforce containment, then stat → read → stat and retry on change. |
| 5 | Workers corrupt repairs; GC deletes in-flight objects | No mutual exclusion. Per-key mkdir locks + global flock; GC skips locked/fresh entries. |
| 6 | Unbounded disk growth | No eviction. Byte cap + LRU under the GC lock, with a grace window. |
Cgroup-awareness: the worker's memory.max/memory.high/cpu.max and /proc/self/cgroup are folded into the key, so workers under different resource limits don't share entries.
$ROOT/
objects/<sha256>/ immutable published objects (READY + artifact)
tmp/<key>.<pid>.<rnd>/ private staging, reaped by GC
locks/<key>/ per-key mkdir lock (pid heartbeat)
.gc.lock global flock for GC/repair
A key is published only by mv -T staging objects/<key>. rename(2) is atomic: a crash leaves either nothing or a complete READY-marked object.
bin/bcache.sh#!/usr/bin/env bash
# bcache.sh - crash-safe, content-addressed, cgroup-aware build artifact cache.
#
# Design invariants:
# * An object is published only by atomically renaming a fully-populated
# staging directory onto objects/<key>. A crash therefore leaves either
# no object or a complete object.
# * Keys are a Merkle-style digest over the full (transitive) prerequisite
# set, the command, the toolchain, the allow-listed environment and the
# worker's cgroup resource limits. Changing anything in that closure
# changes exactly the affected objects.
# * Paths are NUL-delimited everywhere so arbitrary bytes (newlines,
# spaces, backslashes) are safe.
# * Per-key mkdir locks serialize duplicate work and repairs; a global
# flock serializes GC. GC never removes locked or fresh objects.
set -euo pipefail
VERSION="bcache/1"
BC_LOCK=""
: "${BCACHE_GRACE:=60}" # seconds before an object/temp may be GC'd
: "${BCACHE_CAP:=1073741824}" # bytes; default 1 GiB
: "${BCACHE_ENV_KEYS:=}" # file with allow-listed env var names
: "${BCACHE_SRC_ROOTS:=}" # colon-separated roots symlinks must resolve inside
die() { printf 'bcache: %s\n' "$*" >&2; exit 2; }
canon_root() { # canonicalise once so symlinked cache roots cannot be swapped
local r=$1
mkdir -p -- "$r"
readlink -f -- "$r" || die "cannot canonicalise cache root: $r"
}
init_root() {
local r
r=$(canon_root "$1")
mkdir -p -- "$r/objects" "$r/tmp" "$r/locks"
: >>"$r/.gc.lock"
printf '%s\n' "$r"
}
# ---- arbitrary-byte-safe hashing ------------------------------------------
# hash_file prints "<sha256>\0". It resolves symlinks, optionally enforces
# containment, and retries if the inode/mtime changes under us (symlink race /
# concurrent rewrite). stdin (not argv) is hashed so filenames never leak
# into the digest.
hash_file() {
local f=$1 resolved s1 s2 h try=0
if [ -L "$f" ]; then
resolved=$(readlink -f -- "$f" 2>/dev/null) || return 1
if [ -n "$BCACHE_SRC_ROOTS" ]; then
local root ok=1
IFS=: read -r -a __roots <<<"$BCACHE_SRC_ROOTS"
for root in "${__roots[@]}"; do
case "$resolved" in "$root"/*) ok=0; break;; esac
done
[ "$ok" = 0 ] || return 1
fi
f=$resolved
fi
while [ "$try" -lt 5 ]; do
s1=$(stat -c '%d:%i:%s:%Y:%Z' -- "$f" 2>/dev/null) || return 1
h=$(sha256sum <"$f" 2>/dev/null) || return 1
s2=$(stat -c '%d:%i:%s:%Y:%Z' -- "$f" 2>/dev/null) || return 1
if [ "$s1" = "$s2" ]; then printf '%s\0' "${h%% *}"; return 0; fi
try=$((try+1))
done
return 1
}
# emit canonical environment: only allow-listed keys, sorted, NUL-framed.
emit_env() {
local keys=$1 k v
[ -f "$keys" ] || return 0
while IFS= read -r k; do
[ -n "$k" ] || continue
if v=$(printenv -- "$k" 2>/dev/null); then
printf 'ENV\0%s\0%s\0' "$k" "$v"
fi
done < <(LC_ALL=C sort -u -- "$keys")
}
# emit cgroup v2 resource limits that can influence build output/tuning.
emit_cgroup() {
local f
for f in /sys/fs/cgroup/memory.max /sys/fs/cgroup/cpu.max /sys/fs/cgroup/memory.high; do
if [ -r "$f" ]; then printf 'CG\0%s\0' "$f"; tr -d '\n' <"$f"; printf '\0'; fi
done
printf 'CG\0/proc/self/cgroup\0'; tr -d '\n' </proc/self/cgroup 2>/dev/null || true; printf '\0'
}
# ---- key computation -------------------------------------------------------
# spec/ is a target description directory:
# cmd executable command (invoked as: cmd <staging-output-path>)
# deps NUL-delimited transitive prerequisite paths
# tools optional NUL-delimited toolchain files (compilers, linkers, ...)
compute_key() {
local root=$1 spec=$2 p
{
printf '%s\0' "$VERSION"
emit_cgroup
printf 'CMD\0'; cat -- "$spec/cmd"; printf '\0'
emit_env "${spec}/env.keys"
if [ -f "$spec/tools" ]; then
printf 'TOOLS\0'
while IFS= read -r -d '' p; do printf '%s\0' "$p"; hash_file "$p"; done \
< <(LC_ALL=C sort -z -u -- "$spec/tools")
fi
printf 'DEPS\0'
while IFS= read -r -d '' p; do
printf '%s\0' "$p"
hash_file "$p" || { printf 'bcache: unreadable dependency: %q\n' "$p" >&2; exit 3; }
done < <(LC_ALL=C sort -z -u -- "$spec/deps")
} | sha256sum | { read -r k _; printf '%s' "$k"; }
}
# ---- locking ---------------------------------------------------------------
acquire_lock() {
local root=$1 key=$2 i=0
local ld="$root/locks/$key"
while ! mkdir -- "$ld" 2>/dev/null; do
# steal a lock whose owner died (no heartbeat within grace)
if [ -n "$(find -- "$ld" -maxdepth 0 -mmin +"$BCACHE_GRACE" 2>/dev/null)" ]; then
mv -- "$ld" "$ld.stale.$$" 2>/dev/null && rm -rf -- "$ld.stale.$$"
continue
fi
i=$((i+1)); [ "$i" -ge 600 ] && return 1
sleep 0.1
done
printf '%s' "$$" >"$ld/pid"
}
release_lock() { [ -n "${1:-}" ] && rm -rf -- "$1"; return 0; }
# ---- publish ---------------------------------------------------------------
# Stage the built artifact, fsync, then atomically rename. Losing the race is
# fine: the winner's object is byte-identical by construction.
publish() {
local stage=$1 obj=$2
printf 'ok\n' >"$stage/READY"
sync -f -- "$stage/artifact" 2>/dev/null || sync
mkdir -p -- "$(dirname -- "$obj")"
if mv -T -- "$stage" "$obj" 2>/dev/null; then return 0; fi
rm -rf -- "$stage"
[ -f "$obj/READY" ]
}
# ---- CLI -------------------------------------------------------------------
usage() { cat >&2 <<'EOF'
usage:
bcache.sh init <root>
bcache.sh key <root> <spec-dir>
bcache.sh run <root> <spec-dir> <output-path>
bcache.sh gc <root>
EOF
exit 2
}
cmd_init() { init_root "$1" >/dev/null; }
cmd_key() {
local root spec; root=$(canon_root "$1"); spec=$2
[ -f "$spec/cmd" ] || die "spec has no cmd: $spec"
[ -f "$spec/deps" ] || : >"$spec/deps"
compute_key "$root" "$spec"
}
cmd_run() {
local root spec out key obj lock stage rc
root=$(canon_root "$1"); spec=$2; out=$3
[ -f "$spec/cmd" ] || die "spec has no cmd: $spec"
[ -f "$spec/deps" ] || : >"$spec/deps"
key=$(compute_key "$root" "$spec")
obj="$root/objects/$key"
mkdir -p -- "$root/tmp" "$root/locks" "$root/objects"
# fast path: use the immutable object without taking a lock
if [ -f "$obj/READY" ]; then
touch -c -- "$obj" 2>/dev/null || true
cp -a -- "$obj/artifact" "$out"
printf 'HIT %s\n' "$key"; return 0
fi
lock="$root/locks/$key"
acquire_lock "$root" "$key" || die "lock timeout for $key"
BC_LOCK="$lock"
trap 'release_lock "$BC_LOCK"; BC_LOCK=""' EXIT
if [ -f "$obj/READY" ]; then # someone published while we waited
cp -a -- "$obj/artifact" "$out"
printf 'HIT %s\n' "$key"; return 0
fi
stage="$root/tmp/$key.$$.$RANDOM"
rm -rf -- "$stage"; mkdir -p -- "$stage"
if BCACHE_SPEC="$spec" "$spec/cmd" "$stage/artifact" >"$stage/stdout" 2>"$stage/stderr"; then
rc=0
else
rc=$?
printf 'bcache: build failed (%d) for %s\n' "$rc" "$key" >&2
sed -n '1,40p' -- "$stage/stderr" >&2 || true
rm -rf -- "$stage"
return "$rc"
fi
publish "$stage" "$obj" || die "publish failed for $key"
cp -a -- "$obj/artifact" "$out"
printf 'MISS %s\n' "$key"
cmd_gc "$root" || true
}
cmd_gc() {
local root; root=$(canon_root "$1")
mkdir -p -- "$root/objects" "$root/tmp" "$root/locks"
exec {gcfd}>>"$root/.gc.lock"
flock -n "$gcfd" || return 0 # another worker is already repairing
# 1. reap abandoned staging dirs (crash recovery) older than grace
find -- "$root/tmp" -mindepth 1 -maxdepth 1 -mmin +"$BCACHE_GRACE" \
-exec rm -rf -- {} + 2>/dev/null || true
# 2. enforce the byte cap with LRU eviction of unlocked, non-fresh objects
local total victim
total=$(du -sb -- "$root/objects" 2>/dev/null | cut -f1); total=${total:-0}
while [ "$total" -gt "$BCACHE_CAP" ]; do
victim=""
while IFS= read -r cand; do
[ -n "$cand" ] || continue
[ -e "$root/locks/$(basename -- "$cand")" ] && continue # in use
victim=$cand; break
done < <(find -- "$root/objects" -mindepth 1 -maxdepth 1 -type d \
-mmin +"$BCACHE_GRACE" -printf '%T@ %p\n' 2>/dev/null \
| LC_ALL=C sort -n | cut -d' ' -f2-)
[ -n "$victim" ] || break
rm -rf -- "$victim"
total=$(du -sb -- "$root/objects" 2>/dev/null | cut -f1); total=${total:-0}
done
}
[ $# -ge 1 ] || usage
sub=$1; shift
case "$sub" in
init) cmd_init "$@";;
key) cmd_key "$@";;
run) cmd_run "$@";;
gc) cmd_gc "$@";;
*) usage;;
esac
key = SHA256( VERSION
‖ cgroup_limits
‖ cmd_bytes
‖ Σ allowlisted_env(k=v)
‖ Σ tools(path, content_hash)
‖ Σ deps(path, content_hash) ) # both sorted with `sort -z -u`
Because the manifest lists the complete prerequisite set (standard -M depfile semantics), any transitive edit changes exactly the objects whose closure contains it. Downstream objects are invalidated because they list the upstream artifact in their own deps, whose content changed. Objects outside the closure keep their key.
bcache.sh init /var/cache/cc
# spec dir for one target:
# cmd -> executable, called as: cmd <staging-output-path>
# deps -> NUL-delimited transitive prerequisites
# tools -> optional NUL-delimited toolchain files
# env.keys -> optional newline list of env vars that affect the build
bcache.sh run /var/cache/cc ./specs/foo /build/foo.o
bcache.sh key /var/cache/cc ./specs/foo
bcache.sh gc /var/cache/cc # opportunistic; also runs after a MISS
Environment knobs: BCACHE_CAP (bytes), BCACHE_GRACE (seconds), BCACHE_SRC_ROOTS (colon-separated symlink containment roots).
t/run.sh builds a deterministic fake compiler and exercises every failure mode. Run chmod +x bin/bcache.sh t/run.sh && bash t/run.sh. The full harness is in ~/bcache/t/run.sh. Observed result:
== 1. transitive invalidation ==
ok first build is MISS
ok second build is HIT
ok unrelated target stays cached
ok c rebuilds after its source changes
ok b rebuilds transitively
ok a rebuilds transitively
ok u stays cached (exactly affected)
ok b now cached
ok changing b rebuilds b
ok changing b rebuilds a
ok changing b leaves c cached
ok changing a rebuilds only a
== 2. toolchain + env + arbitrary path bytes ==
ok toolchain change invalidates a
ok toolchain content change invalidates
ok newline-bearing filename builds
ok newline-bearing filename hits
ok newline-bearing filename invalidates
ok env change invalidates b
ok stable env hits
== 3. atomic publication survives a crash ==
ok no object published by crashed builder
ok crashed builder leaves staging for GC
ok gc reaps stale staging dirs
== 4. concurrent workers publish one complete object ==
ok all concurrent workers reported HIT/MISS
ok all concurrent outputs are identical
ok published object is complete
== 5. symlink containment ==
ok symlink escaping allowed roots is rejected
ok rejected symlink publishes nothing
== 6. bounded disk (LRU + cap) ==
ok gc shrinks cache under a tiny cap
ok evicted target rebuilds cleanly
RESULT: 29 passed, 0 failed
What each group proves: editing c.src rebuilds c → b → a while u stays cached (exact closure, no over/under-invalidation); toolchain, allow-listed env, and \n-bearing filenames all change the key with NUL framing preventing collisions; SIGKILL mid-write publishes no READY object and GC reaps the orphan; 12 simultaneous builders yield byte-identical outputs and one complete object; a symlink escaping BCACHE_SRC_ROOTS is rejected before building; a tiny cap makes GC shrink the cache and evicted targets still rebuild.
Self-containment check: I re-extracted the fenced bash blocks directly from the markdown into a clean directory and ran the suite against them — RESULT: 29 passed, 0 failed. The document is directly usable as-is.
# Evidence - Problem class: sh-20261006-cgroup-aware-build-cache-invalidation - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-06T22:35:31.688Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Build a shell-driven artifact cache that consumes compiler dependency manifests from concurrent workers, survives process crashes, and invalidates exactly the transitive outputs affected by source, toolchain, or environment changes. Preserve atomic publication and bounded disk use while handling paths with arbitrary bytes, symlink races, and two workers attempting conflicting cache repairs.", "environment": "bash", "language": "shell", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "sh-20261006-cgroup-aware-build-cache-invalidation", "provider": "openrouter", "solved_at": "2026-10-06T22:35:31.689Z", "version": "5"}