Modifying prefetch to account for multi-profile.

chrome/browser/net/predictor.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.
 
 // A Predictor object is instantiated once in the browser process, and manages
 // both preresolution of hostnames, as well as TCP/IP preconnection to expected
 // subresources.
 // Most hostname lists are provided by the renderer processes, and include URLs
 // that *might* be used in the near future by the browsing user.  One goal of
 // this class is to cause the underlying DNS structure to lookup a hostname
@@ skipping 10 matching lines @@
 #pragma once
 
 #include <map>
 #include <queue>
 #include <set>
 #include <string>
 #include <vector>
 
 #include "base/gtest_prod_util.h"
 #include "base/memory/ref_counted.h"
+#include "base/memory/scoped_ptr.h"
 #include "chrome/browser/net/url_info.h"
 #include "chrome/browser/net/referrer.h"
 #include "chrome/common/net/predictor_common.h"
 #include "net/base/host_port_pair.h"
 
 namespace base {
 class ListValue;
 }
 
+namespace base {
+class WaitableEvent;
+}
+
 namespace net {
 class HostResolver;
 }  // namespace net
 
+class PrefService;
+class Profile;
+
 namespace chrome_browser_net {
 
 typedef chrome_common_net::UrlList UrlList;
 typedef chrome_common_net::NameList NameList;
 typedef std::map<GURL, UrlInfo> Results;
 
 // Note that Predictor is not thread safe, and must only be called from
 // the IO thread. Failure to do so will result in a DCHECK at runtime.
 class Predictor : public base::RefCountedThreadSafe<Predictor> {

[willchan no longer on Chromium, 2011/08/10 07:04:08]

Please remove refcounting. Predictor will be destroyed when ProfileIOData gets
destroyed, so we shouldn't refcount it. I suspect you kept it around because you
use NewRunnableMethod(). Don't bother. Use base::Bind() and use
base::Unretained(predictor) to instruct base::Bind() that it doesn't need to be
refcounted. See the example at
http://codesearch.google.com/codesearch#OAMlx_jo-ck/src/base/callback.h&type=....

[rpetterson, 2011/08/12 03:12:36]

Done.

[jar (doing other things), 2011/08/16 01:19:09]

WillChan: I'm trying to be sure I understand the pattern you proposed:
Are you counting on the fact that a posted message to the IO thread will be
dropped when the IO thread goes away... and after the IO thread goes away,
then(?) ProfileIOData will be destroyed... so Predictor will live "long enough"
to service any posts?

On 2011/08/10 07:04:08, willchan wrote:

[willchan no longer on Chromium, 2011/08/16 01:42:57]

Not quite. Shutdown is confusing, but here's how it works. Predictor will get
destroyed when ProfileIOData goes away. The event order is:
* On the UI (main) thread, MessageLoop::Run() returns. We destroy
g_browser_process, which leads to ProfileManager getting destroyed and
destroying all Profile instances.
* Destroying the Profile will cause the member variable
ProfileImplIOData::Handle to get destroyed, which will post a DeleteTask to the
IO thread to delete the ProfileIOData. Predictor gets destroyed when
ProfileIOData does.

Since ProfileIOData strictly gets destroyed *after* the Profile does, it should
be impossible for any tasks to get posted to the Predictor on the IO thread
after it has been destroyed, since those tasks should only be generated by
objects associated with the Profile. If there are still global references to
Predictor, then it's a bug. If an object that is tied to a Profile does not get
destroyed when Profile goes away (translation: it is leaked), it's a bug.

Let me know if that lifetime management makes sense. Chrome shutdown is
confusing so I suspect this won't immediately make sense to folks, but it's the
paradigm we've been switching to and has been working so far.

[jar (doing other things), 2011/08/16 18:45:22]

I'm vaguely convinced that the shutdown order is (currently) as you specified.  

I think depending on such complex global ordering to ensure safety is a bad
pattern. I much prefer the readability of revocable method factories that allow
a very narrow (local) read of the code to assure correctness.  Heaven help us if
someone tries to copy this pattern to another context, without full
understanding of its extensive justifications!

I REALLY like the known global ordering, and the ability to depend on it to
write rational code that should shutdown deterministically.  I like the fact
that you're talking about this ordering.  

However... I don't like depending on global assertions from many distinct sites,
as there is no way to a) assert correctness locally; b) list all the
dependendencies on the ordering (in case we ever wanted to change it!).  With
intricate global ordering dependencies, ordering can't be changed, and is
fragile, with many distant hidden dependencies.

