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