Recover from inconsistent cookie database.

In particular, if the database has multiple cookies defined for the same (host, cookie name, cookie path), we will delete all but the most recently created cookie.

This step happens right after loading the cookie database.

I don't expect this to have any real impact on startup performance, since the cookie database is small, and compared to the cost of reading the DB from disk, should be cheap.

This CL also includes two other related changes:

  (1) Added a histogram "Net.NumDuplicateCookiesInDb" that measures how common the need to remove duplicates is.
  (2) If the in-memory store is ever found to contain duplicates after initializion, fail hard (crash).

The effect of this change will be users that had a bad database will get it fixed, and will no longer be sending duplicate cookies to servers.

-----------------------
Background:
-----------------------

Ok, so why does the corruption happen in the first place?

From what I can tell, the problem stems from how the interface between CookieMonster and the PersistentCookieStore is defined. Notably:
  * It implements overwrites as "delete" + "insert" operations.
  * It doesn't define the behavior when a "delete" or "insert" operation fails.

The steps that CookieMonster() runs through to overwrite a cookie is:

  (a) Find the existing cookie, |old_cookie|, in the in-memory store.
  (b) Delete |old_cookie| from the in-memory store.
  (c) Ask the persistent cookie backing store to delete |old_cookie| (keyed by its creation time)
  (d) Insert |new_cookie| into the in-memory store.
  (e) Ask the persistent backing store to insert |new_cookie|.

This ordering assumes that no failures can happen during steps (c) and (e).
However in actuality, SQLitePersistentCookieStore swallows any errors it encounters writing to the DB, and does not attempt retries.

Here is one sequence of steps that could lead to your database getting hosed:

(1) Your cookie database becomes temporarily unwritable (maybe your home directory is network mounted and your kerberose ticket just expired).

(2) The browser gets a set-cookie to overwrite an existing cookie (perhaps a ping-back from gmail, which happen often).
Clearly steps (c) and (e) will now fail, since the database is offline. So the in-memory store will get changed, but the on-disk one won't.

(3) Now your cookie database becomes writable again (maybe you renewed the ticket).

(4) Another cookie update is received. This time, the update will cause us to insert a duplicate into the cookie database.
This happens because in step (c) the on-disk database is asked to delete the previous (at least according to the in-memory store) cookie. Well, the on-disk DB never wrote that value, so this has no effect, and the actual previous value remains. Next we insert the new value, kaboom.


A next step will be to re-work the PersistentCookieStore interface so SQLitePersistentCookieStore isn't as fragile to errors while overwriting.

BUG=17855

TEST=CookieMonsterTest.DontImportDuplicateCookies

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

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

3 files changed, 277 insertions, 14 deletions

diff --git a/net/base/cookie_monster.cc b/net/base/cookie_monster.cc
index 87ab1bd..1b37f48 100644
--- a/net/base/cookie_monster.cc
+++ b/net/base/cookie_monster.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// Copyright (c) 2010 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.
 
@@ -48,6 +48,7 @@
 
 #include "base/basictypes.h"
 #include "base/format_macros.h"
+#include "base/histogram.h"
 #include "base/logging.h"
 #include "base/scoped_ptr.h"
 #include "base/string_tokenizer.h"
