chrome/browser/net/predictor_unittest.cc

   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 #include <time.h>
   6
   7 #include <algorithm>
   8 #include <sstream>
   9 #include <string>
  10
  11 #include "base/memory/scoped_ptr.h"
  12 #include "base/message_loop/message_loop.h"
  13 #include "base/strings/string_number_conversions.h"
  14 #include "base/timer/timer.h"
  15 #include "base/values.h"
  16 #include "chrome/browser/net/predictor.h"
  17 #include "chrome/browser/net/spdyproxy/proxy_advisor.h"
  18 #include "chrome/browser/net/url_info.h"
  19 #include "chrome/common/net/predictor_common.h"
  20 #include "content/public/test/test_browser_thread.h"
  21 #include "net/base/address_list.h"
  22 #include "net/base/winsock_init.h"
  23 #include "net/dns/mock_host_resolver.h"
  24 #include "testing/gmock/include/gmock/gmock.h"
  25 #include "testing/gtest/include/gtest/gtest.h"
  26
  27 using base::Time;
  28 using base::TimeDelta;
  29 using content::BrowserThread;
  30
  31 namespace chrome_browser_net {
  32
  33 class WaitForResolutionHelper;
  34
  35 typedef base::RepeatingTimer<WaitForResolutionHelper> HelperTimer;
  36
  37 class WaitForResolutionHelper {
  38  public:
  39   WaitForResolutionHelper(Predictor* predictor, const UrlList& hosts,
  40                           HelperTimer* timer, int checks_until_quit)
  41       : predictor_(predictor),
  42         hosts_(hosts),
  43         timer_(timer),
  44         checks_until_quit_(checks_until_quit) {
  45   }
  46
  47   void CheckIfResolutionsDone() {
  48     if (--checks_until_quit_ > 0) {
  49       for (UrlList::const_iterator i = hosts_.begin(); i != hosts_.end(); ++i)
  50         if (predictor_->GetResolutionDuration(*i) ==
  51             UrlInfo::NullDuration())
  52           return;  // We don't have resolution for that host.
  53     }
  54
  55     // When all hostnames have been resolved, or we've hit the limit,
  56     // exit the loop.
  57     timer_->Stop();
  58     base::MessageLoop::current()->Quit();
  59     delete timer_;
  60     delete this;
  61   }
  62
  63  private:
  64   Predictor* predictor_;
  65   const UrlList hosts_;
  66   HelperTimer* timer_;
  67   int checks_until_quit_;
  68 };
  69
  70 class PredictorTest : public testing::Test {
  71  public:
  72   PredictorTest()
  73       : ui_thread_(BrowserThread::UI, &loop_),
  74         io_thread_(BrowserThread::IO, &loop_),
  75         host_resolver_(new net::MockCachingHostResolver()) {
  76   }
  77
  78  protected:
  79   virtual void SetUp() {
  80 #if defined(OS_WIN)
  81     net::EnsureWinsockInit();
  82 #endif
  83     Predictor::set_max_parallel_resolves(
  84         Predictor::kMaxSpeculativeParallelResolves);
  85     Predictor::set_max_queueing_delay(
  86         Predictor::kMaxSpeculativeResolveQueueDelayMs);
  87     // Since we are using a caching HostResolver, the following latencies will
  88     // only be incurred by the first request, after which the result will be
  89     // cached internally by |host_resolver_|.
  90     net::RuleBasedHostResolverProc* rules = host_resolver_->rules();
  91     rules->AddRuleWithLatency("www.google.com", "127.0.0.1", 50);
  92     rules->AddRuleWithLatency("gmail.google.com.com", "127.0.0.1", 70);
  93     rules->AddRuleWithLatency("mail.google.com", "127.0.0.1", 44);
  94     rules->AddRuleWithLatency("gmail.com", "127.0.0.1", 63);
  95   }
  96
  97   void WaitForResolution(Predictor* predictor, const UrlList& hosts) {
  98     HelperTimer* timer = new HelperTimer();
  99     // By default allow the loop to run for a minute -- 600 iterations.
 100     timer->Start(FROM_HERE, TimeDelta::FromMilliseconds(100),
 101                  new WaitForResolutionHelper(predictor, hosts, timer, 600),
 102                  &WaitForResolutionHelper::CheckIfResolutionsDone);
 103     base::MessageLoop::current()->Run();
 104   }
 105
 106   void WaitForResolutionWithLimit(
 107       Predictor* predictor, const UrlList& hosts, int limit) {
 108     HelperTimer* timer = new HelperTimer();
 109     timer->Start(FROM_HERE, TimeDelta::FromMilliseconds(100),
 110                  new WaitForResolutionHelper(predictor, hosts, timer, limit),
 111                  &WaitForResolutionHelper::CheckIfResolutionsDone);
 112     base::MessageLoop::current()->Run();
 113   }
 114
 115  private:
 116   // IMPORTANT: do not move this below |host_resolver_|; the host resolver
 117   // must not outlive the message loop, otherwise bad things can happen
 118   // (like posting to a deleted message loop).
 119   base::MessageLoopForUI loop_;
 120   content::TestBrowserThread ui_thread_;
 121   content::TestBrowserThread io_thread_;
 122
 123  protected:
 124   scoped_ptr<net::MockCachingHostResolver> host_resolver_;
 125 };
 126
 127 //------------------------------------------------------------------------------
 128
 129 TEST_F(PredictorTest, StartupShutdownTest) {
 130   Predictor testing_master(true);
 131   testing_master.Shutdown();
 132 }
 133
 134
 135 TEST_F(PredictorTest, ShutdownWhenResolutionIsPendingTest) {
 136   scoped_ptr<net::HostResolver> host_resolver(new net::HangingHostResolver());
 137
 138   Predictor testing_master(true);
 139   testing_master.SetHostResolver(host_resolver.get());
 140
 141   GURL localhost("http://localhost:80");
 142   UrlList names;
 143   names.push_back(localhost);
 144
 145   testing_master.ResolveList(names, UrlInfo::PAGE_SCAN_MOTIVATED);
 146
 147   base::MessageLoop::current()->PostDelayedTask(
 148       FROM_HERE,
 149       base::MessageLoop::QuitClosure(),
 150       base::TimeDelta::FromMilliseconds(500));
 151   base::MessageLoop::current()->Run();
 152
 153   EXPECT_FALSE(testing_master.WasFound(localhost));
 154
 155   testing_master.Shutdown();
 156
 157   // Clean up after ourselves.
 158   base::MessageLoop::current()->RunUntilIdle();
 159 }
 160
 161 TEST_F(PredictorTest, SingleLookupTest) {
 162   Predictor testing_master(true);
 163   testing_master.SetHostResolver(host_resolver_.get());
 164
 165   GURL goog("http://www.google.com:80");
 166
 167   UrlList names;
 168   names.push_back(goog);
 169
 170   // Try to flood the predictor with many concurrent requests.
 171   for (int i = 0; i < 10; i++)
 172     testing_master.ResolveList(names, UrlInfo::PAGE_SCAN_MOTIVATED);
 173
 174   WaitForResolution(&testing_master, names);
 175
 176   EXPECT_TRUE(testing_master.WasFound(goog));
 177
 178   base::MessageLoop::current()->RunUntilIdle();
 179
 180   EXPECT_GT(testing_master.peak_pending_lookups(), names.size() / 2);
 181   EXPECT_LE(testing_master.peak_pending_lookups(), names.size());
 182   EXPECT_LE(testing_master.peak_pending_lookups(),
 183             testing_master.max_concurrent_dns_lookups());
 184
 185   testing_master.Shutdown();
 186 }
 187
 188 TEST_F(PredictorTest, ConcurrentLookupTest) {
 189   host_resolver_->rules()->AddSimulatedFailure("*.notfound");
 190
 191   Predictor testing_master(true);
 192   testing_master.SetHostResolver(host_resolver_.get());
 193
 194   GURL goog("http://www.google.com:80"),
 195       goog2("http://gmail.google.com.com:80"),
 196       goog3("http://mail.google.com:80"),
 197       goog4("http://gmail.com:80");
 198   GURL bad1("http://bad1.notfound:80"),
 199       bad2("http://bad2.notfound:80");
 200
 201   UrlList names;
 202   names.push_back(goog);
 203   names.push_back(goog3);
 204   names.push_back(bad1);
 205   names.push_back(goog2);
 206   names.push_back(bad2);
 207   names.push_back(goog4);
 208   names.push_back(goog);
 209
 210   // Try to flood the predictor with many concurrent requests.
 211   for (int i = 0; i < 10; i++)
 212     testing_master.ResolveList(names, UrlInfo::PAGE_SCAN_MOTIVATED);
 213
 214   WaitForResolution(&testing_master, names);
 215
 216   EXPECT_TRUE(testing_master.WasFound(goog));
 217   EXPECT_TRUE(testing_master.WasFound(goog3));
 218   EXPECT_TRUE(testing_master.WasFound(goog2));
 219   EXPECT_TRUE(testing_master.WasFound(goog4));
 220   EXPECT_FALSE(testing_master.WasFound(bad1));
 221   EXPECT_FALSE(testing_master.WasFound(bad2));
 222
 223   base::MessageLoop::current()->RunUntilIdle();
 224
 225   EXPECT_FALSE(testing_master.WasFound(bad1));
 226   EXPECT_FALSE(testing_master.WasFound(bad2));
 227
 228   EXPECT_LE(testing_master.peak_pending_lookups(), names.size());
 229   EXPECT_LE(testing_master.peak_pending_lookups(),
 230             testing_master.max_concurrent_dns_lookups());
 231
 232   testing_master.Shutdown();
 233 }
 234
 235 TEST_F(PredictorTest, MassiveConcurrentLookupTest) {
 236   host_resolver_->rules()->AddSimulatedFailure("*.notfound");
 237
 238   Predictor testing_master(true);
 239   testing_master.SetHostResolver(host_resolver_.get());
 240
 241   UrlList names;
 242   for (int i = 0; i < 100; i++)
 243     names.push_back(GURL(
 244         "http://host" + base::IntToString(i) + ".notfound:80"));
 245
 246   // Try to flood the predictor with many concurrent requests.
 247   for (int i = 0; i < 10; i++)
 248     testing_master.ResolveList(names, UrlInfo::PAGE_SCAN_MOTIVATED);
 249
 250   WaitForResolution(&testing_master, names);
 251
 252   base::MessageLoop::current()->RunUntilIdle();
 253
 254   EXPECT_LE(testing_master.peak_pending_lookups(), names.size());
 255   EXPECT_LE(testing_master.peak_pending_lookups(),
 256             testing_master.max_concurrent_dns_lookups());
 257
 258   testing_master.Shutdown();
 259 }
 260
 261 //------------------------------------------------------------------------------
 262 // Functions to help synthesize and test serializations of subresource referrer
 263 // lists.
 264
 265 // Return a motivation_list if we can find one for the given motivating_host (or
 266 // NULL if a match is not found).
 267 static const base::ListValue* FindSerializationMotivation(
 268     const GURL& motivation,
 269     const base::ListValue* referral_list) {
 270   CHECK_LT(0u, referral_list->GetSize());  // Room for version.
 271   int format_version = -1;
 272   CHECK(referral_list->GetInteger(0, &format_version));
 273   CHECK_EQ(Predictor::kPredictorReferrerVersion, format_version);
 274   const base::ListValue* motivation_list(NULL);
 275   for (size_t i = 1; i < referral_list->GetSize(); ++i) {
 276     referral_list->GetList(i, &motivation_list);
 277     std::string existing_spec;
 278     EXPECT_TRUE(motivation_list->GetString(0, &existing_spec));
 279     if (motivation == GURL(existing_spec))
 280       return motivation_list;
 281   }
 282   return NULL;
 283 }
 284
 285 static base::ListValue* FindSerializationMotivation(
 286     const GURL& motivation,
 287     base::ListValue* referral_list) {
 288   return const_cast<base::ListValue*>(FindSerializationMotivation(
 289       motivation, static_cast<const base::ListValue*>(referral_list)));
 290 }
 291
 292 // Create a new empty serialization list.
 293 static base::ListValue* NewEmptySerializationList() {
 294   base::ListValue* list = new base::ListValue;
 295   list->Append(
 296       new base::FundamentalValue(Predictor::kPredictorReferrerVersion));
 297   return list;
 298 }
 299
 300 // Add a motivating_url and a subresource_url to a serialized list, using
 301 // this given latency. This is a helper function for quickly building these
 302 // lists.
 303 static void AddToSerializedList(const GURL& motivation,
 304                                 const GURL& subresource,
 305                                 double use_rate,
 306                                 base::ListValue* referral_list) {
 307   // Find the motivation if it is already used.
 308   base::ListValue* motivation_list = FindSerializationMotivation(motivation,
 309                                                            referral_list);
 310   if (!motivation_list) {
 311     // This is the first mention of this motivation, so build a list.
 312     motivation_list = new base::ListValue;
 313     motivation_list->Append(new base::StringValue(motivation.spec()));
 314     // Provide empty subresource list.
 315     motivation_list->Append(new base::ListValue());
 316
 317     // ...and make it part of the serialized referral_list.
 318     referral_list->Append(motivation_list);
 319   }
 320
 321   base::ListValue* subresource_list(NULL);
 322   // 0 == url; 1 == subresource_list.
 323   EXPECT_TRUE(motivation_list->GetList(1, &subresource_list));
 324
 325   // We won't bother to check for the subresource being there already.  Worst
 326   // case, during deserialization, the latency value we supply plus the
 327   // existing value(s) will be added to the referrer.
 328
 329   subresource_list->Append(new base::StringValue(subresource.spec()));
 330   subresource_list->Append(new base::FundamentalValue(use_rate));
 331 }
 332
 333 // For a given motivation, and subresource, find what latency is currently
 334 // listed.  This assume a well formed serialization, which has at most one such
 335 // entry for any pair of names.  If no such pair is found, then return false.
 336 // Data is written into use_rate arguments.
 337 static bool GetDataFromSerialization(const GURL& motivation,
 338                                      const GURL& subresource,
 339                                      const base::ListValue& referral_list,
 340                                      double* use_rate) {
 341   const base::ListValue* motivation_list =
 342       FindSerializationMotivation(motivation, &referral_list);
 343   if (!motivation_list)
 344     return false;
 345   const base::ListValue* subresource_list;
 346   EXPECT_TRUE(motivation_list->GetList(1, &subresource_list));
 347   for (size_t i = 0; i < subresource_list->GetSize();) {
 348     std::string url_spec;
 349     EXPECT_TRUE(subresource_list->GetString(i++, &url_spec));
 350     EXPECT_TRUE(subresource_list->GetDouble(i++, use_rate));
 351     if (subresource == GURL(url_spec)) {
 352       return true;
 353     }
 354   }
 355   return false;
 356 }
 357
 358 //------------------------------------------------------------------------------
 359
 360 // Make sure nil referral lists really have no entries, and no latency listed.
 361 TEST_F(PredictorTest, ReferrerSerializationNilTest) {
 362   Predictor predictor(true);
 363   predictor.SetHostResolver(host_resolver_.get());
 364
 365   scoped_ptr<base::ListValue> referral_list(NewEmptySerializationList());
 366   predictor.SerializeReferrers(referral_list.get());
 367   EXPECT_EQ(1U, referral_list->GetSize());
 368   EXPECT_FALSE(GetDataFromSerialization(
 369     GURL("http://a.com:79"), GURL("http://b.com:78"),
 370       *referral_list.get(), NULL));
 371
 372   predictor.Shutdown();
 373 }
 374
 375 // Make sure that when a serialization list includes a value, that it can be
 376 // deserialized into the database, and can be extracted back out via
 377 // serialization without being changed.
 378 TEST_F(PredictorTest, ReferrerSerializationSingleReferrerTest) {
 379   Predictor predictor(true);
 380   predictor.SetHostResolver(host_resolver_.get());
 381   const GURL motivation_url("http://www.google.com:91");
 382   const GURL subresource_url("http://icons.google.com:90");
 383   const double kUseRate = 23.4;
 384   scoped_ptr<base::ListValue> referral_list(NewEmptySerializationList());
 385
 386   AddToSerializedList(motivation_url, subresource_url,
 387       kUseRate, referral_list.get());
 388
 389   predictor.DeserializeReferrers(*referral_list.get());
 390
 391   base::ListValue recovered_referral_list;
 392   predictor.SerializeReferrers(&recovered_referral_list);
 393   EXPECT_EQ(2U, recovered_referral_list.GetSize());
 394   double rate;
 395   EXPECT_TRUE(GetDataFromSerialization(
 396       motivation_url, subresource_url, recovered_referral_list, &rate));
 397   EXPECT_EQ(rate, kUseRate);
 398
 399   predictor.Shutdown();
 400 }
 401
 402 // Check that GetHtmlReferrerLists() doesn't crash when given duplicated
 403 // domains for referring URL, and that it sorts the results in the
 404 // correct order.
 405 TEST_F(PredictorTest, GetHtmlReferrerLists) {
 406   Predictor predictor(true);
 407   predictor.SetHostResolver(host_resolver_.get());
 408   const double kUseRate = 23.4;
 409   scoped_ptr<base::ListValue> referral_list(NewEmptySerializationList());
 410
 411   AddToSerializedList(
 412       GURL("http://d.google.com/x1"),
 413       GURL("http://foo.com/"),
 414       kUseRate, referral_list.get());
 415
 416   // Duplicated hostname (d.google.com). This should not cause any crashes
 417   // (i.e. crbug.com/116345)
 418   AddToSerializedList(
 419       GURL("http://d.google.com/x2"),
 420       GURL("http://foo.com/"),
 421       kUseRate, referral_list.get());
 422
 423   AddToSerializedList(
 424       GURL("http://a.yahoo.com/y"),
 425       GURL("http://foo1.com/"),
 426       kUseRate, referral_list.get());
 427
 428   AddToSerializedList(
 429       GURL("http://b.google.com/x3"),
 430       GURL("http://foo2.com/"),
 431       kUseRate, referral_list.get());
 432
 433   AddToSerializedList(
 434       GURL("http://d.yahoo.com/x5"),
 435       GURL("http://i.like.turtles/"),
 436       kUseRate, referral_list.get());
 437
 438   AddToSerializedList(
 439       GURL("http://c.yahoo.com/x4"),
 440       GURL("http://foo3.com/"),
 441       kUseRate, referral_list.get());
 442
 443   predictor.DeserializeReferrers(*referral_list.get());
 444
 445   std::string html;
 446   predictor.GetHtmlReferrerLists(&html);
 447
 448   // The lexicographic sorting of hostnames would be:
 449   //   a.yahoo.com
 450   //   b.google.com
 451   //   c.yahoo.com
 452   //   d.google.com
 453   //   d.yahoo.com
 454   //
 455   // However we expect to sort them by domain in the output:
 456   //   b.google.com
 457   //   d.google.com
 458   //   a.yahoo.com
 459   //   c.yahoo.com
 460   //   d.yahoo.com
 461
 462   size_t pos[] = {
 463       html.find("<td rowspan=1>http://b.google.com/x3"),
 464       html.find("<td rowspan=1>http://d.google.com/x1"),
 465       html.find("<td rowspan=1>http://d.google.com/x2"),
 466       html.find("<td rowspan=1>http://a.yahoo.com/y"),
 467       html.find("<td rowspan=1>http://c.yahoo.com/x4"),
 468       html.find("<td rowspan=1>http://d.yahoo.com/x5"),
 469   };
 470
 471   // Make sure things appeared in the expected order.
 472   for (size_t i = 1; i < arraysize(pos); ++i) {
 473     EXPECT_LT(pos[i - 1], pos[i]) << "Mismatch for pos[" << i << "]";
 474   }
 475
 476   predictor.Shutdown();
 477 }
 478
 479 // Verify that two floats are within 1% of each other in value.
 480 #define EXPECT_SIMILAR(a, b) do { \
 481     double espilon_ratio = 1.01;  \
 482     if ((a) < 0.)  \
 483       espilon_ratio = 1 / espilon_ratio;  \
 484     EXPECT_LT(a, espilon_ratio * (b));   \
 485     EXPECT_GT((a) * espilon_ratio, b);   \
 486     } while (0)
 487
 488
 489 // Make sure the Trim() functionality works as expected.
 490 TEST_F(PredictorTest, ReferrerSerializationTrimTest) {
 491   Predictor predictor(true);
 492   predictor.SetHostResolver(host_resolver_.get());
 493   GURL motivation_url("http://www.google.com:110");
 494
 495   GURL icon_subresource_url("http://icons.google.com:111");
 496   const double kRateIcon = 16.0 * Predictor::kDiscardableExpectedValue;
 497   GURL img_subresource_url("http://img.google.com:118");
 498   const double kRateImg = 8.0 * Predictor::kDiscardableExpectedValue;
 499
 500   scoped_ptr<base::ListValue> referral_list(NewEmptySerializationList());
 501   AddToSerializedList(
 502       motivation_url, icon_subresource_url, kRateIcon, referral_list.get());
 503   AddToSerializedList(
 504       motivation_url, img_subresource_url, kRateImg, referral_list.get());
 505
 506   predictor.DeserializeReferrers(*referral_list.get());
 507
 508   base::ListValue recovered_referral_list;
 509   predictor.SerializeReferrers(&recovered_referral_list);
 510   EXPECT_EQ(2U, recovered_referral_list.GetSize());
 511   double rate;
 512   EXPECT_TRUE(GetDataFromSerialization(
 513       motivation_url, icon_subresource_url, recovered_referral_list,
 514       &rate));
 515   EXPECT_SIMILAR(rate, kRateIcon);
 516
 517   EXPECT_TRUE(GetDataFromSerialization(
 518       motivation_url, img_subresource_url, recovered_referral_list, &rate));
 519   EXPECT_SIMILAR(rate, kRateImg);
 520
 521   // Each time we Trim 24 times, the user_rate figures should reduce by a factor
 522   // of two,  until they are small, and then a trim will delete the whole entry.
 523   for (int i = 0; i < 24; ++i)
 524     predictor.TrimReferrersNow();
 525   predictor.SerializeReferrers(&recovered_referral_list);
 526   EXPECT_EQ(2U, recovered_referral_list.GetSize());
 527   EXPECT_TRUE(GetDataFromSerialization(
 528       motivation_url, icon_subresource_url, recovered_referral_list, &rate));
 529   EXPECT_SIMILAR(rate, kRateIcon / 2);
 530
 531   EXPECT_TRUE(GetDataFromSerialization(
 532       motivation_url, img_subresource_url, recovered_referral_list, &rate));
 533   EXPECT_SIMILAR(rate, kRateImg / 2);
 534
 535   for (int i = 0; i < 24; ++i)
 536     predictor.TrimReferrersNow();
 537   predictor.SerializeReferrers(&recovered_referral_list);
 538   EXPECT_EQ(2U, recovered_referral_list.GetSize());
 539   EXPECT_TRUE(GetDataFromSerialization(
 540       motivation_url, icon_subresource_url, recovered_referral_list, &rate));
 541   EXPECT_SIMILAR(rate, kRateIcon / 4);
 542   EXPECT_TRUE(GetDataFromSerialization(
 543       motivation_url, img_subresource_url, recovered_referral_list, &rate));
 544   EXPECT_SIMILAR(rate, kRateImg / 4);
 545
 546   for (int i = 0; i < 24; ++i)
 547     predictor.TrimReferrersNow();
 548   predictor.SerializeReferrers(&recovered_referral_list);
 549   EXPECT_EQ(2U, recovered_referral_list.GetSize());
 550   EXPECT_TRUE(GetDataFromSerialization(
 551       motivation_url, icon_subresource_url, recovered_referral_list, &rate));
 552   EXPECT_SIMILAR(rate, kRateIcon / 8);
 553
 554   // Img is below threshold, and so it gets deleted.
 555   EXPECT_FALSE(GetDataFromSerialization(
 556       motivation_url, img_subresource_url, recovered_referral_list, &rate));
 557
 558   for (int i = 0; i < 24; ++i)
 559     predictor.TrimReferrersNow();
 560   predictor.SerializeReferrers(&recovered_referral_list);
 561   // Icon is also trimmed away, so entire set gets discarded.
 562   EXPECT_EQ(1U, recovered_referral_list.GetSize());
 563   EXPECT_FALSE(GetDataFromSerialization(
 564       motivation_url, icon_subresource_url, recovered_referral_list, &rate));
 565   EXPECT_FALSE(GetDataFromSerialization(
 566       motivation_url, img_subresource_url, recovered_referral_list, &rate));
 567
 568   predictor.Shutdown();
 569 }
 570
 571
 572 TEST_F(PredictorTest, PriorityQueuePushPopTest) {
 573   Predictor::HostNameQueue queue;
 574
 575   GURL first("http://first:80"), second("http://second:90");
 576
 577   // First check high priority queue FIFO functionality.
 578   EXPECT_TRUE(queue.IsEmpty());
 579   queue.Push(first, UrlInfo::LEARNED_REFERAL_MOTIVATED);
 580   EXPECT_FALSE(queue.IsEmpty());
 581   queue.Push(second, UrlInfo::MOUSE_OVER_MOTIVATED);
 582   EXPECT_FALSE(queue.IsEmpty());
 583   EXPECT_EQ(queue.Pop(), first);
 584   EXPECT_FALSE(queue.IsEmpty());
 585   EXPECT_EQ(queue.Pop(), second);
 586   EXPECT_TRUE(queue.IsEmpty());
 587
 588   // Then check low priority queue FIFO functionality.
 589   queue.Push(first, UrlInfo::PAGE_SCAN_MOTIVATED);
 590   EXPECT_FALSE(queue.IsEmpty());
 591   queue.Push(second, UrlInfo::OMNIBOX_MOTIVATED);
 592   EXPECT_FALSE(queue.IsEmpty());
 593   EXPECT_EQ(queue.Pop(), first);
 594   EXPECT_FALSE(queue.IsEmpty());
 595   EXPECT_EQ(queue.Pop(), second);
 596   EXPECT_TRUE(queue.IsEmpty());
 597 }
 598
 599 TEST_F(PredictorTest, PriorityQueueReorderTest) {
 600   Predictor::HostNameQueue queue;
 601
 602   // Push all the low priority items.
 603   GURL low1("http://low1:80"),
 604       low2("http://low2:80"),
 605       low3("http://low3:443"),
 606       low4("http://low4:80"),
 607       low5("http://low5:80"),
 608       hi1("http://hi1:80"),
 609       hi2("http://hi2:80"),
 610       hi3("http://hi3:80");
 611
 612   EXPECT_TRUE(queue.IsEmpty());
 613   queue.Push(low1, UrlInfo::PAGE_SCAN_MOTIVATED);
 614   queue.Push(low2, UrlInfo::UNIT_TEST_MOTIVATED);
 615   queue.Push(low3, UrlInfo::LINKED_MAX_MOTIVATED);
 616   queue.Push(low4, UrlInfo::OMNIBOX_MOTIVATED);
 617   queue.Push(low5, UrlInfo::STARTUP_LIST_MOTIVATED);
 618   queue.Push(low4, UrlInfo::OMNIBOX_MOTIVATED);
 619
 620   // Push all the high prority items
 621   queue.Push(hi1, UrlInfo::LEARNED_REFERAL_MOTIVATED);
 622   queue.Push(hi2, UrlInfo::STATIC_REFERAL_MOTIVATED);
 623   queue.Push(hi3, UrlInfo::MOUSE_OVER_MOTIVATED);
 624
 625   // Check that high priority stuff comes out first, and in FIFO order.
 626   EXPECT_EQ(queue.Pop(), hi1);
 627   EXPECT_EQ(queue.Pop(), hi2);
 628   EXPECT_EQ(queue.Pop(), hi3);
 629
 630   // ...and then low priority strings.
 631   EXPECT_EQ(queue.Pop(), low1);
 632   EXPECT_EQ(queue.Pop(), low2);
 633   EXPECT_EQ(queue.Pop(), low3);
 634   EXPECT_EQ(queue.Pop(), low4);
 635   EXPECT_EQ(queue.Pop(), low5);
 636   EXPECT_EQ(queue.Pop(), low4);
 637
 638   EXPECT_TRUE(queue.IsEmpty());
 639 }
 640
 641 TEST_F(PredictorTest, CanonicalizeUrl) {
 642   // Base case, only handles HTTP and HTTPS.
 643   EXPECT_EQ(GURL(), Predictor::CanonicalizeUrl(GURL("ftp://anything")));
 644
 645   // Remove path testing.
 646   GURL long_url("http://host:999/path?query=value");
 647   EXPECT_EQ(Predictor::CanonicalizeUrl(long_url), long_url.GetWithEmptyPath());
 648
 649   // Default port cannoncalization.
 650   GURL implied_port("http://test");
 651   GURL explicit_port("http://test:80");
 652   EXPECT_EQ(Predictor::CanonicalizeUrl(implied_port),
 653             Predictor::CanonicalizeUrl(explicit_port));
 654
 655   // Port is still maintained.
 656   GURL port_80("http://test:80");
 657   GURL port_90("http://test:90");
 658   EXPECT_NE(Predictor::CanonicalizeUrl(port_80),
 659             Predictor::CanonicalizeUrl(port_90));
 660
 661   // Host is still maintained.
 662   GURL host_1("http://test_1");
 663   GURL host_2("http://test_2");
 664   EXPECT_NE(Predictor::CanonicalizeUrl(host_1),
 665             Predictor::CanonicalizeUrl(host_2));
 666
 667   // Scheme is maintained (mismatch identified).
 668   GURL http("http://test");
 669   GURL https("https://test");
 670   EXPECT_NE(Predictor::CanonicalizeUrl(http),
 671             Predictor::CanonicalizeUrl(https));
 672
 673   // Https works fine.
 674   GURL long_https("https://host:999/path?query=value");
 675   EXPECT_EQ(Predictor::CanonicalizeUrl(long_https),
 676             long_https.GetWithEmptyPath());
 677 }
 678
 679 TEST_F(PredictorTest, DiscardPredictorResults) {
 680   Predictor predictor(true);
 681   predictor.SetHostResolver(host_resolver_.get());
 682   base::ListValue referral_list;
 683   predictor.SerializeReferrers(&referral_list);
 684   EXPECT_EQ(1U, referral_list.GetSize());
 685
 686   GURL host_1("http://test_1");
 687   GURL host_2("http://test_2");
 688   predictor.LearnFromNavigation(host_1, host_2);
 689
 690   predictor.SerializeReferrers(&referral_list);
 691   EXPECT_EQ(2U, referral_list.GetSize());
 692
 693   predictor.DiscardAllResults();
 694   predictor.SerializeReferrers(&referral_list);
 695   EXPECT_EQ(1U, referral_list.GetSize());
 696
 697   predictor.Shutdown();
 698 }
 699
 700 #if defined(OS_ANDROID) || defined(OS_IOS)
 701 // Tests for the predictor with a proxy advisor
 702
 703 class TestProxyAdvisor : public ProxyAdvisor {
 704  public:
 705   TestProxyAdvisor()
 706       : ProxyAdvisor(NULL, NULL),
 707         would_proxy_(false),
 708         advise_count_(0),
 709         would_proxy_count_(0) {
 710   }
 711
 712   virtual ~TestProxyAdvisor() {}
 713
 714   virtual void Advise(const GURL& url,
 715                       UrlInfo::ResolutionMotivation motivation,
 716                       bool is_preconnect) OVERRIDE {
 717     ++advise_count_;
 718   }
 719
 720   virtual bool WouldProxyURL(const GURL& url) OVERRIDE {
 721     ++would_proxy_count_;
 722     return would_proxy_;
 723   }
 724
 725   bool would_proxy_;
 726   int advise_count_;
 727   int would_proxy_count_;
 728 };
 729
 730 TEST_F(PredictorTest, SingleLookupTestWithDisabledAdvisor) {
 731   Predictor testing_master(true);
 732   TestProxyAdvisor* advisor = new TestProxyAdvisor();
 733   testing_master.SetHostResolver(host_resolver_.get());
 734   testing_master.proxy_advisor_.reset(advisor);
 735
 736   GURL goog("http://www.google.com:80");
 737
 738   advisor->would_proxy_ = false;
 739
 740   UrlList names;
 741   names.push_back(goog);
 742   testing_master.ResolveList(names, UrlInfo::PAGE_SCAN_MOTIVATED);
 743
 744   WaitForResolution(&testing_master, names);
 745   EXPECT_TRUE(testing_master.WasFound(goog));
 746   EXPECT_EQ(advisor->would_proxy_count_, 1);
 747   EXPECT_EQ(advisor->advise_count_, 1);
 748
 749   base::MessageLoop::current()->RunUntilIdle();
 750
 751   testing_master.Shutdown();
 752 }
 753
 754 TEST_F(PredictorTest, SingleLookupTestWithEnabledAdvisor) {
 755   Predictor testing_master(true);
 756   testing_master.SetHostResolver(host_resolver_.get());
 757   TestProxyAdvisor* advisor = new TestProxyAdvisor();
 758   testing_master.proxy_advisor_.reset(advisor);
 759
 760   GURL goog("http://www.google.com:80");
 761
 762   advisor->would_proxy_ = true;
 763
 764   UrlList names;
 765   names.push_back(goog);
 766
 767   testing_master.ResolveList(names, UrlInfo::PAGE_SCAN_MOTIVATED);
 768
 769   // Attempt to resolve a few times.
 770   WaitForResolutionWithLimit(&testing_master, names, 10);
 771
 772   // Because the advisor indicated that the url would be proxied,
 773   // no resolution should have occurred.
 774   EXPECT_FALSE(testing_master.WasFound(goog));
 775   EXPECT_EQ(advisor->would_proxy_count_, 1);
 776   EXPECT_EQ(advisor->advise_count_, 1);
 777
 778   base::MessageLoop::current()->RunUntilIdle();
 779
 780   testing_master.Shutdown();
 781 }
 782
 783 TEST_F(PredictorTest, TestSimplePreconnectAdvisor) {
 784   Predictor testing_master(true);
 785   testing_master.SetHostResolver(host_resolver_.get());
 786   TestProxyAdvisor* advisor = new TestProxyAdvisor();
 787   testing_master.proxy_advisor_.reset(advisor);
 788
 789   GURL goog("http://www.google.com:80");
 790
 791   testing_master.PreconnectUrl(goog, goog, UrlInfo::OMNIBOX_MOTIVATED, 2);
 792
 793   EXPECT_EQ(advisor->would_proxy_count_, 0);
 794   EXPECT_EQ(advisor->advise_count_, 1);
 795
 796   testing_master.Shutdown();
 797 }
 798
 799 #endif  // defined(OS_ANDROID) || defined(OS_IOS)
 800
 801 }  // namespace chrome_browser_net