Re: [RFC][PATCH] module: Optimize __module_address() using a latched RB-tree

[Peter Zijlstra <peterz@infradead.org>]

On Thu, Feb 26, 2015 at 12:43:09PM +0100, Peter Zijlstra wrote:

> +static struct module *__tree_find(struct rb_root *r, unsigned long addr)
> +{
> +	struct rb_node *n = r->rb_node;
> +
> +	while (n) {
> +		struct module *m = mod_entry(n);
> +		int idx = mod_node_idx(m, n);
> +
> +		if (idx & 2) {				/* core */
> +			if (addr < (unsigned long)m->module_core)
> +				n = n->rb_left;
> +			else if (addr >= (unsigned long)m->module_core + m->core_size)
> +				n = n->rb_right;
> +			else
> +				return m;
> +		} else {				/* init */
> +			if (addr < (unsigned long)m->module_init)
> +				n = n->rb_left;
> +			else if (addr >= (unsigned long)m->module_init + m->init_size)
> +				n = n->rb_right;
> +			else
> +				return m;
> +		}
> +	}
> +
> +	return NULL;
> +}

Assuming struct module is cacheline aligned, Rusty? from what I can find
its squirreled away in some data structure:

  mod = (void *)info->sechdrs[info->index.mod].sh_addr

And I can't seem to quickly find its alignment. If its not cacheline
aligned, can we make it so?

The below patch shuffles things around a bit and relies on the above
assumption.

#pahole -EC module ivb-ep-build/kernel/module.o

struct module {
	...

        /* --- cacheline 6 boundary (384 bytes) --- */
        void *                     module_init;                                          /*   384     8 */
        void *                     module_core;                                          /*   392     8 */
        unsigned int               init_size;                                            /*   400     4 */
        unsigned int               core_size;                                            /*   404     4 */
        unsigned int               init_text_size;                                       /*   408     4 */
        unsigned int               core_text_size;                                       /*   412     4 */
        struct module_node {
                struct module *    mod;                                                  /*   416     8 */
                struct rb_node {
                        long unsigned int __rb_parent_color;                             /*   424     8 */
                        struct rb_node * rb_right;                                       /*   432     8 */
                        struct rb_node * rb_left;                                        /*   440     8 */
                } node; /*   424    24 */
        } tree_node[4]; /*   416   128 */

	...
};

Which gets module_{init,core} and {init,core}_size on the same cacheline
as tree_node[0].

And given that module loading/unloading is rare, tree modifications will
be rare, and we'll normally always iterate tree latch0. Furthermore,
execution of init code is brief and by switching core to elements 0,2
we've insured to typically only hit tree_node[0].

Therefore the loads in __tree_find() will (typically) hit the same
cacheline and life is good.

---

Index: linux-2.6/include/linux/module.h
===================================================================
--- linux-2.6.orig/include/linux/module.h	2015-02-26 14:59:06.549177534 +0100
+++ linux-2.6/include/linux/module.h	2015-02-26 14:53:27.708162155 +0100
@@ -222,8 +222,6 @@
 	/* Member of list of modules */
 	struct list_head list;
 
-	struct module_node tree_node[4];
-
 	/* Unique handle for this module */
 	char name[MODULE_NAME_LEN];
 
@@ -278,7 +276,7 @@
 	int (*init)(void);
 
 	/* If this is non-NULL, vfree after init() returns */
-	void *module_init;
+	void *module_init	____cacheline_aligned;
 
 	/* Here is the actual code + data, vfree'd on unload. */
 	void *module_core;
@@ -289,6 +287,8 @@
 	/* The size of the executable code in each section.  */
 	unsigned int init_text_size, core_text_size;
 
+	struct module_node tree_node[4];
+
 	/* Size of RO sections of the module (text+rodata) */
 	unsigned int init_ro_size, core_ro_size;
 
