1 // SPDX-License-Identifier: GPL-2.0
3  * Timer events oriented CPU idle governor
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
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.
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.
119 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_update()
120 	unsigned int sleep_length_us = ktime_to_us(cpu_data->sleep_length_ns);  in teo_update()
121 	int i, idx_hit = -1, idx_timer = -1;  in teo_update()
124 	if (cpu_data->time_span_ns >= cpu_data->sleep_length_ns) {  in teo_update()
127 		 * enough to the closest timer event expected at the idle state  in teo_update()
134 		lat = drv->states[dev->last_state_idx].exit_latency;  in teo_update()
136 		measured_us = ktime_to_us(cpu_data->time_span_ns);  in teo_update()
139 		 * executed by the CPU is not likely to be worst-case every  in teo_update()
144 			measured_us -= lat / 2;  in teo_update()
150 	 * Decay the "early hits" metric for all of the states and find the  in teo_update()
151 	 * states matching the sleep length and the measured idle duration.  in teo_update()
153 	for (i = 0; i < drv->state_count; i++) {  in teo_update()
154 		unsigned int early_hits = cpu_data->states[i].early_hits;  in teo_update()
156 		cpu_data->states[i].early_hits -= early_hits >> DECAY_SHIFT;  in teo_update()
158 		if (drv->states[i].target_residency <= sleep_length_us) {  in teo_update()
160 			if (drv->states[i].target_residency <= measured_us)  in teo_update()
167 	 * length.  If it matches the measured idle duration too, this is a hit,  in teo_update()
171 	 * matches the measured idle duration.  in teo_update()
174 		unsigned int hits = cpu_data->states[idx_timer].hits;  in teo_update()
175 		unsigned int misses = cpu_data->states[idx_timer].misses;  in teo_update()
177 		hits -= hits >> DECAY_SHIFT;  in teo_update()
178 		misses -= misses >> DECAY_SHIFT;  in teo_update()
183 				cpu_data->states[idx_hit].early_hits += PULSE;  in teo_update()
188 		cpu_data->states[idx_timer].misses = misses;  in teo_update()
189 		cpu_data->states[idx_timer].hits = hits;  in teo_update()
193 	 * Save idle duration values corresponding to non-timer wakeups for  in teo_update()
196 	cpu_data->intervals[cpu_data->interval_idx++] = measured_us;  in teo_update()
197 	if (cpu_data->interval_idx > INTERVALS)  in teo_update()
198 		cpu_data->interval_idx = 0;  in teo_update()
202  * teo_find_shallower_state - Find shallower idle state matching given duration.
205  * @state_idx: Index of the capping idle state.
206  * @duration_us: Idle duration value to match.
214 	for (i = state_idx - 1; i >= 0; i--) {  in teo_find_shallower_state()
215 		if (drv->states[i].disabled || dev->states_usage[i].disable)  in teo_find_shallower_state()
219 		if (drv->states[i].target_residency <= duration_us)  in teo_find_shallower_state()
226  * teo_select - Selects the next idle state to enter.
234 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_select()
235 	int latency_req = cpuidle_governor_latency_req(dev->cpu);  in teo_select()
240 	if (dev->last_state_idx >= 0) {  in teo_select()
242 		dev->last_state_idx = -1;  in teo_select()
245 	cpu_data->time_span_ns = local_clock();  in teo_select()
247 	cpu_data->sleep_length_ns = tick_nohz_get_sleep_length(&delta_tick);  in teo_select()
248 	duration_us = ktime_to_us(cpu_data->sleep_length_ns);  in teo_select()
251 	max_early_idx = -1;  in teo_select()
252 	constraint_idx = drv->state_count;  in teo_select()
253 	idx = -1;  in teo_select()
255 	for (i = 0; i < drv->state_count; i++) {  in teo_select()
256 		struct cpuidle_state *s = &drv->states[i];  in teo_select()
257 		struct cpuidle_state_usage *su = &dev->states_usage[i];  in teo_select()
259 		if (s->disabled || su->disable) {  in teo_select()
267 			 * still point to a shallower idle state.  in teo_select()
270 			    count < cpu_data->states[i].early_hits)  in teo_select()
271 				count = cpu_data->states[i].early_hits;  in teo_select()
279 		if (s->target_residency > duration_us)  in teo_select()
282 		if (s->exit_latency > latency_req && constraint_idx > i)  in teo_select()
287 		if (count < cpu_data->states[i].early_hits &&  in teo_select()
289 		      drv->states[i].target_residency < TICK_USEC)) {  in teo_select()
290 			count = cpu_data->states[i].early_hits;  in teo_select()
296 	 * If the "hits" metric of the idle state matching the sleep length is  in teo_select()
298 	 * it is more likely that one of the shallower states will match the  in teo_select()
299 	 * idle duration observed after wakeup, so take the one with the maximum  in teo_select()
303 	if (cpu_data->states[idx].hits <= cpu_data->states[idx].misses &&  in teo_select()
306 		duration_us = drv->states[idx].target_residency;  in teo_select()
311 	 * shallower idle state than the one selected so far.  in teo_select()
317 		idx = 0; /* No states enabled. Must use 0. */  in teo_select()
324 		 * Count and sum the most recent idle duration values less than  in teo_select()
325 		 * the current expected idle duration value.  in teo_select()
328 			unsigned int val = cpu_data->intervals[i];  in teo_select()
338 		 * Give up unless the majority of the most recent idle duration  in teo_select()
345 			 * Avoid spending too much time in an idle state that  in teo_select()
350 				if (drv->states[idx].target_residency > avg_us)  in teo_select()
359 	 * expected idle duration is shorter than the tick period length.  in teo_select()
361 	if (((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) ||  in teo_select()
373 		if (idx > 0 && drv->states[idx].target_residency > delta_tick_us)  in teo_select()
381  * teo_reflect - Note that governor data for the CPU need to be updated.
387 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_reflect()
389 	dev->last_state_idx = state;  in teo_reflect()
392 	 * nets, assume that the CPU might have been idle for the entire sleep  in teo_reflect()
395 	if (dev->poll_time_limit ||  in teo_reflect()
396 	    (tick_nohz_idle_got_tick() && cpu_data->sleep_length_ns > TICK_NSEC)) {  in teo_reflect()
397 		dev->poll_time_limit = false;  in teo_reflect()
398 		cpu_data->time_span_ns = cpu_data->sleep_length_ns;  in teo_reflect()
400 		cpu_data->time_span_ns = local_clock() - cpu_data->time_span_ns;  in teo_reflect()
405  * teo_enable_device - Initialize the governor's data for the target CPU.
412 	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);  in teo_enable_device()
418 		cpu_data->intervals[i] = UINT_MAX;  in teo_enable_device()