Commit | Line | Data |
---|---|---|
f1d8b71c MCC |
1 | ================ |
2 | Circular Buffers | |
3 | ================ | |
90fddabf | 4 | |
f1d8b71c MCC |
5 | :Author: David Howells <dhowells@redhat.com> |
6 | :Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com> | |
90fddabf DH |
7 | |
8 | ||
9 | Linux provides a number of features that can be used to implement circular | |
10 | buffering. There are two sets of such features: | |
11 | ||
12 | (1) Convenience functions for determining information about power-of-2 sized | |
13 | buffers. | |
14 | ||
15 | (2) Memory barriers for when the producer and the consumer of objects in the | |
16 | buffer don't want to share a lock. | |
17 | ||
18 | To use these facilities, as discussed below, there needs to be just one | |
19 | producer and just one consumer. It is possible to handle multiple producers by | |
20 | serialising them, and to handle multiple consumers by serialising them. | |
21 | ||
22 | ||
f1d8b71c | 23 | .. Contents: |
90fddabf DH |
24 | |
25 | (*) What is a circular buffer? | |
26 | ||
27 | (*) Measuring power-of-2 buffers. | |
28 | ||
29 | (*) Using memory barriers with circular buffers. | |
30 | - The producer. | |
31 | - The consumer. | |
32 | ||
33 | ||
f1d8b71c MCC |
34 | |
35 | What is a circular buffer? | |
90fddabf DH |
36 | ========================== |
37 | ||
38 | First of all, what is a circular buffer? A circular buffer is a buffer of | |
39 | fixed, finite size into which there are two indices: | |
40 | ||
41 | (1) A 'head' index - the point at which the producer inserts items into the | |
42 | buffer. | |
43 | ||
44 | (2) A 'tail' index - the point at which the consumer finds the next item in | |
45 | the buffer. | |
46 | ||
47 | Typically when the tail pointer is equal to the head pointer, the buffer is | |
48 | empty; and the buffer is full when the head pointer is one less than the tail | |
49 | pointer. | |
50 | ||
51 | The head index is incremented when items are added, and the tail index when | |
52 | items are removed. The tail index should never jump the head index, and both | |
53 | indices should be wrapped to 0 when they reach the end of the buffer, thus | |
54 | allowing an infinite amount of data to flow through the buffer. | |
55 | ||
56 | Typically, items will all be of the same unit size, but this isn't strictly | |
57 | required to use the techniques below. The indices can be increased by more | |
58 | than 1 if multiple items or variable-sized items are to be included in the | |
59 | buffer, provided that neither index overtakes the other. The implementer must | |
60 | be careful, however, as a region more than one unit in size may wrap the end of | |
61 | the buffer and be broken into two segments. | |
62 | ||
f1d8b71c | 63 | Measuring power-of-2 buffers |
90fddabf DH |
64 | ============================ |
65 | ||
66 | Calculation of the occupancy or the remaining capacity of an arbitrarily sized | |
67 | circular buffer would normally be a slow operation, requiring the use of a | |
68 | modulus (divide) instruction. However, if the buffer is of a power-of-2 size, | |
69 | then a much quicker bitwise-AND instruction can be used instead. | |
70 | ||
71 | Linux provides a set of macros for handling power-of-2 circular buffers. These | |
f1d8b71c | 72 | can be made use of by:: |
90fddabf DH |
73 | |
74 | #include <linux/circ_buf.h> | |
75 | ||
76 | The macros are: | |
77 | ||
f1d8b71c | 78 | (#) Measure the remaining capacity of a buffer:: |
90fddabf DH |
79 | |
80 | CIRC_SPACE(head_index, tail_index, buffer_size); | |
81 | ||
82 | This returns the amount of space left in the buffer[1] into which items | |
83 | can be inserted. | |
84 | ||
85 | ||
f1d8b71c | 86 | (#) Measure the maximum consecutive immediate space in a buffer:: |
90fddabf DH |
87 | |
88 | CIRC_SPACE_TO_END(head_index, tail_index, buffer_size); | |
89 | ||
90 | This returns the amount of consecutive space left in the buffer[1] into | |
91 | which items can be immediately inserted without having to wrap back to the | |
92 | beginning of the buffer. | |
93 | ||
94 | ||
f1d8b71c | 95 | (#) Measure the occupancy of a buffer:: |
90fddabf DH |
96 | |
97 | CIRC_CNT(head_index, tail_index, buffer_size); | |
98 | ||
99 | This returns the number of items currently occupying a buffer[2]. | |
100 | ||
101 | ||
f1d8b71c | 102 | (#) Measure the non-wrapping occupancy of a buffer:: |
90fddabf DH |
103 | |
104 | CIRC_CNT_TO_END(head_index, tail_index, buffer_size); | |
105 | ||
106 | This returns the number of consecutive items[2] that can be extracted from | |
107 | the buffer without having to wrap back to the beginning of the buffer. | |
108 | ||
109 | ||
110 | Each of these macros will nominally return a value between 0 and buffer_size-1, | |
111 | however: | |
112 | ||
f1d8b71c | 113 | (1) CIRC_SPACE*() are intended to be used in the producer. To the producer |
90fddabf DH |
114 | they will return a lower bound as the producer controls the head index, |
115 | but the consumer may still be depleting the buffer on another CPU and | |
116 | moving the tail index. | |
117 | ||
118 | To the consumer it will show an upper bound as the producer may be busy | |
119 | depleting the space. | |
120 | ||
f1d8b71c | 121 | (2) CIRC_CNT*() are intended to be used in the consumer. To the consumer they |
90fddabf DH |
122 | will return a lower bound as the consumer controls the tail index, but the |
123 | producer may still be filling the buffer on another CPU and moving the | |
124 | head index. | |
125 | ||
126 | To the producer it will show an upper bound as the consumer may be busy | |
127 | emptying the buffer. | |
128 | ||
f1d8b71c | 129 | (3) To a third party, the order in which the writes to the indices by the |
90fddabf DH |
130 | producer and consumer become visible cannot be guaranteed as they are |
131 | independent and may be made on different CPUs - so the result in such a | |
132 | situation will merely be a guess, and may even be negative. | |
133 | ||
f1d8b71c | 134 | Using memory barriers with circular buffers |
90fddabf DH |
135 | =========================================== |
136 | ||
137 | By using memory barriers in conjunction with circular buffers, you can avoid | |
138 | the need to: | |
139 | ||
140 | (1) use a single lock to govern access to both ends of the buffer, thus | |
141 | allowing the buffer to be filled and emptied at the same time; and | |
142 | ||
143 | (2) use atomic counter operations. | |
144 | ||
145 | There are two sides to this: the producer that fills the buffer, and the | |
146 | consumer that empties it. Only one thing should be filling a buffer at any one | |
147 | time, and only one thing should be emptying a buffer at any one time, but the | |
148 | two sides can operate simultaneously. | |
149 | ||
150 | ||
f1d8b71c | 151 | The producer |
90fddabf DH |
152 | ------------ |
153 | ||
f1d8b71c | 154 | The producer will look something like this:: |
90fddabf DH |
155 | |
156 | spin_lock(&producer_lock); | |
157 | ||
158 | unsigned long head = buffer->head; | |
6c43c091 | 159 | /* The spin_unlock() and next spin_lock() provide needed ordering. */ |
01e46442 | 160 | unsigned long tail = READ_ONCE(buffer->tail); |
90fddabf DH |
161 | |
162 | if (CIRC_SPACE(head, tail, buffer->size) >= 1) { | |
163 | /* insert one item into the buffer */ | |
164 | struct item *item = buffer[head]; | |
165 | ||
166 | produce_item(item); | |
167 | ||
6c43c091 PM |
168 | smp_store_release(buffer->head, |
169 | (head + 1) & (buffer->size - 1)); | |
90fddabf DH |
170 | |
171 | /* wake_up() will make sure that the head is committed before | |
172 | * waking anyone up */ | |
173 | wake_up(consumer); | |
174 | } | |
175 | ||
176 | spin_unlock(&producer_lock); | |
177 | ||
178 | This will instruct the CPU that the contents of the new item must be written | |
179 | before the head index makes it available to the consumer and then instructs the | |
180 | CPU that the revised head index must be written before the consumer is woken. | |
181 | ||
9873552f PM |
182 | Note that wake_up() does not guarantee any sort of barrier unless something |
183 | is actually awakened. We therefore cannot rely on it for ordering. However, | |
184 | there is always one element of the array left empty. Therefore, the | |
185 | producer must produce two elements before it could possibly corrupt the | |
186 | element currently being read by the consumer. Therefore, the unlock-lock | |
187 | pair between consecutive invocations of the consumer provides the necessary | |
188 | ordering between the read of the index indicating that the consumer has | |
189 | vacated a given element and the write by the producer to that same element. | |
90fddabf DH |
190 | |
191 | ||
f1d8b71c | 192 | The Consumer |
90fddabf DH |
193 | ------------ |
194 | ||
f1d8b71c | 195 | The consumer will look something like this:: |
90fddabf DH |
196 | |
197 | spin_lock(&consumer_lock); | |
198 | ||
6c43c091 PM |
199 | /* Read index before reading contents at that index. */ |
200 | unsigned long head = smp_load_acquire(buffer->head); | |
90fddabf DH |
201 | unsigned long tail = buffer->tail; |
202 | ||
203 | if (CIRC_CNT(head, tail, buffer->size) >= 1) { | |
90fddabf DH |
204 | |
205 | /* extract one item from the buffer */ | |
206 | struct item *item = buffer[tail]; | |
207 | ||
208 | consume_item(item); | |
209 | ||
6c43c091 PM |
210 | /* Finish reading descriptor before incrementing tail. */ |
211 | smp_store_release(buffer->tail, | |
212 | (tail + 1) & (buffer->size - 1)); | |
90fddabf DH |
213 | } |
214 | ||
215 | spin_unlock(&consumer_lock); | |
216 | ||
217 | This will instruct the CPU to make sure the index is up to date before reading | |
218 | the new item, and then it shall make sure the CPU has finished reading the item | |
219 | before it writes the new tail pointer, which will erase the item. | |
220 | ||
01e46442 | 221 | Note the use of READ_ONCE() and smp_load_acquire() to read the |
6c43c091 PM |
222 | opposition index. This prevents the compiler from discarding and |
223 | reloading its cached value - which some compilers will do across | |
224 | smp_read_barrier_depends(). This isn't strictly needed if you can | |
225 | be sure that the opposition index will _only_ be used the once. | |
226 | The smp_load_acquire() additionally forces the CPU to order against | |
227 | subsequent memory references. Similarly, smp_store_release() is used | |
228 | in both algorithms to write the thread's index. This documents the | |
229 | fact that we are writing to something that can be read concurrently, | |
230 | prevents the compiler from tearing the store, and enforces ordering | |
231 | against previous accesses. | |
90fddabf DH |
232 | |
233 | ||
f1d8b71c | 234 | Further reading |
90fddabf DH |
235 | =============== |
236 | ||
237 | See also Documentation/memory-barriers.txt for a description of Linux's memory | |
238 | barrier facilities. |