1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 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 NET_BASE_PRIORITIZED_DISPATCHER_H_ 6 #define NET_BASE_PRIORITIZED_DISPATCHER_H_ 7 8 #include <vector> 9 10 #include "net/base/net_export.h" 11 #include "net/base/priority_queue.h" 12 13 namespace net { 14 15 // A priority-based dispatcher of jobs. Dispatch order is by priority (highest 16 // first) and then FIFO. The dispatcher enforces limits on the number of running 17 // jobs. It never revokes a job once started. The job must call OnJobFinished 18 // once it finishes in order to dispatch further jobs. 19 // 20 // This class is NOT thread-safe which is enforced by the underlying 21 // non-thread-safe PriorityQueue. All operations are O(p) time for p priority 22 // levels. It is safe to execute any method, including destructor, from within 23 // Job::Start. 24 // 25 class NET_EXPORT_PRIVATE PrioritizedDispatcher { 26 public: 27 class Job; 28 typedef PriorityQueue<Job*>::Priority Priority; 29 30 // Describes the limits for the number of jobs started by the dispatcher. 31 // For example, |total_jobs| = 30 and |reserved_slots| = { 0, 5, 10, 5 } allow 32 // for at most 30 running jobs in total. Jobs at priority 0 can't use slots 33 // reserved for higher priorities, so they are limited to 10. 34 // If there are already 24 jobs running, then only 6 more jobs can start. No 35 // jobs at priority 1 or below can start. After one more job starts, no jobs 36 // at priority 2 or below can start, since the remaining 5 slots are reserved 37 // for priority 3 or above. 38 struct NET_EXPORT_PRIVATE Limits { 39 Limits(Priority num_priorities, size_t total_jobs); 40 ~Limits(); 41 42 // Total allowed running jobs. 43 size_t total_jobs; 44 // Number of slots reserved for each priority and higher. 45 // Sum of |reserved_slots| must be no greater than |total_jobs|. 46 std::vector<size_t> reserved_slots; 47 }; 48 49 // An interface to the job dispatched by PrioritizedDispatcher. The dispatcher 50 // does not own the Job but expects it to live as long as the Job is queued. 51 // Use Cancel to remove Job from queue before it is dispatched. The Job can be 52 // deleted after it is dispatched or canceled, or the dispatcher is destroyed. 53 class Job { 54 public: 55 // Note: PrioritizedDispatcher will never delete a Job. ~Job()56 virtual ~Job() {} 57 // Called when the dispatcher starts the job. Once the job finishes, it must 58 // call OnJobFinished. 59 virtual void Start() = 0; 60 }; 61 62 // A handle to the enqueued job. The handle becomes invalid when the job is 63 // canceled, updated, or started. 64 typedef PriorityQueue<Job*>::Pointer Handle; 65 66 // Creates a dispatcher enforcing |limits| on number of running jobs. 67 explicit PrioritizedDispatcher(const Limits& limits); 68 69 ~PrioritizedDispatcher(); 70 num_running_jobs()71 size_t num_running_jobs() const { return num_running_jobs_; } num_queued_jobs()72 size_t num_queued_jobs() const { return queue_.size(); } num_priorities()73 size_t num_priorities() const { return max_running_jobs_.size(); } 74 75 // Adds |job| with |priority| to the dispatcher. If limits permit, |job| is 76 // started immediately. Returns handle to the job or null-handle if the job is 77 // started. The dispatcher does not own |job|, but |job| must live as long as 78 // it is queued in the dispatcher. 79 Handle Add(Job* job, Priority priority); 80 81 // Just like Add, except that it adds Job at the font of queue of jobs with 82 // priorities of |priority|. 83 Handle AddAtHead(Job* job, Priority priority); 84 85 // Removes the job with |handle| from the queue. Invalidates |handle|. 86 // Note: a Handle is valid iff the job is in the queue, i.e. has not Started. 87 void Cancel(const Handle& handle); 88 89 // Cancels and returns the oldest-lowest-priority Job invalidating any 90 // handles to it. Returns NULL if the queue is empty. 91 Job* EvictOldestLowest(); 92 93 // Moves the queued job with |handle| to the end of all values with priority 94 // |priority| and returns the updated handle, or null-handle if it starts the 95 // job. Invalidates |handle|. No-op if priority did not change. 96 Handle ChangePriority(const Handle& handle, Priority priority); 97 98 // Notifies the dispatcher that a running job has finished. Could start a job. 99 void OnJobFinished(); 100 101 // Retrieves the Limits that |this| is currently using. This may not exactly 102 // match the Limits this was created with. In particular, the number of slots 103 // reserved for the lowest priority will always be 0, even if it was non-zero 104 // in the Limits passed to the constructor or to SetLimits. 105 Limits GetLimits() const; 106 107 // Updates |max_running_jobs_| to match |limits|. Starts jobs if new limit 108 // allows. Does not stop jobs if the new limits are lower than the old ones. 109 void SetLimits(const Limits& limits); 110 111 // Set the limits to zero for all priorities, allowing no new jobs to start. 112 void SetLimitsToZero(); 113 114 private: 115 // Attempts to dispatch the job with |handle| at priority |priority| (might be 116 // different than |handle.priority()|. Returns true if successful. If so 117 // the |handle| becomes invalid. 118 bool MaybeDispatchJob(const Handle& handle, Priority priority); 119 120 // Attempts to dispatch the next highest priority job in the queue. Returns 121 // true if successful, and all handles to that job become invalid. 122 bool MaybeDispatchNextJob(); 123 124 // Queue for jobs that need to wait for a spare slot. 125 PriorityQueue<Job*> queue_; 126 // Maximum total number of running jobs allowed after a job at a particular 127 // priority is started. If a greater or equal number of jobs are running, then 128 // another job cannot be started. 129 std::vector<size_t> max_running_jobs_; 130 // Total number of running jobs. 131 size_t num_running_jobs_; 132 133 DISALLOW_COPY_AND_ASSIGN(PrioritizedDispatcher); 134 }; 135 136 } // namespace net 137 138 #endif // NET_BASE_PRIORITIZED_DISPATCHER_H_ 139