On Apr 04 2013, Valdis.Kletnieks@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@worldash.org)