storage/browser/quota/quota_database.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 "storage/browser/quota/quota_database.h"
   6
   7 #include <vector>
   8
   9 #include "base/auto_reset.h"
  10 #include "base/bind.h"
  11 #include "base/files/file_util.h"
  12 #include "base/metrics/histogram_macros.h"
  13 #include "sql/connection.h"
  14 #include "sql/meta_table.h"
  15 #include "sql/statement.h"
  16 #include "sql/transaction.h"
  17 #include "storage/browser/quota/special_storage_policy.h"
  18
  19 namespace storage {
  20 namespace {
  21
  22 // Definitions for database schema.
  23
  24 const int kCurrentVersion = 4;
  25 const int kCompatibleVersion = 2;
  26
  27 const char kHostQuotaTable[] = "HostQuotaTable";
  28 const char kOriginInfoTable[] = "OriginInfoTable";
  29 const char kIsOriginTableBootstrapped[] = "IsOriginTableBootstrapped";
  30
  31 bool VerifyValidQuotaConfig(const char* key) {
  32   return (key != NULL &&
  33           (!strcmp(key, QuotaDatabase::kDesiredAvailableSpaceKey) ||
  34            !strcmp(key, QuotaDatabase::kTemporaryQuotaOverrideKey)));
  35 }
  36
  37 const int kCommitIntervalMs = 30000;
  38
  39 enum OriginType {
  40   // This enum is logged to UMA so only append to it - don't change
  41   // the meaning of the existing values.
  42   OTHER = 0,
  43   NONE = 1,
  44   GOOGLE_DURABLE = 2,
  45   NON_GOOGLE_DURABLE = 3,
  46   GOOGLE_UNLIMITED_EXTENSION = 4,
  47   NON_GOOGLE_UNLIMITED_EXTENSION = 5,
  48   IN_USE = 6,
  49
  50   MAX_ORIGIN_TYPE
  51 };
  52
  53 void HistogramOriginType(const OriginType& entry) {
  54   UMA_HISTOGRAM_ENUMERATION("Quota.LRUOriginTypes", entry, MAX_ORIGIN_TYPE);
  55 }
  56
  57 }  // anonymous namespace
  58
  59 // static
  60 const char QuotaDatabase::kDesiredAvailableSpaceKey[] = "DesiredAvailableSpace";
  61 const char QuotaDatabase::kTemporaryQuotaOverrideKey[] =
  62     "TemporaryQuotaOverride";
  63
  64 const QuotaDatabase::TableSchema QuotaDatabase::kTables[] = {
  65   { kHostQuotaTable,
  66     "(host TEXT NOT NULL,"
  67     " type INTEGER NOT NULL,"
  68     " quota INTEGER DEFAULT 0,"
  69     " UNIQUE(host, type))" },
  70   { kOriginInfoTable,
  71     "(origin TEXT NOT NULL,"
  72     " type INTEGER NOT NULL,"
  73     " used_count INTEGER DEFAULT 0,"
  74     " last_access_time INTEGER DEFAULT 0,"
  75     " last_modified_time INTEGER DEFAULT 0,"
  76     " UNIQUE(origin, type))" },
  77 };
  78
  79 // static
  80 const QuotaDatabase::IndexSchema QuotaDatabase::kIndexes[] = {
  81   { "HostIndex",
  82     kHostQuotaTable,
  83     "(host)",
  84     false },
  85   { "OriginInfoIndex",
  86     kOriginInfoTable,
  87     "(origin)",
  88     false },
  89   { "OriginLastAccessTimeIndex",
  90     kOriginInfoTable,
  91     "(last_access_time)",
  92     false },
  93   { "OriginLastModifiedTimeIndex",
  94     kOriginInfoTable,
  95     "(last_modified_time)",
  96     false },
  97 };
  98
  99 struct QuotaDatabase::QuotaTableImporter {
 100   bool Append(const QuotaTableEntry& entry) {
 101     entries.push_back(entry);
 102     return true;
 103   }
 104   std::vector<QuotaTableEntry> entries;
 105 };
 106
 107 // Clang requires explicit out-of-line constructors for them.
 108 QuotaDatabase::QuotaTableEntry::QuotaTableEntry()
 109     : type(kStorageTypeUnknown),
 110       quota(0) {
 111 }
 112
 113 QuotaDatabase::QuotaTableEntry::QuotaTableEntry(
 114     const std::string& host,
 115     StorageType type,
 116     int64 quota)
 117     : host(host),
 118       type(type),
 119       quota(quota) {
 120 }
 121
 122 QuotaDatabase::OriginInfoTableEntry::OriginInfoTableEntry()
 123     : type(kStorageTypeUnknown),
 124       used_count(0) {
 125 }
 126
 127 QuotaDatabase::OriginInfoTableEntry::OriginInfoTableEntry(
 128     const GURL& origin,
 129     StorageType type,
 130     int used_count,
 131     const base::Time& last_access_time,
 132     const base::Time& last_modified_time)
 133     : origin(origin),
 134       type(type),
 135       used_count(used_count),
 136       last_access_time(last_access_time),
 137       last_modified_time(last_modified_time) {
 138 }
 139
 140 // QuotaDatabase ------------------------------------------------------------
 141 QuotaDatabase::QuotaDatabase(const base::FilePath& path)
 142     : db_file_path_(path),
 143       is_recreating_(false),
 144       is_disabled_(false) {
 145 }
 146
 147 QuotaDatabase::~QuotaDatabase() {
 148   if (db_) {
 149     db_->CommitTransaction();
 150   }
 151 }
 152
 153 void QuotaDatabase::CloseConnection() {
 154   meta_table_.reset();
 155   db_.reset();
 156 }
 157
 158 bool QuotaDatabase::GetHostQuota(
 159     const std::string& host, StorageType type, int64* quota) {
 160   DCHECK(quota);
 161   if (!LazyOpen(false))
 162     return false;
 163
 164   const char* kSql =
 165       "SELECT quota"
 166       " FROM HostQuotaTable"
 167       " WHERE host = ? AND type = ?";
 168
 169   sql::Statement statement(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 170   statement.BindString(0, host);
 171   statement.BindInt(1, static_cast<int>(type));
 172
 173   if (!statement.Step())
 174     return false;
 175
 176   *quota = statement.ColumnInt64(0);
 177   return true;
 178 }
 179
 180 bool QuotaDatabase::SetHostQuota(
 181     const std::string& host, StorageType type, int64 quota) {
 182   DCHECK_GE(quota, 0);
 183   if (!LazyOpen(true))
 184     return false;
 185
 186   const char* kSql =
 187       "INSERT OR REPLACE INTO HostQuotaTable"
 188       " (quota, host, type)"
 189       " VALUES (?, ?, ?)";
 190   sql::Statement statement(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 191   statement.BindInt64(0, quota);
 192   statement.BindString(1, host);
 193   statement.BindInt(2, static_cast<int>(type));
 194
 195   if (!statement.Run())
 196     return false;
 197
 198   ScheduleCommit();
 199   return true;
 200 }
 201
 202 bool QuotaDatabase::SetOriginLastAccessTime(
 203     const GURL& origin, StorageType type, base::Time last_access_time) {
 204   if (!LazyOpen(true))
 205     return false;
 206
 207   sql::Statement statement;
 208
 209   int used_count = 1;
 210   if (FindOriginUsedCount(origin, type, &used_count)) {
 211     ++used_count;
 212     const char* kSql =
 213         "UPDATE OriginInfoTable"
 214         " SET used_count = ?, last_access_time = ?"
 215         " WHERE origin = ? AND type = ?";
 216     statement.Assign(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 217   } else  {
 218     const char* kSql =
 219         "INSERT INTO OriginInfoTable"
 220         " (used_count, last_access_time, origin, type)"
 221         " VALUES (?, ?, ?, ?)";
 222     statement.Assign(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 223   }
 224   statement.BindInt(0, used_count);
 225   statement.BindInt64(1, last_access_time.ToInternalValue());
 226   statement.BindString(2, origin.spec());
 227   statement.BindInt(3, static_cast<int>(type));
 228
 229   if (!statement.Run())
 230     return false;
 231
 232   ScheduleCommit();
 233   return true;
 234 }
 235
 236 bool QuotaDatabase::SetOriginLastModifiedTime(
 237     const GURL& origin, StorageType type, base::Time last_modified_time) {
 238   if (!LazyOpen(true))
 239     return false;
 240
 241   sql::Statement statement;
 242
 243   int dummy;
 244   if (FindOriginUsedCount(origin, type, &dummy)) {
 245     const char* kSql =
 246         "UPDATE OriginInfoTable"
 247         " SET last_modified_time = ?"
 248         " WHERE origin = ? AND type = ?";
 249     statement.Assign(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 250   } else {
 251     const char* kSql =
 252         "INSERT INTO OriginInfoTable"
 253         " (last_modified_time, origin, type)  VALUES (?, ?, ?)";
 254     statement.Assign(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 255   }
 256   statement.BindInt64(0, last_modified_time.ToInternalValue());
 257   statement.BindString(1, origin.spec());
 258   statement.BindInt(2, static_cast<int>(type));
 259
 260   if (!statement.Run())
 261     return false;
 262
 263   ScheduleCommit();
 264   return true;
 265 }
 266
 267 bool QuotaDatabase::RegisterInitialOriginInfo(
 268     const std::set<GURL>& origins, StorageType type) {
 269   if (!LazyOpen(true))
 270     return false;
 271
 272   typedef std::set<GURL>::const_iterator itr_type;
 273   for (itr_type itr = origins.begin(), end = origins.end();
 274        itr != end; ++itr) {
 275     const char* kSql =
 276         "INSERT OR IGNORE INTO OriginInfoTable"
 277         " (origin, type) VALUES (?, ?)";
 278     sql::Statement statement(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 279     statement.BindString(0, itr->spec());
 280     statement.BindInt(1, static_cast<int>(type));
 281
 282     if (!statement.Run())
 283       return false;
 284   }
 285
 286   ScheduleCommit();
 287   return true;
 288 }
 289
 290 bool QuotaDatabase::DeleteHostQuota(
 291     const std::string& host, StorageType type) {
 292   if (!LazyOpen(false))
 293     return false;
 294
 295   const char* kSql =
 296       "DELETE FROM HostQuotaTable"
 297       " WHERE host = ? AND type = ?";
 298
 299   sql::Statement statement(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 300   statement.BindString(0, host);
 301   statement.BindInt(1, static_cast<int>(type));
 302
 303   if (!statement.Run())
 304     return false;
 305
 306   ScheduleCommit();
 307   return true;
 308 }
 309
 310 bool QuotaDatabase::DeleteOriginInfo(
 311     const GURL& origin, StorageType type) {
 312   if (!LazyOpen(false))
 313     return false;
 314
 315   const char* kSql =
 316       "DELETE FROM OriginInfoTable"
 317       " WHERE origin = ? AND type = ?";
 318
 319   sql::Statement statement(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 320   statement.BindString(0, origin.spec());
 321   statement.BindInt(1, static_cast<int>(type));
 322
 323   if (!statement.Run())
 324     return false;
 325
 326   ScheduleCommit();
 327   return true;
 328 }
 329
 330 bool QuotaDatabase::GetQuotaConfigValue(const char* key, int64* value) {
 331   if (!LazyOpen(false))
 332     return false;
 333   DCHECK(VerifyValidQuotaConfig(key));
 334   return meta_table_->GetValue(key, value);
 335 }
 336
 337 bool QuotaDatabase::SetQuotaConfigValue(const char* key, int64 value) {
 338   if (!LazyOpen(true))
 339     return false;
 340   DCHECK(VerifyValidQuotaConfig(key));
 341   return meta_table_->SetValue(key, value);
 342 }
 343
 344 bool QuotaDatabase::GetLRUOrigin(
 345     StorageType type,
 346     const std::set<GURL>& exceptions,
 347     SpecialStoragePolicy* special_storage_policy,
 348     GURL* origin) {
 349   DCHECK(origin);
 350   if (!LazyOpen(false))
 351     return false;
 352
 353   const char* kSql = "SELECT origin FROM OriginInfoTable"
 354                      " WHERE type = ?"
 355                      " ORDER BY last_access_time ASC";
 356
 357   sql::Statement statement(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 358   statement.BindInt(0, static_cast<int>(type));
 359
 360   while (statement.Step()) {
 361     GURL url(statement.ColumnString(0));
 362     if (exceptions.find(url) != exceptions.end()) {
 363       HistogramOriginType(IN_USE);
 364       continue;
 365     }
 366     if (special_storage_policy) {
 367       bool is_google = url.DomainIs("google.com");
 368       if (special_storage_policy->IsStorageDurable(url)) {
 369         HistogramOriginType(is_google ? GOOGLE_DURABLE : NON_GOOGLE_DURABLE);
 370         continue;
 371       }
 372       if (special_storage_policy->IsStorageUnlimited(url)) {
 373         HistogramOriginType(is_google ? GOOGLE_UNLIMITED_EXTENSION
 374                                       : NON_GOOGLE_UNLIMITED_EXTENSION);
 375         continue;
 376       }
 377     }
 378     HistogramOriginType(OTHER);
 379     *origin = url;
 380     return true;
 381   }
 382
 383   HistogramOriginType(NONE);
 384   *origin = GURL();
 385   return statement.Succeeded();
 386 }
 387
 388 bool QuotaDatabase::GetOriginsModifiedSince(
 389     StorageType type, std::set<GURL>* origins, base::Time modified_since) {
 390   DCHECK(origins);
 391   if (!LazyOpen(false))
 392     return false;
 393
 394   const char* kSql = "SELECT origin FROM OriginInfoTable"
 395                      " WHERE type = ? AND last_modified_time >= ?";
 396
 397   sql::Statement statement(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 398   statement.BindInt(0, static_cast<int>(type));
 399   statement.BindInt64(1, modified_since.ToInternalValue());
 400
 401   origins->clear();
 402   while (statement.Step())
 403     origins->insert(GURL(statement.ColumnString(0)));
 404
 405   return statement.Succeeded();
 406 }
 407
 408 bool QuotaDatabase::IsOriginDatabaseBootstrapped() {
 409   if (!LazyOpen(true))
 410     return false;
 411
 412   int flag = 0;
 413   return meta_table_->GetValue(kIsOriginTableBootstrapped, &flag) && flag;
 414 }
 415
 416 bool QuotaDatabase::SetOriginDatabaseBootstrapped(bool bootstrap_flag) {
 417   if (!LazyOpen(true))
 418     return false;
 419
 420   return meta_table_->SetValue(kIsOriginTableBootstrapped, bootstrap_flag);
 421 }
 422
 423 void QuotaDatabase::Commit() {
 424   if (!db_)
 425     return;
 426
 427   if (timer_.IsRunning())
 428     timer_.Stop();
 429
 430   db_->CommitTransaction();
 431   db_->BeginTransaction();
 432 }
 433
 434 void QuotaDatabase::ScheduleCommit() {
 435   if (timer_.IsRunning())
 436     return;
 437   timer_.Start(FROM_HERE, base::TimeDelta::FromMilliseconds(kCommitIntervalMs),
 438                this, &QuotaDatabase::Commit);
 439 }
 440
 441 bool QuotaDatabase::FindOriginUsedCount(
 442     const GURL& origin, StorageType type, int* used_count) {
 443   DCHECK(used_count);
 444   if (!LazyOpen(false))
 445     return false;
 446
 447   const char* kSql =
 448       "SELECT used_count FROM OriginInfoTable"
 449       " WHERE origin = ? AND type = ?";
 450
 451   sql::Statement statement(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 452   statement.BindString(0, origin.spec());
 453   statement.BindInt(1, static_cast<int>(type));
 454
 455   if (!statement.Step())
 456     return false;
 457
 458   *used_count = statement.ColumnInt(0);
 459   return true;
 460 }
 461
 462 bool QuotaDatabase::LazyOpen(bool create_if_needed) {
 463   if (db_)
 464     return true;
 465
 466   // If we tried and failed once, don't try again in the same session
 467   // to avoid creating an incoherent mess on disk.
 468   if (is_disabled_)
 469     return false;
 470
 471   bool in_memory_only = db_file_path_.empty();
 472   if (!create_if_needed &&
 473       (in_memory_only || !base::PathExists(db_file_path_))) {
 474     return false;
 475   }
 476
 477   db_.reset(new sql::Connection);
 478   meta_table_.reset(new sql::MetaTable);
 479
 480   db_->set_histogram_tag("Quota");
 481
 482   bool opened = false;
 483   if (in_memory_only) {
 484     opened = db_->OpenInMemory();
 485   } else if (!base::CreateDirectory(db_file_path_.DirName())) {
 486       LOG(ERROR) << "Failed to create quota database directory.";
 487   } else {
 488     opened = db_->Open(db_file_path_);
 489     if (opened)
 490       db_->Preload();
 491   }
 492
 493   if (!opened || !EnsureDatabaseVersion()) {
 494     LOG(ERROR) << "Could not open the quota database, resetting.";
 495     if (!ResetSchema()) {
 496       LOG(ERROR) << "Failed to reset the quota database.";
 497       is_disabled_ = true;
 498       db_.reset();
 499       meta_table_.reset();
 500       return false;
 501     }
 502   }
 503
 504   // Start a long-running transaction.
 505   db_->BeginTransaction();
 506
 507   return true;
 508 }
 509
 510 bool QuotaDatabase::EnsureDatabaseVersion() {
 511   static const size_t kTableCount = arraysize(kTables);
 512   static const size_t kIndexCount = arraysize(kIndexes);
 513   if (!sql::MetaTable::DoesTableExist(db_.get()))
 514     return CreateSchema(db_.get(), meta_table_.get(),
 515                         kCurrentVersion, kCompatibleVersion,
 516                         kTables, kTableCount,
 517                         kIndexes, kIndexCount);
 518
 519   if (!meta_table_->Init(db_.get(), kCurrentVersion, kCompatibleVersion))
 520     return false;
 521
 522   if (meta_table_->GetCompatibleVersionNumber() > kCurrentVersion) {
 523     LOG(WARNING) << "Quota database is too new.";
 524     return false;
 525   }
 526
 527   if (meta_table_->GetVersionNumber() < kCurrentVersion) {
 528     if (!UpgradeSchema(meta_table_->GetVersionNumber()))
 529       return ResetSchema();
 530   }
 531
 532 #ifndef NDEBUG
 533   DCHECK(sql::MetaTable::DoesTableExist(db_.get()));
 534   for (size_t i = 0; i < kTableCount; ++i) {
 535     DCHECK(db_->DoesTableExist(kTables[i].table_name));
 536   }
 537 #endif
 538
 539   return true;
 540 }
 541
 542 // static
 543 bool QuotaDatabase::CreateSchema(
 544     sql::Connection* database,
 545     sql::MetaTable* meta_table,
 546     int schema_version, int compatible_version,
 547     const TableSchema* tables, size_t tables_size,
 548     const IndexSchema* indexes, size_t indexes_size) {
 549   // TODO(kinuko): Factor out the common code to create databases.
 550   sql::Transaction transaction(database);
 551   if (!transaction.Begin())
 552     return false;
 553
 554   if (!meta_table->Init(database, schema_version, compatible_version))
 555     return false;
 556
 557   for (size_t i = 0; i < tables_size; ++i) {
 558     std::string sql("CREATE TABLE ");
 559     sql += tables[i].table_name;
 560     sql += tables[i].columns;
 561     if (!database->Execute(sql.c_str())) {
 562       VLOG(1) << "Failed to execute " << sql;
 563       return false;
 564     }
 565   }
 566
 567   for (size_t i = 0; i < indexes_size; ++i) {
 568     std::string sql;
 569     if (indexes[i].unique)
 570       sql += "CREATE UNIQUE INDEX ";
 571     else
 572       sql += "CREATE INDEX ";
 573     sql += indexes[i].index_name;
 574     sql += " ON ";
 575     sql += indexes[i].table_name;
 576     sql += indexes[i].columns;
 577     if (!database->Execute(sql.c_str())) {
 578       VLOG(1) << "Failed to execute " << sql;
 579       return false;
 580     }
 581   }
 582
 583   return transaction.Commit();
 584 }
 585
 586 bool QuotaDatabase::ResetSchema() {
 587   DCHECK(!db_file_path_.empty());
 588   DCHECK(base::PathExists(db_file_path_));
 589   VLOG(1) << "Deleting existing quota data and starting over.";
 590
 591   db_.reset();
 592   meta_table_.reset();
 593
 594   if (!sql::Connection::Delete(db_file_path_))
 595     return false;
 596
 597   // So we can't go recursive.
 598   if (is_recreating_)
 599     return false;
 600
 601   base::AutoReset<bool> auto_reset(&is_recreating_, true);
 602   return LazyOpen(true);
 603 }
 604
 605 bool QuotaDatabase::UpgradeSchema(int current_version) {
 606   if (current_version == 2) {
 607     QuotaTableImporter importer;
 608     typedef std::vector<QuotaTableEntry> QuotaTableEntries;
 609     if (!DumpQuotaTable(base::Bind(&QuotaTableImporter::Append,
 610                                    base::Unretained(&importer)))) {
 611       return false;
 612     }
 613     ResetSchema();
 614     for (QuotaTableEntries::const_iterator iter = importer.entries.begin();
 615          iter != importer.entries.end(); ++iter) {
 616       if (!SetHostQuota(iter->host, iter->type, iter->quota))
 617         return false;
 618     }
 619     Commit();
 620     return true;
 621   }
 622   return false;
 623 }
 624
 625 bool QuotaDatabase::DumpQuotaTable(const QuotaTableCallback& callback) {
 626   if (!LazyOpen(true))
 627     return false;
 628
 629   const char* kSql = "SELECT * FROM HostQuotaTable";
 630   sql::Statement statement(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 631
 632   while (statement.Step()) {
 633     QuotaTableEntry entry = QuotaTableEntry(
 634       statement.ColumnString(0),
 635       static_cast<StorageType>(statement.ColumnInt(1)),
 636       statement.ColumnInt64(2));
 637
 638     if (!callback.Run(entry))
 639       return true;
 640   }
 641
 642   return statement.Succeeded();
 643 }
 644
 645 bool QuotaDatabase::DumpOriginInfoTable(
 646     const OriginInfoTableCallback& callback) {
 647
 648   if (!LazyOpen(true))
 649     return false;
 650
 651   const char* kSql = "SELECT * FROM OriginInfoTable";
 652   sql::Statement statement(db_->GetCachedStatement(SQL_FROM_HERE, kSql));
 653
 654   while (statement.Step()) {
 655     OriginInfoTableEntry entry(
 656       GURL(statement.ColumnString(0)),
 657       static_cast<StorageType>(statement.ColumnInt(1)),
 658       statement.ColumnInt(2),
 659       base::Time::FromInternalValue(statement.ColumnInt64(3)),
 660       base::Time::FromInternalValue(statement.ColumnInt64(4)));
 661
 662     if (!callback.Run(entry))
 663       return true;
 664   }
 665
 666   return statement.Succeeded();
 667 }
 668
 669 bool operator<(const QuotaDatabase::QuotaTableEntry& lhs,
 670                const QuotaDatabase::QuotaTableEntry& rhs) {
 671   if (lhs.host < rhs.host) return true;
 672   if (rhs.host < lhs.host) return false;
 673   if (lhs.type < rhs.type) return true;
 674   if (rhs.type < lhs.type) return false;
 675   return lhs.quota < rhs.quota;
 676 }
 677
 678 bool operator<(const QuotaDatabase::OriginInfoTableEntry& lhs,
 679                const QuotaDatabase::OriginInfoTableEntry& rhs) {
 680   if (lhs.origin < rhs.origin) return true;
 681   if (rhs.origin < lhs.origin) return false;
 682   if (lhs.type < rhs.type) return true;
 683   if (rhs.type < lhs.type) return false;
 684   if (lhs.used_count < rhs.used_count) return true;
 685   if (rhs.used_count < lhs.used_count) return false;
 686   return lhs.last_access_time < rhs.last_access_time;
 687 }
 688
 689 }  // namespace storage