table.cc raw
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 #include "leveldb/table.h"
6
7 #include "leveldb/cache.h"
8 #include "leveldb/comparator.h"
9 #include "leveldb/env.h"
10 #include "leveldb/filter_policy.h"
11 #include "leveldb/options.h"
12 #include "table/block.h"
13 #include "table/filter_block.h"
14 #include "table/format.h"
15 #include "table/two_level_iterator.h"
16 #include "util/coding.h"
17
18 namespace leveldb {
19
20 struct Table::Rep {
21 ~Rep() {
22 delete filter;
23 delete[] filter_data;
24 delete index_block;
25 }
26
27 Options options;
28 Status status;
29 RandomAccessFile* file;
30 uint64_t cache_id;
31 FilterBlockReader* filter;
32 const char* filter_data;
33
34 BlockHandle metaindex_handle; // Handle to metaindex_block: saved from footer
35 Block* index_block;
36 };
37
38 Status Table::Open(const Options& options, RandomAccessFile* file,
39 uint64_t size, Table** table) {
40 *table = nullptr;
41 if (size < Footer::kEncodedLength) {
42 return Status::Corruption("file is too short to be an sstable");
43 }
44
45 char footer_space[Footer::kEncodedLength];
46 Slice footer_input;
47 Status s = file->Read(size - Footer::kEncodedLength, Footer::kEncodedLength,
48 &footer_input, footer_space);
49 if (!s.ok()) return s;
50
51 Footer footer;
52 s = footer.DecodeFrom(&footer_input);
53 if (!s.ok()) return s;
54
55 // Read the index block
56 BlockContents index_block_contents;
57 if (s.ok()) {
58 ReadOptions opt;
59 if (options.paranoid_checks) {
60 opt.verify_checksums = true;
61 }
62 s = ReadBlock(file, opt, footer.index_handle(), &index_block_contents);
63 }
64
65 if (s.ok()) {
66 // We've successfully read the footer and the index block: we're
67 // ready to serve requests.
68 Block* index_block = new Block(index_block_contents);
69 Rep* rep = new Table::Rep;
70 rep->options = options;
71 rep->file = file;
72 rep->metaindex_handle = footer.metaindex_handle();
73 rep->index_block = index_block;
74 rep->cache_id = (options.block_cache ? options.block_cache->NewId() : 0);
75 rep->filter_data = nullptr;
76 rep->filter = nullptr;
77 *table = new Table(rep);
78 (*table)->ReadMeta(footer);
79 }
80
81 return s;
82 }
83
84 void Table::ReadMeta(const Footer& footer) {
85 if (rep_->options.filter_policy == nullptr) {
86 return; // Do not need any metadata
87 }
88
89 // TODO(sanjay): Skip this if footer.metaindex_handle() size indicates
90 // it is an empty block.
91 ReadOptions opt;
92 if (rep_->options.paranoid_checks) {
93 opt.verify_checksums = true;
94 }
95 BlockContents contents;
96 if (!ReadBlock(rep_->file, opt, footer.metaindex_handle(), &contents).ok()) {
97 // Do not propagate errors since meta info is not needed for operation
98 return;
99 }
100 Block* meta = new Block(contents);
101
102 Iterator* iter = meta->NewIterator(BytewiseComparator());
103 std::string key = "filter.";
104 key.append(rep_->options.filter_policy->Name());
105 iter->Seek(key);
106 if (iter->Valid() && iter->key() == Slice(key)) {
107 ReadFilter(iter->value());
108 }
109 delete iter;
110 delete meta;
111 }
112
113 void Table::ReadFilter(const Slice& filter_handle_value) {
114 Slice v = filter_handle_value;
115 BlockHandle filter_handle;
116 if (!filter_handle.DecodeFrom(&v).ok()) {
117 return;
118 }
119
120 // We might want to unify with ReadBlock() if we start
121 // requiring checksum verification in Table::Open.
122 ReadOptions opt;
123 if (rep_->options.paranoid_checks) {
124 opt.verify_checksums = true;
125 }
126 BlockContents block;
127 if (!ReadBlock(rep_->file, opt, filter_handle, &block).ok()) {
128 return;
129 }
130 if (block.heap_allocated) {
131 rep_->filter_data = block.data.data(); // Will need to delete later
132 }
133 rep_->filter = new FilterBlockReader(rep_->options.filter_policy, block.data);
134 }
135
136 Table::~Table() { delete rep_; }
137
138 static void DeleteBlock(void* arg, void* ignored) {
139 delete reinterpret_cast<Block*>(arg);
140 }
141
142 static void DeleteCachedBlock(const Slice& key, void* value) {
143 Block* block = reinterpret_cast<Block*>(value);
144 delete block;
145 }
146
147 static void ReleaseBlock(void* arg, void* h) {
148 Cache* cache = reinterpret_cast<Cache*>(arg);
149 Cache::Handle* handle = reinterpret_cast<Cache::Handle*>(h);
150 cache->Release(handle);
151 }
152
153 // Convert an index iterator value (i.e., an encoded BlockHandle)
154 // into an iterator over the contents of the corresponding block.
155 Iterator* Table::BlockReader(void* arg, const ReadOptions& options,
156 const Slice& index_value) {
157 Table* table = reinterpret_cast<Table*>(arg);
158 Cache* block_cache = table->rep_->options.block_cache;
159 Block* block = nullptr;
160 Cache::Handle* cache_handle = nullptr;
161
162 BlockHandle handle;
163 Slice input = index_value;
164 Status s = handle.DecodeFrom(&input);
165 // We intentionally allow extra stuff in index_value so that we
166 // can add more features in the future.
167
168 if (s.ok()) {
169 BlockContents contents;
170 if (block_cache != nullptr) {
171 char cache_key_buffer[16];
172 EncodeFixed64(cache_key_buffer, table->rep_->cache_id);
173 EncodeFixed64(cache_key_buffer + 8, handle.offset());
174 Slice key(cache_key_buffer, sizeof(cache_key_buffer));
175 cache_handle = block_cache->Lookup(key);
176 if (cache_handle != nullptr) {
177 block = reinterpret_cast<Block*>(block_cache->Value(cache_handle));
178 } else {
179 s = ReadBlock(table->rep_->file, options, handle, &contents);
180 if (s.ok()) {
181 block = new Block(contents);
182 if (contents.cachable && options.fill_cache) {
183 cache_handle = block_cache->Insert(key, block, block->size(),
184 &DeleteCachedBlock);
185 }
186 }
187 }
188 } else {
189 s = ReadBlock(table->rep_->file, options, handle, &contents);
190 if (s.ok()) {
191 block = new Block(contents);
192 }
193 }
194 }
195
196 Iterator* iter;
197 if (block != nullptr) {
198 iter = block->NewIterator(table->rep_->options.comparator);
199 if (cache_handle == nullptr) {
200 iter->RegisterCleanup(&DeleteBlock, block, nullptr);
201 } else {
202 iter->RegisterCleanup(&ReleaseBlock, block_cache, cache_handle);
203 }
204 } else {
205 iter = NewErrorIterator(s);
206 }
207 return iter;
208 }
209
210 Iterator* Table::NewIterator(const ReadOptions& options) const {
211 return NewTwoLevelIterator(
212 rep_->index_block->NewIterator(rep_->options.comparator),
213 &Table::BlockReader, const_cast<Table*>(this), options);
214 }
215
216 Status Table::InternalGet(const ReadOptions& options, const Slice& k, void* arg,
217 void (*handle_result)(void*, const Slice&,
218 const Slice&)) {
219 Status s;
220 Iterator* iiter = rep_->index_block->NewIterator(rep_->options.comparator);
221 iiter->Seek(k);
222 if (iiter->Valid()) {
223 Slice handle_value = iiter->value();
224 FilterBlockReader* filter = rep_->filter;
225 BlockHandle handle;
226 if (filter != nullptr && handle.DecodeFrom(&handle_value).ok() &&
227 !filter->KeyMayMatch(handle.offset(), k)) {
228 // Not found
229 } else {
230 Iterator* block_iter = BlockReader(this, options, iiter->value());
231 block_iter->Seek(k);
232 if (block_iter->Valid()) {
233 (*handle_result)(arg, block_iter->key(), block_iter->value());
234 }
235 s = block_iter->status();
236 delete block_iter;
237 }
238 }
239 if (s.ok()) {
240 s = iiter->status();
241 }
242 delete iiter;
243 return s;
244 }
245
246 uint64_t Table::ApproximateOffsetOf(const Slice& key) const {
247 Iterator* index_iter =
248 rep_->index_block->NewIterator(rep_->options.comparator);
249 index_iter->Seek(key);
250 uint64_t result;
251 if (index_iter->Valid()) {
252 BlockHandle handle;
253 Slice input = index_iter->value();
254 Status s = handle.DecodeFrom(&input);
255 if (s.ok()) {
256 result = handle.offset();
257 } else {
258 // Strange: we can't decode the block handle in the index block.
259 // We'll just return the offset of the metaindex block, which is
260 // close to the whole file size for this case.
261 result = rep_->metaindex_handle.offset();
262 }
263 } else {
264 // key is past the last key in the file. Approximate the offset
265 // by returning the offset of the metaindex block (which is
266 // right near the end of the file).
267 result = rep_->metaindex_handle.offset();
268 }
269 delete index_iter;
270 return result;
271 }
272
273 } // namespace leveldb
274