lib/ext2fs/blkmap64_ba.c

   1 /*
   2  * blkmap64_ba.c --- Simple bitarray implementation for bitmaps
   3  *
   4  * Copyright (C) 2008 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 #include "config.h"
  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 #include "bmap64.h"
  30
  31 /*
  32  * Private data for bit array implementation of bitmap ops.
  33  * Currently, this is just a pointer to our big flat hunk of memory,
  34  * exactly equivalent to the old-skool char * bitmap member.
  35  */
  36
  37 struct ext2fs_ba_private_struct {
  38         char *bitarray;
  39 };
  40
  41 typedef struct ext2fs_ba_private_struct *ext2fs_ba_private;
  42
  43 static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap bitmap)
  44 {
  45         ext2fs_ba_private bp;
  46         errcode_t       retval;
  47         size_t          size;
  48
  49         /*
  50          * Since we only have the one pointer, we could just shove our
  51          * private data in the void *private field itself, but then
  52          * we'd have to do a fair bit of rewriting if we ever added a
  53          * field.  I'm agnostic.
  54          */
  55         retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp);
  56         if (retval)
  57                 return retval;
  58
  59         size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
  60
  61         retval = ext2fs_get_mem(size, &bp->bitarray);
  62         if (retval) {
  63                 ext2fs_free_mem(&bp);
  64                 bp = 0;
  65                 return retval;
  66         }
  67         bitmap->private = (void *) bp;
  68         return 0;
  69 }
  70
  71 static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
  72                              ext2fs_generic_bitmap bitmap)
  73 {
  74         ext2fs_ba_private bp;
  75         errcode_t       retval;
  76         size_t          size;
  77
  78         retval = ba_alloc_private_data (bitmap);
  79         if (retval)
  80                 return retval;
  81
  82         bp = (ext2fs_ba_private) bitmap->private;
  83         size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
  84         memset(bp->bitarray, 0, size);
  85
  86         return 0;
  87 }
  88
  89 static void ba_free_bmap(ext2fs_generic_bitmap bitmap)
  90 {
  91         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
  92
  93         if (!bp)
  94                 return;
  95
  96         if (bp->bitarray) {
  97                 ext2fs_free_mem (&bp->bitarray);
  98                 bp->bitarray = 0;
  99         }
 100         ext2fs_free_mem (&bp);
 101         bp = 0;
 102 }
 103
 104 static errcode_t ba_copy_bmap(ext2fs_generic_bitmap src,
 105                               ext2fs_generic_bitmap dest)
 106 {
 107         ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private;
 108         ext2fs_ba_private dest_bp;
 109         errcode_t retval;
 110         size_t size;
 111
 112         retval = ba_alloc_private_data (dest);
 113         if (retval)
 114                 return retval;
 115
 116         dest_bp = (ext2fs_ba_private) dest->private;
 117
 118         size = (size_t) (((src->real_end - src->start) / 8) + 1);
 119         memcpy (dest_bp->bitarray, src_bp->bitarray, size);
 120
 121         return 0;
 122 }
 123
 124 static errcode_t ba_resize_bmap(ext2fs_generic_bitmap bmap,
 125                                 __u64 new_end, __u64 new_real_end)
 126 {
 127         ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private;
 128         errcode_t       retval;
 129         size_t          size, new_size;
 130         __u64           bitno;
 131
 132         /*
 133          * If we're expanding the bitmap, make sure all of the new
 134          * parts of the bitmap are zero.
 135          */
 136         if (new_end > bmap->end) {
 137                 bitno = bmap->real_end;
 138                 if (bitno > new_end)
 139                         bitno = new_end;
 140                 for (; bitno > bmap->end; bitno--)
 141                         ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray);
 142         }
 143         if (new_real_end == bmap->real_end) {
 144                 bmap->end = new_end;
 145                 return 0;
 146         }
 147
 148         size = ((bmap->real_end - bmap->start) / 8) + 1;
 149         new_size = ((new_real_end - bmap->start) / 8) + 1;
 150
 151         if (size != new_size) {
 152                 retval = ext2fs_resize_mem(size, new_size, &bp->bitarray);
 153                 if (retval)
 154                         return retval;
 155         }
 156         if (new_size > size)
 157                 memset(bp->bitarray + size, 0, new_size - size);
 158
 159         bmap->end = new_end;
 160         bmap->real_end = new_real_end;
 161         return 0;
 162
 163 }
 164
 165 static int ba_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
 166 {
 167         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 168         blk64_t bitno = (blk64_t) arg;
 169
 170         return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray);
 171 }
 172
 173 static int ba_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
 174 {
 175         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 176         blk64_t bitno = (blk64_t) arg;
 177
 178         return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray);
 179 }
 180
 181 static int ba_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
 182 {
 183         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 184         blk64_t bitno = (blk64_t) arg;
 185
 186         return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray);
 187 }
 188
 189 static void ba_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
 190                                 unsigned int num)
 191 {
 192         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 193         blk64_t bitno = (blk64_t) arg;
 194         unsigned int i;
 195
 196         for (i = 0; i < num; i++)
 197                 ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray);
 198 }
 199
 200 static void ba_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
 201                                   unsigned int num)
 202 {
 203         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 204         blk64_t bitno = (blk64_t) arg;
 205         unsigned int i;
 206
 207         for (i = 0; i < num; i++)
 208                 ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray);
 209 }
 210
 211 static int ba_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
 212                                      __u64 start, unsigned int len)
 213 {
 214         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 215         __u64 start_byte, len_byte = len >> 3;
 216         unsigned int start_bit, len_bit = len % 8;
 217         unsigned int first_bit = 0;
 218         unsigned int last_bit  = 0;
 219         int mark_count = 0;
 220         int mark_bit = 0;
 221         int i;
 222         const char *ADDR;
 223
 224         ADDR = bp->bitarray;
 225         start -= bitmap->start;
 226         start_byte = start >> 3;
 227         start_bit = start % 8;
 228
 229         if (start_bit != 0) {
 230                 /*
 231                  * The compared start block number or start inode number
 232                  * is not the first bit in a byte.
 233                  */
 234                 mark_count = 8 - start_bit;
 235                 if (len < 8 - start_bit) {
 236                         mark_count = (int)len;
 237                         mark_bit = len + start_bit - 1;
 238                 } else
 239                         mark_bit = 7;
 240
 241                 for (i = mark_count; i > 0; i--, mark_bit--)
 242                         first_bit |= 1 << mark_bit;
 243
 244                 /*
 245                  * Compare blocks or inodes in the first byte.
 246                  * If there is any marked bit, this function returns 0.
 247                  */
 248                 if (first_bit & ADDR[start_byte])
 249                         return 0;
 250                 else if (len <= 8 - start_bit)
 251                         return 1;
 252
 253                 start_byte++;
 254                 len_bit = (len - mark_count) % 8;
 255                 len_byte = (len - mark_count) >> 3;
 256         }
 257
 258         /*
 259          * The compared start block number or start inode number is
 260          * the first bit in a byte.
 261          */
 262         if (len_bit != 0) {
 263                 /*
 264                  * The compared end block number or end inode number is
 265                  * not the last bit in a byte.
 266                  */
 267                 for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
 268                         last_bit |= 1 << mark_bit;
 269
 270                 /*
 271                  * Compare blocks or inodes in the last byte.
 272                  * If there is any marked bit, this function returns 0.
 273                  */
 274                 if (last_bit & ADDR[start_byte + len_byte])
 275                         return 0;
 276                 else if (len_byte == 0)
 277                         return 1;
 278         }
 279
 280         /* Check whether all bytes are 0 */
 281         return ext2fs_mem_is_zero(ADDR + start_byte, len_byte);
 282 }
 283
 284
 285 static errcode_t ba_set_bmap_range(ext2fs_generic_bitmap bitmap,
 286                                      __u64 start, size_t num, void *in)
 287 {
 288         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 289
 290         memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3);
 291
 292         return 0;
 293 }
 294
 295 static errcode_t ba_get_bmap_range(ext2fs_generic_bitmap bitmap,
 296                                      __u64 start, size_t num, void *out)
 297 {
 298         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 299
 300         memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3);
 301
 302         return 0;
 303 }
 304
 305 static void ba_clear_bmap(ext2fs_generic_bitmap bitmap)
 306 {
 307         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 308
 309         memset(bp->bitarray, 0,
 310                (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
 311 }
 312
 313 #ifdef ENABLE_BMAP_STATS
 314 static void ba_print_stats(ext2fs_generic_bitmap bitmap)
 315 {
 316         fprintf(stderr, "%16llu Bytes used by bitarray\n",
 317                 ((bitmap->real_end - bitmap->start) >> 3) + 1 +
 318                 sizeof(struct ext2fs_ba_private_struct));
 319 }
 320 #else
 321 static void ba_print_stats(ext2fs_generic_bitmap bitmap) {}
 322 #endif
 323
 324 /* Find the first zero bit between start and end, inclusive. */
 325 static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap,
 326                                     __u64 start, __u64 end, __u64 *out)
 327 {
 328         ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
 329         unsigned long bitpos = start - bitmap->start;
 330         unsigned long count = end - start + 1;
 331         int byte_found = 0; /* whether a != 0xff byte has been found */
 332         const unsigned char *pos;
 333         unsigned long max_loop_count, i;
 334
 335         /* scan bits until we hit a byte boundary */
 336         while ((bitpos & 0x7) != 0 && count > 0) {
 337                 if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
 338                         *out = bitpos + bitmap->start;
 339                         return 0;
 340                 }
 341                 bitpos++;
 342                 count--;
 343         }
 344
 345         if (!count)
 346                 return ENOENT;
 347
 348         pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
 349         /* scan bytes until 8-byte (64-bit) aligned */
 350         while (count >= 8 && (((unsigned long)pos) & 0x07)) {
 351                 if (*pos != 0xff) {
 352                         byte_found = 1;
 353                         break;
 354                 }
 355                 pos++;
 356                 count -= 8;
 357                 bitpos += 8;
 358         }
 359
 360         if (!byte_found) {
 361                 max_loop_count = count >> 6; /* 8-byte blocks */
 362                 i = max_loop_count;
 363                 while (i) {
 364                         if (*((const __u64 *)pos) != ((__u64)-1))
 365                                 break;
 366                         pos += 8;
 367                         i--;
 368                 }
 369                 count -= 64 * (max_loop_count - i);
 370                 bitpos += 64 * (max_loop_count - i);
 371
 372                 max_loop_count = count >> 3;
 373                 i = max_loop_count;
 374                 while (i) {
 375                         if (*pos != 0xff) {
 376                                 byte_found = 1;
 377                                 break;
 378                         }
 379                         pos++;
 380                         i--;
 381                 }
 382                 count -= 8 * (max_loop_count - i);
 383                 bitpos += 8 * (max_loop_count - i);
 384         }
 385
 386         /* Here either count < 8 or byte_found == 1. */
 387         while (count-- > 0) {
 388                 if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
 389                         *out = bitpos + bitmap->start;
 390                         return 0;
 391                 }
 392                 bitpos++;
 393         }
 394
 395         return ENOENT;
 396 }
 397
 398 /* Find the first one bit between start and end, inclusive. */
 399 static errcode_t ba_find_first_set(ext2fs_generic_bitmap bitmap,
 400                                     __u64 start, __u64 end, __u64 *out)
 401 {
 402         ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
 403         unsigned long bitpos = start - bitmap->start;
 404         unsigned long count = end - start + 1;
 405         int byte_found = 0; /* whether a != 0xff byte has been found */
 406         const unsigned char *pos;
 407         unsigned long max_loop_count, i;
 408
 409         /* scan bits until we hit a byte boundary */
 410         while ((bitpos & 0x7) != 0 && count > 0) {
 411                 if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
 412                         *out = bitpos + bitmap->start;
 413                         return 0;
 414                 }
 415                 bitpos++;
 416                 count--;
 417         }
 418
 419         if (!count)
 420                 return ENOENT;
 421
 422         pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
 423         /* scan bytes until 8-byte (64-bit) aligned */
 424         while (count >= 8 && (((unsigned long)pos) & 0x07)) {
 425                 if (*pos != 0) {
 426                         byte_found = 1;
 427                         break;
 428                 }
 429                 pos++;
 430                 count -= 8;
 431                 bitpos += 8;
 432         }
 433
 434         if (!byte_found) {
 435                 max_loop_count = count >> 6; /* 8-byte blocks */
 436                 i = max_loop_count;
 437                 while (i) {
 438                         if (*((const __u64 *)pos) != 0)
 439                                 break;
 440                         pos += 8;
 441                         i--;
 442                 }
 443                 count -= 64 * (max_loop_count - i);
 444                 bitpos += 64 * (max_loop_count - i);
 445
 446                 max_loop_count = count >> 3;
 447                 i = max_loop_count;
 448                 while (i) {
 449                         if (*pos != 0) {
 450                                 byte_found = 1;
 451                                 break;
 452                         }
 453                         pos++;
 454                         i--;
 455                 }
 456                 count -= 8 * (max_loop_count - i);
 457                 bitpos += 8 * (max_loop_count - i);
 458         }
 459
 460         /* Here either count < 8 or byte_found == 1. */
 461         while (count-- > 0) {
 462                 if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
 463                         *out = bitpos + bitmap->start;
 464                         return 0;
 465                 }
 466                 bitpos++;
 467         }
 468
 469         return ENOENT;
 470 }
 471
 472 struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
 473         .type = EXT2FS_BMAP64_BITARRAY,
 474         .new_bmap = ba_new_bmap,
 475         .free_bmap = ba_free_bmap,
 476         .copy_bmap = ba_copy_bmap,
 477         .resize_bmap = ba_resize_bmap,
 478         .mark_bmap = ba_mark_bmap,
 479         .unmark_bmap = ba_unmark_bmap,
 480         .test_bmap = ba_test_bmap,
 481         .test_clear_bmap_extent = ba_test_clear_bmap_extent,
 482         .mark_bmap_extent = ba_mark_bmap_extent,
 483         .unmark_bmap_extent = ba_unmark_bmap_extent,
 484         .set_bmap_range = ba_set_bmap_range,
 485         .get_bmap_range = ba_get_bmap_range,
 486         .clear_bmap = ba_clear_bmap,
 487         .print_stats = ba_print_stats,
 488         .find_first_zero = ba_find_first_zero,
 489         .find_first_set = ba_find_first_set
 490 };