On Wed, Aug 30, 2017 at 08:55:01AM +0200, Michael Haggerty wrote:
> > + tempfile->active = 0;
> > + for (p = &tempfile_list; *p; p = &(*p)->next) {
> > + if (*p == tempfile) {
> > + *p = tempfile->next;
> > + break;
> > + }
> > }
> > }
>
> `deactivate_tempfile()` is O(N) in the number of active tempfiles. This
> could get noticeable for, say, updating 30k references, which involves
> obtaining 30k reference locks. I think that code adds the locks in
> alphabetical order and also removes them in alphabetical order, so the
> overall effort would go like O(N²). I'm guessing that this would be
> measurable but not fatal for realistic numbers of references, but it
> should at least be benchmarked.
>
> There are three obvious ways to make this O(1) again:
>
> * Make the list doubly-linked.
Yeah, I noticed this when writing it, and the doubly-linked list was my
first thought. It's much more straight-forward than making guesses about
traversal order, and we already have a nice implementation in list.h.
What made me hesitate for this demonstration was that it turns the
removal into _two_ pointer updates. That made me more nervous about the
racy case where we get a single handler while already deleting
something. Specifically when we have "a <-> b <-> c" and we've updated
"a->next" to point to "c" but "c->prev" still points to "b".
But even with the singly-linked list we're not fully race-proof
(somebody could set *p to NULL between the time we look at it and
dereference it). What we really care about is not two versions of the
function running simultaneously, but one version getting interrupted by
another and having the second one see a sane state (because we'll never
return to the first signal handler; the second one will raise() and
die).
And I think we're fine there even with a doubly-linked list. It's still
the single update of the "next" pointer that controls that second
traversal.
-Peff
