Use a priority queue to assure that subresources are resolved asap

Also implement DNS congestion avoidance in the pre-fetch system.

BUG=13276

r=mbelshe
Review URL: http://codereview.chromium.org/118149

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@17605 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 256 insertions, 24 deletions

diff --git a/chrome/browser/net/dns_host_info.cc b/chrome/browser/net/dns_host_info.cc
index d40acd7..dbfde3b 100644
--- a/chrome/browser/net/dns_host_info.cc
+++ b/chrome/browser/net/dns_host_info.cc
@@ -77,6 +77,7 @@ void DnsHostInfo::set_cache_expiration(TimeDelta time) {
 
 void DnsHostInfo::SetQueuedState(ResolutionMotivation motivation) {
   DCHECK(PENDING == state_ || FOUND == state_ || NO_SUCH_NAME == state_);
+  old_prequeue_state_ = state_;
   state_ = QUEUED;
   queue_duration_ = resolve_duration_ = kNullDuration;
   SetMotivation(motivation);
@@ -92,6 +93,24 @@ void DnsHostInfo::SetAssignedState() {
   UMA_HISTOGRAM_TIMES("DNS.PrefetchQueue", queue_duration_);
 }
 
+void DnsHostInfo::RemoveFromQueue() {
+  DCHECK(ASSIGNED == state_);
+  state_ = old_prequeue_state_;
+  DLogResultsStats("DNS Prefetch reset to prequeue");
+  static const TimeDelta kBoundary = TimeDelta::FromSeconds(2);
+  if (queue_duration_ > kBoundary) {
+    UMA_HISTOGRAM_MEDIUM_TIMES("DNS.QueueRecycledDeltaOver2",
+                               queue_duration_ - kBoundary);
+    return;
+  }
+  // Make a custom linear histogram for the region from 0 to boundary.
+  const size_t kBucketCount = 52;
+  static LinearHistogram histogram("DNS.QueueRecycledUnder2", TimeDelta(),
+                                   kBoundary, kBucketCount);
+  histogram.SetFlags(kUmaTargetedHistogramFlag);
+  histogram.AddTime(queue_duration_);
+}
+
 void DnsHostInfo::SetPendingDeleteState() {
   DCHECK(ASSIGNED == state_  || ASSIGNED_BUT_MARKED == state_);
   state_ = ASSIGNED_BUT_MARKED;
@@ -143,7 +162,7 @@ void DnsHostInfo::SetFinishedState(bool was_resolved) {
 
 void DnsHostInfo::SetHostname(const std::string& hostname) {
   if (hostname != hostname_) {
-    DCHECK(hostname_.size() == 0);  // Not yet initialized.
+    DCHECK_EQ(hostname_.size(), 0u);  // Not yet initialized.
     hostname_ = hostname;
   }
 }
@@ -171,7 +190,7 @@ bool DnsHostInfo::IsStillCached() const {
 DnsBenefit DnsHostInfo::AccruePrefetchBenefits(DnsHostInfo* navigation_info) {
   DCHECK(FINISHED == navigation_info->state_ ||
          FINISHED_UNRESOLVED == navigation_info->state_);
-  DCHECK(0 == navigation_info->hostname_.compare(hostname_.data()));
+  DCHECK_EQ(navigation_info->hostname_, hostname_.data());
 
   if ((0 == benefits_remaining_.InMilliseconds()) ||
       (FOUND != state_ && NO_SUCH_NAME != state_)) {
diff --git a/chrome/browser/net/dns_host_info.h b/chrome/browser/net/dns_host_info.h
index 5ffca75..34160d5 100644
--- a/chrome/browser/net/dns_host_info.h
+++ b/chrome/browser/net/dns_host_info.h
@@ -52,11 +52,11 @@ class DnsHostInfo {
   enum DnsProcessingState {
       // When processed by our prefetching system, the states are:
       PENDING,       // Constructor has completed.
-      QUEUED,        // In prefetch queue but not yet being resolved.
-      ASSIGNED,      // Currently being processed.
+      QUEUED,        // In name queue but not yet being resolved.
+      ASSIGNED,      // Being resolved (or being reset to earlier state)
       ASSIGNED_BUT_MARKED,  // Needs to be deleted as soon as it's resolved.
-      FOUND,         // DNS prefetch search completed.
-      NO_SUCH_NAME,  // DNS prefetch search completed.
+      FOUND,         // DNS resolution completed.
+      NO_SUCH_NAME,  // DNS resolution completed.
       // When processed by the network stack during navigation, the states are:
       STARTED,               // Resolution has begun for a navigation.
       FINISHED,              // Resolution has completed for a navigation.
@@ -74,6 +74,7 @@ class DnsHostInfo {
   // initializing of the DnsMaster's map (of info for Hostnames).
   DnsHostInfo()
       : state_(PENDING),
+        old_prequeue_state_(state_),
         resolve_duration_(kNullDuration),
         queue_duration_(kNullDuration),
         benefits_remaining_(),
@@ -95,6 +96,7 @@ class DnsHostInfo {
   // The prefetching lifecycle.
   void SetQueuedState(ResolutionMotivation motivation);
   void SetAssignedState();
+  void RemoveFromQueue();
   void SetPendingDeleteState();
   void SetFoundState();
   void SetNoSuchNameState();
@@ -157,7 +159,13 @@ class DnsHostInfo {
   // The next declaration is non-const to facilitate testing.
   static base::TimeDelta kCacheExpirationDuration;
 
+  // The current state of this instance.
   DnsProcessingState state_;
+
+  // Record the state prior to going to a queued state, in case we have to back
+  // out of the queue.
+  DnsProcessingState old_prequeue_state_;
+
   std::string hostname_;  // Hostname for this info.
 
   // When was last state changed (usually lookup completed).
diff --git a/chrome/browser/net/dns_host_info_unittest.cc b/chrome/browser/net/dns_host_info_unittest.cc
index 2c50236..87f64bc 100644
--- a/chrome/browser/net/dns_host_info_unittest.cc
+++ b/chrome/browser/net/dns_host_info_unittest.cc
@@ -82,6 +82,47 @@ TEST(DnsHostInfoTest, StateChangeTest) {
   EXPECT_TRUE(info.NeedsDnsUpdate(hostname1)) << "expiration time not honored";
 }
 
+// When a system gets "congested" relative to DNS, it means it is doing too many
+// DNS resolutions, and bogging down the system.  When we detect such a
+// situation, we divert the sequence of states a DnsHostInfo instance moves
+// through.  Rather than proceeding from QUEUED (waiting in a name queue for a
+// worker thread that can resolve the name) to ASSIGNED (where a worker thread
+// actively resolves the name), we enter the ASSIGNED state (without actually
+// getting sent to a resolver thread) and reset our state to what it was before
+// the corresponding name was put in the work_queue_.  This test drives through
+// the state transitions used in such congestion handling.
+TEST(DnsHostInfoTest, CongestionResetStateTest) {
+  DnsHostInfo info;
+  std::string hostname1("domain1.com");
+
+  info.SetHostname(hostname1);
+  info.SetQueuedState(DnsHostInfo::UNIT_TEST_MOTIVATED);
+  info.SetAssignedState();
+  EXPECT_TRUE(info.is_assigned());
+
+  info.RemoveFromQueue();  // Do the reset.
+  EXPECT_FALSE(info.is_assigned());
+
+  // Since this was a new info instance, and it never got resolved, we land back
+  // in a PENDING state rather than FOUND or NO_SUCH_NAME.
+  EXPECT_FALSE(info.was_found());
+  EXPECT_FALSE(info.was_nonexistant());
+
+  // Make sure we're completely re-usable, by going throug a normal flow.
+  info.SetQueuedState(DnsHostInfo::UNIT_TEST_MOTIVATED);
+  info.SetAssignedState();
+  info.SetFoundState();
+  EXPECT_TRUE(info.was_found());
+
+  // Use the congestion flow, and check that we end up in the found state.
+  info.SetQueuedState(DnsHostInfo::UNIT_TEST_MOTIVATED);
+  info.SetAssignedState();
+  info.RemoveFromQueue();  // Do the reset.
+  EXPECT_FALSE(info.is_assigned());
+  EXPECT_TRUE(info.was_found());  // Back to what it was before being queued.
+}
+
+
 // TODO(jar): Add death test for illegal state changes, and also for setting
 // hostname when already set.
 
diff --git a/chrome/browser/net/dns_master.cc b/chrome/browser/net/dns_master.cc
index bbb450a..74fb9e5 100644
--- a/chrome/browser/net/dns_master.cc
+++ b/chrome/browser/net/dns_master.cc
@@ -360,23 +360,24 @@ DnsHostInfo* DnsMaster::PreLockedResolve(
   }
 
   info->SetQueuedState(motivation);
-  name_buffer_.push(hostname);
-
+  work_queue_.Push(hostname, motivation);
   PreLockedScheduleLookups();
-
   return info;
 }
 
 void DnsMaster::PreLockedScheduleLookups() {
-  while (!name_buffer_.empty() &&
+  while (!work_queue_.IsEmpty() &&
          pending_lookups_.size() < max_concurrent_lookups_) {
-    const std::string hostname(name_buffer_.front());
-    name_buffer_.pop();
-
+    const std::string hostname(work_queue_.Pop());
     DnsHostInfo* info = &results_[hostname];
     DCHECK(info->HasHostname(hostname));
     info->SetAssignedState();
 
+    if (PreLockedCongestionControlPerformed(info)) {
+      DCHECK(work_queue_.IsEmpty());
+      return;
+    }
+
     LookupRequest* request = new LookupRequest(this, hostname);
     if (request->Start()) {
       pending_lookups_.insert(request);
@@ -389,14 +390,33 @@ void DnsMaster::PreLockedScheduleLookups() {
   }
 }
 
+bool DnsMaster::PreLockedCongestionControlPerformed(DnsHostInfo* info) {
+  // Note: queue_duration is ONLY valid after we go to assigned state.
+  // TODO(jar): Tune selection of arbitrary 1 second constant.  Add plumbing so
+  // that this can be set as part of an A/B experiment.
+  if (info->queue_duration() < base::TimeDelta::FromSeconds(1))
+    return false;
+  // We need to discard all entries in our queue, as we're keeping them waiting
+  // too long.  By doing this, we'll have a chance to quickly service urgent
+  // resolutions, and not have a bogged down system.
+  while (true) {
+    info->RemoveFromQueue();
+    if (work_queue_.IsEmpty())
+      break;
+    info = &results_[work_queue_.Pop()];
+    info->SetAssignedState();
+  }
+  return true;
+}
+
 void DnsMaster::OnLookupFinished(LookupRequest* request,
                                  const std::string& hostname, bool found) {
   AutoLock auto_lock(lock_);  // For map access (changing info values).
   DnsHostInfo* info = &results_[hostname];
   DCHECK(info->HasHostname(hostname));
-  if (info->is_marked_to_delete())
+  if (info->is_marked_to_delete()) {
     results_.erase(hostname);
-  else {
+  } else {
     if (found)
       info->SetFoundState();
     else
@@ -418,10 +438,9 @@ void DnsMaster::DiscardAllResults() {
 
 
   // Try to delete anything in our work queue.
-  while (!name_buffer_.empty()) {
+  while (!work_queue_.IsEmpty()) {
     // Emulate processing cycle as though host was not found.
-    std::string hostname = name_buffer_.front();
-    name_buffer_.pop();
+    std::string hostname = work_queue_.Pop();
     DnsHostInfo* info = &results_[hostname];
     DCHECK(info->HasHostname(hostname));
     info->SetAssignedState();
@@ -497,4 +516,44 @@ void DnsMaster::DeserializeReferrers(const ListValue& referral_list) {
   }
 }
 
+
+//------------------------------------------------------------------------------
+
+DnsMaster::HostNameQueue::HostNameQueue() {
+}
+
+DnsMaster::HostNameQueue::~HostNameQueue() {
+}
+
+void DnsMaster::HostNameQueue::Push(const std::string& hostname,
+    DnsHostInfo::ResolutionMotivation motivation) {
+  switch (motivation) {
+    case DnsHostInfo::STATIC_REFERAL_MOTIVATED:
+    case DnsHostInfo::LEARNED_REFERAL_MOTIVATED:
+    case DnsHostInfo::MOUSE_OVER_MOTIVATED:
+      rush_queue_.push(hostname);
+      break;
+
+    default:
+      background_queue_.push(hostname);
+      break;
+  }
+}
+
+bool DnsMaster::HostNameQueue::IsEmpty() const {
+  return rush_queue_.empty() && background_queue_.empty();
+}
+
+std::string DnsMaster::HostNameQueue::Pop() {
+  DCHECK(!IsEmpty());
+  if (!rush_queue_.empty()) {
+    std::string hostname(rush_queue_.front());
+    rush_queue_.pop();
+    return hostname;
+  }
+  std::string hostname(background_queue_.front());
+  background_queue_.pop();
+  return hostname;
+}
+
 }  // namespace chrome_browser_net
diff --git a/chrome/browser/net/dns_master.h b/chrome/browser/net/dns_master.h
index 5dfb968..a78e061 100644
--- a/chrome/browser/net/dns_master.h
+++ b/chrome/browser/net/dns_master.h
@@ -33,7 +33,7 @@ typedef std::map<std::string, DnsHostInfo> Results;
 class DnsMaster {
  public:
   // Specify how many concurrent (paralell) prefetches will be performed.
-  DnsMaster(size_t max_concurrent);
+  explicit DnsMaster(size_t max_concurrent);
   ~DnsMaster();
 
   // Cancel pending requests and prevent new ones from being made.
@@ -93,10 +93,39 @@ class DnsMaster {
   FRIEND_TEST(DnsMasterTest, SingleLookupTest);
   FRIEND_TEST(DnsMasterTest, ConcurrentLookupTest);
   FRIEND_TEST(DnsMasterTest, MassiveConcurrentLookupTest);
+  FRIEND_TEST(DnsMasterTest, PriorityQueuePushPopTest);
+  FRIEND_TEST(DnsMasterTest, PriorityQueueReorderTest);
   friend class WaitForResolutionHelper;  // For testing.
 
   class LookupRequest;
 
+  // A simple priority queue for handling host names.
+  // Some names that are queued up have |motivation| that requires very rapid
+  // handling.  For example, a sub-resource name lookup MUST be done before the
+  // actual sub-resource is fetched.  In contrast, a name that was speculatively
+  // noted in a page has to be resolved before the user "gets around to"
+  // clicking on a link.  By tagging (with a motivation) each push we make into
+  // this FIFO queue, the queue can re-order the more important names to service
+  // them sooner (relative to some low priority background resolutions).
+  class HostNameQueue {
+   public:
+    HostNameQueue();
+    ~HostNameQueue();
+    void Push(const std::string& hostname,
+              DnsHostInfo::ResolutionMotivation motivation);
+    bool IsEmpty() const;
+    std::string Pop();
+
+  private:
+    // The names in the queue that should be serviced (popped) ASAP.
+    std::queue<std::string> rush_queue_;
+    // The names in the queue that should only be serviced when rush_queue is
+    // empty.
+    std::queue<std::string> background_queue_;
+
+  DISALLOW_COPY_AND_ASSIGN(HostNameQueue);
+  };
+
   // A map that is keyed with the hostnames that we've learned were the cause
   // of loading additional hostnames.  The list of additional hostnames in held
   // in a Referrer instance, which is found in this type.
@@ -133,16 +162,29 @@ class DnsMaster {
   DnsHostInfo* PreLockedResolve(const std::string& hostname,
                                 DnsHostInfo::ResolutionMotivation motivation);
 
-  // Take lookup requests from name_buffer_ and tell HostResolver
-  // to look them up asynchronously, provided we don't exceed
-  // concurrent resolution limit.
+  // Check to see if too much queuing delay has been noted for the given info,
+  // which indicates that there is "congestion" or growing delay in handling the
+  // resolution of names.  Rather than letting this congestion potentially grow
+  // without bounds, we abandon our queued efforts at pre-resolutions in such a
+  // case.
+  // To do this, we will recycle |info|, as well as all queued items, back to
+  // the state they had before they were queued up.  We can't do anything about
+  // the resolutions we've already sent off for processing on another thread, so
+  // we just let them complete.  On a slow system, subject to congestion, this
+  // will greatly reduce the number of resolutions done, but it will assure that
+  // any resolutions that are done, are in a timely and hence potentially
+  // helpful manner.
+  bool PreLockedCongestionControlPerformed(DnsHostInfo* info);
+
+  // Take lookup requests from work_queue_ and tell HostResolver to look them up
+  // asynchronously, provided we don't exceed concurrent resolution limit.
   void PreLockedScheduleLookups();
 
   // Synchronize access to variables listed below.
   Lock lock_;
 
-  // name_buffer_ holds a list of names we need to look up.
-  std::queue<std::string> name_buffer_;
+  // work_queue_ holds a list of names we need to look up.
+  HostNameQueue work_queue_;
 
   // results_ contains information for existing/prior prefetches.
   Results results_;
diff --git a/chrome/browser/net/dns_master_unittest.cc b/chrome/browser/net/dns_master_unittest.cc
index 2285229..b6805f5 100644
--- a/chrome/browser/net/dns_master_unittest.cc
+++ b/chrome/browser/net/dns_master_unittest.cc
@@ -541,4 +541,67 @@ TEST_F(DnsMasterTest, ReferrerSerializationTrimTest) {
   master.Shutdown();
 }
 
+
+TEST_F(DnsMasterTest, PriorityQueuePushPopTest) {
+  DnsMaster::HostNameQueue queue;
+
+  // First check high priority queue FIFO functionality.
+  EXPECT_TRUE(queue.IsEmpty());
+  queue.Push("a", DnsHostInfo::LEARNED_REFERAL_MOTIVATED);
+  EXPECT_FALSE(queue.IsEmpty());
+  queue.Push("b", DnsHostInfo::MOUSE_OVER_MOTIVATED);
+  EXPECT_FALSE(queue.IsEmpty());
+  EXPECT_EQ(queue.Pop(), "a");
+  EXPECT_FALSE(queue.IsEmpty());
+  EXPECT_EQ(queue.Pop(), "b");
+  EXPECT_TRUE(queue.IsEmpty());
+
+  // Then check low priority queue FIFO functionality.
+  queue.IsEmpty();
+  queue.Push("a", DnsHostInfo::PAGE_SCAN_MOTIVATED);
+  EXPECT_FALSE(queue.IsEmpty());
+  queue.Push("b", DnsHostInfo::OMNIBOX_MOTIVATED);
+  EXPECT_FALSE(queue.IsEmpty());
+  EXPECT_EQ(queue.Pop(), "a");
+  EXPECT_FALSE(queue.IsEmpty());
+  EXPECT_EQ(queue.Pop(), "b");
+  EXPECT_TRUE(queue.IsEmpty());
+}
+
+TEST_F(DnsMasterTest, PriorityQueueReorderTest) {
+  DnsMaster::HostNameQueue queue;
+
+  // Push all the low priority items.
+  EXPECT_TRUE(queue.IsEmpty());
+  queue.Push("scan", DnsHostInfo::PAGE_SCAN_MOTIVATED);
+  queue.Push("unit", DnsHostInfo::UNIT_TEST_MOTIVATED);
+  queue.Push("lmax", DnsHostInfo::LINKED_MAX_MOTIVATED);
+  queue.Push("omni", DnsHostInfo::OMNIBOX_MOTIVATED);
+  queue.Push("startup", DnsHostInfo::STARTUP_LIST_MOTIVATED);
+  queue.Push("omni", DnsHostInfo::OMNIBOX_MOTIVATED);
+
+  // Push all the high prority items
+  queue.Push("learned", DnsHostInfo::LEARNED_REFERAL_MOTIVATED);
+  queue.Push("refer", DnsHostInfo::STATIC_REFERAL_MOTIVATED);
+  queue.Push("mouse", DnsHostInfo::MOUSE_OVER_MOTIVATED);
+
+  // Check that high priority stuff comes out first, and in FIFO order.
+  EXPECT_EQ(queue.Pop(), "learned");
+  EXPECT_EQ(queue.Pop(), "refer");
+  EXPECT_EQ(queue.Pop(), "mouse");
+
+  // ...and then low priority strings.
+  EXPECT_EQ(queue.Pop(), "scan");
+  EXPECT_EQ(queue.Pop(), "unit");
+  EXPECT_EQ(queue.Pop(), "lmax");
+  EXPECT_EQ(queue.Pop(), "omni");
+  EXPECT_EQ(queue.Pop(), "startup");
+  EXPECT_EQ(queue.Pop(), "omni");
+
+  EXPECT_TRUE(queue.IsEmpty());
+}
+
+
+
+
 }  // namespace chrome_browser_net