Index: linux-2.6/kernel/module.c
===================================================================
--- linux-2.6.orig/kernel/module.c	2015-02-26 14:59:06.551177534 +0100
+++ linux-2.6/kernel/module.c	2015-02-26 14:52:04.094158360 +0100
@@ -125,10 +125,10 @@
  * module, but other than that its pretty straight forward.
  *
  * idx
- *  0	- latch 0, init
- *  1	- latch 1, init
- *  2	- latch 0, core
- *  3	- latch 1, core
+ *  0	- latch 0, core
+ *  1	- latch 1, core
+ *  2	- latch 0, init
+ *  3	- latch 1, init
  */
 
 struct latch_tree_root {
@@ -138,10 +138,10 @@
 
 static unsigned long mod_value(struct module *mod, int idx)
 {
-	if (idx & 2) {		/* core */
-		return (unsigned long)mod->module_core;
-	} else {		/* init */
+	if (idx & 2) {		/* init */
 		return (unsigned long)mod->module_init;
+	} else {		/* core */
+		return (unsigned long)mod->module_core;
 	}
 }
 
@@ -207,17 +207,17 @@
 		struct module *m = mod_entry(n);
 		int idx = mod_node_idx(m, n);
 
-		if (idx & 2) {				/* core */
-			if (addr < (unsigned long)m->module_core)
+		if (idx & 2) {				/* init */
+			if (addr < (unsigned long)m->module_init)
 				n = n->rb_left;
-			else if (addr >= (unsigned long)m->module_core + m->core_size)
+			else if (addr >= (unsigned long)m->module_init + m->init_size)
 				n = n->rb_right;
 			else
 				return m;
-		} else {				/* init */
-			if (addr < (unsigned long)m->module_init)
+		} else {				/* core */
+			if (addr < (unsigned long)m->module_core)
 				n = n->rb_left;
-			else if (addr >= (unsigned long)m->module_init + m->init_size)
+			else if (addr >= (unsigned long)m->module_core + m->core_size)
 				n = n->rb_right;
 			else
 				return m;
@@ -232,35 +232,35 @@
 static void mod_tree_insert(struct module *mod)
 {
 	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_insert(&mod_tree, mod, 0);		/* core */
 	if (mod->init_size)
-		__tree_insert(&mod_tree, mod, 0);	/* init */
-	__tree_insert(&mod_tree, mod, 2);		/* core */
+		__tree_insert(&mod_tree, mod, 2);	/* init */
 	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_insert(&mod_tree, mod, 1);		/* core */
 	if (mod->init_size)
-		__tree_insert(&mod_tree, mod, 1);	/* init */
-	__tree_insert(&mod_tree, mod, 3);		/* core */
+		__tree_insert(&mod_tree, mod, 3);	/* init */
 }
 
 static void mod_tree_remove_init(struct module *mod)
 {
 	raw_write_seqcount_latch(&mod_tree.seq);
 	if (mod->init_size)
-		__tree_remove(&mod_tree, mod, 0);	/* init */
+		__tree_remove(&mod_tree, mod, 2);	/* init */
 	raw_write_seqcount_latch(&mod_tree.seq);
 	if (mod->init_size)
-		__tree_remove(&mod_tree, mod, 1);	/* init */
+		__tree_remove(&mod_tree, mod, 3);	/* init */
 }
 
 static void mod_tree_remove(struct module *mod)
 {
 	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_remove(&mod_tree, mod, 0);		/* core */
 	if (mod->init_size)
-		__tree_remove(&mod_tree, mod, 0);	/* init */
-	__tree_remove(&mod_tree, mod, 2);		/* core */
+		__tree_remove(&mod_tree, mod, 2);	/* init */
 	raw_write_seqcount_latch(&mod_tree.seq);
+	__tree_remove(&mod_tree, mod, 1);		/* core */
 	if (mod->init_size)
-		__tree_remove(&mod_tree, mod, 1);	/* init */
-	__tree_remove(&mod_tree, mod, 3);		/* core */
+		__tree_remove(&mod_tree, mod, 3);	/* init */
 }
 
 static struct module *mod_tree_find(unsigned long addr)