| 1 | ================
|
| 2 | Circular Buffers
|
| 3 | ================
|
| 4 |
|
| 5 | :Author: David Howells <[email protected]>
|
| 6 | :Author: Paul E. McKenney <[email protected]>
|
| 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 |
|
| 23 | |
| 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 |
|
| 34 |
|
| 35 | What is a circular buffer?
|
| 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 |
|
| 63 | Measuring power-of-2 buffers
|
| 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
|
| 72 | can be made use of by::
|
| 73 |
|
| 74 | #include <linux/circ_buf.h>
|
| 75 |
|
| 76 | The macros are:
|
| 77 |
|
| 78 | (#) Measure the remaining capacity of a buffer::
|
| 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 |
|
| 86 | (#) Measure the maximum consecutive immediate space in a buffer::
|
| 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 |
|
| 95 | (#) Measure the occupancy of a buffer::
|
| 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 |
|
| 102 | (#) Measure the non-wrapping occupancy of a buffer::
|
| 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 |
|
| 113 | (1) CIRC_SPACE*() are intended to be used in the producer. To the producer
|
| 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 |
|
| 121 | (2) CIRC_CNT*() are intended to be used in the consumer. To the consumer they
|
| 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 |
|
| 129 | (3) To a third party, the order in which the writes to the indices by the
|
| 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 |
|
| 134 | Using memory barriers with circular buffers
|
| 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 |
|
| 151 | The producer
|
| 152 | ------------
|
| 153 |
|
| 154 | The producer will look something like this::
|
| 155 |
|
| 156 | spin_lock(&producer_lock);
|
| 157 |
|
| 158 | unsigned long head = buffer->head;
|
| 159 | /* The spin_unlock() and next spin_lock() provide needed ordering. */
|
| 160 | unsigned long tail = READ_ONCE(buffer->tail);
|
| 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 |
|
| 168 | smp_store_release(buffer->head,
|
| 169 | (head + 1) & (buffer->size - 1));
|
| 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 |
|
| 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.
|
| 190 |
|
| 191 |
|
| 192 | The Consumer
|
| 193 | ------------
|
| 194 |
|
| 195 | The consumer will look something like this::
|
| 196 |
|
| 197 | spin_lock(&consumer_lock);
|
| 198 |
|
| 199 | /* Read index before reading contents at that index. */
|
| 200 | unsigned long head = smp_load_acquire(buffer->head);
|
| 201 | unsigned long tail = buffer->tail;
|
| 202 |
|
| 203 | if (CIRC_CNT(head, tail, buffer->size) >= 1) {
|
| 204 |
|
| 205 | /* extract one item from the buffer */
|
| 206 | struct item *item = buffer[tail];
|
| 207 |
|
| 208 | consume_item(item);
|
| 209 |
|
| 210 | /* Finish reading descriptor before incrementing tail. */
|
| 211 | smp_store_release(buffer->tail,
|
| 212 | (tail + 1) & (buffer->size - 1));
|
| 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 |
|
| 221 | Note the use of READ_ONCE() and smp_load_acquire() to read the
|
| 222 | opposition index. This prevents the compiler from discarding and
|
| 223 | reloading its cached value. This isn't strictly needed if you can
|
| 224 | be sure that the opposition index will _only_ be used the once.
|
| 225 | The smp_load_acquire() additionally forces the CPU to order against
|
| 226 | subsequent memory references. Similarly, smp_store_release() is used
|
| 227 | in both algorithms to write the thread's index. This documents the
|
| 228 | fact that we are writing to something that can be read concurrently,
|
| 229 | prevents the compiler from tearing the store, and enforces ordering
|
| 230 | against previous accesses.
|
| 231 |
|
| 232 |
|
| 233 | Further reading
|
| 234 | ===============
|
| 235 |
|
| 236 | See also Documentation/memory-barriers.txt for a description of Linux's memory
|
| 237 | barrier facilities.
|