1 // SPDX-License-Identifier: GPL-2.0
3  * Timer events oriented CPU idle governor
5  * Copyright (C) 2018 - 2021 Intel Corporation
10  * DOC: teo-description
14  * other interrupt types, so they are likely to dominate CPU wakeup patterns.
16  * can be determined at the idle state selection time, although doing that may
18  * for idle state selection.
20  * Of course, non-timer wakeup sources are more important in some use cases,
21  * but even then it is generally unnecessary to consider idle duration values
24  * CPU anyway unless it is woken up earlier.
27  * checks if it can select a shallow idle state using wakeup pattern information
29  * at all.  For this purpose, it counts CPU wakeup events and looks for an idle
30  * state whose target residency has not exceeded the idle duration (measured
36  * boundaries are aligned with the target residency parameter values of the CPU
37  * idle states provided by the %CPUIdle driver in the ascending order.  That is,
39  * the second idle state (idle state 1), the second bin spans from the target
40  * residency of idle state 1 up to, but not including, the target residency of
41  * idle state 2, the third bin spans from the target residency of idle state 2
42  * up to, but not including, the target residency of idle state 3 and so on.
43  * The last bin spans from the target residency of the deepest idle state
47  * They are updated every time before selecting an idle state for the given CPU
51  * sleep length and the idle duration measured after CPU wakeup fall into the
52  * same bin (that is, the CPU appears to wake up "on time" relative to the sleep
54  * non-timer wakeup events for which the measured idle duration falls into a bin
55  * that corresponds to an idle state shallower than the one whose bin is fallen
59  * The governor also counts "intercepts" with the measured idle duration below
63  * In order to select an idle state for a CPU, the governor takes the following
67  * 1. Find the deepest enabled CPU idle state (the candidate idle state) and
70  *    - The sum of the "hits" metric for all of the idle states shallower than
71  *      the candidate one (it represents the cases in which the CPU was likely
74  *    - The sum of the "intercepts" metric for all of the idle states shallower
75  *      than the candidate one (it represents the cases in which the CPU was
76  *      likely woken up by a non-timer wakeup source).
80  *    a shallower idle state is likely to be more suitable, so look for it.
82  *    - Traverse the enabled idle states shallower than the candidate one in the
85  *    - For each of them compute the sum of the "intercepts" metrics over all
86  *      of the idle states between it and the candidate one (including the
89  *    - If this sum is greater than a half of the second sum computed in step 1,
90  *      use the given idle state as the new candidate one.
109  * Idle state exit latency threshold used for deciding whether or not to check
122  * struct teo_bin - Metrics used by the TEO cpuidle governor.
132  * struct teo_cpu - CPU data used by the TEO cpuidle governor.
134  * @state_bins: Idle state data bins for this CPU.
137  * @short_idles: Wakeups after short idle periods.
152  * teo_update - Update CPU metrics after wakeup.
154  * @dev: Target CPU.
158 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_update()
163 	cpu_data->short_idles -= cpu_data->short_idles >> DECAY_SHIFT;  in teo_update()
165 	if (cpu_data->artificial_wakeup) {  in teo_update()
172 		u64 lat_ns = drv->states[dev->last_state_idx].exit_latency_ns;  in teo_update()
174 		measured_ns = dev->last_residency_ns;  in teo_update()
177 		 * executed by the CPU is not likely to be worst-case every  in teo_update()
182 			measured_ns -= lat_ns / 2;  in teo_update()
184 				cpu_data->short_idles += PULSE;  in teo_update()
187 			cpu_data->short_idles += PULSE;  in teo_update()
193 	 * find the bins that the sleep length and the measured idle duration  in teo_update()
196 	for (i = 0; i < drv->state_count; i++) {  in teo_update()
197 		struct teo_bin *bin = &cpu_data->state_bins[i];  in teo_update()
199 		bin->hits -= bin->hits >> DECAY_SHIFT;  in teo_update()
200 		bin->intercepts -= bin->intercepts >> DECAY_SHIFT;  in teo_update()
202 		target_residency_ns = drv->states[i].target_residency_ns;  in teo_update()
204 		if (target_residency_ns <= cpu_data->sleep_length_ns) {  in teo_update()
211 	cpu_data->tick_intercepts -= cpu_data->tick_intercepts >> DECAY_SHIFT;  in teo_update()
213 	 * If the measured idle duration falls into the same bin as the sleep  in teo_update()
216 	 * the measured idle duration.  in teo_update()
219 		cpu_data->state_bins[idx_timer].hits += PULSE;  in teo_update()
221 		cpu_data->state_bins[idx_duration].intercepts += PULSE;  in teo_update()
223 			cpu_data->tick_intercepts += PULSE;  in teo_update()
226 	cpu_data->total -= cpu_data->total >> DECAY_SHIFT;  in teo_update()
227 	cpu_data->total += PULSE;  in teo_update()
233 		drv->states[i].target_residency_ns >= TICK_NSEC;  in teo_state_ok()
237  * teo_find_shallower_state - Find shallower idle state matching given duration.
239  * @dev: Target CPU.
240  * @state_idx: Index of the capping idle state.
241  * @duration_ns: Idle duration value to match.
242  * @no_poll: Don't consider polling states.
250 	for (i = state_idx - 1; i >= 0; i--) {  in teo_find_shallower_state()
251 		if (dev->states_usage[i].disable ||  in teo_find_shallower_state()
252 				(no_poll && drv->states[i].flags & CPUIDLE_FLAG_POLLING))  in teo_find_shallower_state()
256 		if (drv->states[i].target_residency_ns <= duration_ns)  in teo_find_shallower_state()
263  * teo_select - Selects the next idle state to enter.
265  * @dev: Target CPU.
271 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_select()
272 	s64 latency_req = cpuidle_governor_latency_req(dev->cpu);  in teo_select()
279 	int idx0 = 0, idx = -1;  in teo_select()
283 	if (dev->last_state_idx >= 0) {  in teo_select()
285 		dev->last_state_idx = -1;  in teo_select()
293 	 * for the cases when the CPU is mostly woken up by timers and there may  in teo_select()
294 	 * be opportunities to ask for a deeper idle state when no imminent  in teo_select()
297 	cpu_data->sleep_length_ns = KTIME_MAX;  in teo_select()
300 	if (drv->state_count < 2) {  in teo_select()
305 	if (!dev->states_usage[0].disable)  in teo_select()
309 	for (i = 1; i < drv->state_count; i++) {  in teo_select()
310 		struct teo_bin *prev_bin = &cpu_data->state_bins[i-1];  in teo_select()
311 		struct cpuidle_state *s = &drv->states[i];  in teo_select()
314 		 * Update the sums of idle state mertics for all of the states  in teo_select()
317 		intercept_sum += prev_bin->intercepts;  in teo_select()
318 		hit_sum += prev_bin->hits;  in teo_select()
320 		if (dev->states_usage[i].disable)  in teo_select()
328 		if (s->exit_latency_ns <= latency_req)  in teo_select()
338 		idx = 0; /* No states enabled, must use 0. */  in teo_select()
344 		 * Only one idle state is enabled, so use it, but do not  in teo_select()
347 		duration_ns = drv->states[idx].target_residency_ns;  in teo_select()
352 	 * If the sum of the intercepts metric for all of the idle states  in teo_select()
355 	 * all of the deeper states, a shallower idle state is likely to be a  in teo_select()
358 	if (2 * idx_intercept_sum > cpu_data->total - idx_hit_sum) {  in teo_select()
362 		 * Look for the deepest idle state whose target residency had  in teo_select()
363 		 * not exceeded the idle duration in over a half of the relevant  in teo_select()
371 		for (i = idx - 1; i >= 0; i--) {  in teo_select()
372 			struct teo_bin *bin = &cpu_data->state_bins[i];  in teo_select()
374 			intercept_sum += bin->intercepts;  in teo_select()
383 				    !dev->states_usage[i].disable) {  in teo_select()
391 			if (dev->states_usage[i].disable)  in teo_select()
405 			 * states other than the initial candidate have been  in teo_select()
406 			 * found, give up (the remaining states to check are  in teo_select()
418 	 * idle state shallower than the current candidate one.  in teo_select()
428 	 * are dominant.  Namely, it may effectively prevent deeper idle states  in teo_select()
433 	 * CPU are unlikely (user space has a default 50 us slack value for  in teo_select()
436 	 * benefit from using a deep idle state in that case would be  in teo_select()
437 	 * questionable anyway for latency reasons.  Thus if the measured idle  in teo_select()
439 	 * non-timer wakeups to be dominant and skip updating the sleep length  in teo_select()
443 	 * shallow idle states regardless of the wakeup type, so the sleep  in teo_select()
446 	if ((!idx || drv->states[idx].target_residency_ns < RESIDENCY_THRESHOLD_NS) &&  in teo_select()
447 	    (2 * cpu_data->short_idles >= cpu_data->total ||  in teo_select()
452 	cpu_data->sleep_length_ns = duration_ns;  in teo_select()
461 	if (drv->states[idx].target_residency_ns > duration_ns) {  in teo_select()
472 	if (drv->states[idx].target_residency_ns < TICK_NSEC &&  in teo_select()
473 	    cpu_data->tick_intercepts > cpu_data->total / 2 + cpu_data->total / 8)  in teo_select()
479 	 * one or the expected idle duration is shorter than the tick period  in teo_select()
482 	if ((!(drv->states[idx].flags & CPUIDLE_FLAG_POLLING) &&  in teo_select()
492 	    drv->states[idx].target_residency_ns > delta_tick)  in teo_select()
501  * teo_reflect - Note that governor data for the CPU need to be updated.
502  * @dev: Target CPU.
507 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_reflect()
509 	dev->last_state_idx = state;  in teo_reflect()
510 	if (dev->poll_time_limit ||  in teo_reflect()
511 	    (tick_nohz_idle_got_tick() && cpu_data->sleep_length_ns > TICK_NSEC)) {  in teo_reflect()
516 		dev->poll_time_limit = false;  in teo_reflect()
517 		cpu_data->artificial_wakeup = true;  in teo_reflect()
519 		cpu_data->artificial_wakeup = false;  in teo_reflect()
524  * teo_enable_device - Initialize the governor's data for the target CPU.
526  * @dev: Target CPU.
531 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_enable_device()