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