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