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