1 /*
2 * Copyright (c) 2013-2023 Ali Mashtizadeh
3 * All rights reserved.
4 */
5
6 #include <stdbool.h>
7 #include <stdint.h>
8 #include <string.h>
9
10 #include <errno.h>
11 #include <sys/syscall.h>
12
13 #include <sys/kassert.h>
14 #include <sys/kconfig.h>
15 #include <sys/kdebug.h>
16 #include <sys/kmem.h>
17 #include <sys/ktime.h>
18 #include <sys/mp.h>
19 #include <sys/spinlock.h>
20 #include <sys/thread.h>
21
22 #include <machine/trap.h>
23 #include <machine/pmap.h>
24
25 // Scheduler Queues
26 /**
27 * Scheduler lock that protects all queues.
28 */
29 Spinlock schedLock;
30 /**
31 * All threads currently waiting.
32 */
33 ThreadQueue waitQueue;
34 /**
35 * All runnable threads.
36 */
37 ThreadQueue runnableQueue;
38 /**
39 * Current thread executing on a given CPU.
40 */
41 Thread *curProc[MAX_CPUS];
42
43 /*
44 * Scheduler Functions
45 */
46
47 /**
48 * Sched_Current() --
49 *
50 * Get the currently executing thread. This function retains a reference count
51 * and you must release the reference by calling Thread_Release.
52 *
53 * @return Returns the current thread.
54 */
55 Thread *
Sched_Current()56 Sched_Current()
57 {
58 Spinlock_Lock(&schedLock);
59
60 Thread *thr = curProc[CPU()];
61 Thread_Retain(thr);
62
63 Spinlock_Unlock(&schedLock);
64
65 return thr;
66 }
67
68 /**
69 * Sched_SetRunnable --
70 *
71 * Set the thread to the runnable state and move it from the wait queue if
72 * necessary to the runnable queue.
73 *
74 * @param [in] thr Thread to be set as runnable.
75 */
76 void
Sched_SetRunnable(Thread * thr)77 Sched_SetRunnable(Thread *thr)
78 {
79 Spinlock_Lock(&schedLock);
80
81 if (thr->proc->procState == PROC_STATE_NULL)
82 thr->proc->procState = PROC_STATE_READY;
83
84 if (thr->schedState == SCHED_STATE_WAITING) {
85 thr->waitTime += KTime_GetEpochNS() - thr->waitStart;
86 thr->waitStart = 0;
87 TAILQ_REMOVE(&waitQueue, thr, schedQueue);
88 }
89 thr->schedState = SCHED_STATE_RUNNABLE;
90 TAILQ_INSERT_TAIL(&runnableQueue, thr, schedQueue);
91
92 Spinlock_Unlock(&schedLock);
93 }
94
95 /**
96 * Sched_SetWaiting --
97 *
98 * Set the thread to the waiting state and move it to the wait queue. The
99 * thread should be currently running.
100 *
101 * @param [in] thr Thread to be set as waiting.
102 */
103 void
Sched_SetWaiting(Thread * thr)104 Sched_SetWaiting(Thread *thr)
105 {
106 Spinlock_Lock(&schedLock);
107
108 ASSERT(thr->schedState == SCHED_STATE_RUNNING);
109
110 thr->schedState = SCHED_STATE_WAITING;
111 TAILQ_INSERT_TAIL(&waitQueue, thr, schedQueue);
112 thr->waitStart = KTime_GetEpochNS();
113
114 Spinlock_Unlock(&schedLock);
115 }
116
117 /**
118 * Sched_SetZombie --
119 *
120 * Set the thread to the zombie state and move it to the parent processes's
121 * zombie process queue. The thread should be currently running.
122 *
123 * @param [in] thr Thread to be set as zombie.
124 */
125 void
Sched_SetZombie(Thread * thr)126 Sched_SetZombie(Thread *thr)
127 {
128 Process *proc = thr->proc;
129
130 /*
131 * Do not go to sleep holding spinlocks.
132 */
133 ASSERT(Critical_Level() == 0);
134
135 if (proc->threads == 1) {
136 // All processes have parents except 'init' and 'kernel'
137 ASSERT(proc->parent != NULL);
138 Mutex_Lock(&proc->parent->zombieProcLock);
139 Spinlock_Lock(&proc->parent->lock); // Guards child list
140 proc->procState = PROC_STATE_ZOMBIE;
141 TAILQ_REMOVE(&proc->parent->childrenList, proc, siblingList);
142 TAILQ_INSERT_TAIL(&proc->parent->zombieProc, proc, siblingList);
143 Spinlock_Unlock(&proc->parent->lock);
144 CV_Signal(&proc->zombieProcPCV);
145 CV_Signal(&proc->parent->zombieProcCV);
146 }
147
148 /*
149 * Set as zombie just before releasing the zombieProcLock in case we had to
150 * sleep to acquire the zombieProcLock.
151 */
152 Spinlock_Lock(&schedLock);
153 thr->schedState = SCHED_STATE_ZOMBIE;
154 Spinlock_Unlock(&schedLock);
155
156 Spinlock_Lock(&proc->lock);
157 TAILQ_INSERT_TAIL(&proc->zombieQueue, thr, schedQueue);
158 Spinlock_Unlock(&proc->lock);
159
160 if (proc->threads == 1)
161 Mutex_Unlock(&proc->parent->zombieProcLock);
162 }
163
164 /**
165 * Sched_Switch --
166 *
167 * Switch between threads. During the creation of kernel threads (and by proxy
168 * user threads) we may not return through this code path and thus the kernel
169 * thread initialization function must release the scheduler lock.
170 *
171 * @param [in] oldthr Current thread we are switching from.
172 * @param [in] newthr Thread to switch to.
173 */
174 static void
Sched_Switch(Thread * oldthr,Thread * newthr)175 Sched_Switch(Thread *oldthr, Thread *newthr)
176 {
177 // Load AS
178 PMap_LoadAS(newthr->space);
179
180 Thread_SwitchArch(oldthr, newthr);
181 }
182
183 /**
184 * Sched_Scheduler --
185 *
186 * Run our round robin scheduler to find the process and switch to it.
187 */
188 void
Sched_Scheduler()189 Sched_Scheduler()
190 {
191 Thread *prev;
192 Thread *next;
193
194 Spinlock_Lock(&schedLock);
195
196 // Select next thread
197 next = TAILQ_FIRST(&runnableQueue);
198 if (!next) {
199 /*
200 * There may be no other runnable processes on this core. This is a
201 * good opportunity to migrate threads. We should never hit this case
202 * once the OS is up and running because of the idle threads, but just
203 * in case we should assert that we never return to a zombie or waiting
204 * thread.
205 */
206 ASSERT(curProc[CPU()]->schedState == SCHED_STATE_RUNNING);
207 Spinlock_Unlock(&schedLock);
208 return;
209 }
210 ASSERT(next->schedState == SCHED_STATE_RUNNABLE);
211 TAILQ_REMOVE(&runnableQueue, next, schedQueue);
212
213 prev = curProc[CPU()];
214 curProc[CPU()] = next;
215 next->schedState = SCHED_STATE_RUNNING;
216 next->ctxSwitches++;
217
218 if (prev->schedState == SCHED_STATE_RUNNING) {
219 prev->schedState = SCHED_STATE_RUNNABLE;
220 TAILQ_INSERT_TAIL(&runnableQueue, prev, schedQueue);
221 }
222
223 Sched_Switch(prev, next);
224
225 Spinlock_Unlock(&schedLock);
226 }
227
228