Fixes XCC texinfo dependency
[akaros.git] / Documentation / memory_barriers.txt
1 memory_barriers.txt
2 Barret Rhoden
3
4 1. Overview
5 2. General Rules
6 3. Use in the Code Base
7 4. Memory Barriers and Locking
8 5. Other Stuff
9
10 1. Overview
11 ====================
12 Memory barriers exist to make sure the compiler and the CPU do what we intend.
13 The compiler memory barreir (cmb()) (called an optimization barrier in linux)
14 prevents the compliler from reordering operations.  However, CPUs can also
15 reorder reads and writes, in an architecture-dependent manner.  In most places
16 with shared memory synchronization, you'll need some form of memory barriers.
17
18 These barriers apply to 'unrelated' reads and writes.  The compiler or the CPU
19 cannot detect any relationship between them, so it believes it is safe to
20 reorder them.  The problem arises in that we attach some meaning to them,
21 often in the form of signalling other cores.
22
23 CPU memory barriers only apply when talking to different cores or hardware
24 devices.  They do not matter when dealing with your own core (perhaps between
25 a uthread and vcore context, running on the same core).  cmb()s still matter,
26 even when the synchronizing code runs on the same core.  See Section 3 for
27 more details.
28
29 2. General Rules
30 ====================
31 2.1: Types of Memory Barriers
32 ---------------------
33 For CPU memory barriers, we have 5 types. 
34 - rmb() no reordering of reads with future reads
35 - wmb() no reordering of writes with future writes
36 - wrmb() no reordering of writes with future reads
37 - rwmb() no reordering of reads with future writes
38 - mb() no reordering of reads or writes with future reads or writes
39
40 All 5 of these have a cmb() built in. (a "memory" clobber).
41
42 Part of the reason for the distinction between wrmb/rwmb and the full mb is
43 that on many machines (x86), rwmb() is a noop (for us).
44
45 These barriers are used on 'normal' reads and writes, and they do not include
46 streaming/SSE instructions and string ops (on x86), and they do not include
47 talking with hardware devices.  For memory barriers for those types of
48 operations, use the _f variety (force), e.g. rmb() -> rmb_f().
49
50 2.2: Atomics
51 ---------------------
52 Most atomic operations, such as atomic_inc(), provide some form of memory
53 barrier protection.  Specifically, all read-modify-write (RMW) atomic ops act
54 as a CPU memory barrier (like an mb()), but do *not* provide a cmb().  They
55 only provide a cmb() on the variables they apply to (i.e., variables in the
56 clobber list).  
57
58 I considered making all atomics clobber "memory" (like the cmb()), but
59 sync_fetch_and_add() and friends do not do this by default, and it also means
60 that any use of atomics (even when we don't require a cmb()) then provides a
61 cmb().
62
63 Also note that not all atomic operations are RMW.  atomic_set(), _init(), and
64 _read() do not enforce a memory barrier in the CPU.  If in doubt, look for the
65 LOCK in the assembly (except for xchg, which is a locking function).  We're
66 taking advantage of the LOCK the atomics provide to serialize and synchronize
67 our memory.
68
69 In a lot of places, even if we have an atomic I'll still put in the expected
70 mb (e.g., a rmb()), especially if it clarifies the code.  When I rely on the
71 atomic's LOCK, I'll make a note of it (such as in spinlock code).
72
73 Finally, note that the atomic RMWs handle the mb_f()s just like they handle
74 the regular memory barriers.  The LOCK prefix does quite a bit.
75
76 These rules are a bit x86 specific, so for now other architectures will need
77 to implement their atomics such that they provide the same effects.
78
79 2.3: Locking
80 ---------------------
81 If you access shared memory variables only when inside locks, then you do not
82 need to worry about memory barriers.  The details are sorted out in the
83 locking code.
84
85 3. Use in the Code Base
86 ====================
87 Figuring out how / when / if to use memory barriers is relatively easy.
88 - First, notice when  you are using shared memory to synchronize.  Any time
89   you are using a global variable or working on structs that someone else
90   might look at concurrently, and you aren't using locks or another vetted
91   tool (like krefs), then you need to worry about this.
92 - Second, determine what reads and writes you are doing.
93 - Third, determine who you are talking to.
94
95 If you're talking to other cores or devices, you need CPU mbs.  If not, a cmb
96 suffices.  Based on the types of reads and writes you are doing, just pick one
97 of the 5 memory barriers.
98
99 3.1: What's a Read or Write?
100 ---------------------
101 When writing code that synchronizes with other threads via shared memory, we
102 have a variety of patterns.  Most infamous is the "signal, then check if the
103 receiver is still listening", which is the critical part of the "check,
104 signal, check again" pattern.  For examples, look at things like
105 'notif_pending' and when we check VC_CAN_RCV_MSG in event.c.
106
107 In these examples, "write" and "read" include things such as posting events or
108 checking flags (which ultimately involve writes and reads).  You need to be
109 aware that some functions, such as TAILQ_REMOVE are writes, even though it is
110 not written as *x = 3;.  Whatever your code is, you should be able to point
111 out what are the critical variables and their interleavings.  You should see
112 how a CPU reordering would break your algorithm just like a poorly timed
113 interrupt or other concurrent interleaving.
114
115 When looking at a function that we consider a signal/write, you need to know
116 what it does.  It might handle its memory barriers internally (protecting its
117 own memory operations).  However, it might not.  In general, I err on the side
118 of extra mbs, or at the very least leave a comment about what I am doing and
119 what sort of barriers I desire from the code.
120
121 3.2: Who Are We Talking To?
122 ---------------------
123 CPU memory barriers are necessary when synchronizing/talking with remote cores
124 or devices, but not when "talking" with your own core.  For instance, if you
125 issue two writes, then read them, you will see both writes (reads may not be
126 reorderd with older writes to the same location on a single processor, and
127 your reads get served out of the write buffer).  Note, the read can
128 pass/happen before the write, but the CPU gives you the correct value that the
129 write gave you (store-buffer forwarding).  Other cores may not see both of
130 them due to reordering magic.  Put another way, since those remote processors
131 didn't do the initial writing, the rule about reading the same location
132 doesn't apply to them.
133
134 Given this, when finding spots in the code that may require a mb(), I think
135 about signalling a concurrent viewer on a different core.  A classic example
136 is when we signal to say "process an item".  Say we were on one core and
137 filled the struct out and then signalled, if we then started reading from that
138 same core, we would see our old write (you see writes you previously wrote),
139 but someone else on another core may see the signal before the filled out
140 struct.  
141
142 There is still a distinction between the compiler reordering code and the
143 processor reordering code.  Imagine the case of "filling a struct, then
144 posting the pointer to the struct".  If the compiler reorders, the pointer may
145 be posted before the struct is filled, and an interrupt may come in.  The
146 interrupt handler may look at that structure and see invalid data.  This has
147 nothing to do with the CPU reordering - simply the compiler messed with you.
148 Note this only matters if we care about a concurrent interleaving (interrupt
149 handler with a kthread for instance), and we ought to be aware that there is
150 some shared state being mucked with.
151
152 For a more complicated example, consider DONT_MIGRATE and reading vcoreid.
153 Logically, we want to make sure the vcoreid read doesn't come before the flag
154 write (since uthread code now thinks it is on a particular vcore).  This
155 write, then read would normally require a wrmb(), but is that overkill?
156 Clearly, we need the compiler to issue the writes in order, so we need a cmb()
157 at least.  Here's the code that the processor will get:
158         orl    $0x1,0x254(%edi)      (write DONT_MIGRATE)
159         mov    $0xfffffff0,%ebp      (getting ready with the TLS)
160         mov    %gs:0x0(%ebp),%esi    (reading the vcoreid from TLS)
161
162 Do we need a wrmb() here?  Any remote code might see the write after the
163 vcoreid read, but the read is a bit different than normal ones.  We aren't
164 reading global memory, and we aren't trying to synchronize with another core.
165 All that matters is that if the thread running this code saw the vcoreid read,
166 then whoever reads the flag sees the write.
167
168 The 'whoever' is not concurrently running code - it is 2LS code that either
169 runs on the vcore due to an IPI/notification, or it is 2LS code running
170 remotely that responded to a preemption of that vcore.  Both of these cases
171 require an IPI.  AFAIK, interrupts serialize memory operations, so whatever
172 writes were issued before the interrupt hit memory (or cache) before we even
173 do things like write out the trapframe of the thread.  If this isn't true,
174 then the synchronization we do when writing out the trapframe (before allowing
175 a remote core to try and recover the preempted uthread), will handle the
176 DONT_MIGRATE write.
177
178 Anyway, the point is that remote code will look at it, but only when told to
179 look.  That "telling" is the write, which happens after the
180 synchronizing/serializing events of the IPI path.
181
182 4. Memory Barriers and Locking
183 ====================
184 The implementation of locks require memory barriers (both compiler and CPU).
185 Regular users of locks do not need to worry about this.  Lock implementers do.
186
187 We need to consider reorderings of reads and writes from before and after the
188 lock/unlock write.  In these next sections, the reads and writes I talk about
189 are from a given thread/CPU.  Protected reads/writes are those that happen
190 while the lock is held.  When I say you need a wmb(), you could get by with a
191 cmb() and an atomic-RMW op: just so long as you have the cmb() and the
192 approrpiate CPU mb() at a minimum.
193
194 4.1: Locking
195 ---------------------
196 - Don't care about our reads or writes before the lock happening after the
197   lock write.
198 - Don't want protected writes slipping out before the lock write, need a wmb()
199   after the lock write.
200 - Don't want protected reads slipping out before the lock write, need a wrmb()
201   after the lock write.
202
203 4.2: Unlocking
204 ---------------------
205 - Don't want protected writes slipping out after the unlock, so we need a
206   wmb() before the unlock write.
207 - Don't want protected reads slipping out after the unlock, so we need a
208   rwmb() before the unlock write.  Arguably, there is some causality that
209   makes this less meaningful (what did you do with the info? if not a write
210   that was protected, then who cares? )
211 - Don't care about reads or writes after the unlock happening earlier than the
212   unlock write.
213
214 5. Other Stuff
215 ====================
216 Linux has a lot of work on memory barriers, far more advanced than our stuff.
217 Some of it doesn't make any sense.  I've asked our architects about things
218 like read_barrier_depends() and a few other things.  They also support some
219 non-Intel x86 clones that need wmb_f() in place of a wmb() (support out of
220 order writes).  If this pops up, we'll deal with it.
221
222 I chatted with Andrew a bit, and it turns out the following needs a barrier
223 on P2 under the Alpha's memory model:
224
225         (global) int x = 0, *p = 0;
226         
227         P1:
228         x = 3;
229         FENCE
230         p = &x;
231         
232         P2:
233         while (p == NULL) ;
234         assert(*p == 3);
235
236 As far as we can figure, you'd need some sort of 'value-speculating' hardware
237 to make this an issue in practice.  For now, we'll mark these spots in the code
238 if we see them, but I'm not overly concerned about it.
239         
240 Also note that none of these barriers deal with things like page talble walks,
241 page/segmentation update writes, non-temporal hints on writes, etc.  glhf with
242 that, future self!