fs/hfs/bitmap.c

   1 /*
   2  * linux/fs/hfs/bitmap.c
   3  *
   4  * Copyright (C) 1996-1997  Paul H. Hargrove
   5  * This file may be distributed under the terms of the GNU General Public License.
   6  *
   7  * Based on GPLed code Copyright (C) 1995  Michael Dreher
   8  *
   9  * This file contains the code to modify the volume bitmap:
  10  * search/set/clear bits.
  11  *
  12  * "XXX" in a comment is a note to myself to consider changing something.
  13  *
  14  * In function preconditions the term "valid" applied to a pointer to
  15  * a structure means that the pointer is non-NULL and the structure it
  16  * points to has all fields initialized to consistent values.
  17  */
  18
  19 #include "hfs.h"
  20
  21 /*================ Global functions ================*/
  22
  23 /*
  24  * hfs_vbm_count_free()
  25  *
  26  * Description:
  27  *   Count the number of consecutive cleared bits in the bitmap blocks of
  28  *   the hfs MDB starting at bit number 'start'.  'mdb' had better
  29  *   be locked or the indicated number of blocks may be no longer free,
  30  *   when this functions returns!
  31  * Input Variable(s):
  32  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
  33  *   hfs_u16 start: bit number to start at
  34  * Output Variable(s):
  35  *   NONE
  36  * Returns:
  37  *   The number of consecutive cleared bits starting at bit 'start'
  38  * Preconditions:
  39  *   'mdb' points to a "valid" (struct hfs_mdb).
  40  * Postconditions:
  41  *   NONE
  42  */
  43 hfs_u16 hfs_vbm_count_free(const struct hfs_mdb *mdb, hfs_u16 start)
  44 {
  45         hfs_u16 block_nr;       /* index of the current bitmap block */
  46         hfs_u16 bit_nr;         /* index of the current bit in block */
  47         hfs_u16 count;          /* number of bits found so far */
  48         hfs_u16 len;            /* number of bits found in this block */
  49         hfs_u16 max_block;      /* index of last bitmap block */
  50         hfs_u16 max_bits;       /* index of last bit in block */
  51
  52         /* is this a valid HFS MDB? */
  53         if (!mdb) {
  54                 return 0;
  55         }
  56
  57         block_nr = start / HFS_BM_BPB;
  58         bit_nr   = start % HFS_BM_BPB;
  59         max_block = (mdb->fs_ablocks + HFS_BM_BPB - 1) / HFS_BM_BPB - 1;
  60
  61         count = 0;
  62         while (block_nr <= max_block) {
  63                 if (block_nr != max_block) {
  64                         max_bits = HFS_BM_BPB;
  65                 } else {
  66                         max_bits = mdb->fs_ablocks % HFS_BM_BPB;
  67                 }
  68
  69                 len=hfs_count_zero_bits(hfs_buffer_data(mdb->bitmap[block_nr]),
  70                                         max_bits, bit_nr);
  71                 count += len;
  72
  73                 /* see if we fell short of the end of this block */
  74                 if ((len + bit_nr) < max_bits) {
  75                         break;
  76                 }
  77
  78                 ++block_nr;
  79                 bit_nr = 0;
  80         }
  81         return count;
  82 }
  83
  84 /*
  85  * hfs_vbm_search_free()
  86  *
  87  * Description:
  88  *   Search for 'num_bits' consecutive cleared bits in the bitmap blocks of
  89  *   the hfs MDB. 'mdb' had better be locked or the returned range
  90  *   may be no longer free, when this functions returns!
  91  *   XXX Currently the search starts from bit 0, but it should start with
  92  *   the bit number stored in 's_alloc_ptr' of the MDB.
  93  * Input Variable(s):
  94  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
  95  *   hfs_u16 *num_bits: Pointer to the number of cleared bits
  96  *     to search for
  97  * Output Variable(s):
  98  *   hfs_u16 *num_bits: The number of consecutive clear bits of the
  99  *     returned range. If the bitmap is fragmented, this will be less than
 100  *     requested and it will be zero, when the disk is full.
 101  * Returns:
 102  *   The number of the first bit of the range of cleared bits which has been
 103  *   found. When 'num_bits' is zero, this is invalid!
 104  * Preconditions:
 105  *   'mdb' points to a "valid" (struct hfs_mdb).
 106  *   'num_bits' points to a variable of type (hfs_u16), which contains
 107  *      the number of cleared bits to find.
 108  * Postconditions:
 109  *   'num_bits' is set to the length of the found sequence.
 110  */
 111 hfs_u16 hfs_vbm_search_free(const struct hfs_mdb *mdb, hfs_u16 *num_bits)
 112 {
 113         hfs_u16 block_nr; /* index of the current bitmap block */
 114
 115         /* position and length of current portion of a run */
 116         hfs_u16 cur_pos, cur_len;
 117
 118         /* position and length of current complete run */
 119         hfs_u16 pos=0, len=0;
 120
 121         /* position and length of longest complete run */
 122         hfs_u16 longest_pos=0, longest_len=0;
 123
 124         void *bitmap; /* contents of the current bitmap block */
 125         hfs_u16 max_block; /* upper limit of outer loop */
 126         hfs_u16 max_bits; /* upper limit of inner loop */
 127
 128         /* is this a valid HFS MDB? */
 129         if (!mdb) {
 130                 *num_bits = 0;
 131                 hfs_warn("hfs_vbm_search_free: not a valid MDB\n");
 132                 return 0;
 133         }
 134
 135         /* make sure we have actual work to perform */
 136         if (!(*num_bits)) {
 137                 return 0;
 138         }
 139
 140         max_block = (mdb->fs_ablocks+HFS_BM_BPB-1) / HFS_BM_BPB - 1;
 141
 142         /* search all bitmap blocks */
 143         for (block_nr = 0; block_nr <= max_block; block_nr++) {
 144                 bitmap = hfs_buffer_data(mdb->bitmap[block_nr]);
 145
 146                 if (block_nr != max_block) {
 147                         max_bits = HFS_BM_BPB;
 148                 } else {
 149                         max_bits = mdb->fs_ablocks % HFS_BM_BPB;
 150                 }
 151
 152                 cur_pos = 0;
 153                 do {
 154                         cur_len = hfs_count_zero_bits(bitmap, max_bits,
 155                                                       cur_pos);
 156                         len += cur_len;
 157                         if (len > longest_len) {
 158                                 longest_pos = pos;
 159                                 longest_len = len;
 160                                 if (len >= *num_bits) {
 161                                         goto search_end;
 162                                 }
 163                         }
 164                         if ((cur_pos + cur_len) == max_bits) {
 165                                 break; /* zeros may continue into next block */
 166                         }
 167
 168                         /* find start of next run of zeros */
 169                         cur_pos = hfs_find_zero_bit(bitmap, max_bits,
 170                                                     cur_pos + cur_len);
 171                         pos = cur_pos + HFS_BM_BPB*block_nr;
 172                         len = 0;
 173                 } while (cur_pos < max_bits);
 174         }
 175
 176 search_end:
 177         *num_bits = longest_len;
 178         return longest_pos;
 179 }
 180
 181
 182 /*
 183  * hfs_set_vbm_bits()
 184  *
 185  * Description:
 186  *   Set the requested bits in the volume bitmap of the hfs filesystem
 187  * Input Variable(s):
 188  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
 189  *   hfs_u16 start: The offset of the first bit
 190  *   hfs_u16 count: The number of bits
 191  * Output Variable(s):
 192  *   None
 193  * Returns:
 194  *    0: no error
 195  *   -1: One of the bits was already set.  This is a strange
 196  *       error and when it happens, the filesystem must be repaired!
 197  *   -2: One or more of the bits are out of range of the bitmap.
 198  *   -3: The 's_magic' field of the MDB does not match
 199  * Preconditions:
 200  *   'mdb' points to a "valid" (struct hfs_mdb).
 201  * Postconditions:
 202  *   Starting with bit number 'start', 'count' bits in the volume bitmap
 203  *   are set. The affected bitmap blocks are marked "dirty", the free
 204  *   block count of the MDB is updated and the MDB is marked dirty.
 205  */
 206 int hfs_set_vbm_bits(struct hfs_mdb *mdb, hfs_u16 start, hfs_u16 count)
 207 {
 208         hfs_u16 block_nr;       /* index of the current bitmap block */
 209         hfs_u16 u32_nr;         /* index of the current hfs_u32 in block */
 210         hfs_u16 bit_nr;         /* index of the current bit in hfs_u32 */
 211         hfs_u16 left = count;   /* number of bits left to be set */
 212         hfs_u32 *bitmap;        /* the current bitmap block's contents */
 213
 214         /* is this a valid HFS MDB? */
 215         if (!mdb) {
 216                 return -3;
 217         }
 218
 219         /* is there any actual work to be done? */
 220         if (!count) {
 221                 return 0;
 222         }
 223
 224         /* are all of the bits in range? */
 225         if ((start + count) > mdb->fs_ablocks) {
 226                 return -2;
 227         }
 228
 229         block_nr = start / HFS_BM_BPB;
 230         u32_nr = (start % HFS_BM_BPB) / 32;
 231         bit_nr = start % 32;
 232
 233         /* bitmap is always on a 32-bit boundary */
 234         bitmap = (hfs_u32 *)hfs_buffer_data(mdb->bitmap[block_nr]);
 235
 236         /* do any partial hfs_u32 at the start */
 237         if (bit_nr != 0) {
 238                 while ((bit_nr < 32) && left) {
 239                         if (hfs_set_bit(bit_nr, bitmap + u32_nr)) {
 240                                 hfs_buffer_dirty(mdb->bitmap[block_nr]);
 241                                 return -1;
 242                         }
 243                         ++bit_nr;
 244                         --left;
 245                 }
 246                 bit_nr=0;
 247
 248                 /* advance u32_nr and check for end of this block */
 249                 if (++u32_nr > 127) {
 250                         u32_nr = 0;
 251                         hfs_buffer_dirty(mdb->bitmap[block_nr]);
 252                         ++block_nr;
 253                         /* bitmap is always on a 32-bit boundary */
 254                         bitmap = (hfs_u32 *)
 255                                         hfs_buffer_data(mdb->bitmap[block_nr]);
 256                 }
 257         }
 258
 259         /* do full hfs_u32s */
 260         while (left > 31) {
 261                 if (bitmap[u32_nr] != ((hfs_u32)0)) {
 262                         hfs_buffer_dirty(mdb->bitmap[block_nr]);
 263                         return -1;
 264                 }
 265                 bitmap[u32_nr] = ~((hfs_u32)0);
 266                 left -= 32;
 267
 268                 /* advance u32_nr and check for end of this block */
 269                 if (++u32_nr > 127) {
 270                         u32_nr = 0;
 271                         hfs_buffer_dirty(mdb->bitmap[block_nr]);
 272                         ++block_nr;
 273                         /* bitmap is always on a 32-bit boundary */
 274                         bitmap = (hfs_u32 *)
 275                                         hfs_buffer_data(mdb->bitmap[block_nr]);
 276                 }
 277         }
 278
 279
 280         /* do any partial hfs_u32 at end */
 281         while (left) {
 282                 if (hfs_set_bit(bit_nr, bitmap + u32_nr)) {
 283                         hfs_buffer_dirty(mdb->bitmap[block_nr]);
 284                         return -1;
 285                 }
 286                 ++bit_nr;
 287                 --left;
 288         }
 289
 290         hfs_buffer_dirty(mdb->bitmap[block_nr]);
 291         mdb->free_ablocks -= count;
 292
 293         /* successful completion */
 294         hfs_mdb_dirty(mdb->sys_mdb);
 295         return 0;
 296 }
 297
 298 /*
 299  * hfs_clear_vbm_bits()
 300  *
 301  * Description:
 302  *   Clear the requested bits in the volume bitmap of the hfs filesystem
 303  * Input Variable(s):
 304  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
 305  *   hfs_u16 start: The offset of the first bit
 306  *   hfs_u16 count: The number of bits
 307  * Output Variable(s):
 308  *   None
 309  * Returns:
 310  *    0: no error
 311  *   -1: One of the bits was already clear.  This is a strange
 312  *       error and when it happens, the filesystem must be repaired!
 313  *   -2: One or more of the bits are out of range of the bitmap.
 314  *   -3: The 's_magic' field of the MDB does not match
 315  * Preconditions:
 316  *   'mdb' points to a "valid" (struct hfs_mdb).
 317  * Postconditions:
 318  *   Starting with bit number 'start', 'count' bits in the volume bitmap
 319  *   are cleared. The affected bitmap blocks are marked "dirty", the free
 320  *   block count of the MDB is updated and the MDB is marked dirty.
 321  */
 322 int hfs_clear_vbm_bits(struct hfs_mdb *mdb, hfs_u16 start, hfs_u16 count)
 323 {
 324         hfs_u16 block_nr;       /* index of the current bitmap block */
 325         hfs_u16 u32_nr;         /* index of the current hfs_u32 in block */
 326         hfs_u16 bit_nr;         /* index of the current bit in hfs_u32 */
 327         hfs_u16 left = count;   /* number of bits left to be set */
 328         hfs_u32 *bitmap;        /* the current bitmap block's contents */
 329
 330         /* is this a valid HFS MDB? */
 331         if (!mdb) {
 332                 return -3;
 333         }
 334
 335         /* is there any actual work to be done? */
 336         if (!count) {
 337                 return 0;
 338         }
 339
 340         /* are all of the bits in range? */
 341         if ((start + count) > mdb->fs_ablocks) {
 342                 return -2;
 343         }
 344
 345         block_nr = start / HFS_BM_BPB;
 346         u32_nr = (start % HFS_BM_BPB) / 32;
 347         bit_nr = start % 32;
 348
 349         /* bitmap is always on a 32-bit boundary */
 350         bitmap = (hfs_u32 *)hfs_buffer_data(mdb->bitmap[block_nr]);
 351
 352         /* do any partial hfs_u32 at the start */
 353         if (bit_nr != 0) {
 354                 while ((bit_nr < 32) && left) {
 355                         if (!hfs_clear_bit(bit_nr, bitmap + u32_nr)) {
 356                                 hfs_buffer_dirty(mdb->bitmap[block_nr]);
 357                                 return -1;
 358                         }
 359                         ++bit_nr;
 360                         --left;
 361                 }
 362                 bit_nr=0;
 363
 364                 /* advance u32_nr and check for end of this block */
 365                 if (++u32_nr > 127) {
 366                         u32_nr = 0;
 367                         hfs_buffer_dirty(mdb->bitmap[block_nr]);
 368                         ++block_nr;
 369                         /* bitmap is always on a 32-bit boundary */
 370                         bitmap = (hfs_u32 *)
 371                                         hfs_buffer_data(mdb->bitmap[block_nr]);
 372                 }
 373         }
 374
 375         /* do full hfs_u32s */
 376         while (left > 31) {
 377                 if (bitmap[u32_nr] != ~((hfs_u32)0)) {
 378                         hfs_buffer_dirty(mdb->bitmap[block_nr]);
 379                         return -1;
 380                 }
 381                 bitmap[u32_nr] = ((hfs_u32)0);
 382                 left -= 32;
 383
 384                 /* advance u32_nr and check for end of this block */
 385                 if (++u32_nr > 127) {
 386                         u32_nr = 0;
 387                         hfs_buffer_dirty(mdb->bitmap[block_nr]);
 388                         ++block_nr;
 389                         /* bitmap is always on a 32-bit boundary */
 390                         bitmap = (hfs_u32 *)
 391                                         hfs_buffer_data(mdb->bitmap[block_nr]);
 392                 }
 393         }
 394
 395
 396         /* do any partial hfs_u32 at end */
 397         while (left) {
 398                 if (!hfs_clear_bit(bit_nr, bitmap + u32_nr)) {
 399                         hfs_buffer_dirty(mdb->bitmap[block_nr]);
 400                         return -1;
 401                 }
 402                 ++bit_nr;
 403                 --left;
 404         }
 405
 406         hfs_buffer_dirty(mdb->bitmap[block_nr]);
 407         mdb->free_ablocks += count;
 408
 409         /* successful completion */
 410         hfs_mdb_dirty(mdb->sys_mdb);
 411         return 0;
 412 }