On Thu, Apr 03, 2003 at 03:14:53PM -0500, rm wrote: no it is not there. the current code uses mutex_lock and and a condition. The problem i have with the current ringbuffer, is that it does not solve the synchronization of the non realtime thread to the realtime thread. what should be done when you cant write to the buffer ? usleep( a_sensible_value ); ? wouldnt it be nicer to wakeup the non realtime thread with a condition ? the galan ogg-reader starts a reader thread and two gasync queues... then i have 2 struct buffer { SAMPLETIME timestamp; SAMPLE buffer[SIZE]; } * which are passed between the reader and the realtime thread; reader fills in buffer and realtime fills in the timestamp, so the reader thread knows where it should read next. this implementation is just the same as the current capture_client in jack. yeah... that is the principle of the lock free ringbuffer. but how is synchronisation done ? this is my main problem with it. the problem with gasync queue is that a queue is not a threadsafe data structure. so it should be possible to modify the gasync queue to have a ringbuffer instead of a queue and then only use a mutex for the condition signaling. g_cond_signal can be called without holding the mutex so that should be ok for this case. -- torben Hohn http://galan.sourceforge.net -- The graphical Audio language

On Fri, Apr 04, 2003 at 07:27:57AM -0500, rm wrote: oops, missed one assumption: if the rt thread is holding on to n items that were previously given it, it has the capacity to continue to hold on to n items (not necessarily the same ones) whether or not it needs all of them. clearly not very general, but that was the case i used it in. ---- Robert Melby Georgia Institute of Technology, Atlanta Georgia, 30332 uucp: ...!{decvax,hplabs,ncar,purdue,rutgers}!gatech!prism!gt4255a Internet: async(a)cc.gatech.edu

On Fri, Apr 04, 2003 at 07:48:20 -0500, Paul Davis wrote: I think its fine because the addressing technique of the ringbuffer is that the address is evaluated by masking the pointer offset number, and this is true for every access (tecnically speaking, obviously you dont always have to perform the mask). The behaviour is also correct if you address backwards (as in a FIR filters ringbuffer, ie. back in time). Of course this is only true if the buffer is power-of-two sized. - Steve

On Thu, 2003-04-03 at 21:14, rm wrote: Attached is the fifo I've had banging about. It uses atomic_t. -- Bob Ham <rah(a)bash.sh>

OK, I haven't been programming much lately, but when did I miss atomic_t becoming a part of any C standard? Also, several people have referred to the atomicity of int/pointer read/write. This is news to me - can someone point me at the spec for this?

Is it really true on x86? Being that you can do unaligned accesses just fine, you can certainly do cross-cacheline accesses. Pardon the skepticism, but I've never heard such assertions before. Can anyone offer me a specification for this?

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.

