[lttng-dev] URCU accessing rcu_head->func

[lttng-dev] URCU accessing rcu_head->func

[Mathieu Desnoyers]

----- Original Message -----
> From: "Florian Lohoff" <f@zz.de>
> To: lttng-dev at lists.lttng.org
> Sent: Friday, January 31, 2014 3:16:32 PM
> Subject: [lttng-dev] URCU accessing rcu_head->func
> 
> 
> Hi,
> 
> i am having multiple timer which can issue a call_rcu on an object using
> an rcu_head.
> 
> It can happen than an object is already on the call_rcu list
> for destruction and another timer fires.
> 
> So i am doing something like this.
> 
> 	if (!rs->rcuhead.func) {
> 		call_rcu(&rs->rcuhead, free_obj);
> 	}
> 
> I have a feeling in my gut that this didnt blow up
> just by accident and i am doing something utterly stupid.
> 
> I am in the read side critical section so my structure
> cant appear under my feet but the above can be racy at
> best.

I guess you meant "disappear" here ?

> 
> What would be the best way to achieve something like:
> 
> 	"queue for call_rcu if not already queued"
> 
> Another flag with an atomic inc or something?

Indeed, the scheme you describe above seems to be racy, since there could be
two or more read-side critical sections accessing the same object concurrently,
and doing two call_rcu() enqueuing the same object (same linked list node) twice
into the call_rcu lists will simply corrupt those lists.

Let me first rephrase your intent here just to make sure I understand: you use
RCU read-side to provide existence guarantee on the "rs" object, and you want
to enqueue the object rcuhead with call_rcu() for deletion (free_obj) after a
grace period has elapsed.

Assuming you care about keeping this code path wait-free or lock-free (at least),
using uatomic_xchg() would allow you to set an atomic flag and know, from the
returned value, whether you "own" the object reclaim or not. You can then decide
whether or not call_rcu() needs to be called based on the value read by
uatomic_xchg().

You could do something similar with mutexes, but then you would lose the
wait-freedom characteristic of this code path, which I am guessing is one
key reason why you use RCU read-side lock and call_rcu() in the first place.

Does it make sense ?

Thanks,

Mathieu



> 
> Flo
> --
> Florian Lohoff                                                 f at zz.de
> 
> _______________________________________________
> lttng-dev mailing list
> lttng-dev at lists.lttng.org
> http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> 

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

[lttng-dev] URCU accessing rcu_head->func

[Florian Lohoff]

Hi, Mathieu,

On Mon, Feb 03, 2014 at 03:37:38AM +0000, Mathieu Desnoyers wrote:
> > 
> > I am in the read side critical section so my structure
> > cant appear under my feet but the above can be racy at
> > best.
> 
> I guess you meant "disappear" here ?

Yep

> > What would be the best way to achieve something like:
> > 
> > 	"queue for call_rcu if not already queued"
> > 
> > Another flag with an atomic inc or something?
> 
> Indeed, the scheme you describe above seems to be racy, since there could be
> two or more read-side critical sections accessing the same object concurrently,
> and doing two call_rcu() enqueuing the same object (same linked list node) twice
> into the call_rcu lists will simply corrupt those lists.
> 
> Let me first rephrase your intent here just to make sure I understand: you use
> RCU read-side to provide existence guarantee on the "rs" object, and you want
> to enqueue the object rcuhead with call_rcu() for deletion (free_obj) after a
> grace period has elapsed.
> 
> Assuming you care about keeping this code path wait-free or lock-free (at least),
> using uatomic_xchg() would allow you to set an atomic flag and know, from the
> returned value, whether you "own" the object reclaim or not. You can then decide
> whether or not call_rcu() needs to be called based on the value read by
> uatomic_xchg().
> 
> You could do something similar with mutexes, but then you would lose the
> wait-freedom characteristic of this code path, which I am guessing is one
> key reason why you use RCU read-side lock and call_rcu() in the first place.
> 
> Does it make sense ?

I solved it a little different. I am using a RCU hash for keeping the 
data structures and i simply took the reasult of cds_lfht_del
or cds_lfht_add_replace.

If i successfully remove my structure from the hash i queue for later
destruction. As the removal should only happen successfully once i should
be done.

Its just a little bit more tricky to get correct. 

Flo
-- 
Florian Lohoff                                                 f at zz.de
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 828 bytes
Desc: Digital signature
URL: <http://lists.lttng.org/pipermail/lttng-dev/attachments/20140203/ef086497/attachment.pgp>

[lttng-dev] URCU accessing rcu_head->func

[Mathieu Desnoyers]

----- Original Message -----
> From: "Florian Lohoff" <f@zz.de>
> To: "Mathieu Desnoyers" <mathieu.desnoyers at efficios.com>
> Cc: lttng-dev at lists.lttng.org, "Paul E. McKenney" <paulmck at linux.vnet.ibm.com>
> Sent: Monday, February 3, 2014 2:52:59 AM
> Subject: Re: [lttng-dev] URCU accessing rcu_head->func
> 
> 
> Hi, Mathieu,
> 
> On Mon, Feb 03, 2014 at 03:37:38AM +0000, Mathieu Desnoyers wrote:
> > > 
> > > I am in the read side critical section so my structure
> > > cant appear under my feet but the above can be racy at
> > > best.
> > 
> > I guess you meant "disappear" here ?
> 
> Yep
> 
> > > What would be the best way to achieve something like:
> > > 
> > > 	"queue for call_rcu if not already queued"
> > > 
> > > Another flag with an atomic inc or something?
> > 
> > Indeed, the scheme you describe above seems to be racy, since there could
> > be
> > two or more read-side critical sections accessing the same object
> > concurrently,
> > and doing two call_rcu() enqueuing the same object (same linked list node)
> > twice
> > into the call_rcu lists will simply corrupt those lists.
> > 
> > Let me first rephrase your intent here just to make sure I understand: you
> > use
> > RCU read-side to provide existence guarantee on the "rs" object, and you
> > want
> > to enqueue the object rcuhead with call_rcu() for deletion (free_obj) after
> > a
> > grace period has elapsed.
> > 
> > Assuming you care about keeping this code path wait-free or lock-free (at
> > least),
> > using uatomic_xchg() would allow you to set an atomic flag and know, from
> > the
> > returned value, whether you "own" the object reclaim or not. You can then
> > decide
> > whether or not call_rcu() needs to be called based on the value read by
> > uatomic_xchg().
> > 
> > You could do something similar with mutexes, but then you would lose the
> > wait-freedom characteristic of this code path, which I am guessing is one
> > key reason why you use RCU read-side lock and call_rcu() in the first
> > place.
> > 
> > Does it make sense ?
> 
> I solved it a little different. I am using a RCU hash for keeping the
> data structures and i simply took the reasult of cds_lfht_del
> or cds_lfht_add_replace.
> 
> If i successfully remove my structure from the hash i queue for later
> destruction. As the removal should only happen successfully once i should
> be done.
> 
> Its just a little bit more tricky to get correct.

Indeed! We have the return value to del/add replace in place for this
kind of use-case, and it does get you the same result as using the flag
technique.

Thanks,

Mathieu

> 
> Flo
> --
> Florian Lohoff                                                 f at zz.de
> 

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com