ceph/src/test/common/test_cdc.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #include <vector>
   5 #include <cstring>
   6 #include <random>
   7
   8 #include "include/types.h"
   9 #include "include/buffer.h"
  10
  11 #include "common/CDC.h"
  12 #include "gtest/gtest.h"
  13
  14 using namespace std;
  15
  16 class CDCTest : public ::testing::Test,
  17                 public ::testing::WithParamInterface<const char*> {
  18 public:
  19   std::unique_ptr<CDC> cdc;
  20
  21   CDCTest() {
  22     auto plugin = GetParam();
  23     cdc = CDC::create(plugin, 18);
  24   }
  25 };
  26
  27 TEST_P(CDCTest, insert_front)
  28 {
  29   if (GetParam() == "fixed"s) return;
  30   for (int frontlen = 1; frontlen < 163840; frontlen *= 3) {
  31     bufferlist bl1, bl2;
  32     generate_buffer(4*1024*1024, &bl1);
  33     generate_buffer(frontlen, &bl2);
  34     bl2.append(bl1);
  35     bl2.rebuild();
  36
  37     vector<pair<uint64_t, uint64_t>> chunks1, chunks2;
  38     cdc->calc_chunks(bl1, &chunks1);
  39     cdc->calc_chunks(bl2, &chunks2);
  40     cout << "1: " << chunks1 << std::endl;
  41     cout << "2: " << chunks2 << std::endl;
  42
  43     ASSERT_GE(chunks2.size(), chunks1.size());
  44     int match = 0;
  45     for (unsigned i = 0; i < chunks1.size(); ++i) {
  46       unsigned j = i + (chunks2.size() - chunks1.size());
  47       if (chunks1[i].first + frontlen == chunks2[j].first &&
  48           chunks1[i].second == chunks2[j].second) {
  49         match++;
  50       }
  51     }
  52     ASSERT_GE(match, chunks1.size() - 1);
  53   }
  54 }
  55
  56 TEST_P(CDCTest, insert_middle)
  57 {
  58   if (GetParam() == "fixed"s) return;
  59   for (int frontlen = 1; frontlen < 163840; frontlen *= 3) {
  60     bufferlist bl1, bl2;
  61     generate_buffer(4*1024*1024, &bl1);
  62     bufferlist f, m, e;
  63     generate_buffer(frontlen, &m);
  64     f.substr_of(bl1, 0, bl1.length() / 2);
  65     e.substr_of(bl1, bl1.length() / 2, bl1.length() / 2);
  66     bl2 = f;
  67     bl2.append(m);
  68     bl2.append(e);
  69     bl2.rebuild();
  70
  71     vector<pair<uint64_t, uint64_t>> chunks1, chunks2;
  72     cdc->calc_chunks(bl1, &chunks1);
  73     cdc->calc_chunks(bl2, &chunks2);
  74     cout << "1: " << chunks1 << std::endl;
  75     cout << "2: " << chunks2 << std::endl;
  76
  77     ASSERT_GE(chunks2.size(), chunks1.size());
  78     int match = 0;
  79     unsigned i;
  80     for (i = 0; i < chunks1.size()/2; ++i) {
  81       unsigned j = i;
  82       if (chunks1[i].first == chunks2[j].first &&
  83           chunks1[i].second == chunks2[j].second) {
  84         match++;
  85       }
  86     }
  87     for (; i < chunks1.size(); ++i) {
  88       unsigned j = i + (chunks2.size() - chunks1.size());
  89       if (chunks1[i].first + frontlen == chunks2[j].first &&
  90           chunks1[i].second == chunks2[j].second) {
  91         match++;
  92       }
  93     }
  94     ASSERT_GE(match, chunks1.size() - 2);
  95   }
  96 }
  97
  98 TEST_P(CDCTest, specific_result)
  99 {
 100   map<string,vector<pair<uint64_t,uint64_t>>> expected = {
 101     {"fixed", { {0, 262144}, {262144, 262144}, {524288, 262144}, {786432, 262144}, {1048576, 262144}, {1310720, 262144}, {1572864, 262144}, {1835008, 262144}, {2097152, 262144}, {2359296, 262144}, {2621440, 262144}, {2883584, 262144}, {3145728, 262144}, {3407872, 262144}, {3670016, 262144}, {3932160, 262144} }},
 102     {"fastcdc", { {0, 151460}, {151460, 441676}, {593136, 407491}, {1000627, 425767}, {1426394, 602875}, {2029269, 327307}, {2356576, 155515}, {2512091, 159392}, {2671483, 829416}, {3500899, 539667}, {4040566, 153738}}},
 103   };
 104
 105   bufferlist bl;
 106   generate_buffer(4*1024*1024, &bl);
 107   vector<pair<uint64_t,uint64_t>> chunks;
 108   cdc->calc_chunks(bl, &chunks);
 109   ASSERT_EQ(chunks, expected[GetParam()]);
 110 }
 111
 112
 113 void do_size_histogram(CDC& cdc, bufferlist& bl,
 114                        map<int,int> *h)
 115 {
 116   vector<pair<uint64_t, uint64_t>> chunks;
 117   cdc.calc_chunks(bl, &chunks);
 118   uint64_t total = 0;
 119   uint64_t num = 0;
 120   for (auto& i : chunks) {
 121     //unsigned b = i.second & 0xfffff000;
 122     unsigned b = 1 << (cbits(i.second - 1));
 123     (*h)[b]++;
 124     ++num;
 125     total += i.second;
 126   }
 127   (*h)[0] = total / num;
 128 }
 129
 130 void print_histogram(map<int,int>& h)
 131 {
 132   cout << "size\tcount" << std::endl;
 133   for (auto i : h) {
 134     if (i.first) {
 135       cout << i.first << "\t" << i.second << std::endl;
 136     } else {
 137       cout << "avg\t" << i.second << std::endl;
 138     }
 139   }
 140 }
 141
 142 TEST_P(CDCTest, chunk_random)
 143 {
 144   map<int,int> h;
 145   for (int i = 0; i < 32; ++i) {
 146     cout << ".";
 147     cout.flush();
 148     bufferlist r;
 149     generate_buffer(16*1024*1024, &r, i);
 150     do_size_histogram(*cdc, r, &h);
 151   }
 152   cout << std::endl;
 153   print_histogram(h);
 154 }
 155
 156
 157 INSTANTIATE_TEST_SUITE_P(
 158   CDC,
 159   CDCTest,
 160   ::testing::Values(
 161     "fixed",   // note: we skip most tests bc this is not content-based
 162     "fastcdc"
 163     ));