* [PATCH 2/2] Rewrite jump_label.c to use binary search v2
2010-09-22 13:26 [PATCH 1/2] Add for_each_module iterator function v2 Andi Kleen
@ 2010-09-22 13:26 ` Andi Kleen
2010-09-22 14:14 ` [PATCH 1/2] Add for_each_module iterator function v2 Mathieu Desnoyers
1 sibling, 0 replies; 6+ messages in thread
From: Andi Kleen @ 2010-09-22 13:26 UTC (permalink / raw)
To: jbaron
Cc: rostedt, linux-kernel, mingo, mathieu.desnoyers, hpa, tglx,
roland, rth, mhiramat, fweisbec, avi, davem, vgoyal, sam, tony,
Andi Kleen
From: Andi Kleen <ak@linux.intel.com>
After the discussion on linux-kernel I decided to rewrite the
hash table based jump_label.c to use binary search as proposed.
This shrunk the code dramatically by >50%:
hash:
2763 80 544 3387 d3b kernel/jump_label.o
binsearch:
1072 40 0 1112 458 kernel/jump_label.o
This is only code size, at runtime there will be additional savings
because the new code does not allocate any additional memory.
Also the code is a lot simpler now:
jump_label.c | 391 +++++++++++------------------------------------------------
1 files changed, 74 insertions(+), 317 deletions(-)
(+ a few lines for a new generic utility function in module.c)
I believe it's also much cleaner than before.
I did some performance tests comparing the hash implementation
with the binary search. This was with a moderate config x86-64
kernel with 68 modules loaded and about 480 trace points active
in several modules and 1340 dynamic debug statements.
I measured arming all/unarming trace points and enabling all
dynamic debug points. The differences in cycles were always
within 30%, in fact in the dynamic debug case the binsearch
implementation was even faster.
In all cases the runtimes were less than a single ms, so
there was no user visible difference at all.
So this is a vastly simpler implementation with in practice
equivalent performance and less memory overhead (no data structures
outside the sections)
The patch is on top of Jason's patchkit.
v2: Fix off by on bug in binary search pointed out by Mathieu.
Fix another overlap bug inherited from the old code in checking for
conflicts.
Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
kernel/jump_label.c | 391 ++++++++++-----------------------------------------
1 files changed, 74 insertions(+), 317 deletions(-)
diff --git a/kernel/jump_label.c b/kernel/jump_label.c
index f82878b..3f5273f 100644
--- a/kernel/jump_label.c
+++ b/kernel/jump_label.c
@@ -2,133 +2,78 @@
* jump label support
*
* Copyright (C) 2009 Jason Baron <jbaron@redhat.com>
- *
+ * Rewritten in 2010 by Andi Kleen
*/
#include <linux/jump_label.h>
#include <linux/memory.h>
#include <linux/uaccess.h>
#include <linux/module.h>
-#include <linux/list.h>
-#include <linux/jhash.h>
-#include <linux/slab.h>
#include <linux/sort.h>
#include <linux/err.h>
#ifdef HAVE_JUMP_LABEL
-#define JUMP_LABEL_HASH_BITS 6
-#define JUMP_LABEL_TABLE_SIZE (1 << JUMP_LABEL_HASH_BITS)
-static struct hlist_head jump_label_table[JUMP_LABEL_TABLE_SIZE];
+#define ENTRIES(start, stop) (((stop) - (start)) / sizeof(*(start)))
/* mutex to protect coming/going of the the jump_label table */
static DEFINE_MUTEX(jump_label_mutex);
-struct jump_label_entry {
- struct hlist_node hlist;
- struct jump_entry *table;
- int nr_entries;
- /* hang modules off here */
- struct hlist_head modules;
- unsigned long key;
-};
-
-struct jump_label_module_entry {
- struct hlist_node hlist;
- struct jump_entry *table;
- int nr_entries;
- struct module *mod;
-};
-
static int jump_label_cmp(const void *a, const void *b)
{
const struct jump_entry *jea = a;
const struct jump_entry *jeb = b;
- if (jea->key < jeb->key)
- return -1;
-
- if (jea->key > jeb->key)
- return 1;
-
- return 0;
+ return jea->key - jeb->key;
}
static void sort_jump_label_entries(struct jump_entry *start, struct jump_entry *stop)
{
- unsigned long size;
-
- size = (((unsigned long)stop - (unsigned long)start)
- / sizeof(struct jump_entry));
- sort(start, size, sizeof(struct jump_entry), jump_label_cmp, NULL);
+ sort(start, ENTRIES(start, stop), sizeof(struct jump_entry), jump_label_cmp,
+ NULL);
}
-static struct jump_label_entry *get_jump_label_entry(jump_label_t key)
+static struct jump_entry *
+search_jump_table(struct jump_entry *first, struct jump_entry *last,
+ unsigned long key)
{
- struct hlist_head *head;
- struct hlist_node *node;
- struct jump_label_entry *e;
- u32 hash = jhash((void *)&key, sizeof(jump_label_t), 0);
-
- head = &jump_label_table[hash & (JUMP_LABEL_TABLE_SIZE - 1)];
- hlist_for_each_entry(e, node, head, hlist) {
- if (key == e->key)
- return e;
+ while (first <= last) {
+ struct jump_entry *mid = (last - first)/2 + first;
+
+ if (mid->key < key)
+ first = mid + 1;
+ else if (mid->key > key)
+ last = mid - 1;
+ else
+ return mid;
}
return NULL;
}
-static struct jump_label_entry *add_jump_label_entry(jump_label_t key, int nr_entries, struct jump_entry *table)
+void patch_jump_table(unsigned long key, enum jump_label_type type,
+ struct jump_entry *start, struct jump_entry *stop)
{
- struct hlist_head *head;
- struct jump_label_entry *e;
- u32 hash;
-
- e = get_jump_label_entry(key);
- if (e)
- return ERR_PTR(-EEXIST);
-
- e = kmalloc(sizeof(struct jump_label_entry), GFP_KERNEL);
- if (!e)
- return ERR_PTR(-ENOMEM);
-
- hash = jhash((void *)&key, sizeof(jump_label_t), 0);
- head = &jump_label_table[hash & (JUMP_LABEL_TABLE_SIZE - 1)];
- e->key = key;
- e->table = table;
- e->nr_entries = nr_entries;
- INIT_HLIST_HEAD(&(e->modules));
- hlist_add_head(&e->hlist, head);
- return e;
+ struct jump_entry *entry = search_jump_table(start, stop - 1, key);
+ if (!entry)
+ return;
+ while (entry > start && entry[-1].key == key)
+ entry--;
+ for (; entry < stop && entry->key == key; entry++)
+ if (kernel_text_address(entry->code))
+ arch_jump_label_transform(entry, type);
}
-static int build_jump_label_hashtable(struct jump_entry *start, struct jump_entry *stop)
+struct args {
+ unsigned long key;
+ enum jump_label_type type;
+};
+
+static void module_patch_jump_table(struct module *mod, void *args)
{
- struct jump_entry *iter, *iter_begin;
- struct jump_label_entry *entry;
- int count;
+ struct args *a = args;
- sort_jump_label_entries(start, stop);
- iter = start;
- while (iter < stop) {
- entry = get_jump_label_entry(iter->key);
- if (!entry) {
- iter_begin = iter;
- count = 0;
- while ((iter < stop) &&
- (iter->key == iter_begin->key)) {
- iter++;
- count++;
- }
- entry = add_jump_label_entry(iter_begin->key,
- count, iter_begin);
- if (IS_ERR(entry))
- return PTR_ERR(entry);
- } else {
- WARN_ONCE(1, KERN_ERR "build_jump_hashtable: unexpected entry!\n");
- return -1;
- }
- }
- return 0;
+ if (mod->num_jump_entries)
+ patch_jump_table(a->key, a->type, mod->jump_entries,
+ mod->jump_entries + mod->num_jump_entries);
}
/***
@@ -143,82 +88,42 @@ static int build_jump_label_hashtable(struct jump_entry *start, struct jump_entr
void jump_label_update(unsigned long key, enum jump_label_type type)
{
- struct jump_entry *iter;
- struct jump_label_entry *entry;
- struct hlist_node *module_node;
- struct jump_label_module_entry *e_module;
- int count;
+ struct args args = { .key = key, .type = type };
mutex_lock(&jump_label_mutex);
- entry = get_jump_label_entry((jump_label_t)key);
- if (entry) {
- count = entry->nr_entries;
- iter = entry->table;
- while (count--) {
- if (kernel_text_address(iter->code))
- arch_jump_label_transform(iter, type);
- iter++;
- }
- /* eanble/disable jump labels in modules */
- hlist_for_each_entry(e_module, module_node, &(entry->modules),
- hlist) {
- count = e_module->nr_entries;
- iter = e_module->table;
- while (count--) {
- if (kernel_text_address(iter->code))
- arch_jump_label_transform(iter, type);
- iter++;
- }
- }
- }
+ patch_jump_table(key, type, __start___jump_table, __stop___jump_table);
+ for_each_module(module_patch_jump_table, &args);
mutex_unlock(&jump_label_mutex);
}
-static int addr_conflict(struct jump_entry *entry, void *start, void *end)
+static int check_conflict(struct jump_entry *jstart, struct jump_entry *jstop,
+ void *start, void *stop)
{
- if (entry->code <= (unsigned long)end &&
- entry->code + JUMP_LABEL_NOP_SIZE > (unsigned long)start)
- return 1;
+ struct jump_entry *entry;
+ for (entry = jstart; entry < jstop; entry++)
+ if (entry->code <= (unsigned long)stop &&
+ entry->code + JUMP_LABEL_NOP_SIZE > (unsigned long)start)
+ return 1;
return 0;
}
-#ifdef CONFIG_MODULES
+struct conflict_args {
+ void *start, *end;
+ int conflict;
+};
-static int module_conflict(void *start, void *end)
+static void module_check_conflict(struct module *mod, void *args)
{
- 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;
- int conflict = 0;
+ struct conflict_args *a = args;
- 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) {
- hlist_for_each_entry_safe(e_module, module_node,
- module_node_next,
- &(e->modules), hlist) {
- count = e_module->nr_entries;
- iter = e_module->table;
- while (count--) {
- if (addr_conflict(iter, start, end)) {
- conflict = 1;
- goto out;
- }
- iter++;
- }
- }
- }
- }
-out:
- return conflict;
+ if (within_module_core((unsigned long)a->start, mod) ||
+ within_module_init((unsigned long)a->start, mod))
+ a->conflict = check_conflict(mod->jump_entries,
+ mod->jump_entries + mod->num_jump_entries,
+ a->start, a->end);
}
-#endif
-
/***
* jump_label_text_reserved - check if addr range is reserved
* @start: start text addr
@@ -233,189 +138,41 @@ out:
*/
int jump_label_text_reserved(void *start, void *end)
{
- struct jump_entry *iter;
- struct jump_entry *iter_start = __start___jump_table;
- struct jump_entry *iter_stop = __start___jump_table;
- int conflict = 0;
+ struct conflict_args args = { .start = start, .end = end };
mutex_lock(&jump_label_mutex);
- iter = iter_start;
- while (iter < iter_stop) {
- if (addr_conflict(iter, start, end)) {
- conflict = 1;
- goto out;
- }
- iter++;
- }
-
+ args.conflict = check_conflict(__start___jump_table,
+ __stop___jump_table, start, end);
/* now check modules */
#ifdef CONFIG_MODULES
- conflict = module_conflict(start, end);
+ if (!args.conflict)
+ for_each_module(module_check_conflict, &args);
#endif
-out:
mutex_unlock(&jump_label_mutex);
- return conflict;
+ return args.conflict;
}
-static __init int init_jump_label(void)
+static void setup_jump_label(struct jump_entry *start, struct jump_entry *stop)
{
- int ret;
- struct jump_entry *iter_start = __start___jump_table;
- struct jump_entry *iter_stop = __stop___jump_table;
- struct jump_entry *iter;
+ struct jump_entry *entry;
mutex_lock(&jump_label_mutex);
- ret = build_jump_label_hashtable(__start___jump_table,
- __stop___jump_table);
- iter = iter_start;
- while (iter < iter_stop) {
- arch_jump_label_text_poke_early(iter->code);
- iter++;
- }
+ sort_jump_label_entries(start, stop);
+ for (entry = start; entry < stop; entry++)
+ arch_jump_label_text_poke_early(entry->code);
mutex_unlock(&jump_label_mutex);
- return ret;
-}
-early_initcall(init_jump_label);
-
-#ifdef CONFIG_MODULES
-
-static struct jump_label_module_entry *add_jump_label_module_entry(struct jump_label_entry *entry, struct jump_entry *iter_begin, int count, struct module *mod)
-{
- struct jump_label_module_entry *e;
-
- e = kmalloc(sizeof(struct jump_label_module_entry), GFP_KERNEL);
- if (!e)
- return ERR_PTR(-ENOMEM);
- e->mod = mod;
- e->nr_entries = count;
- e->table = iter_begin;
- hlist_add_head(&e->hlist, &entry->modules);
- return e;
}
-static int add_jump_label_module(struct module *mod)
+static int init_jump_label(void)
{
- struct jump_entry *iter, *iter_begin;
- struct jump_label_entry *entry;
- struct jump_label_module_entry *module_entry;
- int count;
-
- /* if the module doesn't have jump label entries, just return */
- if (!mod->num_jump_entries)
- return 0;
-
- sort_jump_label_entries(mod->jump_entries,
- mod->jump_entries + mod->num_jump_entries);
- iter = mod->jump_entries;
- while (iter < mod->jump_entries + mod->num_jump_entries) {
- entry = get_jump_label_entry(iter->key);
- iter_begin = iter;
- count = 0;
- while ((iter < mod->jump_entries + mod->num_jump_entries) &&
- (iter->key == iter_begin->key)) {
- iter++;
- count++;
- }
- if (!entry) {
- entry = add_jump_label_entry(iter_begin->key, 0, NULL);
- if (IS_ERR(entry))
- return PTR_ERR(entry);
- }
- module_entry = add_jump_label_module_entry(entry, iter_begin,
- count, mod);
- if (IS_ERR(module_entry))
- return PTR_ERR(module_entry);
- }
+ setup_jump_label(__start___jump_table, __stop___jump_table);
return 0;
}
+early_initcall(init_jump_label);
-static void remove_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;
- int i;
-
- /* 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) {
- hlist_for_each_entry_safe(e_module, module_node,
- module_node_next,
- &(e->modules), hlist) {
- if (e_module->mod == mod) {
- hlist_del(&e_module->hlist);
- kfree(e_module);
- }
- }
- if (hlist_empty(&e->modules) && (e->nr_entries == 0)) {
- hlist_del(&e->hlist);
- kfree(e);
- }
- }
- }
-}
-
-static int jump_label_module_notify(struct notifier_block *self, unsigned long val, void *data)
-{
- struct module *mod = data;
- int ret = 0;
-
- switch (val) {
- case MODULE_STATE_COMING:
- mutex_lock(&jump_label_mutex);
- ret = add_jump_label_module(mod);
- if (ret)
- remove_jump_label_module(mod);
- mutex_unlock(&jump_label_mutex);
- break;
- case MODULE_STATE_GOING:
- mutex_lock(&jump_label_mutex);
- remove_jump_label_module(mod);
- mutex_unlock(&jump_label_mutex);
- break;
- }
- return ret;
-}
-
-/***
- * apply_jump_label_nops - patch module jump labels with arch_get_jump_label_nop()
- * @mod: module to patch
- *
- * Allow for run-time selection of the optimal nops. Before the module
- * loads patch these with arch_get_jump_label_nop(), which is specified by
- * the arch specific jump label code.
- */
void jump_label_apply_nops(struct module *mod)
{
- struct jump_entry *iter;
-
- /* if the module doesn't have jump label entries, just return */
- if (!mod->num_jump_entries)
- return;
-
- iter = mod->jump_entries;
- while (iter < mod->jump_entries + mod->num_jump_entries) {
- arch_jump_label_text_poke_early(iter->code);
- iter++;
- }
-}
-
-struct notifier_block jump_label_module_nb = {
- .notifier_call = jump_label_module_notify,
- .priority = 0,
-};
-
-static __init int init_jump_label_module(void)
-{
- return register_module_notifier(&jump_label_module_nb);
+ setup_jump_label(mod->jump_entries,
+ mod->jump_entries + mod->num_jump_entries);
}
-early_initcall(init_jump_label_module);
-
-#endif /* CONFIG_MODULES */
-
#endif
--
1.7.1
^ permalink raw reply related [flat|nested] 6+ messages in thread