[RFC patch 0/5] hrtimers: Add deferrable mode

[RFC patch 0/5] hrtimers: Add deferrable mode

[Thomas Gleixner]

Deferrable timers are beneficial for power saving. They behave like
standard timers except that their expiry can be delayed up to the
expiry of the next non deferred timer. That prevents them from waking
up cpus from deep idle periods.

Right now deferrable timers are only available in the timer wheel and
therefor not available to user space applications. Though user space
applications want to optimize their timer usage for power consumption
as well, so exposing deferred timers via the existing timer APIs is
required.

There is no way to bring back timer wheel timers to user space
interfaces as they would reintroduce the problems of CLOCK_REALTIME
and clock setting again and add quite some mess to the various
interfaces.

So the proper solution is to extend the hrtimer functionality with
a deferrable mode.

The following series adds the functionality and makes it accessible
via the clock_nanosleep, timer_settime and timerfd_settime syscalls.

This series is RFC and largely untested.

Thanks,

	tglx

[RFC patch 1/5] hrtimer: Always check for HRTIMER_MODE_REL

[Thomas Gleixner]

[-- Attachment #1: hrtimer-check-for-not-relative.patch --]
[-- Type: text/plain, Size: 1030 bytes --]

We have not just HRTIMER_MODE_REL and HRTIMER_MODE_ABS, so a direct
check for mode == HRTIMER_MODE_ABS is not sufficient.

Always check for the HRTIMER_MODE_REL bit.

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 kernel/hrtimer.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

Index: tip/kernel/hrtimer.c
===================================================================
--- tip.orig/kernel/hrtimer.c
+++ tip/kernel/hrtimer.c
@@ -1186,7 +1186,7 @@ static void __hrtimer_init(struct hrtime
 
 	cpu_base = &__raw_get_cpu_var(hrtimer_bases);
 
-	if (clock_id == CLOCK_REALTIME && mode != HRTIMER_MODE_ABS)
+	if (clock_id == CLOCK_REALTIME && (mode & HRTIMER_MODE_REL))
 		clock_id = CLOCK_MONOTONIC;
 
 	base = hrtimer_clockid_to_base(clock_id);
@@ -1620,7 +1620,7 @@ long hrtimer_nanosleep(struct timespec *
 		goto out;
 
 	/* Absolute timers do not update the rmtp value and restart: */
-	if (mode == HRTIMER_MODE_ABS) {
+	if (!(mode & HRTIMER_MODE_REL)) {
 		ret = -ERESTARTNOHAND;
 		goto out;
 	}

[RFC patch 3/5] hrtimer: Add support for deferrable hrtimers

[Thomas Gleixner]

[-- Attachment #1: hrtimer-add-support-for-deferrable-timer-into-the-hrtimer.patch --]
[-- Type: text/plain, Size: 7536 bytes --]

Deferrable timers have a relaxed expiry mode. The timers are not
guaranteed to expire at the programmed expiry time. They are always
batched with the expiry of non deferrrable timers. If the system goes
idle non deferrable timers are not taken into account for the
calculation of the next timer expiry. This helps for power saving as
the deferrable timers do not wake an idle system.

So far we have only support for deferrable timers for the timer wheel.
User space applications want to optimize their timer usage for power
consumption as well, but the user space interfaces are based on
hrtimers.

There is no way to bring back timer wheel timers to user space
interfaces as they would reintroduce the problems of CLOCK_REALTIME
and clock setting again and add quite some mess to the various
interfaces.

Add deferrable hrtimer support instead. The deferrable hrtimers are
stored in separate hrtimer bases which have the same underlying rules
as the non deferrable standard bases. The deferrable mode is selected
by the new HRTIMER_MODE_DEFERRABLE flag, which is ored on
HRTIMER_MODE_REL/ABS.

The new deferrable bases are not taken into account when the
underlying clock event device is programmed in high resolution mode
and they are not accounted for when the system retrieves the next
expiring timer for an extended idle sleep.

There is no impact on the non deferred hrtimers by the deferred ones
aside of a slightly larger memory footprint.

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

---
 include/linux/hrtimer.h |    8 ++++-
 kernel/hrtimer.c        |   72 ++++++++++++++++++++++++++++++++++++++++++------
 2 files changed, 69 insertions(+), 11 deletions(-)

Index: tip/include/linux/hrtimer.h
===================================================================
--- tip.orig/include/linux/hrtimer.h
+++ tip/include/linux/hrtimer.h
@@ -36,6 +36,7 @@ enum hrtimer_mode {
 	HRTIMER_MODE_PINNED = 0x02,	/* Timer is bound to CPU */
 	HRTIMER_MODE_ABS_PINNED = 0x02,
 	HRTIMER_MODE_REL_PINNED = 0x03,
+	HRTIMER_MODE_DEFERRABLE = 0x04, /* Timer is deferrable */
 };
 
 /*
@@ -158,7 +159,8 @@ enum  hrtimer_base_type {
 	HRTIMER_BASE_REALTIME,
 	HRTIMER_BASE_BOOTTIME,
 	HRTIMER_BASE_TAI,
-	HRTIMER_MAX_CLOCK_BASES,
+	HRTIMER_MAX_STD_BASES,
+	HRTIMER_MAX_CLOCK_BASES = 2 * HRTIMER_MAX_STD_BASES,
 };
 
 /*
@@ -175,7 +177,9 @@ enum  hrtimer_base_type {
  * @nr_retries:		Total number of hrtimer interrupt retries
  * @nr_hangs:		Total number of hrtimer interrupt hangs
  * @max_hang_time:	Maximum time spent in hrtimer_interrupt
- * @clock_base:		array of clock bases for this cpu
+ * @clock_base:		array of clock bases for this cpu. The array size is
+ *			twice the MAX_STD_BASES size. The second part is
+ *			a duplication of the first for deferrable timers.
  */
 struct hrtimer_cpu_base {
 	raw_spinlock_t			lock;
Index: tip/kernel/hrtimer.c
===================================================================
--- tip.orig/kernel/hrtimer.c
+++ tip/kernel/hrtimer.c
@@ -92,6 +92,30 @@ DEFINE_PER_CPU(struct hrtimer_cpu_base,
 			.get_time = &ktime_get_clocktai,
 			.resolution = KTIME_LOW_RES,
 		},
+		{
+			.index = HRTIMER_BASE_MONOTONIC + HRTIMER_MAX_STD_BASES,
+			.clockid = CLOCK_MONOTONIC,
+			.get_time = &ktime_get,
+			.resolution = KTIME_LOW_RES,
+		},
+		{
+			.index = HRTIMER_BASE_REALTIME + HRTIMER_MAX_STD_BASES,
+			.clockid = CLOCK_REALTIME,
+			.get_time = &ktime_get_real,
+			.resolution = KTIME_LOW_RES,
+		},
+		{
+			.index = HRTIMER_BASE_BOOTTIME + HRTIMER_MAX_STD_BASES,
+			.clockid = CLOCK_BOOTTIME,
+			.get_time = &ktime_get_boottime,
+			.resolution = KTIME_LOW_RES,
+		},
+		{
+			.index = HRTIMER_BASE_TAI + HRTIMER_MAX_STD_BASES,
+			.clockid = CLOCK_TAI,
+			.get_time = &ktime_get_clocktai,
+			.resolution = KTIME_LOW_RES,
+		},
 	}
 };
 
@@ -194,7 +218,9 @@ hrtimer_check_target(struct hrtimer *tim
 #ifdef CONFIG_HIGH_RES_TIMERS
 	ktime_t expires;
 
-	if (!new_base->cpu_base->hres_active)
+	/* We do not touch hardware for deferrable timers */
+	if (!new_base->cpu_base->hres_active ||
+	    new_base->index >= HRTIMER_MAX_STD_BASES)
 		return 0;
 
 	expires = ktime_sub(hrtimer_get_expires(timer), new_base->offset);
@@ -556,7 +582,7 @@ hrtimer_force_reprogram(struct hrtimer_c
 
 	expires_next.tv64 = KTIME_MAX;
 
-	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++, base++) {
+	for (i = 0; i < HRTIMER_MAX_STD_BASES; i++, base++) {
 		struct hrtimer *timer;
 		struct timerqueue_node *next;
 
@@ -615,6 +641,13 @@ static int hrtimer_reprogram(struct hrti
 		return 0;
 
 	/*
+	 * Deferrable timers are not touching the underlying
+	 * hardware.
+	 */
+	if (base->index >= HRTIMER_MAX_STD_BASES)
+		return 0;
+
+	/*
 	 * CLOCK_REALTIME timer might be requested with an absolute
 	 * expiry time which is less than base->offset. Nothing wrong
 	 * about that, just avoid to call into the tick code, which
@@ -924,7 +957,10 @@ static void __remove_hrtimer(struct hrti
 
 			expires = ktime_sub(hrtimer_get_expires(timer),
 					    base->offset);
-			if (base->cpu_base->expires_next.tv64 == expires.tv64)
+
+			/* We only care about non deferrable timers here */
+			if (base->index < HRTIMER_MAX_STD_BASES &&
+			    base->cpu_base->expires_next.tv64 == expires.tv64)
 				hrtimer_force_reprogram(base->cpu_base, 1);
 		}
 #endif
@@ -1152,7 +1188,8 @@ ktime_t hrtimer_get_next_event(void)
 	raw_spin_lock_irqsave(&cpu_base->lock, flags);
 
 	if (!hrtimer_hres_active()) {
-		for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++, base++) {
+		/* We only care about non deferrable timers here */
+		for (i = 0; i < HRTIMER_MAX_STD_BASES; i++, base++) {
 			struct hrtimer *timer;
 			struct timerqueue_node *next;
 
@@ -1190,6 +1227,9 @@ static void __hrtimer_init(struct hrtime
 		clock_id = CLOCK_MONOTONIC;
 
 	base = hrtimer_clockid_to_base(clock_id);
+	if (mode & HRTIMER_MODE_DEFERRABLE)
+		base += HRTIMER_MAX_STD_BASES;
+
 	timer->base = &cpu_base->clock_base[base];
 	timerqueue_init(&timer->node);
 
@@ -1342,8 +1382,14 @@ retry:
 						    base->offset);
 				if (expires.tv64 < 0)
 					expires.tv64 = KTIME_MAX;
-				if (expires.tv64 < expires_next.tv64)
-					expires_next = expires;
+				if (expires.tv64 < expires_next.tv64) {
+					/*
+					 * We do not take deferrable timers
+					 * into account here:
+					 */
+					if (idx < HRTIMER_MAX_STD_BASES)
+						expires_next = expires;
+				}
 				break;
 			}
 
@@ -1584,14 +1630,20 @@ static int update_rmtp(struct hrtimer *t
 	return 1;
 }
 
+#define CLOCKID_DEFERRABLE	0x8000
+
 long __sched hrtimer_nanosleep_restart(struct restart_block *restart)
 {
-	struct hrtimer_sleeper t;
+	clockid_t clockid = restart->nanosleep.clockid & ~CLOCKID_DEFERRABLE;
+	enum hrtimer_mode mode = HRTIMER_MODE_ABS;
 	struct timespec __user  *rmtp;
+	struct hrtimer_sleeper t;
 	int ret = 0;
 
-	hrtimer_init_on_stack(&t.timer, restart->nanosleep.clockid,
-				HRTIMER_MODE_ABS);
+	if (restart->nanosleep.clockid & CLOCKID_DEFERRABLE)
+		mode |= HRTIMER_MODE_DEFERRABLE;
+
+	hrtimer_init_on_stack(&t.timer, clockid, mode);
 	hrtimer_set_expires_tv64(&t.timer, restart->nanosleep.expires);
 
 	if (do_nanosleep(&t, HRTIMER_MODE_ABS))
@@ -1643,6 +1695,8 @@ long hrtimer_nanosleep(struct timespec *
 	restart = &current_thread_info()->restart_block;
 	restart->fn = hrtimer_nanosleep_restart;
 	restart->nanosleep.clockid = t.timer.base->clockid;
+	if (mode & HRTIMER_MODE_DEFERRABLE)
+		restart->nanosleep.clockid |= CLOCKID_DEFERRABLE;
 	restart->nanosleep.rmtp = rmtp;
 	restart->nanosleep.expires = hrtimer_get_expires_tv64(&t.timer);
 

[RFC patch 2/5] hrtimer: Make use of the active bases bitfield

[Thomas Gleixner]

[-- Attachment #1: hrtimer-use-active-bases.patch --]
[-- Type: text/plain, Size: 2102 bytes --]

Instead of looping through all bases, find the active ones via the
cpu_base->active_bases bit field.

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 kernel/hrtimer.c |   33 +++++++++++++++++++++------------
 1 file changed, 21 insertions(+), 12 deletions(-)

Index: tip/kernel/hrtimer.c
===================================================================
--- tip.orig/kernel/hrtimer.c
+++ tip/kernel/hrtimer.c
@@ -1284,7 +1284,8 @@ void hrtimer_interrupt(struct clock_even
 {
 	struct hrtimer_cpu_base *cpu_base = &__get_cpu_var(hrtimer_bases);
 	ktime_t expires_next, now, entry_time, delta;
-	int i, retries = 0;
+	unsigned long bases;
+	int retries = 0;
 
 	BUG_ON(!cpu_base->hres_active);
 	cpu_base->nr_events++;
@@ -1302,16 +1303,18 @@ retry:
 	 * this CPU.
 	 */
 	cpu_base->expires_next.tv64 = KTIME_MAX;
+	bases = cpu_base->active_bases;
 
-	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++) {
+	while (bases) {
 		struct hrtimer_clock_base *base;
 		struct timerqueue_node *node;
 		ktime_t basenow;
+		int idx;
 
-		if (!(cpu_base->active_bases & (1 << i)))
-			continue;
+		idx = __ffs(bases);
+		bases &= ~(1 << idx);
 
-		base = cpu_base->clock_base + i;
+		base = cpu_base->clock_base + idx;
 		basenow = ktime_add(now, base->offset);
 
 		while ((node = timerqueue_getnext(&base->active))) {
@@ -1479,18 +1482,24 @@ void hrtimer_run_pending(void)
  */
 void hrtimer_run_queues(void)
 {
-	struct timerqueue_node *node;
 	struct hrtimer_cpu_base *cpu_base = &__get_cpu_var(hrtimer_bases);
-	struct hrtimer_clock_base *base;
-	int index, gettime = 1;
+	unsigned long bases;
+	int gettime = 1;
 
 	if (hrtimer_hres_active())
 		return;
 
-	for (index = 0; index < HRTIMER_MAX_CLOCK_BASES; index++) {
-		base = &cpu_base->clock_base[index];
-		if (!timerqueue_getnext(&base->active))
-			continue;
+	bases = cpu_base->active_bases;
+
+	while (bases) {
+		struct hrtimer_clock_base *base;
+		struct timerqueue_node *node;
+		int idx;
+
+		idx = __ffs(bases);
+		bases &= ~(1 << idx);
+
+		base = &cpu_base->clock_base[idx];
 
 		if (gettime) {
 			hrtimer_get_softirq_time(cpu_base);

[RFC patch 4/5] posix-timers: Expose deferrable mode to user space

[Thomas Gleixner]

[-- Attachment #1: posix-timer-wire-up-deferrables.patch --]
[-- Type: text/plain, Size: 2577 bytes --]

Expose the deferrable timer mode to user space by adding a new
TIMER_IS_DEFERRABLE flag.

The deferrable mode is available for the syscalls clock_nanosleep()
and timer_settime(). For both syscalls TIMER_IS_DEFERRABLE is handed
in via the 'flags' argument. TIMER_ABSTIME and TIMER_IS_DEFERRABLE can
be ored together.

If a timer is started with this flag, the expiry of the timer is
relaxed. The timer is guaranteed to not expire before the given expiry
time, but the expiry can be delayed to the point where a non
deferrable timer expires. Deferred timers are not waking up a cpu from
a deep idle period.

Applications using the TIMER_IS_DEFERRABLE flag work on older kernels
as well, but the timers won't have the deferrable functionality.

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Cc: Michael Kerrisk <mtk.manpages@gmail.com>
---
 include/uapi/linux/time.h |    4 ++++
 kernel/posix-timers.c     |   10 +++++++---
 2 files changed, 11 insertions(+), 3 deletions(-)

Index: tip/include/uapi/linux/time.h
===================================================================
--- tip.orig/include/uapi/linux/time.h
+++ tip/include/uapi/linux/time.h
@@ -63,7 +63,11 @@ struct itimerval {
 
 /*
  * The various flags for setting POSIX.1b interval timers:
+ *
+ * We keep that in sync with the TFD_TIMER_ flags
  */
 #define TIMER_ABSTIME			0x01
+/* Reserved for TFD_ONLY flag		0x02 */
+#define TIMER_IS_DEFERRABLE		0x04
 
 #endif /* _UAPI_LINUX_TIME_H */
Index: tip/kernel/posix-timers.c
===================================================================
--- tip.orig/kernel/posix-timers.c
+++ tip/kernel/posix-timers.c
@@ -846,6 +846,7 @@ common_timer_set(struct k_itimer *timr,
 		return 0;
 
 	mode = flags & TIMER_ABSTIME ? HRTIMER_MODE_ABS : HRTIMER_MODE_REL;
+	mode |= flags & TIMER_DEFERRABLE ? HRTIMER_MODE_DEFERRABLE : 0;
 	hrtimer_init(&timr->it.real.timer, timr->it_clock, mode);
 	timr->it.real.timer.function = posix_timer_fn;
 
@@ -1079,9 +1080,12 @@ SYSCALL_DEFINE2(clock_getres, const cloc
 static int common_nsleep(const clockid_t which_clock, int flags,
 			 struct timespec *tsave, struct timespec __user *rmtp)
 {
-	return hrtimer_nanosleep(tsave, rmtp, flags & TIMER_ABSTIME ?
-				 HRTIMER_MODE_ABS : HRTIMER_MODE_REL,
-				 which_clock);
+	enum hrtimer_mode mode;
+
+	mode = flags & TIMER_ABSTIME ? HRTIMER_MODE_ABS : HRTIMER_MODE_REL;
+	mode |= flags & TIMER_DEFERRABLE ? HRTIMER_MODE_DEFERRABLE : 0;
+
+	return hrtimer_nanosleep(tsave, rmtp, mode, which_clock);
 }
 
 SYSCALL_DEFINE4(clock_nanosleep, const clockid_t, which_clock, int, flags,

[RFC patch 5/5] timerfd: Expose deferrable mode to user space

[Thomas Gleixner]

[-- Attachment #1: timerfd-wire-up-deferrables.patch --]
[-- Type: text/plain, Size: 1739 bytes --]

Expose the deferrable timer mode to user space by adding a new
TDF_TIMER_DEFERRABLE flag.

The deferrable mode is available through the syscall timerfd_settime()
by handing in TDF_TIMER_IS_DEFERRABLE via the 'flags' argument.
TFD_TIMER_IS_DEFERRABLE and the other TFD_TIMER_ flags can be ored
together.

If a timer is started with this flag, the expiry of the timer is
relaxed. The timer is guaranteed to not expire before the given expiry
time, but the expiry can be delayed to the point where a non
deferrable timer expires. Deferred timers are not waking up a cpu from
a deep idle period.

Applications using the TFD_TIMER_IS_DEFERRABLE flag work on older kernels
as well, but the timers won't have the deferrable functionality.

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Cc: Michael Kerrisk <mtk.manpages@gmail.com>
---
 fs/timerfd.c            |    1 +
 include/linux/timerfd.h |    1 +
 2 files changed, 2 insertions(+)

Index: tip/fs/timerfd.c
===================================================================
--- tip.orig/fs/timerfd.c
+++ tip/fs/timerfd.c
@@ -166,6 +166,7 @@ static int timerfd_setup(struct timerfd_
 
 	htmode = (flags & TFD_TIMER_ABSTIME) ?
 		HRTIMER_MODE_ABS: HRTIMER_MODE_REL;
+	htmode |= (flags & TFD_TIMER_DEFERRABLE) ? HRTIMER_MODE_DEFERRABLE : 0;
 
 	texp = timespec_to_ktime(ktmr->it_value);
 	ctx->expired = 0;
Index: tip/include/linux/timerfd.h
===================================================================
--- tip.orig/include/linux/timerfd.h
+++ tip/include/linux/timerfd.h
@@ -20,6 +20,7 @@
  */
 #define TFD_TIMER_ABSTIME (1 << 0)
 #define TFD_TIMER_CANCEL_ON_SET (1 << 1)
+#define TFD_TIMER_DEFERRABLE (2 << 1)
 #define TFD_CLOEXEC O_CLOEXEC
 #define TFD_NONBLOCK O_NONBLOCK
 

Re: [RFC patch 5/5] timerfd: Expose deferrable mode to user space

[Richard Cochran]

On Fri, Feb 21, 2014 at 05:56:18PM -0000, Thomas Gleixner wrote:
> Expose the deferrable timer mode to user space by adding a new
> TDF_TIMER_DEFERRABLE flag.
> 
> The deferrable mode is available through the syscall timerfd_settime()
> by handing in TDF_TIMER_IS_DEFERRABLE via the 'flags' argument.
> TFD_TIMER_IS_DEFERRABLE and the other TFD_TIMER_ flags can be ored
> together.

s/TDF_/TFD_/g

Thanks,
Richard

Re: [RFC patch 1/5] hrtimer: Always check for HRTIMER_MODE_REL

[Peter Zijlstra]

On Fri, Feb 21, 2014 at 05:56:15PM -0000, Thomas Gleixner wrote:
> We have not just HRTIMER_MODE_REL and HRTIMER_MODE_ABS, so a direct
> check for mode == HRTIMER_MODE_ABS is not sufficient.
> 
> Always check for the HRTIMER_MODE_REL bit.

This seems to come from having changed hrtimer_mode from a value field
to a bit field with the addition of PINNED.

But yeah; this certainly fixes these two sites. Ideally we'd to
something better to avoid making the same mistake again later. But the
only thing I can come up with is lots of work.

Acked-by: Peter Zijlstra <peterz@infradead.org>

Re: [RFC patch 2/5] hrtimer: Make use of the active bases bitfield

[Peter Zijlstra]

On Fri, Feb 21, 2014 at 05:56:16PM -0000, Thomas Gleixner wrote:
> -	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++) {
> +	while (bases) {
>  		struct hrtimer_clock_base *base;
>  		struct timerqueue_node *node;
>  		ktime_t basenow;
> +		int idx;
>  
> -		if (!(cpu_base->active_bases & (1 << i)))
> -			continue;
> +		idx = __ffs(bases);
> +		bases &= ~(1 << idx);
>  
> -		base = cpu_base->clock_base + i;
> +		base = cpu_base->clock_base + idx;
>  		basenow = ktime_add(now, base->offset);
>  
>  		while ((node = timerqueue_getnext(&base->active))) {

That's crappy for archs that end up using the generic __ffs().

The simply loop we had isn't too bad, why change this?

Re: [RFC patch 0/5] hrtimers: Add deferrable mode

[Andy Lutomirski]

On 02/21/2014 09:56 AM, Thomas Gleixner wrote:
> Deferrable timers are beneficial for power saving. They behave like
> standard timers except that their expiry can be delayed up to the
> expiry of the next non deferred timer. That prevents them from waking
> up cpus from deep idle periods.

What does this accomplish that can't be done with hrtimers with enormous
slack?

--Andy