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
40 #include <nbdkit-plugin.h>
44 #include "nextnonzero.h"
47 bitmap_resize (struct bitmap
*bm
, uint64_t new_size
)
50 const size_t old_bm_size
= bm
->size
;
51 uint64_t new_bm_size_u64
;
54 new_bm_size_u64
= DIV_ROUND_UP (new_size
,
55 bm
->blksize
* UINT64_C (8) / bm
->bpb
);
56 if (new_bm_size_u64
> SIZE_MAX
) {
57 nbdkit_error ("bitmap too large for this architecture");
60 new_bm_size
= (size_t) new_bm_size_u64
;
62 if (new_bm_size
> 0) {
63 new_bitmap
= realloc (bm
->bitmap
, new_bm_size
);
64 if (new_bitmap
== NULL
) {
65 nbdkit_error ("realloc: %m");
73 bm
->bitmap
= new_bitmap
;
74 bm
->size
= new_bm_size
;
75 if (old_bm_size
< new_bm_size
)
76 memset (&bm
->bitmap
[old_bm_size
], 0, new_bm_size
-old_bm_size
);
78 nbdkit_debug ("bitmap resized to %zu bytes", new_bm_size
);
84 bitmap_next (const struct bitmap
*bm
, uint64_t blk
)
86 uint64_t limit
= bm
->size
* bm
->ibpb
;
89 /* Align to the next byte boundary. */
90 for (; blk
< limit
&& (blk
& (bm
->ibpb
-1)) != 0; ++blk
) {
91 if (bitmap_get_blk (bm
, blk
, 0) != 0)
97 /* Now we're at a byte boundary we can use a fast string function to
98 * find the next non-zero byte.
100 p
= &bm
->bitmap
[blk
>> (3 - bm
->bitshift
)];
101 p
= (const uint8_t *) next_non_zero ((const char *) p
,
102 &bm
->bitmap
[bm
->size
] - p
);
106 /* Now check the non-zero byte to find out which bit (ie. block) is set. */
107 blk
= (p
- bm
->bitmap
) << (3 - bm
->bitshift
);
108 for (; blk
< limit
; ++blk
) {
109 if (bitmap_get_blk (bm
, blk
, 0) != 0)
113 /* Should never be reached. */