Lock free RAII?

DSP, Plug-in and Host development discussion.
Alatar
KVRer
20 posts since 13 Mar, 2011 from Germany

Post Mon Jun 11, 2018 12:03 pm

Hi,

I am currently trying to pass objects from my GUI thread to my audio thread.

I want my audio thread to be lock free. And if possible also some form of RAII.
Normally you could use shared_ptr for RAII. But an atomic shared_ptr is not lock free, as fas as I know (I debugged shared_ptr in VS 2015 and it acquires a spinning lock for atomic_load. So unfortunately that does not seem to be lock free. )
So maybe I am stuck with atomic raw pointers? They are lock free. But I would need to implement my own memory management. I would like to avoid that :-)

Therefore I was wondering: is there a good way to combine lock free with RAII?
Or is it maybe not possible?
How do you guys solve this?
Should I implement my own garbage collector?

Are there any good articles or books on this subject?

User avatar
Aleksey Vaneev
KVRAF
3513 posts since 7 Sep, 2002

Re: Lock free RAII?

Post Mon Jun 11, 2018 12:14 pm

I do not think you can avoid InitializeCriticalSectionAndSpinCount in Windows and OSSpinLock on Mac if you want freedom of pointer interchange. Of course, you should only move pointers, never blocks of data. You can also work with LIFO queues (InterlockedPushEntrySList on Windows, OSAtomicEnqueue on Mac), but they are only marginally more efficient than spinlocks. You can't avoid cache synchronization between cores, so syncing is always not very cheap. If I'm not mistaken, on modern CPUs you can do 20mln critical section entries and exits per second, if your plugin takes 2000 per second it's not such a big problem. Anyway, I have not found a work-around, it probably just does not exist.
Image

stratum
KVRAF
1841 posts since 29 May, 2012

Re: Lock free RAII?

Post Mon Jun 11, 2018 12:16 pm

Code: Select all

audio_thread:

if (mutex.try_lock()) {
  m_p1=m_p2;
  mutex.unlock();
}

Code: Select all

gui_thread:

scoped_lock<mutex_class> lock(mutex);
m_p2= new value();
i.e. the solution doesn't need to be lock free.
~stratum~

mystran
KVRAF
4981 posts since 12 Feb, 2006 from Helsinki, Finland

Re: Lock free RAII?

Post Mon Jun 11, 2018 12:29 pm

What you really want is a "wait-free" scheme rather than "lock-free" scheme, the difference being that "wait-free" is allowed to use locking as long as there is no waiting and "lock-free" is allowed to wait (eg. typically spin) as long as there is no actual locking... and it's the waiting part that's really a problem for real-time.

Now, since you're not really allowed to allocate anything in real-time thread, I assume that you are actually creating and destroying the object in the GUI thread and just want to safely use it in the audio thread. For this purpose, one can use scheme where you "lock" the object in the real-time (ie. audio) thread by first setting a "timestamp" (with an atomic store; the "timestamp" can just be a counter incremented every time you lock, but you need a special value that means "no timestamp"), then fetching the pointer (edit: urgh, got it wrong way around when first writing this point, 'cos brain malfunction). When you "unlock" the object all you need to do is set the "timestamp" to a special "no timestamp" value (atomic store).

Then when you want to replace (or create/destroy) the object (in GUI thread), what you do is first get the old pointer, then atomically store the new pointer (no need to compare and swap or anything). Then you fetch the "timestamp" (again atomic load) and if there is one (ie. it's not the special "no timestamp" value) then you spin (preferably with a short wait in the loop to avoid 100% CPU) until the value has changed. Once the value has changed, the rt-thread has either (1) unlocked, in which case we have no timestamp or (2) locked again, in which case it's using the new pointer. In either situation it's now free for the GUI thread to destroy the old object.

This scheme obviously requires waiting in the GUI thread. If you want to avoid that, you could put the <oldPtr, timestamp> pair into some queue and poll it later while doing something else. This scheme also requires that you never actually modify objects (ie. you just replace them with new versions), but this is pretty much inevitable if you don't want to either wait or fail the lock in the real-time thread.

edit: there is a "race" in the "store timestamp, then fetch pointer" code path in the sense that you might actually get the "new" pointer even if the GUI thread thinks you got the "old" one, but it turns out that this doesn't matter, because next lock or unlock will change the time-stamp again anyway... so as long as you only lock in the RT thread for "short time" (eg. one audio processing call) it's perfectly safe. :)

ps. this scheme ONLY requires atomic loads and stores and on x86 these can be implemented simply by a compiler memory fence (to prevent the optimiser from re-ordering), followed by naturally aligned normal load/store, followed by another compiler memory fence (again to prevent the optimiser from reordering)... so if MSVC implements some retarded spinning for it's atomic loads/stores, just use a regular fence + load/store + fence.
If you'd like Signaldust to return, please ask Katinka Tuisku to resign.

mystran
KVRAF
4981 posts since 12 Feb, 2006 from Helsinki, Finland

Re: Lock free RAII?

Post Mon Jun 11, 2018 12:39 pm

Maybe I should also mention that this can also be extended to multiple readers at the cost of a lot of extra complexity: see the Linux kernel for details. ;)
If you'd like Signaldust to return, please ask Katinka Tuisku to resign.

User avatar
Aleksey Vaneev
KVRAF
3513 posts since 7 Sep, 2002

Re: Lock free RAII?

Post Mon Jun 11, 2018 12:50 pm

