Skip to contentSkip to conversation

cpuidle: Use nanoseconds as the unit of time

RFC PATCH In review Rafael J. Wysocki 3 participants 3 messages Sep 5, 2019 – Sep 20, 2019

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 cpuidle: Use nanoseconds as the unit of time

From: Rafael J. Wysocki <[email protected]>

Currently, the cpuidle subsystem uses microseconds as the unit of time which (among other things) causes the idle loop to incur some integer division overhead for no clear benefit.

In order to allow cpuidle to measure time in nanoseconds, add two additional fields, exit_latency_ns and target_residency_ns, to represent the exit latency and target residency of an idle state in nanoseconds, respectively, to struct cpuidle_state_usage and initialize them with the help of the corresponding valuse in microseconds provided by drivers. In addition to that, change cpuidle_governor_latency_req() to return the idle state exit latency constraint in nanoseconds.

With that, meeasure idle state residency (last_residency_ns in struct cpuidle_device and time_ns in struct cpuidle_driver) in nanoseconds and update the cpuidle core and governors accordingly.

However, the menu governor still computes typical intervals in microseconds to avoid integer overflows.

---

Again, not tested yet, posted for feedback mostly, applies on top of

https://patchwork.kernel.org/patch/11129867/

The patch is rather large, but mostly straightforward. There is a rather ugly piece in the menu governor that first computes the expected idle duration in ns and then converts it to us just in order to compute the typical interval value, and in case that is less than the original expected idle duration value, converts it to ns again. However, if there is a nicer way to do it, I haven't found it so far.

---
 drivers/cpuidle/cpuidle.c            |   36 +++++------
 drivers/cpuidle/driver.c             |   29 ++++++---
 drivers/cpuidle/governor.c           |    7 +-
 drivers/cpuidle/governors/haltpoll.c |    7 --
 drivers/cpuidle/governors/ladder.c   |   25 ++++----
 drivers/cpuidle/governors/menu.c     |  106 +++++++++++++++++------------------
 drivers/cpuidle/governors/teo.c      |   72 +++++++++++------------
 drivers/cpuidle/sysfs.c              |    8 ++
 include/linux/cpuidle.h              |    8 +-
 kernel/sched/idle.c                  |    2 
 10 files changed, 158 insertions(+), 142 deletions(-)
