Back to home page

LXR

 
 

    


0001                                ================
0002                                CIRCULAR BUFFERS
0003                                ================
0004 
0005 By: David Howells <dhowells@redhat.com>
0006     Paul E. McKenney <paulmck@linux.vnet.ibm.com>
0007 
0008 
0009 Linux provides a number of features that can be used to implement circular
0010 buffering.  There are two sets of such features:
0011 
0012  (1) Convenience functions for determining information about power-of-2 sized
0013      buffers.
0014 
0015  (2) Memory barriers for when the producer and the consumer of objects in the
0016      buffer don't want to share a lock.
0017 
0018 To use these facilities, as discussed below, there needs to be just one
0019 producer and just one consumer.  It is possible to handle multiple producers by
0020 serialising them, and to handle multiple consumers by serialising them.
0021 
0022 
0023 Contents:
0024 
0025  (*) What is a circular buffer?
0026 
0027  (*) Measuring power-of-2 buffers.
0028 
0029  (*) Using memory barriers with circular buffers.
0030      - The producer.
0031      - The consumer.
0032 
0033 
0034 ==========================
0035 WHAT IS A CIRCULAR BUFFER?
0036 ==========================
0037 
0038 First of all, what is a circular buffer?  A circular buffer is a buffer of
0039 fixed, finite size into which there are two indices:
0040 
0041  (1) A 'head' index - the point at which the producer inserts items into the
0042      buffer.
0043 
0044  (2) A 'tail' index - the point at which the consumer finds the next item in
0045      the buffer.
0046 
0047 Typically when the tail pointer is equal to the head pointer, the buffer is
0048 empty; and the buffer is full when the head pointer is one less than the tail
0049 pointer.
0050 
0051 The head index is incremented when items are added, and the tail index when
0052 items are removed.  The tail index should never jump the head index, and both
0053 indices should be wrapped to 0 when they reach the end of the buffer, thus
0054 allowing an infinite amount of data to flow through the buffer.
0055 
0056 Typically, items will all be of the same unit size, but this isn't strictly
0057 required to use the techniques below.  The indices can be increased by more
0058 than 1 if multiple items or variable-sized items are to be included in the
0059 buffer, provided that neither index overtakes the other.  The implementer must
0060 be careful, however, as a region more than one unit in size may wrap the end of
0061 the buffer and be broken into two segments.
0062 
0063 
0064 ============================
0065 MEASURING POWER-OF-2 BUFFERS
0066 ============================
0067 
0068 Calculation of the occupancy or the remaining capacity of an arbitrarily sized
0069 circular buffer would normally be a slow operation, requiring the use of a
0070 modulus (divide) instruction.  However, if the buffer is of a power-of-2 size,
0071 then a much quicker bitwise-AND instruction can be used instead.
0072 
0073 Linux provides a set of macros for handling power-of-2 circular buffers.  These
0074 can be made use of by:
0075 
0076         #include <linux/circ_buf.h>
0077 
0078 The macros are:
0079 
0080  (*) Measure the remaining capacity of a buffer:
0081 
0082         CIRC_SPACE(head_index, tail_index, buffer_size);
0083 
0084      This returns the amount of space left in the buffer[1] into which items
0085      can be inserted.
0086 
0087 
0088  (*) Measure the maximum consecutive immediate space in a buffer:
0089 
0090         CIRC_SPACE_TO_END(head_index, tail_index, buffer_size);
0091 
0092      This returns the amount of consecutive space left in the buffer[1] into
0093      which items can be immediately inserted without having to wrap back to the
0094      beginning of the buffer.
0095 
0096 
0097  (*) Measure the occupancy of a buffer:
0098 
0099         CIRC_CNT(head_index, tail_index, buffer_size);
0100 
0101      This returns the number of items currently occupying a buffer[2].
0102 
0103 
0104  (*) Measure the non-wrapping occupancy of a buffer:
0105 
0106         CIRC_CNT_TO_END(head_index, tail_index, buffer_size);
0107 
0108      This returns the number of consecutive items[2] that can be extracted from
0109      the buffer without having to wrap back to the beginning of the buffer.
0110 
0111 
0112 Each of these macros will nominally return a value between 0 and buffer_size-1,
0113 however:
0114 
0115  [1] CIRC_SPACE*() are intended to be used in the producer.  To the producer
0116      they will return a lower bound as the producer controls the head index,
0117      but the consumer may still be depleting the buffer on another CPU and
0118      moving the tail index.
0119 
0120      To the consumer it will show an upper bound as the producer may be busy
0121      depleting the space.
0122 
0123  [2] CIRC_CNT*() are intended to be used in the consumer.  To the consumer they
0124      will return a lower bound as the consumer controls the tail index, but the
0125      producer may still be filling the buffer on another CPU and moving the
0126      head index.
0127 
0128      To the producer it will show an upper bound as the consumer may be busy
0129      emptying the buffer.
0130 
0131  [3] To a third party, the order in which the writes to the indices by the
0132      producer and consumer become visible cannot be guaranteed as they are
0133      independent and may be made on different CPUs - so the result in such a
0134      situation will merely be a guess, and may even be negative.
0135 
0136 
0137 ===========================================
0138 USING MEMORY BARRIERS WITH CIRCULAR BUFFERS
0139 ===========================================
0140 
0141 By using memory barriers in conjunction with circular buffers, you can avoid
0142 the need to:
0143 
0144  (1) use a single lock to govern access to both ends of the buffer, thus
0145      allowing the buffer to be filled and emptied at the same time; and
0146 
0147  (2) use atomic counter operations.
0148 
0149 There are two sides to this: the producer that fills the buffer, and the
0150 consumer that empties it.  Only one thing should be filling a buffer at any one
0151 time, and only one thing should be emptying a buffer at any one time, but the
0152 two sides can operate simultaneously.
0153 
0154 
0155 THE PRODUCER
0156 ------------
0157 
0158 The producer will look something like this:
0159 
0160         spin_lock(&producer_lock);
0161 
0162         unsigned long head = buffer->head;
0163         /* The spin_unlock() and next spin_lock() provide needed ordering. */
0164         unsigned long tail = READ_ONCE(buffer->tail);
0165 
0166         if (CIRC_SPACE(head, tail, buffer->size) >= 1) {
0167                 /* insert one item into the buffer */
0168                 struct item *item = buffer[head];
0169 
0170                 produce_item(item);
0171 
0172                 smp_store_release(buffer->head,
0173                                   (head + 1) & (buffer->size - 1));
0174 
0175                 /* wake_up() will make sure that the head is committed before
0176                  * waking anyone up */
0177                 wake_up(consumer);
0178         }
0179 
0180         spin_unlock(&producer_lock);
0181 
0182 This will instruct the CPU that the contents of the new item must be written
0183 before the head index makes it available to the consumer and then instructs the
0184 CPU that the revised head index must be written before the consumer is woken.
0185 
0186 Note that wake_up() does not guarantee any sort of barrier unless something
0187 is actually awakened.  We therefore cannot rely on it for ordering.  However,
0188 there is always one element of the array left empty.  Therefore, the
0189 producer must produce two elements before it could possibly corrupt the
0190 element currently being read by the consumer.  Therefore, the unlock-lock
0191 pair between consecutive invocations of the consumer provides the necessary
0192 ordering between the read of the index indicating that the consumer has
0193 vacated a given element and the write by the producer to that same element.
0194 
0195 
0196 THE CONSUMER
0197 ------------
0198 
0199 The consumer will look something like this:
0200 
0201         spin_lock(&consumer_lock);
0202 
0203         /* Read index before reading contents at that index. */
0204         unsigned long head = smp_load_acquire(buffer->head);
0205         unsigned long tail = buffer->tail;
0206 
0207         if (CIRC_CNT(head, tail, buffer->size) >= 1) {
0208 
0209                 /* extract one item from the buffer */
0210                 struct item *item = buffer[tail];
0211 
0212                 consume_item(item);
0213 
0214                 /* Finish reading descriptor before incrementing tail. */
0215                 smp_store_release(buffer->tail,
0216                                   (tail + 1) & (buffer->size - 1));
0217         }
0218 
0219         spin_unlock(&consumer_lock);
0220 
0221 This will instruct the CPU to make sure the index is up to date before reading
0222 the new item, and then it shall make sure the CPU has finished reading the item
0223 before it writes the new tail pointer, which will erase the item.
0224 
0225 Note the use of READ_ONCE() and smp_load_acquire() to read the
0226 opposition index.  This prevents the compiler from discarding and
0227 reloading its cached value - which some compilers will do across
0228 smp_read_barrier_depends().  This isn't strictly needed if you can
0229 be sure that the opposition index will _only_ be used the once.
0230 The smp_load_acquire() additionally forces the CPU to order against
0231 subsequent memory references.  Similarly, smp_store_release() is used
0232 in both algorithms to write the thread's index.  This documents the
0233 fact that we are writing to something that can be read concurrently,
0234 prevents the compiler from tearing the store, and enforces ordering
0235 against previous accesses.
0236 
0237 
0238 ===============
0239 FURTHER READING
0240 ===============
0241 
0242 See also Documentation/memory-barriers.txt for a description of Linux's memory
0243 barrier facilities.