[linux-audio-dev] lock-free ring buffer code

[Ingo Oeser]

On Fri, Apr 04, 2003 at 08:00:36PM +0100, Bob Ham wrote:
> On Thu, 2003-04-03 at 21:14, rm wrote:
> 
> > below is what i use (i think it works). the primary thing to notice
> > is that readers and writers are kept in line by the atomicity of
> > integer assignment (though in general, we should probably declare them
> > atomic_t or something).
> 
> Attached is the fifo I've had banging about.  It uses atomic_t.

It's racy. While you are evaluation the atomic_t once more (in
your write logic), your atomic_t could be written again.

The window is small (so you might not care), but it's there. The
kernel doesn't use it this way.

A lock free fifo looks like this:

You account the available bytes in the fifo by an atomic operation.
This works, because the reader only ever decreases the count and
the writer only ever increases the count. 

This scheme allows only one reader and only one writer. If you
need more, you need to synchronize between each writers and
between eache readers, but never between readers/writers. But as
this gets really more complex and shows usally other design
problems, you can just use the fifos provided by them OS.

You DON'T do atomic pointer updates.

So your structure looks like this

struct lock_free_fifo {
   /* These three are constant after init*/
   char *buffer;
   char *end_ptr; 
   size_t max_bytes;

   /* This is only read/written by the reader */
   char *read_ptr;
   /* This is only read/written by the writter */
   char *write_ptr;

   /* This is the only thing modified by both */
   atomic_t filled;
}

struct lock_free_fifo *lff_get(size_t your_size) {
   struct lock_free_fifo *lff = malloc(sizeof(*lff));
   if (!lff) return lff;
   
   lff->buffer = malloc(your_size);
   lff->max_bytes = your_size;
   lff->read_ptr = lff->write_ptr = lff->buffer;
   lff->end_ptr = lff->buffer + lff->max_bytes;
   atomic_init(&lff->filled, 0);

   if (!lff->buffer) {
      free(lff);
      lff = NULL;
   }
   return lff;
}

size_t lff_write(struct lock_free_fifo *lff, char *buffer, size_t count) {
   size_t avail = (lff->max_bytes - atomic_read(&lff->filled));
   size_t todo = count;
   size_t first_todo = lff->end_ptr - lff->write_ptr;
   
   /* Never write more than available */
   if (todo > avail) count = todo = avail;

   /* Does it NOT cross the FIFO end? */
   if (first_todo > todo) first_todo = todo;

   memcpy(lff->write_ptr, buffer, first_todo);

   /* Did we reach or cross the end? */
   if (first_todo <= todo) {
      buffer += first_todo;
      lff->write_ptr = lff->buffer;
      todo -= first_todo;
      if (todo) memcpy(lff->write_ptr, buffer, first_todo);
   }
   lff->write_ptr += todo;

   /* Only atomic modification! */
   atomic_sub(&lff->filled, count);
   return count;
}

size_t lff_read(struct lock_free_fifo *lff, char *buffer, size_t count) {
   size_t avail = atomic_read(&lff->filled);
   size_t todo = count;
   size_t first_todo = lff->end_ptr - lff->read_ptr;
   
   /* Never read more than available */
   if (todo > avail) count = todo = avail;

   /* Does it NOT cross the FIFO end? */
   if (first_todo > todo) first_todo = todo;

   memcpy(buffer, lff->read_ptr, first_todo);

   /* Did we reach or cross the end? */
   if (first_todo <= todo) {
      buffer += first_todo;
      lff->read_ptr = lff->buffer;
      todo -= first_todo;
      if (todo) memcpy(buffer, lff->read_ptr, first_todo);
   }
   lff->read_ptr += todo;


   /* Only atomic modification! */
   atomic_add(&lff->filled, count);
   return count;
}

The reader is the only one allowed to close the FIFO correctly.
This is left as an exercise to the readers of the list ;-)

If we race between the atmic_read and the atomic modifications,
we will just not empty the FIFO completely (reading) or just not
fill the FIFO completely (writing).

That is only a minor performance problem, but never a correctness
problem, since we just require one more read/write in this case.

The algorithm is basically the code in linux/fs/pipe.c, but
without any waiting. You can use the code as I GPL it by sending
it to the list.

Regards

Ingo Oeser
-- 
Marketing ist die Kunst, Leuten Sachen zu verkaufen, die sie
nicht brauchen, mit Geld, was sie nicht haben, um Leute zu
beeindrucken, die sie nicht moegen.