Bottom line: I don't think we should be advocating for this pattern.  I'm sure
there will be performance critical places where we'll have to... but it is IMO a
bad generic pattern.

Am I misunderstanding something??

On 2011/08/16 01:42:57, willchan wrote:

[willchan no longer on Chromium, 2011/08/16 19:02:49]

Agreed!
Note that we aren't *able* to use revocable method factories.
ScopedRunnableMethodFactory uses WeakPtr which depends on NonThreadSafe
implementation details. You'll note in predictor.cc, we use base::Unretained()
in any places where we are posting across threads, since we can't use
ScopedRunnableMethodFactory there.

The previous code used base::RefCountedThreadSafe. The problem with refcounting
is then the destruction order is not well defined. You note that it's great to
have a known global ordering and have deterministic shutdown. I agree with that.
Otherwise then during shutdown, *ALL* objects have to be refcounted and it
usually leads to reference cycles. Since it'll be possible in the future for
profiles to be deleted during normal runtime (due to multiprofile), we can't
afford to refcount, therefore we need to have defined global ordering.

We've tried to limit the scope of having to understand the global ordering to
within the .cc file and it's documented in the header file.

  public:
   // A version number for prefs that are saved. This should be incremented when
   // we change the format so that we discard old data.
   enum { PREDICTOR_REFERRER_VERSION = 2 };
 
   // |max_concurrent| specifies how many concurrent (parallel) prefetches will
   // be performed. Host lookups will be issued through |host_resolver|.
-  Predictor(net::HostResolver* host_resolver,
-            base::TimeDelta max_queue_delay_ms, size_t max_concurrent,
-            bool preconnect_enabled);
+  Predictor();
+
+  ~Predictor();
+
+  // ------------- Start UI thread methods.
+
+  void InitNetworkPredictor(PrefService* user_prefs);
+
+  // The Omnibox has proposed a given url to the user, and if it is a search
+  // URL, then it also indicates that this is preconnectable (i.e., we could
+  // preconnect to the search server).
+  void AnticipateOmniboxUrl(const GURL& url, bool preconnectable);
+
+  // Preconnect a URL and all of its subresource domains.
+  void PreconnectUrlAndSubresources(const GURL& url);
+
+  // Instigate pre-connection to any URLs, or pre-resolution of related host,
+  // that we predict will be needed after this navigation (typically
+  // more-embedded resources on a page).  This method will actually post a task
+  // to do the actual work, so as not to jump ahead of the frame navigation that
+  // instigated this activity.
+  void PredictFrameSubresources(const GURL& url);

[jar (doing other things), 2011/08/16 01:19:09]

I'm surprised this happens on the UI thread.  I'd expect it to happen when an
observer on the IO thread sees a navigation.

Is this instead the entry point used when a user enters an URL in the Omnibox,
and we don't want to wait for the renderer to ack it and get going??

I suspect the posting of the task meant we *could* call it on the UI thread (and
perhaps PreconnectUrlAndSubresources() uses it?)... but I think it is also
called on the IO thread.

[willchan no longer on Chromium, 2011/08/16 01:42:57]

It seems to be a translation of the existing code, which seems to get called on
the UI thread and post to the IO thread. If the translation is incorrect, let's
definitely fix it. I defer to your expertise here Jim.

[rpetterson, 2011/08/16 03:52:12]

This function is called in two places that I know of:
- on the IO thread from ConnectInterceptor::MaybeIntercept(..)
- on the UI thread from Predictor::PreconnectUrlAndSubresources(..) (which is
called from ChromeRenderViewHostObserver::Navigate)

Please let me know if either of these are in error.

