code.delx.au - pulseaudio/blob - 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 pa_flist *pa_flist_new(unsigned size) {
 108     pa_flist *l;
 109
 110     if (!size)
 111         size = FLIST_SIZE;
 112
 113     assert(pa_is_power_of_two(size));
 114
 115     l = pa_xmalloc0(PA_ALIGN(sizeof(pa_flist)) + (sizeof(struct cell) * size));
 116
 117     l->size = size;
 118
 119     pa_atomic_store(&l->read_idx, 0);
 120     pa_atomic_store(&l->write_idx, 0);
 121     pa_atomic_store(&l->length, 0);
 122
 123     return l;
 124 }
 125
 126 static int reduce(pa_flist *l, int value) {
 127     return value & (unsigned) (l->size - 1);
 128 }
 129
 130 void pa_flist_free(pa_flist *l, pa_free_cb_t free_cb) {
 131     assert(l);
 132
 133     if (free_cb) {
 134         struct cell *cells;
 135         int len, idx;
 136
 137         cells = PA_FLIST_CELLS(l);
 138
 139         idx = reduce(l, pa_atomic_load(&l->read_idx));
 140         len = pa_atomic_load(&l->length);
 141
 142         for (; len > 0; len--) {
 143
 144             if (pa_atomic_load(&cells[idx].state) == STATE_USED)
 145                 free_cb(cells[idx].data);
 146
 147             idx = reduce(l, idx + 1);
 148         }
 149     }
 150
 151     pa_xfree(l);
 152 }
 153
 154 int pa_flist_push(pa_flist*l, void *p) {
 155     int idx, len, n;
 156     struct cell *cells;
 157
 158     assert(l);
 159     assert(p);
 160
 161     cells = PA_FLIST_CELLS(l);
 162
 163     n = len = (int) l->size - pa_atomic_load(&l->length) + N_EXTRA_SCAN;
 164     _Y;
 165     idx = reduce(l, pa_atomic_load(&l->write_idx));
 166
 167     for (; n > 0 ; n--) {
 168         _Y;
 169
 170         if (pa_atomic_cmpxchg(&cells[idx].state, STATE_UNUSED, STATE_BUSY)) {
 171             _Y;
 172             pa_atomic_inc(&l->write_idx);
 173             _Y;
 174             cells[idx].data = p;
 175             _Y;
 176             pa_atomic_store(&cells[idx].state, STATE_USED);
 177             _Y;
 178             pa_atomic_inc(&l->length);
 179             return 0;
 180         }
 181
 182         _Y;
 183         idx = reduce(l, idx + 1);
 184     }
 185
 186 #ifdef PROFILE
 187     if (len > N_EXTRA_SCAN)
 188         pa_log("WARNING: Didn't  find free cell after %u iterations.", len);
 189 #endif
 190
 191     return -1;
 192 }
 193
 194 void* pa_flist_pop(pa_flist*l) {
 195     int idx, len, n;
 196     struct cell *cells;
 197
 198     assert(l);
 199
 200     cells = PA_FLIST_CELLS(l);
 201
 202     n = len = pa_atomic_load(&l->length) + N_EXTRA_SCAN;
 203     _Y;
 204     idx = reduce(l, pa_atomic_load(&l->read_idx));
 205
 206     for (; n > 0 ; n--) {
 207         _Y;
 208
 209         if (pa_atomic_cmpxchg(&cells[idx].state, STATE_USED, STATE_BUSY)) {
 210             void *p;
 211             _Y;
 212             pa_atomic_inc(&l->read_idx);
 213             _Y;
 214             p = cells[idx].data;
 215             _Y;
 216             pa_atomic_store(&cells[idx].state, STATE_UNUSED);
 217             _Y;
 218
 219             pa_atomic_dec(&l->length);
 220             return p;
 221         }
 222
 223         _Y;
 224         idx = reduce(l, idx+1);
 225     }
 226
 227 #ifdef PROFILE
 228     if (len > N_EXTRA_SCAN)
 229         pa_log("WARNING: Didn't find used cell after %u iterations.", len);
 230 #endif
 231
 232     return NULL;
 233 }