Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 1 | page.title=Avoiding Priority Inversion |
| 2 | @jd:body |
| 3 | |
Clay Murphy | bc92aea | 2014-10-16 10:13:18 -0700 | [diff] [blame] | 4 | <!-- |
| 5 | Copyright 2013 The Android Open Source Project |
| 6 | |
| 7 | Licensed under the Apache License, Version 2.0 (the "License"); |
| 8 | you may not use this file except in compliance with the License. |
| 9 | You may obtain a copy of the License at |
| 10 | |
| 11 | http://www.apache.org/licenses/LICENSE-2.0 |
| 12 | |
| 13 | Unless required by applicable law or agreed to in writing, software |
| 14 | distributed under the License is distributed on an "AS IS" BASIS, |
| 15 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 16 | See the License for the specific language governing permissions and |
| 17 | limitations under the License. |
| 18 | --> |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 19 | <div id="qv-wrapper"> |
| 20 | <div id="qv"> |
| 21 | <h2>In this document</h2> |
| 22 | <ol id="auto-toc"> |
| 23 | </ol> |
| 24 | </div> |
| 25 | </div> |
| 26 | |
| 27 | <p> |
| 28 | This article explains how the Android's audio system attempts to avoid |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 29 | priority inversion, as of the Android 4.1 release, |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 30 | and highlights techniques that you can use too. |
| 31 | </p> |
| 32 | |
| 33 | <p> |
| 34 | These techniques may be useful to developers of high-performance |
| 35 | audio apps, OEMs, and SoC providers who are implementing an audio |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 36 | HAL. Please note implementing these techniques is not |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 37 | guaranteed to prevent glitches or other failures, particularly if |
| 38 | used outside of the audio context. |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 39 | Your results may vary, and you should conduct your own |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 40 | evaluation and testing. |
| 41 | </p> |
| 42 | |
| 43 | <h2 id="background">Background</h2> |
| 44 | |
| 45 | <p> |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 46 | The Android AudioFlinger audio server and AudioTrack/AudioRecord |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 47 | client implementation are being re-architected to reduce latency. |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 48 | This work started in Android 4.1, continued in 4.2 and 4.3, and now more |
| 49 | improvements exist in version 4.4. |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 50 | </p> |
| 51 | |
| 52 | <p> |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 53 | To achieve this lower latency, many changes were needed throughout the system. One |
| 54 | important change is to assign CPU resources to time-critical |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 55 | threads with a more predictable scheduling policy. Reliable scheduling |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 56 | allows the audio buffer sizes and counts to be reduced while still |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 57 | avoiding artifacts due to underruns. |
| 58 | </p> |
| 59 | |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 60 | <h2 id="priorityInversion">Priority inversion</h2> |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 61 | |
| 62 | <p> |
| 63 | <a href="http://en.wikipedia.org/wiki/Priority_inversion">Priority inversion</a> |
| 64 | is a classic failure mode of real-time systems, |
| 65 | where a higher-priority task is blocked for an unbounded time waiting |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 66 | for a lower-priority task to release a resource such as (shared |
| 67 | state protected by) a |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 68 | <a href="http://en.wikipedia.org/wiki/Mutual_exclusion">mutex</a>. |
| 69 | </p> |
| 70 | |
| 71 | <p> |
| 72 | In an audio system, priority inversion typically manifests as a |
| 73 | <a href="http://en.wikipedia.org/wiki/Glitch">glitch</a> |
| 74 | (click, pop, dropout), |
| 75 | <a href="http://en.wikipedia.org/wiki/Max_Headroom_(character)">repeated audio</a> |
| 76 | when circular buffers |
| 77 | are used, or delay in responding to a command. |
| 78 | </p> |
| 79 | |
| 80 | <p> |
| 81 | In the Android audio implementation, priority inversion is most |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 82 | likely to occur in these places. And so you should focus your attention here: |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 83 | </p> |
| 84 | |
| 85 | <ul> |
| 86 | |
| 87 | <li> |
| 88 | between normal mixer thread and fast mixer thread in AudioFlinger |
| 89 | </li> |
| 90 | |
| 91 | <li> |
| 92 | between application callback thread for a fast AudioTrack and |
| 93 | fast mixer thread (they both have elevated priority, but slightly |
| 94 | different priorities) |
| 95 | </li> |
| 96 | |
| 97 | <li> |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 98 | within the audio Hardware Abstraction Layer (HAL) implementation, e.g. for telephony or echo cancellation |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 99 | </li> |
| 100 | |
| 101 | <li> |
| 102 | within the audio driver in kernel |
| 103 | </li> |
| 104 | |
| 105 | <li> |
| 106 | between AudioTrack callback thread and other app threads (this is out of our control) |
| 107 | </li> |
| 108 | |
| 109 | </ul> |
| 110 | |
| 111 | <p> |
| 112 | As of this writing, reduced latency for AudioRecord is planned but |
| 113 | not yet implemented. The likely priority inversion spots will be |
| 114 | similar to those for AudioTrack. |
| 115 | </p> |
| 116 | |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 117 | <h2 id="commonSolutions">Common solutions</h2> |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 118 | |
| 119 | <p> |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 120 | The typical solutions include: |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 121 | </p> |
| 122 | |
| 123 | <ul> |
| 124 | |
| 125 | <li> |
| 126 | disabling interrupts |
| 127 | </li> |
| 128 | |
| 129 | <li> |
| 130 | priority inheritance mutexes |
| 131 | </li> |
| 132 | |
| 133 | </ul> |
| 134 | |
| 135 | <p> |
| 136 | Disabling interrupts is not feasible in Linux user space, and does |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 137 | not work for Symmetric Multi-Processors (SMP). |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 138 | </p> |
| 139 | |
| 140 | |
| 141 | <p> |
| 142 | Priority inheritance |
| 143 | <a href="http://en.wikipedia.org/wiki/Futex">futexes</a> |
| 144 | (fast user-space mutexes) are available |
| 145 | in Linux kernel, but are not currently exposed by the Android C |
| 146 | runtime library |
| 147 | <a href="http://en.wikipedia.org/wiki/Bionic_(software)">Bionic</a>. |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 148 | They are not used in the audio system because they are relatively heavyweight, |
| 149 | and because they rely on a trusted client. |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 150 | </p> |
| 151 | |
| 152 | <h2 id="androidTechniques">Techniques used by Android</h2> |
| 153 | |
| 154 | <p> |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 155 | Experiments started with "try lock" and lock with timeout. These are |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 156 | non-blocking and bounded blocking variants of the mutex lock |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 157 | operation. Try lock and lock with timeout worked fairly well but were |
| 158 | susceptible to a couple of obscure failure modes: the |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 159 | server was not guaranteed to be able to access the shared state if |
| 160 | the client happened to be busy, and the cumulative timeout could |
| 161 | be too long if there was a long sequence of unrelated locks that |
| 162 | all timed out. |
| 163 | </p> |
| 164 | |
| 165 | |
| 166 | <p> |
| 167 | We also use |
| 168 | <a href="http://en.wikipedia.org/wiki/Linearizability">atomic operations</a> |
| 169 | such as: |
| 170 | </p> |
| 171 | |
| 172 | <ul> |
| 173 | <li>increment</li> |
| 174 | <li>bitwise "or"</li> |
| 175 | <li>bitwise "and"</li> |
| 176 | </ul> |
| 177 | |
| 178 | <p> |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 179 | All of these return the previous value and include the necessary |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 180 | SMP barriers. The disadvantage is they can require unbounded retries. |
| 181 | In practice, we've found that the retries are not a problem. |
| 182 | </p> |
| 183 | |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 184 | <p class="note"><strong>Note:</strong> Atomic operations and their interactions with memory barriers |
| 185 | are notoriously badly misunderstood and used incorrectly. We include these methods |
| 186 | here for completeness but recommend you also read the article |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 187 | <a href="https://developer.android.com/training/articles/smp.html"> |
| 188 | SMP Primer for Android</a> |
| 189 | for further information. |
| 190 | </p> |
| 191 | |
| 192 | <p> |
| 193 | We still have and use most of the above tools, and have recently |
| 194 | added these techniques: |
| 195 | </p> |
| 196 | |
| 197 | <ul> |
| 198 | |
| 199 | <li> |
| 200 | Use non-blocking single-reader single-writer |
| 201 | <a href="http://en.wikipedia.org/wiki/Circular_buffer">FIFO queues</a> |
| 202 | for data. |
| 203 | </li> |
| 204 | |
| 205 | <li> |
| 206 | Try to |
| 207 | <i>copy</i> |
| 208 | state rather than |
| 209 | <i>share</i> |
| 210 | state between high- and |
| 211 | low-priority modules. |
| 212 | </li> |
| 213 | |
| 214 | <li> |
| 215 | When state does need to be shared, limit the state to the |
| 216 | maximum-size |
| 217 | <a href="http://en.wikipedia.org/wiki/Word_(computer_architecture)">word</a> |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 218 | that can be accessed atomically in one-bus operation |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 219 | without retries. |
| 220 | </li> |
| 221 | |
| 222 | <li> |
| 223 | For complex multi-word state, use a state queue. A state queue |
| 224 | is basically just a non-blocking single-reader single-writer FIFO |
| 225 | queue used for state rather than data, except the writer collapses |
| 226 | adjacent pushes into a single push. |
| 227 | </li> |
| 228 | |
| 229 | <li> |
| 230 | Pay attention to |
| 231 | <a href="http://en.wikipedia.org/wiki/Memory_barrier">memory barriers</a> |
| 232 | for SMP correctness. |
| 233 | </li> |
| 234 | |
| 235 | <li> |
| 236 | <a href="http://en.wikipedia.org/wiki/Trust,_but_verify">Trust, but verify</a>. |
| 237 | When sharing |
| 238 | <i>state</i> |
| 239 | between processes, don't |
| 240 | assume that the state is well-formed. For example, check that indices |
| 241 | are within bounds. This verification isn't needed between threads |
| 242 | in the same process, between mutual trusting processes (which |
| 243 | typically have the same UID). It's also unnecessary for shared |
| 244 | <i>data</i> |
| 245 | such as PCM audio where a corruption is inconsequential. |
| 246 | </li> |
| 247 | |
| 248 | </ul> |
| 249 | |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 250 | <h2 id="nonBlockingAlgorithms">Non-blocking algorithms</h2> |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 251 | |
| 252 | <p> |
| 253 | <a href="http://en.wikipedia.org/wiki/Non-blocking_algorithm">Non-blocking algorithms</a> |
| 254 | have been a subject of much recent study. |
| 255 | But with the exception of single-reader single-writer FIFO queues, |
| 256 | we've found them to be complex and error-prone. |
| 257 | </p> |
| 258 | |
| 259 | <p> |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 260 | Starting in Android 4.2, you can find our non-blocking, |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 261 | single-reader/writer classes in these locations: |
| 262 | </p> |
| 263 | |
| 264 | <ul> |
| 265 | |
| 266 | <li> |
| 267 | frameworks/av/include/media/nbaio/ |
| 268 | </li> |
| 269 | |
| 270 | <li> |
| 271 | frameworks/av/media/libnbaio/ |
| 272 | </li> |
| 273 | |
| 274 | <li> |
| 275 | frameworks/av/services/audioflinger/StateQueue* |
| 276 | </li> |
| 277 | |
| 278 | </ul> |
| 279 | |
| 280 | <p> |
| 281 | These were designed specifically for AudioFlinger and are not |
| 282 | general-purpose. Non-blocking algorithms are notorious for being |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 283 | difficult to debug. You can look at this code as a model. But be |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 284 | aware there may be bugs, and the classes are not guaranteed to be |
| 285 | suitable for other purposes. |
| 286 | </p> |
| 287 | |
| 288 | <p> |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 289 | For developers, some of the sample OpenSL ES application code should be updated to |
| 290 | use non-blocking algorithms or reference a non-Android open source library. |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 291 | </p> |
| 292 | |
| 293 | <h2 id="tools">Tools</h2> |
| 294 | |
| 295 | <p> |
| 296 | To the best of our knowledge, there are no automatic tools for |
| 297 | finding priority inversion, especially before it happens. Some |
| 298 | research static code analysis tools are capable of finding priority |
| 299 | inversions if able to access the entire codebase. Of course, if |
| 300 | arbitrary user code is involved (as it is here for the application) |
| 301 | or is a large codebase (as for the Linux kernel and device drivers), |
| 302 | static analysis may be impractical. The most important thing is to |
| 303 | read the code very carefully and get a good grasp on the entire |
| 304 | system and the interactions. Tools such as |
| 305 | <a href="http://developer.android.com/tools/help/systrace.html">systrace</a> |
| 306 | and |
| 307 | <code>ps -t -p</code> |
| 308 | are useful for seeing priority inversion after it occurs, but do |
| 309 | not tell you in advance. |
| 310 | </p> |
| 311 | |
Clay Murphy | 5d83ab4 | 2014-09-09 17:29:09 -0700 | [diff] [blame] | 312 | <h2 id="aFinalWord">A final word</h2> |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 313 | |
| 314 | <p> |
| 315 | After all of this discussion, don't be afraid of mutexes. Mutexes |
| 316 | are your friend for ordinary use, when used and implemented correctly |
| 317 | in ordinary non-time-critical use cases. But between high- and |
| 318 | low-priority tasks and in time-sensitive systems mutexes are more |
| 319 | likely to cause trouble. |
| 320 | </p> |
| 321 | |