How to hold onto things in a multiprocessor world
Taylor ‘Riastradh’ Campbell
campbell@mumble.net
riastradh@NetBSD.org

AsiaBSDcon 2017
Tokyo, Japan
March 12, 2017

Slides’n’code
I Full of code! Please browse at your own pace.
I Slides: https://tinyurl.com/ho2cdhq1
I Paper: https://tinyurl.com/h9kqccf2

Slides:1

Paper:

https://www.NetBSD.org/gallery/presentations/riastradh/asiabsdcon2017/mp-refs-slides.pdf
2
https://www.NetBSD.org/gallery/presentations/riastradh/asiabsdcon2017/mp-refs-paper.pdf

Resources

I Network routes

May be tens of thousands in system.
Acquired and released by packet-processing path.
I Same route may be used simultaneously by many flows.
I Large legacy code base to update for parallelism.
I Update must be incremental!
I
I

I Device drivers
I
I

Only a few dozen in system.
Even wider range of legacy code to safely parallelize.

I File system objects (‘vnodes’)I User credential sets
I ...

The life and times of a resource

I Birth:I
I

Create: allocate memory, initialize it.
Publish: reveal to all threads.

I Life:Acquire: thread begins to use a resource.
Release: thread is done using a resource.
I . . . rinse, repeat.
I Concurrently by many threads at a time.
I
I

I Death:I
I

Delete: prevent threads from acquiring.
Destroy: free memory. . . after all threads have released.

Problems for an implementerIf you are building an API for some class of resources. . .
I You MUST ensure nobody frees memory still in use!
I You MUST satisfy other API contracts, e.g. mutex rules.
I You MAY want to allow concurrent users of resources.
I You MAY care about performance.

Serialize all resources — layout

struct foo {int key;...;
struct foo *next;};
struct {kmutex_t lock;
struct foo *first;} footab;Serialize all resources — create/publish

struct foo *f = alloc_foo(key);mutex_enter(&footab.lock);f->next = footab.first;
footab.first = f;mutex_exit(&footab.lock);Serialize all resources — lookup/use

struct foo *f;mutex_enter(&footab.lock);for (f = footab.first; f != NULL; f = f->next) {if (f->key == key) {...use f...
break;}}
mutex_exit(&footab.lock);Serialize all resources — delete/destroy
Delete/destroy:
struct foo **fp, *f;mutex_enter(&footab.lock);for (fp = &footab.first; (f = *fp) != NULL; fp = &f->next) {if (f->key == key) {*fp = f->next;
break;}}
mutex_exit(&footab.lock);if (f != NULL)
free_foo(f);Serialize all resources — slow and broken!

I No parallelism.
I Not allowed to wait for I/O or do long computation undermutex lock.
I (This is a NetBSD rule to put bounds on progress formutex enter, which is not interruptible.)Mutex and reference counts — layout(a) Add reference count to each object.
(b) Add condition variable for notifying f->refcnt == 0.
struct foo {int key;...;
unsigned refcnt;
struct foo *next;};
struct {kmutex_t lock;kcondvar_t cv;
struct foo *first;} footab;// (a)// (b)

Mutex and reference counts — layout
footabunownedwaiters

rst

NULL

struct foo
key: 1…

refcnt: 3

next

key: 2…

refcnt: 0

next

NULL

Mutex and reference counts — create/publish

struct foo *f = alloc_foo(key);f->refcnt = 0;mutex_enter(&footab.lock);f->next = footab.first;
footab.first = f;mutex_exit(&footab.lock);Mutex and reference counts — lookup/acquire

struct foo *f;mutex_enter(&footab.lock);for (f = footab.first; f != NULL; f = f->next) {if (f->key == key) {f->refcnt++;
break;}}
mutex_exit(&footab.lock);if (f != NULL)...use f...

Mutex and reference counts — releasemutex_enter(&footab.lock);
if (--f->refcnt == 0)
cv_broadcast(&footab.cv);
mutex_exit(&footab.lock);Mutex and reference counts — delete/destroy

struct foo **fp, *f;mutex_enter(&footab.lock);for (fp = &footab.first; (f = *fp) != NULL; fp = &f->next) {if (f->key == key) {*fp = f->next;
while (f->refcnt != 0)
cv_wait(&footab.cv, &footab.lock);break;}}
mutex_exit(&footab.lock);if (f != NULL)
free_foo(f);Mutex lock and reference counts — summary

