linux/Documentation/circular-buffers.txt
<<
>>
Prefs
   1                               ================
   2                               CIRCULAR BUFFERS
   3                               ================
   4
   5By: David Howells <dhowells@redhat.com>
   6    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
  23Contents:
  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
  63
  64============================
  65MEASURING POWER-OF-2 BUFFERS
  66============================
  67
  68Calculation of the occupancy or the remaining capacity of an arbitrarily sized
  69circular buffer would normally be a slow operation, requiring the use of a
  70modulus (divide) instruction.  However, if the buffer is of a power-of-2 size,
  71then a much quicker bitwise-AND instruction can be used instead.
  72
  73Linux provides a set of macros for handling power-of-2 circular buffers.  These
  74can be made use of by:
  75
  76        #include <linux/circ_buf.h>
  77
  78The macros are:
  79
  80 (*) Measure the remaining capacity of a buffer:
  81
  82        CIRC_SPACE(head_index, tail_index, buffer_size);
  83
  84     This returns the amount of space left in the buffer[1] into which items
  85     can be inserted.
  86
  87
  88 (*) Measure the maximum consecutive immediate space in a buffer:
  89
  90        CIRC_SPACE_TO_END(head_index, tail_index, buffer_size);
  91
  92     This returns the amount of consecutive space left in the buffer[1] into
  93     which items can be immediately inserted without having to wrap back to the
  94     beginning of the buffer.
  95
  96
  97 (*) Measure the occupancy of a buffer:
  98
  99        CIRC_CNT(head_index, tail_index, buffer_size);
 100
 101     This returns the number of items currently occupying a buffer[2].
 102
 103
 104 (*) Measure the non-wrapping occupancy of a buffer:
 105
 106        CIRC_CNT_TO_END(head_index, tail_index, buffer_size);
 107
 108     This returns the number of consecutive items[2] that can be extracted from
 109     the buffer without having to wrap back to the beginning of the buffer.
 110
 111
 112Each of these macros will nominally return a value between 0 and buffer_size-1,
 113however:
 114
 115 [1] CIRC_SPACE*() are intended to be used in the producer.  To the producer
 116     they will return a lower bound as the producer controls the head index,
 117     but the consumer may still be depleting the buffer on another CPU and
 118     moving the tail index.
 119
 120     To the consumer it will show an upper bound as the producer may be busy
 121     depleting the space.
 122
 123 [2] CIRC_CNT*() are intended to be used in the consumer.  To the consumer they
 124     will return a lower bound as the consumer controls the tail index, but the
 125     producer may still be filling the buffer on another CPU and moving the
 126     head index.
 127
 128     To the producer it will show an upper bound as the consumer may be busy
 129     emptying the buffer.
 130
 131 [3] To a third party, the order in which the writes to the indices by the
 132     producer and consumer become visible cannot be guaranteed as they are
 133     independent and may be made on different CPUs - so the result in such a
 134     situation will merely be a guess, and may even be negative.
 135
 136
 137===========================================
 138USING MEMORY BARRIERS WITH CIRCULAR BUFFERS
 139===========================================
 140
 141By using memory barriers in conjunction with circular buffers, you can avoid
 142the need to:
 143
 144 (1) use a single lock to govern access to both ends of the buffer, thus
 145     allowing the buffer to be filled and emptied at the same time; and
 146
 147 (2) use atomic counter operations.
 148
 149There are two sides to this: the producer that fills the buffer, and the
 150consumer that empties it.  Only one thing should be filling a buffer at any one
 151time, and only one thing should be emptying a buffer at any one time, but the
 152two sides can operate simultaneously.
 153
 154
 155THE PRODUCER
 156------------
 157
 158The producer will look something like this:
 159
 160        spin_lock(&producer_lock);
 161
 162        unsigned long head = buffer->head;
 163        unsigned long tail = ACCESS_ONCE(buffer->tail);
 164
 165        if (CIRC_SPACE(head, tail, buffer->size) >= 1) {
 166                /* insert one item into the buffer */
 167                struct item *item = buffer[head];
 168
 169                produce_item(item);
 170
 171                smp_wmb(); /* commit the item before incrementing the head */
 172
 173                buffer->head = (head + 1) & (buffer->size - 1);
 174
 175                /* wake_up() will make sure that the head is committed before
 176                 * waking anyone up */
 177                wake_up(consumer);
 178        }
 179
 180        spin_unlock(&producer_lock);
 181
 182This will instruct the CPU that the contents of the new item must be written
 183before the head index makes it available to the consumer and then instructs the
 184CPU that the revised head index must be written before the consumer is woken.
 185
 186Note that wake_up() doesn't have to be the exact mechanism used, but whatever
 187is used must guarantee a (write) memory barrier between the update of the head
 188index and the change of state of the consumer, if a change of state occurs.
 189
 190
 191THE CONSUMER
 192------------
 193
 194The consumer will look something like this:
 195
 196        spin_lock(&consumer_lock);
 197
 198        unsigned long head = ACCESS_ONCE(buffer->head);
 199        unsigned long tail = buffer->tail;
 200
 201        if (CIRC_CNT(head, tail, buffer->size) >= 1) {
 202                /* read index before reading contents at that index */
 203                smp_read_barrier_depends();
 204
 205                /* extract one item from the buffer */
 206                struct item *item = buffer[tail];
 207
 208                consume_item(item);
 209
 210                smp_mb(); /* finish reading descriptor before incrementing tail */
 211
 212                buffer->tail = (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
 221
 222Note the use of ACCESS_ONCE() in both algorithms to read the opposition index.
 223This prevents the compiler from discarding and reloading its cached value -
 224which some compilers will do across smp_read_barrier_depends().  This isn't
 225strictly needed if you can be sure that the opposition index will _only_ be
 226used the once.
 227
 228
 229===============
 230FURTHER READING
 231===============
 232
 233See also Documentation/memory-barriers.txt for a description of Linux's memory
 234barrier facilities.
 235
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.