--- /dev/null
+// -*- 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 <stdio.h>
+#include <assert.h>
+#include <math.h>
+#include <sstream>
+#include <gtest/gtest.h>
+
+
+//#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<BmapEntityTmp> *arr = new mempool::bluestore_alloc::vector<BmapEntityTmp>(num_items);
+ for (i = 0; i < num_items; i++) {
+ (*arr)[i].init(i);
+ }
+ BitMapEntityIter<BmapEntityTmp> iter = BitMapEntityIter<BmapEntityTmp>(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<BmapEntityTmp>(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<BmapEntityTmp>(num_items);
+ for (i = 0; i < num_items; i++) {
+ (*arr)[i].init(i);
+ }
+ iter = BitMapEntityIter<BmapEntityTmp>(arr, off, true);
+ i = off;
+ last_idx = off;
+ count = 0;
+ while ((obj = static_cast<BmapEntityTmp*>(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<BitMapArea*> 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<BitMapArea*>(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);
+ }
+ }
+}
Code Review / stor4nfv.git / blobdiff