How to implement C++26 RCU

Denis Yaroshevskiy

This talk

The plan

  • RCU = read/copy/update
  • motivational example
  • trivial buggy implementation
  • low-level concurrency in C++
  • improvements to RCU
  • hazard pointers

Motivational Example

std::shared_ptr + mutex

Atomic Shared Ptr

Raw pointer

Using RCU

implementing basic rcu

Testing using relacy

RCU smoke test

RCU (broken)

Bug report

low level concurrency in c++

Approaches to Understanding

What does relaxed do?

  • "atomicity"
  • while (!done.load(...))

What do acquire / release do?

  • release store: stalls to leave the buffer
  • load acquire: load then process invalidations

Bug explanation 


old = cfg.exchange(new config(2), acq_rel);
domain.synchronize();
delete old;

Bug explanation 


cfg.store(release);    // old = cfg.exchange(new config(2), acq_rel);
counter.load(acquire); // domain.synchronize();
delete old;

It was not acquire! 


cfg.store(release);  // old = cfg.exchange(new config(2), acq_rel);
counter.load();      // domain.synchronize();
delete old;

What is SC?

  • sc store is release
  • sc load is acquire
  • total order on sc
  • sc only affects sc

This would work 


cfg.store();    // old = cfg.exchange(new config(2));
counter.load(); // domain.synchronize();
delete old;

What can we do? 


// updater
cfg.store(release);
...
counter.load(...)
        

// reader
counter.store(...)
...
config.load(acquire)

SC Fences 


// updater
cfg.store(release);
atomic_thread_fence(seq_cst);
counter.load(relaxed);
        

// reader
counter.store(relaxed);
atomic_thread_fence(seq_cst);
config.load(acquire);

P1202: Asymmetric fences 


// updater
cfg.store(release);
atomic_thread_fence_heavy();
counter.load(relaxed);
        

// reader
counter.store(relaxed);
atomic_thread_fence_light();
config.load(acquire);

P1202: Asymmetric fences

  • David Goldblatt, wg21.link/p1202
  • light: asm volatile("" : : : "memory")
  • heavy: membarrier

Correct trivial RCU

Notes

Improvements to RCU

Recursive locking 


std::scoped_lock _{std::rcu_default_domain()};

Retiring

Using synchronize


auto* old = cfg_.exchange(new Config ...);
std::rcu_synchronize();
delete old;

Using retire API


auto* old = cfg_.exchange(new Config ...);
std::rcu_retire(old);

Retire API

  • std::rcu_obj_base<T, D>
  • std::rcu_retire(T*, D)
  • std::rcu_barrier

Unaddressed topics

  • better waiting
  • no background thread
  • retiring from critical section
  • simultaneous rcu_synchronize

Hazard pointers

Maged M. Michael

Hazard pointers vs RCU

Links