NOHZ updates for v4.6

Linus,

Please pull the latest timers-nohz-for-linus git tree from:

git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git timers-nohz-for-linus

# HEAD: 1f25184656a00a59e3a953189070d42a749f6aee Merge branch 'timers/core-v9' of git://git.kernel.org/pub/scm/linux/kernel/git/frederic/linux-dynticks into timers/nohz

Please pull NOHZ enhancements, by Frederic Weisbecker, which reorganizes/refactors the NOHZ 'can the tick be stopped?' infrastructure and related code to be data driven, and harmonizes the naming and handling of all the various properties.

Querying it all is now a matter of:

  triton:~/tip> git grep TICK_DEP_ kernel/
  kernel/events/core.c:   tick_dep_clear_cpu(smp_processor_id(), TICK_DEP_BIT_PERF_EVENTS);
  kernel/events/core.c:           tick_nohz_dep_clear(TICK_DEP_BIT_PERF_EVENTS);
  kernel/events/core.c:                   tick_dep_set_cpu(smp_processor_id(), TICK_DEP_BIT_PERF_EVENTS);
  kernel/events/core.c:           tick_nohz_dep_set(TICK_DEP_BIT_PERF_EVENTS);
  kernel/sched/clock.c:   tick_dep_clear(TICK_DEP_BIT_CLOCK_UNSTABLE);
  kernel/sched/clock.c:   tick_dep_set(TICK_DEP_BIT_CLOCK_UNSTABLE);
  kernel/sched/sched.h:           tick_nohz_dep_clear_cpu(cpu, TICK_DEP_BIT_SCHED);
  kernel/sched/sched.h:           tick_nohz_dep_set_cpu(cpu, TICK_DEP_BIT_SCHED);
  kernel/time/posix-cpu-timers.c:                 tick_dep_set_task(p, TICK_DEP_BIT_POSIX_TIMER);
  kernel/time/posix-cpu-timers.c:                 tick_dep_set_signal(p->signal, TICK_DEP_BIT_POSIX_TIMER);
  kernel/time/posix-cpu-timers.c:         tick_dep_clear_task(tsk, TICK_DEP_BIT_POSIX_TIMER);
  kernel/time/posix-cpu-timers.c: tick_dep_clear_signal(sig, TICK_DEP_BIT_POSIX_TIMER);
  kernel/time/posix-cpu-timers.c: tick_dep_set_signal(tsk->signal, TICK_DEP_BIT_POSIX_TIMER);

  kernel/time/tick-sched.c:       if (dep & TICK_DEP_MASK_POSIX_TIMER) {
  kernel/time/tick-sched.c:               trace_tick_stop(0, TICK_DEP_MASK_POSIX_TIMER);
  kernel/time/tick-sched.c:       if (dep & TICK_DEP_MASK_PERF_EVENTS) {
  kernel/time/tick-sched.c:               trace_tick_stop(0, TICK_DEP_MASK_PERF_EVENTS);
  kernel/time/tick-sched.c:       if (dep & TICK_DEP_MASK_SCHED) {
  kernel/time/tick-sched.c:               trace_tick_stop(0, TICK_DEP_MASK_SCHED);
  kernel/time/tick-sched.c:       if (dep & TICK_DEP_MASK_CLOCK_UNSTABLE)
  kernel/time/tick-sched.c:               trace_tick_stop(0, TICK_DEP_MASK_CLOCK_UNSTABLE);
  kernel/time/tick-sched.c:               trace_tick_stop(1, TICK_DEP_MASK_NONE);

Thanks,

Ingo

------------------>
Frederic Weisbecker (9):
atomic: Export fetch_or()
nohz: Implement wide kick on top of irq work
nohz: New tick dependency mask
nohz: Use enum code for tick stop failure tracing message
perf: Migrate perf to use new tick dependency mask model
sched: Account rr tasks
sched: Migrate sched to use new tick dependency mask model
posix-cpu-timers: Migrate to use new tick dependency mask model
sched-clock: Migrate to use new tick dependency mask model

 include/linux/atomic.h         |  21 +++++
 include/linux/perf_event.h     |   6 --
 include/linux/posix-timers.h   |   3 -
 include/linux/sched.h          |  11 ++-
 include/linux/tick.h           |  97 ++++++++++++++++++++++-
 include/trace/events/timer.h   |  36 +++++++--
 kernel/events/core.c           |  65 +++++++++++----
 kernel/sched/clock.c           |   5 ++
 kernel/sched/core.c            |  49 +++++-------
 kernel/sched/rt.c              |  16 ++++
 kernel/sched/sched.h           |  48 +++++++----
 kernel/time/posix-cpu-timers.c |  52 +++---------
 kernel/time/tick-sched.c       | 175 ++++++++++++++++++++++++++++++++---------
 kernel/time/tick-sched.h       |   1 +
 14 files changed, 424 insertions(+), 161 deletions(-)

index 301de78d65f7..6c502cb13c95 100644
@@ -548,6 +548,27 @@ static inline int atomic_dec_if_positive(atomic_t *v)
 }
 #endif
 
+/**
+ * fetch_or - perform *ptr |= mask and return old value of *ptr
+ * @ptr: pointer to value
+ * @mask: mask to OR on the value
+ *
+ * cmpxchg based fetch_or, macro so it works for different integer types
+ */
+#ifndef fetch_or
+#define fetch_or(ptr, mask)						\
+({	typeof(*(ptr)) __old, __val = *(ptr);				\
+	for (;;) {							\
+		__old = cmpxchg((ptr), __val, __val | (mask));		\
+		if (__old == __val)					\
+			break;						\
+		__val = __old;						\
+	}								\
+	__old;								\
+})
+#endif
+
+
 #ifdef CONFIG_GENERIC_ATOMIC64
 #include <asm-generic/atomic64.h>
 #endif

index f5c5a3fa2c81..6e44efc19a6a 100644
@@ -1109,12 +1109,6 @@ static inline void perf_event_task_tick(void)				{ }
 static inline int perf_event_release_kernel(struct perf_event *event)	{ return 0; }
 #endif
 
-#if defined(CONFIG_PERF_EVENTS) && defined(CONFIG_NO_HZ_FULL)
-extern bool perf_event_can_stop_tick(void);
-#else
-static inline bool perf_event_can_stop_tick(void)			{ return true; }
-#endif
-
 #if defined(CONFIG_PERF_EVENTS) && defined(CONFIG_CPU_SUP_INTEL)
 extern void perf_restore_debug_store(void);
 #else

index 907f3fd191ac..62d44c176071 100644
@@ -128,9 +128,6 @@ void posix_cpu_timer_schedule(struct k_itimer *timer);
 void run_posix_cpu_timers(struct task_struct *task);
 void posix_cpu_timers_exit(struct task_struct *task);
 void posix_cpu_timers_exit_group(struct task_struct *task);
-
-bool posix_cpu_timers_can_stop_tick(struct task_struct *tsk);
-
 void set_process_cpu_timer(struct task_struct *task, unsigned int clock_idx,
 			   cputime_t *newval, cputime_t *oldval);
 

index a10494a94cc3..2b10348806d8 100644
@@ -719,6 +719,10 @@ struct signal_struct {
 	/* Earliest-expiration cache. */
 	struct task_cputime cputime_expires;
 
+#ifdef CONFIG_NO_HZ_FULL
+	unsigned long tick_dep_mask;
+#endif
+
 	struct list_head cpu_timers[3];
 
 	struct pid *tty_old_pgrp;

@@ -1542,6 +1546,10 @@ struct task_struct {
 		VTIME_SYS,
 	} vtime_snap_whence;
 #endif
+
+#ifdef CONFIG_NO_HZ_FULL
+	unsigned long tick_dep_mask;
+#endif
 	unsigned long nvcsw, nivcsw; /* context switch counts */
 	u64 start_time;		/* monotonic time in nsec */
 	u64 real_start_time;	/* boot based time in nsec */

@@ -2356,10 +2364,7 @@ static inline void wake_up_nohz_cpu(int cpu) { }
 #endif
 
 #ifdef CONFIG_NO_HZ_FULL
-extern bool sched_can_stop_tick(void);
 extern u64 scheduler_tick_max_deferment(void);
-#else
-static inline bool sched_can_stop_tick(void) { return false; }
 #endif
 
 #ifdef CONFIG_SCHED_AUTOGROUP

index 073b9ac245ba..51440131d337 100644
@@ -328,23 +328,49 @@ TRACE_EVENT(itimer_expire,
 );
 
 #ifdef CONFIG_NO_HZ_COMMON
+
+#define TICK_DEP_NAMES					\
+		tick_dep_name(NONE)			\
+		tick_dep_name(POSIX_TIMER)		\
+		tick_dep_name(PERF_EVENTS)		\
+		tick_dep_name(SCHED)			\
+		tick_dep_name_end(CLOCK_UNSTABLE)
+
+#undef tick_dep_name
+#undef tick_dep_name_end
+
+#define tick_dep_name(sdep) TRACE_DEFINE_ENUM(TICK_DEP_MASK_##sdep);
+#define tick_dep_name_end(sdep)  TRACE_DEFINE_ENUM(TICK_DEP_MASK_##sdep);
+
+TICK_DEP_NAMES
+
+#undef tick_dep_name
+#undef tick_dep_name_end
+
+#define tick_dep_name(sdep) { TICK_DEP_MASK_##sdep, #sdep },
+#define tick_dep_name_end(sdep) { TICK_DEP_MASK_##sdep, #sdep }
+
+#define show_tick_dep_name(val)				\
+	__print_symbolic(val, TICK_DEP_NAMES)
+
 TRACE_EVENT(tick_stop,
 
-	TP_PROTO(int success, char *error_msg),
+	TP_PROTO(int success, int dependency),
 
-	TP_ARGS(success, error_msg),
+	TP_ARGS(success, dependency),
 
 	TP_STRUCT__entry(
 		__field( int ,		success	)
-		__string( msg, 		error_msg )
+		__field( int ,		dependency )
 	),
 
 	TP_fast_assign(
 		__entry->success	= success;
-		__assign_str(msg, error_msg);
+		__entry->dependency	= dependency;
 	),
 
-	TP_printk("success=%s msg=%s",  __entry->success ? "yes" : "no", __get_str(msg))
+	TP_printk("success=%d dependency=%s",  __entry->success, \
+			show_tick_dep_name(__entry->dependency))
 );
 #endif
 

index bc54e84675da..fedb967a9841 100644
@@ -61,6 +61,7 @@
 #include <linux/static_key.h>
 #include <linux/workqueue.h>
 #include <linux/compiler.h>
+#include <linux/tick.h>
 
 /*
  * Scheduler clock - returns current time in nanosec units.

@@ -89,6 +90,8 @@ static void __set_sched_clock_stable(void)
 {
 	if (!sched_clock_stable())
 		static_key_slow_inc(&__sched_clock_stable);
+
+	tick_dep_clear(TICK_DEP_BIT_CLOCK_UNSTABLE);
 }
 
 void set_sched_clock_stable(void)

@@ -108,6 +111,8 @@ static void __clear_sched_clock_stable(struct work_struct *work)
 	/* XXX worry about clock continuity */
 	if (sched_clock_stable())
 		static_key_slow_dec(&__sched_clock_stable);
+
+	tick_dep_set(TICK_DEP_BIT_CLOCK_UNSTABLE);
 }
 
 static DECLARE_WORK(sched_clock_work, __clear_sched_clock_stable);

index 8ec86abe0ea1..3f1fcffbb18f 100644
@@ -1142,12 +1142,27 @@ unsigned int rt_se_nr_running(struct sched_rt_entity *rt_se)
 }
 
 static inline
+unsigned int rt_se_rr_nr_running(struct sched_rt_entity *rt_se)
+{
+	struct rt_rq *group_rq = group_rt_rq(rt_se);
+	struct task_struct *tsk;
+
+	if (group_rq)
+		return group_rq->rr_nr_running;
+
+	tsk = rt_task_of(rt_se);
+
+	return (tsk->policy == SCHED_RR) ? 1 : 0;
+}
+
+static inline
 void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
 {
 	int prio = rt_se_prio(rt_se);
 
 	WARN_ON(!rt_prio(prio));
 	rt_rq->rt_nr_running += rt_se_nr_running(rt_se);
+	rt_rq->rr_nr_running += rt_se_rr_nr_running(rt_se);
 
 	inc_rt_prio(rt_rq, prio);
 	inc_rt_migration(rt_se, rt_rq);

@@ -1160,6 +1175,7 @@ void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
 	WARN_ON(!rt_prio(rt_se_prio(rt_se)));
 	WARN_ON(!rt_rq->rt_nr_running);
 	rt_rq->rt_nr_running -= rt_se_nr_running(rt_se);
+	rt_rq->rr_nr_running -= rt_se_rr_nr_running(rt_se);
 
 	dec_rt_prio(rt_rq, rt_se_prio(rt_se));
 	dec_rt_migration(rt_se, rt_rq);

index a4a8d4e9baa1..eb4e32566a83 100644
@@ -60,6 +60,7 @@ struct tick_sched {
 	u64				next_timer;
 	ktime_t				idle_expires;
 	int				do_timer_last;
+	unsigned long			tick_dep_mask;
 };
 
 extern struct tick_sched *tick_get_tick_sched(int cpu);

So the below cures that; but do we want to maybe pull this back into sched.c and expose a version that operates on a fixed type instead?

Although with xchg() and cmpxchg() we've already set a precedence for multi-width operators.

The whole thread_info::flags thing is rather 'special' and I'm not sure we even want to go clean that up, I can see why 64bit arch would very much want a 64bit flags word etc. And TIF_flags are very arch specific.

---
 include/linux/atomic.h | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

index 6c502cb13c95..114caf672b11 100644
@@ -558,8 +558,9 @@ static inline int atomic_dec_if_positive(atomic_t *v)
 #ifndef fetch_or
 #define fetch_or(ptr, mask)						\
 ({	typeof(*(ptr)) __old, __val = *(ptr);				\
+ 	typeof(mask) __mask = (mask);					\
 	for (;;) {							\
-		__old = cmpxchg((ptr), __val, __val | (mask));		\
+		__old = cmpxchg((ptr), __val, __val | __mask);		\
 		if (__old == __val)					\
 			break;						\
 		__val = __old;						\

Indeed.

Yes.

Ok.

I can see two other problems with it as well:

1) 'ptr' may get evaluated multiple times as well, not just 'mask'.

2) its naming sucks. "fetch_or()" does not really signal that it's a fundamentally atomic operation, nor what API family it belongs to.

Given that it's in include/linux/atomic.h, and it has _almost_ xchg() semantics - how about we name it xchg_or() and model it after that? From the semantics POV it's really an unconditional xchg()-alike API, even though technically it's a cmpxchg() loop.

I've attached a (totally untested) patch that fixes the bugs and does the rename.

Indeed, thread_info->flags is 'almost' but not quite 'unsigned long':

triton:~/tip> grep -E '\<flags\>.*;' $(git grep -l 'thread_info {' arch/) | grep -vE 'WARN|return'

 arch/alpha/include/asm/thread_info.h:   unsigned int            flags;          /* low level flags */
 arch/arc/include/asm/thread_info.h:     unsigned long flags;            /* low level flags */
 arch/arm/include/asm/thread_info.h:     unsigned long           flags;          /* low level flags */
 arch/arm64/include/asm/thread_info.h:   unsigned long           flags;          /* low level flags */
 arch/avr32/include/asm/thread_info.h:   unsigned long           flags;          /* low level flags */
 arch/blackfin/include/asm/thread_info.h:        unsigned long flags;    /* low level flags */
 arch/c6x/include/asm/thread_info.h:     unsigned long           flags;          /* low level flags */
 arch/cris/include/asm/thread_info.h:    unsigned long           flags;          /* low level flags */
 arch/frv/include/asm/thread_info.h:     unsigned long           flags;          /* low level flags */
 arch/h8300/include/asm/thread_info.h:   unsigned long      flags;               /* low level flags */
 arch/hexagon/include/asm/thread_info.h: unsigned long           flags;          /* low level flags */
 arch/ia64/include/asm/thread_info.h:    __u32 flags;                    /* thread_info flags (see TIF_*) */
 arch/m32r/include/asm/thread_info.h:    unsigned long           flags;          /* low level flags */
 arch/m68k/include/asm/thread_info.h:    unsigned long           flags;
 arch/metag/include/asm/thread_info.h:   unsigned long flags;    /* low level flags */
 arch/microblaze/include/asm/thread_info.h:      unsigned long           flags; /* low level flags */
 arch/mips/include/asm/thread_info.h:    unsigned long           flags;          /* low level flags */
 arch/mn10300/include/asm/thread_info.h: unsigned long           flags;          /* low level flags */
 arch/nios2/include/asm/thread_info.h:   unsigned long           flags;          /* low level flags */
 arch/openrisc/include/asm/thread_info.h:        unsigned long           flags;          /* low level flags */
 arch/parisc/include/asm/thread_info.h:  unsigned long flags;            /* thread_info flags (see TIF_*) */
 arch/powerpc/include/asm/thread_info.h: unsigned long   flags ____cacheline_aligned_in_smp;
 arch/s390/include/asm/thread_info.h:    unsigned long           flags;          /* low level flags */
 arch/score/include/asm/thread_info.h:   unsigned long           flags;          /* low level flags */
 arch/sh/include/asm/thread_info.h:      unsigned long           flags;          /* low level flags */
 arch/sparc/include/asm/thread_info_32.h:        unsigned long           flags;          /* low level flags */
 arch/sparc/include/asm/thread_info_64.h:        unsigned long           flags;
 arch/tile/include/asm/thread_info.h:    unsigned long           flags;          /* low level flags */
 arch/um/include/asm/thread_info.h:      unsigned long           flags;          /* low level flags */
 arch/unicore32/include/asm/thread_info.h:       unsigned long           flags;          /* low level flags */
 arch/x86/include/asm/thread_info.h:     __u32                   flags;          /* low level flags */
 arch/xtensa/include/asm/thread_info.h:  unsigned long           flags;          /* low level flags */

alpha, ia64 and x86 are the odd ones out with an int ti::flags.

Yes, its natural type would be 'unsigned int'.

Yes, fetch_or() uses cmpxchg() internally, and AFAICS cmpxchg() is guaranteed to work on two integer types:

- 32 bit
- the natural word type of the architecture. (32 or 64 bit)

Many architectures have wider support for cmpxchg(): 8, 16, 32 and 64 bits, but we cannot rely on that in a generic header.

So changing the dependency mask type to 'unsigned int' should be safe. I'll send another patch for that.

Sorry about this, that was quite sloppy on several levels!

Thanks,

Ingo

===========================>
From: Ingo Molnar <[email protected]>
Date: Tue, 15 Mar 2016 10:19:10 +0100
Subject: [PATCH] atomic: Fix bugs in 'fetch_or()' and rename it to 'xchg_or()'

Linus noticed a couple of problems with the fetch_or() implementation introduced by 5fd7a09cfb8c ("atomic: Export fetch_or()"):

- Sloppy macro implementation: 'mask' and 'ptr' is evaluated multiple times, which will break if arguments have side effects.

- Sloppy semantics: the naming and structure of the macro is ambigious, with no well-defined semantics. It's neither an atomic nor a cmpxchg() interface, but still it lives in include/linux/atomic.h.

Solve this by:

- Extracting the arguments into helper variables once, and never using the original arguments from that point on. This makes it pretty clear that there can be no unwanted macro evaluation side effects.

- Renaming fetch_or() to xchg_or(), recognizing that the semantics are xchg()-alike.

Also propagate the rename to the call sites.

---
 include/linux/atomic.h   | 20 +++++++++++++-------
 kernel/sched/core.c      |  2 +-
 kernel/time/tick-sched.c |  4 ++--
 3 files changed, 16 insertions(+), 10 deletions(-)

index 6c502cb13c95..a884f56b882f 100644
@@ -549,21 +549,27 @@ static inline int atomic_dec_if_positive(atomic_t *v)
 #endif
 
 /**
- * fetch_or - perform *ptr |= mask and return old value of *ptr
- * @ptr: pointer to value
+ * xchg_or - perform *ptr |= mask atomically and return old value of *ptr
+ * @ptr: pointer to value (cmpxchg() compatible integer pointer type)
  * @mask: mask to OR on the value
  *
- * cmpxchg based fetch_or, macro so it works for different integer types
+ * cmpxchg() based, it's a macro so it works for different integer types.
  */
-#ifndef fetch_or
-#define fetch_or(ptr, mask)						\
-({	typeof(*(ptr)) __old, __val = *(ptr);				\
+#ifndef xchg_or
+# define xchg_or(ptr, mask)						\
+({									\
+	typeof(ptr)  __ptr  = (ptr);					\
+	typeof(mask) __mask = (mask);					\
+									\
+	typeof(*(__ptr)) __old, __val = *__ptr;				\
+									\
 	for (;;) {							\
-		__old = cmpxchg((ptr), __val, __val | (mask));		\
+		__old = cmpxchg(__ptr, __val, __val | __mask);		\
 		if (__old == __val)					\
 			break;						\
 		__val = __old;						\
 	}								\
+									\
 	__old;								\
 })
 #endif

index 1c82ded3e675..de380776d1df 100644
@@ -330,7 +330,7 @@ static inline void init_hrtick(void)
 static bool set_nr_and_not_polling(struct task_struct *p)
 {
 	struct thread_info *ti = task_thread_info(p);
-	return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
+	return !(xchg_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
 }
 
 /*

index 969e6704c3c9..851631899352 100644
@@ -264,7 +264,7 @@ static void tick_nohz_dep_set_all(unsigned long *dep,
 {
 	unsigned long prev;
 
-	prev = fetch_or(dep, BIT_MASK(bit));
+	prev = xchg_or(dep, BIT_MASK(bit));
 	if (!prev)
 		tick_nohz_full_kick_all();
 }

@@ -294,7 +294,7 @@ void tick_nohz_dep_set_cpu(int cpu, enum tick_dep_bits bit)
 
 	ts = per_cpu_ptr(&tick_cpu_sched, cpu);
 
-	prev = fetch_or(&ts->tick_dep_mask, BIT_MASK(bit));
+	prev = xchg_or(&ts->tick_dep_mask, BIT_MASK(bit));
 	if (!prev) {
 		preempt_disable();
 		/* Perf needs local kick that is NMI safe */

So there are other problems with the macro - see the patch I just sent that tries to fix all of them.

Yes, and if we name the new API 'xchg_or()' as I did it in my patch then it all nicely fits into the existing scheme.

Thanks,

Ingo

Linus noticed that the new tick_dep_mask types introduced in:

d027d45d8a17 ("nohz: New tick dependency mask")

... are sloppily defined as 'unsigned long' - which is wasteful to carry just 4 bits and which may also create suboptimal data types on 64-bit systems with word alignment padding holes in them.

Fix this by changing the type to the more natural 'unsigned int'.

(The xchg_or() API will work fine with 'unsigned int' as well.)

---
 include/linux/sched.h    |  4 ++--
 kernel/time/tick-sched.c | 11 +++++------
 2 files changed, 7 insertions(+), 8 deletions(-)

index c617ea12c6b7..6d1842bb7abd 100644
@@ -718,7 +718,7 @@ struct signal_struct {
 	struct task_cputime cputime_expires;
 
 #ifdef CONFIG_NO_HZ_FULL
-	unsigned long tick_dep_mask;
+	unsigned int tick_dep_mask;
 #endif
 
 	struct list_head cpu_timers[3];

@@ -1548,7 +1548,7 @@ struct task_struct {
 #endif
 
 #ifdef CONFIG_NO_HZ_FULL
-	unsigned long tick_dep_mask;
+	unsigned int tick_dep_mask;
 #endif
 	unsigned long nvcsw, nivcsw; /* context switch counts */
 	u64 start_time;		/* monotonic time in nsec */

index 851631899352..fe0f57f3432f 100644
@@ -157,9 +157,9 @@ static void tick_sched_handle(struct tick_sched *ts, struct pt_regs *regs)
 cpumask_var_t tick_nohz_full_mask;
 cpumask_var_t housekeeping_mask;
 bool tick_nohz_full_running;
-static unsigned long tick_dep_mask;
+static unsigned int tick_dep_mask;
 
-static void trace_tick_dependency(unsigned long dep)
+static void trace_tick_dependency(unsigned int dep)
 {
 	if (dep & TICK_DEP_MASK_POSIX_TIMER) {
 		trace_tick_stop(0, TICK_DEP_MASK_POSIX_TIMER);

@@ -259,10 +259,9 @@ static void tick_nohz_full_kick_all(void)
 	preempt_enable();
 }
 
-static void tick_nohz_dep_set_all(unsigned long *dep,
-				  enum tick_dep_bits bit)
+static void tick_nohz_dep_set_all(unsigned int *dep, enum tick_dep_bits bit)
 {
-	unsigned long prev;
+	unsigned int prev;
 
 	prev = xchg_or(dep, BIT_MASK(bit));
 	if (!prev)

@@ -289,7 +288,7 @@ void tick_nohz_dep_clear(enum tick_dep_bits bit)
  */
 void tick_nohz_dep_set_cpu(int cpu, enum tick_dep_bits bit)
 {
-	unsigned long prev;
+	unsigned int prev;
 	struct tick_sched *ts;
 
 	ts = per_cpu_ptr(&tick_cpu_sched, cpu);

I disagree there, the fetch-$op naming is widely used for atomic operations that return the previous value. See for example the C/C++11 atomic ops.

I've even thought about reworking our entire atomic*_t bits to match. That is, introduce all the fetch_$op primitives, then convert all the $op_return ones over and finally remove all the $op_return ones.

I've not done so because we're all so very used to $op_return that I'm sure people (and this would very much include me) would curse me for changing this.

The reason for fetch_$op is that it also works for irreversible operations like or. With or_return you simply cannot tell what the previous state was (with add_return you can do a simple subtraction to revert to the prior state).

And yes, some people use the xchg-$op naming, but its less widely used (x86 asm being one). Other also use swap-$op.

In any case, I prefer the name as it was.

So this shiny new patch manages to crash the x86 kernel with a NULL pointer dereference:

  [    0.143027] BUG: unable to handle kernel NULL pointer dereference at           (null)
  [    0.144000] IP: [<ffffffff8107c64c>] resched_curr+0x3c/0xc0

GCC manages to turn this:

static bool set_nr_and_not_polling(struct task_struct *p)

{
        struct thread_info *ti = task_thread_info(p);
        return !(xchg_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
}

and this:

    41c1:       89 c2                   mov    %eax,%edx
    41c3:       89 d6                   mov    %edx,%esi
    41c5:       31 c9                   xor    %ecx,%ecx
    41c7:       89 d0                   mov    %edx,%eax
    41c9:       83 ce 08                or     $0x8,%esi
    41cc:       f0 0f b1 31             lock cmpxchg %esi,(%rcx)

    41c4:       89 c2                   mov    %eax,%edx
    41c6:       89 d6                   mov    %edx,%esi
    41c8:       89 d0                   mov    %edx,%eax
    41ca:       83 ce 08                or     $0x8,%esi
    41cd:       f0 0f b1 31             lock cmpxchg %esi,(%rcx)

	cmpxchg_8()
	cmpxchg_16()
	cmpxchg_32()
	cmpxchg_64()

	xchg_or_32()
	xchg_or_64()
	...

The problem I see is that we don't really have the fetch_*() naming in the kernel right now, while we do have the xchg_*() naming. The latter is 'obviously' an atomic operation - while 'fetch' could be anything.

No strong opinion, but I think fetch_or() is not a particularly good name.

Thanks,

Ingo

Hm, so the problem I did not consider is the following:

triton:~/tip> git grep tick_dep_mask kernel | grep _bit

 kernel/time/tick-sched.c:       clear_bit(bit, &tick_dep_mask);
 kernel/time/tick-sched.c:       clear_bit(bit, &ts->tick_dep_mask);
 kernel/time/tick-sched.c:       clear_bit(bit, &tsk->tick_dep_mask);
 kernel/time/tick-sched.c:       clear_bit(bit, &sig->tick_dep_mask);

and the bitops natural type (and in fact the only supported bitops type) is 'unsigned long'.

So it's not that easy to change a bitmask over to unsigned int.

Suggestions?

Thanks,

Ingo

Linus noticed a couple of problems with the fetch_or() implementation introduced by 5fd7a09cfb8c ("atomic: Export fetch_or()"):

- Sloppy macro implementation: 'mask' and 'ptr' is evaluated multiple times, which will break if arguments have side effects. Also, it uses double-underscore temporary variables - which is dangerous as low level asm ones are using those too and they may alias in unexpected ways.

- Sloppy semantics: the naming and structure of the macro is ambigious, with no well-defined semantics. It's neither an atomic nor a cmpxchg() interface, but still it lives in include/linux/atomic.h.

Solve this by:

- Extracting the arguments into helper variables once, and never using the original arguments from that point on. This makes it pretty clear that there can be no unwanted macro evaluation side effects.

- Using single-underscore temporary variables.

- Renaming fetch_or() to xchg_or(), recognizing that the semantics are xchg()-alike.

Also propagate the rename to the call sites.

---
 include/linux/atomic.h   | 26 ++++++++++++++++----------
 kernel/sched/core.c      |  2 +-
 kernel/time/tick-sched.c |  4 ++--
 3 files changed, 19 insertions(+), 13 deletions(-)

index 6c502cb13c95..7bc5297bcca8 100644
@@ -549,22 +549,28 @@ static inline int atomic_dec_if_positive(atomic_t *v)
 #endif
 
 /**
- * fetch_or - perform *ptr |= mask and return old value of *ptr
- * @ptr: pointer to value
+ * xchg_or - perform *ptr |= mask atomically and return old value of *ptr
+ * @ptr: pointer to value (cmpxchg() compatible integer pointer type)
  * @mask: mask to OR on the value
  *
- * cmpxchg based fetch_or, macro so it works for different integer types
+ * cmpxchg() based, it's a macro so it works for different integer types.
  */
-#ifndef fetch_or
-#define fetch_or(ptr, mask)						\
-({	typeof(*(ptr)) __old, __val = *(ptr);				\
+#ifndef xchg_or
+# define xchg_or(ptr, mask)						\
+({									\
+	typeof(ptr)  _ptr  = (ptr);					\
+	typeof(mask) _mask = (mask);					\
+									\
+	typeof(*_ptr) _old, _val = *_ptr;				\
+									\
 	for (;;) {							\
-		__old = cmpxchg((ptr), __val, __val | (mask));		\
-		if (__old == __val)					\
+		_old = cmpxchg(_ptr, _val, _val | _mask);		\
+		if (_old == _val)					\
 			break;						\
-		__val = __old;						\
+		_val = _old;						\
 	}								\
-	__old;								\
+									\
+	_old;								\
 })
 #endif
 

index e5725b931bee..bbd347c04826 100644
@@ -329,7 +329,7 @@ static inline void init_hrtick(void)
 static bool set_nr_and_not_polling(struct task_struct *p)
 {
 	struct thread_info *ti = task_thread_info(p);
-	return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
+	return !(xchg_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
 }
 
 /*

index 969e6704c3c9..851631899352 100644
@@ -264,7 +264,7 @@ static void tick_nohz_dep_set_all(unsigned long *dep,
 {
 	unsigned long prev;
 
-	prev = fetch_or(dep, BIT_MASK(bit));
+	prev = xchg_or(dep, BIT_MASK(bit));
 	if (!prev)
 		tick_nohz_full_kick_all();
 }

@@ -294,7 +294,7 @@ void tick_nohz_dep_set_cpu(int cpu, enum tick_dep_bits bit)
 
 	ts = per_cpu_ptr(&tick_cpu_sched, cpu);
 
-	prev = fetch_or(&ts->tick_dep_mask, BIT_MASK(bit));
+	prev = xchg_or(&ts->tick_dep_mask, BIT_MASK(bit));
 	if (!prev) {
 		preempt_disable();
 		/* Perf needs local kick that is NMI safe */

So if we are still on the same page at this point, we'd have to add a pointer variant too I suspect:

	cmpxchg_ptr()
	xchg_ptr()

... whose bitness may differ between architectures(subarches), but it would still be a single variant per architecture, i.e. still with pretty clear type propagation and with a very clear notion of which architecture supports what.

It looks like a lot of work, but it's all low complexity work AFAICS that could be partly automated.

Thanks,

Ingo

Btw., if we do all this, we could still add auto-type API variants, but now they would be implemented at the highest level, with none of the auto-type complexity pushed down to the architecture level. Architectures just provide their set of APIs for a given list of types, and that's it.

I hate to see all the auto-typing complexity pushed down to the arch assembly level:

/*
* Atomic compare and exchange. Compare OLD with MEM, if identical,
* store NEW in MEM. Return the initial value in MEM. Success is
* indicated by comparing RETURN with OLD.
*/
#define __raw_cmpxchg(ptr, old, new, size, lock) \

({									\
	__typeof__(*(ptr)) __ret;					\
	__typeof__(*(ptr)) __old = (old);				\
	__typeof__(*(ptr)) __new = (new);				\
	switch (size) {							\
	case __X86_CASE_B:						\
	{								\
		volatile u8 *__ptr = (volatile u8 *)(ptr);		\
		asm volatile(lock "cmpxchgb %2,%1"			\
			     : "=a" (__ret), "+m" (*__ptr)		\
			     : "q" (__new), "0" (__old)			\
			     : "memory");				\
		break;							\
	}								\
	case __X86_CASE_W:						\
	{								\
		volatile u16 *__ptr = (volatile u16 *)(ptr);		\
		asm volatile(lock "cmpxchgw %2,%1"			\
			     : "=a" (__ret), "+m" (*__ptr)		\
			     : "r" (__new), "0" (__old)			\
			     : "memory");				\
		break;							\
	}								\
	case __X86_CASE_L:						\
	{								\
		volatile u32 *__ptr = (volatile u32 *)(ptr);		\
		asm volatile(lock "cmpxchgl %2,%1"			\
			     : "=a" (__ret), "+m" (*__ptr)		\
			     : "r" (__new), "0" (__old)			\
			     : "memory");				\
		break;							\
	}								\
	case __X86_CASE_Q:						\
	{								\
		volatile u64 *__ptr = (volatile u64 *)(ptr);		\
		asm volatile(lock "cmpxchgq %2,%1"			\
			     : "=a" (__ret), "+m" (*__ptr)		\
			     : "r" (__new), "0" (__old)			\
			     : "memory");				\
		break;							\
	}								\
	default:							\
		__cmpxchg_wrong_size();					\
	}								\
	__ret;								\
})

it makes things harder to read, harder to debug and harder to optimize.

Thanks,

Ingo

We don't have xchg_*() naming, we have xchg() and that's about it. And yes, people know xchg() is an atomic op. But 'fetch (and) or' is also atomic, it has to be, it needs to do 2 operations in 1.

Furthermore, the relevant wikipedia page is:

https://en.wikipedia.org/wiki/Fetch-and-add

So the naming is widely established.

We typically call those _long(), like atomic_long_t etc.. Under the assumption that sizeof(long) == sizeof(void *).

Also, _IF_ we're going to do this, this is the perfect opportunity to also introduce the __atomic address space and load() and store() operations. This is needed for architectures where:

	cmpxchg()/xchg()

isn't safe against regular stores, like all those who implement atomics using hashed spinlocked.

Its going to be a horrid lot of work though :/

Let me add another argument for why I don't like the "exchange/swap (and) add" naming.

Exchange (and swap) replace one value for another, like:

	old = xchg(ptr, val);

Whatever was there, gets replaced by the independent value in @val. Straight up replacement.

However with something like xchg_or, you don't do a direct replacement with an unrelated value. Instead you modify the pre-existing value. So there really isn't an exchange at all.

So "fetch (and) or" really describes the operation better. You load (fetch) the value and then modify it, in an indivisible (aka atomic) fashion.

Right you are.

Actually, I like the naming, I just don't like the implementation.

It's not just the "evaluated multiple times", it's also the fact that if we start doing "fetch_or()", then some day we'll want "fetch_and()" or "fetch_clear()" etc.

Or, in fact, "fetch_add()", which is often closer to what hardware does than the "atomic_add_return()" we have now (the difference is that "fetch_add()" returns the original value, while "atomic_add_return()" returns the end result).

So what I meant with "try to match what we already have in our existing atomic.h" is that we do the _infrastructure_ so well. We do it well both by having separate UP and SMP versions of the underlying helpers, but we do it well by having those helpers that are then used to implement the different atomic versions.

So I'd like something similar for the "fetch_op" thing.

Linus

Ahh. I missed that too.

Ok, leave the 64-bit field for now, while we think about this. But one option is to just use "atomic_andnot()" instead of clear_bit().

That would imply using an "atomic_t", which would be fairly natural (and would be 32-bit).

And wouldn't it be so nice if "thread_info->flags" would just be atomic_t too. Right now we use a mixture of bit-ops and ACCESS_ONCE() (and many codepaths then doing neither, and just accessing it directly, ignoring any races.

Oh well.

Linus

Thanks a lot for fixing this!
Some comments below:

I wouldn't mind that much having xchg_or() but I think Peterz has good arguments in favour of keeping the original name.

Ah! Now I remember why I used unsigned long :-s

I can try that. And then we would end up with atomic_fetch_or() and maybe the scheduler could keep its ad-hoc version until thread_info types get unified (if that's possible).

I can try that too while at it :-)

The real problem with thread_info->flags is that it's per-architecture, and people access that thing from assembly code.

So changing that is potentially really *very* painful. The patch itself is not likely too bad, but having confidence that everything was caught?

Nasty. It would probably be a very good cleanup, but I'm not sure how worthwhile it is considering the pain.

(The only good news is that any problem is likely to be *very* obvious. Switching the field to a 32-bit type on a big-endian machine and not catching some case will mean that people will check or modify the wrong flags, and you'd likely get breakage quite quickly)

Linus

Ok!

Could we at least somehow sneak the notion of 'atomicity' into it?

	fetch_or()
	fetch_and()
	fetch_not()

vs.

fetch_atomic_or()
fetch_atomic_and()
fetch_atomic_not()

vs.

atomic_fetch_or()
atomic_fetch_and()
atomic_fetch_not()

?

Thanks,

Ingo

Yeah, so in the perf tooling build we do have -Wshadow to catch such mishaps, but not in the main kernel build.

... and yes, if I add it via the patch below the bug gets warned about:

include/linux/atomic.h:561:15: note: shadowed declaration is here

   typeof(ptr)  __ptr  = (ptr);     \
               ^

kernel/sched/core.c:332:11: note: in expansion of macro ‘xchg_or’
return !(xchg_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLA

... but I also get a ton of other warnings, just when building a single kernel/sched/core.o file:

./arch/x86/include/asm/bitops.h:396:28: warning: declaration of ‘ffs’ shadows a built-in function [-Wshadow] ./arch/x86/include/asm/bitops.h:396:28: warning: declaration of ‘ffs’ shadows a built-in function [-Wshadow] include/linux/jiffies.h:422:60: warning: declaration of ‘jiffies’ shadows a global declaration [-Wshadow] ./arch/x86/include/asm/io_apic.h:187:54: warning: declaration of ‘apic’ shadows a global declaration [-Wshadow] ./arch/x86/include/asm/bitops.h:396:28: warning: declaration of ‘ffs’ shadows a built-in function [-Wshadow] include/linux/jiffies.h:422:60: warning: declaration of ‘jiffies’ shadows a global declaration [-Wshadow] ./arch/x86/include/asm/io_apic.h:187:54: warning: declaration of ‘apic’ shadows a global declaration [-Wshadow] include/linux/kernel.h:750:12: warning: declaration of ‘_min1’ shadows a previous local [-Wshadow] include/linux/kernel.h:750:12: warning: declaration of ‘_min1’ shadows a previous local [-Wshadow] include/linux/kernel.h:751:12: warning: declaration of ‘_min2’ shadows a previous local [-Wshadow] kernel/sched/sched.h:308:43: warning: declaration of ‘down’ shadows a global declaration [-Wshadow] kernel/sched/sched.h:308:60: warning: declaration of ‘up’ shadows a global declaration [-Wshadow] kernel/sched/auto_group.h:44:55: warning: declaration of ‘init_task’ shadows a global declaration [-Wshadow] kernel/sched/core.c:635:20: warning: declaration of ‘down’ shadows a global declaration [-Wshadow] kernel/sched/core.c:635:37: warning: declaration of ‘up’ shadows a global declaration [-Wshadow]

and yes, I'd say most of these are signatures of sloppy macros and sloppy variable names - but it would be a ton of work to eliminate these warnings.

Thanks,

Ingo

==============>

 Makefile | 3 +++
 1 file changed, 3 insertions(+)

index 7b3ecdcdc6c1..14b0ce82f2b0 100644
@@ -776,6 +776,9 @@ KBUILD_CFLAGS   += $(call cc-option,-Werror=date-time)
 # use the deterministic mode of AR if available
 KBUILD_ARFLAGS := $(call ar-option,D)
 
+# enforce correct pointer usage
+KBUILD_CFLAGS	+= $(call cc-option,-Wshadow)
+
 # check for 'asm goto'
 ifeq ($(shell $(CONFIG_SHELL) $(srctree)/scripts/gcc-goto.sh $(CC)), y)
 	KBUILD_CFLAGS += -DCC_HAVE_ASM_GOTO

Sure we can go add those. I have a flight scheduled early next month, I'll try and have a go at adding all the fetch_$op variants to all arches.

Heh, what else can we expect from global functions named up() and down() in a millions-lines C project :-)

Yeah that's what I was afraid of.

Thanks for trying it though!