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