Hi, On Sat, Apr 05, 2003 at 01:08:30PM +0100, Steve Harris wrote: Now make that thread-safe and esp. thread-safe on an architecture with weak memory ordering and all the fun stuff. If you have that all working and look at the assembly, then my solution is actually smaller, since all your pointer updates are required to be atomic anyway and that's what we tryed to optimize away here. Yes, your solution is a perfect DSP-chip or hardware solution. It is even nice for ix86, if you have a not that optimizing compiler. But it might be worth to have an special case for these single value reads/writes in my solution, if you don't modify your data much after it or always refer to small amounts. I could also imagine a model, where you do your reads within range back and "skip" that part of the buffer later. So sth. like: char read_value(struct lock_free_fifo *lff, size_t delay) { size_t avail = atomic_read(&lff->filled); if (delay >= avail) { /* Houston, we have a problem! Handling here depends on the * algorithm that requests the delay. */ return FIXUP_VALUE; } return lff->buffer[lff->read_ptr - lff->buffer + delay - lff->max_bytes]; } would read with delay and void skip_bytes(struct lock_free_fifo *lff, size_t bytes) { size_t avail = atomic_read(&lff->filled); if (bytes > avail) bytes = avail; lff->read_ptr += bytes; if (lff->read_ptr >= lff->end_ptr) lff->read_ptr = lff->end_ptr; atomic_sub(&lff->filled, bytes); } would implement the skipping. The if's would degenerate to conditional moves, if CPU and compiler support that. The logic might be switched from direct memory adressing to indirect memory adressing. This is esp. benificial, if you don't work with chars, but with larger data types. With the above routines, you still minimize locking overhead in SMP and can use delaying filters without problems. NOTE: It's still important, that ALL readers are synchronised with each other (the above ARE readers) and ALL writers synchronised to each other. Just no reader need to be synchronised with a writer, as this fifo does it already. NOTE2: My solution also allows to PHYSICALLY decouple the reader and the writer. I have used this scheme for Host->DSP and DSP->Host communication with 1 FIFO per direction. They just synchronize on "filled" variable by telling each other how much they have read/written. For normal computers that means, that you can safely store your read_ptr one one thread stack and the write_ptr on another. Then you can copy the constant data (pointer to memory area used for buffering and fifo size) to have them in the right cachelines. So just the "filled" variable is there to be the synchronisation point and is the only thing, that uses buslocks and does cachline-ping-pong. The last two are increasing factors on multiprocessor systems. P4 with hyperthreading is the same here. 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.

Hi there, On Sat, Apr 05, 2003 at 06:08:51PM +0100, Steve Harris wrote: That is not even true on all ix86 machines. At least I've seen special memory ordering barriers used in the kernel for newer ix86 machines. Right, but if your compiler unrolls your loop, uses indexes to load the data in a random order and increments your pointer later by a bigger chunk. e.g. a1 = buffer[read_ptr++ & (size - 1)]; a2 = buffer[read_ptr++ & (size - 1)]; a3 = buffer[read_ptr++ & (size - 1)]; a4 = buffer[read_ptr++ & (size - 1)]; a5 = buffer[read_ptr++ & (size - 1)]; a_ = (a1 + a2 + a3 + a4 + a5) / 5; can become: read_ptr += 5; a5 = buffer[(read_ptr - 5) & (size - 1)]; a3 = buffer[(read_ptr - 3) & (size - 1)]; a4 = buffer[(read_ptr - 4) & (size - 1)]; a2 = buffer[(read_ptr - 2) & (size - 1)]; a1 = buffer[(read_ptr - 1) & (size - 1)]; a_ = (a1 + a2 + a3 + a4 + a5) / 5; without any problem (compiler tries so parallize load/stores, because the architecture has two load/store units). These are mathematically equivalent transformations backed by the C99 and C89 standard and now your write_ptr will overwrite 5 bytes of your buffer. This may not be important for sound output, because it will only sound wrong, but for recording this is really bad, since it will record wrong data. The ordering will only be kept, if the data access path requires it or you call (non-inlined) functions in between or you use volatile. The kernel people have seen lots of thread safeness being optimized away, so I never assume anything about atomicy in C constructs, that is not backed by the standard. But our solutions combined will give maximum effectiveness. Your masked adressing in indexes removes most of the branches left in my lock_free_fifo scheme. It might be worth to code that all up to have a GPLed high performance fifo scheme. The glibc has internal support for atomic operations (at least atomic_add() is there and allows a negative argument, so atomic_sub() is there too and exchange_and_add(&lff->filled, 0) will provide an atomic read), so there is no problem about portability on Linux systems (and even other systems). Regards Ingo Oeser

the kernel code for atomic_t does this already. atomic_inc(atomic_t* a) resolves to a++ or something like that. --p

On Sun, Apr 06, 2003 at 01:10:17PM +0200, Ingo Oeser wrote: have a look at libvrb. it implements a ringbuffer mapped to 2 adjacent pages. so you can copy the data in and out with 1 memcpy... sort of mmapped ringbuffer. i am not sure if this really improves performance (and if it improves it, its only a minor improvement), but it gives some convenience to the ringbuffer user. -- torben Hohn http://galan.sourceforge.net -- The graphical Audio language