@@ -68,19 +69,32 @@ using base::TimeDelta;
 
 namespace net {
 
+namespace {
+
 // Cookie garbage collection thresholds.  Based off of the Mozilla defaults.
 // It might seem scary to have a high purge value, but really it's not.  You
 // just make sure that you increase the max to cover the increase in purge,
 // and we would have been purging the same amount of cookies.  We're just
 // going through the garbage collection process less often.
-static const size_t kNumCookiesPerHost      = 70;  // ~50 cookies
-static const size_t kNumCookiesPerHostPurge = 20;
-static const size_t kNumCookiesTotal        = 3300;  // ~3000 cookies
-static const size_t kNumCookiesTotalPurge   = 300;
+const size_t kNumCookiesPerHost      = 70;  // ~50 cookies
+const size_t kNumCookiesPerHostPurge = 20;
+const size_t kNumCookiesTotal        = 3300;  // ~3000 cookies
+const size_t kNumCookiesTotalPurge   = 300;
 
 // Default minimum delay after updating a cookie's LastAccessDate before we
 // will update it again.
-static const int kDefaultAccessUpdateThresholdSeconds = 60;
+const int kDefaultAccessUpdateThresholdSeconds = 60;
+
+// Comparator to sort cookies from highest creation date to lowest
+// creation date.
+struct OrderByCreationTimeDesc {
+  bool operator()(const CookieMonster::CookieMap::iterator& a,
+                  const CookieMonster::CookieMap::iterator& b) const {
+    return a->second->CreationDate() > b->second->CreationDate();
+  }
+};
+
+}  // namespace
 
 // static
 bool CookieMonster::enable_file_scheme_ = false;
@@ -117,6 +131,116 @@ void CookieMonster::InitStore() {
        it != cookies.end(); ++it) {
     InternalInsertCookie(it->first, it->second, false);
   }
+
+  // After importing cookies from the PersistentCookieStore, verify that
+  // none of our constraints are violated.
+  //
+  // In particular, the backing store might have given us duplicate cookies.
+  EnsureCookiesMapIsValid();
+}
+
+void CookieMonster::EnsureCookiesMapIsValid() {
+  int num_duplicates_trimmed = 0;
+
+  // Iterate through all the of the cookies, grouped by host.
+  CookieMap::iterator prev_range_end = cookies_.begin();
+  while (prev_range_end != cookies_.end()) {
+    CookieMap::iterator cur_range_begin = prev_range_end;
+    const std::string key = cur_range_begin->first;  // Keep a copy.
+    CookieMap::iterator cur_range_end = cookies_.upper_bound(key);
+    prev_range_end = cur_range_end;
+
+    // Ensure no equivalent cookies for this host.
+    num_duplicates_trimmed +=
+        TrimDuplicateCookiesForHost(key, cur_range_begin, cur_range_end);
+  }
+
+  // Record how many duplicates were found in the database.
+  UMA_HISTOGRAM_COUNTS_10000("Net.NumDuplicateCookiesInDb",
+                             num_duplicates_trimmed);
+
+  // TODO(eroman): Should also verify that there are no cookies with the same
+  // creation time, since that is assumed to be unique by the rest of the code.
+}
+
+// Our strategy to find duplicates is:
+// (1) Build a map from (cookiename, cookiepath) to
+//     {list of cookies with this signature, sorted by creation time}.
+// (2) For each list with more than 1 entry, keep the cookie having the
+//     most recent creation time, and delete the others.
+int CookieMonster::TrimDuplicateCookiesForHost(
+    const std::string& key,
+    CookieMap::iterator begin,
+    CookieMap::iterator end) {
+
+  // Two cookies are considered equivalent if they have the same name and path.
+  typedef std::pair<std::string, std::string> CookieSignature;
+
+  // List of cookies ordered by creation time.
+  typedef std::set<CookieMap::iterator, OrderByCreationTimeDesc> CookieList;
+
+  // Helper map we populate to find the duplicates.
+  typedef std::map<CookieSignature, CookieList> EquivalenceMap;
+  EquivalenceMap equivalent_cookies;
+
+  // The number of duplicate cookies that have been found.
+  int num_duplicates = 0;
+
+  // Iterate through all of the cookies in our range, and insert them into
+  // the equivalence map.
+  for (CookieMap::iterator it = begin; it != end; ++it) {
+    DCHECK_EQ(key, it->first);
+    CanonicalCookie* cookie = it->second;
+
+    CookieSignature signature(cookie->Name(), cookie->Path());
+    CookieList& list = equivalent_cookies[signature];
+
+    // We found a duplicate!
+    if (!list.empty())
+      num_duplicates++;
+
+    // We save the iterator into |cookies_| rather than the actual cookie
+    // pointer, since we may need to delete it later.
+    list.insert(it);
+  }
+
+  // If there were no duplicates, we are done!
+  if (num_duplicates == 0)
+    return 0;
+
+  // Otherwise, delete all the duplicate cookies, both from our in-memory store
+  // and from the backing store.
+  for (EquivalenceMap::iterator it = equivalent_cookies.begin();
+       it != equivalent_cookies.end();
+       ++it) {
+    const CookieSignature& signature = it->first;
+    CookieList& dupes = it->second;
+
+    if (dupes.size() <= 1)
+      continue;  // This cookiename/path has no duplicates.
+
+    // Since |dups| is sorted by creation time (descending), the first cookie
+    // is the most recent one, so we will keep it. The rest are duplicates.
+    dupes.erase(dupes.begin());
+
+    LOG(ERROR) << StringPrintf("Found %d duplicate cookies for host='%s', "
+                               "with {name='%s', path='%s'}",
+                               static_cast<int>(dupes.size()),
+                               key.c_str(),
+                               signature.first.c_str(),
+                               signature.second.c_str());
+
+    // Remove all the cookies identified by |dupes|. It is valid to delete our
+    // list of iterators one at a time, since |cookies_| is a multimap (they
+    // don't invalidate existing iterators following deletion).
+    for (CookieList::iterator dupes_it = dupes.begin();
+         dupes_it != dupes.end();
+         ++dupes_it) {
+      InternalDeleteCookie(*dupes_it, true /*sync_to_store*/);
+    }
+  }
+
+  return num_duplicates;
 }
 
 void CookieMonster::SetDefaultCookieableSchemes() {
@@ -523,7 +647,7 @@ bool CookieMonster::DeleteAnyEquivalentCookie(const std::string& key,
     if (ecc.IsEquivalent(*cc)) {
       // We should never have more than one equivalent cookie, since they should
       // overwrite each other.
-      DCHECK(!found_equivalent_cookie) <<
+      CHECK(!found_equivalent_cookie) <<
           "Duplicate equivalent cookies found, cookie store is corrupted.";
       if (skip_httponly && cc->IsHttpOnly()) {
         skipped_httponly = true;
@@ -531,11 +655,6 @@ bool CookieMonster::DeleteAnyEquivalentCookie(const std::string& key,
         InternalDeleteCookie(curit, true);
       }
       found_equivalent_cookie = true;
-#ifdef NDEBUG
-      // Speed optimization: No point looping through the rest of the cookies
-      // since we're only doing it as a consistency check.
-      break;
-#endif
     }
   }
   return skipped_httponly;
diff --git a/net/base/cookie_monster.h b/net/base/cookie_monster.h
index 6ae2903..f944842 100644
--- a/net/base/cookie_monster.h
+++ b/net/base/cookie_monster.h
@@ -148,6 +148,17 @@ class CookieMonster : public CookieStore {
   // Should only be called by InitIfNecessary().
   void InitStore();
 
+  // Checks that |cookies_| matches our invariants, and tries to repair any
+  // inconsistencies. (In other words, it does not have duplicate cookies).
+  void EnsureCookiesMapIsValid();
+
+  // Checks for any duplicate cookies for host |key|, which lie between
+  // |begin| and |end|. If any are found, all but the most recent are deleted.
+  // Returns the number of duplicate cookies that were deleted.
+  int TrimDuplicateCookiesForHost(const std::string& key,
+                                  CookieMap::iterator begin,
+                                  CookieMap::iterator end);
+
   void SetDefaultCookieableSchemes();
 
   void FindCookiesForHostAndDomain(const GURL& url,
@@ -341,6 +352,7 @@ class CookieMonster::CanonicalCookie {
   bool IsEquivalent(const CanonicalCookie& ecc) const {
     // It seems like it would make sense to take secure and httponly into
     // account, but the RFC doesn't specify this.
+    // NOTE: Keep this logic in-sync with TrimDuplicateCookiesForHost().
     return name_ == ecc.Name() && path_ == ecc.Path();
   }
 
diff --git a/net/base/cookie_monster_unittest.cc b/net/base/cookie_monster_unittest.cc
index 2a86c6d..4c7dd4b 100644
--- a/net/base/cookie_monster_unittest.cc
+++ b/net/base/cookie_monster_unittest.cc
@@ -9,6 +9,7 @@
 #include "base/basictypes.h"
 #include "base/platform_thread.h"
 #include "base/ref_counted.h"
+#include "base/scoped_ptr.h"
 #include "base/string_util.h"
 #include "base/time.h"
 #include "googleurl/src/gurl.h"
@@ -43,16 +44,21 @@ struct CookieStoreCommand {
 
 // Implementation of PersistentCookieStore that captures the
 // received commands and saves them to a list.
+// The result of calls to Load() can be configured using SetLoadExpectation().
 class MockPersistentCookieStore
     : public net::CookieMonster::PersistentCookieStore {
  public:
   typedef std::vector<CookieStoreCommand> CommandList;
 
-  MockPersistentCookieStore() {}
+  MockPersistentCookieStore() : load_return_value_(true) {
+  }
 
   virtual bool Load(
       std::vector<net::CookieMonster::KeyedCanonicalCookie>* out_cookies) {
-    return true;
+    bool ok = load_return_value_;
+    if (ok)
+      *out_cookies = load_result_;
+    return ok;
   }
 
   virtual void AddCookie(const std::string& key,
@@ -73,6 +79,13 @@ class MockPersistentCookieStore
         CookieStoreCommand(CookieStoreCommand::REMOVE, std::string(), cookie));
   }
 
+  void SetLoadExpectation(
+      bool return_value,
+      const std::vector<net::CookieMonster::KeyedCanonicalCookie>& result) {
+    load_return_value_ = return_value;
+    load_result_ = result;
+  }
+
   const CommandList& commands() const {
     return commands_;
   }
@@ -80,9 +93,46 @@ class MockPersistentCookieStore
  private:
   CommandList commands_;
 
+  // Deferred result to use when Load() is called.
+  bool load_return_value_;
+  std::vector<net::CookieMonster::KeyedCanonicalCookie> load_result_;
+
   DISALLOW_COPY_AND_ASSIGN(MockPersistentCookieStore);
 };
 
+// Helper to build a list of KeyedCanonicalCookies.
+void AddKeyedCookieToList(
+    const std::string& key,
+    const std::string& cookie_line,
+    const Time& creation_time,
+    std::vector<net::CookieMonster::KeyedCanonicalCookie>* out_list) {
+
+  // Parse the cookie line.
+  net::CookieMonster::ParsedCookie pc(cookie_line);
+  EXPECT_TRUE(pc.IsValid());
+
+  // This helper is simplistic in interpreting a parsed cookie, in order to
+  // avoid duplicated CookieMonster's CanonPath() and CanonExpiration()
+  // functions. Would be nice to export them, and re-use here.
+  EXPECT_FALSE(pc.HasMaxAge());
+  EXPECT_TRUE(pc.HasPath());
+  Time cookie_expires = pc.HasExpires() ?
+      net::CookieMonster::ParseCookieTime(pc.Expires()) : Time();
+  std::string cookie_path = pc.Path();
+
+  scoped_ptr<net::CookieMonster::CanonicalCookie> cookie(
+      new net::CookieMonster::CanonicalCookie(
+          pc.Name(), pc.Value(), cookie_path,
+          pc.IsSecure(), pc.IsHttpOnly(),
+          creation_time, creation_time,
+          !cookie_expires.is_null(),
+          cookie_expires));
+
+  out_list->push_back(
+      net::CookieMonster::KeyedCanonicalCookie(
+          key, cookie.release()));
+}
+
 }  // namespace
 
 
@@ -1272,3 +1322,85 @@ TEST(CookieMonsterTest, OverwritePersistentCookie) {
   EXPECT_EQ("a=val9", cm->GetCookies(GURL("http://www.google.com/path2")));
   EXPECT_EQ("a=val99", cm->GetCookies(GURL("http://chromium.org/path1")));
 }
+
+// Tests importing from a persistent cookie store that contains duplicate
+// equivalent cookies. This situation should be handled by removing the
+// duplicate cookie (both from the in-memory cache, and from the backing store).
+//
+// This is a regression test for: http://crbug.com/17855.
+TEST(CookieMonsterTest, DontImportDuplicateCookies) {
+  GURL url_google("http://www.google.com/");
+
+  scoped_refptr<MockPersistentCookieStore> store(
+      new MockPersistentCookieStore);
+
+  // We will fill some initial cookies into the PersistentCookieStore,
+  // to simulate a database with 4 duplicates.
+  std::vector<net::CookieMonster::KeyedCanonicalCookie> initial_cookies;
+
+  // Insert 4 cookies with name "X" on path "/", with varying creation
+  // dates. We expect only the most recent one to be preserved following
+  // the import.
+
+  AddKeyedCookieToList("www.google.com",
+                       "X=1; path=/; expires=Mon, 18-Apr-22 22:50:14 GMT",
+                       Time::Now() + TimeDelta::FromDays(3),
+                       &initial_cookies);
+
+  AddKeyedCookieToList("www.google.com",
+                       "X=2; path=/; expires=Mon, 18-Apr-22 22:50:14 GMT",
+                       Time::Now() + TimeDelta::FromDays(1),
+                       &initial_cookies);
+
+  // ===> This one is the WINNER (biggest creation time).  <====
+  AddKeyedCookieToList("www.google.com",
+                       "X=3; path=/; expires=Mon, 18-Apr-22 22:50:14 GMT",
+                       Time::Now() + TimeDelta::FromDays(4),
+                       &initial_cookies);
+
+  AddKeyedCookieToList("www.google.com",
+                       "X=4; path=/; expires=Mon, 18-Apr-22 22:50:14 GMT",
+                       Time::Now(),
+                       &initial_cookies);
+
+  // Insert 2 cookies with name "X" on path "/2", with varying creation
+  // dates. We expect only the most recent one to be preserved the import.
+
+  // ===> This one is the WINNER (biggest creation time).  <====
+  AddKeyedCookieToList("www.google.com",
+                       "X=a1; path=/2; expires=Mon, 18-Apr-22 22:50:14 GMT",
+                       Time::Now() + TimeDelta::FromDays(9),
+                       &initial_cookies);
+
+  AddKeyedCookieToList("www.google.com",
+                       "X=a2; path=/2; expires=Mon, 18-Apr-22 22:50:14 GMT",
+                       Time::Now() + TimeDelta::FromDays(1),
+                       &initial_cookies);
+
+  // Insert 1 cookie with name "Y" on path "/".
+  AddKeyedCookieToList("www.google.com",
+                       "Y=a; path=/; expires=Mon, 18-Apr-22 22:50:14 GMT",
+                       Time::Now() + TimeDelta::FromDays(9),
+                       &initial_cookies);
+
+  // Inject our initial cookies into the mock PersistentCookieStore.
+  store->SetLoadExpectation(true, initial_cookies);
+
+  scoped_refptr<net::CookieMonster> cm(new net::CookieMonster(store));
+
+  // Verify that duplicates were not imported for path "/".
+  // (If this had failed, GetCookies() would have also returned X=1, X=2, X=4).
+  EXPECT_EQ("X=3; Y=a", cm->GetCookies(GURL("http://www.google.com/")));
+
+  // Verify that same-named cookie on a different path ("/x2") didn't get
+  // messed up.
+  EXPECT_EQ("X=a1; X=3; Y=a",
+            cm->GetCookies(GURL("http://www.google.com/2/x")));
+
+  // Verify that the PersistentCookieStore was told to kill its 4 duplicates.
+  ASSERT_EQ(4u, store->commands().size());
+  EXPECT_EQ(CookieStoreCommand::REMOVE, store->commands()[0].type);
+  EXPECT_EQ(CookieStoreCommand::REMOVE, store->commands()[1].type);
+  EXPECT_EQ(CookieStoreCommand::REMOVE, store->commands()[2].type);
+  EXPECT_EQ(CookieStoreCommand::REMOVE, store->commands()[3].type);
+}