Re: pserialized queue(9)

[Mindaugas Rasiukevicius <rmind%netbsd.org@localhost>]

Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost> wrote:
> 
> On 28 Nov, 2014, at 07:33 , Mindaugas Rasiukevicius <rmind%netbsd.org@localhost>
> wrote:
> > Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost> wrote:
> > Yes, Joerg broke the name cache concurrency.  This has to be fixed or at
> > least reverted for netbsd-7.
> 
> He did, but I can't blame him.  The locking arrangement in that code, and
> what it is supposed to accomplish, is really not obvious and deserved a
> comment describing it.

While I agree that the code is underdocumented and not trivial to read,
there was a very short comment above cache_lookup_entry().  The comment
and locking was changed without fully understanding the locking protocol,
without review and without discussion (unless I managed to miss it?).

That is not good.  Anyway.. this is an off-topic problem.

> >> In any case, the use in vfs_cache.c required more than a singly-linked
> >> list (I don't know how you concluded that was all that was necessary),
> >> is not improved by the open-coding that was done and would be worse
> >> still if it was all open-coded.  There really needs to be some way to
> >> build a library of basic data structures which is reusable by some
> >> technique other than cut-and-paste, and while I don't like the macros
> >> I'm not sure what they should be replaced with.
> > 
> > No really.. the proposal here is about queue(9) macros and in this
> > respect it is merely a lockless singly-linked list.  The writer
> > serialisation in vfs_cache.c (which uses mixed locking strategy,
> > handling additions and the removals in a different way, so the lookup
> > could be lockless) is way beyond the queue(9) stuff.
> 
> I think you are maybe mixing two issues.  The garbage collection strategy
> around concurrent reader data structures, whether done by pserialize(9) or
> a locking scheme or reference counting or something else, always addresses
> removals (that's what requires garbage collection) differently than
> additions and is always a challenging problem, but is a problem
> orthogonal to the data structure itself.  All data structures that are
> used like this have this problem.

I am not talking about reclamation mechanism.  As I already pointed out
in my original reply, _PSZ is not right as it can be any other mechanism.
The vfs_cache.c code is exactly the case which illustrates that.  All this
does not really concern queue(9) or other list abstraction.

> In vfs_cache.c the data structure itself is precisely that provided by
> Taylor's LIST_*_PSZ() macros, but with the _INSERT_ open-coded to add the
> barrier instead and with the Alpha-barrier missing.  The macros would be
> an improvement on this.

Yes, but it just illustrates that from the queue(9) API set, only the
singly-linked list is relevant.  Now bear in mind that, as pointed out
in my original reply, I do not object against an alternative abstraction.
It would make sense to create a new interface, e.g. atomic_slist(9) which
besides the memory barrier in iteration would additionally abstract atomic
insertion into the head.  However, it would be very poor abstraction to
hack this on top of queue(9) in the form of _PSZ macros (i.e. assuming
pserialize(9) use) and especially for non-SLIST cases.

-- 
Mindaugas