1 // Copyright 2015 The Chromium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef BASE_TASK_SEQUENCE_MANAGER_WORK_QUEUE_SETS_H_ 6 #define BASE_TASK_SEQUENCE_MANAGER_WORK_QUEUE_SETS_H_ 7 8 #include <functional> 9 #include <optional> 10 #include <vector> 11 12 #include "base/base_export.h" 13 #include "base/containers/intrusive_heap.h" 14 #include "base/dcheck_is_on.h" 15 #include "base/memory/raw_ptr.h" 16 #include "base/memory/raw_ptr_exclusion.h" 17 #include "base/memory/stack_allocated.h" 18 #include "base/task/sequence_manager/sequence_manager.h" 19 #include "base/task/sequence_manager/task_order.h" 20 #include "base/task/sequence_manager/task_queue_impl.h" 21 #include "base/task/sequence_manager/work_queue.h" 22 23 namespace base { 24 namespace sequence_manager { 25 namespace internal { 26 27 struct WorkQueueAndTaskOrder { 28 STACK_ALLOCATED(); 29 30 public: WorkQueueAndTaskOrderWorkQueueAndTaskOrder31 WorkQueueAndTaskOrder(WorkQueue& work_queue, const TaskOrder& task_order) 32 : queue(&work_queue), order(task_order) {} 33 34 WorkQueue* queue = nullptr; 35 TaskOrder order; 36 }; 37 38 // There is a min-heap for each scheduler priority which keeps track of which 39 // queue in the set has the oldest task (i.e. the one that should be run next if 40 // the TaskQueueSelector chooses to run a task a given priority). 41 class BASE_EXPORT WorkQueueSets { 42 public: 43 class Observer { 44 public: 45 virtual ~Observer() = default; 46 47 virtual void WorkQueueSetBecameEmpty(size_t set_index) = 0; 48 49 virtual void WorkQueueSetBecameNonEmpty(size_t set_index) = 0; 50 }; 51 52 WorkQueueSets(const char* name, 53 Observer* observer, 54 const SequenceManager::Settings& settings); 55 WorkQueueSets(const WorkQueueSets&) = delete; 56 WorkQueueSets& operator=(const WorkQueueSets&) = delete; 57 ~WorkQueueSets(); 58 59 // O(log num queues) 60 void AddQueue(WorkQueue* queue, size_t set_index); 61 62 // O(log num queues) 63 void RemoveQueue(WorkQueue* work_queue); 64 65 // O(log num queues) 66 void ChangeSetIndex(WorkQueue* queue, size_t set_index); 67 68 // O(log num queues) 69 void OnQueuesFrontTaskChanged(WorkQueue* queue); 70 71 // O(log num queues) 72 void OnTaskPushedToEmptyQueue(WorkQueue* work_queue); 73 74 // If empty it's O(1) amortized, otherwise it's O(log num queues). Slightly 75 // faster on average than OnQueuesFrontTaskChanged. 76 // Assumes |work_queue| contains the lowest enqueue order in the set. 77 void OnPopMinQueueInSet(WorkQueue* work_queue); 78 79 // O(log num queues) 80 void OnQueueBlocked(WorkQueue* work_queue); 81 82 // O(1) 83 std::optional<WorkQueueAndTaskOrder> GetOldestQueueAndTaskOrderInSet( 84 size_t set_index) const; 85 86 #if DCHECK_IS_ON() 87 // O(1) 88 std::optional<WorkQueueAndTaskOrder> GetRandomQueueAndTaskOrderInSet( 89 size_t set_index) const; 90 #endif 91 92 // O(1) 93 bool IsSetEmpty(size_t set_index) const; 94 95 #if DCHECK_IS_ON() || !defined(NDEBUG) 96 // Note this iterates over everything in |work_queue_heaps_|. 97 // It's intended for use with DCHECKS and for testing 98 bool ContainsWorkQueueForTest(const WorkQueue* queue) const; 99 #endif 100 GetName()101 const char* GetName() const { return name_; } 102 103 // Collects ready tasks which where skipped over when |selected_work_queue| 104 // was selected. Note this is somewhat expensive. 105 void CollectSkippedOverLowerPriorityTasks( 106 const internal::WorkQueue* selected_work_queue, 107 std::vector<const Task*>* result) const; 108 109 private: 110 struct OldestTaskOrder { 111 TaskOrder key; 112 // RAW_PTR_EXCLUSION: Performance: visible in sampling profiler stacks. 113 RAW_PTR_EXCLUSION WorkQueue* value = nullptr; 114 115 // Used for a min-heap. 116 bool operator>(const OldestTaskOrder& other) const { 117 return key > other.key; 118 } 119 SetHeapHandleOldestTaskOrder120 void SetHeapHandle(HeapHandle handle) { value->set_heap_handle(handle); } 121 ClearHeapHandleOldestTaskOrder122 void ClearHeapHandle() { value->set_heap_handle(HeapHandle()); } 123 GetHeapHandleOldestTaskOrder124 HeapHandle GetHeapHandle() const { return value->heap_handle(); } 125 }; 126 127 const char* const name_; 128 129 // For each set |work_queue_heaps_| has a queue of WorkQueue ordered by the 130 // oldest task in each WorkQueue. 131 std::vector<IntrusiveHeap<OldestTaskOrder, std::greater<>>> work_queue_heaps_; 132 133 #if DCHECK_IS_ON() MurmurHash3(uint64_t value)134 static inline uint64_t MurmurHash3(uint64_t value) { 135 value ^= value >> 33; 136 value *= uint64_t{0xFF51AFD7ED558CCD}; 137 value ^= value >> 33; 138 value *= uint64_t{0xC4CEB9FE1A85EC53}; 139 value ^= value >> 33; 140 return value; 141 } 142 143 // This is for a debugging feature which lets us randomize task selection. Its 144 // not for production use. 145 // TODO(crbug.com/40234060): Use a seedable PRNG from ::base if one is added. Random()146 uint64_t Random() const { 147 last_rand_ = MurmurHash3(last_rand_); 148 return last_rand_; 149 } 150 151 mutable uint64_t last_rand_; 152 #endif 153 154 const raw_ptr<Observer> observer_; 155 }; 156 157 } // namespace internal 158 } // namespace sequence_manager 159 } // namespace base 160 161 #endif // BASE_TASK_SEQUENCE_MANAGER_WORK_QUEUE_SETS_H_ 162