Portable Lock-free FIFO

SDL Development
1

Speaking of lock-free FIFOs in the “Portable speakerw API” thread, how about
including something like that as a part of the SDL threading API?

I have an implementation of a lock-free single reader-single writer FIFO that
works on Linux/x86 (user space + kernel space) and DOS real mode (!), but I’m
not entirely sure about SMP systems. (Should work, though, up to the point
where the write size exceeds the word size of the first bus that’s shared by
multiple CPUs - which is the external cache bus/switch on some
architectures…)

Provided the code compiles correctly, it should work safely up to 64 kB
buffer size on practically anything; and 16 MB (no, not 4 GB! Some
architectures have a weird limit at 24 bits atomic write…) on anything 32+
bit.

What I don’t know for sure is if it does compile correctly on all
compilers. It relies on atomic reading and writing of buffer offsets, but
separate CPU caches and other delay factors should have no effect. (Single
reader-single writer means that the reader writes only the output offset,
while the writer only writes the input offset - makes things a lot easier. :slight_smile:

Code snippets:

—8<------------------------------------------------------

typedef struct
{
char buffer;
int size; / Number of bytes /
volatile int readpos; / Read position /
volatile int writepos; / Write position */
} sfifo_t;

------------------------------------------------------>8—

/*

  • Write bytes to a FIFO

  • Return number of bytes written, or an error code
    */
    int sfifo_write(sfifo_t *f, const void *buf, int len)
    {
    int total;
    int i;

     if(!f->buffer)
         return -ENODEV; /* No buffer! */

 /* total = len = min(space, len) */
 total = SFIFO_SPACE(f);
 DBG(printf("SFIFO_SPACE() = %d\n",total));
 if(len > total)
         len = total;
 else
         total = len;

 i = f->writepos;
 if(i + len > f->size)
 {
         memcpy(f->buffer + i, buf, f->size - i);
         buf += f->size - i;
         len -= f->size - i;
         i = 0;
 }
 memcpy(f->buffer + i, buf, len);
 f->writepos = i + len;

 return total;

}

—8<------------------------------------------------------

Interesting?

//David

.- M A I A -------------------------------------------------.
| Multimedia Application Integration Architecture |
| A Free/Open Source Plugin API for Professional Multimedia |
----------------------> http://www.linuxaudiodev.com/maia -' .- David Olofson -------------------------------------------. | Audio Hacker - Open Source Advocate - Singer - Songwriter |--------------------------------------> david at linuxdj.com -’