Skip to contentSkip to conversation

Add for_each_module iterator function

PATCH In review Andi Kleen 7 participants 21 messages Sep 22, 2010

Subsystems (2)
lore
Share & tools
lore

Andi Kleen

author
#0 lore raw

PATCH 1/2 Add for_each_module iterator function

From: Andi Kleen <[email protected]>

This is a generic function to iterate over all modules. To be used in the next patch.

---
 include/linux/module.h |    1 +
 kernel/module.c        |   10 ++++++++++
 2 files changed, 11 insertions(+), 0 deletions(-)
include/linux/module.h +1 -0
index 403ac26..809b6db 100644
@@ -410,6 +410,7 @@ struct module *__module_address(unsigned long addr);
 bool is_module_address(unsigned long addr);
 bool is_module_percpu_address(unsigned long addr);
 bool is_module_text_address(unsigned long addr);
+void for_each_module(void (*op)(struct module *, void *arg), void *arg);
 
 static inline int within_module_core(unsigned long addr, struct module *mod)
 {
kernel/module.c +10 -0
index eba1341..b8fb3e6 100644
@@ -384,6 +384,16 @@ struct module *find_module(const char *name)
 }
 EXPORT_SYMBOL_GPL(find_module);
 
+void for_each_module(void (*op)(struct module *, void *arg), void *arg)
+{
+	struct module *mod;
+
+	preempt_disable();
+	list_for_each_entry_rcu(mod, &modules, list)
+		op(mod, arg);
+	preempt_enable();
+}
+
 #ifdef CONFIG_SMP
 
 static inline void __percpu *mod_percpu(struct module *mod)
Signature · 1 line
1.7.1
author
#1 lore raw

PATCH 2/2 Rewrite jump_label.c to use binary search

From: Andi Kleen <[email protected]>

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.

---
 kernel/jump_label.c |  391 ++++++++++-----------------------------------------
 1 files changed, 74 insertions(+), 317 deletions(-)
kernel/jump_label.c +74 -317
index f82878b..478625e 100644
@@ -2,133 +2,78 @@
  * jump label support
  *
  * Copyright (C) 2009 Jason Baron <[email protected]>
- *
+ * 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, 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)start &&
+		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
Signature · 1 line
1.7.1
#2 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

Quoted 34 lines · * Andi Kleen ([email protected]) wrote:

From: Andi Kleen <[email protected]>

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.

Quoted 6 lines

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)

If both code size and performance show no significant degradation over Jason's hash table approach, then it's definitely worth looking into it. Thanks for proposing this patch, some comments follow. Due to the bugs I identified below, benchmarks should be re-run to fairly compare your approach to Jason's. Your current code does not seem to enable module static jumps at all.

Quoted 69 lines

The patch is on top of Jason's patchkit.

---
 kernel/jump_label.c |  391 ++++++++++-----------------------------------------
 1 files changed, 74 insertions(+), 317 deletions(-)
kernel/jump_label.c +3 -30
index f82878b..478625e 100644
@@ -2,133 +2,78 @@
  * jump label support
  *
  * Copyright (C) 2009 Jason Baron <[email protected]>
- *
+ * 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;
 }

kernel/jump_label.c line 32

Quoted 10 lines
kernel/jump_label.c +2 -5
 
 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);

If you really want to sort this table, then you should move it from RODATA to DATA. I just looked at the bug table: it does not seem to be sorted, so for that one it looks fine to leave it into RODATA.

Ideally we'd like to do this sorting at a post-compilation stage, so we can leave the section RODATA.

Quoted 7 lines
kernel/jump_label.c +3 -1
 }
 
-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)
 {

kernel/jump_label.c line 39

Quoted 10 lines
kernel/jump_label.c +1 -9
-	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) { 

There seems to be a mismatch between the caller and this function. The module patch_jump_table() caller passes first and first + len, while this expects first and last. This looks a little off by one to me.

Quoted 31 lines
kernel/jump_label.c +10 -16
+		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;

kernel/jump_label.c line 59

Quoted 10 lines
kernel/jump_label.c +5 -5
-	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, key);
+	if (!entry)
+		return;
+	while (entry > start && entry[-1].key == key)
+		entry--;

