--- /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.
+ * 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 <assert.h>
+#include "bluestore_types.h"
+#include "common/debug.h"
+#include <math.h>
+
+#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;
+
+
+
+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<int16_t>::max());
+ alloc_assert(total_blocks < std::numeric_limits<int32_t>::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,
+ ExtentList *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 <BmapEntry> iter = BitMapEntityIter<BmapEntry>(
+ &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 <BmapEntry> iter = BitMapEntityIter<BmapEntry>(
+ &m_bmap_vec, 0);
+ dout(0) << __func__ << " zone " << count << " dump start " << dendl;
+ while ((bmap = static_cast<BmapEntry *>(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<int16_t>::max());
+
+ m_child_size_blocks = level_factor;
+
+ std::vector<BitMapArea*> 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<std::mutex> 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<std::mutex> 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<std::mutex> l(m_blocks_lock);
+ return m_used_blocks;
+}
+
+int64_t BitMapAreaIN::get_used_blocks_adj()
+{
+ std::lock_guard<std::mutex> l(m_blocks_lock);
+ return m_used_blocks - m_reserved_blocks;
+}
+
+bool BitMapAreaIN::reserve_blocks(int64_t num)
+{
+ bool res = false;
+ std::lock_guard<std::mutex> 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<std::mutex> 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<std::mutex> 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<BitMapArea *>(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, ExtentList *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<BitMapArea *>(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, ExtentList *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, ExtentList *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<BitMapArea *>(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<BitMapArea *>(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<BitMapArea *>(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<BitMapArea*> 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<BitMapArea *>(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, ExtentList *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<BitMapZone*>(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<BitMapArea *>(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<BitMapArea *>(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, ExtentList *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, ExtentList *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, ExtentList *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(ExtentList *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, ExtentList *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();
+}
Code Review / stor4nfv.git / blobdiff