URL
https://opencores.org/ocsvn/or1k/or1k/trunk
Subversion Repositories or1k
[/] [or1k/] [tags/] [LINUX_2_4_26_OR32/] [linux/] [linux-2.4/] [fs/] [hfs/] [bitmap.c] - Rev 1780
Go to most recent revision | Compare with Previous | Blame | View Log
/* * 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; }
Go to most recent revision | Compare with Previous | Blame | View Log