cursor.cc 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163
  1. // Copyright 2019 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. #include "sql/recover_module/cursor.h"
  5. #include <ostream>
  6. #include "base/containers/span.h"
  7. #include "sql/recover_module/table.h"
  8. namespace sql {
  9. namespace recover {
  10. VirtualCursor::VirtualCursor(VirtualTable* table)
  11. : table_(table),
  12. db_reader_(table),
  13. payload_reader_(&db_reader_),
  14. record_reader_(&payload_reader_, table->column_specs().size()) {
  15. DCHECK(table_ != nullptr);
  16. }
  17. VirtualCursor::~VirtualCursor() {
  18. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  19. table_->WillDeleteCursor(this);
  20. }
  21. int VirtualCursor::First() {
  22. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  23. inner_decoders_.clear();
  24. leaf_decoder_.Reset();
  25. AppendPageDecoder(table_->root_page_id());
  26. return Next();
  27. }
  28. int VirtualCursor::Next() {
  29. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  30. record_reader_.Reset();
  31. while (!inner_decoders_.empty() || leaf_decoder_.IsValid()) {
  32. if (leaf_decoder_.IsValid()) {
  33. if (!leaf_decoder_.CanAdvance()) {
  34. // The leaf has been exhausted. Remove it from the DFS stack.
  35. leaf_decoder_.Reset();
  36. continue;
  37. }
  38. if (!leaf_decoder_.TryAdvance())
  39. continue;
  40. if (!payload_reader_.Initialize(leaf_decoder_.last_record_size(),
  41. leaf_decoder_.last_record_offset())) {
  42. continue;
  43. }
  44. if (!record_reader_.Initialize())
  45. continue;
  46. // Found a healthy record.
  47. if (!IsAcceptableRecord()) {
  48. record_reader_.Reset();
  49. continue;
  50. }
  51. return SQLITE_OK;
  52. }
  53. // Try advancing the bottom-most inner node.
  54. DCHECK(!inner_decoders_.empty());
  55. InnerPageDecoder* inner_decoder = inner_decoders_.back().get();
  56. if (!inner_decoder->CanAdvance()) {
  57. // The inner node's sub-tree has been visited. Remove from the DFS stack.
  58. inner_decoders_.pop_back();
  59. continue;
  60. }
  61. int next_page_id = inner_decoder->TryAdvance();
  62. if (next_page_id == DatabasePageReader::kInvalidPageId)
  63. continue;
  64. AppendPageDecoder(next_page_id);
  65. }
  66. // The cursor reached the end of the table.
  67. return SQLITE_OK;
  68. }
  69. int VirtualCursor::ReadColumn(int column_index,
  70. sqlite3_context* result_context) {
  71. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  72. DCHECK_GE(column_index, 0);
  73. DCHECK_LT(column_index, static_cast<int>(table_->column_specs().size()));
  74. DCHECK(record_reader_.IsInitialized());
  75. if (table_->column_specs()[column_index].type == ModuleColumnType::kRowId) {
  76. sqlite3_result_int64(result_context, RowId());
  77. return SQLITE_OK;
  78. }
  79. if (record_reader_.ReadValue(column_index, result_context))
  80. return SQLITE_OK;
  81. return SQLITE_ERROR;
  82. }
  83. int64_t VirtualCursor::RowId() {
  84. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  85. DCHECK(record_reader_.IsInitialized());
  86. DCHECK(leaf_decoder_.IsValid());
  87. return leaf_decoder_.last_record_rowid();
  88. }
  89. void VirtualCursor::AppendPageDecoder(int page_id) {
  90. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  91. DCHECK(!leaf_decoder_.IsValid())
  92. << __func__
  93. << " must only be called when the current path has no leaf decoder";
  94. if (db_reader_.ReadPage(page_id) != SQLITE_OK)
  95. return;
  96. if (LeafPageDecoder::IsOnValidPage(&db_reader_)) {
  97. leaf_decoder_.Initialize(&db_reader_);
  98. return;
  99. }
  100. if (InnerPageDecoder::IsOnValidPage(&db_reader_)) {
  101. // Detect cycles.
  102. for (const auto& decoder : inner_decoders_) {
  103. if (decoder->page_id() == page_id)
  104. return;
  105. }
  106. // Give up on overly deep tree branches.
  107. //
  108. // SQLite supports up to 2^31 pages. SQLite ensures that inner nodes can
  109. // hold at least 4 child pointers, even in the presence of very large keys.
  110. // So, even poorly balanced trees should not exceed 100 nodes in depth.
  111. // InnerPageDecoder instances take up 32 bytes on 64-bit platforms.
  112. //
  113. // The depth limit below balances recovering broken trees with avoiding
  114. // excessive memory consumption.
  115. constexpr int kMaxTreeDepth = 10000;
  116. if (inner_decoders_.size() == kMaxTreeDepth)
  117. return;
  118. inner_decoders_.emplace_back(
  119. std::make_unique<InnerPageDecoder>(&db_reader_));
  120. return;
  121. }
  122. }
  123. bool VirtualCursor::IsAcceptableRecord() {
  124. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  125. DCHECK(record_reader_.IsInitialized());
  126. const std::vector<RecoveredColumnSpec>& column_specs = table_->column_specs();
  127. const int column_count = static_cast<int>(column_specs.size());
  128. for (int column_index = 0; column_index < column_count; ++column_index) {
  129. ValueType value_type = record_reader_.GetValueType(column_index);
  130. if (!column_specs[column_index].IsAcceptableValue(value_type))
  131. return false;
  132. }
  133. return true;
  134. }
  135. } // namespace recover
  136. } // namespace sql