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