1 /* This file manages the super block table and the related data structures, 2 * namely, the bit maps that keep track of which zones and which inodes are 3 * allocated and which are free. When a new inode or zone is needed, the 4 * appropriate bit map is searched for a free entry. 5 * 6 * The entry points into this file are 7 * alloc_bit: somebody wants to allocate a zone or inode; find one 8 * free_bit: indicate that a zone or inode is available for allocation 9 * get_super: search the 'superblock' table for a device 10 * mounted: tells if file inode is on mounted (or ROOT) file system 11 * read_super: read a superblock 12 */ 13 14 #include "fs.h" 15 #include <string.h> 16 #include <assert.h> 17 #include <minix/com.h> 18 #include <minix/u64.h> 19 #include <minix/bdev.h> 20 #include <machine/param.h> 21 #include <machine/vmparam.h> 22 #include "buf.h" 23 #include "inode.h" 24 #include "super.h" 25 #include "const.h" 26 27 static u32_t used_blocks = 0; 28 29 /*===========================================================================* 30 * alloc_bit * 31 *===========================================================================*/ 32 bit_t alloc_bit(sp, map, origin) 33 struct super_block *sp; /* the filesystem to allocate from */ 34 int map; /* IMAP (inode map) or ZMAP (zone map) */ 35 bit_t origin; /* number of bit to start searching at */ 36 { 37 /* Allocate a bit from a bit map and return its bit number. */ 38 39 block_t start_block; /* first bit block */ 40 block_t block; 41 bit_t map_bits; /* how many bits are there in the bit map? */ 42 short bit_blocks; /* how many blocks are there in the bit map? */ 43 unsigned word, bcount; 44 struct buf *bp; 45 bitchunk_t *wptr, *wlim, k; 46 bit_t i, b; 47 48 if (sp->s_rd_only) 49 panic("can't allocate bit on read-only filesys"); 50 51 if (map == IMAP) { 52 start_block = START_BLOCK; 53 map_bits = (bit_t) (sp->s_ninodes + 1); 54 bit_blocks = sp->s_imap_blocks; 55 } else { 56 start_block = START_BLOCK + sp->s_imap_blocks; 57 map_bits = (bit_t) (sp->s_zones - (sp->s_firstdatazone - 1)); 58 bit_blocks = sp->s_zmap_blocks; 59 } 60 61 /* Figure out where to start the bit search (depends on 'origin'). */ 62 if (origin >= map_bits) origin = 0; /* for robustness */ 63 64 /* Locate the starting place. */ 65 block = (block_t) (origin / FS_BITS_PER_BLOCK(sp->s_block_size)); 66 word = (origin % FS_BITS_PER_BLOCK(sp->s_block_size)) / FS_BITCHUNK_BITS; 67 68 /* Iterate over all blocks plus one, because we start in the middle. */ 69 bcount = bit_blocks + 1; 70 do { 71 bp = get_block(sp->s_dev, start_block + block, NORMAL); 72 wlim = &b_bitmap(bp)[FS_BITMAP_CHUNKS(sp->s_block_size)]; 73 74 /* Iterate over the words in block. */ 75 for (wptr = &b_bitmap(bp)[word]; wptr < wlim; wptr++) { 76 77 /* Does this word contain a free bit? */ 78 if (*wptr == (bitchunk_t) ~0) continue; 79 80 /* Find and allocate the free bit. */ 81 k = (bitchunk_t) conv4(sp->s_native, (int) *wptr); 82 for (i = 0; (k & (1 << i)) != 0; ++i) {} 83 84 /* Bit number from the start of the bit map. */ 85 b = ((bit_t) block * FS_BITS_PER_BLOCK(sp->s_block_size)) 86 + (wptr - &b_bitmap(bp)[0]) * FS_BITCHUNK_BITS 87 + i; 88 89 /* Don't allocate bits beyond the end of the map. */ 90 if (b >= map_bits) break; 91 92 /* Allocate and return bit number. */ 93 k |= 1 << i; 94 *wptr = (bitchunk_t) conv4(sp->s_native, (int) k); 95 MARKDIRTY(bp); 96 put_block(bp, MAP_BLOCK); 97 if(map == ZMAP) { 98 used_blocks++; 99 lmfs_blockschange(sp->s_dev, 1); 100 } 101 return(b); 102 } 103 put_block(bp, MAP_BLOCK); 104 if (++block >= (unsigned int) bit_blocks) /* last block, wrap around */ 105 block = 0; 106 word = 0; 107 } while (--bcount > 0); 108 return(NO_BIT); /* no bit could be allocated */ 109 } 110 111 /*===========================================================================* 112 * free_bit * 113 *===========================================================================*/ 114 void free_bit(sp, map, bit_returned) 115 struct super_block *sp; /* the filesystem to operate on */ 116 int map; /* IMAP (inode map) or ZMAP (zone map) */ 117 bit_t bit_returned; /* number of bit to insert into the map */ 118 { 119 /* Return a zone or inode by turning off its bitmap bit. */ 120 121 unsigned block, word, bit; 122 struct buf *bp; 123 bitchunk_t k, mask; 124 block_t start_block; 125 126 if (sp->s_rd_only) 127 panic("can't free bit on read-only filesys"); 128 129 if (map == IMAP) { 130 start_block = START_BLOCK; 131 } else { 132 start_block = START_BLOCK + sp->s_imap_blocks; 133 } 134 block = bit_returned / FS_BITS_PER_BLOCK(sp->s_block_size); 135 word = (bit_returned % FS_BITS_PER_BLOCK(sp->s_block_size)) 136 / FS_BITCHUNK_BITS; 137 138 bit = bit_returned % FS_BITCHUNK_BITS; 139 mask = 1 << bit; 140 141 bp = get_block(sp->s_dev, start_block + block, NORMAL); 142 143 k = (bitchunk_t) conv4(sp->s_native, (int) b_bitmap(bp)[word]); 144 if (!(k & mask)) { 145 if (map == IMAP) panic("tried to free unused inode"); 146 else panic("tried to free unused block: %u", bit_returned); 147 } 148 149 k &= ~mask; 150 b_bitmap(bp)[word] = (bitchunk_t) conv4(sp->s_native, (int) k); 151 MARKDIRTY(bp); 152 153 put_block(bp, MAP_BLOCK); 154 155 if(map == ZMAP) { 156 used_blocks--; 157 lmfs_blockschange(sp->s_dev, -1); 158 } 159 } 160 161 /*===========================================================================* 162 * get_super * 163 *===========================================================================*/ 164 struct super_block *get_super( 165 dev_t dev /* device number whose super_block is sought */ 166 ) 167 { 168 if (dev == NO_DEV) 169 panic("request for super_block of NO_DEV"); 170 171 if(superblock.s_dev != dev) 172 panic("wrong superblock: 0x%x", (int) dev); 173 174 return(&superblock); 175 } 176 177 178 /*===========================================================================* 179 * get_block_size * 180 *===========================================================================*/ 181 unsigned int get_block_size(dev_t dev) 182 { 183 if (dev == NO_DEV) 184 panic("request for block size of NO_DEV"); 185 186 return(lmfs_fs_block_size()); 187 } 188 189 190 /*===========================================================================* 191 * rw_super * 192 *===========================================================================*/ 193 static int rw_super(struct super_block *sp, int writing) 194 { 195 /* Read/write a superblock. */ 196 int r; 197 dev_t save_dev = sp->s_dev; 198 struct buf *bp; 199 char *sbbuf; 200 201 /* To keep the 1kb on disk clean, only read/write up to and including 202 * this field. 203 */ 204 #define LAST_ONDISK_FIELD s_disk_version 205 int ondisk_bytes = (int) ((char *) &sp->LAST_ONDISK_FIELD - (char *) sp) 206 + sizeof(sp->LAST_ONDISK_FIELD); 207 208 assert(ondisk_bytes > 0); 209 assert(ondisk_bytes < PAGE_SIZE); 210 assert(ondisk_bytes < sizeof(struct super_block)); 211 212 if (sp->s_dev == NO_DEV) 213 panic("request for super_block of NO_DEV"); 214 215 /* we rely on the cache blocksize, before reading the 216 * superblock, being big enough that our complete superblock 217 * is in block 0. 218 * 219 * copy between the disk block and the superblock buffer (depending 220 * on direction). mark the disk block dirty if the copy is into the 221 * disk block. 222 */ 223 assert(lmfs_fs_block_size() >= sizeof(struct super_block) + SUPER_BLOCK_BYTES); 224 assert(SUPER_BLOCK_BYTES >= sizeof(struct super_block)); 225 assert(SUPER_BLOCK_BYTES >= ondisk_bytes); 226 if(!(bp = get_block(sp->s_dev, 0, NORMAL))) 227 panic("get_block of superblock failed"); 228 229 /* sbbuf points to the disk block at the superblock offset */ 230 sbbuf = (char *) b_data(bp) + SUPER_BLOCK_BYTES; 231 232 if(writing) { 233 memset(b_data(bp), 0, lmfs_fs_block_size()); 234 memcpy(sbbuf, sp, ondisk_bytes); 235 lmfs_markdirty(bp); 236 } else { 237 memset(sp, 0, sizeof(*sp)); 238 memcpy(sp, sbbuf, ondisk_bytes); 239 sp->s_dev = save_dev; 240 } 241 242 put_block(bp, FULL_DATA_BLOCK); 243 lmfs_flushall(); 244 245 return OK; 246 } 247 248 /*===========================================================================* 249 * read_super * 250 *===========================================================================*/ 251 int read_super(struct super_block *sp) 252 { 253 unsigned int magic; 254 block_t offset; 255 int version, native, r; 256 257 if((r=rw_super(sp, 0)) != OK) 258 return r; 259 260 magic = sp->s_magic; /* determines file system type */ 261 262 if(magic == SUPER_V2 || magic == SUPER_MAGIC) { 263 printf("MFS: only supports V3 filesystems.\n"); 264 return EINVAL; 265 } 266 267 /* Get file system version and type - only support v3. */ 268 if(magic != SUPER_V3) { 269 return EINVAL; 270 } 271 version = V3; 272 native = 1; 273 274 /* If the super block has the wrong byte order, swap the fields; the magic 275 * number doesn't need conversion. */ 276 sp->s_ninodes = (ino_t) conv4(native, (int) sp->s_ninodes); 277 sp->s_nzones = (zone1_t) conv2(native, (int) sp->s_nzones); 278 sp->s_imap_blocks = (short) conv2(native, (int) sp->s_imap_blocks); 279 sp->s_zmap_blocks = (short) conv2(native, (int) sp->s_zmap_blocks); 280 sp->s_firstdatazone_old =(zone1_t)conv2(native,(int)sp->s_firstdatazone_old); 281 sp->s_log_zone_size = (short) conv2(native, (int) sp->s_log_zone_size); 282 sp->s_max_size = (off_t) conv4(native, sp->s_max_size); 283 sp->s_zones = (zone_t)conv4(native, sp->s_zones); 284 285 /* Calculate some other numbers that depend on the version here too, to 286 * hide some of the differences. 287 */ 288 assert(version == V3); 289 sp->s_block_size = (unsigned short) conv2(native,(int) sp->s_block_size); 290 if (sp->s_block_size < PAGE_SIZE) { 291 return EINVAL; 292 } 293 sp->s_inodes_per_block = V2_INODES_PER_BLOCK(sp->s_block_size); 294 sp->s_ndzones = V2_NR_DZONES; 295 sp->s_nindirs = V2_INDIRECTS(sp->s_block_size); 296 297 /* For even larger disks, a similar problem occurs with s_firstdatazone. 298 * If the on-disk field contains zero, we assume that the value was too 299 * large to fit, and compute it on the fly. 300 */ 301 if (sp->s_firstdatazone_old == 0) { 302 offset = START_BLOCK + sp->s_imap_blocks + sp->s_zmap_blocks; 303 offset += (sp->s_ninodes + sp->s_inodes_per_block - 1) / 304 sp->s_inodes_per_block; 305 306 sp->s_firstdatazone = (offset + (1 << sp->s_log_zone_size) - 1) >> 307 sp->s_log_zone_size; 308 } else { 309 sp->s_firstdatazone = (zone_t) sp->s_firstdatazone_old; 310 } 311 312 if (sp->s_block_size < PAGE_SIZE) 313 return(EINVAL); 314 315 if ((sp->s_block_size % 512) != 0) 316 return(EINVAL); 317 318 if (SUPER_SIZE > sp->s_block_size) 319 return(EINVAL); 320 321 if ((sp->s_block_size % V2_INODE_SIZE) != 0) { 322 return(EINVAL); 323 } 324 325 /* Limit s_max_size to LONG_MAX */ 326 if ((unsigned long)sp->s_max_size > LONG_MAX) 327 sp->s_max_size = LONG_MAX; 328 329 sp->s_isearch = 0; /* inode searches initially start at 0 */ 330 sp->s_zsearch = 0; /* zone searches initially start at 0 */ 331 sp->s_version = version; 332 sp->s_native = native; 333 334 /* Make a few basic checks to see if super block looks reasonable. */ 335 if (sp->s_imap_blocks < 1 || sp->s_zmap_blocks < 1 336 || sp->s_ninodes < 1 || sp->s_zones < 1 337 || sp->s_firstdatazone <= 4 338 || sp->s_firstdatazone >= sp->s_zones 339 || (unsigned) sp->s_log_zone_size > 4) { 340 printf("not enough imap or zone map blocks, \n"); 341 printf("or not enough inodes, or not enough zones, \n" 342 "or invalid first data zone, or zone size too large\n"); 343 return(EINVAL); 344 } 345 346 347 /* Check any flags we don't understand but are required to. Currently 348 * these don't exist so all such unknown bits are fatal. 349 */ 350 if(sp->s_flags & MFSFLAG_MANDATORY_MASK) { 351 printf("MFS: unsupported feature flags on this FS.\n" 352 "Please use a newer MFS to mount it.\n"); 353 return(EINVAL); 354 } 355 356 return(OK); 357 } 358 359 /*===========================================================================* 360 * write_super * 361 *===========================================================================*/ 362 int write_super(struct super_block *sp) 363 { 364 if(sp->s_rd_only) 365 panic("can't write superblock of readonly filesystem"); 366 return rw_super(sp, 1); 367 } 368 369 static int blocks_known = 0; 370 371 u32_t get_used_blocks(struct super_block *sp) 372 { 373 if(!blocks_known) { 374 /* how many blocks are in use? */ 375 used_blocks = sp->s_zones - count_free_bits(sp, ZMAP); 376 blocks_known = 1; 377 } 378 return used_blocks; 379 } 380