Date:   Tue, 31 Jan 2017 19:32:42 -0500
From:   Steven Rostedt <rostedt@...dmis.org>
To:     Jason Baron <jbaron@...mai.com>
Cc:     mingo@...nel.org, linux-kernel@...r.kernel.org,
        Peter Zijlstra <peterz@...radead.org>,
        Joe Perches <joe@...ches.com>
Subject: Re: [PATCH v3] jump_label: reduce the size of struct static_key

On Tue, 31 Jan 2017 17:00:43 -0500
Jason Baron <jbaron@...mai.com> wrote:

> ---
>  Documentation/static-keys.txt |   4 +-
>  include/linux/jump_label.h    |  23 +++++---
>  kernel/jump_label.c           | 126 ++++++++++++++++++++++++++++++++++--------
>  3 files changed, 120 insertions(+), 33 deletions(-)
> 
> diff --git a/Documentation/static-keys.txt b/Documentation/static-keys.txt
> index ea8d7b4e53f0..32a25fad0c1b 100644
> --- a/Documentation/static-keys.txt
> +++ b/Documentation/static-keys.txt
> @@ -155,7 +155,9 @@ or:
>  
>  There are a few functions and macros that architectures must implement in order
>  to take advantage of this optimization. If there is no architecture support, we
> -simply fall back to a traditional, load, test, and jump sequence.
> +simply fall back to a traditional, load, test, and jump sequence. Also, the
> +struct jump_entry table must be at least 4-byte aligned because the
> +static_key->entry field makes use of the two least significant bits.
>  
>  * select HAVE_ARCH_JUMP_LABEL, see: arch/x86/Kconfig
>  
> diff --git a/include/linux/jump_label.h b/include/linux/jump_label.h
> index a0547c571800..680c98b2f41c 100644
> --- a/include/linux/jump_label.h
> +++ b/include/linux/jump_label.h
> @@ -89,11 +89,17 @@ extern bool static_key_initialized;
>  
>  struct static_key {
>  	atomic_t enabled;
> -/* Set lsb bit to 1 if branch is default true, 0 ot */
> -	struct jump_entry *entries;
> -#ifdef CONFIG_MODULES
> -	struct static_key_mod *next;
> -#endif
> +/*
> + * bit 0 => 1 if key is initially true
> + *	    0 if initially false
> + * bit 1 => 1 if points to struct static_key_mod
> + *	    0 if points to struct jump_entry
> + */
> +	union {
> +		unsigned long type;
> +		struct jump_entry *entries;
> +		struct static_key_mod *next;
> +	};
>  };
>  
>  #else
> @@ -118,9 +124,10 @@ struct module;
>  
>  #ifdef HAVE_JUMP_LABEL
>  
> -#define JUMP_TYPE_FALSE	0UL
> -#define JUMP_TYPE_TRUE	1UL
> -#define JUMP_TYPE_MASK	1UL
> +#define JUMP_TYPE_FALSE		0UL
> +#define JUMP_TYPE_TRUE		1UL
> +#define JUMP_TYPE_LINKED	2UL
> +#define JUMP_TYPE_MASK		3UL
>  
>  static __always_inline bool static_key_false(struct static_key *key)
>  {
> diff --git a/kernel/jump_label.c b/kernel/jump_label.c
> index a9b8cf500591..2eb9e80dc691 100644
> --- a/kernel/jump_label.c
> +++ b/kernel/jump_label.c
> @@ -236,12 +236,27 @@ void __weak __init_or_module arch_jump_label_transform_static(struct jump_entry
>  
>  static inline struct jump_entry *static_key_entries(struct static_key *key)
>  {
> -	return (struct jump_entry *)((unsigned long)key->entries & ~JUMP_TYPE_MASK);
> +	return (struct jump_entry *)(key->type & ~JUMP_TYPE_MASK);
>  }
>  
>  static inline bool static_key_type(struct static_key *key)
>  {
> -	return (unsigned long)key->entries & JUMP_TYPE_MASK;
> +	return key->type & JUMP_TYPE_TRUE;
> +}
> +
> +static inline bool static_key_linked(struct static_key *key)
> +{
> +	return key->type & JUMP_TYPE_LINKED;
> +}
> +
> +static inline void static_key_clear_linked(struct static_key *key)
> +{
> +	key->type &= ~JUMP_TYPE_LINKED;
> +}
> +
> +static inline void static_key_set_linked(struct static_key *key)
> +{
> +	key->type |= JUMP_TYPE_LINKED;
>  }
>  
>  static inline struct static_key *jump_entry_key(struct jump_entry *entry)
> @@ -254,6 +269,25 @@ static bool jump_entry_branch(struct jump_entry *entry)
>  	return (unsigned long)entry->key & 1UL;
>  }
>  
> +/***
> + * A 'struct static_key' uses a union such that it either points directly
> + * to a table of 'struct jump_entry' or to a linked list of modules, which in
> + * turn point to 'struct jump_entry' tables. Since most static_key uses occur

I read that three times thinking that the grammar was incorrect, but I
finally figured out that it's not. But the issue is that darn comma
between "modules" and "which". With the comma, it causes one to think
the subject of the sentence is "a linked list of modules" (singular)
where we would use "in turn points to". But if you take out that comma,
it becomes obvious that the "point" is for the "modules" (plural), and
then it makes sense again.

"or a linked list of modules which in turn point to"

See, it reads better that way. Please nuke that comma.

> + * within the module in which they are defined, this saves space. Since the

Also, please nuke the "Since most static_key uses occur..." sentence.
It just reads funny, and I don't think it adds much new info. It's
pretty obvious that we do things like this to save space.

> + * two lower bits of the pointer are used to keep track of which pointer type
> + * is in use and to store the initial branch direction, we need a special
> + * access function which preserves these bits.
> + */

Also, make the "Since the two lower" a new paragraph. It's a separate
topic. And also nuke the "Since", it's bad form ;-)

"The two lower bits of the pointer are used to keep track of which
pointer type is in use and to store the initial branch direction, we
use a special access function which preserves these bits."


> +static void static_key_set_entries(struct static_key *key,
> +				   struct jump_entry *entries)
> +{
> +	unsigned long type;
> +
> +	type = key->type & JUMP_TYPE_MASK;
> +	key->entries = entries;
> +	key->type |= type;
> +}
> +
>  static enum jump_label_type jump_label_type(struct jump_entry *entry)
>  {
>  	struct static_key *key = jump_entry_key(entry);
> @@ -313,13 +347,7 @@ void __init jump_label_init(void)
>  			continue;
>  
>  		key = iterk;
> -		/*
> -		 * Set key->entries to iter, but preserve JUMP_LABEL_TRUE_BRANCH.
> -		 */
> -		*((unsigned long *)&key->entries) += (unsigned long)iter;
> -#ifdef CONFIG_MODULES
> -		key->next = NULL;
> -#endif
> +		static_key_set_entries(key, iter);

The new code does make sense, but I'm trying to see how the old code
works. How was the "+=" an assignment? I'm assuming that as this is
init code, that the key->entries was only assigned as 0 or 1 (depending
on if it was true or false). Looking around, this does seem to be the
case. But as a reviewer, I still like to have that warm cozy feeling of
confirmation ;-)


>  	}
>  	static_key_initialized = true;
>  	jump_label_unlock();
> @@ -343,6 +371,22 @@ struct static_key_mod {
>  	struct module *mod;
>  };
>  
> +static inline struct static_key_mod *static_key_mod(struct static_key *key)
> +{
> +	return (struct static_key_mod *)(key->type & ~JUMP_TYPE_MASK);
> +}
> +
> +/* See comments above static_key_set_entries() */
> +static void static_key_set_mod(struct static_key *key,
> +			       struct static_key_mod *mod)
> +{
> +	unsigned long type;

Even though you have the "see comments", it may still be helpful to
have something simple here. Like:

	/*
	 * key->type and key->next are the same via union.
	 * This sets key->next and preserves the type bits.
	 */

> +
> +	type = static_key_type(key);
> +	key->next = mod;
> +	key->type |= type;
> +}
> +
>  static int __jump_label_mod_text_reserved(void *start, void *end)
>  {
>  	struct module *mod;
> @@ -363,13 +407,19 @@ static int __jump_label_mod_text_reserved(void *start, void *end)
>  
>  static void __jump_label_mod_update(struct static_key *key)
>  {
> -	struct static_key_mod *mod;
> +	struct static_key_mod *mod = static_key_mod(key);
>  
> -	for (mod = key->next; mod; mod = mod->next) {
> +	while (mod) {

Maybe keep the for loop?

	for (mod = static_key_mod(key); mod; mod->next) {


It's still nicely compact.

Also, with a for loop, this can be changed to:

	if (!mod->entries)
		continue;

	if (!m)
		....

Speaking of which ...

> +		struct jump_entry *stop;
>  		struct module *m = mod->mod;
>  
> -		__jump_label_update(key, mod->entries,
> -				    m->jump_entries + m->num_jump_entries);
> +		if (!m)
> +			stop = __stop___jump_table;
> +		else
> +			stop = m->jump_entries + m->num_jump_entries;

How did this work before, if mod->entries was NULL? Or does this have
to do with this being now called by the module itself if linked. But
I'm not sure how that works either.

> +		if (mod->entries)
> +			__jump_label_update(key, mod->entries, stop);
> +		mod = mod->next;
>  	}
>  }
>  
> @@ -404,7 +454,7 @@ static int jump_label_add_module(struct module *mod)
>  	struct jump_entry *iter_stop = iter_start + mod->num_jump_entries;
>  	struct jump_entry *iter;
>  	struct static_key *key = NULL;
> -	struct static_key_mod *jlm;
> +	struct static_key_mod *jlm, *jlm2;
>  
>  	/* if the module doesn't have jump label entries, just return */
>  	if (iter_start == iter_stop)
> @@ -421,20 +471,32 @@ static int jump_label_add_module(struct module *mod)
>  
>  		key = iterk;
>  		if (within_module(iter->key, mod)) {
> -			/*
> -			 * Set key->entries to iter, but preserve JUMP_LABEL_TRUE_BRANCH.
> -			 */
> -			*((unsigned long *)&key->entries) += (unsigned long)iter;
> -			key->next = NULL;
> +			static_key_set_entries(key, iter);
>  			continue;
>  		}
>  		jlm = kzalloc(sizeof(struct static_key_mod), GFP_KERNEL);
>  		if (!jlm)
>  			return -ENOMEM;
> +		if (!static_key_linked(key)) {
> +			jlm2 = kzalloc(sizeof(struct static_key_mod),
> +				       GFP_KERNEL);
> +			if (!jlm2) {
> +				kfree(jlm);
> +				return -ENOMEM;
> +			}
> +			preempt_disable();
> +			jlm2->mod = __module_address((unsigned long)key);
> +			preempt_enable();
> +			jlm2->entries = static_key_entries(key);
> +			jlm2->next = NULL;
> +			static_key_set_mod(key, jlm2);
> +			static_key_set_linked(key);
> +		}
>  		jlm->mod = mod;
>  		jlm->entries = iter;
> -		jlm->next = key->next;
> -		key->next = jlm;

I wonder if a comment would be useful here:

		/*
		 * jlm->next = key->next;
		 * key->next = jlm;
		 */

Just because the encapsulated functions don't show this basic exchange
well. It tripped me up for a moment.

> +		jlm->next = static_key_mod(key);
> +		static_key_set_mod(key, jlm);
> +		static_key_set_linked(key);
>  
>  		/* Only update if we've changed from our initial state */
>  		if (jump_label_type(iter) != jump_label_init_type(iter))
> @@ -462,15 +524,28 @@ static void jump_label_del_module(struct module *mod)
>  			continue;
>  
>  		prev = &key->next;
> -		jlm = key->next;
> +		jlm = static_key_mod(key);
>  
>  		while (jlm && jlm->mod != mod) {
>  			prev = &jlm->next;
>  			jlm = jlm->next;
>  		}
>  

BTW, can !jlm ever happen? I guess it can if it failed to allocate :-/
Maybe a comment about that? And maybe even a WARN()?

-- Steve

> -		if (jlm) {
> +		if (!jlm)
> +			continue;
> +
> +		if (prev == &key->next)
> +			static_key_set_mod(key, jlm->next);
> +		else
>  			*prev = jlm->next;
> +
> +		kfree(jlm);
> +
> +		jlm = static_key_mod(key);
> +		/* if only one etry is left, fold it back into the static_key */
> +		if (jlm->next == NULL) {
> +			static_key_set_entries(key, jlm->entries);
> +			static_key_clear_linked(key);
>  			kfree(jlm);
>  		}
>  	}
> @@ -565,7 +640,10 @@ static void jump_label_update(struct static_key *key)
>  #ifdef CONFIG_MODULES
>  	struct module *mod;
>  
> -	__jump_label_mod_update(key);
> +	if (static_key_linked(key)) {
> +		__jump_label_mod_update(key);
> +		return;
> +	}
>  
>  	preempt_disable();
>  	mod = __module_address((unsigned long)key);

Powered by blists - more mailing lists