patch-pre2.0.6 linux/fs/affs/bitmap.c

• Lines: 445
• Date: Sun May 19 15:22:19 1996
• Orig file: pre2.0.5/linux/fs/affs/bitmap.c
• Orig date: Fri May 17 15:32:17 1996

diff -u --recursive --new-file pre2.0.5/linux/fs/affs/bitmap.c linux/fs/affs/bitmap.c
@@ -2,24 +2,28 @@
  *  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.
  */
 
-/* bitmap.c contains the code that handles the inode and block bitmaps */
-
 #include <linux/sched.h>
 #include <linux/affs_fs.h>
 #include <linux/stat.h>
 #include <linux/kernel.h>
 #include <linux/string.h>
-#include <linux/amigaffs.h>
 #include <linux/locks.h>
+#include <linux/amigaffs.h>
 
 #include <asm/bitops.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 };
 
 int
-affs_count_free_bits(int blocksize, const UBYTE *data)
+affs_count_free_bits(int blocksize, const char *data)
 {
   int	 free;
   int	 i;
@@ -42,94 +46,111 @@
 
 	free = 0;
 	if (s->u.affs_sb.s_flags & SF_BM_VALID) {
-		for (i = 0; i < s->u.affs_sb.s_bm_count; i++) {
-			free += s->u.affs_sb.s_bitmap[i].bm_free;
+		for (i = 0; i < s->u.affs_sb.s_num_az; i++) {
+			free += s->u.affs_sb.s_alloc[i].az_free;
 		}
 	}
 	return free;
 }
 
 void
-affs_free_block(struct super_block *sb, LONG block)
+affs_free_block(struct super_block *sb, int block)
 {
 	int			 bmap;
 	int			 bit;
-	ULONG			 blk;
+	int			 blk;
+	int			 zone_no;
 	struct affs_bm_info	*bm;
 
 	pr_debug("AFFS: free_block(%d)\n",block);
 
-	blk    = block - sb->u.affs_sb.s_reserved;
-	bmap   = blk / (sb->s_blocksize * 8 - 32);
-	bit    = blk % (sb->s_blocksize * 8 - 32);
-	bm     = &sb->u.affs_sb.s_bitmap[bmap];
-	if (bmap >= sb->u.affs_sb.s_bm_count || bit >= bm->bm_size) {
+	blk     = block - sb->u.affs_sb.s_reserved;
+	bmap    = blk / (sb->s_blocksize * 8 - 32);
+	bit     = blk % (sb->s_blocksize * 8 - 32);
+	zone_no = (bmap << (sb->s_blocksize_bits - 7)) + bit / 1024;
+	bm      = &sb->u.affs_sb.s_bitmap[bmap];
+	if (bmap >= sb->u.affs_sb.s_bm_count) {
 		printk("AFFS: free_block(): block %d outside partition.\n",block);
 		return;
 	}
-	blk  = 0;
+	blk = 0;
 	set_bit(bit & 31,&blk);
 
 	lock_super(sb);
+	bm->bm_count++;
+	if (!bm->bm_bh) {
+		bm->bm_bh = affs_bread(sb->s_dev,bm->bm_key,sb->s_blocksize);
+		if (!bm->bm_bh) {
+			bm->bm_count--;
+			unlock_super(sb);
+			printk("AFFS: free_block(): Cannot read bitmap block %d\n",bm->bm_key);
+			return;
+		}
+	}
 	if (set_bit(bit ^ BO_EXBITS,bm->bm_bh->b_data + 4))
 		printk("AFFS: free_block(): block %d is already free.\n",block);
 	else {
-		bm->bm_free++;
-		((ULONG *)bm->bm_bh->b_data)[0] = ntohl(htonl(((ULONG *)bm->bm_bh->b_data)[0]) - blk);
+		sb->u.affs_sb.s_alloc[zone_no].az_free++;
+		((__u32 *)bm->bm_bh->b_data)[0] = ntohl(htonl(((__u32 *)bm->bm_bh->b_data)[0]) - blk);
 		mark_buffer_dirty(bm->bm_bh,1);
 		sb->s_dirt = 1;
 	}
+	if (--bm->bm_count == 0) {
+		affs_brelse(bm->bm_bh);
+		bm->bm_bh = NULL;
+	}
 	unlock_super(sb);
 }
 
-static ULONG
+static int
 affs_balloc(struct inode *inode, int zone_no)
 {
-	ULONG			 w;
-	ULONG			*bm;
+	__u32			 w;
+	__u32			*bm;
 	int			 fb;
 	int			 i;
 	int			 fwb;
-	ULONG			 block;
+	int			 block;
 	struct affs_zone	*zone;
+	struct affs_alloc_zone	*az;
 	struct super_block	*sb;
 
 	sb   = inode->i_sb;
 	zone = &sb->u.affs_sb.s_zones[zone_no];
 
-	if (!zone || !zone->z_bm || !zone->z_bm->bm_bh)
-		return 0;
-	
+	if (!zone->z_bm || !zone->z_bm->bm_bh)
+		return 0;	
+
 	pr_debug("AFFS: balloc(inode=%lu,zone=%d)\n",inode->i_ino,zone_no);
 
-	bm = (ULONG *)zone->z_bm->bm_bh->b_data;
+	az = &sb->u.affs_sb.s_alloc[zone->z_az_no];
+	bm = (__u32 *)zone->z_bm->bm_bh->b_data;
 repeat:
-	fb = (zone->z_bm->bm_size + 31) >> 5;
-	for (i = zone->z_start; i <= fb; i++) {
+	for (i = zone->z_start; i < zone->z_end; i++) {
 		if (bm[i])
 			goto found;
 	}
-	return 0;
+	return 0;	
 
 found:
 	fwb = zone->z_bm->bm_firstblk + (i - 1) * 32;
 	lock_super(sb);
 	zone->z_start = i;
-	w   = htonl(bm[i]);
-	fb  = find_first_one_bit(&w,32);
+	w   = ~htonl(bm[i]);
+	fb  = find_first_zero_bit(&w,32);
 	if (fb > 31 || !clear_bit(fb ^ BO_EXBITS,&bm[i])) {
 		unlock_super(sb);
 		printk("AFFS: balloc(): empty block disappeared somehow\n");
 		goto repeat;
 	}
 	block = fwb + fb;
-	zone->z_bm->bm_free--;
+	az->az_free--;
 
-	/* prealloc as much as possible within this word, but not for headers */
+	/* prealloc as much as possible within this word, but not in header zone */
 
 	if (zone_no) {
 		while (inode->u.affs_i.i_pa_cnt < MAX_PREALLOC && ++fb < 32) {
-			fb = find_next_one_bit(&w,32,fb);
+			fb = find_next_zero_bit(&w,32,fb);
 			if (fb > 31)
 				break;
 			if (!clear_bit(fb ^ BO_EXBITS,&bm[i])) {
@@ -139,102 +160,129 @@
 			inode->u.affs_i.i_data[inode->u.affs_i.i_pa_last++] = fwb + fb;
 			inode->u.affs_i.i_pa_last &= MAX_PREALLOC - 1;
 			inode->u.affs_i.i_pa_cnt++;
-			zone->z_bm->bm_free--;
+			az->az_free--;
 		}
 	}
-	w    -= htonl(bm[i]);
+	w     = ~w - htonl(bm[i]);
 	bm[0] = ntohl(htonl(bm[0]) + w);
 	unlock_super(sb);
 	mark_buffer_dirty(zone->z_bm->bm_bh,1);
+	zone->z_lru_time = jiffies;
 
 	return block;
 }
 
-static void
-affs_find_new_zone(struct super_block *sb,struct affs_zone *z, int minfree, int start)
+static int
+affs_find_new_zone(struct super_block *sb, int zone_no)
 {
 	struct affs_bm_info	*bm;
-	int			 offs;
-	int			 zone;
-	int			 free;
-	int			 len;
+	struct affs_zone	*zone;
+	struct affs_alloc_zone	*az;
+	int			 bestfree;
+	int			 bestno;
+	int			 bestused;
+	int			 lusers;
+	int			 i;
+	int			 min;
 
-	pr_debug("AFFS: find_new_zone()\n");
+	pr_debug("AFFS: find_new_zone(zone_no=%d)\n",zone_no);
 
+	bestfree = 0;
+	bestused = -1;
+	bestno   = -1;
+	lusers   = MAX_ZONES;
+	min      = zone_no ? AFFS_DATA_MIN_FREE : AFFS_HDR_MIN_FREE;
 	lock_super(sb);
-
-	zone    = start;
-	z->z_bm = NULL;
-	while (1) {
-		if (zone >= sb->u.affs_sb.s_num_zones) {
-			zone = 0;
-			continue;
+	zone = &sb->u.affs_sb.s_zones[zone_no];
+	i    = zone->z_az_no;
+	az   = &sb->u.affs_sb.s_alloc[i];
+	if (zone->z_bm && zone->z_bm->bm_count) {
+		if (--zone->z_bm->bm_count == 0) {
+			affs_brelse(zone->z_bm->bm_bh);
+			zone->z_bm->bm_bh = NULL;
 		}
+		if (az->az_count)
+			az->az_count--;
+		else
+			printk("AFFS: find_new_zone(): az_count=0, but bm used\n");
 
-		if (!set_bit(zone,sb->u.affs_sb.s_zonemap)) {
-			bm   = &sb->u.affs_sb.s_bitmap[zone >> (sb->s_blocksize_bits - 8)];
-			offs = zone * 256 & (sb->s_blocksize - 1);
-			len  = bm->bm_size / 8 - offs;
-			if (len > 256)
-				len = 256;
-			offs += 4;
-			free  = affs_count_free_bits(len,(char *)bm->bm_bh->b_data + offs);
-			if (free && (100 * free) / (len * 8) > minfree) {
-				z->z_bm       = bm;
-				z->z_start    = offs / 4;
-				z->z_ino      = 0;
-				z->z_zone_no  = zone;
-				pr_debug("  ++ found zone (%d) in bh %d at offset %d with %d free blocks\n",
-					zone,(zone >> (sb->s_blocksize_bits - 8)),offs,free);
+	}
+	while (1) {
+		if (i >= sb->u.affs_sb.s_num_az)
+			i = 0;
+		az = &sb->u.affs_sb.s_alloc[i];
+		if (!az->az_count) {
+			if (az->az_free > min) {
 				break;
 			}
-			clear_bit(zone,sb->u.affs_sb.s_zonemap);
+			if (az->az_free > bestfree) {
+				bestfree = az->az_free;
+				bestno   = i;
+			}
+		} else if (az->az_free && az->az_count < lusers) {
+			lusers   = az->az_count;
+			bestused = i;
 		}
-
-		/* Skip to next possible zone */
-
-		pr_debug("  ++ Skipping to next zone\n");
-		if (++zone == start)
+		if (++i == zone->z_az_no) {		/* Seen all */
+			if (bestno >= 0) {
+				i = bestno;
+			} else {
+				i = bestused;
+			}
 			break;
+		}
+	}
+	if (i < 0) {
+		/* Didn't find a single free block anywhere. */
+		unlock_super(sb);
+		return 0;
+	}
+	az = &sb->u.affs_sb.s_alloc[i];
+	az->az_count++;
+	bm = &sb->u.affs_sb.s_bitmap[i >> (sb->s_blocksize_bits - 7)];
+	bm->bm_count++;
+	if (!bm->bm_bh)
+		bm->bm_bh = affs_bread(sb->s_dev,bm->bm_key,sb->s_blocksize);
+	if (!bm->bm_bh) {
+		bm->bm_count--;
+		az->az_count--;
+		unlock_super(sb);
+		printk("AFFS: find_new_zone(): Cannot read bitmap\n");
+		return 0;
 	}
+	zone->z_bm    = bm;
+	zone->z_start = (i & ((sb->s_blocksize / 128) - 1)) * 32 + 1;
+	zone->z_end   = zone->z_start + az->az_size;
+	zone->z_az_no = i;
+	zone->z_lru_time = jiffies;
+	pr_debug("  ++ found zone (%d) in bm %d at lw offset %d with %d free blocks\n",
+		 i,(i >> (sb->s_blocksize_bits - 7)),zone->z_start,az->az_free);
 	unlock_super(sb);
-	return;
+	return az->az_free;
 }
 
-LONG
+int
 affs_new_header(struct inode *inode)
 {
-	struct affs_zone	*zone;
-	LONG			 block;
-	struct super_block	*sb;
+	int			 block;
 	struct buffer_head	*bh;
 
-	sb   = inode->i_sb;
-	zone = &sb->u.affs_sb.s_zones[0];
-
-	/* We try up to 3 times to find a free block:
-	 * If there is no more room in the current header zone,
-	 * we try to get a new one and allocate the block there.
-	 * If there is no zone with at least AFFS_HDR_MIN_FREE
-	 * percent of free blocks, we try to find a zone with
-	 * at least one free block.
-	 */
+	pr_debug("AFFS: new_header(ino=%lu)\n",inode->i_ino);
 
 	if (!(block = affs_balloc(inode,0))) {
-		clear_bit(zone->z_zone_no,sb->u.affs_sb.s_zonemap);
-		affs_find_new_zone(sb,zone,AFFS_HDR_MIN_FREE,(sb->u.affs_sb.s_num_zones + 1) / 2);
-		if (!(block = affs_balloc(inode,0))) {
-			clear_bit(zone->z_zone_no,sb->u.affs_sb.s_zonemap);
-			affs_find_new_zone(sb,zone,0,(sb->u.affs_sb.s_num_zones + 1) / 2);
-			if (!(block = affs_balloc(inode,0)))
-				return 0;
+		while(affs_find_new_zone(inode->i_sb,0)) {
+			if ((block = affs_balloc(inode,0)))
+				goto init_block;
+			schedule();
 		}
+		return 0;
 	}
-	if (!(bh = getblk(inode->i_dev,block,sb->s_blocksize))) {
+init_block:
+	if (!(bh = getblk(inode->i_dev,block,AFFS_I2BSIZE(inode)))) {
 		printk("AFFS: balloc(): cannot read block %d\n",block);
 		return 0;
 	}
-	memset(bh->b_data,0,sb->s_blocksize);
+	memset(bh->b_data,0,AFFS_I2BSIZE(inode));
 	mark_buffer_uptodate(bh,1);
 	mark_buffer_dirty(bh,1);
 	affs_brelse(bh);
@@ -242,7 +290,7 @@
 	return block;
 }
 
-LONG
+int
 affs_new_data(struct inode *inode)
 {
 	int			 empty, old;
@@ -251,7 +299,7 @@
 	struct super_block	*sb;
 	struct buffer_head	*bh;
 	int			 i = 0;
-	LONG			 block;
+	int			 block;
 
 	pr_debug("AFFS: new_data(ino=%lu)\n",inode->i_ino);
 
@@ -265,7 +313,6 @@
 		goto init_block;
 	}
 	unlock_super(sb);
-repeat:
 	oldest = jiffies;
 	old    = 0;
 	empty  = 0;
@@ -287,19 +334,25 @@
 		i = empty;
 	else if (old)
 		i = old;
-	else
+	else {
+		inode->u.affs_i.i_zone = 0;
 		return affs_new_header(inode);
+	}
 
 	inode->u.affs_i.i_zone = i;
 	zone->z_ino            = inode->i_ino;
 
 found:
 	zone = &sb->u.affs_sb.s_zones[i];
-	if (!(block = affs_balloc(inode,i))) {				/* Zone is full */
-		clear_bit(zone->z_zone_no,sb->u.affs_sb.s_zonemap);
-		affs_find_new_zone(sb,zone,AFFS_DATA_MIN_FREE,sb->u.affs_sb.s_nextzone);
-		sb->u.affs_sb.s_nextzone = zone->z_zone_no + 1;
-		goto repeat;
+	if (!(block = affs_balloc(inode,i))) {		/* No data zones left */
+		while(affs_find_new_zone(sb,i)) {
+			if ((block = affs_balloc(inode,i)))
+				goto init_block;
+			schedule();
+		}
+		inode->u.affs_i.i_zone = 0;
+		zone->z_ino            = -1;
+		return 0;
 	}
 
 init_block:
@@ -318,15 +371,15 @@
 void
 affs_make_zones(struct super_block *sb)
 {
-	int	 i, j;
-
-	pr_debug("AFFS: make_zones(): num_zones=%d\n",sb->u.affs_sb.s_num_zones);
+	int	 i, mid;
 
-	j = (sb->u.affs_sb.s_num_zones + 1) / 2;
+	pr_debug("AFFS: make_zones(): num_zones=%d\n",sb->u.affs_sb.s_num_az);
 
-	affs_find_new_zone(sb,&sb->u.affs_sb.s_zones[0],AFFS_HDR_MIN_FREE,j);
+	mid = (sb->u.affs_sb.s_num_az + 1) / 2;
+	sb->u.affs_sb.s_zones[0].z_az_no = mid;
+	affs_find_new_zone(sb,0);
 	for (i = 1; i < MAX_ZONES; i++) {
-		affs_find_new_zone(sb,&sb->u.affs_sb.s_zones[i],AFFS_DATA_MIN_FREE,j);
-		j = sb->u.affs_sb.s_zones[i].z_zone_no + 1;
+		sb->u.affs_sb.s_zones[i].z_az_no = mid;
+		affs_find_new_zone(sb,i);
 	}
 }