src/pulsecore/flist.c

   1 /* $Id$ */
   2
   3 /***
   4   This file is part of PulseAudio.
   5
   6   Copyright 2006 Lennart Poettering
   7
   8   PulseAudio is free software; you can redistribute it and/or modify
   9   it under the terms of the GNU Lesser General Public License as
  10   published by the Free Software Foundation; either version 2.1 of the
  11   License, or (at your option) any later version.
  12
  13   PulseAudio is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public
  19   License along with PulseAudio; if not, write to the Free Software
  20   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  21   USA.
  22 ***/
  23
  24 #ifdef HAVE_CONFIG_H
  25 #include <config.h>
  26 #endif
  27
  28 #include <assert.h>
  29
  30 #include <pulsecore/atomic.h>
  31 #include <pulsecore/log.h>
  32 #include <pulsecore/thread.h>
  33 #include <pulsecore/macro.h>
  34 #include <pulse/xmalloc.h>
  35
  36 #include "flist.h"
  37
  38 /* Algorithm is not perfect, in a few corner cases it will fail to pop
  39  * from the flist although it isn't empty, and fail to push into the
  40  * flist, although it isn't full.
  41  *
  42  * We keep a fixed size array of entries, each item is either marked
  43  * UNUSED, USED or BUSY and contains a user data pointer. When pushing
  44  * into the queue we look for an UNUSED cell and mark it BUSY with a
  45  * CAS operation. If successful we use it and mark it USED, otherwise
  46  * we go on and look for the next UNUSED cell. The algorithm for
  47  * popping an item from the queue is practically inverse: look for a
  48  * USED cell and and mark it BUSY with a CAS operation, after reading
  49  * from it mark it UNUSED again.
  50  *
  51  * To accelerate finding of used/unused cells we maintain a read and a
  52  * write index which is used like a ring buffer. After each push we
  53  * increase the write index and after each pop we increase the read
  54  * index.
  55  *
  56  * The indexes are incremented atomically and are never truncated to
  57  * the buffer size. Instead we assume that the buffer size is a power
  58  * of two and that the truncation can thus be done by applying a
  59  * simple AND on read.
  60  *
  61  * To make sure that we do not look for empty cells indefinitely we
  62  * maintain a length value which stores the number of used cells. From
  63  * this value the number of unused cells is easily calculated. Please
  64  * note that the length value is not updated atomically with the read
  65  * and write index and might thus be a few cells off the real
  66  * value. To deal with this we always look for N_EXTRA_SCAN extra
  67  * cells when pushing/popping entries.
  68  *
  69  * It might make sense to replace this implementation with a link list
  70  * stack or queue, which however requires DCAS to be simple. Patches
  71  * welcome.
  72  *
  73  * Please note that this algorithm is home grown.*/
  74
  75 #define FLIST_SIZE 128
  76 #define N_EXTRA_SCAN 2
  77
  78 /* For debugging purposes we can define _Y to put and extra thread
  79  * yield between each operation. */
  80
  81 #ifdef PROFILE
  82 #define _Y pa_thread_yield()
  83 #else
  84 #define _Y do { } while(0)
  85 #endif
  86
  87 enum {
  88     STATE_UNUSED,
  89     STATE_USED,
  90     STATE_BUSY
  91 };
  92
  93 struct cell {
  94     pa_atomic_t state;
  95     void *data;
  96 };
  97
  98 struct pa_flist {
  99     unsigned size;
 100     pa_atomic_t length;
 101     pa_atomic_t read_idx;
 102     pa_atomic_t write_idx;
 103 };
 104
 105 #define PA_FLIST_CELLS(x) ((struct cell*) ((uint8_t*) (x) + PA_ALIGN(sizeof(struct pa_flist))))
 106
 107 static int is_power_of_two(unsigned size) {
 108     return !(size & (size - 1));
 109 }
 110
 111 pa_flist *pa_flist_new(unsigned size) {
 112     pa_flist *l;
 113
 114     if (!size)
 115         size = FLIST_SIZE;
 116
 117     assert(is_power_of_two(size));
 118
 119     l = pa_xmalloc0(PA_ALIGN(sizeof(pa_flist)) + (sizeof(struct cell) * size));
 120
 121     l->size = size;
 122
 123     pa_atomic_store(&l->read_idx, 0);
 124     pa_atomic_store(&l->write_idx, 0);
 125     pa_atomic_store(&l->length, 0);
 126
 127     return l;
 128 }
 129
 130 static int reduce(pa_flist *l, int value) {
 131     return value & (unsigned) (l->size - 1);
 132 }
 133
 134 void pa_flist_free(pa_flist *l, pa_free_cb_t free_cb) {
 135     assert(l);
 136
 137     if (free_cb) {
 138         struct cell *cells;
 139         int len, idx;
 140
 141         cells = PA_FLIST_CELLS(l);
 142
 143         idx = reduce(l, pa_atomic_load(&l->read_idx));
 144         len = pa_atomic_load(&l->length);
 145
 146         for (; len > 0; len--) {
 147
 148             if (pa_atomic_load(&cells[idx].state) == STATE_USED)
 149                 free_cb(cells[idx].data);
 150
 151             idx = reduce(l, idx + 1);
 152         }
 153     }
 154
 155     pa_xfree(l);
 156 }
 157
 158 int pa_flist_push(pa_flist*l, void *p) {
 159     int idx, len, n;
 160     struct cell *cells;
 161
 162     assert(l);
 163     assert(p);
 164
 165     cells = PA_FLIST_CELLS(l);
 166
 167     n = len = (int) l->size - pa_atomic_load(&l->length) + N_EXTRA_SCAN;
 168     _Y;
 169     idx = reduce(l, pa_atomic_load(&l->write_idx));
 170
 171     for (; n > 0 ; n--) {
 172         _Y;
 173
 174         if (pa_atomic_cmpxchg(&cells[idx].state, STATE_UNUSED, STATE_BUSY)) {
 175             _Y;
 176             pa_atomic_inc(&l->write_idx);
 177             _Y;
 178             cells[idx].data = p;
 179             _Y;
 180             pa_atomic_store(&cells[idx].state, STATE_USED);
 181             _Y;
 182             pa_atomic_inc(&l->length);
 183             return 0;
 184         }
 185
 186         _Y;
 187         idx = reduce(l, idx + 1);
 188     }
 189
 190 #ifdef PROFILE
 191     if (len > N_EXTRA_SCAN)
 192         pa_log("WARNING: Didn't  find free cell after %u iterations.", len);
 193 #endif
 194
 195     return -1;
 196 }
 197
 198 void* pa_flist_pop(pa_flist*l) {
 199     int idx, len, n;
 200     struct cell *cells;
 201
 202     assert(l);
 203
 204     cells = PA_FLIST_CELLS(l);
 205
 206     n = len = pa_atomic_load(&l->length) + N_EXTRA_SCAN;
 207     _Y;
 208     idx = reduce(l, pa_atomic_load(&l->read_idx));
 209
 210     for (; n > 0 ; n--) {
 211         _Y;
 212
 213         if (pa_atomic_cmpxchg(&cells[idx].state, STATE_USED, STATE_BUSY)) {
 214             void *p;
 215             _Y;
 216             pa_atomic_inc(&l->read_idx);
 217             _Y;
 218             p = cells[idx].data;
 219             _Y;
 220             pa_atomic_store(&cells[idx].state, STATE_UNUSED);
 221             _Y;
 222
 223             pa_atomic_dec(&l->length);
 224             return p;
 225         }
 226
 227         _Y;
 228         idx = reduce(l, idx+1);
 229     }
 230
 231 #ifdef PROFILE
 232     if (len > N_EXTRA_SCAN)
 233         pa_log("WARNING: Didn't find used cell after %u iterations.", len);
 234 #endif
 235
 236     return NULL;
 237 }