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.
5 #include "db/log_reader.h"
6 #include "db/log_writer.h"
7 #include "leveldb/env.h"
8 #include "util/coding.h"
9 #include "util/crc32c.h"
10 #include "util/random.h"
11 #include "util/testharness.h"
16 // Construct a string of the specified length made out of the supplied
18 static std::string BigString(const std::string& partial_string, size_t n) {
20 while (result.size() < n) {
21 result.append(partial_string);
27 // Construct a string from a number
28 static std::string NumberString(int n) {
30 snprintf(buf, sizeof(buf), "%d.", n);
31 return std::string(buf);
34 // Return a skewed potentially long string
35 static std::string RandomSkewedString(int i, Random* rnd) {
36 return BigString(NumberString(i), rnd->Skewed(17));
41 class StringDest : public WritableFile {
43 std::string contents_;
45 virtual Status Close() { return Status::OK(); }
46 virtual Status Flush() { return Status::OK(); }
47 virtual Status Sync() { return Status::OK(); }
48 virtual Status Append(const Slice& slice) {
49 contents_.append(slice.data(), slice.size());
54 class StringSource : public SequentialFile {
58 bool returned_partial_;
59 StringSource() : force_error_(false), returned_partial_(false) { }
61 virtual Status Read(size_t n, Slice* result, char* scratch) {
62 ASSERT_TRUE(!returned_partial_) << "must not Read() after eof/error";
66 returned_partial_ = true;
67 return Status::Corruption("read error");
70 if (contents_.size() < n) {
72 returned_partial_ = true;
74 *result = Slice(contents_.data(), n);
75 contents_.remove_prefix(n);
79 virtual Status Skip(uint64_t n) {
80 if (n > contents_.size()) {
82 return Status::NotFound("in-memory file skipepd past end");
85 contents_.remove_prefix(n);
91 class ReportCollector : public Reader::Reporter {
93 size_t dropped_bytes_;
96 ReportCollector() : dropped_bytes_(0) { }
97 virtual void Corruption(size_t bytes, const Status& status) {
98 dropped_bytes_ += bytes;
99 message_.append(status.ToString());
104 StringSource source_;
105 ReportCollector report_;
110 // Record metadata for testing initial offset functionality
111 static size_t initial_offset_record_sizes_[];
112 static uint64_t initial_offset_last_record_offsets_[];
115 LogTest() : reading_(false),
117 reader_(&source_, &report_, true/*checksum*/,
118 0/*initial_offset*/) {
121 void Write(const std::string& msg) {
122 ASSERT_TRUE(!reading_) << "Write() after starting to read";
123 writer_.AddRecord(Slice(msg));
126 size_t WrittenBytes() const {
127 return dest_.contents_.size();
133 source_.contents_ = Slice(dest_.contents_);
137 if (reader_.ReadRecord(&record, &scratch)) {
138 return record.ToString();
144 void IncrementByte(int offset, int delta) {
145 dest_.contents_[offset] += delta;
148 void SetByte(int offset, char new_byte) {
149 dest_.contents_[offset] = new_byte;
152 void ShrinkSize(int bytes) {
153 dest_.contents_.resize(dest_.contents_.size() - bytes);
156 void FixChecksum(int header_offset, int len) {
157 // Compute crc of type/len/data
158 uint32_t crc = crc32c::Value(&dest_.contents_[header_offset+6], 1 + len);
159 crc = crc32c::Mask(crc);
160 EncodeFixed32(&dest_.contents_[header_offset], crc);
164 source_.force_error_ = true;
167 size_t DroppedBytes() const {
168 return report_.dropped_bytes_;
171 std::string ReportMessage() const {
172 return report_.message_;
175 // Returns OK iff recorded error message contains "msg"
176 std::string MatchError(const std::string& msg) const {
177 if (report_.message_.find(msg) == std::string::npos) {
178 return report_.message_;
184 void WriteInitialOffsetLog() {
185 for (int i = 0; i < 4; i++) {
186 std::string record(initial_offset_record_sizes_[i],
187 static_cast<char>('a' + i));
192 void CheckOffsetPastEndReturnsNoRecords(uint64_t offset_past_end) {
193 WriteInitialOffsetLog();
195 source_.contents_ = Slice(dest_.contents_);
196 Reader* offset_reader = new Reader(&source_, &report_, true/*checksum*/,
197 WrittenBytes() + offset_past_end);
200 ASSERT_TRUE(!offset_reader->ReadRecord(&record, &scratch));
201 delete offset_reader;
204 void CheckInitialOffsetRecord(uint64_t initial_offset,
205 int expected_record_offset) {
206 WriteInitialOffsetLog();
208 source_.contents_ = Slice(dest_.contents_);
209 Reader* offset_reader = new Reader(&source_, &report_, true/*checksum*/,
213 ASSERT_TRUE(offset_reader->ReadRecord(&record, &scratch));
214 ASSERT_EQ(initial_offset_record_sizes_[expected_record_offset],
216 ASSERT_EQ(initial_offset_last_record_offsets_[expected_record_offset],
217 offset_reader->LastRecordOffset());
218 ASSERT_EQ((char)('a' + expected_record_offset), record.data()[0]);
219 delete offset_reader;
224 size_t LogTest::initial_offset_record_sizes_[] =
225 {10000, // Two sizable records in first block
227 2 * log::kBlockSize - 1000, // Span three blocks
230 uint64_t LogTest::initial_offset_last_record_offsets_[] =
233 2 * (kHeaderSize + 10000),
234 2 * (kHeaderSize + 10000) +
235 (2 * log::kBlockSize - 1000) + 3 * kHeaderSize};
238 TEST(LogTest, Empty) {
239 ASSERT_EQ("EOF", Read());
242 TEST(LogTest, ReadWrite) {
247 ASSERT_EQ("foo", Read());
248 ASSERT_EQ("bar", Read());
249 ASSERT_EQ("", Read());
250 ASSERT_EQ("xxxx", Read());
251 ASSERT_EQ("EOF", Read());
252 ASSERT_EQ("EOF", Read()); // Make sure reads at eof work
255 TEST(LogTest, ManyBlocks) {
256 for (int i = 0; i < 100000; i++) {
257 Write(NumberString(i));
259 for (int i = 0; i < 100000; i++) {
260 ASSERT_EQ(NumberString(i), Read());
262 ASSERT_EQ("EOF", Read());
265 TEST(LogTest, Fragmentation) {
267 Write(BigString("medium", 50000));
268 Write(BigString("large", 100000));
269 ASSERT_EQ("small", Read());
270 ASSERT_EQ(BigString("medium", 50000), Read());
271 ASSERT_EQ(BigString("large", 100000), Read());
272 ASSERT_EQ("EOF", Read());
275 TEST(LogTest, MarginalTrailer) {
276 // Make a trailer that is exactly the same length as an empty record.
277 const int n = kBlockSize - 2*kHeaderSize;
278 Write(BigString("foo", n));
279 ASSERT_EQ(kBlockSize - kHeaderSize, WrittenBytes());
282 ASSERT_EQ(BigString("foo", n), Read());
283 ASSERT_EQ("", Read());
284 ASSERT_EQ("bar", Read());
285 ASSERT_EQ("EOF", Read());
288 TEST(LogTest, MarginalTrailer2) {
289 // Make a trailer that is exactly the same length as an empty record.
290 const int n = kBlockSize - 2*kHeaderSize;
291 Write(BigString("foo", n));
292 ASSERT_EQ(kBlockSize - kHeaderSize, WrittenBytes());
294 ASSERT_EQ(BigString("foo", n), Read());
295 ASSERT_EQ("bar", Read());
296 ASSERT_EQ("EOF", Read());
297 ASSERT_EQ(0, DroppedBytes());
298 ASSERT_EQ("", ReportMessage());
301 TEST(LogTest, ShortTrailer) {
302 const int n = kBlockSize - 2*kHeaderSize + 4;
303 Write(BigString("foo", n));
304 ASSERT_EQ(kBlockSize - kHeaderSize + 4, WrittenBytes());
307 ASSERT_EQ(BigString("foo", n), Read());
308 ASSERT_EQ("", Read());
309 ASSERT_EQ("bar", Read());
310 ASSERT_EQ("EOF", Read());
313 TEST(LogTest, AlignedEof) {
314 const int n = kBlockSize - 2*kHeaderSize + 4;
315 Write(BigString("foo", n));
316 ASSERT_EQ(kBlockSize - kHeaderSize + 4, WrittenBytes());
317 ASSERT_EQ(BigString("foo", n), Read());
318 ASSERT_EQ("EOF", Read());
321 TEST(LogTest, RandomRead) {
323 Random write_rnd(301);
324 for (int i = 0; i < N; i++) {
325 Write(RandomSkewedString(i, &write_rnd));
327 Random read_rnd(301);
328 for (int i = 0; i < N; i++) {
329 ASSERT_EQ(RandomSkewedString(i, &read_rnd), Read());
331 ASSERT_EQ("EOF", Read());
334 // Tests of all the error paths in log_reader.cc follow:
336 TEST(LogTest, ReadError) {
339 ASSERT_EQ("EOF", Read());
340 ASSERT_EQ(kBlockSize, DroppedBytes());
341 ASSERT_EQ("OK", MatchError("read error"));
344 TEST(LogTest, BadRecordType) {
346 // Type is stored in header[6]
347 IncrementByte(6, 100);
349 ASSERT_EQ("EOF", Read());
350 ASSERT_EQ(3, DroppedBytes());
351 ASSERT_EQ("OK", MatchError("unknown record type"));
354 TEST(LogTest, TruncatedTrailingRecordIsIgnored) {
356 ShrinkSize(4); // Drop all payload as well as a header byte
357 ASSERT_EQ("EOF", Read());
358 // Truncated last record is ignored, not treated as an error.
359 ASSERT_EQ(0, DroppedBytes());
360 ASSERT_EQ("", ReportMessage());
363 TEST(LogTest, BadLength) {
364 const int kPayloadSize = kBlockSize - kHeaderSize;
365 Write(BigString("bar", kPayloadSize));
367 // Least significant size byte is stored in header[4].
369 ASSERT_EQ("foo", Read());
370 ASSERT_EQ(kBlockSize, DroppedBytes());
371 ASSERT_EQ("OK", MatchError("bad record length"));
374 TEST(LogTest, BadLengthAtEndIsIgnored) {
377 ASSERT_EQ("EOF", Read());
378 ASSERT_EQ(0, DroppedBytes());
379 ASSERT_EQ("", ReportMessage());
382 TEST(LogTest, ChecksumMismatch) {
384 IncrementByte(0, 10);
385 ASSERT_EQ("EOF", Read());
386 ASSERT_EQ(10, DroppedBytes());
387 ASSERT_EQ("OK", MatchError("checksum mismatch"));
390 TEST(LogTest, UnexpectedMiddleType) {
392 SetByte(6, kMiddleType);
394 ASSERT_EQ("EOF", Read());
395 ASSERT_EQ(3, DroppedBytes());
396 ASSERT_EQ("OK", MatchError("missing start"));
399 TEST(LogTest, UnexpectedLastType) {
401 SetByte(6, kLastType);
403 ASSERT_EQ("EOF", Read());
404 ASSERT_EQ(3, DroppedBytes());
405 ASSERT_EQ("OK", MatchError("missing start"));
408 TEST(LogTest, UnexpectedFullType) {
411 SetByte(6, kFirstType);
413 ASSERT_EQ("bar", Read());
414 ASSERT_EQ("EOF", Read());
415 ASSERT_EQ(3, DroppedBytes());
416 ASSERT_EQ("OK", MatchError("partial record without end"));
419 TEST(LogTest, UnexpectedFirstType) {
421 Write(BigString("bar", 100000));
422 SetByte(6, kFirstType);
424 ASSERT_EQ(BigString("bar", 100000), Read());
425 ASSERT_EQ("EOF", Read());
426 ASSERT_EQ(3, DroppedBytes());
427 ASSERT_EQ("OK", MatchError("partial record without end"));
430 TEST(LogTest, MissingLastIsIgnored) {
431 Write(BigString("bar", kBlockSize));
432 // Remove the LAST block, including header.
434 ASSERT_EQ("EOF", Read());
435 ASSERT_EQ("", ReportMessage());
436 ASSERT_EQ(0, DroppedBytes());
439 TEST(LogTest, PartialLastIsIgnored) {
440 Write(BigString("bar", kBlockSize));
441 // Cause a bad record length in the LAST block.
443 ASSERT_EQ("EOF", Read());
444 ASSERT_EQ("", ReportMessage());
445 ASSERT_EQ(0, DroppedBytes());
448 TEST(LogTest, ErrorJoinsRecords) {
449 // Consider two fragmented records:
450 // first(R1) last(R1) first(R2) last(R2)
451 // where the middle two fragments disappear. We do not want
452 // first(R1),last(R2) to get joined and returned as a valid record.
454 // Write records that span two blocks
455 Write(BigString("foo", kBlockSize));
456 Write(BigString("bar", kBlockSize));
459 // Wipe the middle block
460 for (int offset = kBlockSize; offset < 2*kBlockSize; offset++) {
461 SetByte(offset, 'x');
464 ASSERT_EQ("correct", Read());
465 ASSERT_EQ("EOF", Read());
466 const size_t dropped = DroppedBytes();
467 ASSERT_LE(dropped, 2*kBlockSize + 100);
468 ASSERT_GE(dropped, 2*kBlockSize);
471 TEST(LogTest, ReadStart) {
472 CheckInitialOffsetRecord(0, 0);
475 TEST(LogTest, ReadSecondOneOff) {
476 CheckInitialOffsetRecord(1, 1);
479 TEST(LogTest, ReadSecondTenThousand) {
480 CheckInitialOffsetRecord(10000, 1);
483 TEST(LogTest, ReadSecondStart) {
484 CheckInitialOffsetRecord(10007, 1);
487 TEST(LogTest, ReadThirdOneOff) {
488 CheckInitialOffsetRecord(10008, 2);
491 TEST(LogTest, ReadThirdStart) {
492 CheckInitialOffsetRecord(20014, 2);
495 TEST(LogTest, ReadFourthOneOff) {
496 CheckInitialOffsetRecord(20015, 3);
499 TEST(LogTest, ReadFourthFirstBlockTrailer) {
500 CheckInitialOffsetRecord(log::kBlockSize - 4, 3);
503 TEST(LogTest, ReadFourthMiddleBlock) {
504 CheckInitialOffsetRecord(log::kBlockSize + 1, 3);
507 TEST(LogTest, ReadFourthLastBlock) {
508 CheckInitialOffsetRecord(2 * log::kBlockSize + 1, 3);
511 TEST(LogTest, ReadFourthStart) {
512 CheckInitialOffsetRecord(
513 2 * (kHeaderSize + 1000) + (2 * log::kBlockSize - 1000) + 3 * kHeaderSize,
517 TEST(LogTest, ReadEnd) {
518 CheckOffsetPastEndReturnsNoRecords(0);
521 TEST(LogTest, ReadPastEnd) {
522 CheckOffsetPastEndReturnsNoRecords(5);
526 } // namespace leveldb
528 int main(int argc, char** argv) {
529 return leveldb::test::RunAllTests();