Debian Codegraph @

src/backend/storage/lmgr/README.barrier

raw
1 Memory Barriers
2 ===============
3
4 Modern CPUs make extensive use of pipe-lining and out-of-order execution,
5 meaning that the CPU is often executing more than one instruction at a
6 time, and not necessarily in the order that the source code would suggest.
7 Furthermore, even before the CPU gets a chance to reorder operations, the
8 compiler may (and often does) reorganize the code for greater efficiency,
9 particularly at higher optimization levels. Optimizing compilers and
10 out-of-order execution are both critical for good performance, but they
11 can lead to surprising results when multiple processes access the same
12 memory space.
13
14 Example
15 =======
16
17 Suppose x is a pointer to a structure stored in shared memory, and that the
18 entire structure has been initialized to zero bytes. One backend executes
19 the following code fragment:
20
21 x->foo = 1;
22 x->bar = 1;
23
24 Meanwhile, at approximately the same time, another backend executes this
25 code fragment:
26
27 bar = x->bar;
28 foo = x->foo;
29
30 The second backend might end up with foo = 1 and bar = 1 (if it executes
31 both statements after the first backend), or with foo = 0 and bar = 0 (if
32 it executes both statements before the first backend), or with foo = 1 and
33 bar = 0 (if the first backend executes the first statement, the second
34 backend executes both statements, and then the first backend executes the
35 second statement).
36
37 Surprisingly, however, the second backend could also end up with foo = 0
38 and bar = 1. The compiler might swap the order of the two stores performed
39 by the first backend, or the two loads performed by the second backend.
40 Even if it doesn't, on a machine with weak memory ordering (such as PowerPC
41 or ARM) the CPU might choose to execute either the loads or the stores
42 out of order. This surprising result can lead to bugs.
43
44 A common pattern where this actually does result in a bug is when adding items
45 onto a queue. The writer does this:
46
47 q->items[q->num_items] = new_item;
48 ++q->num_items;
49
50 The reader does this:
51
52 num_items = q->num_items;
53 for (i = 0; i < num_items; ++i)
54 /* do something with q->items[i] */
55
56 This code turns out to be unsafe, because the writer might increment
57 q->num_items before it finishes storing the new item into the appropriate slot.
58 More subtly, the reader might prefetch the contents of the q->items array
59 before reading q->num_items. Thus, there's still a bug here *even if the
60 writer does everything in the order we expect*. We need the writer to update
61 the array before bumping the item counter, and the reader to examine the item
62 counter before examining the array.
63
64 Note that these types of highly counterintuitive bugs can *only* occur when
65 multiple processes are interacting with the same memory segment. A given
66 process always perceives its *own* writes to memory in program order.
67
68 Avoiding Memory Ordering Bugs
69 =============================
70
71 The simplest (and often best) way to avoid memory ordering bugs is to
72 protect the data structures involved with an lwlock. For more details, see
73 src/backend/storage/lmgr/README. For instance, in the above example, the
74 writer could acquire an lwlock in exclusive mode before appending to the
75 queue, and each reader could acquire the same lock in shared mode before
76 reading it. If the data structure is not heavily trafficked, this solution is
77 generally entirely adequate.
78
79 However, in some cases, it is desirable to avoid the overhead of acquiring
80 and releasing locks. In this case, memory barriers may be used to ensure
81 that the apparent order of execution is as the programmer desires. In
82 PostgreSQL backend code, the pg_memory_barrier() macro may be used to achieve
83 this result. In the example above, we can prevent the reader from seeing a
84 garbage value by having the writer do this:
85
86 q->items[q->num_items] = new_item;
87 pg_memory_barrier();
88 ++q->num_items;
89
90 And by having the reader do this:
91
92 num_items = q->num_items;
93 pg_memory_barrier();
94 for (i = 0; i < num_items; ++i)
95 /* do something with q->items[i] */
96
97 The pg_memory_barrier() macro will (1) prevent the compiler from rearranging
98 the code in such a way as to allow the memory accesses to occur out of order
99 and (2) generate any code (often, inline assembly) that is needed to prevent
100 the CPU from executing the memory accesses out of order. Specifically, the
101 barrier prevents loads and stores written after the barrier from being
102 performed before the barrier, and vice-versa.
103
104 Although this code will work, it is needlessly inefficient. On systems with
105 strong memory ordering (such as x86), the CPU never reorders loads with other
106 loads, nor stores with other stores. It can, however, allow a load to be
107 performed before a subsequent store. To avoid emitting unnecessary memory
108 instructions, we provide two additional primitives: pg_read_barrier(), and
109 pg_write_barrier(). When a memory barrier is being used to separate two
110 loads, use pg_read_barrier(); when it is separating two stores, use
111 pg_write_barrier(); when it is a separating a load and a store (in either
112 order), use pg_memory_barrier(). pg_memory_barrier() can always substitute
113 for either a read or a write barrier, but is typically more expensive, and
114 therefore should be used only when needed.
115
116 With these guidelines in mind, the writer can do this:
117
118 q->items[q->num_items] = new_item;
119 pg_write_barrier();
120 ++q->num_items;
121
122 And the reader can do this:
123
124 num_items = q->num_items;
125 pg_read_barrier();
126 for (i = 0; i < num_items; ++i)
127 /* do something with q->items[i] */
128
129 On machines with strong memory ordering, these weaker barriers will simply
130 prevent compiler rearrangement, without emitting any actual machine code.
131 On machines with weak memory ordering, they will prevent compiler
132 reordering and also emit whatever hardware barrier may be required. Even
133 on machines with weak memory ordering, a read or write barrier may be able
134 to use a less expensive instruction than a full barrier.
135
136 Weaknesses of Memory Barriers
137 =============================
138
139 While memory barriers are a powerful tool, and much cheaper than locks, they
140 are also much less capable than locks. Here are some of the problems.
141
142 1. Concurrent writers are unsafe. In the above example of a queue, using
143 memory barriers doesn't make it safe for two processes to add items to the
144 same queue at the same time. If more than one process can write to the queue,
145 a spinlock or lwlock must be used to synchronize access. The readers can
146 perhaps proceed without any lock, but the writers may not.
147
148 Even very simple write operations often require additional synchronization.
149 For example, it's not safe for multiple writers to simultaneously execute
150 this code (supposing x is a pointer into shared memory):
151
152 x->foo++;
153
154 Although this may compile down to a single machine-language instruction,
155 the CPU will execute that instruction by reading the current value of foo,
156 adding one to it, and then storing the result back to the original address.
157 If two CPUs try to do this simultaneously, both may do their reads before
158 either one does their writes. Such a case could be made safe by using an
159 atomic variable and an atomic add. See port/atomics.h.
160
161 2. Eight-byte loads and stores aren't necessarily atomic. We assume in
162 various places in the source code that an aligned four-byte load or store is
163 atomic, and that other processes therefore won't see a half-set value.
164 Sadly, the same can't be said for eight-byte value: on some platforms, an
165 aligned eight-byte load or store will generate two four-byte operations. If
166 you need an atomic eight-byte read or write, you must either serialize access
167 with a lock or use an atomic variable.
168
169 3. No ordering guarantees. While memory barriers ensure that any given
170 process performs loads and stores to shared memory in order, they don't
171 guarantee synchronization. In the queue example above, we can use memory
172 barriers to be sure that readers won't see garbage, but there's nothing to
173 say whether a given reader will run before or after a given writer. If this
174 matters in a given situation, some other mechanism must be used instead of
175 or in addition to memory barriers.
176
177 4. Barrier proliferation. Many algorithms that at first seem appealing
178 require multiple barriers. If the number of barriers required is more than
179 one or two, you may be better off just using a lock. Keep in mind that, on
180 some platforms, a barrier may be implemented by acquiring and releasing a
181 backend-private spinlock. This may be better than a centralized lock under
182 contention, but it may also be slower in the uncontended case.
183
184 Further Reading
185 ===============
186
187 Much of the documentation about memory barriers appears to be quite
188 Linux-specific. The following papers may be helpful:
189
190 Memory Ordering in Modern Microprocessors, by Paul E. McKenney
191 * http://www.rdrop.com/users/paulmck/scalability/paper/ordering.2007.09.19a.pdf
192
193 Memory Barriers: a Hardware View for Software Hackers, by Paul E. McKenney
194 * http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.06.07c.pdf
195
196 The Linux kernel also has some useful documentation on this topic. Start
197 with Documentation/memory-barriers.txt