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

[Arlie Stephens]

On Apr 04 2013, Valdis.Kletnieks at vt.edu wrote:
> On Wed, 03 Apr 2013 19:08:45 -0700, Arlie Stephens said:
> 
> > - I've got a linked list, with entries occassionally added from normal
> > contexts.
> > - Entries are never deleted from the list.
> 
> This is already busted - you *will* eventually OOM the system this
> way.

Probably not. I'm expecting the list to be very short. 

> > 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.
> 
> At that point, you need to be *really* specific on what the semantics
> of "succeed" really are.  In particular, do they merely need to
> succeed at reading a single specific entry, or the entire list?

I need to be able to move to the 'next' item, perhaps repeatedly,
without missing any items which had already been completely added. 

I generally will not be doing this by starting at the first element
and going on to the end (foreach); instead I'll be starting at some
arbitrary element.

If I'm racing with an update, I don't care whether or not I see the
item that's being added, as long as I don't follow bad pointers. 
If I see the new item, I had better see all of it, including a sane
'next' pointer. 

I can live without following the 'prev' pointer chain. 

> You should also be clear on why panic() and oops need to poke the list
> (hint - if you're in panic(), you're there because the kernel is already
> convinced things are too screwed up to continue, so why should you
> trust your list enough to walk across it during panic()?)

Obviously I can't trust anything 100%.

However, the feature I'm working on is analagous to pstore - its job
is to try to get information out in the event of a failure.

If pstore were a little bit more mature, I'd be using/extending it.
It's not, particularly not in the versions available in RHEL 6.1 and
earlier, which is the environment I'm living in. *sigh* 

> > 1) Use an rculist, and hope that it really does cover this
> > situation.
> 
> That's probably safe/sufficient, as long as the read semantics of
> an RCU-protected region are acceptable. In particular, check the
> behavior of when an update happens, compared to when it becomes
> visible to readers.

I'm still trying to really wrap my mind around what rculist actually
does. I've worked on the Itanium (IA64) with its cache incoherency and
intense use of speculative fetches etc., so the principles seem to
make sense. But I find I'm not entirely confident in my understanding.

Some of that is probably because it's doing things I don't care about, 
in order to handle deletion. (I don't need any of the _copy_
semantics, as far as I can see. I just need barriers in the right
places. Unless of course I ever decide to support deletion, whereupon
leaving deleted elements available for an appropriate time period
becomes important. )

Maybe I'm just dense. I'm certainly feeling that way at the moment.

--
Arlie

(Arlie Stephens					arlie at worldash.org)