4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
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.
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.
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
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
40 #ifndef NBDKIT_BITMAP_H
41 #define NBDKIT_BITMAP_H
47 #include <nbdkit-plugin.h>
49 #include "ispowerof2.h"
51 /* This is the bitmap structure. */
53 unsigned blksize
; /* Block size. */
54 uint8_t bpb
; /* Bits per block (1, 2, 4, 8 only). */
55 /* bpb = 1 << bitshift ibpb = 8 / bpb
61 uint8_t bitshift
, ibpb
;
63 uint8_t *bitmap
; /* The bitmap. */
64 size_t size
; /* Size of bitmap in bytes. */
67 static inline void __attribute__ ((__nonnull__ (1)))
68 bitmap_init (struct bitmap
*bm
, unsigned blocksize
, unsigned bpb
)
70 assert (is_power_of_2 (blocksize
));
71 bm
->blksize
= blocksize
;
73 /* bpb can be 1, 2, 4 or 8 only. */
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;
88 /* Only frees the bitmap itself, since it is assumed that the struct
89 * bitmap is statically allocated.
92 bitmap_free (struct bitmap
*bm
)
98 /* Resize the bitmap to the virtual disk size in bytes.
99 * Returns -1 on error, setting nbdkit_error.
101 extern int bitmap_resize (struct bitmap
*bm
, uint64_t new_size
)
102 __attribute__ ((__nonnull__ (1)));
104 /* Clear the bitmap (set everything to zero). */
105 static inline void __attribute__ ((__nonnull__ (1)))
106 bitmap_clear (struct bitmap
*bm
)
108 memset (bm
->bitmap
, 0, bm
->size
);
111 /* This macro calculates the byte offset in the bitmap and which
112 * bit/mask we are addressing within that byte.
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
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
125 /* Return the bit(s) associated with the given block.
126 * If the request is out of range, returns the default value.
128 static inline unsigned __attribute__ ((__nonnull__ (1)))
129 bitmap_get_blk (const struct bitmap
*bm
, uint64_t blk
, unsigned default_
)
131 BITMAP_OFFSET_BIT_MASK (bm
, blk
);
133 if (blk_offset
>= bm
->size
) {
134 nbdkit_debug ("bitmap_get: block number is out of range");
138 return (bm
->bitmap
[blk_offset
] & mask
) >> blk_bit
;
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_
)
145 return bitmap_get_blk (bm
, offset
/ bm
->blksize
, default_
);
148 /* Set the bit(s) associated with the given block.
149 * If out of range, it is ignored.
151 static inline void __attribute__ ((__nonnull__ (1)))
152 bitmap_set_blk (const struct bitmap
*bm
, uint64_t blk
, unsigned v
)
154 BITMAP_OFFSET_BIT_MASK (bm
, blk
);
156 if (blk_offset
>= bm
->size
) {
157 nbdkit_debug ("bitmap_set: block number is out of range");
161 bm
->bitmap
[blk_offset
] &= ~mask
;
162 bm
->bitmap
[blk_offset
] |= v
<< blk_bit
;
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
)
169 return bitmap_set_blk (bm
, offset
/ bm
->blksize
, v
);
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))
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
180 extern int64_t bitmap_next (const struct bitmap
*bm
, uint64_t blk
)
181 __attribute__ ((__nonnull__ (1)));
183 #endif /* NBDKIT_BITMAP_H */