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
