lib/ext2fs/gen_bitmap.c

   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 "config.h"
  14 #include <stdio.h>
  15 #include <string.h>
  16 #if HAVE_UNISTD_H
  17 #include <unistd.h>
  18 #endif
  19 #include <fcntl.h>
  20 #include <time.h>
  21 #if HAVE_SYS_STAT_H
  22 #include <sys/stat.h>
  23 #endif
  24 #if HAVE_SYS_TYPES_H
  25 #include <sys/types.h>
  26 #endif
  27
  28 #include "ext2_fs.h"
  29 #include "ext2fsP.h"
  30
  31 struct ext2fs_struct_generic_bitmap {
  32         errcode_t       magic;
  33         ext2_filsys     fs;
  34         __u32           start, end;
  35         __u32           real_end;
  36         char    *       description;
  37         char    *       bitmap;
  38         errcode_t       base_error_code;
  39         __u32           reserved[7];
  40 };
  41
  42 #define EXT2FS_IS_32_BITMAP(bmap) \
  43         (((bmap)->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) || \
  44          ((bmap)->magic == EXT2_ET_MAGIC_BLOCK_BITMAP) || \
  45          ((bmap)->magic == EXT2_ET_MAGIC_INODE_BITMAP))
  46
  47 #define EXT2FS_IS_64_BITMAP(bmap) \
  48         (((bmap)->magic == EXT2_ET_MAGIC_GENERIC_BITMAP64) || \
  49          ((bmap)->magic == EXT2_ET_MAGIC_BLOCK_BITMAP64) || \
  50          ((bmap)->magic == EXT2_ET_MAGIC_INODE_BITMAP64))
  51
  52 /*
  53  * Used by previously inlined function, so we have to export this and
  54  * not change the function signature
  55  */
  56 void ext2fs_warn_bitmap2(ext2fs_generic_bitmap bitmap,
  57                             int code, unsigned long arg)
  58 {
  59 #ifndef OMIT_COM_ERR
  60         if (bitmap->description)
  61                 com_err(0, bitmap->base_error_code+code,
  62                         "#%lu for %s", arg, bitmap->description);
  63         else
  64                 com_err(0, bitmap->base_error_code + code, "#%lu", arg);
  65 #endif
  66 }
  67
  68 static errcode_t check_magic(ext2fs_generic_bitmap bitmap)
  69 {
  70         if (!bitmap || !((bitmap->magic == EXT2_ET_MAGIC_GENERIC_BITMAP) ||
  71                          (bitmap->magic == EXT2_ET_MAGIC_INODE_BITMAP) ||
  72                          (bitmap->magic == EXT2_ET_MAGIC_BLOCK_BITMAP)))
  73                 return EXT2_ET_MAGIC_GENERIC_BITMAP;
  74         return 0;
  75 }
  76
  77 errcode_t ext2fs_make_generic_bitmap(errcode_t magic, ext2_filsys fs,
  78                                      __u32 start, __u32 end, __u32 real_end,
  79                                      const char *descr, char *init_map,
  80                                      ext2fs_generic_bitmap *ret)
  81 {
  82         ext2fs_generic_bitmap   bitmap;
  83         errcode_t               retval;
  84         size_t                  size;
  85
  86         retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
  87                                 &bitmap);
  88         if (retval)
  89                 return retval;
  90
  91         bitmap->magic = magic;
  92         bitmap->fs = fs;
  93         bitmap->start = start;
  94         bitmap->end = end;
  95         bitmap->real_end = real_end;
  96         switch (magic) {
  97         case EXT2_ET_MAGIC_INODE_BITMAP:
  98                 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
  99                 break;
 100         case EXT2_ET_MAGIC_BLOCK_BITMAP:
 101                 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
 102                 break;
 103         default:
 104                 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
 105         }
 106         if (descr) {
 107                 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
 108                 if (retval) {
 109                         ext2fs_free_mem(&bitmap);
 110                         return retval;
 111                 }
 112                 strcpy(bitmap->description, descr);
 113         } else
 114                 bitmap->description = 0;
 115
 116         size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
 117         /* Round up to allow for the BT x86 instruction */
 118         size = (size + 7) & ~3;
 119         retval = ext2fs_get_mem(size, &bitmap->bitmap);
 120         if (retval) {
 121                 ext2fs_free_mem(&bitmap->description);
 122                 ext2fs_free_mem(&bitmap);
 123                 return retval;
 124         }
 125
 126         if (init_map)
 127                 memcpy(bitmap->bitmap, init_map, size);
 128         else
 129                 memset(bitmap->bitmap, 0, size);
 130         *ret = bitmap;
 131         return 0;
 132 }
 133
 134 errcode_t ext2fs_allocate_generic_bitmap(__u32 start,
 135                                          __u32 end,
 136                                          __u32 real_end,
 137                                          const char *descr,
 138                                          ext2fs_generic_bitmap *ret)
 139 {
 140         return ext2fs_make_generic_bitmap(EXT2_ET_MAGIC_GENERIC_BITMAP, 0,
 141                                           start, end, real_end, descr, 0, ret);
 142 }
 143
 144 errcode_t ext2fs_copy_generic_bitmap(ext2fs_generic_bitmap src,
 145                                      ext2fs_generic_bitmap *dest)
 146 {
 147         return (ext2fs_make_generic_bitmap(src->magic, src->fs,
 148                                            src->start, src->end,
 149                                            src->real_end,
 150                                            src->description, src->bitmap,
 151                                            dest));
 152 }
 153
 154 void ext2fs_free_generic_bitmap(ext2fs_inode_bitmap bitmap)
 155 {
 156         if (check_magic(bitmap))
 157                 return;
 158
 159         bitmap->magic = 0;
 160         if (bitmap->description) {
 161                 ext2fs_free_mem(&bitmap->description);
 162                 bitmap->description = 0;
 163         }
 164         if (bitmap->bitmap) {
 165                 ext2fs_free_mem(&bitmap->bitmap);
 166                 bitmap->bitmap = 0;
 167         }
 168         ext2fs_free_mem(&bitmap);
 169 }
 170
 171 int ext2fs_test_generic_bitmap(ext2fs_generic_bitmap bitmap,
 172                                         blk_t bitno)
 173 {
 174         if (!EXT2FS_IS_32_BITMAP(bitmap)) {
 175                 if (EXT2FS_IS_64_BITMAP(bitmap)) {
 176                         ext2fs_warn_bitmap32(bitmap, __func__);
 177                         return ext2fs_test_generic_bmap(bitmap, bitno);
 178                 }
 179 #ifndef OMIT_COM_ERR
 180                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 181                         "test_bitmap(%lu)", (unsigned long) bitno);
 182 #endif
 183                 return 0;
 184         }
 185
 186         if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
 187                 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, bitno);
 188                 return 0;
 189         }
 190         return ext2fs_test_bit(bitno - bitmap->start, bitmap->bitmap);
 191 }
 192
 193 int ext2fs_mark_generic_bitmap(ext2fs_generic_bitmap bitmap,
 194                                          __u32 bitno)
 195 {
 196         if (!EXT2FS_IS_32_BITMAP(bitmap)) {
 197                 if (EXT2FS_IS_64_BITMAP(bitmap)) {
 198                         ext2fs_warn_bitmap32(bitmap, __func__);
 199                         return ext2fs_mark_generic_bmap(bitmap, bitno);
 200                 }
 201 #ifndef OMIT_COM_ERR
 202                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 203                         "mark_bitmap(%lu)", (unsigned long) bitno);
 204 #endif
 205                 return 0;
 206         }
 207
 208         if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
 209                 ext2fs_warn_bitmap2(bitmap, EXT2FS_MARK_ERROR, bitno);
 210                 return 0;
 211         }
 212         return ext2fs_set_bit(bitno - bitmap->start, bitmap->bitmap);
 213 }
 214
 215 int ext2fs_unmark_generic_bitmap(ext2fs_generic_bitmap bitmap,
 216                                            blk_t bitno)
 217 {
 218         if (!EXT2FS_IS_32_BITMAP(bitmap)) {
 219                 if (EXT2FS_IS_64_BITMAP(bitmap)) {
 220                         ext2fs_warn_bitmap32(bitmap, __func__);
 221                         return ext2fs_unmark_generic_bmap(bitmap, bitno);
 222                 }
 223 #ifndef OMIT_COM_ERR
 224                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 225                         "mark_bitmap(%lu)", (unsigned long) bitno);
 226 #endif
 227                 return 0;
 228         }
 229
 230         if ((bitno < bitmap->start) || (bitno > bitmap->end)) {
 231                 ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR, bitno);
 232                 return 0;
 233         }
 234         return ext2fs_clear_bit(bitno - bitmap->start, bitmap->bitmap);
 235 }
 236
 237 __u32 ext2fs_get_generic_bitmap_start(ext2fs_generic_bitmap bitmap)
 238 {
 239         if (!EXT2FS_IS_32_BITMAP(bitmap)) {
 240                 if (EXT2FS_IS_64_BITMAP(bitmap)) {
 241                         ext2fs_warn_bitmap32(bitmap, __func__);
 242                         return ext2fs_get_generic_bmap_start(bitmap);
 243                 }
 244 #ifndef OMIT_COM_ERR
 245                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 246                         "get_bitmap_start");
 247 #endif
 248                 return 0;
 249         }
 250
 251         return bitmap->start;
 252 }
 253
 254 __u32 ext2fs_get_generic_bitmap_end(ext2fs_generic_bitmap bitmap)
 255 {
 256         if (!EXT2FS_IS_32_BITMAP(bitmap)) {
 257                 if (EXT2FS_IS_64_BITMAP(bitmap)) {
 258                         ext2fs_warn_bitmap32(bitmap, __func__);
 259                         return ext2fs_get_generic_bmap_end(bitmap);
 260                 }
 261 #ifndef OMIT_COM_ERR
 262                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 263                         "get_bitmap_end");
 264 #endif
 265                 return 0;
 266         }
 267         return bitmap->end;
 268 }
 269
 270 void ext2fs_clear_generic_bitmap(ext2fs_generic_bitmap bitmap)
 271 {
 272         if (!EXT2FS_IS_32_BITMAP(bitmap)) {
 273                 if (EXT2FS_IS_64_BITMAP(bitmap)) {
 274                         ext2fs_warn_bitmap32(bitmap, __func__);
 275                         ext2fs_clear_generic_bmap(bitmap);
 276                         return;
 277                 }
 278 #ifndef OMIT_COM_ERR
 279                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 280                         "clear_generic_bitmap");
 281 #endif
 282                 return;
 283         }
 284
 285         memset(bitmap->bitmap, 0,
 286                (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
 287 }
 288
 289 errcode_t ext2fs_fudge_generic_bitmap_end(ext2fs_inode_bitmap bitmap,
 290                                           errcode_t magic, errcode_t neq,
 291                                           ext2_ino_t end, ext2_ino_t *oend)
 292 {
 293         EXT2_CHECK_MAGIC(bitmap, magic);
 294
 295         if (end > bitmap->real_end)
 296                 return neq;
 297         if (oend)
 298                 *oend = bitmap->end;
 299         bitmap->end = end;
 300         return 0;
 301 }
 302
 303 errcode_t ext2fs_resize_generic_bitmap(errcode_t magic,
 304                                        __u32 new_end, __u32 new_real_end,
 305                                        ext2fs_generic_bitmap bmap)
 306 {
 307         errcode_t       retval;
 308         size_t          size, new_size;
 309         __u32           bitno;
 310
 311         if (!bmap || (bmap->magic != magic))
 312                 return magic;
 313
 314         /*
 315          * If we're expanding the bitmap, make sure all of the new
 316          * parts of the bitmap are zero.
 317          */
 318         if (new_end > bmap->end) {
 319                 bitno = bmap->real_end;
 320                 if (bitno > new_end)
 321                         bitno = new_end;
 322                 for (; bitno > bmap->end; bitno--)
 323                         ext2fs_clear_bit(bitno - bmap->start, bmap->bitmap);
 324         }
 325         if (new_real_end == bmap->real_end) {
 326                 bmap->end = new_end;
 327                 return 0;
 328         }
 329
 330         size = ((bmap->real_end - bmap->start) / 8) + 1;
 331         new_size = ((new_real_end - bmap->start) / 8) + 1;
 332
 333         if (size != new_size) {
 334                 retval = ext2fs_resize_mem(size, new_size, &bmap->bitmap);
 335                 if (retval)
 336                         return retval;
 337         }
 338         if (new_size > size)
 339                 memset(bmap->bitmap + size, 0, new_size - size);
 340
 341         bmap->end = new_end;
 342         bmap->real_end = new_real_end;
 343         return 0;
 344 }
 345
 346 errcode_t ext2fs_compare_generic_bitmap(errcode_t magic, errcode_t neq,
 347                                         ext2fs_generic_bitmap bm1,
 348                                         ext2fs_generic_bitmap bm2)
 349 {
 350         blk_t   i;
 351
 352         if (!bm1 || bm1->magic != magic)
 353                 return magic;
 354         if (!bm2 || bm2->magic != magic)
 355                 return magic;
 356
 357         if ((bm1->start != bm2->start) ||
 358             (bm1->end != bm2->end) ||
 359             (memcmp(bm1->bitmap, bm2->bitmap,
 360                     (size_t) (bm1->end - bm1->start)/8)))
 361                 return neq;
 362
 363         for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
 364                 if (ext2fs_fast_test_block_bitmap(bm1, i) !=
 365                     ext2fs_fast_test_block_bitmap(bm2, i))
 366                         return neq;
 367
 368         return 0;
 369 }
 370
 371 void ext2fs_set_generic_bitmap_padding(ext2fs_generic_bitmap map)
 372 {
 373         __u32   i, j;
 374
 375         /* Protect loop from wrap-around if map->real_end is maxed */
 376         for (i=map->end+1, j = i - map->start;
 377              i <= map->real_end && i > map->end;
 378              i++, j++)
 379                 ext2fs_set_bit(j, map->bitmap);
 380 }
 381
 382 errcode_t ext2fs_get_generic_bitmap_range(ext2fs_generic_bitmap bmap,
 383                                           errcode_t magic,
 384                                           __u32 start, __u32 num,
 385                                           void *out)
 386 {
 387         if (!bmap || (bmap->magic != magic))
 388                 return magic;
 389
 390         if ((start < bmap->start) || (start+num-1 > bmap->real_end))
 391                 return EXT2_ET_INVALID_ARGUMENT;
 392
 393         memcpy(out, bmap->bitmap + (start >> 3), (num+7) >> 3);
 394         return 0;
 395 }
 396
 397 errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,
 398                                           errcode_t magic,
 399                                           __u32 start, __u32 num,
 400                                           void *in)
 401 {
 402         if (!bmap || (bmap->magic != magic))
 403                 return magic;
 404
 405         if ((start < bmap->start) || (start+num-1 > bmap->real_end))
 406                 return EXT2_ET_INVALID_ARGUMENT;
 407
 408         memcpy(bmap->bitmap + (start >> 3), in, (num+7) >> 3);
 409         return 0;
 410 }
 411
 412 /*
 413  * Compare @mem to zero buffer by 256 bytes.
 414  * Return 1 if @mem is zeroed memory, otherwise return 0.
 415  */
 416 int ext2fs_mem_is_zero(const char *mem, size_t len)
 417 {
 418         static const char zero_buf[256];
 419
 420         while (len >= sizeof(zero_buf)) {
 421                 if (memcmp(mem, zero_buf, sizeof(zero_buf)))
 422                         return 0;
 423                 len -= sizeof(zero_buf);
 424                 mem += sizeof(zero_buf);
 425         }
 426         /* Deal with leftover bytes. */
 427         if (len)
 428                 return !memcmp(mem, zero_buf, len);
 429         return 1;
 430 }
 431
 432 /*
 433  * Return true if all of the bits in a specified range are clear
 434  */
 435 static int ext2fs_test_clear_generic_bitmap_range(ext2fs_generic_bitmap bitmap,
 436                                                   unsigned int start,
 437                                                   unsigned int len)
 438 {
 439         size_t start_byte, len_byte = len >> 3;
 440         unsigned int start_bit, len_bit = len % 8;
 441         int first_bit = 0;
 442         int last_bit  = 0;
 443         int mark_count = 0;
 444         int mark_bit = 0;
 445         int i;
 446         const char *ADDR = bitmap->bitmap;
 447
 448         start -= bitmap->start;
 449         start_byte = start >> 3;
 450         start_bit = start % 8;
 451
 452         if (start_bit != 0) {
 453                 /*
 454                  * The compared start block number or start inode number
 455                  * is not the first bit in a byte.
 456                  */
 457                 mark_count = 8 - start_bit;
 458                 if (len < 8 - start_bit) {
 459                         mark_count = (int)len;
 460                         mark_bit = len + start_bit - 1;
 461                 } else
 462                         mark_bit = 7;
 463
 464                 for (i = mark_count; i > 0; i--, mark_bit--)
 465                         first_bit |= 1 << mark_bit;
 466
 467                 /*
 468                  * Compare blocks or inodes in the first byte.
 469                  * If there is any marked bit, this function returns 0.
 470                  */
 471                 if (first_bit & ADDR[start_byte])
 472                         return 0;
 473                 else if (len <= 8 - start_bit)
 474                         return 1;
 475
 476                 start_byte++;
 477                 len_bit = (len - mark_count) % 8;
 478                 len_byte = (len - mark_count) >> 3;
 479         }
 480
 481         /*
 482          * The compared start block number or start inode number is
 483          * the first bit in a byte.
 484          */
 485         if (len_bit != 0) {
 486                 /*
 487                  * The compared end block number or end inode number is
 488                  * not the last bit in a byte.
 489                  */
 490                 for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
 491                         last_bit |= 1 << mark_bit;
 492
 493                 /*
 494                  * Compare blocks or inodes in the last byte.
 495                  * If there is any marked bit, this function returns 0.
 496                  */
 497                 if (last_bit & ADDR[start_byte + len_byte])
 498                         return 0;
 499                 else if (len_byte == 0)
 500                         return 1;
 501         }
 502
 503         /* Check whether all bytes are 0 */
 504         return ext2fs_mem_is_zero(ADDR + start_byte, len_byte);
 505 }
 506
 507 errcode_t ext2fs_find_first_zero_generic_bitmap(ext2fs_generic_bitmap bitmap,
 508                                                 __u32 start, __u32 end,
 509                                                 __u32 *out)
 510 {
 511         blk_t b;
 512
 513         if (start < bitmap->start || end > bitmap->end || start > end) {
 514                 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
 515                 return EINVAL;
 516         }
 517
 518         while (start <= end) {
 519                 b = ext2fs_test_bit(start - bitmap->start, bitmap->bitmap);
 520                 if (!b) {
 521                         *out = start;
 522                         return 0;
 523                 }
 524                 start++;
 525         }
 526
 527         return ENOENT;
 528 }
 529
 530 errcode_t ext2fs_find_first_set_generic_bitmap(ext2fs_generic_bitmap bitmap,
 531                                                __u32 start, __u32 end,
 532                                                __u32 *out)
 533 {
 534         blk_t b;
 535
 536         if (start < bitmap->start || end > bitmap->end || start > end) {
 537                 ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
 538                 return EINVAL;
 539         }
 540
 541         while (start <= end) {
 542                 b = ext2fs_test_bit(start - bitmap->start, bitmap->bitmap);
 543                 if (b) {
 544                         *out = start;
 545                         return 0;
 546                 }
 547                 start++;
 548         }
 549
 550         return ENOENT;
 551 }
 552
 553 int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
 554                                    blk_t block, int num)
 555 {
 556         EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_BLOCK_BITMAP);
 557         if ((block < bitmap->start) || (block > bitmap->real_end) ||
 558             (block+num-1 > bitmap->real_end)) {
 559                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST,
 560                                    block, bitmap->description);
 561                 return 0;
 562         }
 563         return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap)
 564                                                       bitmap, block, num);
 565 }
 566
 567 int ext2fs_test_inode_bitmap_range(ext2fs_inode_bitmap bitmap,
 568                                    ext2_ino_t inode, int num)
 569 {
 570         EXT2_CHECK_MAGIC(bitmap, EXT2_ET_MAGIC_INODE_BITMAP);
 571         if ((inode < bitmap->start) || (inode > bitmap->real_end) ||
 572             (inode+num-1 > bitmap->real_end)) {
 573                 ext2fs_warn_bitmap(EXT2_ET_BAD_INODE_TEST,
 574                                    inode, bitmap->description);
 575                 return 0;
 576         }
 577         return ext2fs_test_clear_generic_bitmap_range((ext2fs_generic_bitmap)
 578                                                       bitmap, inode, num);
 579 }
 580
 581 void ext2fs_mark_block_bitmap_range(ext2fs_block_bitmap bitmap,
 582                                     blk_t block, int num)
 583 {
 584         int     i;
 585
 586         if ((block < bitmap->start) || (block > bitmap->end) ||
 587             (block+num-1 > bitmap->end)) {
 588                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
 589                                    bitmap->description);
 590                 return;
 591         }
 592         for (i=0; i < num; i++)
 593                 ext2fs_fast_set_bit(block + i - bitmap->start, bitmap->bitmap);
 594 }
 595
 596 void ext2fs_unmark_block_bitmap_range(ext2fs_block_bitmap bitmap,
 597                                                blk_t block, int num)
 598 {
 599         int     i;
 600
 601         if ((block < bitmap->start) || (block > bitmap->end) ||
 602             (block+num-1 > bitmap->end)) {
 603                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
 604                                    bitmap->description);
 605                 return;
 606         }
 607         for (i=0; i < num; i++)
 608                 ext2fs_fast_clear_bit(block + i - bitmap->start,
 609                                       bitmap->bitmap);
 610 }
 611