circular-buffers.rst 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237
  1. ================
  2. Circular Buffers
  3. ================
  4. :Author: David Howells <dhowells@redhat.com>
  5. :Author: Paul E. McKenney <paulmck@linux.ibm.com>
  6. Linux provides a number of features that can be used to implement circular
  7. buffering. There are two sets of such features:
  8. (1) Convenience functions for determining information about power-of-2 sized
  9. buffers.
  10. (2) Memory barriers for when the producer and the consumer of objects in the
  11. buffer don't want to share a lock.
  12. To use these facilities, as discussed below, there needs to be just one
  13. producer and just one consumer. It is possible to handle multiple producers by
  14. serialising them, and to handle multiple consumers by serialising them.
  15. .. Contents:
  16. (*) What is a circular buffer?
  17. (*) Measuring power-of-2 buffers.
  18. (*) Using memory barriers with circular buffers.
  19. - The producer.
  20. - The consumer.
  21. What is a circular buffer?
  22. ==========================
  23. First of all, what is a circular buffer? A circular buffer is a buffer of
  24. fixed, finite size into which there are two indices:
  25. (1) A 'head' index - the point at which the producer inserts items into the
  26. buffer.
  27. (2) A 'tail' index - the point at which the consumer finds the next item in
  28. the buffer.
  29. Typically when the tail pointer is equal to the head pointer, the buffer is
  30. empty; and the buffer is full when the head pointer is one less than the tail
  31. pointer.
  32. The head index is incremented when items are added, and the tail index when
  33. items are removed. The tail index should never jump the head index, and both
  34. indices should be wrapped to 0 when they reach the end of the buffer, thus
  35. allowing an infinite amount of data to flow through the buffer.
  36. Typically, items will all be of the same unit size, but this isn't strictly
  37. required to use the techniques below. The indices can be increased by more
  38. than 1 if multiple items or variable-sized items are to be included in the
  39. buffer, provided that neither index overtakes the other. The implementer must
  40. be careful, however, as a region more than one unit in size may wrap the end of
  41. the buffer and be broken into two segments.
  42. Measuring power-of-2 buffers
  43. ============================
  44. Calculation of the occupancy or the remaining capacity of an arbitrarily sized
  45. circular buffer would normally be a slow operation, requiring the use of a
  46. modulus (divide) instruction. However, if the buffer is of a power-of-2 size,
  47. then a much quicker bitwise-AND instruction can be used instead.
  48. Linux provides a set of macros for handling power-of-2 circular buffers. These
  49. can be made use of by::
  50. #include <linux/circ_buf.h>
  51. The macros are:
  52. (#) Measure the remaining capacity of a buffer::
  53. CIRC_SPACE(head_index, tail_index, buffer_size);
  54. This returns the amount of space left in the buffer[1] into which items
  55. can be inserted.
  56. (#) Measure the maximum consecutive immediate space in a buffer::
  57. CIRC_SPACE_TO_END(head_index, tail_index, buffer_size);
  58. This returns the amount of consecutive space left in the buffer[1] into
  59. which items can be immediately inserted without having to wrap back to the
  60. beginning of the buffer.
  61. (#) Measure the occupancy of a buffer::
  62. CIRC_CNT(head_index, tail_index, buffer_size);
  63. This returns the number of items currently occupying a buffer[2].
  64. (#) Measure the non-wrapping occupancy of a buffer::
  65. CIRC_CNT_TO_END(head_index, tail_index, buffer_size);
  66. This returns the number of consecutive items[2] that can be extracted from
  67. the buffer without having to wrap back to the beginning of the buffer.
  68. Each of these macros will nominally return a value between 0 and buffer_size-1,
  69. however:
  70. (1) CIRC_SPACE*() are intended to be used in the producer. To the producer
  71. they will return a lower bound as the producer controls the head index,
  72. but the consumer may still be depleting the buffer on another CPU and
  73. moving the tail index.
  74. To the consumer it will show an upper bound as the producer may be busy
  75. depleting the space.
  76. (2) CIRC_CNT*() are intended to be used in the consumer. To the consumer they
  77. will return a lower bound as the consumer controls the tail index, but the
  78. producer may still be filling the buffer on another CPU and moving the
  79. head index.
  80. To the producer it will show an upper bound as the consumer may be busy
  81. emptying the buffer.
  82. (3) To a third party, the order in which the writes to the indices by the
  83. producer and consumer become visible cannot be guaranteed as they are
  84. independent and may be made on different CPUs - so the result in such a
  85. situation will merely be a guess, and may even be negative.
  86. Using memory barriers with circular buffers
  87. ===========================================
  88. By using memory barriers in conjunction with circular buffers, you can avoid
  89. the need to:
  90. (1) use a single lock to govern access to both ends of the buffer, thus
  91. allowing the buffer to be filled and emptied at the same time; and
  92. (2) use atomic counter operations.
  93. There are two sides to this: the producer that fills the buffer, and the
  94. consumer that empties it. Only one thing should be filling a buffer at any one
  95. time, and only one thing should be emptying a buffer at any one time, but the
  96. two sides can operate simultaneously.
  97. The producer
  98. ------------
  99. The producer will look something like this::
  100. spin_lock(&producer_lock);
  101. unsigned long head = buffer->head;
  102. /* The spin_unlock() and next spin_lock() provide needed ordering. */
  103. unsigned long tail = READ_ONCE(buffer->tail);
  104. if (CIRC_SPACE(head, tail, buffer->size) >= 1) {
  105. /* insert one item into the buffer */
  106. struct item *item = buffer[head];
  107. produce_item(item);
  108. smp_store_release(buffer->head,
  109. (head + 1) & (buffer->size - 1));
  110. /* wake_up() will make sure that the head is committed before
  111. * waking anyone up */
  112. wake_up(consumer);
  113. }
  114. spin_unlock(&producer_lock);
  115. This will instruct the CPU that the contents of the new item must be written
  116. before the head index makes it available to the consumer and then instructs the
  117. CPU that the revised head index must be written before the consumer is woken.
  118. Note that wake_up() does not guarantee any sort of barrier unless something
  119. is actually awakened. We therefore cannot rely on it for ordering. However,
  120. there is always one element of the array left empty. Therefore, the
  121. producer must produce two elements before it could possibly corrupt the
  122. element currently being read by the consumer. Therefore, the unlock-lock
  123. pair between consecutive invocations of the consumer provides the necessary
  124. ordering between the read of the index indicating that the consumer has
  125. vacated a given element and the write by the producer to that same element.
  126. The Consumer
  127. ------------
  128. The consumer will look something like this::
  129. spin_lock(&consumer_lock);
  130. /* Read index before reading contents at that index. */
  131. unsigned long head = smp_load_acquire(buffer->head);
  132. unsigned long tail = buffer->tail;
  133. if (CIRC_CNT(head, tail, buffer->size) >= 1) {
  134. /* extract one item from the buffer */
  135. struct item *item = buffer[tail];
  136. consume_item(item);
  137. /* Finish reading descriptor before incrementing tail. */
  138. smp_store_release(buffer->tail,
  139. (tail + 1) & (buffer->size - 1));
  140. }
  141. spin_unlock(&consumer_lock);
  142. This will instruct the CPU to make sure the index is up to date before reading
  143. the new item, and then it shall make sure the CPU has finished reading the item
  144. before it writes the new tail pointer, which will erase the item.
  145. Note the use of READ_ONCE() and smp_load_acquire() to read the
  146. opposition index. This prevents the compiler from discarding and
  147. reloading its cached value. This isn't strictly needed if you can
  148. be sure that the opposition index will _only_ be used the once.
  149. The smp_load_acquire() additionally forces the CPU to order against
  150. subsequent memory references. Similarly, smp_store_release() is used
  151. in both algorithms to write the thread's index. This documents the
  152. fact that we are writing to something that can be read concurrently,
  153. prevents the compiler from tearing the store, and enforces ordering
  154. against previous accesses.
  155. Further reading
  156. ===============
  157. See also Documentation/memory-barriers.txt for a description of Linux's memory
  158. barrier facilities.