Fix purify freeze. Revert "Use a priority queue to assure that subresources are resolved asap"

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

Review URL: http://codereview.chromium.org/118239

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

6 files changed, 24 insertions, 256 deletions

diff --git a/chrome/browser/net/dns_host_info.cc b/chrome/browser/net/dns_host_info.cc
index dbfde3b..d40acd7 100644
--- a/chrome/browser/net/dns_host_info.cc
+++ b/chrome/browser/net/dns_host_info.cc
@@ -77,7 +77,6 @@ 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);
@@ -93,24 +92,6 @@ 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;
@@ -162,7 +143,7 @@ void DnsHostInfo::SetFinishedState(bool was_resolved) {
 
 void DnsHostInfo::SetHostname(const std::string& hostname) {
   if (hostname != hostname_) {
-    DCHECK_EQ(hostname_.size(), 0u);  // Not yet initialized.
+    DCHECK(hostname_.size() == 0);  // Not yet initialized.
     hostname_ = hostname;
   }
 }
@@ -190,7 +171,7 @@ bool DnsHostInfo::IsStillCached() const {
 DnsBenefit DnsHostInfo::AccruePrefetchBenefits(DnsHostInfo* navigation_info) {
   DCHECK(FINISHED == navigation_info->state_ ||
          FINISHED_UNRESOLVED == navigation_info->state_);
-  DCHECK_EQ(navigation_info->hostname_, hostname_.data());
+  DCHECK(0 == navigation_info->hostname_.compare(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 34160d5..5ffca75 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 name queue but not yet being resolved.
-      ASSIGNED,      // Being resolved (or being reset to earlier state)
+      QUEUED,        // In prefetch queue but not yet being resolved.
+      ASSIGNED,      // Currently being processed.
       ASSIGNED_BUT_MARKED,  // Needs to be deleted as soon as it's resolved.
-      FOUND,         // DNS resolution completed.
-      NO_SUCH_NAME,  // DNS resolution completed.
+      FOUND,         // DNS prefetch search completed.
+      NO_SUCH_NAME,  // DNS prefetch search 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,7 +74,6 @@ 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_(),
@@ -96,7 +95,6 @@ class DnsHostInfo {
   // The prefetching lifecycle.
   void SetQueuedState(ResolutionMotivation motivation);
   void SetAssignedState();
-  void RemoveFromQueue();
   void SetPendingDeleteState();
   void SetFoundState();
   void SetNoSuchNameState();
@@ -159,13 +157,7 @@ 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 87f64bc..2c50236 100644
--- a/chrome/browser/net/dns_host_info_unittest.cc
+++ b/chrome/browser/net/dns_host_info_unittest.cc
@@ -82,47 +82,6 @@ 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 74fb9e5..bbb450a 100644
--- a/chrome/browser/net/dns_master.cc
+++ b/chrome/browser/net/dns_master.cc
@@ -360,24 +360,23 @@ DnsHostInfo* DnsMaster::PreLockedResolve(
   }
 
   info->SetQueuedState(motivation);
-  work_queue_.Push(hostname, motivation);
+  name_buffer_.push(hostname);
+
   PreLockedScheduleLookups();
+
   return info;
 }
 
 void DnsMaster::PreLockedScheduleLookups() {
-  while (!work_queue_.IsEmpty() &&
+  while (!name_buffer_.empty() &&
          pending_lookups_.size() < max_concurrent_lookups_) {
-    const std::string hostname(work_queue_.Pop());
+    const std::string hostname(name_buffer_.front());
+    name_buffer_.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);
@@ -390,33 +389,14 @@ 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
@@ -438,9 +418,10 @@ void DnsMaster::DiscardAllResults() {
 
 
   // Try to delete anything in our work queue.
-  while (!work_queue_.IsEmpty()) {
+  while (!name_buffer_.empty()) {
     // Emulate processing cycle as though host was not found.
-    std::string hostname = work_queue_.Pop();
+    std::string hostname = name_buffer_.front();
+    name_buffer_.pop();
     DnsHostInfo* info = &results_[hostname];
     DCHECK(info->HasHostname(hostname));
     info->SetAssignedState();
@@ -516,44 +497,4 @@ 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 a78e061..5dfb968 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.
-  explicit DnsMaster(size_t max_concurrent);
+  DnsMaster(size_t max_concurrent);
   ~DnsMaster();
 
   // Cancel pending requests and prevent new ones from being made.
@@ -93,39 +93,10 @@ 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.
@@ -162,29 +133,16 @@ class DnsMaster {
   DnsHostInfo* PreLockedResolve(const std::string& hostname,
                                 DnsHostInfo::ResolutionMotivation motivation);
 
-  // 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.
+  // Take lookup requests from name_buffer_ 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_;
 
-  // work_queue_ holds a list of names we need to look up.
-  HostNameQueue work_queue_;
+  // name_buffer_ holds a list of names we need to look up.
+  std::queue<std::string> name_buffer_;
 
   // 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 b6805f5..2285229 100644
--- a/chrome/browser/net/dns_master_unittest.cc
+++ b/chrome/browser/net/dns_master_unittest.cc
@@ -541,67 +541,4 @@ 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