media/utils/include/mediautils/TimerThread.h - LeafOS-Project/android_frameworks_av - Gitiles

 /*
  * Copyright (C) 2021 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 <atomic>
 #include <condition_variable>
 #include <deque>
 #include <functional>
 #include <map>
 #include <memory>
 #include <mutex>
 #include <string>
 #include <thread>
 #include <vector>

 #include <android-base/thread_annotations.h>

 #include <mediautils/FixedString.h>

 namespace android::mediautils {

 /**
  * A thread for deferred execution of tasks, with cancellation.
  */
 class TimerThread {
   public:
     // A Handle is a time_point that serves as a unique key to access a queued
     // request to the TimerThread.
     using Handle = std::chrono::steady_clock::time_point;

     // Duration is based on steady_clock (typically nanoseconds)
     // vs the system_clock duration (typically microseconds).
     using Duration = std::chrono::steady_clock::duration;

     static inline constexpr Handle INVALID_HANDLE =
             std::chrono::steady_clock::time_point::min();

     // Handle implementation details:
     // A Handle represents the timer expiration time based on std::chrono::steady_clock
     // (clock monotonic).  This Handle is computed as now() + timeout.
     //
     // The lsb of the Handle time_point is adjusted to indicate whether there is
     // a timeout action (1) or not (0).
     //

     template <size_t COUNT>
     static constexpr bool is_power_of_2_v = COUNT > 0 && (COUNT & (COUNT - 1)) == 0;

     template <size_t COUNT>
     static constexpr size_t mask_from_count_v = COUNT - 1;

     static constexpr size_t HANDLE_TYPES = 2;
     // HANDLE_TYPES must be a power of 2.
     static_assert(is_power_of_2_v<HANDLE_TYPES>);

     // The handle types
     enum class HANDLE_TYPE : size_t {
         NO_TIMEOUT = 0,
         TIMEOUT = 1,
     };

     static constexpr size_t HANDLE_TYPE_MASK = mask_from_count_v<HANDLE_TYPES>;

     template <typename T>
     static constexpr auto enum_as_value(T x) {
         return static_cast<std::underlying_type_t<T>>(x);
     }

     static inline bool isNoTimeoutHandle(Handle handle) {
         return (handle.time_since_epoch().count() & HANDLE_TYPE_MASK) ==
                 enum_as_value(HANDLE_TYPE::NO_TIMEOUT);
     }

     static inline bool isTimeoutHandle(Handle handle) {
         return (handle.time_since_epoch().count() & HANDLE_TYPE_MASK) ==
                 enum_as_value(HANDLE_TYPE::TIMEOUT);
     }

     // Returns a unique Handle that doesn't exist in the container.
     template <size_t MAX_TYPED_HANDLES, size_t HANDLE_TYPE_AS_VALUE, typename C, typename T>
     static Handle getUniqueHandleForHandleType_l(C container, T timeout) {
         static_assert(MAX_TYPED_HANDLES > 0 && HANDLE_TYPE_AS_VALUE < MAX_TYPED_HANDLES
                 && is_power_of_2_v<MAX_TYPED_HANDLES>,
                 " handles must be power of two");

         // Our initial handle is the deadline as computed from steady_clock.
         auto deadline = std::chrono::steady_clock::now() + timeout;

         // We adjust the lsbs by the minimum increment to have the correct
         // HANDLE_TYPE in the least significant bits.
         auto remainder = deadline.time_since_epoch().count() & HANDLE_TYPE_MASK;
         size_t offset = HANDLE_TYPE_AS_VALUE > remainder ? HANDLE_TYPE_AS_VALUE - remainder :
                      MAX_TYPED_HANDLES + HANDLE_TYPE_AS_VALUE - remainder;
         deadline += std::chrono::steady_clock::duration(offset);

         // To avoid key collisions, advance the handle by MAX_TYPED_HANDLES (the modulus factor)
         // until the key is unique.
         while (container.find(deadline) != container.end()) {
             deadline += std::chrono::steady_clock::duration(MAX_TYPED_HANDLES);
         }
         return deadline;
     }

     // TimerCallback invoked on timeout or cancel.
     using TimerCallback = std::function<void(Handle)>;

     /**
      * Schedules a task to be executed in the future (`timeout` duration from now).
      *
      * \param tag     string associated with the task.  This need not be unique,
      *                as the Handle returned is used for cancelling.
      * \param func    callback function that is invoked at the timeout.
      * \param timeoutDuration timeout duration which is converted to milliseconds with at
      *                least 45 integer bits.
      *                A timeout of 0 (or negative) means the timer never expires
      *                so func() is never called. These tasks are stored internally
      *                and reported in the toString() until manually cancelled.
      * \returns       a handle that can be used for cancellation.
      */
     Handle scheduleTask(
             std::string_view tag, TimerCallback&& func,
             Duration timeoutDuration, Duration secondChanceDuration);

     /**
      * Tracks a task that shows up on toString() until cancelled.
      *
      * \param tag     string associated with the task.
      * \returns       a handle that can be used for cancellation.
      */
     Handle trackTask(std::string_view tag);

     /**
      * Cancels a task previously scheduled with scheduleTask()
      * or trackTask().
      *
      * \returns true if cancelled. If the task has already executed
      *          or if the handle doesn't exist, this is a no-op
      *          and returns false.
      */
     bool cancelTask(Handle handle);

     struct SnapshotAnalysis;
     /**
      * Take a snapshot of the current state of the TimerThread and determine the
      * potential cause of a deadlock.
      * \param retiredCount The number of successfully retired calls to capture
      *                      (may be many).
      * \return See below for a description of a SnapShotAnalysis object
      */
     SnapshotAnalysis getSnapshotAnalysis(size_t retiredCount = SIZE_MAX) const;

     /**
      * Returns a string representation of the TimerThread queue.
      *
      * The queue is dumped in order of scheduling (not deadline).
      */
     std::string pendingToString() const;

     /**
      * Returns a string representation of the last retired tasks.
      *
      * These tasks from trackTask() or scheduleTask() are
      * cancelled.
      *
      * These are ordered when the task was retired.
      *
      * \param n is maximum number of tasks to dump.
      */
     std::string retiredToString(size_t n = SIZE_MAX) const;


     /**
      * Returns a string representation of the last timeout tasks.
      *
      * These tasks from scheduleTask() which have  timed-out.
      *
      * These are ordered when the task had timed-out.
      *
      * \param n is maximum number of tasks to dump.
      */
     std::string timeoutToString(size_t n = SIZE_MAX) const;

     /**
      * Dumps a container with SmartPointer<Request> to a string.
      *
      * "{ Request1 } { Request2} ...{ RequestN }"
      */
     template <typename T>
     static std::string requestsToString(const T& containerRequests) {
         std::string s;
         // append seems to be faster than stringstream.
         // https://stackoverflow.com/questions/18892281/most-optimized-way-of-concatenation-in-strings
         for (const auto& request : containerRequests) {
             s.append("{ ").append(request->toString()).append(" } ");
         }
         // If not empty, there's an extra space at the end, so we trim it off.
         if (!s.empty()) s.pop_back();
         return s;
     }

     // To minimize movement of data, we pass around shared_ptrs to Requests.
     // These are allocated and deallocated outside of the lock.
     // TODO(b/243839867) consider options to merge Request with the
     // TimeCheck::TimeCheckHandler struct.
     struct Request {
         Request(std::chrono::system_clock::time_point _scheduled,
                 std::chrono::system_clock::time_point _deadline,
                 Duration _secondChanceDuration,
                 pid_t _tid,
                 std::string_view _tag)
             : scheduled(_scheduled)
             , deadline(_deadline)
             , secondChanceDuration(_secondChanceDuration)
             , tid(_tid)
             , tag(_tag)
             {}

         const std::chrono::system_clock::time_point scheduled;
         const std::chrono::system_clock::time_point deadline; // deadline := scheduled
                                                               // + timeoutDuration
                                                               // + secondChanceDuration
                                                               // if deadline == scheduled, no
                                                               // timeout, task not executed.
         Duration secondChanceDuration;
         const pid_t tid;
         const FixedString62 tag;
         std::string toString() const;
     };


     // SnapshotAnalysis contains info deduced by analysisTimeout().

     struct SnapshotAnalysis {
         // If we were unable to determine any applicable thread ids,
         // we leave their value as INVALID_PID.
         // Note, we use the linux thread id (not pthread), so its type is pid_t.
         static constexpr pid_t INVALID_PID = -1;
         // Description of likely issue and/or blocked method.
         // Empty if no actionable info.
         std::string description;
         // Tid of the (latest) monitored thread which has timed out.
         // This is the thread which the suspect is deduced with respect to.
         // Most often, this is the thread which an abort is being triggered
         // from.
         pid_t timeoutTid = INVALID_PID;
         // Tid of the (HAL) thread which has likely halted progress, selected
         // from pendingRequests. May be the same as timeoutTid, if the timed-out
         // thread directly called into the HAL.
         pid_t suspectTid = INVALID_PID;
         // Number of second chances given by the timer thread
         size_t secondChanceCount;
         // List of pending requests
         std::vector<std::shared_ptr<const Request>> pendingRequests;
         // List of timed-out requests
         std::vector<std::shared_ptr<const Request>> timeoutRequests;
         // List of retired requests
         std::vector<std::shared_ptr<const Request>> retiredRequests;
         // mutex deadlock / wait detection information.
         bool hasMutexCycle = false;
         std::vector<std::pair<pid_t, std::string>> mutexWaitChain;
         // Dumps the information contained above as well as additional call
         // stacks where applicable.
         std::string toString(bool showTimeoutStack = true) const;
     };

   private:
     // Deque of requests, in order of add().
     // This class is thread-safe.
     class RequestQueue {
       public:
         explicit RequestQueue(size_t maxSize)
             : mRequestQueueMax(maxSize) {}

         void add(std::shared_ptr<const Request>);

         // return up to the last "n" requests retired.
         void copyRequests(std::vector<std::shared_ptr<const Request>>& requests,
             size_t n = SIZE_MAX) const;

       private:
         const size_t mRequestQueueMax;
         mutable std::mutex mRQMutex;
         std::deque<std::pair<std::chrono::system_clock::time_point,
                              std::shared_ptr<const Request>>>
                 mRequestQueue GUARDED_BY(mRQMutex);
     };

     // A storage map of tasks without timeouts.  There is no TimerCallback
     // required, it just tracks the tasks with the tag, scheduled time and the tid.
     // These tasks show up on a pendingToString() until manually cancelled.
     class NoTimeoutMap {
         mutable std::mutex mNTMutex;
         std::map<Handle, std::shared_ptr<const Request>> mMap GUARDED_BY(mNTMutex);
         Handle getUniqueHandle_l() REQUIRES(mNTMutex) {
             return getUniqueHandleForHandleType_l<
                     HANDLE_TYPES, enum_as_value(HANDLE_TYPE::NO_TIMEOUT)>(
                 mMap, Duration{} /* timeout */);
         }

       public:
         bool isValidHandle(Handle handle) const; // lock free
         Handle add(std::shared_ptr<const Request> request);
         std::shared_ptr<const Request> remove(Handle handle);
         void copyRequests(std::vector<std::shared_ptr<const Request>>& requests) const;
     };

     // Monitor thread.
     // This thread manages shared pointers to Requests and a function to
     // call on timeout.
     // This class is thread-safe.
     class MonitorThread {
         std::atomic<size_t> mSecondChanceCount{};
         mutable std::mutex mMutex;
         mutable std::condition_variable mCond GUARDED_BY(mMutex);

         // Ordered map of requests based on time of deadline.
         //
         std::map<Handle, std::pair<std::shared_ptr<const Request>, TimerCallback>>
                 mMonitorRequests GUARDED_BY(mMutex);

         // Due to monotonic/steady clock inaccuracies during suspend,
         // we allow an additional second chance waiting time to prevent
         // false removal.

         // This mSecondChanceRequests queue is almost always empty.
         // Using a pair with the original handle allows lookup and keeps
         // the Key unique.
         std::map<std::pair<Handle /* new */, Handle /* original */>,
                 std::pair<std::shared_ptr<const Request>, TimerCallback>>
                         mSecondChanceRequests GUARDED_BY(mMutex);

         RequestQueue& mTimeoutQueue GUARDED_BY(mMutex); // added to when request times out.

         // Worker thread variables
         bool mShouldExit GUARDED_BY(mMutex) = false;

         // To avoid race with initialization,
         // mThread should be initialized last as the thread is launched immediately.
         std::thread mThread;

         void threadFunc();
         Handle getUniqueHandle_l(Duration timeout) REQUIRES(mMutex) {
             return getUniqueHandleForHandleType_l<
                     HANDLE_TYPES, enum_as_value(HANDLE_TYPE::TIMEOUT)>(
                 mMonitorRequests, timeout);
         }

       public:
         MonitorThread(RequestQueue &timeoutQueue);
         ~MonitorThread();

         Handle add(std::shared_ptr<const Request> request, TimerCallback&& func,
                 Duration timeout);
         std::shared_ptr<const Request> remove(Handle handle);
         void copyRequests(std::vector<std::shared_ptr<const Request>>& requests) const;
         size_t getSecondChanceCount() const {
             return mSecondChanceCount.load(std::memory_order_relaxed);
         }
     };


     // A HAL method is where the substring "Hidl" is in the class name.
     // The tag should look like: ... Hidl ... :: ...
     static bool isRequestFromHal(const std::shared_ptr<const Request>& request);

     std::vector<std::shared_ptr<const Request>> getPendingRequests() const;

     static constexpr size_t kRetiredQueueMax = 16;
     RequestQueue mRetiredQueue{kRetiredQueueMax};  // locked internally

     static constexpr size_t kTimeoutQueueMax = 16;
     RequestQueue mTimeoutQueue{kTimeoutQueueMax};  // locked internally

     NoTimeoutMap mNoTimeoutMap;  // locked internally

     MonitorThread mMonitorThread{mTimeoutQueue};  // This should be initialized last because
                                                   // the thread is launched immediately.
                                                   // Locked internally.
 };

 }  // namespace android::mediautils
	/*
	* Copyright (C) 2021 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 <atomic>
	#include <condition_variable>
	#include <deque>
	#include <functional>
	#include <map>
	#include <memory>
	#include <mutex>
	#include <string>
	#include <thread>
	#include <vector>

	#include <android-base/thread_annotations.h>

	#include <mediautils/FixedString.h>

	namespace android::mediautils {

	/**
	* A thread for deferred execution of tasks, with cancellation.
	*/
	class TimerThread {
	public:
	// A Handle is a time_point that serves as a unique key to access a queued
	// request to the TimerThread.
	using Handle = std::chrono::steady_clock::time_point;

	// Duration is based on steady_clock (typically nanoseconds)
	// vs the system_clock duration (typically microseconds).
	using Duration = std::chrono::steady_clock::duration;

	static inline constexpr Handle INVALID_HANDLE =
	std::chrono::steady_clock::time_point::min();

	// Handle implementation details:
	// A Handle represents the timer expiration time based on std::chrono::steady_clock
	// (clock monotonic). This Handle is computed as now() + timeout.
	//
	// The lsb of the Handle time_point is adjusted to indicate whether there is
	// a timeout action (1) or not (0).
	//

	template <size_t COUNT>
	static constexpr bool is_power_of_2_v = COUNT > 0 && (COUNT & (COUNT - 1)) == 0;

	template <size_t COUNT>
	static constexpr size_t mask_from_count_v = COUNT - 1;

	static constexpr size_t HANDLE_TYPES = 2;
	// HANDLE_TYPES must be a power of 2.
	static_assert(is_power_of_2_v<HANDLE_TYPES>);

	// The handle types
	enum class HANDLE_TYPE : size_t {
	NO_TIMEOUT = 0,
	TIMEOUT = 1,
	};

	static constexpr size_t HANDLE_TYPE_MASK = mask_from_count_v<HANDLE_TYPES>;

	template <typename T>
	static constexpr auto enum_as_value(T x) {
	return static_cast<std::underlying_type_t<T>>(x);
	}

	static inline bool isNoTimeoutHandle(Handle handle) {
	return (handle.time_since_epoch().count() & HANDLE_TYPE_MASK) ==
	enum_as_value(HANDLE_TYPE::NO_TIMEOUT);
	}

	static inline bool isTimeoutHandle(Handle handle) {
	return (handle.time_since_epoch().count() & HANDLE_TYPE_MASK) ==
	enum_as_value(HANDLE_TYPE::TIMEOUT);
	}

	// Returns a unique Handle that doesn't exist in the container.
	template <size_t MAX_TYPED_HANDLES, size_t HANDLE_TYPE_AS_VALUE, typename C, typename T>
	static Handle getUniqueHandleForHandleType_l(C container, T timeout) {
	static_assert(MAX_TYPED_HANDLES > 0 && HANDLE_TYPE_AS_VALUE < MAX_TYPED_HANDLES
	&& is_power_of_2_v<MAX_TYPED_HANDLES>,
	" handles must be power of two");

	// Our initial handle is the deadline as computed from steady_clock.
	auto deadline = std::chrono::steady_clock::now() + timeout;

	// We adjust the lsbs by the minimum increment to have the correct
	// HANDLE_TYPE in the least significant bits.
	auto remainder = deadline.time_since_epoch().count() & HANDLE_TYPE_MASK;
	size_t offset = HANDLE_TYPE_AS_VALUE > remainder ? HANDLE_TYPE_AS_VALUE - remainder :
	MAX_TYPED_HANDLES + HANDLE_TYPE_AS_VALUE - remainder;
	deadline += std::chrono::steady_clock::duration(offset);

	// To avoid key collisions, advance the handle by MAX_TYPED_HANDLES (the modulus factor)
	// until the key is unique.
	while (container.find(deadline) != container.end()) {
	deadline += std::chrono::steady_clock::duration(MAX_TYPED_HANDLES);
	}
	return deadline;
	}

	// TimerCallback invoked on timeout or cancel.
	using TimerCallback = std::function<void(Handle)>;

	/**
	* Schedules a task to be executed in the future (`timeout` duration from now).
	*
	* \param tag string associated with the task. This need not be unique,
	* as the Handle returned is used for cancelling.
	* \param func callback function that is invoked at the timeout.
	* \param timeoutDuration timeout duration which is converted to milliseconds with at
	* least 45 integer bits.
	* A timeout of 0 (or negative) means the timer never expires
	* so func() is never called. These tasks are stored internally
	* and reported in the toString() until manually cancelled.
	* \returns a handle that can be used for cancellation.
	*/
	Handle scheduleTask(
	std::string_view tag, TimerCallback&& func,
	Duration timeoutDuration, Duration secondChanceDuration);

	/**
	* Tracks a task that shows up on toString() until cancelled.
	*
	* \param tag string associated with the task.
	* \returns a handle that can be used for cancellation.
	*/
	Handle trackTask(std::string_view tag);

	/**
	* Cancels a task previously scheduled with scheduleTask()
	* or trackTask().
	*
	* \returns true if cancelled. If the task has already executed
	* or if the handle doesn't exist, this is a no-op
	* and returns false.
	*/
	bool cancelTask(Handle handle);

	struct SnapshotAnalysis;
	/**
	* Take a snapshot of the current state of the TimerThread and determine the
	* potential cause of a deadlock.
	* \param retiredCount The number of successfully retired calls to capture
	* (may be many).
	* \return See below for a description of a SnapShotAnalysis object
	*/
	SnapshotAnalysis getSnapshotAnalysis(size_t retiredCount = SIZE_MAX) const;

	/**
	* Returns a string representation of the TimerThread queue.
	*
	* The queue is dumped in order of scheduling (not deadline).
	*/
	std::string pendingToString() const;

	/**
	* Returns a string representation of the last retired tasks.
	*
	* These tasks from trackTask() or scheduleTask() are
	* cancelled.
	*
	* These are ordered when the task was retired.
	*
	* \param n is maximum number of tasks to dump.
	*/
	std::string retiredToString(size_t n = SIZE_MAX) const;


	/**
	* Returns a string representation of the last timeout tasks.
	*
	* These tasks from scheduleTask() which have timed-out.
	*
	* These are ordered when the task had timed-out.
	*
	* \param n is maximum number of tasks to dump.
	*/
	std::string timeoutToString(size_t n = SIZE_MAX) const;

	/**
	* Dumps a container with SmartPointer<Request> to a string.
	*
	* "{ Request1 } { Request2} ...{ RequestN }"
	*/
	template <typename T>
	static std::string requestsToString(const T& containerRequests) {
	std::string s;
	// append seems to be faster than stringstream.
	// https://stackoverflow.com/questions/18892281/most-optimized-way-of-concatenation-in-strings
	for (const auto& request : containerRequests) {
	s.append("{ ").append(request->toString()).append(" } ");
	}
	// If not empty, there's an extra space at the end, so we trim it off.
	if (!s.empty()) s.pop_back();
	return s;
	}

	// To minimize movement of data, we pass around shared_ptrs to Requests.
	// These are allocated and deallocated outside of the lock.
	// TODO(b/243839867) consider options to merge Request with the
	// TimeCheck::TimeCheckHandler struct.
	struct Request {
	Request(std::chrono::system_clock::time_point _scheduled,
	std::chrono::system_clock::time_point _deadline,
	Duration _secondChanceDuration,
	pid_t _tid,
	std::string_view _tag)
	: scheduled(_scheduled)
	, deadline(_deadline)
	, secondChanceDuration(_secondChanceDuration)
	, tid(_tid)
	, tag(_tag)
	{}

	const std::chrono::system_clock::time_point scheduled;
	const std::chrono::system_clock::time_point deadline; // deadline := scheduled
	// + timeoutDuration
	// + secondChanceDuration
	// if deadline == scheduled, no
	// timeout, task not executed.
	Duration secondChanceDuration;
	const pid_t tid;
	const FixedString62 tag;
	std::string toString() const;
	};


	// SnapshotAnalysis contains info deduced by analysisTimeout().

	struct SnapshotAnalysis {
	// If we were unable to determine any applicable thread ids,
	// we leave their value as INVALID_PID.
	// Note, we use the linux thread id (not pthread), so its type is pid_t.
	static constexpr pid_t INVALID_PID = -1;
	// Description of likely issue and/or blocked method.
	// Empty if no actionable info.
	std::string description;
	// Tid of the (latest) monitored thread which has timed out.
	// This is the thread which the suspect is deduced with respect to.
	// Most often, this is the thread which an abort is being triggered
	// from.
	pid_t timeoutTid = INVALID_PID;
	// Tid of the (HAL) thread which has likely halted progress, selected
	// from pendingRequests. May be the same as timeoutTid, if the timed-out
	// thread directly called into the HAL.
	pid_t suspectTid = INVALID_PID;
	// Number of second chances given by the timer thread
	size_t secondChanceCount;
	// List of pending requests
	std::vector<std::shared_ptr<const Request>> pendingRequests;
	// List of timed-out requests
	std::vector<std::shared_ptr<const Request>> timeoutRequests;
	// List of retired requests
	std::vector<std::shared_ptr<const Request>> retiredRequests;
	// mutex deadlock / wait detection information.
	bool hasMutexCycle = false;
	std::vector<std::pair<pid_t, std::string>> mutexWaitChain;
	// Dumps the information contained above as well as additional call
	// stacks where applicable.
	std::string toString(bool showTimeoutStack = true) const;
	};

	private:
	// Deque of requests, in order of add().
	// This class is thread-safe.
	class RequestQueue {
	public:
	explicit RequestQueue(size_t maxSize)
	: mRequestQueueMax(maxSize) {}

	void add(std::shared_ptr<const Request>);

	// return up to the last "n" requests retired.
	void copyRequests(std::vector<std::shared_ptr<const Request>>& requests,
	size_t n = SIZE_MAX) const;

	private:
	const size_t mRequestQueueMax;
	mutable std::mutex mRQMutex;
	std::deque<std::pair<std::chrono::system_clock::time_point,
	std::shared_ptr<const Request>>>
	mRequestQueue GUARDED_BY(mRQMutex);
	};

	// A storage map of tasks without timeouts. There is no TimerCallback
	// required, it just tracks the tasks with the tag, scheduled time and the tid.
	// These tasks show up on a pendingToString() until manually cancelled.
	class NoTimeoutMap {
	mutable std::mutex mNTMutex;
	std::map<Handle, std::shared_ptr<const Request>> mMap GUARDED_BY(mNTMutex);
	Handle getUniqueHandle_l() REQUIRES(mNTMutex) {
	return getUniqueHandleForHandleType_l<
	HANDLE_TYPES, enum_as_value(HANDLE_TYPE::NO_TIMEOUT)>(
	mMap, Duration{} /* timeout */);
	}

	public:
	bool isValidHandle(Handle handle) const; // lock free
	Handle add(std::shared_ptr<const Request> request);
	std::shared_ptr<const Request> remove(Handle handle);
	void copyRequests(std::vector<std::shared_ptr<const Request>>& requests) const;
	};

	// Monitor thread.
	// This thread manages shared pointers to Requests and a function to
	// call on timeout.
	// This class is thread-safe.
	class MonitorThread {
	std::atomic<size_t> mSecondChanceCount{};
	mutable std::mutex mMutex;
	mutable std::condition_variable mCond GUARDED_BY(mMutex);

	// Ordered map of requests based on time of deadline.
	//
	std::map<Handle, std::pair<std::shared_ptr<const Request>, TimerCallback>>
	mMonitorRequests GUARDED_BY(mMutex);

	// Due to monotonic/steady clock inaccuracies during suspend,
	// we allow an additional second chance waiting time to prevent
	// false removal.

	// This mSecondChanceRequests queue is almost always empty.
	// Using a pair with the original handle allows lookup and keeps
	// the Key unique.
	std::map<std::pair<Handle /* new /, Handle / original */>,
	std::pair<std::shared_ptr<const Request>, TimerCallback>>
	mSecondChanceRequests GUARDED_BY(mMutex);

	RequestQueue& mTimeoutQueue GUARDED_BY(mMutex); // added to when request times out.

	// Worker thread variables
	bool mShouldExit GUARDED_BY(mMutex) = false;

	// To avoid race with initialization,
	// mThread should be initialized last as the thread is launched immediately.
	std::thread mThread;

	void threadFunc();
	Handle getUniqueHandle_l(Duration timeout) REQUIRES(mMutex) {
	return getUniqueHandleForHandleType_l<
	HANDLE_TYPES, enum_as_value(HANDLE_TYPE::TIMEOUT)>(
	mMonitorRequests, timeout);
	}

	public:
	MonitorThread(RequestQueue &timeoutQueue);
	~MonitorThread();

	Handle add(std::shared_ptr<const Request> request, TimerCallback&& func,
	Duration timeout);
	std::shared_ptr<const Request> remove(Handle handle);
	void copyRequests(std::vector<std::shared_ptr<const Request>>& requests) const;
	size_t getSecondChanceCount() const {
	return mSecondChanceCount.load(std::memory_order_relaxed);
	}
	};


	// A HAL method is where the substring "Hidl" is in the class name.
	// The tag should look like: ... Hidl ... :: ...
	static bool isRequestFromHal(const std::shared_ptr<const Request>& request);

	std::vector<std::shared_ptr<const Request>> getPendingRequests() const;

	static constexpr size_t kRetiredQueueMax = 16;
	RequestQueue mRetiredQueue{kRetiredQueueMax}; // locked internally

	static constexpr size_t kTimeoutQueueMax = 16;
	RequestQueue mTimeoutQueue{kTimeoutQueueMax}; // locked internally

	NoTimeoutMap mNoTimeoutMap; // locked internally

	MonitorThread mMonitorThread{mTimeoutQueue}; // This should be initialized last because
	// the thread is launched immediately.
	// Locked internally.
	};

	} // namespace android::mediautils