Shared Array redirect lookup races with atomic reference-count updates

[nicolas-abril]

What you did

On unmodified commit e52cda47a58967aa65d1eb26efe8f42a0b0407df, compile this program to C and run the result under ThreadSanitizer with at least two workers:

bun bend2/main.ts redirect-race.bend -o /tmp/redirect-race.c
clang -x c -std=gnu11 -O1 -g -fsanitize=thread -pthread /tmp/redirect-race.c -o /tmp/redirect-race
TSAN_OPTIONS='halt_on_error=0 exitcode=0' /tmp/redirect-race --threads 2 --gpu off

What happened

ThreadSanitizer reliably reports an 8-byte non-atomic read in blk_loc racing with a 4-byte atomic write in term_keep / rfc_bump:

WARNING: ThreadSanitizer: data race
  Read of size 8 ... by thread T1:
    #0 WL_FID_FAN
    #1 monk_step
    #2 pool_work

  Previous atomic write of size 4 ... by thread T2:
    #0 WL_FID_FAN
    #1 monk_step
    #2 pool_work

SUMMARY: ThreadSanitizer: data race in WL_FID_FAN
4
ThreadSanitizer: reported 1 warnings

The redirect cell is initialized as:

e.mem[r] = ((u64)term_loc(t) << 24) | cnt;

blk_loc reads the complete cell as a plain u64:

return blk_shr(a) ? H[term_loc(a)] >> 24 : term_loc(a);

At the same time, rfc_bump and term_drop perform atomic 32-bit read-modify-write operations on the low half of that same u64. Mixing the overlapping non-atomic 64-bit access and atomic 32-bit access is a C data race even though the returned location appears stable in practice.

I could not manifest this as an incorrect or nondeterministic Bend result. The reproducer prints the expected 4, including when ThreadSanitizer continues after reporting the race. A deeper version with 262,144 concurrent leaves, hundreds of repetitions, worker counts 2/4/8/16, Apple Clang and Homebrew Clang/GCC at several optimization levels including LTO, and arm64 and Rosetta x86-64 all produced the expected result.

There is a runtime invariant that explains that result: valid reference-count changes are confined to the low 24 bits, while cell >> 24 returns the immutable target location. A live reader owns a reference, so the redirect wrapper cannot be freed and reused during that read. Refcount overflow is rejected with ERR_RFCS. Thus this is a confirmed language-level C race and possible portability/miscompilation issue, but there is currently no known Bend program whose unsanitized result it corrupts.

Using the existing atomic reconstruction in rfc_view for shared blk_loc calls removes the ThreadSanitizer report. A representation with separately addressable location and reference-count fields would also avoid overlapping accesses.

The file

import Base

@unsafe
def leaf(a: Array<U32>) -> Array<U32>:
  Array.set.fin(U32, Array.atomic.add(a, 0, 1))

@unsafe
def fan(+d: Nat, +a: Array<U32>) -> Array<U32>:
  match d:
    case 0n:
      leaf(a)
    case 1n+p:
      l r = fan(p, a) fan(p, a)
      Array.join(U32, l, r)

def done(r: Array<U32> & U32) -> IO(Unit):
  (a, x) = r
  IO.print(U32.show(x))

def main() -> IO(Unit):
  done(Array.get(U32, fan!(2n, [0 : U32*1n]), 0))

#|4

Environment

• bend --version: bend 2.0.24
• Commit: e52cda47a58967aa65d1eb26efe8f42a0b0407df
• uname -sm: Darwin arm64
• clang --version: Apple clang version 17.0.0 (clang-1700.6.4.2)