+
+  static UrlList GetPredictedUrlListAtStartup(PrefService* user_prefs,
+                                              PrefService* local_state);
+
+  static void set_max_queueing_delay(int max_queueing_delay_ms);
+
+  static void set_max_parallel_resolves(size_t max_parallel_resolves);
+
+  static void RegisterUserPrefs(PrefService* user_prefs);
+
+  // ------------- End UI thread methods.
+
+  // ------------- Start IO thread methods.
 
   // Cancel pending requests and prevent new ones from being made.
   void Shutdown();
 
   // In some circumstances, for privacy reasons, all results should be
   // discarded.  This method gracefully handles that activity.
   // Destroy all our internal state, which shows what names we've looked up, and
   // how long each has taken, etc. etc.  We also destroy records of suggesses
   // (cache hits etc.).
   void DiscardAllResults();
 
   // Add hostname(s) to the queue for processing.
   void ResolveList(const UrlList& urls,
                    UrlInfo::ResolutionMotivation motivation);
+
   void Resolve(const GURL& url,
                UrlInfo::ResolutionMotivation motivation);
 
-  // Instigate pre-connection to any URLs, or pre-resolution of related host,
-  // that we predict will be needed after this navigation (typically
-  // more-embedded resources on a page).  This method will actually post a task
-  // to do the actual work, so as not to jump ahead of the frame navigation that
-  // instigated this activity.
-  void PredictFrameSubresources(const GURL& url);
-
-  // The Omnibox has proposed a given url to the user, and if it is a search
-  // URL, then it also indicates that this is preconnectable (i.e., we could
-  // preconnect to the search server).
-  void AnticipateOmniboxUrl(const GURL& url, bool preconnectable);
-
-  // Preconnect a URL and all of its subresource domains.
-  void PreconnectUrlAndSubresources(const GURL& url);
-
   // Record details of a navigation so that we can preresolve the host name
   // ahead of time the next time the users navigates to the indicated host.
   // Should only be called when urls are distinct, and they should already be
   // canonicalized to not have a path.
   void LearnFromNavigation(const GURL& referring_url, const GURL& target_url);
 
   // Dump HTML table containing list of referrers for about:dns.
   void GetHtmlReferrerLists(std::string* output);
 
   // Dump the list of currently known referrer domains and related prefetchable
@@ skipping 12 matching lines @@
   // so that it can be persisted in a pref.
   void SerializeReferrers(base::ListValue* referral_list);
 
   // Process a ListValue that contains all the data from a previous reference
   // list, as constructed by SerializeReferrers(), and add all the identified
   // values into the current referrer list.
   void DeserializeReferrers(const base::ListValue& referral_list);
 
   void DeserializeReferrersThenDelete(base::ListValue* referral_list);
 
-  // For unit test code only.
-  size_t max_concurrent_dns_lookups() const {
-    return max_concurrent_dns_lookups_;
-  }
+  void DiscardInitialNavigationHistory();
 
-  // Flag setting to use preconnection instead of just DNS pre-fetching.
-  bool preconnect_enabled() const { return preconnect_enabled_; }
+  void FinalizeInitializationOnIOThread(
+      const std::vector<GURL>& urls_to_prefetch,
+      base::ListValue* referral_list,
+      net::HostResolver* host_resolver);
+
+  // During startup, we learn what the first N urls visited are, and then
+  // resolve the associated hosts ASAP during our next startup.
+  void LearnAboutInitialNavigation(const GURL& url);
+
+  // Renderer bundles up list and sends to this browser API via IPC.
+  // TODO(jar): Use UrlList instead to include port and scheme.
+  void DnsPrefetchList(const NameList& hostnames);
+
+  // May be called from either the IO or UI thread and will PostTask
+  // to the IO thread if necessary.
+  void Predictor::DnsPrefetchMotivatedList(
+    const UrlList& urls,
+    UrlInfo::ResolutionMotivation motivation);
+
+  // May be called from either the IO or UI thread and will PostTask
+  // to the IO thread if necessary.
+  void SaveStateForNextStartupAndTrim(PrefService* prefs);
+
+  void SaveDnsPrefetchStateForNextStartupAndTrim(
+      base::ListValue* startup_list,
+      base::ListValue* referral_list,
+      base::WaitableEvent* completion);
+
+  // May be called from either the IO or UI thread and will PostTask
+  // to the IO thread if necessary.
+  void EnablePredictor(bool enable);
+
+  void EnablePredictorOnIOThread(bool enable);
+
+  // ------------- End IO thread methods.
+
+  // The following methods may be called on either the IO or UI threads.
 
   // Put URL in canonical form, including a scheme, host, and port.
   // Returns GURL::EmptyGURL() if the scheme is not http/https or if the url
   // cannot be otherwise canonicalized.
   static GURL CanonicalizeUrl(const GURL& url);
 
