NMIs, Locks, linked lists, barriers, and rculists, oh my!
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
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.
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? 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()?)
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.
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)
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
Hi Michi, These all look like excellent points. Thank you for responding. On Apr 04 2013, michi1@michaelblizek.twilightparadox.com wrote:
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.
If I understand correctly, if you want to deal with the NMI case, you are even more restricted than if you simply want to be called in interrupt context. The protection from interrupts that come with spinlocks doesn't help you in the case of NMI. So all you can use are trylock primitives - get the lock if available, otherwise fail. Fortunately I believe the rcu system doesn't need any locks on the reader side. (If I'm wrong about that, than I'd better stop reading the docs and start reading the code :-) I haven't actually looked at code any lower than rculist.h)
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.
That's part of my working context. I'm writing code for a family of network appliances running scientific linux 6.1 and earlier versions. They are all x86. And the code I'm attempting to enhance addresses a problem that's been addressed upstream with a rather different design. If we didn't already have working code, I'd convince the upstream patches to apply to 2.6.32 and earlier kernels (possibly painful), add support for our hardware, fix whichever of its issues bit us, add the additional features we need, and then try to upstream the lot - preferably in small patches. And if the upstream code handled NMIs well I'd copy its design.
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.
It's notable that __list_add_rcu(), from rculist.h has the order the way I want it, even in our elderly kernel version.
You should at least do atomic_read()+atomic_set(). RCU is exactly that plus a mechanism to free memory after all readers have finished.
Now I'm confused. It seems to me that part of RCU's contribution is use of barrier instructions (compiler and run-time) at appropriate points. Are you saying that atomic_read() and atomic_set() have implicit barriers? -- Arlie
Hi! On 14:03 Thu 04 Apr , Arlie Stephens wrote: ...
On Apr 04 2013, michi1@michaelblizek.twilightparadox.com wrote: ...
On 19:08 Wed 03 Apr , Arlie Stephens wrote: ...
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.
It's notable that __list_add_rcu(), from rculist.h has the order the way I want it, even in our elderly kernel version.
You should at least do atomic_read()+atomic_set(). RCU is exactly that plus a mechanism to free memory after all readers have finished.
Now I'm confused. It seems to me that part of RCU's contribution is use of barrier instructions (compiler and run-time) at appropriate points. Are you saying that atomic_read() and atomic_set() have implicit barriers?
You are right, it seems like atomic ops do not imply barriers: Documentation/atomic_ops.txt -Michi -- programing a layer 3+4 network protocol for mesh networks see http://michaelblizek.twilightparadox.com
participants (3)
-
Arlie Stephens -
michi1＠michaelblizek.twilightparadox.com -
Valdis.Kletnieks＠vt.edu