Devsummit – Concurrency Hacks
Taylor ‘Riastradh’ Campbell
campbell@mumble.net
riastradh@NetBSD.org

EuroBSDcon 2015
Stockholm, Sweden
October 2, 2015

Concurrency hacks

Works in progress — not even compile-tested.
I Lightweight task queues
I Pserialized reader/writer locks
I Reference counts

Tasks background – Softints
I softint(9): defer processing from hardware interrupt

handlers to lower-priority to remain responsive to hardwareinterrupts.
I

softint = softint_establish(&mydriver_softintr,arg);...
softint_schedule(softint);
static void
mydriver_softintr(void *arg){...
}

Tasks background – Softints

I Limited number of softints: use sparingly.
I softint schedule can’t pass argument.
I Multi-CPU: softint schedule schedules up to one softint

per CPU at a time, executed in parallel.
I Cheap: zero interprocessor synchronization.

Tasks background – Workqueues
I workqueue(9): defer processing from higher-priority threads

to lower-priority threads.
I structmydriver_softc {...
struct workqueue *sc_wq;
struct work sc_wk;};
error = workqueue_create(&sc->sc_wq, "mydriver",&mydriver_work, arg, PRI_NONE, IPL_NET,WQ_MPSAFE);...
workqueue_enqueue(sc->sc_wq, &sc->sc_wk, NULL);
static void
mydriver_work(struct work *wk, void *arg)...

Tasks background – Workqueues
I Caller must not reuse struct

work until done, must donecessary bookkeeping to avoid this.

I Caller can pass arguments by embedding struct

work:struct mywork {struct work w;int extra;};I Multi-threaded (WQ PERCPU): each struct

work can executein parallel, one worker thread per CPU.
I Caller can’t wait for individual work — can only destroy

workqueue and wait for all.
I workqueue enqueue acquires per-CPU mutex, so requires

interprocessor synchronization.
I One dedicated thread per workqueue (per CPU): wastes

kernel address space for mostly unused workqueues.

Tasks background – USB tasks
I usb task(9): defer processing from USB interrupt handler tothread.
I structudriver_softc {...
struct usb_task sc_task;};
usb_init_task(&sc->sc_task, &udriver_task, sc,
USB_TASKQ_MPSAFE);...
usb_add_task(sc->sc_udev, &sc->sc_task,
USB_TASKQ_DRIVER);...
usb_rem_task(sc->sc_udev, &sc->sc_task);
static voidudriver_task(void *arg)...

Tasks background – USB Tasks

I USB-specific.
I Per-device/per-host-controller task queues.
I BUG: No way for task to complete — need this for driverdetach.
I usb add task and usb rem task acquire shared mutex, so

require interprocessor synchronization.

Tasks background – Callouts

I callout(9): defer processing until ticks have passed.
I hz granularity.
I Unlike others, supports synchronous cancellation —callout halt.
I Complex triggering protocol: callout pending,callout ack, callout expired, . . .
I ...

Tasks – Unified proposal
I task(9): defer processing from higher-priority contexts tolower-priority contexts.
I structmydriver_softc {...
struct task sc_task;};task_init(task, &mydriver_task);task_schedule(task);
static void
mydriver_task(struct task *task){...
}

Tasks – Unified proposal

I Easy to use.
I Synchronous cancellation.
I Slightly more synchronization overhead softint:

task schedule acquires mutex — but only for local CPU,not contended unless doing cancel.
I Slightly more memory overhead than workqueue: Caller canreschedule struct task without problem (no effect), unlike
workqueue struct work.
I Delayed tasks with nanosecond-resolution API, simpler

triggering protocol.

Tasks – Explicit task queues

I Common API for softint and thread priority levels.
I Default shared system task queues at each softint and threadpriority level.
I Guaranteed concurrency if you make your own task queue:

not held up by other system tasks.
I Per-CPU thread pool shared by different task queues — nothreads wasted on mostly unused task queues.

Pserialized reader/writer locks

I Example: fstrans — recursive transactions to block file system

operations if operator requests suspend, e.g. to take snapshot.
I fstrans begin/fstrans end are cheap if no suspend in

progress: no interprocessor synchronization, using
pserialize(9).
I Suspend is expensive: not just interprocessor synchronization,

but cross-call to wait for all transactions to drain.
I (Fstrans also handles establishing copy-on-write hooks.)

Pserialized reader/writer locks

I rrwlock(9) generalizes (part of) fstrans(9):I l= rrwlock create("foo");

I struct

rrw reader r; rrwlock reader enter(l, &r);

I ...
I rrwlock reader exit(l,I structr);

rrw writer w; rrwlock writer enter(l, &w);

I ...
I rrwlock writer exit(l,w);

I rrwlock destroy(l);I Also non-recursive variant, prwlock(9).

Reference counts
I refcount(9): simple reference counts.
I Many copies of simple reference-counting logic: e.g., struct

kauth cred, struct ifaddr.
I Nothing novel or exciting here: just a nice API.
I /*Create object. */refcount_init(&obj->refcount);/* Acquire reference. */refcount_inc(&obj->refcount);/* Assert held. */KASSERT(refcount_referenced_p(&obj->refcount));Reference counts

I /*Release reference and free if last one.
if (refcount_dec_local(&obj->refcount)) {kmem_free(obj, sizeof(*obj));}*//* Release reference and notify waiters. */refcount_dec_signal(&obj->refcount, &obj->lock);/* Release reference and wait for other users. */refcount_dec_drain(&obj->refcount, &obj->lock);
kmem_free(obj, sizeof(*obj));Problem: cache, don’t free, on last reference

I Want to cache vnodes in memory to avoid reparsing disk forfrequently referenced files.
I On last reference, put vnodes on queue to be freed whenmemory is tight.
I Need to synchronize between acquiring cached vnode andfreeing cached vnode.
I Need to coordinate with per-file-system ‘delete file on lastreference’ logic.
I refcount(9) API doesn’t help with this.