Inside Bitcoin

1// Copyright (c) 2011 The LevelDB 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. See the AUTHORS file for names of contributors.
4//
5// Decodes the blocks generated by block_builder.cc.
6
7#include "table/block.h"
8
9#include <algorithm>
10#include <cstdint>
11#include <vector>
12
13#include "leveldb/comparator.h"
14#include "table/format.h"
15#include "util/coding.h"
16#include "util/logging.h"
17
18namespace leveldb {
19
20inline uint32_t Block::NumRestarts() const {
21  assert(size_ >= sizeof(uint32_t));
22  return DecodeFixed32(data_ + size_ - sizeof(uint32_t));
23}
24
25Block::Block(const BlockContents& contents)
26    : data_(contents.data.data()),
27      size_(contents.data.size()),
28      owned_(contents.heap_allocated) {
29  if (size_ < sizeof(uint32_t)) {
30    size_ = 0;  // Error marker
31  } else {
32    size_t max_restarts_allowed = (size_ - sizeof(uint32_t)) / sizeof(uint32_t);
33    if (NumRestarts() > max_restarts_allowed) {
34      // The size is too small for NumRestarts()
35      size_ = 0;
36    } else {
37      restart_offset_ = size_ - (1 + NumRestarts()) * sizeof(uint32_t);
38    }
39  }
40}
41
42Block::~Block() {
43  if (owned_) {
44    delete[] data_;
45  }
46}
47
48// Helper routine: decode the next block entry starting at "p",
49// storing the number of shared key bytes, non_shared key bytes,
50// and the length of the value in "*shared", "*non_shared", and
51// "*value_length", respectively.  Will not dereference past "limit".
52//
53// If any errors are detected, returns nullptr.  Otherwise, returns a
54// pointer to the key delta (just past the three decoded values).
55static inline const char* DecodeEntry(const char* p, const char* limit,
56                                      uint32_t* shared, uint32_t* non_shared,
57                                      uint32_t* value_length) {
58  if (limit - p < 3) return nullptr;
59  *shared = reinterpret_cast<const uint8_t*>(p)[0];
60  *non_shared = reinterpret_cast<const uint8_t*>(p)[1];
61  *value_length = reinterpret_cast<const uint8_t*>(p)[2];
62  if ((*shared | *non_shared | *value_length) < 128) {
63    // Fast path: all three values are encoded in one byte each
64    p += 3;
65  } else {
66    if ((p = GetVarint32Ptr(p, limit, shared)) == nullptr) return nullptr;
67    if ((p = GetVarint32Ptr(p, limit, non_shared)) == nullptr) return nullptr;
68    if ((p = GetVarint32Ptr(p, limit, value_length)) == nullptr) return nullptr;
69  }
70
71  if (static_cast<uint32_t>(limit - p) < (*non_shared + *value_length)) {
72    return nullptr;
73  }
74  return p;
75}
76
77class Block::Iter : public Iterator {
78 private:
79  const Comparator* const comparator_;
80  const char* const data_;       // underlying block contents
81  uint32_t const restarts_;      // Offset of restart array (list of fixed32)
82  uint32_t const num_restarts_;  // Number of uint32_t entries in restart array
83
84  // current_ is offset in data_ of current entry.  >= restarts_ if !Valid
85  uint32_t current_;
86  uint32_t restart_index_;  // Index of restart block in which current_ falls
87  std::string key_;
88  Slice value_;
89  Status status_;
90
91  inline int Compare(const Slice& a, const Slice& b) const {
92    return comparator_->Compare(a, b);
93  }
94
95  // Return the offset in data_ just past the end of the current entry.
96  inline uint32_t NextEntryOffset() const {
97    return (value_.data() + value_.size()) - data_;
98  }
99
100  uint32_t GetRestartPoint(uint32_t index) {
101    assert(index < num_restarts_);
102    return DecodeFixed32(data_ + restarts_ + index * sizeof(uint32_t));
103  }
104
105  void SeekToRestartPoint(uint32_t index) {
106    key_.clear();
107    restart_index_ = index;
108    // current_ will be fixed by ParseNextKey();
109
110    // ParseNextKey() starts at the end of value_, so set value_ accordingly
111    uint32_t offset = GetRestartPoint(index);
112    value_ = Slice(data_ + offset, 0);
113  }
114
115 public:
116  Iter(const Comparator* comparator, const char* data, uint32_t restarts,
117       uint32_t num_restarts)
118      : comparator_(comparator),
119        data_(data),
120        restarts_(restarts),
121        num_restarts_(num_restarts),
122        current_(restarts_),
123        restart_index_(num_restarts_) {
124    assert(num_restarts_ > 0);
125  }
126
127  bool Valid() const override { return current_ < restarts_; }
128  Status status() const override { return status_; }
129  Slice key() const override {
130    assert(Valid());
131    return key_;
132  }
133  Slice value() const override {
134    assert(Valid());
135    return value_;
136  }
137
138  void Next() override {
139    assert(Valid());
140    ParseNextKey();
141  }
142
143  void Prev() override {
144    assert(Valid());
145
146    // Scan backwards to a restart point before current_
147    const uint32_t original = current_;
148    while (GetRestartPoint(restart_index_) >= original) {
149      if (restart_index_ == 0) {
150        // No more entries
151        current_ = restarts_;
152        restart_index_ = num_restarts_;
153        return;
154      }
155      restart_index_--;
156    }
157
158    SeekToRestartPoint(restart_index_);
159    do {
160      // Loop until end of current entry hits the start of original entry
161    } while (ParseNextKey() && NextEntryOffset() < original);
162  }
163
164  void Seek(const Slice& target) override {
165    // Binary search in restart array to find the last restart point
166    // with a key < target
167    uint32_t left = 0;
168    uint32_t right = num_restarts_ - 1;
169    while (left < right) {
170      uint32_t mid = (left + right + 1) / 2;
171      uint32_t region_offset = GetRestartPoint(mid);
172      uint32_t shared, non_shared, value_length;
173      const char* key_ptr =
174          DecodeEntry(data_ + region_offset, data_ + restarts_, &shared,
175                      &non_shared, &value_length);
176      if (key_ptr == nullptr || (shared != 0)) {
177        CorruptionError();
178        return;
179      }
180      Slice mid_key(key_ptr, non_shared);
181      if (Compare(mid_key, target) < 0) {
182        // Key at "mid" is smaller than "target".  Therefore all
183        // blocks before "mid" are uninteresting.
184        left = mid;
185      } else {
186        // Key at "mid" is >= "target".  Therefore all blocks at or
187        // after "mid" are uninteresting.
188        right = mid - 1;
189      }
190    }
191
192    // Linear search (within restart block) for first key >= target
193    SeekToRestartPoint(left);
194    while (true) {
195      if (!ParseNextKey()) {
196        return;
197      }
198      if (Compare(key_, target) >= 0) {
199        return;
200      }
201    }
202  }
203
204  void SeekToFirst() override {
205    SeekToRestartPoint(0);
206    ParseNextKey();
207  }
208
209  void SeekToLast() override {
210    SeekToRestartPoint(num_restarts_ - 1);
211    while (ParseNextKey() && NextEntryOffset() < restarts_) {
212      // Keep skipping
213    }
214  }
215
216 private:
217  void CorruptionError() {
218    current_ = restarts_;
219    restart_index_ = num_restarts_;
220    status_ = Status::Corruption("bad entry in block");
221    key_.clear();
222    value_.clear();
223  }
224
225  bool ParseNextKey() {
226    current_ = NextEntryOffset();
227    const char* p = data_ + current_;
228    const char* limit = data_ + restarts_;  // Restarts come right after data
229    if (p >= limit) {
230      // No more entries to return.  Mark as invalid.
231      current_ = restarts_;
232      restart_index_ = num_restarts_;
233      return false;
234    }
235
236    // Decode next entry
237    uint32_t shared, non_shared, value_length;
238    p = DecodeEntry(p, limit, &shared, &non_shared, &value_length);
239    if (p == nullptr || key_.size() < shared) {
240      CorruptionError();
241      return false;
242    } else {
243      key_.resize(shared);
244      key_.append(p, non_shared);
245      value_ = Slice(p + non_shared, value_length);
246      while (restart_index_ + 1 < num_restarts_ &&
247             GetRestartPoint(restart_index_ + 1) < current_) {
248        ++restart_index_;
249      }
250      return true;