From e3c0465ab9bc43410b413f5e93ef8083d91f9bc5 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Wed, 6 Feb 2013 16:56:16 -0500 Subject: [PATCH] Speed up probe registration for large amount of events LTTng-UST probe registration is O(n^2). I actually left a comment that describes this, also implying that we can improve this if it becomes an issue. I've had a report from Yang Wang, who works on instrumenting the J9 VM, that O(n^2) does not agree well with 16000 probes and tracepoints. It appears that lttng_probe_register() is being too paranoid for its own good. There are now many things that are guaranteed by the way probe providers are being built. We actually need to keep a check that no provider with the same name has been registered (O(n) on the number of registered providers, could be improved with a hash table if it ever becomes necessary). Use an assert to check that each event name starts with its own provider name (it would be an internal error within the provider if it's not the case). (O(n) on the number of events within a provider) The rest is just useless, so remove this O(n^2) check. While we are there, remove the now unused lttng_event_get()/lttng_event_put() functions. Reported-by: Yang Wang Signed-off-by: Mathieu Desnoyers --- include/lttng/ust-events.h | 2 -- liblttng-ust/lttng-events.c | 2 -- liblttng-ust/lttng-probes.c | 60 ++++++++++++++++--------------------- 3 files changed, 26 insertions(+), 38 deletions(-) diff --git a/include/lttng/ust-events.h b/include/lttng/ust-events.h index 1db8e585..2a5656b5 100644 --- a/include/lttng/ust-events.h +++ b/include/lttng/ust-events.h @@ -523,8 +523,6 @@ void synchronize_trace(void); int lttng_probe_register(struct lttng_probe_desc *desc); void lttng_probe_unregister(struct lttng_probe_desc *desc); int lttng_fix_pending_event_desc(const struct lttng_event_desc *desc); -const struct lttng_event_desc *lttng_event_get(const char *name); -void lttng_event_put(const struct lttng_event_desc *desc); int lttng_probes_init(void); void lttng_probes_exit(void); int lttng_find_context(struct lttng_ctx *ctx, const char *name); diff --git a/liblttng-ust/lttng-events.c b/liblttng-ust/lttng-events.c index f70c65f5..8d316b27 100644 --- a/liblttng-ust/lttng-events.c +++ b/liblttng-ust/lttng-events.c @@ -391,7 +391,6 @@ statedump_error: WARN_ON_ONCE(__tracepoint_probe_unregister(event_name, desc->probe_callback, event)); - lttng_event_put(event->desc); register_error: free(event); cache_error: @@ -622,7 +621,6 @@ void _lttng_event_destroy(struct lttng_event *event) { struct lttng_enabler_ref *enabler_ref, *tmp_enabler_ref; - lttng_event_put(event->desc); cds_list_del(&event->node); lttng_destroy_context(event->ctx); lttng_free_event_filter_runtime(event); diff --git a/liblttng-ust/lttng-probes.c b/liblttng-ust/lttng-probes.c index 9d7d83ce..6b671da0 100644 --- a/liblttng-ust/lttng-probes.c +++ b/liblttng-ust/lttng-probes.c @@ -58,19 +58,20 @@ const struct lttng_probe_desc *find_provider(const char *provider) } static -const struct lttng_event_desc *find_event(const char *name) +int check_event_provider(struct lttng_probe_desc *desc) { - struct lttng_probe_desc *probe_desc; int i; + size_t provider_name_len; - cds_list_for_each_entry(probe_desc, &probe_list, head) { - for (i = 0; i < probe_desc->nr_events; i++) { - if (!strncmp(probe_desc->event_desc[i]->name, name, - LTTNG_UST_SYM_NAME_LEN - 1)) - return probe_desc->event_desc[i]; - } + provider_name_len = strnlen(desc->provider, + LTTNG_UST_SYM_NAME_LEN - 1); + for (i = 0; i < desc->nr_events; i++) { + if (strncmp(desc->event_desc[i]->name, + desc->provider, + provider_name_len)) + return 0; /* provider mismatch */ } - return NULL; + return 1; } int lttng_probe_register(struct lttng_probe_desc *desc) @@ -80,20 +81,28 @@ int lttng_probe_register(struct lttng_probe_desc *desc) int i; ust_lock(); + + /* + * Check if the provider has already been registered. + */ if (find_provider(desc->provider)) { ret = -EEXIST; goto end; } + /* - * TODO: This is O(N^2). Turn into a hash table when probe registration - * overhead becomes an issue. + * Each provider enforce that every event name begins with the + * provider name. Check this in an assertion for extra + * carefulness. This ensures we cannot have duplicate event + * names across providers. + */ + assert(check_event_provider(desc)); + + /* + * The provider ensures there are no duplicate event names. + * Duplicated TRACEPOINT_EVENT event names would generate a + * compile-time error due to duplicated symbol names. */ - for (i = 0; i < desc->nr_events; i++) { - if (find_event(desc->event_desc[i]->name)) { - ret = -EEXIST; - goto end; - } - } /* * We sort the providers by struct lttng_probe_desc pointer @@ -149,23 +158,6 @@ void ltt_probe_unregister(struct lttng_probe_desc *desc) lttng_probe_unregister(desc); } -/* - * called with UST lock held. - */ -const struct lttng_event_desc *lttng_event_get(const char *name) -{ - const struct lttng_event_desc *event; - - event = find_event(name); - if (!event) - return NULL; - return event; -} - -void lttng_event_put(const struct lttng_event_desc *event) -{ -} - void lttng_probes_prune_event_list(struct lttng_ust_tracepoint_list *list) { struct tp_list_entry *list_entry, *tmp; -- 2.34.1