Re: pserialized queue(9)

[Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost>]

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.

>> 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.

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.

> I agree about the need to have a library of data structures.  However,
> adding _PSZ macros is a very wrong direction.

The only problem is I still don't know the right direction, though I'm sur
 cut-'n-paste open coding makes it worse.

My experience with coaxing more complex data structures into library form
generally ends up depending on offsetof() to get from the structure member
the library deals with to the containing structure the application is
interested in, and to get the offsetof() math all in one spot usually
requires writing a "shim" API specializing it to the application data
structure (in C++ you could get the compiler to do the specialization for
you...).  While I hate the macros I have to admit they are effective at
doing this specialization without shims (for simpler data structures at
least), and are hence easier to deal with despite the ugliness.  I have
no idea how to do better than that.

Dennis Ferguson