Re: pserialized queue(9)

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

On 25 Nov, 2014, at 08:29 , Mindaugas Rasiukevicius <rmind%netbsd.org@localhost> wrote:

> Taylor R Campbell <campbell+netbsd-tech-kern%mumble.net@localhost> wrote:
>> The attached patch adds _PSZ variants to all the insert, remove, and
>> foreach operations in <sys/queue.h> to issue the necessary store
>> barriers, for insert, and data-dependent load barriers, for foreach.
>> 
>> <...>
> 
> Please do not.  In practice, we only need singly-linked list which is
> trivial to open-code and apart from data dependency memory barrier for
> Alpha there is nothing to abstract.  Any other cases of locklist list
> use generally do not fit into the existing queue(3) macros; this API
> is quite dated by now and I do not forsee any use of such API around
> pserialize(9) (it is also poorly named since one may as well use other
> techniques).

I'm not a fan of these macros either, but there is already at least
one use of the LIST_* macros for lockless list use (or, at least, there
was until last June) in sys/kern/vfs_cache.c.  LIST_INSERT_HEAD() is
open-coded at about line 740 to add the membar_producer(), and the
LIST_FOREACH() at line 303 was used (without an Alpha-barrier) to
traverse a list that may have had an entry being concurrently added.
This was also an example of a lockless list which didn't use
pserialize(9) for synchronization of entry removals, so I guess I
agree that _PSZ doesn't a very good name for this.

Unfortunately the last two changes to the file changed this, perhaps
inadvertently, from allowing lookups in the cache from all CPUs in
parallel with a possible single concurrent writer to having all lookups
serialized both with the writer and each other.  I suspect the change also
made it a bit buggy now since cache_reclaim() expects to have blocked
cache_invalidate() from being run but the latter is now called with no
lock.

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.

Dennis Ferguson