webkit/browser/quota/usage_tracker.cc

   1 // Copyright 2013 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 "webkit/browser/quota/usage_tracker.h"
   6
   7 #include <algorithm>
   8 #include <deque>
   9 #include <set>
  10 #include <string>
  11 #include <vector>
  12
  13 #include "base/bind.h"
  14 #include "base/message_loop/message_loop_proxy.h"
  15 #include "base/stl_util.h"
  16 #include "net/base/net_util.h"
  17 #include "webkit/browser/quota/storage_monitor.h"
  18 #include "webkit/browser/quota/storage_observer.h"
  19
  20 namespace quota {
  21
  22 namespace {
  23
  24 typedef ClientUsageTracker::OriginUsageAccumulator OriginUsageAccumulator;
  25 typedef ClientUsageTracker::OriginSetByHost OriginSetByHost;
  26
  27 void DidGetOriginUsage(const OriginUsageAccumulator& accumulator,
  28                        const GURL& origin,
  29                        int64 usage) {
  30   accumulator.Run(origin, usage);
  31 }
  32
  33 void DidGetHostUsage(const UsageCallback& callback,
  34                      int64 limited_usage,
  35                      int64 unlimited_usage) {
  36   DCHECK_GE(limited_usage, 0);
  37   DCHECK_GE(unlimited_usage, 0);
  38   callback.Run(limited_usage + unlimited_usage);
  39 }
  40
  41 bool EraseOriginFromOriginSet(OriginSetByHost* origins_by_host,
  42                               const std::string& host,
  43                               const GURL& origin) {
  44   OriginSetByHost::iterator found = origins_by_host->find(host);
  45   if (found == origins_by_host->end())
  46     return false;
  47
  48   if (!found->second.erase(origin))
  49     return false;
  50
  51   if (found->second.empty())
  52     origins_by_host->erase(host);
  53   return true;
  54 }
  55
  56 bool OriginSetContainsOrigin(const OriginSetByHost& origins,
  57                              const std::string& host,
  58                              const GURL& origin) {
  59   OriginSetByHost::const_iterator itr = origins.find(host);
  60   return itr != origins.end() && ContainsKey(itr->second, origin);
  61 }
  62
  63 void DidGetGlobalUsageForLimitedGlobalUsage(const UsageCallback& callback,
  64                                             int64 total_global_usage,
  65                                             int64 global_unlimited_usage) {
  66   callback.Run(total_global_usage - global_unlimited_usage);
  67 }
  68
  69 }  // namespace
  70
  71 // UsageTracker ----------------------------------------------------------
  72
  73 UsageTracker::UsageTracker(const QuotaClientList& clients,
  74                            StorageType type,
  75                            SpecialStoragePolicy* special_storage_policy,
  76                            StorageMonitor* storage_monitor)
  77     : type_(type),
  78       storage_monitor_(storage_monitor),
  79       weak_factory_(this) {
  80   for (QuotaClientList::const_iterator iter = clients.begin();
  81       iter != clients.end();
  82       ++iter) {
  83     if ((*iter)->DoesSupport(type)) {
  84       client_tracker_map_[(*iter)->id()] =
  85           new ClientUsageTracker(this, *iter, type, special_storage_policy,
  86                                  storage_monitor_);
  87     }
  88   }
  89 }
  90
  91 UsageTracker::~UsageTracker() {
  92   STLDeleteValues(&client_tracker_map_);
  93 }
  94
  95 ClientUsageTracker* UsageTracker::GetClientTracker(QuotaClient::ID client_id) {
  96   ClientTrackerMap::iterator found = client_tracker_map_.find(client_id);
  97   if (found != client_tracker_map_.end())
  98     return found->second;
  99   return NULL;
 100 }
 101
 102 void UsageTracker::GetGlobalLimitedUsage(const UsageCallback& callback) {
 103   if (global_usage_callbacks_.HasCallbacks()) {
 104     global_usage_callbacks_.Add(base::Bind(
 105         &DidGetGlobalUsageForLimitedGlobalUsage, callback));
 106     return;
 107   }
 108
 109   if (!global_limited_usage_callbacks_.Add(callback))
 110     return;
 111
 112   AccumulateInfo* info = new AccumulateInfo;
 113   // Calling GetGlobalLimitedUsage(accumulator) may synchronously
 114   // return if the usage is cached, which may in turn dispatch
 115   // the completion callback before we finish looping over
 116   // all clients (because info->pending_clients may reach 0
 117   // during the loop).
 118   // To avoid this, we add one more pending client as a sentinel
 119   // and fire the sentinel callback at the end.
 120   info->pending_clients = client_tracker_map_.size() + 1;
 121   UsageCallback accumulator = base::Bind(
 122       &UsageTracker::AccumulateClientGlobalLimitedUsage,
 123       weak_factory_.GetWeakPtr(), base::Owned(info));
 124
 125   for (ClientTrackerMap::iterator iter = client_tracker_map_.begin();
 126        iter != client_tracker_map_.end();
 127        ++iter)
 128     iter->second->GetGlobalLimitedUsage(accumulator);
 129
 130   // Fire the sentinel as we've now called GetGlobalUsage for all clients.
 131   accumulator.Run(0);
 132 }
 133
 134 void UsageTracker::GetGlobalUsage(const GlobalUsageCallback& callback) {
 135   if (!global_usage_callbacks_.Add(callback))
 136     return;
 137
 138   AccumulateInfo* info = new AccumulateInfo;
 139   // Calling GetGlobalUsage(accumulator) may synchronously
 140   // return if the usage is cached, which may in turn dispatch
 141   // the completion callback before we finish looping over
 142   // all clients (because info->pending_clients may reach 0
 143   // during the loop).
 144   // To avoid this, we add one more pending client as a sentinel
 145   // and fire the sentinel callback at the end.
 146   info->pending_clients = client_tracker_map_.size() + 1;
 147   GlobalUsageCallback accumulator = base::Bind(
 148       &UsageTracker::AccumulateClientGlobalUsage, weak_factory_.GetWeakPtr(),
 149       base::Owned(info));
 150
 151   for (ClientTrackerMap::iterator iter = client_tracker_map_.begin();
 152        iter != client_tracker_map_.end();
 153        ++iter)
 154     iter->second->GetGlobalUsage(accumulator);
 155
 156   // Fire the sentinel as we've now called GetGlobalUsage for all clients.
 157   accumulator.Run(0, 0);
 158 }
 159
 160 void UsageTracker::GetHostUsage(const std::string& host,
 161                                 const UsageCallback& callback) {
 162   if (!host_usage_callbacks_.Add(host, callback))
 163     return;
 164
 165   AccumulateInfo* info = new AccumulateInfo;
 166   // Calling GetHostUsage(accumulator) may synchronously
 167   // return if the usage is cached, which may in turn dispatch
 168   // the completion callback before we finish looping over
 169   // all clients (because info->pending_clients may reach 0
 170   // during the loop).
 171   // To avoid this, we add one more pending client as a sentinel
 172   // and fire the sentinel callback at the end.
 173   info->pending_clients = client_tracker_map_.size() + 1;
 174   UsageCallback accumulator = base::Bind(
 175       &UsageTracker::AccumulateClientHostUsage, weak_factory_.GetWeakPtr(),
 176       base::Owned(info), host);
 177
 178   for (ClientTrackerMap::iterator iter = client_tracker_map_.begin();
 179        iter != client_tracker_map_.end();
 180        ++iter)
 181     iter->second->GetHostUsage(host, accumulator);
 182
 183   // Fire the sentinel as we've now called GetHostUsage for all clients.
 184   accumulator.Run(0);
 185 }
 186
 187 void UsageTracker::UpdateUsageCache(
 188     QuotaClient::ID client_id, const GURL& origin, int64 delta) {
 189   ClientUsageTracker* client_tracker = GetClientTracker(client_id);
 190   DCHECK(client_tracker);
 191   client_tracker->UpdateUsageCache(origin, delta);
 192 }
 193
 194 void UsageTracker::GetCachedHostsUsage(
 195     std::map<std::string, int64>* host_usage) const {
 196   DCHECK(host_usage);
 197   host_usage->clear();
 198   for (ClientTrackerMap::const_iterator iter = client_tracker_map_.begin();
 199        iter != client_tracker_map_.end(); ++iter) {
 200     iter->second->GetCachedHostsUsage(host_usage);
 201   }
 202 }
 203
 204 void UsageTracker::GetCachedOrigins(std::set<GURL>* origins) const {
 205   DCHECK(origins);
 206   origins->clear();
 207   for (ClientTrackerMap::const_iterator iter = client_tracker_map_.begin();
 208        iter != client_tracker_map_.end(); ++iter) {
 209     iter->second->GetCachedOrigins(origins);
 210   }
 211 }
 212
 213 void UsageTracker::SetUsageCacheEnabled(QuotaClient::ID client_id,
 214                                         const GURL& origin,
 215                                         bool enabled) {
 216   ClientUsageTracker* client_tracker = GetClientTracker(client_id);
 217   DCHECK(client_tracker);
 218
 219   client_tracker->SetUsageCacheEnabled(origin, enabled);
 220 }
 221
 222 void UsageTracker::AccumulateClientGlobalLimitedUsage(AccumulateInfo* info,
 223                                                       int64 limited_usage) {
 224   info->usage += limited_usage;
 225   if (--info->pending_clients)
 226     return;
 227
 228   // All the clients have returned their usage data.  Dispatch the
 229   // pending callbacks.
 230   global_limited_usage_callbacks_.Run(MakeTuple(info->usage));
 231 }
 232
 233 void UsageTracker::AccumulateClientGlobalUsage(AccumulateInfo* info,
 234                                                int64 usage,
 235                                                int64 unlimited_usage) {
 236   info->usage += usage;
 237   info->unlimited_usage += unlimited_usage;
 238   if (--info->pending_clients)
 239     return;
 240
 241   // Defend against confusing inputs from clients.
 242   if (info->usage < 0)
 243     info->usage = 0;
 244
 245   // TODO(michaeln): The unlimited number is not trustworthy, it
 246   // can get out of whack when apps are installed or uninstalled.
 247   if (info->unlimited_usage > info->usage)
 248     info->unlimited_usage = info->usage;
 249   else if (info->unlimited_usage < 0)
 250     info->unlimited_usage = 0;
 251
 252   // All the clients have returned their usage data.  Dispatch the
 253   // pending callbacks.
 254   global_usage_callbacks_.Run(MakeTuple(info->usage, info->unlimited_usage));
 255 }
 256
 257 void UsageTracker::AccumulateClientHostUsage(AccumulateInfo* info,
 258                                              const std::string& host,
 259                                              int64 usage) {
 260   info->usage += usage;
 261   if (--info->pending_clients)
 262     return;
 263
 264   // Defend against confusing inputs from clients.
 265   if (info->usage < 0)
 266     info->usage = 0;
 267
 268   // All the clients have returned their usage data.  Dispatch the
 269   // pending callbacks.
 270   host_usage_callbacks_.Run(host, MakeTuple(info->usage));
 271 }
 272
 273 // ClientUsageTracker ----------------------------------------------------
 274
 275 ClientUsageTracker::ClientUsageTracker(
 276     UsageTracker* tracker, QuotaClient* client, StorageType type,
 277     SpecialStoragePolicy* special_storage_policy,
 278     StorageMonitor* storage_monitor)
 279     : tracker_(tracker),
 280       client_(client),
 281       type_(type),
 282       storage_monitor_(storage_monitor),
 283       global_limited_usage_(0),
 284       global_unlimited_usage_(0),
 285       global_usage_retrieved_(false),
 286       special_storage_policy_(special_storage_policy) {
 287   DCHECK(tracker_);
 288   DCHECK(client_);
 289   if (special_storage_policy_.get())
 290     special_storage_policy_->AddObserver(this);
 291 }
 292
 293 ClientUsageTracker::~ClientUsageTracker() {
 294   if (special_storage_policy_.get())
 295     special_storage_policy_->RemoveObserver(this);
 296 }
 297
 298 void ClientUsageTracker::GetGlobalLimitedUsage(const UsageCallback& callback) {
 299   if (!global_usage_retrieved_) {
 300     GetGlobalUsage(base::Bind(&DidGetGlobalUsageForLimitedGlobalUsage,
 301                               callback));
 302     return;
 303   }
 304
 305   if (non_cached_limited_origins_by_host_.empty()) {
 306     callback.Run(global_limited_usage_);
 307     return;
 308   }
 309
 310   AccumulateInfo* info = new AccumulateInfo;
 311   info->pending_jobs = non_cached_limited_origins_by_host_.size() + 1;
 312   UsageCallback accumulator = base::Bind(
 313       &ClientUsageTracker::AccumulateLimitedOriginUsage, AsWeakPtr(),
 314       base::Owned(info), callback);
 315
 316   for (OriginSetByHost::iterator host_itr =
 317            non_cached_limited_origins_by_host_.begin();
 318        host_itr != non_cached_limited_origins_by_host_.end(); ++host_itr) {
 319     for (std::set<GURL>::iterator origin_itr = host_itr->second.begin();
 320          origin_itr != host_itr->second.end(); ++origin_itr)
 321       client_->GetOriginUsage(*origin_itr, type_, accumulator);
 322   }
 323
 324   accumulator.Run(global_limited_usage_);
 325 }
 326
 327 void ClientUsageTracker::GetGlobalUsage(const GlobalUsageCallback& callback) {
 328   if (global_usage_retrieved_ &&
 329       non_cached_limited_origins_by_host_.empty() &&
 330       non_cached_unlimited_origins_by_host_.empty()) {
 331     callback.Run(global_limited_usage_ + global_unlimited_usage_,
 332                  global_unlimited_usage_);
 333     return;
 334   }
 335
 336   client_->GetOriginsForType(type_, base::Bind(
 337       &ClientUsageTracker::DidGetOriginsForGlobalUsage, AsWeakPtr(),
 338       callback));
 339 }
 340
 341 void ClientUsageTracker::GetHostUsage(
 342     const std::string& host, const UsageCallback& callback) {
 343   if (ContainsKey(cached_hosts_, host) &&
 344       !ContainsKey(non_cached_limited_origins_by_host_, host) &&
 345       !ContainsKey(non_cached_unlimited_origins_by_host_, host)) {
 346     // TODO(kinuko): Drop host_usage_map_ cache periodically.
 347     callback.Run(GetCachedHostUsage(host));
 348     return;
 349   }
 350
 351   if (!host_usage_accumulators_.Add(
 352           host, base::Bind(&DidGetHostUsage, callback)))
 353     return;
 354   client_->GetOriginsForHost(type_, host, base::Bind(
 355       &ClientUsageTracker::DidGetOriginsForHostUsage, AsWeakPtr(), host));
 356 }
 357
 358 void ClientUsageTracker::UpdateUsageCache(
 359     const GURL& origin, int64 delta) {
 360   std::string host = net::GetHostOrSpecFromURL(origin);
 361   if (cached_hosts_.find(host) != cached_hosts_.end()) {
 362     if (!IsUsageCacheEnabledForOrigin(origin))
 363       return;
 364
 365     cached_usage_by_host_[host][origin] += delta;
 366     if (IsStorageUnlimited(origin))
 367       global_unlimited_usage_ += delta;
 368     else
 369       global_limited_usage_ += delta;
 370     DCHECK_GE(cached_usage_by_host_[host][origin], 0);
 371     DCHECK_GE(global_limited_usage_, 0);
 372
 373     // Notify the usage monitor that usage has changed. The storage monitor may
 374     // be NULL during tests.
 375     if (storage_monitor_) {
 376       StorageObserver::Filter filter(type_, origin);
 377       storage_monitor_->NotifyUsageChange(filter, delta);
 378     }
 379     return;
 380   }
 381
 382   // We don't know about this host yet, so populate our cache for it.
 383   GetHostUsage(host, base::Bind(&ClientUsageTracker::DidGetHostUsageAfterUpdate,
 384                                 AsWeakPtr(), origin));
 385 }
 386
 387 void ClientUsageTracker::GetCachedHostsUsage(
 388     std::map<std::string, int64>* host_usage) const {
 389   DCHECK(host_usage);
 390   for (HostUsageMap::const_iterator host_iter = cached_usage_by_host_.begin();
 391        host_iter != cached_usage_by_host_.end(); host_iter++) {
 392     const std::string& host = host_iter->first;
 393     (*host_usage)[host] += GetCachedHostUsage(host);
 394   }
 395 }
 396
 397 void ClientUsageTracker::GetCachedOrigins(std::set<GURL>* origins) const {
 398   DCHECK(origins);
 399   for (HostUsageMap::const_iterator host_iter = cached_usage_by_host_.begin();
 400        host_iter != cached_usage_by_host_.end(); host_iter++) {
 401     const UsageMap& origin_map = host_iter->second;
 402     for (UsageMap::const_iterator origin_iter = origin_map.begin();
 403          origin_iter != origin_map.end(); origin_iter++) {
 404       origins->insert(origin_iter->first);
 405     }
 406   }
 407 }
 408
 409 void ClientUsageTracker::SetUsageCacheEnabled(const GURL& origin,
 410                                               bool enabled) {
 411   std::string host = net::GetHostOrSpecFromURL(origin);
 412   if (!enabled) {
 413     // Erase |origin| from cache and subtract its usage.
 414     HostUsageMap::iterator found_host = cached_usage_by_host_.find(host);
 415     if (found_host != cached_usage_by_host_.end()) {
 416       UsageMap& cached_usage_for_host = found_host->second;
 417
 418       UsageMap::iterator found = cached_usage_for_host.find(origin);
 419       if (found != cached_usage_for_host.end()) {
 420         int64 usage = found->second;
 421         UpdateUsageCache(origin, -usage);
 422         cached_usage_for_host.erase(found);
 423         if (cached_usage_for_host.empty()) {
 424           cached_usage_by_host_.erase(found_host);
 425           cached_hosts_.erase(host);
 426         }
 427       }
 428     }
 429
 430     if (IsStorageUnlimited(origin))
 431       non_cached_unlimited_origins_by_host_[host].insert(origin);
 432     else
 433       non_cached_limited_origins_by_host_[host].insert(origin);
 434   } else {
 435     // Erase |origin| from |non_cached_origins_| and invalidate the usage cache
 436     // for the host.
 437     if (EraseOriginFromOriginSet(&non_cached_limited_origins_by_host_,
 438                                  host, origin) ||
 439         EraseOriginFromOriginSet(&non_cached_unlimited_origins_by_host_,
 440                                  host, origin)) {
 441       cached_hosts_.erase(host);
 442       global_usage_retrieved_ = false;
 443     }
 444   }
 445 }
 446
 447 void ClientUsageTracker::AccumulateLimitedOriginUsage(
 448     AccumulateInfo* info,
 449     const UsageCallback& callback,
 450     int64 usage) {
 451   info->limited_usage += usage;
 452   if (--info->pending_jobs)
 453     return;
 454
 455   callback.Run(info->limited_usage);
 456 }
 457
 458 void ClientUsageTracker::DidGetOriginsForGlobalUsage(
 459     const GlobalUsageCallback& callback,
 460     const std::set<GURL>& origins) {
 461   OriginSetByHost origins_by_host;
 462   for (std::set<GURL>::const_iterator itr = origins.begin();
 463        itr != origins.end(); ++itr)
 464     origins_by_host[net::GetHostOrSpecFromURL(*itr)].insert(*itr);
 465
 466   AccumulateInfo* info = new AccumulateInfo;
 467   // Getting host usage may synchronously return the result if the usage is
 468   // cached, which may in turn dispatch the completion callback before we finish
 469   // looping over all hosts (because info->pending_jobs may reach 0 during the
 470   // loop).  To avoid this, we add one more pending host as a sentinel and
 471   // fire the sentinel callback at the end.
 472   info->pending_jobs = origins_by_host.size() + 1;
 473   HostUsageAccumulator accumulator =
 474       base::Bind(&ClientUsageTracker::AccumulateHostUsage, AsWeakPtr(),
 475                  base::Owned(info), callback);
 476
 477   for (OriginSetByHost::iterator itr = origins_by_host.begin();
 478        itr != origins_by_host.end(); ++itr) {
 479     if (host_usage_accumulators_.Add(itr->first, accumulator))
 480       GetUsageForOrigins(itr->first, itr->second);
 481   }
 482
 483   // Fire the sentinel as we've now called GetUsageForOrigins for all clients.
 484   accumulator.Run(0, 0);
 485 }
 486
 487 void ClientUsageTracker::AccumulateHostUsage(
 488     AccumulateInfo* info,
 489     const GlobalUsageCallback& callback,
 490     int64 limited_usage,
 491     int64 unlimited_usage) {
 492   info->limited_usage += limited_usage;
 493   info->unlimited_usage += unlimited_usage;
 494   if (--info->pending_jobs)
 495     return;
 496
 497   DCHECK_GE(info->limited_usage, 0);
 498   DCHECK_GE(info->unlimited_usage, 0);
 499
 500   global_usage_retrieved_ = true;
 501   callback.Run(info->limited_usage + info->unlimited_usage,
 502                info->unlimited_usage);
 503 }
 504
 505 void ClientUsageTracker::DidGetOriginsForHostUsage(
 506     const std::string& host,
 507     const std::set<GURL>& origins) {
 508   GetUsageForOrigins(host, origins);
 509 }
 510
 511 void ClientUsageTracker::GetUsageForOrigins(
 512     const std::string& host,
 513     const std::set<GURL>& origins) {
 514   AccumulateInfo* info = new AccumulateInfo;
 515   // Getting origin usage may synchronously return the result if the usage is
 516   // cached, which may in turn dispatch the completion callback before we finish
 517   // looping over all origins (because info->pending_jobs may reach 0 during the
 518   // loop).  To avoid this, we add one more pending origin as a sentinel and
 519   // fire the sentinel callback at the end.
 520   info->pending_jobs = origins.size() + 1;
 521   OriginUsageAccumulator accumulator =
 522       base::Bind(&ClientUsageTracker::AccumulateOriginUsage, AsWeakPtr(),
 523                  base::Owned(info), host);
 524
 525   for (std::set<GURL>::const_iterator itr = origins.begin();
 526        itr != origins.end(); ++itr) {
 527     DCHECK_EQ(host, net::GetHostOrSpecFromURL(*itr));
 528
 529     int64 origin_usage = 0;
 530     if (GetCachedOriginUsage(*itr, &origin_usage)) {
 531       accumulator.Run(*itr, origin_usage);
 532     } else {
 533       client_->GetOriginUsage(*itr, type_, base::Bind(
 534           &DidGetOriginUsage, accumulator, *itr));
 535     }
 536   }
 537
 538   // Fire the sentinel as we've now called GetOriginUsage for all clients.
 539   accumulator.Run(GURL(), 0);
 540 }
 541
 542 void ClientUsageTracker::AccumulateOriginUsage(AccumulateInfo* info,
 543                                                const std::string& host,
 544                                                const GURL& origin,
 545                                                int64 usage) {
 546   if (!origin.is_empty()) {
 547     if (usage < 0)
 548       usage = 0;
 549
 550     if (IsStorageUnlimited(origin))
 551       info->unlimited_usage += usage;
 552     else
 553       info->limited_usage += usage;
 554     if (IsUsageCacheEnabledForOrigin(origin))
 555       AddCachedOrigin(origin, usage);
 556   }
 557   if (--info->pending_jobs)
 558     return;
 559
 560   AddCachedHost(host);
 561   host_usage_accumulators_.Run(
 562       host, MakeTuple(info->limited_usage, info->unlimited_usage));
 563 }
 564
 565 void ClientUsageTracker::DidGetHostUsageAfterUpdate(
 566     const GURL& origin, int64 usage) {
 567   if (!storage_monitor_)
 568     return;
 569
 570   StorageObserver::Filter filter(type_, origin);
 571   storage_monitor_->NotifyUsageChange(filter, 0);
 572 }
 573
 574 void ClientUsageTracker::AddCachedOrigin(
 575     const GURL& origin, int64 new_usage) {
 576   DCHECK(IsUsageCacheEnabledForOrigin(origin));
 577
 578   std::string host = net::GetHostOrSpecFromURL(origin);
 579   int64* usage = &cached_usage_by_host_[host][origin];
 580   int64 delta = new_usage - *usage;
 581   *usage = new_usage;
 582   if (delta) {
 583     if (IsStorageUnlimited(origin))
 584       global_unlimited_usage_ += delta;
 585     else
 586       global_limited_usage_ += delta;
 587   }
 588   DCHECK_GE(*usage, 0);
 589   DCHECK_GE(global_limited_usage_, 0);
 590 }
 591
 592 void ClientUsageTracker::AddCachedHost(const std::string& host) {
 593   cached_hosts_.insert(host);
 594 }
 595
 596 int64 ClientUsageTracker::GetCachedHostUsage(const std::string& host) const {
 597   HostUsageMap::const_iterator found = cached_usage_by_host_.find(host);
 598   if (found == cached_usage_by_host_.end())
 599     return 0;
 600
 601   int64 usage = 0;
 602   const UsageMap& map = found->second;
 603   for (UsageMap::const_iterator iter = map.begin();
 604        iter != map.end(); ++iter) {
 605     usage += iter->second;
 606   }
 607   return usage;
 608 }
 609
 610 bool ClientUsageTracker::GetCachedOriginUsage(
 611     const GURL& origin,
 612     int64* usage) const {
 613   std::string host = net::GetHostOrSpecFromURL(origin);
 614   HostUsageMap::const_iterator found_host = cached_usage_by_host_.find(host);
 615   if (found_host == cached_usage_by_host_.end())
 616     return false;
 617
 618   UsageMap::const_iterator found = found_host->second.find(origin);
 619   if (found == found_host->second.end())
 620     return false;
 621
 622   DCHECK(IsUsageCacheEnabledForOrigin(origin));
 623   *usage = found->second;
 624   return true;
 625 }
 626
 627 bool ClientUsageTracker::IsUsageCacheEnabledForOrigin(
 628     const GURL& origin) const {
 629   std::string host = net::GetHostOrSpecFromURL(origin);
 630   return !OriginSetContainsOrigin(non_cached_limited_origins_by_host_,
 631                                   host, origin) &&
 632       !OriginSetContainsOrigin(non_cached_unlimited_origins_by_host_,
 633                                host, origin);
 634 }
 635
 636 void ClientUsageTracker::OnGranted(const GURL& origin,
 637                                    int change_flags) {
 638   DCHECK(CalledOnValidThread());
 639   if (change_flags & SpecialStoragePolicy::STORAGE_UNLIMITED) {
 640     int64 usage = 0;
 641     if (GetCachedOriginUsage(origin, &usage)) {
 642       global_unlimited_usage_ += usage;
 643       global_limited_usage_ -= usage;
 644     }
 645
 646     std::string host = net::GetHostOrSpecFromURL(origin);
 647     if (EraseOriginFromOriginSet(&non_cached_limited_origins_by_host_,
 648                                  host, origin))
 649       non_cached_unlimited_origins_by_host_[host].insert(origin);
 650   }
 651 }
 652
 653 void ClientUsageTracker::OnRevoked(const GURL& origin,
 654                                    int change_flags) {
 655   DCHECK(CalledOnValidThread());
 656   if (change_flags & SpecialStoragePolicy::STORAGE_UNLIMITED) {
 657     int64 usage = 0;
 658     if (GetCachedOriginUsage(origin, &usage)) {
 659       global_unlimited_usage_ -= usage;
 660       global_limited_usage_ += usage;
 661     }
 662
 663     std::string host = net::GetHostOrSpecFromURL(origin);
 664     if (EraseOriginFromOriginSet(&non_cached_unlimited_origins_by_host_,
 665                                  host, origin))
 666       non_cached_limited_origins_by_host_[host].insert(origin);
 667   }
 668 }
 669
 670 void ClientUsageTracker::OnCleared() {
 671   DCHECK(CalledOnValidThread());
 672   global_limited_usage_ += global_unlimited_usage_;
 673   global_unlimited_usage_ = 0;
 674
 675   for (OriginSetByHost::const_iterator host_itr =
 676            non_cached_unlimited_origins_by_host_.begin();
 677        host_itr != non_cached_unlimited_origins_by_host_.end();
 678        ++host_itr) {
 679     for (std::set<GURL>::const_iterator origin_itr = host_itr->second.begin();
 680          origin_itr != host_itr->second.end();
 681          ++origin_itr)
 682       non_cached_limited_origins_by_host_[host_itr->first].insert(*origin_itr);
 683   }
 684   non_cached_unlimited_origins_by_host_.clear();
 685 }
 686
 687 bool ClientUsageTracker::IsStorageUnlimited(const GURL& origin) const {
 688   if (type_ == kStorageTypeSyncable)
 689     return false;
 690   return special_storage_policy_.get() &&
 691          special_storage_policy_->IsStorageUnlimited(origin);
 692 }
 693
 694 }  // namespace quota