rlsf icon indicating copy to clipboard operation
rlsf copied to clipboard

Support `cfg(target_arch = "wasm32", target_feature = "atomic")`

Open yvt opened this issue 2 years ago • 0 comments

rlsf::GlobalTlsf (std::alloc::GlobalAlloc implementation) requires target-specific code to synchronize concurrent function calls. The code for cfg(target_arch = "wasm32", target_feature = "atomic") was left out as its support (https://github.com/rust-lang/rust/issues/77839) in Rust was still in infancy.

https://github.com/yvt/rlsf/blob/e315d64d4ca099573f129aa88e2b4220a808b38e/crates/rlsf/src/global/wasm32.rs#L12-L20

Now that WASM atomic intrinsics have been introduced to core (still unstable though), it's possible to implement this now, but we must decide which mutex implementation to use:

  1. std::sync::Mutex

    • Pro: Already stable
    • Con: Runtime and code-size overhead due to poisoning mechanism
    • Con: The current implementation does not provide fairness guarantees, meaning acquiring a lock might not complete in a finite time
      • ...which might be not that bad, considering that the rest of an application is probably gonna use it anyway.
  2. Flag + memory_atomic_{wait32,notify}

    • Pro: Minimum code-size overhead
    • Pro: Minimum runtime overhead in uncontended cases
    • Con: Does not provide fairness guarantees, meaning acquiring a lock might not complete in a finite time
  3. Ticket lock + memory_atomic_{wait32,notify}

    • Pro: Provides fairness guarantees
    • Con: Thundering herd problem, which increases runtime overhead in contended cases
  4. Queue-based lock (e.g., MCS, CLH) + memory_atomic_{wait32,notify}

    • Pro: Provides fairness guarantees
    • Pro: Lowest worst-case runtime overhead
    • Con: High best-case runtime overhead
    • Con: More complicated to implement than other options
    • Scott, Michael L., and William N. Scherer. "Scalable queue-based spin locks with timeout." ACM SIGPLAN Notices 36.7 (2001): 44-52.
  5. Flag + busy loop (spinlock)

    • Pro: Minimum code-size overhead
    • Pro: Minimum runtime overhead in uncontended cases
    • Con: Does not provide fairness guarantees, meaning acquiring a lock might not complete in a finite time
    • Con: Catastrophic runtime overhead in contended cases
  6. Ticket lock + busy loop

    • Pro: Provides fairness guarantees (assuming the scheduler is fair)
    • Con: Catastrophic runtime overhead in contended cases

yvt avatar Mar 18 '24 13:03 yvt