OK, I like the way it handles patching of multiple entries with the same key at once. Sorting really makes sense here.

kernel/jump_label.c line 61

Quoted 2 lines
kernel/jump_label.c +2 -0
+	for (; entry < stop && entry->key == key; entry++)
+		if (kernel_text_address(entry->code))

This does not work for modules I'm afraid, only for the core kernel. You should test for __module_text_address() somewhere.

Dumb question: why do you need this test at all ?

Quoted 69 lines
kernel/jump_label.c +12 -44
+			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;

kernel/jump_label.c static int build_jump_label_hashtable(struct jump_entry *start, struct jump_entr · line 95

Quoted 10 lines
kernel/jump_label.c +2 -8
-			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);

Can we have a for_each_module that keeps preemption on ? Calling arch_jump_label_transform() with preemption off is wrong, as it locks the text_mutex and get/put online cpus, not to mention that text_poke_smp() is probably still based on stop_machine().

Maybe we could stick a synchronize_rcu() in module delete and use a proper RCU read-side C.S. in for_each_module ?

Quoted 4 lines
kernel/jump_label.c +0 -1
 	mutex_unlock(&jump_label_mutex);
 }
 
-static int addr_conflict(struct jump_entry *entry, void *start, void *end)

kernel/jump_label.c static int build_jump_label_hashtable(struct jump_entry *start, struct jump_entr · line 105

Quoted 10 lines
kernel/jump_label.c +5 -3
+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)start &&

start -> end ?

kernel/jump_label.c static int build_jump_label_hashtable(struct jump_entry *start, struct jump_entr · line 106

Quoted 1 line
kernel/jump_label.c +1 -0
+		entry->code + JUMP_LABEL_NOP_SIZE > (unsigned long)start)

Maybe it's my mail client, but indentation looks wrong here.

kernel/jump_label.c static int build_jump_label_hashtable(struct jump_entry *start, struct jump_entr · line 186

Quoted 5 lines
kernel/jump_label.c +1 -1
+			return 1;
 	return 0;
 }
 
-#ifdef CONFIG_MODULES

Why make it build when modules are configured out ?

Quoted 63 lines
kernel/jump_label.c +12 -37
+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)) {

kernel/jump_label.c out: · line 147

Quoted 10 lines
kernel/jump_label.c +2 -6
-			conflict = 1;
-			goto out;
-		}
-		iter++;
-	}
-
+	args.conflict = check_conflict(__start___jump_table, 
+				       __stop___jump_table, start, end);
 	/* now check modules */
 #ifdef CONFIG_MODULES

ifdef could be removed from within this function body by replacing it with a #ifdef CONFIG_MODULES #else #endif that defines an empty static inline when disabled. Also for_each_module for be defined as an empty static inline when modules are disabled.

Thanks!

Mathieu

Quoted 185 lines
kernel/jump_label.c +13 -151
-	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
Signature · 1 line
1.7.1
Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
author
#3 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

Thanks for the review.

Quoted 3 lines

If you really want to sort this table, then you should move it from RODATA to DATA. I just looked at the bug table: it does not seem to be sorted, so for that one it looks fine to leave it into RODATA.

FWIW the table was already sorted before, i didn't actually change that code except for writing it a bit more cleanly.

But you're right. If it's rodata it could fault. Normally it shouldn't be though because the loader has to relocate it for modules. I didn't test with rodata enabled, but will see what happens. Maybe this happens at the right place that it doesn't matter.

I suspect the original version had the same problem if this one has.

Quoted 2 lines

Ideally we'd like to do this sorting at a post-compilation stage, so we can leave the section RODATA.

That's complicated because you would need to fix relocations too. I guess doing that would need to put significant parts of a linker into modpost. Since the goal of this was to reduce complexity ...

This is patterned after the exception tables which always were sorted at runtime, which is much easier.

Besides I don't see a lot of value of having this rodata

Quoted 14 lines
Quoted 14 lines

}

kernel/jump_label.c +3 -7
-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)];
Quoted 8 lines

kernel/jump_label.c line 39

