This article explains how the Android's audio system attempts to avoid priority inversion, and highlights techniques that you can use too.
These techniques may be useful to developers of high-performance audio apps, OEMs, and SoC providers who are implementing an audio HAL. Please note implementing these techniques is not guaranteed to prevent glitches or other failures, particularly if used outside of the audio context. Your results may vary, and you should conduct your own evaluation and testing.
Background
The Android AudioFlinger audio server and AudioTrack/AudioRecord client implementation are being re-architected to reduce latency. This work started in Android 4.1, and continued with further improvements in 4.2, 4.3, 4.4, and 5.0.
To achieve this lower latency, many changes were needed throughout the system. One important change is to assign CPU resources to time-critical threads with a more predictable scheduling policy. Reliable scheduling allows the audio buffer sizes and counts to be reduced while still avoiding underruns and overruns.
Priority inversion
Priority inversion is a classic failure mode of real-time systems, where a higher-priority task is blocked for an unbounded time waiting for a lower-priority task to release a resource such as (shared state protected by) a mutex.
In an audio system, priority inversion typically manifests as a glitch (click, pop, dropout), repeated audio when circular buffers are used, or delay in responding to a command.
A common workaround for priority inversion is to increase audio buffer sizes. However, this method increases latency and merely hides the problem instead of solving it. It is better to understand and prevent priority inversion, as seen below.
In the Android audio implementation, priority inversion is most likely to occur in these places. And so you should focus your attention here:
- between normal mixer thread and fast mixer thread in AudioFlinger
- between application callback thread for a fast AudioTrack and fast mixer thread (they both have elevated priority, but slightly different priorities)
- between application callback thread for a fast AudioRecord and fast capture thread (similar to previous)
- within the audio Hardware Abstraction Layer (HAL) implementation, e.g. for telephony or echo cancellation
- within the audio driver in kernel
- between AudioTrack or AudioRecord callback thread and other app threads (this is out of our control)
Common solutions
The typical solutions include:
- disabling interrupts
- priority inheritance mutexes
Disabling interrupts is not feasible in Linux user space, and does not work for Symmetric Multi-Processors (SMP).
Priority inheritance futexes (fast user-space mutexes) are not used in the audio system because they are relatively heavyweight, and because they rely on a trusted client.
Techniques used by Android
Experiments started with "try lock" and lock with timeout. These are non-blocking and bounded blocking variants of the mutex lock operation. Try lock and lock with timeout worked fairly well but were susceptible to a couple of obscure failure modes: the server was not guaranteed to be able to access the shared state if the client happened to be busy, and the cumulative timeout could be too long if there was a long sequence of unrelated locks that all timed out.
We also use atomic operations such as:
- increment
- bitwise "or"
- bitwise "and"
All of these return the previous value and include the necessary SMP barriers. The disadvantage is they can require unbounded retries. In practice, we've found that the retries are not a problem.
Note: Atomic operations and their interactions with memory barriers are notoriously badly misunderstood and used incorrectly. We include these methods here for completeness but recommend you also read the article SMP Primer for Android for further information.
We still have and use most of the above tools, and have recently added these techniques:
- Use non-blocking single-reader single-writer FIFO queues for data.
- Try to copy state rather than share state between high- and low-priority modules.
- When state does need to be shared, limit the state to the maximum-size word that can be accessed atomically in one-bus operation without retries.
- For complex multi-word state, use a state queue. A state queue is basically just a non-blocking single-reader single-writer FIFO queue used for state rather than data, except the writer collapses adjacent pushes into a single push.
- Pay attention to memory barriers for SMP correctness.
- Trust, but verify. When sharing state between processes, don't assume that the state is well-formed. For example, check that indices are within bounds. This verification isn't needed between threads in the same process, between mutual trusting processes (which typically have the same UID). It's also unnecessary for shared data such as PCM audio where a corruption is inconsequential.
Non-blocking algorithms
Non-blocking algorithms have been a subject of much recent study. But with the exception of single-reader single-writer FIFO queues, we've found them to be complex and error-prone.
Starting in Android 4.2, you can find our non-blocking, single-reader/writer classes in these locations:
- frameworks/av/include/media/nbaio/
- frameworks/av/media/libnbaio/
- frameworks/av/services/audioflinger/StateQueue*
These were designed specifically for AudioFlinger and are not general-purpose. Non-blocking algorithms are notorious for being difficult to debug. You can look at this code as a model. But be aware there may be bugs, and the classes are not guaranteed to be suitable for other purposes.
For developers, some of the sample OpenSL ES application code should be updated to use non-blocking algorithms or reference a non-Android open source library.
We have published an example non-blocking FIFO implementation that is specifically designed for
application code. See these files located in the platform source directory
frameworks/av/audio_utils:
Tools
To the best of our knowledge, there are no automatic tools for
finding priority inversion, especially before it happens. Some
research static code analysis tools are capable of finding priority
inversions if able to access the entire codebase. Of course, if
arbitrary user code is involved (as it is here for the application)
or is a large codebase (as for the Linux kernel and device drivers),
static analysis may be impractical. The most important thing is to
read the code very carefully and get a good grasp on the entire
system and the interactions. Tools such as
systrace
and
ps -t -p
are useful for seeing priority inversion after it occurs, but do
not tell you in advance.
A final word
After all of this discussion, don't be afraid of mutexes. Mutexes are your friend for ordinary use, when used and implemented correctly in ordinary non-time-critical use cases. But between high- and low-priority tasks and in time-sensitive systems mutexes are more likely to cause trouble.