Branch data Line data Source code
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 [ + - ]: 155 : struct Table::Rep {
21 : 155 : ~Rep() {
22 [ + - ]: 155 : delete filter;
23 [ + + ]: 155 : delete[] filter_data;
24 [ + - ]: 155 : delete index_block;
25 [ - + ]: 155 : }
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 : 155 : Status Table::Open(const Options& options, RandomAccessFile* file,
39 : : uint64_t size, Table** table) {
40 : 155 : *table = nullptr;
41 [ - + ]: 155 : if (size < Footer::kEncodedLength) {
42 : 0 : return Status::Corruption("file is too short to be an sstable");
43 : : }
44 : :
45 : 155 : char footer_space[Footer::kEncodedLength];
46 : 155 : Slice footer_input;
47 : 155 : Status s = file->Read(size - Footer::kEncodedLength, Footer::kEncodedLength,
48 : 155 : &footer_input, footer_space);
49 [ - + ]: 155 : if (!s.ok()) return s;
50 : :
51 [ + - ]: 155 : Footer footer;
52 [ + - - + ]: 155 : s = footer.DecodeFrom(&footer_input);
53 [ - + ]: 155 : if (!s.ok()) return s;
54 : :
55 : : // Read the index block
56 [ + - ]: 155 : BlockContents index_block_contents;
57 : 155 : if (s.ok()) {
58 : 155 : ReadOptions opt;
59 [ + - ]: 155 : if (options.paranoid_checks) {
60 : 155 : opt.verify_checksums = true;
61 : : }
62 [ + - - + ]: 155 : s = ReadBlock(file, opt, footer.index_handle(), &index_block_contents);
63 : : }
64 : :
65 [ + - ]: 155 : if (s.ok()) {
66 : : // We've successfully read the footer and the index block: we're
67 : : // ready to serve requests.
68 [ + - + - ]: 155 : Block* index_block = new Block(index_block_contents);
69 [ + - + - ]: 155 : Rep* rep = new Table::Rep;
70 : 155 : rep->options = options;
71 : 155 : rep->file = file;
72 : 155 : rep->metaindex_handle = footer.metaindex_handle();
73 : 155 : rep->index_block = index_block;
74 [ + - + - ]: 155 : rep->cache_id = (options.block_cache ? options.block_cache->NewId() : 0);
75 : 155 : rep->filter_data = nullptr;
76 : 155 : rep->filter = nullptr;
77 [ + - + - ]: 155 : *table = new Table(rep);
78 [ + - ]: 155 : (*table)->ReadMeta(footer);
79 : : }
80 : :
81 : 155 : return s;
82 : 155 : }
83 : :
84 : 155 : void Table::ReadMeta(const Footer& footer) {
85 [ + - ]: 155 : 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 : 155 : ReadOptions opt;
92 [ + - ]: 155 : if (rep_->options.paranoid_checks) {
93 : 155 : opt.verify_checksums = true;
94 : : }
95 : 155 : BlockContents contents;
96 [ - + + - ]: 155 : 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 [ + - ]: 155 : Block* meta = new Block(contents);
101 : :
102 : 155 : Iterator* iter = meta->NewIterator(BytewiseComparator());
103 : 155 : std::string key = "filter.";
104 [ + - + - ]: 155 : key.append(rep_->options.filter_policy->Name());
105 [ - + + - ]: 155 : iter->Seek(key);
106 [ + - + - : 310 : if (iter->Valid() && iter->key() == Slice(key)) {
+ - + - ]
107 [ + - + - ]: 155 : ReadFilter(iter->value());
108 : : }
109 [ + - ]: 155 : delete iter;
110 [ + - ]: 155 : delete meta;
111 : 155 : }
112 : :
113 : 155 : void Table::ReadFilter(const Slice& filter_handle_value) {
114 : 155 : Slice v = filter_handle_value;
115 : 155 : BlockHandle filter_handle;
116 [ - + + - ]: 155 : 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 : 155 : ReadOptions opt;
123 [ + - ]: 155 : if (rep_->options.paranoid_checks) {
124 : 155 : opt.verify_checksums = true;
125 : : }
126 : 155 : BlockContents block;
127 [ - + + - ]: 155 : if (!ReadBlock(rep_->file, opt, filter_handle, &block).ok()) {
128 : : return;
129 : : }
130 [ + + ]: 155 : if (block.heap_allocated) {
131 : 1 : rep_->filter_data = block.data.data(); // Will need to delete later
132 : : }
133 [ + - ]: 155 : rep_->filter = new FilterBlockReader(rep_->options.filter_policy, block.data);
134 : : }
135 : :
136 [ + - ]: 155 : Table::~Table() { delete rep_; }
137 : :
138 : 1489 : static void DeleteBlock(void* arg, void* ignored) {
139 [ + - ]: 1489 : delete reinterpret_cast<Block*>(arg);
140 : 1489 : }
141 : :
142 : 255 : static void DeleteCachedBlock(const Slice& key, void* value) {
143 : 255 : Block* block = reinterpret_cast<Block*>(value);
144 [ + - ]: 255 : delete block;
145 : 255 : }
146 : :
147 : 63694 : static void ReleaseBlock(void* arg, void* h) {
148 : 63694 : Cache* cache = reinterpret_cast<Cache*>(arg);
149 : 63694 : Cache::Handle* handle = reinterpret_cast<Cache::Handle*>(h);
150 : 63694 : cache->Release(handle);
151 : 63694 : }
152 : :
153 : : // Convert an index iterator value (i.e., an encoded BlockHandle)
154 : : // into an iterator over the contents of the corresponding block.
155 : 65183 : Iterator* Table::BlockReader(void* arg, const ReadOptions& options,
156 : : const Slice& index_value) {
157 : 65183 : Table* table = reinterpret_cast<Table*>(arg);
158 : 65183 : Cache* block_cache = table->rep_->options.block_cache;
159 : 65183 : Block* block = nullptr;
160 : 65183 : Cache::Handle* cache_handle = nullptr;
161 : :
162 : 65183 : BlockHandle handle;
163 : 65183 : Slice input = index_value;
164 : 65183 : 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 [ + - ]: 65183 : if (s.ok()) {
169 [ + - ]: 65183 : BlockContents contents;
170 [ + - ]: 65183 : if (block_cache != nullptr) {
171 : 65183 : char cache_key_buffer[16];
172 : 65183 : EncodeFixed64(cache_key_buffer, table->rep_->cache_id);
173 : 65183 : EncodeFixed64(cache_key_buffer + 8, handle.offset());
174 [ + - ]: 65183 : Slice key(cache_key_buffer, sizeof(cache_key_buffer));
175 [ + - ]: 65183 : cache_handle = block_cache->Lookup(key);
176 [ + + ]: 65183 : if (cache_handle != nullptr) {
177 [ + - ]: 63439 : block = reinterpret_cast<Block*>(block_cache->Value(cache_handle));
178 : : } else {
179 [ + - - + ]: 1744 : s = ReadBlock(table->rep_->file, options, handle, &contents);
180 [ + - ]: 1744 : if (s.ok()) {
181 [ + - + - ]: 1744 : block = new Block(contents);
182 [ + + + - ]: 1744 : if (contents.cachable && options.fill_cache) {
183 [ + - ]: 255 : cache_handle = block_cache->Insert(key, block, block->size(),
184 : : &DeleteCachedBlock);
185 : : }
186 : : }
187 : : }
188 : : } else {
189 [ # # # # ]: 0 : s = ReadBlock(table->rep_->file, options, handle, &contents);
190 [ # # ]: 0 : if (s.ok()) {
191 [ # # # # ]: 0 : block = new Block(contents);
192 : : }
193 : : }
194 : : }
195 : :
196 : 64928 : Iterator* iter;
197 [ + - ]: 64928 : if (block != nullptr) {
198 [ + - ]: 65183 : iter = block->NewIterator(table->rep_->options.comparator);
199 [ + + ]: 65183 : if (cache_handle == nullptr) {
200 [ + - ]: 1489 : iter->RegisterCleanup(&DeleteBlock, block, nullptr);
201 : : } else {
202 [ + - ]: 63694 : iter->RegisterCleanup(&ReleaseBlock, block_cache, cache_handle);
203 : : }
204 : : } else {
205 [ # # ]: 0 : iter = NewErrorIterator(s);
206 : : }
207 [ - + ]: 65183 : return iter;
208 : 65183 : }
209 : :
210 : 384 : Iterator* Table::NewIterator(const ReadOptions& options) const {
211 : 384 : return NewTwoLevelIterator(
212 : 384 : rep_->index_block->NewIterator(rep_->options.comparator),
213 : 384 : &Table::BlockReader, const_cast<Table*>(this), options);
214 : : }
215 : :
216 : 1292221 : Status Table::InternalGet(const ReadOptions& options, const Slice& k, void* arg,
217 : : void (*handle_result)(void*, const Slice&,
218 : : const Slice&)) {
219 [ + - ]: 1292221 : Status s;
220 [ + - ]: 1292221 : Iterator* iiter = rep_->index_block->NewIterator(rep_->options.comparator);
221 [ + - ]: 1292221 : iiter->Seek(k);
222 [ + - + - ]: 1292221 : if (iiter->Valid()) {
223 [ + - ]: 1292221 : Slice handle_value = iiter->value();
224 : 1292221 : FilterBlockReader* filter = rep_->filter;
225 [ + - ]: 1292221 : BlockHandle handle;
226 [ + - + - : 3876663 : if (filter != nullptr && handle.DecodeFrom(&handle_value).ok() &&
+ - + + +
+ ]
227 [ + - ]: 1292221 : !filter->KeyMayMatch(handle.offset(), k)) {
228 : : // Not found
229 : : } else {
230 [ + - + - ]: 64822 : Iterator* block_iter = BlockReader(this, options, iiter->value());
231 [ + - ]: 64822 : block_iter->Seek(k);
232 [ + - + + ]: 64822 : if (block_iter->Valid()) {
233 [ + - + - : 64816 : (*handle_result)(arg, block_iter->key(), block_iter->value());
+ - ]
234 : : }
235 [ + - - + ]: 64822 : s = block_iter->status();
236 [ + - ]: 64822 : delete block_iter;
237 : : }
238 : : }
239 [ + - ]: 1292221 : if (s.ok()) {
240 [ + - - + ]: 1292221 : s = iiter->status();
241 : : }
242 [ + - ]: 1292221 : delete iiter;
243 : 1292221 : return s;
244 : 0 : }
245 : :
246 : 110 : uint64_t Table::ApproximateOffsetOf(const Slice& key) const {
247 : 110 : Iterator* index_iter =
248 : 110 : rep_->index_block->NewIterator(rep_->options.comparator);
249 : 110 : index_iter->Seek(key);
250 : 110 : uint64_t result;
251 [ + - ]: 110 : if (index_iter->Valid()) {
252 : 110 : BlockHandle handle;
253 : 110 : Slice input = index_iter->value();
254 : 110 : Status s = handle.DecodeFrom(&input);
255 [ + - ]: 110 : if (s.ok()) {
256 : 110 : 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 : 0 : result = rep_->metaindex_handle.offset();
262 : : }
263 : 110 : } 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 : 0 : result = rep_->metaindex_handle.offset();
268 : : }
269 [ + - ]: 110 : delete index_iter;
270 : 110 : return result;
271 : : }
272 : :
273 : : } // namespace leveldb
|
