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
13namespace 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//
25class 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.
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
71  size_t num_running_jobs() const { return num_running_jobs_; }
72  size_t num_queued_jobs() const { return queue_.size(); }
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