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

[Arlie Stephens]

Hi Folks,

I've got another "what's the natural way to do this in the linux
kernel" question. As always, I'm attempting something bizarre, that
doesn't seem to be covered in the newbie examples, and discussion with
coworkers produced no consensus. I got such useful ideas last time I
asked one of those question here, that I'm coming back for more.

Here's the situation:

- I've got a linked list, with entries occassionally added from normal
contexts. 
- Entries are never deleted from the list.
- I've got data structures which save pointers to various members of
the list.
- I've got routines which want to update a saved pointer to the next
  item in the list, or walk the whole list, or do other simple list
  operations. 

This would be simple, except that the routines which READ the list may
get called from panic(), or inside an oops, or from an NMI. It's
important that they succeed in doing their jobs in that case, even if
they managed to interrupt a list addition in progress. 

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. 

2) Be thankful I'm only running on x86, hope that the linux kernel
isn't built with aggressive optimizations that reorder writes to
pointers, fix __list_add() so it updates pointers in the new entry 
before updating pointers in its neighbours, and do the reads with no
synchronization whatsoever. 

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. 

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? 

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. 

And as for my team, one guy favours the rculist (#1), but isn't sure it's
adequate; one guy wants to use explicit barriers (#3); and I've
optimistically implemented #2, which I know would work on FreeBSD, and
which could fairly easily be converted to using rculists. None of us
want #4.

Thanks for any insight,

--
Arlie