]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | |
6 | #ifndef ROCKSDB_LITE | |
f67539c2 | 7 | #include "table/plain/plain_table_key_coding.h" |
7c673cae FG |
8 | |
9 | #include <algorithm> | |
10 | #include <string> | |
11 | #include "db/dbformat.h" | |
f67539c2 TL |
12 | #include "file/writable_file_writer.h" |
13 | #include "table/plain/plain_table_factory.h" | |
14 | #include "table/plain/plain_table_reader.h" | |
7c673cae | 15 | |
f67539c2 | 16 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
17 | |
18 | enum PlainTableEntryType : unsigned char { | |
19 | kFullKey = 0, | |
20 | kPrefixFromPreviousKey = 1, | |
21 | kKeySuffix = 2, | |
22 | }; | |
23 | ||
24 | namespace { | |
25 | ||
26 | // Control byte: | |
27 | // First two bits indicate type of entry | |
28 | // Other bytes are inlined sizes. If all bits are 1 (0x03F), overflow bytes | |
29 | // are used. key_size-0x3F will be encoded as a variint32 after this bytes. | |
30 | ||
31 | const unsigned char kSizeInlineLimit = 0x3F; | |
32 | ||
33 | // Return 0 for error | |
34 | size_t EncodeSize(PlainTableEntryType type, uint32_t key_size, | |
35 | char* out_buffer) { | |
36 | out_buffer[0] = type << 6; | |
37 | ||
38 | if (key_size < static_cast<uint32_t>(kSizeInlineLimit)) { | |
39 | // size inlined | |
40 | out_buffer[0] |= static_cast<char>(key_size); | |
41 | return 1; | |
42 | } else { | |
43 | out_buffer[0] |= kSizeInlineLimit; | |
44 | char* ptr = EncodeVarint32(out_buffer + 1, key_size - kSizeInlineLimit); | |
45 | return ptr - out_buffer; | |
46 | } | |
47 | } | |
48 | } // namespace | |
49 | ||
50 | // Fill bytes_read with number of bytes read. | |
51 | inline Status PlainTableKeyDecoder::DecodeSize(uint32_t start_offset, | |
52 | PlainTableEntryType* entry_type, | |
53 | uint32_t* key_size, | |
54 | uint32_t* bytes_read) { | |
55 | Slice next_byte_slice; | |
56 | bool success = file_reader_.Read(start_offset, 1, &next_byte_slice); | |
57 | if (!success) { | |
58 | return file_reader_.status(); | |
59 | } | |
60 | *entry_type = static_cast<PlainTableEntryType>( | |
61 | (static_cast<unsigned char>(next_byte_slice[0]) & ~kSizeInlineLimit) >> | |
62 | 6); | |
63 | char inline_key_size = next_byte_slice[0] & kSizeInlineLimit; | |
64 | if (inline_key_size < kSizeInlineLimit) { | |
65 | *key_size = inline_key_size; | |
66 | *bytes_read = 1; | |
67 | return Status::OK(); | |
68 | } else { | |
69 | uint32_t extra_size; | |
70 | uint32_t tmp_bytes_read; | |
71 | success = file_reader_.ReadVarint32(start_offset + 1, &extra_size, | |
72 | &tmp_bytes_read); | |
73 | if (!success) { | |
74 | return file_reader_.status(); | |
75 | } | |
76 | assert(tmp_bytes_read > 0); | |
77 | *key_size = kSizeInlineLimit + extra_size; | |
78 | *bytes_read = tmp_bytes_read + 1; | |
79 | return Status::OK(); | |
80 | } | |
81 | } | |
82 | ||
20effc67 TL |
83 | IOStatus PlainTableKeyEncoder::AppendKey(const Slice& key, |
84 | WritableFileWriter* file, | |
85 | uint64_t* offset, char* meta_bytes_buf, | |
86 | size_t* meta_bytes_buf_size) { | |
7c673cae | 87 | ParsedInternalKey parsed_key; |
20effc67 TL |
88 | Status pik_status = |
89 | ParseInternalKey(key, &parsed_key, false /* log_err_key */); // TODO | |
90 | if (!pik_status.ok()) { | |
91 | return IOStatus::Corruption(pik_status.getState()); | |
7c673cae FG |
92 | } |
93 | ||
94 | Slice key_to_write = key; // Portion of internal key to write out. | |
95 | ||
96 | uint32_t user_key_size = static_cast<uint32_t>(key.size() - 8); | |
97 | if (encoding_type_ == kPlain) { | |
98 | if (fixed_user_key_len_ == kPlainTableVariableLength) { | |
99 | // Write key length | |
100 | char key_size_buf[5]; // tmp buffer for key size as varint32 | |
101 | char* ptr = EncodeVarint32(key_size_buf, user_key_size); | |
102 | assert(ptr <= key_size_buf + sizeof(key_size_buf)); | |
103 | auto len = ptr - key_size_buf; | |
20effc67 TL |
104 | IOStatus io_s = file->Append(Slice(key_size_buf, len)); |
105 | if (!io_s.ok()) { | |
106 | return io_s; | |
7c673cae FG |
107 | } |
108 | *offset += len; | |
109 | } | |
110 | } else { | |
111 | assert(encoding_type_ == kPrefix); | |
112 | char size_bytes[12]; | |
113 | size_t size_bytes_pos = 0; | |
114 | ||
115 | Slice prefix = | |
116 | prefix_extractor_->Transform(Slice(key.data(), user_key_size)); | |
117 | if (key_count_for_prefix_ == 0 || prefix != pre_prefix_.GetUserKey() || | |
118 | key_count_for_prefix_ % index_sparseness_ == 0) { | |
119 | key_count_for_prefix_ = 1; | |
120 | pre_prefix_.SetUserKey(prefix); | |
121 | size_bytes_pos += EncodeSize(kFullKey, user_key_size, size_bytes); | |
20effc67 TL |
122 | IOStatus io_s = file->Append(Slice(size_bytes, size_bytes_pos)); |
123 | if (!io_s.ok()) { | |
124 | return io_s; | |
7c673cae FG |
125 | } |
126 | *offset += size_bytes_pos; | |
127 | } else { | |
128 | key_count_for_prefix_++; | |
129 | if (key_count_for_prefix_ == 2) { | |
130 | // For second key within a prefix, need to encode prefix length | |
131 | size_bytes_pos += | |
132 | EncodeSize(kPrefixFromPreviousKey, | |
133 | static_cast<uint32_t>(pre_prefix_.GetUserKey().size()), | |
134 | size_bytes + size_bytes_pos); | |
135 | } | |
136 | uint32_t prefix_len = | |
137 | static_cast<uint32_t>(pre_prefix_.GetUserKey().size()); | |
138 | size_bytes_pos += EncodeSize(kKeySuffix, user_key_size - prefix_len, | |
139 | size_bytes + size_bytes_pos); | |
20effc67 TL |
140 | IOStatus io_s = file->Append(Slice(size_bytes, size_bytes_pos)); |
141 | if (!io_s.ok()) { | |
142 | return io_s; | |
7c673cae FG |
143 | } |
144 | *offset += size_bytes_pos; | |
145 | key_to_write = Slice(key.data() + prefix_len, key.size() - prefix_len); | |
146 | } | |
147 | } | |
148 | ||
149 | // Encode full key | |
150 | // For value size as varint32 (up to 5 bytes). | |
151 | // If the row is of value type with seqId 0, flush the special flag together | |
152 | // in this buffer to safe one file append call, which takes 1 byte. | |
153 | if (parsed_key.sequence == 0 && parsed_key.type == kTypeValue) { | |
20effc67 | 154 | IOStatus io_s = |
7c673cae | 155 | file->Append(Slice(key_to_write.data(), key_to_write.size() - 8)); |
20effc67 TL |
156 | if (!io_s.ok()) { |
157 | return io_s; | |
7c673cae FG |
158 | } |
159 | *offset += key_to_write.size() - 8; | |
160 | meta_bytes_buf[*meta_bytes_buf_size] = PlainTableFactory::kValueTypeSeqId0; | |
161 | *meta_bytes_buf_size += 1; | |
162 | } else { | |
20effc67 TL |
163 | IOStatus io_s = file->Append(key_to_write); |
164 | if (!io_s.ok()) { | |
165 | return io_s; | |
166 | } | |
7c673cae FG |
167 | *offset += key_to_write.size(); |
168 | } | |
169 | ||
20effc67 | 170 | return IOStatus::OK(); |
7c673cae FG |
171 | } |
172 | ||
173 | Slice PlainTableFileReader::GetFromBuffer(Buffer* buffer, uint32_t file_offset, | |
174 | uint32_t len) { | |
175 | assert(file_offset + len <= file_info_->data_end_offset); | |
176 | return Slice(buffer->buf.get() + (file_offset - buffer->buf_start_offset), | |
177 | len); | |
178 | } | |
179 | ||
180 | bool PlainTableFileReader::ReadNonMmap(uint32_t file_offset, uint32_t len, | |
181 | Slice* out) { | |
182 | const uint32_t kPrefetchSize = 256u; | |
183 | ||
184 | // Try to read from buffers. | |
185 | for (uint32_t i = 0; i < num_buf_; i++) { | |
186 | Buffer* buffer = buffers_[num_buf_ - 1 - i].get(); | |
187 | if (file_offset >= buffer->buf_start_offset && | |
188 | file_offset + len <= buffer->buf_start_offset + buffer->buf_len) { | |
189 | *out = GetFromBuffer(buffer, file_offset, len); | |
190 | return true; | |
191 | } | |
192 | } | |
193 | ||
194 | Buffer* new_buffer; | |
195 | // Data needed is not in any of the buffer. Allocate a new buffer. | |
196 | if (num_buf_ < buffers_.size()) { | |
197 | // Add a new buffer | |
198 | new_buffer = new Buffer(); | |
199 | buffers_[num_buf_++].reset(new_buffer); | |
200 | } else { | |
201 | // Now simply replace the last buffer. Can improve the placement policy | |
202 | // if needed. | |
203 | new_buffer = buffers_[num_buf_ - 1].get(); | |
204 | } | |
205 | ||
206 | assert(file_offset + len <= file_info_->data_end_offset); | |
207 | uint32_t size_to_read = std::min(file_info_->data_end_offset - file_offset, | |
208 | std::max(kPrefetchSize, len)); | |
209 | if (size_to_read > new_buffer->buf_capacity) { | |
210 | new_buffer->buf.reset(new char[size_to_read]); | |
211 | new_buffer->buf_capacity = size_to_read; | |
212 | new_buffer->buf_len = 0; | |
213 | } | |
214 | Slice read_result; | |
20effc67 TL |
215 | Status s = |
216 | file_info_->file->Read(IOOptions(), file_offset, size_to_read, | |
217 | &read_result, new_buffer->buf.get(), nullptr); | |
7c673cae FG |
218 | if (!s.ok()) { |
219 | status_ = s; | |
220 | return false; | |
221 | } | |
222 | new_buffer->buf_start_offset = file_offset; | |
223 | new_buffer->buf_len = size_to_read; | |
224 | *out = GetFromBuffer(new_buffer, file_offset, len); | |
225 | return true; | |
226 | } | |
227 | ||
228 | inline bool PlainTableFileReader::ReadVarint32(uint32_t offset, uint32_t* out, | |
229 | uint32_t* bytes_read) { | |
230 | if (file_info_->is_mmap_mode) { | |
231 | const char* start = file_info_->file_data.data() + offset; | |
232 | const char* limit = | |
233 | file_info_->file_data.data() + file_info_->data_end_offset; | |
234 | const char* key_ptr = GetVarint32Ptr(start, limit, out); | |
235 | assert(key_ptr != nullptr); | |
236 | *bytes_read = static_cast<uint32_t>(key_ptr - start); | |
237 | return true; | |
238 | } else { | |
239 | return ReadVarint32NonMmap(offset, out, bytes_read); | |
240 | } | |
241 | } | |
242 | ||
243 | bool PlainTableFileReader::ReadVarint32NonMmap(uint32_t offset, uint32_t* out, | |
244 | uint32_t* bytes_read) { | |
245 | const char* start; | |
246 | const char* limit; | |
247 | const uint32_t kMaxVarInt32Size = 6u; | |
248 | uint32_t bytes_to_read = | |
249 | std::min(file_info_->data_end_offset - offset, kMaxVarInt32Size); | |
250 | Slice bytes; | |
251 | if (!Read(offset, bytes_to_read, &bytes)) { | |
252 | return false; | |
253 | } | |
254 | start = bytes.data(); | |
255 | limit = bytes.data() + bytes.size(); | |
256 | ||
257 | const char* key_ptr = GetVarint32Ptr(start, limit, out); | |
258 | *bytes_read = | |
259 | (key_ptr != nullptr) ? static_cast<uint32_t>(key_ptr - start) : 0; | |
260 | return true; | |
261 | } | |
262 | ||
263 | Status PlainTableKeyDecoder::ReadInternalKey( | |
264 | uint32_t file_offset, uint32_t user_key_size, ParsedInternalKey* parsed_key, | |
265 | uint32_t* bytes_read, bool* internal_key_valid, Slice* internal_key) { | |
266 | Slice tmp_slice; | |
267 | bool success = file_reader_.Read(file_offset, user_key_size + 1, &tmp_slice); | |
268 | if (!success) { | |
269 | return file_reader_.status(); | |
270 | } | |
271 | if (tmp_slice[user_key_size] == PlainTableFactory::kValueTypeSeqId0) { | |
272 | // Special encoding for the row with seqID=0 | |
273 | parsed_key->user_key = Slice(tmp_slice.data(), user_key_size); | |
274 | parsed_key->sequence = 0; | |
275 | parsed_key->type = kTypeValue; | |
276 | *bytes_read += user_key_size + 1; | |
277 | *internal_key_valid = false; | |
278 | } else { | |
279 | success = file_reader_.Read(file_offset, user_key_size + 8, internal_key); | |
280 | if (!success) { | |
281 | return file_reader_.status(); | |
282 | } | |
283 | *internal_key_valid = true; | |
20effc67 TL |
284 | Status pik_status = ParseInternalKey(*internal_key, parsed_key, |
285 | false /* log_err_key */); // TODO | |
286 | if (!pik_status.ok()) { | |
7c673cae | 287 | return Status::Corruption( |
20effc67 TL |
288 | Slice("Corrupted key found during next key read. "), |
289 | pik_status.getState()); | |
7c673cae FG |
290 | } |
291 | *bytes_read += user_key_size + 8; | |
292 | } | |
293 | return Status::OK(); | |
294 | } | |
295 | ||
296 | Status PlainTableKeyDecoder::NextPlainEncodingKey(uint32_t start_offset, | |
297 | ParsedInternalKey* parsed_key, | |
298 | Slice* internal_key, | |
299 | uint32_t* bytes_read, | |
11fdf7f2 | 300 | bool* /*seekable*/) { |
7c673cae FG |
301 | uint32_t user_key_size = 0; |
302 | Status s; | |
303 | if (fixed_user_key_len_ != kPlainTableVariableLength) { | |
304 | user_key_size = fixed_user_key_len_; | |
305 | } else { | |
306 | uint32_t tmp_size = 0; | |
307 | uint32_t tmp_read; | |
308 | bool success = | |
309 | file_reader_.ReadVarint32(start_offset, &tmp_size, &tmp_read); | |
310 | if (!success) { | |
311 | return file_reader_.status(); | |
312 | } | |
313 | assert(tmp_read > 0); | |
314 | user_key_size = tmp_size; | |
315 | *bytes_read = tmp_read; | |
316 | } | |
317 | // dummy initial value to avoid compiler complain | |
318 | bool decoded_internal_key_valid = true; | |
319 | Slice decoded_internal_key; | |
320 | s = ReadInternalKey(start_offset + *bytes_read, user_key_size, parsed_key, | |
321 | bytes_read, &decoded_internal_key_valid, | |
322 | &decoded_internal_key); | |
323 | if (!s.ok()) { | |
324 | return s; | |
325 | } | |
326 | if (!file_reader_.file_info()->is_mmap_mode) { | |
327 | cur_key_.SetInternalKey(*parsed_key); | |
328 | parsed_key->user_key = | |
329 | Slice(cur_key_.GetInternalKey().data(), user_key_size); | |
330 | if (internal_key != nullptr) { | |
331 | *internal_key = cur_key_.GetInternalKey(); | |
332 | } | |
333 | } else if (internal_key != nullptr) { | |
334 | if (decoded_internal_key_valid) { | |
335 | *internal_key = decoded_internal_key; | |
336 | } else { | |
337 | // Need to copy out the internal key | |
338 | cur_key_.SetInternalKey(*parsed_key); | |
339 | *internal_key = cur_key_.GetInternalKey(); | |
340 | } | |
341 | } | |
342 | return Status::OK(); | |
343 | } | |
344 | ||
345 | Status PlainTableKeyDecoder::NextPrefixEncodingKey( | |
346 | uint32_t start_offset, ParsedInternalKey* parsed_key, Slice* internal_key, | |
347 | uint32_t* bytes_read, bool* seekable) { | |
348 | PlainTableEntryType entry_type; | |
349 | ||
350 | bool expect_suffix = false; | |
351 | Status s; | |
352 | do { | |
353 | uint32_t size = 0; | |
354 | // dummy initial value to avoid compiler complain | |
355 | bool decoded_internal_key_valid = true; | |
356 | uint32_t my_bytes_read = 0; | |
357 | s = DecodeSize(start_offset + *bytes_read, &entry_type, &size, | |
358 | &my_bytes_read); | |
359 | if (!s.ok()) { | |
360 | return s; | |
361 | } | |
362 | if (my_bytes_read == 0) { | |
363 | return Status::Corruption("Unexpected EOF when reading size of the key"); | |
364 | } | |
365 | *bytes_read += my_bytes_read; | |
366 | ||
367 | switch (entry_type) { | |
368 | case kFullKey: { | |
369 | expect_suffix = false; | |
370 | Slice decoded_internal_key; | |
371 | s = ReadInternalKey(start_offset + *bytes_read, size, parsed_key, | |
372 | bytes_read, &decoded_internal_key_valid, | |
373 | &decoded_internal_key); | |
374 | if (!s.ok()) { | |
375 | return s; | |
376 | } | |
377 | if (!file_reader_.file_info()->is_mmap_mode || | |
378 | (internal_key != nullptr && !decoded_internal_key_valid)) { | |
379 | // In non-mmap mode, always need to make a copy of keys returned to | |
380 | // users, because after reading value for the key, the key might | |
381 | // be invalid. | |
382 | cur_key_.SetInternalKey(*parsed_key); | |
383 | saved_user_key_ = cur_key_.GetUserKey(); | |
384 | if (!file_reader_.file_info()->is_mmap_mode) { | |
385 | parsed_key->user_key = | |
386 | Slice(cur_key_.GetInternalKey().data(), size); | |
387 | } | |
388 | if (internal_key != nullptr) { | |
389 | *internal_key = cur_key_.GetInternalKey(); | |
390 | } | |
391 | } else { | |
392 | if (internal_key != nullptr) { | |
393 | *internal_key = decoded_internal_key; | |
394 | } | |
395 | saved_user_key_ = parsed_key->user_key; | |
396 | } | |
397 | break; | |
398 | } | |
399 | case kPrefixFromPreviousKey: { | |
400 | if (seekable != nullptr) { | |
401 | *seekable = false; | |
402 | } | |
403 | prefix_len_ = size; | |
404 | assert(prefix_extractor_ == nullptr || | |
405 | prefix_extractor_->Transform(saved_user_key_).size() == | |
406 | prefix_len_); | |
407 | // Need read another size flag for suffix | |
408 | expect_suffix = true; | |
409 | break; | |
410 | } | |
411 | case kKeySuffix: { | |
412 | expect_suffix = false; | |
413 | if (seekable != nullptr) { | |
414 | *seekable = false; | |
415 | } | |
416 | ||
417 | Slice tmp_slice; | |
418 | s = ReadInternalKey(start_offset + *bytes_read, size, parsed_key, | |
419 | bytes_read, &decoded_internal_key_valid, | |
420 | &tmp_slice); | |
421 | if (!s.ok()) { | |
422 | return s; | |
423 | } | |
424 | if (!file_reader_.file_info()->is_mmap_mode) { | |
425 | // In non-mmap mode, we need to make a copy of keys returned to | |
426 | // users, because after reading value for the key, the key might | |
427 | // be invalid. | |
428 | // saved_user_key_ points to cur_key_. We are making a copy of | |
429 | // the prefix part to another string, and construct the current | |
430 | // key from the prefix part and the suffix part back to cur_key_. | |
431 | std::string tmp = | |
432 | Slice(saved_user_key_.data(), prefix_len_).ToString(); | |
433 | cur_key_.Reserve(prefix_len_ + size); | |
434 | cur_key_.SetInternalKey(tmp, *parsed_key); | |
435 | parsed_key->user_key = | |
436 | Slice(cur_key_.GetInternalKey().data(), prefix_len_ + size); | |
437 | saved_user_key_ = cur_key_.GetUserKey(); | |
438 | } else { | |
439 | cur_key_.Reserve(prefix_len_ + size); | |
440 | cur_key_.SetInternalKey(Slice(saved_user_key_.data(), prefix_len_), | |
441 | *parsed_key); | |
442 | } | |
443 | parsed_key->user_key = cur_key_.GetUserKey(); | |
444 | if (internal_key != nullptr) { | |
445 | *internal_key = cur_key_.GetInternalKey(); | |
446 | } | |
447 | break; | |
448 | } | |
449 | default: | |
450 | return Status::Corruption("Un-identified size flag."); | |
451 | } | |
452 | } while (expect_suffix); // Another round if suffix is expected. | |
453 | return Status::OK(); | |
454 | } | |
455 | ||
456 | Status PlainTableKeyDecoder::NextKey(uint32_t start_offset, | |
457 | ParsedInternalKey* parsed_key, | |
458 | Slice* internal_key, Slice* value, | |
459 | uint32_t* bytes_read, bool* seekable) { | |
460 | assert(value != nullptr); | |
461 | Status s = NextKeyNoValue(start_offset, parsed_key, internal_key, bytes_read, | |
462 | seekable); | |
463 | if (s.ok()) { | |
464 | assert(bytes_read != nullptr); | |
465 | uint32_t value_size; | |
466 | uint32_t value_size_bytes; | |
467 | bool success = file_reader_.ReadVarint32(start_offset + *bytes_read, | |
468 | &value_size, &value_size_bytes); | |
469 | if (!success) { | |
470 | return file_reader_.status(); | |
471 | } | |
472 | if (value_size_bytes == 0) { | |
473 | return Status::Corruption( | |
474 | "Unexpected EOF when reading the next value's size."); | |
475 | } | |
476 | *bytes_read += value_size_bytes; | |
477 | success = file_reader_.Read(start_offset + *bytes_read, value_size, value); | |
478 | if (!success) { | |
479 | return file_reader_.status(); | |
480 | } | |
481 | *bytes_read += value_size; | |
482 | } | |
483 | return s; | |
484 | } | |
485 | ||
486 | Status PlainTableKeyDecoder::NextKeyNoValue(uint32_t start_offset, | |
487 | ParsedInternalKey* parsed_key, | |
488 | Slice* internal_key, | |
489 | uint32_t* bytes_read, | |
490 | bool* seekable) { | |
491 | *bytes_read = 0; | |
492 | if (seekable != nullptr) { | |
493 | *seekable = true; | |
494 | } | |
7c673cae FG |
495 | if (encoding_type_ == kPlain) { |
496 | return NextPlainEncodingKey(start_offset, parsed_key, internal_key, | |
497 | bytes_read, seekable); | |
498 | } else { | |
499 | assert(encoding_type_ == kPrefix); | |
500 | return NextPrefixEncodingKey(start_offset, parsed_key, internal_key, | |
501 | bytes_read, seekable); | |
502 | } | |
503 | } | |
504 | ||
f67539c2 | 505 | } // namespace ROCKSDB_NAMESPACE |
7c673cae | 506 | #endif // ROCKSDB_LIT |