/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- thread_checkstack_init
- thread_checkstack
- thread_create
- cpu_create
- thread_destroy
- exorcise
- thread_panic
- thread_shutdown
- thread_bootstrap
- cpu_hatch
- thread_start_cpus
- thread_make_runnable
- thread_fork
- thread_switch
- thread_startup
- thread_exit
- thread_yield
- schedule
- thread_consider_migration
- wchan_create
- wchan_destroy
- wchan_lock
- wchan_unlock
- wchan_sleep
- wchan_wakeone
- wchan_wakeall
- wchan_isempty
- ipi_send
- ipi_broadcast
- ipi_tlbshootdown
- interprocessor_interrupt
1 /*
2 * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2008, 2009
3 * The President and Fellows of Harvard College.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30 /*
31 * Core kernel-level thread system.
32 */
33
34 #define THREADINLINE
35
36 #include <types.h>
37 #include <kern/errno.h>
38 #include <lib.h>
39 #include <array.h>
40 #include <cpu.h>
41 #include <spl.h>
42 #include <spinlock.h>
43 #include <wchan.h>
44 #include <thread.h>
45 #include <threadlist.h>
46 #include <threadprivate.h>
47 #include <proc.h>
48 #include <current.h>
49 #include <synch.h>
50 #include <addrspace.h>
51 #include <mainbus.h>
52 #include <vnode.h>
53
54 #include "opt-synchprobs.h"
55
56
57 /* Magic number used as a guard value on kernel thread stacks. */
58 #define THREAD_STACK_MAGIC 0xbaadf00d
59
60 /* Wait channel. */
61 struct wchan {
62 const char *wc_name; /* name for this channel */
63 struct threadlist wc_threads; /* list of waiting threads */
64 struct spinlock wc_lock; /* lock for mutual exclusion */
65 };
66
67 /* Master array of CPUs. */
68 DECLARRAY(cpu);
69 DEFARRAY(cpu, /*no inline*/ );
70 static struct cpuarray allcpus;
71
72 /* Used to wait for secondary CPUs to come online. */
73 static struct semaphore *cpu_startup_sem;
74
75 ////////////////////////////////////////////////////////////
76
77 /*
78 * Stick a magic number on the bottom end of the stack. This will
79 * (sometimes) catch kernel stack overflows. Use thread_checkstack()
80 * to test this.
81 */
82 static
83 void
84 thread_checkstack_init(struct thread *thread)
85 {
86 ((uint32_t *)thread->t_stack)[0] = THREAD_STACK_MAGIC;
87 ((uint32_t *)thread->t_stack)[1] = THREAD_STACK_MAGIC;
88 ((uint32_t *)thread->t_stack)[2] = THREAD_STACK_MAGIC;
89 ((uint32_t *)thread->t_stack)[3] = THREAD_STACK_MAGIC;
90 }
91
92 /*
93 * Check the magic number we put on the bottom end of the stack in
94 * thread_checkstack_init. If these assertions go off, it most likely
95 * means you overflowed your stack at some point, which can cause all
96 * kinds of mysterious other things to happen.
97 *
98 * Note that when ->t_stack is NULL, which is the case if the stack
99 * cannot be freed (which in turn is the case if the stack is the boot
100 * stack, and the thread is the boot thread) this doesn't do anything.
101 */
102 static
103 void
104 thread_checkstack(struct thread *thread)
105 {
106 if (thread->t_stack != NULL) {
107 KASSERT(((uint32_t*)thread->t_stack)[0] == THREAD_STACK_MAGIC);
108 KASSERT(((uint32_t*)thread->t_stack)[1] == THREAD_STACK_MAGIC);
109 KASSERT(((uint32_t*)thread->t_stack)[2] == THREAD_STACK_MAGIC);
110 KASSERT(((uint32_t*)thread->t_stack)[3] == THREAD_STACK_MAGIC);
111 }
112 }
113
114 /*
115 * Create a thread. This is used both to create a first thread
116 * for each CPU and to create subsequent forked threads.
117 */
118 static
119 struct thread *
120 thread_create(const char *name)
121 {
122 struct thread *thread;
123
124 DEBUGASSERT(name != NULL);
125
126 thread = kmalloc(sizeof(*thread));
127 if (thread == NULL) {
128 return NULL;
129 }
130
131 thread->t_name = kstrdup(name);
132 if (thread->t_name == NULL) {
133 kfree(thread);
134 return NULL;
135 }
136 thread->t_wchan_name = "NEW";
137 thread->t_state = S_READY;
138
139 /* Thread subsystem fields */
140 thread_machdep_init(&thread->t_machdep);
141 threadlistnode_init(&thread->t_listnode, thread);
142 thread->t_stack = NULL;
143 thread->t_context = NULL;
144 thread->t_cpu = NULL;
145 thread->t_proc = NULL;
146
147 /* Interrupt state fields */
148 thread->t_in_interrupt = false;
149 thread->t_curspl = IPL_HIGH;
150 thread->t_iplhigh_count = 1; /* corresponding to t_curspl */
151
152 /* If you add to struct thread, be sure to initialize here */
153
154 return thread;
155 }
156
157 /*
158 * Create a CPU structure. This is used for the bootup CPU and
159 * also for secondary CPUs.
160 *
161 * The hardware number (the number assigned by firmware or system
162 * board config or whatnot) is tracked separately because it is not
163 * necessarily anything sane or meaningful.
164 */
165 struct cpu *
166 cpu_create(unsigned hardware_number)
167 {
168 struct cpu *c;
169 int result;
170 char namebuf[16];
171
172 c = kmalloc(sizeof(*c));
173 if (c == NULL) {
174 panic("cpu_create: Out of memory\n");
175 }
176
177 c->c_self = c;
178 c->c_hardware_number = hardware_number;
179
180 c->c_curthread = NULL;
181 threadlist_init(&c->c_zombies);
182 c->c_hardclocks = 0;
183
184 c->c_isidle = false;
185 threadlist_init(&c->c_runqueue);
186 spinlock_init(&c->c_runqueue_lock);
187
188 c->c_ipi_pending = 0;
189 c->c_numshootdown = 0;
190 spinlock_init(&c->c_ipi_lock);
191
192 result = cpuarray_add(&allcpus, c, &c->c_number);
193 if (result != 0) {
194 panic("cpu_create: array_add: %s\n", strerror(result));
195 }
196
197 snprintf(namebuf, sizeof(namebuf), "<boot #%d>", c->c_number);
198 c->c_curthread = thread_create(namebuf);
199 if (c->c_curthread == NULL) {
200 panic("cpu_create: thread_create failed\n");
201 }
202 result = proc_addthread(kproc, c->c_curthread);
203 if (result) {
204 panic("cpu_create: proc_addthread:: %s\n", strerror(result));
205 }
206
207 if (c->c_number == 0) {
208 /*
209 * Leave c->c_curthread->t_stack NULL for the boot
210 * cpu. This means we're using the boot stack, which
211 * can't be freed. (Exercise: what would it take to
212 * make it possible to free the boot stack?)
213 */
214 /*c->c_curthread->t_stack = ... */
215 }
216 else {
217 c->c_curthread->t_stack = kmalloc(STACK_SIZE);
218 if (c->c_curthread->t_stack == NULL) {
219 panic("cpu_create: couldn't allocate stack");
220 }
221 thread_checkstack_init(c->c_curthread);
222 }
223 c->c_curthread->t_cpu = c;
224
225 cpu_machdep_init(c);
226
227 return c;
228 }
229
230 /*
231 * Destroy a thread.
232 *
233 * This function cannot be called in the victim thread's own context.
234 * Nor can it be called on a running thread.
235 *
236 * (Freeing the stack you're actually using to run is ... inadvisable.)
237 */
238 static
239 void
240 thread_destroy(struct thread *thread)
241 {
242 KASSERT(thread != curthread);
243 KASSERT(thread->t_state != S_RUN);
244
245 /*
246 * If you add things to struct thread, be sure to clean them up
247 * either here or in thread_exit(). (And not both...)
248 */
249
250 /* Thread subsystem fields */
251 KASSERT(thread->t_proc == NULL);
252 if (thread->t_stack != NULL) {
253 kfree(thread->t_stack);
254 }
255 threadlistnode_cleanup(&thread->t_listnode);
256 thread_machdep_cleanup(&thread->t_machdep);
257
258 /* sheer paranoia */
259 thread->t_wchan_name = "DESTROYED";
260
261 kfree(thread->t_name);
262 kfree(thread);
263 }
264
265 /*
266 * Clean up zombies. (Zombies are threads that have exited but still
267 * need to have thread_destroy called on them.)
268 *
269 * The list of zombies is per-cpu.
270 */
271 static
272 void
273 exorcise(void)
274 {
275 struct thread *z;
276
277 while ((z = threadlist_remhead(&curcpu->c_zombies)) != NULL) {
278 KASSERT(z != curthread);
279 KASSERT(z->t_state == S_ZOMBIE);
280 thread_destroy(z);
281 }
282 }
283
284 /*
285 * On panic, stop the thread system (as much as is reasonably
286 * possible) to make sure we don't end up letting any other threads
287 * run.
288 */
289 void
290 thread_panic(void)
291 {
292 /*
293 * Kill off other CPUs.
294 *
295 * We could wait for them to stop, except that they might not.
296 */
297 ipi_broadcast(IPI_PANIC);
298
299 /*
300 * Drop runnable threads on the floor.
301 *
302 * Don't try to get the run queue lock; we might not be able
303 * to. Instead, blat the list structure by hand, and take the
304 * risk that it might not be quite atomic.
305 */
306 curcpu->c_runqueue.tl_count = 0;
307 curcpu->c_runqueue.tl_head.tln_next = NULL;
308 curcpu->c_runqueue.tl_tail.tln_prev = NULL;
309
310 /*
311 * Ideally, we want to make sure sleeping threads don't wake
312 * up and start running. However, there's no good way to track
313 * down all the wchans floating around the system. Another
314 * alternative would be to set a global flag to make the wchan
315 * wakeup operations do nothing; but that would mean we
316 * ourselves couldn't sleep to wait for an I/O completion
317 * interrupt, and we'd like to be able to do that if the
318 * system isn't that badly hosed.
319 *
320 * So, do nothing else here.
321 *
322 * This may prove inadequate in practice and further steps
323 * might be needed. It may also be necessary to go through and
324 * forcibly unlock all locks or the like...
325 */
326 }
327
328 /*
329 * At system shutdown, ask the other CPUs to switch off.
330 */
331 void
332 thread_shutdown(void)
333 {
334 /*
335 * Stop the other CPUs.
336 *
337 * We should probably wait for them to stop and shut them off
338 * on the system board.
339 */
340 ipi_broadcast(IPI_OFFLINE);
341 }
342
343 /*
344 * Thread system initialization.
345 */
346 void
347 thread_bootstrap(void)
348 {
349 struct cpu *bootcpu;
350 struct thread *bootthread;
351
352 cpuarray_init(&allcpus);
353
354 /*
355 * Create the cpu structure for the bootup CPU, the one we're
356 * currently running on. Assume the hardware number is 0; that
357 * might be updated later by mainbus-type code. This also
358 * creates a thread structure for the first thread, the one
359 * that's already implicitly running when the kernel is
360 * started from the bootloader.
361 */
362 bootcpu = cpu_create(0);
363 bootthread = bootcpu->c_curthread;
364
365 /*
366 * Initializing curcpu and curthread is machine-dependent
367 * because either of curcpu and curthread might be defined in
368 * terms of the other.
369 */
370 INIT_CURCPU(bootcpu, bootthread);
371
372 /*
373 * Now make sure both t_cpu and c_curthread are set. This
374 * might be partially redundant with INIT_CURCPU depending on
375 * how things are defined.
376 */
377 curthread->t_cpu = curcpu;
378 curcpu->c_curthread = curthread;
379
380 /* cpu_create() should have set t_proc. */
381 KASSERT(curthread->t_proc != NULL);
382
383 /* Done */
384 }
385
386 /*
387 * New CPUs come here once MD initialization is finished. curthread
388 * and curcpu should already be initialized.
389 *
390 * Other than clearing thread_start_cpus() to continue, we don't need
391 * to do anything. The startup thread can just exit; we only need it
392 * to be able to get into thread_switch() properly.
393 */
394 void
395 cpu_hatch(unsigned software_number)
396 {
397 KASSERT(curcpu != NULL);
398 KASSERT(curthread != NULL);
399 KASSERT(curcpu->c_number == software_number);
400
401 spl0();
402
403 kprintf("cpu%u: %s\n", software_number, cpu_identify());
404
405 V(cpu_startup_sem);
406 thread_exit();
407 }
408
409 /*
410 * Start up secondary cpus. Called from boot().
411 */
412 void
413 thread_start_cpus(void)
414 {
415 unsigned i;
416
417 kprintf("cpu0: %s\n", cpu_identify());
418
419 cpu_startup_sem = sem_create("cpu_hatch", 0);
420 mainbus_start_cpus();
421
422 for (i=0; i<cpuarray_num(&allcpus) - 1; i++) {
423 P(cpu_startup_sem);
424 }
425 sem_destroy(cpu_startup_sem);
426 cpu_startup_sem = NULL;
427 }
428
429 /*
430 * Make a thread runnable.
431 *
432 * targetcpu might be curcpu; it might not be, too.
433 */
434 static
435 void
436 thread_make_runnable(struct thread *target, bool already_have_lock)
437 {
438 struct cpu *targetcpu;
439 bool isidle;
440
441 /* Lock the run queue of the target thread's cpu. */
442 targetcpu = target->t_cpu;
443
444 if (already_have_lock) {
445 /* The target thread's cpu should be already locked. */
446 KASSERT(spinlock_do_i_hold(&targetcpu->c_runqueue_lock));
447 }
448 else {
449 spinlock_acquire(&targetcpu->c_runqueue_lock);
450 }
451
452 isidle = targetcpu->c_isidle;
453 threadlist_addtail(&targetcpu->c_runqueue, target);
454 if (isidle) {
455 /*
456 * Other processor is idle; send interrupt to make
457 * sure it unidles.
458 */
459 ipi_send(targetcpu, IPI_UNIDLE);
460 }
461
462 if (!already_have_lock) {
463 spinlock_release(&targetcpu->c_runqueue_lock);
464 }
465 }
466
467 /*
468 * Create a new thread based on an existing one.
469 *
470 * The new thread has name NAME, and starts executing in function
471 * ENTRYPOINT. DATA1 and DATA2 are passed to ENTRYPOINT.
472 *
473 * The new thread is created in the process P. If P is null, the
474 * process is inherited from the caller. It will start on the same CPU
475 * as the caller, unless the scheduler intervenes first.
476 */
477 int
478 thread_fork(const char *name,
479 struct proc *proc,
480 void (*entrypoint)(void *data1, unsigned long data2),
481 void *data1, unsigned long data2)
482 {
483 struct thread *newthread;
484 int result;
485
486 #ifdef UW
487 DEBUG(DB_THREADS,"Forking thread: %s\n",name);
488 #endif // UW
489
490 newthread = thread_create(name);
491 if (newthread == NULL) {
492 return ENOMEM;
493 }
494
495 /* Allocate a stack */
496 newthread->t_stack = kmalloc(STACK_SIZE);
497 if (newthread->t_stack == NULL) {
498 thread_destroy(newthread);
499 return ENOMEM;
500 }
501 thread_checkstack_init(newthread);
502
503 /*
504 * Now we clone various fields from the parent thread.
505 */
506
507 /* Thread subsystem fields */
508 newthread->t_cpu = curthread->t_cpu;
509
510 /* Attach the new thread to its process */
511 if (proc == NULL) {
512 proc = curthread->t_proc;
513 }
514 result = proc_addthread(proc, newthread);
515 if (result) {
516 /* thread_destroy will clean up the stack */
517 thread_destroy(newthread);
518 return result;
519 }
520
521 /*
522 * Because new threads come out holding the cpu runqueue lock
523 * (see notes at bottom of thread_switch), we need to account
524 * for the spllower() that will be done releasing it.
525 */
526 newthread->t_iplhigh_count++;
527
528 /* Set up the switchframe so entrypoint() gets called */
529 switchframe_init(newthread, entrypoint, data1, data2);
530
531 /* Lock the current cpu's run queue and make the new thread runnable */
532 thread_make_runnable(newthread, false);
533
534 return 0;
535 }
536
537 /*
538 * High level, machine-independent context switch code.
539 *
540 * The current thread is queued appropriately and its state is changed
541 * to NEWSTATE; another thread to run is selected and switched to.
542 *
543 * If NEWSTATE is S_SLEEP, the thread is queued on the wait channel
544 * WC. Otherwise WC should be NULL.
545 */
546 static
547 void
548 thread_switch(threadstate_t newstate, struct wchan *wc)
549 {
550 struct thread *cur, *next;
551 int spl;
552
553 DEBUGASSERT(curcpu->c_curthread == curthread);
554 DEBUGASSERT(curthread->t_cpu == curcpu->c_self);
555
556 /* Explicitly disable interrupts on this processor */
557 spl = splhigh();
558
559 cur = curthread;
560
561 /*
562 * If we're idle, return without doing anything. This happens
563 * when the timer interrupt interrupts the idle loop.
564 */
565 if (curcpu->c_isidle) {
566 splx(spl);
567 return;
568 }
569
570 /* Check the stack guard band. */
571 thread_checkstack(cur);
572
573 /* Lock the run queue. */
574 spinlock_acquire(&curcpu->c_runqueue_lock);
575
576 /* Micro-optimization: if nothing to do, just return */
577 if (newstate == S_READY && threadlist_isempty(&curcpu->c_runqueue)) {
578 spinlock_release(&curcpu->c_runqueue_lock);
579 splx(spl);
580 return;
581 }
582
583 /* Put the thread in the right place. */
584 switch (newstate) {
585 case S_RUN:
586 panic("Illegal S_RUN in thread_switch\n");
587 case S_READY:
588 thread_make_runnable(cur, true /*have lock*/);
589 break;
590 case S_SLEEP:
591 cur->t_wchan_name = wc->wc_name;
592 /*
593 * Add the thread to the list in the wait channel, and
594 * unlock same. To avoid a race with someone else
595 * calling wchan_wake*, we must keep the wchan locked
596 * from the point the caller of wchan_sleep locked it
597 * until the thread is on the list.
598 *
599 * (We could for symmetry relock the channel before
600 * returning from wchan_sleep, but we don't, for two
601 * reasons. One is that the caller is unlikely to need
602 * or want it locked and if it does can lock it itself
603 * without racing. Exercise: what's the other?)
604 */
605 threadlist_addtail(&wc->wc_threads, cur);
606 wchan_unlock(wc);
607 break;
608 case S_ZOMBIE:
609 cur->t_wchan_name = "ZOMBIE";
610 threadlist_addtail(&curcpu->c_zombies, cur);
611 break;
612 }
613 cur->t_state = newstate;
614
615 /*
616 * Get the next thread. While there isn't one, call md_idle().
617 * curcpu->c_isidle must be true when md_idle is
618 * called. Unlock the runqueue while idling too, to make sure
619 * things can be added to it.
620 *
621 * Note that we don't need to unlock the runqueue atomically
622 * with idling; becoming unidle requires receiving an
623 * interrupt (either a hardware interrupt or an interprocessor
624 * interrupt from another cpu posting a wakeup) and idling
625 * *is* atomic with respect to re-enabling interrupts.
626 *
627 * Note that c_isidle becomes true briefly even if we don't go
628 * idle. However, because one is supposed to hold the runqueue
629 * lock to look at it, this should not be visible or matter.
630 */
631
632 /* The current cpu is now idle. */
633 curcpu->c_isidle = true;
634 do {
635 next = threadlist_remhead(&curcpu->c_runqueue);
636 if (next == NULL) {
637 spinlock_release(&curcpu->c_runqueue_lock);
638 cpu_idle();
639 spinlock_acquire(&curcpu->c_runqueue_lock);
640 }
641 } while (next == NULL);
642 curcpu->c_isidle = false;
643
644 /*
645 * Note that curcpu->c_curthread may be the same variable as
646 * curthread and it may not be, depending on how curthread and
647 * curcpu are defined by the MD code. We'll assign both and
648 * assume the compiler will optimize one away if they're the
649 * same.
650 */
651 curcpu->c_curthread = next;
652 curthread = next;
653
654 /* do the switch (in assembler in switch.S) */
655 switchframe_switch(&cur->t_context, &next->t_context);
656
657 /*
658 * When we get to this point we are either running in the next
659 * thread, or have come back to the same thread again,
660 * depending on how you look at it. That is,
661 * switchframe_switch returns immediately in another thread
662 * context, which in general will be executing here with a
663 * different stack and different values in the local
664 * variables. (Although new threads go to thread_startup
665 * instead.) But, later on when the processor, or some
666 * processor, comes back to the previous thread, it's also
667 * executing here with the *same* value in the local
668 * variables.
669 *
670 * The upshot, however, is as follows:
671 *
672 * - The thread now currently running is "cur", not "next",
673 * because when we return from switchrame_switch on the
674 * same stack, we're back to the thread that
675 * switchframe_switch call switched away from, which is
676 * "cur".
677 *
678 * - "cur" is _not_ the thread that just *called*
679 * switchframe_switch.
680 *
681 * - If newstate is S_ZOMB we never get back here in that
682 * context at all.
683 *
684 * - If the thread just chosen to run ("next") was a new
685 * thread, we don't get to this code again until
686 * *another* context switch happens, because when new
687 * threads return from switchframe_switch they teleport
688 * to thread_startup.
689 *
690 * - At this point the thread whose stack we're now on may
691 * have been migrated to another cpu since it last ran.
692 *
693 * The above is inherently confusing and will probably take a
694 * while to get used to.
695 *
696 * However, the important part is that code placed here, after
697 * the call to switchframe_switch, does not necessarily run on
698 * every context switch. Thus any such code must be either
699 * skippable on some switches or also called from
700 * thread_startup.
701 */
702
703
704 /* Clear the wait channel and set the thread state. */
705 cur->t_wchan_name = NULL;
706 cur->t_state = S_RUN;
707
708 /* Unlock the run queue. */
709 spinlock_release(&curcpu->c_runqueue_lock);
710
711 /* Activate our address space in the MMU. */
712 as_activate();
713
714 /* Clean up dead threads. */
715 exorcise();
716
717 /* Turn interrupts back on. */
718 splx(spl);
719 }
720
721 /*
722 * This function is where new threads start running. The arguments
723 * ENTRYPOINT, DATA1, and DATA2 are passed through from thread_fork.
724 *
725 * Because new code comes here from inside the middle of
726 * thread_switch, the beginning part of this function must match the
727 * tail of thread_switch.
728 */
729 void
730 thread_startup(void (*entrypoint)(void *data1, unsigned long data2),
731 void *data1, unsigned long data2)
732 {
733 struct thread *cur;
734
735 cur = curthread;
736
737 /* Clear the wait channel and set the thread state. */
738 cur->t_wchan_name = NULL;
739 cur->t_state = S_RUN;
740
741 /* Release the runqueue lock acquired in thread_switch. */
742 spinlock_release(&curcpu->c_runqueue_lock);
743
744 /* Activate our address space in the MMU. */
745 as_activate();
746
747 /* Clean up dead threads. */
748 exorcise();
749
750 /* Enable interrupts. */
751 spl0();
752
753 #if OPT_SYNCHPROBS
754 /* Yield a random number of times to get a good mix of threads. */
755 {
756 int i, n;
757 n = random()%161 + random()%161;
758 for (i=0; i<n; i++) {
759 thread_yield();
760 }
761 }
762 #endif
763
764 /* Call the function. */
765 entrypoint(data1, data2);
766
767 /* Done. */
768 thread_exit();
769 }
770
771 /*
772 * Cause the current thread to exit.
773 *
774 * The parts of the thread structure we don't actually need to run
775 * should be cleaned up right away. The rest has to wait until
776 * thread_destroy is called from exorcise().
777 *
778 * Does not return.
779 */
780 void
781 thread_exit(void)
782 {
783 struct thread *cur;
784
785 cur = curthread;
786
787 #ifdef UW
788 /* threads for user processes should have detached from their process
789 in sys__exit */
790 KASSERT(curproc == kproc || curproc == NULL);
791 /* kernel threads don't go through sys__exit, so we detach them from kproc here */
792 if (curproc == kproc) {
793 proc_remthread(cur);
794 }
795 #else // UW
796 proc_remthread(cur);
797 #endif // UW
798
799 /* Make sure we *are* detached (move this only if you're sure!) */
800 KASSERT(cur->t_proc == NULL);
801
802 /* Check the stack guard band. */
803 thread_checkstack(cur);
804
805 /* Interrupts off on this processor */
806 splhigh();
807 thread_switch(S_ZOMBIE, NULL);
808 panic("The zombie walks!\n");
809 }
810
811 /*
812 * Yield the cpu to another process, but stay runnable.
813 */
814 void
815 thread_yield(void)
816 {
817 thread_switch(S_READY, NULL);
818 }
819
820 ////////////////////////////////////////////////////////////
821
822 /*
823 * Scheduler.
824 *
825 * This is called periodically from hardclock(). It should reshuffle
826 * the current CPU's run queue by job priority.
827 */
828
829 void
830 schedule(void)
831 {
832 /*
833 * You can write this. If we do nothing, threads will run in
834 * round-robin fashion.
835 */
836 }
837
838 /*
839 * Thread migration.
840 *
841 * This is also called periodically from hardclock(). If the current
842 * CPU is busy and other CPUs are idle, or less busy, it should move
843 * threads across to those other other CPUs.
844 *
845 * Migrating threads isn't free because of cache affinity; a thread's
846 * working cache set will end up having to be moved to the other CPU,
847 * which is fairly slow. The tradeoff between this performance loss
848 * and the performance loss due to underutilization of some CPUs is
849 * something that needs to be tuned and probably is workload-specific.
850 *
851 * For here and now, because we know we're running on System/161 and
852 * System/161 does not (yet) model such cache effects, we'll be very
853 * aggressive.
854 */
855 void
856 thread_consider_migration(void)
857 {
858 unsigned my_count, total_count, one_share, to_send;
859 unsigned i, numcpus;
860 struct cpu *c;
861 struct threadlist victims;
862 struct thread *t;
863
864 my_count = total_count = 0;
865 numcpus = cpuarray_num(&allcpus);
866 for (i=0; i<numcpus; i++) {
867 c = cpuarray_get(&allcpus, i);
868 spinlock_acquire(&c->c_runqueue_lock);
869 total_count += c->c_runqueue.tl_count;
870 if (c == curcpu->c_self) {
871 my_count = c->c_runqueue.tl_count;
872 }
873 spinlock_release(&c->c_runqueue_lock);
874 }
875
876 one_share = DIVROUNDUP(total_count, numcpus);
877 if (my_count < one_share) {
878 return;
879 }
880
881 to_send = my_count - one_share;
882 threadlist_init(&victims);
883 spinlock_acquire(&curcpu->c_runqueue_lock);
884 for (i=0; i<to_send; i++) {
885 t = threadlist_remtail(&curcpu->c_runqueue);
886 threadlist_addhead(&victims, t);
887 }
888 spinlock_release(&curcpu->c_runqueue_lock);
889
890 for (i=0; i < numcpus && to_send > 0; i++) {
891 c = cpuarray_get(&allcpus, i);
892 if (c == curcpu->c_self) {
893 continue;
894 }
895 spinlock_acquire(&c->c_runqueue_lock);
896 while (c->c_runqueue.tl_count < one_share && to_send > 0) {
897 t = threadlist_remhead(&victims);
898 /*
899 * Ordinarily, curthread will not appear on
900 * the run queue. However, it can under the
901 * following circumstances:
902 * - it went to sleep;
903 * - the processor became idle, so it
904 * remained curthread;
905 * - it was reawakened, so it was put on the
906 * run queue;
907 * - and the processor hasn't fully unidled
908 * yet, so all these things are still true.
909 *
910 * If the timer interrupt happens at (almost)
911 * exactly the proper moment, we can come here
912 * while things are in this state and see
913 * curthread. However, *migrating* curthread
914 * can cause bad things to happen (Exercise:
915 * Why? And what?) so shuffle it to the end of
916 * the list and decrement to_send in order to
917 * skip it. Then it goes back on our own run
918 * queue below.
919 */
920 if (t == curthread) {
921 threadlist_addtail(&victims, t);
922 to_send--;
923 continue;
924 }
925
926 t->t_cpu = c;
927 threadlist_addtail(&c->c_runqueue, t);
928 DEBUG(DB_THREADS,
929 "Migrated thread %s: cpu %u -> %u",
930 t->t_name, curcpu->c_number, c->c_number);
931 to_send--;
932 if (c->c_isidle) {
933 /*
934 * Other processor is idle; send
935 * interrupt to make sure it unidles.
936 */
937 ipi_send(c, IPI_UNIDLE);
938 }
939 }
940 spinlock_release(&c->c_runqueue_lock);
941 }
942
943 /*
944 * Because the code above isn't atomic, the thread counts may have
945 * changed while we were working and we may end up with leftovers.
946 * Don't panic; just put them back on our own run queue.
947 */
948 if (!threadlist_isempty(&victims)) {
949 spinlock_acquire(&curcpu->c_runqueue_lock);
950 while ((t = threadlist_remhead(&victims)) != NULL) {
951 threadlist_addtail(&curcpu->c_runqueue, t);
952 }
953 spinlock_release(&curcpu->c_runqueue_lock);
954 }
955
956 KASSERT(threadlist_isempty(&victims));
957 threadlist_cleanup(&victims);
958 }
959
960 ////////////////////////////////////////////////////////////
961
962 /*
963 * Wait channel functions
964 */
965
966 /*
967 * Create a wait channel. NAME is a symbolic string name for it.
968 * This is what's displayed by ps -alx in Unix.
969 *
970 * NAME should generally be a string constant. If it isn't, alternate
971 * arrangements should be made to free it after the wait channel is
972 * destroyed.
973 */
974 struct wchan *
975 wchan_create(const char *name)
976 {
977 struct wchan *wc;
978
979 wc = kmalloc(sizeof(*wc));
980 if (wc == NULL) {
981 return NULL;
982 }
983 spinlock_init(&wc->wc_lock);
984 threadlist_init(&wc->wc_threads);
985 wc->wc_name = name;
986 return wc;
987 }
988
989 /*
990 * Destroy a wait channel. Must be empty and unlocked.
991 * (The corresponding cleanup functions require this.)
992 */
993 void
994 wchan_destroy(struct wchan *wc)
995 {
996 spinlock_cleanup(&wc->wc_lock);
997 threadlist_cleanup(&wc->wc_threads);
998 kfree(wc);
999 }
1000
1001 /*
1002 * Lock and unlock a wait channel, respectively.
1003 */
1004 void
1005 wchan_lock(struct wchan *wc)
1006 {
1007 spinlock_acquire(&wc->wc_lock);
1008 }
1009
1010 void
1011 wchan_unlock(struct wchan *wc)
1012 {
1013 spinlock_release(&wc->wc_lock);
1014 }
1015
1016 /*
1017 * Yield the cpu to another process, and go to sleep, on the specified
1018 * wait channel WC. Calling wakeup on the channel will make the thread
1019 * runnable again. The channel must be locked, and will be *unlocked*
1020 * upon return.
1021 */
1022 void
1023 wchan_sleep(struct wchan *wc)
1024 {
1025 /* may not sleep in an interrupt handler */
1026 KASSERT(!curthread->t_in_interrupt);
1027
1028 thread_switch(S_SLEEP, wc);
1029 }
1030
1031 /*
1032 * Wake up one thread sleeping on a wait channel.
1033 */
1034 void
1035 wchan_wakeone(struct wchan *wc)
1036 {
1037 struct thread *target;
1038
1039 /* Lock the channel and grab a thread from it */
1040 spinlock_acquire(&wc->wc_lock);
1041 target = threadlist_remhead(&wc->wc_threads);
1042 /*
1043 * Nobody else can wake up this thread now, so we don't need
1044 * to hang onto the lock.
1045 */
1046 spinlock_release(&wc->wc_lock);
1047
1048 if (target == NULL) {
1049 /* Nobody was sleeping. */
1050 return;
1051 }
1052
1053 thread_make_runnable(target, false);
1054 }
1055
1056 /*
1057 * Wake up all threads sleeping on a wait channel.
1058 */
1059 void
1060 wchan_wakeall(struct wchan *wc)
1061 {
1062 struct thread *target;
1063 struct threadlist list;
1064
1065 threadlist_init(&list);
1066
1067 /*
1068 * Lock the channel and grab all the threads, moving them to a
1069 * private list.
1070 */
1071 spinlock_acquire(&wc->wc_lock);
1072 while ((target = threadlist_remhead(&wc->wc_threads)) != NULL) {
1073 threadlist_addtail(&list, target);
1074 }
1075 /*
1076 * Nobody else can wake up these threads now, so we don't need
1077 * to hang onto the lock.
1078 */
1079 spinlock_release(&wc->wc_lock);
1080
1081 /*
1082 * We could conceivably sort by cpu first to cause fewer lock
1083 * ops and fewer IPIs, but for now at least don't bother. Just
1084 * make each thread runnable.
1085 */
1086 while ((target = threadlist_remhead(&list)) != NULL) {
1087 thread_make_runnable(target, false);
1088 }
1089
1090 threadlist_cleanup(&list);
1091 }
1092
1093 /*
1094 * Return nonzero if there are no threads sleeping on the channel.
1095 * This is meant to be used only for diagnostic purposes.
1096 */
1097 bool
1098 wchan_isempty(struct wchan *wc)
1099 {
1100 bool ret;
1101
1102 spinlock_acquire(&wc->wc_lock);
1103 ret = threadlist_isempty(&wc->wc_threads);
1104 spinlock_release(&wc->wc_lock);
1105
1106 return ret;
1107 }
1108
1109 ////////////////////////////////////////////////////////////
1110
1111 /*
1112 * Machine-independent IPI handling
1113 */
1114
1115 /*
1116 * Send an IPI (inter-processor interrupt) to the specified CPU.
1117 */
1118 void
1119 ipi_send(struct cpu *target, int code)
1120 {
1121 KASSERT(code >= 0 && code < 32);
1122
1123 spinlock_acquire(&target->c_ipi_lock);
1124 target->c_ipi_pending |= (uint32_t)1 << code;
1125 mainbus_send_ipi(target);
1126 spinlock_release(&target->c_ipi_lock);
1127 }
1128
1129 void
1130 ipi_broadcast(int code)
1131 {
1132 unsigned i;
1133 struct cpu *c;
1134
1135 for (i=0; i < cpuarray_num(&allcpus); i++) {
1136 c = cpuarray_get(&allcpus, i);
1137 if (c != curcpu->c_self) {
1138 ipi_send(c, code);
1139 }
1140 }
1141 }
1142
1143 void
1144 ipi_tlbshootdown(struct cpu *target, const struct tlbshootdown *mapping)
1145 {
1146 int n;
1147
1148 spinlock_acquire(&target->c_ipi_lock);
1149
1150 n = target->c_numshootdown;
1151 if (n == TLBSHOOTDOWN_MAX) {
1152 target->c_numshootdown = TLBSHOOTDOWN_ALL;
1153 }
1154 else {
1155 target->c_shootdown[n] = *mapping;
1156 target->c_numshootdown = n+1;
1157 }
1158
1159 target->c_ipi_pending |= (uint32_t)1 << IPI_TLBSHOOTDOWN;
1160 mainbus_send_ipi(target);
1161
1162 spinlock_release(&target->c_ipi_lock);
1163 }
1164
1165 void
1166 interprocessor_interrupt(void)
1167 {
1168 uint32_t bits;
1169 int i;
1170
1171 spinlock_acquire(&curcpu->c_ipi_lock);
1172 bits = curcpu->c_ipi_pending;
1173
1174 if (bits & (1U << IPI_PANIC)) {
1175 /* panic on another cpu - just stop dead */
1176 cpu_halt();
1177 }
1178 if (bits & (1U << IPI_OFFLINE)) {
1179 /* offline request */
1180 spinlock_acquire(&curcpu->c_runqueue_lock);
1181 if (!curcpu->c_isidle) {
1182 kprintf("cpu%d: offline: warning: not idle\n",
1183 curcpu->c_number);
1184 }
1185 spinlock_release(&curcpu->c_runqueue_lock);
1186 kprintf("cpu%d: offline.\n", curcpu->c_number);
1187 cpu_halt();
1188 }
1189 if (bits & (1U << IPI_UNIDLE)) {
1190 /*
1191 * The cpu has already unidled itself to take the
1192 * interrupt; don't need to do anything else.
1193 */
1194 }
1195 if (bits & (1U << IPI_TLBSHOOTDOWN)) {
1196 if (curcpu->c_numshootdown == TLBSHOOTDOWN_ALL) {
1197 vm_tlbshootdown_all();
1198 }
1199 else {
1200 for (i=0; i<curcpu->c_numshootdown; i++) {
1201 vm_tlbshootdown(&curcpu->c_shootdown[i]);
1202 }
1203 }
1204 curcpu->c_numshootdown = 0;
1205 }
1206
1207 curcpu->c_ipi_pending = 0;
1208 spinlock_release(&curcpu->c_ipi_lock);
1209 }