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
15  * wakeups from idle states.  Moreover, information about what happened in the
17  * idle state with target residency within the (known) time till the closest
19  * the upcoming CPU idle period and, if not, then which of the shallower idle
22  * Of course, non-timer wakeup sources are more important in some use cases
23  * which can be covered by taking a few most recent idle time intervals of the
25  * consider idle duration values greater than the sleep length, because the
29  * Thus this governor estimates whether or not the prospective idle duration of
31  * an idle state for it accordingly.
35  * idle states provided by the %CPUIdle driver in the ascending order.  That is,
37  * the second idle state (idle state 1), the second bin spans from the target
38  * residency of idle state 1 up to, but not including, the target residency of
39  * idle state 2, the third bin spans from the target residency of idle state 2
40  * up to, but not including, the target residency of idle state 3 and so on.
41  * The last bin spans from the target residency of the deepest idle state
45  * They are updated every time before selecting an idle state for the given CPU
49  * sleep length and the idle duration measured after CPU wakeup fall into the
52  * situations in which the measured idle duration is so much shorter than the
53  * sleep length that the bin it falls into corresponds to an idle state
61  * In order to select an idle state for a CPU, the governor takes the following
65  * 1. Find the deepest CPU idle state whose target residency does not exceed
66  *    the current sleep length (the candidate idle state) and compute 3 sums as
69  *    - The sum of the "hits" and "intercepts" metrics for the candidate state
70  *      and all of the deeper idle states (it represents the cases in which the
71  *      CPU was idle long enough to avoid being intercepted if the sleep length
74  *    - The sum of the "intercepts" metrics for all of the idle states shallower
76  *      idle long enough to avoid being intercepted if the sleep length had been
79  *    - The sum of the numbers of recent intercepts for all of the idle states
84  *    for an alternative idle state to select.
86  *    - Traverse the idle states shallower than the candidate one in the
89  *    - For each of them compute the sum of the "intercepts" metrics and the sum
90  *      of the numbers of recent intercepts over all of the idle states between
94  *    - If each of these sums that needs to be taken into account (because the
97  *      1 (which means that the target residency of the state in question had
98  *      not exceeded the idle duration in over a half of the relevant cases),
99  *      select the given idle state instead of the candidate one.
101  * 3. By default, select the candidate state.
118  * Number of the most recent idle duration values to take into consideration for
124  * struct teo_bin - Metrics used by the TEO cpuidle governor.
136  * struct teo_cpu - CPU data used by the TEO cpuidle governor.
137  * @time_span_ns: Time between idle state selection and post-wakeup update.
139  * @state_bins: Idle state data bins for this CPU.
156  * teo_update - Update CPU metrics after wakeup.
157  * @drv: cpuidle driver containing state data.
162 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_update()
166 	if (cpu_data->time_span_ns >= cpu_data->sleep_length_ns) {  in teo_update()
169 		 * enough to the closest timer event expected at the idle state  in teo_update()
174 		u64 lat_ns = drv->states[dev->last_state_idx].exit_latency_ns;  in teo_update()
178 		 * (saved) time till the next timer event and the measured idle  in teo_update()
183 		measured_ns = dev->last_residency_ns;  in teo_update()
186 		 * executed by the CPU is not likely to be worst-case every  in teo_update()
191 			measured_ns -= lat_ns / 2;  in teo_update()
196 	cpu_data->total = 0;  in teo_update()
200 	 * find the bins that the sleep length and the measured idle duration  in teo_update()
203 	for (i = 0; i < drv->state_count; i++) {  in teo_update()
204 		s64 target_residency_ns = drv->states[i].target_residency_ns;  in teo_update()
205 		struct teo_bin *bin = &cpu_data->state_bins[i];  in teo_update()
207 		bin->hits -= bin->hits >> DECAY_SHIFT;  in teo_update()
208 		bin->intercepts -= bin->intercepts >> DECAY_SHIFT;  in teo_update()
210 		cpu_data->total += bin->hits + bin->intercepts;  in teo_update()
212 		if (target_residency_ns <= cpu_data->sleep_length_ns) {  in teo_update()
219 	i = cpu_data->next_recent_idx++;  in teo_update()
220 	if (cpu_data->next_recent_idx >= NR_RECENT)  in teo_update()
221 		cpu_data->next_recent_idx = 0;  in teo_update()
223 	if (cpu_data->recent_idx[i] >= 0)  in teo_update()
224 		cpu_data->state_bins[cpu_data->recent_idx[i]].recent--;  in teo_update()
227 	 * If the measured idle duration falls into the same bin as the sleep  in teo_update()
230 	 * the measured idle duration.  in teo_update()
233 		cpu_data->state_bins[idx_timer].hits += PULSE;  in teo_update()
234 		cpu_data->recent_idx[i] = -1;  in teo_update()
236 		cpu_data->state_bins[idx_duration].intercepts += PULSE;  in teo_update()
237 		cpu_data->state_bins[idx_duration].recent++;  in teo_update()
238 		cpu_data->recent_idx[i] = idx_duration;  in teo_update()
241 	cpu_data->total += PULSE;  in teo_update()
251 	return (drv->states[idx].target_residency_ns +  in teo_middle_of_bin()
252 		drv->states[idx+1].target_residency_ns) / 2;  in teo_middle_of_bin()
256  * teo_find_shallower_state - Find shallower idle state matching given duration.
257  * @drv: cpuidle driver containing state data.
259  * @state_idx: Index of the capping idle state.
260  * @duration_ns: Idle duration value to match.
268 	for (i = state_idx - 1; i >= 0; i--) {  in teo_find_shallower_state()
269 		if (dev->states_usage[i].disable)  in teo_find_shallower_state()
273 		if (drv->states[i].target_residency_ns <= duration_ns)  in teo_find_shallower_state()
280  * teo_select - Selects the next idle state to enter.
281  * @drv: cpuidle driver containing state data.
288 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_select()
289 	s64 latency_req = cpuidle_governor_latency_req(dev->cpu);  in teo_select()
297 	int idx0 = 0, idx = -1;  in teo_select()
303 	if (dev->last_state_idx >= 0) {  in teo_select()
305 		dev->last_state_idx = -1;  in teo_select()
308 	cpu_data->time_span_ns = local_clock();  in teo_select()
311 	cpu_data->sleep_length_ns = duration_ns;  in teo_select()
314 	if (drv->state_count < 2) {  in teo_select()
318 	if (!dev->states_usage[0].disable) {  in teo_select()
320 		if (drv->states[1].target_residency_ns > duration_ns)  in teo_select()
325 	 * Find the deepest idle state whose target residency does not exceed  in teo_select()
326 	 * the current sleep length and the deepest idle state not deeper than  in teo_select()
331 	for (i = 1; i < drv->state_count; i++) {  in teo_select()
332 		struct teo_bin *prev_bin = &cpu_data->state_bins[i-1];  in teo_select()
333 		struct cpuidle_state *s = &drv->states[i];  in teo_select()
336 		 * Update the sums of idle state mertics for all of the states  in teo_select()
339 		intercept_sum += prev_bin->intercepts;  in teo_select()
340 		hit_sum += prev_bin->hits;  in teo_select()
341 		recent_sum += prev_bin->recent;  in teo_select()
343 		if (dev->states_usage[i].disable)  in teo_select()
347 			idx = i; /* first enabled state */  in teo_select()
351 		if (s->target_residency_ns > duration_ns)  in teo_select()
356 		if (s->exit_latency_ns <= latency_req)  in teo_select()
373 	 * If the sum of the intercepts metric for all of the idle states  in teo_select()
375 	 * sum of the intercepts and hits metrics for the candidate state and  in teo_select()
380 	 * idle state to select.  in teo_select()
382 	alt_intercepts = 2 * idx_intercept_sum > cpu_data->total - idx_hit_sum;  in teo_select()
389 		 * Look for the deepest idle state whose target residency had  in teo_select()
390 		 * not exceeded the idle duration in over a half of the relevant  in teo_select()
400 		for (i = idx - 1; i >= 0; i--) {  in teo_select()
401 			struct teo_bin *bin = &cpu_data->state_bins[i];  in teo_select()
404 			intercept_sum += bin->intercepts;  in teo_select()
405 			recent_sum += bin->recent;  in teo_select()
413 				    !dev->states_usage[i].disable) {  in teo_select()
418 					 * The current state is too shallow or  in teo_select()
420 					 * deeper state with suitable time span.  in teo_select()
428 			if (dev->states_usage[i].disable)  in teo_select()
433 				 * The current state is too shallow, but if an  in teo_select()
434 				 * alternative candidate state has been found,  in teo_select()
450 	 * idle state shallower than the current candidate one.  in teo_select()
457 	 * Don't stop the tick if the selected state is a polling one or if the  in teo_select()
458 	 * expected idle duration is shorter than the tick period length.  in teo_select()
460 	if (((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) ||  in teo_select()
466 		 * residency of the state to be returned is not within the time  in teo_select()
471 		    drv->states[idx].target_residency_ns > delta_tick)  in teo_select()
479  * teo_reflect - Note that governor data for the CPU need to be updated.
481  * @state: Entered state.
483 static void teo_reflect(struct cpuidle_device *dev, int state)  in teo_reflect()  argument
485 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_reflect()
487 	dev->last_state_idx = state;  in teo_reflect()
490 	 * nets, assume that the CPU might have been idle for the entire sleep  in teo_reflect()
493 	if (dev->poll_time_limit ||  in teo_reflect()
494 	    (tick_nohz_idle_got_tick() && cpu_data->sleep_length_ns > TICK_NSEC)) {  in teo_reflect()
495 		dev->poll_time_limit = false;  in teo_reflect()
496 		cpu_data->time_span_ns = cpu_data->sleep_length_ns;  in teo_reflect()
498 		cpu_data->time_span_ns = local_clock() - cpu_data->time_span_ns;  in teo_reflect()
503  * teo_enable_device - Initialize the governor's data for the target CPU.
510 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_enable_device()
516 		cpu_data->recent_idx[i] = -1;  in teo_enable_device()