2 * gen_bitmap.c --- Generic (32-bit) bitmap routines
4 * Copyright (C) 2001 Theodore Ts'o.
7 * This file may be redistributed under the terms of the GNU Public
24 #include <sys/types.h>
30 struct ext2fs_struct_generic_bitmap {
37 errcode_t base_error_code;
42 * Used by previously inlined function, so we have to export this and
43 * not change the function signature
45 void ext2fs_warn_bitmap2(ext2fs_generic_bitmap bitmap,
46 int code, unsigned long arg)
49 if (bitmap->description)
50 com_err(0, bitmap->base_error_code+code,
51 "#%lu for %s", arg, bitmap->description);
53 com_err(0, bitmap->base_error_code + code, "#%lu", arg);
57 static errcode_t check_magic(ext2fs_generic_bitmap bitmap)
59 if (!bitmap || !((bitmap->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) ||
60 (bitmap->magic == EXT2_ET_MAGIC_INODE_BITMAP) ||
61 (bitmap->magic == EXT2_ET_MAGIC_BLOCK_BITMAP)))
62 return EXT2_ET_MAGIC_GENERIC_BITMAP;
66 errcode_t ext2fs_make_generic_bitmap(errcode_t magic, ext2_filsys fs,
67 __u32 start, __u32 end, __u32 real_end,
68 const char *descr, char *init_map,
69 ext2fs_generic_bitmap *ret)
71 ext2fs_generic_bitmap bitmap;
75 retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
80 bitmap->magic = magic;
82 bitmap->start = start;
84 bitmap->real_end = real_end;
86 case EXT2_ET_MAGIC_INODE_BITMAP:
87 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
89 case EXT2_ET_MAGIC_BLOCK_BITMAP:
90 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
93 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
96 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
98 ext2fs_free_mem(&bitmap);
101 strcpy(bitmap->description, descr);
103 bitmap->description = 0;
105 size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
106 retval = ext2fs_get_mem(size, &bitmap->bitmap);
108 ext2fs_free_mem(&bitmap->description);
109 ext2fs_free_mem(&bitmap);
114 memcpy(bitmap->bitmap, init_map, size);
116 memset(bitmap->bitmap, 0, size);
121 errcode_t ext2fs_allocate_generic_bitmap(__u32 start,
125 ext2fs_generic_bitmap *ret)
127 return ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_GENERIC_BITMAP, 0,
128 start, end, real_end, descr, 0, ret);
131 errcode_t ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap src,
132 ext2fs_generic_bitmap *dest)
134 return (ext2fs_make_generic_bitmap(src->magic, src->fs,
135 src->start, src->end,
137 src->description, src->bitmap,
141 void ext2fs_free_generic_bitmap(ext2fs_inode_bitmap bitmap)
143 if (check_magic(bitmap))
147 if (bitmap->description) {
148 ext2fs_free_mem(&bitmap->description);
149 bitmap->description = 0;
151 if (bitmap->bitmap) {
152 ext2fs_free_mem(&bitmap->bitmap);
155 ext2fs_free_mem(&bitmap);
158 int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
161 if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
162 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno);
165 return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap);
168 int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
171 if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
172 ext2fs_warn_bitmap2(bitmap, EXT2FS_MARK_ERROR, bitno);
175 return ext2fs_set_bit(bitno - bitmap->start, bitmap->bitmap);
178 int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
181 if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
182 ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, bitno);
185 return ext2fs_clear_bit(bitno - bitmap->start, bitmap->bitmap);
188 __u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap)
190 return bitmap->start;
193 __u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap)
198 void ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap)
200 if (check_magic(bitmap))
203 memset(bitmap->bitmap, 0,
204 (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
207 errcode_t ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap bitmap,
208 errcode_t magic, errcode_t neq,
209 ext2_ino_t end, ext2_ino_t *oend)
211 EXT2_CHECK_MAGIC(bitmap, magic);
213 if (end > bitmap->real_end)
221 errcode_t ext2fs_resize_generic_bitmap(errcode_t magic,
222 __u32 new_end, __u32 new_real_end,
223 ext2fs_generic_bitmap bmap)
226 size_t size, new_size;
229 if (!bmap || (bmap->magic != magic))
233 * If we're expanding the bitmap, make sure all of the new
234 * parts of the bitmap are zero.
236 if (new_end > bmap->end) {
237 bitno = bmap->real_end;
240 for (; bitno > bmap->end; bitno--)
241 ext2fs_clear_bit(bitno - bmap->start, bmap->bitmap);
243 if (new_real_end == bmap->real_end) {
248 size = ((bmap->real_end - bmap->start) / 8) + 1;
249 new_size = ((new_real_end - bmap->start) / 8) + 1;
251 if (size != new_size) {
252 retval = ext2fs_resize_mem(size, new_size, &bmap->bitmap);
257 memset(bmap->bitmap + size, 0, new_size - size);
260 bmap->real_end = new_real_end;
264 errcode_t ext2fs_compare_generic_bitmap(errcode_t magic, errcode_t neq,
265 ext2fs_generic_bitmap bm1,
266 ext2fs_generic_bitmap bm2)
270 if (!bm1 || bm1->magic != magic)
272 if (!bm2 || bm2->magic != magic)
275 if ((bm1->start != bm2->start) ||
276 (bm1->end != bm2->end) ||
277 (memcmp(bm1->bitmap, bm2->bitmap,
278 (size_t) (bm1->end - bm1->start)/8)))
281 for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
282 if (ext2fs_fast_test_block_bitmap(bm1, i) !=
283 ext2fs_fast_test_block_bitmap(bm2, i))
289 void ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap map)
293 /* Protect loop from wrap-around if map->real_end is maxed */
294 for (i=map->end+1, j = i - map->start;
295 i <= map->real_end && i > map->end;
297 ext2fs_set_bit(j, map->bitmap);
300 errcode_t ext2fs_get_generic_bitmap_range(ext2fs_generic_bitmap bmap,
302 __u32 start, __u32 num,
305 if (!bmap || (bmap->magic != magic))
308 if ((start < bmap->start) || (start+num-1 > bmap->real_end))
309 return EXT2_ET_INVALID_ARGUMENT;
311 memcpy(out, bmap->bitmap + (start >> 3), (num+7) >> 3);
315 errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,
317 __u32 start, __u32 num,
320 if (!bmap || (bmap->magic != magic))
323 if ((start < bmap->start) || (start+num-1 > bmap->real_end))
324 return EXT2_ET_INVALID_ARGUMENT;
326 memcpy(bmap->bitmap + (start >> 3), in, (num+7) >> 3);
331 * Compare @mem to zero buffer by 256 bytes.
332 * Return 1 if @mem is zeroed memory, otherwise return 0.
334 static int mem_is_zero(const char *mem, size_t len)
336 static const char zero_buf[256];
338 while (len >= sizeof(zero_buf)) {
339 if (memcmp(mem, zero_buf, sizeof(zero_buf)))
341 len -= sizeof(zero_buf);
342 mem += sizeof(zero_buf);
344 /* Deal with leftover bytes. */
346 return !memcmp(mem, zero_buf, len);
351 * Return true if all of the bits in a specified range are clear
353 static int ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap bitmap,
357 size_t start_byte, len_byte = len >> 3;
358 unsigned int start_bit, len_bit = len % 8;
364 const char *ADDR = bitmap->bitmap;
366 start -= bitmap->start;
367 start_byte = start >> 3;
368 start_bit = start % 8;
370 if (start_bit != 0) {
372 * The compared start block number or start inode number
373 * is not the first bit in a byte.
375 mark_count = 8 - start_bit;
376 if (len < 8 - start_bit) {
377 mark_count = (int)len;
378 mark_bit = len + start_bit - 1;
382 for (i = mark_count; i > 0; i--, mark_bit--)
383 first_bit |= 1 << mark_bit;
386 * Compare blocks or inodes in the first byte.
387 * If there is any marked bit, this function returns 0.
389 if (first_bit & ADDR[start_byte])
391 else if (len <= 8 - start_bit)
395 len_bit = (len - mark_count) % 8;
396 len_byte = (len - mark_count) >> 3;
400 * The compared start block number or start inode number is
401 * the first bit in a byte.
405 * The compared end block number or end inode number is
406 * not the last bit in a byte.
408 for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
409 last_bit |= 1 << mark_bit;
412 * Compare blocks or inodes in the last byte.
413 * If there is any marked bit, this function returns 0.
415 if (last_bit & ADDR[start_byte + len_byte])
417 else if (len_byte == 0)
421 /* Check whether all bytes are 0 */
422 return mem_is_zero(ADDR + start_byte, len_byte);
425 int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
426 blk_t block, int num)
428 EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_BLOCK_BITMAP);
429 if ((block < bitmap->start) || (block+num-1 > bitmap->real_end)) {
430 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
431 block, bitmap->description);
434 return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap)
438 int ext2fs_test_inode_bitmap_range(ext2fs_inode_bitmap bitmap,
439 ino_t inode, int num)
441 EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_INODE_BITMAP);
442 if ((inode < bitmap->start) || (inode+num-1 > bitmap->real_end)) {
443 ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_TEST,
444 inode, bitmap->description);
447 return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap)
451 void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
452 blk_t block, int num)
456 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
457 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
458 bitmap->description);
461 for (i=0; i < num; i++)
462 ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap);
465 void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
466 blk_t block, int num)
470 if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
471 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
472 bitmap->description);
475 for (i=0; i < num; i++)
476 ext2fs_fast_clear_bit(block + i - bitmap->start,