xref: /dragonfly/sys/kern/kern_synch.c (revision 685c703c)
1 /*-
2  * Copyright (c) 1982, 1986, 1990, 1991, 1993
3  *	The Regents of the University of California.  All rights reserved.
4  * (c) UNIX System Laboratories, Inc.
5  * All or some portions of this file are derived from material licensed
6  * to the University of California by American Telephone and Telegraph
7  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
8  * the permission of UNIX System Laboratories, Inc.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  * 3. All advertising materials mentioning features or use of this software
19  *    must display the following acknowledgement:
20  *	This product includes software developed by the University of
21  *	California, Berkeley and its contributors.
22  * 4. Neither the name of the University nor the names of its contributors
23  *    may be used to endorse or promote products derived from this software
24  *    without specific prior written permission.
25  *
26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36  * SUCH DAMAGE.
37  *
38  *	@(#)kern_synch.c	8.9 (Berkeley) 5/19/95
39  * $FreeBSD: src/sys/kern/kern_synch.c,v 1.87.2.6 2002/10/13 07:29:53 kbyanc Exp $
40  * $DragonFly: src/sys/kern/kern_synch.c,v 1.64 2006/07/11 01:01:50 dillon Exp $
41  */
42 
43 #include "opt_ktrace.h"
44 
45 #include <sys/param.h>
46 #include <sys/systm.h>
47 #include <sys/proc.h>
48 #include <sys/kernel.h>
49 #include <sys/signalvar.h>
50 #include <sys/resourcevar.h>
51 #include <sys/vmmeter.h>
52 #include <sys/sysctl.h>
53 #include <sys/lock.h>
54 #ifdef KTRACE
55 #include <sys/uio.h>
56 #include <sys/ktrace.h>
57 #endif
58 #include <sys/xwait.h>
59 #include <sys/ktr.h>
60 
61 #include <sys/thread2.h>
62 #include <sys/spinlock2.h>
63 
64 #include <machine/cpu.h>
65 #include <machine/ipl.h>
66 #include <machine/smp.h>
67 
68 TAILQ_HEAD(tslpque, thread);
69 
70 static void sched_setup (void *dummy);
71 SYSINIT(sched_setup, SI_SUB_KICK_SCHEDULER, SI_ORDER_FIRST, sched_setup, NULL)
72 
73 int	hogticks;
74 int	lbolt;
75 int	lbolt_syncer;
76 int	sched_quantum;		/* Roundrobin scheduling quantum in ticks. */
77 int	ncpus;
78 int	ncpus2, ncpus2_shift, ncpus2_mask;
79 int	safepri;
80 
81 static struct callout loadav_callout;
82 static struct callout schedcpu_callout;
83 MALLOC_DEFINE(M_TSLEEP, "tslpque", "tsleep queues");
84 
85 #if !defined(KTR_TSLEEP)
86 #define KTR_TSLEEP	KTR_ALL
87 #endif
88 KTR_INFO_MASTER(tsleep);
89 KTR_INFO(KTR_TSLEEP, tsleep, tsleep_beg, 0, "tsleep enter", 0);
90 KTR_INFO(KTR_TSLEEP, tsleep, tsleep_end, 0, "tsleep exit", 0);
91 KTR_INFO(KTR_TSLEEP, tsleep, wakeup_beg, 0, "wakeup enter", 0);
92 KTR_INFO(KTR_TSLEEP, tsleep, wakeup_end, 0, "wakeup exit", 0);
93 #define logtsleep(name)	KTR_LOG(tsleep_ ## name)
94 
95 struct loadavg averunnable =
96 	{ {0, 0, 0}, FSCALE };	/* load average, of runnable procs */
97 /*
98  * Constants for averages over 1, 5, and 15 minutes
99  * when sampling at 5 second intervals.
100  */
101 static fixpt_t cexp[3] = {
102 	0.9200444146293232 * FSCALE,	/* exp(-1/12) */
103 	0.9834714538216174 * FSCALE,	/* exp(-1/60) */
104 	0.9944598480048967 * FSCALE,	/* exp(-1/180) */
105 };
106 
107 static void	endtsleep (void *);
108 static void	unsleep_and_wakeup_thread(struct thread *td);
109 static void	loadav (void *arg);
110 static void	schedcpu (void *arg);
111 
112 /*
113  * Adjust the scheduler quantum.  The quantum is specified in microseconds.
114  * Note that 'tick' is in microseconds per tick.
115  */
116 static int
117 sysctl_kern_quantum(SYSCTL_HANDLER_ARGS)
118 {
119 	int error, new_val;
120 
121 	new_val = sched_quantum * tick;
122 	error = sysctl_handle_int(oidp, &new_val, 0, req);
123         if (error != 0 || req->newptr == NULL)
124 		return (error);
125 	if (new_val < tick)
126 		return (EINVAL);
127 	sched_quantum = new_val / tick;
128 	hogticks = 2 * sched_quantum;
129 	return (0);
130 }
131 
132 SYSCTL_PROC(_kern, OID_AUTO, quantum, CTLTYPE_INT|CTLFLAG_RW,
133 	0, sizeof sched_quantum, sysctl_kern_quantum, "I", "");
134 
135 /*
136  * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the
137  * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below
138  * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT).
139  *
140  * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used:
141  *     1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits).
142  *
143  * If you don't want to bother with the faster/more-accurate formula, you
144  * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate
145  * (more general) method of calculating the %age of CPU used by a process.
146  *
147  * decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing
148  */
149 #define CCPU_SHIFT	11
150 
151 static fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
152 SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
153 
154 /*
155  * kernel uses `FSCALE', userland (SHOULD) use kern.fscale
156  */
157 static int     fscale __unused = FSCALE;
158 SYSCTL_INT(_kern, OID_AUTO, fscale, CTLFLAG_RD, 0, FSCALE, "");
159 
160 /*
161  * Recompute process priorities, once a second.
162  *
163  * Since the userland schedulers are typically event oriented, if the
164  * estcpu calculation at wakeup() time is not sufficient to make a
165  * process runnable relative to other processes in the system we have
166  * a 1-second recalc to help out.
167  *
168  * This code also allows us to store sysclock_t data in the process structure
169  * without fear of an overrun, since sysclock_t are guarenteed to hold
170  * several seconds worth of count.
171  *
172  * WARNING!  callouts can preempt normal threads.  However, they will not
173  * preempt a thread holding a spinlock so we *can* safely use spinlocks.
174  */
175 static int schedcpu_stats(struct proc *p, void *data __unused);
176 static int schedcpu_resource(struct proc *p, void *data __unused);
177 
178 static void
179 schedcpu(void *arg)
180 {
181 	allproc_scan(schedcpu_stats, NULL);
182 	allproc_scan(schedcpu_resource, NULL);
183 	wakeup((caddr_t)&lbolt);
184 	wakeup((caddr_t)&lbolt_syncer);
185 	callout_reset(&schedcpu_callout, hz, schedcpu, NULL);
186 }
187 
188 /*
189  * General process statistics once a second
190  */
191 static int
192 schedcpu_stats(struct proc *p, void *data __unused)
193 {
194 	crit_enter();
195 	p->p_swtime++;
196 	if (p->p_stat == SSLEEP)
197 		p->p_slptime++;
198 
199 	/*
200 	 * Only recalculate processes that are active or have slept
201 	 * less then 2 seconds.  The schedulers understand this.
202 	 */
203 	if (p->p_slptime <= 1) {
204 		p->p_usched->recalculate(&p->p_lwp);
205 	} else {
206 		p->p_pctcpu = (p->p_pctcpu * ccpu) >> FSHIFT;
207 	}
208 	crit_exit();
209 	return(0);
210 }
211 
212 /*
213  * Resource checks.  XXX break out since psignal/killproc can block,
214  * limiting us to one process killed per second.  There is probably
215  * a better way.
216  */
217 static int
218 schedcpu_resource(struct proc *p, void *data __unused)
219 {
220 	u_int64_t ttime;
221 
222 	crit_enter();
223 	if (p->p_stat == SIDL ||
224 	    (p->p_flag & P_ZOMBIE) ||
225 	    p->p_limit == NULL ||
226 	    p->p_thread == NULL
227 	) {
228 		crit_exit();
229 		return(0);
230 	}
231 
232 	ttime = p->p_thread->td_sticks + p->p_thread->td_uticks;
233 
234 	switch(plimit_testcpulimit(p->p_limit, ttime)) {
235 	case PLIMIT_TESTCPU_KILL:
236 		killproc(p, "exceeded maximum CPU limit");
237 		break;
238 	case PLIMIT_TESTCPU_XCPU:
239 		if ((p->p_flag & P_XCPU) == 0) {
240 			p->p_flag |= P_XCPU;
241 			psignal(p, SIGXCPU);
242 		}
243 		break;
244 	default:
245 		break;
246 	}
247 	crit_exit();
248 	return(0);
249 }
250 
251 /*
252  * This is only used by ps.  Generate a cpu percentage use over
253  * a period of one second.
254  *
255  * MPSAFE
256  */
257 void
258 updatepcpu(struct lwp *lp, int cpticks, int ttlticks)
259 {
260 	fixpt_t acc;
261 	int remticks;
262 
263 	acc = (cpticks << FSHIFT) / ttlticks;
264 	if (ttlticks >= ESTCPUFREQ) {
265 		lp->lwp_pctcpu = acc;
266 	} else {
267 		remticks = ESTCPUFREQ - ttlticks;
268 		lp->lwp_pctcpu = (acc * ttlticks + lp->lwp_pctcpu * remticks) /
269 				ESTCPUFREQ;
270 	}
271 }
272 
273 /*
274  * We're only looking at 7 bits of the address; everything is
275  * aligned to 4, lots of things are aligned to greater powers
276  * of 2.  Shift right by 8, i.e. drop the bottom 256 worth.
277  */
278 #define TABLESIZE	128
279 #define LOOKUP(x)	(((intptr_t)(x) >> 8) & (TABLESIZE - 1))
280 
281 static cpumask_t slpque_cpumasks[TABLESIZE];
282 
283 /*
284  * General scheduler initialization.  We force a reschedule 25 times
285  * a second by default.  Note that cpu0 is initialized in early boot and
286  * cannot make any high level calls.
287  *
288  * Each cpu has its own sleep queue.
289  */
290 void
291 sleep_gdinit(globaldata_t gd)
292 {
293 	static struct tslpque slpque_cpu0[TABLESIZE];
294 	int i;
295 
296 	if (gd->gd_cpuid == 0) {
297 		sched_quantum = (hz + 24) / 25;
298 		hogticks = 2 * sched_quantum;
299 
300 		gd->gd_tsleep_hash = slpque_cpu0;
301 	} else {
302 		gd->gd_tsleep_hash = malloc(sizeof(slpque_cpu0),
303 					    M_TSLEEP, M_WAITOK | M_ZERO);
304 	}
305 	for (i = 0; i < TABLESIZE; ++i)
306 		TAILQ_INIT(&gd->gd_tsleep_hash[i]);
307 }
308 
309 /*
310  * General sleep call.  Suspends the current process until a wakeup is
311  * performed on the specified identifier.  The process will then be made
312  * runnable with the specified priority.  Sleeps at most timo/hz seconds
313  * (0 means no timeout).  If flags includes PCATCH flag, signals are checked
314  * before and after sleeping, else signals are not checked.  Returns 0 if
315  * awakened, EWOULDBLOCK if the timeout expires.  If PCATCH is set and a
316  * signal needs to be delivered, ERESTART is returned if the current system
317  * call should be restarted if possible, and EINTR is returned if the system
318  * call should be interrupted by the signal (return EINTR).
319  *
320  * Note that if we are a process, we release_curproc() before messing with
321  * the LWKT scheduler.
322  *
323  * During autoconfiguration or after a panic, a sleep will simply
324  * lower the priority briefly to allow interrupts, then return.
325  */
326 int
327 tsleep(void *ident, int flags, const char *wmesg, int timo)
328 {
329 	struct thread *td = curthread;
330 	struct proc *p = td->td_proc;		/* may be NULL */
331 	globaldata_t gd;
332 	int sig;
333 	int catch;
334 	int id;
335 	int error;
336 	int oldpri;
337 	struct callout thandle;
338 
339 	/*
340 	 * NOTE: removed KTRPOINT, it could cause races due to blocking
341 	 * even in stable.  Just scrap it for now.
342 	 */
343 	if (cold || panicstr) {
344 		/*
345 		 * After a panic, or during autoconfiguration,
346 		 * just give interrupts a chance, then just return;
347 		 * don't run any other procs or panic below,
348 		 * in case this is the idle process and already asleep.
349 		 */
350 		splz();
351 		oldpri = td->td_pri & TDPRI_MASK;
352 		lwkt_setpri_self(safepri);
353 		lwkt_switch();
354 		lwkt_setpri_self(oldpri);
355 		return (0);
356 	}
357 	logtsleep(tsleep_beg);
358 	gd = td->td_gd;
359 	KKASSERT(td != &gd->gd_idlethread);	/* you must be kidding! */
360 
361 	/*
362 	 * NOTE: all of this occurs on the current cpu, including any
363 	 * callout-based wakeups, so a critical section is a sufficient
364 	 * interlock.
365 	 *
366 	 * The entire sequence through to where we actually sleep must
367 	 * run without breaking the critical section.
368 	 */
369 	id = LOOKUP(ident);
370 	catch = flags & PCATCH;
371 	error = 0;
372 	sig = 0;
373 
374 	crit_enter_quick(td);
375 
376 	KASSERT(ident != NULL, ("tsleep: no ident"));
377 	KASSERT(p == NULL || p->p_stat == SRUN, ("tsleep %p %s %d",
378 		ident, wmesg, p->p_stat));
379 
380 	/*
381 	 * Setup for the current process (if this is a process).
382 	 */
383 	if (p) {
384 		if (catch) {
385 			/*
386 			 * Early termination if PCATCH was set and a
387 			 * signal is pending, interlocked with the
388 			 * critical section.
389 			 *
390 			 * Early termination only occurs when tsleep() is
391 			 * entered while in a normal SRUN state.
392 			 */
393 			if ((sig = CURSIG(p)) != 0)
394 				goto resume;
395 
396 			/*
397 			 * Causes psignal to wake us up when.
398 			 */
399 			p->p_flag |= P_SINTR;
400 		}
401 
402 		/*
403 		 * Make sure the current process has been untangled from
404 		 * the userland scheduler and initialize slptime to start
405 		 * counting.
406 		 */
407 		if (flags & PNORESCHED)
408 			td->td_flags |= TDF_NORESCHED;
409 		p->p_usched->release_curproc(&p->p_lwp);
410 		p->p_slptime = 0;
411 	}
412 
413 	/*
414 	 * Move our thread to the correct queue and setup our wchan, etc.
415 	 */
416 	lwkt_deschedule_self(td);
417 	td->td_flags |= TDF_TSLEEPQ;
418 	TAILQ_INSERT_TAIL(&gd->gd_tsleep_hash[id], td, td_threadq);
419 	atomic_set_int(&slpque_cpumasks[id], gd->gd_cpumask);
420 
421 	td->td_wchan = ident;
422 	td->td_wmesg = wmesg;
423 	td->td_wdomain = flags & PDOMAIN_MASK;
424 
425 	/*
426 	 * Setup the timeout, if any
427 	 */
428 	if (timo) {
429 		callout_init(&thandle);
430 		callout_reset(&thandle, timo, endtsleep, td);
431 	}
432 
433 	/*
434 	 * Beddy bye bye.
435 	 */
436 	if (p) {
437 		/*
438 		 * Ok, we are sleeping.  Place us in the SSLEEP state.
439 		 */
440 		KKASSERT((p->p_flag & P_ONRUNQ) == 0);
441 		p->p_stat = SSLEEP;
442 		p->p_stats->p_ru.ru_nvcsw++;
443 		lwkt_switch();
444 
445 		/*
446 		 * And when we are woken up, put us back in SRUN.  If we
447 		 * slept for over a second, recalculate our estcpu.
448 		 */
449 		p->p_stat = SRUN;
450 		if (p->p_slptime)
451 			p->p_usched->recalculate(&p->p_lwp);
452 		p->p_slptime = 0;
453 	} else {
454 		lwkt_switch();
455 	}
456 
457 	/*
458 	 * Make sure we haven't switched cpus while we were asleep.  It's
459 	 * not supposed to happen.  Cleanup our temporary flags.
460 	 */
461 	KKASSERT(gd == td->td_gd);
462 	td->td_flags &= ~TDF_NORESCHED;
463 
464 	/*
465 	 * Cleanup the timeout.
466 	 */
467 	if (timo) {
468 		if (td->td_flags & TDF_TIMEOUT) {
469 			td->td_flags &= ~TDF_TIMEOUT;
470 			if (sig == 0)
471 				error = EWOULDBLOCK;
472 		} else {
473 			callout_stop(&thandle);
474 		}
475 	}
476 
477 	/*
478 	 * Since td_threadq is used both for our run queue AND for the
479 	 * tsleep hash queue, we can't still be on it at this point because
480 	 * we've gotten cpu back.
481 	 */
482 	KASSERT((td->td_flags & TDF_TSLEEPQ) == 0, ("tsleep: impossible thread flags %08x", td->td_flags));
483 	td->td_wchan = NULL;
484 	td->td_wmesg = NULL;
485 	td->td_wdomain = 0;
486 
487 	/*
488 	 * Figure out the correct error return
489 	 */
490 resume:
491 	if (p) {
492 		p->p_flag &= ~(P_BREAKTSLEEP | P_SINTR);
493 		if (catch && error == 0 && (sig != 0 || (sig = CURSIG(p)))) {
494 			if (SIGISMEMBER(p->p_sigacts->ps_sigintr, sig))
495 				error = EINTR;
496 			else
497 				error = ERESTART;
498 		}
499 	}
500 	logtsleep(tsleep_end);
501 	crit_exit_quick(td);
502 	return (error);
503 }
504 
505 /*
506  * This is a dandy function that allows us to interlock tsleep/wakeup
507  * operations with unspecified upper level locks, such as lockmgr locks,
508  * simply by holding a critical section.  The sequence is:
509  *
510  *	(enter critical section)
511  *	(acquire upper level lock)
512  *	tsleep_interlock(blah)
513  *	(release upper level lock)
514  *	tsleep(blah, ...)
515  *	(exit critical section)
516  *
517  * Basically this function sets our cpumask for the ident which informs
518  * other cpus that our cpu 'might' be waiting (or about to wait on) the
519  * hash index related to the ident.  The critical section prevents another
520  * cpu's wakeup() from being processed on our cpu until we are actually
521  * able to enter the tsleep().  Thus, no race occurs between our attempt
522  * to release a resource and sleep, and another cpu's attempt to acquire
523  * a resource and call wakeup.
524  *
525  * There isn't much of a point to this function unless you call it while
526  * holding a critical section.
527  */
528 static __inline void
529 _tsleep_interlock(globaldata_t gd, void *ident)
530 {
531 	int id = LOOKUP(ident);
532 
533 	atomic_set_int(&slpque_cpumasks[id], gd->gd_cpumask);
534 }
535 
536 void
537 tsleep_interlock(void *ident)
538 {
539 	_tsleep_interlock(mycpu, ident);
540 }
541 
542 /*
543  * Interlocked spinlock sleep.  An exclusively held spinlock must
544  * be passed to msleep().  The function will atomically release the
545  * spinlock and tsleep on the ident, then reacquire the spinlock and
546  * return.
547  *
548  * This routine is fairly important along the critical path, so optimize it
549  * heavily.
550  */
551 int
552 msleep(void *ident, struct spinlock *spin, int flags,
553        const char *wmesg, int timo)
554 {
555 	globaldata_t gd = mycpu;
556 	int error;
557 
558 	crit_enter_gd(gd);
559 	_tsleep_interlock(gd, ident);
560 	spin_unlock_wr_quick(gd, spin);
561 	error = tsleep(ident, flags, wmesg, timo);
562 	spin_lock_wr_quick(gd, spin);
563 	crit_exit_gd(gd);
564 
565 	return (error);
566 }
567 
568 /*
569  * Implement the timeout for tsleep.
570  *
571  * We set P_BREAKTSLEEP to indicate that an event has occured, but
572  * we only call setrunnable if the process is not stopped.
573  *
574  * This type of callout timeout is scheduled on the same cpu the process
575  * is sleeping on.  Also, at the moment, the MP lock is held.
576  */
577 static void
578 endtsleep(void *arg)
579 {
580 	thread_t td = arg;
581 	struct proc *p;
582 
583 	ASSERT_MP_LOCK_HELD(curthread);
584 	crit_enter();
585 
586 	/*
587 	 * cpu interlock.  Thread flags are only manipulated on
588 	 * the cpu owning the thread.  proc flags are only manipulated
589 	 * by the older of the MP lock.  We have both.
590 	 */
591 	if (td->td_flags & TDF_TSLEEPQ) {
592 		td->td_flags |= TDF_TIMEOUT;
593 
594 		if ((p = td->td_proc) != NULL) {
595 			p->p_flag |= P_BREAKTSLEEP;
596 			if ((p->p_flag & P_STOPPED) == 0)
597 				setrunnable(p);
598 		} else {
599 			unsleep_and_wakeup_thread(td);
600 		}
601 	}
602 	crit_exit();
603 }
604 
605 /*
606  * Unsleep and wakeup a thread.  This function runs without the MP lock
607  * which means that it can only manipulate thread state on the owning cpu,
608  * and cannot touch the process state at all.
609  */
610 static
611 void
612 unsleep_and_wakeup_thread(struct thread *td)
613 {
614 	globaldata_t gd = mycpu;
615 	int id;
616 
617 #ifdef SMP
618 	if (td->td_gd != gd) {
619 		lwkt_send_ipiq(td->td_gd, (ipifunc1_t)unsleep_and_wakeup_thread, td);
620 		return;
621 	}
622 #endif
623 	crit_enter();
624 	if (td->td_flags & TDF_TSLEEPQ) {
625 		td->td_flags &= ~TDF_TSLEEPQ;
626 		id = LOOKUP(td->td_wchan);
627 		TAILQ_REMOVE(&gd->gd_tsleep_hash[id], td, td_threadq);
628 		if (TAILQ_FIRST(&gd->gd_tsleep_hash[id]) == NULL)
629 			atomic_clear_int(&slpque_cpumasks[id], gd->gd_cpumask);
630 		lwkt_schedule(td);
631 	}
632 	crit_exit();
633 }
634 
635 /*
636  * Make all processes sleeping on the specified identifier runnable.
637  * count may be zero or one only.
638  *
639  * The domain encodes the sleep/wakeup domain AND the first cpu to check
640  * (which is always the current cpu).  As we iterate across cpus
641  *
642  * This call may run without the MP lock held.  We can only manipulate thread
643  * state on the cpu owning the thread.  We CANNOT manipulate process state
644  * at all.
645  */
646 static void
647 _wakeup(void *ident, int domain)
648 {
649 	struct tslpque *qp;
650 	struct thread *td;
651 	struct thread *ntd;
652 	globaldata_t gd;
653 #ifdef SMP
654 	cpumask_t mask;
655 	cpumask_t tmask;
656 	int startcpu;
657 	int nextcpu;
658 #endif
659 	int id;
660 
661 	crit_enter();
662 	logtsleep(wakeup_beg);
663 	gd = mycpu;
664 	id = LOOKUP(ident);
665 	qp = &gd->gd_tsleep_hash[id];
666 restart:
667 	for (td = TAILQ_FIRST(qp); td != NULL; td = ntd) {
668 		ntd = TAILQ_NEXT(td, td_threadq);
669 		if (td->td_wchan == ident &&
670 		    td->td_wdomain == (domain & PDOMAIN_MASK)
671 		) {
672 			KKASSERT(td->td_flags & TDF_TSLEEPQ);
673 			td->td_flags &= ~TDF_TSLEEPQ;
674 			TAILQ_REMOVE(qp, td, td_threadq);
675 			if (TAILQ_FIRST(qp) == NULL) {
676 				atomic_clear_int(&slpque_cpumasks[id],
677 						 gd->gd_cpumask);
678 			}
679 			lwkt_schedule(td);
680 			if (domain & PWAKEUP_ONE)
681 				goto done;
682 			goto restart;
683 		}
684 	}
685 
686 #ifdef SMP
687 	/*
688 	 * We finished checking the current cpu but there still may be
689 	 * more work to do.  Either wakeup_one was requested and no matching
690 	 * thread was found, or a normal wakeup was requested and we have
691 	 * to continue checking cpus.
692 	 *
693 	 * The cpu that started the wakeup sequence is encoded in the domain.
694 	 * We use this information to determine which cpus still need to be
695 	 * checked, locate a candidate cpu, and chain the wakeup
696 	 * asynchronously with an IPI message.
697 	 *
698 	 * It should be noted that this scheme is actually less expensive then
699 	 * the old scheme when waking up multiple threads, since we send
700 	 * only one IPI message per target candidate which may then schedule
701 	 * multiple threads.  Before we could have wound up sending an IPI
702 	 * message for each thread on the target cpu (!= current cpu) that
703 	 * needed to be woken up.
704 	 *
705 	 * NOTE: Wakeups occuring on remote cpus are asynchronous.  This
706 	 * should be ok since we are passing idents in the IPI rather then
707 	 * thread pointers.
708 	 */
709 	if ((domain & PWAKEUP_MYCPU) == 0 &&
710 	    (mask = slpque_cpumasks[id]) != 0
711 	) {
712 		/*
713 		 * Look for a cpu that might have work to do.  Mask out cpus
714 		 * which have already been processed.
715 		 *
716 		 * 31xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
717 		 *        ^        ^           ^
718 		 *      start   currentcpu    start
719 		 *      case2                 case1
720 		 *        *        *           *
721 		 * 11111111111111110000000000000111	case1
722 		 * 00000000111111110000000000000000	case2
723 		 *
724 		 * case1:  We started at start_case1 and processed through
725 		 *  	   to the current cpu.  We have to check any bits
726 		 *	   after the current cpu, then check bits before
727 		 *         the starting cpu.
728 		 *
729 		 * case2:  We have already checked all the bits from
730 		 *         start_case2 to the end, and from 0 to the current
731 		 *         cpu.  We just have the bits from the current cpu
732 		 *         to start_case2 left to check.
733 		 */
734 		startcpu = PWAKEUP_DECODE(domain);
735 		if (gd->gd_cpuid >= startcpu) {
736 			/*
737 			 * CASE1
738 			 */
739 			tmask = mask & ~((gd->gd_cpumask << 1) - 1);
740 			if (mask & tmask) {
741 				nextcpu = bsfl(mask & tmask);
742 				lwkt_send_ipiq2(globaldata_find(nextcpu),
743 						_wakeup, ident, domain);
744 			} else {
745 				tmask = (1 << startcpu) - 1;
746 				if (mask & tmask) {
747 					nextcpu = bsfl(mask & tmask);
748 					lwkt_send_ipiq2(
749 						    globaldata_find(nextcpu),
750 						    _wakeup, ident, domain);
751 				}
752 			}
753 		} else {
754 			/*
755 			 * CASE2
756 			 */
757 			tmask = ~((gd->gd_cpumask << 1) - 1) &
758 				 ((1 << startcpu) - 1);
759 			if (mask & tmask) {
760 				nextcpu = bsfl(mask & tmask);
761 				lwkt_send_ipiq2(globaldata_find(nextcpu),
762 						_wakeup, ident, domain);
763 			}
764 		}
765 	}
766 #endif
767 done:
768 	logtsleep(wakeup_end);
769 	crit_exit();
770 }
771 
772 /*
773  * Wakeup all threads tsleep()ing on the specified ident, on all cpus
774  */
775 void
776 wakeup(void *ident)
777 {
778     _wakeup(ident, PWAKEUP_ENCODE(0, mycpu->gd_cpuid));
779 }
780 
781 /*
782  * Wakeup one thread tsleep()ing on the specified ident, on any cpu.
783  */
784 void
785 wakeup_one(void *ident)
786 {
787     /* XXX potentially round-robin the first responding cpu */
788     _wakeup(ident, PWAKEUP_ENCODE(0, mycpu->gd_cpuid) | PWAKEUP_ONE);
789 }
790 
791 /*
792  * Wakeup threads tsleep()ing on the specified ident on the current cpu
793  * only.
794  */
795 void
796 wakeup_mycpu(void *ident)
797 {
798     _wakeup(ident, PWAKEUP_MYCPU);
799 }
800 
801 /*
802  * Wakeup one thread tsleep()ing on the specified ident on the current cpu
803  * only.
804  */
805 void
806 wakeup_mycpu_one(void *ident)
807 {
808     /* XXX potentially round-robin the first responding cpu */
809     _wakeup(ident, PWAKEUP_MYCPU|PWAKEUP_ONE);
810 }
811 
812 /*
813  * Wakeup all thread tsleep()ing on the specified ident on the specified cpu
814  * only.
815  */
816 void
817 wakeup_oncpu(globaldata_t gd, void *ident)
818 {
819 #ifdef SMP
820     if (gd == mycpu) {
821 	_wakeup(ident, PWAKEUP_MYCPU);
822     } else {
823 	lwkt_send_ipiq2(gd, _wakeup, ident, PWAKEUP_MYCPU);
824     }
825 #else
826     _wakeup(ident, PWAKEUP_MYCPU);
827 #endif
828 }
829 
830 /*
831  * Wakeup one thread tsleep()ing on the specified ident on the specified cpu
832  * only.
833  */
834 void
835 wakeup_oncpu_one(globaldata_t gd, void *ident)
836 {
837 #ifdef SMP
838     if (gd == mycpu) {
839 	_wakeup(ident, PWAKEUP_MYCPU | PWAKEUP_ONE);
840     } else {
841 	lwkt_send_ipiq2(gd, _wakeup, ident, PWAKEUP_MYCPU | PWAKEUP_ONE);
842     }
843 #else
844     _wakeup(ident, PWAKEUP_MYCPU | PWAKEUP_ONE);
845 #endif
846 }
847 
848 /*
849  * Wakeup all threads waiting on the specified ident that slept using
850  * the specified domain, on all cpus.
851  */
852 void
853 wakeup_domain(void *ident, int domain)
854 {
855     _wakeup(ident, PWAKEUP_ENCODE(domain, mycpu->gd_cpuid));
856 }
857 
858 /*
859  * Wakeup one thread waiting on the specified ident that slept using
860  * the specified  domain, on any cpu.
861  */
862 void
863 wakeup_domain_one(void *ident, int domain)
864 {
865     /* XXX potentially round-robin the first responding cpu */
866     _wakeup(ident, PWAKEUP_ENCODE(domain, mycpu->gd_cpuid) | PWAKEUP_ONE);
867 }
868 
869 /*
870  * setrunnable()
871  *
872  * Make a process runnable.  The MP lock must be held on call.  This only
873  * has an effect if we are in SSLEEP.  We only break out of the
874  * tsleep if P_BREAKTSLEEP is set, otherwise we just fix-up the state.
875  *
876  * NOTE: With the MP lock held we can only safely manipulate the process
877  * structure.  We cannot safely manipulate the thread structure.
878  */
879 void
880 setrunnable(struct proc *p)
881 {
882 	crit_enter();
883 	ASSERT_MP_LOCK_HELD(curthread);
884 	p->p_flag &= ~P_STOPPED;
885 	if (p->p_stat == SSLEEP && (p->p_flag & P_BREAKTSLEEP)) {
886 		unsleep_and_wakeup_thread(p->p_thread);
887 	}
888 	crit_exit();
889 }
890 
891 /*
892  * The process is stopped due to some condition, usually because P_STOPPED
893  * is set but also possibly due to being traced.
894  *
895  * NOTE!  If the caller sets P_STOPPED, the caller must also clear P_WAITED
896  * because the parent may check the child's status before the child actually
897  * gets to this routine.
898  *
899  * This routine is called with the current process only, typically just
900  * before returning to userland.
901  *
902  * Setting P_BREAKTSLEEP before entering the tsleep will cause a passive
903  * SIGCONT to break out of the tsleep.
904  */
905 void
906 tstop(struct proc *p)
907 {
908 	wakeup((caddr_t)p->p_pptr);
909 	p->p_flag |= P_BREAKTSLEEP;
910 	tsleep(p, 0, "stop", 0);
911 }
912 
913 /*
914  * Yield / synchronous reschedule.  This is a bit tricky because the trap
915  * code might have set a lazy release on the switch function.   Setting
916  * P_PASSIVE_ACQ will ensure that the lazy release executes when we call
917  * switch, and that we are given a greater chance of affinity with our
918  * current cpu.
919  *
920  * We call lwkt_setpri_self() to rotate our thread to the end of the lwkt
921  * run queue.  lwkt_switch() will also execute any assigned passive release
922  * (which usually calls release_curproc()), allowing a same/higher priority
923  * process to be designated as the current process.
924  *
925  * While it is possible for a lower priority process to be designated,
926  * it's call to lwkt_maybe_switch() in acquire_curproc() will likely
927  * round-robin back to us and we will be able to re-acquire the current
928  * process designation.
929  */
930 void
931 uio_yield(void)
932 {
933 	struct thread *td = curthread;
934 	struct proc *p = td->td_proc;
935 
936 	lwkt_setpri_self(td->td_pri & TDPRI_MASK);
937 	if (p) {
938 		p->p_flag |= P_PASSIVE_ACQ;
939 		lwkt_switch();
940 		p->p_flag &= ~P_PASSIVE_ACQ;
941 	} else {
942 		lwkt_switch();
943 	}
944 }
945 
946 /*
947  * Compute a tenex style load average of a quantity on
948  * 1, 5 and 15 minute intervals.
949  */
950 static int loadav_count_runnable(struct proc *p, void *data);
951 
952 static void
953 loadav(void *arg)
954 {
955 	struct loadavg *avg;
956 	int i, nrun;
957 
958 	nrun = 0;
959 	allproc_scan(loadav_count_runnable, &nrun);
960 	avg = &averunnable;
961 	for (i = 0; i < 3; i++) {
962 		avg->ldavg[i] = (cexp[i] * avg->ldavg[i] +
963 		    nrun * FSCALE * (FSCALE - cexp[i])) >> FSHIFT;
964 	}
965 
966 	/*
967 	 * Schedule the next update to occur after 5 seconds, but add a
968 	 * random variation to avoid synchronisation with processes that
969 	 * run at regular intervals.
970 	 */
971 	callout_reset(&loadav_callout, hz * 4 + (int)(random() % (hz * 2 + 1)),
972 		      loadav, NULL);
973 }
974 
975 static int
976 loadav_count_runnable(struct proc *p, void *data)
977 {
978 	int *nrunp = data;
979 	thread_t td;
980 
981 	switch (p->p_stat) {
982 	case SRUN:
983 		if ((td = p->p_thread) == NULL)
984 			break;
985 		if (td->td_flags & TDF_BLOCKED)
986 			break;
987 		/* fall through */
988 	case SIDL:
989 		++*nrunp;
990 		break;
991 	default:
992 		break;
993 	}
994 	return(0);
995 }
996 
997 /* ARGSUSED */
998 static void
999 sched_setup(void *dummy)
1000 {
1001 	callout_init(&loadav_callout);
1002 	callout_init(&schedcpu_callout);
1003 
1004 	/* Kick off timeout driven events by calling first time. */
1005 	schedcpu(NULL);
1006 	loadav(NULL);
1007 }
1008 
1009