common/bitmap/bitmap.h

   1 /* nbdkit
   2  * Copyright Red Hat
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  * * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * * Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  *
  15  * * Neither the name of Red Hat nor the names of its contributors may be
  16  * used to endorse or promote products derived from this software without
  17  * specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  22  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  26  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  27  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 /* This is a very simple structure for creating a bitmap associated
  34  * with a virtual disk.  1, 2, 4 or 8 bits can be associated with each
  35  * block of the disk.  You can choose the number of bits and block
  36  * size when creating the bitmap.  Entries in the bitmap are
  37  * initialized to 0.
  38  */
  39
  40 #ifndef NBDKIT_BITMAP_H
  41 #define NBDKIT_BITMAP_H
  42
  43 #include <stdint.h>
  44 #include <string.h>
  45 #include <assert.h>
  46
  47 #include <nbdkit-plugin.h>
  48
  49 #include "ispowerof2.h"
  50
  51 /* This is the bitmap structure. */
  52 struct bitmap {
  53   unsigned blksize;            /* Block size. */
  54   uint8_t bpb;                 /* Bits per block (1, 2, 4, 8 only). */
  55   /* bpb = 1 << bitshift   ibpb = 8 / bpb
  56      1          0          8
  57      2          1          4
  58      4          2          2
  59      8          3          1
  60   */
  61   uint8_t bitshift, ibpb;
  62
  63   uint8_t *bitmap;              /* The bitmap. */
  64   size_t size;                  /* Size of bitmap in bytes. */
  65 };
  66
  67 static inline void __attribute__ ((__nonnull__ (1)))
  68 bitmap_init (struct bitmap *bm, unsigned blocksize, unsigned bpb)
  69 {
  70   assert (is_power_of_2 (blocksize));
  71   bm->blksize = blocksize;
  72
  73   /* bpb can be 1, 2, 4 or 8 only. */
  74   bm->bpb = bpb;
  75   switch (bpb) {
  76   case 1: bm->bitshift = 0; break;
  77   case 2: bm->bitshift = 1; break;
  78   case 4: bm->bitshift = 2; break;
  79   case 8: bm->bitshift = 3; break;
  80   default: abort ();
  81   }
  82   bm->ibpb = 8/bpb;
  83
  84   bm->bitmap = NULL;
  85   bm->size = 0;
  86 }
  87
  88 /* Only frees the bitmap itself, since it is assumed that the struct
  89  * bitmap is statically allocated.
  90  */
  91 static inline void
  92 bitmap_free (struct bitmap *bm)
  93 {
  94   if (bm)
  95     free (bm->bitmap);
  96 }
  97
  98 /* Resize the bitmap to the virtual disk size in bytes.
  99  * Returns -1 on error, setting nbdkit_error.
 100  */
 101 extern int bitmap_resize (struct bitmap *bm, uint64_t new_size)
 102   __attribute__ ((__nonnull__ (1)));
 103
 104 /* Clear the bitmap (set everything to zero). */
 105 static inline void  __attribute__ ((__nonnull__ (1)))
 106 bitmap_clear (struct bitmap *bm)
 107 {
 108   memset (bm->bitmap, 0, bm->size);
 109 }
 110
 111 /* This macro calculates the byte offset in the bitmap and which
 112  * bit/mask we are addressing within that byte.
 113  *
 114  * bpb     blk_offset         blk_bit          mask
 115  * 1       blk >> 3           0,1,2,...,7      any single bit
 116  * 2       blk >> 2           0, 2, 4 or 6     0x03, 0x0c, 0x30 or 0xc0
 117  * 4       blk >> 1           0 or 4           0x0f or 0xf0
 118  * 8       blk >> 0           always 0         always 0xff
 119  */
 120 #define BITMAP_OFFSET_BIT_MASK(bm, blk)                         \
 121   uint64_t blk_offset = (blk) >> (3 - (bm)->bitshift);          \
 122   unsigned blk_bit = (bm)->bpb * ((blk) & ((bm)->ibpb - 1));    \
 123   unsigned mask = ((1 << (bm)->bpb) - 1) << blk_bit
 124
 125 /* Return the bit(s) associated with the given block.
 126  * If the request is out of range, returns the default value.
 127  */
 128 static inline unsigned __attribute__ ((__nonnull__ (1)))
 129 bitmap_get_blk (const struct bitmap *bm, uint64_t blk, unsigned default_)
 130 {
 131   BITMAP_OFFSET_BIT_MASK (bm, blk);
 132
 133   if (blk_offset >= bm->size) {
 134     nbdkit_debug ("bitmap_get: block number is out of range");
 135     return default_;
 136   }
 137
 138   return (bm->bitmap[blk_offset] & mask) >> blk_bit;
 139 }
 140
 141 /* As above but works with virtual disk offset in bytes. */
 142 static inline unsigned __attribute__ ((__nonnull__ (1)))
 143 bitmap_get (const struct bitmap *bm, uint64_t offset, unsigned default_)
 144 {
 145   return bitmap_get_blk (bm, offset / bm->blksize, default_);
 146 }
 147
 148 /* Set the bit(s) associated with the given block.
 149  * If out of range, it is ignored.
 150  */
 151 static inline void __attribute__ ((__nonnull__ (1)))
 152 bitmap_set_blk (const struct bitmap *bm, uint64_t blk, unsigned v)
 153 {
 154   BITMAP_OFFSET_BIT_MASK (bm, blk);
 155
 156   if (blk_offset >= bm->size) {
 157     nbdkit_debug ("bitmap_set: block number is out of range");
 158     return;
 159   }
 160
 161   bm->bitmap[blk_offset] &= ~mask;
 162   bm->bitmap[blk_offset] |= v << blk_bit;
 163 }
 164
 165 /* As above bit works with virtual disk offset in bytes. */
 166 static inline void __attribute__ ((__nonnull__ (1)))
 167 bitmap_set (const struct bitmap *bm, uint64_t offset, unsigned v)
 168 {
 169   return bitmap_set_blk (bm, offset / bm->blksize, v);
 170 }
 171
 172 /* Iterate over blocks represented in the bitmap. */
 173 #define bitmap_for(bm, /* uint64_t */ blknum)                           \
 174   for ((blknum) = 0; (blknum) < (bm)->size * (bm)->ibpb; ++(blknum))
 175
 176 /* Find the next non-zero block in the bitmap, starting at ‘blk’.
 177  * Returns -1 if the bitmap is all zeroes from blk to the end of the
 178  * bitmap.
 179  */
 180 extern int64_t bitmap_next (const struct bitmap *bm, uint64_t blk)
 181   __attribute__ ((__nonnull__ (1)));
 182
 183 #endif /* NBDKIT_BITMAP_H */