Merge remote branch 'origin/sparc-dev'
[akaros.git] / Documentation / process-internals.txt
1 This discusses core issues with process design and implementation.  Most of this
2 info is available in the source in the comments (but may not be in the future).
3 For now, it's a dumping ground for topics that people ought to understand before
4 they muck with how processes work.
5
6 1. Reference Counting
7 ===========================
8 1.1 Basics:
9 ---------------------------
10 Reference counts (proc_refcnt) exist to keep a process alive.  Eventually, this
11 will probably turn into a regular "kernel design pattern", like it is in Linux
12 (http://lwn.net/Articles/336224/).  The style of reference counting we use for
13 processes is similar to a kref:
14 - Can only incref if the current value is greater than 0, meaning there is
15   already a reference to it.  It is a bug to try to incref on something that has
16   no references, so always make sure you incref something that you know has a
17   reference.  If you don't know, you need to get it manually (CAREFULLY!) or use
18   pid2proc (which is a careful way of doing this).  If you incref and there are
19   0 references, the kernel will panic.  Fix your bug / don't incref random
20   pointers.
21 - Can always decref.
22 - When the decref returns 0, perform some operation.  This does some final
23   cleanup on the object.
24
25 For a process, proc_destroy() decrefs, and other codes using the proc also
26 decref.  The last one to decref calls proc_free to do the final cleanup.
27
28 1.2 Brief History of the Refcnt:
29 ---------------------------
30 Originally, the refcnt was created to keep page tables from being destroyed (in
31 proc_free()) while cores were still using them, which is what was happens during
32 an ARSC (async remote syscall).  It was then defined to be a count of places in
33 the kernel that had an interest in the process staying alive, practically just
34 to protect current/cr3.  This 'interest' actually extends to any code holding a
35 pointer to the proc, such as one acquired via pid2proc(), which is its current
36 meaning.
37
38 1.3 Quick Aside: The current Macro:
39 ---------------------------
40 current is a pointer to the proc that is currently loaded/running on any given
41 core.  It is stored in the per_cpu_info struct, and set/managed by low-level
42 process code.  It is necessary for the kernel to quickly figure out who is
43 running on its code, especially when servicing interrupts and traps.  current is
44 protected by a refcnt.
45
46 1.4 Reference Counting Rules:
47 ---------------------------
48 +1 for existing.
49 - The fact that the process is supposed to exist is worth +1.  When it is time
50   to die, we decref, and it will eventually be cleaned up.
51
52 +1 for someone using it or planning to use it.
53 - This includes simply having a pointer to the proc, since presumably you will
54   use it.  pid2proc() will incref for you.  When you are done, decref.
55 - Functions that create a process and return a pointer (like proc_create() or
56   kfs_proc_create()) will also up the refcnt for you.  Decref when you're done.
57 - If the *proc is stored somewhere where it will be used again, such as in an IO
58   continuation, it needs to be refcnt'd.  Note that if you already had a
59   reference from pid2proc(), simply don't decref after you store the pointer.
60
61 +1 for current.
62 - current counts as someone using it (expressing interest in the core), but is
63   also a source of the pointer, so its a bit different.
64 - You have a reference from current and can use it without refcnting, but
65   anything that needs to eat a reference or store/use it needs an incref first.
66   To be clear, your reference is *NOT* edible.  It protects the cr3, guarantees
67   the process won't die, and serves as a bootstrappable reference.
68 - Specifically, if you get a ref from current, but then save it somewhere (like
69   an IO continuation request), then clearly you must incref, since it's both
70   current and stored/used.
71 - If you don't know what might be downstream from your function, then incref
72   before passing the reference, and decref when it returns.  Like when handling
73   syscalls, for example.
74
75 All functions that take a *proc have a refcnt'd reference, though it may not be
76 edible (it could be current).  It is the callers responsibility to make sure
77 it'd edible if it necessary.  It is the callees responsibility to incref if it
78 stores or makes a copy of the reference.
79
80 1.5 Functions That Don't or Might Not Return:
81 ---------------------------
82 Refcnting and especially decreffing gets tricky when there are functions that
83 MAY not return.  proc_startcore() does not return (it pops into userspace).
84 proc_run() might not return, if the core it was called on will pop into
85 userspace (if it was a _S, or if the core is part of the vcoremap for a _M).
86
87 Functions that MAY not return will "eat" your reference *IF* they do not return.
88 This means that you must have a reference when you call them (like always), and
89 that reference will be consumed / decref'd for you if the function doesn't
90 return.  Or something similarly appropriate.
91
92 We do this because when the function does not return, you will not have the
93 chance to decref (your decref code will never run).  We need the reference when
94 going in to keep the object alive (like with any other refcnt).  We can't have
95 the function always eat the reference, since you cannot simply re-incref the
96 pointer (not allowed to incref unless you know you had a good reference).  You'd
97 have to do something like p = pid2proc(p_pid);  It's clunky to do that, easy to
98 screw up, and semantically, if the function returns, then we may still have an
99 interest in p and should decref later.
100
101 The downside is that functions need to determine if they will return or not,
102 which can be a pain (a linear time search when running an _M, for instance,
103 which can suck if we are trying to use a broadcast/logical IPI).
104
105 As the caller, you usually won't know if the function will return or not, so you
106 need to provide a consumable reference.  Current doesn't count.  For example,
107 proc_run() requires a reference.  You can proc_run(p), and use p afterwards, and
108 later decref.  You need to make sure you have a reference, so things like
109 proc_run(pid2proc(55)) works, since pid2proc() increfs for you.  But you cannot
110 proc_run(current), unless you incref current in advance.  Incidentally,
111 proc_running current doesn't make a lot of sense.
112
113 As another example, proc_startcore() will take your reference and store it
114 in current.  Since it is used by both the __startcore and the interrupt return
115 paths, we're currently going with the model of "caller makes sure there is a ref
116 for current".  Check its comments for details.
117
118 1.6 Runnable List:
119 ---------------------------
120 Procs on the runnable list need to have a refcnt (other than the +1 for
121 existing).  It's something that cares that the process exists.  We could have
122 had it implicitly be refcnt'd (the fact that it's on the list is enough, sort of
123 as if it was part of the +1 for existing), but that complicates things.  For
124 instance, it is a source of a reference (for the scheduler) and you could not
125 proc_run() a process from the runnable list without worrying about increfing it
126 before hand.  Remember that proc_run() might consume your reference (which
127 actually turns into a current reference, which is later destroyed by decref in
128 abandon_core()).
129
130 1.7 Internal Details for Specific Functions:
131 ---------------------------
132 proc_run(): makes sure enough refcnts are in place for all places that will
133 install current.  This also makes it easier on the system (one big incref(n),
134 instead of n increfs of (1) from multiple cores).  In the off chance current was
135 already set for a core receiving the active message, __startcore will decref.
136 Also note that while proc_run() consumes your reference, it's not actually
137 decreffing, so there's no danger within proc_run() of the process dying /
138 __proc_free()ing.
139
140 proc_startcore(): assumes all references to p are sorted.  *p is already
141 accounted for as if it was current on the core startcore runs on. (there is only
142 one refcnt for both *p and current, not 2 separate ones).
143
144 proc_destroy(): it might not return (if the calling core belongs to the
145 process), so it may eat your reference and you must have an edible reference.
146 It is possible you called proc_destroy(current).  The cleanup of the current
147 will be its own decref, so you need to have a usable/real reference (current
148 doesn't count as an edible reference).  So incref before doing that.  Even if p
149 == current, proc_destroy() can't tell if you sent it p (and had a reference) or
150 current and didn't.
151
152 proc_yield(): this never returns, so it eats your reference.  It will also
153 decref when it abandon_core()s.
154
155 __proc_give_cores() and friends: you call this while holding the lock, but it is
156 possible that your core is in the corelist you gave it.  In this case, it will
157 detect it, and return a bool signalling if an IPI is pending.  It will not
158 consume your reference.  The reasoning behind this is that it is an internal
159 function, and you may want to do other things before decreffing.  There is also
160 a helper function that will unlock and possibly decref/wait for the IPI, called
161 __proc_unlock_ipi_pending().  Use this when it is time to unlock.  It's just a
162 helper, which may go away.
163
164 abandon_core(): it was not given a reference, so it doesn't eat one.  It will
165 decref when it unloads the cr3.  Note that this is a potential performance
166 issue.  When preempting or killing, there are n cores that are fighting for the
167 cacheline to decref.  An alternative would be to have one core decref for all n
168 cores, after it knows all cores unloaded the cr3.  This would be a good use of
169 the checklist (possibly with one cacheline per core).  It would take a large
170 amount of memory for better scalability.
171
172 1.8 Core Request:
173 ---------------------------
174 core_request() is run outside of the process code (for now), though it is fairly
175 intricate.  It's another function that might not return, but the reasons for
176 this vary:
177         1: The process is moving from _S to _M so the return path to userspace won't
178         happen (and sort of will on the new core / the other side), but that will
179         happen when popping into userspace.
180         2: The scheduler is giving the current core to the process, which can kick
181         in via either proc_run() or __proc_give_cores().
182         3: It was a request to give up all cores, which means the current core will
183         receive an IPI (if it wasn't an async call, which isn't handled yet).
184
185 For these reasons, core_request() needs to have an edible reference.
186
187 Also, since core_request calls functions that might not return, there are cases
188 where it will not be able to call abandon_core() and leave process context.
189 This is an example of why we have the fallback case of leaving process context
190 in proc_startcore().  See the section below about process context for more
191 information.
192
193 Eventually, core_request() will be split better, probably with the brutal logic
194 in process.c that would call out some functions in resource.c that actually make
195 choices.
196
197 1.9 Things I Could Have Done But Didn't And Why:
198 ---------------------------
199 Q: Could we have the first reference (existence) mean it could be on the runnable
200 list or otherwise in the proc system (but not other subsystems)?  In this case,
201 proc_run() won't need to eat a reference at all - it will just incref for every
202 current it will set up.
203
204 A: No: if you pid2proc(), then proc_run() but never return, you have (and lose)
205 an extra reference.  We need proc_run() to eat the reference when it does not
206 return.  If you decref between pid2proc() and proc_run(), there's a (rare) race
207 where the refcnt hits 0 by someone else trying to kill it.  While proc_run()
208 will check to see if someone else is trying to kill it, there's a slight chance
209 that the struct will be reused and recreated.  It'll probably never happen, but
210 it could, and out of principle we shouldn't be referencing memory after it's
211 been deallocated.  Avoiding races like this is one of the reasons for our refcnt
212 discipline.
213
214 Q: Could proc_run() always eat your reference, which would make it easier for
215 its implementation?
216
217 A: Yeah, technically, but it'd be a pain, as mentioned above.  You'd need to
218 reaquire a reference via pid2proc, and is rather easy to mess up.
219
220 Q: Could we have made proc_destroy() take a flag, saying whether or not it was
221 called on current and needed a decref instead of wasting an incref?
222
223 A: We could, but won't.  This is one case where the external caller is the one
224 that knows the function needs to decref or not.  But it breaks the convention a
225 bit, doesn't mirror proc_create() as well, and we need to pull in the cacheline
226 with the refcnt anyways.  So for now, no.
227
228 Q: Could we make __proc_give_cores() simply not return if an IPI is coming?
229
230 A: I did this originally, and manually unlocked and __wait_for_ipi()d.  Though
231 we'd then need to deal with it like that for all of the related functions, which
232 doesn't work if you wanted to do something afterwards (like schedule(p)).  Also
233 these functions are meant to be internal helpers, so returning the bool makes
234 more sense.  It eventually led to having __proc_unlock_ipi_pending(), which made
235 proc_destroy() much cleaner and helped with a general model of dealing with
236 these issues.  Win-win.
237
238 2 When Do We Really Leave "Process Context"?
239 ===========================
240 2.1 Overview
241 ---------------------------
242 First off, it's not really "process context" in the way Linux deals with it.  We
243 aren't operating in kernel mode on behalf of the process (always).  We are
244 specifically talking about when a process's cr3 is loaded on a core.  Usually,
245 current is also set (the exception for now is when processing ARSCs).
246
247 There are a couple different ways to do this.  One is to never unload a context
248 until something new is being run there (handled solely in proc_startcore()).
249 Another way is to always explicitly leave the core, like by abandon_core()ing.
250
251 The issue with the former is that you could have contexts sitting around for a
252 while, and also would have a bit of extra latency when __proc_free()ing during
253 someone *else's* proc_startcore() (though that could be avoided if it becomes a
254 real issue, via some form of reaping).  You'll also probably have excessive
255 decrefs (based on the interactions between proc_run() and __startcore()).
256
257 The issue with the latter is excessive TLB shootdowns and corner cases.  There
258 could be some weird cases (in core_request() for example) where the core you are
259 running on has the context loaded for proc A on a mgmt core, but decides to give
260 it to proc B.
261
262 If no process is running there, current == 0 and boot_cr3 is loaded, meaning no
263 process's context is loaded.
264
265 2.2 Here's how it is done now:
266 ---------------------------
267 We try to proactively leave, but have the ability to stay in context til
268 proc_startcore() to handle the corner cases (and to maybe cut down the TLB
269 flushes later).  To stop proactively leaving, just change abandon_core() to not
270 do anything with current/cr3.  You'll see weird things like processes that won't
271 die until their old cores are reused.  The reason we proactively leave context
272 is to help with sanity for these issues, and also to avoid decref's in
273 __startcore().
274
275 A couple other details: __startcore() sorts the extra increfs, and
276 proc_startcore() sorts leaving the old context.  Anytime a __startcore active
277 message is sent, the sender increfs in advance for the current refcnt.  If that
278 was in error, __startcore decrefs.  proc_startcore(), which the last moment
279 before we *must* have the cr3/current issues sorted, does the actual check if
280 there was an old process there or not, while it handles the lcr3 (if necessary).
281 In general, lcr3's ought to have refcnts near them, or else comments explaining
282 why not.
283
284 So we leave process context when told to do so (__death/abandon_core()) or if
285 another process is run there.  The _M code is such that a proc will stay on its
286 core until it receives a message, and that message would cleanup/restore a
287 generic context (boot_cr3).  A _S could stay on its core until another _S came
288 in.  This is much simpler for cases when a timer interrupt goes off to force a
289 schedule() decision.  It also avoids a TLB flush in case the scheduler picked
290 that same proc to run again.  This could also happen to an _M, if for some
291 reason it was given a management core (!!!) or some other event happened that
292 caused some management/scheduling function to run on one of it's cores (perhaps
293 it asked).
294
295 proc_yield() abandons the core / leaves context.
296
297 2.3 Other issues:
298 ---------------------------
299 Note that it is not clear exactly how we want to deal with interrupting
300 processes that are in the kernel.  There is no true process context, so we can't
301 leave a core until the kernel is in a "safe place", i.e. it's state is bundled
302 enough that it can be recontinued later.  We might end up letting the call
303 proceed, but not return to userspace (since that's a good save point).  There's
304 some rough comments about this in proc_startcore() (check for a pending
305 preempt).
306
307 This same thing applies to __death messages.  Even though a process is dying, it
308 doesn't mean we can just drop whatever the kernel was doing on its behalf.  For
309 instance, it might be holding a reference that will never get decreffed if its
310 stack gets dropped.  This is a big TODO.
311
312 3. Leaving the Kernel Stack:
313 ===========================
314 Next painful commit will deal with this a bit more...