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