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

On Fri, Apr 04, 2003 at 08:00:36PM +0100, Bob Ham wrote: 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.