[PATCH 0/7] static_key: fix timer bugs & change api (a bit)

[PATCH 0/7] static_key: fix timer bugs & change api (a bit)

[Radim Krčmář]

While fixing a simple crash on kvm module unload

1: rate_limit timer can fire after we free its key's module memory.

I noticed other deficiencies in jump_label/static_key code
(The most important is 4.)

2: jump_label_rate_limit() uses an initializator and thus cannot be used
   more than once, leaving no good way to change the timeout.

I have made the API easier on programmers: [1/7]
 * timer is automatically flushed on rmmod
 * jump_label_rate_limit() initializes only once
    - pretty hacky, but we cannot automatically initialize on
      kernel_init/insmod due to insufficient information and while I
      would love getting it through another section, it is probably
      better to do a useless check with this low-rate operation
    * we could flush the timer on change
    * 'init()' + 'set()' (+ 'exit()' ?) would be an alternative ...

3: schedule_delayed_work() does not queue the work if one is already
   pending, but atomic_inc(&key->enabled) is called anyway in
   static_key_slow_dec_deferred(), with the false belief it will be
   decreased when the timer fires.

Fixed in [2,3,4/7], by addition of static_key_slow_inc_deferred().

I'm still not happy with the final design: we don't want delayed
decrease, we just don't want change more that once a interval.
A good solution should immediately enable/disable if interval since last
change has already passed.
I'll generalize ratelimit (probably) to suit our needs, but it won't be
quick, so we could use this in the meantime.

4: static_key_{true,false}() is a horrible name for a representation of
   a boolean and its use is unnecessarily restricted

In patch [5/7], static keys are transformed so one key can be hinted
both ways. This is done by bloating the jump_entry.

Patch [6/7] changes the name to static_key_{likely,unlikely}() because
we no longer have incompatible behaviour.

5: jump_label_init() is called too late

I've seen some patches that debugged the case where we use static_keys
before patching.
Moving jump_label_init() near the top of start_kernel() should help us
avoid it. [7/7]

n: jump_label and static_key api should be split;
   static_key_deferred isn't complete api, or subclass of static_key;
   some functions should be renamed, some removed;
   ...

There are already some patches prepared, but the diffstat isn't pretty,
so I'm keeping them to ripen.

Applied on top of torvalds-3.12-rc5.

Radim Krčmář (7):
  static_key: flush rate limit timer on rmmod
  static_key: add static_key_slow_inc_deferred()
  static_key: keep deferred enabled counter debt
  static_key: use static_key_slow_inc_deferred()
  jump_label: relax branch hinting restrictions
  static_key: use {,un}likely instead of {tru,fals}e
  init: execute jump_label_init() earlier

 Documentation/static-keys.txt         | 39 ++++++++------------
 arch/arm/include/asm/jump_label.h     | 19 +++++++---
 arch/arm/kernel/jump_label.c          |  2 +-
 arch/mips/include/asm/jump_label.h    | 19 +++++++---
 arch/mips/kernel/jump_label.c         |  2 +-
 arch/powerpc/include/asm/jump_label.h | 19 +++++++---
 arch/powerpc/kernel/jump_label.c      |  2 +-
 arch/s390/include/asm/jump_label.h    | 19 +++++++---
 arch/s390/kernel/jump_label.c         |  2 +-
 arch/sparc/include/asm/jump_label.h   | 19 +++++++---
 arch/sparc/kernel/jump_label.c        |  2 +-
 arch/x86/include/asm/jump_label.h     | 19 +++++++---
 arch/x86/include/asm/spinlock.h       |  4 +--
 arch/x86/kernel/jump_label.c          | 32 +++--------------
 arch/x86/kvm/lapic.c                  |  7 ++--
 arch/x86/kvm/lapic.h                  |  6 ++--
 arch/x86/kvm/mmu_audit.c              |  2 +-
 include/linux/context_tracking.h      | 10 +++---
 include/linux/jump_label.h            | 66 +++++++++++++---------------------
 include/linux/jump_label_ratelimit.h  |  6 ++++
 include/linux/memcontrol.h            |  2 +-
 include/linux/netfilter.h             |  2 +-
 include/linux/perf_event.h            |  6 ++--
 include/linux/tick.h                  |  2 +-
 include/linux/tracepoint.h            |  4 +--
 include/linux/vtime.h                 |  2 +-
 include/net/sock.h                    |  4 +--
 init/main.c                           |  6 +++-
 kernel/context_tracking.c             |  4 +--
 kernel/events/core.c                  |  6 ++--
 kernel/jump_label.c                   | 68 ++++++++++++++++++++---------------
 kernel/sched/core.c                   |  4 ++-
 kernel/sched/cputime.c                |  2 +-
 kernel/sched/fair.c                   |  2 +-
 kernel/sched/sched.h                  |  4 +--
 lib/crc-t10dif.c                      |  2 +-
 net/core/dev.c                        |  8 ++---
 net/ipv4/udp.c                        |  4 +--
 net/ipv6/udp.c                        |  4 +--
 39 files changed, 231 insertions(+), 201 deletions(-)

-- 
1.8.3.1

[PATCH 1/7] static_key: flush rate limit timer on rmmod

[Radim Krčmář]

Fix a bug when we free module memory while timer is pending by marking
deferred static keys and flushing the timer on module unload.

Also make static_key_rate_limit() useable more than once.

Reproducer: (host crasher)
  modprobe kvm_intel
  (sleep 1; echo quit) \
    | qemu-kvm -kernel /dev/null -monitor stdio &
  sleep 0.5
  until modprobe -rv kvm_intel 2>/dev/null; do true; done
  modprobe -v kvm_intel

Signed-off-by: Radim Krčmář <rkrcmar@redhat.com>
---
Very hacky; I've already queued generalizing ratelimit and applying it
here, but there is still a lot to do on static keys ...

 include/linux/jump_label.h |  1 +
 kernel/jump_label.c        | 17 ++++++++++++++++-
 2 files changed, 17 insertions(+), 1 deletion(-)

diff --git a/include/linux/jump_label.h b/include/linux/jump_label.h
index a507907..848bd15 100644
--- a/include/linux/jump_label.h
+++ b/include/linux/jump_label.h
@@ -58,6 +58,7 @@ struct static_key {
 #ifdef CONFIG_MODULES
 	struct static_key_mod *next;
 #endif
+	atomic_t deferred;
 };
 
 # include <asm/jump_label.h>
diff --git a/kernel/jump_label.c b/kernel/jump_label.c
index 297a924..7018042 100644
--- a/kernel/jump_label.c
+++ b/kernel/jump_label.c
@@ -116,8 +116,9 @@ EXPORT_SYMBOL_GPL(static_key_slow_dec_deferred);
 void jump_label_rate_limit(struct static_key_deferred *key,
 		unsigned long rl)
 {
+	if (!atomic_xchg(&key->key.deferred, 1))
+		INIT_DELAYED_WORK(&key->work, jump_label_update_timeout);
 	key->timeout = rl;
-	INIT_DELAYED_WORK(&key->work, jump_label_update_timeout);
 }
 EXPORT_SYMBOL_GPL(jump_label_rate_limit);
 
@@ -185,6 +186,14 @@ static enum jump_label_type jump_label_type(struct static_key *key)
 	return JUMP_LABEL_DISABLE;
 }
 
