1================ 2Circular Buffers 3================ 4 5:Author: David Howells <dhowells@redhat.com> 6:Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com> 7 8 9Linux provides a number of features that can be used to implement circular 10buffering. 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 18To use these facilities, as discussed below, there needs to be just one 19producer and just one consumer. It is possible to handle multiple producers by 20serialising them, and to handle multiple consumers by serialising them. 21 22 23.. Contents: 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 35What is a circular buffer? 36========================== 37 38First of all, what is a circular buffer? A circular buffer is a buffer of 39fixed, 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 47Typically when the tail pointer is equal to the head pointer, the buffer is 48empty; and the buffer is full when the head pointer is one less than the tail 49pointer. 50 51The head index is incremented when items are added, and the tail index when 52items are removed. The tail index should never jump the head index, and both 53indices should be wrapped to 0 when they reach the end of the buffer, thus 54allowing an infinite amount of data to flow through the buffer. 55 56Typically, items will all be of the same unit size, but this isn't strictly 57required to use the techniques below. The indices can be increased by more 58than 1 if multiple items or variable-sized items are to be included in the 59buffer, provided that neither index overtakes the other. The implementer must 60be careful, however, as a region more than one unit in size may wrap the end of 61the buffer and be broken into two segments. 62 63Measuring power-of-2 buffers 64============================ 65 66Calculation of the occupancy or the remaining capacity of an arbitrarily sized 67circular buffer would normally be a slow operation, requiring the use of a 68modulus (divide) instruction. However, if the buffer is of a power-of-2 size, 69then a much quicker bitwise-AND instruction can be used instead. 70 71Linux provides a set of macros for handling power-of-2 circular buffers. These 72can be made use of by:: 73 74 #include <linux/circ_buf.h> 75 76The 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 110Each of these macros will nominally return a value between 0 and buffer_size-1, 111however: 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 134Using memory barriers with circular buffers 135=========================================== 136 137By using memory barriers in conjunction with circular buffers, you can avoid 138the 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 145There are two sides to this: the producer that fills the buffer, and the 146consumer that empties it. Only one thing should be filling a buffer at any one 147time, and only one thing should be emptying a buffer at any one time, but the 148two sides can operate simultaneously. 149 150 151The producer 152------------ 153 154The 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 178This will instruct the CPU that the contents of the new item must be written 179before the head index makes it available to the consumer and then instructs the 180CPU that the revised head index must be written before the consumer is woken. 181 182Note that wake_up() does not guarantee any sort of barrier unless something 183is actually awakened. We therefore cannot rely on it for ordering. However, 184there is always one element of the array left empty. Therefore, the 185producer must produce two elements before it could possibly corrupt the 186element currently being read by the consumer. Therefore, the unlock-lock 187pair between consecutive invocations of the consumer provides the necessary 188ordering between the read of the index indicating that the consumer has 189vacated a given element and the write by the producer to that same element. 190 191 192The Consumer 193------------ 194 195The 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 217This will instruct the CPU to make sure the index is up to date before reading 218the new item, and then it shall make sure the CPU has finished reading the item 219before it writes the new tail pointer, which will erase the item. 220 221Note the use of READ_ONCE() and smp_load_acquire() to read the 222opposition index. This prevents the compiler from discarding and 223reloading its cached value. This isn't strictly needed if you can 224be sure that the opposition index will _only_ be used the once. 225The smp_load_acquire() additionally forces the CPU to order against 226subsequent memory references. Similarly, smp_store_release() is used 227in both algorithms to write the thread's index. This documents the 228fact that we are writing to something that can be read concurrently, 229prevents the compiler from tearing the store, and enforces ordering 230against previous accesses. 231 232 233Further reading 234=============== 235 236See also Documentation/memory-barriers.txt for a description of Linux's memory 237barrier facilities. 238