+  // Used for testing.
+  void SetHostResolver(net::HostResolver* host_resolver) {
+    host_resolver_ = host_resolver;
+  }
+  // Used for testing.
+  size_t max_concurrent_dns_lookups() const {
+    return max_concurrent_dns_lookups_;
+  }
+
+  // Flag setting to use preconnection instead of just DNS pre-fetching.
+  bool preconnect_enabled() const {
+    return preconnect_enabled_;
+  }
+
+  // Flag setting for whether we are prefetching dns lookups.
+  bool predictor_enabled() const {
+    return predictor_enabled_;
+  }
+
+  // Given that the underlying Chromium resolver defaults to a total maximum of
+  // 8 paralell resolutions, we will avoid any chance of starving navigational
+  // resolutions by limiting the number of paralell speculative resolutions.
+  // This is used in the field trials and testing.
+  // TODO(jar): Move this limitation into the resolver.
+  static const size_t kMaxSpeculativeParallelResolves;
+
+  // To control the congestion avoidance system, we need an estimate of how
+  // many speculative requests may arrive at once.  Since we currently only
+  // keep 8 subresource names for each frame, we'll use that as our basis.
+  // Note that when scanning search results lists, we might actually get 10 at
+  // a time, and wikipedia can often supply (during a page scan) upwards of 50.
+  // In those odd cases, we may discard some of the later speculative requests
+  // mistakenly assuming that the resolutions took too long.
+  static const int kTypicalSpeculativeGroupSize;
+
+// The next constant specifies an amount of queueing delay that is
+// "too large," and indicative of problems with resolutions (perhaps due to
+// an overloaded router, or such).  When we exceed this delay, congestion
+// avoidance will kick in and all speculations in the queue will be discarded.

[jar (doing other things), 2011/08/16 01:19:09]

nit: indent comments.

[rpetterson, 2011/08/16 03:52:12]

Done.

+  static const int kMaxSpeculativeResolveQueueDelayMs;
+
+
  private:
   friend class base::RefCountedThreadSafe<Predictor>;
   FRIEND_TEST_ALL_PREFIXES(PredictorTest, BenefitLookupTest);
   FRIEND_TEST_ALL_PREFIXES(PredictorTest, ShutdownWhenResolutionIsPendingTest);
   FRIEND_TEST_ALL_PREFIXES(PredictorTest, SingleLookupTest);
   FRIEND_TEST_ALL_PREFIXES(PredictorTest, ConcurrentLookupTest);
   FRIEND_TEST_ALL_PREFIXES(PredictorTest, MassiveConcurrentLookupTest);
   FRIEND_TEST_ALL_PREFIXES(PredictorTest, PriorityQueuePushPopTest);
   FRIEND_TEST_ALL_PREFIXES(PredictorTest, PriorityQueueReorderTest);
   FRIEND_TEST_ALL_PREFIXES(PredictorTest, ReferrerSerializationTrimTest);
@@ skipping 21 matching lines @@
    private:
     // The names in the queue that should be serviced (popped) ASAP.
     std::queue<GURL> rush_queue_;
     // The names in the queue that should only be serviced when rush_queue is
     // empty.
     std::queue<GURL> background_queue_;
 
   DISALLOW_COPY_AND_ASSIGN(HostNameQueue);
   };
 
