Documentation/circular-buffers.txt

   1 ================
   2 Circular Buffers
   3 ================
   4
   5 :Author: David Howells <dhowells@redhat.com>
   6 :Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
   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 .. 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
  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 - 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.
 232
 233
 234 Further reading
 235 ===============
 236
 237 See also Documentation/memory-barriers.txt for a description of Linux's memory
 238 barrier facilities.