Re: [lttng-dev] [rp] [RFC] Readiness for URCU release with RCU lock-free hash table
* Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote:
On Thu, May 03, 2012 at 01:13:30PM -0400, Mathieu Desnoyers wrote:
* Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote:
[...]
A write barrier would be sufficient in the case where there were only
two threads observing each other. A full memory barrier would be needed
to prevent the assertion from firing in this sort of case (not sure that
this is exactly right, but something like this):
Initial contents: B, C
T0: add A; del B
T1: if (!lookup B) { add B; del C }
T2: r1 = lookup C; smp_mb(); r2 = lookup A
assert(lookup C || lookup A);
What you are bringing here as counter-example is, I think, transitivity.
Yep!
I'm trying to figure out how your example could fail, and I cannot see
how. Follows a detail of the closest scenario I get to failing is the
following, but it does not fail. After that, I'm proposing a different
scenario, which I think will be more appropriate for the current topic.
Attempted detail of your scenario:
T0 T1 T2
add A
wmb
(add A globally
observable)
Almost. All that this really guarantees is that if someone sees
the add B, they will also see the add A.
del B
(del B globally
observable)
(add A NOT brought
into cache)
(del B brought into
cache)
read B
(test false)
add B
wmb
(add B globally
observable)
del C
(del C globally
observable)
Here, if someone sees the del C, they will see the add B, and
they also will have lost the opportunity to modify B before T1
reads from it and modifies it.
(add A NOT brought
into cache)
(del C brought into
cache)
read C - not there.
mb
(add A brought
into cache)
read A - there - success.
So we see that C is not there. We know that B would be there if
we looked at it. But we don't look at B, we look at A. But the
ordering back to T0's add A requires transitivity, which wmb
does not guarantee.
OK, got it!
If I look at the transitivity section in Linux memory-barriers.txt, I
notice that the example is mainly around using read barrier around loads
rather than general barrier. Let's see if I can modify that example to
come up with an example error case:
Initial content: empty
T0: add X
T1: r1 = lookup X; smp_mb; r2 = lookup Y
T2: add Y; r3 = lookup X
assert( !(r1 !r2 !r3) )
The key thing here is that if the barrier in T2 after add Y is a
smp_wmb rather than a smp_mb, this could allow the r3 = lookup X to be
reordered before add Y, thus allowing the assertion to fail.
Your example is simpler, and demonstrates the need just as well, so
let's go with your example.
I think it would be more intuitive for users if lookups vs updates
performed on the same thread are ordered with full memory barriers.
Given that we don't want to add extra barriers in read operations, it
would make sense to guarantee full memory barriers before and after
updates.
So how about we use full memory barriers before and after each of: add,
del (success), add_unique (success), replace, and add_replace ? If we
ever want to relax those ordering guarantees, then we can always add new
update APIs with a weaker ordering.
Thoughts ?
That line of reasoning makes a lot of sense to me!
Sounds good.
Here is what I propose, thoughts ?
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 2d8a310..2938e5e 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -203,6 +203,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
*
* Call with rcu_read_lock held.
* Threads calling this API need to be registered RCU read-side threads.
+ * This function acts as a rcu_dereference() to read the node pointer.
*/
void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
cds_lfht_match_fct match, const void *key,
@@ -226,6 +227,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long
hash,
* node returned by a previous cds_lfht_next.
* Call with rcu_read_lock held.
* Threads calling this API need to be registered RCU read-side threads.
+ * This function acts as a rcu_dereference() to read the node pointer.
*/
void cds_lfht_next_duplicate(struct cds_lfht *ht,
cds_lfht_match_fct match, const void *key,
@@ -239,6 +241,7 @@ void
Re: [lttng-dev] [rp] [RFC] Readiness for URCU release with RCU lock-free hash table
On Fri, May 04, 2012 at 12:53:12PM -0400, Mathieu Desnoyers wrote:
* Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote:
On Thu, May 03, 2012 at 01:13:30PM -0400, Mathieu Desnoyers wrote:
* Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote:
[...]
A write barrier would be sufficient in the case where there were only
two threads observing each other. A full memory barrier would be needed
to prevent the assertion from firing in this sort of case (not sure that
this is exactly right, but something like this):
Initial contents: B, C
T0: add A; del B
T1: if (!lookup B) { add B; del C }
T2: r1 = lookup C; smp_mb(); r2 = lookup A
assert(lookup C || lookup A);
What you are bringing here as counter-example is, I think, transitivity.
Yep!
I'm trying to figure out how your example could fail, and I cannot see
how. Follows a detail of the closest scenario I get to failing is the
following, but it does not fail. After that, I'm proposing a different
scenario, which I think will be more appropriate for the current topic.
Attempted detail of your scenario:
T0 T1 T2
add A
wmb
(add A globally
observable)
Almost. All that this really guarantees is that if someone sees
the add B, they will also see the add A.
del B
(del B globally
observable)
(add A NOT brought
into cache)
(del B brought into
cache)
read B
(test false)
add B
wmb
(add B globally
observable)
del C
(del C globally
observable)
Here, if someone sees the del C, they will see the add B, and
they also will have lost the opportunity to modify B before T1
reads from it and modifies it.
(add A NOT brought
into cache)
(del C brought into
cache)
read C - not there.
mb
(add A brought
into cache)
read A - there - success.
So we see that C is not there. We know that B would be there if
we looked at it. But we don't look at B, we look at A. But the
ordering back to T0's add A requires transitivity, which wmb
does not guarantee.
OK, got it!
If I look at the transitivity section in Linux memory-barriers.txt, I
notice that the example is mainly around using read barrier around loads
rather than general barrier. Let's see if I can modify that example to
come up with an example error case:
Initial content: empty
T0: add X
T1: r1 = lookup X; smp_mb; r2 = lookup Y
T2: add Y; r3 = lookup X
assert( !(r1 !r2 !r3) )
The key thing here is that if the barrier in T2 after add Y is a
smp_wmb rather than a smp_mb, this could allow the r3 = lookup X to be
reordered before add Y, thus allowing the assertion to fail.
Your example is simpler, and demonstrates the need just as well, so
let's go with your example.
I think it would be more intuitive for users if lookups vs updates
performed on the same thread are ordered with full memory barriers.
Given that we don't want to add extra barriers in read operations, it
would make sense to guarantee full memory barriers before and after
updates.
So how about we use full memory barriers before and after each of: add,
del (success), add_unique (success), replace, and add_replace ? If we
ever want to relax those ordering guarantees, then we can always add new
update APIs with a weaker ordering.
Thoughts ?
That line of reasoning makes a lot of sense to me!
Sounds good.
Here is what I propose, thoughts ?
Just to make sure I understand -- the reason that the del functions
say no memory barrier instead of acts like rcu_dereference() is
that the del functions don't return anything.
Assuming my understanding is correct:
Reviewed-by: Paul E. McKenney paul...@linux.vnet.ibm.com
Thanx, Paul
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 2d8a310..2938e5e 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -203,6 +203,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
*
* Call with rcu_read_lock held.
* Threads calling this API need to be registered RCU read-side threads.
+ * This function acts as a rcu_dereference() to read the node pointer.
*/
void cds_lfht_lookup(struct cds_lfht *ht, unsigned
Re: [lttng-dev] beginner question
On 12-05-05 12:14 AM, Loris Degioanni wrote: I just installed the lttng package on a fresh Ubuntu 12 machine, and I'm following the tutorial at http://lttng.org/quickstart. The enable-event step fails with this error: # lttng enable-event sched_switch,sys_open -k kernel event sched_switch created in channel channel0 Error: Event sys_open: Enable kernel event failed (channel channel0, session mysession) Warning: Some command(s) went wrong What am I doing wrong? Loris Hi, Can you please paste the output of: # lttng list -k -- Alexandre Montplaisir DORSAL lab, École Polytechnique de Montréal ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] beginner question
Hi, On 05/05/12 12:14 AM, Loris Degioanni wrote: I just installed the lttng package on a fresh Ubuntu 12 machine, and I'm following the tutorial at http://lttng.org/quickstart. The enable-event step fails with this error: # lttng enable-event sched_switch,sys_open -k kernel event sched_switch created in channel channel0 Error: Event sys_open: Enable kernel event failed (channel channel0, session mysession) Warning: Some command(s) went wrong What am I doing wrong? As of now, you can't enable system calls tracing one by one (sys_open is a system call), it's either all of them or none. So if you want sched_switch and all the syscalls you have to do : lttng enable-event -k sched_switch lttng enable-event -k --syscall -a Have fun, Julien ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] beginner question
On 12-05-05 12:42 AM, Julien Desfossez wrote: Hi, On 05/05/12 12:14 AM, Loris Degioanni wrote: I just installed the lttng package on a fresh Ubuntu 12 machine, and I'm following the tutorial at http://lttng.org/quickstart. The enable-event step fails with this error: # lttng enable-event sched_switch,sys_open -k kernel event sched_switch created in channel channel0 Error: Event sys_open: Enable kernel event failed (channel channel0, session mysession) Warning: Some command(s) went wrong What am I doing wrong? As of now, you can't enable system calls tracing one by one (sys_open is a system call), it's either all of them or none. So if you want sched_switch and all the syscalls you have to do : lttng enable-event -k sched_switch lttng enable-event -k --syscall -a Well, good to know I guess ;) I'll update the example on the website. Thanks for the catch Loris. Cheers, -- Alexandre Montplaisir DORSAL lab, École Polytechnique de Montréal ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
[lttng-dev] lttng enable-channel options
Is there some way to make the userspace application block if the buffer is full ? I'm thinking about something like: lttng enable-channel myblockingchannel --block I know I can increase the subbuf-size but sometimes this is not an option (embedded targets with less RAM). --block would be a fine complement for the already existing options --discard and --overwrite. What do you think ? Thanks, Paul -- Paul Woegerer | SW Development Engineer Mentor Embedded(tm) | Prinz Eugen Straße 72/2/4, Vienna, 1040 Austria P 43.1.535991320 Nucleus® | Linux® | Android(tm) | Services | UI | Multi-OS Android is a trademark of Google Inc. Use of this trademark is subject to Google Permissions. Linux is the registered trademark of Linus Torvalds in the U.S. and other countries. ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
[lttng-dev] Lttng support for RT-Patched Linux Kernel 2.6.33
Hi , I want to use LTTng on ARM processor running Linux 2.6.33 kernel with real-time patches, My quires are whether there's an LTTng port which is compatible with an RT patched Kernel, If not what's required to make it RT Patch compatible. Please kindly help me on this. Thanks In Advance, Pavan SASKEN BUSINESS DISCLAIMER: This message may contain confidential, proprietary or legally privileged information. In case you are not the original intended Recipient of the message, you must not, directly or indirectly, use, disclose, distribute, print, or copy any part of this message and you are requested to delete it and inform the sender. Any views expressed in this message are those of the individual sender unless otherwise stated. Nothing contained in this message shall be construed as an offer or acceptance of any offer by Sasken Communication Technologies Limited (Sasken) unless sent with that express intent and with due authority of Sasken. Sasken has taken enough precautions to prevent the spread of viruses. However the company accepts no liability for any damage caused by any virus transmitted by this email. Read Disclaimer at http://www.sasken.com/extras/mail_disclaimer.html ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] beginner question
First of all, that worked. Thank you. So let's suppose I only want to track a handful of system calls, what's the most efficient way to filter out everything else? Loris On 5/4/2012 9:42 PM, Julien Desfossez wrote: Hi, On 05/05/12 12:14 AM, Loris Degioanni wrote: I just installed the lttng package on a fresh Ubuntu 12 machine, and I'm following the tutorial at http://lttng.org/quickstart. The enable-event step fails with this error: # lttng enable-event sched_switch,sys_open -k kernel event sched_switch created in channel channel0 Error: Event sys_open: Enable kernel event failed (channel channel0, session mysession) Warning: Some command(s) went wrong What am I doing wrong? As of now, you can't enable system calls tracing one by one (sys_open is a system call), it's either all of them or none. So if you want sched_switch and all the syscalls you have to do : lttng enable-event -k sched_switch lttng enable-event -k --syscall -a Have fun, Julien ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] Lttng support for RT-Patched Linux Kernel 2.6.33
Hi Pavan, Hi , I want to use LTTng on ARM processor running *Linux 2.6.33 kernel with real-time patches, **My quires are** * whether there’s an LTTng port which is compatible with an RT patched Kernel, If not what’s required to make it RT Patch compatible. Please kindly help me on this. Thanks In Advance, Pavan LTTng is already working on Linux-RT kernels. You don't need to do anything more than installing LTTng ! Raphaël ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] beginner question
First of all, that worked. Thank you. So let's suppose I only want to track a handful of system calls, what's the most efficient way to filter out everything else? You can't filter at the source for now, you need to trace all system calls, so your filtering will be done at analysis time. If you are using babeltrace, you can just use grep on the output. For example : babeltrace /path/to/your/trace | grep -E sched_switch|sys_open I know that's not really pretty, but for now it is the only option. Soon the full-fledged trace viewers will allow a cleaner way to filter and eventually we'll be able to select exactly the syscalls we want. Hope this helps, Julien ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