+  // The InitialObserver monitors navigations made by the network stack. This
+  // is only used to identify startup time resolutions (for re-resolution
+  // during our next process startup).
+  // TODO(jar): Consider preconnecting at startup, which may be faster than
+  // waiting for render process to start and request a connection.
+  class InitialObserver {
+   public:
+    // Recording of when we observed each navigation.
+    typedef std::map<GURL, base::TimeTicks> FirstNavigations;
+
+    // Potentially add a new URL to our startup list.
+    void Append(const GURL& url, Predictor* predictor);
+
+    // Get an HTML version of our current planned first_navigations_.
+    void GetFirstResolutionsHtml(std::string* output);
+
+    // Persist the current first_navigations_ for storage in a list.
+    void GetInitialDnsResolutionList(base::ListValue* startup_list);
+
+    // Discards all initial loading history.
+    void DiscardInitialNavigationHistory() { first_navigations_.clear(); }
+
+   private:
+    // List of the first N URL resolutions observed in this run.
+    FirstNavigations first_navigations_;
+
+    // The number of URLs we'll save for pre-resolving at next startup.
+    static const size_t kStartupResolutionCount = 10;
+  };
+
   // A map that is keyed with the host/port that we've learned were the cause
   // of loading additional URLs.  The list of additional targets is held
   // in a Referrer instance, which is a value in this map.
   typedef std::map<GURL, Referrer> Referrers;
 
   // Depending on the expected_subresource_use_, we may either make a TCP/IP
   // preconnection, or merely pre-resolve the hostname via DNS (or even do
   // nothing).  The following are the threasholds for taking those actions.
   static const double kPreconnectWorthyExpectedValue;
   static const double kDNSPreresolutionWorthyExpectedValue;
   // Referred hosts with a subresource_use_rate_ that are less than the
   // following threshold will be discarded when we Trim() the list.
   static const double kDiscardableExpectedValue;
   // During trimming operation to discard hosts for which we don't have likely
   // subresources, we multiply the expected_subresource_use_ value by the
   // following ratio until that value is less than kDiscardableExpectedValue.
   // This number should always be less than 1, an more than 0.
   static const double kReferrerTrimRatio;
 
   // Interval between periodic trimming of our whole referrer list.
   // We only do a major trimming about once an hour, and then only when the user
   // is actively browsing.
   static const base::TimeDelta kDurationBetweenTrimmings;
   // Interval between incremental trimmings (to avoid inducing Jank).
   static const base::TimeDelta kDurationBetweenTrimmingIncrements;
   // Number of referring URLs processed in an incremental trimming.
   static const size_t kUrlsTrimmedPerIncrement;
 
-  ~Predictor();
-
-  // Perform actual resolution or preconnection to subresources now.  This is
-  // an internal worker method that is reached via a post task from
-  // PredictFrameSubresources().
-  void PrepareFrameSubresources(const GURL& url);
-
   // Only for testing. Returns true if hostname has been successfully resolved
   // (name found).
   bool WasFound(const GURL& url) const {
     Results::const_iterator it(results_.find(url));
     return (it != results_.end()) &&
             it->second.was_found();
   }
 
   // Only for testing. Return how long was the resolution
   // or UrlInfo::kNullDuration if it hasn't been resolved yet.
   base::TimeDelta GetResolutionDuration(const GURL& url) {
     if (results_.find(url) == results_.end())
       return UrlInfo::kNullDuration;
     return results_[url].resolve_duration();
   }
 
   // Only for testing;
   size_t peak_pending_lookups() const { return peak_pending_lookups_; }
 
