btree.cc 9.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259
  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/btree.h"
  5. #include <algorithm>
  6. #include <limits>
  7. #include <ostream>
  8. #include <type_traits>
  9. #include "base/check_op.h"
  10. #include "sql/recover_module/integers.h"
  11. #include "sql/recover_module/pager.h"
  12. #include "third_party/sqlite/sqlite3.h"
  13. namespace sql {
  14. namespace recover {
  15. namespace {
  16. // The SQLite database format is documented at the following URLs.
  17. // https://www.sqlite.org/fileformat.html
  18. // https://www.sqlite.org/fileformat2.html
  19. constexpr uint8_t kInnerTablePageType = 0x05;
  20. constexpr uint8_t kLeafTablePageType = 0x0D;
  21. // Offset from the page header to the page type byte.
  22. constexpr int kPageTypePageOffset = 0;
  23. // Offset from the page header to the 2-byte cell count.
  24. constexpr int kCellCountPageOffset = 3;
  25. // Offset from an inner page header to the 4-byte last child page ID.
  26. constexpr int kLastChildIdInnerPageOffset = 8;
  27. // Offset from an inner page header to the cell pointer array.
  28. constexpr int kFirstCellOfsetInnerPageOffset = 12;
  29. // Offset from a leaf page header to the cell pointer array.
  30. constexpr int kFirstCellOfsetLeafPageOffset = 8;
  31. } // namespace
  32. #if !DCHECK_IS_ON()
  33. // In DCHECKed builds, the decoder contains a sequence checker, which has a
  34. // non-trivial destructor.
  35. static_assert(std::is_trivially_destructible<InnerPageDecoder>::value,
  36. "Move the destructor to the .cc file if it's non-trival");
  37. #endif // !DCHECK_IS_ON()
  38. InnerPageDecoder::InnerPageDecoder(DatabasePageReader* db_reader) noexcept
  39. : page_id_(db_reader->page_id()),
  40. db_reader_(db_reader),
  41. cell_count_(ComputeCellCount(db_reader)),
  42. next_read_index_(0) {
  43. DCHECK(IsOnValidPage(db_reader));
  44. DCHECK(DatabasePageReader::IsValidPageId(page_id_));
  45. }
  46. int InnerPageDecoder::TryAdvance() {
  47. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  48. DCHECK(CanAdvance());
  49. const int sqlite_status = db_reader_->ReadPage(page_id_);
  50. if (sqlite_status != SQLITE_OK) {
  51. // TODO(pwnall): UMA the error code.
  52. next_read_index_ = cell_count_ + 1; // End the reading process.
  53. return DatabasePageReader::kInvalidPageId;
  54. }
  55. const uint8_t* const page_data = db_reader_->page_data();
  56. const int read_index = next_read_index_;
  57. next_read_index_ += 1;
  58. if (read_index == cell_count_)
  59. return LoadBigEndianInt32(page_data + kLastChildIdInnerPageOffset);
  60. const int cell_pointer_offset =
  61. kFirstCellOfsetInnerPageOffset + (read_index << 1);
  62. DCHECK_LE(cell_pointer_offset + 2, db_reader_->page_size())
  63. << "ComputeCellCount() used an incorrect upper bound";
  64. const int cell_pointer = LoadBigEndianUint16(page_data + cell_pointer_offset);
  65. static_assert(std::numeric_limits<uint16_t>::max() + 4 <
  66. std::numeric_limits<int>::max(),
  67. "The addition below may overflow");
  68. if (cell_pointer + 4 >= db_reader_->page_size()) {
  69. // Each cell needs 1 byte for the rowid varint, in addition to the 4 bytes
  70. // for the child page number that will be read below. Skip cells that
  71. // obviously go over the page end.
  72. return DatabasePageReader::kInvalidPageId;
  73. }
  74. if (cell_pointer < kFirstCellOfsetInnerPageOffset) {
  75. // The pointer points into the cell's header.
  76. return DatabasePageReader::kInvalidPageId;
  77. }
  78. return LoadBigEndianInt32(page_data + cell_pointer);
  79. }
  80. // static
  81. bool InnerPageDecoder::IsOnValidPage(DatabasePageReader* db_reader) {
  82. static_assert(kPageTypePageOffset < DatabasePageReader::kMinUsablePageSize,
  83. "The check below may perform an out-of-bounds memory access");
  84. return db_reader->page_data()[kPageTypePageOffset] == kInnerTablePageType;
  85. }
  86. // static
  87. int InnerPageDecoder::ComputeCellCount(DatabasePageReader* db_reader) {
  88. // The B-tree page header stores the cell count.
  89. int header_count =
  90. LoadBigEndianUint16(db_reader->page_data() + kCellCountPageOffset);
  91. static_assert(
  92. kCellCountPageOffset + 2 <= DatabasePageReader::kMinUsablePageSize,
  93. "The read above may be out of bounds");
  94. // However, the data may be corrupted. So, use an upper bound based on the
  95. // fact that the cell pointer array should never extend past the end of the
  96. // page.
  97. //
  98. // The page size is always even, because it is either a power of two, for
  99. // most pages, or a power of two minus 100, for the first database page. The
  100. // cell pointer array starts at offset 12. So, each cell pointer must be
  101. // separated from the page buffer's end by an even number of bytes.
  102. DCHECK((db_reader->page_size() - kFirstCellOfsetInnerPageOffset) % 2 == 0);
  103. int upper_bound =
  104. (db_reader->page_size() - kFirstCellOfsetInnerPageOffset) >> 1;
  105. static_assert(
  106. kFirstCellOfsetInnerPageOffset <= DatabasePageReader::kMinUsablePageSize,
  107. "The |upper_bound| computation above may overflow");
  108. return std::min(header_count, upper_bound);
  109. }
  110. #if !DCHECK_IS_ON()
  111. // In DCHECKed builds, the decoder contains a sequence checker, which has a
  112. // non-trivial destructor.
  113. static_assert(std::is_trivially_destructible<LeafPageDecoder>::value,
  114. "Move the destructor to the .cc file if it's non-trival");
  115. #endif // !DCHECK_IS_ON()
  116. LeafPageDecoder::LeafPageDecoder() noexcept = default;
  117. void LeafPageDecoder::Initialize(DatabasePageReader* db_reader) {
  118. page_id_ = db_reader->page_id();
  119. db_reader_ = db_reader;
  120. cell_count_ = ComputeCellCount(db_reader);
  121. next_read_index_ = 0;
  122. last_record_size_ = 0;
  123. DCHECK(IsOnValidPage(db_reader));
  124. DCHECK(DatabasePageReader::IsValidPageId(page_id_));
  125. }
  126. void LeafPageDecoder::Reset() {
  127. db_reader_ = nullptr;
  128. }
  129. bool LeafPageDecoder::TryAdvance() {
  130. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  131. DCHECK(CanAdvance());
  132. #if DCHECK_IS_ON()
  133. // DCHECKs use last_record_size == 0 to check for incorrect access to the
  134. // decoder's state.
  135. last_record_size_ = 0;
  136. #endif // DCHECK_IS_ON()
  137. const int sqlite_status = db_reader_->ReadPage(page_id_);
  138. if (sqlite_status != SQLITE_OK) {
  139. // TODO(pwnall): UMA the error code.
  140. next_read_index_ = cell_count_; // End the reading process.
  141. return false;
  142. }
  143. const uint8_t* page_data = db_reader_->page_data();
  144. const int read_index = next_read_index_;
  145. next_read_index_ += 1;
  146. const int cell_pointer_offset =
  147. kFirstCellOfsetLeafPageOffset + (read_index << 1);
  148. DCHECK_LE(cell_pointer_offset + 2, db_reader_->page_size())
  149. << "ComputeCellCount() used an incorrect upper bound";
  150. const int cell_pointer = LoadBigEndianUint16(page_data + cell_pointer_offset);
  151. static_assert(std::numeric_limits<uint16_t>::max() + 3 <
  152. std::numeric_limits<int>::max(),
  153. "The addition below may overflow");
  154. if (cell_pointer + 3 >= db_reader_->page_size()) {
  155. // Each cell needs at least 1 byte for page type varint, 1 byte for the
  156. // rowid varint, and 1 byte for the record header size varint. Skip cells
  157. // that obviously go over the page end.
  158. return false;
  159. }
  160. if (cell_pointer < kFirstCellOfsetLeafPageOffset) {
  161. // The pointer points into the cell's header.
  162. return false;
  163. }
  164. const uint8_t* const cell_start = page_data + cell_pointer;
  165. const uint8_t* const page_end = page_data + db_reader_->page_size();
  166. DCHECK_LT(cell_start, page_end) << "Failed to skip over empty cells";
  167. const uint8_t* rowid_start;
  168. std::tie(last_record_size_, rowid_start) = ParseVarint(cell_start, page_end);
  169. if (rowid_start == page_end) {
  170. // The value size varint extended to the end of the page, so the rowid
  171. // varint starts past the page end.
  172. return false;
  173. }
  174. if (last_record_size_ <= 0) {
  175. // Each payload needs at least one varint. Skip empty payloads.
  176. #if DCHECK_IS_ON()
  177. // DCHECKs use last_record_size == 0 to check for incorrect access to the
  178. // decoder's state.
  179. last_record_size_ = 0;
  180. #endif // DCHECK_IS_ON()
  181. return false;
  182. }
  183. const uint8_t* record_start;
  184. std::tie(last_record_rowid_, record_start) =
  185. ParseVarint(rowid_start, page_end);
  186. if (record_start == page_end) {
  187. // The rowid varint extended to the end of the page, so the record starts
  188. // past the page end. Records need at least 1 byte for their header size
  189. // varint, so this suggests corruption.
  190. last_record_size_ = 0;
  191. return false;
  192. }
  193. last_record_offset_ = record_start - page_data;
  194. return true;
  195. }
  196. // static
  197. bool LeafPageDecoder::IsOnValidPage(DatabasePageReader* db_reader) {
  198. static_assert(kPageTypePageOffset < DatabasePageReader::kMinUsablePageSize,
  199. "The check below may perform an out-of-bounds memory access");
  200. return db_reader->page_data()[kPageTypePageOffset] == kLeafTablePageType;
  201. }
  202. // static
  203. int LeafPageDecoder::ComputeCellCount(DatabasePageReader* db_reader) {
  204. // See InnerPageDecoder::ComputeCellCount() for the reasoning behind the code.
  205. int header_count =
  206. LoadBigEndianUint16(db_reader->page_data() + kCellCountPageOffset);
  207. static_assert(
  208. kCellCountPageOffset + 2 <= DatabasePageReader::kMinUsablePageSize,
  209. "The read above may be out of bounds");
  210. int upper_bound =
  211. (db_reader->page_size() - kFirstCellOfsetLeafPageOffset) >> 1;
  212. static_assert(
  213. kFirstCellOfsetLeafPageOffset <= DatabasePageReader::kMinUsablePageSize,
  214. "The |upper_bound| computation above may overflow");
  215. return std::min(header_count, upper_bound);
  216. }
  217. } // namespace recover
  218. } // namespace sql