Refactoring of job dispatch in HostResolverImpl in preparation for DnsClient.

net/base/prioritized_dispatcher.h

+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef NET_BASE_PRIORITY_DISPATCH_H_
+#define NET_BASE_PRIORITY_DISPATCH_H_
+#pragma once
+
+#include "net/base/net_export.h"
+#include "net/base/priority_queue.h"
+#include "net/base/request_priority.h"
+
+namespace net {
+
+// A priority-based dispatcher of jobs. The dispatcher enforces limits on
+// the number of running jobs. It never revokes a job once started. The job
+// must call OnJobFinished once it finishes in order to dispatch further jobs.
+// All operations are O(1) time. The class is fully reentrant: it is safe to
+// execute any method (incl. destructor) from within Job callbacks.
+class NET_EXPORT_PRIVATE PrioritizedDispatcher {
+ public:
+  // Describes the limits for the number of jobs started by the dispatcher.
+  // For example, |total_jobs| = 30 and |reserved_slots| = { 5, 10, 5, 0, 0 }
+  // allow for at most 30 running jobs in total. If there are already 24 jobs
+  // running, then there can be 6 more jobs started of which at most 1 can be
+  // MEDIUM but the rest has to be HIGHEST.
+  struct NET_EXPORT_PRIVATE Limits {
+    // Total allowed running jobs.
+    size_t total_jobs;
+    // Number of slots reserved for each priority and higher.
+    // Sum of |reserved_slots| must be no greater than |total_jobs|.
+    size_t reserved_slots[NUM_PRIORITIES];

[cbentzel, 2012/01/03 19:39:09]

Like PriorityQueue, it feels like this should be decoupled from NUM_PRIORITIES.
Perhaps have a vector<size_t> or something similar. 

+  };
+
+  // An interface to the job dispatched by PrioritizedDispatcher. The dispatcher
+  // does not own the Job but expects it to live as long as the Job is queued.
+  // Use Cancel to remove Job from queue before it is dispatched (with either
+  // Start or OnEvicted). The Job can be deleted after it is dispatched,
+  // canceled or the dispatcher is destroyed.
+  class Job {
+   public:
+    // Note: PriorityDispatch will never delete a Job.
+    virtual ~Job() {}
+    // Called when the dispatcher starts the job. Must call OnJobFinished when
+    // done.
+    virtual void Start() = 0;
+    // Called when the job is evicted due to |max_queued|.
+    virtual void OnEvicted() = 0;
+  };
+
+  // A handle to the enqueued job. The handle becomes invalid when the job is
+  // canceled, updated, evicted, or started.
+  typedef PriorityQueue<Job*>::Pointer Handle;
+
+  // Creates a dispatcher enforcing |limits| on number of running jobs and
+  // |max_queued| on queued jobs.
+  PrioritizedDispatcher(const Limits& limits, size_t max_queued);
+
+  ~PrioritizedDispatcher();
+
+  size_t num_running_jobs() const { return num_running_jobs_; }
+  size_t num_queued_jobs() const { return queue_.size(); }
+
+  // Configures |max_queued|. May be called only when queue is empty.

[cbentzel, 2012/01/03 19:39:09]

Why isn't this part of Limits? 

[szym, 2012/01/03 20:48:52]

It makes sense, but note my concern about enforcing queue size at the dispatcher
level.

+  void SetMaxQueued(size_t max_queued);
+
+  // Returns true iff a new job with |priority| would itself be evicted on Add.
+  bool WouldEvict(RequestPriority priority) const;

[cbentzel, 2012/01/03 19:39:09]

From the one caller I saw, it looks like this method could be removed and Add
could be called with a check for is_null - assuming that a different approach is
taking for Handle if the job is immediately started.

[szym, 2012/01/03 20:48:52]

We must not call OnEvicted on the Job that is being Added.

Two reasons I prefer WouldEvict:
- No need to even create the Job if it would be evicted.
- No need for Job to provide its own mechanism to distinguish between eviction
and start on Add.
(Although that makes the code checking if the evicted Job is being added dead.)

One reason I would prefer just Add:
- Add needs to redo what WouldEvict already does.

+
+  // Adds |job| with |priority| to the dispatcher. If limits permit, |job| is
+  // started immediately. Returns handle to the job or null-handle if the job is
+  // started or evicted.
+  Handle Add(Job* job, RequestPriority priority);
+
+  // Removes the job with |handle| from the queue. Invalidates |handle|.
+  void Cancel(const Handle& handle);

[cbentzel, 2012/01/03 19:39:09]

I think this needs to be a bit more defensive about handling invalidated
Handle's.

For example, lets say Add is called and the Job is unable to start right away so
it's queued up and a non-null Handle is returned.

At some later point, the Job is started because another completes. While this
happens, Cancel is called.

Now arguably this shouldn't happen. Start is called on the Job so Cancel should
no longer be called on the Handle. 

But that adds a lot of tight coupling between the Job itself and the owner of
the job lifetime. It would be nicer if Cancel could handle invalid handles as a
no-op. 

[szym, 2012/01/03 20:48:52]

Agreed, although I don't really have a better contract than: "please invalidate
your handle after either OnStart or OnEvict is called, and after you called
Update or Cancel."

The issue with PriorityQueue using std::list is that AFAIK there's no (portable)
way to determine that an iterator is invalid. If we switched to LinkedList then
the Handle could essentially be a pointer to a LinkNode, and so it would remain
usable until the Job is destroyed. It could then store a pointer to the
PriorityQueue to check if it's an element of it or not.

The downside of using LinkedList is that then we need to add stuff to the
pure-virtual Job interface making it impure. That said, I'm leaning towards that
solution.

+
+  // Moves the queued job with |handle| to the end of all values with priority
+  // |priority| and returns the updated handle, or null-handle if it starts the
+  // job. Invalidates |handle|. No-op if priority did not change.
+  Handle Update(const Handle& handle, RequestPriority priority);
+
+  // Notifies the dispatcher that a running job has finished. Could start a job.
+  void OnJobFinished();
+
+ private:
+  // Attempts to dispatch the job with |handle| at priority |priority| (might be
+  // different than |handle.priority()|. Returns true if successful. If so
+  // the |handle| becomes invalid.
+  bool DispatchJob(const Handle& handle, RequestPriority priority);
+
+  // Queue for jobs that need to wait for a spare slot.
+  PriorityQueue<Job*> queue_;
+  // Maximum total number of running jobs allowed after a job at a particular
+  // priority is started. If a greater or equal number of jobs are running, then
+  // another job cannot be started.
+  size_t max_running_jobs_[NUM_PRIORITIES];
+  // Total number of running jobs.
+  size_t num_running_jobs_;
+  // Maximum number of jobs in |queue_|.
+  size_t max_queued_jobs_;
+
+  DISALLOW_COPY_AND_ASSIGN(PrioritizedDispatcher);
+};
+
+}  // namespace net
+
+#endif  // NET_BASE_PRIORITY_DISPATCH_H_
+