The host may not open GUI thread and so you'll have to do memory management in audio thread anyway. Dunno, that hardly ever caused a problem to end-users - SPAN uses memory allocations in the audio thread constantly. I think it's an old myth that memory management should not be done in real-time threads, in reality it's just a matter of overhead like any other operation, with malloc/free weird locks do not happen out of nowhere nowadays. And with spin locks, if the operation inside spin lock is small, the chance of spinning is close to zero.
Image

mystran
KVRAF
4981 posts since 12 Feb, 2006 from Helsinki, Finland

Re: Lock free RAII?

Post Mon Jun 11, 2018 1:10 pm

Aleksey Vaneev wrote:The host may not open GUI thread and so you'll have to do memory management in audio thread anyway. Dunno, that hardly ever caused a problem to end-users - SPAN uses memory allocations in the audio thread constantly. I think it's an old myth that memory management should not be done in real-time threads, in reality it's just a matter of overhead like any other operation, with malloc/free weird locks do not happen out of nowhere nowadays. And with spin locks, if the operation inside spin lock is small, the chance of spinning is close to zero.
I think the pointer-swap thing is most useful when you have to do some non-trivial operation in the GUI like maybe prepare a new set of wavetables or preprocess an impulse response or whatever. I actually used to just use a small critical section too and I don't think it caused huge issues, but since there's a solution that doesn't involve waiting in the audio thread one might just as well use it to reduce the probability of hickups further. :)
If you'd like Signaldust to return, please ask Katinka Tuisku to resign.

User avatar
Aleksey Vaneev
KVRAF
3513 posts since 7 Sep, 2002

Re: Lock free RAII?

Post Mon Jun 11, 2018 1:28 pm

mystran wrote:I think the pointer-swap thing is most useful when you have to do some non-trivial operation in the GUI like maybe prepare a new set of wavetables or preprocess an impulse response or whatever. I actually used to just use a small critical section too and I don't think it caused huge issues, but since there's a solution that doesn't involve waiting in the audio thread one might just as well use it to reduce the probability of hickups further. :)
GUI may be closed while preset/automation is changing by host's command. So, for heavy recalculations can't rely on GUI availability, a background thread is needed, and that introduces state change latency which will unfortunately vary a lot at bounce/render, and some hosts may not even report offline state correctly.
Image

Alatar
KVRer
20 posts since 13 Mar, 2011 from Germany

Re: Lock free RAII?

Post Mon Jun 11, 2018 10:30 pm

Thanks for your input.
So, maybe 100% lock free is not necessary. Hmmm... I see...
And thanks for pointing that out with parameter automation. Have to take a look at that.
Is parameter automation done on the audio thread or on a separate thread?

sonigen
KVRian
562 posts since 23 Nov, 2010

Re: Lock free RAII?

Post Tue Jun 12, 2018 12:45 am

I use lock free queues, one to ferry stuff to the Audio thread, one to ferry stuff back, and what I call a garbage queue that takes any memory to be freed, it takes garbage to a thread that wakes up once a second to free any stuff.

Sounds complicated but once you have the lock free queue its pretty simple.
Chris Jones
www.sonigen.com

sonigen
KVRian
562 posts since 23 Nov, 2010

Re: Lock free RAII?

Post Tue Jun 12, 2018 12:46 am

sonigen wrote:I use lock free queues, one to ferry stuff to the Audio thread, one to ferry stuff back, and what I call a garbage queue that takes any memory to be freed, it takes garbage to a thread that wakes up once a second to empty and free stuff in the queue.

Sounds complicated but once you have the lock free queue its pretty simple.
Chris Jones
www.sonigen.com

User avatar
Guillaume Piolat
KVRist
177 posts since 21 Sep, 2015 from Grenoble

Re: Lock free RAII?

Post Tue Jun 12, 2018 2:05 am

Just a reminder than it may be helpful to use the "raw" memory model when using atomics, if applicable.
This will resort to a normal load or store without LOCK, since x86 memory model already make some guarantees. Yup, no core synchronization.
VST/AU/AAX: Couture | Panagement | Graillon

arne
KVRist
141 posts since 21 Aug, 2004

Re: Lock free RAII?

Post Tue Jun 12, 2018 12:48 pm

Another reminder for everyone who thinks that locks or memory allocations are OK in the audio thread :
https://www.youtube.com/watch?v=SJXGSJ6Zoro

So please do not lock or allocate in the audio thread.

User avatar
Aleksey Vaneev
KVRAF
3513 posts since 7 Sep, 2002

Re: Lock free RAII?

Post Tue Jun 12, 2018 4:32 pm

arne wrote:So please do not lock or allocate in the audio thread.
That's reasonable in theory, but in practice in many cases it's impossible to implement. A better suggestion would be - implement a custom LIFO block memory manager for smaller objects (ultra-efficient, something like 300 ticks per allocation and occassionally more to grow block pool). OS memory allocation is costly, but e.g. allocating a big display spectrum data block takes only 10000 CPU ticks with occasional peak of 50000. It's well within usual plugin CPU budget, nothing that can cause a hiccup.

Do things in GUI thread - wrong suggestion, won't work if GUI is closed. Background thread should have been mentioned. But that also opens a can of worms. If each plugin in the project starts a couple of background threads, that would degrade system's performance.
Image

Alatar
KVRer
20 posts since 13 Mar, 2011 from Germany

Re: Lock free RAII?

Post Tue Jun 12, 2018 9:24 pm

Very interesting discusson.
I am still no quite sure, what to implement, as opinions seem to vary.
But I got good suggestions. :-)

Return to “DSP and Plug-in Development”