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 <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 }