Quoted 4 lines
kernel/jump_label.c +1 -3
-	hlist_for_each_entry(e, node, head, hlist) {
-		if (key == e->key)
-			return e;
+	while (first <= last) {

There seems to be a mismatch between the caller and this function. The module patch_jump_table() caller passes first and first + len, while this expects first and last. This looks a little off by one to me.

True. Will fix that.

Quoted 5 lines

kernel/jump_label.c line 61

Quoted 2 lines
kernel/jump_label.c +2 -0
+	for (; entry < stop && entry->key == key; entry++)
+		if (kernel_text_address(entry->code))

This does not work for modules I'm afraid, only for the core kernel. You should test for __module_text_address() somewhere.

I thought it was shared now, but ok.

Quoted 1 line

Dumb question: why do you need this test at all ?

I just copied that from the original code. In fact I was wondering too why it's needed. Jason?

Quoted 10 lines

kernel/jump_label.c static int build_jump_label_hashtable(struct jump_entry *start, struct jump_entr · line 95

Quoted 4 lines
(quoted diff) +1 -1
-	}
+	patch_jump_table(key, type, __start___jump_table,

__stop___jump_table);

kernel/jump_label.c +1 -0
+	for_each_module(module_patch_jump_table, &args);

Can we have a for_each_module that keeps preemption on ? Calling arch_jump_label_transform() with preemption off is wrong, as it locks the text_mutex and get/put online cpus, not to mention that text_poke_smp() is probably still based on stop_machine().

Quoted 2 lines

Maybe we could stick a synchronize_rcu() in module delete and use a proper RCU read-side C.S. in for_each_module ?

Hmpf. Ok I didn't read that code.

I guess could just take the module mutex or whatever it's called during the walk.

Copying Rusty, maybe he has ideas how to handle this.

Quoted 7 lines

kernel/jump_label.c static int build_jump_label_hashtable(struct jump_entry *start, struct jump_entr · line 105

Quoted 5 lines
kernel/jump_label.c +3 -1
-		return 1;
+	struct jump_entry *entry;
 
+	for (entry = jstart; entry < jstop; entry++)
+		if (entry->code <= (unsigned long)start &&

start -> end ?

I copied this from the original code too. I remember stumbling over it too. Yes it was probably wrong in the original too.

Quoted 4 lines

kernel/jump_label.c static int build_jump_label_hashtable(struct jump_entry *start, struct jump_entr · line 106

Quoted 2 lines
kernel/jump_label.c +1 -0
+		entry->code + JUMP_LABEL_NOP_SIZE > (unsigned long)start)

Maybe it's my mail client, but indentation looks wrong here.

All the horrors you do for the holy 80 columns.

Quoted 4 lines
Quoted 2 lines

-#ifdef CONFIG_MODULES

Why make it build when modules are configured out ?

Because it's shared code for the module and non module case.

Quoted 9 lines

kernel/jump_label.c out: · line 147

Quoted 4 lines
kernel/jump_label.c +2 -0
+	args.conflict = check_conflict(__start___jump_table,
+				       __stop___jump_table, start, end);
 	/* now check modules */
 #ifdef CONFIG_MODULES

ifdef could be removed from within this function body by replacing it with a #ifdef CONFIG_MODULES #else #endif that defines an empty static inline when disabled. Also for_each_module for be defined as an empty static inline when modules are disabled.

It could yes, but really a single clean #ifdef is imho fine and much simpler.

-Andi

author
#4 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

Quoted 9 lines
Quoted 7 lines

kernel/jump_label.c line 61

Quoted 4 lines
kernel/jump_label.c +2 -0
+	for (; entry < stop && entry->key == key; entry++)
+		if (kernel_text_address(entry->code))

This does not work for modules I'm afraid, only for the core kernel. You should test for __module_text_address() somewhere.

I thought it was shared now, but ok.

Double checked. This is ok because kernel_text_address() already checks for modules. You were probably thinking of __kernel_text_address()

-Andi

#5 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

Quoted 8 lines · * Andi Kleen ([email protected]) wrote:
Quoted 8 lines
Quoted 7 lines

kernel/jump_label.c line 61

Quoted 4 lines
kernel/jump_label.c +2 -0
+	for (; entry < stop && entry->key == key; entry++)
+		if (kernel_text_address(entry->code))

This does not work for modules I'm afraid, only for the core kernel. You should test for __module_text_address() somewhere.

Quoted 5 lines
Quoted 1 line

I thought it was shared now, but ok.

Double checked. This is ok because kernel_text_address() already checks for modules. You were probably thinking of __kernel_text_address()

Ah right,

Although we have another problem:

__module_text_address() includes module init text, which defeats the purpose of the check put in there by Jason.

So the check works for the core kernel, but not for modules.

Mathieu

Quoted 3 lines

-Andi

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#6 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

Quoted 15 lines · * Mathieu Desnoyers ([email protected]) wrote:
Quoted 8 lines · * Andi Kleen ([email protected]) wrote:
Quoted 8 lines
Quoted 7 lines

kernel/jump_label.c line 61

Quoted 4 lines
kernel/jump_label.c +2 -0
+	for (; entry < stop && entry->key == key; entry++)
+		if (kernel_text_address(entry->code))

This does not work for modules I'm afraid, only for the core kernel. You should test for __module_text_address() somewhere.

Quoted 5 lines
Quoted 1 line

I thought it was shared now, but ok.

Double checked. This is ok because kernel_text_address() already checks for modules. You were probably thinking of __kernel_text_address()

Quoted 8 lines

Ah right,

Although we have another problem:

__module_text_address() includes module init text, which defeats the purpose of the check put in there by Jason.

So the check works for the core kernel, but not for modules.

So, we have this issue, but I also have a question for Jason: what happens if someone puts static jump in a function declared in the __init section of the core kernel/module ? Can we enable them at early boot ?

Thanks,

Mathieu

Quoted 12 lines

Mathieu

Quoted 3 lines

-Andi

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#7 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

Quoted 25 lines · Mathieu Desnoyers
Quoted 15 lines · * Mathieu Desnoyers ([email protected]) wrote:
Quoted 8 lines · * Andi Kleen ([email protected]) wrote:
Quoted 8 lines
Quoted 7 lines

kernel/jump_label.c line 61

Quoted 4 lines
kernel/jump_label.c +2 -0
+	for (; entry < stop && entry->key == key; entry++)
+		if (kernel_text_address(entry->code))

This does not work for modules I'm afraid, only for the core kernel. You should test for __module_text_address() somewhere.

Quoted 5 lines
Quoted 1 line

I thought it was shared now, but ok.

Double checked. This is ok because kernel_text_address() already checks for modules. You were probably thinking of __kernel_text_address()

Quoted 8 lines

Ah right,

Although we have another problem:

__module_text_address() includes module init text, which defeats the purpose of the check put in there by Jason.

So the check works for the core kernel, but not for modules.

Quoted 8 lines

So, we have this issue, but I also have a question for Jason: what happens if someone puts static jump in a function declared in the __init section of the core kernel/module ? Can we enable them at early boot ?

Thanks,

Mathieu

Hi Mathieu,

Yes, we should be able to enable these. Look at the definition for core_kernel_text():

int core_kernel_text(unsigned long addr)

{
        if (addr >= (unsigned long)_stext &&
            addr <= (unsigned long)_etext)
                return 1;

        if (system_state == SYSTEM_BOOTING &&
            init_kernel_text(addr))
                return 1;
        return 0;
}

If the system is in the SYSTEM_BOOTING state we allow the text to be updated. same for modules, the check will allow module __init text modifications. At very early init there could be some issue text_poke_smp() working on x86, I'm not sure. In any case, we could always fall back to text_poke_early(), if needed. So I don't see any fundamental issues with this case.

thanks,

-Jason

#8 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

In reply to Mathieu Desnoyers
Quoted 17 lines · Mathieu Desnoyers
Quoted 8 lines · * Andi Kleen ([email protected]) wrote:
Quoted 8 lines
Quoted 7 lines

kernel/jump_label.c line 61

Quoted 4 lines
kernel/jump_label.c +2 -0
+	for (; entry < stop && entry->key == key; entry++)
+		if (kernel_text_address(entry->code))

This does not work for modules I'm afraid, only for the core kernel. You should test for __module_text_address() somewhere.

Quoted 5 lines
Quoted 1 line

I thought it was shared now, but ok.

Double checked. This is ok because kernel_text_address() already checks for modules. You were probably thinking of __kernel_text_address()

Ah right,

Quoted 9 lines

Although we have another problem:

__module_text_address() includes module init text, which defeats the purpose of the check put in there by Jason.

So the check works for the core kernel, but not for modules.

Mathieu

it works for modules too...it does:

struct module *__module_text_address(unsigned long addr)

{
        struct module *mod = __module_address(addr);
        if (mod) {
                /* Make sure it's within the text section. */
                if (!within(addr, mod->module_init, mod->init_text_size)
                    && !within(addr, mod->module_core,
mod->core_text_size))
                        mod = NULL;
        }
        return mod;
}

and then in kernel/module.c we have :

        module_free(mod, mod->module_init);
        mod->module_init = NULL;

So, I was relying on the fact module_init gets set to NULL after the free happens. However, there a small race there in that the vfree() happens before module_init() is set to NULL. So that is probably most easily fixed be wrapping those two lines with the jump_label_mutex.

thanks,

-Jason

#9 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

Quoted 46 lines · * Jason Baron ([email protected]) wrote:
Quoted 17 lines · Mathieu Desnoyers
Quoted 8 lines · * Andi Kleen ([email protected]) wrote:
Quoted 8 lines
Quoted 7 lines

kernel/jump_label.c line 61

Quoted 4 lines
kernel/jump_label.c +2 -0
+	for (; entry < stop && entry->key == key; entry++)
+		if (kernel_text_address(entry->code))

This does not work for modules I'm afraid, only for the core kernel. You should test for __module_text_address() somewhere.

Quoted 5 lines
Quoted 1 line

I thought it was shared now, but ok.

Double checked. This is ok because kernel_text_address() already checks for modules. You were probably thinking of __kernel_text_address()

Ah right,

Quoted 9 lines

Although we have another problem:

__module_text_address() includes module init text, which defeats the purpose of the check put in there by Jason.

So the check works for the core kernel, but not for modules.

Mathieu

it works for modules too...it does:

struct module *__module_text_address(unsigned long addr)

{
        struct module *mod = __module_address(addr);
        if (mod) {
                /* Make sure it's within the text section. */
                if (!within(addr, mod->module_init, mod->init_text_size)
                    && !within(addr, mod->module_core,
mod->core_text_size))
                        mod = NULL;
        }
        return mod;
}

and then in kernel/module.c we have :

Quoted 8 lines
        module_free(mod, mod->module_init);
        mod->module_init = NULL;

So, I was relying on the fact module_init gets set to NULL after the free happens. However, there a small race there in that the vfree() happens before module_init() is set to NULL. So that is probably most easily fixed be wrapping those two lines with the jump_label_mutex.

It's both module_init = NULL _and_ init_text_size = 0 that make sure the test "within(addr, mod->module_init, mod->init_text_size)" is valid. Just the "module_init = NULL" can cause problems with addresses in the low range of kernel addresses. With a long enough module init section, the offset from NULL can end up (temporarily) in the kernel address range.

But this is all wrong: __module_text_address is relying on preempt_disable() to ensure coherency of this test is just racy, as you point out above. So we either do the RCU synchronization properly, or hold the module_mutex around the module text address test _and_ actual access to the module init section.

Thanks,

Mathieu

Quoted 6 lines

thanks,

-Jason

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#10 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

In reply to Andi Kleen
Quoted 7 lines · Andi Kleen
Quoted 6 lines

kernel/jump_label.c line 61

Quoted 3 lines
kernel/jump_label.c +2 -0
+	for (; entry < stop && entry->key == key; entry++)
+		if (kernel_text_address(entry->code))

This does not work for modules I'm afraid, only for the core kernel. You should test for __module_text_address() somewhere.

Quoted 8 lines

I thought it was shared now, but ok.

Quoted 1 line

Dumb question: why do you need this test at all ?

I just copied that from the original code. In fact I was wondering too why it's needed. Jason?

It was put there for jump labels that are in __init sections. Without this check the code will corrupt itself when we toggle a jump label after the __init sections have been freed.

thanks,

-Jason

#11 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

In reply to Andi Kleen
Quoted 10 lines · Andi Kleen
Quoted 6 lines

kernel/jump_label.c static int build_jump_label_hashtable(struct jump_entry *start, struct jump_entr · line 105

Quoted 4 lines
kernel/jump_label.c +3 -0
+	struct jump_entry *entry;
 
+	for (entry = jstart; entry < jstop; entry++)
+		if (entry->code <= (unsigned long)start &&

start -> end ?

I copied this from the original code too. I remember stumbling over it too. Yes it was probably wrong in the original too.

No...the original version had it correct, check the archive.

This bug was introduced in your version.

thanks,

-Jason

#12 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

In reply to Mathieu Desnoyers
Quoted 33 lines · Mathieu Desnoyers
Quoted 19 lines
kernel/jump_label.c +2 -16
-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;

kernel/jump_label.c line 59

Quoted 10 lines
kernel/jump_label.c +5 -5
-	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, key);
+	if (!entry)
+		return;
+	while (entry > start && entry[-1].key == key)
+		entry--;

OK, I like the way it handles patching of multiple entries with the same key at once. Sorting really makes sense here.

Quoted 5 lines

kernel/jump_label.c line 61

Quoted 2 lines
kernel/jump_label.c +2 -0
+	for (; entry < stop && entry->key == key; entry++)
+		if (kernel_text_address(entry->code))

This does not work for modules I'm afraid, only for the core kernel. You should test for __module_text_address() somewhere.

No, look:

int kernel_text_address(unsigned long addr)

{
	if (core_kernel_text(addr))
		return 1;
	return is_module_text_address(addr);
}
Quoted 1 line

Dumb question: why do you need this test at all ?

I wonder about that too.

#13 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

In reply to Andi Kleen
Quoted 8 lines · Andi Kleen

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.

Now, the ideal data structure for this stuff is something called a minimal perfect hash. This is something that would have to be generated (for each module and for the monolithic kernel) at compile time -- presumably in modpost -- because the static generation of them is fairly complex.

That would provide extremely simple handling in the kernel (just do some shifts and a table lookup and you have your answer) and if combined with an AVL or red-black tree holding the module addresses it would give extremely fast address-to-metadata lookup, not just for this but also for things like exception handling.

I have used MPH's in other projects and pitched them to Linus at one point for exception handling. What is clear, though, is that we should do the same thing for exceptions, trace points, and any other similar things that depend on exact PC.

-hpa

#14 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

Quoted 22 lines · * H. Peter Anvin ([email protected]) wrote:
Quoted 8 lines · Andi Kleen

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.

Now, the ideal data structure for this stuff is something called a minimal perfect hash. This is something that would have to be generated (for each module and for the monolithic kernel) at compile time -- presumably in modpost -- because the static generation of them is fairly complex.

That would provide extremely simple handling in the kernel (just do some shifts and a table lookup and you have your answer) and if combined with an AVL or red-black tree holding the module addresses it would give extremely fast address-to-metadata lookup, not just for this but also for things like exception handling.

Quoted 4 lines

I have used MPH's in other projects and pitched them to Linus at one point for exception handling. What is clear, though, is that we should do the same thing for exceptions, trace points, and any other similar things that depend on exact PC.

That's a very interesting idea, which applies very well to exception handlers, but tracepoints and static jumps suffer from the problem that there are many possible instances of the same key.

Tracepoints use a lookup by tracepoint name. Static jumps use a lookup by associated variable address (but this variable can be associated with many instances, e.g. in the case of static inline functions, or just when the same variable is used to control many instances of static jumps).

But maybe we could find a way to do an initial sort phase, so the perfect hash could point to the first entry corresponding to the looked up key ?

Thanks,

Mathieu

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#15 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

Quoted 13 lines · Mathieu Desnoyers
Quoted 1 line · * H. Peter Anvin ([email protected]) wrote:

On 09/22/2010 03:08 AM, Andi Kleen wrote:

That's a very interesting idea, which applies very well to exception handlers, but tracepoints and static jumps suffer from the problem that there are many possible instances of the same key.

Tracepoints use a lookup by tracepoint name. Static jumps use a lookup by associated variable address (but this variable can be associated with many instances, e.g. in the case of static inline functions, or just when the same variable is used to control many instances of static jumps).

Quoted 4 lines

But maybe we could find a way to do an initial sort phase, so the perfect hash could point to the first entry corresponding to the looked up key ?

In the case of multiple instances of the same key you want the perfect hash to point to the cluster of solutions -- a list. Since this is by necessity something that needs to be done at compile time that list can simply be an array.

-hpa

#16 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

Quoted 14 lines · * H. Peter Anvin ([email protected]) wrote:
Quoted 13 lines · Mathieu Desnoyers
Quoted 1 line · * H. Peter Anvin ([email protected]) wrote:

On 09/22/2010 03:08 AM, Andi Kleen wrote:

That's a very interesting idea, which applies very well to exception handlers, but tracepoints and static jumps suffer from the problem that there are many possible instances of the same key.

Tracepoints use a lookup by tracepoint name. Static jumps use a lookup by associated variable address (but this variable can be associated with many instances, e.g. in the case of static inline functions, or just when the same variable is used to control many instances of static jumps).

Quoted 8 lines
Quoted 4 lines

But maybe we could find a way to do an initial sort phase, so the perfect hash could point to the first entry corresponding to the looked up key ?

In the case of multiple instances of the same key you want the perfect hash to point to the cluster of solutions -- a list. Since this is by simply be an array.

Yep, and sorting the section seems like a very natural way to create these arrays. So to summarize:

- We add a post-linking step to core image and module build in modpost.c.
- This step accesses exception tables, tracepoint and static jump sections.
- Both tracepoint and static jump need to be sorted.
- For each of the 3 sections, a perfect hash is computed (creation must have the property to always succeed). The perfect hash creation should only take into account the first entry of duplicate keys.
- Each of these perfect hash would translate into C code that would need to be compiled in a post-link phase.
- Then we can link the perfect hash objects with the rest of the code, filling in one symbol per considered section (function pointer to the perfect hash function) and setting function pointers in struct module for modules.

I'm mostly writing this down as food for thoughts, since my own implementation time is currently focused on other things.

Thanks,

Mathieu

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#17 lore raw

Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

Quoted 23 lines · Mathieu Desnoyers
Quoted 4 lines

In the case of multiple instances of the same key you want the perfect hash to point to the cluster of solutions -- a list. Since this is by simply be an array.

Yep, and sorting the section seems like a very natural way to create these arrays. So to summarize:

- We add a post-linking step to core image and module build in modpost.c.
- This step accesses exception tables, tracepoint and static jump sections.
- Both tracepoint and static jump need to be sorted.
- For each of the 3 sections, a perfect hash is computed (creation must have the property to always succeed). The perfect hash creation should only take into account the first entry of duplicate keys.
- Each of these perfect hash would translate into C code that would need to be compiled in a post-link phase.
- Then we can link the perfect hash objects with the rest of the code, filling in one symbol per considered section (function pointer to the perfect hash function) and setting function pointers in struct module for modules.

Quoted 3 lines

I'm mostly writing this down as food for thoughts, since my own implementation time is currently focused on other things.

For what it's worth, here is a working (verified and in use) perfect hash generator written in Perl:

http://repo.or.cz/w/nasm.git/tree/HEAD:/perllib

Like most other perfect hash generators it needs a prehash: the prehash should be parameterizable (seedable) and produce 2 ceil(log n) bits of hash material and cannot have collisions. The actual phash algorithm compresses it down to a perfect hash. The prehash is typically generated via a pseudorandom algorithm: the particular implementation pointed to uses one based on CRC64 because it's fast to compute but has a finite probability of not existing; a universal prehash is guaranteed to exist but is much more expensive. In practice a very simple prehash is usually sufficient, and one goes for speed.

For binary numbers being input, an even simpler prehash based on multiplies or rotates is generally more than sufficient.

-hpa

#18 lore raw
In reply to Andi Kleen
Quoted 28 lines · Andi Kleen

From: Andi Kleen <[email protected]>

This is a generic function to iterate over all modules. To be used in the next patch.

---
 include/linux/module.h |    1 +
 kernel/module.c        |   10 ++++++++++
 2 files changed, 11 insertions(+), 0 deletions(-)
include/linux/module.h +1 -0
index 403ac26..809b6db 100644
@@ -410,6 +410,7 @@ struct module *__module_address(unsigned long addr);
 bool is_module_address(unsigned long addr);
 bool is_module_percpu_address(unsigned long addr);
 bool is_module_text_address(unsigned long addr);
+void for_each_module(void (*op)(struct module *, void *arg), void *arg);
 
 static inline int within_module_core(unsigned long addr, struct module *mod)
 {
kernel/module.c +0 -0
index eba1341..b8fb3e6 100644

kernel/module.c struct module *find_module(const char *name) · line 391

Quoted 8 lines
kernel/module.c +5 -0
@@ -384,6 +384,16 @@ struct module *find_module(const char *name)
 }
 EXPORT_SYMBOL_GPL(find_module);
 
+void for_each_module(void (*op)(struct module *, void *arg), void *arg)
+{
+	struct module *mod;
+
+	preempt_disable();

That wants rcu_read_lock()

kernel/module.c struct module *find_module(const char *name) · line 394

Quoted 3 lines
kernel/module.c +3 -0
+	list_for_each_entry_rcu(mod, &modules, list)
+		op(mod, arg);
+	preempt_enable();

Thanks,

tglx

author
#19 lore raw
Quoted 7 lines

kernel/module.c struct module *find_module(const char *name) · line 391

Quoted 5 lines
kernel/module.c +5 -0
+void for_each_module(void (*op)(struct module *, void *arg), void *arg)
+{
+	struct module *mod;
+
+	preempt_disable();

That wants rcu_read_lock()

Thanks. It was wrong anyways for the intended use case, switched to module_mutex now.

BTW I think i copied this from somewhere else in module.c Probably should be fixed there too.

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only.
#20 lore raw
In reply to Thomas Gleixner
Quoted 35 lines · * Thomas Gleixner ([email protected]) wrote:
Quoted 31 lines · Andi Kleen

From: Andi Kleen <[email protected]>

This is a generic function to iterate over all modules. To be used in the next patch.

---
 include/linux/module.h |    1 +
 kernel/module.c        |   10 ++++++++++
 2 files changed, 11 insertions(+), 0 deletions(-)
include/linux/module.h +1 -0
index 403ac26..809b6db 100644
@@ -410,6 +410,7 @@ struct module *__module_address(unsigned long addr);
 bool is_module_address(unsigned long addr);
 bool is_module_percpu_address(unsigned long addr);
 bool is_module_text_address(unsigned long addr);
+void for_each_module(void (*op)(struct module *, void *arg), void *arg);
 
 static inline int within_module_core(unsigned long addr, struct module *mod)
 {
kernel/module.c +0 -0
index eba1341..b8fb3e6 100644
@@ -384,6 +384,16 @@ struct module *find_module(const char *name)
 }
 EXPORT_SYMBOL_GPL(find_module);
 
Quoted 7 lines

kernel/module.c struct module *find_module(const char *name) · line 391

Quoted 5 lines
kernel/module.c +5 -0
+void for_each_module(void (*op)(struct module *, void *arg), void *arg)
+{
+	struct module *mod;
+
+	preempt_disable();

That wants rcu_read_lock()

Then we might need to add synchronize_rcu() call when modules are unloaded. For now, there is only synchronize_sched().

Mathieu

Quoted 8 lines

kernel/module.c struct module *find_module(const char *name) · line 394

Quoted 4 lines
kernel/module.c +3 -0
+	list_for_each_entry_rcu(mod, &modules, list)
+		op(mod, arg);
+	preempt_enable();

Thanks,

tglx

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com