+  // ------------- Start IO thread methods.
+
+  // Perform actual resolution or preconnection to subresources now.  This is
+  // an internal worker method that is reached via a post task from
+  // PredictFrameSubresources().
+  void PrepareFrameSubresources(const GURL& url);
+
   // Access method for use by async lookup request to pass resolution result.
   void OnLookupFinished(LookupRequest* request, const GURL& url, bool found);
 
   // Underlying method for both async and synchronous lookup to update state.
   void LookupFinished(LookupRequest* request,
                       const GURL& url, bool found);
 
   // Queue hostname for resolution.  If queueing was done, return the pointer
   // to the queued instance, otherwise return NULL.
   UrlInfo* AppendToResolutionQueue(const GURL& url,
@@ skipping 25 matching lines @@
   void LoadUrlsForTrimming();
 
   // Posts a task to do additional incremental trimming of referrers_.
   void PostIncrementalTrimTask();
 
   // Calls Trim() on some or all of urls_being_trimmed_.
   // If it does not process all the URLs in that vector, it posts a task to
   // continue with them shortly (i.e., it yeilds and continues).
   void IncrementalTrimReferrers(bool trim_all_now);
 
+  // ------------- End IO thread methods.
+
+  scoped_ptr<InitialObserver> initial_observer_;
+
+  // Status of speculative DNS resolution and speculative TCP/IP connection
+  // feature.
+  bool predictor_enabled_;
+
   // work_queue_ holds a list of names we need to look up.
   HostNameQueue work_queue_;
 
   // results_ contains information for existing/prior prefetches.
   Results results_;
 
   std::set<LookupRequest*> pending_lookups_;
 
   // For testing, to verify that we don't exceed the limit.
   size_t peak_pending_lookups_;
 
   // When true, we don't make new lookup requests.
   bool shutdown_;
 
   // The number of concurrent speculative lookups currently allowed to be sent
   // to the resolver.  Any additional lookups will be queued to avoid exceeding
   // this value.  The queue is a priority queue that will accelerate
   // sub-resource speculation, and retard resolutions suggested by page scans.
   const size_t max_concurrent_dns_lookups_;
 
   // The maximum queueing delay that is acceptable before we enter congestion
   // reduction mode, and discard all queued (but not yet assigned) resolutions.
   const base::TimeDelta max_dns_queue_delay_;
 
   // The host resolver we warm DNS entries for.
-  net::HostResolver* const host_resolver_;
+  net::HostResolver* host_resolver_;
 
   // Are we currently using preconnection, rather than just DNS resolution, for
   // subresources and omni-box search URLs.
   bool preconnect_enabled_;

[jar (doing other things), 2011/08/16 01:19:09]

I don't think we really support this feature any more (pre-resolution, without
pre-connection support)... and perhaps you could kill it and simplify some code.

[willchan no longer on Chromium, 2011/08/16 01:42:57]

I would need to reread the code, but I think this member variable's meaning has
changed, and might just indicate whether or not network prediction is
enabled/disabled (due to user preferences in chrome://settings, or to enterprise
policy settings). Maybe the comment should be updated and the variable renamed
to |enabled_|.

Please verify my statement, I'm not 100% sure.

[rpetterson, 2011/08/16 03:52:12]

Right now the code definitely looks for the preconnect_enabled flag. This can
apparently still be set via the command line so well be taking away that control
as well if we kill it. Let me know.

Will, the variable you're referring to is predictor_enabled_ which is used for
user preferences about doing network prediction at all.

 
   // Most recent suggestion from Omnibox provided via AnticipateOmniboxUrl().
   std::string last_omnibox_host_;
 
   // The time when the last preresolve was done for last_omnibox_host_.
   base::TimeTicks last_omnibox_preresolve_;
 
   // The number of consecutive requests to AnticipateOmniboxUrl() that suggested
   // preconnecting (because it was to a search service).
   int consecutive_omnibox_preconnect_count_;
 
   // The time when the last preconnection was requested to a search service.
   base::TimeTicks last_omnibox_preconnect_;
 
   // For each URL that we might navigate to (that we've "learned about")
   // we have a Referrer list. Each Referrer list has all hostnames we might
   // need to pre-resolve or pre-connect to when there is a navigation to the
   // orginial hostname.
   Referrers referrers_;
 
   // List of URLs in referrers_ currently being trimmed (scaled down to
   // eventually be aged out of use).
   std::vector<GURL> urls_being_trimmed_;
 
   // A time after which we need to do more trimming of referrers.
   base::TimeTicks next_trim_time_;
 
-  ScopedRunnableMethodFactory<Predictor> trim_task_factory_;
+  scoped_ptr<ScopedRunnableMethodFactory<Predictor> > trim_task_factory_;
 
   DISALLOW_COPY_AND_ASSIGN(Predictor);
 };
 
 }  // namespace chrome_browser_net
 
 #endif  // CHROME_BROWSER_NET_PREDICTOR_H_