I If this works for you, stop here!
I Easy to prove correct.
I Just go to another talk.
I . . . but it does have problems:
I Only one lookup at any time.
I Contention over lock for every object.
I Hence not scalable to many CPUs.

Hashed locks

I Randomly partition resources into buckets.
I If distribution on resource use is uniform, lower contention for

lookup!

Hashed locks — layout

struct {struct foobucket {kmutex_t lock;kcondvar_t cv;
struct foo *first;} b;char pad[roundup(
sizeof(struct foobucket),
CACHELINE_SIZE)];} footab[NBUCKET];

Hashed locks — acquire

size_t h = hash(key);mutex_enter(&footab[h].b.lock);for (f = footab[h].b.first; f != NULL; f = f->next) {if (f->key == key) {f->refcnt++;
break;}}
mutex_exit(&footab[h].b.lock);Hashed locks

I Randomly partition resources into buckets.
I If distribution on resource use is uniform, lower contention

for lookup!
I What if many threads want to look up same object?
I Still only one lookup at a time for that object.
I Still contention for releasing resources after use.

Mutex lock and atomic reference counts

I Use atomic operations to manage most uses of a resource.
I No need to acquire global table lock to release a resource if

it’s not the last one.

Mutex lock and atomic reference counts — acquire

struct foo *f;mutex_enter(&footab.lock);for (f = footab.first; f != NULL; f = f->next) {if (f->key == key) {atomic_inc_uint(&f->refcnt);
break;}}
mutex_exit(&footab.lock);if (f != NULL)...use f...

Mutex lock and atomic reference counts — releasedo {old = f->refcnt;
if (old == 1) {mutex_enter(&footab.lock);if (f->refcnt == 1) {f->refcnt = 0;
cv_broadcast(&footab.cv);} else {atomic_dec_uint(&f->refcnt);}
mutex_exit(&footab.lock);break;}} while (atomic_cas_uint(&f->refcnt, old, new) != old);Atomics: still not scalable

I We avoid contention over global table lock to release.
I But if many threads want to use the same foo. . .
I Atomic operations are not a magic bullet!
I Single atomic is slightly faster and uses less memory than amutex lock enter/exit.
I But contended atomics are just as bad as contended locks!

Atomics: interprocessor synchronization3
CPU 0
CPU 1
Cache
Cache
Interconnect

Memory

3

CPU 2
CPU 3
Cache
Cache
Interconnect

System Interconnect

MemoryInterconnect
Cache
Cache

Interconnect
Cache
Cache

CPU 4

CPU 6

CPU 5

CPU 7

Diagram Copyright c 2005–2010, Paul E. McKenney. FromPaul E. McKenney, Is Parallel Programming Hard, And, If So, What Can You
Do About It?, 2011. https://www.kernel.org/pub/linux/kernel/people/
paulmck/perfbook/perfbook.2011.01.02a.pdf

Reader/writer locks for lookup

I Instead of mutex lock for table, use rwlock.
I At any time, either one writer or many readers.
I Allows concurrent lookups, not just concurrent resource use.
I If lookups are slow, great!
I If lookups are fast, reader count is just another reference

count managed with atomics—contention!

Basic problem: to read, we must write!

I All approaches here require readers to coordinate writes.

Acquire table lock: write who owns it now.
Acquire read lock: write how many readers.
I Acquire reference count: write how many users.
I

I

I Can we avoid writes to read?
I Are there more reads than creations or destructions?
I Can we make reads cheaper, perhaps at the cost of making

creation or destruction more expensive?

No-contention references in NetBSD

I Passive serialization.
I
I

Like read–copy–update, RCU in Linux.
. . . but US patent expired sooner!

I Passive references.
I
I

Similar to hazard pointers.
Similar to OpenBSD SRP.

I Local counts—per-CPU reference counts.
I

Similar to sleepable RCU, SRCU, but simpler.

Coordinate publish and read

I Linked-list insert and read can coordinate with no atomics.
I . . . as long as they write and read in the correct order.
I One writer, any number of readers!
I Same principle for hash tables (‘hashed lists’), radix trees.

Publish

I Write data first.
I Then write pointer to it.

struct foo *f = alloc_foo(key);mutex_enter(&footab.lock);f->next = footab.first;
membar_producer();footab.first = f;mutex_exit(&footab.lock);Publish 1: after writing data

head

data

next

data

data

next

next

NULL

Publish 2: after write barrier

head

data

next

data

data

next

next

NULL

Publish 3: after writing pointer

head

data

next

data

data

next

next

NULL

