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 struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
 314         .type = EXT2FS_BMAP64_BITARRAY,
 315         .new_bmap = ba_new_bmap,
 316         .free_bmap = ba_free_bmap,
 317         .copy_bmap = ba_copy_bmap,
 318         .resize_bmap = ba_resize_bmap,
 319         .mark_bmap = ba_mark_bmap,
 320         .unmark_bmap = ba_unmark_bmap,
 321         .test_bmap = ba_test_bmap,
 322         .test_clear_bmap_extent = ba_test_clear_bmap_extent,
 323         .mark_bmap_extent = ba_mark_bmap_extent,
 324         .unmark_bmap_extent = ba_unmark_bmap_extent,
 325         .set_bmap_range = ba_set_bmap_range,
 326         .get_bmap_range = ba_get_bmap_range,
 327         .clear_bmap = ba_clear_bmap,
 328 };