Re: [xen-unstable test] 6947: regressions - trouble: broken/fail/pass

[Keir Fraser <keir.xen@gmail.com>]

On 02/05/2011 15:04, "Jan Beulich" <JBeulich@novell.com> wrote:

>> The most straightforward way to convert to RCU with the most similar
>> synchronising semantics would be to add a 'live' boolean flag to each
>> pirq-related struct that is stored in a radix tree. Then:
>>  * insertions into radix tree would be moved before acquisition of the
>> irq_desc lock, then set 'live' under the lock
>>  * deletions would clear 'live' under the lock, then do the actual radix
>> deletion would happen after irq_desc lock release;
>>  * lookups would happen as usual under the irq_desc lock, but with an extra
>> test of the 'live' flag.
> 
> This still leaves unclear to me how an insert hitting a not-yet-deleted
> (but no longer live) entry should behave. Simply setting 'live' again
> won't help, as that wouldn't cover a delete->insert->delete all
> happening before the first delete's grace period expires. Nor would
> this work with populating the new data (prior to setting live) when
> the old data might sill be used.

Yes, this is why in my follow-up email I explained that a secondary lock is
needed that covers both logical and physical insertion/deletion. Then the
case you describe above cannot happen. As you say, event_lock covers us.

> But wait - what you describe doesn't need RCU anymore, at least
> as long as the code paths from radix tree insert to setting 'live'
> (and similarly from clearing 'live' to doing the radix tree delete) are
> fully covered by some other lock (d->event_lock, see below). Am
> I overlooking something?

No, I think you just misunderstand RCU. What I (and now also you, a bit
independently ;-) have described is how to synchronise writers against other
writers -- e.g., someone inserting concurrently with deleting, as you
describe above. What RCU is all about is synchronising *readers* against
writers, without needing a lock. And we still need it because the radix-tree
updates will happen under d->event_lock, which the readers in IRQ context
will not be holding. The main thing that RCU generally needs is that, when a
node is deleted from a structure (radix-tree in this case) it cannot be
freed until an RCU grace period because concurrent lock-free readers may
still hold a pointer to it. There are also other details to consider but
actually the whole RCU issue appears to be handled by Linux's radix-tree
implementation -- we just need to pull an up-to-date version across into
Xen.

 -- Keir