Kernel messages 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 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 Trickiness:
71 --------------------------------
72 If a function does not return, then the code might not check the list again, or
73 send the EOI.  This is one reason why we send the EOI first, and insist that the
74 __kernel_message() handler execute with interrupts disabled.  The routine
75 messages do not need to have their interrupts disabled (if they are executed
76 somewhere else).  If another IPI comes in, immediate messages will run, but
77 other routine messages won't (they will get executed when the list is checked
78 again).  However, enabling interrupts in the __kernel_message() handler can be
79 problematic, depending on when the EOI is sent (nesting on the same code).
80
81 The other reason we send_eoi() first is that we can only send it once per
82 handler (not per message).  Otherwise, it can start acknowleding other interrupt
83 vectors, which is bad.  We might move it in the while loop and protect it with a
84 static check, but it doesn't seem worth it.  We still can't turn on interrupts,
85 since the self_ipi could would fire and return while processing a routine
86 function, negating the intent of the self_ipi.
87
88 Since IPIs get "squashed" (my word, meaning if a core receives more than two at
89 a time, future IPIs for a vector are ignored), and since functions might not
90 return, there is the possibility of losing a message.  There can be more
91 messages than IPIs (imagine three k_msgs, each that doesn't return).  To protect
92 against this, if there is not an IPI pending (you can check on x86), and if
93 there are messages in the routine list, then the code self_ipi's the current
94 core.
95
96 We don't need to check the immediate list, since we just checked it higher in
97 the code (o/w, we wouldn't be executing routine messages).  If an immediate
98 showed up since we executed the lapic_send_eoi(), an IPI will be on the way
99 (messages are enqueued before sending the IPI).
100
101 When we check the routine list, we don't need to lock.  All that macro does is
102 check to see if head->item == 0 (and the list head won't get changed).  It's
103 basically just a read, which gains no protection from a lock.
104
105 Other Notes:
106 --------------------------------
107 Unproven hunch, but the main performance bottleneck with multiple senders and
108 receivers of k_msgs will be the slab allocator.  We use the slab so we can
109 dynamically create the k_msgs (can pass them around easily, delay with them
110 easily (alarms), and most importantly we can't deadlock by running out of room
111 in a static buffer).
112
113 Architecture Dependence:
114 --------------------------------
115 Some details will differ, based on architectural support.  For instance,
116 immediate messages can be implemented with true active messages.  Other systems
117 with maskable IPI vectors can use a different IPI for routine messages, and that
118 interrupt can get masked whenever we enter the kernel (note, that means making
119 every trap gate an interrupt gate), and we unmask that interrupt when we want to
120 process routine messages.