ceph/src/test/objectstore/BitAllocator_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  * Bitmap based in-memory allocator unit test cases.
   5  * Author: Ramesh Chander, Ramesh.Chander@sandisk.com
   6  */
   7
   8 #include "include/Context.h"
   9 #include "os/bluestore/BitAllocator.h"
  10 #include <stdio.h>
  11 #include <assert.h>
  12 #include <math.h>
  13 #include <sstream>
  14 #include <gtest/gtest.h>
  15
  16
  17 //#define bmap_test_assert(x) ASSERT_EQ(true, (x))
  18 #define bmap_test_assert(x) assert((x))
  19 #define NUM_THREADS 16
  20 #define MAX_BLOCKS (1024 * 1024 * 1)
  21
  22 TEST(BitAllocator, test_bmap_iter)
  23 {
  24   int num_items = 5;
  25   int off = 2;
  26
  27   class BmapEntityTmp {
  28       int64_t m_num;
  29       int64_t m_len;
  30     public:
  31       void init(int index) {
  32         m_num = index;
  33       }
  34       BmapEntityTmp() {
  35
  36       }
  37       BmapEntityTmp(int num) {
  38         m_num = num;
  39         m_len = num;
  40       }
  41
  42       int64_t get_index() {
  43         return m_num;
  44       }
  45       bool is_allocated(int64_t s, int64_t num)
  46       {
  47         return true;
  48       }
  49   };
  50   BmapEntityTmp *obj = NULL;
  51   int i = 0;
  52   mempool::bluestore_alloc::vector<BmapEntityTmp> *arr = new mempool::bluestore_alloc::vector<BmapEntityTmp>(num_items);
  53   for (i = 0; i < num_items; i++) {
  54     (*arr)[i].init(i);
  55   }
  56   BitMapEntityIter<BmapEntityTmp> iter = BitMapEntityIter<BmapEntityTmp>(arr, off, false);
  57
  58   i = off;
  59   int count = 0;
  60   int64_t last_idx = off;
  61   while ((obj = iter.next())) {
  62     bmap_test_assert(obj->get_index() == last_idx);
  63     bmap_test_assert(obj->get_index() == i);
  64     bmap_test_assert(obj == &(*arr)[i]);
  65     last_idx = iter.index();
  66     i++;
  67     count++;
  68   }
  69   bmap_test_assert(i == num_items);
  70   bmap_test_assert(count == num_items - off);
  71
  72   iter = BitMapEntityIter<BmapEntityTmp>(arr, off, true);
  73
  74   i = off;
  75   last_idx = off;
  76   count = 0;
  77   while ((obj = iter.next())) {
  78     bmap_test_assert(obj->get_index() == last_idx);
  79     bmap_test_assert(obj->get_index() == i);
  80     bmap_test_assert(obj == &(*arr)[i]);
  81     last_idx = iter.index();
  82
  83     i = (i + 1) % num_items;
  84     count++;
  85   }
  86   bmap_test_assert(i == off + 1);
  87   bmap_test_assert(count == num_items + 1);
  88
  89   delete arr;
  90
  91   num_items = 4;
  92   off = num_items - 1;
  93
  94   arr = new mempool::bluestore_alloc::vector<BmapEntityTmp>(num_items);
  95   for (i = 0; i < num_items; i++) {
  96     (*arr)[i].init(i);
  97   }
  98   iter = BitMapEntityIter<BmapEntityTmp>(arr, off, true);
  99   i = off;
 100   last_idx = off;
 101   count = 0;
 102   while ((obj = static_cast<BmapEntityTmp*>(iter.next()))) {
 103     bmap_test_assert(obj->get_index() == last_idx);
 104     bmap_test_assert(obj->get_index() == i);
 105     bmap_test_assert(obj == &(*arr)[i]);
 106     last_idx = iter.index();
 107     i = (i + 1) % num_items;
 108     count++;
 109   }
 110   bmap_test_assert(i == (off + 1)%num_items);
 111   bmap_test_assert(count == num_items + 1);
 112
 113   delete arr;
 114
 115   /*
 116    * BitMapArea Iter tests.
 117    */
 118   BitMapArea *area = nullptr;
 119   std::vector<BitMapArea*> children;
 120   children.reserve(num_items);
 121   for (i = 0; i < num_items; i++) {
 122     children.emplace_back(new BitMapAreaLeaf(
 123       g_ceph_context,
 124       BitMapArea::get_span_size(g_ceph_context), i, false));
 125   }
 126
 127   off = 0;
 128   BitMapAreaList *area_list = \
 129     new BitMapAreaList(std::vector<BitMapArea*>(children));
 130   BmapEntityListIter area_iter = BmapEntityListIter(
 131                                 area_list, (int64_t) 0);
 132   i = off;
 133   last_idx = off;
 134   count = 0;
 135   while ((area = area_iter.next())) {
 136     bmap_test_assert(area->get_index() == last_idx);
 137     bmap_test_assert(area->get_index() == i);
 138     bmap_test_assert(area == children[i]);
 139     last_idx = area_iter.index();
 140     i = (i + 1) % num_items;
 141     count++;
 142   }
 143   bmap_test_assert(i == off);
 144   bmap_test_assert(count == num_items);
 145
 146   off = 0;
 147   area_iter = BmapEntityListIter(area_list, off, true);
 148   i = off;
 149   last_idx = off;
 150   count = 0;
 151   while ((area = area_iter.next())) {
 152     bmap_test_assert(area->get_index() == last_idx);
 153     bmap_test_assert(area->get_index() == i);
 154     bmap_test_assert(area == children[i]);
 155     last_idx = area_iter.index();
 156     i = (i + 1) % num_items;
 157     count++;
 158   }
 159   bmap_test_assert(i == (off + 1)%num_items);
 160   bmap_test_assert(count == num_items + 1);
 161
 162   for (i = 0; i < num_items; i++)
 163     delete children[i];
 164
 165   delete area_list;
 166 }
 167
 168 TEST(BitAllocator, test_bmap_entry)
 169 {
 170   int i = 0;
 171   int start = 0;
 172   int64_t scanned = 0;
 173   int64_t allocated = 0;
 174   int size = BmapEntry::size();
 175
 176   BmapEntry *bmap = new BmapEntry(g_ceph_context, true);
 177
 178   // Clear bits one by one and check they are cleared
 179   for (i = 0; i < size; i++) {
 180     bmap->clear_bit(i);
 181     bmap_test_assert(!bmap->check_bit(i));
 182   }
 183
 184   // Set all bits again using set_bits
 185   bmap->set_bits(0, size);
 186
 187   // clear 4 bits at a time and then check allocated
 188   for (i = 0; i < size/4; i++) {
 189     bmap->clear_bits(i * 4, 4);
 190     bmap_test_assert(!bmap->is_allocated(i * 4, 4));
 191   }
 192
 193   // set all bits again
 194   bmap->set_bits(0, size);
 195
 196   // clear alternate bits, check and set those bits
 197   for (i = 0; i < size/2; i++) {
 198     bmap->clear_bit(i * 2 + 1);
 199     bmap_test_assert(!bmap->check_bit(i * 2 + 1));
 200     bmap_test_assert(bmap->check_n_set_bit(i * 2 + 1));
 201   }
 202
 203   // free 1, 2 and size bits at a time and try to find n cont bits
 204   for (i = 0; i < size / 4; i++) {
 205     bmap->clear_bits(i * 2 + 1, i + 1);
 206     bmap_test_assert(!bmap->check_bit(i * 2 + 1));
 207     bmap_test_assert(bmap->find_n_cont_bits(i * 2 + 1, i + 1) ==
 208         i + 1);
 209   }
 210
 211   // free 1, 2 and size bits at a time and try to find any cont bits
 212   for (i = 0; i < size / 4; i++) {
 213     bmap->clear_bits(i * 2 + 1, i + 1);
 214     bmap_test_assert(!bmap->is_allocated(i * 2 + 1, i + 1));
 215   }
 216
 217   for (i = 0; i < size / 4; i++) {
 218     bmap->clear_bits(i * 2 + 1, i + 1);
 219     allocated = bmap->find_first_set_bits(i + 1, 0, &start, &scanned);
 220
 221     bmap_test_assert(allocated == i + 1);
 222     bmap_test_assert(scanned == ((i * 2 + 1) + (i + 1)));
 223     bmap_test_assert(start == i * 2 + 1);
 224     bmap->set_bits(0, BmapEntry::size());
 225
 226   }
 227
 228
 229
 230   // Find few bits at end of bitmap and find those
 231   bmap->clear_bits(0, 4);
 232   bmap->clear_bits(BmapEntry::size() - 12, 5);
 233   bmap->clear_bits(BmapEntry::size() - 6, 6);
 234   allocated = bmap->find_first_set_bits(6, 0, &start, &scanned);
 235
 236   bmap_test_assert(allocated == 6);
 237   bmap_test_assert(scanned == BmapEntry::size() - 6 + 6);
 238   bmap_test_assert(start == BmapEntry::size() - 6);
 239   bmap_test_assert(bmap->is_allocated(start, 6));
 240
 241   delete bmap;
 242
 243   {
 244
 245     bmap = new BmapEntry(g_ceph_context, false);
 246     start = -1;
 247     scanned = 0;
 248     allocated = 0;
 249     allocated = bmap->find_first_set_bits(1, 1, &start, &scanned);
 250     bmap_test_assert(allocated == 1);
 251     bmap_test_assert(start == 1);
 252
 253     allocated = bmap->find_first_set_bits(1, BmapEntry::size() - 2, &start, &scanned);
 254     bmap_test_assert(allocated == 1);
 255     bmap_test_assert(start == BmapEntry::size() - 2);
 256
 257     bmap->clear_bits(0, BmapEntry::size());
 258     bmap->set_bits(0, BmapEntry::size() / 4);
 259     allocated = bmap->find_first_set_bits(4, 2, &start, &scanned);
 260     bmap_test_assert(allocated == 4);
 261     bmap_test_assert(start == BmapEntry::size() / 4);
 262     delete bmap;
 263   }
 264
 265   bmap = new BmapEntry(g_ceph_context, false);
 266   bmap->set_bits(4, BmapEntry::size() - 4);
 267   bmap_test_assert(bmap->is_allocated(4, BmapEntry::size() - 4));
 268   bmap_test_assert(!bmap->is_allocated(0, 4));
 269   bmap->set_bits(0, 4);
 270   bmap_test_assert(bmap->is_allocated(0, BmapEntry::size()));
 271   delete bmap;
 272
 273 }
 274
 275 TEST(BitAllocator, test_zone_alloc)
 276 {
 277   int total_blocks = 1024;
 278   int64_t allocated = 0;
 279
 280   BitMapZone *zone = new BitMapZone(g_ceph_context, total_blocks, 0);
 281
 282   // Allocate all blocks and see that it is allocating in order.
 283   bool lock = zone->lock_excl_try();
 284   bmap_test_assert(lock);
 285
 286   int64_t blk_size = 1024;
 287   AllocExtentVector extents;
 288   ExtentList *block_list = new ExtentList(&extents, blk_size);
 289   allocated = zone->alloc_blocks_dis(zone->size() / 2, 1, 0, 0, block_list);
 290   bmap_test_assert(allocated == zone->size() / 2);
 291
 292
 293   {
 294     int64_t blk_size = 1024;
 295     AllocExtentVector extents;
 296     ExtentList *block_list = new ExtentList(&extents, blk_size);
 297
 298     zone = new BitMapZone(g_ceph_context, total_blocks, 0);
 299     lock = zone->lock_excl_try();
 300     bmap_test_assert(lock);
 301     for (int i = 0; i < zone->size(); i += 4) {
 302       block_list->reset();
 303       allocated = zone->alloc_blocks_dis(1, 1, i, 0, block_list);
 304       bmap_test_assert(allocated == 1);
 305       EXPECT_EQ(extents[0].offset, (uint64_t) i * blk_size);
 306     }
 307
 308     for (int i = 0; i < zone->size(); i += 4) {
 309       zone->free_blocks(i, 1);
 310     }
 311   }
 312
 313   /*
 314    * Min alloc size cases.
 315    */
 316   {
 317     int64_t blk_size = 1;
 318     AllocExtentVector extents;
 319
 320     for (int i = 1; i <= total_blocks - BmapEntry::size(); i = i << 1) {
 321       for (int64_t j = 0; j <= BmapEntry::size(); j = 1 << j) {
 322         extents.clear();
 323         ExtentList *block_list = new ExtentList(&extents, blk_size);
 324         zone = new BitMapZone(g_ceph_context, total_blocks, 0);
 325         lock = zone->lock_excl_try();
 326         bmap_test_assert(lock);
 327
 328         block_list->reset();
 329         int64_t need_blks = (((total_blocks - j) / i) * i);
 330         allocated = zone->alloc_blocks_dis(need_blks, i, j, 0, block_list);
 331         bmap_test_assert(allocated == need_blks);
 332         bmap_test_assert(extents[0].offset ==  (uint64_t) j);
 333         delete block_list;
 334         delete zone;
 335       }
 336     }
 337
 338     //allocation in loop
 339     {
 340       extents.clear();
 341       ExtentList *block_list = new ExtentList(&extents, blk_size);
 342       zone = new BitMapZone(g_ceph_context, total_blocks, 0);
 343       lock = zone->lock_excl_try();
 344
 345       for (int iter = 1; iter < 5; iter++) {
 346         for (int i = 1; i <= total_blocks; i = i << 1) {
 347           for (int j = 0; j < total_blocks; j +=i) {
 348             bmap_test_assert(lock);
 349             block_list->reset();
 350             int64_t need_blks = i;
 351             allocated = zone->alloc_blocks_dis(need_blks, i, 0, 0, block_list);
 352             bmap_test_assert(allocated == need_blks);
 353             bmap_test_assert(extents[0].offset ==  (uint64_t) j);
 354             block_list->reset();
 355           }
 356           {
 357             allocated = zone->alloc_blocks_dis(1, 1, 0, 0, block_list);
 358             bmap_test_assert(allocated == 0);
 359             block_list->reset();
 360           }
 361
 362           for (int j = 0; j < total_blocks; j +=i) {
 363             zone->free_blocks(j, i);
 364           }
 365         }
 366       }
 367       delete block_list;
 368       delete zone;
 369     }
 370
 371     {
 372       extents.clear();
 373       ExtentList *block_list = new ExtentList(&extents, blk_size);
 374       zone = new BitMapZone(g_ceph_context, total_blocks, 0);
 375       lock = zone->lock_excl_try();
 376       bmap_test_assert(lock);
 377
 378       block_list->reset();
 379       allocated = zone->alloc_blocks_dis(total_blocks + 1, total_blocks + 1, 0, 1024, block_list);
 380       bmap_test_assert(allocated == 0);
 381
 382       block_list->reset();
 383       allocated = zone->alloc_blocks_dis(total_blocks, total_blocks, 1, 1024, block_list);
 384       bmap_test_assert(allocated == 0);
 385
 386       block_list->reset();
 387       allocated = zone->alloc_blocks_dis(total_blocks, total_blocks, 0, 0, block_list);
 388       bmap_test_assert(allocated == total_blocks);
 389       bmap_test_assert(extents[0].offset == 0);
 390
 391       zone->free_blocks(extents[0].offset, allocated);
 392
 393       delete block_list;
 394       extents.clear();
 395       block_list = new ExtentList(&extents, blk_size, total_blocks / 4 * blk_size);
 396       allocated = zone->alloc_blocks_dis(total_blocks, total_blocks / 4, 0, 0, block_list);
 397       bmap_test_assert(allocated == total_blocks);
 398       for (int i = 0; i < 4; i++) {
 399         bmap_test_assert(extents[i].offset == (uint64_t) i * (total_blocks / 4));
 400       }
 401     }
 402   }
 403 }
 404
 405 TEST(BitAllocator, test_bmap_alloc)
 406 {
 407   const int max_iter = 3;
 408
 409   for (int round = 0; round < 3; round++) {
 410     // Test zone of different sizes: 512, 1024, 2048
 411     int64_t zone_size = 512ull << round;
 412     ostringstream val;
 413     val << zone_size;
 414     g_conf->set_val("bluestore_bitmapallocator_blocks_per_zone", val.str());
 415
 416     // choose randomized span_size
 417     int64_t span_size = 512ull << (rand() % 4);
 418     val.str("");
 419     val << span_size;
 420     g_conf->set_val("bluestore_bitmapallocator_span_size", val.str());
 421     g_ceph_context->_conf->apply_changes(NULL);
 422
 423     int64_t total_blocks = zone_size * 4;
 424     int64_t allocated = 0;
 425
 426     BitAllocator *alloc = new BitAllocator(g_ceph_context, total_blocks,
 427                                            zone_size, CONCURRENT);
 428     int64_t alloc_size = 2;
 429     for (int64_t iter = 0; iter < max_iter; iter++) {
 430       for (int64_t j = 0; alloc_size <= total_blocks; j++) {
 431         int64_t blk_size = 1024;
 432         AllocExtentVector extents;
 433         ExtentList *block_list = new ExtentList(&extents, blk_size, alloc_size);
 434         for (int64_t i = 0; i < total_blocks; i += alloc_size) {
 435           bmap_test_assert(alloc->reserve_blocks(alloc_size) == true);
 436           allocated = alloc->alloc_blocks_dis_res(alloc_size, MIN(alloc_size, zone_size),
 437                                                   0, block_list);
 438           bmap_test_assert(alloc_size == allocated);
 439           bmap_test_assert(block_list->get_extent_count() ==
 440                            (alloc_size > zone_size? alloc_size / zone_size: 1));
 441           bmap_test_assert(extents[0].offset == (uint64_t) i * blk_size);
 442           bmap_test_assert((int64_t) extents[0].length ==
 443                            ((alloc_size > zone_size? zone_size: alloc_size) * blk_size));
 444           block_list->reset();
 445         }
 446         for (int64_t i = 0; i < total_blocks; i += alloc_size) {
 447           alloc->free_blocks(i, alloc_size);
 448         }
 449         alloc_size = 2 << j;
 450       }
 451     }
 452
 453     int64_t blk_size = 1024;
 454     AllocExtentVector extents;
 455
 456     ExtentList *block_list = new ExtentList(&extents, blk_size);
 457
 458     ASSERT_EQ(alloc->reserve_blocks(alloc->size() / 2), true);
 459     allocated = alloc->alloc_blocks_dis_res(alloc->size()/2, 1, 0, block_list);
 460     ASSERT_EQ(alloc->size()/2, allocated);
 461
 462     block_list->reset();
 463     ASSERT_EQ(alloc->reserve_blocks(1), true);
 464     allocated = alloc->alloc_blocks_dis_res(1, 1, 0, block_list);
 465     bmap_test_assert(allocated == 1);
 466
 467     alloc->free_blocks(alloc->size()/2, 1);
 468
 469     block_list->reset();
 470     ASSERT_EQ(alloc->reserve_blocks(1), true);
 471     allocated = alloc->alloc_blocks_dis_res(1, 1, 0, block_list);
 472     bmap_test_assert(allocated == 1);
 473
 474     bmap_test_assert((int64_t) extents[0].offset == alloc->size()/2 * blk_size);
 475
 476     delete block_list;
 477     delete alloc;
 478
 479   }
 480
 481   // restore to typical value
 482   g_conf->set_val("bluestore_bitmapallocator_blocks_per_zone", "1024");
 483   g_conf->set_val("bluestore_bitmapallocator_span_size", "1024");
 484   g_ceph_context->_conf->apply_changes(NULL);
 485 }
 486
 487 bool alloc_extents_max_block(BitAllocator *alloc,
 488            int64_t max_alloc,
 489            int64_t total_alloc)
 490 {
 491   int64_t blk_size = 1;
 492   int64_t allocated = 0;
 493   int64_t verified = 0;
 494   int64_t count = 0;
 495   AllocExtentVector extents;
 496
 497   ExtentList *block_list = new ExtentList(&extents, blk_size, max_alloc);
 498
 499   EXPECT_EQ(alloc->reserve_blocks(total_alloc), true);
 500   allocated = alloc->alloc_blocks_dis_res(total_alloc, blk_size, 0, block_list);
 501   EXPECT_EQ(allocated, total_alloc);
 502
 503   max_alloc = total_alloc > max_alloc? max_alloc: total_alloc;
 504
 505   for (auto &p: extents) {
 506     count++;
 507     EXPECT_EQ(p.length,  max_alloc);
 508     verified += p.length;
 509     if (verified >= total_alloc) {
 510       break;
 511     }
 512   }
 513
 514   EXPECT_EQ(total_alloc / max_alloc, count);
 515   return true;
 516 }
 517
 518 TEST(BitAllocator, test_bmap_alloc2)
 519 {
 520   int64_t total_blocks = 1024 * 4;
 521   int64_t zone_size = 1024;
 522   BitAllocator *alloc = new BitAllocator(g_ceph_context, total_blocks,
 523                                          zone_size, CONCURRENT);
 524
 525   alloc_extents_max_block(alloc, 1, 16);
 526   alloc_extents_max_block(alloc, 4, 16);
 527   alloc_extents_max_block(alloc, 16, 16);
 528   alloc_extents_max_block(alloc, 32, 16);
 529 }
 530
 531 __thread int my_tid;
 532
 533 void
 534 do_work_dis(BitAllocator *alloc)
 535 {
 536   int num_iters = 10;
 537   int64_t alloced = 0;
 538   int64_t num_blocks = alloc->size() / NUM_THREADS;
 539
 540   AllocExtentVector extents;
 541   ExtentList *block_list = new ExtentList(&extents, 4096);
 542
 543   while (num_iters--) {
 544     alloc_assert(alloc->reserve_blocks(num_blocks));
 545     alloced = alloc->alloc_blocks_dis_res(num_blocks, 1, 0, block_list);
 546     alloc_assert(alloced == num_blocks);
 547
 548     alloc_assert(alloc->is_allocated_dis(block_list, num_blocks));
 549     alloc->free_blocks_dis(num_blocks, block_list);
 550     block_list->reset();
 551   }
 552 }
 553
 554 int tid = 0;
 555 static bool cont = true;
 556
 557 void *
 558 worker(void *args)
 559 {
 560   my_tid = __sync_fetch_and_add(&tid, 1);
 561   BitAllocator *alloc = (BitAllocator *) args;
 562   printf("Starting thread %d", my_tid);
 563   do_work_dis(alloc);
 564
 565   return NULL;
 566 }
 567
 568 TEST(BitAllocator, test_bmap_alloc_concurrent)
 569 {
 570   int64_t total_blocks = MAX_BLOCKS;
 571   int64_t zone_size = 1024;
 572   pthread_t pthreads[NUM_THREADS] = {0};
 573
 574   bmap_test_assert(total_blocks <= MAX_BLOCKS);
 575
 576   BitAllocator *alloc = new BitAllocator(g_ceph_context, total_blocks,
 577                                          zone_size, CONCURRENT);
 578
 579   for (int k = 0; k < 2; k++) {
 580     cont = k;
 581     printf("Spawning %d threads for parallel test. Mode Cont = %d.....\n", NUM_THREADS, cont);
 582     for (int j = 0; j < NUM_THREADS; j++) {
 583       if (pthread_create(&pthreads[j], NULL, worker, alloc)) {
 584         printf("Unable to create worker thread.\n");
 585         exit(0);
 586       }
 587     }
 588
 589     for (int j = 0; j < NUM_THREADS; j++) {
 590       pthread_join(pthreads[j], NULL);
 591     }
 592   }
 593 }