123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163 |
- // Copyright 2019 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "sql/recover_module/cursor.h"
- #include <ostream>
- #include "base/containers/span.h"
- #include "sql/recover_module/table.h"
- namespace sql {
- namespace recover {
- VirtualCursor::VirtualCursor(VirtualTable* table)
- : table_(table),
- db_reader_(table),
- payload_reader_(&db_reader_),
- record_reader_(&payload_reader_, table->column_specs().size()) {
- DCHECK(table_ != nullptr);
- }
- VirtualCursor::~VirtualCursor() {
- DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
- table_->WillDeleteCursor(this);
- }
- int VirtualCursor::First() {
- DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
- inner_decoders_.clear();
- leaf_decoder_.Reset();
- AppendPageDecoder(table_->root_page_id());
- return Next();
- }
- int VirtualCursor::Next() {
- DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
- record_reader_.Reset();
- while (!inner_decoders_.empty() || leaf_decoder_.IsValid()) {
- if (leaf_decoder_.IsValid()) {
- if (!leaf_decoder_.CanAdvance()) {
- // The leaf has been exhausted. Remove it from the DFS stack.
- leaf_decoder_.Reset();
- continue;
- }
- if (!leaf_decoder_.TryAdvance())
- continue;
- if (!payload_reader_.Initialize(leaf_decoder_.last_record_size(),
- leaf_decoder_.last_record_offset())) {
- continue;
- }
- if (!record_reader_.Initialize())
- continue;
- // Found a healthy record.
- if (!IsAcceptableRecord()) {
- record_reader_.Reset();
- continue;
- }
- return SQLITE_OK;
- }
- // Try advancing the bottom-most inner node.
- DCHECK(!inner_decoders_.empty());
- InnerPageDecoder* inner_decoder = inner_decoders_.back().get();
- if (!inner_decoder->CanAdvance()) {
- // The inner node's sub-tree has been visited. Remove from the DFS stack.
- inner_decoders_.pop_back();
- continue;
- }
- int next_page_id = inner_decoder->TryAdvance();
- if (next_page_id == DatabasePageReader::kInvalidPageId)
- continue;
- AppendPageDecoder(next_page_id);
- }
- // The cursor reached the end of the table.
- return SQLITE_OK;
- }
- int VirtualCursor::ReadColumn(int column_index,
- sqlite3_context* result_context) {
- DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
- DCHECK_GE(column_index, 0);
- DCHECK_LT(column_index, static_cast<int>(table_->column_specs().size()));
- DCHECK(record_reader_.IsInitialized());
- if (table_->column_specs()[column_index].type == ModuleColumnType::kRowId) {
- sqlite3_result_int64(result_context, RowId());
- return SQLITE_OK;
- }
- if (record_reader_.ReadValue(column_index, result_context))
- return SQLITE_OK;
- return SQLITE_ERROR;
- }
- int64_t VirtualCursor::RowId() {
- DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
- DCHECK(record_reader_.IsInitialized());
- DCHECK(leaf_decoder_.IsValid());
- return leaf_decoder_.last_record_rowid();
- }
- void VirtualCursor::AppendPageDecoder(int page_id) {
- DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
- DCHECK(!leaf_decoder_.IsValid())
- << __func__
- << " must only be called when the current path has no leaf decoder";
- if (db_reader_.ReadPage(page_id) != SQLITE_OK)
- return;
- if (LeafPageDecoder::IsOnValidPage(&db_reader_)) {
- leaf_decoder_.Initialize(&db_reader_);
- return;
- }
- if (InnerPageDecoder::IsOnValidPage(&db_reader_)) {
- // Detect cycles.
- for (const auto& decoder : inner_decoders_) {
- if (decoder->page_id() == page_id)
- return;
- }
- // Give up on overly deep tree branches.
- //
- // SQLite supports up to 2^31 pages. SQLite ensures that inner nodes can
- // hold at least 4 child pointers, even in the presence of very large keys.
- // So, even poorly balanced trees should not exceed 100 nodes in depth.
- // InnerPageDecoder instances take up 32 bytes on 64-bit platforms.
- //
- // The depth limit below balances recovering broken trees with avoiding
- // excessive memory consumption.
- constexpr int kMaxTreeDepth = 10000;
- if (inner_decoders_.size() == kMaxTreeDepth)
- return;
- inner_decoders_.emplace_back(
- std::make_unique<InnerPageDecoder>(&db_reader_));
- return;
- }
- }
- bool VirtualCursor::IsAcceptableRecord() {
- DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
- DCHECK(record_reader_.IsInitialized());
- const std::vector<RecoveredColumnSpec>& column_specs = table_->column_specs();
- const int column_count = static_cast<int>(column_specs.size());
- for (int column_index = 0; column_index < column_count; ++column_index) {
- ValueType value_type = record_reader_.GetValueType(column_index);
- if (!column_specs[column_index].IsAcceptableValue(value_type))
- return false;
- }
- return true;
- }
- } // namespace recover
- } // namespace sql
|