servers/mfs/super.c

   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 <minix/com.h>
  17 #include <minix/u64.h>
  18 #include "buf.h"
  19 #include "inode.h"
  20 #include "super.h"
  21 #include "const.h"
  22
  23
  24 /*===========================================================================*
  25  *                              alloc_bit                                    *
  26  *===========================================================================*/
  27 PUBLIC bit_t alloc_bit(sp, map, origin)
  28 struct super_block *sp;         /* the filesystem to allocate from */
  29 int map;                        /* IMAP (inode map) or ZMAP (zone map) */
  30 bit_t origin;                   /* number of bit to start searching at */
  31 {
  32 /* Allocate a bit from a bit map and return its bit number. */
  33
  34   block_t start_block;          /* first bit block */
  35   bit_t map_bits;               /* how many bits are there in the bit map? */
  36   unsigned bit_blocks;          /* how many blocks are there in the bit map? */
  37   unsigned block, word, bcount;
  38   struct buf *bp;
  39   bitchunk_t *wptr, *wlim, k;
  40   bit_t i, b;
  41
  42   if (sp->s_rd_only)
  43         panic(__FILE__,"can't allocate bit on read-only filesys.", NO_NUM);
  44
  45   if (map == IMAP) {
  46         start_block = START_BLOCK;
  47         map_bits = sp->s_ninodes + 1;
  48         bit_blocks = sp->s_imap_blocks;
  49   } else {
  50         start_block = START_BLOCK + sp->s_imap_blocks;
  51         map_bits = sp->s_zones - (sp->s_firstdatazone - 1);
  52         bit_blocks = sp->s_zmap_blocks;
  53   }
  54
  55   /* Figure out where to start the bit search (depends on 'origin'). */
  56   if (origin >= map_bits) origin = 0;   /* for robustness */
  57
  58   /* Locate the starting place. */
  59   block = origin / FS_BITS_PER_BLOCK(sp->s_block_size);
  60   word = (origin % FS_BITS_PER_BLOCK(sp->s_block_size)) / FS_BITCHUNK_BITS;
  61
  62   /* Iterate over all blocks plus one, because we start in the middle. */
  63   bcount = bit_blocks + 1;
  64   do {
  65         bp = get_block(sp->s_dev, start_block + block, NORMAL);
  66         wlim = &bp->b_bitmap[FS_BITMAP_CHUNKS(sp->s_block_size)];
  67
  68         /* Iterate over the words in block. */
  69         for (wptr = &bp->b_bitmap[word]; wptr < wlim; wptr++) {
  70
  71                 /* Does this word contain a free bit? */
  72                 if (*wptr == (bitchunk_t) ~0) continue;
  73
  74                 /* Find and allocate the free bit. */
  75                 k = conv2(sp->s_native, (int) *wptr);
  76                 for (i = 0; (k & (1 << i)) != 0; ++i) {}
  77
  78                 /* Bit number from the start of the bit map. */
  79                 b = ((bit_t) block * FS_BITS_PER_BLOCK(sp->s_block_size))
  80                     + (wptr - &bp->b_bitmap[0]) * FS_BITCHUNK_BITS
  81                     + i;
  82
  83                 /* Don't allocate bits beyond the end of the map. */
  84                 if (b >= map_bits) break;
  85
  86                 /* Allocate and return bit number. */
  87                 k |= 1 << i;
  88                 *wptr = conv2(sp->s_native, (int) k);
  89                 bp->b_dirt = DIRTY;
  90                 put_block(bp, MAP_BLOCK);
  91                 return(b);
  92         }
  93         put_block(bp, MAP_BLOCK);
  94         if (++block >= bit_blocks) block = 0;   /* last block, wrap around */
  95         word = 0;
  96   } while (--bcount > 0);
  97   return(NO_BIT);               /* no bit could be allocated */
  98 }
  99
 100 /*===========================================================================*
 101  *                              free_bit                                     *
 102  *===========================================================================*/
 103 PUBLIC void free_bit(sp, map, bit_returned)
 104 struct super_block *sp;         /* the filesystem to operate on */
 105 int map;                        /* IMAP (inode map) or ZMAP (zone map) */
 106 bit_t bit_returned;             /* number of bit to insert into the map */
 107 {
 108 /* Return a zone or inode by turning off its bitmap bit. */
 109
 110   unsigned block, word, bit;
 111   struct buf *bp;
 112   bitchunk_t k, mask;
 113   block_t start_block;
 114
 115   if (sp->s_rd_only)
 116         panic(__FILE__,"can't free bit on read-only filesys.", NO_NUM);
 117
 118   if (map == IMAP) {
 119         start_block = START_BLOCK;
 120   } else {
 121         start_block = START_BLOCK + sp->s_imap_blocks;
 122   }
 123   block = bit_returned / FS_BITS_PER_BLOCK(sp->s_block_size);
 124   word = (bit_returned % FS_BITS_PER_BLOCK(sp->s_block_size))
 125          / FS_BITCHUNK_BITS;
 126
 127   bit = bit_returned % FS_BITCHUNK_BITS;
 128   mask = 1 << bit;
 129
 130   bp = get_block(sp->s_dev, start_block + block, NORMAL);
 131
 132   k = conv2(sp->s_native, (int) bp->b_bitmap[word]);
 133   if (!(k & mask)) {
 134         panic(__FILE__,map == IMAP ? "tried to free unused inode" :
 135               "tried to free unused block", bit_returned);
 136   }
 137
 138   k &= ~mask;
 139   bp->b_bitmap[word] = conv2(sp->s_native, (int) k);
 140   bp->b_dirt = DIRTY;
 141
 142   put_block(bp, MAP_BLOCK);
 143 }
 144
 145 /*===========================================================================*
 146  *                              get_super                                    *
 147  *===========================================================================*/
 148 PUBLIC struct super_block *get_super(dev)
 149 dev_t dev;                      /* device number whose super_block is sought */
 150 {
 151 /* Search the superblock table for this device.  It is supposed to be there. */
 152
 153   register struct super_block *sp;
 154
 155   if (dev == NO_DEV)
 156         panic(__FILE__,"request for super_block of NO_DEV", NO_NUM);
 157
 158   for (sp = &super_block[0]; sp < &super_block[NR_SUPERS]; sp++)
 159         if (sp->s_dev == dev) return(sp);
 160 printf("MFS(%d)get_super: sp->s_dev: %d, dev: %d\n", SELF_E, sp->s_dev, dev);
 161
 162   /* Search failed.  Something wrong. */
 163   panic(__FILE__,"can't find superblock for device (in decimal)", (int) dev);
 164
 165   return(NIL_SUPER);            /* to keep the compiler and lint quiet */
 166 }
 167
 168 /*===========================================================================*
 169  *                              get_block_size                               *
 170  *===========================================================================*/
 171 PUBLIC int get_block_size(dev_t dev)
 172 {
 173 /* Search the superblock table for this device. */
 174
 175   register struct super_block *sp;
 176
 177   if (dev == NO_DEV)
 178         panic(__FILE__,"request for block size of NO_DEV", NO_NUM);
 179
 180   for (sp = &super_block[0]; sp < &super_block[NR_SUPERS]; sp++) {
 181         if (sp->s_dev == dev) {
 182                 return(sp->s_block_size);
 183         }
 184   }
 185
 186   /* no mounted filesystem? use this block size then. */
 187   return _MIN_BLOCK_SIZE;
 188 }
 189
 190 /*===========================================================================*
 191  *                              mounted                                      *
 192  *===========================================================================*/
 193 /* Report on whether the given inode is on a mounted (or ROOT) file system. */
 194 /*
 195 PUBLIC int mounted(rip)
 196 register struct inode *rip;
 197 {
 198
 199   register struct super_block *sp;
 200   register dev_t dev;
 201
 202   dev = (dev_t) rip->i_zone[0];
 203   if (dev == root_dev) return(TRUE);
 204
 205   for (sp = &super_block[0]; sp < &super_block[NR_SUPERS]; sp++)
 206         if (sp->s_dev == dev) return(TRUE);
 207
 208   return(FALSE);
 209 }
 210 */
 211 /*===========================================================================*
 212  *                              read_super                                   *
 213  *===========================================================================*/
 214 PUBLIC int read_super(sp)
 215 register struct super_block *sp; /* pointer to a superblock */
 216 {
 217 /* Read a superblock. */
 218   dev_t dev;
 219   int magic;
 220   int version, native, r;
 221   static char sbbuf[_MIN_BLOCK_SIZE];
 222
 223   dev = sp->s_dev;              /* save device (will be overwritten by copy) */
 224   if (dev == NO_DEV)
 225         panic(__FILE__,"request for super_block of NO_DEV", NO_NUM);
 226
 227   r = block_dev_io(MFS_DEV_READ, dev, SELF_E,
 228         sbbuf, cvu64(SUPER_BLOCK_BYTES), _MIN_BLOCK_SIZE, 0);
 229   if (r != _MIN_BLOCK_SIZE) {
 230         return EINVAL;
 231   }
 232   memcpy(sp, sbbuf, sizeof(*sp));
 233   sp->s_dev = NO_DEV;           /* restore later */
 234   magic = sp->s_magic;          /* determines file system type */
 235
 236   /* Get file system version and type. */
 237   if (magic == SUPER_MAGIC || magic == conv2(BYTE_SWAP, SUPER_MAGIC)) {
 238         version = V1;
 239         native  = (magic == SUPER_MAGIC);
 240   } else if (magic == SUPER_V2 || magic == conv2(BYTE_SWAP, SUPER_V2)) {
 241         version = V2;
 242         native  = (magic == SUPER_V2);
 243   } else if (magic == SUPER_V3) {
 244         version = V3;
 245         native = 1;
 246   } else {
 247         return(EINVAL);
 248   }
 249
 250   /* If the super block has the wrong byte order, swap the fields; the magic
 251    * number doesn't need conversion. */
 252   sp->s_ninodes =       conv4(native, sp->s_ninodes);
 253   sp->s_nzones =        conv2(native, (int) sp->s_nzones);
 254   sp->s_imap_blocks =   conv2(native, (int) sp->s_imap_blocks);
 255   sp->s_zmap_blocks =   conv2(native, (int) sp->s_zmap_blocks);
 256   sp->s_firstdatazone = conv2(native, (int) sp->s_firstdatazone);
 257   sp->s_log_zone_size = conv2(native, (int) sp->s_log_zone_size);
 258   sp->s_max_size =      conv4(native, sp->s_max_size);
 259   sp->s_zones =         conv4(native, sp->s_zones);
 260
 261   /* In V1, the device size was kept in a short, s_nzones, which limited
 262    * devices to 32K zones.  For V2, it was decided to keep the size as a
 263    * long.  However, just changing s_nzones to a long would not work, since
 264    * then the position of s_magic in the super block would not be the same
 265    * in V1 and V2 file systems, and there would be no way to tell whether
 266    * a newly mounted file system was V1 or V2.  The solution was to introduce
 267    * a new variable, s_zones, and copy the size there.
 268    *
 269    * Calculate some other numbers that depend on the version here too, to
 270    * hide some of the differences.
 271    */
 272   if (version == V1) {
 273         sp->s_block_size = _STATIC_BLOCK_SIZE;
 274         sp->s_zones = sp->s_nzones;     /* only V1 needs this copy */
 275         sp->s_inodes_per_block = V1_INODES_PER_BLOCK;
 276         sp->s_ndzones = V1_NR_DZONES;
 277         sp->s_nindirs = V1_INDIRECTS;
 278   } else {
 279         if (version == V2)
 280                 sp->s_block_size = _STATIC_BLOCK_SIZE;
 281         if (sp->s_block_size < _MIN_BLOCK_SIZE) {
 282                 return EINVAL;
 283         }
 284         sp->s_inodes_per_block = V2_INODES_PER_BLOCK(sp->s_block_size);
 285         sp->s_ndzones = V2_NR_DZONES;
 286         sp->s_nindirs = V2_INDIRECTS(sp->s_block_size);
 287   }
 288
 289   if (sp->s_block_size < _MIN_BLOCK_SIZE) {
 290         return EINVAL;
 291   }
 292   if (sp->s_block_size > _MAX_BLOCK_SIZE) {
 293         printf("Filesystem block size is %d kB; maximum filesystem\n"
 294         "block size is %d kB. This limit can be increased by recompiling.\n",
 295         sp->s_block_size/1024, _MAX_BLOCK_SIZE/1024);
 296         return EINVAL;
 297   }
 298   if ((sp->s_block_size % 512) != 0) {
 299         return EINVAL;
 300   }
 301   if (SUPER_SIZE > sp->s_block_size) {
 302         return EINVAL;
 303   }
 304   if ((sp->s_block_size % V2_INODE_SIZE) != 0 ||
 305      (sp->s_block_size % V1_INODE_SIZE) != 0) {
 306         return EINVAL;
 307   }
 308
 309   /* Limit s_max_size to LONG_MAX */
 310   if ((unsigned long)sp->s_max_size > LONG_MAX)
 311   {
 312         printf("read_super: reducing s_max_size to LONG_MAX\n");
 313         sp->s_max_size= LONG_MAX;
 314   }
 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                                 || (unsigned) sp->s_log_zone_size > 4) {
 325         printf("not enough imap or zone map blocks, \n");
 326         printf("or not enough inodes, or not enough zones, "
 327                 "or zone size too large\n");
 328         return(EINVAL);
 329   }
 330   sp->s_dev = dev;              /* restore device number */
 331   return(OK);
 332 }