Read
I Read pointer first.
I Then read data from it.
I . . . Yes, in principle stale data could be cached.
I Fortunately, membar datadep consumer is a no-op on allCPUs other than DEC Alpha.
for (f = footab.first; f != NULL; f = f->next) {membar_datadep_consumer();
if (f->key == key) {use(f);
break;}}

Read 1: after reading pointer

head

data

next

garbagedata

garbage

next

NULL

Read 2: after read barrier

head

data

next

data

data

next

next

NULL

Read 3: after reading data

head

data

next

data

data

next

next

NULL

DeleteI Deletion is even easier!
I *fp= f->next;

I . . . but there is a catch.

Delete 1: before delete

head

data

next

data

data

next

next

NULL

Delete 1: after delete

head

data

next

data

data

next

next

NULL

The catch

I All well and good for publish and use!
I All well and good for delete!
I But when can we destroy (free memory, etc.)?
I No signal for when all users are done with a resource.
I How to signal release without contention?

Passive serialization: pserialize(9)I Lookup/use:

1. Acquire: Block interrupts on CPU.
2. Look up resource.
3. Use it.
4. Release: Restore and process queued interrupts on CPU.
5. (Cannot use resource any more after this point!)
I Delete/destroy:

1. Remove resource from list: *fp = f->next.
2. Send interprocessor interrupt to all CPUs.
3. Wait for it to return on all CPUs.
4. All users that could have seen this resource have exited.

Passive serialization
CPU A

read section
defer IPI

CPU B

unlinksafe to destroy

send IPI

CPU C

answer IPI

read section

answer IPI

timeread section

Passive serialization — lookup/use
1. Acquire: Block interrupts with pserialize read enter.
2. Lookup: Read pointer.
3. Memory barrier!
4. Use: Read data.
5. Release: Restore and process queued interrupts withpserialize read exit.
s = pserialize_read_enter();for (f = footab.first; f != NULL; f = f->next) {membar_datadep_consumer();
if (f->key == key) {use(f);
break;}}
pserialize_read_exit(s);Passive serialization — delete/destroy(a) Delete from list to prevent new users.
(b) Send IPI to wait for existing users to drain.
(c) Free memory.
mutex_enter(&footab.lock);for (fp = &footab.first; (f = *fp) != NULL; f = f->next) {if (f->key == key) {/* (a) Prevent new users. */*fp = f->next;/* (b) Wait for old users. */pserialize_perform(footab.psz);}}
mutex_exit(&footab.lock);if (f != NULL)/* (c) Destroy. */free_foo(f);Passive serialization — lists

I sys/queue.h macros do not have correct memory barriers.
I So we provide PSLIST(9), like LIST in sys/queue.h.
I Linked list with constant-time insert and delete. . .
I . . . and correct memory barrier for insert and read.

Passive serialization — PSLIST(9)struct foo { ... struct pslist_entry f_entry; ... };struct { ... struct pslist_head head; ... } footab;
mutex_enter(&footab.lock);
PSLIST_WRITER_INSERT_HEAD(&footab.head, f, f_entry);
mutex_exit(&footab.lock);s = pserialize_read_enter();
PSLIST_READER_FOREACH(f, &footab.head, struct foo,
f_entry) {if (f->key == key) {...use f...;break;}}
pserialize_read_exit(s);Passive serialization pros

I Zero contention!
I Serially fast readers!
I
I

We use software interrupts, so cheap to block and restore.
No hardware interrupt controller reconfiguration!

I Constant memory overhead—no memory per resource, perCPU!

Passive serialization cons

I Interrupts must be blocked during read.
I Thread cannot sleep during read.
I What if we want to pserialize the network stack?
I Code was written in ’80s before parallelism mattered. . .
I . . . and does memory allocation in packet path (e.g., toprepend a header in a tunnel). . .
I . . . and simultaneously re-engineering the whole network stackis hard!
I Can we do it incrementally with different tradeoffs?

Passive references: psref(9)I Record per-CPU list of all resources in use.
I Lookup: use pserialize for table lookup.
I To acquire resource: put it on the list.
I Can now do anything on the CPU—sleep, eat, watch

television. . .
I To release resource: remove it from the list.
I To wait for users: send IPI to check for resource on eachCPU’s list.
I Note: Reader threads must not switch CPUs!

Passive references — create/publish

