content/browser/indexed_db/instance/leveldb/tombstone_sweeper.cc - chromium/src.git - Git at Google

 // Copyright 2017 The Chromium Authors
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "content/browser/indexed_db/instance/leveldb/tombstone_sweeper.h"

 #include <string>
 #include <string_view>

 #include "base/metrics/histogram_functions.h"
 #include "base/rand_util.h"
 #include "base/strings/string_number_conversions.h"
 #include "components/services/storage/indexed_db/scopes/varint_coding.h"
 #include "content/browser/indexed_db/instance/leveldb/backing_store.h"
 #include "third_party/blink/public/common/indexeddb/indexeddb_key.h"
 #include "third_party/blink/public/common/indexeddb/indexeddb_metadata.h"
 #include "third_party/leveldatabase/env_chromium.h"
 #include "third_party/leveldatabase/src/include/leveldb/db.h"
 #include "third_party/leveldatabase/src/include/leveldb/iterator.h"

 namespace content::indexed_db::level_db {
 namespace {

 using blink::IndexedDBDatabaseMetadata;
 using blink::IndexedDBIndexMetadata;
 using blink::IndexedDBKey;
 using blink::IndexedDBObjectStoreMetadata;

 }  // namespace

 template <typename T>
 WrappingIterator<T>::WrappingIterator() {}

 template <typename T>
 WrappingIterator<T>::WrappingIterator(const T* container,
                                       size_t start_position) {
   container_ = container;
   valid_ = true;
   iterations_done_ = 0;
   DCHECK_LT(start_position, container_->size());
   inner_ = container_->begin();
   std::advance(inner_, start_position);
   CHECK(inner_ != container_->end());
 }

 template <typename T>
 WrappingIterator<T>::~WrappingIterator() {}

 template <typename T>
 void WrappingIterator<T>::Next() {
   DCHECK(valid_);
   iterations_done_++;
   if (iterations_done_ >= container_->size()) {
     valid_ = false;
     return;
   }
   inner_++;
   if (inner_ == container_->end()) {
     inner_ = container_->begin();
   }
 }

 template <typename T>
 const typename T::value_type& WrappingIterator<T>::Value() const {
   CHECK(valid_);
   return *inner_;
 }

 namespace {
 // The number of iterations for every 'round' of the tombstone sweeper.
 // A new sweep task will be scheduled after reaching current round limit.
 constexpr int kTombstoneSweeperRoundIterations = 1000;
 // The maximum total iterations for the tombstone sweeper.
 constexpr int kTombstoneSweeperMaxIterations = 10 * 1000 * 1000;
 }  // namespace

 LevelDbTombstoneSweeper::LevelDbTombstoneSweeper(leveldb::DB* database)
     : LevelDbTombstoneSweeper(kTombstoneSweeperRoundIterations,
                               kTombstoneSweeperMaxIterations,
                               database) {}

 LevelDbTombstoneSweeper::LevelDbTombstoneSweeper(int round_iterations,
                                                  int max_iterations,
                                                  leveldb::DB* database)
     : BackingStorePreCloseTaskQueue::PreCloseTask(database),
       max_round_iterations_(round_iterations),
       max_iterations_(max_iterations) {
   sweep_state_.start_database_seed = static_cast<size_t>(base::RandUint64());
   sweep_state_.start_object_store_seed =
       static_cast<size_t>(base::RandUint64());
   sweep_state_.start_index_seed = static_cast<size_t>(base::RandUint64());
 }

 LevelDbTombstoneSweeper::~LevelDbTombstoneSweeper() {
   base::UmaHistogramCounts1M(
       "IndexedDB.LevelDbTombstoneSweeper.TombstonesFound", tombstones_found_);
 }

 bool LevelDbTombstoneSweeper::RequiresMetadata() const {
   return true;
 }

 void LevelDbTombstoneSweeper::SetMetadata(
     const std::vector<std::unique_ptr<IndexedDBDatabaseMetadata>>* metadata) {
   database_metadata_ = metadata;
 }

 LevelDbTombstoneSweeper::SweepState::SweepState() = default;

 LevelDbTombstoneSweeper::SweepState::~SweepState() = default;

 bool LevelDbTombstoneSweeper::RunRound() {
   DCHECK(database_metadata_);

   if (database_metadata_->empty()) {
     return true;
   }

   Status s;
   SweepStatus status = DoSweep(&s);

   if (status != SweepStatus::DONE_ERROR) {
     s = FlushDeletions();
     if (!s.ok()) {
       status = SweepStatus::DONE_ERROR;
     }
   }

   return status != SweepStatus::SWEEPING;
 }

 Status LevelDbTombstoneSweeper::FlushDeletions() {
   if (!has_writes_) {
     return Status::OK();
   }

   Status status(
       database()->Write(leveldb::WriteOptions(), &round_deletion_batch_));
   round_deletion_batch_.Clear();
   has_writes_ = false;
   return status;
 }

 bool LevelDbTombstoneSweeper::ShouldContinueIteration(
     const leveldb::Iterator& iterator,
     LevelDbTombstoneSweeper::SweepStatus* sweep_status,
     Status* leveldb_status,
     int* round_iterations) {
   ++num_iterations_;
   ++(*round_iterations);

   if (!iterator.Valid()) {
     *leveldb_status = iterator.status();
     if (!leveldb_status->ok()) {
       *sweep_status = SweepStatus::DONE_ERROR;
       return false;
     }
     *sweep_status = SweepStatus::SWEEPING;
     return true;
   }
   if (*round_iterations >= max_round_iterations_) {
     *sweep_status = SweepStatus::SWEEPING;
     return false;
   }
   if (num_iterations_ >= max_iterations_) {
     *sweep_status = SweepStatus::DONE;
     return false;
   }
   return true;
 }

 LevelDbTombstoneSweeper::SweepStatus LevelDbTombstoneSweeper::DoSweep(
     Status* leveldb_status) {
   int round_iterations = 0;
   SweepStatus sweep_status;
   if (database_metadata_->empty()) {
     return SweepStatus::DONE;
   }

   if (!sweep_state_.database_it) {
     size_t start_database_idx = static_cast<size_t>(
         sweep_state_.start_database_seed % database_metadata_->size());
     sweep_state_.database_it.emplace(database_metadata_.get(),
                                      start_database_idx);
   }
   // Loop conditions facilitate starting at random index.
   for (; sweep_state_.database_it->IsValid();
        sweep_state_.database_it->Next()) {
     const blink::IndexedDBDatabaseMetadata& database =
         *sweep_state_.database_it->Value();

     if (database.object_stores.empty()) {
       continue;
     }

     if (!sweep_state_.object_store_it) {
       size_t start_object_store_idx = static_cast<size_t>(
           sweep_state_.start_object_store_seed % database.object_stores.size());
       sweep_state_.object_store_it.emplace(&database.object_stores,
                                            start_object_store_idx);
     }
     // Loop conditions facilitate starting at random index.
     for (; sweep_state_.object_store_it->IsValid();
          sweep_state_.object_store_it->Next()) {
       const IndexedDBObjectStoreMetadata& object_store =
           sweep_state_.object_store_it->Value().second;

       if (object_store.indexes.empty()) {
         continue;
       }

       if (!sweep_state_.index_it) {
         size_t start_index_idx = static_cast<size_t>(
             sweep_state_.start_index_seed % object_store.indexes.size());
         sweep_state_.index_it = WrappingIterator<IndexMetadataMap>(
             &object_store.indexes, start_index_idx);
       }
       // Loop conditions facilitate starting at random index.
       for (; sweep_state_.index_it->IsValid(); sweep_state_.index_it->Next()) {
         const IndexedDBIndexMetadata& index =
             sweep_state_.index_it->Value().second;

         int64_t database_id =
             reinterpret_cast<const BackingStore::DatabaseMetadata*>(&database)
                 ->id.value();
         bool can_continue =
             IterateIndex(database_id, object_store.id, index, &sweep_status,
                          leveldb_status, &round_iterations);
         if (!can_continue) {
           return sweep_status;
         }
       }
       sweep_state_.index_it = std::nullopt;
     }
     sweep_state_.object_store_it = std::nullopt;
   }
   return SweepStatus::DONE;
 }

 bool LevelDbTombstoneSweeper::IterateIndex(
     int64_t database_id,
     int64_t object_store_id,
     const IndexedDBIndexMetadata& index,
     LevelDbTombstoneSweeper::SweepStatus* sweep_status,
     Status* leveldb_status,
     int* round_iterations) {
   std::unique_ptr<leveldb::Iterator> iterator(
       database()->NewIterator({.verify_checksums = true, .fill_cache = false}));

   // If the sweeper exited early from an index scan, continue where it left off.
   if (sweep_state_.index_it_key) {
     iterator->Seek(sweep_state_.index_it_key->Encode());
     if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
                                  round_iterations)) {
       return false;
     }
     // Start at the first unvisited value.
     iterator->Next();
     if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
                                  round_iterations)) {
       return false;
     }
   } else {
     iterator->Seek(
         IndexDataKey::EncodeMinKey(database_id, object_store_id, index.id));
     if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
                                  round_iterations)) {
       return false;
     }
   }

   while (iterator->Valid()) {
     leveldb::Slice key_slice = iterator->key();
     std::string_view index_key_str = leveldb_env::MakeStringView(key_slice);
     std::string_view index_value_str =
         leveldb_env::MakeStringView(iterator->value());
     // See if we've reached the end of the current index or all indexes.
     sweep_state_.index_it_key.emplace(IndexDataKey());
     if (!IndexDataKey::Decode(&index_key_str,
                               &sweep_state_.index_it_key.value()) ||
         sweep_state_.index_it_key->IndexId() != index.id) {
       break;
     }

     int64_t index_data_version;
     std::unique_ptr<IndexedDBKey> primary_key;

     if (!DecodeVarInt(&index_value_str, &index_data_version)) {
       iterator->Next();
       if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
                                    round_iterations)) {
         return false;
       }
       continue;
     }
     std::string encoded_primary_key(index_value_str);
     std::string exists_key = ExistsEntryKey::Encode(
         database_id, object_store_id, encoded_primary_key);

     std::string exists_value;
     Status s(
         database()->Get(leveldb::ReadOptions(), exists_key, &exists_value));
     if (!s.ok()) {
       iterator->Next();
       if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
                                    round_iterations)) {
         return false;
       }
       continue;
     }
     std::string_view exists_value_piece(exists_value);
     int64_t decoded_exists_version;
     if (!DecodeInt(&exists_value_piece, &decoded_exists_version) ||
         !exists_value_piece.empty()) {
       iterator->Next();
       if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
                                    round_iterations)) {
         return false;
       }
       continue;
     }

     if (decoded_exists_version != index_data_version) {
       has_writes_ = true;
       round_deletion_batch_.Delete(key_slice);
       ++tombstones_found_;
     }

     iterator->Next();
     if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
                                  round_iterations)) {
       return false;
     }
   }
   sweep_state_.index_it_key = std::nullopt;
   return true;
 }

 }  // namespace content::indexed_db::level_db
	// Copyright 2017 The Chromium Authors
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "content/browser/indexed_db/instance/leveldb/tombstone_sweeper.h"

	#include <string>
	#include <string_view>

	#include "base/metrics/histogram_functions.h"
	#include "base/rand_util.h"
	#include "base/strings/string_number_conversions.h"
	#include "components/services/storage/indexed_db/scopes/varint_coding.h"
	#include "content/browser/indexed_db/instance/leveldb/backing_store.h"
	#include "third_party/blink/public/common/indexeddb/indexeddb_key.h"
	#include "third_party/blink/public/common/indexeddb/indexeddb_metadata.h"
	#include "third_party/leveldatabase/env_chromium.h"
	#include "third_party/leveldatabase/src/include/leveldb/db.h"
	#include "third_party/leveldatabase/src/include/leveldb/iterator.h"

	namespace content::indexed_db::level_db {
	namespace {

	using blink::IndexedDBDatabaseMetadata;
	using blink::IndexedDBIndexMetadata;
	using blink::IndexedDBKey;
	using blink::IndexedDBObjectStoreMetadata;

	} // namespace

	template <typename T>
	WrappingIterator<T>::WrappingIterator() {}

	template <typename T>
	WrappingIterator<T>::WrappingIterator(const T* container,
	size_t start_position) {
	container_ = container;
	valid_ = true;
	iterations_done_ = 0;
	DCHECK_LT(start_position, container_->size());
	inner_ = container_->begin();
	std::advance(inner_, start_position);
	CHECK(inner_ != container_->end());
	}

	template <typename T>
	WrappingIterator<T>::~WrappingIterator() {}

	template <typename T>
	void WrappingIterator<T>::Next() {
	DCHECK(valid_);
	iterations_done_++;
	if (iterations_done_ >= container_->size()) {
	valid_ = false;
	return;
	}
	inner_++;
	if (inner_ == container_->end()) {
	inner_ = container_->begin();
	}
	}

	template <typename T>
	const typename T::value_type& WrappingIterator<T>::Value() const {
	CHECK(valid_);
	return *inner_;
	}

	namespace {
	// The number of iterations for every 'round' of the tombstone sweeper.
	// A new sweep task will be scheduled after reaching current round limit.
	constexpr int kTombstoneSweeperRoundIterations = 1000;
	// The maximum total iterations for the tombstone sweeper.
	constexpr int kTombstoneSweeperMaxIterations = 10 * 1000 * 1000;
	} // namespace

	LevelDbTombstoneSweeper::LevelDbTombstoneSweeper(leveldb::DB* database)
	: LevelDbTombstoneSweeper(kTombstoneSweeperRoundIterations,
	kTombstoneSweeperMaxIterations,
	database) {}

	LevelDbTombstoneSweeper::LevelDbTombstoneSweeper(int round_iterations,
	int max_iterations,
	leveldb::DB* database)
	: BackingStorePreCloseTaskQueue::PreCloseTask(database),
	max_round_iterations_(round_iterations),
	max_iterations_(max_iterations) {
	sweep_state_.start_database_seed = static_cast<size_t>(base::RandUint64());
	sweep_state_.start_object_store_seed =
	static_cast<size_t>(base::RandUint64());
	sweep_state_.start_index_seed = static_cast<size_t>(base::RandUint64());
	}

	LevelDbTombstoneSweeper::~LevelDbTombstoneSweeper() {
	base::UmaHistogramCounts1M(
	"IndexedDB.LevelDbTombstoneSweeper.TombstonesFound", tombstones_found_);
	}

	bool LevelDbTombstoneSweeper::RequiresMetadata() const {
	return true;
	}

	void LevelDbTombstoneSweeper::SetMetadata(
	const std::vector<std::unique_ptr<IndexedDBDatabaseMetadata>>* metadata) {
	database_metadata_ = metadata;
	}

	LevelDbTombstoneSweeper::SweepState::SweepState() = default;

	LevelDbTombstoneSweeper::SweepState::~SweepState() = default;

	bool LevelDbTombstoneSweeper::RunRound() {
	DCHECK(database_metadata_);

	if (database_metadata_->empty()) {
	return true;
	}

	Status s;
	SweepStatus status = DoSweep(&s);

	if (status != SweepStatus::DONE_ERROR) {
	s = FlushDeletions();
	if (!s.ok()) {
	status = SweepStatus::DONE_ERROR;
	}
	}

	return status != SweepStatus::SWEEPING;
	}

	Status LevelDbTombstoneSweeper::FlushDeletions() {
	if (!has_writes_) {
	return Status::OK();
	}

	Status status(
	database()->Write(leveldb::WriteOptions(), &round_deletion_batch_));
	round_deletion_batch_.Clear();
	has_writes_ = false;
	return status;
	}

	bool LevelDbTombstoneSweeper::ShouldContinueIteration(
	const leveldb::Iterator& iterator,
	LevelDbTombstoneSweeper::SweepStatus* sweep_status,
	Status* leveldb_status,
	int* round_iterations) {
	++num_iterations_;
	++(*round_iterations);

	if (!iterator.Valid()) {
	*leveldb_status = iterator.status();
	if (!leveldb_status->ok()) {
	*sweep_status = SweepStatus::DONE_ERROR;
	return false;
	}
	*sweep_status = SweepStatus::SWEEPING;
	return true;
	}
	if (*round_iterations >= max_round_iterations_) {
	*sweep_status = SweepStatus::SWEEPING;
	return false;
	}
	if (num_iterations_ >= max_iterations_) {
	*sweep_status = SweepStatus::DONE;
	return false;
	}
	return true;
	}

	LevelDbTombstoneSweeper::SweepStatus LevelDbTombstoneSweeper::DoSweep(
	Status* leveldb_status) {
	int round_iterations = 0;
	SweepStatus sweep_status;
	if (database_metadata_->empty()) {
	return SweepStatus::DONE;
	}

	if (!sweep_state_.database_it) {
	size_t start_database_idx = static_cast<size_t>(
	sweep_state_.start_database_seed % database_metadata_->size());
	sweep_state_.database_it.emplace(database_metadata_.get(),
	start_database_idx);
	}
	// Loop conditions facilitate starting at random index.
	for (; sweep_state_.database_it->IsValid();
	sweep_state_.database_it->Next()) {
	const blink::IndexedDBDatabaseMetadata& database =
	*sweep_state_.database_it->Value();

	if (database.object_stores.empty()) {
	continue;
	}

	if (!sweep_state_.object_store_it) {
	size_t start_object_store_idx = static_cast<size_t>(
	sweep_state_.start_object_store_seed % database.object_stores.size());
	sweep_state_.object_store_it.emplace(&database.object_stores,
	start_object_store_idx);
	}
	// Loop conditions facilitate starting at random index.
	for (; sweep_state_.object_store_it->IsValid();
	sweep_state_.object_store_it->Next()) {
	const IndexedDBObjectStoreMetadata& object_store =
	sweep_state_.object_store_it->Value().second;

	if (object_store.indexes.empty()) {
	continue;
	}

	if (!sweep_state_.index_it) {
	size_t start_index_idx = static_cast<size_t>(
	sweep_state_.start_index_seed % object_store.indexes.size());
	sweep_state_.index_it = WrappingIterator<IndexMetadataMap>(
	&object_store.indexes, start_index_idx);
	}
	// Loop conditions facilitate starting at random index.
	for (; sweep_state_.index_it->IsValid(); sweep_state_.index_it->Next()) {
	const IndexedDBIndexMetadata& index =
	sweep_state_.index_it->Value().second;

	int64_t database_id =
	reinterpret_cast<const BackingStore::DatabaseMetadata*>(&database)
	->id.value();
	bool can_continue =
	IterateIndex(database_id, object_store.id, index, &sweep_status,
	leveldb_status, &round_iterations);
	if (!can_continue) {
	return sweep_status;
	}
	}
	sweep_state_.index_it = std::nullopt;
	}
	sweep_state_.object_store_it = std::nullopt;
	}
	return SweepStatus::DONE;
	}

	bool LevelDbTombstoneSweeper::IterateIndex(
	int64_t database_id,
	int64_t object_store_id,
	const IndexedDBIndexMetadata& index,
	LevelDbTombstoneSweeper::SweepStatus* sweep_status,
	Status* leveldb_status,
	int* round_iterations) {
	std::unique_ptr<leveldb::Iterator> iterator(
	database()->NewIterator({.verify_checksums = true, .fill_cache = false}));

	// If the sweeper exited early from an index scan, continue where it left off.
	if (sweep_state_.index_it_key) {
	iterator->Seek(sweep_state_.index_it_key->Encode());
	if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
	round_iterations)) {
	return false;
	}
	// Start at the first unvisited value.
	iterator->Next();
	if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
	round_iterations)) {
	return false;
	}
	} else {
	iterator->Seek(
	IndexDataKey::EncodeMinKey(database_id, object_store_id, index.id));
	if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
	round_iterations)) {
	return false;
	}
	}

	while (iterator->Valid()) {
	leveldb::Slice key_slice = iterator->key();
	std::string_view index_key_str = leveldb_env::MakeStringView(key_slice);
	std::string_view index_value_str =
	leveldb_env::MakeStringView(iterator->value());
	// See if we've reached the end of the current index or all indexes.
	sweep_state_.index_it_key.emplace(IndexDataKey());
	if (!IndexDataKey::Decode(&index_key_str,
	&sweep_state_.index_it_key.value()) \|\|
	sweep_state_.index_it_key->IndexId() != index.id) {
	break;
	}

	int64_t index_data_version;
	std::unique_ptr<IndexedDBKey> primary_key;

	if (!DecodeVarInt(&index_value_str, &index_data_version)) {
	iterator->Next();
	if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
	round_iterations)) {
	return false;
	}
	continue;
	}
	std::string encoded_primary_key(index_value_str);
	std::string exists_key = ExistsEntryKey::Encode(
	database_id, object_store_id, encoded_primary_key);

	std::string exists_value;
	Status s(
	database()->Get(leveldb::ReadOptions(), exists_key, &exists_value));
	if (!s.ok()) {
	iterator->Next();
	if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
	round_iterations)) {
	return false;
	}
	continue;
	}
	std::string_view exists_value_piece(exists_value);
	int64_t decoded_exists_version;
	if (!DecodeInt(&exists_value_piece, &decoded_exists_version) \|\|
	!exists_value_piece.empty()) {
	iterator->Next();
	if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
	round_iterations)) {
	return false;
	}
	continue;
	}

	if (decoded_exists_version != index_data_version) {
	has_writes_ = true;
	round_deletion_batch_.Delete(key_slice);
	++tombstones_found_;
	}

	iterator->Next();
	if (!ShouldContinueIteration(*iterator, sweep_status, leveldb_status,
	round_iterations)) {
	return false;
	}
	}
	sweep_state_.index_it_key = std::nullopt;
	return true;
	}

	} // namespace content::indexed_db::level_db