1/*
2 * Copyright (c) 2000-2008 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/*
29 * @OSF_COPYRIGHT@
30 */
31/*
32 * Mach Operating System
33 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
34 * All Rights Reserved.
35 *
36 * Permission to use, copy, modify and distribute this software and its
37 * documentation is hereby granted, provided that both the copyright
38 * notice and this permission notice appear in all copies of the
39 * software, derivative works or modified versions, and any portions
40 * thereof, and that both notices appear in supporting documentation.
41 *
42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
43 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
45 *
46 * Carnegie Mellon requests users of this software to return to
47 *
48 *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
49 *  School of Computer Science
50 *  Carnegie Mellon University
51 *  Pittsburgh PA 15213-3890
52 *
53 * any improvements or extensions that they make and grant Carnegie Mellon
54 * the rights to redistribute these changes.
55 */
56/*
57 */
58/*
59 *	File:	clock_prim.c
60 *	Author:	Avadis Tevanian, Jr.
61 *	Date:	1986
62 *
63 *	Clock primitives.
64 */
65
66#include <mach/boolean.h>
67#include <mach/kern_return.h>
68#include <mach/machine.h>
69#include <kern/host.h>
70#include <kern/mach_param.h>
71#include <kern/sched.h>
72#include <kern/spl.h>
73#include <kern/thread.h>
74#include <kern/processor.h>
75#include <machine/machparam.h>
76
77/*
78 *	thread_quantum_expire:
79 *
80 *	Recalculate the quantum and priority for a thread.
81 *
82 *	Called at splsched.
83 */
84
85void
86thread_quantum_expire(
87	timer_call_param_t	p0,
88	timer_call_param_t	p1)
89{
90	processor_t			processor = p0;
91	thread_t			thread = p1;
92	ast_t				preempt;
93
94	thread_lock(thread);
95
96	/*
97	 *	Check for fail-safe trip.
98	 */
99	if (!(thread->sched_mode & (TH_MODE_TIMESHARE|TH_MODE_PROMOTED))) {
100		uint64_t			new_computation;
101
102		new_computation = processor->quantum_end;
103		new_computation -= thread->computation_epoch;
104		if (new_computation + thread->computation_metered >
105											max_unsafe_computation) {
106
107			if (thread->sched_mode & TH_MODE_REALTIME) {
108				thread->priority = DEPRESSPRI;
109
110				thread->safe_mode |= TH_MODE_REALTIME;
111				thread->sched_mode &= ~TH_MODE_REALTIME;
112			}
113
114			sched_share_incr();
115
116			thread->safe_release = sched_tick + sched_safe_duration;
117			thread->sched_mode |= (TH_MODE_FAILSAFE|TH_MODE_TIMESHARE);
118		}
119	}
120
121	/*
122	 *	Recompute scheduled priority if appropriate.
123	 */
124	if (thread->sched_stamp != sched_tick)
125		update_priority(thread);
126	else
127	if (thread->sched_mode & TH_MODE_TIMESHARE) {
128		register uint32_t	delta;
129
130		thread_timer_delta(thread, delta);
131
132		/*
133		 *	Accumulate timesharing usage only
134		 *	during contention for processor
135		 *	resources.
136		 */
137		if (thread->pri_shift < INT8_MAX)
138			thread->sched_usage += delta;
139
140		thread->cpu_delta += delta;
141
142		/*
143		 * Adjust the scheduled priority if
144		 * the thread has not been promoted
145		 * and is not depressed.
146		 */
147		if (	!(thread->sched_mode & TH_MODE_PROMOTED)	&&
148				!(thread->sched_mode & TH_MODE_ISDEPRESSED)		)
149			compute_my_priority(thread);
150	}
151
152	processor->current_pri = thread->sched_pri;
153
154	/*
155	 *	This quantum is up, give this thread another.
156	 */
157	if (first_timeslice(processor))
158		processor->timeslice--;
159
160	thread_quantum_init(thread);
161	processor->quantum_end += thread->current_quantum;
162	timer_call_enter1(&processor->quantum_timer,
163							thread, processor->quantum_end);
164
165	/*
166	 *	Context switch check.
167	 */
168	if ((preempt = csw_check(processor)) != AST_NONE)
169		ast_on(preempt);
170	else {
171		processor_set_t		pset = processor->processor_set;
172
173		pset_lock(pset);
174
175		pset_pri_hint(pset, processor, processor->current_pri);
176		pset_count_hint(pset, processor, processor->runq.count);
177
178		pset_unlock(pset);
179	}
180
181	thread_unlock(thread);
182}
183
184/*
185 *	Define shifts for simulating (5/8) ** n
186 *
187 *	Shift structures for holding update shifts.  Actual computation
188 *	is  usage = (usage >> shift1) +/- (usage >> abs(shift2))  where the
189 *	+/- is determined by the sign of shift 2.
190 */
191struct shift_data {
192	int	shift1;
193	int	shift2;
194};
195
196#define SCHED_DECAY_TICKS	32
197static struct shift_data	sched_decay_shifts[SCHED_DECAY_TICKS] = {
198	{1,1},{1,3},{1,-3},{2,-7},{3,5},{3,-5},{4,-8},{5,7},
199	{5,-7},{6,-10},{7,10},{7,-9},{8,-11},{9,12},{9,-11},{10,-13},
200	{11,14},{11,-13},{12,-15},{13,17},{13,-15},{14,-17},{15,19},{16,18},
201	{16,-19},{17,22},{18,20},{18,-20},{19,26},{20,22},{20,-22},{21,-27}
202};
203
204/*
205 *	do_priority_computation:
206 *
207 *	Calculate the timesharing priority based upon usage and load.
208 */
209#define do_priority_computation(thread, pri)							\
210	MACRO_BEGIN															\
211	(pri) = (thread)->priority		/* start with base priority */		\
212	    - ((thread)->sched_usage >> (thread)->pri_shift);				\
213	if ((pri) < MINPRI_USER)											\
214		(pri) = MINPRI_USER;											\
215	else																\
216	if ((pri) > MAXPRI_KERNEL)											\
217		(pri) = MAXPRI_KERNEL;											\
218	MACRO_END
219
220/*
221 *	set_priority:
222 *
223 *	Set the base priority of the thread
224 *	and reset its scheduled priority.
225 *
226 *	Called with the thread locked.
227 */
228void
229set_priority(
230	register thread_t	thread,
231	register int		priority)
232{
233	thread->priority = priority;
234	compute_priority(thread, FALSE);
235}
236
237/*
238 *	compute_priority:
239 *
240 *	Reset the scheduled priority of the thread
241 *	according to its base priority if the
242 *	thread has not been promoted or depressed.
243 *
244 *	Called with the thread locked.
245 */
246void
247compute_priority(
248	register thread_t	thread,
249	boolean_t			override_depress)
250{
251	register int		priority;
252
253	if (	!(thread->sched_mode & TH_MODE_PROMOTED)			&&
254			(!(thread->sched_mode & TH_MODE_ISDEPRESSED)	||
255				 override_depress							)		) {
256		if (thread->sched_mode & TH_MODE_TIMESHARE)
257			do_priority_computation(thread, priority);
258		else
259			priority = thread->priority;
260
261		set_sched_pri(thread, priority);
262	}
263}
264
265/*
266 *	compute_my_priority:
267 *
268 *	Reset the scheduled priority for
269 *	a timesharing thread.
270 *
271 *	Only for use on the current thread
272 *	if timesharing and not depressed.
273 *
274 *	Called with the thread locked.
275 */
276void
277compute_my_priority(
278	register thread_t	thread)
279{
280	register int		priority;
281
282	do_priority_computation(thread, priority);
283	assert(thread->runq == PROCESSOR_NULL);
284	thread->sched_pri = priority;
285}
286
287/*
288 *	update_priority
289 *
290 *	Perform housekeeping operations driven by scheduler tick.
291 *
292 *	Called with the thread locked.
293 */
294void
295update_priority(
296	register thread_t	thread)
297{
298	register unsigned	ticks;
299	register uint32_t	delta;
300
301	ticks = sched_tick - thread->sched_stamp;
302	assert(ticks != 0);
303	thread->sched_stamp += ticks;
304	thread->pri_shift = sched_pri_shift;
305
306	/*
307	 *	Gather cpu usage data.
308	 */
309	thread_timer_delta(thread, delta);
310	if (ticks < SCHED_DECAY_TICKS) {
311		register struct shift_data	*shiftp;
312
313		/*
314		 *	Accumulate timesharing usage only
315		 *	during contention for processor
316		 *	resources.
317		 */
318		if (thread->pri_shift < INT8_MAX)
319			thread->sched_usage += delta;
320
321		thread->cpu_usage += delta + thread->cpu_delta;
322		thread->cpu_delta = 0;
323
324		shiftp = &sched_decay_shifts[ticks];
325		if (shiftp->shift2 > 0) {
326		    thread->cpu_usage =
327						(thread->cpu_usage >> shiftp->shift1) +
328						(thread->cpu_usage >> shiftp->shift2);
329		    thread->sched_usage =
330						(thread->sched_usage >> shiftp->shift1) +
331						(thread->sched_usage >> shiftp->shift2);
332		}
333		else {
334		    thread->cpu_usage =
335						(thread->cpu_usage >> shiftp->shift1) -
336						(thread->cpu_usage >> -(shiftp->shift2));
337		    thread->sched_usage =
338						(thread->sched_usage >> shiftp->shift1) -
339						(thread->sched_usage >> -(shiftp->shift2));
340		}
341	}
342	else {
343		thread->cpu_usage = thread->cpu_delta = 0;
344		thread->sched_usage = 0;
345	}
346
347	/*
348	 *	Check for fail-safe release.
349	 */
350	if (	(thread->sched_mode & TH_MODE_FAILSAFE)		&&
351			thread->sched_stamp >= thread->safe_release		) {
352		if (!(thread->safe_mode & TH_MODE_TIMESHARE)) {
353			if (thread->safe_mode & TH_MODE_REALTIME) {
354				thread->priority = BASEPRI_RTQUEUES;
355
356				thread->sched_mode |= TH_MODE_REALTIME;
357			}
358
359			thread->sched_mode &= ~TH_MODE_TIMESHARE;
360
361			if ((thread->state & (TH_RUN|TH_IDLE)) == TH_RUN)
362				sched_share_decr();
363
364			if (!(thread->sched_mode & TH_MODE_ISDEPRESSED))
365				set_sched_pri(thread, thread->priority);
366		}
367
368		thread->safe_mode = 0;
369		thread->sched_mode &= ~TH_MODE_FAILSAFE;
370	}
371
372	/*
373	 *	Recompute scheduled priority if appropriate.
374	 */
375	if (	(thread->sched_mode & TH_MODE_TIMESHARE)	&&
376			!(thread->sched_mode & TH_MODE_PROMOTED)	&&
377			!(thread->sched_mode & TH_MODE_ISDEPRESSED)		) {
378		register int		new_pri;
379
380		do_priority_computation(thread, new_pri);
381		if (new_pri != thread->sched_pri) {
382			boolean_t		removed = run_queue_remove(thread);
383
384			thread->sched_pri = new_pri;
385			if (removed)
386				thread_setrun(thread, SCHED_TAILQ);
387		}
388	}
389}
390