proc messages are routine instead of immediate
[akaros.git] / Documentation / kernel_messages.txt
1 kernel_messages.txt
2 Barret Rhoden
3 2010-03-19
4
5 This document explains the basic ideas behind our "kernel messages" and some of
6 the arcane bits behind the implementation.  These were formerly called active
7 messages, since they were an implementation of the low-level hardware messaging.
8
9 Overview:
10 --------------------------------
11 Our kernel messages are just work that is shipped remotely, delayed, or both.
12 They currently consist of a PC and a few arguments.  Initially, they were meant
13 to be a way to immediately execute code on another core (once interrupts are
14 enabled), in the order in which the messages were sent.  This is insufficient
15 (and wasn't what we wanted for the task, incidentally).  We simply want to do
16 work on another core, but not necessarily instantly.  And not necessarily on
17 another core.
18
19 Currently, there are two types, distinguished by which list they are sent to per
20 core: immediate and routine.  Urgent messages will get executed as soon as
21 possible (once interrupts are enabled).  Routine messages will be executed at
22 convenient points in the kernel.  This includes when the kernel is about to pop
23 back to userspace, or smp_idle()ing.  Routine messages are necessary when their
24 function does not return, such as a __startcore, __death, or anything else that
25 can ruin whatever the kernel was doing.  They should also be used if the work is
26 not worth fully interrupting the kernel.  (An IPI will still be sent, but the
27 work will be delayed)
28
29 Kernel messages of a given type will be executed in order.  If immediate
30 messages show up while processing a routine message, the immediate message will
31 get processed next, at the latest.  Even if the routine function doesn't return,
32 once interrupts are reenabled (like when popping to userspace), the
33 __kernel_message() handler will fire again.
34
35 History:
36 --------------------------------
37 A bit of history: we used to use "immediate" messages (when all messages were
38 immediate) for __death calls.  The idea was that we didn't care what the core
39 was doing, since we didn't need to save state or anything.  I could see that
40 there were going to be issues with preemption, since we would want to do some
41 saving of what the core was doing (and what the kernel was doing on its behalf),
42 so we prepared to deal with that.  However, even __death could break certain
43 codes that were holding a reference (and hence a refcnt) for a process, which
44 would prevent the process from ever being cleaned up.  It was a specific case of
45 a job that the kernel needed to finish before executing the message.
46
47 An example of an immediate message would be a TLB_shootdown.  Check current,
48 flush if applicable, and return.  It doesn't harm the kernel at all.  Another
49 example would be certain debug routines.
50
51 Kernel messages are currently an arch-dependent thing, but this ought to change
52 when sparc has IPI functions similar to x86.
53
54 Other Uses:
55 --------------------------------
56 Kernel messages will also be the basis for the alarm system.  All it is is
57 expressing work that needs to be done.  That being said, the k_msg struct will
58 probably receive a timestamp field, among other things.  Routine messages also
59 will replace the old workqueue, which hasn't really been used in 10 months or
60 so.
61
62 To Return or Not:
63 --------------------------------
64 Routine k_msgs do not have to return.  Urgent messages must.  The distinction is
65 in how they are sent (send_kernel_message() will take a flag), so be careful.
66 Technically, an immediate message could not return, but only if the kernel code
67 that was interrupted was not holding any locks, mucking with any invariants, or
68 otherwise doing work that needed to be done.  Those cases seem rather rare.
69
70 To retain some sort of sanity, the functions that do not return must adhere to
71 some rules.  At some point they need to end in a place where they check routine
72 messages or enable interrupts.  Returning to userspace will do this (interrupts
73 are enabled).  __death will eventually call smp_idle(), which will check.  The
74 idea behind this is that route messages will get processed once the kernel is
75 able to (at a convenient place).
76
77 Since some routine messages do not return by popping to userspace, we need to
78 self-ipi to make sure the kernel regains control (this need might go away in the
79 future).  Since we also want immediate messages to get processed before routine
80 messages, and we want the system to be able to have a bunch of outstanding
81 routine messages (though that is unlikely at this point), we briefly check
82 for immed's inside process_routine_kmsg().  By only turning interrupts on for
83 this means we avoid receiving excessive self_ipis for potentially not-returning
84 routine messages.  Keep in mind that each one of those IPIs would be useless,
85 since they will only run their functions when interrupting from userspace.
86
87 Trickiness:
88 --------------------------------
89 If a function does not return, then the code might not check the list again, or
90 send the EOI.  This is one reason why we send the EOI first, and insist that the
91 __kernel_message() handler execute with interrupts disabled.  The routine
92 messages do not need to have their interrupts disabled (if they are executed
93 somewhere else).  If another IPI comes in, immediate messages will run, but
94 other routine messages won't (they will get executed when the list is checked
95 again).  However, enabling interrupts in the __kernel_message() handler can be
96 problematic, depending on when the EOI is sent (nesting on the same code).
97
98 The other reason we send_eoi() first is that we can only send it once per
99 handler (not per message).  Otherwise, it can start acknowleding other interrupt
100 vectors, which is bad.  We might move it in the while loop and protect it with a
101 static check, but it doesn't seem worth it.  We still can't turn on interrupts,
102 since the self_ipi could would fire and return while processing a routine
103 function, negating the intent of the self_ipi.
104
105 Since IPIs get "squashed" (my word, meaning if a core receives more than two at
106 a time, future IPIs for a vector are ignored), and since functions might not
107 return, there is the possibility of losing a message.  There can be more
108 messages than IPIs (imagine three k_msgs, each that doesn't return).  To protect
109 against this, if there is not an IPI pending (you can check on x86), and if
110 there are messages in the routine list, then the code self_ipi's the current
111 core.
112
113 We don't need to check the immediate list, since we just checked it higher in
114 the code (o/w, we wouldn't be executing routine messages).  If an immediate
115 showed up since we executed the lapic_send_eoi(), an IPI will be on the way
116 (messages are enqueued before sending the IPI).
117
118 When we check the routine list, we don't need to lock.  All that macro does is
119 check to see if head->item == 0 (and the list head won't get changed).  It's
120 basically just a read, which gains no protection from a lock.
121
122 Other Notes:
123 --------------------------------
124 Unproven hunch, but the main performance bottleneck with multiple senders and
125 receivers of k_msgs will be the slab allocator.  We use the slab so we can
126 dynamically create the k_msgs (can pass them around easily, delay with them
127 easily (alarms), and most importantly we can't deadlock by running out of room
128 in a static buffer).
129
130 When running our process_routine_kmsg()s, we could have made a userspace process
131 that would get interrupted if there were any outstanding IPIs for routine
132 messages.  We'd have to self_ipi, then switch to this process.  That kinda
133 sucks, and would also mean that when we want to actually smp_idle, we'd have to
134 be in userspace (and probably not cpu_halt()ing).  Making it possible to process
135 the messages from within the kernel seemed much more flexible and better.
136
137 Architecture Dependence:
138 --------------------------------
139 Some details will differ, based on architectural support.  For instance,
140 immediate messages can be implemented with true active messages.  Other systems
141 with maskable IPI vectors can use a different IPI for routine messages, and that
142 interrupt can get masked whenever we enter the kernel (note, that means making
143 every trap gate an interrupt gate), and we unmask that interrupt when we want to
144 process routine messages.