media/jni/soundpool/StreamManager.h - SHIFTPHONES/android_frameworks_base - Gitiles

 /*
  * Copyright (C) 2019 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.
  */

 #pragma once

 #include "Stream.h"

 #include <condition_variable>
 #include <future>
 #include <list>
 #include <map>
 #include <memory>
 #include <mutex>
 #include <unordered_set>
 #include <vector>

 #include <utils/AndroidThreads.h>

 namespace android::soundpool {

 // TODO: Move helper classes to a utility file, with separate test.

 /**
  * JavaThread is used like std::thread but for threads that may call the JVM.
  *
  * std::thread does not easily attach to the JVM.  We need JVM capable threads
  * from createThreadEtc() since android binder call optimization may attempt to
  * call back into Java if the SoundPool runs in system server.
  *
  *
  * No locking is required - the member variables are inherently thread-safe.
  */
 class JavaThread {
 public:
     JavaThread(std::function<void()> f, const char *name)
         : mF{std::move(f)} {
         createThreadEtc(staticFunction, this, name);
     }

     JavaThread(JavaThread &&) = delete; // uses "this" ptr, not moveable.

     ~JavaThread() {
         join(); // manually block until the future is ready as std::future
                 // destructor doesn't block unless it comes from std::async
                 // and it is the last reference to shared state.
     }

     void join() const {
         mFuture.wait();
     }

     bool isClosed() const {
         return mIsClosed;
     }

 private:
     static int staticFunction(void *data) {
         JavaThread *jt = static_cast<JavaThread *>(data);
         jt->mF();
         jt->mIsClosed = true;  // set the flag that we are closed
                                // now before we allow the destructor to execute;
                                // otherwise there may be a use after free.
         jt->mPromise.set_value();
         return 0;
     }

     // No locking is provided as these variables are initialized in the constructor
     // and the members referenced are thread-safe objects.
     // (mFuture.wait() can block multiple threads.)
     // Note the order of member variables is reversed for destructor.
     const std::function<void()> mF;
     // Used in join() to block until the thread completes.
     // See https://en.cppreference.com/w/cpp/thread/promise for the void specialization of
     // promise.
     std::promise<void>          mPromise;
     std::future<void>           mFuture{mPromise.get_future()};
     std::atomic_bool            mIsClosed = false;
 };

 /**
  * The ThreadPool manages thread lifetimes of SoundPool worker threads.
  *
  * TODO: the (eventual) goal of ThreadPool is to transparently and cooperatively
  * maximize CPU utilization while avoiding starvation of other applications.
  * Some possibilities:
  *
  * We should create worker threads when we have SoundPool work and the system is idle.
  * CPU cycles are "use-it-or-lose-it" when the system is idle.
  *
  * We should adjust the priority of worker threads so that the second (and subsequent) worker
  * threads have lower priority (should we try to promote priority also?).
  *
  * We should throttle the spawning of new worker threads, spacing over time, to avoid
  * creating too many new threads all at once, on initialization.
  */
 class ThreadPool {
 public:
     ThreadPool(size_t maxThreadCount, std::string name)
         : mMaxThreadCount(maxThreadCount)
         , mName{std::move(name)} { }

     ~ThreadPool() { quit(); }

     size_t getActiveThreadCount() const { return mActiveThreadCount; }
     size_t getMaxThreadCount() const { return mMaxThreadCount; }

     void quit() {
         std::list<std::unique_ptr<JavaThread>> threads;
         {
             std::lock_guard lock(mThreadLock);
             if (mQuit) return;  // already joined.
             mQuit = true;
             threads = std::move(mThreads);
             mThreads.clear();
         }
         // mQuit set under lock, no more threads will be created.
         for (auto &thread : threads) {
             thread->join();
             thread.reset();
         }
         LOG_ALWAYS_FATAL_IF(mActiveThreadCount != 0,
                 "Invalid Active Threads: %zu", (size_t)mActiveThreadCount);
     }

     // returns a non-zero id if successful, the id is to help logging messages.
     int32_t launch(std::function<void(int32_t /* id */)> f) {
         std::list<std::unique_ptr<JavaThread>> threadsToRelease; // release outside of lock.
         std::lock_guard lock(mThreadLock);
         if (mQuit) return 0;  // ignore if we have quit

         // clean up threads.
         for (auto it = mThreads.begin(); it != mThreads.end(); ) {
             if ((*it)->isClosed()) {
                 threadsToRelease.emplace_back(std::move(*it));
                it = mThreads.erase(it);
             } else {
                ++it;
             }
         }

         const size_t threadCount = mThreads.size();
         if (threadCount < mMaxThreadCount) {
             // if the id wraps, we don't care about collisions.  it's just for logging.
             mNextThreadId = mNextThreadId == INT32_MAX ? 1 : ++mNextThreadId;
             const int32_t id = mNextThreadId;
             mThreads.emplace_back(std::make_unique<JavaThread>(
                     [this, id, mf = std::move(f)] { mf(id); --mActiveThreadCount; },
                     (mName + std::to_string(id)).c_str()));
             ++mActiveThreadCount;
             return id;
         }
         return 0;
     }

     // TODO: launch only if load average is low.
     // This gets the load average
     // See also std::thread::hardware_concurrency() for the concurrent capability.
     static double getLoadAvg() {
         double loadAvg[1];
         if (getloadavg(loadAvg, std::size(loadAvg)) > 0) {
             return loadAvg[0];
         }
         return -1.;
     }

 private:
     const size_t            mMaxThreadCount;
     const std::string       mName;

     std::atomic_size_t      mActiveThreadCount = 0;

     std::mutex              mThreadLock;
     bool                    mQuit = false;           // GUARDED_BY(mThreadLock)
     int32_t                 mNextThreadId = 0;       // GUARDED_BY(mThreadLock)
     std::list<std::unique_ptr<JavaThread>> mThreads; // GUARDED_BY(mThreadLock)
 };

 /**
  * A Perfect HashTable for IDs (key) to pointers (value).
  *
  * There are no collisions.  Why? because we generate the IDs for you to look up :-).
  *
  * The goal of this hash table is to map an integer ID handle > 0 to a pointer.
  * We give these IDs in monotonic order (though we may skip if it were to cause a collision).
  *
  * The size of the hashtable must be large enough to accommodate the max number of keys.
  * We suggest 2x.
  *
  * Readers are lockless
  * Single writer could be lockless, but we allow multiple writers through an internal lock.
  *
  * For the Key type K, valid keys generated are > 0 (signed or unsigned)
  * For the Value type V, values are pointers - nullptr means empty.
  */
 template <typename K, typename V>
 class PerfectHash {
 public:
     PerfectHash(size_t hashCapacity)
         : mHashCapacity(hashCapacity)
         , mK2V{new std::atomic<V>[hashCapacity]()} {
     }

     // Generate a key for a value V.
     // There is a testing function getKforV() which checks what the value reports as its key.
     //
     // Calls back into getKforV under lock.
     //
     // We expect that the hashCapacity is 2x the number of stored keys in order
     // to have one or two tries to find an empty slot
     K generateKey(V value, std::function<K(V)> getKforV, K oldKey = 0) {
         std::lock_guard lock(mHashLock);
         // try to remove the old key.
         if (oldKey > 0) {  // key valid
             const V v = getValue(oldKey);
             if (v != nullptr) {  // value still valid
                 const K atPosition = getKforV(v);
                 if (atPosition < 0 ||            // invalid value
                         atPosition == oldKey ||  // value's key still valid and matches old key
                         ((atPosition ^ oldKey) & (mHashCapacity - 1)) != 0) { // stale key entry
                     getValue(oldKey) = nullptr;  // invalidate
                 }
             } // else if value is invalid, no need to invalidate.
         }
         // check if we are invalidating only.
         if (value == nullptr) return 0;
         // now insert the new value and return the key.
         size_t tries = 0;
         for (; tries < mHashCapacity; ++tries) {
             mNextKey = mNextKey == std::numeric_limits<K>::max() ? 1 : mNextKey + 1;
             const V v = getValue(mNextKey);
             //ALOGD("tries: %zu, key:%d value:%p", tries, (int)mNextKey, v);
             if (v == nullptr) break; // empty
             const K atPosition = getKforV(v);
             //ALOGD("tries: %zu  key atPosition:%d", tries, (int)atPosition);
             if (atPosition < 0 || // invalid value
                     ((atPosition ^ mNextKey) & (mHashCapacity - 1)) != 0) { // stale key entry
                 break;
            }
         }
         LOG_ALWAYS_FATAL_IF(tries == mHashCapacity, "hash table overflow!");
         //ALOGD("%s: found after %zu tries", __func__, tries);
         getValue(mNextKey) = value;
         return mNextKey;
     }

     std::atomic<V> &getValue(K key) { return mK2V[key & (mHashCapacity - 1)]; }
     const std::atomic_int32_t &getValue(K key) const { return mK2V[key & (mHashCapacity - 1)]; }

 private:
     mutable std::mutex          mHashLock;
     const size_t                mHashCapacity; // size of mK2V no lock needed.
     std::unique_ptr<std::atomic<V>[]> mK2V;    // no lock needed for read access.
     K                           mNextKey{};    // GUARDED_BY(mHashLock)
 };

 /**
  * StreamMap contains the all the valid streams available to SoundPool.
  *
  * There is no Lock required for this class because the streams are
  * allocated in the constructor, the lookup is lockless, and the Streams
  * returned are locked internally.
  *
  * The lookup uses a perfect hash.
  * It is possible to use a lockless hash table or to use a stripe-locked concurrent
  * hashmap for essentially lock-free lookup.
  *
  * This follows Map-Reduce parallelism model.
  * https://en.wikipedia.org/wiki/MapReduce
  *
  * Conceivably the forEach could be parallelized using std::for_each with a
  * std::execution::par policy.
  *
  * https://en.cppreference.com/w/cpp/algorithm/for_each
  */
 class StreamMap {
 public:
     explicit StreamMap(int32_t streams);

     // Returns the stream associated with streamID or nullptr if not found.
     // This need not be locked.
     // The stream ID will never migrate to another Stream, but it may change
     // underneath you.  The Stream operations that take a streamID will confirm
     // that the streamID matches under the Stream lock before executing otherwise
     // it ignores the command as stale.
     Stream* findStream(int32_t streamID) const;

     // Iterates through the stream pool applying the function f.
     // Since this enumerates over every single stream, it is unlocked.
     //
     // See related: https://en.cppreference.com/w/cpp/algorithm/for_each
     void forEach(std::function<void(const Stream *)>f) const {
         for (size_t i = 0; i < mStreamPoolSize; ++i) {
             f(&mStreamPool[i]);
         }
     }

     void forEach(std::function<void(Stream *)>f) {
         for (size_t i = 0; i < mStreamPoolSize; ++i) {
             f(&mStreamPool[i]);
         }
     }

     // Returns the pair stream for a given Stream.
     // This need not be locked as it is a property of the pointer address.
     Stream* getPairStream(const Stream* stream) const {
         const size_t index = streamPosition(stream);
         return &mStreamPool[index ^ 1];
     }

     // find the position of the stream in mStreamPool array.
     size_t streamPosition(const Stream* stream) const; // no lock needed

     size_t getStreamMapSize() const {
         return mStreamPoolSize;
     }

     // find the next valid ID for a stream and store in hash table.
     int32_t getNextIdForStream(Stream* stream) const;

 private:

     // use the hash table to attempt to find the stream.
     // nullptr is returned if the lookup fails.
     Stream* lookupStreamFromId(int32_t streamID) const;

     // The stream pool is initialized in the constructor, effectively const.
     // no locking required for access.
     //
     // The constructor parameter "streams" results in streams pairs of streams.
     // We have twice as many streams because we wish to return a streamID "handle"
     // back to the app immediately, while we may be stopping the other stream in the
     // pair to get its AudioTrack :-).
     //
     // Of the stream pair, only one of the streams may have an AudioTrack.
     // The fixed association of a stream pair allows callbacks from the AudioTrack
     // to be associated properly to either one or the other of the stream pair.
     //
     // TODO: The stream pair arrangement can be removed if we have better AudioTrack
     // callback handling (being able to remove and change the callback after construction).
     //
     // Streams may be accessed anytime off of the stream pool
     // as there is internal locking on each stream.
     std::unique_ptr<Stream[]>   mStreamPool;        // no lock needed for access.
     size_t                      mStreamPoolSize;    // no lock needed for access.

     // In order to find the Stream from a StreamID, we could do a linear lookup in mStreamPool.
     // As an alternative, one could use stripe-locked or lock-free concurrent hashtables.
     //
     // When considering linear search vs hashmap, verify the typical use-case size.
     // Linear search is faster than std::unordered_map (circa 2018) for less than 40 elements.
     // [ Skarupke, M. (2018), "You Can Do Better than std::unordered_map: New and Recent
     // Improvements to Hash Table Performance." C++Now 2018. cppnow.org, see
     // https://www.youtube.com/watch?v=M2fKMP47slQ ]
     //
     // Here, we use a PerfectHash of Id to Stream *, since we can control the
     // StreamID returned to the user.  This allows O(1) read access to mStreamPool lock-free.
     //
     // We prefer that the next stream ID is monotonic for aesthetic reasons
     // (if we didn't care about monotonicity, a simple method is to apply a generation count
     // to each stream in the unused upper bits of its index in mStreamPool for the id).
     //
     std::unique_ptr<PerfectHash<int32_t, Stream *>> mPerfectHash;
 };

 /**
  * StreamManager is used to manage the streams (accessed by StreamID from Java).
  *
  * Locking order (proceeds from application to component).
  *  SoundPool mApiLock (if needed) -> StreamManager mStreamManagerLock
  *                                 -> pair Stream mLock -> queued Stream mLock
  */
 class StreamManager : public StreamMap {
 public:
     // Note: the SoundPool pointer is only used for stream initialization.
     // It is not stored in StreamManager.
     StreamManager(int32_t streams, size_t threads, const audio_attributes_t* attributes);
     ~StreamManager();

     // Returns positive streamID on success, 0 on failure.  This is locked.
     int32_t queueForPlay(const std::shared_ptr<Sound> &sound,
             int32_t soundID, float leftVolume, float rightVolume,
             int32_t priority, int32_t loop, float rate);

     ///////////////////////////////////////////////////////////////////////
     // Called from soundpool::Stream

     const audio_attributes_t* getAttributes() const { return &mAttributes; }

     // Moves the stream to the restart queue (called upon BUFFER_END of the static track)
     // this is locked internally.
     // If activeStreamIDToMatch is nonzero, it will only move to the restart queue
     // if the streamIDToMatch is found on the active queue.
     void moveToRestartQueue(Stream* stream, int32_t activeStreamIDToMatch = 0);

 private:

     void run(int32_t id);                        // worker thread, takes lock internally.
     void dump() const;                           // no lock needed

     // returns true if more worker threads are needed.
     bool needMoreThreads_l() {
         return mRestartStreams.size() > 0 &&
                 (mThreadPool->getActiveThreadCount() == 0
                 || std::distance(mRestartStreams.begin(),
                         mRestartStreams.upper_bound(systemTime()))
                         > (ptrdiff_t)mThreadPool->getActiveThreadCount());
     }

     // returns true if the stream was added.
     bool moveToRestartQueue_l(Stream* stream, int32_t activeStreamIDToMatch = 0);
     // returns number of queues the stream was removed from (should be 0 or 1);
     // a special code of -1 is returned if activeStreamIDToMatch is > 0 and
     // the stream wasn't found on the active queue.
     ssize_t removeFromQueues_l(Stream* stream, int32_t activeStreamIDToMatch = 0);
     void addToRestartQueue_l(Stream *stream);
     void addToActiveQueue_l(Stream *stream);
     void sanityCheckQueue_l() const;

     const audio_attributes_t mAttributes;
     std::unique_ptr<ThreadPool> mThreadPool;                  // locked internally

     // mStreamManagerLock is used to lock access for transitions between the
     // 4 stream queues by the Manager Thread or by the user initiated play().
     // A stream pair has exactly one stream on exactly one of the queues.
     std::mutex                  mStreamManagerLock;
     std::condition_variable     mStreamManagerCondition;

     bool                        mQuit = false;      // GUARDED_BY(mStreamManagerLock)

     // There are constructor arg "streams" pairs of streams, only one of each
     // pair on the 4 stream queues below.  The other stream in the pair serves as
     // placeholder to accumulate user changes, pending actual availability of the
     // AudioTrack, as it may be in use, requiring stop-then-restart.
     //
     // The 4 queues are implemented in the appropriate STL container based on perceived
     // optimality.

     // 1) mRestartStreams: Streams awaiting stop.
     // The paired stream may be active (but with no AudioTrack), and will be restarted
     // with an active AudioTrack when the current stream is stopped.
     std::multimap<int64_t /* stopTimeNs */, Stream*>
                                 mRestartStreams;    // GUARDED_BY(mStreamManagerLock)

     // 2) mActiveStreams: Streams that are active.
     // The paired stream will be inactive.
     // This is in order of specified by kStealActiveStream_OldestFirst
     std::list<Stream*>          mActiveStreams;     // GUARDED_BY(mStreamManagerLock)

     // 3) mAvailableStreams: Streams that are inactive.
     // The paired stream will also be inactive.
     // No particular order.
     std::unordered_set<Stream*> mAvailableStreams;  // GUARDED_BY(mStreamManagerLock)

     // 4) mProcessingStreams: Streams that are being processed by the ManagerThreads
     // When on this queue, the stream and its pair are not available for stealing.
     // Each ManagerThread will have at most one stream on the mProcessingStreams queue.
     // The paired stream may be active or restarting.
     // No particular order.
     std::unordered_set<Stream*> mProcessingStreams; // GUARDED_BY(mStreamManagerLock)
 };

 } // namespace android::soundpool
	/*
	* Copyright (C) 2019 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.
	*/

	#pragma once

	#include "Stream.h"

	#include <condition_variable>
	#include <future>
	#include <list>
	#include <map>
	#include <memory>
	#include <mutex>
	#include <unordered_set>
	#include <vector>

	#include <utils/AndroidThreads.h>

	namespace android::soundpool {

	// TODO: Move helper classes to a utility file, with separate test.

	/**
	* JavaThread is used like std::thread but for threads that may call the JVM.
	*
	* std::thread does not easily attach to the JVM. We need JVM capable threads
	* from createThreadEtc() since android binder call optimization may attempt to
	* call back into Java if the SoundPool runs in system server.
	*
	*
	* No locking is required - the member variables are inherently thread-safe.
	*/
	class JavaThread {
	public:
	JavaThread(std::function<void()> f, const char *name)
	: mF{std::move(f)} {
	createThreadEtc(staticFunction, this, name);
	}

	JavaThread(JavaThread &&) = delete; // uses "this" ptr, not moveable.

	~JavaThread() {
	join(); // manually block until the future is ready as std::future
	// destructor doesn't block unless it comes from std::async
	// and it is the last reference to shared state.
	}

	void join() const {
	mFuture.wait();
	}

	bool isClosed() const {
	return mIsClosed;
	}

	private:
	static int staticFunction(void *data) {
	JavaThread jt = static_cast<JavaThread >(data);
	jt->mF();
	jt->mIsClosed = true; // set the flag that we are closed
	// now before we allow the destructor to execute;
	// otherwise there may be a use after free.
	jt->mPromise.set_value();
	return 0;
	}

	// No locking is provided as these variables are initialized in the constructor
	// and the members referenced are thread-safe objects.
	// (mFuture.wait() can block multiple threads.)
	// Note the order of member variables is reversed for destructor.
	const std::function<void()> mF;
	// Used in join() to block until the thread completes.
	// See https://en.cppreference.com/w/cpp/thread/promise for the void specialization of
	// promise.
	std::promise<void> mPromise;
	std::future<void> mFuture{mPromise.get_future()};
	std::atomic_bool mIsClosed = false;
	};

	/**
	* The ThreadPool manages thread lifetimes of SoundPool worker threads.
	*
	* TODO: the (eventual) goal of ThreadPool is to transparently and cooperatively
	* maximize CPU utilization while avoiding starvation of other applications.
	* Some possibilities:
	*
	* We should create worker threads when we have SoundPool work and the system is idle.
	* CPU cycles are "use-it-or-lose-it" when the system is idle.
	*
	* We should adjust the priority of worker threads so that the second (and subsequent) worker
	* threads have lower priority (should we try to promote priority also?).
	*
	* We should throttle the spawning of new worker threads, spacing over time, to avoid
	* creating too many new threads all at once, on initialization.
	*/
	class ThreadPool {
	public:
	ThreadPool(size_t maxThreadCount, std::string name)
	: mMaxThreadCount(maxThreadCount)
	, mName{std::move(name)} { }

	~ThreadPool() { quit(); }

	size_t getActiveThreadCount() const { return mActiveThreadCount; }
	size_t getMaxThreadCount() const { return mMaxThreadCount; }

	void quit() {
	std::list<std::unique_ptr<JavaThread>> threads;
	{
	std::lock_guard lock(mThreadLock);
	if (mQuit) return; // already joined.
	mQuit = true;
	threads = std::move(mThreads);
	mThreads.clear();
	}
	// mQuit set under lock, no more threads will be created.
	for (auto &thread : threads) {
	thread->join();
	thread.reset();
	}
	LOG_ALWAYS_FATAL_IF(mActiveThreadCount != 0,
	"Invalid Active Threads: %zu", (size_t)mActiveThreadCount);
	}

	// returns a non-zero id if successful, the id is to help logging messages.
	int32_t launch(std::function<void(int32_t /* id */)> f) {
	std::list<std::unique_ptr<JavaThread>> threadsToRelease; // release outside of lock.
	std::lock_guard lock(mThreadLock);
	if (mQuit) return 0; // ignore if we have quit

	// clean up threads.
	for (auto it = mThreads.begin(); it != mThreads.end(); ) {
	if ((*it)->isClosed()) {
	threadsToRelease.emplace_back(std::move(*it));
	it = mThreads.erase(it);
	} else {
	++it;
	}
	}

	const size_t threadCount = mThreads.size();
	if (threadCount < mMaxThreadCount) {
	// if the id wraps, we don't care about collisions. it's just for logging.
	mNextThreadId = mNextThreadId == INT32_MAX ? 1 : ++mNextThreadId;
	const int32_t id = mNextThreadId;
	mThreads.emplace_back(std::make_unique<JavaThread>(
	[this, id, mf = std::move(f)] { mf(id); --mActiveThreadCount; },
	(mName + std::to_string(id)).c_str()));
	++mActiveThreadCount;
	return id;
	}
	return 0;
	}

	// TODO: launch only if load average is low.
	// This gets the load average
	// See also std::thread::hardware_concurrency() for the concurrent capability.
	static double getLoadAvg() {
	double loadAvg[1];
	if (getloadavg(loadAvg, std::size(loadAvg)) > 0) {
	return loadAvg[0];
	}
	return -1.;
	}

	private:
	const size_t mMaxThreadCount;
	const std::string mName;

	std::atomic_size_t mActiveThreadCount = 0;

	std::mutex mThreadLock;
	bool mQuit = false; // GUARDED_BY(mThreadLock)
	int32_t mNextThreadId = 0; // GUARDED_BY(mThreadLock)
	std::list<std::unique_ptr<JavaThread>> mThreads; // GUARDED_BY(mThreadLock)
	};

	/**
	* A Perfect HashTable for IDs (key) to pointers (value).
	*
	* There are no collisions. Why? because we generate the IDs for you to look up :-).
	*
	* The goal of this hash table is to map an integer ID handle > 0 to a pointer.
	* We give these IDs in monotonic order (though we may skip if it were to cause a collision).
	*
	* The size of the hashtable must be large enough to accommodate the max number of keys.
	* We suggest 2x.
	*
	* Readers are lockless
	* Single writer could be lockless, but we allow multiple writers through an internal lock.
	*
	* For the Key type K, valid keys generated are > 0 (signed or unsigned)
	* For the Value type V, values are pointers - nullptr means empty.
	*/
	template <typename K, typename V>
	class PerfectHash {
	public:
	PerfectHash(size_t hashCapacity)
	: mHashCapacity(hashCapacity)
	, mK2V{new std::atomic<V>[hashCapacity]()} {
	}

	// Generate a key for a value V.
	// There is a testing function getKforV() which checks what the value reports as its key.
	//
	// Calls back into getKforV under lock.
	//
	// We expect that the hashCapacity is 2x the number of stored keys in order
	// to have one or two tries to find an empty slot
	K generateKey(V value, std::function<K(V)> getKforV, K oldKey = 0) {
	std::lock_guard lock(mHashLock);
	// try to remove the old key.
	if (oldKey > 0) { // key valid
	const V v = getValue(oldKey);
	if (v != nullptr) { // value still valid
	const K atPosition = getKforV(v);
	if (atPosition < 0 \|\| // invalid value
	atPosition == oldKey \|\| // value's key still valid and matches old key
	((atPosition ^ oldKey) & (mHashCapacity - 1)) != 0) { // stale key entry
	getValue(oldKey) = nullptr; // invalidate
	}
	} // else if value is invalid, no need to invalidate.
	}
	// check if we are invalidating only.
	if (value == nullptr) return 0;
	// now insert the new value and return the key.
	size_t tries = 0;
	for (; tries < mHashCapacity; ++tries) {
	mNextKey = mNextKey == std::numeric_limits<K>::max() ? 1 : mNextKey + 1;
	const V v = getValue(mNextKey);
	//ALOGD("tries: %zu, key:%d value:%p", tries, (int)mNextKey, v);
	if (v == nullptr) break; // empty
	const K atPosition = getKforV(v);
	//ALOGD("tries: %zu key atPosition:%d", tries, (int)atPosition);
	if (atPosition < 0 \|\| // invalid value
	((atPosition ^ mNextKey) & (mHashCapacity - 1)) != 0) { // stale key entry
	break;
	}
	}
	LOG_ALWAYS_FATAL_IF(tries == mHashCapacity, "hash table overflow!");
	//ALOGD("%s: found after %zu tries", __func__, tries);
	getValue(mNextKey) = value;
	return mNextKey;
	}

	std::atomic<V> &getValue(K key) { return mK2V[key & (mHashCapacity - 1)]; }
	const std::atomic_int32_t &getValue(K key) const { return mK2V[key & (mHashCapacity - 1)]; }

	private:
	mutable std::mutex mHashLock;
	const size_t mHashCapacity; // size of mK2V no lock needed.
	std::unique_ptr<std::atomic<V>[]> mK2V; // no lock needed for read access.
	K mNextKey{}; // GUARDED_BY(mHashLock)
	};

	/**
	* StreamMap contains the all the valid streams available to SoundPool.
	*
	* There is no Lock required for this class because the streams are
	* allocated in the constructor, the lookup is lockless, and the Streams
	* returned are locked internally.
	*
	* The lookup uses a perfect hash.
	* It is possible to use a lockless hash table or to use a stripe-locked concurrent
	* hashmap for essentially lock-free lookup.
	*
	* This follows Map-Reduce parallelism model.
	* https://en.wikipedia.org/wiki/MapReduce
	*
	* Conceivably the forEach could be parallelized using std::for_each with a
	* std::execution::par policy.
	*
	* https://en.cppreference.com/w/cpp/algorithm/for_each
	*/
	class StreamMap {
	public:
	explicit StreamMap(int32_t streams);

	// Returns the stream associated with streamID or nullptr if not found.
	// This need not be locked.
	// The stream ID will never migrate to another Stream, but it may change
	// underneath you. The Stream operations that take a streamID will confirm
	// that the streamID matches under the Stream lock before executing otherwise
	// it ignores the command as stale.
	Stream* findStream(int32_t streamID) const;

	// Iterates through the stream pool applying the function f.
	// Since this enumerates over every single stream, it is unlocked.
	//
	// See related: https://en.cppreference.com/w/cpp/algorithm/for_each
	void forEach(std::function<void(const Stream *)>f) const {
	for (size_t i = 0; i < mStreamPoolSize; ++i) {
	f(&mStreamPool[i]);
	}
	}

	void forEach(std::function<void(Stream *)>f) {
	for (size_t i = 0; i < mStreamPoolSize; ++i) {
	f(&mStreamPool[i]);
	}
	}

	// Returns the pair stream for a given Stream.
	// This need not be locked as it is a property of the pointer address.
	Stream* getPairStream(const Stream* stream) const {
	const size_t index = streamPosition(stream);
	return &mStreamPool[index ^ 1];
	}

	// find the position of the stream in mStreamPool array.
	size_t streamPosition(const Stream* stream) const; // no lock needed

	size_t getStreamMapSize() const {
	return mStreamPoolSize;
	}

	// find the next valid ID for a stream and store in hash table.
	int32_t getNextIdForStream(Stream* stream) const;

	private:

	// use the hash table to attempt to find the stream.
	// nullptr is returned if the lookup fails.
	Stream* lookupStreamFromId(int32_t streamID) const;

	// The stream pool is initialized in the constructor, effectively const.
	// no locking required for access.
	//
	// The constructor parameter "streams" results in streams pairs of streams.
	// We have twice as many streams because we wish to return a streamID "handle"
	// back to the app immediately, while we may be stopping the other stream in the
	// pair to get its AudioTrack :-).
	//
	// Of the stream pair, only one of the streams may have an AudioTrack.
	// The fixed association of a stream pair allows callbacks from the AudioTrack
	// to be associated properly to either one or the other of the stream pair.
	//
	// TODO: The stream pair arrangement can be removed if we have better AudioTrack
	// callback handling (being able to remove and change the callback after construction).
	//
	// Streams may be accessed anytime off of the stream pool
	// as there is internal locking on each stream.
	std::unique_ptr<Stream[]> mStreamPool; // no lock needed for access.
	size_t mStreamPoolSize; // no lock needed for access.

	// In order to find the Stream from a StreamID, we could do a linear lookup in mStreamPool.
	// As an alternative, one could use stripe-locked or lock-free concurrent hashtables.
	//
	// When considering linear search vs hashmap, verify the typical use-case size.
	// Linear search is faster than std::unordered_map (circa 2018) for less than 40 elements.
	// [ Skarupke, M. (2018), "You Can Do Better than std::unordered_map: New and Recent
	// Improvements to Hash Table Performance." C++Now 2018. cppnow.org, see
	// https://www.youtube.com/watch?v=M2fKMP47slQ ]
	//
	// Here, we use a PerfectHash of Id to Stream *, since we can control the
	// StreamID returned to the user. This allows O(1) read access to mStreamPool lock-free.
	//
	// We prefer that the next stream ID is monotonic for aesthetic reasons
	// (if we didn't care about monotonicity, a simple method is to apply a generation count
	// to each stream in the unused upper bits of its index in mStreamPool for the id).
	//
	std::unique_ptr<PerfectHash<int32_t, Stream *>> mPerfectHash;
	};

	/**
	* StreamManager is used to manage the streams (accessed by StreamID from Java).
	*
	* Locking order (proceeds from application to component).
	* SoundPool mApiLock (if needed) -> StreamManager mStreamManagerLock
	* -> pair Stream mLock -> queued Stream mLock
	*/
	class StreamManager : public StreamMap {
	public:
	// Note: the SoundPool pointer is only used for stream initialization.
	// It is not stored in StreamManager.
	StreamManager(int32_t streams, size_t threads, const audio_attributes_t* attributes);
	~StreamManager();

	// Returns positive streamID on success, 0 on failure. This is locked.
	int32_t queueForPlay(const std::shared_ptr<Sound> &sound,
	int32_t soundID, float leftVolume, float rightVolume,
	int32_t priority, int32_t loop, float rate);

	///////////////////////////////////////////////////////////////////////
	// Called from soundpool::Stream

	const audio_attributes_t* getAttributes() const { return &mAttributes; }

	// Moves the stream to the restart queue (called upon BUFFER_END of the static track)
	// this is locked internally.
	// If activeStreamIDToMatch is nonzero, it will only move to the restart queue
	// if the streamIDToMatch is found on the active queue.
	void moveToRestartQueue(Stream* stream, int32_t activeStreamIDToMatch = 0);

	private:

	void run(int32_t id); // worker thread, takes lock internally.
	void dump() const; // no lock needed

	// returns true if more worker threads are needed.
	bool needMoreThreads_l() {
	return mRestartStreams.size() > 0 &&
	(mThreadPool->getActiveThreadCount() == 0
	\|\| std::distance(mRestartStreams.begin(),
	mRestartStreams.upper_bound(systemTime()))
	> (ptrdiff_t)mThreadPool->getActiveThreadCount());
	}

	// returns true if the stream was added.
	bool moveToRestartQueue_l(Stream* stream, int32_t activeStreamIDToMatch = 0);
	// returns number of queues the stream was removed from (should be 0 or 1);
	// a special code of -1 is returned if activeStreamIDToMatch is > 0 and
	// the stream wasn't found on the active queue.
	ssize_t removeFromQueues_l(Stream* stream, int32_t activeStreamIDToMatch = 0);
	void addToRestartQueue_l(Stream *stream);
	void addToActiveQueue_l(Stream *stream);
	void sanityCheckQueue_l() const;

	const audio_attributes_t mAttributes;
	std::unique_ptr<ThreadPool> mThreadPool; // locked internally

	// mStreamManagerLock is used to lock access for transitions between the
	// 4 stream queues by the Manager Thread or by the user initiated play().
	// A stream pair has exactly one stream on exactly one of the queues.
	std::mutex mStreamManagerLock;
	std::condition_variable mStreamManagerCondition;

	bool mQuit = false; // GUARDED_BY(mStreamManagerLock)

	// There are constructor arg "streams" pairs of streams, only one of each
	// pair on the 4 stream queues below. The other stream in the pair serves as
	// placeholder to accumulate user changes, pending actual availability of the
	// AudioTrack, as it may be in use, requiring stop-then-restart.
	//
	// The 4 queues are implemented in the appropriate STL container based on perceived
	// optimality.

	// 1) mRestartStreams: Streams awaiting stop.
	// The paired stream may be active (but with no AudioTrack), and will be restarted
	// with an active AudioTrack when the current stream is stopped.
	std::multimap<int64_t /* stopTimeNs /, Stream>
	mRestartStreams; // GUARDED_BY(mStreamManagerLock)

	// 2) mActiveStreams: Streams that are active.
	// The paired stream will be inactive.
	// This is in order of specified by kStealActiveStream_OldestFirst
	std::list<Stream*> mActiveStreams; // GUARDED_BY(mStreamManagerLock)

	// 3) mAvailableStreams: Streams that are inactive.
	// The paired stream will also be inactive.
	// No particular order.
	std::unordered_set<Stream*> mAvailableStreams; // GUARDED_BY(mStreamManagerLock)

	// 4) mProcessingStreams: Streams that are being processed by the ManagerThreads
	// When on this queue, the stream and its pair are not available for stealing.
	// Each ManagerThread will have at most one stream on the mProcessingStreams queue.
	// The paired stream may be active or restarting.
	// No particular order.
	std::unordered_set<Stream*> mProcessingStreams; // GUARDED_BY(mStreamManagerLock)
	};

	} // namespace android::soundpool