NMIs, Locks, linked lists, barriers, and rculists, oh my!

[michi1 at michaelblizek.twilightparadox.com]

Hi!

On 19:08 Wed 03 Apr     , Arlie Stephens wrote:
...
> Put another way, my problem is that I want the readers to be able to
> do their thing regardless of the state of the lock that serializes
> writers. 
> 
> In all cases, writers are protected from each other with a mutex. 
> 
> Here are some choices for making sure readers see something sensible:
> 
> 1) Use an rculist, and hope that it really does cover this
> situation. 

rculist might cover this case. The question is whether you can aquire read
locks inside panic(), NMI, ... However, you should be able to skip the read
lock, if you never free the contents.

> 2) Be thankful I'm only running on x86,

Is there any good reason for limiting your code to x86? "My machine is x86 and
I do not care about yours" will probably not convince maintainers.

> hope that the linux kernel isn't built with aggressive optimizations that
> reorder writes to pointers,

There is no guarantee for that.

> fix __list_add() so it updates pointers in the new entry before updating
> pointers in its neighbours,

IMHO, this is like asking for trouble. Somebody else might change the order
in the future without knowing it might break your stuff. Also, if you have bad
luck, somebody else might already depend on the current order without you
knowing.

> and do the reads with no synchronization whatsoever.

You should at least do atomic_read()+atomic_set(). RCU is exactly that plus
a mechanism to free memory after all readers have finished.

> 3) Add my own explicit use of compiler directives, either to a copy 
> of list.h or to a simpler, home-grown singly linked tail queue 
> implementation. Because I'm on x86 all I really care about is compiler 
> optimizations, but it looks like the linux way to do this may be
> with barrier macros. 

You can do that. If you do that, I recommend using atomic operations. Do not
hope that the compiler does the right thing. It almost certainly does not
(atomic operations need the "lock" prefix in assembly and the compiler will
not add it).

> 4) Give up on always getting this to work from an NMI. Use something
> like a reader-writer spinlock, but if I'm in an NMI, make only a
> conditional attempt to acquire it - and don't try to walk the list if
> that acquisition fails (presumed self-deadlock)
> 
> As always, my questions are:
> 
> - Will these even work? In particular, do I need to deal with compiler
> optimizations on x86? And is using RCU semantics sufficient to deal
> with interrupting the writing context?
> 
> - Which of these make sense from the POV of someone whose been in the
> linux kernel for a while? 

Not sure if I qualify (I do not have any code upstream), I would do either
1 or 3. Option 2 is broken and 4 looks more like a last resort.

> As a generic kernel person who's spent a lot of time in industry, my
> instincts are to avoid roll-your-own unless no existing primitive can
> do what I want. I also have a particular dislike of home grown
> concurrency control; even if the original author gets it right, it's
> tricky enough that some maintainer is almost certain to break it. 

In this case you have to deal with concurrency either way. Just do it way
which is not tricky or subtle.

	-Michi
-- 
programing a layer 3+4 network protocol for mesh networks
see http://michaelblizek.twilightparadox.com