198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenpage.title=Avoiding Priority Inversion 298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten@jd:body 398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 4bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy<!-- 5bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy Copyright 2013 The Android Open Source Project 6bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy 7bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy Licensed under the Apache License, Version 2.0 (the "License"); 8bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy you may not use this file except in compliance with the License. 9bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy You may obtain a copy of the License at 10bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy 11bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy http://www.apache.org/licenses/LICENSE-2.0 12bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy 13bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy Unless required by applicable law or agreed to in writing, software 14bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy distributed under the License is distributed on an "AS IS" BASIS, 15bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy See the License for the specific language governing permissions and 17bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy limitations under the License. 18bc92aea666f04a57b8717fa0c1d43f1f287acd9aClay Murphy--> 1998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<div id="qv-wrapper"> 2098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten <div id="qv"> 2198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten <h2>In this document</h2> 2298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten <ol id="auto-toc"> 2398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten </ol> 2498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten </div> 2598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</div> 2698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 2798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 2898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenThis article explains how the Android's audio system attempts to avoid 29c28f237dd66f3826b36b51dbdea57411b9585869Clay Murphypriority inversion, as of the Android 4.1 release, 3098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenand highlights techniques that you can use too. 3198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 3298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 3398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 3498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenThese techniques may be useful to developers of high-performance 3598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenaudio apps, OEMs, and SoC providers who are implementing an audio 36c28f237dd66f3826b36b51dbdea57411b9585869Clay MurphyHAL. Please note implementing these techniques is not 3798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenguaranteed to prevent glitches or other failures, particularly if 3898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenused outside of the audio context. 39c28f237dd66f3826b36b51dbdea57411b9585869Clay MurphyYour results may vary, and you should conduct your own 4098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenevaluation and testing. 4198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 4298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 4398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<h2 id="background">Background</h2> 4498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 4598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 46c28f237dd66f3826b36b51dbdea57411b9585869Clay MurphyThe Android AudioFlinger audio server and AudioTrack/AudioRecord 4798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenclient implementation are being re-architected to reduce latency. 48c28f237dd66f3826b36b51dbdea57411b9585869Clay MurphyThis work started in Android 4.1, continued in 4.2 and 4.3, and now more 49c28f237dd66f3826b36b51dbdea57411b9585869Clay Murphyimprovements exist in version 4.4. 5098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 5198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 5298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 53c28f237dd66f3826b36b51dbdea57411b9585869Clay MurphyTo achieve this lower latency, many changes were needed throughout the system. One 54c28f237dd66f3826b36b51dbdea57411b9585869Clay Murphyimportant change is to assign CPU resources to time-critical 5598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenthreads with a more predictable scheduling policy. Reliable scheduling 56c28f237dd66f3826b36b51dbdea57411b9585869Clay Murphyallows the audio buffer sizes and counts to be reduced while still 5798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenavoiding artifacts due to underruns. 5898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 5998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 605d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphy<h2 id="priorityInversion">Priority inversion</h2> 6198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 6298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 6398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Priority_inversion">Priority inversion</a> 6498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenis a classic failure mode of real-time systems, 6598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenwhere a higher-priority task is blocked for an unbounded time waiting 665d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphyfor a lower-priority task to release a resource such as (shared 675d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphystate protected by) a 6898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Mutual_exclusion">mutex</a>. 6998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 7098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 7198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 7298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenIn an audio system, priority inversion typically manifests as a 7398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Glitch">glitch</a> 7498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten(click, pop, dropout), 7598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Max_Headroom_(character)">repeated audio</a> 7698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenwhen circular buffers 7798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenare used, or delay in responding to a command. 7898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 7998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 8098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 8198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenIn the Android audio implementation, priority inversion is most 825d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphylikely to occur in these places. And so you should focus your attention here: 8398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 8498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 8598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<ul> 8698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 8798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 8898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenbetween normal mixer thread and fast mixer thread in AudioFlinger 8998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 9098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 9198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 9298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenbetween application callback thread for a fast AudioTrack and 9398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenfast mixer thread (they both have elevated priority, but slightly 9498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastendifferent priorities) 9598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 9698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 9798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 98c28f237dd66f3826b36b51dbdea57411b9585869Clay Murphywithin the audio Hardware Abstraction Layer (HAL) implementation, e.g. for telephony or echo cancellation 9998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 10098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 10198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 10298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenwithin the audio driver in kernel 10398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 10498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 10598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 10698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenbetween AudioTrack callback thread and other app threads (this is out of our control) 10798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 10898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 10998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</ul> 11098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 11198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 11298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenAs of this writing, reduced latency for AudioRecord is planned but 11398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastennot yet implemented. The likely priority inversion spots will be 11498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastensimilar to those for AudioTrack. 11598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 11698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 1175d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphy<h2 id="commonSolutions">Common solutions</h2> 11898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 11998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 1205d83ab4822d3a64be5564b2040f892beacdeb995Clay MurphyThe typical solutions include: 12198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 12298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 12398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<ul> 12498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 12598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 12698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastendisabling interrupts 12798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 12898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 12998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 13098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenpriority inheritance mutexes 13198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 13298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 13398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</ul> 13498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 13598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 13698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenDisabling interrupts is not feasible in Linux user space, and does 137c28f237dd66f3826b36b51dbdea57411b9585869Clay Murphynot work for Symmetric Multi-Processors (SMP). 13898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 13998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 14098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 14198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 14298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenPriority inheritance 14398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Futex">futexes</a> 14498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten(fast user-space mutexes) are available 14598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenin Linux kernel, but are not currently exposed by the Android C 14698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenruntime library 14798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Bionic_(software)">Bionic</a>. 1485d83ab4822d3a64be5564b2040f892beacdeb995Clay MurphyThey are not used in the audio system because they are relatively heavyweight, 1495d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphyand because they rely on a trusted client. 15098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 15198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 15298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<h2 id="androidTechniques">Techniques used by Android</h2> 15398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 15498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 1555d83ab4822d3a64be5564b2040f892beacdeb995Clay MurphyExperiments started with "try lock" and lock with timeout. These are 15698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastennon-blocking and bounded blocking variants of the mutex lock 1575d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphyoperation. Try lock and lock with timeout worked fairly well but were 1585d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphysusceptible to a couple of obscure failure modes: the 15998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenserver was not guaranteed to be able to access the shared state if 16098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenthe client happened to be busy, and the cumulative timeout could 16198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenbe too long if there was a long sequence of unrelated locks that 16298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenall timed out. 16398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 16498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 16598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 16698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 16798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenWe also use 16898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Linearizability">atomic operations</a> 16998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastensuch as: 17098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 17198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 17298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<ul> 17398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li>increment</li> 17498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li>bitwise "or"</li> 17598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li>bitwise "and"</li> 17698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</ul> 17798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 17898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 179c28f237dd66f3826b36b51dbdea57411b9585869Clay MurphyAll of these return the previous value and include the necessary 18098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenSMP barriers. The disadvantage is they can require unbounded retries. 18198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenIn practice, we've found that the retries are not a problem. 18298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 18398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 1845d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphy<p class="note"><strong>Note:</strong> Atomic operations and their interactions with memory barriers 1855d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphyare notoriously badly misunderstood and used incorrectly. We include these methods 1865d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphyhere for completeness but recommend you also read the article 18798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="https://developer.android.com/training/articles/smp.html"> 18898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenSMP Primer for Android</a> 18998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenfor further information. 19098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 19198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 19298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 19398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenWe still have and use most of the above tools, and have recently 19498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenadded these techniques: 19598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 19698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 19798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<ul> 19898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 19998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 20098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenUse non-blocking single-reader single-writer 20198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Circular_buffer">FIFO queues</a> 20298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenfor data. 20398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 20498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 20598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 20698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenTry to 20798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<i>copy</i> 20898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenstate rather than 20998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<i>share</i> 21098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenstate between high- and 21198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenlow-priority modules. 21298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 21398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 21498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 21598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenWhen state does need to be shared, limit the state to the 21698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenmaximum-size 21798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Word_(computer_architecture)">word</a> 218c28f237dd66f3826b36b51dbdea57411b9585869Clay Murphythat can be accessed atomically in one-bus operation 21998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenwithout retries. 22098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 22198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 22298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 22398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenFor complex multi-word state, use a state queue. A state queue 22498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenis basically just a non-blocking single-reader single-writer FIFO 22598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenqueue used for state rather than data, except the writer collapses 22698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenadjacent pushes into a single push. 22798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 22898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 22998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 23098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenPay attention to 23198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Memory_barrier">memory barriers</a> 23298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenfor SMP correctness. 23398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 23498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 23598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 23698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Trust,_but_verify">Trust, but verify</a>. 23798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenWhen sharing 23898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<i>state</i> 23998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenbetween processes, don't 24098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenassume that the state is well-formed. For example, check that indices 24198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenare within bounds. This verification isn't needed between threads 24298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenin the same process, between mutual trusting processes (which 24398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastentypically have the same UID). It's also unnecessary for shared 24498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<i>data</i> 24598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastensuch as PCM audio where a corruption is inconsequential. 24698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 24798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 24898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</ul> 24998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 2505d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphy<h2 id="nonBlockingAlgorithms">Non-blocking algorithms</h2> 25198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 25298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 25398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://en.wikipedia.org/wiki/Non-blocking_algorithm">Non-blocking algorithms</a> 25498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenhave been a subject of much recent study. 25598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenBut with the exception of single-reader single-writer FIFO queues, 25698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenwe've found them to be complex and error-prone. 25798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 25898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 25998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 260c28f237dd66f3826b36b51dbdea57411b9585869Clay MurphyStarting in Android 4.2, you can find our non-blocking, 26198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastensingle-reader/writer classes in these locations: 26298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 26398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 26498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<ul> 26598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 26698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 26798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenframeworks/av/include/media/nbaio/ 26898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 26998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 27098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 27198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenframeworks/av/media/libnbaio/ 27298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 27398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 27498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<li> 27598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenframeworks/av/services/audioflinger/StateQueue* 27698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</li> 27798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 27898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</ul> 27998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 28098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 28198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenThese were designed specifically for AudioFlinger and are not 28298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastengeneral-purpose. Non-blocking algorithms are notorious for being 283c28f237dd66f3826b36b51dbdea57411b9585869Clay Murphydifficult to debug. You can look at this code as a model. But be 28498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenaware there may be bugs, and the classes are not guaranteed to be 28598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastensuitable for other purposes. 28698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 28798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 28898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 2895d83ab4822d3a64be5564b2040f892beacdeb995Clay MurphyFor developers, some of the sample OpenSL ES application code should be updated to 2905d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphyuse non-blocking algorithms or reference a non-Android open source library. 29198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 29298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 29398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<h2 id="tools">Tools</h2> 29498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 29598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 29698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenTo the best of our knowledge, there are no automatic tools for 29798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenfinding priority inversion, especially before it happens. Some 29898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenresearch static code analysis tools are capable of finding priority 29998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasteninversions if able to access the entire codebase. Of course, if 30098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenarbitrary user code is involved (as it is here for the application) 30198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenor is a large codebase (as for the Linux kernel and device drivers), 30298afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenstatic analysis may be impractical. The most important thing is to 30398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenread the code very carefully and get a good grasp on the entire 30498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastensystem and the interactions. Tools such as 30598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<a href="http://developer.android.com/tools/help/systrace.html">systrace</a> 30698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenand 30798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<code>ps -t -p</code> 30898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenare useful for seeing priority inversion after it occurs, but do 30998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastennot tell you in advance. 31098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 31198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 3125d83ab4822d3a64be5564b2040f892beacdeb995Clay Murphy<h2 id="aFinalWord">A final word</h2> 31398afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 31498afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten<p> 31598afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn KastenAfter all of this discussion, don't be afraid of mutexes. Mutexes 31698afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenare your friend for ordinary use, when used and implemented correctly 31798afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenin ordinary non-time-critical use cases. But between high- and 31898afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenlow-priority tasks and in time-sensitive systems mutexes are more 31998afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kastenlikely to cause trouble. 32098afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten</p> 32198afa53e3b9f45e52273ef1a4e9dea84c4df5e78Glenn Kasten 322