change interrupt event's list of handler from TAILQ to SLIST
ClosedPublic
Actions

Authored by avg on Jun 26 2018, 9:21 AM.

Details

Reviewers

cem
imp
jhb
kib
mmacy
mjg

Commits

rS336635: change interrupt event's list of handlers from TAILQ to CK_SLIST

Summary

SLIST is sufficient. The only operation that gets worse performance is
a removal of a handler. But it is not critical. Also, the list is not
expected to be long anyway.

Additionally, it is easier to reason about SLIST when considering the
concurrent lock-free access to the list from the interrupt context and
interrupt thread.

Diff Detail

Repository

rS FreeBSD src repository - subversion

Lint

Lint Not Applicable

Unit

Tests Not Applicable

Event Timeline

avg created this revision.Jun 26 2018, 9:21 AM

Harbormaster completed remote builds in B17622: Diff 44454.Jun 26 2018, 9:21 AM

avg mentioned this in D15905: safer wait-free iteration of shared interrupt handlers.Jun 26 2018, 9:22 AM

avg added a child revision: D15905: safer wait-free iteration of shared interrupt handlers.Jun 26 2018, 10:52 AM

LGTM modulo I think SLIST_INSERT_PREVPTR should be added to queue.h instead of open-coded.

sys/kern/kern_intr.c
598–600 ↗	(On Diff #44454)	Add an API name for this and add it to queue.h, even if temporary or hidden (underscore(s)-prefix)? The name looks reasonable to me.
sys/sys/queue.h
264 ↗	(On Diff #44454)	Ok, I think this makes sense to me. If the list was mutated at the current element (`var`), `(varp) != (var)`. (For inserts, `varp` points to the new element; for removals, it points to the element after `var`.) In either event we want to visit `varp`, which the update condition + exit condition achieves. If the list was not mutated, we just want to visit `var`'s next. If we instead visited `varp`, we'd spin at the same location in the list forever.

This revision is now accepted and ready to land.Jun 26 2018, 3:37 PM

avg added inline comments.Jun 26 2018, 4:00 PM

sys/kern/kern_intr.c
598–600 ↗	(On Diff #44454)	Will do. I think that it should be generally useful if anyone ever uses PREVPTR API again.
sys/sys/queue.h
264 ↗	(On Diff #44454)	Yes, that's the idea. Handling of removals is sound, but inserts via INSERT_PREVPTR are not as much. The problem is that the iteration would visit the current element again after visiting the newly inserted element. It would be better skip the inserted element and to go to the next element (as if there was no insertion). But I could not think of any way to differentiate between a removal and an insertion. So, `SLIST_FOREACH_PREVPTR_SAFE` is safe only with respect to remove and insert-after. Not sure if this is sufficient to qualify for _SAFE suffix.

cem added inline comments.Jun 26 2018, 4:27 PM

sys/sys/queue.h
264 ↗	(On Diff #44454)	We could instead take the usual approach of adding an additional `next` variable (as compared to the non-"_SAFE" version of the similar loop construct). That would avoid duplicate traversals even with INSERT_PREVPTR. I think it makes sense that consumers using FOREACH_PREVPTR may try to use INSERT_PREVPTR in a "_SAFE" loop and they may be surprised by duplicate traversal. The only real downside there is an additional macro parameter. That doesn't seem so bad?

avg added inline comments.Jun 26 2018, 7:41 PM

sys/sys/queue.h
264 ↗	(On Diff #44454)	The problem is with getting a coherent "prevptr" for that `next` variable.

cem added inline comments.Jun 26 2018, 10:07 PM

sys/sys/queue.h
264 ↗	(On Diff #44454)	It seems maybe surmountable if we only allow deleting the current node, not the next one — which is a requirement of any `_SAFE` version of the various loops already. If `varp` == `next`, the current node was removed (updating `varp`). `varp` remains unmodified in the "update" step of the for-loop. If `varp` == `var`, the list was unmodified. `varp` is changed to `&SLIST_NEXT(...)` in the update step so that we traverse the next node. Otherwise, a new node or node(s) was/were inserted, also updating `varp`. We can leave `varp` unmodified in this case too. I might be missing or forgetting something.

Use CK_SLIST instead of SLIST to avoid a need for hand-rolled list
operations with fences.
This change adds CK_SLIST_{INSERT,REMOVE}_PREVPTR.

Also, I decided against adding [CK_]SLIST_FOREACH_PREVPTR_SAFE.
So, I now use SLIST_FOREACH_SAFE and explicitly track the previous element.

Finally, an obsoleted comment is removed.

This revision now requires review to proceed.Jul 4 2018, 11:12 AM

Harbormaster completed remote builds in B17837: Diff 44850.Jul 4 2018, 11:12 AM

cem added inline comments.Jul 4 2018, 9:12 PM

sys/contrib/ck/include/ck_queue.h
183 ↗	(On Diff #44850)	Can/should/has this be(en) pushed to upstream CK?
190 ↗	(On Diff #44850)	probably shouldn't be making unrelated whitespace changes to contrib code -- ditto below

(Other than nits above, LGTM.)

mmacy added inline comments.Jul 4 2018, 9:15 PM

sys/contrib/ck/include/ck_queue.h
190 ↗	(On Diff #44850)	Please don't make FreeBSD local changes to ck. They're very responsive to PRs. Submit a PR for this (assuming it's correct and justifed) and then have cognet import the update.

avg added inline comments.Jul 10 2018, 3:08 PM

sys/contrib/ck/include/ck_queue.h
183 ↗	(On Diff #44850)	I've opened a CK PR for this.
190 ↗	(On Diff #44850)	I've opened a CK PR for this as well.

sbahra_repnop.org added a subscriber: sbahra_repnop.org.Jul 12 2018, 2:01 AM

sbahra_repnop.org added inline comments.

sys/contrib/ck/include/ck_queue.h
183 ↗	(On Diff #44850)	Merged!
sys/kern/kern_intr.c
200 ↗	(On Diff #44850)	Unrelated: Is there an off by one here or is it expected this won't always be NUL-terminated?=
762 ↗	(On Diff #44850)	hmmm, this looks suspect to me. Is `subr_epoch` used anywhere? What's protecting a reader doing a concurrent iteration from having the handler freed from underneath it? I might be missing a detail

avg added inline comments.Jul 16 2018, 7:50 AM

sys/contrib/ck/include/ck_queue.h
183 ↗	(On Diff #44850)	Thank you! How do we integrate the change into FreeBSD now? What's the process?
sys/kern/kern_intr.c
200 ↗	(On Diff #44850)	I think that the check is correct given that it has the strict comparison.
762 ↗	(On Diff #44850)	Well, that's exactly the problem I am trying to solve. This change covers only the mechanical conversion of TAILQ to CK_SLIST. The other review request covers the "interesting" part of the fix.