ceph/src/test/objectstore/Allocator_bench.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * In memory space allocator benchmarks.
   5  * Author: Igor Fedotov, ifedotov@suse.com
   6  */
   7 #include <iostream>
   8 #include <boost/scoped_ptr.hpp>
   9 #include <gtest/gtest.h>
  10
  11 #include "common/Cond.h"
  12 #include "common/errno.h"
  13 #include "include/stringify.h"
  14 #include "include/Context.h"
  15 #include "os/bluestore/Allocator.h"
  16
  17 #include <boost/random/uniform_int.hpp>
  18 typedef boost::mt11213b gen_type;
  19
  20 #include "common/debug.h"
  21 #define dout_context g_ceph_context
  22 #define dout_subsys ceph_subsys_
  23
  24 using namespace std;
  25
  26 class AllocTest : public ::testing::TestWithParam<const char*> {
  27
  28 public:
  29   boost::scoped_ptr<Allocator> alloc;
  30   AllocTest(): alloc(0) { }
  31   void init_alloc(int64_t size, uint64_t min_alloc_size) {
  32     std::cout << "Creating alloc type " << string(GetParam()) << " \n";
  33     alloc.reset(Allocator::create(g_ceph_context, GetParam(), size,
  34                                   min_alloc_size));
  35   }
  36
  37   void init_close() {
  38     alloc.reset(0);
  39   }
  40   void doOverwriteTest(uint64_t capacity, uint64_t prefill,
  41     uint64_t overwrite);
  42 };
  43
  44 const uint64_t _1m = 1024 * 1024;
  45
  46 void dump_mempools()
  47 {
  48   ostringstream ostr;
  49   Formatter* f = Formatter::create("json-pretty", "json-pretty", "json-pretty");
  50   ostr << "Mempools: ";
  51   f->open_object_section("mempools");
  52   mempool::dump(f);
  53   f->close_section();
  54   f->flush(ostr);
  55   delete f;
  56   ldout(g_ceph_context, 0) << ostr.str() << dendl;
  57 }
  58
  59 class AllocTracker
  60 {
  61   std::vector<uint64_t> allocations;
  62   uint64_t head = 0;
  63   uint64_t tail = 0;
  64   uint64_t size = 0;
  65   boost::uniform_int<> u1;
  66
  67 public:
  68   AllocTracker(uint64_t capacity, uint64_t alloc_unit)
  69     : u1(0, capacity)
  70   {
  71     ceph_assert(alloc_unit >= 0x100);
  72     ceph_assert(capacity <= (uint64_t(1) << 48)); // we use 5 octets (bytes 1 - 5) to store
  73                                  // offset to save the required space.
  74                                  // This supports capacity up to 281 TB
  75
  76     allocations.resize(capacity / alloc_unit);
  77   }
  78   inline uint64_t get_head() const
  79   {
  80     return head;
  81   }
  82
  83   inline uint64_t get_tail() const
  84   {
  85     return tail;
  86   }
  87
  88   bool push(uint64_t offs, uint32_t len)
  89   {
  90     ceph_assert((len & 0xff) == 0);
  91     ceph_assert((offs & 0xff) == 0);
  92     ceph_assert((offs & 0xffff000000000000) == 0);
  93
  94     if (head + 1 == tail)
  95       return false;
  96     uint64_t val = (offs << 16) | (len >> 8);
  97     allocations[head++] = val;
  98     head %= allocations.size();
  99     ++size;
 100     return true;
 101   }
 102   bool pop(uint64_t* offs, uint32_t* len)
 103   {
 104     if (size == 0)
 105       return false;
 106     uint64_t val = allocations[tail++];
 107     *len = uint64_t((val & 0xffffff) << 8);
 108     *offs = (val >> 16) & ~uint64_t(0xff);
 109     tail %= allocations.size();
 110     --size;
 111     return true;
 112   }
 113   bool pop_random(gen_type& rng, uint64_t* offs, uint32_t* len,
 114     uint32_t max_len = 0)
 115   {
 116     if (size == 0)
 117       return false;
 118
 119     uint64_t pos = (u1(rng) % size) + tail;
 120     pos %= allocations.size();
 121     uint64_t val = allocations[pos];
 122     *len = uint64_t((val & 0xffffff) << 8);
 123     *offs = (val >> 16) & ~uint64_t(0xff);
 124     if (max_len && *len > max_len) {
 125       val = ((*offs + max_len) << 16) | ((*len - max_len) >> 8);
 126       allocations[pos] = val;
 127       *len = max_len;
 128     } else {
 129       allocations[pos] = allocations[tail++];
 130       tail %= allocations.size();
 131       --size;
 132     }
 133     return true;
 134   }
 135 };
 136
 137 TEST_P(AllocTest, test_alloc_bench_seq)
 138 {
 139   uint64_t capacity = uint64_t(1024) * 1024 * 1024 * 1024;
 140   uint64_t alloc_unit = 4096;
 141   uint64_t want_size = alloc_unit;
 142   PExtentVector allocated, tmp;
 143
 144   init_alloc(capacity, alloc_unit);
 145   alloc->init_add_free(0, capacity);
 146
 147   utime_t start = ceph_clock_now();
 148   for (uint64_t i = 0; i < capacity; i += want_size)
 149   {
 150     tmp.clear();
 151     EXPECT_EQ(static_cast<int64_t>(want_size),
 152               alloc->allocate(want_size, alloc_unit, 0, 0, &tmp));
 153     if (0 == (i % (1 * 1024 * _1m))) {
 154       std::cout << "alloc " << i / 1024 / 1024 << " mb of "
 155         << capacity / 1024 / 1024 << std::endl;
 156     }
 157   }
 158
 159   std::cout << "releasing..." << std::endl;
 160   for (size_t i = 0; i < capacity; i += want_size)
 161   {
 162     interval_set<uint64_t> release_set;
 163     release_set.insert(i, want_size);
 164     alloc->release(release_set);
 165     if (0 == (i % (1 * 1024 * _1m))) {
 166       std::cout << "release " << i / 1024 / 1024 << " mb of "
 167         << capacity / 1024 / 1024 << std::endl;
 168     }
 169   }
 170   std::cout<<"Executed in "<< ceph_clock_now() - start << std::endl;
 171   dump_mempools();
 172 }
 173
 174 TEST_P(AllocTest, test_alloc_bench)
 175 {
 176   uint64_t capacity = uint64_t(1024) * 1024 * 1024 * 1024;
 177   uint64_t alloc_unit = 4096;
 178   PExtentVector allocated, tmp;
 179   AllocTracker at(capacity, alloc_unit);
 180
 181   init_alloc(capacity, alloc_unit);
 182   alloc->init_add_free(0, capacity);
 183
 184   gen_type rng(time(NULL));
 185   boost::uniform_int<> u1(0, 9); // 4K-2M
 186   boost::uniform_int<> u2(0, 7); // 4K-512K
 187
 188   utime_t start = ceph_clock_now();
 189   for (uint64_t i = 0; i < capacity * 2; )
 190   {
 191     uint32_t want = alloc_unit << u1(rng);
 192
 193     tmp.clear();
 194     auto r = alloc->allocate(want, alloc_unit, 0, 0, &tmp);
 195     if (r < want) {
 196       break;
 197     }
 198     i += r;
 199
 200     for(auto a : tmp) {
 201       bool full = !at.push(a.offset, a.length);
 202       EXPECT_EQ(full, false);
 203     }
 204     uint64_t want_release = alloc_unit << u2(rng);
 205     uint64_t released = 0;
 206     do {
 207       uint64_t o = 0;
 208       uint32_t l = 0;
 209       interval_set<uint64_t> release_set;
 210       if (!at.pop_random(rng, &o, &l, want_release - released)) {
 211         break;
 212       }
 213       release_set.insert(o, l);
 214       alloc->release(release_set);
 215       released += l;
 216     } while (released < want_release);
 217
 218     if (0 == (i % (1 * 1024 * _1m))) {
 219       std::cout << "alloc " << i / 1024 / 1024 << " mb of "
 220         << capacity / 1024 / 1024 << std::endl;
 221     }
 222   }
 223   std::cout<<"Executed in "<< ceph_clock_now() - start << std::endl;
 224   std::cout<<"Avail "<< alloc->get_free() / _1m << " MB" << std::endl;
 225   dump_mempools();
 226 }
 227
 228 void AllocTest::doOverwriteTest(uint64_t capacity, uint64_t prefill,
 229   uint64_t overwrite)
 230 {
 231   uint64_t alloc_unit = 4096;
 232   PExtentVector allocated, tmp;
 233   AllocTracker at(capacity, alloc_unit);
 234
 235   init_alloc(capacity, alloc_unit);
 236   alloc->init_add_free(0, capacity);
 237
 238   gen_type rng(time(NULL));
 239   boost::uniform_int<> u1(0, 9); // 4K-2M
 240   boost::uniform_int<> u2(0, 9); // 4K-512K
 241
 242   utime_t start = ceph_clock_now();
 243   // allocate 90% of the capacity
 244   auto cap = prefill;
 245   for (uint64_t i = 0; i < cap; )
 246   {
 247     uint32_t want = alloc_unit << u1(rng);
 248     tmp.clear();
 249     auto r = alloc->allocate(want, alloc_unit, 0, 0, &tmp);
 250     if (r < want) {
 251       break;
 252     }
 253     i += r;
 254
 255     for(auto a : tmp) {
 256       bool full = !at.push(a.offset, a.length);
 257       EXPECT_EQ(full, false);
 258     }
 259     if (0 == (i % (1 * 1024 * _1m))) {
 260       std::cout << "alloc " << i / 1024 / 1024 << " mb of "
 261         << cap / 1024 / 1024 << std::endl;
 262     }
 263   }
 264
 265   cap = overwrite;
 266   for (uint64_t i = 0; i < cap; )
 267   {
 268     uint64_t want_release = alloc_unit << u2(rng);
 269     uint64_t released = 0;
 270     do {
 271       uint64_t o = 0;
 272       uint32_t l = 0;
 273       interval_set<uint64_t> release_set;
 274       if (!at.pop_random(rng, &o, &l, want_release - released)) {
 275         break;
 276       }
 277       release_set.insert(o, l);
 278       alloc->release(release_set);
 279       released += l;
 280     } while (released < want_release);
 281
 282     uint32_t want = alloc_unit << u1(rng);
 283     tmp.clear();
 284     auto r = alloc->allocate(want, alloc_unit, 0, 0, &tmp);
 285     if (r != want) {
 286       std::cout<<"Can't allocate more space, stopping."<< std::endl;
 287       break;
 288     }
 289     i += r;
 290
 291     for(auto a : tmp) {
 292       bool full = !at.push(a.offset, a.length);
 293       EXPECT_EQ(full, false);
 294     }
 295
 296     if (0 == (i % (1 * 1024 * _1m))) {
 297       std::cout << "reuse " << i / 1024 / 1024 << " mb of "
 298         << cap / 1024 / 1024 << std::endl;
 299     }
 300   }
 301   std::cout<<"Executed in "<< ceph_clock_now() - start << std::endl;
 302   std::cout<<"Avail "<< alloc->get_free() / _1m << " MB" << std::endl;
 303
 304   dump_mempools();
 305 }
 306
 307 TEST_P(AllocTest, test_alloc_bench_90_300)
 308 {
 309   uint64_t capacity = uint64_t(1024) * 1024 * 1024 * 1024;
 310   auto prefill = capacity - capacity / 10;
 311   auto overwrite = capacity * 3;
 312   doOverwriteTest(capacity, prefill, overwrite);
 313 }
 314
 315 TEST_P(AllocTest, test_alloc_bench_50_300)
 316 {
 317   uint64_t capacity = uint64_t(1024) * 1024 * 1024 * 1024;
 318   auto prefill = capacity / 2;
 319   auto overwrite = capacity * 3;
 320   doOverwriteTest(capacity, prefill, overwrite);
 321 }
 322
 323 TEST_P(AllocTest, test_alloc_bench_10_300)
 324 {
 325   uint64_t capacity = uint64_t(1024) * 1024 * 1024 * 1024;
 326   auto prefill = capacity / 10;
 327   auto overwrite = capacity * 3;
 328   doOverwriteTest(capacity, prefill, overwrite);
 329 }
 330
 331 TEST_P(AllocTest, mempoolAccounting)
 332 {
 333   uint64_t bytes = mempool::bluestore_alloc::allocated_bytes();
 334   uint64_t items = mempool::bluestore_alloc::allocated_items();
 335
 336   uint64_t alloc_size = 4 * 1024;
 337   uint64_t capacity = 512ll * 1024 * 1024 * 1024;
 338   Allocator* alloc = Allocator::create(g_ceph_context, GetParam(),
 339                                        capacity, alloc_size);
 340   ASSERT_NE(alloc, nullptr);
 341   alloc->init_add_free(0, capacity);
 342
 343   std::map<uint32_t, PExtentVector> all_allocs;
 344   for (size_t i = 0; i < 10000; i++) {
 345     PExtentVector tmp;
 346     alloc->allocate(alloc_size, alloc_size, 0, 0, &tmp);
 347     all_allocs[rand()] = tmp;
 348     tmp.clear();
 349     alloc->allocate(alloc_size, alloc_size, 0, 0, &tmp);
 350     all_allocs[rand()] = tmp;
 351     tmp.clear();
 352
 353     auto it = all_allocs.upper_bound(rand());
 354     if (it != all_allocs.end()) {
 355       alloc->release(it->second);
 356       all_allocs.erase(it);
 357     }
 358   }
 359
 360   delete(alloc);
 361   ASSERT_EQ(mempool::bluestore_alloc::allocated_bytes(), bytes);
 362   ASSERT_EQ(mempool::bluestore_alloc::allocated_items(), items);
 363 }
 364
 365 INSTANTIATE_TEST_SUITE_P(
 366   Allocator,
 367   AllocTest,
 368   ::testing::Values("stupid", "bitmap", "avl", "btree", "hybrid"));