Home | History | Annotate | Download | only in ext2fs
      1 /*
      2  * gen_bitmap.c --- Generic (32-bit) bitmap routines
      3  *
      4  * Copyright (C) 2001 Theodore Ts'o.
      5  *
      6  * %Begin-Header%
      7  * This file may be redistributed under the terms of the GNU Library
      8  * General Public License, version 2.
      9  * %End-Header%
     10  */
     11 
     12 
     13 #include <stdio.h>
     14 #include <string.h>
     15 #if HAVE_UNISTD_H
     16 #include <unistd.h>
     17 #endif
     18 #include <fcntl.h>
     19 #include <time.h>
     20 #if HAVE_SYS_STAT_H
     21 #include <sys/stat.h>
     22 #endif
     23 #if HAVE_SYS_TYPES_H
     24 #include <sys/types.h>
     25 #endif
     26 
     27 #include "ext2_fs.h"
     28 #include "ext2fs.h"
     29 
     30 struct ext2fs_struct_generic_bitmap {
     31 	errcode_t	magic;
     32 	ext2_filsys 	fs;
     33 	__u32		start, end;
     34 	__u32		real_end;
     35 	char	*	description;
     36 	char	*	bitmap;
     37 	errcode_t	base_error_code;
     38 	__u32		reserved[7];
     39 };
     40 
     41 /*
     42  * Used by previously inlined function, so we have to export this and
     43  * not change the function signature
     44  */
     45 void ext2fs_warn_bitmap2(ext2fs_generic_bitmap bitmap,
     46 			    int code, unsigned long arg)
     47 {
     48 #ifndef OMIT_COM_ERR
     49 	if (bitmap->description)
     50 		com_err(0, bitmap->base_error_code+code,
     51 			"#%lu for %s", arg, bitmap->description);
     52 	else
     53 		com_err(0, bitmap->base_error_code + code, "#%lu", arg);
     54 #endif
     55 }
     56 
     57 static errcode_t check_magic(ext2fs_generic_bitmap bitmap)
     58 {
     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;
     63 	return 0;
     64 }
     65 
     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)
     70 {
     71 	ext2fs_generic_bitmap	bitmap;
     72 	errcode_t		retval;
     73 	size_t			size;
     74 
     75 	retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
     76 				&bitmap);
     77 	if (retval)
     78 		return retval;
     79 
     80 	bitmap->magic = magic;
     81 	bitmap->fs = fs;
     82 	bitmap->start = start;
     83 	bitmap->end = end;
     84 	bitmap->real_end = real_end;
     85 	switch (magic) {
     86 	case EXT2_ET_MAGIC_INODE_BITMAP:
     87 		bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
     88 		break;
     89 	case EXT2_ET_MAGIC_BLOCK_BITMAP:
     90 		bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
     91 		break;
     92 	default:
     93 		bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
     94 	}
     95 	if (descr) {
     96 		retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
     97 		if (retval) {
     98 			ext2fs_free_mem(&bitmap);
     99 			return retval;
    100 		}
    101 		strcpy(bitmap->description, descr);
    102 	} else
    103 		bitmap->description = 0;
    104 
    105 	size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
    106 	/* Round up to allow for the BT x86 instruction */
    107 	size = (size + 7) & ~3;
    108 	retval = ext2fs_get_mem(size, &bitmap->bitmap);
    109 	if (retval) {
    110 		ext2fs_free_mem(&bitmap->description);
    111 		ext2fs_free_mem(&bitmap);
    112 		return retval;
    113 	}
    114 
    115 	if (init_map)
    116 		memcpy(bitmap->bitmap, init_map, size);
    117 	else
    118 		memset(bitmap->bitmap, 0, size);
    119 	*ret = bitmap;
    120 	return 0;
    121 }
    122 
    123 errcode_t ext2fs_allocate_generic_bitmap(__u32 start,
    124 					 __u32 end,
    125 					 __u32 real_end,
    126 					 const char *descr,
    127 					 ext2fs_generic_bitmap *ret)
    128 {
    129 	return ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_GENERIC_BITMAP, 0,
    130 					  start, end, real_end, descr, 0, ret);
    131 }
    132 
    133 errcode_t ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap src,
    134 				     ext2fs_generic_bitmap *dest)
    135 {
    136 	return (ext2fs_make_generic_bitmap(src->magic, src->fs,
    137 					   src->start, src->end,
    138 					   src->real_end,
    139 					   src->description, src->bitmap,
    140 					   dest));
    141 }
    142 
    143 void ext2fs_free_generic_bitmap(ext2fs_inode_bitmap bitmap)
    144 {
    145 	if (check_magic(bitmap))
    146 		return;
    147 
    148 	bitmap->magic = 0;
    149 	if (bitmap->description) {
    150 		ext2fs_free_mem(&bitmap->description);
    151 		bitmap->description = 0;
    152 	}
    153 	if (bitmap->bitmap) {
    154 		ext2fs_free_mem(&bitmap->bitmap);
    155 		bitmap->bitmap = 0;
    156 	}
    157 	ext2fs_free_mem(&bitmap);
    158 }
    159 
    160 int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
    161 					blk_t bitno)
    162 {
    163 	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
    164 		ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno);
    165 		return 0;
    166 	}
    167 	return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap);
    168 }
    169 
    170 int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
    171 					 __u32 bitno)
    172 {
    173 	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
    174 		ext2fs_warn_bitmap2(bitmap, EXT2FS_MARK_ERROR, bitno);
    175 		return 0;
    176 	}
    177 	return ext2fs_set_bit(bitno - bitmap->start, bitmap->bitmap);
    178 }
    179 
    180 int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
    181 					   blk_t bitno)
    182 {
    183 	if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
    184 		ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, bitno);
    185 		return 0;
    186 	}
    187 	return ext2fs_clear_bit(bitno - bitmap->start, bitmap->bitmap);
    188 }
    189 
    190 __u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap)
    191 {
    192 	return bitmap->start;
    193 }
    194 
    195 __u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap)
    196 {
    197 	return bitmap->end;
    198 }
    199 
    200 void ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap)
    201 {
    202 	if (check_magic(bitmap))
    203 		return;
    204 
    205 	memset(bitmap->bitmap, 0,
    206 	       (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
    207 }
    208 
    209 errcode_t ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap bitmap,
    210 					  errcode_t magic, errcode_t neq,
    211 					  ext2_ino_t end, ext2_ino_t *oend)
    212 {
    213 	EXT2_CHECK_MAGIC(bitmap, magic);
    214 
    215 	if (end > bitmap->real_end)
    216 		return neq;
    217 	if (oend)
    218 		*oend = bitmap->end;
    219 	bitmap->end = end;
    220 	return 0;
    221 }
    222 
    223 errcode_t ext2fs_resize_generic_bitmap(errcode_t magic,
    224 				       __u32 new_end, __u32 new_real_end,
    225 				       ext2fs_generic_bitmap bmap)
    226 {
    227 	errcode_t	retval;
    228 	size_t		size, new_size;
    229 	__u32		bitno;
    230 
    231 	if (!bmap || (bmap->magic != magic))
    232 		return magic;
    233 
    234 	/*
    235 	 * If we're expanding the bitmap, make sure all of the new
    236 	 * parts of the bitmap are zero.
    237 	 */
    238 	if (new_end > bmap->end) {
    239 		bitno = bmap->real_end;
    240 		if (bitno > new_end)
    241 			bitno = new_end;
    242 		for (; bitno > bmap->end; bitno--)
    243 			ext2fs_clear_bit(bitno - bmap->start, bmap->bitmap);
    244 	}
    245 	if (new_real_end == bmap->real_end) {
    246 		bmap->end = new_end;
    247 		return 0;
    248 	}
    249 
    250 	size = ((bmap->real_end - bmap->start) / 8) + 1;
    251 	new_size = ((new_real_end - bmap->start) / 8) + 1;
    252 
    253 	if (size != new_size) {
    254 		retval = ext2fs_resize_mem(size, new_size, &bmap->bitmap);
    255 		if (retval)
    256 			return retval;
    257 	}
    258 	if (new_size > size)
    259 		memset(bmap->bitmap + size, 0, new_size - size);
    260 
    261 	bmap->end = new_end;
    262 	bmap->real_end = new_real_end;
    263 	return 0;
    264 }
    265 
    266 errcode_t ext2fs_compare_generic_bitmap(errcode_t magic, errcode_t neq,
    267 					ext2fs_generic_bitmap bm1,
    268 					ext2fs_generic_bitmap bm2)
    269 {
    270 	blk_t	i;
    271 
    272 	if (!bm1 || bm1->magic != magic)
    273 		return magic;
    274 	if (!bm2 || bm2->magic != magic)
    275 		return magic;
    276 
    277 	if ((bm1->start != bm2->start) ||
    278 	    (bm1->end != bm2->end) ||
    279 	    (memcmp(bm1->bitmap, bm2->bitmap,
    280 		    (size_t) (bm1->end - bm1->start)/8)))
    281 		return neq;
    282 
    283 	for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
    284 		if (ext2fs_fast_test_block_bitmap(bm1, i) !=
    285 		    ext2fs_fast_test_block_bitmap(bm2, i))
    286 			return neq;
    287 
    288 	return 0;
    289 }
    290 
    291 void ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap map)
    292 {
    293 	__u32	i, j;
    294 
    295 	/* Protect loop from wrap-around if map->real_end is maxed */
    296 	for (i=map->end+1, j = i - map->start;
    297 	     i <= map->real_end && i > map->end;
    298 	     i++, j++)
    299 		ext2fs_set_bit(j, map->bitmap);
    300 }
    301 
    302 errcode_t ext2fs_get_generic_bitmap_range(ext2fs_generic_bitmap bmap,
    303 					  errcode_t magic,
    304 					  __u32 start, __u32 num,
    305 					  void *out)
    306 {
    307 	if (!bmap || (bmap->magic != magic))
    308 		return magic;
    309 
    310 	if ((start < bmap->start) || (start+num-1 > bmap->real_end))
    311 		return EXT2_ET_INVALID_ARGUMENT;
    312 
    313 	memcpy(out, bmap->bitmap + (start >> 3), (num+7) >> 3);
    314 	return 0;
    315 }
    316 
    317 errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,
    318 					  errcode_t magic,
    319 					  __u32 start, __u32 num,
    320 					  void *in)
    321 {
    322 	if (!bmap || (bmap->magic != magic))
    323 		return magic;
    324 
    325 	if ((start < bmap->start) || (start+num-1 > bmap->real_end))
    326 		return EXT2_ET_INVALID_ARGUMENT;
    327 
    328 	memcpy(bmap->bitmap + (start >> 3), in, (num+7) >> 3);
    329 	return 0;
    330 }
    331 
    332 /*
    333  * Compare @mem to zero buffer by 256 bytes.
    334  * Return 1 if @mem is zeroed memory, otherwise return 0.
    335  */
    336 static int mem_is_zero(const char *mem, size_t len)
    337 {
    338 	static const char zero_buf[256];
    339 
    340 	while (len >= sizeof(zero_buf)) {
    341 		if (memcmp(mem, zero_buf, sizeof(zero_buf)))
    342 			return 0;
    343 		len -= sizeof(zero_buf);
    344 		mem += sizeof(zero_buf);
    345 	}
    346 	/* Deal with leftover bytes. */
    347 	if (len)
    348 		return !memcmp(mem, zero_buf, len);
    349 	return 1;
    350 }
    351 
    352 /*
    353  * Return true if all of the bits in a specified range are clear
    354  */
    355 static int ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap bitmap,
    356 						  unsigned int start,
    357 						  unsigned int len)
    358 {
    359 	size_t start_byte, len_byte = len >> 3;
    360 	unsigned int start_bit, len_bit = len % 8;
    361 	int first_bit = 0;
    362 	int last_bit  = 0;
    363 	int mark_count = 0;
    364 	int mark_bit = 0;
    365 	int i;
    366 	const char *ADDR = bitmap->bitmap;
    367 
    368 	start -= bitmap->start;
    369 	start_byte = start >> 3;
    370 	start_bit = start % 8;
    371 
    372 	if (start_bit != 0) {
    373 		/*
    374 		 * The compared start block number or start inode number
    375 		 * is not the first bit in a byte.
    376 		 */
    377 		mark_count = 8 - start_bit;
    378 		if (len < 8 - start_bit) {
    379 			mark_count = (int)len;
    380 			mark_bit = len + start_bit - 1;
    381 		} else
    382 			mark_bit = 7;
    383 
    384 		for (i = mark_count; i > 0; i--, mark_bit--)
    385 			first_bit |= 1 << mark_bit;
    386 
    387 		/*
    388 		 * Compare blocks or inodes in the first byte.
    389 		 * If there is any marked bit, this function returns 0.
    390 		 */
    391 		if (first_bit & ADDR[start_byte])
    392 			return 0;
    393 		else if (len <= 8 - start_bit)
    394 			return 1;
    395 
    396 		start_byte++;
    397 		len_bit = (len - mark_count) % 8;
    398 		len_byte = (len - mark_count) >> 3;
    399 	}
    400 
    401 	/*
    402 	 * The compared start block number or start inode number is
    403 	 * the first bit in a byte.
    404 	 */
    405 	if (len_bit != 0) {
    406 		/*
    407 		 * The compared end block number or end inode number is
    408 		 * not the last bit in a byte.
    409 		 */
    410 		for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
    411 			last_bit |= 1 << mark_bit;
    412 
    413 		/*
    414 		 * Compare blocks or inodes in the last byte.
    415 		 * If there is any marked bit, this function returns 0.
    416 		 */
    417 		if (last_bit & ADDR[start_byte + len_byte])
    418 			return 0;
    419 		else if (len_byte == 0)
    420 			return 1;
    421 	}
    422 
    423 	/* Check whether all bytes are 0 */
    424 	return mem_is_zero(ADDR + start_byte, len_byte);
    425 }
    426 
    427 int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
    428 				   blk_t block, int num)
    429 {
    430 	EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_BLOCK_BITMAP);
    431 	if ((block < bitmap->start) || (block+num-1 > bitmap->real_end)) {
    432 		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
    433 				   block, bitmap->description);
    434 		return 0;
    435 	}
    436 	return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap)
    437 						      bitmap, block, num);
    438 }
    439 
    440 int ext2fs_test_inode_bitmap_range(ext2fs_inode_bitmap bitmap,
    441 				   ino_t inode, int num)
    442 {
    443 	EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_INODE_BITMAP);
    444 	if ((inode < bitmap->start) || (inode+num-1 > bitmap->real_end)) {
    445 		ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_TEST,
    446 				   inode, bitmap->description);
    447 		return 0;
    448 	}
    449 	return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap)
    450 						      bitmap, inode, num);
    451 }
    452 
    453 void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
    454 				    blk_t block, int num)
    455 {
    456 	int	i;
    457 
    458 	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
    459 		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
    460 				   bitmap->description);
    461 		return;
    462 	}
    463 	for (i=0; i < num; i++)
    464 		ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap);
    465 }
    466 
    467 void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
    468 					       blk_t block, int num)
    469 {
    470 	int	i;
    471 
    472 	if ((block < bitmap->start) || (block+num-1 > bitmap->end)) {
    473 		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
    474 				   bitmap->description);
    475 		return;
    476 	}
    477 	for (i=0; i < num; i++)
    478 		ext2fs_fast_clear_bit(block + i - bitmap->start,
    479 				      bitmap->bitmap);
    480 }
    481