metadata_database_index_on_disk.cc revision 5f1c94371a64b3196d4be9466099bb892df9b88e
1// Copyright 2014 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 "chrome/browser/sync_file_system/drive_backend/metadata_database_index_on_disk.h" 6 7#include "base/format_macros.h" 8#include "base/logging.h" 9#include "base/strings/string_number_conversions.h" 10#include "base/strings/string_util.h" 11#include "chrome/browser/sync_file_system/drive_backend/drive_backend_constants.h" 12#include "chrome/browser/sync_file_system/drive_backend/drive_backend_util.h" 13#include "chrome/browser/sync_file_system/drive_backend/leveldb_wrapper.h" 14#include "chrome/browser/sync_file_system/drive_backend/metadata_database.pb.h" 15#include "chrome/browser/sync_file_system/logger.h" 16#include "third_party/leveldatabase/src/include/leveldb/status.h" 17 18// LevelDB database schema 19// ======================= 20// 21// NOTE 22// - Entries are sorted by keys. 23// - int64 value is serialized as a string by base::Int64ToString(). 24// - ServiceMetadata, FileMetadata, and FileTracker values are serialized 25// as a string by SerializeToString() of protocol buffers. 26// 27// Version 4: 28// # Version of this schema 29// key: "VERSION" 30// value: "4" 31// 32// # Metadata of the SyncFS service (compatible with version 3) 33// key: "SERVICE" 34// value: <ServiceMetadata 'service_metadata'> 35// 36// # Metadata of remote files (compatible with version 3) 37// key: "FILE: " + <string 'file_id'> 38// value: <FileMetadata 'metadata'> 39// 40// # Trackers of remote file updates (compatible with version 3) 41// key: "TRACKER: " + <int64 'tracker_id'> 42// value: <FileTracker 'tracker'> 43// 44// # Index from App ID to the tracker ID 45// key: "APP_ROOT: " + <string 'app_id'> 46// value: <int64 'app_root_tracker_id'> 47// 48// # Index from file ID to the active tracker ID 49// key: "ACTIVE_FILE: " + <string 'file_id'> 50// value: <int64 'active_tracker_id'> 51// 52// # Index from file ID to a tracker ID 53// key: "TRACKER_FILE: " + <string 'file_id'> + '\x00' + <int64 'tracker_id'> 54// value: <empty> 55// 56// # Tracker IDs; a file metadata linked to multiple tracker IDs. 57// key: "MULTI_FILE: " + <int64 'tracker_id'> 58// value: <empty> 59// 60// # Index from the parent tracker ID and the title to the active tracker ID 61// key: "ACTIVE_PATH: " + <int64 'parent_tracker_id'> + 62// '\x00' + <string 'title'> 63// value: <int64 'active_tracker_id'> 64// 65// # Index from the parent tracker ID and the title to a tracker ID 66// key: "TRACKER_PATH: " + <int64 'parent_tracker_id'> + 67// '\x00' + <string 'title'> + '\x00' + <int64 'tracker_id'> 68// value: <empty> 69// 70// # Tracker IDs; a parent tracker ID and a title figure multiple tracker IDs 71// key: "MULTI_PATH: " + <int64 'tracker_id'> 72// value: <empty> 73// 74// # Dirty tracker IDs 75// key: "DIRTY: " + <int64 'dirty_tracker_id'> 76// value: <empty> 77// 78// # Demoted dirty tracker IDs 79// key: "DEMOTED_DIRTY: " + <int64 'demoted_dirty_tracker_id'> 80// value: <empty> 81 82namespace sync_file_system { 83namespace drive_backend { 84 85namespace { 86 87std::string GenerateAppRootIDByAppIDKey(const std::string& app_id) { 88 return kAppRootIDByAppIDKeyPrefix + app_id; 89} 90 91std::string GenerateActiveTrackerIDByFileIDKey(const std::string& file_id) { 92 return kActiveTrackerIDByFileIDKeyPrefix + file_id; 93} 94 95std::string GenerateTrackerIDByFileIDKeyPrefix(const std::string& file_id) { 96 std::ostringstream oss; 97 oss << kTrackerIDByFileIDKeyPrefix << file_id << '\0'; 98 return oss.str(); 99} 100 101std::string GenerateMultiTrackerKey(const std::string& file_id) { 102 return kMultiTrackerByFileIDKeyPrefix + file_id; 103} 104 105std::string GenerateActiveTrackerIDByParentAndTitleKey( 106 int64 parent_id, const std::string& title) { 107 std::ostringstream oss; 108 oss << kActiveTrackerIDByParentAndTitleKeyPrefix << parent_id 109 << '\0' << title; 110 return oss.str(); 111} 112 113std::string GenerateTrackerIDByParentAndTitleKeyPrefix( 114 int64 parent_id, const std::string& title) { 115 std::ostringstream oss; 116 oss << kTrackerIDByParentAndTitleKeyPrefix << parent_id << '\0' 117 << title << '\0'; 118 return oss.str(); 119} 120 121std::string GenerateTrackerIDsByParentIDKeyPrefix(int64 parent_id) { 122 std::ostringstream oss; 123 oss << kTrackerIDByParentAndTitleKeyPrefix << parent_id << '\0'; 124 return oss.str(); 125} 126 127std::string GenerateMultiBackingParentAndTitleKey( 128 int64 parent_id, const std::string& title) { 129 std::ostringstream oss; 130 oss << kMultiBackingParentAndTitleKeyPrefix << parent_id << '\0' 131 << title; 132 return oss.str(); 133} 134 135std::string GenerateDirtyIDKey(int64 tracker_id) { 136 return kDirtyIDKeyPrefix + base::Int64ToString(tracker_id); 137} 138 139std::string GenerateDemotedDirtyIDKey(int64 tracker_id) { 140 return kDemotedDirtyIDKeyPrefix + base::Int64ToString(tracker_id); 141} 142 143void RemoveUnreachableItems(LevelDBWrapper* db) { 144 DCHECK(db); 145 146 typedef std::map<int64, std::set<int64> > ChildTrackersByParent; 147 ChildTrackersByParent trackers_by_parent; 148 { 149 // Set up links from parent tracker to child trackers. 150 std::set<int64> inactive_trackers; 151 scoped_ptr<LevelDBWrapper::Iterator> itr = db->NewIterator(); 152 for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) { 153 if (!RemovePrefix(itr->key().ToString(), kFileTrackerKeyPrefix, NULL)) 154 break; 155 156 scoped_ptr<FileTracker> tracker(new FileTracker); 157 if (!tracker->ParseFromString(itr->value().ToString())) { 158 util::Log(logging::LOG_WARNING, FROM_HERE, 159 "Failed to parse a Tracker"); 160 continue; 161 } 162 163 int64 parent_tracker_id = tracker->parent_tracker_id(); 164 int64 tracker_id = tracker->tracker_id(); 165 trackers_by_parent[parent_tracker_id].insert(tracker_id); 166 if (!tracker->active()) 167 inactive_trackers.insert(tracker_id); 168 } 169 170 // Drop links from inactive trackers. 171 for (std::set<int64>::iterator iter = inactive_trackers.begin(); 172 iter != inactive_trackers.end(); ++iter) { 173 trackers_by_parent.erase(*iter); 174 } 175 } 176 177 // Traverse tracker tree from sync-root. 178 std::set<int64> visited_trackers; 179 { 180 scoped_ptr<ServiceMetadata> service_metadata = 181 InitializeServiceMetadata(db); 182 int64 sync_root_tracker_id = service_metadata->sync_root_tracker_id(); 183 std::vector<int64> pending; 184 if (sync_root_tracker_id != kInvalidTrackerID) 185 pending.push_back(sync_root_tracker_id); 186 187 while (!pending.empty()) { 188 int64 tracker_id = pending.back(); 189 DCHECK_NE(kInvalidTrackerID, tracker_id); 190 pending.pop_back(); 191 192 if (!visited_trackers.insert(tracker_id).second) { 193 NOTREACHED(); 194 continue; 195 } 196 197 AppendContents( 198 LookUpMap(trackers_by_parent, tracker_id, std::set<int64>()), 199 &pending); 200 } 201 } 202 203 // Delete all unreachable trackers, and list all |file_id| referred by 204 // remained trackers. 205 base::hash_set<std::string> referred_file_ids; 206 { 207 scoped_ptr<LevelDBWrapper::Iterator> itr = db->NewIterator(); 208 for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) { 209 if (!RemovePrefix(itr->key().ToString(), kFileTrackerKeyPrefix, NULL)) 210 break; 211 212 scoped_ptr<FileTracker> tracker(new FileTracker); 213 if (!tracker->ParseFromString(itr->value().ToString())) { 214 util::Log(logging::LOG_WARNING, FROM_HERE, 215 "Failed to parse a Tracker"); 216 continue; 217 } 218 219 if (ContainsKey(visited_trackers, tracker->tracker_id())) { 220 referred_file_ids.insert(tracker->file_id()); 221 } else { 222 PutFileTrackerDeletionToDB(tracker->tracker_id(), db); 223 } 224 } 225 } 226 227 // Delete all unreferred metadata. 228 { 229 scoped_ptr<LevelDBWrapper::Iterator> itr = db->NewIterator(); 230 for (itr->Seek(kFileMetadataKeyPrefix); itr->Valid(); itr->Next()) { 231 if (!RemovePrefix(itr->key().ToString(), kFileMetadataKeyPrefix, NULL)) 232 break; 233 234 scoped_ptr<FileMetadata> metadata(new FileMetadata); 235 if (!metadata->ParseFromString(itr->value().ToString())) { 236 util::Log(logging::LOG_WARNING, FROM_HERE, 237 "Failed to parse a Tracker"); 238 continue; 239 } 240 241 if (!ContainsKey(referred_file_ids, metadata->file_id())) 242 PutFileMetadataDeletionToDB(metadata->file_id(), db); 243 } 244 } 245} 246 247} // namespace 248 249// static 250scoped_ptr<MetadataDatabaseIndexOnDisk> 251MetadataDatabaseIndexOnDisk::Create(LevelDBWrapper* db) { 252 DCHECK(db); 253 254 PutVersionToDB(kDatabaseOnDiskVersion, db); 255 // TODO(peria): It is not good to call RemoveUnreachableItems on every 256 // creation. 257 RemoveUnreachableItems(db); 258 scoped_ptr<MetadataDatabaseIndexOnDisk> 259 index(new MetadataDatabaseIndexOnDisk(db)); 260 return index.Pass(); 261} 262 263MetadataDatabaseIndexOnDisk::~MetadataDatabaseIndexOnDisk() {} 264 265bool MetadataDatabaseIndexOnDisk::GetFileMetadata( 266 const std::string& file_id, FileMetadata* metadata) const { 267 const std::string key = kFileMetadataKeyPrefix + file_id; 268 std::string value; 269 leveldb::Status status = db_->Get(key, &value); 270 271 if (status.IsNotFound()) 272 return false; 273 274 if (!status.ok()) { 275 util::Log(logging::LOG_WARNING, FROM_HERE, 276 "LevelDB error (%s) in getting FileMetadata for ID: %s", 277 status.ToString().c_str(), 278 file_id.c_str()); 279 return false; 280 } 281 282 FileMetadata tmp_metadata; 283 if (!tmp_metadata.ParseFromString(value)) { 284 util::Log(logging::LOG_WARNING, FROM_HERE, 285 "Failed to parse a FileMetadata for ID: %s", 286 file_id.c_str()); 287 return false; 288 } 289 if (metadata) 290 metadata->CopyFrom(tmp_metadata); 291 292 return true; 293} 294 295bool MetadataDatabaseIndexOnDisk::GetFileTracker( 296 int64 tracker_id, FileTracker* tracker) const { 297 const std::string key = 298 kFileTrackerKeyPrefix + base::Int64ToString(tracker_id); 299 std::string value; 300 leveldb::Status status = db_->Get(key, &value); 301 302 if (status.IsNotFound()) 303 return false; 304 305 if (!status.ok()) { 306 util::Log(logging::LOG_WARNING, FROM_HERE, 307 "LevelDB error (%s) in getting FileTracker for ID: %" PRId64, 308 status.ToString().c_str(), 309 tracker_id); 310 return false; 311 } 312 313 FileTracker tmp_tracker; 314 if (!tmp_tracker.ParseFromString(value)) { 315 util::Log(logging::LOG_WARNING, FROM_HERE, 316 "Failed to parse a Tracker for ID: %" PRId64, 317 tracker_id); 318 return false; 319 } 320 if (tracker) 321 tracker->CopyFrom(tmp_tracker); 322 323 return true; 324} 325 326void MetadataDatabaseIndexOnDisk::StoreFileMetadata( 327 scoped_ptr<FileMetadata> metadata) { 328 DCHECK(metadata); 329 PutFileMetadataToDB(*metadata, db_); 330} 331 332void MetadataDatabaseIndexOnDisk::StoreFileTracker( 333 scoped_ptr<FileTracker> tracker) { 334 DCHECK(tracker); 335 336 int64 tracker_id = tracker->tracker_id(); 337 FileTracker old_tracker; 338 if (!GetFileTracker(tracker_id, &old_tracker)) { 339 DVLOG(3) << "Adding new tracker: " << tracker->tracker_id() 340 << " " << GetTrackerTitle(*tracker); 341 AddToAppIDIndex(*tracker); 342 AddToFileIDIndexes(*tracker); 343 AddToPathIndexes(*tracker); 344 AddToDirtyTrackerIndexes(*tracker); 345 } else { 346 DVLOG(3) << "Updating tracker: " << tracker->tracker_id() 347 << " " << GetTrackerTitle(*tracker); 348 UpdateInAppIDIndex(old_tracker, *tracker); 349 UpdateInFileIDIndexes(old_tracker, *tracker); 350 UpdateInPathIndexes(old_tracker, *tracker); 351 UpdateInDirtyTrackerIndexes(old_tracker, *tracker); 352 353 } 354 355 PutFileTrackerToDB(*tracker, db_); 356} 357 358void MetadataDatabaseIndexOnDisk::RemoveFileMetadata( 359 const std::string& file_id) { 360 PutFileMetadataDeletionToDB(file_id, db_); 361} 362 363void MetadataDatabaseIndexOnDisk::RemoveFileTracker(int64 tracker_id) { 364 FileTracker tracker; 365 if (!GetFileTracker(tracker_id, &tracker)) { 366 NOTREACHED(); 367 return; 368 } 369 370 DVLOG(1) << "Removing tracker: " 371 << tracker.tracker_id() << " " << GetTrackerTitle(tracker); 372 RemoveFromAppIDIndex(tracker); 373 RemoveFromFileIDIndexes(tracker); 374 RemoveFromPathIndexes(tracker); 375 RemoveFromDirtyTrackerIndexes(tracker); 376 377 PutFileTrackerDeletionToDB(tracker_id, db_); 378} 379 380TrackerIDSet MetadataDatabaseIndexOnDisk::GetFileTrackerIDsByFileID( 381 const std::string& file_id) const { 382 return GetTrackerIDSetByPrefix( 383 GenerateActiveTrackerIDByFileIDKey(file_id), 384 GenerateTrackerIDByFileIDKeyPrefix(file_id)); 385} 386 387int64 MetadataDatabaseIndexOnDisk::GetAppRootTracker( 388 const std::string& app_id) const { 389 const std::string key = GenerateAppRootIDByAppIDKey(app_id); 390 std::string value; 391 leveldb::Status status = db_->Get(key, &value); 392 393 if (status.IsNotFound()) 394 return kInvalidTrackerID; 395 396 if (!status.ok()) { 397 util::Log(logging::LOG_WARNING, FROM_HERE, 398 "LevelDB error (%s) in getting AppRoot for AppID: %s", 399 status.ToString().c_str(), 400 app_id.c_str()); 401 return kInvalidTrackerID; 402 } 403 404 int64 root_id; 405 if (!base::StringToInt64(value, &root_id)) { 406 util::Log(logging::LOG_WARNING, FROM_HERE, 407 "Failed to parse a root ID (%s) for an App ID: %s", 408 value.c_str(), 409 app_id.c_str()); 410 return kInvalidTrackerID; 411 } 412 413 return root_id; 414} 415 416TrackerIDSet MetadataDatabaseIndexOnDisk::GetFileTrackerIDsByParentAndTitle( 417 int64 parent_tracker_id, const std::string& title) const { 418 return GetTrackerIDSetByPrefix( 419 GenerateActiveTrackerIDByParentAndTitleKey(parent_tracker_id, title), 420 GenerateTrackerIDByParentAndTitleKeyPrefix(parent_tracker_id, title)); 421} 422 423std::vector<int64> MetadataDatabaseIndexOnDisk::GetFileTrackerIDsByParent( 424 int64 parent_id) const { 425 std::vector<int64> result; 426 427 const std::string prefix = GenerateTrackerIDsByParentIDKeyPrefix(parent_id); 428 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 429 for (itr->Seek(prefix); itr->Valid(); itr->Next()) { 430 const std::string& key(itr->key().ToString()); 431 std::string title_and_id; 432 if (!RemovePrefix(key, prefix, &title_and_id)) 433 break; 434 435 size_t pos = title_and_id.rfind('\0'); 436 DCHECK(pos != std::string::npos); 437 438 int64 tracker_id; 439 if (!base::StringToInt64(title_and_id.substr(pos + 1), &tracker_id)) 440 continue; 441 result.push_back(tracker_id); 442 } 443 return result; 444} 445 446std::string MetadataDatabaseIndexOnDisk::PickMultiTrackerFileID() const { 447 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 448 itr->Seek(kMultiTrackerByFileIDKeyPrefix); 449 if (!itr->Valid()) 450 return std::string(); 451 452 std::string file_id; 453 if (!RemovePrefix(itr->key().ToString(), 454 kMultiTrackerByFileIDKeyPrefix, &file_id)) 455 return std::string(); 456 457 return file_id; 458} 459 460ParentIDAndTitle MetadataDatabaseIndexOnDisk::PickMultiBackingFilePath() const { 461 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 462 itr->Seek(kMultiBackingParentAndTitleKeyPrefix); 463 if (!itr->Valid()) 464 return ParentIDAndTitle(); 465 466 std::string value; 467 if (!RemovePrefix(itr->key().ToString(), 468 kMultiBackingParentAndTitleKeyPrefix, &value)) 469 return ParentIDAndTitle(); 470 471 size_t pos = value.find('\0'); // '\0' is a separator. 472 if (pos == std::string::npos) 473 return ParentIDAndTitle(); 474 475 int64 parent_id; 476 return base::StringToInt64(value.substr(0, pos), &parent_id) ? 477 ParentIDAndTitle(parent_id, value.substr(pos + 1)) : ParentIDAndTitle(); 478} 479 480int64 MetadataDatabaseIndexOnDisk::PickDirtyTracker() const { 481 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 482 itr->Seek(kDirtyIDKeyPrefix); 483 if (!itr->Valid()) 484 return kInvalidTrackerID; 485 486 std::string id_str; 487 if (!RemovePrefix(itr->key().ToString(), kDirtyIDKeyPrefix, &id_str)) 488 return kInvalidTrackerID; 489 490 int64 tracker_id; 491 if (!base::StringToInt64(id_str, &tracker_id)) 492 return kInvalidTrackerID; 493 494 return tracker_id; 495} 496 497void MetadataDatabaseIndexOnDisk::DemoteDirtyTracker(int64 tracker_id) { 498 const std::string key = GenerateDirtyIDKey(tracker_id); 499 500 std::string value; 501 leveldb::Status status = db_->Get(key, &value); 502 if (status.IsNotFound()) 503 return; 504 if (!status.ok()) { 505 util::Log(logging::LOG_WARNING, FROM_HERE, 506 "LevelDB error (%s) in getting a dirty tracker for ID: %" PRId64, 507 status.ToString().c_str(), 508 tracker_id); 509 return; 510 } 511 512 db_->Delete(key); 513 db_->Put(GenerateDemotedDirtyIDKey(tracker_id), std::string()); 514} 515 516bool MetadataDatabaseIndexOnDisk::HasDemotedDirtyTracker() const { 517 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 518 itr->Seek(kDemotedDirtyIDKeyPrefix); 519 if (!itr->Valid()) 520 return false; 521 return StartsWithASCII(itr->key().ToString(), kDemotedDirtyIDKeyPrefix, true); 522} 523 524void MetadataDatabaseIndexOnDisk::PromoteDemotedDirtyTrackers() { 525 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 526 for (itr->Seek(kDirtyIDKeyPrefix); itr->Valid(); itr->Next()) { 527 std::string id_str; 528 if (!RemovePrefix(itr->key().ToString(), kDirtyIDKeyPrefix, &id_str)) 529 break; 530 531 int64 tracker_id; 532 if (!base::StringToInt64(id_str, &tracker_id)) 533 continue; 534 535 db_->Delete(itr->key().ToString()); 536 db_->Put(GenerateDemotedDirtyIDKey(tracker_id), std::string()); 537 } 538} 539 540size_t MetadataDatabaseIndexOnDisk::CountDirtyTracker() const { 541 size_t num_dirty_trackers = 0; 542 543 // TODO(peria): Store the number of dirty trackers, and do not iterate 544 // everytime. 545 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 546 for (itr->Seek(kDirtyIDKeyPrefix); itr->Valid(); itr->Next()) { 547 if (!StartsWithASCII(itr->key().ToString(), kDirtyIDKeyPrefix, true)) 548 break; 549 ++num_dirty_trackers; 550 } 551 552 for (itr->Seek(kDemotedDirtyIDKeyPrefix); itr->Valid(); itr->Next()) { 553 if (!StartsWithASCII(itr->key().ToString(), kDemotedDirtyIDKeyPrefix, true)) 554 break; 555 ++num_dirty_trackers; 556 } 557 558 return num_dirty_trackers; 559} 560 561size_t MetadataDatabaseIndexOnDisk::CountFileMetadata() const { 562 // TODO(peria): Cache the number of FileMetadata in the DB. 563 size_t count = 0; 564 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 565 for (itr->Seek(kFileMetadataKeyPrefix); itr->Valid(); itr->Next()) { 566 if (!StartsWithASCII(itr->key().ToString(), kFileMetadataKeyPrefix, true)) 567 break; 568 ++count; 569 } 570 return count; 571} 572 573size_t MetadataDatabaseIndexOnDisk::CountFileTracker() const { 574 // TODO(peria): Cache the number of FileTracker in the DB. 575 size_t count = 0; 576 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 577 for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) { 578 if (!StartsWithASCII(itr->key().ToString(), kFileTrackerKeyPrefix, true)) 579 break; 580 ++count; 581 } 582 return count; 583} 584 585void MetadataDatabaseIndexOnDisk::SetSyncRootTrackerID( 586 int64 sync_root_id) const { 587 service_metadata_->set_sync_root_tracker_id(sync_root_id); 588 PutServiceMetadataToDB(*service_metadata_, db_); 589} 590 591void MetadataDatabaseIndexOnDisk::SetLargestChangeID( 592 int64 largest_change_id) const { 593 service_metadata_->set_largest_change_id(largest_change_id); 594 PutServiceMetadataToDB(*service_metadata_, db_); 595} 596 597void MetadataDatabaseIndexOnDisk::SetNextTrackerID( 598 int64 next_tracker_id) const { 599 service_metadata_->set_next_tracker_id(next_tracker_id); 600 PutServiceMetadataToDB(*service_metadata_, db_); 601} 602 603int64 MetadataDatabaseIndexOnDisk::GetSyncRootTrackerID() const { 604 if (!service_metadata_->has_sync_root_tracker_id()) 605 return kInvalidTrackerID; 606 return service_metadata_->sync_root_tracker_id(); 607} 608 609int64 MetadataDatabaseIndexOnDisk::GetLargestChangeID() const { 610 if (!service_metadata_->has_largest_change_id()) 611 return kInvalidTrackerID; 612 return service_metadata_->largest_change_id(); 613} 614 615int64 MetadataDatabaseIndexOnDisk::GetNextTrackerID() const { 616 if (!service_metadata_->has_next_tracker_id()) 617 return kInvalidTrackerID; 618 return service_metadata_->next_tracker_id(); 619} 620 621std::vector<std::string> 622MetadataDatabaseIndexOnDisk::GetRegisteredAppIDs() const { 623 std::vector<std::string> result; 624 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 625 for (itr->Seek(kAppRootIDByAppIDKeyPrefix); itr->Valid(); itr->Next()) { 626 std::string id; 627 if (!RemovePrefix(itr->key().ToString(), kAppRootIDByAppIDKeyPrefix, &id)) 628 break; 629 result.push_back(id); 630 } 631 return result; 632} 633 634std::vector<int64> MetadataDatabaseIndexOnDisk::GetAllTrackerIDs() const { 635 std::vector<int64> tracker_ids; 636 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 637 for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) { 638 std::string id_str; 639 if (!RemovePrefix(itr->key().ToString(), kFileTrackerKeyPrefix, &id_str)) 640 break; 641 642 int64 tracker_id; 643 if (!base::StringToInt64(id_str, &tracker_id)) 644 continue; 645 tracker_ids.push_back(tracker_id); 646 } 647 return tracker_ids; 648} 649 650std::vector<std::string> 651MetadataDatabaseIndexOnDisk::GetAllMetadataIDs() const { 652 std::vector<std::string> file_ids; 653 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 654 for (itr->Seek(kFileMetadataKeyPrefix); itr->Valid(); itr->Next()) { 655 std::string file_id; 656 if (!RemovePrefix(itr->key().ToString(), kFileMetadataKeyPrefix, &file_id)) 657 break; 658 file_ids.push_back(file_id); 659 } 660 return file_ids; 661} 662 663void MetadataDatabaseIndexOnDisk::BuildTrackerIndexes() { 664 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 665 for (itr->Seek(kFileTrackerKeyPrefix); itr->Valid(); itr->Next()) { 666 if (!RemovePrefix(itr->key().ToString(), kFileTrackerKeyPrefix, NULL)) 667 break; 668 669 FileTracker tracker; 670 if (!tracker.ParseFromString(itr->value().ToString())) { 671 util::Log(logging::LOG_WARNING, FROM_HERE, 672 "Failed to parse a Tracker"); 673 continue; 674 } 675 676 AddToAppIDIndex(tracker); 677 AddToFileIDIndexes(tracker); 678 AddToPathIndexes(tracker); 679 AddToDirtyTrackerIndexes(tracker); 680 } 681} 682 683LevelDBWrapper* MetadataDatabaseIndexOnDisk::GetDBForTesting() { 684 return db_; 685} 686 687MetadataDatabaseIndexOnDisk::MetadataDatabaseIndexOnDisk(LevelDBWrapper* db) 688 : db_(db) { 689 // TODO(peria): Add UMA to measure the number of FileMetadata, FileTracker, 690 // and AppRootId. 691 // TODO(peria): If the DB version is 3, build up index lists. 692 service_metadata_ = InitializeServiceMetadata(db_); 693} 694 695void MetadataDatabaseIndexOnDisk::AddToAppIDIndex(const FileTracker& tracker) { 696 if (!IsAppRoot(tracker)) { 697 DVLOG(3) << " Tracker for " << tracker.file_id() << " is not an App root."; 698 return; 699 } 700 701 DVLOG(1) << " Add to App root by App ID: " << tracker.app_id(); 702 703 const std::string db_key = GenerateAppRootIDByAppIDKey(tracker.app_id()); 704 DCHECK(tracker.active()); 705 DCHECK(!DBHasKey(db_key)); 706 db_->Put(db_key, base::Int64ToString(tracker.tracker_id())); 707} 708 709void MetadataDatabaseIndexOnDisk::UpdateInAppIDIndex( 710 const FileTracker& old_tracker, 711 const FileTracker& new_tracker) { 712 DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id()); 713 714 if (IsAppRoot(old_tracker) && !IsAppRoot(new_tracker)) { 715 DCHECK(old_tracker.active()); 716 DCHECK(!new_tracker.active()); 717 const std::string key = GenerateAppRootIDByAppIDKey(old_tracker.app_id()); 718 DCHECK(DBHasKey(key)); 719 720 DVLOG(1) << " Remove from App root by App ID: " << old_tracker.app_id(); 721 db_->Delete(key); 722 } else if (!IsAppRoot(old_tracker) && IsAppRoot(new_tracker)) { 723 DCHECK(!old_tracker.active()); 724 DCHECK(new_tracker.active()); 725 const std::string key = GenerateAppRootIDByAppIDKey(new_tracker.app_id()); 726 DCHECK(!DBHasKey(key)); 727 728 DVLOG(1) << " Add to App root by App ID: " << new_tracker.app_id(); 729 db_->Put(key, base::Int64ToString(new_tracker.tracker_id())); 730 } 731} 732 733void MetadataDatabaseIndexOnDisk::RemoveFromAppIDIndex( 734 const FileTracker& tracker) { 735 if (!IsAppRoot(tracker)) { 736 DVLOG(3) << " Tracker for " << tracker.file_id() << " is not an App root."; 737 return; 738 } 739 740 DCHECK(tracker.active()); 741 const std::string key = GenerateAppRootIDByAppIDKey(tracker.app_id()); 742 DCHECK(DBHasKey(key)); 743 744 DVLOG(1) << " Remove from App root by App ID: " << tracker.app_id(); 745 db_->Delete(key); 746} 747 748void MetadataDatabaseIndexOnDisk::AddToFileIDIndexes( 749 const FileTracker& new_tracker) { 750 const std::string& file_id = new_tracker.file_id(); 751 752 DVLOG(1) << " Add to trackers by file ID: " << file_id; 753 const std::string prefix = GenerateTrackerIDByFileIDKeyPrefix(file_id); 754 AddToTrackerIDSetWithPrefix( 755 GenerateActiveTrackerIDByFileIDKey(file_id), 756 prefix, new_tracker); 757 758 const std::string multi_tracker_key = GenerateMultiTrackerKey(file_id); 759 if (!DBHasKey(multi_tracker_key) && 760 CountWithPrefix(prefix, new_tracker.tracker_id()) != NONE) { 761 DVLOG(1) << " Add to multi-tracker file IDs: " << file_id; 762 db_->Put(multi_tracker_key, std::string()); 763 } 764} 765 766void MetadataDatabaseIndexOnDisk::UpdateInFileIDIndexes( 767 const FileTracker& old_tracker, 768 const FileTracker& new_tracker) { 769 DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id()); 770 DCHECK_EQ(old_tracker.file_id(), new_tracker.file_id()); 771 772 const std::string& file_id = new_tracker.file_id(); 773 const std::string prefix = GenerateTrackerIDByFileIDKeyPrefix(file_id); 774 DCHECK(DBHasKey(prefix + base::Int64ToString(new_tracker.tracker_id()))); 775 776 if (old_tracker.active() && !new_tracker.active()) { 777 DeactivateInTrackerIDSetWithPrefix( 778 GenerateActiveTrackerIDByFileIDKey(file_id), prefix, 779 new_tracker.tracker_id()); 780 } else if (!old_tracker.active() && new_tracker.active()) { 781 ActivateInTrackerIDSetWithPrefix( 782 GenerateActiveTrackerIDByFileIDKey(file_id), prefix, 783 new_tracker.tracker_id()); 784 } 785} 786 787void MetadataDatabaseIndexOnDisk::RemoveFromFileIDIndexes( 788 const FileTracker& tracker) { 789 const std::string& file_id = tracker.file_id(); 790 const std::string prefix = 791 GenerateTrackerIDByFileIDKeyPrefix(file_id); 792 793 if (!EraseInTrackerIDSetWithPrefix( 794 GenerateActiveTrackerIDByFileIDKey(file_id), 795 prefix, tracker.tracker_id())) 796 return; 797 798 DVLOG(1) << " Remove from trackers by file ID: " << tracker.tracker_id(); 799 800 const std::string multi_key = GenerateMultiTrackerKey(file_id); 801 if (DBHasKey(multi_key) && 802 CountWithPrefix(prefix, tracker.tracker_id()) != MULTIPLE) { 803 DVLOG(1) << " Remove from multi-tracker file IDs: " << file_id; 804 db_->Delete(multi_key); 805 } 806} 807 808void MetadataDatabaseIndexOnDisk::AddToPathIndexes( 809 const FileTracker& new_tracker) { 810 int64 parent_id = new_tracker.parent_tracker_id(); 811 std::string title = GetTrackerTitle(new_tracker); 812 813 DVLOG(1) << " Add to trackers by parent and title: " 814 << parent_id << " " << title; 815 816 const std::string prefix = 817 GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title); 818 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 819 for (itr->Seek(prefix); itr->Valid(); itr->Next()) { 820 std::string id_str; 821 if (!RemovePrefix(itr->key().ToString(), prefix, &id_str)) 822 break; 823 824 int64 tracker_id; 825 if (!base::StringToInt64(id_str, &tracker_id)) 826 continue; 827 if (tracker_id == new_tracker.tracker_id()) { 828 NOTREACHED(); 829 continue; 830 } 831 832 const std::string multi_key = 833 GenerateMultiBackingParentAndTitleKey(parent_id, title); 834 DVLOG_IF(1, !DBHasKey(multi_key)) 835 << " Add to multi backing file paths: " << parent_id << " " << title; 836 db_->Put(GenerateMultiBackingParentAndTitleKey(parent_id, title), 837 std::string()); 838 break; 839 } 840 841 AddToTrackerIDSetWithPrefix( 842 GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title), 843 prefix, new_tracker); 844} 845 846void MetadataDatabaseIndexOnDisk::UpdateInPathIndexes( 847 const FileTracker& old_tracker, 848 const FileTracker& new_tracker) { 849 DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id()); 850 DCHECK_EQ(old_tracker.parent_tracker_id(), new_tracker.parent_tracker_id()); 851 DCHECK(GetTrackerTitle(old_tracker) == GetTrackerTitle(new_tracker) || 852 !old_tracker.has_synced_details()); 853 854 int64 tracker_id = new_tracker.tracker_id(); 855 int64 parent_id = new_tracker.parent_tracker_id(); 856 const std::string old_title = GetTrackerTitle(old_tracker); 857 const std::string title = GetTrackerTitle(new_tracker); 858 859 if (old_title != title) { 860 const std::string old_prefix = 861 GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, old_title); 862 EraseInTrackerIDSetWithPrefix( 863 GenerateActiveTrackerIDByParentAndTitleKey(parent_id, old_title), 864 old_prefix, tracker_id); 865 866 if (!old_title.empty() && 867 CountWithPrefix(old_prefix, tracker_id) != MULTIPLE) { 868 const std::string old_multi_backing_key = 869 GenerateMultiBackingParentAndTitleKey(parent_id, old_title); 870 DVLOG_IF(1, DBHasKey(old_multi_backing_key)) 871 << " Remove from multi backing file paths: " 872 << parent_id << " " << old_title; 873 db_->Delete(old_multi_backing_key); 874 } 875 876 DVLOG(1) << " Add to trackers by parent and title: " 877 << parent_id << " " << title; 878 879 const std::string prefix = 880 GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title); 881 AddToTrackerIDSetWithPrefix( 882 GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title), 883 prefix, new_tracker); 884 885 if (CountWithPrefix(prefix, tracker_id) != NONE) { 886 const std::string multi_backing_key = 887 GenerateMultiBackingParentAndTitleKey(parent_id, title); 888 DVLOG_IF(1, !DBHasKey(multi_backing_key)) 889 << " Add to multi backing file_paths: " 890 << parent_id << " " << title; 891 db_->Put(multi_backing_key, std::string()); 892 } 893 894 return; 895 } 896 897 const std::string active_tracker_key = 898 GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title); 899 const std::string prefix = 900 GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title); 901 if (old_tracker.active() && !new_tracker.active()) { 902 DeactivateInTrackerIDSetWithPrefix( 903 active_tracker_key, prefix, tracker_id); 904 } else if (!old_tracker.active() && new_tracker.active()) { 905 ActivateInTrackerIDSetWithPrefix( 906 active_tracker_key, prefix, tracker_id); 907 } 908} 909 910void MetadataDatabaseIndexOnDisk::RemoveFromPathIndexes( 911 const FileTracker& tracker) { 912 int64 tracker_id = tracker.tracker_id(); 913 int64 parent_id = tracker.parent_tracker_id(); 914 std::string title = GetTrackerTitle(tracker); 915 916 DVLOG(1) << " Remove from trackers by parent and title: " 917 << parent_id << " " << title; 918 919 const std::string active_tracker_key = 920 GenerateActiveTrackerIDByParentAndTitleKey(parent_id, title); 921 const std::string key_prefix = 922 GenerateTrackerIDByParentAndTitleKeyPrefix(parent_id, title); 923 if (!EraseInTrackerIDSetWithPrefix( 924 active_tracker_key, key_prefix, tracker_id)) 925 return; 926 927 const std::string multi_key = 928 GenerateMultiBackingParentAndTitleKey(parent_id, title); 929 if (!title.empty() && DBHasKey(multi_key) && 930 CountWithPrefix(key_prefix, tracker_id) != MULTIPLE) { 931 DVLOG(1) << " Remove from multi backing file paths: " 932 << parent_id << " " << title; 933 db_->Delete(multi_key); 934 } 935} 936 937void MetadataDatabaseIndexOnDisk::AddToDirtyTrackerIndexes( 938 const FileTracker& new_tracker) { 939 const std::string dirty_key = GenerateDirtyIDKey(new_tracker.tracker_id()); 940 DCHECK(!DBHasKey(dirty_key)); 941 DCHECK(!DBHasKey(GenerateDemotedDirtyIDKey(new_tracker.tracker_id()))); 942 943 if (new_tracker.dirty()) { 944 DVLOG(1) << " Add to dirty tracker IDs: " << new_tracker.tracker_id(); 945 db_->Put(dirty_key, std::string()); 946 } 947} 948 949void MetadataDatabaseIndexOnDisk::UpdateInDirtyTrackerIndexes( 950 const FileTracker& old_tracker, 951 const FileTracker& new_tracker) { 952 DCHECK_EQ(old_tracker.tracker_id(), new_tracker.tracker_id()); 953 954 int64 tracker_id = new_tracker.tracker_id(); 955 const std::string dirty_key = GenerateDirtyIDKey(tracker_id); 956 const std::string demoted_key = GenerateDemotedDirtyIDKey(tracker_id); 957 if (old_tracker.dirty() && !new_tracker.dirty()) { 958 DCHECK(DBHasKey(dirty_key) || DBHasKey(demoted_key)); 959 960 DVLOG(1) << " Remove from dirty trackers IDs: " << tracker_id; 961 962 db_->Delete(dirty_key); 963 db_->Delete(demoted_key); 964 } else if (!old_tracker.dirty() && new_tracker.dirty()) { 965 DCHECK(!DBHasKey(dirty_key)); 966 DCHECK(!DBHasKey(demoted_key)); 967 968 DVLOG(1) << " Add to dirty tracker IDs: " << tracker_id; 969 970 db_->Put(dirty_key, std::string()); 971 } 972} 973 974void MetadataDatabaseIndexOnDisk::RemoveFromDirtyTrackerIndexes( 975 const FileTracker& tracker) { 976 if (tracker.dirty()) { 977 int64 tracker_id = tracker.tracker_id(); 978 const std::string dirty_key = GenerateDirtyIDKey(tracker_id); 979 const std::string demoted_key = GenerateDemotedDirtyIDKey(tracker_id); 980 DCHECK(DBHasKey(dirty_key) || DBHasKey(demoted_key)); 981 982 DVLOG(1) << " Remove from dirty tracker IDs: " << tracker_id; 983 db_->Delete(dirty_key); 984 db_->Delete(demoted_key); 985 } 986} 987 988TrackerIDSet MetadataDatabaseIndexOnDisk::GetTrackerIDSetByPrefix( 989 const std::string& active_tracker_key, 990 const std::string& ids_prefix) const { 991 TrackerIDSet trackers; 992 993 // Seek IDs. 994 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 995 for (itr->Seek(ids_prefix); itr->Valid(); itr->Next()) { 996 const std::string& key(itr->key().ToString()); 997 std::string id_str; 998 if (!RemovePrefix(key, ids_prefix, &id_str)) 999 break; 1000 1001 int64 tracker_id; 1002 if (!base::StringToInt64(id_str, &tracker_id)) 1003 continue; 1004 trackers.InsertInactiveTracker(tracker_id); 1005 } 1006 1007 // Set an active tracker ID, if available. 1008 std::string value; 1009 leveldb::Status status = db_->Get(active_tracker_key, &value); 1010 int64 active_tracker; 1011 if (status.ok() && base::StringToInt64(value, &active_tracker) && 1012 active_tracker != kInvalidTrackerID) { 1013 trackers.Activate(active_tracker); 1014 } 1015 1016 return trackers; 1017} 1018 1019void MetadataDatabaseIndexOnDisk::AddToTrackerIDSetWithPrefix( 1020 const std::string& active_tracker_key, const std::string& key_prefix, 1021 const FileTracker& tracker) { 1022 DCHECK(tracker.tracker_id()); 1023 1024 const std::string id_str = base::Int64ToString(tracker.tracker_id()); 1025 db_->Put(key_prefix + id_str, std::string()); 1026 if (tracker.active()) 1027 db_->Put(active_tracker_key, id_str); 1028} 1029 1030bool MetadataDatabaseIndexOnDisk::EraseInTrackerIDSetWithPrefix( 1031 const std::string& active_tracker_key, const std::string& key_prefix, 1032 int64 tracker_id) { 1033 std::string value; 1034 const std::string del_key = key_prefix + base::Int64ToString(tracker_id); 1035 leveldb::Status status = db_->Get(del_key, &value); 1036 if (status.IsNotFound()) 1037 return false; 1038 1039 db_->Delete(del_key); 1040 1041 size_t count = 0; 1042 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 1043 for (itr->Seek(key_prefix); itr->Valid(); itr->Next()) { 1044 const std::string key = itr->key().ToString(); 1045 if (!StartsWithASCII(key, key_prefix, true)) 1046 break; 1047 // Entry for |del_key| is not deleted yet. 1048 if (key == del_key) 1049 continue; 1050 ++count; 1051 break; 1052 } 1053 1054 if (count > 0) { 1055 // TrackerIDSet is still alive. Deactivate if the tracker is active. 1056 leveldb::Status status = 1057 db_->Get(active_tracker_key, &value); 1058 int64 active_tracker_id; 1059 if (status.ok() && base::StringToInt64(value, &active_tracker_id) && 1060 active_tracker_id == tracker_id) { 1061 db_->Put(active_tracker_key, base::Int64ToString(kInvalidTrackerID)); 1062 } 1063 } else { 1064 // TrackerIDSet is no longer alive. Erase active tracker entry. 1065 db_->Delete(active_tracker_key); 1066 } 1067 1068 return true; 1069} 1070 1071void MetadataDatabaseIndexOnDisk::ActivateInTrackerIDSetWithPrefix( 1072 const std::string& active_tracker_key, const std::string& key_prefix, 1073 int64 tracker_id) { 1074 DCHECK(DBHasKey(key_prefix + base::Int64ToString(tracker_id))); 1075 1076 std::string value; 1077 leveldb::Status status = db_->Get(active_tracker_key, &value); 1078 int64 active_tracker_id = kInvalidTrackerID; 1079 if (status.IsNotFound() || 1080 (status.ok() && base::StringToInt64(value, &active_tracker_id))) { 1081 DCHECK(active_tracker_id != tracker_id); 1082 db_->Put(active_tracker_key, base::Int64ToString(tracker_id)); 1083 } 1084} 1085 1086void MetadataDatabaseIndexOnDisk::DeactivateInTrackerIDSetWithPrefix( 1087 const std::string& active_tracker_key, const std::string& key_prefix, 1088 int64 tracker_id) { 1089 DCHECK(DBHasKey(key_prefix + base::Int64ToString(tracker_id))); 1090 1091 std::string value; 1092 leveldb::Status status = db_->Get(active_tracker_key, &value); 1093 int64 active_tracker_id; 1094 if (status.ok() && base::StringToInt64(value, &active_tracker_id)) { 1095 DCHECK(active_tracker_id == tracker_id); 1096 db_->Put(active_tracker_key, base::Int64ToString(kInvalidTrackerID)); 1097 } 1098} 1099 1100bool MetadataDatabaseIndexOnDisk::DBHasKey(const std::string& key) { 1101 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 1102 itr->Seek(key); 1103 return itr->Valid() && (itr->key() == key); 1104} 1105 1106MetadataDatabaseIndexOnDisk::NumEntries 1107MetadataDatabaseIndexOnDisk::CountWithPrefix( 1108 const std::string& prefix, int64 ignored_id) { 1109 const std::string ignored = base::Int64ToString(ignored_id); 1110 1111 size_t count = 0; 1112 scoped_ptr<LevelDBWrapper::Iterator> itr(db_->NewIterator()); 1113 for (itr->Seek(prefix); itr->Valid() && count <= 1; itr->Next()) { 1114 std::string value; 1115 if (!RemovePrefix(itr->key().ToString(), prefix, &value)) 1116 break; 1117 if (value == ignored) 1118 continue; 1119 1120 ++count; 1121 } 1122 1123 if (count >= 2) 1124 return MULTIPLE; 1125 return count == 0 ? NONE : SINGLE; 1126} 1127 1128} // namespace drive_backend 1129} // namespace sync_file_system 1130