Kthread infrastructure
[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 Immediate kernel messages are executed in interrupt context.  Routine messages
36 may technically be done in interrupt context (it's a nebulous term) because they
37 are executed because of an interrupt handler, but from the kernel's perspective
38 they are like executing in regular context (like when a process makes a syscall,
39 aka real "process context").  This is because there are no concerns about the
40 kernel holding locks or otherwise "interrupting" its own execution.  Routine
41 messages are a little different than just trapping into the kernel, since the
42 functions don't have to return and may result in clobbering the kernel stack.
43 Also note that this behavior is dependent on where we call
44 process_routine_kmsg().  Don't call it somewhere you need to return to.
45
46 History:
47 --------------------------------
48 A bit of history: we used to use "immediate" messages (when all messages were
49 immediate) for __death calls.  The idea was that we didn't care what the core
50 was doing, since we didn't need to save state or anything.  I could see that
51 there were going to be issues with preemption, since we would want to do some
52 saving of what the core was doing (and what the kernel was doing on its behalf),
53 so we prepared to deal with that.  However, even __death could break certain
54 codes that were holding a reference (and hence a refcnt) for a process, which
55 would prevent the process from ever being cleaned up.  It was a specific case of
56 a job that the kernel needed to finish before executing the message.
57
58 An example of an immediate message would be a TLB_shootdown.  Check current,
59 flush if applicable, and return.  It doesn't harm the kernel at all.  Another
60 example would be certain debug routines.
61
62 Kernel messages are currently an arch-dependent thing, but this ought to change
63 when sparc has IPI functions similar to x86.
64
65 Other Uses:
66 --------------------------------
67 Kernel messages will also be the basis for the alarm system.  All it is is
68 expressing work that needs to be done.  That being said, the k_msg struct will
69 probably receive a timestamp field, among other things.  Routine messages also
70 will replace the old workqueue, which hasn't really been used in 10 months or
71 so.
72
73 To Return or Not:
74 --------------------------------
75 Routine k_msgs do not have to return.  Urgent messages must.  The distinction is
76 in how they are sent (send_kernel_message() will take a flag), so be careful.
77 Technically, an immediate message could not return, but only if the kernel code
78 that was interrupted was not holding any locks, mucking with any invariants, or
79 otherwise doing work that needed to be done.  Those cases seem rather rare.
80
81 To retain some sort of sanity, the functions that do not return must adhere to
82 some rules.  At some point they need to end in a place where they check routine
83 messages or enable interrupts.  Returning to userspace will do this (interrupts
84 are enabled).  __death will eventually call smp_idle(), which will check.  The
85 idea behind this is that route messages will get processed once the kernel is
86 able to (at a convenient place).
87
88 Since some routine messages do not return by popping to userspace, we need to
89 self-ipi to make sure the kernel regains control (this need might go away in the
90 future).  Since we also want immediate messages to get processed before routine
91 messages, and we want the system to be able to have a bunch of outstanding
92 routine messages (though that is unlikely at this point), we briefly check
93 for immed's inside process_routine_kmsg().  By only turning interrupts on for
94 this means we avoid receiving excessive self_ipis for potentially not-returning
95 routine messages.  Keep in mind that each one of those IPIs would be useless,
96 since they will only run their functions when interrupting from userspace.
97
98 Trickiness:
99 --------------------------------
100 If a function does not return, then the code might not check the list again, or
101 send the EOI.  This is one reason why we send the EOI first, and insist that the
102 __kernel_message() handler execute with interrupts disabled.  The routine
103 messages do not need to have their interrupts disabled (if they are executed
104 somewhere else).  If another IPI comes in, immediate messages will run, but
105 other routine messages won't (they will get executed when the list is checked
106 again).  However, enabling interrupts in the __kernel_message() handler can be
107 problematic, depending on when the EOI is sent (nesting on the same code).
108
109 The other reason we send_eoi() first is that we can only send it once per
110 handler (not per message).  Otherwise, it can start acknowleding other interrupt
111 vectors, which is bad.  We might move it in the while loop and protect it with a
112 static check, but it doesn't seem worth it.  We still can't turn on interrupts,
113 since the self_ipi could would fire and return while processing a routine
114 function, negating the intent of the self_ipi.
115
116 Since IPIs get "squashed" (my word, meaning if a core receives more than two at
117 a time, future IPIs for a vector are ignored), and since functions might not
118 return, there is the possibility of losing a message.  There can be more
119 messages than IPIs (imagine three k_msgs, each that doesn't return).  To protect
120 against this, if there is not an IPI pending (you can check on x86), and if
121 there are messages in the routine list, then the code self_ipi's the current
122 core.
123
124 We don't need to check the immediate list, since we just checked it higher in
125 the code (o/w, we wouldn't be executing routine messages).  If an immediate
126 showed up since we executed the lapic_send_eoi(), an IPI will be on the way
127 (messages are enqueued before sending the IPI).
128
129 When we check the routine list, we don't need to lock.  All that macro does is
130 check to see if head->item == 0 (and the list head won't get changed).  It's
131 basically just a read, which gains no protection from a lock.
132
133 Other Notes:
134 --------------------------------
135 Unproven hunch, but the main performance bottleneck with multiple senders and
136 receivers of k_msgs will be the slab allocator.  We use the slab so we can
137 dynamically create the k_msgs (can pass them around easily, delay with them
138 easily (alarms), and most importantly we can't deadlock by running out of room
139 in a static buffer).
140
141 When running our process_routine_kmsg()s, we could have made a userspace process
142 that would get interrupted if there were any outstanding IPIs for routine
143 messages.  We'd have to self_ipi, then switch to this process.  That kinda
144 sucks, and would also mean that when we want to actually smp_idle, we'd have to
145 be in userspace (and probably not cpu_halt()ing).  Making it possible to process
146 the messages from within the kernel seemed much more flexible and better.
147
148 Architecture Dependence:
149 --------------------------------
150 Some details will differ, based on architectural support.  For instance,
151 immediate messages can be implemented with true active messages.  Other systems
152 with maskable IPI vectors can use a different IPI for routine messages, and that
153 interrupt can get masked whenever we enter the kernel (note, that means making
154 every trap gate an interrupt gate), and we unmask that interrupt when we want to
155 process routine messages.