page.title=Avoiding Priority Inversion
@jd:body

<!--
    Copyright 2013 The Android Open Source Project

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

        http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
-->
<div id="qv-wrapper">
  <div id="qv">
    <h2>In this document</h2>
    <ol id="auto-toc">
    </ol>
  </div>
</div>

<p>
This article explains how the Android's audio system attempts to avoid
priority inversion,
and highlights techniques that you can use too.
</p>

<p>
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.
</p>

<h2 id="background">Background</h2>

<p>
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.
</p>

<p>
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.
</p>

<h2 id="priorityInversion">Priority inversion</h2>

<p>
<a href="http://en.wikipedia.org/wiki/Priority_inversion">Priority inversion</a>
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
<a href="http://en.wikipedia.org/wiki/Mutual_exclusion">mutex</a>.
</p>

<p>
In an audio system, priority inversion typically manifests as a
<a href="http://en.wikipedia.org/wiki/Glitch">glitch</a>
(click, pop, dropout),
<a href="http://en.wikipedia.org/wiki/Max_Headroom_(character)">repeated audio</a>
when circular buffers
are used, or delay in responding to a command.
</p>

<p>
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.
</p>

<p>
In the Android audio implementation, priority inversion is most
likely to occur in these places. And so you should focus your attention here:
</p>

<ul>

<li>
between normal mixer thread and fast mixer thread in AudioFlinger
</li>

<li>
between application callback thread for a fast AudioTrack and
fast mixer thread (they both have elevated priority, but slightly
different priorities)
</li>

<li>
between application callback thread for a fast AudioRecord and
fast capture thread (similar to previous)
</li>

<li>
within the audio Hardware Abstraction Layer (HAL) implementation, e.g. for telephony or echo cancellation
</li>

<li>
within the audio driver in kernel
</li>

<li>
between AudioTrack or AudioRecord callback thread and other app threads (this is out of our control)
</li>

</ul>

<h2 id="commonSolutions">Common solutions</h2>

<p>
The typical solutions include:
</p>

<ul>

<li>
disabling interrupts
</li>

<li>
priority inheritance mutexes
</li>

</ul>

<p>
Disabling interrupts is not feasible in Linux user space, and does
not work for Symmetric Multi-Processors (SMP).
</p>


<p>
Priority inheritance
<a href="http://en.wikipedia.org/wiki/Futex">futexes</a>
(fast user-space mutexes) are available
in Linux kernel, but are not currently exposed by the Android C
runtime library
<a href="http://en.wikipedia.org/wiki/Bionic_(software)">Bionic</a>.
They are not used in the audio system because they are relatively heavyweight,
and because they rely on a trusted client.
</p>

<h2 id="androidTechniques">Techniques used by Android</h2>

<p>
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.
</p>


<p>
We also use
<a href="http://en.wikipedia.org/wiki/Linearizability">atomic operations</a>
such as:
</p>

<ul>
<li>increment</li>
<li>bitwise "or"</li>
<li>bitwise "and"</li>
</ul>

<p>
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.
</p>

<p class="note"><strong>Note:</strong> 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
<a href="https://developer.android.com/training/articles/smp.html">
SMP Primer for Android</a>
for further information.
</p>

<p>
We still have and use most of the above tools, and have recently
added these techniques:
</p>

<ul>

<li>
Use non-blocking single-reader single-writer
<a href="http://en.wikipedia.org/wiki/Circular_buffer">FIFO queues</a>
for data.
</li>

<li>
Try to
<i>copy</i>
state rather than
<i>share</i>
state between high- and
low-priority modules.
</li>

<li>
When state does need to be shared, limit the state to the
maximum-size
<a href="http://en.wikipedia.org/wiki/Word_(computer_architecture)">word</a>
that can be accessed atomically in one-bus operation
without retries.
</li>

<li>
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.
</li>

<li>
Pay attention to
<a href="http://en.wikipedia.org/wiki/Memory_barrier">memory barriers</a>
for SMP correctness.
</li>

<li>
<a href="http://en.wikipedia.org/wiki/Trust,_but_verify">Trust, but verify</a>.
When sharing
<i>state</i>
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
<i>data</i>
such as PCM audio where a corruption is inconsequential.
</li>

</ul>

<h2 id="nonBlockingAlgorithms">Non-blocking algorithms</h2>

<p>
<a href="http://en.wikipedia.org/wiki/Non-blocking_algorithm">Non-blocking algorithms</a>
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.
</p>

<p>
Starting in Android 4.2, you can find our non-blocking,
single-reader/writer classes in these locations:
</p>

<ul>

<li>
frameworks/av/include/media/nbaio/
</li>

<li>
frameworks/av/media/libnbaio/
</li>

<li>
frameworks/av/services/audioflinger/StateQueue*
</li>

</ul>

<p>
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.
</p>

<p>
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.
</p>

<p>
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
<code>frameworks/av/audio_utils</code>:
</p>
<ul>
  <li><a href="https://android.googlesource.com/platform/system/media/+/master/audio_utils/include/audio_utils/fifo.h">include/audio_utils/fifo.h</a></li>
  <li><a href="https://android.googlesource.com/platform/system/media/+/master/audio_utils/fifo.c">fifo.c</a></li>
  <li><a href="https://android.googlesource.com/platform/system/media/+/master/audio_utils/include/audio_utils/roundup.h">include/audio_utils/roundup.h</a></li>
  <li><a href="https://android.googlesource.com/platform/system/media/+/master/audio_utils/roundup.c">roundup.c</a></li>
</ul>

<h2 id="tools">Tools</h2>

<p>
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
<a href="http://developer.android.com/tools/help/systrace.html">systrace</a>
and
<code>ps -t -p</code>
are useful for seeing priority inversion after it occurs, but do
not tell you in advance.
</p>

<h2 id="aFinalWord">A final word</h2>

<p>
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.
</p>