ingo-fifo.txt

   1
   2   [linux-audio-dev] lock-free ring buffer code
   3
   4 *Ingo Oeser * linux-audio-dev@music.columbia.edu
   5 <mailto:linux-audio-dev%40music.columbia.edu>
   6 /Sat Apr 5 06:15:01 2003/
   7
   8     * Previous message: [linux-audio-dev] lock-free ring buffer code
   9       <003648.html>
  10     * Next message: [linux-audio-dev] lock-free ring buffer code
  11       <003650.html>
  12     * *Messages sorted by:* [ date ] <date.html#3649> [ thread ]
  13       <thread.html#3649> [ subject ] <subject.html#3649> [ author ]
  14       <author.html#3649>
  15
  16 ------------------------------------------------------------------------
  17
  18 On Fri, Apr 04, 2003 at 08:00:36PM +0100, Bob Ham wrote:
  19 >/ On Thu, 2003-04-03 at 21:14, rm wrote:
  20 />/
  21 />/ > below is what i use (i think it works). the primary thing to notice
  22 />/ > is that readers and writers are kept in line by the atomicity of
  23 />/ > integer assignment (though in general, we should probably declare them
  24 />/ > atomic_t or something).
  25 />/
  26 />/ Attached is the fifo I've had banging about.  It uses atomic_t.
  27 /
  28 It's racy. While you are evaluation the atomic_t once more (in
  29 your write logic), your atomic_t could be written again.
  30
  31 The window is small (so you might not care), but it's there. The
  32 kernel doesn't use it this way.
  33
  34 A lock free fifo looks like this:
  35
  36 You account the available bytes in the fifo by an atomic operation.
  37 This works, because the reader only ever decreases the count and
  38 the writer only ever increases the count.
  39
  40 This scheme allows only one reader and only one writer. If you
  41 need more, you need to synchronize between each writers and
  42 between eache readers, but never between readers/writers. But as
  43 this gets really more complex and shows usally other design
  44 problems, you can just use the fifos provided by them OS.
  45
  46 You DON'T do atomic pointer updates.
  47
  48 So your structure looks like this
  49
  50 struct lock_free_fifo {
  51    /* These three are constant after init*/
  52    char *buffer;
  53    char *end_ptr;
  54    size_t max_bytes;
  55
  56    /* This is only read/written by the reader */
  57    char *read_ptr;
  58    /* This is only read/written by the writter */
  59    char *write_ptr;
  60
  61    /* This is the only thing modified by both */
  62    atomic_t filled;
  63 }
  64
  65 struct lock_free_fifo *lff_get(size_t your_size) {
  66    struct lock_free_fifo *lff = malloc(sizeof(*lff));
  67    if (!lff) return lff;
  68
  69    lff->buffer = malloc(your_size);
  70    lff->max_bytes = your_size;
  71    lff->read_ptr = lff->write_ptr = lff->buffer;
  72    lff->end_ptr = lff->buffer + lff->max_bytes;
  73    atomic_init(&lff->filled, 0);
  74
  75    if (!lff->buffer) {
  76       free(lff);
  77       lff = NULL;
  78    }
  79    return lff;
  80 }
  81
  82 size_t lff_write(struct lock_free_fifo *lff, char *buffer, size_t count) {
  83    size_t avail = (lff->max_bytes - atomic_read(&lff->filled));
  84    size_t todo = count;
  85    size_t first_todo = lff->end_ptr - lff->write_ptr;
  86
  87    /* Never write more than available */
  88    if (todo > avail) count = todo = avail;
  89
  90    /* Does it NOT cross the FIFO end? */
  91    if (first_todo > todo) first_todo = todo;
  92
  93    memcpy(lff->write_ptr, buffer, first_todo);
  94
  95    /* Did we reach or cross the end? */
  96    if (first_todo <= todo) {
  97       buffer += first_todo;
  98       lff->write_ptr = lff->buffer;
  99       todo -= first_todo;
 100       if (todo) memcpy(lff->write_ptr, buffer, first_todo);
 101    }
 102    lff->write_ptr += todo;
 103
 104    /* Only atomic modification! */
 105    atomic_sub(&lff->filled, count);
 106    return count;
 107 }
 108
 109 size_t lff_read(struct lock_free_fifo *lff, char *buffer, size_t count) {
 110    size_t avail = atomic_read(&lff->filled);
 111    size_t todo = count;
 112    size_t first_todo = lff->end_ptr - lff->read_ptr;
 113
 114    /* Never read more than available */
 115    if (todo > avail) count = todo = avail;
 116
 117    /* Does it NOT cross the FIFO end? */
 118    if (first_todo > todo) first_todo = todo;
 119
 120    memcpy(buffer, lff->read_ptr, first_todo);
 121
 122    /* Did we reach or cross the end? */
 123    if (first_todo <= todo) {
 124       buffer += first_todo;
 125       lff->read_ptr = lff->buffer;
 126       todo -= first_todo;
 127       if (todo) memcpy(buffer, lff->read_ptr, first_todo);
 128    }
 129    lff->read_ptr += todo;
 130
 131
 132    /* Only atomic modification! */
 133    atomic_add(&lff->filled, count);
 134    return count;
 135 }
 136
 137 The reader is the only one allowed to close the FIFO correctly.
 138 This is left as an exercise to the readers of the list ;-)
 139
 140 If we race between the atmic_read and the atomic modifications,
 141 we will just not empty the FIFO completely (reading) or just not
 142 fill the FIFO completely (writing).
 143
 144 That is only a minor performance problem, but never a correctness
 145 problem, since we just require one more read/write in this case.
 146
 147 The algorithm is basically the code in linux/fs/pipe.c, but
 148 without any waiting. You can use the code as I GPL it by sending
 149 it to the list.
 150
 151 Regards
 152
 153 Ingo Oeser
 154 --
 155 Marketing ist die Kunst, Leuten Sachen zu verkaufen, die sie
 156 nicht brauchen, mit Geld, was sie nicht haben, um Leute zu
 157 beeindrucken, die sie nicht moegen.
 158
 159 ------------------------------------------------------------------------
 160
 161     * Previous message: [linux-audio-dev] lock-free ring buffer code
 162       <003648.html>
 163     * Next message: [linux-audio-dev] lock-free ring buffer code
 164       <003650.html>
 165     * *Messages sorted by:* [ date ] <date.html#3649> [ thread ]
 166       <thread.html#3649> [ subject ] <subject.html#3649> [ author ]
 167       <author.html#3649>
 168