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_64 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_64 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_64 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_64 src,
 105                               ext2fs_generic_bitmap_64 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_64 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_64 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_64 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_64 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_64 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_64 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_64 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_64 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_64 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_64 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_64 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_64 bitmap EXT2FS_ATTR((unused)))
 322 {
 323 }
 324 #endif
 325
 326 /* Find the first zero bit between start and end, inclusive. */
 327 static errcode_t ba_find_first_zero(ext2fs_generic_bitmap_64 bitmap,
 328                                     __u64 start, __u64 end, __u64 *out)
 329 {
 330         ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
 331         unsigned long bitpos = start - bitmap->start;
 332         unsigned long count = end - start + 1;
 333         int byte_found = 0; /* whether a != 0xff byte has been found */
 334         const unsigned char *pos;
 335         unsigned long max_loop_count, i;
 336
 337         /* scan bits until we hit a byte boundary */
 338         while ((bitpos & 0x7) != 0 && count > 0) {
 339                 if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
 340                         *out = bitpos + bitmap->start;
 341                         return 0;
 342                 }
 343                 bitpos++;
 344                 count--;
 345         }
 346
 347         if (!count)
 348                 return ENOENT;
 349
 350         pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
 351         /* scan bytes until 8-byte (64-bit) aligned */
 352         while (count >= 8 && (((uintptr_t)pos) & 0x07)) {
 353                 if (*pos != 0xff) {
 354                         byte_found = 1;
 355                         break;
 356                 }
 357                 pos++;
 358                 count -= 8;
 359                 bitpos += 8;
 360         }
 361
 362         if (!byte_found) {
 363                 max_loop_count = count >> 6; /* 8-byte blocks */
 364                 i = max_loop_count;
 365                 while (i) {
 366                         if (*((const __u64 *)pos) != ((__u64)-1))
 367                                 break;
 368                         pos += 8;
 369                         i--;
 370                 }
 371                 count -= 64 * (max_loop_count - i);
 372                 bitpos += 64 * (max_loop_count - i);
 373
 374                 max_loop_count = count >> 3;
 375                 i = max_loop_count;
 376                 while (i) {
 377                         if (*pos != 0xff) {
 378                                 byte_found = 1;
 379                                 break;
 380                         }
 381                         pos++;
 382                         i--;
 383                 }
 384                 count -= 8 * (max_loop_count - i);
 385                 bitpos += 8 * (max_loop_count - i);
 386         }
 387
 388         /* Here either count < 8 or byte_found == 1. */
 389         while (count-- > 0) {
 390                 if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
 391                         *out = bitpos + bitmap->start;
 392                         return 0;
 393                 }
 394                 bitpos++;
 395         }
 396
 397         return ENOENT;
 398 }
 399
 400 /* Find the first one bit between start and end, inclusive. */
 401 static errcode_t ba_find_first_set(ext2fs_generic_bitmap_64 bitmap,
 402                                     __u64 start, __u64 end, __u64 *out)
 403 {
 404         ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
 405         unsigned long bitpos = start - bitmap->start;
 406         unsigned long count = end - start + 1;
 407         int byte_found = 0; /* whether a != 0xff byte has been found */
 408         const unsigned char *pos;
 409         unsigned long max_loop_count, i;
 410
 411         /* scan bits until we hit a byte boundary */
 412         while ((bitpos & 0x7) != 0 && count > 0) {
 413                 if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
 414                         *out = bitpos + bitmap->start;
 415                         return 0;
 416                 }
 417                 bitpos++;
 418                 count--;
 419         }
 420
 421         if (!count)
 422                 return ENOENT;
 423
 424         pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
 425         /* scan bytes until 8-byte (64-bit) aligned */
 426         while (count >= 8 && (((uintptr_t)pos) & 0x07)) {
 427                 if (*pos != 0) {
 428                         byte_found = 1;
 429                         break;
 430                 }
 431                 pos++;
 432                 count -= 8;
 433                 bitpos += 8;
 434         }
 435
 436         if (!byte_found) {
 437                 max_loop_count = count >> 6; /* 8-byte blocks */
 438                 i = max_loop_count;
 439                 while (i) {
 440                         if (*((const __u64 *)pos) != 0)
 441                                 break;
 442                         pos += 8;
 443                         i--;
 444                 }
 445                 count -= 64 * (max_loop_count - i);
 446                 bitpos += 64 * (max_loop_count - i);
 447
 448                 max_loop_count = count >> 3;
 449                 i = max_loop_count;
 450                 while (i) {
 451                         if (*pos != 0) {
 452                                 byte_found = 1;
 453                                 break;
 454                         }
 455                         pos++;
 456                         i--;
 457                 }
 458                 count -= 8 * (max_loop_count - i);
 459                 bitpos += 8 * (max_loop_count - i);
 460         }
 461
 462         /* Here either count < 8 or byte_found == 1. */
 463         while (count-- > 0) {
 464                 if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
 465                         *out = bitpos + bitmap->start;
 466                         return 0;
 467                 }
 468                 bitpos++;
 469         }
 470
 471         return ENOENT;
 472 }
 473
 474 struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
 475         .type = EXT2FS_BMAP64_BITARRAY,
 476         .new_bmap = ba_new_bmap,
 477         .free_bmap = ba_free_bmap,
 478         .copy_bmap = ba_copy_bmap,
 479         .resize_bmap = ba_resize_bmap,
 480         .mark_bmap = ba_mark_bmap,
 481         .unmark_bmap = ba_unmark_bmap,
 482         .test_bmap = ba_test_bmap,
 483         .test_clear_bmap_extent = ba_test_clear_bmap_extent,
 484         .mark_bmap_extent = ba_mark_bmap_extent,
 485         .unmark_bmap_extent = ba_unmark_bmap_extent,
 486         .set_bmap_range = ba_set_bmap_range,
 487         .get_bmap_range = ba_get_bmap_range,
 488         .clear_bmap = ba_clear_bmap,
 489         .print_stats = ba_print_stats,
 490         .find_first_zero = ba_find_first_zero,
 491         .find_first_set = ba_find_first_set
 492 };