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