Re: [lttng-dev] [PATCH v2 0/4] userspace-rcu: Add lock-free, ordered singly linked list
- On Jul 30, 2019, at 9:34 AM, Junchang Wang junchangw...@gmail.com wrote: > On Mon, Jul 29, 2019 at 9:55 PM Mathieu Desnoyers > wrote: >> >> - On Jul 29, 2019, at 9:35 AM, Junchang Wang junchangw...@gmail.com >> wrote: >> >> > Hi Mathieu and the list, >> > >> > I'm recently using userspace-rcu to build lock-free data structures. >> > Thanks for >> > sharing this excellent project! >> > >> > In building a hash table, I am looking for an ordered singly linked list >> > that is lock-free. It seems such a list is missing in userspace-rcu. I >> > discussed this with Paul in the mailing list of perfbook, and he kindly >> > suggested me to submit my implementation to userspace-rcu. So here is the >> > RFC. Any comments and suggestions are warmly welcome. >> >> One point worth mentioning: the rculfhash data structure (rcu lock-free hash >> table) already implements such list internally. You might want to have a look >> at it, and perhaps just lift out its implementation into a separate .c file >> and header file so we can expose its implementation publicly ? >> >> Items are linked through the struct cds_lfht_node next field. >> >> The struct cds_lfht_iter is used as a iterator on the list. >> >> struct cds_lfht tbl_oder, tbl_chunk and tbl_mmap contain the >> linked lists heads for each memory allocation scheme. > > Hi Mathieu, > > Thanks for the note. I checked rculfhash today, and the list > implementation within rculfhash is indeed quite similar to the one I'm > working on. I will check to see if we can merge the two versions and > provide an independent rculflist. Great! > >> >> I'm wondering why you need to re-implement a hash table though. What is >> missing from rculfhash to suit your needs ? >> > > The major reason is that I want a hash table that can change its hash > function on-the-fly. Split-ordered list is not adequate because it can > only increase/decrease the number of buckets. Besides, I doubt the > reverse operation is always efficient on platforms where hardware > cannot help reverse bit strings. Hence I'm working on the new hash > table algorithm, which, of course, is built on top of the linked list > we are working on :-). That makes a lot of sense. Re-hasing is indeed the main feature missing from rculfhash. I have ideas on how it could be introduced within the current split-ordered implementation with only small changes. One possibility would be to create two lists (rather than one): the current list, and a second list that would be used when a re-hasing is performed. The old list would be used by readers while re-hashing is in progress, and add/del would take care of both lists when done concurrently with re-hashing. After re-hasing is complete, the old list would not be used anymore after a grace period has passed. The cost of this approach is to have two next pointers per node (rather than one). An alternative would be to add a temporary layer of indirection when the re-hasing is performed. The "next" pointer would actually point to an intermediate object which contains the chaining information for both the old and the new lists. This would save the cost of the additional next pointer within each node, at the expense of doing extra temporary memory allocation when doing the re-hashing. I'd also be curious to see benchmarks of the bit-reversal compared to the rest of the operations needed for lookup, addition, and removal in a lock-free hash table for the main architectures that matter today. What architectures do you care about ? I'm also curious to see what new hash table algorithm you have in mind! Thanks, Mathieu > > Thanks, > --Junchang > >> Thanks, >> >> Mathieu >> >> >> > >> > This singly linked list is based on the following research paper: >> > - Maged M. Michael. High performance dynamic lock-free hash tables >> > and list-based sets. In Proceedings of the fourteenth annual ACM >> > symposium on Parallel algorithms and architectures, ACM Press, >> > (2002), 73-82. >> > >> > And we made the following two major improvements: >> > (1) Insert, Delete, and Find operations are protected by RCU read_lock, >> > such that the existence guarantees are provided by the RCU mechanism, >> > and that no special memory management schemes (e.g., hazard pointers) >> > is required anymore. >> > (2) The use of the RCU mechanism can naturally prevent the ABA problem, >> > such that no flag field is required in this implementation. Hence, >> > we save a variable of 8 bytes (typically sizeof(long)) for each node. >> > >> > In the past two weeks, I found some bugs in the first version of the >> > list in building a lock-free hash table on top it. So this is the second >> > version which fixes the known issues. Please review this version, if >> > possible. The major changes are as follows. Sorry for the inconvenience. >> > Any suggestions and comments are warmly welcome. >> > >> > v1 -> v2: >> > - Functions insert(), delete(), and find() return 0
[lttng-dev] Tracing Summit 2019 - Schedule Release
Hi all, We're happy to announce the schedule for the Tracing Summit 2019 is now available. We are going to have an amazing conference with diverse topics such as trace analysis, GPU tracing, distributed systems tracing and more. Checkout the schedule and talk abstracts on the website.[1] Tracing Summit 2019 will be held in San Diego, California on August 20th, 2019, Don't forget to register for the summit either when buying your Open Source Summit ticket or using this link [2]! See you in August! The Tracing Summit Organizers [1] https://tracingsummit.org/wiki/TracingSummit2019 [2] https://www.cvent.com/events/tracing-summit-2019/registration-63351d06945a46d890b8e5a200dbc0fc.aspx?fqp=true -- Francis Deslauriers Computer Engineer EfficiOS inc. ___ lttng-dev mailing list lttng-dev@lists.lttng.org https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] [PATCH lttng-ust v2] Fix: wait for initial statedump before proceeding to the main program
Merged into master, 2.11, 2.10, 2.9, thanks!
Mathieu
- On Jul 29, 2019, at 6:05 PM, Gabriel-Andrew Pollo-Guilbert
gabriel.pollo-guilb...@efficios.com wrote:
> In the case of short lived applications, the application may exit before
> the initial statedump has completed.
>
> Higher-level trace analysis features such as translating addresses to
> symbols rely on statedump. That information is required for those
> analyses to work on such short-lived applications.
>
> Force the statedump to occur before handing the control to the
> application.
>
> Fixes #1190
>
> Signed-off-by: Gabriel-Andrew Pollo-Guilbert
>
> Signed-off-by: Mathieu Desnoyers
> ---
> v2:
> * renamed constructor_sem_posted -> registration_done
> * add sem_count_initial_value
> * add assert in decrement_sem_count()
> * edit documentation for handle_pending_statedump
> * reset registration_done and initial_statedump_done in
> cleanup_sock_info
>
> liblttng-ust/lttng-ust-comm.c | 88 ++-
> 1 file changed, 67 insertions(+), 21 deletions(-)
>
> diff --git a/liblttng-ust/lttng-ust-comm.c b/liblttng-ust/lttng-ust-comm.c
> index a299ba84..0c6db9fe 100644
> --- a/liblttng-ust/lttng-ust-comm.c
> +++ b/liblttng-ust/lttng-ust-comm.c
> @@ -228,7 +228,11 @@ static sem_t constructor_wait;
> /*
> * Doing this for both the global and local sessiond.
> */
> -static int sem_count = { 2 };
> +enum {
> + sem_count_initial_value = 4,
> +};
> +
> +static int sem_count = sem_count_initial_value;
>
> /*
> * Counting nesting within lttng-ust. Used to ensure that calling fork()
> @@ -243,7 +247,7 @@ struct sock_info {
> const char *name;
> pthread_t ust_listener; /* listener thread */
> int root_handle;
> - int constructor_sem_posted;
> + int registration_done;
> int allowed;
> int global;
> int thread_active;
> @@ -256,6 +260,7 @@ struct sock_info {
> char *wait_shm_mmap;
> /* Keep track of lazy state dump not performed yet. */
> int statedump_pending;
> + int initial_statedump_done;
> };
>
> /* Socket from app (connect) to session daemon (listen) for communication */
> @@ -264,6 +269,7 @@ struct sock_info global_apps = {
> .global = 1,
>
> .root_handle = -1,
> + .registration_done = 0,
> .allowed = 0,
> .thread_active = 0,
>
> @@ -274,6 +280,7 @@ struct sock_info global_apps = {
> .wait_shm_path = "/" LTTNG_UST_WAIT_FILENAME,
>
> .statedump_pending = 0,
> + .initial_statedump_done = 0,
> };
>
> /* TODO: allow global_apps_sock_path override */
> @@ -282,6 +289,7 @@ struct sock_info local_apps = {
> .name = "local",
> .global = 0,
> .root_handle = -1,
> + .registration_done = 0,
> .allowed = 0, /* Check setuid bit first */
> .thread_active = 0,
>
> @@ -289,6 +297,7 @@ struct sock_info local_apps = {
> .notify_socket = -1,
>
> .statedump_pending = 0,
> + .initial_statedump_done = 0,
> };
>
> static int wait_poll_fallback;
> @@ -621,45 +630,81 @@ int send_reply(int sock, struct ustcomm_ust_reply *lur)
> }
>
> static
> -int handle_register_done(struct sock_info *sock_info)
> +void decrement_sem_count(unsigned int count)
> {
> int ret;
>
> - if (sock_info->constructor_sem_posted)
> - return 0;
> - sock_info->constructor_sem_posted = 1;
> + assert(uatomic_read(_count) >= count);
> +
> if (uatomic_read(_count) <= 0) {
> - return 0;
> + return;
> }
> - ret = uatomic_add_return(_count, -1);
> +
> + ret = uatomic_add_return(_count, -count);
> if (ret == 0) {
> ret = sem_post(_wait);
> assert(!ret);
> }
> +}
> +
> +static
> +int handle_register_done(struct sock_info *sock_info)
> +{
> + if (sock_info->registration_done)
> + return 0;
> + sock_info->registration_done = 1;
> +
> + decrement_sem_count(1);
> +
> + return 0;
> +}
> +
> +static
> +int handle_register_failed(struct sock_info *sock_info)
> +{
> + if (sock_info->registration_done)
> + return 0;
> + sock_info->registration_done = 1;
> + sock_info->initial_statedump_done = 1;
> +
> + decrement_sem_count(2);
> +
> return 0;
> }
>
> /*
> * Only execute pending statedump after the constructor semaphore has
> - * been posted by each listener thread. This means statedump will only
> - * be performed after the "registration done" command is received from
> - * each session daemon the application is connected to.
> + * been posted by the current listener thread. This means statedump will
> + * only be performed after the "registration done" command is received
> + * from this thread's session daemon.
> *
> * This ensures we don't run into deadlock issues with the dynamic
> * loader mutex, which is held while the constructor is called and
> * waiting on the constructor semaphore. All operations
Re: [lttng-dev] gcc plugin for instrumenting individual functions
Hi, On Mon, 29 Jul 2019 at 21:23, Jonathan Rajotte-Julien < jonathan.rajotte-jul...@efficios.com> wrote: > Hi, > > For those at home wondering why this would be relevant to lttng, > lttng-ust comes with a utility shared object allowing you to leverage the > -finstrument-function sites to hook lttng tracepoints [1]. > > [1] https://lttng.org/man/3/lttng-ust-cyg-profile/v2.10/ > > Thank you for providing some context! > Thanks Christophe for this contribution. > > Do you know why GCC does not support this out of the box? > I'm not sure. I looked at the the relevant parts of the gcc codebase, and came to the conclusion that it just wasn't written with this feature in mind (which is why the plugin uses a sort of workaround). Is this something that > could be presented to the GCC community? If people think it should be presented! Christophe ___ lttng-dev mailing list lttng-dev@lists.lttng.org https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] 回复:Re: 回复:Re: Pros and Cons of LTTng
Hi, The current LTTng kernel tracer (lttng-modules) supports Linux 3.0+ only. If you only need to trace user-space, you might be able to use lttng-tools and lttng-ust on an older kernel. Please refer to the README.md files of each project for information about their environment prerequisites. The RHEL6 kernel variant based on 2.6.32-2.6.35 Linux kernels has never been supported by the LTTng 2.x kernel tracers without kernel patching. Thanks, Mathieu - On Jul 29, 2019, at 8:34 PM, 杨海 wrote: > Hi Mathieu, > Thanks. I am looking for packages for older distributions like CentOS 6 (with > kernel 2.6) but could not find it. And which kernel version is minimum > requirement for LTTng? > Regards > Hai > -- Original -- > From: "Mathieu Desnoyers"; > Date: Thu, Jul 25, 2019 11:48 PM > To: "杨海"; > Cc: "Jonathan Rajotte"; > "lttng-dev"; > Subject: Re: [lttng-dev] 回复:Re: 回复:Re: Pros and Cons of LTTng > - On Jul 25, 2019, at 4:21 PM, 杨海 wrote: >> Hi >> Thanks for quick response. >> LTTng is really impressive on performance，especially under heavy workload. >> When >> using it on critical machines，stability is also essential. >> I wonder how LTTng is commercialized and any products or OS distributions >> already enabled it. >> I took a look at lttng-modules bug list，there are a few kernel oops years ago >> and got resolved. May I say it is very stable or it has not been fully >> tested? > Hi, > EfficiOS has had commercial customers using LTTng in production for many years > now. > LTTng per-se is distributed as packages in all major Linux distributions. > EfficiOS also provides > more up-to-date packages for some distributions through [ > http://packages.efficios.com/ | http://packages.efficios.com/ ] > The way we commercialize LTTng is through funding for design and > implementation > of > customer's feature requests. We also provide commercial support tailored to > specific > customer's environments, which includes SLA and continuous integration testing > of specific > environments. > If those are services you are interested in, please feel free to contact us in > private so we > can further discuss your needs. > Best regards, > Mathieu >> regards >> Hai >> --原始邮件-- >> 发件人："Jonathan Rajotte-Julien "; >> 发送时间：2019年7月23日(星期二) 上午6:20 >> 收件人："杨海" ; >> 抄送："lttng-dev "; >> 主题：Re: 回复:Re: [lttng-dev] Pros and Cons of LTTng >> --- >> Hi, >>> As to LD_PRELOAD, it is also used for privilege escalation. Will it be >>> regarded >> > as vulnerability and forbidden on some Linux systems? >> It could yes. >> In that case you will be limited to the syscalls interface for the libc >> observability unless you instrument it and distribute it. >> Cheers. >> ___ >> lttng-dev mailing list >> lttng-dev@lists.lttng.org >> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev > -- > Mathieu Desnoyers > EfficiOS Inc. > http://www.efficios.com -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com ___ lttng-dev mailing list lttng-dev@lists.lttng.org https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] [PATCH v2 0/4] userspace-rcu: Add lock-free, ordered singly linked list
On Mon, Jul 29, 2019 at 9:55 PM Mathieu Desnoyers wrote: > > - On Jul 29, 2019, at 9:35 AM, Junchang Wang junchangw...@gmail.com wrote: > > > Hi Mathieu and the list, > > > > I'm recently using userspace-rcu to build lock-free data structures. Thanks > > for > > sharing this excellent project! > > > > In building a hash table, I am looking for an ordered singly linked list > > that is lock-free. It seems such a list is missing in userspace-rcu. I > > discussed this with Paul in the mailing list of perfbook, and he kindly > > suggested me to submit my implementation to userspace-rcu. So here is the > > RFC. Any comments and suggestions are warmly welcome. > > One point worth mentioning: the rculfhash data structure (rcu lock-free hash > table) already implements such list internally. You might want to have a look > at it, and perhaps just lift out its implementation into a separate .c file > and header file so we can expose its implementation publicly ? > > Items are linked through the struct cds_lfht_node next field. > > The struct cds_lfht_iter is used as a iterator on the list. > > struct cds_lfht tbl_oder, tbl_chunk and tbl_mmap contain the > linked lists heads for each memory allocation scheme. Hi Mathieu, Thanks for the note. I checked rculfhash today, and the list implementation within rculfhash is indeed quite similar to the one I'm working on. I will check to see if we can merge the two versions and provide an independent rculflist. > > I'm wondering why you need to re-implement a hash table though. What is > missing from rculfhash to suit your needs ? > The major reason is that I want a hash table that can change its hash function on-the-fly. Split-ordered list is not adequate because it can only increase/decrease the number of buckets. Besides, I doubt the reverse operation is always efficient on platforms where hardware cannot help reverse bit strings. Hence I'm working on the new hash table algorithm, which, of course, is built on top of the linked list we are working on :-). Thanks, --Junchang > Thanks, > > Mathieu > > > > > > This singly linked list is based on the following research paper: > > - Maged M. Michael. High performance dynamic lock-free hash tables > > and list-based sets. In Proceedings of the fourteenth annual ACM > > symposium on Parallel algorithms and architectures, ACM Press, > > (2002), 73-82. > > > > And we made the following two major improvements: > > (1) Insert, Delete, and Find operations are protected by RCU read_lock, > > such that the existence guarantees are provided by the RCU mechanism, > > and that no special memory management schemes (e.g., hazard pointers) > > is required anymore. > > (2) The use of the RCU mechanism can naturally prevent the ABA problem, > > such that no flag field is required in this implementation. Hence, > > we save a variable of 8 bytes (typically sizeof(long)) for each node. > > > > In the past two weeks, I found some bugs in the first version of the > > list in building a lock-free hash table on top it. So this is the second > > version which fixes the known issues. Please review this version, if > > possible. The major changes are as follows. Sorry for the inconvenience. > > Any suggestions and comments are warmly welcome. > > > > v1 -> v2: > > - Functions insert(), delete(), and find() return 0 in success, and > >return -Exxx otherwise. > > - Fix a bug in function is_removed(). > > > > Cheers, > > --Junchang > > > > Junchang Wang (4): > > userspace-rcu: Add lock-free singly linked list rculflist > > userspace-rcu: Add sample code of rculflist > > userspace-rcu: Update Makefile.am to include rculflist into the > >project > > userspace-rcu: Add a brief description of rculflist in cds-api.md > > > > doc/cds-api.md | 7 + > > doc/examples/rculflist/Makefile| 24 ++ > > .../rculflist/Makefile.cds_lflist_delete_rcu | 21 ++ > > .../rculflist/Makefile.cds_lflist_find_rcu | 21 ++ > > .../rculflist/Makefile.cds_lflist_insert_rcu | 21 ++ > > doc/examples/rculflist/cds_lflist_delete_rcu.c | 101 > > doc/examples/rculflist/cds_lflist_find_rcu.c | 96 +++ > > doc/examples/rculflist/cds_lflist_insert_rcu.c | 69 + > > include/Makefile.am| 1 + > > include/urcu/cds.h | 1 + > > include/urcu/rculflist.h | 284 > > + > > 11 files changed, 646 insertions(+) > > create mode 100644 doc/examples/rculflist/Makefile > > create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_delete_rcu > > create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_find_rcu > > create mode 100644 doc/examples/rculflist/Makefile.cds_lflist_insert_rcu > > create mode 100644 doc/examples/rculflist/cds_lflist_delete_rcu.c > > create mode 100644 doc/examples/rculflist/cds_lflist_find_rcu.c > > create
