Merge remote branch 'origin/sparc-dev'
[akaros.git] / Documentation / processes.txt
1 All things processes!  This explains processes from a high level, especially
2 focusing on the user-kernel boundary and transitions to the multi-cored state,
3 which is the way in which parallel processes run.  This doesn't discuss deep
4 details of the ROS kernel's process code.
5
6 This is motivated by two things: kernel scalability and direct support for
7 parallel applications.
8
9 Part 1: Overview
10 Part 2: How They Work
11 Part 3: Resource Requests
12 Part 4: Notification
13 Part 5: Old Arguments (mostly for archival purposes))
14 Part 6: Parlab app use cases
15
16 Part 1: World View of Processes
17 ==================================
18 A process is the lowest level of control, protection, and organization in the
19 kernel.
20
21 1.1: What's a process?
22 -------------------------------
23 Features:
24 - They are an executing instance of a program.  A program can load multiple
25   other chunks of code and run them (libraries), but they are written to work
26   with each other, within the same address space, and are in essence one
27   entity.
28 - They have one address space/ protection domain.  
29 - They run in Ring 3 / Usermode.
30 - They can interact with each other, subject to permissions enforced by the
31   kernel.
32 - They can make requests from the kernel, for things like resource guarantees.
33   They have a list of resources that are given/leased to them.
34
35 None of these are new.  Here's what's new:
36 - They can run in a multi-core mode, where its cores run at the same time, and
37   it is aware of changes to these conditions (page faults, preemptions).  It
38   can still request more resources (cores, memory, whatever).
39 - Every core in a multi-cored process is *not* backed by a kernel
40   thread/kernel stack, unlike with Linux tasks.
41         - There are *no* per-core run-queues in the kernel that decide for
42           themselves which kernel thread to run.
43 - They are not fork()/execed().  They are created(), and then later made
44   runnable.  This allows the controlling process (parent) to do whatever it
45   wants: pass file descriptors, give resources, whatever.
46
47 These changes are directly motivated by what is wrong with current SMP
48 operating systems as we move towards many-core: direct (first class) support
49 for truly parallel processes, kernel scalability, and an ability of a process
50 to see through classic abstractions (the virtual processor) to understand (and
51 make requests about) the underlying state of the machine.
52
53 1.2: What's a partition?
54 -------------------------------
55 So a process can make resource requests, but some part of the system needs to
56 decide what to grant, when to grant it, etc.  This goes by several names:
57 scheduler / resource allocator / resource manager.  The scheduler simply says
58 when you get some resources, then calls functions from lower parts of the
59 kernel to make it happen.
60
61 This is where the partitioning of resources comes in.  In the simple case (one
62 process per partitioned block of resources), the scheduler just finds a slot
63 and runs the process, giving it its resources.  
64
65 A big distinction is that the *partitioning* of resources only makes sense
66 from the scheduler on up in the stack (towards userspace).  The lower levels
67 of the kernel know about resources that are granted to a process.  The
68 partitioning is about the accounting of resources and an interface for
69 adjusting their allocation.  It is a method for telling the 'scheduler' how
70 you want resources to be granted to processes.
71
72 A possible interface for this is procfs, which has a nice hierarchy.
73 Processes can be grouped together, and resources can be granted to them.  Who
74 does this?  A process can create it's own directory entry (a partition), and
75 move anyone it controls (parent of, though that's not necessary) into its
76 partition or a sub-partition.  Likewise, a sysadmin/user can simply move PIDs
77 around in the tree, creating partitions consisting of processes completely
78 unaware of each other.
79
80 Now you can say things like "give 25% of the system's resources to apache and
81 mysql".  They don't need to know about each other.  If you want finer-grained
82 control, you can create subdirectories (subpartitions), and give resources on
83 a per-process basis.  This is back to the simple case of one process for one
84 (sub)partition.
85
86 This is all influenced by Linux's cgroups (process control groups).
87 http://www.mjmwired.net/kernel/Documentation/cgroups.txt. They group processes
88 together, and allow subsystems to attach meaning to those groups.
89
90 Ultimately, I view partitioning as something that tells the kernel how to
91 grant resources.  It's an abstraction presented to userspace and higher levels
92 of the kernel.  The specifics still need to be worked out, but by separating
93 them from the process abstraction, we can work it out and try a variety of
94 approaches.
95
96 The actual granting of resources and enforcement is done by the lower levels
97 of the kernel (or by hardware, depending on future architectural changes).
98
99 Part 2: How They Work
100 ===============================
101 2.1: States
102 -------------------------------
103 PROC_CREATED
104 PROC_RUNNABLE_S
105 PROC_RUNNING_S
106 PROC_WAITING
107 PROC_DYING
108 PROC_RUNNABLE_M
109 PROC_RUNNING_M
110
111 Difference between the _M and the _S states:
112 - _S : legacy process mode
113 - RUNNING_M implies *guaranteed* core(s).  You can be a single core in the
114   RUNNING_M state.  The guarantee is subject to time slicing, but when you
115   run, you get all of your cores.
116 - The time slicing is at a coarser granularity for _M states.  This means that
117   when you run an _S on a core, it should be interrupted/time sliced more
118   often, which also means the core should be classified differently for a
119   while.  Possibly even using it's local APIC timer.
120 - A process in an _M state will be informed about changes to its state, e.g.,
121   will have a handler run in the event of a page fault
122
123 For more details, check out kern/inc/process.h  For valid transitions between
124 these, check out kern/src/process.c's proc_set_state().
125
126 2.2: Creation and Running
127 -------------------------------
128 Unlike the fork-exec model, processes are created, and then explicitly made
129 runnable.  In the time between creation and running, the parent (or another
130 controlling process) can do whatever it wants with the child, such as pass
131 specific file descriptors, map shared memory regions (which can be used to
132 pass arguments).
133
134 New processes are not a copy-on-write version of the parent's address space.
135 Due to our changes in the threading model, we no longer need (or want) this
136 behavior left over from the fork-exec model.
137
138 By splitting the creation from the running and by explicitly sharing state
139 between processes (like inherited file descriptors), we avoid a lot of
140 concurrency and security issues.
141
142 2.3: Vcoreid vs Pcoreid
143 -------------------------------
144 The vcoreid is a virtual cpu number.  Its purpose is to provide an easy way
145 for the kernel and userspace to talk about the same core.  pcoreid (physical)
146 would also work.  The vcoreid makes things a little easier, such as when a
147 process wants to refer to one of its other cores (not the calling core).  It
148 also makes the event notification mechanisms easier to specify and maintain.
149
150 The vcoreid only makes sense when in an _M mode.  In _S mode, your vcoreid is
151 0.  Vcoreid's only persist when in _M mode.  If you leave _M mode on a non-0
152 vcore, that context becomes vcore0.  This can get tricky for userspace's
153 stacks (more below).
154
155 Processes that care about locality should check what their pcoreid is.  This
156 is currently done via sys_getcpuid().  The name will probably change.
157
158 2.4: Transitioning to and from states
159 -------------------------------
160 2.4.1: To go from _S to _M, a process requests cores.
161 --------------
162 A resource request from 0 to 1 or more causes a transition from _S to _M.  The
163 calling context moves to vcore0 (proc_run() handles that) and continues from
164 where it left off (the return point of the syscall).  
165
166 For all other cores, and all subsequently allocated cores, they start at the
167 elf entry point, with vcoreid in eax or a suitable arch-specific manner.  This
168 could be replaced with a syscall that returns the vcoreid, but probably won't
169 to help out sparc.
170
171 Future proc_runs(), like from RUNNABLE_M to RUNNING_M start all cores at the
172 entry point, including vcore0.  The magic of moving contexts only happens on
173 the transition from _S to _M (which the process needs to be aware of for a
174 variety of reasons).  This also means that userspace needs to handle vcore0
175 coming up at the entry point again (and not starting the program over).  I
176 recommend setting a global variable that can be checked from assembly before
177 going to _M the first time.
178
179 When coming in to the entry point, new cores should grab a stack.  There are a
180 few ways to do this.  They ought to be the same stack every time for a
181 specific vcore.  They will be the transition stacks (in Lithe terms) that are
182 used as jumping-off points for future function calls.  These stacks need to be
183 used in a continuation-passing style.  Start from the top every time.  The
184 reason for that is actual contexts may move around, and vcores will come and
185 go - and each vcore will always reuse the same stack.  Lithe works this way,
186 so it's not an issue.
187
188 It's recommended that while in _S mode the process allocates stacks and puts
189 them in an array, indexed by vcoreid for the entry point to easily find them.
190 Then each core grabs its transition stack, then goes into hart_entry.
191
192 Userspace needs to make sure the calling context (which will become vcore0) is
193 on a good stack, like USTACKTOP.  This could happen if you leave _M from a core
194 other than vcore0, then return to _M mode.  While in _S mode, you were still
195 on whatever stack you came from (like vcore3's transition stack).
196
197 2.4.2: To go from _M to _S, a process requests 0 cores
198 --------------
199 The caller becomes the new _S context.  Everyone else gets trashed
200 (abandon_core()).  Their stacks are still allocated and it is up to userspace
201 to deal with this.  In general, they will regrab their transition stacks when
202 they come back up.  Their other stacks and whatnot (like TBB threads) need to
203 be dealt with.
204
205 As mentioned above, when the caller next switches to _M, that context
206 (including its stack) becomes the new vcore0.
207
208 2.4.3: Requesting more cores while in _M
209 --------------
210 Any core can request more cores and adjust the resource allocation in any way.
211 These new cores come up just like the original new cores in the transition
212 from _S to _M: at the entry point.
213
214 2.4.4: Yielding
215 --------------
216 Yielding gives up a core.  In _S mode, it will transition from RUNNING_S to
217 RUNNABLE_S.  The context is saved in env_tf.  A yield will *not* transition
218 from _M to _S.
219
220 In _M mode, this yields the calling core.  The kernel will rip it out of your
221 vcore list.  A process can yield its cores in any order.  The kernel will
222 "fill in the holes of the vcoremap" when for any future newcores (e.g., proc A
223 has 4 vcores, yields vcore2, and then asks for another vcore.  The new one
224 will be vcore2).
225
226 When you are in _M and yield your last core, it is an m_yield.  This
227 completely suspends all cores, like a voluntary preemption.  When the process
228 is run again, all cores will come up at the entry point (including vcore0 and
229 the calling core).  This isn't implemented yet, and will wait on some work
230 with preemption.
231
232 2.4.5: Others
233 --------------
234 There are other transitions, mostly self-explanatory.  We don't currently use
235 any WAITING states, since we have nothing to block on yet.  DYING is a state
236 when the kernel is trying to kill your process, which can take a little while
237 to clean up.
238         
239 2.5: Preemption
240 -------------------------------
241 None of this is implemented yet, or fully flushed out.
242
243 2.5.1: Ideas
244 --------------
245 The rough plan is to notify beforehand, then take action if userspace doesn't
246 yield.
247
248 When a core is preempted or interrupted for any reason (like a pagefault or
249 other trap), the context is saved in a structure in procinfo that contains the
250 vcoreid, a code for what happened, and the actual context (probably always
251 including FP/SSE registers).
252
253 If userspace is keeping the core, like with a page fault or other trap, that
254 core will start up at the entry point, and regrab its transition stack.  There
255 could be issues with this, if the trap came while operating on that stack.
256 There'll probably be some way other way to help userspace know something
257 happened.  Recursive (page) faults are also tricky.
258
259 If it lost the core, like in a preemption, the context is saved (fully), and
260 the process is notified (in the manner it wishes).  See Part 4.
261
262 When a process loses all of its cores, it just loses them all.  There is no
263 notification interrupt (though there will be a message posted).  When a
264 process comes up at the entry point once it is run again, it should check its
265 event queue (if it cares).
266
267 2.5.2: Issues with preemption, trap redirection, and event notification
268 --------------
269 There are other issues with cascading interrupts (when contexts are still
270 running handlers).  Imagine a pagefault, followed by preempting the handler.
271 It doesn't make sense to run the preempt context after the page fault.  The
272 difficulty is in determining when the context is no longer handling an event.
273 We could consider using a register, controllable by userspace, to give the
274 kernel this hint.  Maybe have a window of time we won't preempt again (though
275 that is really painful.  How long is this window?).
276
277 Even worse, consider vcore0 is set up to receive all events.  If events come
278 in faster than it can process them, it will both nest too deep and process out
279 of order.
280
281 Also, we don't have a good way to handle interrupts/events when on the
282 transition stack at all (let alone cascading or overflow).  The kernel will
283 just start you from the top of the stack, which will eventually clobber
284 whatever the core was doing previously.
285
286 We can consider using another register to signal some sort of exceptional
287 event, and before touching the transition stack, the core can jump to a
288 per-core exception stack.  Perhaps to avoid nesting exceptions, when an
289 interrupt comes in, the kernel can see userspace is on it's exception stack
290 and not post the event, and it's up to userspace to check for any missed
291 events before leaving its core.  Ugly.  And can't handle traps.
292
293 Pre-Notification issues: how much time does userspace need to clean up and
294 yield?  How quickly does the kernel need the core back (for scheduling
295 reasons)?
296
297 Part 3: Resource Requests
298 ===============================
299 A process can ask for resources from the kernel.  The kernel either grants
300 these requests or not, subject to QoS guarantees, or other scheduler-related
301 criteria.
302
303 A process requests resources, currently via sys_resource_req.  The form of a
304 request is to tell the kernel how much of a resource it wants.  Currently,
305 this is the amt_wanted.  We'll also have a minimum amount wanted, which tells
306 the scheduler not to run the process until the minimum amount of resources are
307 available.
308
309 How the kernel actually grants resources is resource-specific.  In general,
310 there are functions like proc_give_cores() (which gives certain cores to a
311 process) that actually does the allocation, as well as adjusting the
312 amt_granted for that resource.
313
314 For expressing QoS guarantees, we'll probably use something like procfs (as
315 mentioned above) to explicitly tell the scheduler/resource manager what the
316 user/sysadmin wants.  An interface like this ought to be usable both by
317 programs as well as simple filesystem tools (cat, etc).
318
319 Guarantees exist regardless of whether or not the allocation has happened.  An
320 example of this is when a process may be guaranteed to use 8 cores, but
321 currently only needs 2.  Whenever it asks for up to 8 cores, it will get them.
322 The exact nature of the guarantee is TBD, but there will be some sort of
323 latency involved in the guarantee for systems that want to take advantage of
324 idle resources (compared to simply reserving and not allowing anyone else to
325 use them).  A latency of 0 would mean a process wants it instantly, which
326 probably means they ought to be already allocated (and billed to) that
327 process.  
328
329 Part 4: Event Notification
330 ===============================
331 One of the philosophical goals of ROS is to expose information up to userspace
332 (and allow requests based on that information).  There will be a variety of
333 events in the system that processes will want to know about.  To handle this,
334 we'll eventually build something like the following.
335
336 All events will have a number, like an interrupt vector.  Each process will
337 have an event queue.  On most architectures, it will be a simple
338 producer-consumer ring buffer sitting in the "shared memory" procdata region
339 (shared between the kernel and userspace).  The kernel writes a message into
340 the buffer with the event number and some other helpful information.  For
341 instance, a preemption event will say which vcore was preempted and provide a
342 pointer to the context that was preempted.
343
344 Additionally, the process may request to be actively notified of specific
345 events.  This is done by having the process write into an event vector table
346 (like an IDT) in procdata.  For each event, the process can write a function
347 pointer and a vcoreid.  The kernel will execute that function on the given
348 core (and pass appropriate arguments, such as a pointer to the message in the
349 event queue and a pointer to the context that was just interrupted).
350
351 Part 5: Old Arguments about Processes vs Partitions
352 ===============================
353 This is based on my interpretation of the cell (formerly what I thought was
354 called a partition).
355
356 5.1: Program vs OS
357 -------------------------------
358 A big difference is what runs inside the object.  I think trying to support
359 OS-like functionality is a quick path to unnecessary layers and complexity,
360 esp for the common case.  This leads to discussions of physical memory
361 management, spawning new programs, virtualizing HW, shadow page tables,
362 exporting protection rings, etc.
363
364 This unnecessarily brings in the baggage and complexity of supporting VMs,
365 which are a special case.  Yes, we want processes to be able to use their
366 resources, but I'd rather approach this from the perspective of "what do they
367 need?" than "how can we make it look like a real machine."  Virtual machines
368 are cool, and paravirtualization influenced a lot of my ideas, but they have
369 their place and I don't think this is it.
370
371 For example, exporting direct control of physical pages is a bad idea.  I
372 wasn't clear if anyone was advocating this or not.  By exposing actual machine
373 physical frames, we lose our ability to do all sorts of things (like swapping,
374 for all practical uses, and other VM tricks).  If the cell/process thinks it
375 is manipulating physical pages, but really isn't, we're in the VM situation of
376 managing nested or shadow page tables, which we don't want.
377
378 For memory, we'd be better off giving an allocation of a quantity frames, not
379 specific frames.  A process can pin up to X pages, for instance.  It can also
380 pick pages to be evicted when there's memory pressure.  There are already
381 similar ideas out there, both in POSIX and in ACPM.
382
383 Instead of mucking with faking multiple programs / entities within an cell,
384 just make more processes.  Otherwise, you'd have to export weird controls that
385 the kernel is doing anyway (and can do better!), and have complicated middle
386 layers.
387
388 5.2: Multiple "Things" in a "partition"
389 -------------------------------
390 In the process-world, the kernel can make a distinction between different
391 entities that are using a block of resources.  Yes, "you" can still do
392 whatever you want with your resources.  But the kernel directly supports
393 useful controls that you want. 
394 - Multiple protection domains are no problem.  They are just multiple
395   processes.  Resource allocation is a separate topic.
396 - Processes can control one another, based on a rational set of rules.  Even
397   if you have just cells, we still need them to be able to control one another
398   (it's a sysadmin thing).
399
400 "What happens in a cell, stays in a cell."  What does this really mean?  If
401 it's about resource allocation and passing of resources around, we can do that
402 with process groups.  If it's about the kernel not caring about what code runs
403 inside a protection domain, a process provides that.  If it's about a "parent"
404 program trying to control/kill/whatever a "child" (even if it's within a cell,
405 in the cell model), you *want* the kernel to be involved.  The kernel is the
406 one that can do protection between entities.
407
408 5.3: Other Things
409 -------------------------------
410 Let the kernel do what it's made to do, and in the best position to do: manage
411 protection and low-level resources.
412
413 Both processes and partitions "have" resources.  They are at different levels
414 in the system.  A process actually gets to use the resources.  A partition is
415 a collection of resources allocated to one or more processes.
416
417 In response to this:
418
419 On 2009-09-15 at 22:33 John Kubiatowicz wrote:
420 > John Shalf wrote:  
421 > >
422 > > Anyhow, Barret is asking that resource requirements attributes be 
423 > > assigned on a process basis rather than partition basis.  We need
424 > > to justify why gang scheduling of a partition and resource
425 > > management should be linked.  
426
427 I want a process to be aware of it's specific resources, as well as the other
428 members of it's partition.  An individual process (which is gang-scheduled in
429 multi-core mode) has a specific list of resources.  Its just that the overall
430 'partition of system resources' is separate from the list of specific
431 resources of a process, simply because there can be many processes under the
432 same partition (collection of resources allocated).
433
434 > >  
435 > Simplicity!
436
437 > Yes, we can allow lots of options, but at the end of the day, the 
438 > simplest model that does what we need is likely the best. I don't
439 > want us to hack together a frankenscheduler.  
440
441 My view is also simple in the case of one address space/process per
442 'partition.'  Extending it to multiple address spaces is simply asking that
443 resources be shared between processes, but without design details that I
444 imagine will be brutally complicated in the Cell model.
445
446
447 Part 6: Use Cases
448 ===============================
449 6.1: Matrix Multiply / Trusting Many-core app
450 -------------------------------
451 The process is created by something (bash, for instance).  It's parent makes
452 it runnable.  The process requests a bunch of cores and RAM.  The scheduler
453 decides to give it a certain amount of resources, which creates it's partition
454 (aka, chunk of resources granted to it's process group, of which it is the
455 only member).  The sysadmin can tweak this allocation via procfs.
456
457 The process runs on its cores in it's multicore mode.  It is gang scheduled,
458 and knows how many cores there are.  When the kernel starts the process on
459 it's extra cores, it passes control to a known spot in code (the ELF entry
460 point), with the virtual core id passed as a parameter.
461
462 The code runs from a single binary image, eventually with shared
463 object/library support.  It's view of memory is a virtual address space, but
464 it also can see it's own page tables to see which pages are really resident
465 (similar to POSIX's mincore()).
466
467 When it comes time to lose a core, or be completely preempted, the process is
468 notified by the OS running a handler of the process's choosing (in userspace).
469 The process can choose what to do (pick a core to yield, prepare to be
470 preempted, etc).
471
472 To deal with memory, the process is notified when it page faults, and keeps
473 its core.  The process can pin pages in memory.  If there is memory pressure,
474 the process can tell the kernel which pages to unmap.
475
476 This is the simple case.
477
478 6.2: Browser
479 -------------------------------
480 In this case, a process wants to create multiple protection domains that share
481 the same pool of resources.  Or rather, with it's own allocated resources.
482
483 The browser process is created, as above.  It creates, but does not run, it's
484 untrusted children.  The kernel will have a variety of ways a process can
485 "mess with" a process it controls.  So for this untrusted child, the parent
486 can pass (for example), a file descriptor of what to render, "sandbox" that
487 process (only allow a whitelist of syscalls, e.g. can only read and write
488 descriptors it has).  You can't do this easily in the cell model.
489
490 The parent can also set up a shared memory mapping / channel with the child.
491
492 For resources, the parent can put the child in a subdirectory/ subpartition
493 and give a portion of its resources to that subpartition.  The scheduler will
494 ensure that both the parent and the child are run at the same time, and will
495 give the child process the resources specified.  (cores, RAM, etc).
496
497 After this setup, the parent will then make the child "runnable".  This is why
498 we want to separate the creation from the runnability of a process, which we
499 can't do with the fork/exec model.
500
501 The parent can later kill the child if it wants, reallocate the resources in
502 the partition (perhaps to another process rendering a more important page),
503 preempt that process, whatever.
504
505 6.3: SMP Virtual Machines
506 -------------------------------
507 The main issue (regardless of paravirt or full virt), is that what's running
508 on the cores may or may not trust one another.  One solution is to run each
509 VM-core in it's own process (like with Linux's KVM, it uses N tasks (part of
510 one process) for an N-way SMP VM).  The processes set up the appropriate
511 shared memory mapping between themselves early on.  Another approach would be
512 to allow a multi-cored process to install specific address spaces on each
513 core, and interpose on syscalls, privileged instructions, and page faults.
514 This sounds very much like the Cell approach, which may be fine for a VM, but
515 not for the general case of a process.
516
517 Or with a paravirtualized SMP guest, you could (similar to the L4Linux way,)
518 make any Guest OS processes actual processes in our OS.  The resource
519 allocation to the Guest OS partition would be managed by the parent process of
520 the group (which would be running the Guest OS kernel).  We still need to play
521 tricks with syscall redirection.
522
523 For full virtualization, we'd need to make use of hardware virtualization
524 instructions. Dealing with the VMEXITs, emulation, and other things is a real
525 pain, but already done.  The long range plan was to wait til the
526 http://v3vee.org/ project supported Intel's instructions and eventually
527 incorporate that.
528
529 All of these ways involve subtle and not-so-subtle difficulties.  The
530 Cell-as-OS mode will have to deal with them for the common case, which seems
531 brutal.  And rather unnecessary.