From 9d239bd92ef3198e80333c703f3ab8ff8cdaeaf7 Mon Sep 17 00:00:00 2001 From: compudj Date: Sun, 21 Aug 2005 02:04:38 +0000 Subject: [PATCH] hook by ID optimisation for incoming 10k index size : 256 facilities * 10 events * 4 bytes git-svn-id: http://ltt.polymtl.ca/svn@1034 04897980-b3bd-0310-b5e0-8ef037075253 --- ltt/branches/poly/ltt/ltt.h | 1 + ltt/branches/poly/ltt/type.c | 7 ++- ltt/branches/poly/lttv/lttv/hook.c | 44 ++++++++++++++----- ltt/branches/poly/lttv/lttv/hook.h | 7 ++- ltt/branches/poly/lttv/lttv/state.c | 43 +++++++++++++------ ltt/branches/poly/lttv/lttv/stats.c | 50 +++++++++++++++------- ltt/branches/poly/lttv/lttv/tracecontext.c | 27 ++++++------ 7 files changed, 124 insertions(+), 55 deletions(-) diff --git a/ltt/branches/poly/ltt/ltt.h b/ltt/branches/poly/ltt/ltt.h index 081d12ca..5154c05b 100644 --- a/ltt/branches/poly/ltt/ltt.h +++ b/ltt/branches/poly/ltt/ltt.h @@ -68,6 +68,7 @@ associated to the trace. */ #define NUM_FACILITIES 256 +#define AVG_EVENTS_PER_FACILITIES 10 typedef struct _LttTrace LttTrace; diff --git a/ltt/branches/poly/ltt/type.c b/ltt/branches/poly/ltt/type.c index e153d540..4b09e3f7 100644 --- a/ltt/branches/poly/ltt/type.c +++ b/ltt/branches/poly/ltt/type.c @@ -357,12 +357,17 @@ LttField *ltt_field_member(LttField *f, unsigned i) { LttField *field_member; + g_assert(f->field_type->type_class == LTT_STRUCT || + f->field_type->type_class == LTT_UNION); + g_assert(i < f->field_type->element_number); +#if 0 if(unlikely( f->field_type->type_class != LTT_STRUCT && f->field_type->type_class != LTT_UNION) || i >= f->field_type->element_number ) field_member = NULL; else - field_member = f->child[i]; +#endif //0 + field_member = f->child[i]; return field_member; } diff --git a/ltt/branches/poly/lttv/lttv/hook.c b/ltt/branches/poly/lttv/lttv/hook.c index 04d1a748..0ec85653 100644 --- a/ltt/branches/poly/lttv/lttv/hook.c +++ b/ltt/branches/poly/lttv/lttv/hook.c @@ -22,6 +22,7 @@ #include #include +#include typedef struct _LttvHookClosure { LttvHook hook; @@ -397,10 +398,20 @@ gboolean lttv_hooks_call_check_merge(LttvHooks *h1, void *call_data1, } +/* Two pointer arrays : + * * one indexed by id for quick search : + * size : max id + * typically 4 bytes * 256 facilities * 10 events = 10kbytes + * * another array that keeps a list of used numbers (for later deletion) + * size : number of ids used. + */ LttvHooksById *lttv_hooks_by_id_new() { - return g_ptr_array_new(); + LttvHooksById *h = g_new(LttvHooksById, 1); + h->index = g_ptr_array_sized_new(NUM_FACILITIES * AVG_EVENTS_PER_FACILITIES); + h->array = g_array_sized_new(FALSE, FALSE, sizeof(guint), 50); + return h; } @@ -408,31 +419,42 @@ void lttv_hooks_by_id_destroy(LttvHooksById *h) { guint i; - for(i = 0 ; i < h->len ; i++) { - if(h->pdata[i] != NULL) lttv_hooks_destroy((LttvHooks *)(h->pdata[i])); + for(i = 0 ; i < h->array->len ; i++) { + guint index = g_array_index(h->array, guint, i); + if(h->index->pdata[index] != NULL) { /* hook may have been removed */ + lttv_hooks_destroy(h->index->pdata[index]); + h->index->pdata[index] = NULL; /* Must be there in case of + multiple addition of the same index */ + } } - g_ptr_array_free(h, TRUE); + g_ptr_array_free(h->index, TRUE); + g_array_free(h->array, TRUE); } /* Optimised for searching an existing hook */ LttvHooks *lttv_hooks_by_id_find(LttvHooksById *h, unsigned id) { - if(unlikely(h->len <= id)) g_ptr_array_set_size(h, id + 1); - if(unlikely(h->pdata[id] == NULL)) h->pdata[id] = lttv_hooks_new(); - return h->pdata[id]; + if(unlikely(h->index->len <= id)) g_ptr_array_set_size(h->index, id + 1); + if(unlikely(h->index->pdata[id] == NULL)) { + h->index->pdata[id] = lttv_hooks_new(); + g_array_append_val(h->array, id); + } + return h->index->pdata[id]; } unsigned lttv_hooks_by_id_max_id(LttvHooksById *h) { - return h->len; + return h->index->len; } +/* We don't bother removing the used slot array id : lttv_hooks_by_id_destroy is + * almost never called and is able to deal with used slot repetition. */ void lttv_hooks_by_id_remove(LttvHooksById *h, unsigned id) { - if(likely(id < h->len && h->pdata[id] != NULL)) { - lttv_hooks_destroy((LttvHooks *)h->pdata[id]); - h->pdata[id] = NULL; + if(likely(id < h->index->len && h->index->pdata[id] != NULL)) { + lttv_hooks_destroy((LttvHooks *)h->index->pdata[id]); + h->index->pdata[id] = NULL; } } diff --git a/ltt/branches/poly/lttv/lttv/hook.h b/ltt/branches/poly/lttv/lttv/hook.h index 12272035..b62ddcfc 100644 --- a/ltt/branches/poly/lttv/lttv/hook.h +++ b/ltt/branches/poly/lttv/lttv/hook.h @@ -123,7 +123,10 @@ gboolean lttv_hooks_call_check_merge(LttvHooks *h1, void *call_data1, /* Sometimes different hooks need to be called based on the case. The case is represented by an unsigned integer id */ -typedef GPtrArray LttvHooksById; +typedef struct _LttvHooksById { + GPtrArray *index; + GArray *array; +} LttvHooksById; /* Create and destroy a hooks by id list */ @@ -148,7 +151,7 @@ unsigned lttv_hooks_by_id_max_id(LttvHooksById *h); static inline LttvHooks *lttv_hooks_by_id_get(LttvHooksById *h, unsigned id) { LttvHooks *ret; - if(likely(id < h->len)) ret = h->pdata[id]; + if(likely(id < h->index->len)) ret = h->index->pdata[id]; else ret = NULL; return ret; diff --git a/ltt/branches/poly/lttv/lttv/state.c b/ltt/branches/poly/lttv/lttv/state.c index 274d5f48..95d6a5a5 100644 --- a/ltt/branches/poly/lttv/lttv/state.c +++ b/ltt/branches/poly/lttv/lttv/state.c @@ -1022,9 +1022,14 @@ static gboolean irq_entry(void *hook_data, void *call_data) { LttvTracefileState *s = (LttvTracefileState *)call_data; LttEvent *e = ltt_tracefile_get_event(s->parent.tf); + guint8 fac_id = ltt_event_facility_id(e); + guint8 ev_id = ltt_event_eventtype_id(e); LttvTraceHookByFacility *thf = lttv_trace_hook_get_fac((LttvTraceHook *)hook_data, ltt_event_facility_id(e)); + // g_assert(lttv_trace_hook_get_first((LttvTraceHook *)hook_data)->f1 != NULL); + g_assert(thf->f1 != NULL); + // g_assert(thf == lttv_trace_hook_get_first((LttvTraceHook *)hook_data)); LttField *f = thf->f1; LttvExecutionSubmode submode; @@ -1204,6 +1209,8 @@ void lttv_state_add_event_hooks(LttvTracesetState *self) LttvAttributeValue val; + gint ret; + nb_trace = lttv_traceset_number(traceset); for(i = 0 ; i < nb_trace ; i++) { ts = (LttvTraceState *)self->parent.traces[i]; @@ -1214,55 +1221,65 @@ void lttv_state_add_event_hooks(LttvTracesetState *self) hooks = g_array_sized_new(FALSE, FALSE, sizeof(LttvTraceHook), 10); g_array_set_size(hooks, 10); - lttv_trace_find_hook(ts->parent.t, + ret = lttv_trace_find_hook(ts->parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_SYSCALL_ENTRY, LTT_FIELD_SYSCALL_ID, 0, 0, syscall_entry, &g_array_index(hooks, LttvTraceHook, 0)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.t, + ret = lttv_trace_find_hook(ts->parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_SYSCALL_EXIT, 0, 0, 0, syscall_exit, &g_array_index(hooks, LttvTraceHook, 1)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.t, + ret = lttv_trace_find_hook(ts->parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_TRAP_ENTRY, LTT_FIELD_TRAP_ID, 0, 0, trap_entry, &g_array_index(hooks, LttvTraceHook, 2)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.t, + ret = lttv_trace_find_hook(ts->parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_TRAP_EXIT, 0, 0, 0, trap_exit, &g_array_index(hooks, LttvTraceHook, 3)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.t, + ret = lttv_trace_find_hook(ts->parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_IRQ_ENTRY, LTT_FIELD_IRQ_ID, 0, 0, irq_entry, &g_array_index(hooks, LttvTraceHook, 4)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.t, + ret = lttv_trace_find_hook(ts->parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_IRQ_EXIT, 0, 0, 0, irq_exit, &g_array_index(hooks, LttvTraceHook, 5)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.t, + ret = lttv_trace_find_hook(ts->parent.t, LTT_FACILITY_PROCESS, LTT_EVENT_SCHEDCHANGE, LTT_FIELD_OUT, LTT_FIELD_IN, LTT_FIELD_OUT_STATE, schedchange, &g_array_index(hooks, LttvTraceHook, 6)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.t, + ret = lttv_trace_find_hook(ts->parent.t, LTT_FACILITY_PROCESS, LTT_EVENT_FORK, LTT_FIELD_PARENT_PID, LTT_FIELD_CHILD_PID, 0, process_fork, &g_array_index(hooks, LttvTraceHook, 7)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.t, + ret = lttv_trace_find_hook(ts->parent.t, LTT_FACILITY_PROCESS, LTT_EVENT_EXIT, LTT_FIELD_PID, 0, 0, process_exit, &g_array_index(hooks, LttvTraceHook, 8)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.t, + ret = lttv_trace_find_hook(ts->parent.t, LTT_FACILITY_PROCESS, LTT_EVENT_FREE, LTT_FIELD_PID, 0, 0, process_free, &g_array_index(hooks, LttvTraceHook, 9)); + g_assert(!ret); /* Add these hooks to each event_by_id hooks list */ @@ -1271,8 +1288,8 @@ void lttv_state_add_event_hooks(LttvTracesetState *self) for(j = 0 ; j < nb_tracefile ; j++) { tfs = - LTTV_TRACEFILE_STATE(&g_array_index(ts->parent.tracefiles, - LttvTracefileContext, j)); + LTTV_TRACEFILE_STATE(g_array_index(ts->parent.tracefiles, + LttvTracefileContext*, j)); for(k = 0 ; k < hooks->len ; k++) { hook = &g_array_index(hooks, LttvTraceHook, k); @@ -1281,7 +1298,7 @@ void lttv_state_add_event_hooks(LttvTracesetState *self) lttv_hooks_add( lttv_hooks_by_id_find(tfs->parent.event_by_id, thf->id), thf->h, - &g_array_index(hooks, LttvTraceHook, k), + hook, LTTV_PRIO_STATE); } } diff --git a/ltt/branches/poly/lttv/lttv/stats.c b/ltt/branches/poly/lttv/lttv/stats.c index bfd88d46..d5b4f5e6 100644 --- a/ltt/branches/poly/lttv/lttv/stats.c +++ b/ltt/branches/poly/lttv/lttv/stats.c @@ -761,6 +761,8 @@ void lttv_stats_add_event_hooks(LttvTracesetStats *self) LttvAttributeValue val; + gint ret; + nb_trace = lttv_traceset_number(traceset); for(i = 0 ; i < nb_trace ; i++) { ts = (LttvTraceStats *)self->parent.parent.traces[i]; @@ -771,98 +773,114 @@ void lttv_stats_add_event_hooks(LttvTracesetStats *self) hooks = g_array_sized_new(FALSE, FALSE, sizeof(LttvTraceHook), 7); g_array_set_size(hooks, 7); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_SYSCALL_ENTRY, LTT_FIELD_SYSCALL_ID, 0, 0, before_syscall_entry, &g_array_index(hooks, LttvTraceHook, 0)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_SYSCALL_EXIT, 0, 0, 0, before_syscall_exit, &g_array_index(hooks, LttvTraceHook, 1)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_TRAP_ENTRY, LTT_FIELD_TRAP_ID, 0, 0, before_trap_entry, &g_array_index(hooks, LttvTraceHook, 2)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_TRAP_EXIT, 0, 0, 0, before_trap_exit, &g_array_index(hooks, LttvTraceHook, 3)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_IRQ_ENTRY, LTT_FIELD_IRQ_ID, 0, 0, before_irq_entry, &g_array_index(hooks, LttvTraceHook, 4)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_IRQ_EXIT, 0, 0, 0, before_irq_exit, &g_array_index(hooks, LttvTraceHook, 5)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_PROCESS, LTT_EVENT_SCHEDCHANGE, LTT_FIELD_OUT, LTT_FIELD_IN, LTT_FIELD_OUT_STATE, before_schedchange, &g_array_index(hooks, LttvTraceHook, 6)); + g_assert(!ret); before_hooks = hooks; hooks = g_array_sized_new(FALSE, FALSE, sizeof(LttvTraceHook), 9); g_array_set_size(hooks, 9); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_SYSCALL_ENTRY, LTT_FIELD_SYSCALL_ID, 0, 0, after_syscall_entry, &g_array_index(hooks, LttvTraceHook, 0)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_SYSCALL_EXIT, 0, 0, 0, after_syscall_exit, &g_array_index(hooks, LttvTraceHook, 1)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_TRAP_ENTRY, LTT_FIELD_TRAP_ID, 0, 0, after_trap_entry, &g_array_index(hooks, LttvTraceHook, 2)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_TRAP_EXIT, 0, 0, 0, after_trap_exit, &g_array_index(hooks, LttvTraceHook, 3)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_IRQ_ENTRY, LTT_FIELD_IRQ_ID, 0, 0, after_irq_entry, &g_array_index(hooks, LttvTraceHook, 4)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_KERNEL, LTT_EVENT_IRQ_EXIT, 0, 0, 0, after_irq_exit, &g_array_index(hooks, LttvTraceHook, 5)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_PROCESS, LTT_EVENT_FORK, LTT_FIELD_PARENT_PID, LTT_FIELD_CHILD_PID, 0, process_fork, &g_array_index(hooks, LttvTraceHook, 6)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_PROCESS, LTT_EVENT_EXIT, LTT_FIELD_PID, 0, 0, process_exit, &g_array_index(hooks, LttvTraceHook, 7)); + g_assert(!ret); - lttv_trace_find_hook(ts->parent.parent.t, + ret = lttv_trace_find_hook(ts->parent.parent.t, LTT_FACILITY_PROCESS, LTT_EVENT_FREE, LTT_FIELD_PID, 0, 0, process_free, &g_array_index(hooks, LttvTraceHook, 7)); + g_assert(!ret); after_hooks = hooks; diff --git a/ltt/branches/poly/lttv/lttv/tracecontext.c b/ltt/branches/poly/lttv/lttv/tracecontext.c index 95462d96..28c27967 100644 --- a/ltt/branches/poly/lttv/lttv/tracecontext.c +++ b/ltt/branches/poly/lttv/lttv/tracecontext.c @@ -385,18 +385,19 @@ void lttv_tracefile_context_add_hooks(LttvTracefileContext *self, LttvHooks *event, LttvHooksById *event_by_id) { - guint i; + guint i, index; LttvHooks *hook; lttv_hooks_call(before_tracefile, self); lttv_hooks_add_list(self->event, event); - if(event_by_id != NULL) - for(i = 0; i < lttv_hooks_by_id_max_id(event_by_id); i++) { - hook = lttv_hooks_by_id_find(self->event_by_id, i); - lttv_hooks_add_list(hook, lttv_hooks_by_id_get(event_by_id, i)); + if(event_by_id != NULL) { + for(i = 0; i < event_by_id->array->len; i++) { + index = g_array_index(event_by_id->array, guint, i); + hook = lttv_hooks_by_id_find(self->event_by_id, index); + lttv_hooks_add_list(hook, lttv_hooks_by_id_get(event_by_id, index)); } - + } } void lttv_tracefile_context_remove_hooks(LttvTracefileContext *self, @@ -404,18 +405,19 @@ void lttv_tracefile_context_remove_hooks(LttvTracefileContext *self, LttvHooks *event, LttvHooksById *event_by_id) { - guint i; + guint i, index; LttvHooks *hook; - lttv_hooks_remove_list(self->event, event); - if(event_by_id != NULL) - for(i = 0; i < lttv_hooks_by_id_max_id(event_by_id); i++) { - hook = lttv_hooks_by_id_get(self->event_by_id, i); + if(event_by_id != NULL) { + for(i = 0; i < event_by_id->array->len; i++) { + index = g_array_index(event_by_id->array, guint, i); + hook = lttv_hooks_by_id_get(self->event_by_id, index); if(hook != NULL) - lttv_hooks_remove_list(hook, lttv_hooks_by_id_get(event_by_id, i)); + lttv_hooks_remove_list(hook, lttv_hooks_by_id_get(event_by_id, index)); } + } lttv_hooks_call(after_tracefile, self); } @@ -869,6 +871,7 @@ lttv_trace_find_hook(LttTrace *t, GQuark facility, GQuark event, thf = &g_array_index(th->fac_index, LttvTraceHookByFacility, fac_id); g_array_index(th->fac_list, LttvTraceHookByFacility*, 0) = thf; + thf->h = h; thf->id = ltt_eventtype_id(et); thf->f1 = find_field(et, field1); -- 2.34.1