1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
// 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_ = nullptr;
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_.get()) {
if (leaf_decoder_.get()) {
if (!leaf_decoder_->CanAdvance()) {
// The leaf has been exhausted. Remove it from the DFS stack.
leaf_decoder_ = nullptr;
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_.get());
return leaf_decoder_->last_record_rowid();
}
void VirtualCursor::AppendPageDecoder(int page_id) {
DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
DCHECK(leaf_decoder_.get() == nullptr)
<< __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_ = std::make_unique<LeafPageDecoder>(&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
|
