proc messages are routine instead of immediate
[akaros.git] / Documentation / processes.txt
1 processes.txt
2 Barret Rhoden
3
4 All things processes!  This explains processes from a high level, especially
5 focusing on the user-kernel boundary and transitions to the many-core state,
6 which is the way in which parallel processes run.  This doesn't discuss deep
7 details of the ROS kernel's process code.
8
9 This is motivated by two things: kernel scalability and direct support for
10 parallel applications.
11
12 Part 1: Overview
13 Part 2: How They Work
14 Part 3: Resource Requests
15 Part 4: Preemption and Notification
16 Part 5: Old Arguments (mostly for archival purposes))
17 Part 6: Parlab app use cases
18
19 Revision History:
20 2009-10-30 - Initial version
21 2010-03-04 - Preemption/Notification, changed to many-core processes
22
23 Part 1: World View of Processes
24 ==================================
25 A process is the lowest level of control, protection, and organization in the
26 kernel.
27
28 1.1: What's a process?
29 -------------------------------
30 Features:
31 - They are an executing instance of a program.  A program can load multiple
32   other chunks of code and run them (libraries), but they are written to work
33   with each other, within the same address space, and are in essence one
34   entity.
35 - They have one address space/ protection domain.  
36 - They run in Ring 3 / Usermode.
37 - They can interact with each other, subject to permissions enforced by the
38   kernel.
39 - They can make requests from the kernel, for things like resource guarantees.
40   They have a list of resources that are given/leased to them.
41
42 None of these are new.  Here's what's new:
43 - They can run in a many-core mode, where its cores run at the same time, and
44   it is aware of changes to these conditions (page faults, preemptions).  It
45   can still request more resources (cores, memory, whatever).
46 - Every core in a many-core process (MCP) is *not* backed by a kernel
47   thread/kernel stack, unlike with Linux tasks.
48         - There are *no* per-core run-queues in the kernel that decide for
49           themselves which kernel thread to run.
50 - They are not fork()/execed().  They are created(), and then later made
51   runnable.  This allows the controlling process (parent) to do whatever it
52   wants: pass file descriptors, give resources, whatever.
53
54 These changes are directly motivated by what is wrong with current SMP
55 operating systems as we move towards many-core: direct (first class) support
56 for truly parallel processes, kernel scalability, and an ability of a process
57 to see through classic abstractions (the virtual processor) to understand (and
58 make requests about) the underlying state of the machine.
59
60 1.2: What's a partition?
61 -------------------------------
62 So a process can make resource requests, but some part of the system needs to
63 decide what to grant, when to grant it, etc.  This goes by several names:
64 scheduler / resource allocator / resource manager.  The scheduler simply says
65 when you get some resources, then calls functions from lower parts of the
66 kernel to make it happen.
67
68 This is where the partitioning of resources comes in.  In the simple case (one
69 process per partitioned block of resources), the scheduler just finds a slot
70 and runs the process, giving it its resources.  
71
72 A big distinction is that the *partitioning* of resources only makes sense
73 from the scheduler on up in the stack (towards userspace).  The lower levels
74 of the kernel know about resources that are granted to a process.  The
75 partitioning is about the accounting of resources and an interface for
76 adjusting their allocation.  It is a method for telling the 'scheduler' how
77 you want resources to be granted to processes.
78
79 A possible interface for this is procfs, which has a nice hierarchy.
80 Processes can be grouped together, and resources can be granted to them.  Who
81 does this?  A process can create it's own directory entry (a partition), and
82 move anyone it controls (parent of, though that's not necessary) into its
83 partition or a sub-partition.  Likewise, a sysadmin/user can simply move PIDs
84 around in the tree, creating partitions consisting of processes completely
85 unaware of each other.
86
87 Now you can say things like "give 25% of the system's resources to apache and
88 mysql".  They don't need to know about each other.  If you want finer-grained
89 control, you can create subdirectories (subpartitions), and give resources on
90 a per-process basis.  This is back to the simple case of one process for one
91 (sub)partition.
92
93 This is all influenced by Linux's cgroups (process control groups).
94 http://www.mjmwired.net/kernel/Documentation/cgroups.txt. They group processes
95 together, and allow subsystems to attach meaning to those groups.
96
97 Ultimately, I view partitioning as something that tells the kernel how to
98 grant resources.  It's an abstraction presented to userspace and higher levels
99 of the kernel.  The specifics still need to be worked out, but by separating
100 them from the process abstraction, we can work it out and try a variety of
101 approaches.
102
103 The actual granting of resources and enforcement is done by the lower levels
104 of the kernel (or by hardware, depending on future architectural changes).
105
106 Part 2: How They Work
107 ===============================
108 2.1: States
109 -------------------------------
110 PROC_CREATED
111 PROC_RUNNABLE_S
112 PROC_RUNNING_S
113 PROC_WAITING
114 PROC_DYING
115 PROC_RUNNABLE_M
116 PROC_RUNNING_M
117
118 Difference between the _M and the _S states:
119 - _S : legacy process mode
120 - RUNNING_M implies *guaranteed* core(s).  You can be a single core in the
121   RUNNING_M state.  The guarantee is subject to time slicing, but when you
122   run, you get all of your cores.
123 - The time slicing is at a coarser granularity for _M states.  This means that
124   when you run an _S on a core, it should be interrupted/time sliced more
125   often, which also means the core should be classified differently for a
126   while.  Possibly even using it's local APIC timer.
127 - A process in an _M state will be informed about changes to its state, e.g.,
128   will have a handler run in the event of a page fault
129
130 For more details, check out kern/inc/process.h  For valid transitions between
131 these, check out kern/src/process.c's proc_set_state().
132
133 2.2: Creation and Running
134 -------------------------------
135 Unlike the fork-exec model, processes are created, and then explicitly made
136 runnable.  In the time between creation and running, the parent (or another
137 controlling process) can do whatever it wants with the child, such as pass
138 specific file descriptors, map shared memory regions (which can be used to
139 pass arguments).
140
141 New processes are not a copy-on-write version of the parent's address space.
142 Due to our changes in the threading model, we no longer need (or want) this
143 behavior left over from the fork-exec model.
144
145 By splitting the creation from the running and by explicitly sharing state
146 between processes (like inherited file descriptors), we avoid a lot of
147 concurrency and security issues.
148
149 2.3: Vcoreid vs Pcoreid
150 -------------------------------
151 The vcoreid is a virtual cpu number.  Its purpose is to provide an easy way
152 for the kernel and userspace to talk about the same core.  pcoreid (physical)
153 would also work.  The vcoreid makes things a little easier, such as when a
154 process wants to refer to one of its other cores (not the calling core).  It
155 also makes the event notification mechanisms easier to specify and maintain.
156
157 Processes that care about locality should check what their pcoreid is.  This
158 is currently done via sys_getcpuid().  The name will probably change.
159
160 2.4: Transitioning to and from states
161 -------------------------------
162 2.4.1: To go from _S to _M, a process requests cores.
163 --------------
164 A resource request from 0 to 1 or more causes a transition from _S to _M.  The
165 calling context moves to vcore0 (proc_run() handles that) and continues from
166 where it left off (the return point of the syscall).  
167
168 For all other cores, and all subsequently allocated cores, they start at the
169 elf entry point, with vcoreid in eax or a suitable arch-specific manner.  This
170 could be replaced with a syscall that returns the vcoreid, but probably won't
171 to help out sparc.
172
173 Future proc_runs(), like from RUNNABLE_M to RUNNING_M start all cores at the
174 entry point, including vcore0.  The magic of moving contexts only happens on
175 the transition from _S to _M (which the process needs to be aware of for a
176 variety of reasons).  This also means that userspace needs to handle vcore0
177 coming up at the entry point again (and not starting the program over).  I
178 recommend setting a global variable that can be checked from assembly before
179 going to _M the first time.
180
181 When coming in to the entry point, whether as the result of a startcore or a
182 notification, the kernel will set the stack pointer to whatever is requested
183 by userspace in procdata.  A process should allocate stacks of whatever size
184 it wants for its vcores when it is in _S mode, and write these location to
185 procdata.  These stacks are the transition stacks (in Lithe terms) that are
186 used as jumping-off points for future function calls.  These stacks need to be
187 used in a continuation-passing style, and each time they are used, they start
188 from the top.
189
190 2.4.2: To go from _M to _S, a process requests 0 cores
191 --------------
192 The caller becomes the new _S context.  Everyone else gets trashed
193 (abandon_core()).  Their stacks are still allocated and it is up to userspace
194 to deal with this.  In general, they will regrab their transition stacks when
195 they come back up.  Their other stacks and whatnot (like TBB threads) need to
196 be dealt with.
197
198 When the caller next switches to _M, that context (including its stack)
199 maintains its old vcore identity.  If vcore3 causes the switch to _S mode, it
200 ought to remain vcore3 (lots of things get broken otherwise).
201 As of March 2010, the code does not reflect this
202
203 2.4.3: Requesting more cores while in _M
204 --------------
205 Any core can request more cores and adjust the resource allocation in any way.
206 These new cores come up just like the original new cores in the transition
207 from _S to _M: at the entry point.
208
209 2.4.4: Yielding
210 --------------
211 This will get revised soon, to account for different types of yields.
212
213 Yielding gives up a core.  In _S mode, it will transition from RUNNING_S to
214 RUNNABLE_S.  The context is saved in env_tf.  A yield will *not* transition
215 from _M to _S.
216
217 In _M mode, this yields the calling core.  The kernel will rip it out of your
218 vcore list.  A process can yield its cores in any order.  The kernel will
219 "fill in the holes of the vcoremap" when for any future newcores (e.g., proc A
220 has 4 vcores, yields vcore2, and then asks for another vcore.  The new one
221 will be vcore2).
222
223 When you are in _M and yield your last core, it is an m_yield.  This
224 completely suspends all cores, like a voluntary preemption.  When the process
225 is run again, all cores will come up at the entry point (including vcore0 and
226 the calling core).  This isn't implemented yet, and will wait on some work
227 with preemption.
228
229 We also need a type of yield (or a flag) that says the process is just giving
230 up the core temporarily, but actually wants the core and does not want
231 resource requests to be readjusted.  For example, in the event of a preemption
232 notification, a process may yield (ought to!) so that the kernel does not need
233 to waste effort with full preemption.
234
235 2.4.5: Others
236 --------------
237 There are other transitions, mostly self-explanatory.  We don't currently use
238 any WAITING states, since we have nothing to block on yet.  DYING is a state
239 when the kernel is trying to kill your process, which can take a little while
240 to clean up.
241
242 Part 3: Resource Requests
243 ===============================
244 A process can ask for resources from the kernel.  The kernel either grants
245 these requests or not, subject to QoS guarantees, or other scheduler-related
246 criteria.
247
248 A process requests resources, currently via sys_resource_req.  The form of a
249 request is to tell the kernel how much of a resource it wants.  Currently,
250 this is the amt_wanted.  We'll also have a minimum amount wanted, which tells
251 the scheduler not to run the process until the minimum amount of resources are
252 available.
253
254 How the kernel actually grants resources is resource-specific.  In general,
255 there are functions like proc_give_cores() (which gives certain cores to a
256 process) that actually does the allocation, as well as adjusting the
257 amt_granted for that resource.
258
259 For expressing QoS guarantees, we'll probably use something like procfs (as
260 mentioned above) to explicitly tell the scheduler/resource manager what the
261 user/sysadmin wants.  An interface like this ought to be usable both by
262 programs as well as simple filesystem tools (cat, etc).
263
264 Guarantees exist regardless of whether or not the allocation has happened.  An
265 example of this is when a process may be guaranteed to use 8 cores, but
266 currently only needs 2.  Whenever it asks for up to 8 cores, it will get them.
267 The exact nature of the guarantee is TBD, but there will be some sort of
268 latency involved in the guarantee for systems that want to take advantage of
269 idle resources (compared to simply reserving and not allowing anyone else to
270 use them).  A latency of 0 would mean a process wants it instantly, which
271 probably means they ought to be already allocated (and billed to) that
272 process.  
273
274 Part 4: Preemption and Event Notification
275 ===============================
276 Preemption and Notification are tied together.  Preemption is when the kernel
277 takes a resource (specifically, cores).  There are two types core_preempt()
278 (one core) and gang_preempt() (all cores).  Notification (discussed below) is
279 when the kernel informs a process of an event, usually referring to the act of
280 running a function on a core (active notification).
281
282 The rough plan for preemption is to notify beforehand, then take action if
283 userspace doesn't yield.  This is a notification a process can ignore, though
284 it is highly recommended to at least be aware of impending core_preempt()
285 events.
286
287 4.1: Notification Basics
288 -------------------------------
289 One of the philosophical goals of ROS is to expose information up to userspace
290 (and allow requests based on that information).  There will be a variety of
291 events in the system that processes will want to know about.  To handle this,
292 we'll eventually build something like the following.
293
294 All events will have a number, like an interrupt vector.  Each process will
295 have an event queue (per core, described below).  On most architectures, it
296 will be a simple producer-consumer ring buffer sitting in the "shared memory"
297 procdata region (shared between the kernel and userspace).  The kernel writes
298 a message into the buffer with the event number and some other helpful
299 information.
300
301 Additionally, the process may request to be actively notified of specific
302 events.  This is done by having the process write into an event vector table
303 (like an IDT) in procdata.  For each event, the process writes the vcoreid it
304 wants to be notified on.
305
306 4.2: Notification Specifics
307 -------------------------------
308 In procdata there is an array of per-vcore data, holding some
309 preempt/notification information and space for two trapframes: one for
310 notification and one for preemption.
311
312 When a notification arrives to a process under normal circumstances, the
313 kernel places the previous running context in the notification trapframe, and
314 returns to userspace at the program entry point (the elf entry point) on the
315 transition stack.  If a process is already handling a notification on that
316 core, the kernel will not interrupt it.  It is the processes's responsibility
317 to check for more notifications before returning to its normal work.  The
318 process must also unmask notifications (in procdata) before it returns to do
319 normal work.  Unmasking notifications is the signal to the kernel to not
320 bother sending IPIs, and if an IPI is sent before notifications are masked,
321 then the kernel will double-check this flag to make sure interrupts should
322 have arrived.
323
324 Notification unmasking is done by setting the notif_enabled flag (similar to
325 turning interrupts on in hardware).  When a core starts up, this flag is off,
326 meaning that notifications are disabled by default.  It is the process's
327 responsibility to turn on notifications for a given vcore.
328
329 When the process runs the handler, it is actually starting up at the same
330 location in code as it always does, so the kernel will pass it a parameter in
331 a register to let it know that it is in a notification.  Additionally, the
332 kernel will mask notifications (much like an x86 interrupt gate).  The process
333 must check its per-core event queue to see why it was called, and deal with
334 all of the events on the queue.  In the case where the event queue overflows,
335 the kernel will up a counter so the process can at least be aware things are
336 missed.
337
338 For missed events, and for events that do not need messages (they have no
339 parameters and multiple notifications are irrelevant), the kernel will toggle
340 that event's bit in a bitmask.  For the events that don't want messages, we may
341 have a flag that userspace sets, meaning they just want to know it happened.
342 This might be too much of a pain, so we'll see.  For notification events that
343 overflowed the queue, the parameters will be lost, but hopefully the application
344 can sort it out.  Again, we'll see.  A specific notif_event should not appear in
345 both the event buffers and in the bitmask.
346
347 These notification events include things such as: an IO is complete, a
348 preemption is pending to this core, the process just returned from a
349 preemption, there was a trap (divide by 0, page fault), and many other things.
350 We plan to allow this list to grow at runtime (a process can request new event
351 notification types).  These messages will often need some form of a timestamp,
352 especially ones that will expire in meaning (such as a preempt_pending).
353
354 Note that only one notification can be active at a time, including a fault.
355 This means that if a process page faults or something while notifications are
356 masked, the process will simply be killed.    It is up to the process to make
357 sure the appropriate pages are pinned, which it should do before entering _M
358 mode.
359
360 We considered having the kernel be aware of a process's transition stacks and
361 sizes so that it can detect if a vcore is in a notification handler based on
362 the stack pointer in the trapframe when a trap or interrupt fires.  While
363 cool, the flag for notif_enabled is much easier and just as capable.
364 Userspace needs to be aware of various races, and only enable notifications
365 when it is ready to have its transition stack clobbered.  This means that when
366 switching from big user-thread to user-thread, the process should temporarily
367 disable notifications and reenable them before starting the new thread fully.
368 This is analogous to having a kernel that disables interrupts while in process
369 context.
370
371 A process can fake not being on its transition stack, and even unmapping their
372 stack.  At worst, a vcore could recursively page fault (the kernel does not
373 know it is in a handler, if they keep enabling notifs before faulting), and
374 that would continue til the core is forcibly preempted.  This is not an issue
375 for the kernel.
376
377 When a process wants to use its transition stack, it ought to check
378 preempt_pending, mask notifications, jump to its transition stack, do its work
379 (e.g. process notifications, check for new notifications, schedule a new
380 thread) periodically checking for a pending preemption, and making sure the
381 notification queue/list is empty before moving back to real code.  Then it
382 should jump back to a real stack, unmask notifications, and jump to the newly
383 scheduled thread.
384
385 4.3: Preemption Specifics
386 -------------------------------
387 When a vcore is preempted, the kernel takes whatever context was running (which
388 could be a notification context) and stores it in the preempt trapframe for
389 that vcore in procdata.  There is also a flag (actually a counter) that states
390 if the context there has been sorted out.  Userspace should set this once it
391 has copied out the data and dealt with it accordingly.
392
393 The invariant regarding the preemption slot is that there should never be
394 anything running on a vcore when there is a valid/not-sorted preempt
395 trapframe.  The reason is that a preemption can come in at any time (such as
396 right after returning from a preemption).
397
398 To maintain this invariant, when the kernel starts a vcore, it will run the
399 context that is in the preempt trapframe if the "preempt_tf_sorted" (name will
400 change) flag is not set.  A process needs to be careful of a race here.  If
401 they are trying to deal with a preempt trapframe (must be from another vcore,
402 btw), the kernel could start to run that trapframe (in case it is granting a
403 core request / proc_startcore()ing).  When the kernel prepares to use the
404 trapframe (which it will do regardless of userspace activities), it will up
405 the flag/counter.  If the process notices a change in that flag, it ought to
406 abort its operation.  It can up the counter on its own when it no longer wants
407 the kernel to run that context (this means it can get clobbered).
408
409 4.4: Other trickiness
410 -------------------------------
411 4.4.1: Preemption -> deadlock
412 -------------------------------
413 One issue is that a context can be holding a lock that is necessary for the
414 userspace scheduler to manage preempted threads, and this context can be
415 preempted.  This would deadlock the scheduler.  To assist a process from
416 locking itself up, the kernel will toggle a preempt_pending flag in
417 procdata for that vcore before sending the actual preemption.  Whenever the
418 scheduler is grabbing one of these critical spinlocks, it needs to check that
419 flag first, and yield if a preemption is coming in.
420
421 Another option we may implement is for the process to be able to signal to the
422 kernel that it is in one of these ultra-critical sections by writing a magic
423 value to a specific register in the trapframe.  If there kernel sees this, it
424 will allow the process to run for a little longer.  The issue with this is
425 that the kernel would need to assume processes will always do this (malicious
426 ones will) and add this extra wait time to the worst case preemption time.
427
428 Finally, a scheduler could try to use non-blocking synchronization (no
429 spinlocks), or one of our other long-term research synchronization methods to
430 avoid deadlock, though we realize this is a pain for userspace for now.  FWIW,
431 there are some OSs out there with only non-blocking synchronization (I think).
432
433 4.4.2: Cascading and overflow
434 -------------------------------
435 There used to be issues with cascading interrupts (when contexts are still
436 running handlers).  Imagine a pagefault, followed by preempting the handler.
437 It doesn't make sense to run the preempt context after the page fault.
438 Earlier designs had issues where it was hard for a vcore to determine the
439 order of events and unmixing preemption, notification, and faults.  We deal
440 with this by having separate slots for preemption and notification, and by
441 treating faults as another form of notification.  Faulting while handling a
442 notification just leads to death.  Perhaps there is a better way to do that.
443
444 Another thing we considered would be to have two stacks - transition for
445 notification and an exception stack for faults.  We'd also need a fault slot
446 for the faulting trapframe.  This begins to take up even more memory, and it
447 is not clear how to handle mixed faults and notifications.  If you fault while
448 on the notification slot, then fine.  But you could fault for other reasons,
449 and then receive a notification.  And then if you fault in that handler, we're
450 back to where we started - might as well just kill them.
451
452 Another issue was overload.  Consider if vcore0 is set up to receive all
453 events.  If events come in faster than it can process them, it will both nest
454 too deep and process out of order.  To handle this, we only notify once, and
455 will not send future active notifications / interrupts until the process
456 issues an "end of interrupt" (EOI) for that vcore.  This is modelled after
457 hardware interrupts (on x86, at least).
458
459 4.4.3: Restarting a Preempted Notification
460 -------------------------------
461 There will be cases where the trapframe in the preempt_tf slot is actually a
462 notification handler, which was running on the transition stack of that
463 particular vcore.  Userspace needs to be careful about restarting contexts
464 that were on those cores.  They can tell by examining the stack pointer to see
465 if it was on a transition stack.  Alternatively, if notifications are masked,
466 it is also likely they in a notification handler.  The real concern is the
467 transition stack.  If a vcore is processing on the transition stack of another
468 vcore, there is a risk that the vcore comes back up and starts clobbering the
469 transition stack.
470
471 To avoid this, userspace should allocate a new transition stack and switch the
472 target vcore to use that new stack (in procdata).  The only time (for now)
473 that the kernel cares about a transition stack is when it is popping a tf on a
474 new or freshly notified vcore.
475
476 This all should be a rare occurance, since the vcore should see the
477 preempt_pending when it starts its notification and yield, instead of being
478 forced into this weird situation.  This also means that notifications should
479 take less time than the kernel will wait before preempting.
480
481 This issue ties in with deadlocking in 4.4.1.  If userspace is never in a
482 notif handler when it gets preempted, that deadlock will not happen (and we
483 also may need only one trapframe slot).  Userspace probably cannot guarantee
484 that, so we'll have to deal with it.  Avoiding the deadlock on a spinlock is
485 much more reasonable (and we can provide the locking function).
486
487 4.4.4: Userspace Yield Races
488 -------------------------------
489 Imagine a vcore realizes it is getting preempted soon, so it starts to yield.
490 However, it is too slow and doesn't make it into the kernel before a preempt
491 message takes over.  When that vcore is run again, it will continue where it
492 left off and yield its core.  The desired outcome is for yield to fail, since
493 the process doesn't really want to yield that core.  To sort this out, yield
494 will take a parameter saying that the yield is in response to a pending
495 preemption.  If the phase is over (preempted and returned), the call will not
496 yield and simply return to userspace.
497
498 4.4.5: Userspace m_yield
499 -------------------------------
500 There are a variety of ways to implement an m_yield (yield the entire MCP).
501 We could have a "no niceness" yield - just immediately preempt, but there is a danger of the
502 locking business.  We could do the usual delay game, though if userspace is
503 requesting its yield, arguably we don't need to give warning. 
504
505 Another approach would be to not have an explicit m_yield call.  Instead, we
506 can provide a notify_all call, where the notification sent to every vcore is
507 to yield.  I imagine we'll have a notify_all (or rather, flags to the notify
508 call) anyway, so we can do this for now.
509
510 The fastest way will probably be the no niceness way.  One way to make this
511 work would be for vcore0 to hold all of the low-level locks (from 4.4.1) and
512 manually unlock them when it wakes up.  Yikes!
513
514 4.5: Random Other Stuff
515 -------------------------------
516 Pre-Notification issues: how much time does userspace need to clean up and
517 yield?  How quickly does the kernel need the core back (for scheduling
518 reasons)?
519
520 Part 5: Old Arguments about Processes vs Partitions
521 ===============================
522 This is based on my interpretation of the cell (formerly what I thought was
523 called a partition).
524
525 5.1: Program vs OS
526 -------------------------------
527 A big difference is what runs inside the object.  I think trying to support
528 OS-like functionality is a quick path to unnecessary layers and complexity,
529 esp for the common case.  This leads to discussions of physical memory
530 management, spawning new programs, virtualizing HW, shadow page tables,
531 exporting protection rings, etc.
532
533 This unnecessarily brings in the baggage and complexity of supporting VMs,
534 which are a special case.  Yes, we want processes to be able to use their
535 resources, but I'd rather approach this from the perspective of "what do they
536 need?" than "how can we make it look like a real machine."  Virtual machines
537 are cool, and paravirtualization influenced a lot of my ideas, but they have
538 their place and I don't think this is it.
539
540 For example, exporting direct control of physical pages is a bad idea.  I
541 wasn't clear if anyone was advocating this or not.  By exposing actual machine
542 physical frames, we lose our ability to do all sorts of things (like swapping,
543 for all practical uses, and other VM tricks).  If the cell/process thinks it
544 is manipulating physical pages, but really isn't, we're in the VM situation of
545 managing nested or shadow page tables, which we don't want.
546
547 For memory, we'd be better off giving an allocation of a quantity frames, not
548 specific frames.  A process can pin up to X pages, for instance.  It can also
549 pick pages to be evicted when there's memory pressure.  There are already
550 similar ideas out there, both in POSIX and in ACPM.
551
552 Instead of mucking with faking multiple programs / entities within an cell,
553 just make more processes.  Otherwise, you'd have to export weird controls that
554 the kernel is doing anyway (and can do better!), and have complicated middle
555 layers.
556
557 5.2: Multiple "Things" in a "partition"
558 -------------------------------
559 In the process-world, the kernel can make a distinction between different
560 entities that are using a block of resources.  Yes, "you" can still do
561 whatever you want with your resources.  But the kernel directly supports
562 useful controls that you want. 
563 - Multiple protection domains are no problem.  They are just multiple
564   processes.  Resource allocation is a separate topic.
565 - Processes can control one another, based on a rational set of rules.  Even
566   if you have just cells, we still need them to be able to control one another
567   (it's a sysadmin thing).
568
569 "What happens in a cell, stays in a cell."  What does this really mean?  If
570 it's about resource allocation and passing of resources around, we can do that
571 with process groups.  If it's about the kernel not caring about what code runs
572 inside a protection domain, a process provides that.  If it's about a "parent"
573 program trying to control/kill/whatever a "child" (even if it's within a cell,
574 in the cell model), you *want* the kernel to be involved.  The kernel is the
575 one that can do protection between entities.
576
577 5.3: Other Things
578 -------------------------------
579 Let the kernel do what it's made to do, and in the best position to do: manage
580 protection and low-level resources.
581
582 Both processes and partitions "have" resources.  They are at different levels
583 in the system.  A process actually gets to use the resources.  A partition is
584 a collection of resources allocated to one or more processes.
585
586 In response to this:
587
588 On 2009-09-15 at 22:33 John Kubiatowicz wrote:
589 > John Shalf wrote:  
590 > >
591 > > Anyhow, Barret is asking that resource requirements attributes be 
592 > > assigned on a process basis rather than partition basis.  We need
593 > > to justify why gang scheduling of a partition and resource
594 > > management should be linked.  
595
596 I want a process to be aware of it's specific resources, as well as the other
597 members of it's partition.  An individual process (which is gang-scheduled in
598 many-core mode) has a specific list of resources.  Its just that the overall
599 'partition of system resources' is separate from the list of specific
600 resources of a process, simply because there can be many processes under the
601 same partition (collection of resources allocated).
602
603 > >  
604 > Simplicity!
605
606 > Yes, we can allow lots of options, but at the end of the day, the 
607 > simplest model that does what we need is likely the best. I don't
608 > want us to hack together a frankenscheduler.  
609
610 My view is also simple in the case of one address space/process per
611 'partition.'  Extending it to multiple address spaces is simply asking that
612 resources be shared between processes, but without design details that I
613 imagine will be brutally complicated in the Cell model.
614
615
616 Part 6: Use Cases
617 ===============================
618 6.1: Matrix Multiply / Trusting Many-core app
619 -------------------------------
620 The process is created by something (bash, for instance).  It's parent makes
621 it runnable.  The process requests a bunch of cores and RAM.  The scheduler
622 decides to give it a certain amount of resources, which creates it's partition
623 (aka, chunk of resources granted to it's process group, of which it is the
624 only member).  The sysadmin can tweak this allocation via procfs.
625
626 The process runs on its cores in it's many-core mode.  It is gang scheduled,
627 and knows how many cores there are.  When the kernel starts the process on
628 it's extra cores, it passes control to a known spot in code (the ELF entry
629 point), with the virtual core id passed as a parameter.
630
631 The code runs from a single binary image, eventually with shared
632 object/library support.  It's view of memory is a virtual address space, but
633 it also can see it's own page tables to see which pages are really resident
634 (similar to POSIX's mincore()).
635
636 When it comes time to lose a core, or be completely preempted, the process is
637 notified by the OS running a handler of the process's choosing (in userspace).
638 The process can choose what to do (pick a core to yield, prepare to be
639 preempted, etc).
640
641 To deal with memory, the process is notified when it page faults, and keeps
642 its core.  The process can pin pages in memory.  If there is memory pressure,
643 the process can tell the kernel which pages to unmap.
644
645 This is the simple case.
646
647 6.2: Browser
648 -------------------------------
649 In this case, a process wants to create multiple protection domains that share
650 the same pool of resources.  Or rather, with it's own allocated resources.
651
652 The browser process is created, as above.  It creates, but does not run, it's
653 untrusted children.  The kernel will have a variety of ways a process can
654 "mess with" a process it controls.  So for this untrusted child, the parent
655 can pass (for example), a file descriptor of what to render, "sandbox" that
656 process (only allow a whitelist of syscalls, e.g. can only read and write
657 descriptors it has).  You can't do this easily in the cell model.
658
659 The parent can also set up a shared memory mapping / channel with the child.
660
661 For resources, the parent can put the child in a subdirectory/ subpartition
662 and give a portion of its resources to that subpartition.  The scheduler will
663 ensure that both the parent and the child are run at the same time, and will
664 give the child process the resources specified.  (cores, RAM, etc).
665
666 After this setup, the parent will then make the child "runnable".  This is why
667 we want to separate the creation from the runnability of a process, which we
668 can't do with the fork/exec model.
669
670 The parent can later kill the child if it wants, reallocate the resources in
671 the partition (perhaps to another process rendering a more important page),
672 preempt that process, whatever.
673
674 6.3: SMP Virtual Machines
675 -------------------------------
676 The main issue (regardless of paravirt or full virt), is that what's running
677 on the cores may or may not trust one another.  One solution is to run each
678 VM-core in it's own process (like with Linux's KVM, it uses N tasks (part of
679 one process) for an N-way SMP VM).  The processes set up the appropriate
680 shared memory mapping between themselves early on.  Another approach would be
681 to allow a many-cored process to install specific address spaces on each
682 core, and interpose on syscalls, privileged instructions, and page faults.
683 This sounds very much like the Cell approach, which may be fine for a VM, but
684 not for the general case of a process.
685
686 Or with a paravirtualized SMP guest, you could (similar to the L4Linux way,)
687 make any Guest OS processes actual processes in our OS.  The resource
688 allocation to the Guest OS partition would be managed by the parent process of
689 the group (which would be running the Guest OS kernel).  We still need to play
690 tricks with syscall redirection.
691
692 For full virtualization, we'd need to make use of hardware virtualization
693 instructions. Dealing with the VMEXITs, emulation, and other things is a real
694 pain, but already done.  The long range plan was to wait til the
695 http://v3vee.org/ project supported Intel's instructions and eventually
696 incorporate that.
697
698 All of these ways involve subtle and not-so-subtle difficulties.  The
699 Cell-as-OS mode will have to deal with them for the common case, which seems
700 brutal.  And rather unnecessary.