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