fs/ext2/ialloc.c

   1 /*
   2  *  linux/fs/ext2/ialloc.c
   3  *
   4  * Copyright (C) 1992, 1993, 1994, 1995
   5  * Remy Card (card@masi.ibp.fr)
   6  * Laboratoire MASI - Institut Blaise Pascal
   7  * Universite Pierre et Marie Curie (Paris VI)
   8  *
   9  *  BSD ufs-inspired inode and directory allocation by
  10  *  Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
  11  *  Big-endian to little-endian byte-swapping/bitmaps by
  12  *        David S. Miller (davem@caip.rutgers.edu), 1995
  13  */
  14
  15 #include <linux/config.h>
  16 #include <linux/fs.h>
  17 #include <linux/locks.h>
  18 #include <linux/quotaops.h>
  19
  20
  21 /*
  22  * ialloc.c contains the inodes allocation and deallocation routines
  23  */
  24
  25 /*
  26  * The free inodes are managed by bitmaps.  A file system contains several
  27  * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
  28  * block for inodes, N blocks for the inode table and data blocks.
  29  *
  30  * The file system contains group descriptors which are located after the
  31  * super block.  Each descriptor contains the number of the bitmap block and
  32  * the free blocks count in the block.  The descriptors are loaded in memory
  33  * when a file system is mounted (see ext2_read_super).
  34  */
  35
  36
  37 /*
  38  * Read the inode allocation bitmap for a given block_group, reading
  39  * into the specified slot in the superblock's bitmap cache.
  40  *
  41  * Return >=0 on success or a -ve error code.
  42  */
  43 static int read_inode_bitmap (struct super_block * sb,
  44                                unsigned long block_group,
  45                                unsigned int bitmap_nr)
  46 {
  47         struct ext2_group_desc * gdp;
  48         struct buffer_head * bh = NULL;
  49         int retval = 0;
  50
  51         gdp = ext2_get_group_desc (sb, block_group, NULL);
  52         if (!gdp) {
  53                 retval = -EIO;
  54                 goto error_out;
  55         }
  56         bh = bread (sb->s_dev, le32_to_cpu(gdp->bg_inode_bitmap), sb->s_blocksize);
  57         if (!bh) {
  58                 ext2_error (sb, "read_inode_bitmap",
  59                             "Cannot read inode bitmap - "
  60                             "block_group = %lu, inode_bitmap = %lu",
  61                             block_group, (unsigned long) gdp->bg_inode_bitmap);
  62                 retval = -EIO;
  63         }
  64         /*
  65          * On IO error, just leave a zero in the superblock's block pointer for
  66          * this group.  The IO will be retried next time.
  67          */
  68 error_out:
  69         sb->u.ext2_sb.s_inode_bitmap_number[bitmap_nr] = block_group;
  70         sb->u.ext2_sb.s_inode_bitmap[bitmap_nr] = bh;
  71         return retval;
  72 }
  73
  74 /*
  75  * load_inode_bitmap loads the inode bitmap for a blocks group
  76  *
  77  * It maintains a cache for the last bitmaps loaded.  This cache is managed
  78  * with a LRU algorithm.
  79  *
  80  * Notes:
  81  * 1/ There is one cache per mounted file system.
  82  * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
  83  *    this function reads the bitmap without maintaining a LRU cache.
  84  *
  85  * Return the slot used to store the bitmap, or a -ve error code.
  86  */
  87 static int load_inode_bitmap (struct super_block * sb,
  88                               unsigned int block_group)
  89 {
  90         int i, j, retval = 0;
  91         unsigned long inode_bitmap_number;
  92         struct buffer_head * inode_bitmap;
  93
  94         if (block_group >= sb->u.ext2_sb.s_groups_count)
  95                 ext2_panic (sb, "load_inode_bitmap",
  96                             "block_group >= groups_count - "
  97                             "block_group = %d, groups_count = %lu",
  98                              block_group, sb->u.ext2_sb.s_groups_count);
  99         if (sb->u.ext2_sb.s_loaded_inode_bitmaps > 0 &&
 100             sb->u.ext2_sb.s_inode_bitmap_number[0] == block_group &&
 101             sb->u.ext2_sb.s_inode_bitmap[0] != NULL)
 102                 return 0;
 103         if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED) {
 104                 if (sb->u.ext2_sb.s_inode_bitmap[block_group]) {
 105                         if (sb->u.ext2_sb.s_inode_bitmap_number[block_group] != block_group)
 106                                 ext2_panic (sb, "load_inode_bitmap",
 107                                             "block_group != inode_bitmap_number");
 108                         else
 109                                 return block_group;
 110                 } else {
 111                         retval = read_inode_bitmap (sb, block_group,
 112                                                     block_group);
 113                         if (retval < 0)
 114                                 return retval;
 115                         return block_group;
 116                 }
 117         }
 118
 119         for (i = 0; i < sb->u.ext2_sb.s_loaded_inode_bitmaps &&
 120                     sb->u.ext2_sb.s_inode_bitmap_number[i] != block_group;
 121              i++)
 122                 ;
 123         if (i < sb->u.ext2_sb.s_loaded_inode_bitmaps &&
 124             sb->u.ext2_sb.s_inode_bitmap_number[i] == block_group) {
 125                 inode_bitmap_number = sb->u.ext2_sb.s_inode_bitmap_number[i];
 126                 inode_bitmap = sb->u.ext2_sb.s_inode_bitmap[i];
 127                 for (j = i; j > 0; j--) {
 128                         sb->u.ext2_sb.s_inode_bitmap_number[j] =
 129                                 sb->u.ext2_sb.s_inode_bitmap_number[j - 1];
 130                         sb->u.ext2_sb.s_inode_bitmap[j] =
 131                                 sb->u.ext2_sb.s_inode_bitmap[j - 1];
 132                 }
 133                 sb->u.ext2_sb.s_inode_bitmap_number[0] = inode_bitmap_number;
 134                 sb->u.ext2_sb.s_inode_bitmap[0] = inode_bitmap;
 135
 136                 /*
 137                  * There's still one special case here --- if inode_bitmap == 0
 138                  * then our last attempt to read the bitmap failed and we have
 139                  * just ended up caching that failure.  Try again to read it.
 140                  */
 141                 if (!inode_bitmap)
 142                         retval = read_inode_bitmap (sb, block_group, 0);
 143
 144         } else {
 145                 if (sb->u.ext2_sb.s_loaded_inode_bitmaps < EXT2_MAX_GROUP_LOADED)
 146                         sb->u.ext2_sb.s_loaded_inode_bitmaps++;
 147                 else
 148                         brelse (sb->u.ext2_sb.s_inode_bitmap[EXT2_MAX_GROUP_LOADED - 1]);
 149                 for (j = sb->u.ext2_sb.s_loaded_inode_bitmaps - 1; j > 0; j--) {
 150                         sb->u.ext2_sb.s_inode_bitmap_number[j] =
 151                                 sb->u.ext2_sb.s_inode_bitmap_number[j - 1];
 152                         sb->u.ext2_sb.s_inode_bitmap[j] =
 153                                 sb->u.ext2_sb.s_inode_bitmap[j - 1];
 154                 }
 155                 retval = read_inode_bitmap (sb, block_group, 0);
 156         }
 157         return retval;
 158 }
 159
 160 /*
 161  * NOTE! When we get the inode, we're the only people
 162  * that have access to it, and as such there are no
 163  * race conditions we have to worry about. The inode
 164  * is not on the hash-lists, and it cannot be reached
 165  * through the filesystem because the directory entry
 166  * has been deleted earlier.
 167  *
 168  * HOWEVER: we must make sure that we get no aliases,
 169  * which means that we have to call "clear_inode()"
 170  * _before_ we mark the inode not in use in the inode
 171  * bitmaps. Otherwise a newly created file might use
 172  * the same inode number (not actually the same pointer
 173  * though), and then we'd have two inodes sharing the
 174  * same inode number and space on the harddisk.
 175  */
 176 void ext2_free_inode (struct inode * inode)
 177 {
 178         struct super_block * sb = inode->i_sb;
 179         int is_directory;
 180         unsigned long ino;
 181         struct buffer_head * bh;
 182         struct buffer_head * bh2;
 183         unsigned long block_group;
 184         unsigned long bit;
 185         int bitmap_nr;
 186         struct ext2_group_desc * gdp;
 187         struct ext2_super_block * es;
 188
 189         ino = inode->i_ino;
 190         ext2_debug ("freeing inode %lu\n", ino);
 191
 192         /*
 193          * Note: we must free any quota before locking the superblock,
 194          * as writing the quota to disk may need the lock as well.
 195          */
 196         DQUOT_FREE_INODE(sb, inode);
 197         DQUOT_DROP(inode);
 198
 199         lock_super (sb);
 200         es = sb->u.ext2_sb.s_es;
 201         if (ino < EXT2_FIRST_INO(sb) ||
 202             ino > le32_to_cpu(es->s_inodes_count)) {
 203                 ext2_error (sb, "free_inode",
 204                             "reserved inode or nonexistent inode");
 205                 goto error_return;
 206         }
 207         block_group = (ino - 1) / EXT2_INODES_PER_GROUP(sb);
 208         bit = (ino - 1) % EXT2_INODES_PER_GROUP(sb);
 209         bitmap_nr = load_inode_bitmap (sb, block_group);
 210         if (bitmap_nr < 0)
 211                 goto error_return;
 212
 213         bh = sb->u.ext2_sb.s_inode_bitmap[bitmap_nr];
 214
 215         is_directory = S_ISDIR(inode->i_mode);
 216
 217         /* Do this BEFORE marking the inode not in use */
 218         clear_inode (inode);
 219
 220         /* Ok, now we can actually update the inode bitmaps.. */
 221         if (!ext2_clear_bit (bit, bh->b_data))
 222                 ext2_error (sb, "ext2_free_inode",
 223                               "bit already cleared for inode %lu", ino);
 224         else {
 225                 gdp = ext2_get_group_desc (sb, block_group, &bh2);
 226                 if (gdp) {
 227                         gdp->bg_free_inodes_count =
 228                                 cpu_to_le16(le16_to_cpu(gdp->bg_free_inodes_count) + 1);
 229                         if (is_directory)
 230                                 gdp->bg_used_dirs_count =
 231                                         cpu_to_le16(le16_to_cpu(gdp->bg_used_dirs_count) - 1);
 232                 }
 233                 mark_buffer_dirty(bh2, 1);
 234                 es->s_free_inodes_count =
 235                         cpu_to_le32(le32_to_cpu(es->s_free_inodes_count) + 1);
 236                 mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1);
 237         }
 238         mark_buffer_dirty(bh, 1);
 239         if (sb->s_flags & MS_SYNCHRONOUS) {
 240                 ll_rw_block (WRITE, 1, &bh);
 241                 wait_on_buffer (bh);
 242         }
 243         sb->s_dirt = 1;
 244 error_return:
 245         unlock_super (sb);
 246 }
 247
 248 /*
 249  * There are two policies for allocating an inode.  If the new inode is
 250  * a directory, then a forward search is made for a block group with both
 251  * free space and a low directory-to-inode ratio; if that fails, then of
 252  * the groups with above-average free space, that group with the fewest
 253  * directories already is chosen.
 254  *
 255  * For other inodes, search forward from the parent directory\'s block
 256  * group to find a free inode.
 257  */
 258 struct inode * ext2_new_inode (const struct inode * dir, int mode, int * err)
 259 {
 260         struct super_block * sb;
 261         struct buffer_head * bh;
 262         struct buffer_head * bh2;
 263         int i, j, avefreei;
 264         struct inode * inode;
 265         int bitmap_nr;
 266         struct ext2_group_desc * gdp;
 267         struct ext2_group_desc * tmp;
 268         struct ext2_super_block * es;
 269
 270         /* Cannot create files in a deleted directory */
 271         if (!dir || !dir->i_nlink) {
 272                 *err = -EPERM;
 273                 return NULL;
 274         }
 275
 276         inode = get_empty_inode ();
 277         if (!inode) {
 278                 *err = -ENOMEM;
 279                 return NULL;
 280         }
 281
 282         sb = dir->i_sb;
 283         inode->i_sb = sb;
 284         inode->i_flags = 0;
 285         lock_super (sb);
 286         es = sb->u.ext2_sb.s_es;
 287 repeat:
 288         gdp = NULL; i=0;
 289
 290         *err = -ENOSPC;
 291         if (S_ISDIR(mode)) {
 292                 avefreei = le32_to_cpu(es->s_free_inodes_count) /
 293                         sb->u.ext2_sb.s_groups_count;
 294 /* I am not yet convinced that this next bit is necessary.
 295                 i = dir->u.ext2_i.i_block_group;
 296                 for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
 297                         tmp = ext2_get_group_desc (sb, i, &bh2);
 298                         if (tmp &&
 299                             (le16_to_cpu(tmp->bg_used_dirs_count) << 8) <
 300                              le16_to_cpu(tmp->bg_free_inodes_count)) {
 301                                 gdp = tmp;
 302                                 break;
 303                         }
 304                         else
 305                         i = ++i % sb->u.ext2_sb.s_groups_count;
 306                 }
 307 */
 308                 if (!gdp) {
 309                         for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
 310                                 tmp = ext2_get_group_desc (sb, j, &bh2);
 311                                 if (tmp &&
 312                                     le16_to_cpu(tmp->bg_free_inodes_count) &&
 313                                     le16_to_cpu(tmp->bg_free_inodes_count) >= avefreei) {
 314                                         if (!gdp ||
 315                                             (le16_to_cpu(tmp->bg_free_blocks_count) >
 316                                              le16_to_cpu(gdp->bg_free_blocks_count))) {
 317                                                 i = j;
 318                                                 gdp = tmp;
 319                                         }
 320                                 }
 321                         }
 322                 }
 323         }
 324         else
 325         {
 326                 /*
 327                  * Try to place the inode in its parent directory
 328                  */
 329                 i = dir->u.ext2_i.i_block_group;
 330                 tmp = ext2_get_group_desc (sb, i, &bh2);
 331                 if (tmp && le16_to_cpu(tmp->bg_free_inodes_count))
 332                         gdp = tmp;
 333                 else
 334                 {
 335                         /*
 336                          * Use a quadratic hash to find a group with a
 337                          * free inode
 338                          */
 339                         for (j = 1; j < sb->u.ext2_sb.s_groups_count; j <<= 1) {
 340                                 i += j;
 341                                 if (i >= sb->u.ext2_sb.s_groups_count)
 342                                         i -= sb->u.ext2_sb.s_groups_count;
 343                                 tmp = ext2_get_group_desc (sb, i, &bh2);
 344                                 if (tmp &&
 345                                     le16_to_cpu(tmp->bg_free_inodes_count)) {
 346                                         gdp = tmp;
 347                                         break;
 348                                 }
 349                         }
 350                 }
 351                 if (!gdp) {
 352                         /*
 353                          * That failed: try linear search for a free inode
 354                          */
 355                         i = dir->u.ext2_i.i_block_group + 1;
 356                         for (j = 2; j < sb->u.ext2_sb.s_groups_count; j++) {
 357                                 if (++i >= sb->u.ext2_sb.s_groups_count)
 358                                         i = 0;
 359                                 tmp = ext2_get_group_desc (sb, i, &bh2);
 360                                 if (tmp &&
 361                                     le16_to_cpu(tmp->bg_free_inodes_count)) {
 362                                         gdp = tmp;
 363                                         break;
 364                                 }
 365                         }
 366                 }
 367         }
 368
 369         if (!gdp) {
 370                 unlock_super (sb);
 371                 iput(inode);
 372                 return NULL;
 373         }
 374         bitmap_nr = load_inode_bitmap (sb, i);
 375         if (bitmap_nr < 0) {
 376                 unlock_super (sb);
 377                 iput(inode);
 378                 *err = -EIO;
 379                 return NULL;
 380         }
 381
 382         bh = sb->u.ext2_sb.s_inode_bitmap[bitmap_nr];
 383         if ((j = ext2_find_first_zero_bit ((unsigned long *) bh->b_data,
 384                                       EXT2_INODES_PER_GROUP(sb))) <
 385             EXT2_INODES_PER_GROUP(sb)) {
 386                 if (ext2_set_bit (j, bh->b_data)) {
 387                         ext2_error (sb, "ext2_new_inode",
 388                                       "bit already set for inode %d", j);
 389                         goto repeat;
 390                 }
 391                 mark_buffer_dirty(bh, 1);
 392                 if (sb->s_flags & MS_SYNCHRONOUS) {
 393                         ll_rw_block (WRITE, 1, &bh);
 394                         wait_on_buffer (bh);
 395                 }
 396         } else {
 397                 if (le16_to_cpu(gdp->bg_free_inodes_count) != 0) {
 398                         ext2_error (sb, "ext2_new_inode",
 399                                     "Free inodes count corrupted in group %d",
 400                                     i);
 401                         unlock_super (sb);
 402                         iput (inode);
 403                         return NULL;
 404                 }
 405                 goto repeat;
 406         }
 407         j += i * EXT2_INODES_PER_GROUP(sb) + 1;
 408         if (j < EXT2_FIRST_INO(sb) || j > le32_to_cpu(es->s_inodes_count)) {
 409                 ext2_error (sb, "ext2_new_inode",
 410                             "reserved inode or inode > inodes count - "
 411                             "block_group = %d,inode=%d", i, j);
 412                 unlock_super (sb);
 413                 iput (inode);
 414                 return NULL;
 415         }
 416         gdp->bg_free_inodes_count =
 417                 cpu_to_le16(le16_to_cpu(gdp->bg_free_inodes_count) - 1);
 418         if (S_ISDIR(mode))
 419                 gdp->bg_used_dirs_count =
 420                         cpu_to_le16(le16_to_cpu(gdp->bg_used_dirs_count) + 1);
 421         mark_buffer_dirty(bh2, 1);
 422         es->s_free_inodes_count =
 423                 cpu_to_le32(le32_to_cpu(es->s_free_inodes_count) - 1);
 424         mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1);
 425         sb->s_dirt = 1;
 426         inode->i_mode = mode;
 427         inode->i_sb = sb;
 428         inode->i_nlink = 1;
 429         inode->i_dev = sb->s_dev;
 430         inode->i_uid = current->fsuid;
 431         if (test_opt (sb, GRPID))
 432                 inode->i_gid = dir->i_gid;
 433         else if (dir->i_mode & S_ISGID) {
 434                 inode->i_gid = dir->i_gid;
 435                 if (S_ISDIR(mode))
 436                         mode |= S_ISGID;
 437         } else
 438                 inode->i_gid = current->fsgid;
 439
 440         inode->i_ino = j;
 441         inode->i_blksize = PAGE_SIZE;   /* This is the optimal IO size (for stat), not the fs block size */
 442         inode->i_blocks = 0;
 443         inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
 444         inode->u.ext2_i.i_new_inode = 1;
 445         inode->u.ext2_i.i_flags = dir->u.ext2_i.i_flags;
 446         if (S_ISLNK(mode))
 447                 inode->u.ext2_i.i_flags &= ~(EXT2_IMMUTABLE_FL | EXT2_APPEND_FL);
 448         inode->u.ext2_i.i_faddr = 0;
 449         inode->u.ext2_i.i_frag_no = 0;
 450         inode->u.ext2_i.i_frag_size = 0;
 451         inode->u.ext2_i.i_file_acl = 0;
 452         inode->u.ext2_i.i_dir_acl = 0;
 453         inode->u.ext2_i.i_dtime = 0;
 454         inode->u.ext2_i.i_block_group = i;
 455         if (inode->u.ext2_i.i_flags & EXT2_SYNC_FL)
 456                 inode->i_flags |= MS_SYNCHRONOUS;
 457         insert_inode_hash(inode);
 458         inode->i_generation = event++;
 459         mark_inode_dirty(inode);
 460
 461         unlock_super (sb);
 462         if(DQUOT_ALLOC_INODE(sb, inode)) {
 463                 sb->dq_op->drop(inode);
 464                 inode->i_nlink = 0;
 465                 iput(inode);
 466                 *err = -EDQUOT;
 467                 return NULL;
 468         }
 469         ext2_debug ("allocating inode %lu\n", inode->i_ino);
 470
 471         *err = 0;
 472         return inode;
 473 }
 474
 475 unsigned long ext2_count_free_inodes (struct super_block * sb)
 476 {
 477 #ifdef EXT2FS_DEBUG
 478         struct ext2_super_block * es;
 479         unsigned long desc_count, bitmap_count, x;
 480         int bitmap_nr;
 481         struct ext2_group_desc * gdp;
 482         int i;
 483
 484         lock_super (sb);
 485         es = sb->u.ext2_sb.s_es;
 486         desc_count = 0;
 487         bitmap_count = 0;
 488         gdp = NULL;
 489         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 490                 gdp = ext2_get_group_desc (sb, i, NULL);
 491                 if (!gdp)
 492                         continue;
 493                 desc_count += le16_to_cpu(gdp->bg_free_inodes_count);
 494                 bitmap_nr = load_inode_bitmap (sb, i);
 495                 if (bitmap_nr < 0)
 496                         continue;
 497
 498                 x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
 499                                      EXT2_INODES_PER_GROUP(sb) / 8);
 500                 printk ("group %d: stored = %d, counted = %lu\n",
 501                         i, le16_to_cpu(gdp->bg_free_inodes_count), x);
 502                 bitmap_count += x;
 503         }
 504         printk("ext2_count_free_inodes: stored = %lu, computed = %lu, %lu\n",
 505                 le32_to_cpu(es->s_free_inodes_count), desc_count, bitmap_count);
 506         unlock_super (sb);
 507         return desc_count;
 508 #else
 509         return le32_to_cpu(sb->u.ext2_sb.s_es->s_free_inodes_count);
 510 #endif
 511 }
 512
 513 #ifdef CONFIG_EXT2_CHECK
 514 /* Called at mount-time, super-block is locked */
 515 void ext2_check_inodes_bitmap (struct super_block * sb)
 516 {
 517         struct ext2_super_block * es;
 518         unsigned long desc_count, bitmap_count, x;
 519         int bitmap_nr;
 520         struct ext2_group_desc * gdp;
 521         int i;
 522
 523         es = sb->u.ext2_sb.s_es;
 524         desc_count = 0;
 525         bitmap_count = 0;
 526         gdp = NULL;
 527         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 528                 gdp = ext2_get_group_desc (sb, i, NULL);
 529                 if (!gdp)
 530                         continue;
 531                 desc_count += le16_to_cpu(gdp->bg_free_inodes_count);
 532                 bitmap_nr = load_inode_bitmap (sb, i);
 533                 if (bitmap_nr < 0)
 534                         continue;
 535
 536                 x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
 537                                      EXT2_INODES_PER_GROUP(sb) / 8);
 538                 if (le16_to_cpu(gdp->bg_free_inodes_count) != x)
 539                         ext2_error (sb, "ext2_check_inodes_bitmap",
 540                                     "Wrong free inodes count in group %d, "
 541                                     "stored = %d, counted = %lu", i,
 542                                     le16_to_cpu(gdp->bg_free_inodes_count), x);
 543                 bitmap_count += x;
 544         }
 545         if (le32_to_cpu(es->s_free_inodes_count) != bitmap_count)
 546                 ext2_error (sb, "ext2_check_inodes_bitmap",
 547                             "Wrong free inodes count in super block, "
 548                             "stored = %lu, counted = %lu",
 549                             (unsigned long) le32_to_cpu(es->s_free_inodes_count),
 550                             bitmap_count);
 551 }
 552 #endif