X-Git-Url: https://gerrit.opnfv.org/gerrit/gitweb?a=blobdiff_plain;f=src%2Fceph%2Fsrc%2Ftest%2Fobjectstore%2FBitAllocator_test.cc;fp=src%2Fceph%2Fsrc%2Ftest%2Fobjectstore%2FBitAllocator_test.cc;h=5d1da96a016addee55895c7900c466d303556ac0;hb=812ff6ca9fcd3e629e49d4328905f33eee8ca3f5;hp=0000000000000000000000000000000000000000;hpb=15280273faafb77777eab341909a3f495cf248d9;p=stor4nfv.git diff --git a/src/ceph/src/test/objectstore/BitAllocator_test.cc b/src/ceph/src/test/objectstore/BitAllocator_test.cc new file mode 100644 index 0000000..5d1da96 --- /dev/null +++ b/src/ceph/src/test/objectstore/BitAllocator_test.cc @@ -0,0 +1,593 @@ +// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- +// vim: ts=8 sw=2 smarttab +/* + * Bitmap based in-memory allocator unit test cases. + * Author: Ramesh Chander, Ramesh.Chander@sandisk.com + */ + +#include "include/Context.h" +#include "os/bluestore/BitAllocator.h" +#include +#include +#include +#include +#include + + +//#define bmap_test_assert(x) ASSERT_EQ(true, (x)) +#define bmap_test_assert(x) assert((x)) +#define NUM_THREADS 16 +#define MAX_BLOCKS (1024 * 1024 * 1) + +TEST(BitAllocator, test_bmap_iter) +{ + int num_items = 5; + int off = 2; + + class BmapEntityTmp { + int64_t m_num; + int64_t m_len; + public: + void init(int index) { + m_num = index; + } + BmapEntityTmp() { + + } + BmapEntityTmp(int num) { + m_num = num; + m_len = num; + } + + int64_t get_index() { + return m_num; + } + bool is_allocated(int64_t s, int64_t num) + { + return true; + } + }; + BmapEntityTmp *obj = NULL; + int i = 0; + mempool::bluestore_alloc::vector *arr = new mempool::bluestore_alloc::vector(num_items); + for (i = 0; i < num_items; i++) { + (*arr)[i].init(i); + } + BitMapEntityIter iter = BitMapEntityIter(arr, off, false); + + i = off; + int count = 0; + int64_t last_idx = off; + while ((obj = iter.next())) { + bmap_test_assert(obj->get_index() == last_idx); + bmap_test_assert(obj->get_index() == i); + bmap_test_assert(obj == &(*arr)[i]); + last_idx = iter.index(); + i++; + count++; + } + bmap_test_assert(i == num_items); + bmap_test_assert(count == num_items - off); + + iter = BitMapEntityIter(arr, off, true); + + i = off; + last_idx = off; + count = 0; + while ((obj = iter.next())) { + bmap_test_assert(obj->get_index() == last_idx); + bmap_test_assert(obj->get_index() == i); + bmap_test_assert(obj == &(*arr)[i]); + last_idx = iter.index(); + + i = (i + 1) % num_items; + count++; + } + bmap_test_assert(i == off + 1); + bmap_test_assert(count == num_items + 1); + + delete arr; + + num_items = 4; + off = num_items - 1; + + arr = new mempool::bluestore_alloc::vector(num_items); + for (i = 0; i < num_items; i++) { + (*arr)[i].init(i); + } + iter = BitMapEntityIter(arr, off, true); + i = off; + last_idx = off; + count = 0; + while ((obj = static_cast(iter.next()))) { + bmap_test_assert(obj->get_index() == last_idx); + bmap_test_assert(obj->get_index() == i); + bmap_test_assert(obj == &(*arr)[i]); + last_idx = iter.index(); + i = (i + 1) % num_items; + count++; + } + bmap_test_assert(i == (off + 1)%num_items); + bmap_test_assert(count == num_items + 1); + + delete arr; + + /* + * BitMapArea Iter tests. + */ + BitMapArea *area = nullptr; + std::vector children; + children.reserve(num_items); + for (i = 0; i < num_items; i++) { + children.emplace_back(new BitMapAreaLeaf( + g_ceph_context, + BitMapArea::get_span_size(g_ceph_context), i, false)); + } + + off = 0; + BitMapAreaList *area_list = \ + new BitMapAreaList(std::vector(children)); + BmapEntityListIter area_iter = BmapEntityListIter( + area_list, (int64_t) 0); + i = off; + last_idx = off; + count = 0; + while ((area = area_iter.next())) { + bmap_test_assert(area->get_index() == last_idx); + bmap_test_assert(area->get_index() == i); + bmap_test_assert(area == children[i]); + last_idx = area_iter.index(); + i = (i + 1) % num_items; + count++; + } + bmap_test_assert(i == off); + bmap_test_assert(count == num_items); + + off = 0; + area_iter = BmapEntityListIter(area_list, off, true); + i = off; + last_idx = off; + count = 0; + while ((area = area_iter.next())) { + bmap_test_assert(area->get_index() == last_idx); + bmap_test_assert(area->get_index() == i); + bmap_test_assert(area == children[i]); + last_idx = area_iter.index(); + i = (i + 1) % num_items; + count++; + } + bmap_test_assert(i == (off + 1)%num_items); + bmap_test_assert(count == num_items + 1); + + for (i = 0; i < num_items; i++) + delete children[i]; + + delete area_list; +} + +TEST(BitAllocator, test_bmap_entry) +{ + int i = 0; + int start = 0; + int64_t scanned = 0; + int64_t allocated = 0; + int size = BmapEntry::size(); + + BmapEntry *bmap = new BmapEntry(g_ceph_context, true); + + // Clear bits one by one and check they are cleared + for (i = 0; i < size; i++) { + bmap->clear_bit(i); + bmap_test_assert(!bmap->check_bit(i)); + } + + // Set all bits again using set_bits + bmap->set_bits(0, size); + + // clear 4 bits at a time and then check allocated + for (i = 0; i < size/4; i++) { + bmap->clear_bits(i * 4, 4); + bmap_test_assert(!bmap->is_allocated(i * 4, 4)); + } + + // set all bits again + bmap->set_bits(0, size); + + // clear alternate bits, check and set those bits + for (i = 0; i < size/2; i++) { + bmap->clear_bit(i * 2 + 1); + bmap_test_assert(!bmap->check_bit(i * 2 + 1)); + bmap_test_assert(bmap->check_n_set_bit(i * 2 + 1)); + } + + // free 1, 2 and size bits at a time and try to find n cont bits + for (i = 0; i < size / 4; i++) { + bmap->clear_bits(i * 2 + 1, i + 1); + bmap_test_assert(!bmap->check_bit(i * 2 + 1)); + bmap_test_assert(bmap->find_n_cont_bits(i * 2 + 1, i + 1) == + i + 1); + } + + // free 1, 2 and size bits at a time and try to find any cont bits + for (i = 0; i < size / 4; i++) { + bmap->clear_bits(i * 2 + 1, i + 1); + bmap_test_assert(!bmap->is_allocated(i * 2 + 1, i + 1)); + } + + for (i = 0; i < size / 4; i++) { + bmap->clear_bits(i * 2 + 1, i + 1); + allocated = bmap->find_first_set_bits(i + 1, 0, &start, &scanned); + + bmap_test_assert(allocated == i + 1); + bmap_test_assert(scanned == ((i * 2 + 1) + (i + 1))); + bmap_test_assert(start == i * 2 + 1); + bmap->set_bits(0, BmapEntry::size()); + + } + + + + // Find few bits at end of bitmap and find those + bmap->clear_bits(0, 4); + bmap->clear_bits(BmapEntry::size() - 12, 5); + bmap->clear_bits(BmapEntry::size() - 6, 6); + allocated = bmap->find_first_set_bits(6, 0, &start, &scanned); + + bmap_test_assert(allocated == 6); + bmap_test_assert(scanned == BmapEntry::size() - 6 + 6); + bmap_test_assert(start == BmapEntry::size() - 6); + bmap_test_assert(bmap->is_allocated(start, 6)); + + delete bmap; + + { + + bmap = new BmapEntry(g_ceph_context, false); + start = -1; + scanned = 0; + allocated = 0; + allocated = bmap->find_first_set_bits(1, 1, &start, &scanned); + bmap_test_assert(allocated == 1); + bmap_test_assert(start == 1); + + allocated = bmap->find_first_set_bits(1, BmapEntry::size() - 2, &start, &scanned); + bmap_test_assert(allocated == 1); + bmap_test_assert(start == BmapEntry::size() - 2); + + bmap->clear_bits(0, BmapEntry::size()); + bmap->set_bits(0, BmapEntry::size() / 4); + allocated = bmap->find_first_set_bits(4, 2, &start, &scanned); + bmap_test_assert(allocated == 4); + bmap_test_assert(start == BmapEntry::size() / 4); + delete bmap; + } + + bmap = new BmapEntry(g_ceph_context, false); + bmap->set_bits(4, BmapEntry::size() - 4); + bmap_test_assert(bmap->is_allocated(4, BmapEntry::size() - 4)); + bmap_test_assert(!bmap->is_allocated(0, 4)); + bmap->set_bits(0, 4); + bmap_test_assert(bmap->is_allocated(0, BmapEntry::size())); + delete bmap; + +} + +TEST(BitAllocator, test_zone_alloc) +{ + int total_blocks = 1024; + int64_t allocated = 0; + + BitMapZone *zone = new BitMapZone(g_ceph_context, total_blocks, 0); + + // Allocate all blocks and see that it is allocating in order. + bool lock = zone->lock_excl_try(); + bmap_test_assert(lock); + + int64_t blk_size = 1024; + AllocExtentVector extents; + ExtentList *block_list = new ExtentList(&extents, blk_size); + allocated = zone->alloc_blocks_dis(zone->size() / 2, 1, 0, 0, block_list); + bmap_test_assert(allocated == zone->size() / 2); + + + { + int64_t blk_size = 1024; + AllocExtentVector extents; + ExtentList *block_list = new ExtentList(&extents, blk_size); + + zone = new BitMapZone(g_ceph_context, total_blocks, 0); + lock = zone->lock_excl_try(); + bmap_test_assert(lock); + for (int i = 0; i < zone->size(); i += 4) { + block_list->reset(); + allocated = zone->alloc_blocks_dis(1, 1, i, 0, block_list); + bmap_test_assert(allocated == 1); + EXPECT_EQ(extents[0].offset, (uint64_t) i * blk_size); + } + + for (int i = 0; i < zone->size(); i += 4) { + zone->free_blocks(i, 1); + } + } + + /* + * Min alloc size cases. + */ + { + int64_t blk_size = 1; + AllocExtentVector extents; + + for (int i = 1; i <= total_blocks - BmapEntry::size(); i = i << 1) { + for (int64_t j = 0; j <= BmapEntry::size(); j = 1 << j) { + extents.clear(); + ExtentList *block_list = new ExtentList(&extents, blk_size); + zone = new BitMapZone(g_ceph_context, total_blocks, 0); + lock = zone->lock_excl_try(); + bmap_test_assert(lock); + + block_list->reset(); + int64_t need_blks = (((total_blocks - j) / i) * i); + allocated = zone->alloc_blocks_dis(need_blks, i, j, 0, block_list); + bmap_test_assert(allocated == need_blks); + bmap_test_assert(extents[0].offset == (uint64_t) j); + delete block_list; + delete zone; + } + } + + //allocation in loop + { + extents.clear(); + ExtentList *block_list = new ExtentList(&extents, blk_size); + zone = new BitMapZone(g_ceph_context, total_blocks, 0); + lock = zone->lock_excl_try(); + + for (int iter = 1; iter < 5; iter++) { + for (int i = 1; i <= total_blocks; i = i << 1) { + for (int j = 0; j < total_blocks; j +=i) { + bmap_test_assert(lock); + block_list->reset(); + int64_t need_blks = i; + allocated = zone->alloc_blocks_dis(need_blks, i, 0, 0, block_list); + bmap_test_assert(allocated == need_blks); + bmap_test_assert(extents[0].offset == (uint64_t) j); + block_list->reset(); + } + { + allocated = zone->alloc_blocks_dis(1, 1, 0, 0, block_list); + bmap_test_assert(allocated == 0); + block_list->reset(); + } + + for (int j = 0; j < total_blocks; j +=i) { + zone->free_blocks(j, i); + } + } + } + delete block_list; + delete zone; + } + + { + extents.clear(); + ExtentList *block_list = new ExtentList(&extents, blk_size); + zone = new BitMapZone(g_ceph_context, total_blocks, 0); + lock = zone->lock_excl_try(); + bmap_test_assert(lock); + + block_list->reset(); + allocated = zone->alloc_blocks_dis(total_blocks + 1, total_blocks + 1, 0, 1024, block_list); + bmap_test_assert(allocated == 0); + + block_list->reset(); + allocated = zone->alloc_blocks_dis(total_blocks, total_blocks, 1, 1024, block_list); + bmap_test_assert(allocated == 0); + + block_list->reset(); + allocated = zone->alloc_blocks_dis(total_blocks, total_blocks, 0, 0, block_list); + bmap_test_assert(allocated == total_blocks); + bmap_test_assert(extents[0].offset == 0); + + zone->free_blocks(extents[0].offset, allocated); + + delete block_list; + extents.clear(); + block_list = new ExtentList(&extents, blk_size, total_blocks / 4 * blk_size); + allocated = zone->alloc_blocks_dis(total_blocks, total_blocks / 4, 0, 0, block_list); + bmap_test_assert(allocated == total_blocks); + for (int i = 0; i < 4; i++) { + bmap_test_assert(extents[i].offset == (uint64_t) i * (total_blocks / 4)); + } + } + } +} + +TEST(BitAllocator, test_bmap_alloc) +{ + const int max_iter = 3; + + for (int round = 0; round < 3; round++) { + // Test zone of different sizes: 512, 1024, 2048 + int64_t zone_size = 512ull << round; + ostringstream val; + val << zone_size; + g_conf->set_val("bluestore_bitmapallocator_blocks_per_zone", val.str()); + + // choose randomized span_size + int64_t span_size = 512ull << (rand() % 4); + val.str(""); + val << span_size; + g_conf->set_val("bluestore_bitmapallocator_span_size", val.str()); + g_ceph_context->_conf->apply_changes(NULL); + + int64_t total_blocks = zone_size * 4; + int64_t allocated = 0; + + BitAllocator *alloc = new BitAllocator(g_ceph_context, total_blocks, + zone_size, CONCURRENT); + int64_t alloc_size = 2; + for (int64_t iter = 0; iter < max_iter; iter++) { + for (int64_t j = 0; alloc_size <= total_blocks; j++) { + int64_t blk_size = 1024; + AllocExtentVector extents; + ExtentList *block_list = new ExtentList(&extents, blk_size, alloc_size); + for (int64_t i = 0; i < total_blocks; i += alloc_size) { + bmap_test_assert(alloc->reserve_blocks(alloc_size) == true); + allocated = alloc->alloc_blocks_dis_res(alloc_size, MIN(alloc_size, zone_size), + 0, block_list); + bmap_test_assert(alloc_size == allocated); + bmap_test_assert(block_list->get_extent_count() == + (alloc_size > zone_size? alloc_size / zone_size: 1)); + bmap_test_assert(extents[0].offset == (uint64_t) i * blk_size); + bmap_test_assert((int64_t) extents[0].length == + ((alloc_size > zone_size? zone_size: alloc_size) * blk_size)); + block_list->reset(); + } + for (int64_t i = 0; i < total_blocks; i += alloc_size) { + alloc->free_blocks(i, alloc_size); + } + alloc_size = 2 << j; + } + } + + int64_t blk_size = 1024; + AllocExtentVector extents; + + ExtentList *block_list = new ExtentList(&extents, blk_size); + + ASSERT_EQ(alloc->reserve_blocks(alloc->size() / 2), true); + allocated = alloc->alloc_blocks_dis_res(alloc->size()/2, 1, 0, block_list); + ASSERT_EQ(alloc->size()/2, allocated); + + block_list->reset(); + ASSERT_EQ(alloc->reserve_blocks(1), true); + allocated = alloc->alloc_blocks_dis_res(1, 1, 0, block_list); + bmap_test_assert(allocated == 1); + + alloc->free_blocks(alloc->size()/2, 1); + + block_list->reset(); + ASSERT_EQ(alloc->reserve_blocks(1), true); + allocated = alloc->alloc_blocks_dis_res(1, 1, 0, block_list); + bmap_test_assert(allocated == 1); + + bmap_test_assert((int64_t) extents[0].offset == alloc->size()/2 * blk_size); + + delete block_list; + delete alloc; + + } + + // restore to typical value + g_conf->set_val("bluestore_bitmapallocator_blocks_per_zone", "1024"); + g_conf->set_val("bluestore_bitmapallocator_span_size", "1024"); + g_ceph_context->_conf->apply_changes(NULL); +} + +bool alloc_extents_max_block(BitAllocator *alloc, + int64_t max_alloc, + int64_t total_alloc) +{ + int64_t blk_size = 1; + int64_t allocated = 0; + int64_t verified = 0; + int64_t count = 0; + AllocExtentVector extents; + + ExtentList *block_list = new ExtentList(&extents, blk_size, max_alloc); + + EXPECT_EQ(alloc->reserve_blocks(total_alloc), true); + allocated = alloc->alloc_blocks_dis_res(total_alloc, blk_size, 0, block_list); + EXPECT_EQ(allocated, total_alloc); + + max_alloc = total_alloc > max_alloc? max_alloc: total_alloc; + + for (auto &p: extents) { + count++; + EXPECT_EQ(p.length, max_alloc); + verified += p.length; + if (verified >= total_alloc) { + break; + } + } + + EXPECT_EQ(total_alloc / max_alloc, count); + return true; +} + +TEST(BitAllocator, test_bmap_alloc2) +{ + int64_t total_blocks = 1024 * 4; + int64_t zone_size = 1024; + BitAllocator *alloc = new BitAllocator(g_ceph_context, total_blocks, + zone_size, CONCURRENT); + + alloc_extents_max_block(alloc, 1, 16); + alloc_extents_max_block(alloc, 4, 16); + alloc_extents_max_block(alloc, 16, 16); + alloc_extents_max_block(alloc, 32, 16); +} + +__thread int my_tid; + +void +do_work_dis(BitAllocator *alloc) +{ + int num_iters = 10; + int64_t alloced = 0; + int64_t num_blocks = alloc->size() / NUM_THREADS; + + AllocExtentVector extents; + ExtentList *block_list = new ExtentList(&extents, 4096); + + while (num_iters--) { + alloc_assert(alloc->reserve_blocks(num_blocks)); + alloced = alloc->alloc_blocks_dis_res(num_blocks, 1, 0, block_list); + alloc_assert(alloced == num_blocks); + + alloc_assert(alloc->is_allocated_dis(block_list, num_blocks)); + alloc->free_blocks_dis(num_blocks, block_list); + block_list->reset(); + } +} + +int tid = 0; +static bool cont = true; + +void * +worker(void *args) +{ + my_tid = __sync_fetch_and_add(&tid, 1); + BitAllocator *alloc = (BitAllocator *) args; + printf("Starting thread %d", my_tid); + do_work_dis(alloc); + + return NULL; +} + +TEST(BitAllocator, test_bmap_alloc_concurrent) +{ + int64_t total_blocks = MAX_BLOCKS; + int64_t zone_size = 1024; + pthread_t pthreads[NUM_THREADS] = {0}; + + bmap_test_assert(total_blocks <= MAX_BLOCKS); + + BitAllocator *alloc = new BitAllocator(g_ceph_context, total_blocks, + zone_size, CONCURRENT); + + for (int k = 0; k < 2; k++) { + cont = k; + printf("Spawning %d threads for parallel test. Mode Cont = %d.....\n", NUM_THREADS, cont); + for (int j = 0; j < NUM_THREADS; j++) { + if (pthread_create(&pthreads[j], NULL, worker, alloc)) { + printf("Unable to create worker thread.\n"); + exit(0); + } + } + + for (int j = 0; j < NUM_THREADS; j++) { + pthread_join(pthreads[j], NULL); + } + } +}