struct foo { ... struct psref_target target; ... };struct { ... struct psref_class *psr; ... } footab;
struct foo *f = alloc_foo(key);
psref_target_init(&f->target, footab.psr);
mutex_enter(&footab.lock);
PSLIST_WRITER_INSERT_HEAD(&footab.head, f_entry, f);mutex_exit(&footab.lock);Passive references — lookup/acquire
psref acquire inserts entry on CPU-local list: no atomics!
struct psref fref;
int bound, s;/* Bind to current CPU and lookup. */bound = curlwp_bind();s = pserialize_read_enter();
PSLIST_READER_FOREACH(f, &footab.head, struct foo,
f_entry) {if (f->key == key) {psref_acquire(&fref, &f->target,
footab.psr);
break;}}
pserialize_read_exit(s);Passive references — releaseI psref remove removes entry on CPU-local list, and notifies

destroyer if there is one.
I No atomics unless another thread is waiting to destroy the

resource.
/* Release psref and unbind from CPU. */psref_release(&fref, &f->target, footab.psr);
curlwp_bindx(bound);Passive references — delete/destroy

I psref target destroy marks the resource as being

destroyed.
I Thus, future psref release will wake it.
I Then psref target destroy repeatedly checks forreferences on all CPUs and sleeps until there are none left.

Passive references — delete/destroy/* (a) Prevent new users. */mutex_enter(&footab.lock);
PSLIST_WRITER_FOREACH(f, &footab.head, struct foo,
f_entry) {if (f->key == key) {PSLIST_WRITER_REMOVE(f, f_entry);
pserialize_perform(footab.psz);
break;}}
mutex_exit(&footab.lock);if (f != NULL) {/* (b) Wait for old users. */psref_target_destroy(&f->target, footab.psr);/* (c) Destroy. */free_foo(f);}Passive references — notes

I Threads can sleep while holding passive references.
I Binding to CPU is not usually a problem.
I Much of network stack already runs bound to a CPU anyway!
I Bonus: can write precise asserts for diagnostics!

KASSERT(psref_held(&f->target, footab.psr));
I Modest memory cost:

O(#CPU) + O(#resource) + O(#references).
I Network routes: tens of thousands in system.
I Network routes: a handful per CPU at any time.

Local counts: localcount(9)I Global reference count per resource=⇒ contention.

I What about a per-CPU reference count per resource?
I High memory cost: O(#CPU × #resource).
I So use only for small numbers of resources, like device drivers.
I Device drivers: dozens in system.
I Device drivers: maybe thousands of uses at any time during

heavy I/O loads.

Local counts — create/publish

struct foo { ... struct localcount lc; ... };struct foo *f = alloc_foo(key);
localcount_init(&f->lc);
mutex_enter(&footab.lock);
PSLIST_WRITER_INSERT_HEAD(&footab.head, f_entry, f);mutex_exit(&footab.lock);Local counts — lookup/acquire
localcount acquire increments a CPU-local counter—noatomics!
s = pserialize_read_enter();
PSLIST_READER_FOREACH(f, &footab.head, struct foo,
f_entry) {if (f->key == key) {localcount_acquire(&f->lc);
break;}}
pserialize_read_exit(s);Local counts — release

I localcount release increments a CPU-local counter.
I If there is a destroyer, updates destroyer’s global reference

count.
I No atomics unless another thread is waiting to destroy the

resource.
localcount_release(&f->lc);

Local counts — delete/destroy

I localcount destroy marks resource as being destroyed.
I Sends IPI to compute global reference count by adding up

each CPU’s local reference count.
I (Fun fact: local reference counts can be negative, if threads

have migrated!)
I Waits for all IPIs to return and reference count to becomezero.

Local counts — delete/destroy/* (a) Prevent new users. */mutex_enter(&footab.lock);
PSLIST_WRITER_FOREACH(f, &footab.head, struct foo,
f_entry) {if (f->key == key) {PSLIST_WRITER_REMOVE(f, f_entry);
pserialize_perform(footab.psz);
break;}}
mutex_exit(&footab.lock);if (f != NULL) {/* (b) Wait for old users. */localcount_destroy(&f->lc);/* (c) Destroy. */free_foo(f);}Local counts — notes

I Not yet integrated in NetBSD—still on an experimental

branch!
I To be used for MP-safely unloading device driver modules.
I Other applications? Probably yes!

Summary

I Avoid locks! Locks don’t scale.
I Avoid atomics! Atomics don’t scale.
I pserialize: short uninterruptible reads, fast but limited.
I psref: sleepable readers, modest time/memory cost, flexible.
I localcount: migratable readers, fast but memory-intensive.

Questions?
riastradh@NetBSD.org