From 3afa6cc3d0ddeab6325568150dd0031cbcea1474 Mon Sep 17 00:00:00 2001 From: Igor Fedotov Date: Mon, 14 May 2018 16:09:22 +0300 Subject: [PATCH] os/bluestore: remove original bitmap allocator Signed-off-by: Igor Fedotov (cherry picked from commit 95bd72fc22aa313112de096ac3ef98e45c71bce5) --- src/os/CMakeLists.txt | 2 - src/os/bluestore/Allocator.cc | 1 - src/os/bluestore/BitAllocator.cc | 1441 --------------------- src/os/bluestore/BitAllocator.h | 613 --------- src/os/bluestore/BitMapAllocator.cc | 226 ---- src/os/bluestore/BitMapAllocator.h | 47 - src/test/objectstore/BitAllocator_test.cc | 589 --------- src/test/objectstore/CMakeLists.txt | 8 - 8 files changed, 2927 deletions(-) delete mode 100644 src/os/bluestore/BitAllocator.cc delete mode 100644 src/os/bluestore/BitAllocator.h delete mode 100644 src/os/bluestore/BitMapAllocator.cc delete mode 100644 src/os/bluestore/BitMapAllocator.h delete mode 100644 src/test/objectstore/BitAllocator_test.cc diff --git a/src/os/CMakeLists.txt b/src/os/CMakeLists.txt index 886ac3bcba185..cd39ebad5897d 100644 --- a/src/os/CMakeLists.txt +++ b/src/os/CMakeLists.txt @@ -32,9 +32,7 @@ if(HAVE_LIBAIO) bluestore/FreelistManager.cc bluestore/KernelDevice.cc bluestore/StupidAllocator.cc - bluestore/BitMapAllocator.cc bluestore/BitmapFastAllocator.cc - bluestore/BitAllocator.cc bluestore/aio.cc ) endif(HAVE_LIBAIO) diff --git a/src/os/bluestore/Allocator.cc b/src/os/bluestore/Allocator.cc index d91568ef184f9..9b12301bac8cc 100644 --- a/src/os/bluestore/Allocator.cc +++ b/src/os/bluestore/Allocator.cc @@ -3,7 +3,6 @@ #include "Allocator.h" #include "StupidAllocator.h" -#include "BitMapAllocator.h" #include "BitmapFastAllocator.h" #include "common/debug.h" diff --git a/src/os/bluestore/BitAllocator.cc b/src/os/bluestore/BitAllocator.cc deleted file mode 100644 index aeec97924d275..0000000000000 --- a/src/os/bluestore/BitAllocator.cc +++ /dev/null @@ -1,1441 +0,0 @@ -// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- - -// vim: ts=8 sw=2 smarttab -/* - * Bitmap based in-memory allocator. - * Author: Ramesh Chander, Ramesh.Chander@sandisk.com - * - * BitMap Tree Design: - * Storage is divided into bitmap of blocks. Each bitmap has size of - * unsigned long. Group of bitmap creates a Zone. Zone is a unit where - * at a time single thread can be active as well as single biggest - * contiguous allocation that can be requested. - * - * Rest of the nodes are classified into three categories: - * root node or Allocator - * internal nodes or BitMapAreaIN - * final nodes that contains Zones called BitMapAreaLeaf - * This classification is according to their own implmentation of some - * of the interfaces defined in BitMapArea. - */ - -#include "BitAllocator.h" -#include -#include "bluestore_types.h" -#include "common/debug.h" -#include - -#define dout_context cct -#define dout_subsys ceph_subsys_bluestore -#undef dout_prefix -#define dout_prefix *_dout << "bitalloc:" - -MEMPOOL_DEFINE_OBJECT_FACTORY(BitMapArea, BitMapArea, bluestore_alloc); -MEMPOOL_DEFINE_OBJECT_FACTORY(BitMapAreaIN, BitMapAreaIN, bluestore_alloc); -MEMPOOL_DEFINE_OBJECT_FACTORY(BitMapAreaLeaf, BitMapAreaLeaf, bluestore_alloc); -MEMPOOL_DEFINE_OBJECT_FACTORY(BitMapZone, BitMapZone, bluestore_alloc); -MEMPOOL_DEFINE_OBJECT_FACTORY(BmapEntry, BmapEntry, bluestore_alloc); -MEMPOOL_DEFINE_OBJECT_FACTORY(BitAllocator, BitAllocator, bluestore_alloc); - -int64_t BitMapAreaLeaf::count = 0; -int64_t BitMapZone::count = 0; -int64_t BitMapZone::total_blocks = 0; - -void AllocatorExtentList::add_extents(int64_t start, int64_t count) -{ - bluestore_pextent_t *last_extent = NULL; - bool can_merge = false; - - if (!m_extents->empty()) { - last_extent = &(m_extents->back()); - uint64_t last_offset = last_extent->end() / m_block_size; - uint32_t last_length = last_extent->length / m_block_size; - if ((last_offset == (uint64_t) start) && - (!m_max_blocks || (last_length + count) <= m_max_blocks)) { - can_merge = true; - } - } - - if (can_merge) { - last_extent->length += (count * m_block_size); - } else { - m_extents->emplace_back(bluestore_pextent_t(start * m_block_size, - count * m_block_size)); - } -} - -int64_t BmapEntityListIter::index() -{ - return m_cur_idx; -} - -BmapEntry::BmapEntry(CephContext*, const bool full) -{ - if (full) { - m_bits = BmapEntry::full_bmask(); - } else { - m_bits = BmapEntry::empty_bmask(); - } -} - -BmapEntry::~BmapEntry() -{ - -} - -bool BmapEntry::check_bit(int bit) -{ - return (atomic_fetch() & bit_mask(bit)); -} - -bool BmapEntry::is_allocated(int64_t offset, int64_t num_bits) -{ - bmap_t bmask = BmapEntry::align_mask(num_bits) >> offset; - return ((m_bits & bmask) == bmask); -} - -void BmapEntry::clear_bit(int bit) -{ - bmap_t bmask = bit_mask(bit); - m_bits &= ~(bmask); -} - -void BmapEntry::clear_bits(int offset, int num_bits) -{ - if (num_bits == 0) { - return; - } - - bmap_t bmask = BmapEntry::align_mask(num_bits) >> offset; - m_bits &= ~(bmask); -} - -void BmapEntry::set_bits(int offset, int num_bits) -{ - if (num_bits == 0) { - return; - } - - bmap_t bmask = BmapEntry::align_mask(num_bits) >> offset; - m_bits |= bmask; -} - -/* - * Allocate a bit if it was free. - * Retruns true if it was free. - */ -bool BmapEntry::check_n_set_bit(int bit) -{ - bmap_t bmask = bit_mask(bit); - bool res = !(m_bits & bmask); - m_bits |= bmask; - return res; -} - -/* - * Find N cont free bits in BitMap starting from an offset. - * - * Returns number of continuous bits found. - */ -int BmapEntry::find_n_cont_bits(int start_offset, int64_t num_bits) -{ - int count = 0; - int i = 0; - - if (num_bits == 0) { - return 0; - } - - if (start_offset >= BmapEntry::size()) { - return 0; - } - - for (i = start_offset; i < BmapEntry::size() && count < num_bits; i++) { - if (!check_n_set_bit(i)) { - break; - } - count++; - } - - return count; -} - -/* - * Find N free bits starting search from a given offset. - * - * Returns number of bits found, start bit and end of - * index next to bit where our search ended + 1. - */ -int BmapEntry::find_n_free_bits(int start_idx, int64_t max_bits, - int *free_bit, int *end_idx) -{ - int i = 0; - int count = 0; - - *free_bit = 0; - alloc_assert(max_bits > 0); - - /* - * Find free bit aligned to bit_align return the bit_num in free_bit. - */ - if (atomic_fetch() == BmapEntry::full_bmask()) { - /* - * All bits full, return fail. - */ - *end_idx = BmapEntry::size(); - return 0; - } - - /* - * Do a serial scan on bitmap. - */ - for (i = start_idx; i < BmapEntry::size(); i++) { - if (check_n_set_bit(i)) { - /* - * Found first free bit - */ - *free_bit = i; - count++; - break; - } - } - count += find_n_cont_bits(i + 1, max_bits - 1); - - (*end_idx) = i + count; - return count; -} - -/* - * Find first series of contiguous bits free in bitmap starting - * from start offset that either - * satisfy our need or are touching right edge of bitmap. - * - * Returns allocated bits, start bit of allocated, number of bits - * scanned from start offset. - */ -int -BmapEntry::find_first_set_bits(int64_t required_blocks, - int bit_offset, int *start_offset, - int64_t *scanned) -{ - int allocated = 0; - int conti = 0; - int end_idx = 0; - - *scanned = 0; - - while (bit_offset < BmapEntry::size()) { - conti = find_n_free_bits(bit_offset, required_blocks, - start_offset, &end_idx); - - *scanned += end_idx - bit_offset; - /* - * Either end of bitmap or got required. - */ - if (conti == required_blocks || - (conti + *start_offset == BmapEntry::size())) { - allocated += conti; - break; - } - - /* - * Did not get expected, search from next index again. - */ - clear_bits(*start_offset, conti); - allocated = 0; - - bit_offset = end_idx; - } - - return allocated; -} - -void BmapEntry::dump_state(CephContext* const cct, const int& count) -{ - dout(0) << count << ":: 0x" << std::hex << m_bits << std::dec << dendl; -} - -/* - * Zone related functions. - */ -void BitMapZone::init(CephContext* const cct, - const int64_t zone_num, - const int64_t total_blocks, - const bool def) -{ - m_area_index = zone_num; - BitMapZone::total_blocks = total_blocks; - alloc_assert(size() > 0); - - m_used_blocks = def? total_blocks: 0; - - int64_t num_bmaps = total_blocks / BmapEntry::size(); - alloc_assert(num_bmaps < std::numeric_limits::max()); - alloc_assert(total_blocks < std::numeric_limits::max()); - alloc_assert(!(total_blocks % BmapEntry::size())); - - m_bmap_vec.resize(num_bmaps, BmapEntry(cct, def)); - incr_count(); -} - -int64_t BitMapZone::sub_used_blocks(int64_t num_blocks) -{ - return std::atomic_fetch_sub(&m_used_blocks, (int32_t) num_blocks); -} - -int64_t BitMapZone::add_used_blocks(int64_t num_blocks) -{ - return std::atomic_fetch_add(&m_used_blocks, (int32_t)num_blocks) + num_blocks; -} - -/* Intensionally hinted because BitMapAreaLeaf::child_check_n_lock. */ -inline int64_t BitMapZone::get_used_blocks() -{ - return std::atomic_load(&m_used_blocks); -} - -bool BitMapZone::reserve_blocks(int64_t num_blocks) -{ - ceph_abort(); - return false; -} - -void BitMapZone::unreserve(int64_t num_blocks, int64_t allocated) -{ - ceph_abort(); -} - -int64_t BitMapZone::get_reserved_blocks() -{ - ceph_abort(); - return 0; -} - -BitMapZone::BitMapZone(CephContext* cct, int64_t total_blocks, - int64_t zone_num) - : BitMapArea(cct) -{ - init(cct, zone_num, total_blocks, false); -} - -BitMapZone::BitMapZone(CephContext* cct, int64_t total_blocks, - int64_t zone_num, bool def) - : BitMapArea(cct) -{ - init(cct, zone_num, total_blocks, def); -} - -void BitMapZone::shutdown() -{ -} - -BitMapZone::~BitMapZone() -{ -} - -/* - * Check if some search took zone marker to end. - * - * The inline hint has been added intensionally because of importance of this - * method for BitMapAreaLeaf::child_check_n_lock, and thus for the overall - * allocator's performance. Examination of disassemblies coming from GCC 5.4.0 - * showed that the compiler really needs that hint. - */ -inline bool BitMapZone::is_exhausted() -{ - /* BitMapZone::get_used_blocks operates atomically. No need for lock. */ - return BitMapZone::get_used_blocks() == BitMapZone::size(); -} - -bool BitMapZone::is_allocated(int64_t start_block, int64_t num_blocks) -{ - BmapEntry *bmap = NULL; - int bit = 0; - int64_t falling_in_bmap = 0; - - while (num_blocks) { - bit = start_block % BmapEntry::size(); - bmap = &m_bmap_vec[start_block / BmapEntry::size()]; - falling_in_bmap = MIN(num_blocks, BmapEntry::size() - bit); - - if (!bmap->is_allocated(bit, falling_in_bmap)) { - return false; - } - - start_block += falling_in_bmap; - num_blocks -= falling_in_bmap; - } - - return true; -} - -void BitMapZone::set_blocks_used(int64_t start_block, int64_t num_blocks) -{ - BmapEntry *bmap = NULL; - int bit = 0; - int64_t falling_in_bmap = 0; - int64_t blks = num_blocks; - - while (blks) { - bit = start_block % BmapEntry::size(); - bmap = &m_bmap_vec[start_block / BmapEntry::size()]; - falling_in_bmap = MIN(blks, BmapEntry::size() - bit); - - bmap->set_bits(bit, falling_in_bmap); - - start_block += falling_in_bmap; - blks -= falling_in_bmap; - } - add_used_blocks(num_blocks); -} - -void BitMapZone::free_blocks_int(int64_t start_block, int64_t num_blocks) -{ - BmapEntry *bmap = NULL; - int bit = 0; - int64_t falling_in_bmap = 0; - int64_t count = num_blocks; - int64_t first_blk = start_block; - - if (num_blocks == 0) { - return; - } - alloc_dbg_assert(is_allocated(start_block, num_blocks)); - - while (count) { - bit = first_blk % BmapEntry::size(); - bmap = &m_bmap_vec[first_blk / BmapEntry::size()]; - falling_in_bmap = MIN(count, BmapEntry::size() - bit); - - bmap->clear_bits(bit, falling_in_bmap); - - first_blk += falling_in_bmap; - count -= falling_in_bmap; - } - alloc_dbg_assert(!is_allocated(start_block, num_blocks)); -} - -void BitMapZone::lock_excl() -{ - m_lock.lock(); -} - -bool BitMapZone::lock_excl_try() -{ - return m_lock.try_lock(); -} - -void BitMapZone::unlock() -{ - m_lock.unlock(); -} - -bool BitMapZone::check_locked() -{ - return !lock_excl_try(); -} - -void BitMapZone::free_blocks(int64_t start_block, int64_t num_blocks) -{ - free_blocks_int(start_block, num_blocks); - sub_used_blocks(num_blocks); - alloc_assert(get_used_blocks() >= 0); -} - -int64_t BitMapZone::alloc_blocks_dis(int64_t num_blocks, - int64_t min_alloc, - int64_t hint, - int64_t zone_blk_off, - AllocatorExtentList *alloc_blocks) -{ - int64_t bmap_idx = hint / BmapEntry::size(); - int bit = hint % BmapEntry::size(); - BmapEntry *bmap = NULL; - int64_t allocated = 0; - int64_t blk_off = 0; - int64_t alloc_cont = 0; - int64_t last_cont = 0; - int64_t last_running_ext = 0; - int search_idx = bit; - int64_t scanned = 0; - int start_off = 0; - - - alloc_assert(check_locked()); - - BitMapEntityIter iter = BitMapEntityIter( - &m_bmap_vec, bmap_idx); - bmap = iter.next(); - if (!bmap) { - return 0; - } - - while (allocated < num_blocks) { - blk_off = zone_blk_off + bmap_idx * bmap->size(); - if (last_cont) { - /* - * We had bits free at end of last bitmap, try to complete required - * min alloc size using that. - */ - alloc_cont = bmap->find_n_cont_bits(0, min_alloc - last_cont); - allocated += alloc_cont; - last_cont += alloc_cont; - - if (!alloc_cont) { - if (last_cont) { - this->free_blocks_int(last_running_ext - zone_blk_off, last_cont); - } - allocated -= last_cont; - last_cont = 0; - } else if (last_cont / min_alloc) { - /* - * Got contiguous min_alloc_size across bitmaps. - */ - alloc_blocks->add_extents(last_running_ext, last_cont); - last_cont = 0; - last_running_ext = 0; - } - search_idx = alloc_cont; - } else { - /* - * Try to allocate min_alloc_size bits from given bmap. - */ - alloc_cont = bmap->find_first_set_bits(min_alloc, search_idx, &start_off, &scanned); - search_idx = search_idx + scanned; - allocated += alloc_cont; - if (alloc_cont / min_alloc) { - /* - * Got contiguous min_alloc_size within a bitmap. - */ - alloc_blocks->add_extents(blk_off + start_off, min_alloc); - } - - if (alloc_cont % min_alloc) { - /* - * Got some bits at end of bitmap, carry them to try match with - * start bits from next bitmap. - */ - if (!last_cont) { - last_running_ext = blk_off + start_off; - } - last_cont += alloc_cont % min_alloc; - } - } - - - if (search_idx == BmapEntry::size()) { - search_idx = 0; - bmap_idx = iter.index(); - if ((bmap = iter.next()) == NULL) { - if (last_cont) { - this->free_blocks_int(last_running_ext - zone_blk_off, last_cont); - } - allocated -= last_cont; - break; - } - } - } - - add_used_blocks(allocated); - return allocated; -} - - - -void BitMapZone::dump_state(CephContext* const cct, int& count) -{ - BmapEntry *bmap = NULL; - int bmap_idx = 0; - BitMapEntityIter iter = BitMapEntityIter( - &m_bmap_vec, 0); - dout(0) << __func__ << " zone " << count << " dump start " << dendl; - while ((bmap = static_cast(iter.next()))) { - bmap->dump_state(cct, bmap_idx); - bmap_idx++; - } - dout(0) << __func__ << " zone " << count << " dump end " << dendl; - count++; -} - - -/* - * BitMapArea Leaf and non-Leaf functions. - */ -int64_t BitMapArea::get_zone_size(CephContext* cct) -{ - return cct->_conf->bluestore_bitmapallocator_blocks_per_zone; -} - -int64_t BitMapArea::get_span_size(CephContext* cct) -{ - return cct->_conf->bluestore_bitmapallocator_span_size; -} - -int BitMapArea::get_level(CephContext* cct, int64_t total_blocks) -{ - int level = 1; - int64_t zone_size_block = get_zone_size(cct); - int64_t span_size = get_span_size(cct); - int64_t spans = zone_size_block * span_size; - while (spans < total_blocks) { - spans *= span_size; - level++; - } - return level; -} - -int64_t BitMapArea::get_level_factor(CephContext* cct, int level) -{ - alloc_assert(level > 0); - - int64_t zone_size = get_zone_size(cct); - if (level == 1) { - return zone_size; - } - - int64_t level_factor = zone_size; - int64_t span_size = get_span_size(cct); - while (--level) { - level_factor *= span_size; - } - - return level_factor; -} - -int64_t BitMapArea::get_index() -{ - return m_area_index; -} - -/* - * BitMapArea Leaf and Internal - */ -BitMapAreaIN::BitMapAreaIN(CephContext* cct) - : BitMapArea(cct) -{ - // nothing -} - -void BitMapAreaIN::init_common(CephContext* const cct, - const int64_t total_blocks, - const int64_t area_idx, - const bool def) -{ - m_area_index = area_idx; - m_total_blocks = total_blocks; - m_level = BitMapArea::get_level(cct, total_blocks); - m_reserved_blocks = 0; - - m_used_blocks = def? total_blocks: 0; -} - -void BitMapAreaIN::init(CephContext* const cct, - int64_t total_blocks, - const int64_t area_idx, - const bool def) -{ - int64_t num_child = 0; - alloc_assert(!(total_blocks % BmapEntry::size())); - - init_common(cct, total_blocks, area_idx, def); - int64_t level_factor = BitMapArea::get_level_factor(cct, m_level); - - num_child = (total_blocks + level_factor - 1) / level_factor; - alloc_assert(num_child < std::numeric_limits::max()); - - m_child_size_blocks = level_factor; - - std::vector children; - children.reserve(num_child); - int i = 0; - for (i = 0; i < num_child - 1; i++) { - if (m_level <= 2) { - children.push_back(new BitMapAreaLeaf(cct, m_child_size_blocks, i, def)); - } else { - children.push_back(new BitMapAreaIN(cct, m_child_size_blocks, i, def)); - } - total_blocks -= m_child_size_blocks; - } - - int last_level = BitMapArea::get_level(cct, total_blocks); - if (last_level == 1) { - children.push_back(new BitMapAreaLeaf(cct, total_blocks, i, def)); - } else { - children.push_back(new BitMapAreaIN(cct, total_blocks, i, def)); - } - m_child_list = BitMapAreaList(std::move(children)); -} - -BitMapAreaIN::BitMapAreaIN(CephContext* cct,int64_t total_blocks, - int64_t area_idx) - : BitMapArea(cct) -{ - init(cct, total_blocks, area_idx, false); -} - -BitMapAreaIN::BitMapAreaIN(CephContext* cct, int64_t total_blocks, - int64_t area_idx, bool def) - : BitMapArea(cct) -{ - init(cct, total_blocks, area_idx, def); -} - -BitMapAreaIN::~BitMapAreaIN() -{ -} - -void BitMapAreaIN::shutdown() -{ - lock_excl(); - m_total_blocks = -1; - m_area_index = -2; - unlock(); -} - -bool BitMapAreaIN::child_check_n_lock(BitMapArea *child, int64_t required) -{ - child->lock_shared(); - - if (child->is_exhausted()) { - child->unlock(); - return false; - } - - int64_t child_used_blocks = child->get_used_blocks(); - int64_t child_total_blocks = child->size(); - if ((child_total_blocks - child_used_blocks) < required) { - child->unlock(); - return false; - } - - return true; -} - -void BitMapAreaIN::child_unlock(BitMapArea *child) -{ - child->unlock(); -} - -bool BitMapAreaIN::is_exhausted() -{ - return get_used_blocks() == size(); -} - -int64_t BitMapAreaIN::add_used_blocks(int64_t blks) -{ - std::lock_guard l(m_blocks_lock); - m_used_blocks += blks; - return m_used_blocks; -} - -int64_t BitMapAreaIN::sub_used_blocks(int64_t num_blocks) -{ - std::lock_guard l(m_blocks_lock); - - int64_t used_blks = m_used_blocks; - m_used_blocks -= num_blocks; - alloc_assert(m_used_blocks >= 0); - return used_blks; -} - -int64_t BitMapAreaIN::get_used_blocks() -{ - std::lock_guard l(m_blocks_lock); - return m_used_blocks; -} - -int64_t BitMapAreaIN::get_used_blocks_adj() -{ - std::lock_guard l(m_blocks_lock); - return m_used_blocks - m_reserved_blocks; -} - -bool BitMapAreaIN::reserve_blocks(int64_t num) -{ - bool res = false; - std::lock_guard u_l(m_blocks_lock); - if (m_used_blocks + num <= size()) { - m_used_blocks += num; - m_reserved_blocks += num; - res = true; - } - alloc_assert(m_used_blocks <= size()); - return res; -} - -void BitMapAreaIN::unreserve(int64_t needed, int64_t allocated) -{ - std::lock_guard l(m_blocks_lock); - m_used_blocks -= (needed - allocated); - m_reserved_blocks -= needed; - alloc_assert(m_used_blocks >= 0); - alloc_assert(m_reserved_blocks >= 0); -} -int64_t BitMapAreaIN::get_reserved_blocks() -{ - std::lock_guard l(m_blocks_lock); - return m_reserved_blocks; -} - -bool BitMapAreaIN::is_allocated(int64_t start_block, int64_t num_blocks) -{ - BitMapArea *area = NULL; - int64_t area_block_offset = 0; - int64_t falling_in_area = 0; - - alloc_assert(start_block >= 0 && - (start_block + num_blocks <= size())); - - if (num_blocks == 0) { - return true; - } - - while (num_blocks) { - area = static_cast(m_child_list.get_nth_item( - start_block / m_child_size_blocks)); - - area_block_offset = start_block % m_child_size_blocks; - falling_in_area = MIN(m_child_size_blocks - area_block_offset, - num_blocks); - if (!area->is_allocated(area_block_offset, falling_in_area)) { - return false; - } - start_block += falling_in_area; - num_blocks -= falling_in_area; - } - return true; -} - -int64_t BitMapAreaIN::alloc_blocks_dis_int_work(bool wrap, int64_t num_blocks, int64_t min_alloc, - int64_t hint, int64_t area_blk_off, AllocatorExtentList *block_list) -{ - BitMapArea *child = NULL; - int64_t allocated = 0; - int64_t blk_off = 0; - - BmapEntityListIter iter = BmapEntityListIter( - &m_child_list, hint / m_child_size_blocks, wrap); - - while ((child = static_cast(iter.next()))) { - if (!child_check_n_lock(child, 1)) { - hint = 0; - continue; - } - - blk_off = child->get_index() * m_child_size_blocks + area_blk_off; - allocated += child->alloc_blocks_dis(num_blocks - allocated, min_alloc, - hint % m_child_size_blocks, blk_off, block_list); - hint = 0; - child_unlock(child); - if (allocated == num_blocks) { - break; - } - } - - return allocated; -} - -int64_t BitMapAreaIN::alloc_blocks_dis_int(int64_t num_blocks, int64_t min_alloc, - int64_t hint, int64_t area_blk_off, AllocatorExtentList *block_list) -{ - return alloc_blocks_dis_int_work(false, num_blocks, min_alloc, hint, - area_blk_off, block_list); -} - -int64_t BitMapAreaIN::alloc_blocks_dis(int64_t num_blocks, int64_t min_alloc, - int64_t hint, int64_t blk_off, AllocatorExtentList *block_list) -{ - int64_t allocated = 0; - - lock_shared(); - allocated += alloc_blocks_dis_int(num_blocks, min_alloc, hint, blk_off, block_list); - add_used_blocks(allocated); - - unlock(); - return allocated; -} - - -void BitMapAreaIN::set_blocks_used_int(int64_t start_block, int64_t num_blocks) -{ - BitMapArea *child = NULL; - int64_t child_block_offset = 0; - int64_t falling_in_child = 0; - int64_t blks = num_blocks; - int64_t start_blk = start_block; - - alloc_assert(start_block >= 0); - - while (blks) { - child = static_cast(m_child_list.get_nth_item( - start_blk / m_child_size_blocks)); - - child_block_offset = start_blk % child->size(); - falling_in_child = MIN(m_child_size_blocks - child_block_offset, - blks); - child->set_blocks_used(child_block_offset, falling_in_child); - start_blk += falling_in_child; - blks -= falling_in_child; - } - - add_used_blocks(num_blocks); - alloc_dbg_assert(is_allocated(start_block, num_blocks)); -} - -void BitMapAreaIN::set_blocks_used(int64_t start_block, int64_t num_blocks) -{ - if (num_blocks == 0) { - return; - } - - lock_shared(); - set_blocks_used_int(start_block, num_blocks); - unlock(); -} - -void BitMapAreaIN::free_blocks_int(int64_t start_block, int64_t num_blocks) -{ - BitMapArea *child = NULL; - int64_t child_block_offset = 0; - int64_t falling_in_child = 0; - - alloc_assert(start_block >= 0 && - (start_block + num_blocks) <= size()); - - if (num_blocks == 0) { - return; - } - - while (num_blocks) { - child = static_cast(m_child_list.get_nth_item( - start_block / m_child_size_blocks)); - - child_block_offset = start_block % m_child_size_blocks; - - falling_in_child = MIN(m_child_size_blocks - child_block_offset, - num_blocks); - child->free_blocks(child_block_offset, falling_in_child); - start_block += falling_in_child; - num_blocks -= falling_in_child; - } - -} -void BitMapAreaIN::free_blocks(int64_t start_block, int64_t num_blocks) -{ - if (num_blocks == 0) { - return; - } - lock_shared(); - alloc_dbg_assert(is_allocated(start_block, num_blocks)); - - free_blocks_int(start_block, num_blocks); - (void) sub_used_blocks(num_blocks); - - unlock(); -} - -void BitMapAreaIN::dump_state(CephContext* const cct, int& count) -{ - BitMapArea *child = NULL; - - BmapEntityListIter iter = BmapEntityListIter( - &m_child_list, 0, false); - - while ((child = static_cast(iter.next()))) { - child->dump_state(cct, count); - } -} - -/* - * BitMapArea Leaf - */ -BitMapAreaLeaf::BitMapAreaLeaf(CephContext* cct, int64_t total_blocks, - int64_t area_idx) - : BitMapAreaIN(cct) -{ - init(cct, total_blocks, area_idx, false); -} - -BitMapAreaLeaf::BitMapAreaLeaf(CephContext* cct, int64_t total_blocks, - int64_t area_idx, bool def) - : BitMapAreaIN(cct) -{ - init(cct, total_blocks, area_idx, def); -} - -void BitMapAreaLeaf::init(CephContext* const cct, - const int64_t total_blocks, - const int64_t area_idx, - const bool def) -{ - int64_t num_child = 0; - alloc_assert(!(total_blocks % BmapEntry::size())); - - init_common(cct, total_blocks, area_idx, def); - alloc_assert(m_level == 1); - int zone_size_block = get_zone_size(cct); - alloc_assert(zone_size_block > 0); - num_child = (total_blocks + zone_size_block - 1) / zone_size_block; - alloc_assert(num_child); - m_child_size_blocks = total_blocks / num_child; - - std::vector children; - children.reserve(num_child); - for (int i = 0; i < num_child; i++) { - children.emplace_back(new BitMapZone(cct, m_child_size_blocks, i, def)); - } - - m_child_list = BitMapAreaList(std::move(children)); - - BitMapAreaLeaf::incr_count(); -} - -BitMapAreaLeaf::~BitMapAreaLeaf() -{ - lock_excl(); - - for (int64_t i = 0; i < m_child_list.size(); i++) { - auto child = static_cast(m_child_list.get_nth_item(i)); - delete child; - } - - unlock(); -} - -/* Intensionally hinted because BitMapAreaLeaf::alloc_blocks_dis_int. */ -inline bool BitMapAreaLeaf::child_check_n_lock(BitMapZone* const child, - const int64_t required, - const bool lock) -{ - /* The exhausted check can be performed without acquiring the lock. This - * is because 1) BitMapZone::is_exhausted() actually operates atomically - * and 2) it's followed by the exclusive, required-aware re-verification. */ - if (child->BitMapZone::is_exhausted()) { - return false; - } - - if (lock) { - child->lock_excl(); - } else if (!child->lock_excl_try()) { - return false; - } - - int64_t child_used_blocks = child->get_used_blocks(); - int64_t child_total_blocks = child->size(); - if ((child_total_blocks - child_used_blocks) < required) { - child->unlock(); - return false; - } - - return true; -} - -int64_t BitMapAreaLeaf::alloc_blocks_dis_int(int64_t num_blocks, int64_t min_alloc, - int64_t hint, int64_t area_blk_off, AllocatorExtentList *block_list) -{ - BitMapZone* child = nullptr; - int64_t allocated = 0; - int64_t blk_off = 0; - - BmapEntityListIter iter = BmapEntityListIter( - &m_child_list, hint / m_child_size_blocks, false); - - /* We're sure the only element type we aggregate is BitMapZone, - * so there is no business to go through vptr and thus prohibit - * compiler to inline the stuff. Consult BitMapAreaLeaf::init. */ - while ((child = static_cast(iter.next()))) { - if (!child_check_n_lock(child, 1, false)) { - hint = 0; - continue; - } - - blk_off = child->get_index() * m_child_size_blocks + area_blk_off; - allocated += child->alloc_blocks_dis(num_blocks - allocated, min_alloc, - hint % m_child_size_blocks, blk_off, block_list); - child->unlock(); - if (allocated == num_blocks) { - break; - } - hint = 0; - } - return allocated; -} - -void BitMapAreaLeaf::free_blocks_int(int64_t start_block, int64_t num_blocks) -{ - BitMapArea *child = NULL; - int64_t child_block_offset = 0; - int64_t falling_in_child = 0; - - alloc_assert(start_block >= 0 && - (start_block + num_blocks) <= size()); - - if (num_blocks == 0) { - return; - } - - while (num_blocks) { - child = static_cast(m_child_list.get_nth_item( - start_block / m_child_size_blocks)); - - child_block_offset = start_block % m_child_size_blocks; - - falling_in_child = MIN(m_child_size_blocks - child_block_offset, - num_blocks); - - child->lock_excl(); - child->free_blocks(child_block_offset, falling_in_child); - child->unlock(); - start_block += falling_in_child; - num_blocks -= falling_in_child; - } -} - -/* - * Main allocator functions. - */ -BitAllocator::BitAllocator(CephContext* cct, int64_t total_blocks, - int64_t zone_size_block, bmap_alloc_mode_t mode) - : BitMapAreaIN(cct), - cct(cct) -{ - init_check(total_blocks, zone_size_block, mode, false, false); -} - -BitAllocator::BitAllocator(CephContext* cct, int64_t total_blocks, - int64_t zone_size_block, bmap_alloc_mode_t mode, - bool def) - : BitMapAreaIN(cct), - cct(cct) -{ - init_check(total_blocks, zone_size_block, mode, def, false); -} - -BitAllocator::BitAllocator(CephContext* cct, int64_t total_blocks, - int64_t zone_size_block, bmap_alloc_mode_t mode, - bool def, bool stats_on) - : BitMapAreaIN(cct), - cct(cct) -{ - init_check(total_blocks, zone_size_block, mode, def, stats_on); -} - -void BitAllocator::init_check(int64_t total_blocks, int64_t zone_size_block, - bmap_alloc_mode_t mode, bool def, bool stats_on) -{ - int64_t unaligned_blocks = 0; - - if (mode != SERIAL && mode != CONCURRENT) { - ceph_abort(); - } - - if (total_blocks <= 0) { - ceph_abort(); - } - - if (zone_size_block == 0 || - zone_size_block < BmapEntry::size()) { - ceph_abort(); - } - - zone_size_block = (zone_size_block / BmapEntry::size()) * - BmapEntry::size(); - - unaligned_blocks = total_blocks % zone_size_block; - m_extra_blocks = unaligned_blocks? zone_size_block - unaligned_blocks: 0; - total_blocks = ROUND_UP_TO(total_blocks, zone_size_block); - - m_alloc_mode = mode; - m_is_stats_on = stats_on; - if (m_is_stats_on) { - m_stats = new BitAllocatorStats(); - } - - pthread_rwlock_init(&m_rw_lock, NULL); - init(cct, total_blocks, 0, def); - if (!def && unaligned_blocks) { - /* - * Mark extra padded blocks used from beginning. - */ - set_blocks_used(total_blocks - m_extra_blocks, m_extra_blocks); - } -} - -void BitAllocator::lock_excl() -{ - pthread_rwlock_wrlock(&m_rw_lock); -} - -void BitAllocator::lock_shared() -{ - pthread_rwlock_rdlock(&m_rw_lock); -} - -bool BitAllocator::try_lock() -{ - bool get_lock = false; - if (pthread_rwlock_trywrlock(&m_rw_lock) == 0) { - get_lock = true; - } - - return get_lock; -} - -void BitAllocator::unlock() -{ - pthread_rwlock_unlock(&m_rw_lock); -} - -BitAllocator::~BitAllocator() -{ - lock_excl(); - - for (int64_t i = 0; i < m_child_list.size(); i++) { - auto child = static_cast(m_child_list.get_nth_item(i)); - delete child; - } - - unlock(); - pthread_rwlock_destroy(&m_rw_lock); -} - -void -BitAllocator::shutdown() -{ - bool get_lock = try_lock(); - assert(get_lock); - bool get_serial_lock = try_serial_lock(); - assert(get_serial_lock); - serial_unlock(); - unlock(); -} - -void BitAllocator::unreserve_blocks(int64_t unused) -{ - unreserve(unused, 0); -} - -void BitAllocator::serial_lock() -{ - if (m_alloc_mode == SERIAL) { - m_serial_mutex.lock(); - } -} - -void BitAllocator::serial_unlock() -{ - if (m_alloc_mode == SERIAL) { - m_serial_mutex.unlock(); - } -} - -bool BitAllocator::try_serial_lock() -{ - bool get_lock = false; - if (m_alloc_mode == SERIAL) { - if (m_serial_mutex.try_lock() == 0) { - get_lock = true; - } - } else { - get_lock = true; - } - return get_lock; -} - -bool BitAllocator::child_check_n_lock(BitMapArea *child, int64_t required) -{ - child->lock_shared(); - - if (child->is_exhausted()) { - child->unlock(); - return false; - } - - int64_t child_used_blocks = child->get_used_blocks(); - int64_t child_total_blocks = child->size(); - if ((child_total_blocks - child_used_blocks) < required) { - child->unlock(); - return false; - } - - return true; -} - -void BitAllocator::child_unlock(BitMapArea *child) -{ - child->unlock(); -} - -bool BitAllocator::check_input_dis(int64_t num_blocks) -{ - if (num_blocks == 0 || num_blocks > size()) { - return false; - } - return true; -} - -bool BitAllocator::check_input(int64_t num_blocks) -{ - if (num_blocks == 0 || num_blocks > get_zone_size(cct)) { - return false; - } - return true; -} - -void BitAllocator::free_blocks(int64_t start_block, int64_t num_blocks) -{ - if (num_blocks == 0) { - return; - } - - alloc_assert(start_block + num_blocks <= size()); - if (is_stats_on()) { - m_stats->add_free_calls(1); - m_stats->add_freed(num_blocks); - } - - lock_shared(); - alloc_dbg_assert(is_allocated(start_block, num_blocks)); - - free_blocks_int(start_block, num_blocks); - (void) sub_used_blocks(num_blocks); - - unlock(); -} - - -void BitAllocator::set_blocks_used(int64_t start_block, int64_t num_blocks) -{ - if (num_blocks == 0) { - return; - } - - alloc_assert(start_block + num_blocks <= size()); - lock_shared(); - serial_lock(); - set_blocks_used_int(start_block, num_blocks); - - serial_unlock(); - unlock(); -} - -/* - * Allocate N dis-contiguous blocks. - */ -int64_t BitAllocator::alloc_blocks_dis_int(int64_t num_blocks, int64_t min_alloc, - int64_t hint, int64_t area_blk_off, AllocatorExtentList *block_list) -{ - return alloc_blocks_dis_int_work(true, num_blocks, min_alloc, hint, - area_blk_off, block_list); -} - -int64_t BitAllocator::alloc_blocks_dis_res(int64_t num_blocks, int64_t min_alloc, - int64_t hint, AllocatorExtentList *block_list) -{ - return alloc_blocks_dis_work(num_blocks, min_alloc, hint, block_list, true); -} - -int64_t BitAllocator::alloc_blocks_dis_work(int64_t num_blocks, int64_t min_alloc, - int64_t hint, AllocatorExtentList *block_list, bool reserved) -{ - int scans = 1; - int64_t allocated = 0; - /* - * This is root so offset is 0 yet. - */ - int64_t blk_off = 0; - - if (!check_input_dis(num_blocks)) { - return 0; - } - - if (is_stats_on()) { - m_stats->add_alloc_calls(1); - m_stats->add_allocated(num_blocks); - } - - lock_shared(); - serial_lock(); - if (!reserved && !reserve_blocks(num_blocks)) { - goto exit; - } - - if (is_stats_on()) { - m_stats->add_concurrent_scans(scans); - } - - while (scans && allocated < num_blocks) { - allocated += alloc_blocks_dis_int(num_blocks - allocated, min_alloc, hint + allocated, blk_off, block_list); - scans--; - } - - if (allocated < num_blocks) { - /* - * Could not find anything in concurrent scan. - * Go in serial manner to get something for sure - * if available. - */ - serial_unlock(); - unlock(); - lock_excl(); - serial_lock(); - allocated += alloc_blocks_dis_int(num_blocks - allocated, min_alloc, hint + allocated, - blk_off, block_list); - if (is_stats_on()) { - m_stats->add_serial_scans(1); - } - } - - unreserve(num_blocks, allocated); - alloc_dbg_assert(is_allocated_dis(block_list, allocated)); - -exit: - serial_unlock(); - unlock(); - - return allocated; -} - -bool BitAllocator::is_allocated_dis(AllocatorExtentList *blocks, int64_t num_blocks) -{ - int64_t count = 0; - for (int64_t j = 0; j < blocks->get_extent_count(); j++) { - auto p = blocks->get_nth_extent(j); - count += p.second; - if (!is_allocated(p.first, p.second)) { - return false; - } - } - - alloc_assert(count == num_blocks); - return true; -} - -void BitAllocator::free_blocks_dis(int64_t num_blocks, AllocatorExtentList *block_list) -{ - int64_t freed = 0; - lock_shared(); - if (is_stats_on()) { - m_stats->add_free_calls(1); - m_stats->add_freed(num_blocks); - } - - for (int64_t i = 0; i < block_list->get_extent_count(); i++) { - free_blocks_int(block_list->get_nth_extent(i).first, - block_list->get_nth_extent(i).second); - freed += block_list->get_nth_extent(i).second; - } - - alloc_assert(num_blocks == freed); - sub_used_blocks(num_blocks); - alloc_assert(get_used_blocks() >= 0); - unlock(); -} - -void BitAllocator::dump() -{ - int count = 0; - serial_lock(); - dump_state(cct, count); - serial_unlock(); -} diff --git a/src/os/bluestore/BitAllocator.h b/src/os/bluestore/BitAllocator.h deleted file mode 100644 index 1613059c861d4..0000000000000 --- a/src/os/bluestore/BitAllocator.h +++ /dev/null @@ -1,613 +0,0 @@ -// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- -// vim: ts=8 sw=2 smarttab -/* - * Bitmap based in memory allocator. - * Author: Ramesh Chander, Ramesh.Chander@sandisk.com - */ - -#ifndef CEPH_OS_BLUESTORE_BITALLOCATOR_H -#define CEPH_OS_BLUESTORE_BITALLOCATOR_H - - -#include -#include -#include -#include -#include -#include -#include "include/intarith.h" -#include "os/bluestore/Allocator.h" -#include "os/bluestore/bluestore_types.h" - -#define alloc_assert assert - -#ifdef BIT_ALLOCATOR_DEBUG -#define alloc_dbg_assert(x) assert(x) -#else -#define alloc_dbg_assert(x) (static_cast (0)) -#endif - -class AllocatorExtentList { - PExtentVector *m_extents; - int64_t m_block_size; - int64_t m_max_blocks; - -public: - void init(PExtentVector *extents, int64_t block_size, - uint64_t max_alloc_size) { - m_extents = extents; - m_block_size = block_size; - m_max_blocks = max_alloc_size / block_size; - assert(m_extents->empty()); - } - - AllocatorExtentList(PExtentVector *extents, int64_t block_size) { - init(extents, block_size, 0); - } - - AllocatorExtentList(PExtentVector *extents, int64_t block_size, - uint64_t max_alloc_size) { - init(extents, block_size, max_alloc_size); - } - - void reset() { - m_extents->clear(); - } - - void add_extents(int64_t start, int64_t count); - - PExtentVector *get_extents() { - return m_extents; - } - - std::pair get_nth_extent(int index) { - return std::make_pair - ((*m_extents)[index].offset / m_block_size, - (*m_extents)[index].length / m_block_size); - } - - int64_t get_extent_count() { - return m_extents->size(); - } -}; - -class BitAllocatorStats { -public: - std::atomic m_total_alloc_calls; - std::atomic m_total_free_calls; - std::atomic m_total_allocated; - std::atomic m_total_freed; - std::atomic m_total_serial_scans; - std::atomic m_total_concurrent_scans; - std::atomic m_total_node_scanned; - - BitAllocatorStats() { - m_total_alloc_calls = 0; - m_total_free_calls = 0; - m_total_allocated = 0; - m_total_freed = 0; - m_total_serial_scans = 0; - m_total_concurrent_scans = 0; - m_total_node_scanned = 0; - } - - void add_alloc_calls(int64_t val) { - std::atomic_fetch_add(&m_total_alloc_calls, val); - } - void add_free_calls(int64_t val) { - std::atomic_fetch_add(&m_total_free_calls, val); - } - void add_allocated(int64_t val) { - std::atomic_fetch_add(&m_total_allocated, val); - } - void add_freed(int64_t val) { - std::atomic_fetch_add(&m_total_freed, val); - } - void add_serial_scans(int64_t val) { - std::atomic_fetch_add(&m_total_serial_scans, val); - } - void add_concurrent_scans(int64_t val) { - std::atomic_fetch_add(&m_total_concurrent_scans, val); - } - void add_node_scanned(int64_t val) { - std::atomic_fetch_add(&m_total_node_scanned, val); - } -}; - -template -class BitMapEntityIter { - typedef mempool::bluestore_alloc::vector BitMapEntityVector; - BitMapEntityVector *m_list; - int64_t m_start_idx; - int64_t m_cur_idx; - bool m_wrap; - bool m_wrapped; - bool m_end; -public: - - void init(BitMapEntityVector *list, bool wrap, int64_t start_idx) { - m_list = list; - m_wrap = wrap; - m_start_idx = start_idx; - m_cur_idx = m_start_idx; - m_wrapped = false; - m_end = false; - } - - BitMapEntityIter(BitMapEntityVector *list, int64_t start_idx) { - init(list, false, start_idx); - } - BitMapEntityIter(BitMapEntityVector *list, int64_t start_idx, bool wrap) { - init(list, wrap, start_idx); - } - - BitMapEntity *next() { - int64_t cur_idx = m_cur_idx; - - if (m_wrapped && - cur_idx == m_start_idx) { - /* - * End of wrap cycle + 1 - */ - if (!m_end) { - m_end = true; - return &(*m_list)[cur_idx]; - } - return NULL; - } - m_cur_idx++; - - if (m_cur_idx == (int64_t)m_list->size() && - m_wrap) { - m_cur_idx = 0; - m_wrapped = true; - } - - if (cur_idx == (int64_t)m_list->size()) { - /* - * End of list - */ - return NULL; - } - - alloc_assert(cur_idx < (int64_t)m_list->size()); - return &(*m_list)[cur_idx]; - } - - int64_t index() { - return m_cur_idx; - } -}; - -typedef unsigned long bmap_t; -typedef mempool::bluestore_alloc::vector bmap_mask_vec_t; - -class BmapEntry { -private: - bmap_t m_bits; - -public: - MEMPOOL_CLASS_HELPERS(); - static bmap_t full_bmask() { - return (bmap_t) -1; - } - static int64_t size() { - return (sizeof(bmap_t) * 8); - } - static bmap_t empty_bmask() { - return (bmap_t) 0; - } - static bmap_t align_mask(int x) { - return ((x) >= BmapEntry::size()? (bmap_t) -1 : (~(((bmap_t) -1) >> (x)))); - } - static bmap_t bit_mask(int bit_num) { - return (bmap_t) 0x1 << ((BmapEntry::size() - 1) - bit_num); - } - bmap_t atomic_fetch() { - return m_bits; - } - BmapEntry(CephContext*, bool val); - BmapEntry(CephContext*) { - m_bits = 0; - } - BmapEntry(const BmapEntry& bmap) { - m_bits = bmap.m_bits; - } - - void clear_bit(int bit); - void clear_bits(int offset, int num_bits); - void set_bits(int offset, int num_bits); - bool check_n_set_bit(int bit); - bool check_bit(int bit); - bool is_allocated(int64_t start_bit, int64_t num_bits); - - int find_n_cont_bits(int start_offset, int64_t num_bits); - int find_n_free_bits(int start_idx, int64_t max_bits, - int *free_bit, int *end_idx); - int find_first_set_bits(int64_t required_blocks, int bit_offset, - int *start_offset, int64_t *scanned); - - void dump_state(CephContext* cct, const int& count); - ~BmapEntry(); - -}; - -class BitMapArea { -protected: - int16_t m_area_index; - -public: - MEMPOOL_CLASS_HELPERS(); - static int64_t get_zone_size(CephContext* cct); - static int64_t get_span_size(CephContext* cct); - static int get_level(CephContext* cct, int64_t total_blocks); - static int64_t get_level_factor(CephContext* cct, int level); - virtual bool is_allocated(int64_t start_block, int64_t num_blocks) = 0; - virtual bool is_exhausted() = 0; - virtual bool child_check_n_lock(BitMapArea *child, int64_t required) { - ceph_abort(); - return true; - } - virtual bool child_check_n_lock(BitMapArea *child, int64_t required, bool lock) { - ceph_abort(); - return true; - } - virtual void child_unlock(BitMapArea *child) { - ceph_abort(); - } - - virtual void lock_excl() = 0; - virtual bool lock_excl_try() { - ceph_abort(); - return false; - } - virtual void lock_shared() { - ceph_abort(); - return; - } - virtual void unlock() = 0; - - virtual int64_t sub_used_blocks(int64_t num_blocks) = 0; - virtual int64_t add_used_blocks(int64_t num_blocks) = 0; - virtual bool reserve_blocks(int64_t num_blocks) = 0; - virtual void unreserve(int64_t num_blocks, int64_t allocated) = 0; - virtual int64_t get_reserved_blocks() = 0; - virtual int64_t get_used_blocks() = 0; - - virtual void shutdown() = 0; - - virtual int64_t alloc_blocks_dis(int64_t num_blocks, int64_t min_alloc, - int64_t hint, int64_t blk_off, AllocatorExtentList *block_list) { - ceph_abort(); - return 0; - } - - virtual void set_blocks_used(int64_t start_block, int64_t num_blocks) = 0; - virtual void free_blocks(int64_t start_block, int64_t num_blocks) = 0; - virtual int64_t size() = 0; - - int64_t child_count(); - int64_t get_index(); - int64_t get_level(); - virtual void dump_state(CephContext* cct, int& count) = 0; - BitMapArea(CephContext*) { } - virtual ~BitMapArea() { } -}; - -class BitMapAreaList { - -private: - std::vector m_items; - -public: - /* Must be DefaultConstructible as BitMapAreaIN and derivates employ - * a deferred init, sorry. */ - BitMapAreaList() = default; - - BitMapAreaList(std::vector&& m_items) - : m_items(std::move(m_items)) { - } - - BitMapArea *get_nth_item(const int64_t idx) { - return m_items[idx]; - } - - /* FIXME: we really should use size_t. */ - int64_t size() const { - return m_items.size(); - } -}; - -/* Intensionally inlined for the sake of BitMapAreaLeaf::alloc_blocks_dis_int. */ -class BmapEntityListIter { - BitMapAreaList* m_list; - int64_t m_start_idx; - int64_t m_cur_idx; - bool m_wrap; - bool m_wrapped; - bool m_end; - -public: - BmapEntityListIter(BitMapAreaList* const list, - const int64_t start_idx, - const bool wrap = false) - : m_list(list), - m_start_idx(start_idx), - m_cur_idx(start_idx), - m_wrap(wrap), - m_wrapped(false), - m_end(false) { - } - - BitMapArea* next() { - int64_t cur_idx = m_cur_idx; - - if (m_wrapped && - cur_idx == m_start_idx) { - /* - * End of wrap cycle + 1 - */ - if (!m_end) { - m_end = true; - return m_list->get_nth_item(cur_idx); - } - return NULL; - } - m_cur_idx++; - - if (m_cur_idx == m_list->size() && - m_wrap) { - m_cur_idx = 0; - m_wrapped = true; - } - if (cur_idx == m_list->size()) { - /* - * End of list - */ - return NULL; - } - - /* This method should be *really* fast as it's being executed over - * and over during traversal of allocators indexes. */ - alloc_dbg_assert(cur_idx < m_list->size()); - return m_list->get_nth_item(cur_idx); - } - - int64_t index(); -}; - -typedef mempool::bluestore_alloc::vector BmapEntryVector; - -class BitMapZone: public BitMapArea { - -private: - std::atomic m_used_blocks; - BmapEntryVector m_bmap_vec; - std::mutex m_lock; - -public: - MEMPOOL_CLASS_HELPERS(); - static int64_t count; - static int64_t total_blocks; - static void incr_count() { count++;} - static int64_t get_total_blocks() {return total_blocks;} - bool is_allocated(int64_t start_block, int64_t num_blocks) override; - bool is_exhausted() override final; - void reset_marker(); - - int64_t sub_used_blocks(int64_t num_blocks) override; - int64_t add_used_blocks(int64_t num_blocks) override; - bool reserve_blocks(int64_t num_blocks) override; - void unreserve(int64_t num_blocks, int64_t allocated) override; - int64_t get_reserved_blocks() override; - int64_t get_used_blocks() override final; - int64_t size() override final { - return get_total_blocks(); - } - - void lock_excl() override; - bool lock_excl_try() override; - void unlock() override; - bool check_locked(); - - void free_blocks_int(int64_t start_block, int64_t num_blocks); - void init(CephContext* cct, int64_t zone_num, int64_t total_blocks, bool def); - - BitMapZone(CephContext* cct, int64_t total_blocks, int64_t zone_num); - BitMapZone(CephContext* cct, int64_t total_blocks, int64_t zone_num, bool def); - - ~BitMapZone() override; - void shutdown() override; - int64_t alloc_blocks_dis(int64_t num_blocks, int64_t min_alloc, int64_t hint, - int64_t blk_off, AllocatorExtentList *block_list) override; - void set_blocks_used(int64_t start_block, int64_t num_blocks) override; - - void free_blocks(int64_t start_block, int64_t num_blocks) override; - void dump_state(CephContext* cct, int& count) override; -}; - -class BitMapAreaIN: public BitMapArea{ - -protected: - int64_t m_child_size_blocks; - int64_t m_total_blocks; - int16_t m_level; - - int64_t m_used_blocks; - int64_t m_reserved_blocks; - std::mutex m_blocks_lock; - BitMapAreaList m_child_list; - - bool is_allocated(int64_t start_block, int64_t num_blocks) override; - bool is_exhausted() override; - - bool child_check_n_lock(BitMapArea *child, int64_t required, bool lock) override { - ceph_abort(); - return false; - } - - bool child_check_n_lock(BitMapArea *child, int64_t required) override; - void child_unlock(BitMapArea *child) override; - - void lock_excl() override { - return; - } - void lock_shared() override { - return; - } - void unlock() override { - return; - } - - void init(CephContext* cct, int64_t total_blocks, int64_t zone_size_block, bool def); - void init_common(CephContext* cct, - int64_t total_blocks, - int64_t zone_size_block, - bool def); - int64_t alloc_blocks_dis_int_work(bool wrap, int64_t num_blocks, int64_t min_alloc, int64_t hint, - int64_t blk_off, AllocatorExtentList *block_list); - - int64_t alloc_blocks_int_work(bool wait, bool wrap, - int64_t num_blocks, int64_t hint, int64_t *start_block); - -public: - MEMPOOL_CLASS_HELPERS(); - BitMapAreaIN(CephContext* cct); - BitMapAreaIN(CephContext* cct, int64_t zone_num, int64_t total_blocks); - BitMapAreaIN(CephContext* cct, int64_t zone_num, int64_t total_blocks, - bool def); - - ~BitMapAreaIN() override; - void shutdown() override; - int64_t sub_used_blocks(int64_t num_blocks) override; - int64_t add_used_blocks(int64_t num_blocks) override; - bool reserve_blocks(int64_t num_blocks) override; - void unreserve(int64_t num_blocks, int64_t allocated) override; - int64_t get_reserved_blocks() override; - int64_t get_used_blocks() override; - virtual int64_t get_used_blocks_adj(); - int64_t size() override { - return m_total_blocks; - } - using BitMapArea::alloc_blocks_dis; //non-wait version - - virtual int64_t alloc_blocks_dis_int(int64_t num_blocks, int64_t min_alloc, int64_t hint, - int64_t blk_off, AllocatorExtentList *block_list); - int64_t alloc_blocks_dis(int64_t num_blocks, int64_t min_alloc, int64_t hint, - int64_t blk_off, AllocatorExtentList *block_list) override; - virtual void set_blocks_used_int(int64_t start_block, int64_t num_blocks); - void set_blocks_used(int64_t start_block, int64_t num_blocks) override; - - virtual void free_blocks_int(int64_t start_block, int64_t num_blocks); - void free_blocks(int64_t start_block, int64_t num_blocks) override; - void dump_state(CephContext* cct, int& count) override; -}; - -class BitMapAreaLeaf: public BitMapAreaIN{ - -private: - void init(CephContext* cct, int64_t total_blocks, int64_t zone_size_block, - bool def); - -public: - MEMPOOL_CLASS_HELPERS(); - static int64_t count; - static void incr_count() { count++;} - BitMapAreaLeaf(CephContext* cct) : BitMapAreaIN(cct) { } - BitMapAreaLeaf(CephContext* cct, int64_t zone_num, int64_t total_blocks); - BitMapAreaLeaf(CephContext* cct, int64_t zone_num, int64_t total_blocks, - bool def); - - using BitMapAreaIN::child_check_n_lock; - bool child_check_n_lock(BitMapArea *child, int64_t required) override { - ceph_abort(); - return false; - } - - bool child_check_n_lock(BitMapZone* child, int64_t required, bool lock); - - int64_t alloc_blocks_int(int64_t num_blocks, int64_t hint, int64_t *start_block); - int64_t alloc_blocks_dis_int(int64_t num_blocks, int64_t min_alloc, int64_t hint, - int64_t blk_off, AllocatorExtentList *block_list) override; - void free_blocks_int(int64_t start_block, int64_t num_blocks) override; - - ~BitMapAreaLeaf() override; -}; - - -typedef enum bmap_alloc_mode { - SERIAL = 1, - CONCURRENT = 2, -} bmap_alloc_mode_t; - -class BitAllocator:public BitMapAreaIN{ -private: - CephContext* const cct; - bmap_alloc_mode_t m_alloc_mode; - std::mutex m_serial_mutex; - pthread_rwlock_t m_rw_lock; - BitAllocatorStats *m_stats; - bool m_is_stats_on; - int64_t m_extra_blocks; - - bool is_stats_on() { - return m_is_stats_on; - } - - using BitMapArea::child_check_n_lock; - bool child_check_n_lock(BitMapArea *child, int64_t required) override; - void child_unlock(BitMapArea *child) override; - - void serial_lock(); - bool try_serial_lock(); - void serial_unlock(); - void lock_excl() override; - void lock_shared() override; - bool try_lock(); - void unlock() override; - - bool check_input(int64_t num_blocks); - bool check_input_dis(int64_t num_blocks); - void init_check(int64_t total_blocks, int64_t zone_size_block, - bmap_alloc_mode_t mode, bool def, bool stats_on); - int64_t alloc_blocks_dis_work(int64_t num_blocks, int64_t min_alloc, int64_t hint, AllocatorExtentList *block_list, bool reserved); - - int64_t alloc_blocks_dis_int(int64_t num_blocks, int64_t min_alloc, - int64_t hint, int64_t area_blk_off, AllocatorExtentList *block_list) override; - -public: - MEMPOOL_CLASS_HELPERS(); - - BitAllocator(CephContext* cct, int64_t total_blocks, - int64_t zone_size_block, bmap_alloc_mode_t mode); - BitAllocator(CephContext* cct, int64_t total_blocks, int64_t zone_size_block, - bmap_alloc_mode_t mode, bool def); - BitAllocator(CephContext* cct, int64_t total_blocks, int64_t zone_size_block, - bmap_alloc_mode_t mode, bool def, bool stats_on); - ~BitAllocator() override; - void shutdown() override; - using BitMapAreaIN::alloc_blocks_dis; //Wait version - - void free_blocks(int64_t start_block, int64_t num_blocks) override; - void set_blocks_used(int64_t start_block, int64_t num_blocks) override; - void unreserve_blocks(int64_t blocks); - - int64_t alloc_blocks_dis_res(int64_t num_blocks, int64_t min_alloc, int64_t hint, AllocatorExtentList *block_list); - - void free_blocks_dis(int64_t num_blocks, AllocatorExtentList *block_list); - bool is_allocated_dis(AllocatorExtentList *blocks, int64_t num_blocks); - - int64_t total_blocks() const { - return m_total_blocks - m_extra_blocks; - } - int64_t get_used_blocks() override { - return (BitMapAreaIN::get_used_blocks_adj() - m_extra_blocks); - } - - BitAllocatorStats *get_stats() { - return m_stats; - } - void dump(); -}; - -#endif //End of file diff --git a/src/os/bluestore/BitMapAllocator.cc b/src/os/bluestore/BitMapAllocator.cc deleted file mode 100644 index 823992216f3a9..0000000000000 --- a/src/os/bluestore/BitMapAllocator.cc +++ /dev/null @@ -1,226 +0,0 @@ -// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- -// vim: ts=8 sw=2 smarttab -/* - * Bitmap based in-memory allocator. - * Author: Ramesh Chander, Ramesh.Chander@sandisk.com - * - */ - -#include "BitAllocator.h" - -#include "BitMapAllocator.h" -#include "bluestore_types.h" -#include "common/debug.h" - -#define dout_context cct -#define dout_subsys ceph_subsys_bluestore -#undef dout_prefix -#define dout_prefix *_dout << "bitmapalloc:" - - -BitMapAllocator::BitMapAllocator(CephContext* cct, int64_t device_size, - int64_t block_size) - : cct(cct) -{ - if (!ISP2(block_size)) { - derr << __func__ << " block_size " << block_size - << " not power of 2 aligned!" - << dendl; - assert(ISP2(block_size)); - return; - } - - int64_t zone_size_blks = cct->_conf->bluestore_bitmapallocator_blocks_per_zone; - if (!ISP2(zone_size_blks)) { - derr << __func__ << " zone_size " << zone_size_blks - << " not power of 2 aligned!" - << dendl; - assert(ISP2(zone_size_blks)); - return; - } - - int64_t span_size = cct->_conf->bluestore_bitmapallocator_span_size; - if (!ISP2(span_size)) { - derr << __func__ << " span_size " << span_size - << " not power of 2 aligned!" - << dendl; - assert(ISP2(span_size)); - return; - } - - m_block_size = block_size; - m_total_size = P2ALIGN(device_size, block_size); - m_bit_alloc = new BitAllocator(cct, device_size / block_size, - zone_size_blks, CONCURRENT, true); - if (!m_bit_alloc) { - derr << __func__ << " Unable to intialize Bit Allocator" << dendl; - assert(m_bit_alloc); - } - dout(10) << __func__ << " instance " << (uint64_t) this - << " size 0x" << std::hex << device_size << std::dec - << dendl; -} - -BitMapAllocator::~BitMapAllocator() -{ - delete m_bit_alloc; -} - -void BitMapAllocator::insert_free(uint64_t off, uint64_t len) -{ - dout(20) << __func__ << " instance " << (uint64_t) this - << " off 0x" << std::hex << off - << " len 0x" << len << std::dec - << dendl; - - assert(!(off % m_block_size)); - assert(!(len % m_block_size)); - - m_bit_alloc->free_blocks(off / m_block_size, - len / m_block_size); -} - -int64_t BitMapAllocator::allocate( - uint64_t want_size, uint64_t alloc_unit, uint64_t max_alloc_size, - int64_t hint, PExtentVector *extents) -{ - - assert(!(alloc_unit % m_block_size)); - assert(alloc_unit); - - assert(!max_alloc_size || max_alloc_size >= alloc_unit); - - { - int nblks = want_size / m_block_size; // apply floor - assert(!(want_size % m_block_size)); - dout(10) << __func__ << " instance " << (uint64_t) this - << " num_used " << m_bit_alloc->get_used_blocks() - << " total " << m_bit_alloc->total_blocks() - << dendl; - - if (!m_bit_alloc->reserve_blocks(nblks)) { - return -ENOSPC; - } - } - - - dout(10) << __func__ <<" instance "<< (uint64_t) this - << " want_size " << want_size - << " alloc_unit " << alloc_unit - << " hint " << hint - << dendl; - hint = hint % m_total_size; // make hint error-tolerant - auto res = allocate_dis(want_size, alloc_unit / m_block_size, - max_alloc_size, hint / m_block_size, extents); - - if (res < want_size) { - auto unused = want_size - res; - int nblks = unused / m_block_size; - assert(!(unused % m_block_size)); - - dout(10) << __func__ << " instance " << (uint64_t) this - << " unused " << nblks - << " num used " << m_bit_alloc->get_used_blocks() - << " total " << m_bit_alloc->total_blocks() - << dendl; - - m_bit_alloc->unreserve_blocks(nblks); - } - return res; -} - -int64_t BitMapAllocator::allocate_dis( - uint64_t want_size, uint64_t alloc_unit, uint64_t max_alloc_size, - int64_t hint, PExtentVector *extents) -{ - AllocatorExtentList block_list(extents, m_block_size, max_alloc_size); - int64_t nblks = (want_size + m_block_size - 1) / m_block_size; - int64_t num = 0; - - num = m_bit_alloc->alloc_blocks_dis_res(nblks, alloc_unit, hint, &block_list); - if (num == 0) { - return -ENOSPC; - } - - return num * m_block_size; -} - -void BitMapAllocator::release( - const interval_set& release_set) -{ - for (interval_set::const_iterator p = release_set.begin(); - p != release_set.end(); - ++p) { - const auto offset = p.get_start(); - const auto length = p.get_len(); - dout(10) << __func__ << " 0x" - << std::hex << offset << "~" << length << std::dec - << dendl; - insert_free(offset, length); - } -} - -uint64_t BitMapAllocator::get_free() -{ - assert(m_bit_alloc->total_blocks() >= m_bit_alloc->get_used_blocks()); - return (( - m_bit_alloc->total_blocks() - m_bit_alloc->get_used_blocks()) * - m_block_size); -} - -void BitMapAllocator::dump() -{ - dout(0) << __func__ << " instance " << this << dendl; - m_bit_alloc->dump(); -} - -void BitMapAllocator::init_add_free(uint64_t offset, uint64_t length) -{ - dout(10) << __func__ << " instance " << (uint64_t) this - << " offset 0x" << std::hex << offset - << " length 0x" << length << std::dec - << dendl; - uint64_t size = m_bit_alloc->size() * m_block_size; - - uint64_t offset_adj = ROUND_UP_TO(offset, m_block_size); - uint64_t length_adj = ((length - (offset_adj - offset)) / - m_block_size) * m_block_size; - - if ((offset_adj + length_adj) > size) { - assert(((offset_adj + length_adj) - m_block_size) < size); - length_adj = size - offset_adj; - } - - insert_free(offset_adj, length_adj); -} - -void BitMapAllocator::init_rm_free(uint64_t offset, uint64_t length) -{ - dout(10) << __func__ << " instance " << (uint64_t) this - << " offset 0x" << std::hex << offset - << " length 0x" << length << std::dec - << dendl; - - // we use the same adjustment/alignment that init_add_free does - // above so that we can yank back some of the space. - uint64_t offset_adj = ROUND_UP_TO(offset, m_block_size); - uint64_t length_adj = ((length - (offset_adj - offset)) / - m_block_size) * m_block_size; - - assert(!(offset_adj % m_block_size)); - assert(!(length_adj % m_block_size)); - - int64_t first_blk = offset_adj / m_block_size; - int64_t count = length_adj / m_block_size; - - if (count) - m_bit_alloc->set_blocks_used(first_blk, count); -} - - -void BitMapAllocator::shutdown() -{ - dout(10) << __func__ << " instance " << (uint64_t) this << dendl; - m_bit_alloc->shutdown(); -} - diff --git a/src/os/bluestore/BitMapAllocator.h b/src/os/bluestore/BitMapAllocator.h deleted file mode 100644 index 8283a68c5bad5..0000000000000 --- a/src/os/bluestore/BitMapAllocator.h +++ /dev/null @@ -1,47 +0,0 @@ -// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- -// vim: ts=8 sw=2 smarttab - -#ifndef CEPH_OS_BLUESTORE_BITMAPALLOCATOR_H -#define CEPH_OS_BLUESTORE_BITMAPALLOCATOR_H - -#include - -#include "Allocator.h" -#include "BitAllocator.h" - -class BitMapAllocator : public Allocator { - CephContext* cct; - - int64_t m_block_size; - int64_t m_total_size; - - BitAllocator *m_bit_alloc; // Bit allocator instance - - void insert_free(uint64_t offset, uint64_t len); - - int64_t allocate_dis( - uint64_t want_size, uint64_t alloc_unit, uint64_t max_alloc_size, - int64_t hint, PExtentVector *extents); - -public: - BitMapAllocator(CephContext* cct, int64_t device_size, int64_t block_size); - ~BitMapAllocator() override; - - int64_t allocate( - uint64_t want_size, uint64_t alloc_unit, uint64_t max_alloc_size, - int64_t hint, PExtentVector *extents) override; - - void release( - const interval_set& release_set) override; - - uint64_t get_free() override; - - void dump() override; - - void init_add_free(uint64_t offset, uint64_t length) override; - void init_rm_free(uint64_t offset, uint64_t length) override; - - void shutdown() override; -}; - -#endif diff --git a/src/test/objectstore/BitAllocator_test.cc b/src/test/objectstore/BitAllocator_test.cc deleted file mode 100644 index d4df51606effd..0000000000000 --- a/src/test/objectstore/BitAllocator_test.cc +++ /dev/null @@ -1,589 +0,0 @@ -// -*- 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; - PExtentVector extents; - AllocatorExtentList block_list(&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; - PExtentVector extents; - AllocatorExtentList block_list(&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; - PExtentVector 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(); - AllocatorExtentList block_list(&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 zone; - } - } - - //allocation in loop - { - extents.clear(); - AllocatorExtentList block_list(&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 zone; - } - - { - extents.clear(); - AllocatorExtentList block_list(&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); - - extents.clear(); - block_list = AllocatorExtentList(&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; - PExtentVector extents; - AllocatorExtentList block_list(&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, std::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; - PExtentVector extents; - - AllocatorExtentList block_list(&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 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; - PExtentVector extents; - - AllocatorExtentList block_list(&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; - - PExtentVector extents; - AllocatorExtentList block_list(&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); - } - } -} diff --git a/src/test/objectstore/CMakeLists.txt b/src/test/objectstore/CMakeLists.txt index 691c08b5ca71d..3705d2c03b58f 100644 --- a/src/test/objectstore/CMakeLists.txt +++ b/src/test/objectstore/CMakeLists.txt @@ -108,14 +108,6 @@ add_ceph_unittest(unittest_rocksdb_option ${CMAKE_RUNTIME_OUTPUT_DIRECTORY}/unit target_link_libraries(unittest_rocksdb_option global os ${BLKID_LIBRARIES}) if(HAVE_LIBAIO) - # unittest_bit_alloc - add_executable(unittest_bit_alloc - BitAllocator_test.cc - $ - ) - add_ceph_unittest(unittest_bit_alloc ${CMAKE_RUNTIME_OUTPUT_DIRECTORY}/unittest_bit_alloc) - target_link_libraries(unittest_bit_alloc os global) - add_executable(unittest_alloc Allocator_test.cc -- 2.39.5