1 // SPDX-License-Identifier: GPL-2.0
3  * Timer events oriented CPU idle governor
10  * other interrupts, so they are likely to be the most significant source of CPU
11  * wakeups from idle states.  Moreover, information about what happened in the
13  * idle state with target residency within the time to the closest timer is
14  * likely to be suitable for the upcoming idle time of the CPU and, if not, then
15  * which of the shallower idle states to choose.
17  * Of course, non-timer wakeup sources are more important in some use cases and
18  * they can be covered by taking a few most recent idle time intervals of the
19  * CPU into account.  However, even in that case it is not necessary to consider
20  * idle duration values greater than the time till the closest timer, as the
24  * Thus this governor estimates whether or not the upcoming idle time of the CPU
26  * idle state for it in accordance with that, as follows:
28  * - Find an idle state on the basis of the sleep length and state statistics
31  *   o Find the deepest idle state whose target residency is less than or equal
34  *   o Select it if it matched both the sleep length and the observed idle
36  *     (i.e. the observed idle duration was significantly shorter than the sleep
42  * - If the majority of the most recent idle duration values are below the
43  *   target residency of the idle state selected so far, use those values to
44  *   compute the new expected idle duration and find an idle state matching it
62  * Number of the most recent idle duration values to take into consideration for
68  * struct teo_idle_state - Idle state data used by the TEO cpuidle governor.
69  * @early_hits: "Early" CPU wakeups "matching" this state.
70  * @hits: "On time" CPU wakeups "matching" this state.
71  * @misses: CPU wakeups "missing" this state.
73  * A CPU wakeup is "matched" by a given idle state if the idle duration measured
75  * residency of the next one (or if this is the deepest available idle state, it
76  * "matches" a CPU wakeup when the measured idle duration is at least equal to
79  * Also, from the TEO governor perspective, a CPU wakeup from idle is "early" if
81  * is, early enough to match an idle state shallower than the one matching the
86  * the time till the closest timer event used for idle state selection.
95  * struct teo_cpu - CPU data used by the TEO cpuidle governor.
96  * @time_span_ns: Time between idle state selection and post-wakeup update.
98  * @states: Idle states data corresponding to this CPU.
99  * @interval_idx: Index of the most recent saved idle interval.
100  * @intervals: Saved idle duration values.
105 	struct teo_idle_state states[CPUIDLE_STATE_MAX];  member
113  * teo_update - Update CPU data after wakeup.
115  * @dev: Target CPU.
119 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_update()
120 	int i, idx_hit = -1, idx_timer = -1;  in teo_update()
123 	if (cpu_data->time_span_ns >= cpu_data->sleep_length_ns) {  in teo_update()
126 		 * enough to the closest timer event expected at the idle state  in teo_update()
131 		u64 lat_ns = drv->states[dev->last_state_idx].exit_latency_ns;  in teo_update()
135 		 * (saved) time till the next timer event and the measured idle  in teo_update()
140 		measured_ns = dev->last_residency_ns;  in teo_update()
143 		 * executed by the CPU is not likely to be worst-case every  in teo_update()
148 			measured_ns -= lat_ns / 2;  in teo_update()
154 	 * Decay the "early hits" metric for all of the states and find the  in teo_update()
155 	 * states matching the sleep length and the measured idle duration.  in teo_update()
157 	for (i = 0; i < drv->state_count; i++) {  in teo_update()
158 		unsigned int early_hits = cpu_data->states[i].early_hits;  in teo_update()
160 		cpu_data->states[i].early_hits -= early_hits >> DECAY_SHIFT;  in teo_update()
162 		if (drv->states[i].target_residency_ns <= cpu_data->sleep_length_ns) {  in teo_update()
164 			if (drv->states[i].target_residency_ns <= measured_ns)  in teo_update()
171 	 * length.  If it matches the measured idle duration too, this is a hit,  in teo_update()
175 	 * matches the measured idle duration.  in teo_update()
178 		unsigned int hits = cpu_data->states[idx_timer].hits;  in teo_update()
179 		unsigned int misses = cpu_data->states[idx_timer].misses;  in teo_update()
181 		hits -= hits >> DECAY_SHIFT;  in teo_update()
182 		misses -= misses >> DECAY_SHIFT;  in teo_update()
187 				cpu_data->states[idx_hit].early_hits += PULSE;  in teo_update()
192 		cpu_data->states[idx_timer].misses = misses;  in teo_update()
193 		cpu_data->states[idx_timer].hits = hits;  in teo_update()
197 	 * Save idle duration values corresponding to non-timer wakeups for  in teo_update()
200 	cpu_data->intervals[cpu_data->interval_idx++] = measured_ns;  in teo_update()
201 	if (cpu_data->interval_idx >= INTERVALS)  in teo_update()
202 		cpu_data->interval_idx = 0;  in teo_update()
211  * teo_find_shallower_state - Find shallower idle state matching given duration.
213  * @dev: Target CPU.
214  * @state_idx: Index of the capping idle state.
215  * @duration_ns: Idle duration value to match.
223 	for (i = state_idx - 1; i >= 0; i--) {  in teo_find_shallower_state()
224 		if (dev->states_usage[i].disable)  in teo_find_shallower_state()
228 		if (drv->states[i].target_residency_ns <= duration_ns)  in teo_find_shallower_state()
235  * teo_select - Selects the next idle state to enter.
237  * @dev: Target CPU.
243 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_select()
244 	s64 latency_req = cpuidle_governor_latency_req(dev->cpu);  in teo_select()
250 	if (dev->last_state_idx >= 0) {  in teo_select()
252 		dev->last_state_idx = -1;  in teo_select()
255 	cpu_data->time_span_ns = local_clock();  in teo_select()
258 	cpu_data->sleep_length_ns = duration_ns;  in teo_select()
263 	max_early_idx = -1;  in teo_select()
264 	prev_max_early_idx = -1;  in teo_select()
265 	constraint_idx = drv->state_count;  in teo_select()
266 	idx = -1;  in teo_select()
268 	for (i = 0; i < drv->state_count; i++) {  in teo_select()
269 		struct cpuidle_state *s = &drv->states[i];  in teo_select()
271 		if (dev->states_usage[i].disable) {  in teo_select()
273 			 * Ignore disabled states with target residencies beyond  in teo_select()
274 			 * the anticipated idle duration.  in teo_select()
276 			if (s->target_residency_ns > duration_ns)  in teo_select()
280 			 * This state is disabled, so the range of idle duration  in teo_select()
287 			hits = cpu_data->states[i].hits;  in teo_select()
288 			misses = cpu_data->states[i].misses;  in teo_select()
290 			if (early_hits >= cpu_data->states[i].early_hits ||  in teo_select()
302 				early_hits = cpu_data->states[i].early_hits;  in teo_select()
314 			if (teo_time_ok(drv->states[idx].target_residency_ns)) {  in teo_select()
316 				early_hits = cpu_data->states[i].early_hits;  in teo_select()
325 			hits = cpu_data->states[i].hits;  in teo_select()
326 			misses = cpu_data->states[i].misses;  in teo_select()
329 		if (s->target_residency_ns > duration_ns)  in teo_select()
332 		if (s->exit_latency_ns > latency_req && constraint_idx > i)  in teo_select()
336 		hits = cpu_data->states[i].hits;  in teo_select()
337 		misses = cpu_data->states[i].misses;  in teo_select()
339 		if (early_hits < cpu_data->states[i].early_hits &&  in teo_select()
340 		    teo_time_ok(drv->states[i].target_residency_ns)) {  in teo_select()
342 			early_hits = cpu_data->states[i].early_hits;  in teo_select()
348 	 * If the "hits" metric of the idle state matching the sleep length is  in teo_select()
350 	 * it is more likely that one of the shallower states will match the  in teo_select()
351 	 * idle duration observed after wakeup, so take the one with the maximum  in teo_select()
359 		 * shallower states.  in teo_select()
366 			duration_ns = drv->states[idx].target_residency_ns;  in teo_select()
372 	 * shallower idle state than the one selected so far.  in teo_select()
378 		idx = 0; /* No states enabled. Must use 0. */  in teo_select()
384 		 * Count and sum the most recent idle duration values less than  in teo_select()
385 		 * the current expected idle duration value.  in teo_select()
388 			u64 val = cpu_data->intervals[i];  in teo_select()
398 		 * Give up unless the majority of the most recent idle duration  in teo_select()
405 			 * Avoid spending too much time in an idle state that  in teo_select()
410 				if (drv->states[idx].target_residency_ns > avg_ns)  in teo_select()
419 	 * expected idle duration is shorter than the tick period length.  in teo_select()
421 	if (((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) ||  in teo_select()
431 		if (idx > 0 && drv->states[idx].target_residency_ns > delta_tick)  in teo_select()
439  * teo_reflect - Note that governor data for the CPU need to be updated.
440  * @dev: Target CPU.
445 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_reflect()
447 	dev->last_state_idx = state;  in teo_reflect()
450 	 * nets, assume that the CPU might have been idle for the entire sleep  in teo_reflect()
453 	if (dev->poll_time_limit ||  in teo_reflect()
454 	    (tick_nohz_idle_got_tick() && cpu_data->sleep_length_ns > TICK_NSEC)) {  in teo_reflect()
455 		dev->poll_time_limit = false;  in teo_reflect()
456 		cpu_data->time_span_ns = cpu_data->sleep_length_ns;  in teo_reflect()
458 		cpu_data->time_span_ns = local_clock() - cpu_data->time_span_ns;  in teo_reflect()
463  * teo_enable_device - Initialize the governor's data for the target CPU.
465  * @dev: Target CPU.
470 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_enable_device()
476 		cpu_data->intervals[i] = U64_MAX;  in teo_enable_device()