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