FreeBSD/Linux Kernel Cross Reference
sys/fs/hfs/bitmap.c

     /*
      * linux/fs/hfs/bitmap.c
      *
      * Copyright (C) 1996-1997  Paul H. Hargrove
      * This file may be distributed under the terms of the GNU General Public License.
      *
      * Based on GPLed code Copyright (C) 1995  Michael Dreher
      *
      * This file contains the code to modify the volume bitmap:
     * search/set/clear bits.
     *
     * "XXX" in a comment is a note to myself to consider changing something.
     *
     * In function preconditions the term "valid" applied to a pointer to
     * a structure means that the pointer is non-NULL and the structure it
     * points to has all fields initialized to consistent values.
     */
    
    #include "hfs.h"
    
    /*================ Global functions ================*/
    
    /*
     * hfs_vbm_count_free()
     *
     * Description:
     *   Count the number of consecutive cleared bits in the bitmap blocks of
     *   the hfs MDB starting at bit number 'start'.  'mdb' had better
     *   be locked or the indicated number of blocks may be no longer free,
     *   when this functions returns!
     * Input Variable(s):
     *   struct hfs_mdb *mdb: Pointer to the hfs MDB
     *   hfs_u16 start: bit number to start at
     * Output Variable(s):
     *   NONE
     * Returns:
     *   The number of consecutive cleared bits starting at bit 'start'
     * Preconditions:
     *   'mdb' points to a "valid" (struct hfs_mdb).
     * Postconditions:
     *   NONE
     */
    hfs_u16 hfs_vbm_count_free(const struct hfs_mdb *mdb, hfs_u16 start)
    {
            hfs_u16 block_nr;       /* index of the current bitmap block */
            hfs_u16 bit_nr;         /* index of the current bit in block */
            hfs_u16 count;          /* number of bits found so far */
            hfs_u16 len;            /* number of bits found in this block */
            hfs_u16 max_block;      /* index of last bitmap block */
            hfs_u16 max_bits;       /* index of last bit in block */
    
            /* is this a valid HFS MDB? */
            if (!mdb) {
                    return 0;
            }
    
            block_nr = start / HFS_BM_BPB;
            bit_nr   = start % HFS_BM_BPB;
            max_block = (mdb->fs_ablocks + HFS_BM_BPB - 1) / HFS_BM_BPB - 1;
    
            count = 0;
            while (block_nr <= max_block) {
                    if (block_nr != max_block) {
                            max_bits = HFS_BM_BPB;
                    } else {
                            max_bits = mdb->fs_ablocks % HFS_BM_BPB;
                    }
    
                    len=hfs_count_zero_bits(hfs_buffer_data(mdb->bitmap[block_nr]),
                                            max_bits, bit_nr);
                    count += len;
    
                    /* see if we fell short of the end of this block */
                    if ((len + bit_nr) < max_bits) {
                            break;
                    }
    
                    ++block_nr;
                    bit_nr = 0;
            }
            return count;
    }
    
    /*
     * hfs_vbm_search_free()
     *
     * Description:
     *   Search for 'num_bits' consecutive cleared bits in the bitmap blocks of
     *   the hfs MDB. 'mdb' had better be locked or the returned range
     *   may be no longer free, when this functions returns!
     *   XXX Currently the search starts from bit 0, but it should start with
     *   the bit number stored in 's_alloc_ptr' of the MDB.
     * Input Variable(s):
     *   struct hfs_mdb *mdb: Pointer to the hfs MDB
     *   hfs_u16 *num_bits: Pointer to the number of cleared bits
     *     to search for
     * Output Variable(s):
     *   hfs_u16 *num_bits: The number of consecutive clear bits of the
     *     returned range. If the bitmap is fragmented, this will be less than
    *     requested and it will be zero, when the disk is full.
    * Returns:
    *   The number of the first bit of the range of cleared bits which has been
    *   found. When 'num_bits' is zero, this is invalid!
    * Preconditions:
    *   'mdb' points to a "valid" (struct hfs_mdb).
    *   'num_bits' points to a variable of type (hfs_u16), which contains
    *      the number of cleared bits to find.
    * Postconditions:
    *   'num_bits' is set to the length of the found sequence.
    */
   hfs_u16 hfs_vbm_search_free(const struct hfs_mdb *mdb, hfs_u16 *num_bits)
   {
           hfs_u16 block_nr; /* index of the current bitmap block */
   
           /* position and length of current portion of a run */
           hfs_u16 cur_pos, cur_len;
   
           /* position and length of current complete run */
           hfs_u16 pos=0, len=0;
           
           /* position and length of longest complete run */
           hfs_u16 longest_pos=0, longest_len=0;
   
           void *bitmap; /* contents of the current bitmap block */
           hfs_u16 max_block; /* upper limit of outer loop */
           hfs_u16 max_bits; /* upper limit of inner loop */
   
           /* is this a valid HFS MDB? */
           if (!mdb) {
                   *num_bits = 0;
                   hfs_warn("hfs_vbm_search_free: not a valid MDB\n");
                   return 0;
           }
           
           /* make sure we have actual work to perform */
           if (!(*num_bits)) {
                   return 0;
           }
   
           max_block = (mdb->fs_ablocks+HFS_BM_BPB-1) / HFS_BM_BPB - 1;
           
           /* search all bitmap blocks */
           for (block_nr = 0; block_nr <= max_block; block_nr++) {
                   bitmap = hfs_buffer_data(mdb->bitmap[block_nr]);
   
                   if (block_nr != max_block) {
                           max_bits = HFS_BM_BPB;
                   } else {
                           max_bits = mdb->fs_ablocks % HFS_BM_BPB;
                   }
   
                   cur_pos = 0;
                   do {
                           cur_len = hfs_count_zero_bits(bitmap, max_bits,
                                                         cur_pos);
                           len += cur_len;
                           if (len > longest_len) {
                                   longest_pos = pos;
                                   longest_len = len;
                                   if (len >= *num_bits) {
                                           goto search_end;
                                   }
                           }
                           if ((cur_pos + cur_len) == max_bits) {
                                   break; /* zeros may continue into next block */
                           }
   
                           /* find start of next run of zeros */
                           cur_pos = hfs_find_zero_bit(bitmap, max_bits,
                                                       cur_pos + cur_len);
                           pos = cur_pos + HFS_BM_BPB*block_nr;
                           len = 0;
                   } while (cur_pos < max_bits);
           }
   
   search_end:
           *num_bits = longest_len;
           return longest_pos;
   }
   
   
   /*
    * hfs_set_vbm_bits()
    *
    * Description:
    *   Set the requested bits in the volume bitmap of the hfs filesystem
    * Input Variable(s):
    *   struct hfs_mdb *mdb: Pointer to the hfs MDB
    *   hfs_u16 start: The offset of the first bit
    *   hfs_u16 count: The number of bits
    * Output Variable(s):
    *   None
    * Returns:
    *    0: no error
    *   -1: One of the bits was already set.  This is a strange
    *       error and when it happens, the filesystem must be repaired!
    *   -2: One or more of the bits are out of range of the bitmap.
    *   -3: The 's_magic' field of the MDB does not match
    * Preconditions:
    *   'mdb' points to a "valid" (struct hfs_mdb).
    * Postconditions:
    *   Starting with bit number 'start', 'count' bits in the volume bitmap
    *   are set. The affected bitmap blocks are marked "dirty", the free
    *   block count of the MDB is updated and the MDB is marked dirty.
    */
   int hfs_set_vbm_bits(struct hfs_mdb *mdb, hfs_u16 start, hfs_u16 count)
   {
           hfs_u16 block_nr;       /* index of the current bitmap block */
           hfs_u16 u32_nr;         /* index of the current hfs_u32 in block */
           hfs_u16 bit_nr;         /* index of the current bit in hfs_u32 */
           hfs_u16 left = count;   /* number of bits left to be set */
           hfs_u32 *bitmap;        /* the current bitmap block's contents */
   
           /* is this a valid HFS MDB? */
           if (!mdb) {
                   return -3;
           }
   
           /* is there any actual work to be done? */
           if (!count) {
                   return 0;
           }
   
           /* are all of the bits in range? */
           if ((start + count) > mdb->fs_ablocks) {
                   return -2;
           }
   
           block_nr = start / HFS_BM_BPB;
           u32_nr = (start % HFS_BM_BPB) / 32;
           bit_nr = start % 32;
   
           /* bitmap is always on a 32-bit boundary */
           bitmap = (hfs_u32 *)hfs_buffer_data(mdb->bitmap[block_nr]);
   
           /* do any partial hfs_u32 at the start */
           if (bit_nr != 0) {
                   while ((bit_nr < 32) && left) {
                           if (hfs_set_bit(bit_nr, bitmap + u32_nr)) {
                                   hfs_buffer_dirty(mdb->bitmap[block_nr]);
                                   return -1;
                           }
                           ++bit_nr;
                           --left;
                   }
                   bit_nr=0;
   
                   /* advance u32_nr and check for end of this block */
                   if (++u32_nr > 127) {
                           u32_nr = 0;
                           hfs_buffer_dirty(mdb->bitmap[block_nr]);
                           ++block_nr;
                           /* bitmap is always on a 32-bit boundary */
                           bitmap = (hfs_u32 *)
                                           hfs_buffer_data(mdb->bitmap[block_nr]);
                   }
           }
   
           /* do full hfs_u32s */
           while (left > 31) {
                   if (bitmap[u32_nr] != ((hfs_u32)0)) {
                           hfs_buffer_dirty(mdb->bitmap[block_nr]);
                           return -1;
                   }
                   bitmap[u32_nr] = ~((hfs_u32)0);
                   left -= 32;
   
                   /* advance u32_nr and check for end of this block */
                   if (++u32_nr > 127) {
                           u32_nr = 0;
                           hfs_buffer_dirty(mdb->bitmap[block_nr]);
                           ++block_nr;
                           /* bitmap is always on a 32-bit boundary */
                           bitmap = (hfs_u32 *)
                                           hfs_buffer_data(mdb->bitmap[block_nr]);
                   }
           }
   
                           
           /* do any partial hfs_u32 at end */
           while (left) {
                   if (hfs_set_bit(bit_nr, bitmap + u32_nr)) {
                           hfs_buffer_dirty(mdb->bitmap[block_nr]);
                           return -1;
                   }
                   ++bit_nr;
                   --left;
           }
   
           hfs_buffer_dirty(mdb->bitmap[block_nr]);
           mdb->free_ablocks -= count;
   
           /* successful completion */
           hfs_mdb_dirty(mdb->sys_mdb);
           return 0;
   }
   
   /*
    * hfs_clear_vbm_bits()
    *
    * Description:
    *   Clear the requested bits in the volume bitmap of the hfs filesystem
    * Input Variable(s):
    *   struct hfs_mdb *mdb: Pointer to the hfs MDB
    *   hfs_u16 start: The offset of the first bit
    *   hfs_u16 count: The number of bits
    * Output Variable(s):
    *   None
    * Returns:
    *    0: no error
    *   -1: One of the bits was already clear.  This is a strange
    *       error and when it happens, the filesystem must be repaired!
    *   -2: One or more of the bits are out of range of the bitmap.
    *   -3: The 's_magic' field of the MDB does not match
    * Preconditions:
    *   'mdb' points to a "valid" (struct hfs_mdb).
    * Postconditions:
    *   Starting with bit number 'start', 'count' bits in the volume bitmap
    *   are cleared. The affected bitmap blocks are marked "dirty", the free
    *   block count of the MDB is updated and the MDB is marked dirty.
    */
   int hfs_clear_vbm_bits(struct hfs_mdb *mdb, hfs_u16 start, hfs_u16 count)
   {
           hfs_u16 block_nr;       /* index of the current bitmap block */
           hfs_u16 u32_nr;         /* index of the current hfs_u32 in block */
           hfs_u16 bit_nr;         /* index of the current bit in hfs_u32 */
           hfs_u16 left = count;   /* number of bits left to be set */
           hfs_u32 *bitmap;        /* the current bitmap block's contents */
   
           /* is this a valid HFS MDB? */
           if (!mdb) {
                   return -3;
           }
   
           /* is there any actual work to be done? */
           if (!count) {
                   return 0;
           }
   
           /* are all of the bits in range? */
           if ((start + count) > mdb->fs_ablocks) {
                   return -2;
           }
   
           block_nr = start / HFS_BM_BPB;
           u32_nr = (start % HFS_BM_BPB) / 32;
           bit_nr = start % 32;
   
           /* bitmap is always on a 32-bit boundary */
           bitmap = (hfs_u32 *)hfs_buffer_data(mdb->bitmap[block_nr]);
   
           /* do any partial hfs_u32 at the start */
           if (bit_nr != 0) {
                   while ((bit_nr < 32) && left) {
                           if (!hfs_clear_bit(bit_nr, bitmap + u32_nr)) {
                                   hfs_buffer_dirty(mdb->bitmap[block_nr]);
                                   return -1;
                           }
                           ++bit_nr;
                           --left;
                   }
                   bit_nr=0;
   
                   /* advance u32_nr and check for end of this block */
                   if (++u32_nr > 127) {
                           u32_nr = 0;
                           hfs_buffer_dirty(mdb->bitmap[block_nr]);
                           ++block_nr;
                           /* bitmap is always on a 32-bit boundary */
                           bitmap = (hfs_u32 *)
                                           hfs_buffer_data(mdb->bitmap[block_nr]);
                   }
           }
   
           /* do full hfs_u32s */
           while (left > 31) {
                   if (bitmap[u32_nr] != ~((hfs_u32)0)) {
                           hfs_buffer_dirty(mdb->bitmap[block_nr]);
                           return -1;
                   }
                   bitmap[u32_nr] = ((hfs_u32)0);
                   left -= 32;
   
                   /* advance u32_nr and check for end of this block */
                   if (++u32_nr > 127) {
                           u32_nr = 0;
                           hfs_buffer_dirty(mdb->bitmap[block_nr]);
                           ++block_nr;
                           /* bitmap is always on a 32-bit boundary */
                           bitmap = (hfs_u32 *)
                                           hfs_buffer_data(mdb->bitmap[block_nr]);
                   }
           }
   
                           
           /* do any partial hfs_u32 at end */
           while (left) {
                   if (!hfs_clear_bit(bit_nr, bitmap + u32_nr)) {
                           hfs_buffer_dirty(mdb->bitmap[block_nr]);
                           return -1;
                   }
                   ++bit_nr;
                   --left;
           }
   
           hfs_buffer_dirty(mdb->bitmap[block_nr]);
           mdb->free_ablocks += count;
   
           /* successful completion */
           hfs_mdb_dirty(mdb->sys_mdb);
           return 0;
   }

Cache object: eb93a0c2b90b19b1078498c375f7eed1