sys/gnu/fs/ext2fs/ext2_linux_ialloc.c

   1 /*-
   2  *  modified for Lites 1.1
   3  *
   4  *  Aug 1995, Godmar Back (gback@cs.utah.edu)
   5  *  University of Utah, Department of Computer Science
   6  *
   7  * $FreeBSD$
   8  */
   9 /*-
  10  *  linux/fs/ext2/ialloc.c
  11  *
  12  * Copyright (C) 1992, 1993, 1994, 1995
  13  * Remy Card (card@masi.ibp.fr)
  14  * Laboratoire MASI - Institut Blaise Pascal
  15  * Universite Pierre et Marie Curie (Paris VI)
  16  *
  17  *  BSD ufs-inspired inode and directory allocation by
  18  *  Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
  19  *
  20  *      This program is free software; you can redistribute it and/or modify
  21  *      it under the terms of the GNU General Public License as published by
  22  *      the Free Software Foundation; either version 2 of the License.
  23  *
  24  *      This program is distributed in the hope that it will be useful,
  25  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
  26  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  27  *      GNU General Public License for more details.
  28  *
  29  *      You should have received a copy of the GNU General Public License
  30  *      along with this program; if not, write to the Free Software
  31  *      Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  32  *
  33  */
  34
  35 /*
  36  * The free inodes are managed by bitmaps.  A file system contains several
  37  * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
  38  * block for inodes, N blocks for the inode table and data blocks.
  39  *
  40  * The file system contains group descriptors which are located after the
  41  * super block.  Each descriptor contains the number of the bitmap block and
  42  * the free blocks count in the block.  The descriptors are loaded in memory
  43  * when a file system is mounted (see ext2_read_super).
  44  */
  45
  46 #include <sys/param.h>
  47 #include <sys/systm.h>
  48 #include <sys/bio.h>
  49 #include <sys/buf.h>
  50 #include <sys/mount.h>
  51 #include <sys/vnode.h>
  52
  53 #include <gnu/fs/ext2fs/inode.h>
  54 #include <gnu/fs/ext2fs/ext2_mount.h>
  55 #include <gnu/fs/ext2fs/ext2_extern.h>
  56 #include <gnu/fs/ext2fs/ext2_fs.h>
  57 #include <gnu/fs/ext2fs/ext2_fs_sb.h>
  58 #include <gnu/fs/ext2fs/fs.h>
  59 #include <sys/stat.h>
  60
  61 #ifdef __i386__
  62 #include <gnu/fs/ext2fs/i386-bitops.h>
  63 #else
  64 #include <gnu/fs/ext2fs/ext2_bitops.h>
  65 #endif
  66
  67 /* this is supposed to mark a buffer dirty on ready for delayed writing
  68  */
  69 void mark_buffer_dirty(struct buf *bh)
  70 {
  71         int s;
  72
  73         s = splbio();
  74         bh->b_flags |= B_DIRTY;
  75         splx(s);
  76 }
  77
  78 struct ext2_group_desc * get_group_desc (struct mount * mp,
  79                                                 unsigned int block_group,
  80                                                 struct buffer_head ** bh)
  81 {
  82         struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
  83         unsigned long group_desc;
  84         unsigned long desc;
  85         struct ext2_group_desc * gdp;
  86
  87         if (block_group >= sb->s_groups_count)
  88                 panic ("get_group_desc: "
  89                             "block_group >= groups_count - "
  90                             "block_group = %d, groups_count = %lu",
  91                             block_group, sb->s_groups_count);
  92
  93         group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
  94         desc = block_group % EXT2_DESC_PER_BLOCK(sb);
  95         if (!sb->s_group_desc[group_desc])
  96                 panic ( "get_group_desc:"
  97                             "Group descriptor not loaded - "
  98                             "block_group = %d, group_desc = %lu, desc = %lu",
  99                              block_group, group_desc, desc);
 100         gdp = (struct ext2_group_desc *)
 101                 sb->s_group_desc[group_desc]->b_data;
 102         if (bh)
 103                 *bh = sb->s_group_desc[group_desc];
 104         return gdp + desc;
 105 }
 106
 107 static void read_inode_bitmap (struct mount * mp,
 108                                unsigned long block_group,
 109                                unsigned int bitmap_nr)
 110 {
 111         struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
 112         struct ext2_group_desc * gdp;
 113         struct buffer_head * bh;
 114         int     error;
 115
 116         gdp = get_group_desc (mp, block_group, NULL);
 117         if ((error = bread (VFSTOEXT2(mp)->um_devvp,
 118                             fsbtodb(sb, gdp->bg_inode_bitmap),
 119                             sb->s_blocksize,
 120                             NOCRED, &bh)) != 0)
 121                 panic ( "read_inode_bitmap:"
 122                             "Cannot read inode bitmap - "
 123                             "block_group = %lu, inode_bitmap = %lu",
 124                             block_group, (unsigned long) gdp->bg_inode_bitmap);
 125         sb->s_inode_bitmap_number[bitmap_nr] = block_group;
 126         sb->s_inode_bitmap[bitmap_nr] = bh;
 127         LCK_BUF(bh)
 128 }
 129
 130 /*
 131  * load_inode_bitmap loads the inode bitmap for a blocks group
 132  *
 133  * It maintains a cache for the last bitmaps loaded.  This cache is managed
 134  * with a LRU algorithm.
 135  *
 136  * Notes:
 137  * 1/ There is one cache per mounted file system.
 138  * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
 139  *    this function reads the bitmap without maintaining a LRU cache.
 140  */
 141 static int load_inode_bitmap (struct mount * mp,
 142                               unsigned int block_group)
 143 {
 144         struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
 145         int i, j;
 146         unsigned long inode_bitmap_number;
 147         struct buffer_head * inode_bitmap;
 148
 149         if (block_group >= sb->s_groups_count)
 150                 panic ("load_inode_bitmap:"
 151                             "block_group >= groups_count - "
 152                             "block_group = %d, groups_count = %lu",
 153                              block_group, sb->s_groups_count);
 154         if (sb->s_loaded_inode_bitmaps > 0 &&
 155             sb->s_inode_bitmap_number[0] == block_group)
 156                 return 0;
 157         if (sb->s_groups_count <= EXT2_MAX_GROUP_LOADED) {
 158                 if (sb->s_inode_bitmap[block_group]) {
 159                         if (sb->s_inode_bitmap_number[block_group] !=
 160                                 block_group)
 161                                 panic ( "load_inode_bitmap:"
 162                                     "block_group != inode_bitmap_number");
 163                         else
 164                                 return block_group;
 165                 } else {
 166                         read_inode_bitmap (mp, block_group, block_group);
 167                         return block_group;
 168                 }
 169         }
 170
 171         for (i = 0; i < sb->s_loaded_inode_bitmaps &&
 172                     sb->s_inode_bitmap_number[i] != block_group;
 173              i++)
 174                 ;
 175         if (i < sb->s_loaded_inode_bitmaps &&
 176             sb->s_inode_bitmap_number[i] == block_group) {
 177                 inode_bitmap_number = sb->s_inode_bitmap_number[i];
 178                 inode_bitmap = sb->s_inode_bitmap[i];
 179                 for (j = i; j > 0; j--) {
 180                         sb->s_inode_bitmap_number[j] =
 181                                 sb->s_inode_bitmap_number[j - 1];
 182                         sb->s_inode_bitmap[j] =
 183                                 sb->s_inode_bitmap[j - 1];
 184                 }
 185                 sb->s_inode_bitmap_number[0] = inode_bitmap_number;
 186                 sb->s_inode_bitmap[0] = inode_bitmap;
 187         } else {
 188                 if (sb->s_loaded_inode_bitmaps < EXT2_MAX_GROUP_LOADED)
 189                         sb->s_loaded_inode_bitmaps++;
 190                 else
 191                         ULCK_BUF(sb->s_inode_bitmap[EXT2_MAX_GROUP_LOADED - 1])
 192                 for (j = sb->s_loaded_inode_bitmaps - 1; j > 0; j--) {
 193                         sb->s_inode_bitmap_number[j] =
 194                                 sb->s_inode_bitmap_number[j - 1];
 195                         sb->s_inode_bitmap[j] =
 196                                 sb->s_inode_bitmap[j - 1];
 197                 }
 198                 read_inode_bitmap (mp, block_group, 0);
 199         }
 200         return 0;
 201 }
 202
 203
 204 void ext2_free_inode (struct inode * inode)
 205 {
 206         struct ext2_sb_info * sb;
 207         struct buffer_head * bh;
 208         struct buffer_head * bh2;
 209         unsigned long block_group;
 210         unsigned long bit;
 211         int bitmap_nr;
 212         struct ext2_group_desc * gdp;
 213         struct ext2_super_block * es;
 214
 215         if (!inode)
 216                 return;
 217
 218         if (inode->i_nlink) {
 219                 printf ("ext2_free_inode: inode has nlink=%d\n",
 220                         inode->i_nlink);
 221                 return;
 222         }
 223
 224         ext2_debug ("freeing inode %lu\n", inode->i_number);
 225
 226         sb = inode->i_e2fs;
 227         lock_super (DEVVP(inode));
 228         if (inode->i_number < EXT2_FIRST_INO(sb) ||
 229             inode->i_number > sb->s_es->s_inodes_count) {
 230                 printf ("free_inode reserved inode or nonexistent inode");
 231                 unlock_super (DEVVP(inode));
 232                 return;
 233         }
 234         es = sb->s_es;
 235         block_group = (inode->i_number - 1) / EXT2_INODES_PER_GROUP(sb);
 236         bit = (inode->i_number - 1) % EXT2_INODES_PER_GROUP(sb);
 237         bitmap_nr = load_inode_bitmap (ITOV(inode)->v_mount, block_group);
 238         bh = sb->s_inode_bitmap[bitmap_nr];
 239         if (!clear_bit (bit, bh->b_data))
 240                 printf ( "ext2_free_inode:"
 241                       "bit already cleared for inode %lu",
 242                       (unsigned long)inode->i_number);
 243         else {
 244                 gdp = get_group_desc (ITOV(inode)->v_mount, block_group, &bh2);
 245                 gdp->bg_free_inodes_count++;
 246                 if (S_ISDIR(inode->i_mode))
 247                         gdp->bg_used_dirs_count--;
 248                 mark_buffer_dirty(bh2);
 249                 es->s_free_inodes_count++;
 250         }
 251         mark_buffer_dirty(bh);
 252 /*** XXX
 253         if (sb->s_flags & MS_SYNCHRONOUS) {
 254                 ll_rw_block (WRITE, 1, &bh);
 255                 wait_on_buffer (bh);
 256         }
 257 ***/
 258         sb->s_dirt = 1;
 259         unlock_super (DEVVP(inode));
 260 }
 261
 262 #ifdef linux
 263 /*
 264  * This function increments the inode version number
 265  *
 266  * This may be used one day by the NFS server
 267  */
 268 static void inc_inode_version (struct inode * inode,
 269                                struct ext2_group_desc *gdp,
 270                                int mode)
 271 {
 272         unsigned long inode_block;
 273         struct buffer_head * bh;
 274         struct ext2_inode * raw_inode;
 275
 276         inode_block = gdp->bg_inode_table + (((inode->i_number - 1) %
 277                         EXT2_INODES_PER_GROUP(inode->i_sb)) /
 278                         EXT2_INODES_PER_BLOCK(inode->i_sb));
 279         bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
 280         if (!bh) {
 281                 printf ("inc_inode_version Cannot load inode table block - "
 282                             "inode=%lu, inode_block=%lu\n",
 283                             inode->i_number, inode_block);
 284                 inode->u.ext2_i.i_version = 1;
 285                 return;
 286         }
 287         raw_inode = ((struct ext2_inode *) bh->b_data) +
 288                         (((inode->i_number - 1) %
 289                         EXT2_INODES_PER_GROUP(inode->i_sb)) %
 290                         EXT2_INODES_PER_BLOCK(inode->i_sb));
 291         raw_inode->i_version++;
 292         inode->u.ext2_i.i_version = raw_inode->i_version;
 293         bdwrite (bh);
 294 }
 295
 296 #endif /* linux */
 297
 298 /*
 299  * There are two policies for allocating an inode.  If the new inode is
 300  * a directory, then a forward search is made for a block group with both
 301  * free space and a low directory-to-inode ratio; if that fails, then of
 302  * the groups with above-average free space, that group with the fewest
 303  * directories already is chosen.
 304  *
 305  * For other inodes, search forward from the parent directory\'s block
 306  * group to find a free inode.
 307  */
 308 /*
 309  * this functino has been reduced to the actual 'find the inode number' part
 310  */
 311 ino_t ext2_new_inode (const struct inode * dir, int mode)
 312 {
 313         struct ext2_sb_info * sb;
 314         struct buffer_head * bh;
 315         struct buffer_head * bh2;
 316         int i, j, avefreei;
 317         int bitmap_nr;
 318         struct ext2_group_desc * gdp;
 319         struct ext2_group_desc * tmp;
 320         struct ext2_super_block * es;
 321
 322         if (!dir)
 323                 return 0;
 324         sb = dir->i_e2fs;
 325
 326         lock_super (DEVVP(dir));
 327         es = sb->s_es;
 328 repeat:
 329         gdp = NULL; i=0;
 330
 331         if (S_ISDIR(mode)) {
 332                 avefreei = es->s_free_inodes_count /
 333                         sb->s_groups_count;
 334 /* I am not yet convinced that this next bit is necessary.
 335                 i = dir->u.ext2_i.i_block_group;
 336                 for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
 337                         tmp = get_group_desc (sb, i, &bh2);
 338                         if ((tmp->bg_used_dirs_count << 8) <
 339                             tmp->bg_free_inodes_count) {
 340                                 gdp = tmp;
 341                                 break;
 342                         }
 343                         else
 344                         i = ++i % sb->u.ext2_sb.s_groups_count;
 345                 }
 346 */
 347                 if (!gdp) {
 348                         for (j = 0; j < sb->s_groups_count; j++) {
 349                                 tmp = get_group_desc(ITOV(dir)->v_mount,j,&bh2);
 350                                 if (tmp->bg_free_inodes_count &&
 351                                         tmp->bg_free_inodes_count >= avefreei) {
 352                                         if (!gdp ||
 353                                             (tmp->bg_free_blocks_count >
 354                                              gdp->bg_free_blocks_count)) {
 355                                                 i = j;
 356                                                 gdp = tmp;
 357                                         }
 358                                 }
 359                         }
 360                 }
 361         }
 362         else
 363         {
 364                 /*
 365                  * Try to place the inode in its parent directory
 366                  */
 367                 i = dir->i_block_group;
 368                 tmp = get_group_desc (ITOV(dir)->v_mount, i, &bh2);
 369                 if (tmp->bg_free_inodes_count)
 370                         gdp = tmp;
 371                 else
 372                 {
 373                         /*
 374                          * Use a quadratic hash to find a group with a
 375                          * free inode
 376                          */
 377                         for (j = 1; j < sb->s_groups_count; j <<= 1) {
 378                                 i += j;
 379                                 if (i >= sb->s_groups_count)
 380                                         i -= sb->s_groups_count;
 381                                 tmp = get_group_desc(ITOV(dir)->v_mount,i,&bh2);
 382                                 if (tmp->bg_free_inodes_count) {
 383                                         gdp = tmp;
 384                                         break;
 385                                 }
 386                         }
 387                 }
 388                 if (!gdp) {
 389                         /*
 390                          * That failed: try linear search for a free inode
 391                          */
 392                         i = dir->i_block_group + 1;
 393                         for (j = 2; j < sb->s_groups_count; j++) {
 394                                 if (++i >= sb->s_groups_count)
 395                                         i = 0;
 396                                 tmp = get_group_desc(ITOV(dir)->v_mount,i,&bh2);
 397                                 if (tmp->bg_free_inodes_count) {
 398                                         gdp = tmp;
 399                                         break;
 400                                 }
 401                         }
 402                 }
 403         }
 404
 405         if (!gdp) {
 406                 unlock_super (DEVVP(dir));
 407                 return 0;
 408         }
 409         bitmap_nr = load_inode_bitmap (ITOV(dir)->v_mount, i);
 410         bh = sb->s_inode_bitmap[bitmap_nr];
 411         if ((j = find_first_zero_bit ((unsigned long *) bh->b_data,
 412                                       EXT2_INODES_PER_GROUP(sb))) <
 413             EXT2_INODES_PER_GROUP(sb)) {
 414                 if (set_bit (j, bh->b_data)) {
 415                         printf ( "ext2_new_inode:"
 416                                       "bit already set for inode %d", j);
 417                         goto repeat;
 418                 }
 419 /* Linux now does the following:
 420                 mark_buffer_dirty(bh);
 421                 if (sb->s_flags & MS_SYNCHRONOUS) {
 422                         ll_rw_block (WRITE, 1, &bh);
 423                         wait_on_buffer (bh);
 424                 }
 425 */
 426                 mark_buffer_dirty(bh);
 427         } else {
 428                 if (gdp->bg_free_inodes_count != 0) {
 429                         printf ( "ext2_new_inode:"
 430                                     "Free inodes count corrupted in group %d",
 431                                     i);
 432                         unlock_super (DEVVP(dir));
 433                         return 0;
 434                 }
 435                 goto repeat;
 436         }
 437         j += i * EXT2_INODES_PER_GROUP(sb) + 1;
 438         if (j < EXT2_FIRST_INO(sb) || j > es->s_inodes_count) {
 439                 printf ( "ext2_new_inode:"
 440                             "reserved inode or inode > inodes count - "
 441                             "block_group = %d,inode=%d", i, j);
 442                 unlock_super (DEVVP(dir));
 443                 return 0;
 444         }
 445         gdp->bg_free_inodes_count--;
 446         if (S_ISDIR(mode))
 447                 gdp->bg_used_dirs_count++;
 448         mark_buffer_dirty(bh2);
 449         es->s_free_inodes_count--;
 450         /* mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1); */
 451         sb->s_dirt = 1;
 452         unlock_super (DEVVP(dir));
 453         return j;
 454 }
 455
 456 #ifdef unused
 457 static unsigned long ext2_count_free_inodes (struct mount * mp)
 458 {
 459 #ifdef EXT2FS_DEBUG
 460         struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
 461         struct ext2_super_block * es;
 462         unsigned long desc_count, bitmap_count, x;
 463         int bitmap_nr;
 464         struct ext2_group_desc * gdp;
 465         int i;
 466
 467         lock_super (VFSTOEXT2(mp)->um_devvp);
 468         es = sb->s_es;
 469         desc_count = 0;
 470         bitmap_count = 0;
 471         gdp = NULL;
 472         for (i = 0; i < sb->s_groups_count; i++) {
 473                 gdp = get_group_desc (mp, i, NULL);
 474                 desc_count += gdp->bg_free_inodes_count;
 475                 bitmap_nr = load_inode_bitmap (mp, i);
 476                 x = ext2_count_free (sb->s_inode_bitmap[bitmap_nr],
 477                                      EXT2_INODES_PER_GROUP(sb) / 8);
 478                 ext2_debug ("group %d: stored = %d, counted = %lu\n",
 479                         i, gdp->bg_free_inodes_count, x);
 480                 bitmap_count += x;
 481         }
 482         ext2_debug("stored = %lu, computed = %lu, %lu\n",
 483                 es->s_free_inodes_count, desc_count, bitmap_count);
 484         unlock_super (VFSTOEXT2(mp)->um_devvp);
 485         return desc_count;
 486 #else
 487         return VFSTOEXT2(mp)->um_e2fsb->s_free_inodes_count;
 488 #endif
 489 }
 490 #endif /* unused */
 491
 492 #ifdef LATER
 493 void ext2_check_inodes_bitmap (struct mount * mp)
 494 {
 495         struct ext2_super_block * es;
 496         unsigned long desc_count, bitmap_count, x;
 497         int bitmap_nr;
 498         struct ext2_group_desc * gdp;
 499         int i;
 500
 501         lock_super (sb);
 502         es = sb->u.ext2_sb.s_es;
 503         desc_count = 0;
 504         bitmap_count = 0;
 505         gdp = NULL;
 506         for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
 507                 gdp = get_group_desc (sb, i, NULL);
 508                 desc_count += gdp->bg_free_inodes_count;
 509                 bitmap_nr = load_inode_bitmap (sb, i);
 510                 x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
 511                                      EXT2_INODES_PER_GROUP(sb) / 8);
 512                 if (gdp->bg_free_inodes_count != x)
 513                         printf ( "ext2_check_inodes_bitmap:"
 514                                     "Wrong free inodes count in group %d, "
 515                                     "stored = %d, counted = %lu", i,
 516                                     gdp->bg_free_inodes_count, x);
 517                 bitmap_count += x;
 518         }
 519         if (es->s_free_inodes_count != bitmap_count)
 520                 printf ( "ext2_check_inodes_bitmap:"
 521                             "Wrong free inodes count in super block, "
 522                             "stored = %lu, counted = %lu",
 523                             (unsigned long) es->s_free_inodes_count, bitmap_count);
 524         unlock_super (sb);
 525 }
 526 #endif