Line data Source code
1 : /* 2 : * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved. 3 : * Copyright Contributors to the OpenSDN project 4 : */ 5 : 6 : // queue_task.h 7 : // 8 : // Task based queue processor implementing thread safe enqueue and dequeue 9 : // using concurrent queues. If queue is empty, enqueue creates a dequeue task 10 : // that drains the queue. The dequeue task runs a maximum of kMaxIterations 11 : // before yielding. 12 : // 13 : #ifndef __QUEUE_TASK_H__ 14 : #define __QUEUE_TASK_H__ 15 : 16 : #include <iostream> 17 : #include <sstream> 18 : #include <algorithm> 19 : #include <vector> 20 : #include <set> 21 : #include <mutex> 22 : #include <atomic> 23 : 24 : #include <tbb/concurrent_queue.h> 25 : #include <tbb/spin_rw_mutex.h> 26 : 27 : #include <base/task.h> 28 : #include <base/time_util.h> 29 : #include <base/watermark.h> 30 : 31 : template <typename QueueEntryT, typename QueueT> 32 : class QueueTaskRunner : public Task { 33 : public: 34 323503 : QueueTaskRunner(QueueT *queue) 35 323503 : : Task(queue->GetTaskId(), queue->GetTaskInstance()), queue_(queue) { 36 323502 : } 37 : 38 864887 : bool Run() { 39 : // Check if this run needs to be deferred 40 864887 : if (!queue_->OnEntry()) { 41 1166 : return false; 42 : } 43 863766 : return RunQueue(); 44 : // No more client callbacks after updating 45 : // queue running_ and current_runner_ in RunQueue to 46 : // avoid client callbacks running concurrently 47 : } 48 : 49 0 : virtual std::string Description() const { 50 0 : return queue_->Description(); 51 : } 52 : 53 : private: 54 863743 : bool RunQueue() { 55 : // Check if we need to abort 56 863743 : if (queue_->RunnerAbort()) { 57 19 : return queue_->RunnerDone(); 58 : } 59 : 60 863756 : uint64_t start = 0; 61 863756 : if (queue_->measure_busy_time_) 62 0 : start = ClockMonotonicUsec(); 63 : 64 863735 : QueueEntryT entry = QueueEntryT(); 65 863736 : size_t count = 0; 66 3331834 : while (queue_->Dequeue(&entry)) { 67 : // Process the entry 68 3014929 : if (!queue_->GetCallback()(entry)) { 69 502763 : break; 70 : } 71 2512218 : if (++count == queue_->max_iterations_) { 72 44120 : if (start) 73 0 : queue_->add_busy_time(ClockMonotonicUsec() - start); 74 44120 : return queue_->RunnerDone(); 75 : } 76 : } 77 : 78 819639 : if (start) 79 0 : queue_->add_busy_time(ClockMonotonicUsec() - start); 80 : 81 : // Running is done if queue_ is empty 82 : // While notification is being run, its possible that more entries 83 : // are added into queue_ 84 819639 : return queue_->RunnerDone(); 85 118425 : } 86 : 87 : QueueT *queue_; 88 : }; 89 : 90 : template <typename QueueEntryT> 91 : struct WorkQueueDelete { 92 : template <typename QueueT> 93 20521 : void operator()(QueueT &, bool) {} 94 : }; 95 : 96 : template <typename QueueEntryT> 97 : struct WorkQueueDelete<QueueEntryT *> { 98 : template <typename QueueT> 99 39793 : void operator()(QueueT &q, bool delete_entry) { 100 : QueueEntryT *entry; 101 39793 : while (q.try_pop(entry)) { 102 0 : if (delete_entry) { 103 0 : delete entry; 104 : } 105 : } 106 39793 : } 107 : }; 108 : 109 : template <typename QueueEntryT> 110 : class WorkQueue { 111 : public: 112 : static const int kMaxSize = 1024; 113 : static const int kMaxIterations = 32; 114 : typedef tbb::concurrent_queue<QueueEntryT> Queue; 115 : typedef boost::function<bool (QueueEntryT)> Callback; 116 : typedef boost::function<bool (void)> StartRunnerFunc; 117 : typedef boost::function<void (bool)> TaskExitCallback; 118 : typedef boost::function<bool ()> TaskEntryCallback; 119 : 120 58459 : WorkQueue(int taskId, int taskInstance, Callback callback, 121 : size_t size = kMaxSize, 122 : size_t max_iterations = kMaxIterations) : 123 58459 : running_(false), 124 58459 : taskId_(taskId), 125 58459 : taskInstance_(taskInstance), 126 58459 : name_(""), 127 58459 : callback_(callback), 128 58459 : on_entry_cb_(0), 129 58459 : on_exit_cb_(0), 130 58459 : start_runner_(0), 131 58459 : current_runner_(NULL), 132 58459 : on_entry_defer_count_(0), 133 58459 : deleted_(false), 134 58459 : enqueues_(0), 135 58459 : dequeues_(0), 136 58459 : drops_(0), 137 58459 : max_iterations_(max_iterations), 138 58459 : size_(size), 139 58459 : bounded_(false), 140 58459 : shutdown_scheduled_(false), 141 58459 : delete_entries_on_shutdown_(true), 142 58459 : task_starts_(0), 143 58459 : max_queue_len_(0), 144 58459 : busy_time_(0), 145 116918 : measure_busy_time_(false) { 146 58459 : count_ = 0; 147 58459 : disabled_ = false; 148 58459 : } 149 : 150 : // Concurrency - should be called from a task whose policy 151 : // assures that the dequeue task - QueueTaskRunner is not running 152 : // concurrently 153 57970 : void Shutdown(bool delete_entries = true) { 154 57970 : std::scoped_lock lock(mutex_); 155 57970 : ShutdownLocked(delete_entries); 156 57970 : } 157 : 158 : // Concurrency - can be called from any context 159 : // Schedule shutdown of the WorkQueue, shutdown may happen asynchronously 160 : // or in the caller's context also 161 5 : void ScheduleShutdown(bool delete_entries = true) { 162 5 : std::scoped_lock lock(mutex_); 163 5 : if (shutdown_scheduled_) { 164 0 : return; 165 : } 166 5 : shutdown_scheduled_ = true; 167 5 : delete_entries_on_shutdown_ = delete_entries; 168 : 169 : // Cancel QueueTaskRunner 170 5 : if (running_) { 171 4 : assert(current_runner_); 172 4 : TaskScheduler *scheduler = TaskScheduler::GetInstance(); 173 : TaskScheduler::CancelReturnCode cancel_code = 174 4 : scheduler->Cancel(current_runner_); 175 4 : if (cancel_code == TaskScheduler::CANCELLED) { 176 1 : running_ = false; 177 1 : current_runner_ = NULL; 178 1 : ShutdownLocked(delete_entries); 179 : } else { 180 3 : assert(cancel_code == TaskScheduler::QUEUED); 181 : } 182 : } else { 183 1 : ShutdownLocked(delete_entries); 184 : } 185 5 : } 186 : 187 58431 : ~WorkQueue() { 188 58431 : std::scoped_lock lock(mutex_); 189 : // Shutdown() needs to be called before deleting 190 : //assert(!running_ && deleted_); 191 58431 : } 192 : 193 174 : void SetStartRunnerFunc(StartRunnerFunc start_runner_fn) { 194 174 : start_runner_ = start_runner_fn; 195 174 : } 196 : 197 21 : void SetSize(size_t size) { 198 21 : size_ = size; 199 21 : } 200 : 201 27 : void SetBounded(bool bounded) { 202 27 : bounded_ = bounded; 203 27 : } 204 : 205 : bool GetBounded() const { 206 : return bounded_; 207 : } 208 : 209 1 : void SetHighWaterMark(const WaterMarkInfos &high_water) { 210 1 : std::scoped_lock lock(water_mutex_); 211 1 : watermarks_.SetHighWaterMark(high_water); 212 1 : } 213 : 214 299 : void SetHighWaterMark(const WaterMarkInfo& hwm_info) { 215 299 : std::scoped_lock lock(water_mutex_); 216 299 : watermarks_.SetHighWaterMark(hwm_info); 217 299 : } 218 : 219 60434 : void ResetHighWaterMark() { 220 60434 : std::scoped_lock lock(water_mutex_); 221 60434 : watermarks_.ResetHighWaterMark(); 222 60434 : } 223 : 224 1 : WaterMarkInfos GetHighWaterMark() const { 225 1 : std::scoped_lock lock(water_mutex_); 226 2 : return watermarks_.GetHighWaterMark(); 227 1 : } 228 : 229 4 : void SetLowWaterMark(const WaterMarkInfos &low_water) { 230 4 : std::scoped_lock lock(water_mutex_); 231 4 : watermarks_.SetLowWaterMark(low_water); 232 4 : } 233 : 234 284 : void SetLowWaterMark(const WaterMarkInfo& lwm_info) { 235 284 : std::scoped_lock lock(water_mutex_); 236 284 : watermarks_.SetLowWaterMark(lwm_info); 237 284 : } 238 : 239 60433 : void ResetLowWaterMark() { 240 60433 : std::scoped_lock lock(water_mutex_); 241 60433 : watermarks_.ResetLowWaterMark(); 242 60433 : } 243 : 244 1 : WaterMarkInfos GetLowWaterMark() const { 245 1 : std::scoped_lock lock(water_mutex_); 246 2 : return watermarks_.GetLowWaterMark(); 247 1 : } 248 : 249 2976866 : bool Enqueue(QueueEntryT entry) { 250 2976866 : if (bounded_) { 251 2200 : if (AreWaterMarksSet()) { 252 0 : return EnqueueBoundedLocked(entry); 253 : } else { 254 2200 : return EnqueueBounded(entry); 255 : } 256 : } else { 257 2974666 : if (AreWaterMarksSet()) { 258 100577 : return EnqueueInternalLocked(entry); 259 : } else { 260 2874083 : return EnqueueInternal(entry); 261 : } 262 : } 263 : } 264 : 265 : // Returns true if pop is successful. 266 3331775 : bool Dequeue(QueueEntryT *entry) { 267 3331775 : if (AreWaterMarksSet()) { 268 100867 : return DequeueInternalLocked(entry); 269 : } else { 270 3230896 : return DequeueInternal(entry); 271 : } 272 : } 273 : 274 323502 : int GetTaskId() const { 275 323502 : return taskId_; 276 : } 277 : 278 323503 : int GetTaskInstance() const { 279 323503 : return taskInstance_; 280 : } 281 : 282 3032489 : void MayBeStartRunner() { 283 3032489 : std::scoped_lock lock(mutex_); 284 3032493 : if (running_ || queue_.empty() || deleted_ || RunnerAbortLocked()) { 285 2708973 : return; 286 : } 287 323500 : task_starts_++; 288 323500 : running_ = true; 289 323500 : assert(current_runner_ == NULL); 290 323502 : current_runner_ = 291 323500 : new QueueTaskRunner<QueueEntryT, WorkQueue<QueueEntryT> >(this); 292 323502 : TaskScheduler *scheduler = TaskScheduler::GetInstance(); 293 323501 : scheduler->Enqueue(current_runner_); 294 3032504 : } 295 : 296 3014925 : Callback GetCallback() const { 297 3014925 : return callback_; 298 : } 299 : 300 26 : void SetEntryCallback(TaskEntryCallback on_entry) { 301 26 : on_entry_cb_ = on_entry; 302 26 : } 303 : 304 341 : void SetExitCallback(TaskExitCallback on_exit) { 305 341 : on_exit_cb_ = on_exit; 306 341 : } 307 : 308 17525 : void set_name(const std::string &name) { 309 17525 : name_ = name; 310 17525 : } 311 40 : std::string Description() const { 312 40 : if (name_.empty() == false) 313 40 : return name_; 314 : 315 0 : std::ostringstream str; 316 0 : str << "Function " << callback_; 317 0 : return str.str(); 318 0 : } 319 : 320 34223 : void set_disable(bool disabled) { 321 34223 : if (disabled_ != disabled) { 322 34220 : disabled_ = disabled; 323 34220 : if (!disabled_) { 324 17110 : MayBeStartRunner(); 325 : } 326 : } 327 34223 : } 328 : 329 : bool IsDisabled() const { 330 : return disabled_; 331 : } 332 : 333 : size_t on_entry_defer_count() const { 334 : return on_entry_defer_count_; 335 : } 336 : 337 864915 : bool OnEntry() { 338 864915 : bool run = (on_entry_cb_.empty() || on_entry_cb_()); 339 : 340 : // Track number of times this queue run is deferred 341 864935 : if (!run) { 342 1166 : on_entry_defer_count_++; 343 : } 344 864935 : return run; 345 : } 346 : 347 863781 : void OnExit(bool done) { 348 863781 : if (!on_exit_cb_.empty()) { 349 11662 : on_exit_cb_(done); 350 : } 351 863779 : } 352 : 353 18285 : bool IsQueueEmpty() const { 354 18285 : return queue_.empty(); 355 : } 356 : 357 365 : size_t Length() const { 358 365 : return count_; 359 : } 360 : 361 65 : size_t NumEnqueues() const { 362 65 : return enqueues_; 363 : } 364 : 365 66 : size_t NumDequeues() const { 366 66 : return dequeues_; 367 : } 368 : 369 : size_t NumDrops() const { 370 : return drops_; 371 : } 372 : 373 6 : bool deleted() const { 374 6 : return deleted_; 375 : } 376 : 377 45 : uint32_t task_starts() const { return task_starts_; } 378 61 : size_t max_queue_len() const { return max_queue_len_; } 379 : bool measure_busy_time() const { return measure_busy_time_; } 380 73 : void set_measure_busy_time(bool val) const { measure_busy_time_ = val; } 381 45 : uint64_t busy_time() const { return busy_time_; } 382 0 : void add_busy_time(uint64_t t) { busy_time_ += t; } 383 0 : void ClearStats() const { 384 0 : max_queue_len_ = 0; 385 0 : enqueues_ = 0; 386 0 : dequeues_ = 0; 387 0 : busy_time_ = 0; 388 0 : task_starts_ = 0; 389 0 : } 390 : private: 391 : // Returns true if pop is successful. 392 3331747 : bool DequeueInternal(QueueEntryT *entry) { 393 3331747 : bool success = queue_.try_pop(*entry); 394 3331842 : if (success) { 395 3014965 : dequeues_++; 396 3014965 : size_t ncount(AtomicDecrementQueueCount(entry)); 397 3014990 : ProcessLowWaterMarks(ncount); 398 : } 399 3331818 : return success; 400 : } 401 : 402 100867 : bool DequeueInternalLocked(QueueEntryT *entry) { 403 100867 : std::scoped_lock lock(water_mutex_); 404 201734 : return DequeueInternal(entry); 405 100867 : } 406 : 407 6347006 : bool AreWaterMarksSet() const { 408 6347006 : return watermarks_.AreWaterMarksSet(); 409 : } 410 : 411 60433 : void ShutdownLocked(bool delete_entries) { 412 : // Cancel QueueTaskRunner from the scheduler 413 60433 : assert(!deleted_); 414 60433 : if (running_) { 415 292 : running_ = false; 416 292 : assert(current_runner_); 417 292 : TaskScheduler *scheduler = TaskScheduler::GetInstance(); 418 : TaskScheduler::CancelReturnCode cancel_code = 419 292 : scheduler->Cancel(current_runner_); 420 292 : assert(cancel_code == TaskScheduler::CANCELLED); 421 292 : current_runner_ = NULL; 422 : } 423 60433 : ResetHighWaterMark(); 424 60433 : ResetLowWaterMark(); 425 : WorkQueueDelete<QueueEntryT> deleter; 426 60433 : deleter(queue_, delete_entries); 427 60433 : queue_.clear(); 428 60433 : count_ = 0; 429 60433 : deleted_ = true; 430 60433 : } 431 : 432 2976328 : size_t AtomicIncrementQueueCount(QueueEntryT *entry) { 433 5952656 : return count_.fetch_add(1) + 1; 434 : } 435 : 436 3014424 : size_t AtomicDecrementQueueCount(QueueEntryT *entry) { 437 6028848 : return count_.fetch_sub(1) - 1; 438 : } 439 : 440 2976881 : void ProcessHighWaterMarks(size_t count) { 441 2976881 : watermarks_.ProcessHighWaterMarks(count); 442 2976873 : } 443 : 444 3014988 : void ProcessLowWaterMarks(size_t count) { 445 3014988 : watermarks_.ProcessLowWaterMarks(count); 446 3014935 : } 447 : 448 2974661 : bool EnqueueInternal(QueueEntryT entry) { 449 2974661 : enqueues_++; 450 2974661 : size_t ncount(AtomicIncrementQueueCount(&entry)); 451 2974688 : if (ncount > max_queue_len_) 452 588511 : max_queue_len_ = ncount; 453 2974688 : ProcessHighWaterMarks(ncount); 454 2974679 : queue_.push(entry); 455 2974676 : MayBeStartRunner(); 456 2974685 : return ncount < size_; 457 : } 458 : 459 100577 : bool EnqueueInternalLocked(QueueEntryT entry) { 460 100577 : std::scoped_lock lock(water_mutex_); 461 201154 : return EnqueueInternal(entry); 462 100577 : } 463 : 464 2200 : bool EnqueueBounded(QueueEntryT entry) { 465 2200 : size_t ncount(AtomicIncrementQueueCount(&entry)); 466 2200 : if (ncount > max_queue_len_) 467 119 : max_queue_len_ = ncount; 468 2200 : if (ncount < size_) { 469 2195 : enqueues_++; 470 2195 : ProcessHighWaterMarks(ncount); 471 2195 : queue_.push(entry); 472 2195 : MayBeStartRunner(); 473 2195 : return true; 474 : } 475 5 : AtomicDecrementQueueCount(&entry); 476 5 : drops_++; 477 5 : max_queue_len_ = count_; 478 5 : return false; 479 : } 480 : 481 0 : bool EnqueueBoundedLocked(QueueEntryT entry) { 482 0 : std::scoped_lock lock(water_mutex_); 483 0 : return EnqueueBounded(entry); 484 0 : } 485 : 486 1751932 : bool RunnerAbortLocked() { 487 3479839 : return (disabled_ || shutdown_scheduled_ || 488 3479817 : (!start_runner_.empty() && !start_runner_())); 489 : } 490 : 491 863739 : bool RunnerAbort() { 492 863739 : std::scoped_lock lock(mutex_); 493 1727564 : return RunnerAbortLocked(); 494 863779 : } 495 : 496 863806 : bool RunnerDone() { 497 863806 : std::scoped_lock lock(mutex_); 498 863804 : bool done = false; 499 863804 : if (queue_.empty() || RunnerAbortLocked()) { 500 323208 : done = true; 501 323208 : OnExit(done); 502 323207 : current_runner_ = NULL; 503 323207 : running_ = false; 504 323207 : if (shutdown_scheduled_) { 505 3 : ShutdownLocked(delete_entries_on_shutdown_); 506 : } 507 : } else { 508 540574 : OnExit(done); 509 540573 : running_ = true; 510 : } 511 863799 : return done; 512 863780 : } 513 : 514 : Queue queue_; 515 : std::atomic<size_t> count_; 516 : std::mutex mutex_; 517 : bool running_; 518 : int taskId_; 519 : int taskInstance_; 520 : std::string name_; 521 : Callback callback_; 522 : TaskEntryCallback on_entry_cb_; 523 : TaskExitCallback on_exit_cb_; 524 : StartRunnerFunc start_runner_; 525 : QueueTaskRunner<QueueEntryT, WorkQueue<QueueEntryT> > *current_runner_; 526 : size_t on_entry_defer_count_; 527 : std::atomic<bool> disabled_; 528 : bool deleted_; 529 : mutable size_t enqueues_; 530 : mutable size_t dequeues_; 531 : size_t drops_; 532 : size_t max_iterations_; 533 : size_t size_; 534 : bool bounded_; 535 : bool shutdown_scheduled_; 536 : bool delete_entries_on_shutdown_; 537 : WaterMarkTuple watermarks_; 538 : mutable std::mutex water_mutex_; 539 : mutable uint32_t task_starts_; 540 : mutable size_t max_queue_len_; 541 : mutable uint64_t busy_time_; 542 : mutable bool measure_busy_time_; 543 : 544 : friend class QueueTaskTest; 545 : friend class QueueTaskShutdownTest; 546 : friend class QueueTaskWaterMarkTest; 547 : friend class QueueTaskRunner<QueueEntryT, WorkQueue<QueueEntryT> >; 548 : 549 : DISALLOW_COPY_AND_ASSIGN(WorkQueue); 550 : }; 551 : 552 : #endif /* __QUEUE_TASK_H__ */