ceph/src/rocksdb/db/dbformat_test.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   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).
   5 //
   6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   7 // Use of this source code is governed by a BSD-style license that can be
   8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   9
  10 #include "db/dbformat.h"
  11
  12 #include "table/block_based/index_builder.h"
  13 #include "test_util/testharness.h"
  14 #include "test_util/testutil.h"
  15
  16 namespace ROCKSDB_NAMESPACE {
  17
  18 static std::string IKey(const std::string& user_key, uint64_t seq,
  19                         ValueType vt) {
  20   std::string encoded;
  21   AppendInternalKey(&encoded, ParsedInternalKey(user_key, seq, vt));
  22   return encoded;
  23 }
  24
  25 static std::string Shorten(const std::string& s, const std::string& l) {
  26   std::string result = s;
  27   ShortenedIndexBuilder::FindShortestInternalKeySeparator(*BytewiseComparator(),
  28                                                           &result, l);
  29   return result;
  30 }
  31
  32 static std::string ShortSuccessor(const std::string& s) {
  33   std::string result = s;
  34   ShortenedIndexBuilder::FindShortInternalKeySuccessor(*BytewiseComparator(),
  35                                                        &result);
  36   return result;
  37 }
  38
  39 static void TestKey(const std::string& key, uint64_t seq, ValueType vt) {
  40   std::string encoded = IKey(key, seq, vt);
  41
  42   Slice in(encoded);
  43   ParsedInternalKey decoded("", 0, kTypeValue);
  44
  45   ASSERT_OK(ParseInternalKey(in, &decoded, true /* log_err_key */));
  46   ASSERT_EQ(key, decoded.user_key.ToString());
  47   ASSERT_EQ(seq, decoded.sequence);
  48   ASSERT_EQ(vt, decoded.type);
  49
  50   ASSERT_NOK(ParseInternalKey(Slice("bar"), &decoded, true /* log_err_key */));
  51 }
  52
  53 class FormatTest : public testing::Test {};
  54
  55 TEST_F(FormatTest, InternalKey_EncodeDecode) {
  56   const char* keys[] = {"", "k", "hello", "longggggggggggggggggggggg"};
  57   const uint64_t seq[] = {1,
  58                           2,
  59                           3,
  60                           (1ull << 8) - 1,
  61                           1ull << 8,
  62                           (1ull << 8) + 1,
  63                           (1ull << 16) - 1,
  64                           1ull << 16,
  65                           (1ull << 16) + 1,
  66                           (1ull << 32) - 1,
  67                           1ull << 32,
  68                           (1ull << 32) + 1};
  69   for (unsigned int k = 0; k < sizeof(keys) / sizeof(keys[0]); k++) {
  70     for (unsigned int s = 0; s < sizeof(seq) / sizeof(seq[0]); s++) {
  71       TestKey(keys[k], seq[s], kTypeValue);
  72       TestKey("hello", 1, kTypeDeletion);
  73     }
  74   }
  75 }
  76
  77 TEST_F(FormatTest, InternalKeyShortSeparator) {
  78   // When user keys are same
  79   ASSERT_EQ(IKey("foo", 100, kTypeValue),
  80             Shorten(IKey("foo", 100, kTypeValue), IKey("foo", 99, kTypeValue)));
  81   ASSERT_EQ(
  82       IKey("foo", 100, kTypeValue),
  83       Shorten(IKey("foo", 100, kTypeValue), IKey("foo", 101, kTypeValue)));
  84   ASSERT_EQ(
  85       IKey("foo", 100, kTypeValue),
  86       Shorten(IKey("foo", 100, kTypeValue), IKey("foo", 100, kTypeValue)));
  87   ASSERT_EQ(
  88       IKey("foo", 100, kTypeValue),
  89       Shorten(IKey("foo", 100, kTypeValue), IKey("foo", 100, kTypeDeletion)));
  90
  91   // When user keys are misordered
  92   ASSERT_EQ(IKey("foo", 100, kTypeValue),
  93             Shorten(IKey("foo", 100, kTypeValue), IKey("bar", 99, kTypeValue)));
  94
  95   // When user keys are different, but correctly ordered
  96   ASSERT_EQ(
  97       IKey("g", kMaxSequenceNumber, kValueTypeForSeek),
  98       Shorten(IKey("foo", 100, kTypeValue), IKey("hello", 200, kTypeValue)));
  99
 100   ASSERT_EQ(IKey("ABC2", kMaxSequenceNumber, kValueTypeForSeek),
 101             Shorten(IKey("ABC1AAAAA", 100, kTypeValue),
 102                     IKey("ABC2ABB", 200, kTypeValue)));
 103
 104   ASSERT_EQ(IKey("AAA2", kMaxSequenceNumber, kValueTypeForSeek),
 105             Shorten(IKey("AAA1AAA", 100, kTypeValue),
 106                     IKey("AAA2AA", 200, kTypeValue)));
 107
 108   ASSERT_EQ(
 109       IKey("AAA2", kMaxSequenceNumber, kValueTypeForSeek),
 110       Shorten(IKey("AAA1AAA", 100, kTypeValue), IKey("AAA4", 200, kTypeValue)));
 111
 112   ASSERT_EQ(
 113       IKey("AAA1B", kMaxSequenceNumber, kValueTypeForSeek),
 114       Shorten(IKey("AAA1AAA", 100, kTypeValue), IKey("AAA2", 200, kTypeValue)));
 115
 116   ASSERT_EQ(IKey("AAA2", kMaxSequenceNumber, kValueTypeForSeek),
 117             Shorten(IKey("AAA1AAA", 100, kTypeValue),
 118                     IKey("AAA2A", 200, kTypeValue)));
 119
 120   ASSERT_EQ(
 121       IKey("AAA1", 100, kTypeValue),
 122       Shorten(IKey("AAA1", 100, kTypeValue), IKey("AAA2", 200, kTypeValue)));
 123
 124   // When start user key is prefix of limit user key
 125   ASSERT_EQ(
 126       IKey("foo", 100, kTypeValue),
 127       Shorten(IKey("foo", 100, kTypeValue), IKey("foobar", 200, kTypeValue)));
 128
 129   // When limit user key is prefix of start user key
 130   ASSERT_EQ(
 131       IKey("foobar", 100, kTypeValue),
 132       Shorten(IKey("foobar", 100, kTypeValue), IKey("foo", 200, kTypeValue)));
 133 }
 134
 135 TEST_F(FormatTest, InternalKeyShortestSuccessor) {
 136   ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek),
 137             ShortSuccessor(IKey("foo", 100, kTypeValue)));
 138   ASSERT_EQ(IKey("\xff\xff", 100, kTypeValue),
 139             ShortSuccessor(IKey("\xff\xff", 100, kTypeValue)));
 140 }
 141
 142 TEST_F(FormatTest, IterKeyOperation) {
 143   IterKey k;
 144   const char p[] = "abcdefghijklmnopqrstuvwxyz";
 145   const char q[] = "0123456789";
 146
 147   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
 148             std::string(""));
 149
 150   k.TrimAppend(0, p, 3);
 151   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
 152             std::string("abc"));
 153
 154   k.TrimAppend(1, p, 3);
 155   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
 156             std::string("aabc"));
 157
 158   k.TrimAppend(0, p, 26);
 159   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
 160             std::string("abcdefghijklmnopqrstuvwxyz"));
 161
 162   k.TrimAppend(26, q, 10);
 163   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
 164             std::string("abcdefghijklmnopqrstuvwxyz0123456789"));
 165
 166   k.TrimAppend(36, q, 1);
 167   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
 168             std::string("abcdefghijklmnopqrstuvwxyz01234567890"));
 169
 170   k.TrimAppend(26, q, 1);
 171   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
 172             std::string("abcdefghijklmnopqrstuvwxyz0"));
 173
 174   // Size going up, memory allocation is triggered
 175   k.TrimAppend(27, p, 26);
 176   ASSERT_EQ(std::string(k.GetUserKey().data(), k.GetUserKey().size()),
 177             std::string("abcdefghijklmnopqrstuvwxyz0"
 178                         "abcdefghijklmnopqrstuvwxyz"));
 179 }
 180
 181 TEST_F(FormatTest, UpdateInternalKey) {
 182   std::string user_key("abcdefghijklmnopqrstuvwxyz");
 183   uint64_t new_seq = 0x123456;
 184   ValueType new_val_type = kTypeDeletion;
 185
 186   std::string ikey;
 187   AppendInternalKey(&ikey, ParsedInternalKey(user_key, 100U, kTypeValue));
 188   size_t ikey_size = ikey.size();
 189   UpdateInternalKey(&ikey, new_seq, new_val_type);
 190   ASSERT_EQ(ikey_size, ikey.size());
 191
 192   Slice in(ikey);
 193   ParsedInternalKey decoded;
 194   ASSERT_OK(ParseInternalKey(in, &decoded, true /* log_err_key */));
 195   ASSERT_EQ(user_key, decoded.user_key.ToString());
 196   ASSERT_EQ(new_seq, decoded.sequence);
 197   ASSERT_EQ(new_val_type, decoded.type);
 198 }
 199
 200 TEST_F(FormatTest, RangeTombstoneSerializeEndKey) {
 201   RangeTombstone t("a", "b", 2);
 202   InternalKey k("b", 3, kTypeValue);
 203   const InternalKeyComparator cmp(BytewiseComparator());
 204   ASSERT_LT(cmp.Compare(t.SerializeEndKey(), k), 0);
 205 }
 206
 207 }  // namespace ROCKSDB_NAMESPACE
 208
 209 int main(int argc, char** argv) {
 210   ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
 211   ::testing::InitGoogleTest(&argc, argv);
 212   RegisterCustomObjects(argc, argv);
 213   return RUN_ALL_TESTS();
 214 }