On Thursday, July 07, 2011 07:50:57 pm James Morris wrote: It is... when you re-use one that's already been written and debugged. ;-) Why not copy/paste the JACK ringbuffer (C) or even Ardours (C++ Container)? -gabriel

On 8 July 2011 02:04, Gabriel M. Beddingfield <gabrbedd(a)gmail.com> wrote: Sorry, with my warbling I forgot all about asking when the lock function of jack ringbuffer would be used? Cheers, James.

the linux kernel and supercollider have their own implementations of this algorithm as well ... iirc it is also described in the book `the art of multiprocessor programming' by maurice herlihy and nir shavit. and i would like to do some self-advertising: i have submitted some of my lock- free data structures to boost, and they will be reviewed in the end of july (18th-27th). source and docs are online [1, 2] and i'd like to invite everybody with an interest in lock-free programming to take part in the review. all the provided data structures (wait-free spsc ringbuffer, lock-free mpmc fifo and lock-free mpmc lifo) are potentially interesting for audio applications and i heavily use them for my multiprocessor-aware supercollider server ... the review itself will take place on the boost-dev mailinglist [3] cheers, tim [1] http://tim.klingt.org/boost_lockfree [2] http://tim.klingt.org/git?p=boost_lockfree.git;a=summary [3] http://www.boost.org/community/groups.html#main

On 8 July 2011 12:24, James Morris <jwm.art.net(a)gmail.com> wrote: MSG_BUF_SIZE = 32, MSG_COUNT = 700000 JACK RING BUF: [sirrom@scrapyard msg_test]$ time ./msg_test msg_test.c: 164 main(): read back loop count:700032 real 0m0.136s user 0m0.260s sys 0m0.003s [sirrom@scrapyard msg_test]$ time ./msg_test msg_test.c: 164 main(): read back loop count:700032 real 0m0.136s user 0m0.263s sys 0m0.000s [sirrom@scrapyard msg_test]$ time ./msg_test msg_test.c: 164 main(): read back loop count:700032 real 0m0.142s user 0m0.273s sys 0m0.003s MY RING BUF WITH ATOMIC POINTERS [sirrom@scrapyard msg_test]$ time ./msg_test msg_test.c: 286 main(): read back loop count:702657 real 0m0.169s user 0m0.330s sys 0m0.000s [sirrom@scrapyard msg_test]$ time ./msg_test msg_test.c: 286 main(): read back loop count:738329 real 0m0.173s user 0m0.337s sys 0m0.000s [sirrom@scrapyard msg_test]$ time ./msg_test msg_test.c: 286 main(): read back loop count:753976 real 0m0.171s user 0m0.333s sys 0m0.000s A very simple data integrity check was used, (note: pointers to data were stored in the rbufs rather than data), the main thread set the items data to point to the item itself. the integrity check was that it should come back intact, still pointing to itself. success in both instances. JACK's ringbuf, as most will have undoubtedly known all along, is faster, and the test code required 50000 iterations less than when using my ring buf. maybe somewhere, the atomics are required? james.

On Fri, Jul 8, 2011 at 7:24 AM, James Morris <jwm.art.net(a)gmail.com> wrote: we've been through this several times on LAD-related mailing lists. the usability of a lock free ringbuffer does NOT rely on the stuff discussed in that article. the reason it works is because even if there is a sync error between threads, the error has no negative consequences. put differently, a lock free ringbuffer does not rely on two threads interacting in a particular way, it relies on the fact that if they interact in the "wrong" way, all that happens is that the reader sees less data to read than actually exists, and/or the writer sees less space to write than is actually available. if your application views this as a "negative", then it will have to use some kind of locking primitives to avoid it, but most audio applications can deal with this without blinking. this is entirely different from more generic lock free programming techniques (e.g. lock free lists) where it is definitely true that you need to understand memory barriers and so forth to ensure that they are safe). its also important to recognize that the "locks" used by memory barriers are processor-level, and not really equivalent in most senses to the locks used by the kernel or user space. they do have the capability to block a thread, but the delay is measured in instructions (mostly) and does not involve process-level information. the one wrinkle in this is that in theory a compiler could so completely reorder instructions that even the basic assumptions that make the single reader/single-writer ringbuffer safe would break down. this is theoretically possible (and actually, not that hard to create in practice if you were really trying to) but as oliver mentioned, we've done some fairly exhaustive testing that when combined with a moderately common sense approach to compiler design (e.g. the existence of function scope and related stuff) makes it fundamentally not worth worrying about this theoretical possibility.

On Friday, July 08, 2011 12:17:34 pm Fons Adriaensen wrote: wrote: Take for instance jack_ringbuffer_read(), which has this line: rb->read_ptr = (rb->read_ptr + n) & rb->size_mask; There's a remote possibility that the compiler could optimize this as: rb->read_ptr += n; rb->read_ptr &= rb->size_mask; ...and this would break the ringbuffer. I don't know if the `volatile` keyword prevents this or not. -gabriel

On Friday 08 July 2011 20:12:08 Gabriel M. Beddingfield wrote: What would happen? The ringbuffer in jack is explicitely only for one-reader- one-writer. So in this optimization, the only participant using the read_ptr to do something possibly bad, is the reading participant which is currently executing this code. The writing participant can access that read_ptr for example to check the available space. But as the docs state (afair), the available sizes for read/write are not strict functions, the only thing that counts is if you have space for reading/writing. And that is fulfilled if read_ptr!=write_ptr... Have fun, Arnold

On Fri, Jul 8, 2011 at 7:23 PM, Dan Muresan <danmbox(a)gmail.com> wrote: +1 volatile is not the droid you're looking for. - Dan

On Fri, Jul 8, 2011 at 8:49 PM, Paul Davis <paul(a)linuxaudiosystems.com> wrote: I sure as heck don't know for sure :-) At least on x86, where Intel was very careful to preserve the illusion of coherence, it works... usually? http://en.wikipedia.org/wiki/Non-blocking_algorithm seems to agree with you, but http://www.rossbencina.com/code/lockfree seems to agree with you only on a uniprocessor system. http://www.codeproject.com/KB/threads/LockFree.aspx has lots of interesting links. In particular, it links to a couple articles by Herb Sutter, http://drdobbs.com/cpp/210600279 http://drdobbs.com/high-performance-computing/211601363 He makes it sound like it's only possible using compare-and-swap atomic primitives. - Dan

The apps already need to do some type of synchronization internally. For example a player's disk thread, when its ringbuffer is full, needs to wait for the process thread to consume some data and thus free up some space. So I think it would be better to drop the volatile's, and leave safety to the app level. There's no point in duplicating synchronization at the library and at the app level. -- Dan

How about the other "end" (i.e. the "disk thread"?) Would that normally be periodic? OK, even if your disk thread is periodic for some reason, how does that argue for library-level synchronization, *instead of* app-level synchronization? In this case the cost would be the same -- no loss. "From the same CPU"? Are we regressing to non-SMP-only schemes? And "Intel and AMD" only? How about multiple cores / CPUs / caches? Pipeline reordering is not the main concern (though it can happen) -- cache coherence is. Under which access patterns, with what compiler / optimization flags etc? I would not make such generalizations... Volatile frustrates the optimizer's ability to chose the optimal access patterns. Hijacking volatile for *manual* type checking, at the cost of frustrating the optimizer? Andrei Alexandrescu once advocated that approach for *automatic* type checking in a famous article (http://drdobbs.com/cpp/184403766). I believe the shortcomings have been thoroughly discussed in comp.lang.c++. If you want to remind yourself, you could group the variable(s) and the mutex / semaphore in a structure, or name them similarly etc. It has no place in properly synchronized threaded programs. And it cannot guarantee the correctness of un-synchronized threaded programs (unless you assume non-SMP, non-hyper-threaded, Intely-type hardware -- *maybe*) What does that accomplish? You're merely frustrating the compiler's ability to optimize. You're not achieving complete thread safety by *adding* volatile -- not on arbitrary hardware. If your code is completely thread-safe with volatile, it is also completely thread-safe (and faster) without volatile. Volatile does not offer any guarantees that cannot be later undone by the pipeline or CPU cache. -- Dan

Ah. pthread_mutex_lock() / unlock(), as EXTERNAL functions, will never be optimized away or inlined. Now, being all sequence points, if you simply do pthread_mutex_lock(); xval = x; pthread_mutex_unlock(); the compiler is not allowed to move statements out the locked section or reorder them in any way (without need for any volatile qualifiers). http://en.wikipedia.org/wiki/Sequence_point (or the C89 standard). This is another point that people forget -- many reorderings that they wish to prohibit using volatile are already prohibited by the "sequence point theory". In fact, I think the optimization you fear might not be allowed by sequence points, even without any mutex calls (or volatiles) at all -- depending on your actual code. You initially replied to my advice to not do any sync at *lib-level* (jack/ringbuffer.h), and leave sync up to the app (whoever includes jack/ringbuffer.h). But we're splitting hairs now. I see. But as I said, in general the cache coherency problem is worse than the pipeline reordering problem -- i.e. when there are multiple CPUs/cores using different caches, they may see actions out-of-order. Your call. Still, don't forget that x86 != AMD + Intel -- there are also VIAs, and others. I don't really know how widespread they are in "PCs", or what guarantees they offer. I also don't know if your non-reordering assumption (for which I haven't really seen any hard documentation -- though I've heard rumours too) applies to Intel Atom's, AMD Geode's etc (some of which may be in netbooks, OLPC etc). OK... This thread's subject is about programming advice though :) Plus, when there is no big cost to doing things "by the book", I think developers should be encouraged to keep their code portable, at least in order to save the world future pains a-la Y2K etc. -- Dan

Yes, the hardware would be allowed to reorder them, so pthread_mutex_lock() has memory barriers. I think everyone knew that much :) However my point to Fons was that, because pthread_mutex_lock() is an external function, the compiler is not allowed to make any assumptions about the global variable x (both functions might modify it): it cannot re-read x after unlock(), or read x before lock(). This was the missing ingredient. So it's a cooperation of sequence point-rules and memory barriers that achieves the effects of a critical section in C. So in 10 years we will be able to rely on a conformant compiler being available on all relevant platforms :) -- Dan

On Sun, Jul 10, 2011 at 1:28 PM, Tim Blechmann <tim(a)klingt.org> wrote: if it all works ... very nice. but note that its only been tested on a couple of versions of gcc on a couple of *nix-ish platforms.

On Sun, Jul 10, 2011 at 06:05:45PM +0300, Dan Muresan wrote: OK. This is becoming an interesting discussion, so please allow me to restate clearly the context. We have a variable 'int xval' that is being modified by forces unknown to the code we are discussing. This code is a function f() which uses the value of xval, but the algorithm implemented by f() requires that the same value is used at all points where f() uses xval during a single invocation of that function. So we have: extern int xval; void f(void) { int a, b, c, ... x, y, z; x = xval; // lots of code using a ... z; } Since f() has much more local variables than the CPU has registers, the compiler could be tempted to reuse the register used to store x for some other purpose at some point in the code. It could do that in two ways: 1. Store x on the stack, and read that location when xval is required again, or 2. Just reuse the register without saving it, and read the memory location 'xval' again when required. (2) could make the algorithm fail, because xval could have changed. So we want to prevent that happening. The solution I propose is to declare xval volatile. This forces the compiler to read it just once, as expressed by the source code. So it either will do (1), or maybe decide not to trash the register holding x at all but use another one. The solution you propose is to protect xval by a mutex. I invite you to consider the following: A. If xval is being modified by an interrupt handler then clearly you can't use the mutex - you can't risk to block the interrupt handler. B. From the point of view of the code we are discussing *there is no difference* between xval being modified by an interrupt handler, or by another thread. The difference is completely irrelevant to f(). The only thing that matters is that xval can change while f() executes. You would probably accept the 'volatile' if xval is being written by an interrupt handler. Given (B), there is no good reason to reject it in either case. On that I absolutely agree - cache coherency is the real problem, not pipelining. The latter should in fact be transparent from a language such as C/C++. Ciao, -- FA

On Jul 10, 2011, at 2:41 PM, Paul Davis wrote: Yes. PowerPC and Alpha do not. UltraSPARC v9 and ARMv6/ARM11 and later have modes where they do not (and linux on a SPARC v9 runs in that mode.) Here's some good reading that may help: Memory Ordering in Modern Microprocessors, Part I http://www.linuxjournal.com/article/8211 Memory Ordering in Modern Microprocessors, Part II http://www.linuxjournal.com/article/8212 Linux Kernel Memory Barriers http://www.kernel.org/doc/Documentation/memory-barriers.txt ARM11 Processors: Ordering requirements for memory accesses http://infocenter.arm.com/help/topic/com.arm.doc.ddi0211i/Babcijbf.html Good--without memory barriers, JACK's ringbuffer is at risk for this corruption on these platforms. Cheers, -Sean

On 07/11/2011 03:45 AM, Sean Bolton wrote: Good catch... Multi-core ARM devices are actually arriving massively. With Android, there's the Motorola Atrix, the Samsung Galaxy S II, etc.. I think it wouldn't hurt to run the ringbuffer tests again.. -- Olivier

On Monday 11 July 2011, at 22.32.08, James Morris <jwm.art.net(a)gmail.com> wrote: Also, if/when it's time to port, find the code and/or information you need at the time, and test thoroughly on the actual hardware. These things can usually be done on "anything", one way or another, more or less efficiently. The only thing that's worse than missing support for some new platform is "support" that doesn't actually work properly. Lots of debugging fun to be had that way... :-) -- //David Olofson - Consultant, Developer, Artist, Open Source Advocate .--- Games, examples, libraries, scripting, sound, music, graphics ---. | http://consulting.olofson.net http://olofsonarcade.com | '---------------------------------------------------------------------'

On 11 July 2011 21:50, Chris Cannam <cannam(a)all-day-breakfast.com> wrote: "just" across Chris

On 11 July 2011 21:58, Paul Davis <paul(a)linuxaudiosystems.com> wrote: Well OK, the vital library ringbuffer implementation that everyone relies on is probably a bad place to start arguing for doing things the wrong but easy way rather than the right way. But I know my limitations (increasingly as I get older!) and reasoning accurately about the behaviour of lock-free shared structures in a system with relaxed memory ordering is probably among them. My existing code contains plenty of consequences of "oh, we don't need a lock here because..." fuzz that won't work correctly in such an environment. I do wonder whether there isn't going to be increasingly a case for doing it wrong in principle (through locking) but at least getting the right answers. Reading around for lock-free FIFO implementations I see several that consist of "sequences of objects" (where the objects are allocated outside the scope of the example) that rely on a single atomic operation to update the read index -- that wouldn't be an adequate barrier for the data itself in our buffer-of-floats, though, right? We need a general write barrier after storing the data and before updating the read index, yes? how is that expressed as portably as possible? Does __sync_synchronized reliably do that? (The documentation is surprisingly short...) Chris

Will this solve any of the problems you are worrying about ? Anyway, I'm mentioning it: http://gcc.gnu.org/projects/gomp/ -- E.R.

On 07/12/2011 09:45 PM, Chris Cannam wrote: Quite interestingly, I have noticed that discussions about memory barriers are often somehow endless. What happened in the past is that I saw countless discussions about whether they are needed, whether they are not, and people would argue a lot and passionately. So I thought, maybe there's a hidden topic behind that. A "memory barrier"... Well, that very much reminds me of this memory loss which happens to all of us in the childhood. It turns early years into fuzzy memories. That is a barrier, too. Whether such psychological barriers are needed or not, that's an interesting question :) -- Olivier

On 12 July 2011 21:36, Paul Davis <paul(a)linuxaudiosystems.com> wrote: The transactional metaphor for this kind of thing seems useful -- the idea that "we've written everything, now we commit for our readers" feels like a helpful way to picture the points where barriers might be necessary. Since transactional integrity is not provided for us, the commit needs to be either * protected with a memory barrier, if it doesn't matter that the data is available before it has been announced but does matter if the data is announced before being available * an atomic swap, if the new data must not be available before it has been announced and also there is only a single point of reference to the new data * mutex protected, if the references to any changes may be significant or we are not confident of either of the previous cases ...? Chris

On 12 July 2011 22:32, Olivier Guilyardi <list(a)samalyse.com> wrote: There is one in the iPad 2 example Sean posted a link to earlier in the thread: http://wanderingcoder.net/2011/04/01/arm-memory-ordering/ I haven't tried it, lacking an iPad 2 or any other multicore ARM computer. Chris

On Tue, Jul 12, 2011 at 2:32 PM, Olivier Guilyardi <list(a)samalyse.com> wrote: That's an interesting assertion. It's kind of tempting to write some buggy circular buffers and test that assumption on common hardware.

On Jul 12, 2011, at 19:50 05, Olivier Guilyardi wrote: Is your testing code online somewhere? I do have such a setup (iPad 2 provisioned as a development device in XCode), and may take a crack at this. Cheers! |-------------------------------------------------------------------------| | Frederick F. Gleason, Jr. | Chief Developer | | | Paravel Systems | |-------------------------------------------------------------------------| | Research is what I'm doing when I don't know what I'm doing. | | -- Werner von Braun | |-------------------------------------------------------------------------|

in fact, testing is not the best approach for verifying lock-free data structures: an implementation may work for years, if a certain condition is never triggered. the only reasonable way to ensure the correctness is a formal proof. unfortunately, most publications assume a sequencially consistent memory model and sometimes even avoid dealing with the ABA problem. fortunately the atomics of c++0x/c1x will make it much clearer (and more robust as the memory order argument to the atomic functions defaults to sequencial consistency) cheers, tim

On Wed, Jul 13, 2011 at 9:46 AM, Olivier Guilyardi <list(a)samalyse.com> wrote: i don't see why this is needed. its trivial to demonstrate on a piece of paper that in a system with weak memory ordering constraints, absence of a memory barrier is incorrect for any code with coupled data values (e.g. a read index and read data). it doesn't matter if this doesn't happen very often. you don't need a simulator of any given CPU+memory model - its just demonstrably incorrect.

On Wed, Jul 13, 2011 at 8:51 AM, Paul Davis <paul(a)linuxaudiosystems.com> wrote: [snip] "Beware of bugs in the above code -- I've only proved it correct not actually run it." - Knuth

On 12 July 2011 21:20, Olivier Guilyardi <list(a)samalyse.com> wrote: Indeed -- perhaps these discussions need some sort of memory write barrier, ensuring that everything discussed before the barrier will be recalled from store subsequently, instead of being discussed anew. But this list would be awfully quiet if we had such a thing. Chris

On Tuesday 12 July 2011 22:20:48 Olivier Guilyardi wrote: You mean there should be a barrier to discussions about memory barriers? Sorry, couldn't resist...

Le 13/07/11 01:56, Paul Davis a écrit : Yes, I think that might well be it :) But it's getting late now. Good night -- Olivier

2011/7/20 Kai Vehmanen <kvehmanen(a)eca.cx>cx>: It's called C++11 now and accepted by ISO already ;) 2011 April 11 --- C++11, passed review by the technical standards committee: http://www.physorg.com/news/2011-04-c11-iteration-language.html The biggest changes: http://www.softwarequalityconnection.com/2011/06/the-biggest-changes-in-c11… I've never particularly liked C++ (syntax and complexity) though and would prefer a different language to be spread. Technologies as Mono and LLVM appear to make that possible. -- E.R.

2011/8/20 Emanuel Rumpf <xbran(a)web.de>de>: ... and Java. "Microsoft submitted a portion of its .Net framework to a standards body, but Heffner estimates it amounts to only 10%, ..." ( source: http://www.computerworld.com/s/article/71221/.Net_vs._Java ) "Because of the possible threat of Microsoft patents, the FSF recommends that people avoid creating software that depends on Mono or C#" ( source: http://en.wikipedia.org/wiki/Comparison_of_the_Java_and_.NET_platforms ) So, maybe rather not .net / Mono ;) -- E.R.

On Mon, Jul 11, 2011 at 05:15:26PM -0400, Tim E. Real wrote: The time required to take a lock if it is free is probably not significant in most cases (this should not involve a system call). The problem with e.g. a Jack callback trying to take a lock is that the lock could be held by a non-RT thread, and you have no idea how long it could take before that thread releases it. Even if the Jack thread blocks waiting for the lock, that doesn't mean the one holding the lock will continue, and even if it does that provides no guarantee. OTOH, if you have a number of threads at the same priority as Jack's and doing audio work (e.g. to use all the CPUs of an SMP machine) then using locks between them (but no other threads) should be OK - depending a bit on how they are used. These could take a long time in some cases (if your process needs more memory from the system for example), so they can't be used safely. -- FA

On 07/12/2011 12:06 AM, Fons Adriaensen wrote: So, you can use locks as long as that's only meant to synchronize realtime threads with each other? Should some master thread (could be the JACK process thread) have a realtime priority slightly higher than the other (worker) realtime threads? What are the caveats in general? -- Olivier

On 07/12/2011 10:27 AM, Tim Blechmann wrote: I understand. That's interesting. We're actually benchmarking scheduling latency at the moment. Ah yes, you ensure that threads run on separate cores. That really makes sense. Thanks for the tip. -- Olivier

On 07/12/2011 11:15 AM, Tim Blechmann wrote: Wow, that's pretty exhaustive.. I'll setup something when we're done. The tests can actually be found in: http://code.google.com/p/andraudio/source/browse/experiments/scheduling Beware though this is about non-RT. We're trying to see if running multiple inter-connected audio clients is feasible on Android without adding latency. -- Olivier

On Tue, 2011-07-12 at 00:12 +0200, Arnold Krille wrote: Err not really. Real-time means "Has a bounded response time", locks generally put your completion time at the mercy of another process that is often not designed to have a bounded response time. It is probably more correct to say that locks should be used with extreme caution in RT processes as their use makes the relevant part of another thread part of the time critical response timing. Trylock is an interesting case can can actually be used to solve some of this, have two copies of the working data structure, one protected by a lock, then in the RT thread call trylock and if it succeeds copy the data protected by the lock over the data set used by the RT process and release the lock. If it fails then you still have a coherent set of data, and it might succeed the next time, this is useful for UI data sets (in both directions). Regards, Dan.

On Mon, Jul 11, 2011 at 6:27 PM, Robin Gareus <robin(a)gareus.org> wrote: and in an audio context, for developers of applications, real time means: time to process N audio frames = (A * number_of_frames) + B where A and B are constants. that is, you have a fixed amount of computation per frame, plus a constant overhead. this is an *ideal* - its not often actually accomplished in real life.

Guys, if you're writing code for your own use, and don't care about portability or security, go ahead and use volatile as a synchronization primitive. But if the code is going to be accepted into an open source project that gets wide use, volatile is a bad idea. But don't take my word for it; here's what kernel.org, cert.org, and an intel researcher say about it: "Volatile considered harmful", http://www.kernel.org/doc/Documentation/volatile-considered-harmful.txt "The use of volatile is likely to be seen as a bug and will bring additional scrutiny to the code." "CERT Secure Coding Standards, recommendation POS03: Do not use volatile as a synchronization primitive" https://www.securecoding.cert.org/confluence/display/seccode/POS03-C.+Do+no… "A variable declared as volatile is not cached in a register, leading to this confusion that it can be used safely as a synchronization primitive. When declared volatile, the compiler does not re-order the sequence of reads and writes to that memory location. However, the compiler might re-order these reads and writes with those to other memory locations. This might result in non-atomic operations on the synchronization variable resulting in errors." "Ad Hoc Synchronization Considered Harmful", www.xiongww.com/papers/osdi10-xiong.pdf "Ad hoc synchronizations are error-prone. Significant percentages (22-67%) of these ad hoc synchronizations introduced bugs or severe performance issues." Volatile is a 1980's solution to a 2000's problem, and it just doesn't cut the mustard anymore. - Dan

On Mon, Jul 11, 2011 at 03:02:57PM +0300, Dan Muresan wrote: The typical use case would be xval being some parameter used by e.g. a Jack callback and updated by e.g. MIDI events, or a measurement; and f() being the code that runs periodically to update the GUI element for that parameter or measurement. There is no synchronisation and occasionally using an out- dated value has no fatal consequences - it will very probably be put right on the next update which is 1/10 second or so in the future. The display is informative only, correct audio processing does in no way depend on it being up to date. That would mean the other side has to use the mutex as well when updating xval, and in a Jack callback that is 'not done', at least not if the mutex could be held by a non-realtime thread such as one updating the GUI. Not if there is no synchronisation involved as in the example above. If all the signal handler has to do is update xval, it doesn't matter in which thread it runs. Strictly true, but R/W of ints is atomic on the platforms that matter to me. Ciao, -- FA

On Mon, Jul 11, 2011 at 09:59:25PM +0300, Dan Muresan wrote: Wouldn't that seem quite natural ? Semas provide one-way communication. It's the sem_post() that means there is an event to be seen by some other thread. So it has to make sure that any data related to it is visible to the receiver. The receiver taking the event (returning from sem_wait()), or checking for it (calling sem_wait()), is not meant to be an event for the other side. You need a second sema if events have to go both ways. For a ringbuffer you need two anyway if the buffer is longer than one item, and you want to signal both of 'not empty' and 'not full' in the appropriate direction. Ciao, -- FA

Given that a mutex can be replaced with a semaphore initialized with 1 (then lock == sem_wait, unlock == sem_post), your statement should be true as long as the semaphore value is 0 / 1. However, I don't know if your statement must still be true when the semaphore is used as a count tied to a number of items, i.e. when it always hovers above 1. POSIX talks about a "thread of control", but in this case, there is no exclusion, thus no "thread of control". http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag… (same link as a few posts ago) -- Dan

On Fri, Jul 08, 2011 at 09:05:42PM +0200, Arnold Krille wrote: Actually things are a little better: you can be sure that _at least_ the space indicated is available for reading or writing, not just that you can read or write one item (byte in this case). Looking at the way things are implemented, the right value would be returned even if the unmasked 'other side' count is used. I'm using a slightly different (C++) implementation: the stored values equivalent to jack's rd_ptr and wr_ptr (wrong names, they are not pointers but indices) are never masked. The 'size-1' mask (with size = 2^N) is applied only when they are used to index the buffer array. This has two consequences: - You can use all 2^n elements, there is no ambiguity between full and empty. - The code is simplified a bit: n_avail_read = wr_index - rd_index; n_avail_write = rd_index - wr_index + size; and no conditions, masking, or -1 are necessary. Ciao, -- FA

On Friday 08 July 2011 22:41:54 Paul Davis wrote: Empty for reading. Lots of space for writing. Its much more interesting to see what happens when the indezes cross the 2^32 or 2^64 mark, then the write-index will be smaller then the read-index untill the read-index catches up. But as far as I see currently, this wouldn't be a problem either. The writer only has to stop writing when its at read_ptr - 1. Maybe I don't understand it all, but with fons approach I think it only works when the buffer-sizes are 2^n. When you have a buffer of say 5 elements, doing the modulo at the element-access and not at the read/write-head-movement, this will jump every now and then, right? Have fun, Arnold

On Fri, Jul 08, 2011 at 04:41:54PM -0400, Paul Davis wrote: That the buffer is empty, rd_avail = size, wr_avail = 0 -- FA