include/linux/cpuidle.h +5 -3
Index: linux-pm/include/linux/cpuidle.h
===================================================================
@@ -35,7 +35,7 @@ struct cpuidle_driver;
 struct cpuidle_state_usage {
 	unsigned long long	disable;
 	unsigned long long	usage;
-	unsigned long long	time; /* in US */
+	u64			time_ns;
 	unsigned long long	above; /* Number of times it's been too deep */
 	unsigned long long	below; /* Number of times it's been too shallow */
 #ifdef CONFIG_SUSPEND
@@ -48,6 +48,8 @@ struct cpuidle_state {
 	char		name[CPUIDLE_NAME_LEN];
 	char		desc[CPUIDLE_DESC_LEN];
 
+	u64		exit_latency_ns;
+	u64		target_residency_ns;
 	unsigned int	flags;
 	unsigned int	exit_latency; /* in US */
 	int		power_usage; /* in mW */
@@ -89,7 +91,7 @@ struct cpuidle_device {
 	ktime_t			next_hrtimer;
 
 	int			last_state_idx;
-	int			last_residency;
+	u64			last_residency_ns;
 	u64			poll_limit_ns;
 	struct cpuidle_state_usage	states_usage[CPUIDLE_STATE_MAX];
 	struct cpuidle_state_kobj *kobjs[CPUIDLE_STATE_MAX];
@@ -260,7 +262,7 @@ struct cpuidle_governor {
 
 #ifdef CONFIG_CPU_IDLE
 extern int cpuidle_register_governor(struct cpuidle_governor *gov);
-extern int cpuidle_governor_latency_req(unsigned int cpu);
+extern s64 cpuidle_governor_latency_req(unsigned int cpu);
 #else
 static inline int cpuidle_register_governor(struct cpuidle_governor *gov)
 {return 0;}
drivers/cpuidle/driver.c +20 -9
Index: linux-pm/drivers/cpuidle/driver.c
===================================================================
@@ -166,16 +166,27 @@ static void __cpuidle_driver_init(struct
 	if (!drv->cpumask)
 		drv->cpumask = (struct cpumask *)cpu_possible_mask;
 
-	/*
-	 * Look for the timer stop flag in the different states, so that we know
-	 * if the broadcast timer has to be set up.  The loop is in the reverse
-	 * order, because usually one of the deeper states have this flag set.
-	 */
-	for (i = drv->state_count - 1; i >= 0 ; i--) {
-		if (drv->states[i].flags & CPUIDLE_FLAG_TIMER_STOP) {
+	for (i = 0; i < drv->state_count; i++) {
+		struct cpuidle_state *s = &drv->states[i];
+
+		/*
+		 * Look for the timer stop flag in the different states and if
+		 * it is found, indicate that the broadcast timer has to be set
+		 * up.
+		 */
+		if (s->flags & CPUIDLE_FLAG_TIMER_STOP)
 			drv->bctimer = 1;
-			break;
-		}
+
+		/*
+		 * The core will use the target residency and exit latency
+		 * values in nanoseconds, but allow drivers to provide them in
+		 * microseconds too.
+		 */
+		if (s->target_residency > 0)
+			s->target_residency_ns = s->target_residency * NSEC_PER_USEC;
+
+		if (s->exit_latency > 0)
+			s->exit_latency_ns = s->exit_latency * NSEC_PER_USEC;
 	}
 }
 
drivers/cpuidle/cpuidle.c +17 -19
Index: linux-pm/drivers/cpuidle/cpuidle.c
===================================================================
@@ -75,24 +75,24 @@ int cpuidle_play_dead(void)
 
 static int find_deepest_state(struct cpuidle_driver *drv,
 			      struct cpuidle_device *dev,
-			      unsigned int max_latency,
+			      u64 max_latency_ns,
 			      unsigned int forbidden_flags,
 			      bool s2idle)
 {
-	unsigned int latency_req = 0;
+	u64 latency_req = 0;
 	int i, ret = 0;
 
 	for (i = 1; i < drv->state_count; i++) {
 		struct cpuidle_state *s = &drv->states[i];
 
 		if (dev->states_usage[i].disable ||
-		    s->exit_latency <= latency_req ||
-		    s->exit_latency > max_latency ||
+		    s->exit_latency_ns <= latency_req ||
+		    s->exit_latency_ns > max_latency_ns ||
 		    (s->flags & forbidden_flags) ||
 		    (s2idle && !s->enter_s2idle))
 			continue;
 
-		latency_req = s->exit_latency;
+		latency_req = s->exit_latency_ns;
 		ret = i;
 	}
 	return ret;
@@ -124,7 +124,7 @@ void cpuidle_use_deepest_state(bool enab
 int cpuidle_find_deepest_state(struct cpuidle_driver *drv,
 			       struct cpuidle_device *dev)
 {
-	return find_deepest_state(drv, dev, UINT_MAX, 0, false);
+	return find_deepest_state(drv, dev, U64_MAX, 0, false);
 }
 
 #ifdef CONFIG_SUSPEND
@@ -180,7 +180,7 @@ int cpuidle_enter_s2idle(struct cpuidle_
 	 * that interrupts won't be enabled when it exits and allows the tick to
 	 * be frozen safely.
 	 */
-	index = find_deepest_state(drv, dev, UINT_MAX, 0, true);
+	index = find_deepest_state(drv, dev, U64_MAX, 0, true);
 	if (index > 0)
 		enter_s2idle_proper(drv, dev, index);
 
@@ -209,7 +209,7 @@ int cpuidle_enter_state(struct cpuidle_d
 	 * CPU as a broadcast timer, this call may fail if it is not available.
 	 */
 	if (broadcast && tick_broadcast_enter()) {
-		index = find_deepest_state(drv, dev, target_state->exit_latency,
+		index = find_deepest_state(drv, dev, target_state->exit_latency_ns,
 					   CPUIDLE_FLAG_TIMER_STOP, false);
 		if (index < 0) {
 			default_idle_call();
@@ -247,7 +247,7 @@ int cpuidle_enter_state(struct cpuidle_d
 		local_irq_enable();
 
 	if (entered_state >= 0) {
-		s64 diff, delay = drv->states[entered_state].exit_latency;
+		s64 diff, delay = drv->states[entered_state].exit_latency_ns;
 		int i;
 
 		/*
@@ -255,15 +255,13 @@ int cpuidle_enter_state(struct cpuidle_d
 		 * This can be moved to within driver enter routine,
 		 * but that results in multiple copies of same code.
 		 */
-		diff = ktime_us_delta(time_end, time_start);
-		if (diff > INT_MAX)
-			diff = INT_MAX;
+		diff = ktime_sub(time_end, time_start);
 
-		dev->last_residency = (int)diff;
-		dev->states_usage[entered_state].time += dev->last_residency;
+		dev->last_residency_ns = diff;
+		dev->states_usage[entered_state].time_ns += diff;
 		dev->states_usage[entered_state].usage++;
 
-		if (diff < drv->states[entered_state].target_residency) {
+		if (diff < drv->states[entered_state].target_residency_ns) {
 			for (i = entered_state - 1; i >= 0; i--) {
 				if (dev->states_usage[i].disable)
 					continue;
@@ -281,14 +279,14 @@ int cpuidle_enter_state(struct cpuidle_d
 				 * Update if a deeper state would have been a
 				 * better match for the observed idle duration.
 				 */
-				if (diff - delay >= drv->states[i].target_residency)
+				if (diff - delay >= drv->states[i].target_residency_ns)
 					dev->states_usage[entered_state].below++;
 
 				break;
 			}
 		}
 	} else {
-		dev->last_residency = 0;
+		dev->last_residency_ns = 0;
 	}
 
 	return entered_state;
@@ -381,7 +379,7 @@ u64 cpuidle_poll_time(struct cpuidle_dri
 		if (dev->states_usage[i].disable)
 			continue;
 
-		limit_ns = (u64)drv->states[i].target_residency * NSEC_PER_USEC;
+		limit_ns = (u64)drv->states[i].target_residency_ns;
 	}
 
 	dev->poll_limit_ns = limit_ns;
@@ -552,7 +550,7 @@ static void __cpuidle_unregister_device(
 static void __cpuidle_device_init(struct cpuidle_device *dev)
 {
 	memset(dev->states_usage, 0, sizeof(dev->states_usage));
-	dev->last_residency = 0;
+	dev->last_residency_ns = 0;
 	dev->next_hrtimer = 0;
 }
 
drivers/cpuidle/sysfs.c +7 -1
Index: linux-pm/drivers/cpuidle/sysfs.c
===================================================================
@@ -277,13 +277,19 @@ define_show_state_function(exit_latency)
 define_show_state_function(target_residency)
 define_show_state_function(power_usage)
 define_show_state_ull_function(usage)
-define_show_state_ull_function(time)
 define_show_state_str_function(name)
 define_show_state_str_function(desc)
 define_show_state_ull_function(disable)
 define_show_state_ull_function(above)
 define_show_state_ull_function(below)
 
+static ssize_t show_state_time(struct cpuidle_state *state,
+			       struct cpuidle_state_usage *state_usage,
+			       char *buf)
+{
+	return sprintf(buf, "%llu\n", ktime_to_us(state_usage->time_ns));
+}
+
 static ssize_t store_state_disable(struct cpuidle_state *state,
 				   struct cpuidle_state_usage *state_usage,
 				   const char *buf, size_t size)
drivers/cpuidle/governor.c +5 -2
Index: linux-pm/drivers/cpuidle/governor.c
===================================================================
@@ -106,11 +106,14 @@ int cpuidle_register_governor(struct cpu
  * cpuidle_governor_latency_req - Compute a latency constraint for CPU
  * @cpu: Target CPU
  */
-int cpuidle_governor_latency_req(unsigned int cpu)
+s64 cpuidle_governor_latency_req(unsigned int cpu)
 {
 	int global_req = pm_qos_request(PM_QOS_CPU_DMA_LATENCY);
 	struct device *device = get_cpu_device(cpu);
 	int device_req = dev_pm_qos_raw_resume_latency(device);
 
-	return device_req < global_req ? device_req : global_req;
+	if (device_req < global_req)
+		device_req = global_req;
+
+	return (s64)device_req * NSEC_PER_USEC;
 }
drivers/cpuidle/governors/ladder.c +13 -12
Index: linux-pm/drivers/cpuidle/governors/ladder.c
===================================================================
@@ -27,8 +27,8 @@ struct ladder_device_state {
 	struct {
 		u32 promotion_count;
 		u32 demotion_count;
-		u32 promotion_time;
-		u32 demotion_time;
+		u64 promotion_time_ns;
+		u64 demotion_time_ns;
 	} threshold;
 	struct {
 		int promotion_count;
@@ -68,9 +68,10 @@ static int ladder_select_state(struct cp
 {
 	struct ladder_device *ldev = this_cpu_ptr(&ladder_devices);
 	struct ladder_device_state *last_state;
-	int last_residency, last_idx = dev->last_state_idx;
+	int last_idx = dev->last_state_idx;
 	int first_idx = drv->states[0].flags & CPUIDLE_FLAG_POLLING ? 1 : 0;
-	int latency_req = cpuidle_governor_latency_req(dev->cpu);
+	s64 latency_req = cpuidle_governor_latency_req(dev->cpu);
+	s64 last_residency;
 
 	/* Special case when user has set very strict latency requirement */
 	if (unlikely(latency_req == 0)) {
@@ -80,13 +81,13 @@ static int ladder_select_state(struct cp
 
 	last_state = &ldev->states[last_idx];
 
-	last_residency = dev->last_residency - drv->states[last_idx].exit_latency;
+	last_residency = dev->last_residency_ns - drv->states[last_idx].exit_latency_ns;
 
 	/* consider promotion */
 	if (last_idx < drv->state_count - 1 &&
 	    !dev->states_usage[last_idx + 1].disable &&
-	    last_residency > last_state->threshold.promotion_time &&
-	    drv->states[last_idx + 1].exit_latency <= latency_req) {
+	    last_residency > last_state->threshold.promotion_time_ns &&
+	    drv->states[last_idx + 1].exit_latency_ns <= latency_req) {
 		last_state->stats.promotion_count++;
 		last_state->stats.demotion_count = 0;
 		if (last_state->stats.promotion_count >= last_state->threshold.promotion_count) {
@@ -98,11 +99,11 @@ static int ladder_select_state(struct cp
 	/* consider demotion */
 	if (last_idx > first_idx &&
 	    (dev->states_usage[last_idx].disable ||
-	    drv->states[last_idx].exit_latency > latency_req)) {
+	    drv->states[last_idx].exit_latency_ns > latency_req)) {
 		int i;
 
 		for (i = last_idx - 1; i > first_idx; i--) {
-			if (drv->states[i].exit_latency <= latency_req)
+			if (drv->states[i].exit_latency_ns <= latency_req)
 				break;
 		}
 		ladder_do_selection(dev, ldev, last_idx, i);
@@ -110,7 +111,7 @@ static int ladder_select_state(struct cp
 	}
 
 	if (last_idx > first_idx &&
-	    last_residency < last_state->threshold.demotion_time) {
+	    last_residency < last_state->threshold.demotion_time_ns) {
 		last_state->stats.demotion_count++;
 		last_state->stats.promotion_count = 0;
 		if (last_state->stats.demotion_count >= last_state->threshold.demotion_count) {
@@ -150,9 +151,9 @@ static int ladder_enable_device(struct c
 		lstate->threshold.demotion_count = DEMOTION_COUNT;
 
 		if (i < drv->state_count - 1)
-			lstate->threshold.promotion_time = state->exit_latency;
+			lstate->threshold.promotion_time_ns = state->exit_latency_ns;
 		if (i > first_idx)
-			lstate->threshold.demotion_time = state->exit_latency;
+			lstate->threshold.demotion_time_ns = state->exit_latency_ns;
 	}
 
 	return 0;
drivers/cpuidle/governors/menu.c +53 -53

256 lines not on this page · raw message

drivers/cpuidle/governors/teo.c +34 -38

197 lines not on this page · raw message

drivers/cpuidle/governors/haltpoll.c +3 -4
Index: linux-pm/drivers/cpuidle/governors/haltpoll.c
===================================================================
@@ -49,7 +49,7 @@ static int haltpoll_select(struct cpuidl
 			   struct cpuidle_device *dev,
 			   bool *stop_tick)
 {
-	int latency_req = cpuidle_governor_latency_req(dev->cpu);
+	s64 latency_req = cpuidle_governor_latency_req(dev->cpu);
 
 	if (!drv->state_count || latency_req == 0) {
 		*stop_tick = false;
@@ -75,10 +75,9 @@ static int haltpoll_select(struct cpuidl
 	return 0;
 }
 
-static void adjust_poll_limit(struct cpuidle_device *dev, unsigned int block_us)
+static void adjust_poll_limit(struct cpuidle_device *dev, u64 block_ns)
 {
 	unsigned int val;
-	u64 block_ns = block_us*NSEC_PER_USEC;
 
 	/* Grow cpu_halt_poll_us if
 	 * cpu_halt_poll_us < block_ns < guest_halt_poll_us
@@ -115,7 +114,7 @@ static void haltpoll_reflect(struct cpui
 	dev->last_state_idx = index;
 
 	if (index != 0)
-		adjust_poll_limit(dev, dev->last_residency);
+		adjust_poll_limit(dev, dev->last_residency_ns);
 }
 
 /**
kernel/sched/idle.c +1 -1
Index: linux-pm/kernel/sched/idle.c
===================================================================
@@ -104,7 +104,7 @@ static int call_cpuidle(struct cpuidle_d
 	 * update no idle residency and return.
 	 */
 	if (current_clr_polling_and_test()) {
-		dev->last_residency = 0;
+		dev->last_residency_ns = 0;
 		local_irq_enable();
 		return -EBUSY;
 	}
maintainer
#1 lore raw
Quoted 5 lines · Rafael J. Wysocki

The patch is rather large, but mostly straightforward. There is a rather ugly piece in the menu governor that first computes the expected idle duration in ns and then converts it to us just in order to compute the typical interval value, and in case that is less than the original expected idle duration value, converts it to ns again. However, if there is a nicer way to do it, I haven't found it so far.

	predicted_ns = div64_u64(data->next_timer_ns *
					data->correction_factor[data->bucket],
				 RESOLUTION * DECAY);
	predicted_us = ktime_to_us(predicted_ns);
	/*
	 * Use the lowest expected idle interval to pick the idle state.
	 */
	typical_us = get_typical_interval(data, predicted_us);
	if (typical_us < predicted_us) {
		predicted_us = typical_us;
		predicted_ns = (u64)typical_us * NSEC_PER_USEC;
	}

Yeah, that is a bit yuck.

The first part:

	predicted_ns = div64_u64(data->next_timer_ns *
					data->correction_factor[data->bucket],
				 RESOLUTION * DECAY);
	predicted_us = ktime_to_us(predicted_ns);

can of course be written like:

	predicted_us = div_u64(data->next_timer_ns * data->correction_factor[data->bucket],
			       RESOLUTION * DECAY * NSEC_PER_USEC);

Since RESOLUTION * DECAY * NSEC_PER_USEC is only 8e6, that doesn't need to be a u64, so u64 / u32 is sufficient and cheaper.

(looking at the original, you did loose the ROUND_CLOSEST bit, which can trivially be restored like:

	predicted_us = div_u64(data->next_timer_ns * data->correction_factor[data->bucket] +
			(RESOLUTION * DECAY * NSEC_PER_USEC) / 2, RESOLUTION * DECAY * NSEC_PER_USEC);

So that reduces from: u64/u64 + u64/32 to u64/32, which should be lots on 32bit.

After that it then becomes:

	predicted_ns = (u64)min(predicted_us, get_typical_interval(data, predicted_us)) * NSEC_PER_USEC;

Which is an unconditional multiplication with a constant, which is loads better than divisions.

Granted, it's still not pretty, but it should be faster than it was.

(this all assumes the initial multiplication doesn't overflow due to now using ->next_timer_ns of course)

#2 lore raw
In reply to Rafael J. Wysocki

Hi Rafael,

To be able to try this patch (and the idle disable consolidation one),
I simply waited until it would apply properly in the main git tree, which it now does.

However it does not compile:

On 2019.09.05 09:35 Rafael J. Wysocki wrote:

...

Quoted 3 lines

In addition to that, change cpuidle_governor_latency_req() to return the idle state exit latency constraint in nanoseconds.

...

Quoted 1 line

Index: linux-pm/drivers/cpuidle/governors/menu.c

...

Quoted 4 lines
drivers/cpuidle/governors/menu.c +0 -0
@@ -388,13 +390,13 @@ static int menu_select(struct cpuidle_dr
 			 * closest timer event, select this one to avoid getting
 			 * stuck in the shallow one for too long.
 			 */

drivers/cpuidle/governors/menu.c static int menu_select(struct cpuidle_dr · line 399

Quoted 10 lines
drivers/cpuidle/governors/menu.c +3 -3
-			if (drv->states[idx].target_residency < TICK_USEC &&
-			    s->target_residency <= ktime_to_us(delta_next))
+			if (drv->states[idx].target_residency_ns < TICK_NSEC &&
+			    s->target_residency_ns <= delta_next)
 				idx = i;
 
 			return idx;
 		}
-		if (s->exit_latency > latency_req)
+		if (s->exit_latency_ns > latency_req_ns)
                                     ^^^^^^^^^^^^^^^

Should be (I think):

+ if (s->exit_latency_ns > latency_req)