1 /* 2 * linux/fs/minix/bitmap.c 3 * 4 * Copyright (C) 1991, 1992 Linus Torvalds 5 */ 6 7 /* 8 * Modified for 680x0 by Hamish Macdonald 9 * Fixed for 680x0 by Andreas Schwab 10 */ 11 12 /* bitmap.c contains the code that handles the inode and block bitmaps */ 13 14 #include "minix.h" 15 #include <linux/buffer_head.h> 16 #include <linux/bitops.h> 17 #include <linux/sched.h> 18 19 static const int nibblemap[] = { 4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0 }; 20 21 static DEFINE_SPINLOCK(bitmap_lock); 22 23 static unsigned long count_free(struct buffer_head *map[], unsigned numblocks, __u32 numbits) 24 { 25 unsigned i, j, sum = 0; 26 struct buffer_head *bh; 27 28 for (i=0; i<numblocks-1; i++) { 29 if (!(bh=map[i])) 30 return(0); 31 for (j=0; j<bh->b_size; j++) 32 sum += nibblemap[bh->b_data[j] & 0xf] 33 + nibblemap[(bh->b_data[j]>>4) & 0xf]; 34 } 35 36 if (numblocks==0 || !(bh=map[numblocks-1])) 37 return(0); 38 i = ((numbits - (numblocks-1) * bh->b_size * 8) / 16) * 2; 39 for (j=0; j<i; j++) { 40 sum += nibblemap[bh->b_data[j] & 0xf] 41 + nibblemap[(bh->b_data[j]>>4) & 0xf]; 42 } 43 44 i = numbits%16; 45 if (i!=0) { 46 i = *(__u16 *)(&bh->b_data[j]) | ~((1<<i) - 1); 47 sum += nibblemap[i & 0xf] + nibblemap[(i>>4) & 0xf]; 48 sum += nibblemap[(i>>8) & 0xf] + nibblemap[(i>>12) & 0xf]; 49 } 50 return(sum); 51 } 52 53 void minix_free_block(struct inode *inode, unsigned long block) 54 { 55 struct super_block *sb = inode->i_sb; 56 struct minix_sb_info *sbi = minix_sb(sb); 57 struct buffer_head *bh; 58 int k = sb->s_blocksize_bits + 3; 59 unsigned long bit, zone; 60 61 if (block < sbi->s_firstdatazone || block >= sbi->s_nzones) { 62 printk("Trying to free block not in datazone\n"); 63 return; 64 } 65 zone = block - sbi->s_firstdatazone + 1; 66 bit = zone & ((1<<k) - 1); 67 zone >>= k; 68 if (zone >= sbi->s_zmap_blocks) { 69 printk("minix_free_block: nonexistent bitmap buffer\n"); 70 return; 71 } 72 bh = sbi->s_zmap[zone]; 73 spin_lock(&bitmap_lock); 74 if (!minix_test_and_clear_bit(bit, bh->b_data)) 75 printk("minix_free_block (%s:%lu): bit already cleared\n", 76 sb->s_id, block); 77 spin_unlock(&bitmap_lock); 78 mark_buffer_dirty(bh); 79 return; 80 } 81 82 int minix_new_block(struct inode * inode) 83 { 84 struct minix_sb_info *sbi = minix_sb(inode->i_sb); 85 int bits_per_zone = 8 * inode->i_sb->s_blocksize; 86 int i; 87 88 for (i = 0; i < sbi->s_zmap_blocks; i++) { 89 struct buffer_head *bh = sbi->s_zmap[i]; 90 int j; 91 92 spin_lock(&bitmap_lock); 93 j = minix_find_first_zero_bit(bh->b_data, bits_per_zone); 94 if (j < bits_per_zone) { 95 minix_set_bit(j, bh->b_data); 96 spin_unlock(&bitmap_lock); 97 mark_buffer_dirty(bh); 98 j += i * bits_per_zone + sbi->s_firstdatazone-1; 99 if (j < sbi->s_firstdatazone || j >= sbi->s_nzones) 100 break; 101 return j; 102 } 103 spin_unlock(&bitmap_lock); 104 } 105 return 0; 106 } 107 108 unsigned long minix_count_free_blocks(struct minix_sb_info *sbi) 109 { 110 return (count_free(sbi->s_zmap, sbi->s_zmap_blocks, 111 sbi->s_nzones - sbi->s_firstdatazone + 1) 112 << sbi->s_log_zone_size); 113 } 114 115 struct minix_inode * 116 minix_V1_raw_inode(struct super_block *sb, ino_t ino, struct buffer_head **bh) 117 { 118 int block; 119 struct minix_sb_info *sbi = minix_sb(sb); 120 struct minix_inode *p; 121 122 if (!ino || ino > sbi->s_ninodes) { 123 printk("Bad inode number on dev %s: %ld is out of range\n", 124 sb->s_id, (long)ino); 125 return NULL; 126 } 127 ino--; 128 block = 2 + sbi->s_imap_blocks + sbi->s_zmap_blocks + 129 ino / MINIX_INODES_PER_BLOCK; 130 *bh = sb_bread(sb, block); 131 if (!*bh) { 132 printk("Unable to read inode block\n"); 133 return NULL; 134 } 135 p = (void *)(*bh)->b_data; 136 return p + ino % MINIX_INODES_PER_BLOCK; 137 } 138 139 struct minix2_inode * 140 minix_V2_raw_inode(struct super_block *sb, ino_t ino, struct buffer_head **bh) 141 { 142 int block; 143 struct minix_sb_info *sbi = minix_sb(sb); 144 struct minix2_inode *p; 145 int minix2_inodes_per_block = sb->s_blocksize / sizeof(struct minix2_inode); 146 147 *bh = NULL; 148 if (!ino || ino > sbi->s_ninodes) { 149 printk("Bad inode number on dev %s: %ld is out of range\n", 150 sb->s_id, (long)ino); 151 return NULL; 152 } 153 ino--; 154 block = 2 + sbi->s_imap_blocks + sbi->s_zmap_blocks + 155 ino / minix2_inodes_per_block; 156 *bh = sb_bread(sb, block); 157 if (!*bh) { 158 printk("Unable to read inode block\n"); 159 return NULL; 160 } 161 p = (void *)(*bh)->b_data; 162 return p + ino % minix2_inodes_per_block; 163 } 164 165 /* Clear the link count and mode of a deleted inode on disk. */ 166 167 static void minix_clear_inode(struct inode *inode) 168 { 169 struct buffer_head *bh = NULL; 170 171 if (INODE_VERSION(inode) == MINIX_V1) { 172 struct minix_inode *raw_inode; 173 raw_inode = minix_V1_raw_inode(inode->i_sb, inode->i_ino, &bh); 174 if (raw_inode) { 175 raw_inode->i_nlinks = 0; 176 raw_inode->i_mode = 0; 177 } 178 } else { 179 struct minix2_inode *raw_inode; 180 raw_inode = minix_V2_raw_inode(inode->i_sb, inode->i_ino, &bh); 181 if (raw_inode) { 182 raw_inode->i_nlinks = 0; 183 raw_inode->i_mode = 0; 184 } 185 } 186 if (bh) { 187 mark_buffer_dirty(bh); 188 brelse (bh); 189 } 190 } 191 192 void minix_free_inode(struct inode * inode) 193 { 194 struct super_block *sb = inode->i_sb; 195 struct minix_sb_info *sbi = minix_sb(inode->i_sb); 196 struct buffer_head *bh; 197 int k = sb->s_blocksize_bits + 3; 198 unsigned long ino, bit; 199 200 ino = inode->i_ino; 201 if (ino < 1 || ino > sbi->s_ninodes) { 202 printk("minix_free_inode: inode 0 or nonexistent inode\n"); 203 return; 204 } 205 bit = ino & ((1<<k) - 1); 206 ino >>= k; 207 if (ino >= sbi->s_imap_blocks) { 208 printk("minix_free_inode: nonexistent imap in superblock\n"); 209 return; 210 } 211 212 minix_clear_inode(inode); /* clear on-disk copy */ 213 214 bh = sbi->s_imap[ino]; 215 spin_lock(&bitmap_lock); 216 if (!minix_test_and_clear_bit(bit, bh->b_data)) 217 printk("minix_free_inode: bit %lu already cleared\n", bit); 218 spin_unlock(&bitmap_lock); 219 mark_buffer_dirty(bh); 220 } 221 222 struct inode *minix_new_inode(const struct inode *dir, int mode, int *error) 223 { 224 struct super_block *sb = dir->i_sb; 225 struct minix_sb_info *sbi = minix_sb(sb); 226 struct inode *inode = new_inode(sb); 227 struct buffer_head * bh; 228 int bits_per_zone = 8 * sb->s_blocksize; 229 unsigned long j; 230 int i; 231 232 if (!inode) { 233 *error = -ENOMEM; 234 return NULL; 235 } 236 j = bits_per_zone; 237 bh = NULL; 238 *error = -ENOSPC; 239 spin_lock(&bitmap_lock); 240 for (i = 0; i < sbi->s_imap_blocks; i++) { 241 bh = sbi->s_imap[i]; 242 j = minix_find_first_zero_bit(bh->b_data, bits_per_zone); 243 if (j < bits_per_zone) 244 break; 245 } 246 if (!bh || j >= bits_per_zone) { 247 spin_unlock(&bitmap_lock); 248 iput(inode); 249 return NULL; 250 } 251 if (minix_test_and_set_bit(j, bh->b_data)) { /* shouldn't happen */ 252 spin_unlock(&bitmap_lock); 253 printk("minix_new_inode: bit already set\n"); 254 iput(inode); 255 return NULL; 256 } 257 spin_unlock(&bitmap_lock); 258 mark_buffer_dirty(bh); 259 j += i * bits_per_zone; 260 if (!j || j > sbi->s_ninodes) { 261 iput(inode); 262 return NULL; 263 } 264 inode_init_owner(inode, dir, mode); 265 inode->i_ino = j; 266 inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME_SEC; 267 inode->i_blocks = 0; 268 memset(&minix_i(inode)->u, 0, sizeof(minix_i(inode)->u)); 269 insert_inode_hash(inode); 270 mark_inode_dirty(inode); 271 272 *error = 0; 273 return inode; 274 } 275 276 unsigned long minix_count_free_inodes(struct minix_sb_info *sbi) 277 { 278 return count_free(sbi->s_imap, sbi->s_imap_blocks, sbi->s_ninodes + 1); 279 } 280