Glibc networking support (XCC)
[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.  There is no need for a second-level scheduler, and
120   the code running is analogous to a user-level thread.
121 - RUNNING_M implies *guaranteed* core(s).  You can be a single core in the
122   RUNNING_M state.  The guarantee is subject to time slicing, but when you
123   run, you get all of your cores.
124 - The time slicing is at a coarser granularity for _M states.  This means that
125   when you run an _S on a core, it should be interrupted/time sliced more
126   often, which also means the core should be classified differently for a
127   while.  Possibly even using it's local APIC timer.
128 - A process in an _M state will be informed about changes to its state, e.g.,
129   will have a handler run in the event of a page fault
130
131 For more details, check out kern/inc/process.h  For valid transitions between
132 these, check out kern/src/process.c's proc_set_state().
133
134 2.2: Creation and Running
135 -------------------------------
136 Unlike the fork-exec model, processes are created, and then explicitly made
137 runnable.  In the time between creation and running, the parent (or another
138 controlling process) can do whatever it wants with the child, such as pass
139 specific file descriptors, map shared memory regions (which can be used to
140 pass arguments).
141
142 New processes are not a copy-on-write version of the parent's address space.
143 Due to our changes in the threading model, we no longer need (or want) this
144 behavior left over from the fork-exec model.
145
146 By splitting the creation from the running and by explicitly sharing state
147 between processes (like inherited file descriptors), we avoid a lot of
148 concurrency and security issues.
149
150 2.3: Vcoreid vs Pcoreid
151 -------------------------------
152 The vcoreid is a virtual cpu number.  Its purpose is to provide an easy way
153 for the kernel and userspace to talk about the same core.  pcoreid (physical)
154 would also work.  The vcoreid makes things a little easier, such as when a
155 process wants to refer to one of its other cores (not the calling core).  It
156 also makes the event notification mechanisms easier to specify and maintain.
157
158 Processes that care about locality should check what their pcoreid is.  This
159 is currently done via sys_getcpuid().  The name will probably change.
160
161 2.4: Transitioning to and from states
162 -------------------------------
163 2.4.1: To go from _S to _M, a process requests cores.
164 --------------
165 A resource request from 0 to 1 or more causes a transition from _S to _M.  The
166 calling context is saved in the notification slot (notif_tf) in vcore0's
167 preemption data (in procdata).  The second level scheduler needs to be able to
168 restart the context when vcore0 starts up.  To do this, it will need to save the
169 TLS/TCB descriptor and the floating point/silly state (if applicable) in the
170 user-thread control block, and do whatever is needed to signal vcore0 to run the
171 _S context when it starts up.  One way would be to mark vcore0's "active thread"
172 variable to point to the _S thread.  When vcore0 starts up at
173 _start/vcore_entry() (like all vcores), it will see a thread was running there
174 and restart it.  The kernel will migrate the _S thread's silly state (FP) to the
175 new pcore, so that it looks like the process was simply running the _S thread
176 and got notified.  Odds are, it will want to just restart that thread, but the
177 kernel won't assume that (hence the notification).
178
179 In general, all cores (and all subsequently allocated cores) start at the elf
180 entry point, with vcoreid in eax or a suitable arch-specific manner.  There is
181 also a syscall to get the vcoreid, but this will save an extra trap at vcore
182 start time.
183
184 Future proc_runs(), like from RUNNABLE_M to RUNNING_M start all cores at the
185 entry point, including vcore0.  The saving of a _S context to vcore0's notif_tf
186 only happens on the transition from _S to _M (which the process needs to be
187 aware of for a variety of reasons).  This also means that userspace needs to
188 handle vcore0 coming up at the entry point again (and not starting the program
189 over).  This is currently done in sysdeps-ros/start.c, via the static variable
190 init.  Note there are some tricky things involving dynamically linked programs,
191 but it all works currently.
192
193 When coming in to the entry point, whether as the result of a startcore or a
194 notification, the kernel will set the stack pointer to whatever is requested
195 by userspace in procdata.  A process should allocate stacks of whatever size
196 it wants for its vcores when it is in _S mode, and write these location to
197 procdata.  These stacks are the transition stacks (in Lithe terms) that are
198 used as jumping-off points for future function calls.  These stacks need to be
199 used in a continuation-passing style, and each time they are used, they start
200 from the top.
201
202 2.4.2: To go from _M to _S, a process requests 0 cores
203 --------------
204 The caller becomes the new _S context.  Everyone else gets trashed
205 (abandon_core()).  Their stacks are still allocated and it is up to userspace
206 to deal with this.  In general, they will regrab their transition stacks when
207 they come back up.  Their other stacks and whatnot (like TBB threads) need to
208 be dealt with.
209
210 When the caller next switches to _M, that context (including its stack)
211 maintains its old vcore identity.  If vcore3 causes the switch to _S mode, it
212 ought to remain vcore3 (lots of things get broken otherwise).
213 As of March 2010, the code does not reflect this.  Don't rely on anything in
214 this section for the time being.
215
216 2.4.3: Requesting more cores while in _M
217 --------------
218 Any core can request more cores and adjust the resource allocation in any way.
219 These new cores come up just like the original new cores in the transition
220 from _S to _M: at the entry point.
221
222 2.4.4: Yielding
223 --------------
224 sys_yield()/proc_yield() will give up the calling core, and may or may not
225 adjust the desired number of cores, subject to its parameters.  Yield is
226 performing two tasks, both of which result in giving up the core.  One is for
227 not wanting the core anymore.  The other is in response to a preemption.  Yield
228 may not be called remotely (ARSC).
229
230 In _S mode, it will transition from RUNNING_S to RUNNABLE_S.  The context is
231 saved in env_tf.
232
233 In _M mode, this yields the calling core.  A yield will *not* transition from _M
234 to _S.  The kernel will rip it out of your vcore list.  A process can yield its
235 cores in any order.  The kernel will "fill in the holes of the vcoremap" for any
236 future new cores requested (e.g., proc A has 4 vcores, yields vcore2, and then
237 asks for another vcore.  The new one will be vcore2).  When any core starts in
238 _M mode, even after a yield, it will come back at the vcore_entry()/_start point.
239
240 Yield will normally adjust your desired amount of vcores to the amount after the
241 calling core is taken.  This is the way a process gives its cores back.
242
243 Yield can also be used to say the process is just giving up the core in response
244 to a pending preemption, but actually wants the core and does not want resource
245 requests to be readjusted.  For example, in the event of a preemption
246 notification, a process may yield (ought to!) so that the kernel does not need
247 to waste effort with full preemption.  This is done by passing in a bool
248 (being_nice), which signals the kernel that it is in response to a preemption.
249 The kernel will not readjust the amt_wanted, and if there is no preemption
250 pending, the kernel will ignore the yield.
251
252 There may be an m_yield(), which will yield all or some of the cores of an MPC,
253 remotely.  This is discussed farther down a bit.  It's not clear what exactly
254 it's purpose would be.
255
256 We also haven't addressed other reasons to yield, or more specifically to wait,
257 such as for an interrupt or an event of some sort.
258
259 2.4.5: Others
260 --------------
261 There are other transitions, mostly self-explanatory.  We don't currently use
262 any WAITING states, since we have nothing to block on yet.  DYING is a state
263 when the kernel is trying to kill your process, which can take a little while
264 to clean up.
265
266 Part 3: Resource Requests
267 ===============================
268 A process can ask for resources from the kernel.  The kernel either grants
269 these requests or not, subject to QoS guarantees, or other scheduler-related
270 criteria.
271
272 A process requests resources, currently via sys_resource_req.  The form of a
273 request is to tell the kernel how much of a resource it wants.  Currently,
274 this is the amt_wanted.  We'll also have a minimum amount wanted, which tells
275 the scheduler not to run the process until the minimum amount of resources are
276 available.
277
278 How the kernel actually grants resources is resource-specific.  In general,
279 there are functions like proc_give_cores() (which gives certain cores to a
280 process) that actually does the allocation, as well as adjusting the
281 amt_granted for that resource.
282
283 For expressing QoS guarantees, we'll probably use something like procfs (as
284 mentioned above) to explicitly tell the scheduler/resource manager what the
285 user/sysadmin wants.  An interface like this ought to be usable both by
286 programs as well as simple filesystem tools (cat, etc).
287
288 Guarantees exist regardless of whether or not the allocation has happened.  An
289 example of this is when a process may be guaranteed to use 8 cores, but
290 currently only needs 2.  Whenever it asks for up to 8 cores, it will get them.
291 The exact nature of the guarantee is TBD, but there will be some sort of
292 latency involved in the guarantee for systems that want to take advantage of
293 idle resources (compared to simply reserving and not allowing anyone else to
294 use them).  A latency of 0 would mean a process wants it instantly, which
295 probably means they ought to be already allocated (and billed to) that
296 process.  
297
298 Part 4: Preemption and Event Notification
299 ===============================
300 Preemption and Notification are tied together.  Preemption is when the kernel
301 takes a resource (specifically, cores).  There are two types core_preempt()
302 (one core) and gang_preempt() (all cores).  Notification (discussed below) is
303 when the kernel informs a process of an event, usually referring to the act of
304 running a function on a core (active notification).
305
306 The rough plan for preemption is to notify beforehand, then take action if
307 userspace doesn't yield.  This is a notification a process can ignore, though
308 it is highly recommended to at least be aware of impending core_preempt()
309 events.
310
311 4.1: Notification Basics
312 -------------------------------
313 One of the philosophical goals of ROS is to expose information up to userspace
314 (and allow requests based on that information).  There will be a variety of
315 events in the system that processes will want to know about.  To handle this,
316 we'll eventually build something like the following.
317
318 All events will have a number, like an interrupt vector.  Each process will
319 have an event queue (per core, described below).  On most architectures, it
320 will be a simple producer-consumer ring buffer sitting in the "shared memory"
321 procdata region (shared between the kernel and userspace).  The kernel writes
322 a message into the buffer with the event number and some other helpful
323 information.
324
325 Additionally, the process may request to be actively notified of specific
326 events.  This is done by having the process write into an event vector table
327 (like an IDT) in procdata.  For each event, the process writes the vcoreid it
328 wants to be notified on.
329
330 4.2: Notification Specifics
331 -------------------------------
332 In procdata there is an array of per-vcore data, holding some
333 preempt/notification information and space for two trapframes: one for
334 notification and one for preemption.
335
336 4.2.1: Overall
337 -----------------------------
338 When a notification arrives to a process under normal circumstances, the
339 kernel places the previous running context in the notification trapframe, and
340 returns to userspace at the program entry point (the elf entry point) on the
341 transition stack.  If a process is already handling a notification on that
342 core, the kernel will not interrupt it.  It is the processes's responsibility
343 to check for more notifications before returning to its normal work.  The
344 process must also unmask notifications (in procdata) before it returns to do
345 normal work.  Unmasking notifications is the signal to the kernel to not
346 bother sending IPIs, and if an IPI is sent before notifications are masked,
347 then the kernel will double-check this flag to make sure interrupts should
348 have arrived.
349
350 Notification unmasking is done by setting the notif_enabled flag (similar to
351 turning interrupts on in hardware).  When a core starts up, this flag is off,
352 meaning that notifications are disabled by default.  It is the process's
353 responsibility to turn on notifications for a given vcore.
354
355 4.2.2: Notif Event Details
356 -----------------------------
357 When the process runs the handler, it is actually starting up at the same
358 location in code as it always does.  To determine if it was a notification or
359 not, simply check the queue and bitmask.  This has the added benefit of allowing
360 a process to notice notifications that it missed previously, or notifs it wanted
361 without active notification (IPI).  If we want to bypass this check by having a
362 magic register signal, we can add that later.  Additionally, the kernel will
363 mask notifications (much like an x86 interrupt gate).  It will also mask
364 notifications when starting a core with a fresh trapframe, since the process
365 will be executing on its transition stack.  The process must check its per-core
366 event queue to see why it was called, and deal with all of the events on the
367 queue.  In the case where the event queue overflows, the kernel will up a
368 counter so the process can at least be aware things are missed.  At the very
369 least, the process will see the notification marked in a bitmask.
370
371 These notification events include things such as: an IO is complete, a
372 preemption is pending to this core, the process just returned from a
373 preemption, there was a trap (divide by 0, page fault), and many other things.
374 We plan to allow this list to grow at runtime (a process can request new event
375 notification types).  These messages will often need some form of a timestamp,
376 especially ones that will expire in meaning (such as a preempt_pending).
377
378 Note that only one notification can be active at a time, including a fault.
379 This means that if a process page faults or something while notifications are
380 masked, the process will simply be killed.    It is up to the process to make
381 sure the appropriate pages are pinned, which it should do before entering _M
382 mode.
383
384 4.2.3: Event Overflow and Non-Messages
385 -----------------------------
386 For missed/overflowed events, and for events that do not need messages (they
387 have no parameters and multiple notifications are irrelevant), the kernel will
388 toggle that event's bit in a bitmask.  For the events that don't want messages,
389 we may have a flag that userspace sets, meaning they just want to know it
390 happened.  This might be too much of a pain, so we'll see.  For notification
391 events that overflowed the queue, the parameters will be lost, but hopefully the
392 application can sort it out.  Again, we'll see.  A specific notif_event should
393 not appear in both the event buffers and in the bitmask.
394
395 It does not make sense for all events to have messages.  Others, it does not
396 make sense to specify a different core on which to run the handler (e.g. page
397 faults).  The notification methods that the process expresses via procdata are
398 suggestions to the kernel.  When they don't make sense, they will be ignored.
399 Some notifications might be unserviceable without messages.  A process needs to
400 have a fallback mechanism.  For example, they can read the vcoremap to see who
401 was lost, or they can restart a thread to cause it to page fault again.
402
403 Event overflow sucks - it leads to a bunch of complications.  Ultimately, what
404 we really want is a limitless amount of notification messages (per core), as
405 well as a limitless amount of notification types.  And we want these to be
406 relayed to userspace without trapping into the kernel. 
407
408 We could do this if we had a way to dynamically manage memory in procdata, with
409 a distrusted process on one side of the relationship.  We could imagine growing
410 procdata dynamically (we plan to, mostly to grow the preempt_data struct as we
411 request more vcores), and then run some sort of heap manager / malloc.  Things
412 get very tricky since the kernel should never follow pointers that userspace can
413 touch.  Additionally, whatever memory management we use becomes a part of the
414 kernel interface.  
415
416 Even if we had that, dynamic notification *types* is tricky - they are
417 identified by a number, not by a specific (list) element.
418
419 For now, this all seems like an unnecessary pain in the ass.  We might adjust it
420 in the future if we come up with clean, clever ways to deal with the problem,
421 which we aren't even sure is a problem yet.
422
423 4.2.4: How to Use and Leave a Transition Stack
424 -----------------------------
425 We considered having the kernel be aware of a process's transition stacks and
426 sizes so that it can detect if a vcore is in a notification handler based on
427 the stack pointer in the trapframe when a trap or interrupt fires.  While
428 cool, the flag for notif_enabled is much easier and just as capable.
429 Userspace needs to be aware of various races, and only enable notifications
430 when it is ready to have its transition stack clobbered.  This means that when
431 switching from big user-thread to user-thread, the process should temporarily
432 disable notifications and reenable them before starting the new thread fully.
433 This is analogous to having a kernel that disables interrupts while in process
434 context.
435
436 A process can fake not being on its transition stack, and even unmapping their
437 stack.  At worst, a vcore could recursively page fault (the kernel does not
438 know it is in a handler, if they keep enabling notifs before faulting), and
439 that would continue til the core is forcibly preempted.  This is not an issue
440 for the kernel.
441
442 When a process wants to use its transition stack, it ought to check
443 preempt_pending, mask notifications, jump to its transition stack, do its work
444 (e.g. process notifications, check for new notifications, schedule a new
445 thread) periodically checking for a pending preemption, and making sure the
446 notification queue/list is empty before moving back to real code.  Then it
447 should jump back to a real stack, unmask notifications, and jump to the newly
448 scheduled thread.
449
450 This can be really tricky.  When userspace is changing threads, it will need to
451 unmask notifs as well as jump to the new thread.  There is a slight race here,
452 but it is okay.  The race is that an IPI can arrive after notifs are unmasked,
453 but before returning to the real user thread.  Then the code will think the
454 notif_tf represents the new user thread, even though it hasn't started (and the
455 PC is wrong).  The trick is to make sure that all state required to start the
456 new thread, as well as future instructions, are all saved within the "stuff"
457 that gets saved in the notif_tf.  When these threading packages change contexts,
458 they ought to push the PC on the stack of the new thread, (then enable notifs)
459 and then execute a return.  If an IPI arrives before the "function return", then
460 when that context gets restarted, it will run the "return" with the appropriate
461 value on the stack still.
462
463 There is a further complication.  The kernel can send an IPI that the process
464 wanted, but the vcore did not get truly interrupted since its notifs were
465 disabled.  There is a race between checking the queue/bitmask and then enabling
466 notifications.  The way we deal with it is that the kernel posts the
467 message/bit, then sets notif_pending.  Then it sends the IPI, which may or may
468 not be received (based on notif_enabled).  (Actually, the kernel only ought to
469 send the IPI if notif_pending was 0 (atomically) and notif_enabled is 1).  When
470 leaving the transition stack, userspace should clear the notif_pending, then
471 check the queue do whatever, and then try to pop the tf.  When popping the tf,
472 after enabling notifications, check notif_pending.  If it is still clear, return
473 without fear of missing a notif.  If it is not clear, it needs to manually
474 notify itself (sys_self_notify) so that it can process the notification that it
475 missed and for which it wanted to receive an IPI.  Before it does this, it needs
476 to clear notif_pending, so the kernel will send it an IPI.  These last parts are
477 handled in pop_ros_tf().
478
479 4.3: Preemption Specifics
480 -------------------------------
481 When a vcore is preempted, the kernel takes whatever context was running (which
482 could be a notification context) and stores it in the preempt trapframe for
483 that vcore in procdata.  There is also a flag (actually a counter) that states
484 if the context there has been sorted out.  Userspace should set this once it
485 has copied out the data and dealt with it accordingly.
486
487 The invariant regarding the preemption slot is that there should never be
488 anything running on a vcore when there is a valid/not-sorted preempt
489 trapframe.  The reason is that a preemption can come in at any time (such as
490 right after returning from a preemption).
491
492 To maintain this invariant, when the kernel starts a vcore, it will run the
493 context that is in the preempt trapframe if the "preempt_tf_valid" seq_ctr is
494 not set.  A process needs to be careful of a race here.  If they are trying to
495 deal with a preempt trapframe (must be from another vcore, btw), the kernel
496 could start to run that trapframe (in case it is granting a core request /
497 proc_startcore()ing).  When the kernel prepares to use the trapframe (which it
498 will do regardless of userspace activities), it will up the seq_ctr.  We use a
499 seq_ctr (mostly just a counter) to avoid ABA-related issues.  If the process
500 notices a change in that flag, it ought to abort its operation.  It can up the
501 counter on its own when it no longer wants the kernel to run that context (this
502 means the preempt_tf can get clobbered).
503
504 4.4: Other trickiness
505 -------------------------------
506 4.4.1: Preemption -> deadlock
507 -------------------------------
508 One issue is that a context can be holding a lock that is necessary for the
509 userspace scheduler to manage preempted threads, and this context can be
510 preempted.  This would deadlock the scheduler.  To assist a process from
511 locking itself up, the kernel will toggle a preempt_pending flag in
512 procdata for that vcore before sending the actual preemption.  Whenever the
513 scheduler is grabbing one of these critical spinlocks, it needs to check that
514 flag first, and yield if a preemption is coming in.
515
516 Another option we may implement is for the process to be able to signal to the
517 kernel that it is in one of these ultra-critical sections by writing a magic
518 value to a specific register in the trapframe.  If there kernel sees this, it
519 will allow the process to run for a little longer.  The issue with this is
520 that the kernel would need to assume processes will always do this (malicious
521 ones will) and add this extra wait time to the worst case preemption time.
522
523 Finally, a scheduler could try to use non-blocking synchronization (no
524 spinlocks), or one of our other long-term research synchronization methods to
525 avoid deadlock, though we realize this is a pain for userspace for now.  FWIW,
526 there are some OSs out there with only non-blocking synchronization (I think).
527
528 4.4.2: Cascading and overflow
529 -------------------------------
530 There used to be issues with cascading interrupts (when contexts are still
531 running handlers).  Imagine a pagefault, followed by preempting the handler.
532 It doesn't make sense to run the preempt context after the page fault.
533 Earlier designs had issues where it was hard for a vcore to determine the
534 order of events and unmixing preemption, notification, and faults.  We deal
535 with this by having separate slots for preemption and notification, and by
536 treating faults as another form of notification.  Faulting while handling a
537 notification just leads to death.  Perhaps there is a better way to do that.
538
539 Another thing we considered would be to have two stacks - transition for
540 notification and an exception stack for faults.  We'd also need a fault slot
541 for the faulting trapframe.  This begins to take up even more memory, and it
542 is not clear how to handle mixed faults and notifications.  If you fault while
543 on the notification slot, then fine.  But you could fault for other reasons,
544 and then receive a notification.  And then if you fault in that handler, we're
545 back to where we started - might as well just kill them.
546
547 Another issue was overload.  Consider if vcore0 is set up to receive all
548 events.  If events come in faster than it can process them, it will both nest
549 too deep and process out of order.  To handle this, we only notify once, and
550 will not send future active notifications / interrupts until the process
551 issues an "end of interrupt" (EOI) for that vcore.  This is modelled after
552 hardware interrupts (on x86, at least).
553
554 4.4.3: Restarting a Preempted Notification
555 -------------------------------
556 There will be cases where the trapframe in the preempt_tf slot is actually a
557 notification handler, which was running on the transition stack of that
558 particular vcore.  Userspace needs to be careful about restarting contexts
559 that were on those cores on different cores.  They can tell by examining the
560 stack pointer to see if it was on a transition stack.  Alternatively, if
561 notifications are masked, it is also likely they in a notification handler.  The
562 real concern is the transition stack.  If a vcore is processing on the
563 transition stack of another vcore, there is a risk that the vcore comes back up
564 and starts clobbering the transition stack.
565
566 To avoid this, userspace could allocate a new transition stack and switch the
567 target vcore to use that new stack (in procdata).  The only time (for now)
568 that the kernel cares about a transition stack is when it is popping a tf on a
569 new or freshly notified vcore.  Something similar will need to be done with TLS.
570
571 This all should be a rare occurance, since the vcore should see the
572 preempt_pending when it starts its notification and yield, instead of being
573 forced into this weird situation.  This also means that notifications should
574 take less time than the kernel will wait before preempting.
575
576 This issue ties in with deadlocking in 4.4.1.  If userspace is never in a
577 notif handler when it gets preempted, that deadlock will not happen (and we
578 also may need only one trapframe slot).  Userspace probably cannot guarantee
579 that, so we'll have to deal with it.  Avoiding the deadlock on a spinlock is
580 much more reasonable (and we can provide the locking function).
581
582 Another thing to keep in mind is that userspace probably won't want to restart a
583 notification handler on a different core.  It's conceivable that they want to
584 take a regular user thread and context and restart it, not a transition context.
585
586 4.4.4: Userspace Yield Races
587 -------------------------------
588 Imagine a vcore realizes it is getting preempted soon, so it starts to yield.
589 However, it is too slow and doesn't make it into the kernel before a preempt
590 message takes over.  When that vcore is run again, it will continue where it
591 left off and yield its core.  The desired outcome is for yield to fail, since
592 the process doesn't really want to yield that core.  To sort this out, yield
593 will take a parameter saying that the yield is in response to a pending
594 preemption.  If the phase is over (preempted and returned), the call will not
595 yield and simply return to userspace.
596
597 4.4.5: Userspace m_yield
598 -------------------------------
599 There are a variety of ways to implement an m_yield (yield the entire MCP).
600 We could have a "no niceness" yield - just immediately preempt, but there is a
601 danger of the locking business.  We could do the usual delay game, though if
602 userspace is requesting its yield, arguably we don't need to give warning. 
603
604 Another approach would be to not have an explicit m_yield call.  Instead, we
605 can provide a notify_all call, where the notification sent to every vcore is
606 to yield.  I imagine we'll have a notify_all (or rather, flags to the notify
607 call) anyway, so we can do this for now.
608
609 The fastest way will probably be the no niceness way.  One way to make this
610 work would be for vcore0 to hold all of the low-level locks (from 4.4.1) and
611 manually unlock them when it wakes up.  Yikes!
612
613 4.5: Random Other Stuff
614 -------------------------------
615 Pre-Notification issues: how much time does userspace need to clean up and
616 yield?  How quickly does the kernel need the core back (for scheduling
617 reasons)?
618
619 Part 5: Old Arguments about Processes vs Partitions
620 ===============================
621 This is based on my interpretation of the cell (formerly what I thought was
622 called a partition).
623
624 5.1: Program vs OS
625 -------------------------------
626 A big difference is what runs inside the object.  I think trying to support
627 OS-like functionality is a quick path to unnecessary layers and complexity,
628 esp for the common case.  This leads to discussions of physical memory
629 management, spawning new programs, virtualizing HW, shadow page tables,
630 exporting protection rings, etc.
631
632 This unnecessarily brings in the baggage and complexity of supporting VMs,
633 which are a special case.  Yes, we want processes to be able to use their
634 resources, but I'd rather approach this from the perspective of "what do they
635 need?" than "how can we make it look like a real machine."  Virtual machines
636 are cool, and paravirtualization influenced a lot of my ideas, but they have
637 their place and I don't think this is it.
638
639 For example, exporting direct control of physical pages is a bad idea.  I
640 wasn't clear if anyone was advocating this or not.  By exposing actual machine
641 physical frames, we lose our ability to do all sorts of things (like swapping,
642 for all practical uses, and other VM tricks).  If the cell/process thinks it
643 is manipulating physical pages, but really isn't, we're in the VM situation of
644 managing nested or shadow page tables, which we don't want.
645
646 For memory, we'd be better off giving an allocation of a quantity frames, not
647 specific frames.  A process can pin up to X pages, for instance.  It can also
648 pick pages to be evicted when there's memory pressure.  There are already
649 similar ideas out there, both in POSIX and in ACPM.
650
651 Instead of mucking with faking multiple programs / entities within an cell,
652 just make more processes.  Otherwise, you'd have to export weird controls that
653 the kernel is doing anyway (and can do better!), and have complicated middle
654 layers.
655
656 5.2: Multiple "Things" in a "partition"
657 -------------------------------
658 In the process-world, the kernel can make a distinction between different
659 entities that are using a block of resources.  Yes, "you" can still do
660 whatever you want with your resources.  But the kernel directly supports
661 useful controls that you want. 
662 - Multiple protection domains are no problem.  They are just multiple
663   processes.  Resource allocation is a separate topic.
664 - Processes can control one another, based on a rational set of rules.  Even
665   if you have just cells, we still need them to be able to control one another
666   (it's a sysadmin thing).
667
668 "What happens in a cell, stays in a cell."  What does this really mean?  If
669 it's about resource allocation and passing of resources around, we can do that
670 with process groups.  If it's about the kernel not caring about what code runs
671 inside a protection domain, a process provides that.  If it's about a "parent"
672 program trying to control/kill/whatever a "child" (even if it's within a cell,
673 in the cell model), you *want* the kernel to be involved.  The kernel is the
674 one that can do protection between entities.
675
676 5.3: Other Things
677 -------------------------------
678 Let the kernel do what it's made to do, and in the best position to do: manage
679 protection and low-level resources.
680
681 Both processes and partitions "have" resources.  They are at different levels
682 in the system.  A process actually gets to use the resources.  A partition is
683 a collection of resources allocated to one or more processes.
684
685 In response to this:
686
687 On 2009-09-15 at 22:33 John Kubiatowicz wrote:
688 > John Shalf wrote:  
689 > >
690 > > Anyhow, Barret is asking that resource requirements attributes be 
691 > > assigned on a process basis rather than partition basis.  We need
692 > > to justify why gang scheduling of a partition and resource
693 > > management should be linked.  
694
695 I want a process to be aware of it's specific resources, as well as the other
696 members of it's partition.  An individual process (which is gang-scheduled in
697 many-core mode) has a specific list of resources.  Its just that the overall
698 'partition of system resources' is separate from the list of specific
699 resources of a process, simply because there can be many processes under the
700 same partition (collection of resources allocated).
701
702 > >  
703 > Simplicity!
704
705 > Yes, we can allow lots of options, but at the end of the day, the 
706 > simplest model that does what we need is likely the best. I don't
707 > want us to hack together a frankenscheduler.  
708
709 My view is also simple in the case of one address space/process per
710 'partition.'  Extending it to multiple address spaces is simply asking that
711 resources be shared between processes, but without design details that I
712 imagine will be brutally complicated in the Cell model.
713
714
715 Part 6: Use Cases
716 ===============================
717 6.1: Matrix Multiply / Trusting Many-core app
718 -------------------------------
719 The process is created by something (bash, for instance).  It's parent makes
720 it runnable.  The process requests a bunch of cores and RAM.  The scheduler
721 decides to give it a certain amount of resources, which creates it's partition
722 (aka, chunk of resources granted to it's process group, of which it is the
723 only member).  The sysadmin can tweak this allocation via procfs.
724
725 The process runs on its cores in it's many-core mode.  It is gang scheduled,
726 and knows how many cores there are.  When the kernel starts the process on
727 it's extra cores, it passes control to a known spot in code (the ELF entry
728 point), with the virtual core id passed as a parameter.
729
730 The code runs from a single binary image, eventually with shared
731 object/library support.  It's view of memory is a virtual address space, but
732 it also can see it's own page tables to see which pages are really resident
733 (similar to POSIX's mincore()).
734
735 When it comes time to lose a core, or be completely preempted, the process is
736 notified by the OS running a handler of the process's choosing (in userspace).
737 The process can choose what to do (pick a core to yield, prepare to be
738 preempted, etc).
739
740 To deal with memory, the process is notified when it page faults, and keeps
741 its core.  The process can pin pages in memory.  If there is memory pressure,
742 the process can tell the kernel which pages to unmap.
743
744 This is the simple case.
745
746 6.2: Browser
747 -------------------------------
748 In this case, a process wants to create multiple protection domains that share
749 the same pool of resources.  Or rather, with it's own allocated resources.
750
751 The browser process is created, as above.  It creates, but does not run, it's
752 untrusted children.  The kernel will have a variety of ways a process can
753 "mess with" a process it controls.  So for this untrusted child, the parent
754 can pass (for example), a file descriptor of what to render, "sandbox" that
755 process (only allow a whitelist of syscalls, e.g. can only read and write
756 descriptors it has).  You can't do this easily in the cell model.
757
758 The parent can also set up a shared memory mapping / channel with the child.
759
760 For resources, the parent can put the child in a subdirectory/ subpartition
761 and give a portion of its resources to that subpartition.  The scheduler will
762 ensure that both the parent and the child are run at the same time, and will
763 give the child process the resources specified.  (cores, RAM, etc).
764
765 After this setup, the parent will then make the child "runnable".  This is why
766 we want to separate the creation from the runnability of a process, which we
767 can't do with the fork/exec model.
768
769 The parent can later kill the child if it wants, reallocate the resources in
770 the partition (perhaps to another process rendering a more important page),
771 preempt that process, whatever.
772
773 6.3: SMP Virtual Machines
774 -------------------------------
775 The main issue (regardless of paravirt or full virt), is that what's running
776 on the cores may or may not trust one another.  One solution is to run each
777 VM-core in it's own process (like with Linux's KVM, it uses N tasks (part of
778 one process) for an N-way SMP VM).  The processes set up the appropriate
779 shared memory mapping between themselves early on.  Another approach would be
780 to allow a many-cored process to install specific address spaces on each
781 core, and interpose on syscalls, privileged instructions, and page faults.
782 This sounds very much like the Cell approach, which may be fine for a VM, but
783 not for the general case of a process.
784
785 Or with a paravirtualized SMP guest, you could (similar to the L4Linux way,)
786 make any Guest OS processes actual processes in our OS.  The resource
787 allocation to the Guest OS partition would be managed by the parent process of
788 the group (which would be running the Guest OS kernel).  We still need to play
789 tricks with syscall redirection.
790
791 For full virtualization, we'd need to make use of hardware virtualization
792 instructions. Dealing with the VMEXITs, emulation, and other things is a real
793 pain, but already done.  The long range plan was to wait til the
794 http://v3vee.org/ project supported Intel's instructions and eventually
795 incorporate that.
796
797 All of these ways involve subtle and not-so-subtle difficulties.  The
798 Cell-as-OS mode will have to deal with them for the common case, which seems
799 brutal.  And rather unnecessary.