Alc/ringbuffer.cpp

   1 /**
   2  * OpenAL cross platform audio library
   3  * Copyright (C) 1999-2007 by authors.
   4  * This library is free software; you can redistribute it and/or
   5  *  modify it under the terms of the GNU Library General Public
   6  *  License as published by the Free Software Foundation; either
   7  *  version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  *  Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  *  License along with this library; if not, write to the
  16  *  Free Software Foundation, Inc.,
  17  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18  * Or go to http://www.gnu.org/copyleft/lgpl.html
  19  */
  20
  21 #include "config.h"
  22
  23 #include <string.h>
  24 #include <stdlib.h>
  25 #include <limits.h>
  26
  27 #include "ringbuffer.h"
  28 #include "atomic.h"
  29 #include "threads.h"
  30 #include "almalloc.h"
  31 #include "compat.h"
  32
  33
  34 /* NOTE: This lockless ringbuffer implementation is copied from JACK, extended
  35  * to include an element size. Consequently, parameters and return values for a
  36  * size or count is in 'elements', not bytes. Additionally, it only supports
  37  * single-consumer/single-provider operation. */
  38 struct ll_ringbuffer {
  39     std::atomic<size_t> write_ptr;
  40     std::atomic<size_t> read_ptr;
  41     size_t size;
  42     size_t size_mask;
  43     size_t elem_size;
  44
  45     alignas(16) char buf[];
  46 };
  47
  48 ll_ringbuffer_t *ll_ringbuffer_create(size_t sz, size_t elem_sz, int limit_writes)
  49 {
  50     ll_ringbuffer_t *rb;
  51     size_t power_of_two = 0;
  52
  53     if(sz > 0)
  54     {
  55         power_of_two = sz;
  56         power_of_two |= power_of_two>>1;
  57         power_of_two |= power_of_two>>2;
  58         power_of_two |= power_of_two>>4;
  59         power_of_two |= power_of_two>>8;
  60         power_of_two |= power_of_two>>16;
  61 #if SIZE_MAX > UINT_MAX
  62         power_of_two |= power_of_two>>32;
  63 #endif
  64     }
  65     power_of_two++;
  66     if(power_of_two < sz) return NULL;
  67
  68     rb = static_cast<ll_ringbuffer_t*>(al_malloc(16, sizeof(*rb) + power_of_two*elem_sz));
  69     if(!rb) return NULL;
  70
  71     ATOMIC_INIT(&rb->write_ptr, static_cast<size_t>(0));
  72     ATOMIC_INIT(&rb->read_ptr, static_cast<size_t>(0));
  73     rb->size = limit_writes ? sz : power_of_two;
  74     rb->size_mask = power_of_two - 1;
  75     rb->elem_size = elem_sz;
  76     return rb;
  77 }
  78
  79 void ll_ringbuffer_free(ll_ringbuffer_t *rb)
  80 {
  81     al_free(rb);
  82 }
  83
  84 void ll_ringbuffer_reset(ll_ringbuffer_t *rb)
  85 {
  86     rb->write_ptr.store(0, std::memory_order_release);
  87     rb->read_ptr.store(0, std::memory_order_release);
  88     memset(rb->buf, 0, (rb->size_mask+1)*rb->elem_size);
  89 }
  90
  91
  92 size_t ll_ringbuffer_read_space(const ll_ringbuffer_t *rb)
  93 {
  94     size_t w = rb->write_ptr.load(std::memory_order_acquire);
  95     size_t r = rb->read_ptr.load(std::memory_order_acquire);
  96     return (w-r) & rb->size_mask;
  97 }
  98
  99 size_t ll_ringbuffer_write_space(const ll_ringbuffer_t *rb)
 100 {
 101     size_t w = rb->write_ptr.load(std::memory_order_acquire);
 102     size_t r = rb->read_ptr.load(std::memory_order_acquire);
 103     w = (r-w-1) & rb->size_mask;
 104     return (w > rb->size) ? rb->size : w;
 105 }
 106
 107
 108 size_t ll_ringbuffer_read(ll_ringbuffer_t *rb, void *dest, size_t cnt)
 109 {
 110     size_t read_ptr;
 111     size_t free_cnt;
 112     size_t cnt2;
 113     size_t to_read;
 114     size_t n1, n2;
 115
 116     free_cnt = ll_ringbuffer_read_space(rb);
 117     if(free_cnt == 0) return 0;
 118
 119     to_read = (cnt > free_cnt) ? free_cnt : cnt;
 120     read_ptr = rb->read_ptr.load(std::memory_order_relaxed) & rb->size_mask;
 121
 122     cnt2 = read_ptr + to_read;
 123     if(cnt2 > rb->size_mask+1)
 124     {
 125         n1 = rb->size_mask+1 - read_ptr;
 126         n2 = cnt2 & rb->size_mask;
 127     }
 128     else
 129     {
 130         n1 = to_read;
 131         n2 = 0;
 132     }
 133
 134     memcpy(dest, &rb->buf[read_ptr*rb->elem_size], n1*rb->elem_size);
 135     read_ptr += n1;
 136     if(n2)
 137     {
 138         memcpy(static_cast<char*>(dest) + n1*rb->elem_size,
 139                &rb->buf[(read_ptr&rb->size_mask)*rb->elem_size],
 140                n2*rb->elem_size);
 141         read_ptr += n2;
 142     }
 143     rb->read_ptr.store(read_ptr, std::memory_order_release);
 144     return to_read;
 145 }
 146
 147 size_t ll_ringbuffer_peek(ll_ringbuffer_t *rb, void *dest, size_t cnt)
 148 {
 149     size_t free_cnt;
 150     size_t cnt2;
 151     size_t to_read;
 152     size_t n1, n2;
 153     size_t read_ptr;
 154
 155     free_cnt = ll_ringbuffer_read_space(rb);
 156     if(free_cnt == 0) return 0;
 157
 158     to_read = (cnt > free_cnt) ? free_cnt : cnt;
 159     read_ptr = rb->read_ptr.load(std::memory_order_relaxed) & rb->size_mask;
 160
 161     cnt2 = read_ptr + to_read;
 162     if(cnt2 > rb->size_mask+1)
 163     {
 164         n1 = rb->size_mask+1 - read_ptr;
 165         n2 = cnt2 & rb->size_mask;
 166     }
 167     else
 168     {
 169         n1 = to_read;
 170         n2 = 0;
 171     }
 172
 173     memcpy(dest, &rb->buf[read_ptr*rb->elem_size], n1*rb->elem_size);
 174     if(n2)
 175     {
 176         read_ptr += n1;
 177         memcpy(static_cast<char*>(dest) + n1*rb->elem_size,
 178                &rb->buf[(read_ptr&rb->size_mask)*rb->elem_size],
 179                n2*rb->elem_size);
 180     }
 181     return to_read;
 182 }
 183
 184 size_t ll_ringbuffer_write(ll_ringbuffer_t *rb, const void *src, size_t cnt)
 185 {
 186     size_t write_ptr;
 187     size_t free_cnt;
 188     size_t cnt2;
 189     size_t to_write;
 190     size_t n1, n2;
 191
 192     free_cnt = ll_ringbuffer_write_space(rb);
 193     if(free_cnt == 0) return 0;
 194
 195     to_write = (cnt > free_cnt) ? free_cnt : cnt;
 196     write_ptr = rb->write_ptr.load(std::memory_order_relaxed) & rb->size_mask;
 197
 198     cnt2 = write_ptr + to_write;
 199     if(cnt2 > rb->size_mask+1)
 200     {
 201         n1 = rb->size_mask+1 - write_ptr;
 202         n2 = cnt2 & rb->size_mask;
 203     }
 204     else
 205     {
 206         n1 = to_write;
 207         n2 = 0;
 208     }
 209
 210     memcpy(&rb->buf[write_ptr*rb->elem_size], src, n1*rb->elem_size);
 211     write_ptr += n1;
 212     if(n2)
 213     {
 214         memcpy(&rb->buf[(write_ptr&rb->size_mask)*rb->elem_size],
 215                static_cast<const char*>(src) + n1*rb->elem_size,
 216                n2*rb->elem_size);
 217         write_ptr += n2;
 218     }
 219     rb->write_ptr.store(write_ptr, std::memory_order_release);
 220     return to_write;
 221 }
 222
 223
 224 void ll_ringbuffer_read_advance(ll_ringbuffer_t *rb, size_t cnt)
 225 {
 226     rb->read_ptr.fetch_add(cnt, std::memory_order_acq_rel);
 227 }
 228
 229 void ll_ringbuffer_write_advance(ll_ringbuffer_t *rb, size_t cnt)
 230 {
 231     rb->write_ptr.fetch_add(cnt, std::memory_order_acq_rel);
 232 }
 233
 234
 235 ll_ringbuffer_data_pair ll_ringbuffer_get_read_vector(const ll_ringbuffer_t *rb)
 236 {
 237     ll_ringbuffer_data_pair ret;
 238     size_t free_cnt;
 239     size_t cnt2;
 240
 241     size_t w = rb->write_ptr.load(std::memory_order_acquire);
 242     size_t r = rb->read_ptr.load(std::memory_order_acquire);
 243     w &= rb->size_mask;
 244     r &= rb->size_mask;
 245     free_cnt = (w-r) & rb->size_mask;
 246
 247     cnt2 = r + free_cnt;
 248     if(cnt2 > rb->size_mask+1)
 249     {
 250         /* Two part vector: the rest of the buffer after the current write ptr,
 251          * plus some from the start of the buffer. */
 252         ret.first.buf = const_cast<char*>(&rb->buf[r*rb->elem_size]);
 253         ret.first.len = rb->size_mask+1 - r;
 254         ret.second.buf = const_cast<char*>(rb->buf);
 255         ret.second.len = cnt2 & rb->size_mask;
 256     }
 257     else
 258     {
 259         /* Single part vector: just the rest of the buffer */
 260         ret.first.buf = const_cast<char*>(&rb->buf[r*rb->elem_size]);
 261         ret.first.len = free_cnt;
 262         ret.second.buf = nullptr;
 263         ret.second.len = 0;
 264     }
 265
 266     return ret;
 267 }
 268
 269 ll_ringbuffer_data_pair ll_ringbuffer_get_write_vector(const ll_ringbuffer_t *rb)
 270 {
 271     ll_ringbuffer_data_pair ret;
 272     size_t free_cnt;
 273     size_t cnt2;
 274
 275     size_t w = rb->write_ptr.load(std::memory_order_acquire);
 276     size_t r = rb->read_ptr.load(std::memory_order_acquire);
 277     w &= rb->size_mask;
 278     r &= rb->size_mask;
 279     free_cnt = (r-w-1) & rb->size_mask;
 280     if(free_cnt > rb->size) free_cnt = rb->size;
 281
 282     cnt2 = w + free_cnt;
 283     if(cnt2 > rb->size_mask+1)
 284     {
 285         /* Two part vector: the rest of the buffer after the current write ptr,
 286          * plus some from the start of the buffer. */
 287         ret.first.buf = const_cast<char*>(&rb->buf[w*rb->elem_size]);
 288         ret.first.len = rb->size_mask+1 - w;
 289         ret.second.buf = const_cast<char*>(rb->buf);
 290         ret.second.len = cnt2 & rb->size_mask;
 291     }
 292     else
 293     {
 294         ret.first.buf = const_cast<char*>(&rb->buf[w*rb->elem_size]);
 295         ret.first.len = free_cnt;
 296         ret.second.buf = nullptr;
 297         ret.second.len = 0;
 298     }
 299
 300     return ret;
 301 }