Messages in this thread | | | Subject | Re: [PATCH 1/3] jump label: add enabled/disabled state to jump label key entries | From | Steven Rostedt <> | Date | Tue, 23 Nov 2010 19:00:30 -0500 |
| |
On Tue, 2010-11-23 at 18:43 -0500, Mathieu Desnoyers wrote: > * Jason Baron (jbaron@redhat.com) wrote: > [...] > > +static void update_jump_label_module(struct module *mod) > > +{ > > + struct hlist_head *head; > > + struct hlist_node *node, *node_next, *module_node, *module_node_next; > > + struct jump_label_entry *e; > > + struct jump_label_module_entry *e_module; > > + struct jump_entry *iter; > > + int i, count; > > + > > + /* if the module doesn't have jump label entries, just return */ > > + if (!mod->num_jump_entries) > > + return; > > + > > + for (i = 0; i < JUMP_LABEL_TABLE_SIZE; i++) { > > + head = &jump_label_table[i]; > > + hlist_for_each_entry_safe(e, node, node_next, head, hlist) { > > + if (!e->enabled) > > + continue; > > + hlist_for_each_entry_safe(e_module, module_node, > > + module_node_next, > > + &(e->modules), hlist) { > > + if (e_module->mod != mod) > > + continue; > > Ouch. > > Could you iterate on the loaded/unloaded module jump labels and do hash > table lookups rather than doing this O(n^3) iteration ?
This does not look O(n^3) to me.
It's a hash table, thus the first two loops is just iterating O(n) items in the hash.
And the third loop is all the modules that use a particular event.
So it is O(n*m) where n is the number of events, and m is the number of modules attached to the events. And that's only if all events are used by those modules. The actual case is much smaller.
-- Steve
| |