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 | |
| 60 | <h2 id="priorityInversion">Priority Inversion</h2> |
| 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 |
| 66 | for a lower-priority task to release a resource such as [shared |
| 67 | state protected by] a |
| 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 | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 82 | likely to occur in these places. And so we focus 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 | |
| 117 | <h2 id="commonSolutions">Common Solutions</h2> |
| 118 | |
| 119 | <p> |
| 120 | The typical solutions listed in the Wikipedia article include: |
| 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>. |
| 148 | We chose not to use them in the audio system |
| 149 | because they are relatively heavyweight, and because they rely on |
| 150 | a trusted client. |
| 151 | </p> |
| 152 | |
| 153 | <h2 id="androidTechniques">Techniques used by Android</h2> |
| 154 | |
| 155 | <p> |
| 156 | We started with "try lock" and lock with timeout. These are |
| 157 | non-blocking and bounded blocking variants of the mutex lock |
| 158 | operation. Try lock and lock with timeout worked fairly well for |
| 159 | us, but were susceptible to a couple of obscure failure modes: the |
| 160 | server was not guaranteed to be able to access the shared state if |
| 161 | the client happened to be busy, and the cumulative timeout could |
| 162 | be too long if there was a long sequence of unrelated locks that |
| 163 | all timed out. |
| 164 | </p> |
| 165 | |
| 166 | |
| 167 | <p> |
| 168 | We also use |
| 169 | <a href="http://en.wikipedia.org/wiki/Linearizability">atomic operations</a> |
| 170 | such as: |
| 171 | </p> |
| 172 | |
| 173 | <ul> |
| 174 | <li>increment</li> |
| 175 | <li>bitwise "or"</li> |
| 176 | <li>bitwise "and"</li> |
| 177 | </ul> |
| 178 | |
| 179 | <p> |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 180 | All of these return the previous value and include the necessary |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 181 | SMP barriers. The disadvantage is they can require unbounded retries. |
| 182 | In practice, we've found that the retries are not a problem. |
| 183 | </p> |
| 184 | |
| 185 | <p> |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 186 | <strong>Note</strong>: Atomic operations and their interactions with memory barriers |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 187 | are notoriously badly misunderstood and used incorrectly. We include |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 188 | these methods here for completeness but recommend you also read the article |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 189 | <a href="https://developer.android.com/training/articles/smp.html"> |
| 190 | SMP Primer for Android</a> |
| 191 | for further information. |
| 192 | </p> |
| 193 | |
| 194 | <p> |
| 195 | We still have and use most of the above tools, and have recently |
| 196 | added these techniques: |
| 197 | </p> |
| 198 | |
| 199 | <ul> |
| 200 | |
| 201 | <li> |
| 202 | Use non-blocking single-reader single-writer |
| 203 | <a href="http://en.wikipedia.org/wiki/Circular_buffer">FIFO queues</a> |
| 204 | for data. |
| 205 | </li> |
| 206 | |
| 207 | <li> |
| 208 | Try to |
| 209 | <i>copy</i> |
| 210 | state rather than |
| 211 | <i>share</i> |
| 212 | state between high- and |
| 213 | low-priority modules. |
| 214 | </li> |
| 215 | |
| 216 | <li> |
| 217 | When state does need to be shared, limit the state to the |
| 218 | maximum-size |
| 219 | <a href="http://en.wikipedia.org/wiki/Word_(computer_architecture)">word</a> |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 220 | that can be accessed atomically in one-bus operation |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 221 | without retries. |
| 222 | </li> |
| 223 | |
| 224 | <li> |
| 225 | For complex multi-word state, use a state queue. A state queue |
| 226 | is basically just a non-blocking single-reader single-writer FIFO |
| 227 | queue used for state rather than data, except the writer collapses |
| 228 | adjacent pushes into a single push. |
| 229 | </li> |
| 230 | |
| 231 | <li> |
| 232 | Pay attention to |
| 233 | <a href="http://en.wikipedia.org/wiki/Memory_barrier">memory barriers</a> |
| 234 | for SMP correctness. |
| 235 | </li> |
| 236 | |
| 237 | <li> |
| 238 | <a href="http://en.wikipedia.org/wiki/Trust,_but_verify">Trust, but verify</a>. |
| 239 | When sharing |
| 240 | <i>state</i> |
| 241 | between processes, don't |
| 242 | assume that the state is well-formed. For example, check that indices |
| 243 | are within bounds. This verification isn't needed between threads |
| 244 | in the same process, between mutual trusting processes (which |
| 245 | typically have the same UID). It's also unnecessary for shared |
| 246 | <i>data</i> |
| 247 | such as PCM audio where a corruption is inconsequential. |
| 248 | </li> |
| 249 | |
| 250 | </ul> |
| 251 | |
| 252 | <h2 id="nonBlockingAlgorithms">Non-Blocking Algorithms</h2> |
| 253 | |
| 254 | <p> |
| 255 | <a href="http://en.wikipedia.org/wiki/Non-blocking_algorithm">Non-blocking algorithms</a> |
| 256 | have been a subject of much recent study. |
| 257 | But with the exception of single-reader single-writer FIFO queues, |
| 258 | we've found them to be complex and error-prone. |
| 259 | </p> |
| 260 | |
| 261 | <p> |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 262 | Starting in Android 4.2, you can find our non-blocking, |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 263 | single-reader/writer classes in these locations: |
| 264 | </p> |
| 265 | |
| 266 | <ul> |
| 267 | |
| 268 | <li> |
| 269 | frameworks/av/include/media/nbaio/ |
| 270 | </li> |
| 271 | |
| 272 | <li> |
| 273 | frameworks/av/media/libnbaio/ |
| 274 | </li> |
| 275 | |
| 276 | <li> |
| 277 | frameworks/av/services/audioflinger/StateQueue* |
| 278 | </li> |
| 279 | |
| 280 | </ul> |
| 281 | |
| 282 | <p> |
| 283 | These were designed specifically for AudioFlinger and are not |
| 284 | general-purpose. Non-blocking algorithms are notorious for being |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 285 | 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] | 286 | aware there may be bugs, and the classes are not guaranteed to be |
| 287 | suitable for other purposes. |
| 288 | </p> |
| 289 | |
| 290 | <p> |
| 291 | For developers, we may update some of the sample OpenSL ES application |
Clay Murphy | c28f237 | 2013-09-25 16:13:40 -0700 | [diff] [blame] | 292 | code to use non-blocking algorithms or reference a non-Android open source |
Glenn Kasten | 98afa53 | 2013-04-15 14:02:36 -0700 | [diff] [blame] | 293 | library. |
| 294 | </p> |
| 295 | |
| 296 | <h2 id="tools">Tools</h2> |
| 297 | |
| 298 | <p> |
| 299 | To the best of our knowledge, there are no automatic tools for |
| 300 | finding priority inversion, especially before it happens. Some |
| 301 | research static code analysis tools are capable of finding priority |
| 302 | inversions if able to access the entire codebase. Of course, if |
| 303 | arbitrary user code is involved (as it is here for the application) |
| 304 | or is a large codebase (as for the Linux kernel and device drivers), |
| 305 | static analysis may be impractical. The most important thing is to |
| 306 | read the code very carefully and get a good grasp on the entire |
| 307 | system and the interactions. Tools such as |
| 308 | <a href="http://developer.android.com/tools/help/systrace.html">systrace</a> |
| 309 | and |
| 310 | <code>ps -t -p</code> |
| 311 | are useful for seeing priority inversion after it occurs, but do |
| 312 | not tell you in advance. |
| 313 | </p> |
| 314 | |
| 315 | <h2 id="aFinalWord">A Final Word</h2> |
| 316 | |
| 317 | <p> |
| 318 | After all of this discussion, don't be afraid of mutexes. Mutexes |
| 319 | are your friend for ordinary use, when used and implemented correctly |
| 320 | in ordinary non-time-critical use cases. But between high- and |
| 321 | low-priority tasks and in time-sensitive systems mutexes are more |
| 322 | likely to cause trouble. |
| 323 | </p> |
| 324 | |