ceph/src/test/objectstore/Allocator_test.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 test cases.
   5  * Author: Ramesh Chander, Ramesh.Chander@sandisk.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 typedef boost::mt11213b gen_type;
  18
  19 class AllocTest : public ::testing::TestWithParam<const char*> {
  20
  21 public:
  22   boost::scoped_ptr<Allocator> alloc;
  23   AllocTest(): alloc(0) { }
  24   void init_alloc(int64_t size, uint64_t min_alloc_size) {
  25     std::cout << "Creating alloc type " << string(GetParam()) << " \n";
  26     alloc.reset(Allocator::create(g_ceph_context, string(GetParam()), size,
  27                                   min_alloc_size));
  28   }
  29
  30   void init_close() {
  31     alloc.reset(0);
  32   }
  33 };
  34
  35 TEST_P(AllocTest, test_alloc_init)
  36 {
  37   int64_t blocks = 64;
  38   init_alloc(blocks, 1);
  39   ASSERT_EQ(0U, alloc->get_free());
  40   alloc->shutdown();
  41   blocks = 1024 * 2 + 16;
  42   init_alloc(blocks, 1);
  43   ASSERT_EQ(0U, alloc->get_free());
  44   alloc->shutdown();
  45   blocks = 1024 * 2;
  46   init_alloc(blocks, 1);
  47   ASSERT_EQ(alloc->get_free(), (uint64_t) 0);
  48 }
  49
  50 TEST_P(AllocTest, test_alloc_min_alloc)
  51 {
  52   int64_t block_size = 1024;
  53   int64_t capacity = 4 * 1024 * block_size;
  54
  55   {
  56     init_alloc(capacity, block_size);
  57
  58     alloc->init_add_free(block_size, block_size);
  59     PExtentVector extents;
  60     EXPECT_EQ(block_size, alloc->allocate(block_size, block_size,
  61                                           0, (int64_t) 0, &extents));
  62   }
  63
  64   /*
  65    * Allocate extent and make sure all comes in single extent.
  66    */
  67   {
  68     init_alloc(capacity, block_size);
  69     alloc->init_add_free(0, block_size * 4);
  70     PExtentVector extents;
  71     EXPECT_EQ(4*block_size,
  72               alloc->allocate(4 * (uint64_t)block_size, (uint64_t) block_size,
  73                               0, (int64_t) 0, &extents));
  74     EXPECT_EQ(1u, extents.size());
  75     EXPECT_EQ(extents[0].length, 4 * block_size);
  76   }
  77
  78   /*
  79    * Allocate extent and make sure we get two different extents.
  80    */
  81   {
  82     init_alloc(capacity, block_size);
  83     alloc->init_add_free(0, block_size * 2);
  84     alloc->init_add_free(3 * block_size, block_size * 2);
  85     PExtentVector extents;
  86
  87     EXPECT_EQ(4*block_size,
  88               alloc->allocate(4 * (uint64_t)block_size, (uint64_t) block_size,
  89                               0, (int64_t) 0, &extents));
  90     EXPECT_EQ(2u, extents.size());
  91     EXPECT_EQ(extents[0].length, 2 * block_size);
  92     EXPECT_EQ(extents[1].length, 2 * block_size);
  93   }
  94   alloc->shutdown();
  95 }
  96
  97 TEST_P(AllocTest, test_alloc_min_max_alloc)
  98 {
  99   int64_t block_size = 1024;
 100
 101   int64_t capacity = 4 * 1024 * block_size;
 102   init_alloc(capacity, block_size);
 103
 104   /*
 105    * Make sure we get all extents different when
 106    * min_alloc_size == max_alloc_size
 107    */
 108   {
 109     init_alloc(capacity, block_size);
 110     alloc->init_add_free(0, block_size * 4);
 111     PExtentVector extents;
 112     EXPECT_EQ(4*block_size,
 113               alloc->allocate(4 * (uint64_t)block_size, (uint64_t) block_size,
 114                               block_size, (int64_t) 0, &extents));
 115     for (auto e : extents) {
 116       EXPECT_EQ(e.length, block_size);
 117     }
 118     EXPECT_EQ(4u, extents.size());
 119   }
 120
 121
 122   /*
 123    * Make sure we get extents of length max_alloc size
 124    * when max alloc size > min_alloc size
 125    */
 126   {
 127     init_alloc(capacity, block_size);
 128     alloc->init_add_free(0, block_size * 4);
 129     PExtentVector extents;
 130     EXPECT_EQ(4*block_size,
 131               alloc->allocate(4 * (uint64_t)block_size, (uint64_t) block_size,
 132                               2 * block_size, (int64_t) 0, &extents));
 133     EXPECT_EQ(2u, extents.size());
 134     for (auto& e : extents) {
 135       EXPECT_EQ(e.length, block_size * 2);
 136     }
 137   }
 138
 139   /*
 140    * Make sure allocations are of min_alloc_size when min_alloc_size > block_size.
 141    */
 142   {
 143     init_alloc(capacity, block_size);
 144     alloc->init_add_free(0, block_size * 1024);
 145     PExtentVector extents;
 146     EXPECT_EQ(1024 * block_size,
 147               alloc->allocate(1024 * (uint64_t)block_size,
 148                               (uint64_t) block_size * 4,
 149                               block_size * 4, (int64_t) 0, &extents));
 150     for (auto& e : extents) {
 151       EXPECT_EQ(e.length, block_size * 4);
 152     }
 153     EXPECT_EQ(1024u/4, extents.size());
 154   }
 155
 156   /*
 157    * Allocate and free.
 158    */
 159   {
 160     init_alloc(capacity, block_size);
 161     alloc->init_add_free(0, block_size * 16);
 162     PExtentVector extents;
 163     EXPECT_EQ(16 * block_size,
 164               alloc->allocate(16 * (uint64_t)block_size, (uint64_t) block_size,
 165                               2 * block_size, (int64_t) 0, &extents));
 166
 167     EXPECT_EQ(extents.size(), 8u);
 168     for (auto& e : extents) {
 169       EXPECT_EQ(e.length, 2 * block_size);
 170     }
 171   }
 172 }
 173
 174 TEST_P(AllocTest, test_alloc_failure)
 175 {
 176   int64_t block_size = 1024;
 177   int64_t capacity = 4 * 1024 * block_size;
 178
 179   {
 180     init_alloc(capacity, block_size);
 181     alloc->init_add_free(0, block_size * 256);
 182     alloc->init_add_free(block_size * 512, block_size * 256);
 183
 184     PExtentVector extents;
 185     EXPECT_EQ(512 * block_size,
 186               alloc->allocate(512 * (uint64_t)block_size,
 187                               (uint64_t) block_size * 256,
 188                               block_size * 256, (int64_t) 0, &extents));
 189     alloc->init_add_free(0, block_size * 256);
 190     alloc->init_add_free(block_size * 512, block_size * 256);
 191     extents.clear();
 192     EXPECT_EQ(-ENOSPC,
 193               alloc->allocate(512 * (uint64_t)block_size,
 194                               (uint64_t) block_size * 512,
 195                               block_size * 512, (int64_t) 0, &extents));
 196   }
 197 }
 198
 199 TEST_P(AllocTest, test_alloc_big)
 200 {
 201   int64_t block_size = 4096;
 202   int64_t blocks = 104857600;
 203   int64_t mas = 4096;
 204   init_alloc(blocks*block_size, block_size);
 205   alloc->init_add_free(2*block_size, (blocks-2)*block_size);
 206   for (int64_t big = mas; big < 1048576*128; big*=2) {
 207     cout << big << std::endl;
 208     PExtentVector extents;
 209     EXPECT_EQ(big,
 210               alloc->allocate(big, mas, 0, &extents));
 211   }
 212 }
 213
 214 TEST_P(AllocTest, test_alloc_non_aligned_len)
 215 {
 216   int64_t block_size = 1 << 12;
 217   int64_t blocks = (1 << 20) * 100;
 218   int64_t want_size = 1 << 22;
 219   int64_t alloc_unit = 1 << 20;
 220
 221   init_alloc(blocks*block_size, block_size);
 222   alloc->init_add_free(0, 2097152);
 223   alloc->init_add_free(2097152, 1064960);
 224   alloc->init_add_free(3670016, 2097152);
 225
 226   PExtentVector extents;
 227   EXPECT_EQ(want_size, alloc->allocate(want_size, alloc_unit, 0, &extents));
 228 }
 229
 230 TEST_P(AllocTest, test_alloc_39334)
 231 {
 232   uint64_t block = 0x4000;
 233   uint64_t size = 0x5d00000000;
 234
 235   init_alloc(size, block);
 236   alloc->init_add_free(0x4000, 0x5cffffc000);
 237   EXPECT_EQ(size - block, alloc->get_free());
 238 }
 239
 240 TEST_P(AllocTest, test_alloc_fragmentation)
 241 {
 242   uint64_t capacity = 4 * 1024 * 1024;
 243   uint64_t alloc_unit = 4096;
 244   uint64_t want_size = alloc_unit;
 245   PExtentVector allocated, tmp;
 246
 247   init_alloc(capacity, alloc_unit);
 248   alloc->init_add_free(0, capacity);
 249   bool bitmap_alloc = GetParam() == std::string("bitmap");
 250
 251   EXPECT_EQ(0.0, alloc->get_fragmentation());
 252
 253   for (size_t i = 0; i < capacity / alloc_unit; ++i)
 254   {
 255     tmp.clear();
 256     EXPECT_EQ(static_cast<int64_t>(want_size),
 257               alloc->allocate(want_size, alloc_unit, 0, 0, &tmp));
 258     allocated.insert(allocated.end(), tmp.begin(), tmp.end());
 259
 260     // bitmap fragmentation calculation doesn't provide such constant
 261     // estimate
 262     if (!bitmap_alloc) {
 263       EXPECT_EQ(0.0, alloc->get_fragmentation());
 264     }
 265   }
 266   tmp.clear();
 267   EXPECT_EQ(-ENOSPC, alloc->allocate(want_size, alloc_unit, 0, 0, &tmp));
 268
 269   if (GetParam() == string("avl")) {
 270     // AVL allocator uses a different allocating strategy
 271     GTEST_SKIP() << "skipping for AVL allocator";
 272   } else if (GetParam() == string("hybrid")) {
 273     // AVL allocator uses a different allocating strategy
 274     GTEST_SKIP() << "skipping for Hybrid allocator";
 275   }
 276
 277   for (size_t i = 0; i < allocated.size(); i += 2)
 278   {
 279     interval_set<uint64_t> release_set;
 280     release_set.insert(allocated[i].offset, allocated[i].length);
 281     alloc->release(release_set);
 282   }
 283   EXPECT_EQ(1.0, alloc->get_fragmentation());
 284   EXPECT_EQ(66u, uint64_t(alloc->get_fragmentation_score() * 100));
 285
 286   for (size_t i = 1; i < allocated.size() / 2; i += 2)
 287   {
 288     interval_set<uint64_t> release_set;
 289     release_set.insert(allocated[i].offset, allocated[i].length);
 290     alloc->release(release_set);
 291   }
 292   if (bitmap_alloc) {
 293     // fragmentation = one l1 slot is free + one l1 slot is partial
 294     EXPECT_EQ(50U, uint64_t(alloc->get_fragmentation() * 100));
 295   } else {
 296     // fragmentation approx = 257 intervals / 768 max intervals
 297     EXPECT_EQ(33u, uint64_t(alloc->get_fragmentation() * 100));
 298   }
 299   EXPECT_EQ(27u, uint64_t(alloc->get_fragmentation_score() * 100));
 300
 301   for (size_t i = allocated.size() / 2 + 1; i < allocated.size(); i += 2)
 302   {
 303     interval_set<uint64_t> release_set;
 304     release_set.insert(allocated[i].offset, allocated[i].length);
 305     alloc->release(release_set);
 306   }
 307   // doing some rounding trick as stupid allocator doesn't merge all the
 308   // extents that causes some minor fragmentation (minor bug or by-design behavior?).
 309   // Hence leaving just two
 310   // digits after decimal point due to this.
 311   EXPECT_EQ(0u, uint64_t(alloc->get_fragmentation() * 100));
 312   if (bitmap_alloc) {
 313     EXPECT_EQ(0u, uint64_t(alloc->get_fragmentation_score() * 100));
 314   } else {
 315     EXPECT_EQ(11u, uint64_t(alloc->get_fragmentation_score() * 100));
 316   }
 317 }
 318
 319 TEST_P(AllocTest, test_dump_fragmentation_score)
 320 {
 321   uint64_t capacity = 1024 * 1024 * 1024;
 322   uint64_t one_alloc_max = 2 * 1024 * 1024;
 323   uint64_t alloc_unit = 4096;
 324   uint64_t want_size = alloc_unit;
 325   uint64_t rounds = 10;
 326   uint64_t actions_per_round = 1000;
 327   PExtentVector allocated, tmp;
 328   gen_type rng;
 329
 330   init_alloc(capacity, alloc_unit);
 331   alloc->init_add_free(0, capacity);
 332
 333   EXPECT_EQ(0.0, alloc->get_fragmentation());
 334   EXPECT_EQ(0.0, alloc->get_fragmentation_score());
 335
 336   uint64_t allocated_cnt = 0;
 337   for (size_t round = 0; round < rounds ; round++) {
 338     for (size_t j = 0; j < actions_per_round ; j++) {
 339       //free or allocate ?
 340       if ( rng() % capacity >= allocated_cnt ) {
 341         //allocate
 342         want_size = ( rng() % one_alloc_max ) / alloc_unit * alloc_unit + alloc_unit;
 343         tmp.clear();
 344         uint64_t r = alloc->allocate(want_size, alloc_unit, 0, 0, &tmp);
 345         for (auto& t: tmp) {
 346           if (t.length > 0)
 347             allocated.push_back(t);
 348         }
 349         allocated_cnt += r;
 350       } else {
 351         //free
 352         ceph_assert(allocated.size() > 0);
 353         size_t item = rng() % allocated.size();
 354         ceph_assert(allocated[item].length > 0);
 355         allocated_cnt -= allocated[item].length;
 356         interval_set<uint64_t> release_set;
 357         release_set.insert(allocated[item].offset, allocated[item].length);
 358         alloc->release(release_set);
 359         std::swap(allocated[item], allocated[allocated.size() - 1]);
 360         allocated.resize(allocated.size() - 1);
 361       }
 362     }
 363
 364     size_t free_sum = 0;
 365     auto iterated_allocation = [&](size_t off, size_t len) {
 366       ceph_assert(len > 0);
 367       free_sum += len;
 368     };
 369     alloc->dump(iterated_allocation);
 370     EXPECT_GT(1, alloc->get_fragmentation_score());
 371     EXPECT_EQ(capacity, free_sum + allocated_cnt);
 372   }
 373
 374   for (size_t i = 0; i < allocated.size(); i ++)
 375   {
 376     interval_set<uint64_t> release_set;
 377     release_set.insert(allocated[i].offset, allocated[i].length);
 378     alloc->release(release_set);
 379   }
 380 }
 381
 382 TEST_P(AllocTest, test_alloc_bug_24598)
 383 {
 384   if (string(GetParam()) != "bitmap")
 385     return;
 386
 387   uint64_t capacity = 0x2625a0000ull;
 388   uint64_t alloc_unit = 0x4000;
 389   uint64_t want_size = 0x200000;
 390   PExtentVector allocated, tmp;
 391
 392   init_alloc(capacity, alloc_unit);
 393
 394   alloc->init_add_free(0x4800000, 0x100000);
 395   alloc->init_add_free(0x4a00000, 0x100000);
 396
 397   alloc->init_rm_free(0x4800000, 0x100000);
 398   alloc->init_rm_free(0x4a00000, 0x100000);
 399
 400   alloc->init_add_free(0x3f00000, 0x500000);
 401   alloc->init_add_free(0x4500000, 0x100000);
 402   alloc->init_add_free(0x4700000, 0x100000);
 403   alloc->init_add_free(0x4900000, 0x100000);
 404   alloc->init_add_free(0x4b00000, 0x200000);
 405
 406   EXPECT_EQ(static_cast<int64_t>(want_size),
 407             alloc->allocate(want_size, 0x100000, 0, 0, &tmp));
 408   EXPECT_EQ(1u, tmp.size());
 409   EXPECT_EQ(0x4b00000u, tmp[0].offset);
 410   EXPECT_EQ(0x200000u, tmp[0].length);
 411 }
 412
 413 //Verifies issue from
 414 //http://tracker.ceph.com/issues/40703
 415 //
 416 TEST_P(AllocTest, test_alloc_big2)
 417 {
 418   int64_t block_size = 4096;
 419   int64_t blocks = 1048576 * 2;
 420   int64_t mas = 1024*1024;
 421   init_alloc(blocks*block_size, block_size);
 422   alloc->init_add_free(0, blocks * block_size);
 423
 424   PExtentVector extents;
 425   uint64_t need = block_size * blocks / 4; // 2GB
 426   EXPECT_EQ(need,
 427       alloc->allocate(need, mas, 0, &extents));
 428   need = block_size * blocks / 4; // 2GB
 429   extents.clear();
 430   EXPECT_EQ(need,
 431       alloc->allocate(need, mas, 0, &extents));
 432   EXPECT_TRUE(extents[0].length > 0);
 433 }
 434
 435 //Verifies stuck 4GB chunk allocation
 436 //in StupidAllocator
 437 //
 438 TEST_P(AllocTest, test_alloc_big3)
 439 {
 440   int64_t block_size = 4096;
 441   int64_t blocks = 1048576 * 2;
 442   int64_t mas = 1024*1024;
 443   init_alloc(blocks*block_size, block_size);
 444   alloc->init_add_free(0, blocks * block_size);
 445
 446   PExtentVector extents;
 447   uint64_t need = block_size * blocks / 2; // 4GB
 448   EXPECT_EQ(need,
 449       alloc->allocate(need, mas, 0, &extents));
 450   EXPECT_TRUE(extents[0].length > 0);
 451 }
 452
 453 TEST_P(AllocTest, test_alloc_contiguous)
 454 {
 455   int64_t block_size = 0x1000;
 456   int64_t capacity = block_size * 1024 * 1024;
 457
 458   {
 459     init_alloc(capacity, block_size);
 460
 461     alloc->init_add_free(0, capacity);
 462     PExtentVector extents;
 463     uint64_t need = 4 * block_size;
 464     EXPECT_EQ(need,
 465       alloc->allocate(need, need,
 466         0, (int64_t)0, &extents));
 467     EXPECT_EQ(1u, extents.size());
 468     EXPECT_EQ(extents[0].offset, 0);
 469     EXPECT_EQ(extents[0].length, 4 * block_size);
 470
 471     extents.clear();
 472     EXPECT_EQ(need,
 473       alloc->allocate(need, need,
 474         0, (int64_t)0, &extents));
 475     EXPECT_EQ(1u, extents.size());
 476     EXPECT_EQ(extents[0].offset, 4 * block_size);
 477     EXPECT_EQ(extents[0].length, 4 * block_size);
 478   }
 479
 480   alloc->shutdown();
 481 }
 482
 483 TEST_P(AllocTest, test_alloc_47883)
 484 {
 485   uint64_t block = 0x1000;
 486   uint64_t size = 1599858540544ul;
 487
 488   init_alloc(size, block);
 489
 490   alloc->init_add_free(0x1b970000, 0x26000);
 491   alloc->init_add_free(0x1747e9d5000, 0x493000);
 492   alloc->init_add_free(0x1747ee6a000, 0x196000);
 493
 494   PExtentVector extents;
 495   auto need = 0x3f980000;
 496   auto got = alloc->allocate(need, 0x10000, 0, (int64_t)0, &extents);
 497   EXPECT_GT(got, 0);
 498   EXPECT_EQ(got, 0x630000);
 499 }
 500
 501 INSTANTIATE_TEST_SUITE_P(
 502   Allocator,
 503   AllocTest,
 504   ::testing::Values("stupid", "bitmap", "avl", "hybrid"));