+static void static_key_rate_limit_flush(struct static_key *key)
+{
+	struct static_key_deferred *dkey =
+		container_of(key, struct static_key_deferred, key);
+	if (atomic_read(&key->deferred))
+		flush_delayed_work(&dkey->work);
+}
+
 void __init jump_label_init(void)
 {
 	struct jump_entry *iter_start = __start___jump_table;
@@ -334,6 +343,12 @@ static void jump_label_del_module(struct module *mod)
 
 		key = (struct static_key *)(unsigned long)iter->key;
 
+		/* We could also check if the static_key is used in its
+		 * defining module and skip this flush then.
+		 * (Rewrite of ratelimit in planned, so we don't care much)
+		 */
+		static_key_rate_limit_flush(key);
+
 		if (__module_address(iter->key) == mod)
 			continue;
 
-- 
1.8.3.1

[PATCH 2/7] static_key: add static_key_slow_inc_deferred()

[Radim Krčmář]

We can cancel deferred static_key_slow_dec() instead of increasing
.enabled.counter.

Timer now won't fire before 'timeout' since last increase, so this patch
further stabilizes the case of frequent switching.

Signed-off-by: Radim Krčmář <rkrcmar@redhat.com>
---
 include/linux/jump_label_ratelimit.h | 5 +++++
 kernel/jump_label.c                  | 7 +++++++
 2 files changed, 12 insertions(+)

diff --git a/include/linux/jump_label_ratelimit.h b/include/linux/jump_label_ratelimit.h
index 1137883..e2fa2e7 100644
--- a/include/linux/jump_label_ratelimit.h
+++ b/include/linux/jump_label_ratelimit.h
@@ -13,6 +13,7 @@ struct static_key_deferred {
 #endif
 
 #ifdef HAVE_JUMP_LABEL
+extern void static_key_slow_inc_deferred(struct static_key_deferred *key);
 extern void static_key_slow_dec_deferred(struct static_key_deferred *key);
 extern void
 jump_label_rate_limit(struct static_key_deferred *key, unsigned long rl);
@@ -21,6 +22,10 @@ jump_label_rate_limit(struct static_key_deferred *key, unsigned long rl);
 struct static_key_deferred {
 	struct static_key  key;
 };
+static inline void static_key_slow_inc_deferred(struct static_key_deferred *key)
+{
+	static_key_slow_inc(&key->key);
+}
 static inline void static_key_slow_dec_deferred(struct static_key_deferred *key)
 {
 	static_key_slow_dec(&key->key);
diff --git a/kernel/jump_label.c b/kernel/jump_label.c
index 7018042..ff67257 100644
--- a/kernel/jump_label.c
+++ b/kernel/jump_label.c
@@ -73,6 +73,13 @@ void static_key_slow_inc(struct static_key *key)
 }
 EXPORT_SYMBOL_GPL(static_key_slow_inc);
 
+void static_key_slow_inc_deferred(struct static_key_deferred *key)
+{
+	if (!cancel_delayed_work(&key->work))
+		static_key_slow_inc(&key->key);
+}
+EXPORT_SYMBOL_GPL(static_key_slow_inc_deferred);
+
 static void __static_key_slow_dec(struct static_key *key,
 		unsigned long rate_limit, struct delayed_work *work)
 {
-- 
1.8.3.1

[PATCH 3/7] static_key: keep deferred enabled counter debt

[Radim Krčmář]

When '.enabled.counter == 1', static_key_slow_dec_deferred() gets
silently dropped if the decrease is already pending.

We print a warning if this happens and because .enabled.counter cannot
go below 1 before the decrease has finished, the number of ignored
static_key_slow_dec_deferred() is kept and we skip an equal amount of
static_key_slow_inc_deferred().

Signed-off-by: Radim Krčmář <rkrcmar@redhat.com>
---
atomic_dec_if_positive() is weird ...

 include/linux/jump_label_ratelimit.h |  1 +
 kernel/jump_label.c                  | 17 +++++++++++------
 2 files changed, 12 insertions(+), 6 deletions(-)

diff --git a/include/linux/jump_label_ratelimit.h b/include/linux/jump_label_ratelimit.h
index e2fa2e7..e3a7a83 100644
--- a/include/linux/jump_label_ratelimit.h
+++ b/include/linux/jump_label_ratelimit.h
@@ -9,6 +9,7 @@ struct static_key_deferred {
 	struct static_key key;
 	unsigned long timeout;
 	struct delayed_work work;
+	atomic_t enabled_debt;
 };
 #endif
 
diff --git a/kernel/jump_label.c b/kernel/jump_label.c
index ff67257..30aa3b0 100644
--- a/kernel/jump_label.c
+++ b/kernel/jump_label.c
@@ -75,13 +75,15 @@ EXPORT_SYMBOL_GPL(static_key_slow_inc);
 
 void static_key_slow_inc_deferred(struct static_key_deferred *key)
 {
+	if (atomic_dec_if_positive(&key->enabled_debt) >= 0)
+		return;
 	if (!cancel_delayed_work(&key->work))
 		static_key_slow_inc(&key->key);
 }
 EXPORT_SYMBOL_GPL(static_key_slow_inc_deferred);
 
 static void __static_key_slow_dec(struct static_key *key,
-		unsigned long rate_limit, struct delayed_work *work)
+		struct static_key_deferred *dkey)
 {
 	if (!atomic_dec_and_mutex_lock(&key->enabled, &jump_label_mutex)) {
 		WARN(atomic_read(&key->enabled) < 0,
@@ -89,9 +91,12 @@ static void __static_key_slow_dec(struct static_key *key,
 		return;
 	}
 
-	if (rate_limit) {
+	if (dkey && dkey->timeout) {
 		atomic_inc(&key->enabled);
-		schedule_delayed_work(work, rate_limit);
+		if (!schedule_delayed_work(&dkey->work, dkey->timeout)) {
+			atomic_inc(&dkey->enabled_debt);
+			WARN(1, "jump label: negative deferred count!\n");
+		}
 	} else {
 		if (!jump_label_get_branch_default(key))
 			jump_label_update(key, JUMP_LABEL_DISABLE);
@@ -105,18 +110,18 @@ static void jump_label_update_timeout(struct work_struct *work)
 {
 	struct static_key_deferred *key =
 		container_of(work, struct static_key_deferred, work.work);
-	__static_key_slow_dec(&key->key, 0, NULL);
+	__static_key_slow_dec(&key->key, NULL);
 }
 
 void static_key_slow_dec(struct static_key *key)
 {
-	__static_key_slow_dec(key, 0, NULL);
+	__static_key_slow_dec(key, NULL);
 }
 EXPORT_SYMBOL_GPL(static_key_slow_dec);
 
 void static_key_slow_dec_deferred(struct static_key_deferred *key)
 {
-	__static_key_slow_dec(&key->key, key->timeout, &key->work);
+	__static_key_slow_dec(&key->key, key);
 }
 EXPORT_SYMBOL_GPL(static_key_slow_dec_deferred);
 
-- 
1.8.3.1

[PATCH 4/7] static_key: use static_key_slow_inc_deferred()

[Radim Krčmář]

Simple replacement where possible.
Saves us problematic access to the structure and allows optimalizations
and bug fixes to take place.

Signed-off-by: Radim Krčmář <rkrcmar@redhat.com>
---
 arch/x86/kvm/lapic.c | 7 ++++---
 kernel/events/core.c | 6 +++---
 2 files changed, 7 insertions(+), 6 deletions(-)

diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c
index 5439117..eff85f6 100644
--- a/arch/x86/kvm/lapic.c
+++ b/arch/x86/kvm/lapic.c
@@ -121,7 +121,7 @@ static inline void apic_set_spiv(struct kvm_lapic *apic, u32 val)
 		if (val & APIC_SPIV_APIC_ENABLED)
 			static_key_slow_dec_deferred(&apic_sw_disabled);
 		else
-			static_key_slow_inc(&apic_sw_disabled.key);
+			static_key_slow_inc_deferred(&apic_sw_disabled);
 	}
 	apic_set_reg(apic, APIC_SPIV, val);
 }
@@ -1351,7 +1351,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
 		if (value & MSR_IA32_APICBASE_ENABLE)
 			static_key_slow_dec_deferred(&apic_hw_disabled);
 		else
-			static_key_slow_inc(&apic_hw_disabled.key);
+			static_key_slow_inc_deferred(&apic_hw_disabled);
 		recalculate_apic_map(vcpu->kvm);
 	}
 
@@ -1546,7 +1546,8 @@ int kvm_create_lapic(struct kvm_vcpu *vcpu)
 	kvm_lapic_set_base(vcpu,
 			APIC_DEFAULT_PHYS_BASE | MSR_IA32_APICBASE_ENABLE);
 
-	static_key_slow_inc(&apic_sw_disabled.key); /* sw disabled at reset */
+	/* sw disabled at reset */
+	static_key_slow_inc_deferred(&apic_sw_disabled);
 	kvm_lapic_reset(vcpu);
 	kvm_iodevice_init(&apic->dev, &apic_mmio_ops);
 
diff --git a/kernel/events/core.c b/kernel/events/core.c
index d49a9d2..ade89a1 100644
--- a/kernel/events/core.c
+++ b/kernel/events/core.c
@@ -6565,7 +6565,7 @@ static void account_event(struct perf_event *event)
 		return;
 
 	if (event->attach_state & PERF_ATTACH_TASK)
-		static_key_slow_inc(&perf_sched_events.key);
+		static_key_slow_inc_deferred(&perf_sched_events);
 	if (event->attr.mmap || event->attr.mmap_data)
 		atomic_inc(&nr_mmap_events);
 	if (event->attr.comm)
@@ -6577,9 +6577,9 @@ static void account_event(struct perf_event *event)
 			tick_nohz_full_kick_all();
 	}
 	if (has_branch_stack(event))
-		static_key_slow_inc(&perf_sched_events.key);
+		static_key_slow_inc_deferred(&perf_sched_events);
 	if (is_cgroup_event(event))
-		static_key_slow_inc(&perf_sched_events.key);
+		static_key_slow_inc_deferred(&perf_sched_events);
 
 	account_event_cpu(event, event->cpu);
 }
-- 
1.8.3.1

[PATCH 5/7] jump_label: relax branch hinting restrictions

[Radim Krčmář]

We implemented the optimized branch selection in higher levels of api.
That made static_keys very unintuitive, so this patch introduces another
element to jump_table, carrying one bit that tells the underlying code
which branch to optimize.

It is now possible to select optimized branch for every jump_entry.

Current side effect is 1/3 increase increase in space, we could:
* use bitmasks and selectors on 2+ aligned code/struct.
  - aligning jump target is easy, but because it is not done by default
    and few bytes in .text are much worse that few kilos in .data,
    I chose not to
  - data is probably aligned by default on all current architectures,
    but programmer can force misalignment of static_key
* optimize each architecture independently
  - I can't test everything and this patch shouldn't break anything, so
    others can contribute in the future
* choose something worse, like packing or splitting
* ignore

proof: example & x86_64 disassembly: (F = ffffffff)

  struct static_key flexible_feature;
  noinline void jump_label_experiment(void) {
  	if ( static_key_false(&flexible_feature))
  	     asm ("push 0xa1");
  	else asm ("push 0xa0");
  	if (!static_key_false(&flexible_feature))
  	     asm ("push 0xb0");
  	else asm ("push 0xb1");
  	if ( static_key_true(&flexible_feature))
  	     asm ("push 0xc1");
  	else asm ("push 0xc0");
  	if (!static_key_true(&flexible_feature))
  	     asm ("push 0xd0");
  	else asm ("push 0xd1");
  }

  Disassembly of section .text: (push marked by "->")

  F81002000 <jump_label_experiment>:
  F81002000:       e8 7b 29 75 00          callq  F81754980 <__fentry__>
  F81002005:       55                      push   %rbp
  F81002006:       48 89 e5                mov    %rsp,%rbp
  F81002009:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
  F8100200e: ->    ff 34 25 a0 00 00 00    pushq  0xa0
  F81002015:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
  F8100201a: ->    ff 34 25 b0 00 00 00    pushq  0xb0
  F81002021:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
  F81002026: ->    ff 34 25 c1 00 00 00    pushq  0xc1
  F8100202d:       0f 1f 00                nopl   (%rax)
  F81002030:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
  F81002035: ->    ff 34 25 d1 00 00 00    pushq  0xd1
  F8100203c:       5d                      pop    %rbp
  F8100203d:       0f 1f 00                nopl   (%rax)
  F81002040:       c3                      retq
  F81002041:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  F81002048: ->    ff 34 25 d0 00 00 00    pushq  0xd0
  F8100204f:       5d                      pop    %rbp
  F81002050:       c3                      retq
  F81002051:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
  F81002058: ->    ff 34 25 c0 00 00 00    pushq  0xc0
  F8100205f:       90                      nop
  F81002060:       eb cb                   jmp    F8100202d <[...]+0x2d>
  F81002062:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
  F81002068: ->    ff 34 25 b1 00 00 00    pushq  0xb1
  F8100206f:       90                      nop
  F81002070:       eb af                   jmp    F81002021 <[...]+0x21>
  F81002072:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
  F81002078: ->    ff 34 25 a1 00 00 00    pushq  0xa1
  F8100207f:       90                      nop
  F81002080:       eb 93                   jmp    F81002015 <[...]+0x15>
  F81002082:       66 66 66 66 66 2e 0f    [...]
  F81002089:       1f 84 00 00 00 00 00

  Contents of section .data: (relevant part of embedded __jump_table)
    F81d26a40 09200081 ffffffff 78200081 ffffffff
    F81d26a50 20600f82 ffffffff 00000000 00000000
    F81d26a60 15200081 ffffffff 68200081 ffffffff
    F81d26a70 20600f82 ffffffff 00000000 00000000
    F81d26a80 21200081 ffffffff 58200081 ffffffff
    F81d26a90 20600f82 ffffffff 01000000 00000000
    F81d26aa0 30200081 ffffffff 48200081 ffffffff
    F81d26ab0 20600f82 ffffffff 01000000 00000000

  (I've also compiled for s390x, blocks were placed correctly,
   jump table looked ok too;
   I hope the least significant bit is correct everywhere)

Signed-off-by: Radim Krčmář <rkrcmar@redhat.com>
---
 Documentation/static-keys.txt         |  6 ----
 arch/arm/include/asm/jump_label.h     | 19 ++++++++----
 arch/arm/kernel/jump_label.c          |  2 +-
 arch/mips/include/asm/jump_label.h    | 19 ++++++++----
 arch/mips/kernel/jump_label.c         |  2 +-
 arch/powerpc/include/asm/jump_label.h | 19 ++++++++----
 arch/powerpc/kernel/jump_label.c      |  2 +-
 arch/s390/include/asm/jump_label.h    | 19 ++++++++----
 arch/s390/kernel/jump_label.c         |  2 +-
 arch/sparc/include/asm/jump_label.h   | 19 ++++++++----
 arch/sparc/kernel/jump_label.c        |  2 +-
 arch/x86/include/asm/jump_label.h     | 19 ++++++++----
 arch/x86/kernel/jump_label.c          | 32 ++++----------------
 include/linux/jump_label.h            | 55 ++++++++++++-----------------------
 kernel/jump_label.c                   | 29 ++++--------------
 15 files changed, 119 insertions(+), 127 deletions(-)

diff --git a/Documentation/static-keys.txt b/Documentation/static-keys.txt
index 9f5263d..57c040e 100644
--- a/Documentation/static-keys.txt
+++ b/Documentation/static-keys.txt
@@ -103,12 +103,6 @@ Or:
         else
                 do unlikely code
 
-A key that is initialized via 'STATIC_KEY_INIT_FALSE', must be used in a
-'static_key_false()' construct. Likewise, a key initialized via
-'STATIC_KEY_INIT_TRUE' must be used in a 'static_key_true()' construct. A
-single key can be used in many branches, but all the branches must match the
-way that the key has been initialized.
-
 The branch(es) can then be switched via:
 
 	static_key_slow_inc(&key);
diff --git a/arch/arm/include/asm/jump_label.h b/arch/arm/include/asm/jump_label.h
index 863c892..f4ec3af 100644
--- a/arch/arm/include/asm/jump_label.h
+++ b/arch/arm/include/asm/jump_label.h
@@ -14,18 +14,21 @@
 #define JUMP_LABEL_NOP	"nop"
 #endif
 
-static __always_inline bool arch_static_branch(struct static_key *key)
+struct static_key;
+
+static __always_inline bool arch_static_branch(struct static_key *key,
+		const bool default_branch)
 {
 	asm_volatile_goto("1:\n\t"
 		 JUMP_LABEL_NOP "\n\t"
 		 ".pushsection __jump_table,  \"aw\"\n\t"
-		 ".word 1b, %l[l_yes], %c0\n\t"
+		 ".word 1b, %l[l_yes], %c0, %c1\n\t"
 		 ".popsection\n\t"
-		 : :  "i" (key) :  : l_yes);
+		 : :  "i" (key), "i" (default_branch) :  : l_yes);
 
-	return false;
+	return default_branch;
 l_yes:
-	return true;
+	return !default_branch;
 }
 
 #endif /* __KERNEL__ */
@@ -36,6 +39,12 @@ struct jump_entry {
 	jump_label_t code;
 	jump_label_t target;
 	jump_label_t key;
+	union {
+		jump_label_t flags;
+		struct {
+			unsigned default_branch:1; /* lsb */
+		};
+	};
 };
 
 #endif
diff --git a/arch/arm/kernel/jump_label.c b/arch/arm/kernel/jump_label.c
index 4ce4f78..b02c531 100644
--- a/arch/arm/kernel/jump_label.c
+++ b/arch/arm/kernel/jump_label.c
@@ -13,7 +13,7 @@ static void __arch_jump_label_transform(struct jump_entry *entry,
 	void *addr = (void *)entry->code;
 	unsigned int insn;
 
-	if (type == JUMP_LABEL_ENABLE)
+	if (type != jump_label_default_branch(entry))
 		insn = arm_gen_branch(entry->code, entry->target);
 	else
 		insn = arm_gen_nop();
diff --git a/arch/mips/include/asm/jump_label.h b/arch/mips/include/asm/jump_label.h
index e194f95..2c065ec 100644
--- a/arch/mips/include/asm/jump_label.h
+++ b/arch/mips/include/asm/jump_label.h
@@ -20,17 +20,20 @@
 #define WORD_INSN ".word"
 #endif
 
-static __always_inline bool arch_static_branch(struct static_key *key)
+struct static_key;
+
+static __always_inline bool arch_static_branch(struct static_key *key,
+		const bool default_branch)
 {
 	asm_volatile_goto("1:\tnop\n\t"
 		"nop\n\t"
 		".pushsection __jump_table,  \"aw\"\n\t"
-		WORD_INSN " 1b, %l[l_yes], %0\n\t"
+		WORD_INSN " 1b, %l[l_yes], %0, %1\n\t"
 		".popsection\n\t"
-		: :  "i" (key) : : l_yes);
-	return false;
+		: :  "i" (key), "i" (default_branch) : : l_yes);
+	return default_branch;
 l_yes:
-	return true;
+	return !default_branch;
 }
 
 #endif /* __KERNEL__ */
@@ -45,6 +48,12 @@ struct jump_entry {
 	jump_label_t code;
 	jump_label_t target;
 	jump_label_t key;
+	union {
+		jump_label_t flags;
+		struct {
+			unsigned default_branch:1; /* lsb */
+		};
+	};
 };
 
 #endif /* _ASM_MIPS_JUMP_LABEL_H */
diff --git a/arch/mips/kernel/jump_label.c b/arch/mips/kernel/jump_label.c
index 6001610..e5b17ee 100644
--- a/arch/mips/kernel/jump_label.c
+++ b/arch/mips/kernel/jump_label.c
@@ -33,7 +33,7 @@ void arch_jump_label_transform(struct jump_entry *e,
 	/* Target must have 4 byte alignment. */
 	BUG_ON((e->target & 3) != 0);
 
-	if (type == JUMP_LABEL_ENABLE) {
+	if (type != jump_label_default_branch(entry)) {
 		insn.j_format.opcode = j_op;
 		insn.j_format.target = (e->target & J_RANGE_MASK) >> 2;
 	} else {
diff --git a/arch/powerpc/include/asm/jump_label.h b/arch/powerpc/include/asm/jump_label.h
index f016bb6..463c03d 100644
--- a/arch/powerpc/include/asm/jump_label.h
+++ b/arch/powerpc/include/asm/jump_label.h
@@ -17,17 +17,20 @@
 #define JUMP_ENTRY_TYPE		stringify_in_c(FTR_ENTRY_LONG)
 #define JUMP_LABEL_NOP_SIZE	4
 
-static __always_inline bool arch_static_branch(struct static_key *key)
+struct static_key;
+
+static __always_inline bool arch_static_branch(struct static_key *key,
+		const bool default_branch)
 {
 	asm_volatile_goto("1:\n\t"
 		 "nop\n\t"
 		 ".pushsection __jump_table,  \"aw\"\n\t"
-		 JUMP_ENTRY_TYPE "1b, %l[l_yes], %c0\n\t"
+		 JUMP_ENTRY_TYPE "1b, %l[l_yes], %c0, %c1\n\t"
 		 ".popsection \n\t"
-		 : :  "i" (key) : : l_yes);
-	return false;
+		 : :  "i" (key), "i" (default_branch) : : l_yes);
+	return default_branch;
 l_yes:
-	return true;
+	return !default_branch;
 }
 
 #ifdef CONFIG_PPC64
@@ -40,6 +43,12 @@ struct jump_entry {
 	jump_label_t code;
 	jump_label_t target;
 	jump_label_t key;
+	union {
+		jump_label_t flags;
+		struct {
+			unsigned default_branch:1; /* lsb */
+		};
+	};
 };
 
 #endif /* _ASM_POWERPC_JUMP_LABEL_H */
diff --git a/arch/powerpc/kernel/jump_label.c b/arch/powerpc/kernel/jump_label.c
index a1ed8a8..ebf148b 100644
--- a/arch/powerpc/kernel/jump_label.c
+++ b/arch/powerpc/kernel/jump_label.c
@@ -17,7 +17,7 @@ void arch_jump_label_transform(struct jump_entry *entry,
 {
 	u32 *addr = (u32 *)(unsigned long)entry->code;
 
-	if (type == JUMP_LABEL_ENABLE)
+	if (type != jump_label_default_branch(entry))
 		patch_branch(addr, entry->target, 0);
 	else
 		patch_instruction(addr, PPC_INST_NOP);
diff --git a/arch/s390/include/asm/jump_label.h b/arch/s390/include/asm/jump_label.h
index 346b1c8..5259b49 100644
--- a/arch/s390/include/asm/jump_label.h
+++ b/arch/s390/include/asm/jump_label.h
@@ -13,17 +13,20 @@
 #define ASM_ALIGN ".balign 4"
 #endif
 
-static __always_inline bool arch_static_branch(struct static_key *key)
+struct static_key;
+
+static __always_inline bool arch_static_branch(struct static_key *key,
+		const bool default_branch)
 {
 	asm_volatile_goto("0:	brcl 0,0\n"
 		".pushsection __jump_table, \"aw\"\n"
 		ASM_ALIGN "\n"
-		ASM_PTR " 0b, %l[label], %0\n"
+		ASM_PTR " 0b, %l[label], %0, %1\n"
 		".popsection\n"
-		: : "X" (key) : : label);
-	return false;
+		: : "X" (key), "X" (default_branch) : : label);
+	return default_branch;
 label:
-	return true;
+	return !default_branch;
 }
 
 typedef unsigned long jump_label_t;
@@ -32,6 +35,12 @@ struct jump_entry {
 	jump_label_t code;
 	jump_label_t target;
 	jump_label_t key;
+	union {
+		jump_label_t flags;
+		struct {
+			unsigned default_branch:1; /* lsb */
+		};
+	};
 };
 
 #endif
diff --git a/arch/s390/kernel/jump_label.c b/arch/s390/kernel/jump_label.c
index b987ab2..95958c5 100644
--- a/arch/s390/kernel/jump_label.c
+++ b/arch/s390/kernel/jump_label.c
@@ -28,7 +28,7 @@ static void __jump_label_transform(struct jump_entry *entry,
 	struct insn insn;
 	int rc;
 
-	if (type == JUMP_LABEL_ENABLE) {
+	if (type != jump_label_default_branch(entry)) {
 		/* brcl 15,offset */
 		insn.opcode = 0xc0f4;
 		insn.offset = (entry->target - entry->code) >> 1;
diff --git a/arch/sparc/include/asm/jump_label.h b/arch/sparc/include/asm/jump_label.h
index ec2e2e2..67b763d 100644
--- a/arch/sparc/include/asm/jump_label.h
+++ b/arch/sparc/include/asm/jump_label.h
@@ -7,19 +7,22 @@
 
 #define JUMP_LABEL_NOP_SIZE 4
 
-static __always_inline bool arch_static_branch(struct static_key *key)
+struct static_key;
+
+static __always_inline bool arch_static_branch(struct static_key *key,
+		const bool default_branch)
 {
 		asm_volatile_goto("1:\n\t"
 			 "nop\n\t"
 			 "nop\n\t"
 			 ".pushsection __jump_table,  \"aw\"\n\t"
 			 ".align 4\n\t"
-			 ".word 1b, %l[l_yes], %c0\n\t"
+			 ".word 1b, %l[l_yes], %c0, %c1\n\t"
 			 ".popsection \n\t"
-			 : :  "i" (key) : : l_yes);
-	return false;
+			 : :  "i" (key), "i" (default_branch) : : l_yes);
+	return default_branch;
 l_yes:
-	return true;
+	return !default_branch;
 }
 
 #endif /* __KERNEL__ */
@@ -30,6 +33,12 @@ struct jump_entry {
 	jump_label_t code;
 	jump_label_t target;
 	jump_label_t key;
+	union {
+		jump_label_t flags;
+		struct {
+			unsigned default_branch:1; /* lsb */
+		};
+	};
 };
 
 #endif
diff --git a/arch/sparc/kernel/jump_label.c b/arch/sparc/kernel/jump_label.c
index 48565c1..c963a9c 100644
--- a/arch/sparc/kernel/jump_label.c
+++ b/arch/sparc/kernel/jump_label.c
@@ -16,7 +16,7 @@ void arch_jump_label_transform(struct jump_entry *entry,
 	u32 val;
 	u32 *insn = (u32 *) (unsigned long) entry->code;
 
-	if (type == JUMP_LABEL_ENABLE) {
+	if (type != jump_label_default_branch(entry)) {
 		s32 off = (s32)entry->target - (s32)entry->code;
 
 #ifdef CONFIG_SPARC64
diff --git a/arch/x86/include/asm/jump_label.h b/arch/x86/include/asm/jump_label.h
index 6a2cefb..18e192e 100644
--- a/arch/x86/include/asm/jump_label.h
+++ b/arch/x86/include/asm/jump_label.h
@@ -16,18 +16,21 @@
 # define STATIC_KEY_INIT_NOP GENERIC_NOP5_ATOMIC
 #endif
 
-static __always_inline bool arch_static_branch(struct static_key *key)
+struct static_key;
+
+static __always_inline bool arch_static_branch(struct static_key *key,
+		const bool default_branch)
 {
 	asm_volatile_goto("1:"
 		".byte " __stringify(STATIC_KEY_INIT_NOP) "\n\t"
 		".pushsection __jump_table,  \"aw\" \n\t"
 		_ASM_ALIGN "\n\t"
-		_ASM_PTR "1b, %l[l_yes], %c0 \n\t"
+		_ASM_PTR "1b, %l[l_yes], %c0, %c1 \n\t"
 		".popsection \n\t"
-		: :  "i" (key) : : l_yes);
-	return false;
+		: :  "i" (key), "i" (default_branch) : : l_yes);
+	return default_branch;
 l_yes:
-	return true;
+	return !default_branch;
 }
 
 #endif /* __KERNEL__ */
@@ -42,6 +45,12 @@ struct jump_entry {
 	jump_label_t code;
 	jump_label_t target;
 	jump_label_t key;
+	union {
+		jump_label_t flags;
+		struct {
+			unsigned default_branch:1; /* lsb */
+		};
+	};
 };
 
 #endif
diff --git a/arch/x86/kernel/jump_label.c b/arch/x86/kernel/jump_label.c
index ee11b7d..8b66855 100644
--- a/arch/x86/kernel/jump_label.c
+++ b/arch/x86/kernel/jump_label.c
@@ -43,13 +43,15 @@ static void __jump_label_transform(struct jump_entry *entry,
 {
 	union jump_code_union code;
 	const unsigned char *ideal_nop = ideal_nops[NOP_ATOMIC5];
+	const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
 
-	if (type == JUMP_LABEL_ENABLE) {
+	if (type != jump_label_default_branch(entry)) {
 		/*
 		 * We are enabling this jump label. If it is not a nop
 		 * then something must have gone wrong.
 		 */
-		if (unlikely(memcmp((void *)entry->code, ideal_nop, 5) != 0))
+		if (unlikely(memcmp((void *)entry->code,
+		                    init ? default_nop : ideal_nop, 5) != 0))
 			bug_at((void *)entry->code, __LINE__);
 
 		code.jump = 0xe9;
@@ -63,7 +65,6 @@ static void __jump_label_transform(struct jump_entry *entry,
 		 * are converting the default nop to the ideal nop.
 		 */
 		if (init) {
-			const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
 			if (unlikely(memcmp((void *)entry->code, default_nop, 5) != 0))
 				bug_at((void *)entry->code, __LINE__);
 		} else {
@@ -101,33 +102,10 @@ void arch_jump_label_transform(struct jump_entry *entry,
 	put_online_cpus();
 }
 
-static enum {
-	JL_STATE_START,
-	JL_STATE_NO_UPDATE,
-	JL_STATE_UPDATE,
-} jlstate __initdata_or_module = JL_STATE_START;
-
 __init_or_module void arch_jump_label_transform_static(struct jump_entry *entry,
 				      enum jump_label_type type)
 {
-	/*
-	 * This function is called at boot up and when modules are
-	 * first loaded. Check if the default nop, the one that is
-	 * inserted at compile time, is the ideal nop. If it is, then
-	 * we do not need to update the nop, and we can leave it as is.
-	 * If it is not, then we need to update the nop to the ideal nop.
-	 */
-	if (jlstate == JL_STATE_START) {
-		const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
-		const unsigned char *ideal_nop = ideal_nops[NOP_ATOMIC5];
-
-		if (memcmp(ideal_nop, default_nop, 5) != 0)
-			jlstate = JL_STATE_UPDATE;
-		else
-			jlstate = JL_STATE_NO_UPDATE;
-	}
-	if (jlstate == JL_STATE_UPDATE)
-		__jump_label_transform(entry, type, text_poke_early, 1);
+	__jump_label_transform(entry, type, text_poke_early, 1);
 }
 
 #endif
diff --git a/include/linux/jump_label.h b/include/linux/jump_label.h
index 848bd15..a06791c 100644
--- a/include/linux/jump_label.h
+++ b/include/linux/jump_label.h
@@ -10,7 +10,8 @@
  * Jump labels provide an interface to generate dynamic branches using
  * self-modifying code. Assuming toolchain and architecture support the result
  * of a "if (static_key_false(&key))" statement is a unconditional branch (which
- * defaults to false - and the true block is placed out of line).
+ * defaults to false - and the true block is placed out of line,
+ * static_key_true(&key) has default to true)
  *
  * However at runtime we can change the branch target using
  * static_key_slow_{inc,dec}(). These function as a 'reference' count on the key
@@ -32,17 +33,9 @@
  * Lacking toolchain and or architecture support, it falls back to a simple
  * conditional branch.
  *
- * struct static_key my_key = STATIC_KEY_INIT_TRUE;
- *
- *   if (static_key_true(&my_key)) {
- *   }
- *
- * will result in the true case being in-line and starts the key with a single
- * reference. Mixing static_key_true() and static_key_false() on the same key is not
- * allowed.
- *
- * Not initializing the key (static data is initialized to 0s anyway) is the
- * same as using STATIC_KEY_INIT_FALSE.
+ * Initial count can be set by STATIC_KEY_INIT(x), defaults to 0, but it takes
+ * effect after jump_label_init() has finished, so static_key_enabled() must be
+ * used instead of static_key_{true,false} before.
  *
 */
 
@@ -53,7 +46,6 @@
 
 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;
@@ -75,30 +67,20 @@ struct module;
 #include <linux/atomic.h>
 #ifdef HAVE_JUMP_LABEL
 
-#define JUMP_LABEL_TRUE_BRANCH 1UL
-
 static
 inline struct jump_entry *jump_label_get_entries(struct static_key *key)
 {
-	return (struct jump_entry *)((unsigned long)key->entries
-						& ~JUMP_LABEL_TRUE_BRANCH);
-}
-
-static inline bool jump_label_get_branch_default(struct static_key *key)
-{
-	if ((unsigned long)key->entries & JUMP_LABEL_TRUE_BRANCH)
-		return true;
-	return false;
+	return (struct jump_entry *)((unsigned long)key->entries);
 }
 
 static __always_inline bool static_key_false(struct static_key *key)
 {
-	return arch_static_branch(key);
+	return arch_static_branch(key, false);
 }
 
 static __always_inline bool static_key_true(struct static_key *key)
 {
-	return !static_key_false(key);
+	return arch_static_branch(key, true);
 }
 
 extern struct jump_entry __start___jump_table[];
@@ -116,10 +98,13 @@ extern void static_key_slow_inc(struct static_key *key);
 extern void static_key_slow_dec(struct static_key *key);
 extern void jump_label_apply_nops(struct module *mod);
 
-#define STATIC_KEY_INIT_TRUE ((struct static_key) \
-	{ .enabled = ATOMIC_INIT(1), .entries = (void *)1 })
-#define STATIC_KEY_INIT_FALSE ((struct static_key) \
-	{ .enabled = ATOMIC_INIT(0), .entries = (void *)0 })
+/* this function does not exactly belong here, but it is the path of least
+ * resistance; refactoring will move it into arch specific code */
+static inline enum jump_label_type
+jump_label_default_branch(struct jump_entry *entry) {
+	return entry->default_branch ? JUMP_LABEL_ENABLE
+	                             : JUMP_LABEL_DISABLE;
+}
 
 #else  /* !HAVE_JUMP_LABEL */
 
@@ -168,14 +153,12 @@ static inline int jump_label_apply_nops(struct module *mod)
 	return 0;
 }
 
-#define STATIC_KEY_INIT_TRUE ((struct static_key) \
-		{ .enabled = ATOMIC_INIT(1) })
-#define STATIC_KEY_INIT_FALSE ((struct static_key) \
-		{ .enabled = ATOMIC_INIT(0) })
-
 #endif	/* HAVE_JUMP_LABEL */
 
-#define STATIC_KEY_INIT STATIC_KEY_INIT_FALSE
+#define STATIC_KEY_INIT(x) ((struct static_key) { .enabled = ATOMIC_INIT(x) })
+#define STATIC_KEY_INIT_TRUE  STATIC_KEY_INIT(1)
+#define STATIC_KEY_INIT_FALSE STATIC_KEY_INIT(0)
+
 #define jump_label_enabled static_key_enabled
 
 static inline bool static_key_enabled(struct static_key *key)
diff --git a/kernel/jump_label.c b/kernel/jump_label.c
index 30aa3b0..3670c0e 100644
--- a/kernel/jump_label.c
+++ b/kernel/jump_label.c
@@ -63,10 +63,7 @@ void static_key_slow_inc(struct static_key *key)
 
 	jump_label_lock();
 	if (atomic_read(&key->enabled) == 0) {
-		if (!jump_label_get_branch_default(key))
-			jump_label_update(key, JUMP_LABEL_ENABLE);
-		else
-			jump_label_update(key, JUMP_LABEL_DISABLE);
+		jump_label_update(key, JUMP_LABEL_ENABLE);
 	}
 	atomic_inc(&key->enabled);
 	jump_label_unlock();
@@ -98,10 +95,7 @@ static void __static_key_slow_dec(struct static_key *key,
 			WARN(1, "jump label: negative deferred count!\n");
 		}
 	} else {
-		if (!jump_label_get_branch_default(key))
-			jump_label_update(key, JUMP_LABEL_DISABLE);
-		else
-			jump_label_update(key, JUMP_LABEL_ENABLE);
+		jump_label_update(key, JUMP_LABEL_DISABLE);
 	}
 	jump_label_unlock();
 }
@@ -189,13 +183,8 @@ static void __jump_label_update(struct static_key *key,
 
 static enum jump_label_type jump_label_type(struct static_key *key)
 {
-	bool true_branch = jump_label_get_branch_default(key);
-	bool state = static_key_enabled(key);
-
-	if ((!true_branch && state) || (true_branch && !state))
-		return JUMP_LABEL_ENABLE;
-
-	return JUMP_LABEL_DISABLE;
+	return static_key_enabled(key) ? JUMP_LABEL_ENABLE
+	                               : JUMP_LABEL_DISABLE;
 }
 
 static void static_key_rate_limit_flush(struct static_key *key)
@@ -225,10 +214,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;
+		*((unsigned long *)&key->entries) = (unsigned long)iter;
 #ifdef CONFIG_MODULES
 		key->next = NULL;
 #endif
@@ -319,10 +305,7 @@ static int jump_label_add_module(struct module *mod)
 
 		key = iterk;
 		if (__module_address(iter->key) == mod) {
-			/*
-			 * Set key->entries to iter, but preserve JUMP_LABEL_TRUE_BRANCH.
-			 */
-			*((unsigned long *)&key->entries) += (unsigned long)iter;
+			*((unsigned long *)&key->entries) = (unsigned long)iter;
 			key->next = NULL;
 			continue;
 		}
-- 
1.8.3.1

[PATCH 7/7] init: execute jump_label_init() earlier

[Radim Krčmář]

Patching of jump labels does not have to depend on any other init code,
so we should do it as soon as possible because static_keys cannot be
used before that.

If we find it does depend on something, the init case of patching should
be modified.

Signed-off-by: Radim Krčmář <rkrcmar@redhat.com>
---
There should be no reason to use static_key_enabled() now, I'll remove
it from api in following series if there are no objections.

I would also feel a bit safer with disabled interrupts, but it might not
be required.

 init/main.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/init/main.c b/init/main.c
index 63d3e8f..c84fbb9 100644
--- a/init/main.c
+++ b/init/main.c
@@ -489,6 +489,11 @@ asmlinkage void __init start_kernel(void)
 	 */
 	boot_init_stack_canary();
 
+	/*
+	 * Jump labels have undefined semantics before initialization
+	 */
+	jump_label_init();
+
 	cgroup_init_early();
 
 	local_irq_disable();
@@ -518,7 +523,6 @@ asmlinkage void __init start_kernel(void)
 		   __stop___param - __start___param,
 		   -1, -1, &unknown_bootoption);
 
-	jump_label_init();
 
 	/*
 	 * These use large bootmem allocations and must precede
-- 
1.8.3.1

Re: [PATCH 1/7] static_key: flush rate limit timer on rmmod

[Paolo Bonzini]

Il 17/10/2013 12:10, Radim Krčmář ha scritto:
> Fix a bug when we free module memory while timer is pending by marking
> deferred static keys and flushing the timer on module unload.
> 
> Also make static_key_rate_limit() useable more than once.
> 
> Reproducer: (host crasher)
>   modprobe kvm_intel
>   (sleep 1; echo quit) \
>     | qemu-kvm -kernel /dev/null -monitor stdio &
>   sleep 0.5
>   until modprobe -rv kvm_intel 2>/dev/null; do true; done
>   modprobe -v kvm_intel
> 
> Signed-off-by: Radim Krčmář <rkrcmar@redhat.com>
> ---
> Very hacky; I've already queued generalizing ratelimit and applying it
> here, but there is still a lot to do on static keys ...
> 
>  include/linux/jump_label.h |  1 +
>  kernel/jump_label.c        | 17 ++++++++++++++++-
>  2 files changed, 17 insertions(+), 1 deletion(-)
> 
> diff --git a/include/linux/jump_label.h b/include/linux/jump_label.h
> index a507907..848bd15 100644
> --- a/include/linux/jump_label.h
> +++ b/include/linux/jump_label.h
> @@ -58,6 +58,7 @@ struct static_key {
>  #ifdef CONFIG_MODULES
>  	struct static_key_mod *next;
>  #endif
> +	atomic_t deferred;
>  };
>  
>  # include <asm/jump_label.h>
> diff --git a/kernel/jump_label.c b/kernel/jump_label.c
> index 297a924..7018042 100644
> --- a/kernel/jump_label.c
> +++ b/kernel/jump_label.c
> @@ -116,8 +116,9 @@ EXPORT_SYMBOL_GPL(static_key_slow_dec_deferred);
>  void jump_label_rate_limit(struct static_key_deferred *key,
>  		unsigned long rl)
>  {
> +	if (!atomic_xchg(&key->key.deferred, 1))
> +		INIT_DELAYED_WORK(&key->work, jump_label_update_timeout);

Can it actually happen that jump_label_rate_limit is called multiple
times?  If so, this hunk alone would be a separate bugfix.  I don't
think all the concurrency that you're protecting against can actually
happen, but in any case I'd just take the jump_label_lock() instead of
using atomics.

It's also not necessary to use a new field, since you can just check
key->timeout.

All this gives something like this for static_key_rate_limit_flush:

        if (key->timeout) {
		jump_label_lock();
		if (key->enabled) {
			jump_label_unlock();
			flush_delayed_work(&dkey->work);
		} else
			jump_label_unlock();
	}

Paolo

>  	key->timeout = rl;
> -	INIT_DELAYED_WORK(&key->work, jump_label_update_timeout);
>  }
>  EXPORT_SYMBOL_GPL(jump_label_rate_limit);
>  
> @@ -185,6 +186,14 @@ static enum jump_label_type jump_label_type(struct static_key *key)
>  	return JUMP_LABEL_DISABLE;
>  }
>  
> +static void static_key_rate_limit_flush(struct static_key *key)
> +{
> +	struct static_key_deferred *dkey =
> +		container_of(key, struct static_key_deferred, key);
> +	if (atomic_read(&key->deferred))
> +		flush_delayed_work(&dkey->work);
> +}
> +
>  void __init jump_label_init(void)
>  {
>  	struct jump_entry *iter_start = __start___jump_table;
> @@ -334,6 +343,12 @@ static void jump_label_del_module(struct module *mod)
>  
>  		key = (struct static_key *)(unsigned long)iter->key;
>  
> +		/* We could also check if the static_key is used in its
> +		 * defining module and skip this flush then.
> +		 * (Rewrite of ratelimit in planned, so we don't care much)
> +		 */
> +		static_key_rate_limit_flush(key);
> +
>  		if (__module_address(iter->key) == mod)
>  			continue;
>  
> 

Re: [PATCH 4/7] static_key: use static_key_slow_inc_deferred()

[Paolo Bonzini]

Il 17/10/2013 12:10, Radim Krčmář ha scritto:
> Simple replacement where possible.
> Saves us problematic access to the structure and allows optimalizations
> and bug fixes to take place.

I think you should introduce this first as a simple wrapper around
static_key_slow_inc, and then add the bells and whistles you have in
patches 2 and 3.

Paolo

> Signed-off-by: Radim Krčmář <rkrcmar@redhat.com>
> ---
>  arch/x86/kvm/lapic.c | 7 ++++---
>  kernel/events/core.c | 6 +++---
>  2 files changed, 7 insertions(+), 6 deletions(-)
> 
> diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c
> index 5439117..eff85f6 100644
> --- a/arch/x86/kvm/lapic.c
> +++ b/arch/x86/kvm/lapic.c
> @@ -121,7 +121,7 @@ static inline void apic_set_spiv(struct kvm_lapic *apic, u32 val)
>  		if (val & APIC_SPIV_APIC_ENABLED)
>  			static_key_slow_dec_deferred(&apic_sw_disabled);
>  		else
> -			static_key_slow_inc(&apic_sw_disabled.key);
> +			static_key_slow_inc_deferred(&apic_sw_disabled);
>  	}
>  	apic_set_reg(apic, APIC_SPIV, val);
>  }
> @@ -1351,7 +1351,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
>  		if (value & MSR_IA32_APICBASE_ENABLE)
>  			static_key_slow_dec_deferred(&apic_hw_disabled);
>  		else
> -			static_key_slow_inc(&apic_hw_disabled.key);
> +			static_key_slow_inc_deferred(&apic_hw_disabled);
>  		recalculate_apic_map(vcpu->kvm);
>  	}
>  
> @@ -1546,7 +1546,8 @@ int kvm_create_lapic(struct kvm_vcpu *vcpu)
>  	kvm_lapic_set_base(vcpu,
>  			APIC_DEFAULT_PHYS_BASE | MSR_IA32_APICBASE_ENABLE);
>  
> -	static_key_slow_inc(&apic_sw_disabled.key); /* sw disabled at reset */
> +	/* sw disabled at reset */
> +	static_key_slow_inc_deferred(&apic_sw_disabled);
>  	kvm_lapic_reset(vcpu);
>  	kvm_iodevice_init(&apic->dev, &apic_mmio_ops);
>  
> diff --git a/kernel/events/core.c b/kernel/events/core.c
> index d49a9d2..ade89a1 100644
> --- a/kernel/events/core.c
> +++ b/kernel/events/core.c
> @@ -6565,7 +6565,7 @@ static void account_event(struct perf_event *event)
>  		return;
>  
>  	if (event->attach_state & PERF_ATTACH_TASK)
> -		static_key_slow_inc(&perf_sched_events.key);
> +		static_key_slow_inc_deferred(&perf_sched_events);
>  	if (event->attr.mmap || event->attr.mmap_data)
>  		atomic_inc(&nr_mmap_events);
>  	if (event->attr.comm)
> @@ -6577,9 +6577,9 @@ static void account_event(struct perf_event *event)
>  			tick_nohz_full_kick_all();
>  	}
>  	if (has_branch_stack(event))
> -		static_key_slow_inc(&perf_sched_events.key);
> +		static_key_slow_inc_deferred(&perf_sched_events);
>  	if (is_cgroup_event(event))
> -		static_key_slow_inc(&perf_sched_events.key);
> +		static_key_slow_inc_deferred(&perf_sched_events);
>  
>  	account_event_cpu(event, event->cpu);
>  }
> 

Re: [PATCH 0/7] static_key: fix timer bugs & change api (a bit)

[Paolo Bonzini]

Il 17/10/2013 12:10, Radim Krčmář ha scritto:
> While fixing a simple crash on kvm module unload
> 
> 1: rate_limit timer can fire after we free its key's module memory.
> 
> I noticed other deficiencies in jump_label/static_key code
> (The most important is 4.)
> 
> 2: jump_label_rate_limit() uses an initializator and thus cannot be used
>    more than once, leaving no good way to change the timeout.
> 
> I have made the API easier on programmers: [1/7]
>  * timer is automatically flushed on rmmod
>  * jump_label_rate_limit() initializes only once
>     - pretty hacky, but we cannot automatically initialize on
>       kernel_init/insmod due to insufficient information and while I
>       would love getting it through another section, it is probably
>       better to do a useless check with this low-rate operation
>     * we could flush the timer on change
>     * 'init()' + 'set()' (+ 'exit()' ?) would be an alternative ...
> 
> 3: schedule_delayed_work() does not queue the work if one is already
>    pending, but atomic_inc(&key->enabled) is called anyway in
>    static_key_slow_dec_deferred(), with the false belief it will be
>    decreased when the timer fires.
> 
> Fixed in [2,3,4/7], by addition of static_key_slow_inc_deferred().

I think you're doing a bit too much for one series.  Let's focus on the
bugfix and perhaps the improvements to the deferred static key API, that
is patches 1/2/3/4.

Paolo

Re: [PATCH 5/7] jump_label: relax branch hinting restrictions

[Steven Rostedt]

On Thu, 17 Oct 2013 12:10:28 +0200
Radim Krčmář <rkrcmar@redhat.com> wrote:

> We implemented the optimized branch selection in higher levels of api.
> That made static_keys very unintuitive, so this patch introduces another
> element to jump_table, carrying one bit that tells the underlying code
> which branch to optimize.
> 
> It is now possible to select optimized branch for every jump_entry.
> 
> Current side effect is 1/3 increase increase in space, we could:
> * use bitmasks and selectors on 2+ aligned code/struct.
>   - aligning jump target is easy, but because it is not done by default
>     and few bytes in .text are much worse that few kilos in .data,
>     I chose not to
>   - data is probably aligned by default on all current architectures,
>     but programmer can force misalignment of static_key
> * optimize each architecture independently
>   - I can't test everything and this patch shouldn't break anything, so
>     others can contribute in the future
> * choose something worse, like packing or splitting
> * ignore
> 
> proof: example & x86_64 disassembly: (F = ffffffff)
> 
>   struct static_key flexible_feature;
>   noinline void jump_label_experiment(void) {
>   	if ( static_key_false(&flexible_feature))
>   	     asm ("push 0xa1");
>   	else asm ("push 0xa0");
>   	if (!static_key_false(&flexible_feature))
>   	     asm ("push 0xb0");
>   	else asm ("push 0xb1");
>   	if ( static_key_true(&flexible_feature))
>   	     asm ("push 0xc1");
>   	else asm ("push 0xc0");
>   	if (!static_key_true(&flexible_feature))
>   	     asm ("push 0xd0");
>   	else asm ("push 0xd1");
>   }
> 
>   Disassembly of section .text: (push marked by "->")
> 
>   F81002000 <jump_label_experiment>:
>   F81002000:       e8 7b 29 75 00          callq  F81754980 <__fentry__>
>   F81002005:       55                      push   %rbp
>   F81002006:       48 89 e5                mov    %rsp,%rbp
>   F81002009:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
>   F8100200e: ->    ff 34 25 a0 00 00 00    pushq  0xa0
>   F81002015:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
>   F8100201a: ->    ff 34 25 b0 00 00 00    pushq  0xb0
>   F81002021:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
>   F81002026: ->    ff 34 25 c1 00 00 00    pushq  0xc1
>   F8100202d:       0f 1f 00                nopl   (%rax)
>   F81002030:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
>   F81002035: ->    ff 34 25 d1 00 00 00    pushq  0xd1
>   F8100203c:       5d                      pop    %rbp
>   F8100203d:       0f 1f 00                nopl   (%rax)
>   F81002040:       c3                      retq

This looks exactly like what we want. I take it this is with your
patch. What was the result before the patch?

-- Steve

>   F81002041:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
>   F81002048: ->    ff 34 25 d0 00 00 00    pushq  0xd0
>   F8100204f:       5d                      pop    %rbp
>   F81002050:       c3                      retq
>   F81002051:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
>   F81002058: ->    ff 34 25 c0 00 00 00    pushq  0xc0
>   F8100205f:       90                      nop
>   F81002060:       eb cb                   jmp    F8100202d <[...]+0x2d>
>   F81002062:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
>   F81002068: ->    ff 34 25 b1 00 00 00    pushq  0xb1
>   F8100206f:       90                      nop
>   F81002070:       eb af                   jmp    F81002021 <[...]+0x21>
>   F81002072:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
>   F81002078: ->    ff 34 25 a1 00 00 00    pushq  0xa1
>   F8100207f:       90                      nop
>   F81002080:       eb 93                   jmp    F81002015 <[...]+0x15>
>   F81002082:       66 66 66 66 66 2e 0f    [...]
>   F81002089:       1f 84 00 00 00 00 00
> 
>   Contents of section .data: (relevant part of embedded __jump_table)

Re: [PATCH 1/7] static_key: flush rate limit timer on rmmod

[Radim Krčmář]

2013-10-17 12:35+0200, Paolo Bonzini:
> Il 17/10/2013 12:10, Radim Krčmář ha scritto:
> > Fix a bug when we free module memory while timer is pending by marking
> > deferred static keys and flushing the timer on module unload.
> > 
> > Also make static_key_rate_limit() useable more than once.
> > 
> > Reproducer: (host crasher)
> >   modprobe kvm_intel
> >   (sleep 1; echo quit) \
> >     | qemu-kvm -kernel /dev/null -monitor stdio &
> >   sleep 0.5
> >   until modprobe -rv kvm_intel 2>/dev/null; do true; done
> >   modprobe -v kvm_intel
> > 
> > Signed-off-by: Radim Krčmář <rkrcmar@redhat.com>
> > ---
> > Very hacky; I've already queued generalizing ratelimit and applying it
> > here, but there is still a lot to do on static keys ...
> > 
> >  include/linux/jump_label.h |  1 +
> >  kernel/jump_label.c        | 17 ++++++++++++++++-
> >  2 files changed, 17 insertions(+), 1 deletion(-)
> > 
> > diff --git a/include/linux/jump_label.h b/include/linux/jump_label.h
> > index a507907..848bd15 100644
> > --- a/include/linux/jump_label.h
> > +++ b/include/linux/jump_label.h
> > @@ -58,6 +58,7 @@ struct static_key {
> >  #ifdef CONFIG_MODULES
> >  	struct static_key_mod *next;
> >  #endif
> > +	atomic_t deferred;
> >  };
> >  
> >  # include <asm/jump_label.h>
> > diff --git a/kernel/jump_label.c b/kernel/jump_label.c
> > index 297a924..7018042 100644
> > --- a/kernel/jump_label.c
> > +++ b/kernel/jump_label.c
> > @@ -116,8 +116,9 @@ EXPORT_SYMBOL_GPL(static_key_slow_dec_deferred);
> >  void jump_label_rate_limit(struct static_key_deferred *key,
> >  		unsigned long rl)
> >  {
> > +	if (!atomic_xchg(&key->key.deferred, 1))
> > +		INIT_DELAYED_WORK(&key->work, jump_label_update_timeout);
> 
> Can it actually happen that jump_label_rate_limit is called multiple
> times?  If so, this hunk alone would be a separate bugfix.  I don't
> think all the concurrency that you're protecting against can actually
> happen, but in any case I'd just take the jump_label_lock() instead of
> using atomics.

It can't happen in current code and it is highly unlikely to happen in
future too.

There was no reason to take the lock, so I didn't, but we could use bool
in struct then ... I'll do it, even though it has more lines of code, it
is probably easier to understand.

> It's also not necessary to use a new field, since you can just check
> key->timeout.

The flush is done automatically and we don't know if the jump_entry
belongs to deferred key, so we shouldn't just blindly try.
(another bit to jump_entry flags would supply enough information, but we
 haven't decided if we want to optimize them into pointers and there
 isn't much space in them + they were introduced in patch [5/7])

> All this gives something like this for static_key_rate_limit_flush:
> 
>         if (key->timeout) {
> 		jump_label_lock();
> 		if (key->enabled) {
> 			jump_label_unlock();
> 			flush_delayed_work(&dkey->work);
> 		} else
> 			jump_label_unlock();
> 	}

Ugh, I see a problem in original patch now: I changed it from
cancel_delayed_work() in the module that owns this key shortly before
posting, because it could still bug then and forgot it isn't good to
take jump_label_lock() a second time, which would be done in the flush.

This needs be solved by checking if we are the last module that uses
this key and issuing a cancel() then and I'm not sure it would not still
bug yet -- the work could already be running, just waiting for
jump_label_lock() we would then somehow manage to free the memory first.

(leaving it to programmer starts to look sane ...)

> Paolo

Re: [PATCH 4/7] static_key: use static_key_slow_inc_deferred()

[Radim Krčmář]

2013-10-17 12:39+0200, Paolo Bonzini:
> Il 17/10/2013 12:10, Radim Krčmář ha scritto:
> > Simple replacement where possible.
> > Saves us problematic access to the structure and allows optimalizations
> > and bug fixes to take place.
> 
> I think you should introduce this first as a simple wrapper around
> static_key_slow_inc, and then add the bells and whistles you have in
> patches 2 and 3.

Ok, thanks.

Re: [PATCH 5/7] jump_label: relax branch hinting restrictions

[Radim Krčmář]

2013-10-17 13:35-0400, Steven Rostedt:
> On Thu, 17 Oct 2013 12:10:28 +0200
> Radim Krčmář <rkrcmar@redhat.com> wrote:
> 
> > We implemented the optimized branch selection in higher levels of api.
> > That made static_keys very unintuitive, so this patch introduces another
> > element to jump_table, carrying one bit that tells the underlying code
> > which branch to optimize.
> > 
> > It is now possible to select optimized branch for every jump_entry.
> > 
> > Current side effect is 1/3 increase increase in space, we could:
> > * use bitmasks and selectors on 2+ aligned code/struct.
> >   - aligning jump target is easy, but because it is not done by default
> >     and few bytes in .text are much worse that few kilos in .data,
> >     I chose not to
> >   - data is probably aligned by default on all current architectures,
> >     but programmer can force misalignment of static_key
> > * optimize each architecture independently
> >   - I can't test everything and this patch shouldn't break anything, so
> >     others can contribute in the future
> > * choose something worse, like packing or splitting
> > * ignore
> > 
> > proof: example & x86_64 disassembly: (F = ffffffff)
> > 
> >   struct static_key flexible_feature;
> >   noinline void jump_label_experiment(void) {
> >   	if ( static_key_false(&flexible_feature))
> >   	     asm ("push 0xa1");
> >   	else asm ("push 0xa0");
> >   	if (!static_key_false(&flexible_feature))
> >   	     asm ("push 0xb0");
> >   	else asm ("push 0xb1");
> >   	if ( static_key_true(&flexible_feature))
> >   	     asm ("push 0xc1");
> >   	else asm ("push 0xc0");
> >   	if (!static_key_true(&flexible_feature))
> >   	     asm ("push 0xd0");
> >   	else asm ("push 0xd1");
> >   }
> > 
> >   Disassembly of section .text: (push marked by "->")
> > 
> >   F81002000 <jump_label_experiment>:
> >   F81002000:       e8 7b 29 75 00          callq  F81754980 <__fentry__>
> >   F81002005:       55                      push   %rbp
> >   F81002006:       48 89 e5                mov    %rsp,%rbp
> >   F81002009:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
> >   F8100200e: ->    ff 34 25 a0 00 00 00    pushq  0xa0
> >   F81002015:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
> >   F8100201a: ->    ff 34 25 b0 00 00 00    pushq  0xb0
> >   F81002021:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
> >   F81002026: ->    ff 34 25 c1 00 00 00    pushq  0xc1
> >   F8100202d:       0f 1f 00                nopl   (%rax)
> >   F81002030:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
> >   F81002035: ->    ff 34 25 d1 00 00 00    pushq  0xd1
> >   F8100203c:       5d                      pop    %rbp
> >   F8100203d:       0f 1f 00                nopl   (%rax)
> >   F81002040:       c3                      retq
> 
> This looks exactly like what we want. I take it this is with your
> patch. What was the result before the patch?

Yes, this is after the patch.

The branches would (should) be the same without patch, but
static_key_true() was defined as !static_key_false(), so this piece of
code was invalid before, because half of them would be patched to use
the wrong branch.

> -- Steve
> 
> >   F81002041:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
> >   F81002048: ->    ff 34 25 d0 00 00 00    pushq  0xd0
> >   F8100204f:       5d                      pop    %rbp
> >   F81002050:       c3                      retq
> >   F81002051:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)
> >   F81002058: ->    ff 34 25 c0 00 00 00    pushq  0xc0
> >   F8100205f:       90                      nop
> >   F81002060:       eb cb                   jmp    F8100202d <[...]+0x2d>
> >   F81002062:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
> >   F81002068: ->    ff 34 25 b1 00 00 00    pushq  0xb1
> >   F8100206f:       90                      nop
> >   F81002070:       eb af                   jmp    F81002021 <[...]+0x21>
> >   F81002072:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
> >   F81002078: ->    ff 34 25 a1 00 00 00    pushq  0xa1
> >   F8100207f:       90                      nop
> >   F81002080:       eb 93                   jmp    F81002015 <[...]+0x15>
> >   F81002082:       66 66 66 66 66 2e 0f    [...]
> >   F81002089:       1f 84 00 00 00 00 00
> > 
> >   Contents of section .data: (relevant part of embedded __jump_table)