← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-lowlatency/precise

« back to all changes in this revision

Viewing changes to Documentation/circular-buffers.txt

  • Committer: Package Import Robot
  • Author(s): Alessio Igor Bogani
  • Date: 2011-10-26 11:13:05 UTC
  • Revision ID: package-import@ubuntu.com-20111026111305-tz023xykf0i6eosh
Tags: upstream-3.2.0
Import upstream version 3.2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
Documentation/circular-buffers.txt
 
1
                               ================
 
2
                               CIRCULAR BUFFERS
 
3
                               ================
 
4
 
 
5
By: David Howells <dhowells@redhat.com>
 
6
    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
 
 
64
============================
 
65
MEASURING POWER-OF-2 BUFFERS
 
66
============================
 
67
 
 
68
Calculation of the occupancy or the remaining capacity of an arbitrarily sized
 
69
circular buffer would normally be a slow operation, requiring the use of a
 
70
modulus (divide) instruction.  However, if the buffer is of a power-of-2 size,
 
71
then a much quicker bitwise-AND instruction can be used instead.
 
72
 
 
73
Linux provides a set of macros for handling power-of-2 circular buffers.  These
 
74
can be made use of by:
 
75
 
 
76
        #include <linux/circ_buf.h>
 
77
 
 
78
The 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
 
 
112
Each of these macros will nominally return a value between 0 and buffer_size-1,
 
113
however:
 
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
===========================================
 
138
USING MEMORY BARRIERS WITH CIRCULAR BUFFERS
 
139
===========================================
 
140
 
 
141
By using memory barriers in conjunction with circular buffers, you can avoid
 
142
the 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
 
 
149
There are two sides to this: the producer that fills the buffer, and the
 
150
consumer that empties it.  Only one thing should be filling a buffer at any one
 
151
time, and only one thing should be emptying a buffer at any one time, but the
 
152
two sides can operate simultaneously.
 
153
 
 
154
 
 
155
THE PRODUCER
 
156
------------
 
157
 
 
158
The 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
 
 
182
This will instruct the CPU that the contents of the new item must be written
 
183
before the head index makes it available to the consumer and then instructs the
 
184
CPU that the revised head index must be written before the consumer is woken.
 
185
 
 
186
Note that wake_up() doesn't have to be the exact mechanism used, but whatever
 
187
is used must guarantee a (write) memory barrier between the update of the head
 
188
index and the change of state of the consumer, if a change of state occurs.
 
189
 
 
190
 
 
191
THE CONSUMER
 
192
------------
 
193
 
 
194
The 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
 
 
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
 
 
222
Note the use of ACCESS_ONCE() in both algorithms to read the opposition index.
 
223
This prevents the compiler from discarding and reloading its cached value -
 
224
which some compilers will do across smp_read_barrier_depends().  This isn't
 
225
strictly needed if you can be sure that the opposition index will _only_ be
 
226
used the once.
 
227
 
 
228
 
 
229
===============
 
230
FURTHER READING
 
231
===============
 
232
 
 
233
See also Documentation/memory-barriers.txt for a description of Linux's memory
 
234
barrier facilities.