ceph/src/os/bluestore/simple_bitmap.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * Author: Gabriel BenHanokh <gbenhano@redhat.com>
   7  *
   8  * This is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License version 2.1, as published by the Free Software
  11  * Foundation.  See file COPYING.
  12  *
  13  */
  14 #pragma once
  15 #include <cstdint>
  16 #include <iostream>
  17 #include <string>
  18 #include <cstring>
  19 #include <cmath>
  20 #include <iomanip>
  21
  22 #include "include/ceph_assert.h"
  23
  24 struct extent_t {
  25   uint64_t offset;
  26   uint64_t length;
  27   bool operator==(const extent_t& other) const {
  28     return (this->offset == other.offset && this->length == other.length);
  29   }
  30 };
  31
  32 class SimpleBitmap {
  33 public:
  34   SimpleBitmap(CephContext *_cct, uint64_t num_bits);
  35   ~SimpleBitmap();
  36
  37   SimpleBitmap(const SimpleBitmap&) = delete;
  38   SimpleBitmap& operator=(const SimpleBitmap&) = delete;
  39
  40
  41   // set a bit range range of @length starting at @offset
  42   bool     set(uint64_t offset, uint64_t length);
  43   // clear a bit range range of @length starting at @offset
  44   bool     clr(uint64_t offset, uint64_t length);
  45
  46   // returns a copy of the next set extent starting at @offset
  47   extent_t get_next_set_extent(uint64_t offset);
  48
  49   // returns a copy of the next clear extent starting at @offset
  50   extent_t get_next_clr_extent(uint64_t offset);
  51
  52   //----------------------------------------------------------------------------
  53   inline uint64_t get_size() {
  54     return m_num_bits;
  55   }
  56
  57   //----------------------------------------------------------------------------
  58   // clears all bits in the bitmap
  59   inline void clear_all() {
  60     std::memset(m_arr, 0, words_to_bytes(m_word_count));
  61   }
  62
  63   //----------------------------------------------------------------------------
  64   // sets all bits in the bitmap
  65   inline void set_all() {
  66     std::memset(m_arr, 0xFF,  words_to_bytes(m_word_count));
  67     // clear bits in the last word past the last legal bit
  68     uint64_t incomplete_word_bit_offset = (m_num_bits & BITS_IN_WORD_MASK);
  69     if (incomplete_word_bit_offset) {
  70       uint64_t clr_mask   = ~(FULL_MASK << incomplete_word_bit_offset);
  71       m_arr[m_word_count - 1] &= clr_mask;
  72     }
  73   }
  74
  75   //----------------------------------------------------------------------------
  76   bool bit_is_set(uint64_t offset) {
  77     if (offset < m_num_bits) {
  78       auto [word_index, bit_offset] = split(offset);
  79       uint64_t mask       = 1ULL << bit_offset;
  80       return (m_arr[word_index] & mask);
  81     } else {
  82       ceph_assert(offset < m_num_bits);
  83       return false;
  84     }
  85   }
  86
  87   //----------------------------------------------------------------------------
  88   bool bit_is_clr(uint64_t offset) {
  89     if (offset < m_num_bits) {
  90       auto [word_index, bit_offset] = split(offset);
  91       uint64_t mask       = 1ULL << bit_offset;
  92       return ( (m_arr[word_index] & mask) == 0 );
  93     } else {
  94       ceph_assert(offset < m_num_bits);
  95       return false;
  96     }
  97   }
  98
  99 private:
 100   //----------------------------------------------------------------------------
 101   static inline std::pair<uint64_t, uint64_t> split(uint64_t offset) {
 102     return { offset_to_index(offset), (offset & BITS_IN_WORD_MASK) };
 103   }
 104
 105   //---------------------------------------------------------------------------
 106   static inline uint64_t offset_to_index(uint64_t offset) {
 107     return offset >> BITS_IN_WORD_SHIFT;
 108   }
 109
 110   //---------------------------------------------------------------------------
 111   static inline uint64_t index_to_offset(uint64_t index) {
 112     return index << BITS_IN_WORD_SHIFT;
 113   }
 114
 115   //---------------------------------------------------------------------------
 116   static  inline uint64_t bits_to_words(uint64_t bit_count) {
 117     return bit_count >> BITS_IN_WORD_SHIFT;
 118   }
 119
 120   //---------------------------------------------------------------------------
 121   static  inline uint64_t words_to_bits(uint64_t words_count) {
 122     return words_count << BITS_IN_WORD_SHIFT;
 123   }
 124
 125   //---------------------------------------------------------------------------
 126   static  inline uint64_t bytes_to_words(uint64_t byte_count) {
 127     return byte_count >> BYTES_IN_WORD_SHIFT;
 128   }
 129
 130   //---------------------------------------------------------------------------
 131   static  inline uint64_t words_to_bytes(uint64_t words_count) {
 132     return (words_count << BYTES_IN_WORD_SHIFT);
 133   }
 134
 135   constexpr static uint64_t      BYTES_IN_WORD       = sizeof(uint64_t);
 136   constexpr static uint64_t      BYTES_IN_WORD_SHIFT = 3;
 137   constexpr static uint64_t      BITS_IN_WORD        = (BYTES_IN_WORD * 8);
 138   constexpr static uint64_t      BITS_IN_WORD_MASK   = (BITS_IN_WORD - 1);
 139   constexpr static uint64_t      BITS_IN_WORD_SHIFT  = 6;
 140   constexpr static uint64_t      FULL_MASK           = (~((uint64_t)0));
 141
 142   CephContext *cct;
 143   uint64_t    *m_arr;
 144   uint64_t     m_num_bits;
 145   uint64_t     m_word_count;
 146 };