/[svn]/linuxsampler/trunk/src/common/RingBuffer.h
ViewVC logotype

Contents of /linuxsampler/trunk/src/common/RingBuffer.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1790 - (show annotations) (download) (as text)
Sun Nov 2 12:05:00 2008 UTC (15 years, 4 months ago) by persson
File MIME type: text/x-c++hdr
File size: 20334 byte(s)
* added memory ordering constraints to improve stability on multi-core
  and multi-cpu systems

1 /***************************************************************************
2 * *
3 * LinuxSampler - modular, streaming capable sampler *
4 * *
5 * Copyright (C) 2003, 2004 by Benno Senoner and Christian Schoenebeck *
6 * Copyright (C) 2005 - 2008 Christian Schoenebeck *
7 * *
8 * This program is free software; you can redistribute it and/or modify *
9 * it under the terms of the GNU General Public License as published by *
10 * the Free Software Foundation; either version 2 of the License, or *
11 * (at your option) any later version. *
12 * *
13 * This program is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16 * GNU General Public License for more details. *
17 * *
18 * You should have received a copy of the GNU General Public License *
19 * along with this program; if not, write to the Free Software *
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, *
21 * MA 02111-1307 USA *
22 ***************************************************************************/
23
24 #ifndef RINGBUFFER_H
25 #define RINGBUFFER_H
26
27 #define DEFAULT_WRAP_ELEMENTS 0
28
29 #include <string.h>
30
31 #include "lsatomic.h"
32
33 using LinuxSampler::atomic;
34 using LinuxSampler::memory_order_relaxed;
35 using LinuxSampler::memory_order_acquire;
36 using LinuxSampler::memory_order_release;
37
38
39 /** @brief Real-time safe and type safe RingBuffer implementation.
40 *
41 * This constant size buffer can be used to send data from exactly one
42 * sender / writing thread to exactly one receiver / reading thread. It is
43 * real-time safe due to the fact that data is only allocated when this
44 * RingBuffer is created and no system level mechanisms are used for
45 * ensuring thread safety of this class.
46 *
47 * <b>Important:</b> There are two distinct behaviors of this RingBuffer
48 * which has to be given as template argument @c T_DEEP_COPY, which is a
49 * boolean flag:
50 *
51 * - @c true: The RingBuffer will copy elements of type @c T by using type
52 * @c T's assignment operator. This behavior is mandatory for all data
53 * structures (classes) which additionally allocate memory on the heap.
54 * Type @c T's needs to have an assignment operator implementation though,
55 * otherwise this will cause a compilation error. This behavior is more
56 * safe, but usually slower (except for very small buffer sizes, where it
57 * might be even faster).
58 * - @c false: The RingBuffer will copy elements of type @c T by flatly
59 * copying their structural data ( i.e. with @c memcpy() ) in one piece.
60 * This will only work if class @c T (and all of its subelements) does not
61 * allocate any additional data on the heap by itself. So use this option
62 * with great care, because otherwise it will result in very ugly behavior
63 * and crashes! For larger buffer sizes, this behavior will most probably
64 * be faster.
65 */
66 template<class T, bool T_DEEP_COPY>
67 class RingBuffer
68 {
69 public:
70 RingBuffer (int sz, int wrap_elements = DEFAULT_WRAP_ELEMENTS) :
71 write_ptr(0), read_ptr(0) {
72 int power_of_two;
73
74 this->wrap_elements = wrap_elements;
75
76 for (power_of_two = 1;
77 1<<power_of_two < sz;
78 power_of_two++);
79
80 size = 1<<power_of_two;
81 size_mask = size;
82 size_mask -= 1;
83 buf = new T[size + wrap_elements];
84 };
85
86 virtual ~RingBuffer() {
87 delete [] buf;
88 }
89
90 /**
91 * Sets all remaining write space elements to zero. The write pointer
92 * will currently not be incremented after, but that might change in
93 * future.
94 *
95 * @e Caution: for @c T_DEEP_COPY=true you might probably @e NOT want
96 * to call this method at all, at least not in case type @c T allocates
97 * any additional data on the heap by itself.
98 */
99 inline void fill_write_space_with_null() {
100 int w = write_ptr.load(memory_order_relaxed),
101 r = read_ptr.load(memory_order_acquire);
102 memset(get_write_ptr(), 0, sizeof(T)*write_space_to_end());
103 if (r && w >= r) {
104 memset(get_buffer_begin(), 0, sizeof(T)*(r - 1));
105 }
106
107 // set the wrap space elements to null
108 if (wrap_elements) memset(&buf[size], 0, sizeof(T)*wrap_elements);
109 }
110
111 __inline int read (T *dest, int cnt);
112 __inline int write (T *src, int cnt);
113
114 inline int push(T* src) { return write(src,1); }
115 inline int pop(T* dst) { return read(dst,1); }
116
117 __inline T *get_buffer_begin();
118
119 __inline T *get_read_ptr(void) {
120 return(&buf[read_ptr.load(memory_order_relaxed)]);
121 }
122
123 /**
124 * Returns a pointer to the element from the current read position,
125 * advanced by \a offset elements.
126 */
127 /*inline T* get_read_ptr(int offset) {
128 int r = read_ptr.load(memory_order_relaxed);
129 r += offset;
130 r &= size_mask;
131 return &buf[r];
132 }*/
133
134 __inline T *get_write_ptr();
135 __inline void increment_read_ptr(int cnt) {
136 read_ptr.store((read_ptr.load(memory_order_relaxed) + cnt) & size_mask, memory_order_release);
137 }
138 __inline void set_read_ptr(int val) {
139 read_ptr.store(val, memory_order_release);
140 }
141
142 __inline void increment_write_ptr(int cnt) {
143 write_ptr.store((write_ptr.load(memory_order_relaxed) + cnt) & size_mask, memory_order_release);
144 }
145
146 /* this function increments the write_ptr by cnt, if the buffer wraps then
147 subtract size from the write_ptr value so that it stays within 0<write_ptr<size
148 use this function to increment the write ptr after you filled the buffer
149 with a number of elements given by write_space_to_end_with_wrap().
150 This ensures that the data that is written to the buffer fills up all
151 the wrap space that resides past the regular buffer. The wrap_space is needed for
152 interpolation. So that the audio thread sees the ringbuffer like a linear space
153 which allows us to use faster routines.
154 When the buffer wraps the wrap part is memcpy()ied to the beginning of the buffer
155 and the write ptr incremented accordingly.
156 */
157 __inline void increment_write_ptr_with_wrap(int cnt) {
158 int w = write_ptr.load(memory_order_relaxed);
159 w += cnt;
160 if(w >= size) {
161 w -= size;
162 copy(&buf[0], &buf[size], w);
163 //printf("DEBUG !!!! increment_write_ptr_with_wrap: buffer wrapped, elements wrapped = %d (wrap_elements %d)\n",w,wrap_elements);
164 }
165 write_ptr.store(w, memory_order_release);
166 }
167
168 /* this function returns the available write space in the buffer
169 when the read_ptr > write_ptr it returns the space inbetween, otherwise
170 when the read_ptr < write_ptr it returns the space between write_ptr and
171 the buffer end, including the wrap_space.
172 There is an exception to it. When read_ptr <= wrap_elements. In that
173 case we return the write space to buffer end (-1) without the wrap_elements,
174 this is needed because a subsequent increment_write_ptr which copies the
175 data that resides into the wrap space to the beginning of the buffer and increments
176 the write_ptr would cause the write_ptr overstepping the read_ptr which would be an error.
177 So basically the if(r<=wrap_elements) we return the buffer space to end - 1 which
178 ensures that at the next call there will be one element free to write before the buffer wraps
179 and usually (except in EOF situations) the next write_space_to_end_with_wrap() will return
180 1 + wrap_elements which ensures that the wrap part gets fully filled with data
181 */
182 __inline int write_space_to_end_with_wrap() {
183 int w, r;
184
185 w = write_ptr.load(memory_order_relaxed);
186 r = read_ptr.load(memory_order_acquire);
187 //printf("write_space_to_end: w=%d r=%d\n",w,r);
188 if(r > w) {
189 //printf("DEBUG: write_space_to_end_with_wrap: r>w r=%d w=%d val=%d\n",r,w,r - w - 1);
190 return(r - w - 1);
191 }
192 if(r <= wrap_elements) {
193 //printf("DEBUG: write_space_to_end_with_wrap: ATTENTION r <= wrap_elements: r=%d w=%d val=%d\n",r,w,size - w -1);
194 return(size - w -1);
195 }
196 if(r) {
197 //printf("DEBUG: write_space_to_end_with_wrap: r=%d w=%d val=%d\n",r,w,size - w + wrap_elements);
198 return(size - w + wrap_elements);
199 }
200 //printf("DEBUG: write_space_to_end_with_wrap: r=0 w=%d val=%d\n",w,size - w - 1 + wrap_elements);
201 return(size - w - 1 + wrap_elements);
202 }
203
204 /* this function adjusts the number of elements to write into the ringbuffer
205 in a way that the size boundary is avoided and that the wrap space always gets
206 entirely filled.
207 cnt contains the write_space_to_end_with_wrap() amount while
208 capped_cnt contains a capped amount of samples to read.
209 normally capped_cnt == cnt but in some cases eg when the disk thread needs
210 to refill tracks with smaller blocks because lots of streams require immediate
211 refill because lots of notes were started simultaneously.
212 In that case we set for example capped_cnt to a fixed amount (< cnt, eg 64k),
213 which helps to reduce the buffer refill latencies that occur between streams.
214 the first if() checks if the current write_ptr + capped_cnt resides within
215 the wrap area but is < size+wrap_elements. in that case we cannot return
216 capped_cnt because it would lead to a write_ptr wrapping and only a partial fill
217 of wrap space which would lead to errors. So we simply return cnt which ensures
218 that the the entire wrap space will get filled correctly.
219 In all other cases (which are not problematic because no write_ptr wrapping
220 occurs) we simply return capped_cnt.
221 */
222 __inline int adjust_write_space_to_avoid_boundary(int cnt, int capped_cnt) {
223 int w;
224 w = write_ptr.load(memory_order_relaxed);
225 if((w+capped_cnt) >= size && (w+capped_cnt) < (size+wrap_elements)) {
226 //printf("adjust_write_space_to_avoid_boundary returning cnt = %d\n",cnt);
227 return(cnt);
228 }
229 //printf("adjust_write_space_to_avoid_boundary returning capped_cnt = %d\n",capped_cnt);
230 return(capped_cnt);
231 }
232
233 __inline int write_space_to_end() {
234 int w, r;
235
236 w = write_ptr.load(memory_order_relaxed);
237 r = read_ptr.load(memory_order_acquire);
238 //printf("write_space_to_end: w=%d r=%d\n",w,r);
239 if(r > w) return(r - w - 1);
240 if(r) return(size - w);
241 return(size - w - 1);
242 }
243
244 __inline int read_space_to_end() {
245 int w, r;
246
247 w = write_ptr.load(memory_order_acquire);
248 r = read_ptr.load(memory_order_relaxed);
249 if(w >= r) return(w - r);
250 return(size - r);
251 }
252 __inline void init() {
253 write_ptr.store(0, memory_order_relaxed);
254 read_ptr.store(0, memory_order_relaxed);
255 // wrap=0;
256 }
257
258 int write_space () {
259 int w, r;
260
261 w = write_ptr.load(memory_order_relaxed);
262 r = read_ptr.load(memory_order_acquire);
263
264 if (w > r) {
265 return ((r - w + size) & size_mask) - 1;
266 } else if (w < r) {
267 return (r - w) - 1;
268 } else {
269 return size - 1;
270 }
271 }
272
273 int read_space () {
274 int w, r;
275
276 w = write_ptr.load(memory_order_acquire);
277 r = read_ptr.load(memory_order_relaxed);
278
279 if (w >= r) {
280 return w - r;
281 } else {
282 return (w - r + size) & size_mask;
283 }
284 }
285
286 int size;
287 int wrap_elements;
288
289 /**
290 * Independent, random access reading from a RingBuffer. This class
291 * allows to read from a RingBuffer without being forced to free read
292 * data while reading / positioning.
293 */
294 template<class T1, bool T1_DEEP_COPY>
295 class _NonVolatileReader {
296 public:
297 int read_space() {
298 int r = read_ptr;
299 int w = pBuf->write_ptr.load(memory_order_acquire);
300 return (w >= r) ? w - r : (w - r + pBuf->size) & pBuf->size_mask;
301 }
302
303 /**
304 * Prefix decrement operator, for reducing NonVolatileReader's
305 * read position by one.
306 */
307 inline void operator--() {
308 if (read_ptr == pBuf->read_ptr.load(memory_order_relaxed)) return; //TODO: or should we react oh this case (e.g. force segfault), as this is a very odd case?
309 read_ptr = (read_ptr-1) & pBuf->size_mask;
310 }
311
312 /**
313 * Postfix decrement operator, for reducing NonVolatileReader's
314 * read position by one.
315 */
316 inline void operator--(int) {
317 --*this;
318 }
319
320 /**
321 * Returns pointer to the RingBuffer data of current
322 * NonVolatileReader's read position and increments
323 * NonVolatileReader's read position by one.
324 *
325 * @returns pointer to element of current read position
326 */
327 T* pop() {
328 if (!read_space()) return NULL;
329 T* pData = &pBuf->buf[read_ptr];
330 read_ptr++;
331 read_ptr &= pBuf->size_mask;
332 return pData;
333 }
334
335 /**
336 * Reads one element from the NonVolatileReader's current read
337 * position and copies it to the variable pointed by \a dst and
338 * finally increments the NonVolatileReader's read position by
339 * one.
340 *
341 * @param dst - where the element is copied to
342 * @returns 1 on success, 0 otherwise
343 */
344 int pop(T* dst) { return read(dst,1); }
345
346 /**
347 * Reads \a cnt elements from the NonVolatileReader's current
348 * read position and copies it to the buffer pointed by \a dest
349 * and finally increments the NonVolatileReader's read position
350 * by the number of read elements.
351 *
352 * @param dest - destination buffer
353 * @param cnt - number of elements to read
354 * @returns number of read elements
355 */
356 int read(T* dest, int cnt) {
357 int free_cnt;
358 int cnt2;
359 int to_read;
360 int n1, n2;
361 int priv_read_ptr;
362
363 priv_read_ptr = read_ptr;
364
365 if ((free_cnt = read_space()) == 0) return 0;
366
367 to_read = cnt > free_cnt ? free_cnt : cnt;
368
369 cnt2 = priv_read_ptr + to_read;
370
371 if (cnt2 > pBuf->size) {
372 n1 = pBuf->size - priv_read_ptr;
373 n2 = cnt2 & pBuf->size_mask;
374 } else {
375 n1 = to_read;
376 n2 = 0;
377 }
378
379 copy(dest, &pBuf->buf[priv_read_ptr], n1);
380 priv_read_ptr = (priv_read_ptr + n1) & pBuf->size_mask;
381
382 if (n2) {
383 copy(dest+n1, pBuf->buf, n2);
384 priv_read_ptr = n2;
385 }
386
387 this->read_ptr = priv_read_ptr;
388 return to_read;
389 }
390
391 /**
392 * Finally when the read data is not needed anymore, this method
393 * should be called to free the data in the RingBuffer up to the
394 * current read position of this NonVolatileReader.
395 *
396 * @see RingBuffer::increment_read_ptr()
397 */
398 void free() {
399 pBuf->read_ptr.store(read_ptr, memory_order_release);
400 }
401
402 protected:
403 _NonVolatileReader(RingBuffer<T1,T1_DEEP_COPY>* pBuf) {
404 this->pBuf = pBuf;
405 this->read_ptr = pBuf->read_ptr.load(memory_order_relaxed);
406 }
407
408 RingBuffer<T1,T1_DEEP_COPY>* pBuf;
409 int read_ptr;
410
411 friend class RingBuffer<T1,T1_DEEP_COPY>;
412 };
413
414 typedef _NonVolatileReader<T,T_DEEP_COPY> NonVolatileReader;
415
416 NonVolatileReader get_non_volatile_reader() { return NonVolatileReader(this); }
417
418 protected:
419 T *buf;
420 atomic<int> write_ptr;
421 atomic<int> read_ptr;
422 int size_mask;
423
424 /**
425 * Copies \a n amount of elements from the buffer given by
426 * \a pSrc to the buffer given by \a pDst.
427 */
428 inline static void copy(T* pDst, T* pSrc, int n);
429
430 friend class _NonVolatileReader<T,T_DEEP_COPY>;
431 };
432
433 template<class T, bool T_DEEP_COPY>
434 T* RingBuffer<T,T_DEEP_COPY>::get_write_ptr (void) {
435 return(&buf[write_ptr.load(memory_order_relaxed)]);
436 }
437
438 template<class T, bool T_DEEP_COPY>
439 T* RingBuffer<T,T_DEEP_COPY>::get_buffer_begin (void) {
440 return(buf);
441 }
442
443
444
445 template<class T, bool T_DEEP_COPY>
446 int RingBuffer<T,T_DEEP_COPY>::read(T* dest, int cnt)
447 {
448 int free_cnt;
449 int cnt2;
450 int to_read;
451 int n1, n2;
452 int priv_read_ptr;
453
454 priv_read_ptr = read_ptr.load(memory_order_relaxed);
455
456 if ((free_cnt = read_space ()) == 0) {
457 return 0;
458 }
459
460 to_read = cnt > free_cnt ? free_cnt : cnt;
461
462 cnt2 = priv_read_ptr + to_read;
463
464 if (cnt2 > size) {
465 n1 = size - priv_read_ptr;
466 n2 = cnt2 & size_mask;
467 } else {
468 n1 = to_read;
469 n2 = 0;
470 }
471
472 copy(dest, &buf[priv_read_ptr], n1);
473 priv_read_ptr = (priv_read_ptr + n1) & size_mask;
474
475 if (n2) {
476 copy(dest+n1, buf, n2);
477 priv_read_ptr = n2;
478 }
479
480 read_ptr.store(priv_read_ptr, memory_order_release);
481 return to_read;
482 }
483
484 template<class T, bool T_DEEP_COPY>
485 int RingBuffer<T,T_DEEP_COPY>::write(T* src, int cnt)
486 {
487 int free_cnt;
488 int cnt2;
489 int to_write;
490 int n1, n2;
491 int priv_write_ptr;
492
493 priv_write_ptr = write_ptr.load(memory_order_relaxed);
494
495 if ((free_cnt = write_space ()) == 0) {
496 return 0;
497 }
498
499 to_write = cnt > free_cnt ? free_cnt : cnt;
500
501 cnt2 = priv_write_ptr + to_write;
502
503 if (cnt2 > size) {
504 n1 = size - priv_write_ptr;
505 n2 = cnt2 & size_mask;
506 } else {
507 n1 = to_write;
508 n2 = 0;
509 }
510
511 copy(&buf[priv_write_ptr], src, n1);
512 priv_write_ptr = (priv_write_ptr + n1) & size_mask;
513
514 if (n2) {
515 copy(buf, src+n1, n2);
516 priv_write_ptr = n2;
517 }
518 write_ptr.store(priv_write_ptr, memory_order_release);
519 return to_write;
520 }
521
522 template<class T, bool T_DEEP_COPY>
523 void RingBuffer<T,T_DEEP_COPY>::copy(T* pDst, T* pSrc, int n) {
524 if (T_DEEP_COPY) { // deep copy - won't work for data structures without assignment operator implementation
525 for (int i = 0; i < n; i++) pDst[i] = pSrc[i];
526 } else { // flat copy - won't work for complex data structures !
527 memcpy(pDst, pSrc, n * sizeof(T));
528 }
529 }
530
531 #endif /* RINGBUFFER_H */

  ViewVC Help
Powered by ViewVC