Kthread infrastructure
[akaros.git] / Documentation / kthreads.txt
1 kthreads.txt
2 Barret Rhoden
3
4 What Are They, And Why?
5 -------------------------------
6 Eventually a thread of execution in the kernel will want to block.  This means
7 that the thread is unable to make forward progress and something else ought
8 to run - the common case for this is when we wait on an IO operation.  This gets
9 trickier when a function does not know if a function it calls will block or not.
10 Sometimes they do, sometimes they don't.
11
12 The critical feature is not that we want to save the registers, but that we want
13 to preserve the stack and be able to use it independently of whatever else we do
14 on that core in the interim time.  If we knew we would be done with and return
15 from whatever_else() before we needed to continue the current thread of
16 execution, we could simply call the function.  Instead, we want to be able to
17 run the old context independently of what else is running (which may be a
18 process). 
19
20 We call this suspended context and the associated information a kthread, managed
21 by a struct kthread.  It's the bare minimum needed for the kernel to stop and
22 restart a thread of execution.  It holds the registers, stack pointer, PC,
23 struct proc* if applicable, stacktop, and little else.  There is no silly_state
24 / floating point state, or anything else.  Its address space is determined from
25 which process context (possibly none) that was running.
26
27 We also get a few other benefits, such as the ability to pick and choose which
28 kthreads to run where and when.  Users of kthreads should not assume that the
29 core_id() stayed the same across function calls.  
30
31 We can also use this infrastructure of other cases where we might want to start
32 on a new stack.  One example is when we deal with low memory.  We may have to do
33 a lot of work, but only need to do a little to allow the original thread (that
34 might have failed on a page_alloc) to keep running, while we want the memory
35 freer to keep running too (or later) from where it left off.  In essence, we
36 want to fork, work, and yield or run on another core.  The kthread is just a
37 means of suspending a call stack and a context for a little while.
38
39 Side Note:
40 -----------
41 Right now, blocking a kthread is an explicit action.  Some function realizes it
42 can't make progress (like waiting on a block device), so it sleeps on something
43 (for now a semaphore), and gets woken up when it receives its signal.  This
44 differs from processes, which can be stopped and suspended at any moment
45 (pagefault is the classic example).  In the future, we could make kthreads be
46 preemptable (timer interrupt goes off, and we choose to suspend a kthread), but
47 even then kthreads still have the ability to turn off interrupts for tricky
48 situations (like suspending the kthread).  The analog in the process code is
49 disabling notifications, which dramatically complicates its functions (compare
50 the save and pop functions for _ros_tf and _kernel_tf).  Furthermore, when a
51 process disables notifications, it still doesn't mean it is running without
52 interruptions (it looks like that to the vcore).  When the kernel disables
53 interrupts, it really is running.
54
55 What About Events?
56 -------------------------------
57 Why not just be event driven for all IO?  Why do we need these kernel threads?
58 In short, IO isn't as simple as "I just want a block and when it's done, run a
59 function."  While that is what the block device driver will do, the subsystems
60 actually needing the IO are much simpler if they are threaded.  Consider the
61 potentially numerous blocking IO calls involved in opening a file.  Having a
62 continuation for each one of those points in the call graph seems like a real
63 pain to code.  Perhaps I'm not seeing it, but if you're looking for a simple,
64 light mechanism for keeping track of what work you need to do, just use a stack.
65 Programming is much simpler, and it costs a page plus a small data structure.
66
67 Note that this doesn't mean that all IO needs to use kthreads, just that some
68 will really benefit from it.  I plan to make the "last part" of some IO calls
69 more event driven.  Basically, it's all just a toolbox, and you should use what
70 you need.
71
72 Freeing Stacks and Structs
73 -------------------------------
74 When we restart a kthread, we have to be careful about freeing the old stack and
75 the struct kthread.  We need to delay the freeing of both of these until after
76 we pop_kernel_tf().  We can't free the kthread before popping it, and we are on
77 the stack we need to free (until we pop to the new stack).
78
79 To deal with this, we have a "spare" kthread per core, which gets assigned as
80 the spare when we restart a previous kthread.  When making/suspending a kthread,
81 we'll use this spare.  When restarting one, we'll free the old spare if it
82 exists and put ours there.  One drawback is that we potentially waste a chunk of
83 memory (1 page + a bit per core, worst case), but it is a nice, simple solution.
84 Also, it will cut down on contention for free pages and the kthread_kcache,
85 though this won't help with serious contention issues (which we'll deal with
86 eventually).
87
88 What To Run Next?
89 -------------------------------
90 When a kthread suspends, what do we run next?  And how do we know what to run
91 next?  For now, we call smp_idle() - it is what you do when you have nothing
92 else to do, or don't know what to do.  We could consider having sleep_on() take
93 a function pointer, but when we start hopping stacks, passing that info gets
94 tricky.  And we need to make a decision about which function to call quickly (in
95 the code.  I don't trust the compiler much).  We can store the function pointer
96 at the bottom of the future stack and extract it from there.  Or we could put it
97 in per_cpu_info.  Or we can send ourselves a routine kernel message.
98
99 Regardless of where we put it, we ought to call smp_idle() (or something
100 similar) before calling it, since we need to make sure that whatever we call
101 right after jumping stacks never returns.  It's more flexible to allow a
102 function that returns for the func *, so we'll use smp_idle() as a level of
103 indirection.
104
105 Semaphore Stuff
106 -------------------------------
107 We use the semaphore (defined in kthread.h) for kthreads to sleep on and wait
108 for a signal.  It is possible that the signal wins the race and beats the call
109 to sleep_on().  The semaphore handles this by "returning false."  You'll notice
110 that we don't actually call __down_sem(), but instead "build it in" to
111 sleep_on().  I didn't want to deal with returning a bool (even if it was an
112 inline), because I want to minimize the amount of stuff we do with potential
113 stack variables (I don't trust the register variable).  As soon as we unlock,
114 the kthread could be restarted (in theory), and it could start to clobber the
115 stack in later function calls.
116
117 So it is possible that we lose the semaphore race and shouldn't sleep.  We unwind the
118 sleep prep work.  An alternative was to only do the prep work if we won the
119 race, but that would mean we have to do a lot of work in that delicate period of
120 "I'm on the queue but it is unlocked" - work that requires touching the stack.
121 Or we could just hold the lock for a longer period of time, which I don't care
122 to do.
123
124 Note that a lot of this is probably needless worry - we have interrupts disabled
125 for most of sleep_on(), though arguably we can be a little more careful with
126 pcpui->spare and move the disable_irq() down to right before save_kernel_tf().
127
128 What's the Deal with Stacks/Stacktops?
129 -------------------------------
130 When the kernel traps from userspace, it needs to know what to set the kernel
131 stack pointer to.  In x86, it looks in the TSS.  In sparc, we have a data
132 structure tracking that info (core_stacktops).  One thing I considered was
133 migrating the kernel from its boot stacks (x86, just core0, sparc, all the cores
134 have one).  Instead, we just make sure the tables/TSS are up to date right away
135 (before interrupts or traps can come in for x86, and right away for sparc).
136 These boot stacks aren't particularly special, just note they are in the program
137 data/bss sections and were never originally added to a free list.  But they can
138 be freed later on.  This might be an issue in some places, but those places
139 ought to be fixed.
140
141 There is also some implications about PGSIZE stacks (specifically in the
142 asserts, how we alloc only one page, etc).  The bootstacks are bigger than a
143 page (for now), but in general we don't want to have giant stacks (and shouldn't
144 need them - note linux runs with 4KB stacks).  In the future (long range, when
145 we're 64 bit), I'd like to put all kernel stacks high in the address space, with
146 guard pages after them.  This would require a certain "quiet migration" to the
147 new locations for the bootstacks (though not a new page - just a different
148 virtual address for the stacks (not their page-alloced KVA).  A bunch of minor
149 things would need to change for that, so don't hold your breath.
150
151 So what about stacktop?  It's just the top of the stack, but sometimes it is the
152 stack we were on (when suspending the kthread), other times kthread->stacktop
153 is just a scrap page's top.
154
155 What's important when suspending is that the current stack is not
156 used in future traps - that it doesn't get clobbered.  That's why we need to
157 find a new stack and set it as the current stacktop.  We also need to 'save'
158 the stack page of the old kthread - we don't want it to be freed, since we
159 need it later. When starting a kthread, I don't particularly care about which
160 stack is now the default stack.  The sleep_on() assumes it was the kthread's,
161 so unless we always have a default one that is only used very briefly and
162 never blocked on, (which requires a stack jump), we ought to just have a
163 kthread run with its stack as the default stacktop.
164
165 When restarting a kthread, we eventually will use its stack, instead of the
166 current one, but we can't free the current stack until after we actually
167 pop_kernel_tf().  this is the same problem as with the struct kthread dealloc.
168 So we can have the kthread (which we want to free later) hold on to the page we
169 wanted to dealloc.  Likewise, when we would need a fresh kthread, we also need a
170 page to use as the default stacktop.  So if we had a cached kthread, we then use
171 the page that kthread was pointing to.  NOTE: the spare kthread struct is not
172 holding the stack it was originally saved with.  Instead, it is saving the page
173 of the stack that was running when that kthread was reactivated.  It's spare
174 storage for both the struct and the page, but they aren't linked in any
175 meaningful way (like it is the stack of the page).  That linkage is only true
176 when a kthread is being used (like in a semaphore queue).
177
178 Current and Process Contexts
179 -------------------------------
180 When a kthread is suspended, should the core stay in process context (if it was
181 before)?  Short answer: yes.
182
183 For vcore local calls (process context, trapped on the calling core), we're
184 giving the core back, so we can avoid TLB shootdowns.  Though we do have to
185 incref (which writes a cache line in the proc struct), since we are storing a
186 reference to the proc (and will try to load its cr3 later).  While this sucks,
187 keep in mind this is for a blocking IO call (where we couldn't find the page in
188 any cache, etc).  It might be a scalability bottleneck, but it also might not
189 matter in any real case.
190
191 For async calls, it is less clear.  We might want to keep processing that
192 process's syscalls, so it'd be easier to keep its cr3 loaded.  Though it's not
193 as clear how we get from smp_idle() to a workable function and if it is useful
194 to be in process context until we start processing those functions again.  Keep
195 in mind that normally, smp_idle() shouldn't be in any process's context.  I'll
196 probably write something later that abandons any context before halting to make
197 sure processes die appropriately.  But there are still some unresolved issues
198 that depend on what exactly we want to do.
199
200 While it is tempting to say that we stay in process context if it was local, but
201 not if it is async, there is an added complication.  The function calling
202 sleep_on() doesn't care about whether it is on a process-allocated core or not.
203 This is solvable by using per_cpu_info(), and will probably work its way into a
204 future patch, regardless of whether or not we stay in process context for async
205 calls.
206         
207 As a final case, what will we do for processes that were interrupted by
208 something that wants to block, but wasn't servicing a syscall?  We probably
209 shouldn't have these (I don't have a good example of when we'd want it, and a
210 bunch of reasons why we wouldn't), but if we do, then it might be okay anyway -
211 the kthread is just holding that proc alive for a bit.
212
213 Kmsgs and Kthreads
214 -------------------------------
215 Is there a way to mix kernel messages and kthreads?  What's the difference, and
216 can one do the other?  A kthread is a suspended call-stack and context (thread),
217 stopped in the middle of its work.  Kernel messages are about starting fresh -
218 "hey core X, run this function."  A kmsg can very easily be a tool used to
219 restart a kthread (either locally or on another core).  We do this in the test
220 code, if you're curious how it could work.
221
222 Note we use the semaphore to deal with races.  In test_kthreads(), we're
223 actually using the kmsg to up the semaphore.  You just as easily could up the
224 semaphore in one core (possibly in response to a kmsg, though more likely due to
225 an interrupt), and then send the kthread to another core to restart via a kmsg.
226
227 There's no reason you can't separate the __up_sem() and the running of the
228 kthread - the semaphore just protects you from missing the signal.  Perhaps
229 you'll want to rerun the kthread on the physical core it was suspended on!
230 (cache locality, and it might be a legit option to allow processes to say it's
231 okay to take their vcore).  Note this may require more bookkeeping in the struct
232 kthread.