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 <stdio.h>
  13 #include <string.h>
  14 #if HAVE_UNISTD_H
  15 #include <unistd.h>
  16 #endif
  17 #include <fcntl.h>
  18 #include <time.h>
  19 #if HAVE_SYS_STAT_H
  20 #include <sys/stat.h>
  21 #endif
  22 #if HAVE_SYS_TYPES_H
  23 #include <sys/types.h>
  24 #endif
  25
  26 #include "ext2_fs.h"
  27 #include "ext2fsP.h"
  28 #include "bmap64.h"
  29
  30 /*
  31  * Private data for bit array implementation of bitmap ops.
  32  * Currently, this is just a pointer to our big flat hunk of memory,
  33  * exactly equivalent to the old-skool char * bitmap member.
  34  */
  35
  36 struct ext2fs_ba_private_struct {
  37         char *bitarray;
  38 };
  39
  40 typedef struct ext2fs_ba_private_struct *ext2fs_ba_private;
  41
  42 static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap bitmap)
  43 {
  44         ext2fs_ba_private bp;
  45         errcode_t       retval;
  46         size_t          size;
  47
  48         /*
  49          * Since we only have the one pointer, we could just shove our
  50          * private data in the void *private field itself, but then
  51          * we'd have to do a fair bit of rewriting if we ever added a
  52          * field.  I'm agnostic.
  53          */
  54         retval = ext2fs_get_mem(sizeof (ext2fs_ba_private), &bp);
  55         if (retval)
  56                 return retval;
  57
  58         size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
  59
  60         retval = ext2fs_get_mem(size, &bp->bitarray);
  61         if (retval) {
  62                 ext2fs_free_mem(&bp);
  63                 bp = 0;
  64                 return retval;
  65         }
  66         bitmap->private = (void *) bp;
  67         return 0;
  68 }
  69
  70 static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
  71                              ext2fs_generic_bitmap bitmap)
  72 {
  73         ext2fs_ba_private bp;
  74         errcode_t       retval;
  75         size_t          size;
  76
  77         retval = ba_alloc_private_data (bitmap);
  78         if (retval)
  79                 return retval;
  80
  81         bp = (ext2fs_ba_private) bitmap->private;
  82         size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
  83         memset(bp->bitarray, 0, size);
  84
  85         return 0;
  86 }
  87
  88 static void ba_free_bmap(ext2fs_generic_bitmap bitmap)
  89 {
  90         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
  91
  92         if (!bp)
  93                 return;
  94
  95         if (bp->bitarray) {
  96                 ext2fs_free_mem (&bp->bitarray);
  97                 bp->bitarray = 0;
  98         }
  99         ext2fs_free_mem (&bp);
 100         bp = 0;
 101 }
 102
 103 static errcode_t ba_copy_bmap(ext2fs_generic_bitmap src,
 104                               ext2fs_generic_bitmap dest)
 105 {
 106         ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private;
 107         ext2fs_ba_private dest_bp;
 108         errcode_t retval;
 109         size_t size;
 110
 111         retval = ba_alloc_private_data (dest);
 112         if (retval)
 113                 return retval;
 114
 115         dest_bp = (ext2fs_ba_private) dest->private;
 116
 117         size = (size_t) (((src->real_end - src->start) / 8) + 1);
 118         memcpy (dest_bp->bitarray, src_bp->bitarray, size);
 119
 120         return 0;
 121 }
 122
 123 static errcode_t ba_resize_bmap(ext2fs_generic_bitmap bmap,
 124                                 __u64 new_end, __u64 new_real_end)
 125 {
 126         ext2fs_ba_private bp = (ext2fs_ba_private) bmap->private;
 127         errcode_t       retval;
 128         size_t          size, new_size;
 129         __u64           bitno;
 130
 131         /*
 132          * If we're expanding the bitmap, make sure all of the new
 133          * parts of the bitmap are zero.
 134          */
 135         if (new_end > bmap->end) {
 136                 bitno = bmap->real_end;
 137                 if (bitno > new_end)
 138                         bitno = new_end;
 139                 for (; bitno > bmap->end; bitno--)
 140                         ext2fs_clear_bit64(bitno - bmap->start, bp->bitarray);
 141         }
 142         if (new_real_end == bmap->real_end) {
 143                 bmap->end = new_end;
 144                 return 0;
 145         }
 146
 147         size = ((bmap->real_end - bmap->start) / 8) + 1;
 148         new_size = ((new_real_end - bmap->start) / 8) + 1;
 149
 150         if (size != new_size) {
 151                 retval = ext2fs_resize_mem(size, new_size, &bp->bitarray);
 152                 if (retval)
 153                         return retval;
 154         }
 155         if (new_size > size)
 156                 memset(bp->bitarray + size, 0, new_size - size);
 157
 158         bmap->end = new_end;
 159         bmap->real_end = new_real_end;
 160         return 0;
 161
 162 }
 163
 164 static int ba_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
 165 {
 166         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 167         blk64_t bitno = (blk64_t) arg;
 168
 169         return ext2fs_set_bit64(bitno - bitmap->start, bp->bitarray);
 170 }
 171
 172 static int ba_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
 173 {
 174         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 175         blk64_t bitno = (blk64_t) arg;
 176
 177         return ext2fs_clear_bit64(bitno - bitmap->start, bp->bitarray);
 178 }
 179
 180 static int ba_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
 181 {
 182         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 183         blk64_t bitno = (blk64_t) arg;
 184
 185         return ext2fs_test_bit64(bitno - bitmap->start, bp->bitarray);
 186 }
 187
 188 static void ba_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
 189                                 unsigned int num)
 190 {
 191         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 192         blk64_t bitno = (blk64_t) arg;
 193         unsigned int i;
 194
 195         for (i = 0; i < num; i++)
 196                 ext2fs_fast_set_bit64(bitno + i - bitmap->start, bp->bitarray);
 197 }
 198
 199 static void ba_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
 200                                   unsigned int num)
 201 {
 202         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 203         blk64_t bitno = (blk64_t) arg;
 204         unsigned int i;
 205
 206         for (i = 0; i < num; i++)
 207                 ext2fs_fast_clear_bit64(bitno + i - bitmap->start, bp->bitarray);
 208 }
 209
 210 static int ba_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
 211                                      __u64 start, unsigned int len)
 212 {
 213         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 214         __u64 start_byte, len_byte = len >> 3;
 215         unsigned int start_bit, len_bit = len % 8;
 216         unsigned int first_bit = 0;
 217         unsigned int last_bit  = 0;
 218         int mark_count = 0;
 219         int mark_bit = 0;
 220         int i;
 221         const char *ADDR;
 222
 223         ADDR = bp->bitarray;
 224         start -= bitmap->start;
 225         start_byte = start >> 3;
 226         start_bit = start % 8;
 227
 228         if (start_bit != 0) {
 229                 /*
 230                  * The compared start block number or start inode number
 231                  * is not the first bit in a byte.
 232                  */
 233                 mark_count = 8 - start_bit;
 234                 if (len < 8 - start_bit) {
 235                         mark_count = (int)len;
 236                         mark_bit = len + start_bit - 1;
 237                 } else
 238                         mark_bit = 7;
 239
 240                 for (i = mark_count; i > 0; i--, mark_bit--)
 241                         first_bit |= 1 << mark_bit;
 242
 243                 /*
 244                  * Compare blocks or inodes in the first byte.
 245                  * If there is any marked bit, this function returns 0.
 246                  */
 247                 if (first_bit & ADDR[start_byte])
 248                         return 0;
 249                 else if (len <= 8 - start_bit)
 250                         return 1;
 251
 252                 start_byte++;
 253                 len_bit = (len - mark_count) % 8;
 254                 len_byte = (len - mark_count) >> 3;
 255         }
 256
 257         /*
 258          * The compared start block number or start inode number is
 259          * the first bit in a byte.
 260          */
 261         if (len_bit != 0) {
 262                 /*
 263                  * The compared end block number or end inode number is
 264                  * not the last bit in a byte.
 265                  */
 266                 for (mark_bit = len_bit - 1; mark_bit >= 0; mark_bit--)
 267                         last_bit |= 1 << mark_bit;
 268
 269                 /*
 270                  * Compare blocks or inodes in the last byte.
 271                  * If there is any marked bit, this function returns 0.
 272                  */
 273                 if (last_bit & ADDR[start_byte + len_byte])
 274                         return 0;
 275                 else if (len_byte == 0)
 276                         return 1;
 277         }
 278
 279         /* Check whether all bytes are 0 */
 280         return ext2fs_mem_is_zero(ADDR + start_byte, len_byte);
 281 }
 282
 283
 284 static errcode_t ba_set_bmap_range(ext2fs_generic_bitmap bitmap,
 285                                      __u64 start, size_t num, void *in)
 286 {
 287         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 288
 289         memcpy (bp->bitarray + (start >> 3), in, (num + 7) >> 3);
 290
 291         return 0;
 292 }
 293
 294 static errcode_t ba_get_bmap_range(ext2fs_generic_bitmap bitmap,
 295                                      __u64 start, size_t num, void *out)
 296 {
 297         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 298
 299         memcpy (out, bp->bitarray + (start >> 3), (num + 7) >> 3);
 300
 301         return 0;
 302 }
 303
 304 static void ba_clear_bmap(ext2fs_generic_bitmap bitmap)
 305 {
 306         ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 307
 308         memset(bp->bitarray, 0,
 309                (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
 310 }
 311
 312 struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
 313         .type = EXT2FS_BMAP64_BITARRAY,
 314         .new_bmap = ba_new_bmap,
 315         .free_bmap = ba_free_bmap,
 316         .copy_bmap = ba_copy_bmap,
 317         .resize_bmap = ba_resize_bmap,
 318         .mark_bmap = ba_mark_bmap,
 319         .unmark_bmap = ba_unmark_bmap,
 320         .test_bmap = ba_test_bmap,
 321         .test_clear_bmap_extent = ba_test_clear_bmap_extent,
 322         .mark_bmap_extent = ba_mark_bmap_extent,
 323         .unmark_bmap_extent = ba_unmark_bmap_extent,
 324         .set_bmap_range = ba_set_bmap_range,
 325         .get_bmap_range = ba_get_bmap_range,
 326         .clear_bmap = ba_clear_bmap,
 327 };