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