About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Documentation / circular-buffers.txt


Based on kernel version 4.16.1. Page generated on 2018-04-09 11:52 EST.

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.  This isn't strictly needed if you can
224	be sure that the opposition index will _only_ be used the once.
225	The smp_load_acquire() additionally forces the CPU to order against
226	subsequent memory references.  Similarly, smp_store_release() is used
227	in both algorithms to write the thread's index.  This documents the
228	fact that we are writing to something that can be read concurrently,
229	prevents the compiler from tearing the store, and enforces ordering
230	against previous accesses.
231	
232	
233	Further reading
234	===============
235	
236	See also Documentation/memory-barriers.txt for a description of Linux's memory
237	barrier facilities.
Hide Line Numbers


About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog