summaryrefslogtreecommitdiff
path: root/fs/affs/bitmap.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 15:20:36 -0700
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 15:20:36 -0700
commit1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch)
tree0bba044c4ce775e45a88a51686b5d9f90697ea9d /fs/affs/bitmap.c
Linux-2.6.12-rc2v2.6.12-rc2
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!
Diffstat (limited to 'fs/affs/bitmap.c')
-rw-r--r--fs/affs/bitmap.c390
1 files changed, 390 insertions, 0 deletions
diff --git a/fs/affs/bitmap.c b/fs/affs/bitmap.c
new file mode 100644
index 000000000000..b0b953683c1a
--- /dev/null
+++ b/fs/affs/bitmap.c
@@ -0,0 +1,390 @@
+/*
+ * linux/fs/affs/bitmap.c
+ *
+ * (c) 1996 Hans-Joachim Widmaier
+ *
+ * bitmap.c contains the code that handles all bitmap related stuff -
+ * block allocation, deallocation, calculation of free space.
+ */
+
+#include "affs.h"
+
+/* This is, of course, shamelessly stolen from fs/minix */
+
+static int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
+
+static u32
+affs_count_free_bits(u32 blocksize, const void *data)
+{
+ const u32 *map;
+ u32 free;
+ u32 tmp;
+
+ map = data;
+ free = 0;
+ for (blocksize /= 4; blocksize > 0; blocksize--) {
+ tmp = *map++;
+ while (tmp) {
+ free += nibblemap[tmp & 0xf];
+ tmp >>= 4;
+ }
+ }
+
+ return free;
+}
+
+u32
+affs_count_free_blocks(struct super_block *sb)
+{
+ struct affs_bm_info *bm;
+ u32 free;
+ int i;
+
+ pr_debug("AFFS: count_free_blocks()\n");
+
+ if (sb->s_flags & MS_RDONLY)
+ return 0;
+
+ down(&AFFS_SB(sb)->s_bmlock);
+
+ bm = AFFS_SB(sb)->s_bitmap;
+ free = 0;
+ for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
+ free += bm->bm_free;
+
+ up(&AFFS_SB(sb)->s_bmlock);
+
+ return free;
+}
+
+void
+affs_free_block(struct super_block *sb, u32 block)
+{
+ struct affs_sb_info *sbi = AFFS_SB(sb);
+ struct affs_bm_info *bm;
+ struct buffer_head *bh;
+ u32 blk, bmap, bit, mask, tmp;
+ __be32 *data;
+
+ pr_debug("AFFS: free_block(%u)\n", block);
+
+ if (block > sbi->s_partition_size)
+ goto err_range;
+
+ blk = block - sbi->s_reserved;
+ bmap = blk / sbi->s_bmap_bits;
+ bit = blk % sbi->s_bmap_bits;
+ bm = &sbi->s_bitmap[bmap];
+
+ down(&sbi->s_bmlock);
+
+ bh = sbi->s_bmap_bh;
+ if (sbi->s_last_bmap != bmap) {
+ affs_brelse(bh);
+ bh = affs_bread(sb, bm->bm_key);
+ if (!bh)
+ goto err_bh_read;
+ sbi->s_bmap_bh = bh;
+ sbi->s_last_bmap = bmap;
+ }
+
+ mask = 1 << (bit & 31);
+ data = (__be32 *)bh->b_data + bit / 32 + 1;
+
+ /* mark block free */
+ tmp = be32_to_cpu(*data);
+ if (tmp & mask)
+ goto err_free;
+ *data = cpu_to_be32(tmp | mask);
+
+ /* fix checksum */
+ tmp = be32_to_cpu(*(__be32 *)bh->b_data);
+ *(__be32 *)bh->b_data = cpu_to_be32(tmp - mask);
+
+ mark_buffer_dirty(bh);
+ sb->s_dirt = 1;
+ bm->bm_free++;
+
+ up(&sbi->s_bmlock);
+ return;
+
+err_free:
+ affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
+ up(&sbi->s_bmlock);
+ return;
+
+err_bh_read:
+ affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
+ sbi->s_bmap_bh = NULL;
+ sbi->s_last_bmap = ~0;
+ up(&sbi->s_bmlock);
+ return;
+
+err_range:
+ affs_error(sb, "affs_free_block","Block %u outside partition", block);
+ return;
+}
+
+/*
+ * Allocate a block in the given allocation zone.
+ * Since we have to byte-swap the bitmap on little-endian
+ * machines, this is rather expensive. Therefor we will
+ * preallocate up to 16 blocks from the same word, if
+ * possible. We are not doing preallocations in the
+ * header zone, though.
+ */
+
+u32
+affs_alloc_block(struct inode *inode, u32 goal)
+{
+ struct super_block *sb;
+ struct affs_sb_info *sbi;
+ struct affs_bm_info *bm;
+ struct buffer_head *bh;
+ __be32 *data, *enddata;
+ u32 blk, bmap, bit, mask, mask2, tmp;
+ int i;
+
+ sb = inode->i_sb;
+ sbi = AFFS_SB(sb);
+
+ pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
+
+ if (AFFS_I(inode)->i_pa_cnt) {
+ pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
+ AFFS_I(inode)->i_pa_cnt--;
+ return ++AFFS_I(inode)->i_lastalloc;
+ }
+
+ if (!goal || goal > sbi->s_partition_size) {
+ if (goal)
+ affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
+ //if (!AFFS_I(inode)->i_last_block)
+ // affs_warning(sb, "affs_balloc", "no last alloc block");
+ goal = sbi->s_reserved;
+ }
+
+ blk = goal - sbi->s_reserved;
+ bmap = blk / sbi->s_bmap_bits;
+ bm = &sbi->s_bitmap[bmap];
+
+ down(&sbi->s_bmlock);
+
+ if (bm->bm_free)
+ goto find_bmap_bit;
+
+find_bmap:
+ /* search for the next bmap buffer with free bits */
+ i = sbi->s_bmap_count;
+ do {
+ if (--i < 0)
+ goto err_full;
+ bmap++;
+ bm++;
+ if (bmap < sbi->s_bmap_count)
+ continue;
+ /* restart search at zero */
+ bmap = 0;
+ bm = sbi->s_bitmap;
+ } while (!bm->bm_free);
+ blk = bmap * sbi->s_bmap_bits;
+
+find_bmap_bit:
+
+ bh = sbi->s_bmap_bh;
+ if (sbi->s_last_bmap != bmap) {
+ affs_brelse(bh);
+ bh = affs_bread(sb, bm->bm_key);
+ if (!bh)
+ goto err_bh_read;
+ sbi->s_bmap_bh = bh;
+ sbi->s_last_bmap = bmap;
+ }
+
+ /* find an unused block in this bitmap block */
+ bit = blk % sbi->s_bmap_bits;
+ data = (__be32 *)bh->b_data + bit / 32 + 1;
+ enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize);
+ mask = ~0UL << (bit & 31);
+ blk &= ~31UL;
+
+ tmp = be32_to_cpu(*data);
+ if (tmp & mask)
+ goto find_bit;
+
+ /* scan the rest of the buffer */
+ do {
+ blk += 32;
+ if (++data >= enddata)
+ /* didn't find something, can only happen
+ * if scan didn't start at 0, try next bmap
+ */
+ goto find_bmap;
+ } while (!*data);
+ tmp = be32_to_cpu(*data);
+ mask = ~0;
+
+find_bit:
+ /* finally look for a free bit in the word */
+ bit = ffs(tmp & mask) - 1;
+ blk += bit + sbi->s_reserved;
+ mask2 = mask = 1 << (bit & 31);
+ AFFS_I(inode)->i_lastalloc = blk;
+
+ /* prealloc as much as possible within this word */
+ while ((mask2 <<= 1)) {
+ if (!(tmp & mask2))
+ break;
+ AFFS_I(inode)->i_pa_cnt++;
+ mask |= mask2;
+ }
+ bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
+
+ *data = cpu_to_be32(tmp & ~mask);
+
+ /* fix checksum */
+ tmp = be32_to_cpu(*(__be32 *)bh->b_data);
+ *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask);
+
+ mark_buffer_dirty(bh);
+ sb->s_dirt = 1;
+
+ up(&sbi->s_bmlock);
+
+ pr_debug("%d\n", blk);
+ return blk;
+
+err_bh_read:
+ affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
+ sbi->s_bmap_bh = NULL;
+ sbi->s_last_bmap = ~0;
+err_full:
+ up(&sbi->s_bmlock);
+ pr_debug("failed\n");
+ return 0;
+}
+
+int affs_init_bitmap(struct super_block *sb, int *flags)
+{
+ struct affs_bm_info *bm;
+ struct buffer_head *bmap_bh = NULL, *bh = NULL;
+ __be32 *bmap_blk;
+ u32 size, blk, end, offset, mask;
+ int i, res = 0;
+ struct affs_sb_info *sbi = AFFS_SB(sb);
+
+ if (*flags & MS_RDONLY)
+ return 0;
+
+ if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
+ printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n",
+ sb->s_id);
+ *flags |= MS_RDONLY;
+ return 0;
+ }
+
+ sbi->s_last_bmap = ~0;
+ sbi->s_bmap_bh = NULL;
+ sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
+ sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
+ sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
+ size = sbi->s_bmap_count * sizeof(*bm);
+ bm = sbi->s_bitmap = kmalloc(size, GFP_KERNEL);
+ if (!sbi->s_bitmap) {
+ printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
+ return -ENOMEM;
+ }
+ memset(sbi->s_bitmap, 0, size);
+
+ bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
+ blk = sb->s_blocksize / 4 - 49;
+ end = blk + 25;
+
+ for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
+ affs_brelse(bh);
+
+ bm->bm_key = be32_to_cpu(bmap_blk[blk]);
+ bh = affs_bread(sb, bm->bm_key);
+ if (!bh) {
+ printk(KERN_ERR "AFFS: Cannot read bitmap\n");
+ res = -EIO;
+ goto out;
+ }
+ if (affs_checksum_block(sb, bh)) {
+ printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n",
+ bm->bm_key, sb->s_id);
+ *flags |= MS_RDONLY;
+ goto out;
+ }
+ pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key);
+ bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
+
+ /* Don't try read the extension if this is the last block,
+ * but we also need the right bm pointer below
+ */
+ if (++blk < end || i == 1)
+ continue;
+ if (bmap_bh)
+ affs_brelse(bmap_bh);
+ bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
+ if (!bmap_bh) {
+ printk(KERN_ERR "AFFS: Cannot read bitmap extension\n");
+ res = -EIO;
+ goto out;
+ }
+ bmap_blk = (__be32 *)bmap_bh->b_data;
+ blk = 0;
+ end = sb->s_blocksize / 4 - 1;
+ }
+
+ offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
+ mask = ~(0xFFFFFFFFU << (offset & 31));
+ pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
+ offset = offset / 32 + 1;
+
+ if (mask) {
+ u32 old, new;
+
+ /* Mark unused bits in the last word as allocated */
+ old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
+ new = old & mask;
+ //if (old != new) {
+ ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
+ /* fix checksum */
+ //new -= old;
+ //old = be32_to_cpu(*(__be32 *)bh->b_data);
+ //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
+ //mark_buffer_dirty(bh);
+ //}
+ /* correct offset for the bitmap count below */
+ //offset++;
+ }
+ while (++offset < sb->s_blocksize / 4)
+ ((__be32 *)bh->b_data)[offset] = 0;
+ ((__be32 *)bh->b_data)[0] = 0;
+ ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
+ mark_buffer_dirty(bh);
+
+ /* recalculate bitmap count for last block */
+ bm--;
+ bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
+
+out:
+ affs_brelse(bh);
+ affs_brelse(bmap_bh);
+ return res;
+}
+
+void affs_free_bitmap(struct super_block *sb)
+{
+ struct affs_sb_info *sbi = AFFS_SB(sb);
+
+ if (!sbi->s_bitmap)
+ return;
+
+ affs_brelse(sbi->s_bmap_bh);
+ sbi->s_bmap_bh = NULL;
+ sbi->s_last_bmap = ~0;
+ kfree(sbi->s_bitmap);
+ sbi->s_bitmap = NULL;
+}