From d56fa7193ab7fa9c5ce1a35a0faf77ed04c80d20 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Wed, 16 Jan 2013 12:56:09 -0500 Subject: [PATCH] Introduce hash table for lttng_create_event_if_missing() lttng_create_event_if_missing() takes a lot of CPU time with stress-test applications containing 1000 different TRACEPOINT_EVENT() and 1000 individual tracepoint() call-site. With tracing disabled: time ./AppWith1000_lines_TP 0 real 0m2.487s user 0m2.424s sys 0m0.000s Introducing this hash table cuts the overhead very significantly when tracing is enabled: Before patch: 72.16% AppWith1000_lin liblttng-ust.so.0.0.0 [.] lttng_create_event_if_missing 25.64% AppWith1000_lin AppWith1000_lines_TP [.] a(int) time ./AppWith1000_lines_TP 0 real 0m7.946s user 0m7.864s sys 0m0.000s After patch: 89.13% AppWith1000_lin AppWith1000_lines_TP [.] a(int) 3.30% AppWith1000_lin liblttng-ust.so.0.0.0 [.] lttng_create_event_if_missing time ./AppWith1000_lines_TP 0 real 0m2.762s user 0m2.692s sys 0m0.004s Acked-by: David Goulet Acked-by: Christian Babeux Signed-off-by: Mathieu Desnoyers --- include/lttng/ust-events.h | 2 ++ liblttng-ust/lttng-events.c | 32 ++++++++++++++++++++++---------- 2 files changed, 24 insertions(+), 10 deletions(-) diff --git a/include/lttng/ust-events.h b/include/lttng/ust-events.h index 095fb1ef..1db8e585 100644 --- a/include/lttng/ust-events.h +++ b/include/lttng/ust-events.h @@ -362,6 +362,7 @@ struct lttng_event { int has_enablers_without_bytecode; /* Backward references: list of lttng_enabler_ref (ref to enablers) */ struct cds_list_head enablers_ref_head; + struct cds_hlist_node hlist; /* session ht of events */ }; struct channel; @@ -467,6 +468,7 @@ struct lttng_session { /* New UST 2.1 */ /* List of enablers */ struct cds_list_head enablers_head; + struct lttng_ust_event_ht events_ht; /* ht of events */ }; struct lttng_transport { diff --git a/liblttng-ust/lttng-events.c b/liblttng-ust/lttng-events.c index 5e6c90cb..f70c65f5 100644 --- a/liblttng-ust/lttng-events.c +++ b/liblttng-ust/lttng-events.c @@ -127,7 +127,7 @@ void synchronize_trace(void) struct lttng_session *lttng_session_create(void) { struct lttng_session *session; - int ret; + int ret, i; session = zmalloc(sizeof(struct lttng_session)); if (!session) @@ -135,6 +135,8 @@ struct lttng_session *lttng_session_create(void) CDS_INIT_LIST_HEAD(&session->chan_head); CDS_INIT_LIST_HEAD(&session->events_head); CDS_INIT_LIST_HEAD(&session->enablers_head); + for (i = 0; i < LTTNG_UST_EVENT_HT_SIZE; i++) + CDS_INIT_HLIST_HEAD(&session->events_ht.table[i]); ret = lttng_ust_uuid_generate(session->uuid); if (ret != 0) { session->uuid[0] = '\0'; @@ -329,17 +331,19 @@ int lttng_event_create(const struct lttng_event_desc *desc, { const char *event_name = desc->name; struct lttng_event *event; + struct cds_hlist_head *head; + struct cds_hlist_node *node; int ret = 0; + size_t name_len = strlen(event_name); + uint32_t hash; if (chan->used_event_id == -1U) { ret = -ENOMEM; goto full; } - /* - * This is O(n^2) (for each event, the loop is called at event - * creation). Might require a hash if we have lots of events. - */ - cds_list_for_each_entry(event, &chan->session->events_head, node) { + hash = jhash(event_name, name_len, 0); + head = &chan->session->events_ht.table[hash & (LTTNG_UST_EVENT_HT_SIZE - 1)]; + cds_hlist_for_each_entry(event, node, head, hlist) { assert(event->desc); if (!strncmp(event->desc->name, desc->name, @@ -380,6 +384,7 @@ int lttng_event_create(const struct lttng_event_desc *desc, if (ret) goto statedump_error; cds_list_add(&event->node, &chan->session->events_head); + cds_hlist_add_head(&event->hlist, head); return 0; statedump_error: @@ -499,17 +504,24 @@ void lttng_create_event_if_missing(struct lttng_enabler *enabler) cds_list_for_each_entry(probe_desc, probe_list, head) { for (i = 0; i < probe_desc->nr_events; i++) { int found = 0, ret; + struct cds_hlist_head *head; + struct cds_hlist_node *node; + const char *event_name; + size_t name_len; + uint32_t hash; desc = probe_desc->event_desc[i]; if (!lttng_desc_match_enabler(desc, enabler)) continue; + event_name = desc->name; + name_len = strlen(event_name); /* - * For each event in session event list, - * check if already created. + * Check if already created. */ - cds_list_for_each_entry(event, - &session->events_head, node) { + hash = jhash(event_name, name_len, 0); + head = &session->events_ht.table[hash & (LTTNG_UST_EVENT_HT_SIZE - 1)]; + cds_hlist_for_each_entry(event, node, head, hlist) { if (event->desc == desc) found = 1; } -- 2.34.1