servers/ext2/ialloc.c

   1 /* This files manages inodes allocation and deallocation.
   2  *
   3  * The entry points into this file are:
   4  *   alloc_inode:  allocate a new, unused inode.
   5  *   free_inode:   mark an inode as available for a new file.
   6  *
   7  * Created (alloc_inode/free_inode/wipe_inode are from MFS):
   8  *   June 2010 (Evgeniy Ivanov)
   9  */
  10
  11 #include "fs.h"
  12 #include <string.h>
  13 #include <stdlib.h>
  14 #include <minix/com.h>
  15 #include <minix/u64.h>
  16 #include "buf.h"
  17 #include "inode.h"
  18 #include "super.h"
  19 #include "const.h"
  20
  21
  22 static bit_t alloc_inode_bit(struct super_block *sp, struct inode
  23         *parent, int is_dir);
  24 static void free_inode_bit(struct super_block *sp, bit_t bit_returned,
  25         int is_dir);
  26 static void wipe_inode(struct inode *rip);
  27
  28
  29 /*===========================================================================*
  30  *                alloc_inode                                                *
  31  *===========================================================================*/
  32 struct inode *alloc_inode(struct inode *parent, mode_t bits)
  33 {
  34 /* Allocate a free inode on parent's dev, and return a pointer to it. */
  35
  36   register struct inode *rip;
  37   register struct super_block *sp;
  38   int inumb;
  39   bit_t b;
  40   static int print_oos_msg = 1;
  41
  42   sp = get_super(parent->i_dev);    /* get pointer to super_block */
  43   if (sp->s_rd_only) {    /* can't allocate an inode on a read only device. */
  44         err_code = EROFS;
  45         return(NULL);
  46   }
  47
  48   /* Acquire an inode from the bit map. */
  49   b = alloc_inode_bit(sp, parent, (bits & I_TYPE) == I_DIRECTORY);
  50   if (b == NO_BIT) {
  51         err_code = ENOSPC;
  52         if (print_oos_msg)
  53                 ext2_debug("Out of i-nodes on device %d/%d\n",
  54                            major(sp->s_dev), minor(sp->s_dev));
  55         print_oos_msg = 0;      /* Don't repeat message */
  56         return(NULL);
  57   }
  58   print_oos_msg = 1;
  59
  60   inumb = (int) b;        /* be careful not to pass unshort as param */
  61
  62   /* Try to acquire a slot in the inode table. */
  63   if ((rip = get_inode(NO_DEV, inumb)) == NULL) {
  64         /* No inode table slots available.  Free the inode just allocated. */
  65         free_inode_bit(sp, b, (bits & I_TYPE) == I_DIRECTORY);
  66   } else {
  67         /* An inode slot is available. Put the inode just allocated into it. */
  68         rip->i_mode = bits;         /* set up RWX bits */
  69         rip->i_links_count = NO_LINK; /* initial no links */
  70         rip->i_uid = caller_uid;    /* file's uid is owner's */
  71         rip->i_gid = caller_gid;    /* ditto group id */
  72         rip->i_dev = parent->i_dev; /* mark which device it is on */
  73         rip->i_sp = sp;             /* pointer to super block */
  74
  75         /* Fields not cleared already are cleared in wipe_inode(). They have
  76          * been put there because truncate() needs to clear the same fields if
  77          * the file happens to be open while being truncated. It saves space
  78          * not to repeat the code twice.
  79          */
  80         wipe_inode(rip);
  81   }
  82
  83   return(rip);
  84 }
  85
  86
  87 /*===========================================================================*
  88  *                free_inode                                                 *
  89  *===========================================================================*/
  90 void free_inode(
  91   register struct inode *rip  /* inode to free */
  92 )
  93 {
  94 /* Return an inode to the pool of unallocated inodes. */
  95   register struct super_block *sp;
  96   dev_t dev = rip->i_dev;
  97   bit_t b = rip->i_num;
  98   u16_t mode = rip->i_mode;
  99
 100   /* Locate the appropriate super_block. */
 101   sp = get_super(dev);
 102
 103   if (b <= NO_ENTRY || b > sp->s_inodes_count)
 104         return;
 105   free_inode_bit(sp, b, (mode & I_TYPE) == I_DIRECTORY);
 106
 107   rip->i_mode = I_NOT_ALLOC;     /* clear I_TYPE field */
 108 }
 109
 110
 111 static int find_group_dir(struct super_block *sp);
 112 static int find_group_hashalloc(struct super_block *sp, struct inode
 113         *parent);
 114 static int find_group_any(struct super_block *sp);
 115 static int find_group_orlov(struct super_block *sp, struct inode
 116         *parent);
 117
 118
 119 /*===========================================================================*
 120  *                              alloc_inode_bit                              *
 121  *===========================================================================*/
 122 static bit_t alloc_inode_bit(sp, parent, is_dir)
 123 struct super_block *sp;         /* the filesystem to allocate from */
 124 struct inode *parent;           /* parent of newly allocated inode */
 125 int is_dir;                     /* inode will be a directory if it is TRUE */
 126 {
 127   int group;
 128   ino_t inumber = NO_BIT;
 129   bit_t bit;
 130   struct buf *bp;
 131   struct group_desc *gd;
 132
 133   if (sp->s_rd_only)
 134         panic("can't alloc inode on read-only filesys.");
 135
 136   if (opt.mfsalloc) {
 137         group = find_group_any(sp);
 138   } else {
 139         if (is_dir) {
 140                 if (opt.use_orlov) {
 141                         group = find_group_orlov(sp, parent);
 142                 } else {
 143                         group = find_group_dir(sp);
 144                 }
 145         } else {
 146                 group = find_group_hashalloc(sp, parent);
 147         }
 148   }
 149   /* Check if we have a group where to allocate an inode */
 150   if (group == -1)
 151         return(NO_BIT); /* no bit could be allocated */
 152
 153   gd = get_group_desc(group);
 154   if (gd == NULL)
 155           panic("can't get group_desc to alloc block");
 156
 157   /* find_group_* should always return either a group with
 158    * a free inode slot or -1, which we checked earlier.
 159    */
 160   ASSERT(gd->free_inodes_count);
 161
 162   bp = get_block(sp->s_dev, gd->inode_bitmap, NORMAL);
 163   bit = setbit(b_bitmap(bp), sp->s_inodes_per_group, 0);
 164   ASSERT(bit != -1); /* group definitly contains free inode */
 165
 166   inumber = group * sp->s_inodes_per_group + bit + 1;
 167
 168   /* Extra checks before real allocation.
 169    * Only major bug can cause problems. Since setbit changed
 170    * bp->b_bitmap there is no way to recover from this bug.
 171    * Should never happen.
 172    */
 173   if (inumber > sp->s_inodes_count) {
 174         panic("ext2: allocator returned inum greater, than\
 175                     total number of inodes.\n");
 176   }
 177
 178   if (inumber < EXT2_FIRST_INO(sp)) {
 179         panic("ext2: allocator tryed to use reserved inode.\n");
 180   }
 181
 182   lmfs_markdirty(bp);
 183   put_block(bp, MAP_BLOCK);
 184
 185   gd->free_inodes_count--;
 186   sp->s_free_inodes_count--;
 187   if (is_dir) {
 188         gd->used_dirs_count++;
 189         sp->s_dirs_counter++;
 190   }
 191
 192   group_descriptors_dirty = 1;
 193
 194   /* Almost the same as previous 'group' ASSERT */
 195   ASSERT(inumber != NO_BIT);
 196   return inumber;
 197 }
 198
 199
 200 /*===========================================================================*
 201  *                          free_inode_bit                                   *
 202  *===========================================================================*/
 203 static void free_inode_bit(struct super_block *sp, bit_t bit_returned,
 204                            int is_dir)
 205 {
 206  /* Return an inode by turning off its bitmap bit. */
 207   int group;            /* group number of bit_returned */
 208   int bit;              /* bit_returned number within its group */
 209   struct buf *bp;
 210   struct group_desc *gd;
 211
 212   if (sp->s_rd_only)
 213         panic("can't free bit on read-only filesys.");
 214
 215   /* At first search group, to which bit_returned belongs to
 216    * and figure out in what word bit is stored.
 217    */
 218   if (bit_returned > sp->s_inodes_count ||
 219       bit_returned < EXT2_FIRST_INO(sp))
 220         panic("trying to free inode %d beyond inodes scope.", bit_returned);
 221
 222   group = (bit_returned - 1) / sp->s_inodes_per_group;
 223   bit = (bit_returned - 1) % sp->s_inodes_per_group; /* index in bitmap */
 224
 225   gd = get_group_desc(group);
 226   if (gd == NULL)
 227         panic("can't get group_desc to alloc block");
 228
 229   bp = get_block(sp->s_dev, gd->inode_bitmap, NORMAL);
 230
 231   if (unsetbit(b_bitmap(bp), bit))
 232         panic("Tried to free unused inode", bit_returned);
 233
 234   lmfs_markdirty(bp);
 235   put_block(bp, MAP_BLOCK);
 236
 237   gd->free_inodes_count++;
 238   sp->s_free_inodes_count++;
 239
 240   if (is_dir) {
 241         gd->used_dirs_count--;
 242         sp->s_dirs_counter--;
 243   }
 244
 245   group_descriptors_dirty = 1;
 246
 247   if (group < sp->s_igsearch)
 248         sp->s_igsearch = group;
 249 }
 250
 251
 252 /* it's implemented very close to the linux' find_group_dir() */
 253 static int find_group_dir(struct super_block *sp)
 254 {
 255   int avefreei = sp->s_free_inodes_count / sp->s_groups_count;
 256   struct group_desc *gd, *best_gd = NULL;
 257   int group, best_group = -1;
 258
 259   for (group = 0; group < sp->s_groups_count; ++group) {
 260         gd = get_group_desc(group);
 261         if (gd == NULL)
 262                 panic("can't get group_desc to alloc inode");
 263         if (gd->free_inodes_count == 0)
 264                 continue;
 265         if (gd->free_inodes_count < avefreei)
 266                 continue;
 267         if (!best_gd ||
 268              gd->free_blocks_count > best_gd->free_blocks_count) {
 269                 best_gd = gd;
 270                 best_group = group;
 271         }
 272   }
 273
 274   return best_group; /* group or -1 */
 275 }
 276
 277
 278 /* Analog of ffs_hashalloc() from *BSD.
 279  * 1) Check parent's for free inodes and blocks.
 280  * 2) Quadradically rehash on the group number.
 281  * 3) Make a linear search for free inode.
 282  */
 283 static int find_group_hashalloc(struct super_block *sp, struct inode *parent)
 284 {
 285   int ngroups = sp->s_groups_count;
 286   struct group_desc *gd;
 287   int group, i;
 288   int parent_group = (parent->i_num - 1) / sp->s_inodes_per_group;
 289
 290   /* Try to place new inode in its parent group */
 291   gd = get_group_desc(parent_group);
 292   if (gd == NULL)
 293         panic("can't get group_desc to alloc inode");
 294   if (gd->free_inodes_count && gd->free_blocks_count)
 295         return parent_group;
 296
 297   /* We can't allocate inode in the parent's group.
 298    * Now we will try to place it in another blockgroup.
 299    * The main idea is still to keep files from the same
 300    * directory together and use different blockgroups for
 301    * files from another directory, which lives in the same
 302    * blockgroup as our parent.
 303    * Thus we will spread things on the disk.
 304    */
 305   group = (parent_group + parent->i_num) % ngroups;
 306
 307   /* Make quadratic probing to find a group with free inodes and blocks. */
 308   for (i = 1; i < ngroups; i <<= 1) {
 309         group += i;
 310         if (group >= ngroups)
 311                 group -= ngroups;
 312         gd = get_group_desc(group);
 313         if (gd == NULL)
 314                 panic("can't get group_desc to alloc inode");
 315         if (gd->free_inodes_count && gd->free_blocks_count)
 316                 return group;
 317   }
 318
 319   /* Still no group for new inode, try linear search.
 320    * Also check parent again (but for free inodes only).
 321    */
 322   group = parent_group;
 323   for (i = 0; i < ngroups; i++, group++) {
 324         if (group >= ngroups)
 325                 group = 0;
 326         gd = get_group_desc(group);
 327         if (gd == NULL)
 328                 panic("can't get group_desc to alloc inode");
 329         if (gd->free_inodes_count)
 330                 return group;
 331   }
 332
 333   return -1;
 334 }
 335
 336
 337 /* Find first group which has free inode slot.
 338  * This is similar to what MFS does.
 339  */
 340 static int find_group_any(struct super_block *sp)
 341 {
 342   int ngroups = sp->s_groups_count;
 343   struct group_desc *gd;
 344   int group = sp->s_igsearch;
 345
 346   for (; group < ngroups; group++) {
 347         gd = get_group_desc(group);
 348         if (gd == NULL)
 349                 panic("can't get group_desc to alloc inode");
 350         if (gd->free_inodes_count) {
 351                 sp->s_igsearch = group;
 352                 return group;
 353         }
 354   }
 355
 356   return -1;
 357 }
 358
 359
 360 /* We try to spread first-level directories (i.e. directories in the root
 361  * or in the directory marked as TOPDIR).
 362  * If there are blockgroups with counts for blocks and inodes less than average
 363  * we return a group with lowest directory count. Otherwise we either
 364  * return a group with good free inodes and blocks counts or just a group
 365  * with free inode.
 366  *
 367  * For other directories we try to find a 'good' group, we consider a group as
 368  * a 'good' if it has enough blocks and inodes (greater than min_blocks and
 369  * min_inodes).
 370  *
 371  */
 372 static int find_group_orlov(struct super_block *sp, struct inode *parent)
 373 {
 374   int avefreei = sp->s_free_inodes_count / sp->s_groups_count;
 375   int avefreeb = sp->s_free_blocks_count / sp->s_groups_count;
 376
 377   int group = -1;
 378   int fallback_group = -1; /* Group with at least 1 free inode */
 379   struct group_desc *gd;
 380   int i;
 381
 382   if (parent->i_num == ROOT_INODE ||
 383       parent->i_flags & EXT2_TOPDIR_FL) {
 384         int best_group = -1;
 385         int best_avefree_group = -1; /* Best value of avefreei/avefreeb */
 386         int best_ndir = sp->s_inodes_per_group;
 387
 388         group = (unsigned int)random();
 389         for (i = 0; i < sp->s_groups_count; i++, group++) {
 390                 if (group >= sp->s_groups_count)
 391                         group = 0;
 392                 gd = get_group_desc(group);
 393                 if (gd == NULL)
 394                         panic("can't get group_desc to alloc inode");
 395                 if (gd->free_inodes_count == 0)
 396                         continue;
 397
 398                 fallback_group = group;
 399
 400                 if (gd->free_inodes_count < avefreei ||
 401                     gd->free_blocks_count < avefreeb)
 402                         continue;
 403
 404                 best_avefree_group  = group;
 405
 406                 if (gd->used_dirs_count >= best_ndir)
 407                         continue;
 408                 best_ndir = gd->used_dirs_count;
 409                 best_group = group;
 410         }
 411         if (best_group >= 0)
 412                 return best_group;
 413         if (best_avefree_group >= 0)
 414                 return best_avefree_group;
 415         return fallback_group;
 416   } else {
 417         int parent_group = (parent->i_num - 1) / sp->s_inodes_per_group;
 418         /* 2 is kind of random thing for now,
 419          * but performance results are still good.
 420          */
 421         int min_blocks = avefreeb / 2;
 422         int min_inodes = avefreei / 2;
 423
 424         group = parent_group;
 425         for (i = 0; i < sp->s_groups_count; i++, group++) {
 426                 if (group >= sp->s_groups_count)
 427                         group = 0;
 428                 gd = get_group_desc(group);
 429                 if (gd == NULL)
 430                         panic("can't get group_desc to alloc inode");
 431                 if (gd->free_inodes_count == 0)
 432                         continue;
 433
 434                 fallback_group = group;
 435
 436                 if (gd->free_inodes_count >= min_inodes &&
 437                     gd->free_blocks_count >= min_blocks)
 438                         return group;
 439         }
 440         return fallback_group;
 441   }
 442
 443   return -1;
 444 }
 445
 446
 447 /*===========================================================================*
 448  *                wipe_inode                                                 *
 449  *===========================================================================*/
 450 static void wipe_inode(
 451   register struct inode *rip     /* the inode to be erased */
 452 )
 453 {
 454 /* Erase some fields in the inode. This function is called from alloc_inode()
 455  * when a new inode is to be allocated, and from truncate(), when an existing
 456  * inode is to be truncated.
 457  */
 458
 459   register int i;
 460
 461   rip->i_size = 0;
 462   rip->i_update = ATIME | CTIME | MTIME;    /* update all times later */
 463   rip->i_blocks = 0;
 464   rip->i_flags = 0;
 465   rip->i_generation = 0;
 466   rip->i_file_acl = 0;
 467   rip->i_dir_acl = 0;
 468   rip->i_faddr = 0;
 469
 470   for (i = 0; i < EXT2_N_BLOCKS; i++)
 471         rip->i_block[i] = NO_BLOCK;
 472   rip->i_block[0] = NO_BLOCK;
 473
 474   rip->i_dirt = IN_DIRTY;
 475 }