diff options
| -rw-r--r-- | net/cookies/cookie_monster.cc | 279 | ||||
| -rw-r--r-- | net/cookies/cookie_monster.h | 67 | ||||
| -rw-r--r-- | net/cookies/cookie_monster_unittest.cc | 173 |
3 files changed, 380 insertions, 139 deletions
diff --git a/net/cookies/cookie_monster.cc b/net/cookies/cookie_monster.cc index c9b386a..0b0bb68 100644 --- a/net/cookies/cookie_monster.cc +++ b/net/cookies/cookie_monster.cc @@ -45,6 +45,7 @@ #include "net/cookies/cookie_monster.h" #include <algorithm> +#include <functional> #include <set> #include "base/basictypes.h" @@ -97,6 +98,14 @@ const size_t CookieMonster::kDomainMaxCookies = 180; const size_t CookieMonster::kDomainPurgeCookies = 30; const size_t CookieMonster::kMaxCookies = 3300; const size_t CookieMonster::kPurgeCookies = 300; + +const size_t CookieMonster::kDomainCookiesQuotaLow = 30; +const size_t CookieMonster::kDomainCookiesQuotaMedium = 50; +const size_t CookieMonster::kDomainCookiesQuotaHigh = + CookieMonster::kDomainMaxCookies - CookieMonster::kDomainPurgeCookies + - CookieMonster::kDomainCookiesQuotaLow + - CookieMonster::kDomainCookiesQuotaMedium; + const int CookieMonster::kSafeFromGlobalPurgeDays = 30; namespace { @@ -132,7 +141,7 @@ bool CookieSorter(CanonicalCookie* cc1, CanonicalCookie* cc2) { return cc1->Path().length() > cc2->Path().length(); } -bool LRUCookieSorter(const CookieMonster::CookieMap::iterator& it1, +bool LRACookieSorter(const CookieMonster::CookieMap::iterator& it1, const CookieMonster::CookieMap::iterator& it2) { // Cookies accessed less recently should be deleted first. if (it1->second->LastAccessDate() != it2->second->LastAccessDate()) @@ -192,36 +201,57 @@ bool GetCookieDomain(const GURL& url, return cookie_util::GetCookieDomainWithString(url, domain_string, result); } -// Helper for GarbageCollection. If |cookie_its->size() > num_max|, remove the -// |num_max - num_purge| most recently accessed cookies from cookie_its. -// (In other words, leave the entries that are candidates for -// eviction in cookie_its.) The cookies returned will be in order sorted by -// access time, least recently accessed first. The access time of the least -// recently accessed entry not returned will be placed in -// |*lra_removed| if that pointer is set. FindLeastRecentlyAccessed -// returns false if no manipulation is done (because the list size is less -// than num_max), true otherwise. -bool FindLeastRecentlyAccessed( - size_t num_max, - size_t num_purge, - Time* lra_removed, - std::vector<CookieMonster::CookieMap::iterator>* cookie_its) { - DCHECK_LE(num_purge, num_max); - if (cookie_its->size() > num_max) { - VLOG(kVlogGarbageCollection) - << "FindLeastRecentlyAccessed() Deep Garbage Collect."; - num_purge += cookie_its->size() - num_max; - DCHECK_GT(cookie_its->size(), num_purge); - - // Add 1 so that we can get the last time left in the store. - std::partial_sort(cookie_its->begin(), cookie_its->begin() + num_purge + 1, - cookie_its->end(), LRUCookieSorter); - *lra_removed = - (*(cookie_its->begin() + num_purge))->second->LastAccessDate(); - cookie_its->erase(cookie_its->begin() + num_purge, cookie_its->end()); - return true; +// For a CookieItVector iterator range [|it_begin|, |it_end|), +// sorts the first |num_sort| + 1 elements by LastAccessDate(). +// The + 1 element exists so for any interval of length <= |num_sort| starting +// from |cookies_its_begin|, a LastAccessDate() bound can be found. +void SortLeastRecentlyAccessed( + CookieMonster::CookieItVector::iterator it_begin, + CookieMonster::CookieItVector::iterator it_end, + size_t num_sort) { + DCHECK_LT(static_cast<int>(num_sort), it_end - it_begin); + std::partial_sort(it_begin, it_begin + num_sort + 1, it_end, LRACookieSorter); +} + +// Predicate to support PartitionCookieByPriority(). +struct CookiePriorityEqualsTo + : std::unary_function<const CookieMonster::CookieMap::iterator, bool> { + CookiePriorityEqualsTo(CookiePriority priority) + : priority_(priority) {} + + bool operator()(const CookieMonster::CookieMap::iterator it) const { + return it->second->Priority() == priority_; } - return false; + + const CookiePriority priority_; +}; + +// For a CookieItVector iterator range [|it_begin|, |it_end|), +// moves all cookies with a given |priority| to the beginning of the list. +// Returns: An iterator in [it_begin, it_end) to the first element with +// priority != |priority|, or |it_end| if all have priority == |priority|. +CookieMonster::CookieItVector::iterator PartitionCookieByPriority( + CookieMonster::CookieItVector::iterator it_begin, + CookieMonster::CookieItVector::iterator it_end, + CookiePriority priority) { + return std::partition(it_begin, it_end, CookiePriorityEqualsTo(priority)); +} + +bool LowerBoundAccessDateComparator( + const CookieMonster::CookieMap::iterator it, const Time& access_date) { + return it->second->LastAccessDate() < access_date; +} + +// For a CookieItVector iterator range [|it_begin|, |it_end|) +// from a CookieItVector sorted by LastAccessDate(), returns the +// first iterator with access date >= |access_date|, or cookie_its_end if this +// holds for all. +CookieMonster::CookieItVector::iterator LowerBoundAccessDate( + const CookieMonster::CookieItVector::iterator its_begin, + const CookieMonster::CookieItVector::iterator its_end, + const Time& access_date) { + return std::lower_bound(its_begin, its_end, access_date, + LowerBoundAccessDateComparator); } // Mapping between DeletionCause and Delegate::ChangeCause; the mapping also @@ -288,7 +318,8 @@ CookieMonster::CookieMonster(PersistentCookieStore* store, Delegate* delegate) delegate_(delegate), last_statistic_record_time_(Time::Now()), keep_expired_cookies_(false), - persist_session_cookies_(false) { + persist_session_cookies_(false), + priority_aware_garbage_collection_(false) { InitializeHistograms(); SetDefaultCookieableSchemes(); } @@ -304,7 +335,8 @@ CookieMonster::CookieMonster(PersistentCookieStore* store, delegate_(delegate), last_statistic_record_time_(base::Time::Now()), keep_expired_cookies_(false), - persist_session_cookies_(false) { + persist_session_cookies_(false), + priority_aware_garbage_collection_(false) { InitializeHistograms(); SetDefaultCookieableSchemes(); } @@ -1293,12 +1325,19 @@ CookieMonster* CookieMonster::GetCookieMonster() { return this; } +// This function must be called before the CookieMonster is used. void CookieMonster::SetPersistSessionCookies(bool persist_session_cookies) { - // This function must be called before the CookieMonster is used. DCHECK(!initialized_); persist_session_cookies_ = persist_session_cookies; } +// This function must be called before the CookieMonster is used. +void CookieMonster::SetPriorityAwareGarbageCollection( + bool priority_aware_garbage_collection) { + DCHECK(!initialized_); + priority_aware_garbage_collection_ = priority_aware_garbage_collection; +} + void CookieMonster::SetForceKeepSessionState() { if (store_) { store_->SetForceKeepSessionState(); @@ -1758,78 +1797,124 @@ void CookieMonster::InternalDeleteCookie(CookieMap::iterator it, } // Domain expiry behavior is unchanged by key/expiry scheme (the -// meaning of the key is different, but that's not visible to this -// routine). +// meaning of the key is different, but that's not visible to this routine). int CookieMonster::GarbageCollect(const Time& current, const std::string& key) { lock_.AssertAcquired(); int num_deleted = 0; + Time safe_date( + Time::Now() - TimeDelta::FromDays(kSafeFromGlobalPurgeDays)); - // Collect garbage for this key. + // Collect garbage for this key, minding cookie priorities. if (cookies_.count(key) > kDomainMaxCookies) { VLOG(kVlogGarbageCollection) << "GarbageCollect() key: " << key; - std::vector<CookieMap::iterator> cookie_its; + CookieItVector cookie_its; num_deleted += GarbageCollectExpired( current, cookies_.equal_range(key), &cookie_its); - base::Time oldest_removed; - if (FindLeastRecentlyAccessed(kDomainMaxCookies, kDomainPurgeCookies, - &oldest_removed, &cookie_its)) { - // Delete in two passes so we can figure out what we're nuking - // that would be kept at the global level. - int num_subject_to_global_purge = - GarbageCollectDeleteList( - current, - Time::Now() - TimeDelta::FromDays(kSafeFromGlobalPurgeDays), - DELETE_COOKIE_EVICTED_DOMAIN_PRE_SAFE, - cookie_its); - num_deleted += num_subject_to_global_purge; - // Correct because FindLeastRecentlyAccessed returns a sorted list. - cookie_its.erase(cookie_its.begin(), - cookie_its.begin() + num_subject_to_global_purge); - num_deleted += - GarbageCollectDeleteList( - current, - Time(), - DELETE_COOKIE_EVICTED_DOMAIN_POST_SAFE, - cookie_its); + if (cookie_its.size() > kDomainMaxCookies) { + VLOG(kVlogGarbageCollection) << "Deep Garbage Collect domain."; + size_t purge_goal = + cookie_its.size() - (kDomainMaxCookies - kDomainPurgeCookies); + DCHECK(purge_goal > kDomainPurgeCookies); + + // Boundary iterators into |cookie_its| for different priorities. + CookieItVector::iterator it_bdd[4]; + // Intialize |it_bdd| while sorting |cookie_its| by priorities. + // Schematic: [MLLHMHHLMM] => [LLL|MMMM|HHH], with 4 boundaries. + it_bdd[0] = cookie_its.begin(); + it_bdd[3] = cookie_its.end(); + it_bdd[1] = PartitionCookieByPriority(it_bdd[0], it_bdd[3], + COOKIE_PRIORITY_LOW); + it_bdd[2] = PartitionCookieByPriority(it_bdd[1], it_bdd[3], + COOKIE_PRIORITY_MEDIUM); + size_t quota[3] = { + kDomainCookiesQuotaLow, + kDomainCookiesQuotaMedium, + kDomainCookiesQuotaHigh + }; + + // Purge domain cookies in 3 rounds. + // Round 1: consider low-priority cookies only: evict least-recently + // accessed, while protecting quota[0] of these from deletion. + // Round 2: consider {low, medium}-priority cookies, evict least-recently + // accessed, while protecting quota[0] + quota[1]. + // Round 3: consider all cookies, evict least-recently accessed. + size_t accumulated_quota = 0; + CookieItVector::iterator it_purge_begin = it_bdd[0]; + for (int i = 0; i < 3 && purge_goal > 0; ++i) { + accumulated_quota += quota[i]; + + // If we are not using priority, only do Round 3. This reproduces the + // old way of indiscriminately purging least-recently accessed cookies. + if (!priority_aware_garbage_collection_ && i < 2) + continue; + + size_t num_considered = it_bdd[i + 1] - it_purge_begin; + if (num_considered <= accumulated_quota) + continue; + + // Number of cookies that will be purged in this round. + size_t round_goal = + std::min(purge_goal, num_considered - accumulated_quota); + purge_goal -= round_goal; + + SortLeastRecentlyAccessed(it_purge_begin, it_bdd[i + 1], round_goal); + // Cookies accessed on or after |safe_date| would have been safe from + // global purge, and we want to keep track of this. + CookieItVector::iterator it_purge_end = it_purge_begin + round_goal; + CookieItVector::iterator it_purge_middle = + LowerBoundAccessDate(it_purge_begin, it_purge_end, safe_date); + // Delete cookies accessed before |safe_date|. + num_deleted += GarbageCollectDeleteRange( + current, + DELETE_COOKIE_EVICTED_DOMAIN_PRE_SAFE, + it_purge_begin, + it_purge_middle); + // Delete cookies accessed on or after |safe_date|. + num_deleted += GarbageCollectDeleteRange( + current, + DELETE_COOKIE_EVICTED_DOMAIN_POST_SAFE, + it_purge_middle, + it_purge_end); + it_purge_begin = it_purge_end; + } + DCHECK_EQ(0U, purge_goal); } } - // Collect garbage for everything. With firefox style we want to - // preserve cookies touched in kSafeFromGlobalPurgeDays, otherwise - // not. + // Collect garbage for everything. With firefox style we want to preserve + // cookies accessed in kSafeFromGlobalPurgeDays, otherwise evict. if (cookies_.size() > kMaxCookies && - (earliest_access_time_ < - Time::Now() - TimeDelta::FromDays(kSafeFromGlobalPurgeDays))) { + earliest_access_time_ < safe_date) { VLOG(kVlogGarbageCollection) << "GarbageCollect() everything"; - std::vector<CookieMap::iterator> cookie_its; - base::Time oldest_left; + CookieItVector cookie_its; num_deleted += GarbageCollectExpired( current, CookieMapItPair(cookies_.begin(), cookies_.end()), &cookie_its); - if (FindLeastRecentlyAccessed(kMaxCookies, kPurgeCookies, - &oldest_left, &cookie_its)) { - Time oldest_safe_cookie( - (Time::Now() - TimeDelta::FromDays(kSafeFromGlobalPurgeDays))); - int num_evicted = GarbageCollectDeleteList( + if (cookie_its.size() > kMaxCookies) { + VLOG(kVlogGarbageCollection) << "Deep Garbage Collect everything."; + size_t purge_goal = cookie_its.size() - (kMaxCookies - kPurgeCookies); + DCHECK(purge_goal > kPurgeCookies); + // Sorts up to *and including* |cookie_its[purge_goal]|, so + // |earliest_access_time| will be properly assigned even if + // |global_purge_it| == |cookie_its.begin() + purge_goal|. + SortLeastRecentlyAccessed(cookie_its.begin(), cookie_its.end(), + purge_goal); + // Find boundary to cookies older than safe_date. + CookieItVector::iterator global_purge_it = + LowerBoundAccessDate(cookie_its.begin(), + cookie_its.begin() + purge_goal, + safe_date); + // Only delete the old cookies. + num_deleted += GarbageCollectDeleteRange( current, - oldest_safe_cookie, DELETE_COOKIE_EVICTED_GLOBAL, - cookie_its); - - // If no cookies were preserved by the time limit, the global last - // access is set to the value returned from FindLeastRecentlyAccessed. - // If the time limit preserved some cookies, we use the last access of - // the oldest preserved cookie. - if (num_evicted == static_cast<int>(cookie_its.size())) { - earliest_access_time_ = oldest_left; - } else { - earliest_access_time_ = - (*(cookie_its.begin() + num_evicted))->second->LastAccessDate(); - } - num_deleted += num_evicted; + cookie_its.begin(), + global_purge_it); + // Set access day to the oldest cookie that wasn't deleted. + earliest_access_time_ = (*global_purge_it)->second->LastAccessDate(); } } @@ -1839,7 +1924,7 @@ int CookieMonster::GarbageCollect(const Time& current, int CookieMonster::GarbageCollectExpired( const Time& current, const CookieMapItPair& itpair, - std::vector<CookieMap::iterator>* cookie_its) { + CookieItVector* cookie_its) { if (keep_expired_cookies_) return 0; @@ -1861,23 +1946,17 @@ int CookieMonster::GarbageCollectExpired( return num_deleted; } -int CookieMonster::GarbageCollectDeleteList( +int CookieMonster::GarbageCollectDeleteRange( const Time& current, - const Time& keep_accessed_after, DeletionCause cause, - std::vector<CookieMap::iterator>& cookie_its) { - int num_deleted = 0; - for (std::vector<CookieMap::iterator>::iterator it = cookie_its.begin(); - it != cookie_its.end(); it++) { - if (keep_accessed_after.is_null() || - (*it)->second->LastAccessDate() < keep_accessed_after) { - histogram_evicted_last_access_minutes_->Add( - (current - (*it)->second->LastAccessDate()).InMinutes()); - InternalDeleteCookie((*it), true, cause); - num_deleted++; - } - } - return num_deleted; + CookieMonster::CookieItVector::iterator it_begin, + CookieMonster::CookieItVector::iterator it_end) { + for (CookieItVector::iterator it = it_begin; it != it_end; it++) { + histogram_evicted_last_access_minutes_->Add( + (current - (*it)->second->LastAccessDate()).InMinutes()); + InternalDeleteCookie((*it), true, cause); + } + return it_end - it_begin; } // A wrapper around RegistryControlledDomainService::GetDomainAndRegistry diff --git a/net/cookies/cookie_monster.h b/net/cookies/cookie_monster.h index bb7686e..c957539 100644 --- a/net/cookies/cookie_monster.h +++ b/net/cookies/cookie_monster.h @@ -106,6 +106,31 @@ class NET_EXPORT CookieMonster : public CookieStore { // subtantially more entries in the map. typedef std::multimap<std::string, CanonicalCookie*> CookieMap; typedef std::pair<CookieMap::iterator, CookieMap::iterator> CookieMapItPair; + typedef std::vector<CookieMap::iterator> CookieItVector; + + // Cookie garbage collection thresholds. Based off of the Mozilla defaults. + // When the number of cookies gets to k{Domain,}MaxCookies + // purge down to k{Domain,}MaxCookies - k{Domain,}PurgeCookies. + // 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 number of cookies. + // We're just going through the garbage collection process less often. + // Note that the DOMAIN values are per eTLD+1; see comment for the + // CookieMap typedef. So, e.g., the maximum number of cookies allowed for + // google.com and all of its subdomains will be 150-180. + // + // Any cookies accessed more recently than kSafeFromGlobalPurgeDays will not + // be evicted by global garbage collection, even if we have more than + // kMaxCookies. This does not affect domain garbage collection. + static const size_t kDomainMaxCookies; + static const size_t kDomainPurgeCookies; + static const size_t kMaxCookies; + static const size_t kPurgeCookies; + + // Quota for cookies with {low, medium, high} priorities within a domain. + static const size_t kDomainCookiesQuotaLow; + static const size_t kDomainCookiesQuotaMedium; + static const size_t kDomainCookiesQuotaHigh; // The store passed in should not have had Init() called on it yet. This // class will take care of initializing it. The backing store is NOT owned by @@ -255,6 +280,11 @@ class NET_EXPORT CookieMonster : public CookieStore { // (i.e. as part of the instance initialization process). void SetPersistSessionCookies(bool persist_session_cookies); + // Enables the new garbage collection algorithm where domain cookie eviction + // uses cookie priorities to decide which cookies to purge and which to keep. + void SetPriorityAwareGarbageCollection( + bool priority_aware_garbage_collection); + // Debugging method to perform various validation checks on the map. // Currently just checking that there are no null CanonicalCookie pointers // in the map. @@ -340,28 +370,6 @@ class NET_EXPORT CookieMonster : public CookieStore { DELETE_COOKIE_LAST_ENTRY }; - // Cookie garbage collection thresholds. Based off of the Mozilla defaults. - // When the number of cookies gets to k{Domain,}MaxCookies - // purge down to k{Domain,}MaxCookies - k{Domain,}PurgeCookies. - // 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. - // Note that the DOMAIN values are per eTLD+1; see comment for the - // CookieMap typedef. So, e.g., the maximum number of cookies allowed for - // google.com and all of its subdomains will be 150-180. - // - // Any cookies accessed more recently than kSafeFromGlobalPurgeDays will not - // be evicted by global garbage collection, even if we have more than - // kMaxCookies. This does not affect domain garbage collection. - // - // Present in .h file to make accessible to tests through FRIEND_TEST. - // Actual definitions are in cookie_monster.cc. - static const size_t kDomainMaxCookies; - static const size_t kDomainPurgeCookies; - static const size_t kMaxCookies; - static const size_t kPurgeCookies; - // The number of days since last access that cookies will not be subject // to global garbage collection. static const int kSafeFromGlobalPurgeDays; @@ -538,14 +546,12 @@ class NET_EXPORT CookieMonster : public CookieStore { const CookieMapItPair& itpair, std::vector<CookieMap::iterator>* cookie_its); - // Helper for GarbageCollect(). Deletes all cookies in the list - // that were accessed before |keep_accessed_after|, using DeletionCause - // |cause|. If |keep_accessed_after| is null, deletes all cookies in the - // list. Returns the number of cookies deleted. - int GarbageCollectDeleteList(const base::Time& current, - const base::Time& keep_accessed_after, - DeletionCause cause, - std::vector<CookieMap::iterator>& cookie_its); + // Helper for GarbageCollect(). Deletes all cookies in the range specified by + // [|it_begin|, |it_end|). Returns the number of cookies deleted. + int GarbageCollectDeleteRange(const base::Time& current, + DeletionCause cause, + CookieItVector::iterator cookie_its_begin, + CookieItVector::iterator cookie_its_end); // Find the key (for lookup in cookies_) based on the given domain. // See comment on keys before the CookieMap typedef. @@ -650,6 +656,7 @@ class NET_EXPORT CookieMonster : public CookieStore { bool keep_expired_cookies_; bool persist_session_cookies_; + bool priority_aware_garbage_collection_; // Static setting for whether or not file scheme cookies are allows when // a new CookieMonster is created, or the accepted schemes on a CookieMonster diff --git a/net/cookies/cookie_monster_unittest.cc b/net/cookies/cookie_monster_unittest.cc index 9034975..df4fa9d 100644 --- a/net/cookies/cookie_monster_unittest.cc +++ b/net/cookies/cookie_monster_unittest.cc @@ -4,7 +4,9 @@ #include "net/cookies/cookie_store_unittest.h" +#include <algorithm> #include <string> +#include <vector> #include "base/basictypes.h" #include "base/bind.h" @@ -14,6 +16,9 @@ #include "base/metrics/histogram.h" #include "base/metrics/histogram_samples.h" #include "base/stringprintf.h" +#include "base/strings/string_number_conversions.h" +#include "base/strings/string_piece.h" +#include "base/strings/string_split.h" #include "base/strings/string_tokenizer.h" #include "base/threading/thread.h" #include "base/time.h" @@ -357,9 +362,9 @@ class CookieMonsterTest : public CookieStoreTest<CookieMonsterTestTraits> { return std::count(str.begin(), str.end(), c); } - void TestHostGarbageCollectHelper( - int domain_max_cookies, - int domain_purge_cookies) { + void TestHostGarbageCollectHelper() { + int domain_max_cookies = CookieMonster::kDomainMaxCookies; + int domain_purge_cookies = CookieMonster::kDomainPurgeCookies; const int more_than_enough_cookies = (domain_max_cookies + domain_purge_cookies) * 2; // Add a bunch of cookies on a single host, should purge them. @@ -402,12 +407,159 @@ class CookieMonsterTest : public CookieStoreTest<CookieMonsterTestTraits> { std::string cookies_specific = this->GetCookies(cm, url_google_specific); int total_cookies = (CountInString(cookies_general, '=') + CountInString(cookies_specific, '=')); - EXPECT_GE(total_cookies, - domain_max_cookies - domain_purge_cookies); + EXPECT_GE(total_cookies, domain_max_cookies - domain_purge_cookies); EXPECT_LE(total_cookies, domain_max_cookies); } } + CookiePriority CharToPriority(char ch) { + switch (ch) { + case 'L': + return COOKIE_PRIORITY_LOW; + case 'M': + return COOKIE_PRIORITY_MEDIUM; + case 'H': + return COOKIE_PRIORITY_HIGH; + } + NOTREACHED(); + return COOKIE_PRIORITY_DEFAULT; + } + + // Instantiates a CookieMonster, adds multiple cookies (to url_google_) with + // priorities specified by |coded_priority_str|, and tests priority-aware + // domain cookie eviction. + // |coded_priority_str| specifies a run-length-encoded string of priorities. + // Example: "2M 3L M 4H" means "MMLLLMHHHH", and speicifies sequential (i.e., + // from least- to most-recently accessed) insertion of 2 medium-priority + // cookies, 3 low-priority cookies, 1 medium-priority cookie, and 4 + // high-priority cookies. + // Within each priority, only the least-accessed cookies should be evicted. + // Thus, to describe expected suriving cookies, it suffices to specify the + // expected population of surviving cookies per priority, i.e., + // |expected_low_count|, |expected_medium_count|, and |expected_high_count|. + void TestPriorityCookieCase(CookieMonster* cm, + const std::string& coded_priority_str, + size_t expected_low_count, + size_t expected_medium_count, + size_t expected_high_count) { + DeleteAll(cm); + int next_cookie_id = 0; + std::vector<CookiePriority> priority_list; + std::vector<int> id_list[3]; // Indexed by CookiePriority. + + // Parse |coded_priority_str| and add cookies. + std::vector<std::string> priority_tok_list; + base::SplitString(coded_priority_str, ' ', &priority_tok_list); + for (std::vector<std::string>::iterator it = priority_tok_list.begin(); + it != priority_tok_list.end(); ++it) { + size_t len = it->length(); + DCHECK_NE(len, 0U); + // Take last character as priority. + CookiePriority priority = CharToPriority((*it)[len - 1]); + std::string priority_str = CookiePriorityToString(priority); + // The rest of the string (possibly empty) specifies repetition. + int rep = 1; + if (!it->empty()) { + bool result = base::StringToInt( + base::StringPiece(it->begin(), it->end() - 1), &rep); + DCHECK(result); + } + for (; rep > 0; --rep, ++next_cookie_id) { + std::string cookie = base::StringPrintf( + "a%d=b;priority=%s", next_cookie_id, priority_str.c_str()); + EXPECT_TRUE(SetCookie(cm, url_google_, cookie)); + priority_list.push_back(priority); + id_list[priority].push_back(next_cookie_id); + } + } + + int num_cookies = static_cast<int>(priority_list.size()); + std::vector<int> surviving_id_list[3]; // Indexed by CookiePriority. + + // Parse the list of cookies + std::string cookie_str = this->GetCookies(cm, url_google_); + std::vector<std::string> cookie_tok_list; + base::SplitString(cookie_str, ';', &cookie_tok_list); + for (std::vector<std::string>::iterator it = cookie_tok_list.begin(); + it != cookie_tok_list.end(); ++it) { + // Assuming *it is "a#=b", so extract and parse "#" portion. + int id = -1; + bool result = base::StringToInt( + base::StringPiece(it->begin() + 1, it->end() - 2), &id); + DCHECK(result); + DCHECK_GE(id, 0); + DCHECK_LT(id, num_cookies); + surviving_id_list[priority_list[id]].push_back(id); + } + + // Validate each priority. + size_t expected_count[3] = { + expected_low_count, expected_medium_count, expected_high_count + }; + for (int i = 0; i < 3; ++i) { + DCHECK_LE(surviving_id_list[i].size(), id_list[i].size()); + EXPECT_EQ(expected_count[i], surviving_id_list[i].size()); + // Verify that the remaining cookies are the most recent among those + // with the same priorities. + if (expected_count[i] == surviving_id_list[i].size()) { + std::sort(surviving_id_list[i].begin(), surviving_id_list[i].end()); + EXPECT_TRUE(std::equal(surviving_id_list[i].begin(), + surviving_id_list[i].end(), + id_list[i].end() - expected_count[i])); + } + } + } + + void TestPriorityAwareGarbageCollectHelper() { + // Hard-coding limits in the test, but use DCHECK_EQ to enforce constraint. + DCHECK_EQ(180U, CookieMonster::kDomainMaxCookies); + DCHECK_EQ(150U, CookieMonster::kDomainMaxCookies - + CookieMonster::kDomainPurgeCookies); + DCHECK_EQ(30U, CookieMonster::kDomainCookiesQuotaLow); + DCHECK_EQ(50U, CookieMonster::kDomainCookiesQuotaMedium); + DCHECK_EQ(70U, CookieMonster::kDomainCookiesQuotaHigh); + + scoped_refptr<CookieMonster> cm(new CookieMonster(NULL, NULL)); + cm->SetPriorityAwareGarbageCollection(true); + + // Each test case adds 181 cookies, so 31 cookies are evicted. + // Cookie same priority, repeated for each priority. + TestPriorityCookieCase(cm, "181L", 150U, 0U, 0U); + TestPriorityCookieCase(cm, "181M", 0U, 150U, 0U); + TestPriorityCookieCase(cm, "181H", 0U, 0U, 150U); + + // Pairwise scenarios. + // Round 1 => none; round2 => 31M; round 3 => none. + TestPriorityCookieCase(cm, "10H 171M", 0U, 140U, 10U); + // Round 1 => 10L; round2 => 21M; round 3 => none. + TestPriorityCookieCase(cm, "141M 40L", 30U, 120U, 0U); + // Round 1 => none; round2 => none; round 3 => 31H. + TestPriorityCookieCase(cm, "101H 80M", 0U, 80U, 70U); + + // For {low, medium} priorities right on quota, different orders. + // Round 1 => 1L; round 2 => none, round3 => 30L. + TestPriorityCookieCase(cm, "31L 50M 100H", 0U, 50U, 100U); + // Round 1 => none; round 2 => 1M, round3 => 30M. + TestPriorityCookieCase(cm, "51M 100H 30L", 30U, 20U, 100U); + // Round 1 => none; round 2 => none; round3 => 31H. + TestPriorityCookieCase(cm, "101H 50M 30L", 30U, 50U, 70U); + + // Round 1 => 10L; round 2 => 10M; round3 => 11H. + TestPriorityCookieCase(cm, "81H 60M 40L", 30U, 50U, 70U); + + // More complex scenarios. + // Round 1 => 10L; round 2 => 10M; round 3 => 11H. + TestPriorityCookieCase(cm, "21H 60M 40L 60H", 30U, 50U, 70U); + // Round 1 => 10L; round 2 => 11M, 10L; round 3 => none. + TestPriorityCookieCase(cm, "11H 10M 20L 110M 20L 10H", 20U, 109U, 21U); + // Round 1 => none; round 2 => none; round 3 => 11L, 10M, 10H. + TestPriorityCookieCase(cm, "11L 10M 140H 10M 10L", 10U, 10U, 130U); + // Round 1 => none; round 2 => 1M; round 3 => 10L, 10M, 10H. + TestPriorityCookieCase(cm, "11M 10H 10L 60M 90H", 0U, 60U, 90U); + // Round 1 => none; round 2 => 10L, 21M; round 3 => none. + TestPriorityCookieCase(cm, "11M 10H 10L 90M 60H", 0U, 80U, 70U); + } + // Function for creating a CM with a number of cookies in it, // no store (and hence no ability to affect access time). CookieMonster* CreateMonsterForGC(int num_cookies) { @@ -561,8 +713,8 @@ class DeferredCookieTaskTest : public CookieMonsterTest { // Defines a cookie to be returned from PersistentCookieStore::Load void DeclareLoadedCookie(const std::string& key, - const std::string& cookie_line, - const base::Time& creation_time) { + const std::string& cookie_line, + const base::Time& creation_time) { AddCookieToList(key, cookie_line, creation_time, &loaded_cookies_); } @@ -1011,8 +1163,11 @@ TEST_F(CookieMonsterTest, TestLastAccess) { } TEST_F(CookieMonsterTest, TestHostGarbageCollection) { - TestHostGarbageCollectHelper( - CookieMonster::kDomainMaxCookies, CookieMonster::kDomainPurgeCookies); + TestHostGarbageCollectHelper(); +} + +TEST_F(CookieMonsterTest, TestPriorityAwareGarbageCollection) { + TestPriorityAwareGarbageCollectHelper(); } TEST_F(CookieMonsterTest, TestDeleteSingleCookie) { |