1 /** 2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 #ifndef PANDA_RUNTIME_COMPILER_QUEUE_COUNTER_PRIORITY_H_ 16 #define PANDA_RUNTIME_COMPILER_QUEUE_COUNTER_PRIORITY_H_ 17 18 #include <algorithm> 19 #include <cstring> 20 21 #include "libpandabase/utils/time.h" 22 #include "runtime/compiler_queue_interface.h" 23 #include "runtime/include/mem/panda_containers.h" 24 #include "runtime/include/method-inl.h" 25 26 namespace ark { 27 28 class CompilationQueueElement { 29 public: CompilationQueueElement(CompilerTask && task)30 explicit CompilationQueueElement(CompilerTask &&task) : context_(std::move(task)) 31 { 32 timestamp_ = time::GetCurrentTimeInMillis(); 33 counter_ = context_.GetMethod()->GetHotnessCounter(); 34 } 35 GetCounter()36 int64_t GetCounter() const 37 { 38 // Do not return method->counter as it can changed during sorting 39 return counter_; 40 } 41 GetContext()42 const CompilerTask &GetContext() const 43 { 44 return context_; 45 } 46 GetContext()47 CompilerTask &GetContext() 48 { 49 return context_; 50 } 51 GetTimestamp()52 uint64_t GetTimestamp() const 53 { 54 return timestamp_; 55 } 56 UpdateCounter(int64_t newCounter)57 void UpdateCounter(int64_t newCounter) 58 { 59 counter_ = newCounter; 60 } 61 62 private: 63 uint64_t timestamp_; 64 int64_t counter_; 65 CompilerTask context_; 66 }; 67 68 /** 69 * The counter priority queue sorts all tasks (methods) by its hotness counters. 70 * It extracts the most hot method for compilation (the lesser counter). 71 * It also has a limit of tasks for compilation. If the task is too old, it is expired and removed from the queue. 72 * Note, in case of skip the method due to length limit, its hotness counter is reset. 73 * Max length and life time is configured. 74 * This queue is thread unsafe (should be used under lock). 75 */ 76 class CompilerPriorityCounterQueue : public CompilerQueueInterface { 77 public: CompilerPriorityCounterQueue(mem::InternalAllocatorPtr allocator,uint64_t maxLength,uint64_t taskLifeSpan)78 explicit CompilerPriorityCounterQueue(mem::InternalAllocatorPtr allocator, uint64_t maxLength, 79 uint64_t taskLifeSpan) 80 : allocator_(allocator), queue_(allocator->Adapter()) 81 { 82 maxLength_ = maxLength; 83 taskLifeSpan_ = taskLifeSpan; 84 queueName_ = ""; 85 SetQueueName("priority counter compilation queue"); 86 } 87 GetTask()88 CompilerTask GetTask() override 89 { 90 UpdateQueue(); 91 if (queue_.empty()) { 92 LOG(DEBUG, COMPILATION_QUEUE) << "Empty " << queueName_ << ", return nothing"; 93 return CompilerTask(); 94 } 95 sort(queue_.begin(), queue_.end(), comparator_); 96 auto element = queue_.back(); 97 auto task = std::move(element->GetContext()); 98 queue_.pop_back(); 99 allocator_->Delete(element); 100 LOG(DEBUG, COMPILATION_QUEUE) << "Extract a task from a " << queueName_ << ": " << GetTaskDescription(task); 101 return task; 102 } 103 104 // NOLINTNEXTLINE(google-default-arguments) 105 void AddTask(CompilerTask &&ctx, [[maybe_unused]] size_t priority = 0) override 106 { 107 UpdateQueue(); 108 if (queue_.size() >= maxLength_) { 109 // Not sure if it is possible to exceed the size more than one 110 // Reset the counter of the rejected method; 111 ctx.GetMethod()->ResetHotnessCounter(); 112 ctx.GetMethod()->AtomicSetCompilationStatus(Method::WAITING, 113 ctx.IsOsr() ? Method::COMPILED : Method::NOT_COMPILED); 114 // Maybe, replace the other method in queue? 115 LOG(DEBUG, COMPILATION_QUEUE) << "Skip adding the task " << GetTaskDescription(ctx) 116 << " due to limit of tasks (" << maxLength_ << ") in a " << queueName_; 117 return; 118 } 119 LOG(DEBUG, COMPILATION_QUEUE) << "Add an element to a " << queueName_ << ": " << GetTaskDescription(ctx); 120 auto element = allocator_->New<CompilationQueueElement>(std::move(ctx)); 121 // Sorting will be in Get function 122 queue_.push_back(element); 123 } 124 Finalize()125 void Finalize() override 126 { 127 for (auto e : queue_) { 128 allocator_->Delete(e); 129 } 130 queue_.clear(); 131 LOG(DEBUG, COMPILATION_QUEUE) << "Clear a " << queueName_; 132 } 133 134 protected: GetQueueSize()135 size_t GetQueueSize() override 136 { 137 return queue_.size(); 138 } 139 UpdateCounterAndCheck(CompilationQueueElement * element)140 virtual bool UpdateCounterAndCheck(CompilationQueueElement *element) 141 { 142 // The only way to update counter 143 element->UpdateCounter(element->GetContext().GetMethod()->GetHotnessCounter()); 144 uint64_t curStamp = time::GetCurrentTimeInMillis(); 145 return (curStamp - element->GetTimestamp() >= taskLifeSpan_); 146 } 147 SetQueueName(char const * name)148 void SetQueueName(char const *name) 149 { 150 queueName_ = name; 151 } 152 153 private: 154 class Comparator { 155 public: operator()156 bool operator()(CompilationQueueElement *a, CompilationQueueElement *b) const 157 { 158 if (a->GetCounter() == b->GetCounter()) { 159 // Use method name just in case? 160 if (a->GetTimestamp() == b->GetTimestamp()) { 161 // The only way is a name 162 // Again, as we pull from the end return reversed compare 163 return strcmp(reinterpret_cast<const char *>(a->GetContext().GetMethod()->GetName().data), 164 reinterpret_cast<const char *>(b->GetContext().GetMethod()->GetName().data)) > 0; 165 } 166 // Low time is high priority (pull from the end) 167 return a->GetTimestamp() > b->GetTimestamp(); 168 } 169 // First, handle a method with higher hotness (less counter) 170 return (a->GetCounter() > b->GetCounter()); 171 } 172 }; 173 UpdateQueue()174 void UpdateQueue() 175 { 176 // Remove expired tasks 177 for (auto it = queue_.begin(); it != queue_.end();) { 178 auto element = *it; 179 // We should update the counter inside as the queue choose the semantic of the counter by itself 180 if (UpdateCounterAndCheck(element)) { 181 LOG(DEBUG, COMPILATION_QUEUE) << "Remove an expired element from a " << queueName_ << ": " 182 << GetTaskDescription(element->GetContext()); 183 auto ctx = std::move(element->GetContext()); 184 ctx.GetMethod()->AtomicSetCompilationStatus(Method::WAITING, 185 ctx.IsOsr() ? Method::COMPILED : Method::NOT_COMPILED); 186 allocator_->Delete(element); 187 it = queue_.erase(it); 188 } else { 189 ++it; 190 } 191 } 192 } 193 mem::InternalAllocatorPtr allocator_; 194 PandaVector<CompilationQueueElement *> queue_; 195 Comparator comparator_; 196 uint64_t maxLength_; 197 // In milliseconds 198 uint64_t taskLifeSpan_; 199 const char *queueName_; 200 }; 201 202 } // namespace ark 203 204 #endif // PANDA_RUNTIME_COMPILER_QUEUE_COUNTER_PRIORITY_H_ 205