sys/vfs/gnu/ext2fs/ext2_linux_balloc.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_balloc.c,v 1.11.2.3 2001/08/14 18:03:19 gallatin Exp $
   8  * $DragonFly: src/sys/vfs/gnu/ext2fs/ext2_linux_balloc.c,v 1.6 2006/01/13 21:09:27 swildner Exp $
   9  */
  10 /*
  11  *  linux/fs/ext2/balloc.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  *  Enhanced block allocation by Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
  19  */
  20
  21 /*
  22  * The free blocks 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 #include <sys/buf2.h>
  39 #include <sys/thread2.h>
  40
  41 #include <vfs/ufs/quota.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
  48 #ifdef __i386__
  49 #include "i386-bitops.h"
  50 #elif defined (__alpha__)
  51 #include "alpha-bitops.h"
  52 #else
  53 #error Provide an bitops.h file, please !
  54 #endif
  55
  56 #define in_range(b, first, len)         ((b) >= (first) && (b) <= (first) + (len) - 1)
  57
  58 /* got rid of get_group_desc since it can already be found in
  59  * ext2_linux_ialloc.c
  60  */
  61
  62 static void
  63 read_block_bitmap(struct mount *mp, unsigned int block_group,
  64                   unsigned long bitmap_nr)
  65 {
  66         struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
  67         struct ext2_group_desc * gdp;
  68         struct buffer_head * bh;
  69         int    error;
  70
  71         gdp = get_group_desc (mp, block_group, NULL);
  72         if ((error = bread (VFSTOUFS(mp)->um_devvp,
  73                 fsbtodb(sb, gdp->bg_block_bitmap),sb->s_blocksize, &bh)) != 0)
  74                 panic ( "read_block_bitmap: "
  75                             "Cannot read block bitmap - "
  76                             "block_group = %d, block_bitmap = %lu",
  77                             block_group, (unsigned long) gdp->bg_block_bitmap);
  78         sb->s_block_bitmap_number[bitmap_nr] = block_group;
  79         sb->s_block_bitmap[bitmap_nr] = bh;
  80         LCK_BUF(bh)
  81 }
  82
  83 /*
  84  * load_block_bitmap loads the block bitmap for a blocks group
  85  *
  86  * It maintains a cache for the last bitmaps loaded.  This cache is managed
  87  * with a LRU algorithm.
  88  *
  89  * Notes:
  90  * 1/ There is one cache per mounted file system.
  91  * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
  92  *    this function reads the bitmap without maintaining a LRU cache.
  93  */
  94 static int
  95 load__block_bitmap(struct mount *mp, unsigned int block_group)
  96 {
  97         int i, j;
  98         struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
  99         unsigned long block_bitmap_number;
 100         struct buffer_head * block_bitmap;
 101
 102         if (block_group >= sb->s_groups_count)
 103                 panic ( "load_block_bitmap: "
 104                             "block_group >= groups_count - "
 105                             "block_group = %d, groups_count = %lu",
 106                             block_group, sb->s_groups_count);
 107
 108         if (sb->s_groups_count <= EXT2_MAX_GROUP_LOADED) {
 109                 if (sb->s_block_bitmap[block_group]) {
 110                         if (sb->s_block_bitmap_number[block_group] !=
 111                             block_group)
 112                                 panic ( "load_block_bitmap: "
 113                                             "block_group != block_bitmap_number");
 114                         else
 115                                 return block_group;
 116                 } else {
 117                         read_block_bitmap (mp, block_group, block_group);
 118                         return block_group;
 119                 }
 120         }
 121
 122         for (i = 0; i < sb->s_loaded_block_bitmaps &&
 123                     sb->s_block_bitmap_number[i] != block_group; i++)
 124                 ;
 125         if (i < sb->s_loaded_block_bitmaps &&
 126             sb->s_block_bitmap_number[i] == block_group) {
 127                 block_bitmap_number = sb->s_block_bitmap_number[i];
 128                 block_bitmap = sb->s_block_bitmap[i];
 129                 for (j = i; j > 0; j--) {
 130                         sb->s_block_bitmap_number[j] =
 131                                 sb->s_block_bitmap_number[j - 1];
 132                         sb->s_block_bitmap[j] =
 133                                 sb->s_block_bitmap[j - 1];
 134                 }
 135                 sb->s_block_bitmap_number[0] = block_bitmap_number;
 136                 sb->s_block_bitmap[0] = block_bitmap;
 137         } else {
 138                 if (sb->s_loaded_block_bitmaps < EXT2_MAX_GROUP_LOADED)
 139                         sb->s_loaded_block_bitmaps++;
 140                 else
 141                         ULCK_BUF(sb->s_block_bitmap[EXT2_MAX_GROUP_LOADED - 1])
 142
 143                 for (j = sb->s_loaded_block_bitmaps - 1; j > 0;  j--) {
 144                         sb->s_block_bitmap_number[j] =
 145                                 sb->s_block_bitmap_number[j - 1];
 146                         sb->s_block_bitmap[j] =
 147                                 sb->s_block_bitmap[j - 1];
 148                 }
 149                 read_block_bitmap (mp, block_group, 0);
 150         }
 151         return 0;
 152 }
 153
 154 static __inline int
 155 load_block_bitmap(struct mount * mp, unsigned int block_group)
 156 {
 157         struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
 158         if (sb->s_loaded_block_bitmaps > 0 &&
 159             sb->s_block_bitmap_number[0] == block_group)
 160                 return 0;
 161
 162         if (sb->s_groups_count <= EXT2_MAX_GROUP_LOADED &&
 163             sb->s_block_bitmap_number[block_group] == block_group &&
 164             sb->s_block_bitmap[block_group])
 165                 return block_group;
 166
 167         return load__block_bitmap (mp, block_group);
 168 }
 169
 170 void
 171 ext2_free_blocks(struct mount * mp, unsigned long block,
 172                  unsigned long count)
 173 {
 174         struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
 175         struct buffer_head * bh;
 176         struct buffer_head * bh2;
 177         unsigned long block_group;
 178         unsigned long bit;
 179         unsigned long i;
 180         int bitmap_nr;
 181         struct ext2_group_desc * gdp;
 182         struct ext2_super_block * es = sb->s_es;
 183
 184         if (!sb) {
 185                 printf ("ext2_free_blocks: nonexistent device");
 186                 return;
 187         }
 188         lock_super (VFSTOUFS(mp)->um_devvp);
 189         if (block < es->s_first_data_block ||
 190             (block + count) > es->s_blocks_count) {
 191                 printf ( "ext2_free_blocks: "
 192                             "Freeing blocks not in datazone - "
 193                             "block = %lu, count = %lu", block, count);
 194                 unlock_super (VFSTOUFS(mp)->um_devvp);
 195                 return;
 196         }
 197
 198         ext2_debug ("freeing blocks %lu to %lu\n", block, block+count-1);
 199
 200         block_group = (block - es->s_first_data_block) /
 201                       EXT2_BLOCKS_PER_GROUP(sb);
 202         bit = (block - es->s_first_data_block) % EXT2_BLOCKS_PER_GROUP(sb);
 203         if (bit + count > EXT2_BLOCKS_PER_GROUP(sb))
 204                 panic ( "ext2_free_blocks: "
 205                             "Freeing blocks across group boundary - "
 206                             "Block = %lu, count = %lu",
 207                             block, count);
 208         bitmap_nr = load_block_bitmap (mp, block_group);
 209         bh = sb->s_block_bitmap[bitmap_nr];
 210         gdp = get_group_desc (mp, block_group, &bh2);
 211
 212         if (/* test_opt (sb, CHECK_STRICT) &&   assume always strict ! */
 213             (in_range (gdp->bg_block_bitmap, block, count) ||
 214              in_range (gdp->bg_inode_bitmap, block, count) ||
 215              in_range (block, gdp->bg_inode_table,
 216                        sb->s_itb_per_group) ||
 217              in_range (block + count - 1, gdp->bg_inode_table,
 218                        sb->s_itb_per_group)))
 219                 panic ( "ext2_free_blocks: "
 220                             "Freeing blocks in system zones - "
 221                             "Block = %lu, count = %lu",
 222                             block, count);
 223
 224         for (i = 0; i < count; i++) {
 225                 if (!clear_bit (bit + i, bh->b_data))
 226                         printf ("ext2_free_blocks: "
 227                                       "bit already cleared for block %lu",
 228                                       block);
 229                 else {
 230                         gdp->bg_free_blocks_count++;
 231                         es->s_free_blocks_count++;
 232                 }
 233         }
 234
 235         mark_buffer_dirty(bh2);
 236         mark_buffer_dirty(bh);
 237 /****
 238         if (sb->s_flags & MS_SYNCHRONOUS) {
 239                 ll_rw_block (WRITE, 1, &bh);
 240                 wait_on_buffer (bh);
 241         }
 242 ****/
 243         sb->s_dirt = 1;
 244         unlock_super (VFSTOUFS(mp)->um_devvp);
 245         return;
 246 }
 247
 248 /*
 249  * ext2_new_block uses a goal block to assist allocation.  If the goal is
 250  * free, or there is a free block within 32 blocks of the goal, that block
 251  * is allocated.  Otherwise a forward search is made for a free block; within
 252  * each block group the search first looks for an entire free byte in the block
 253  * bitmap, and then for any free bit if that fails.
 254  */
 255 int
 256 ext2_new_block(struct mount * mp, unsigned long goal,
 257                u_int32_t * prealloc_count,
 258                u_int32_t * prealloc_block)
 259 {
 260         struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
 261         struct buffer_head * bh;
 262         struct buffer_head * bh2;
 263         char * p, * r;
 264         int i, j, k, tmp;
 265         int bitmap_nr;
 266         struct ext2_group_desc * gdp;
 267         struct ext2_super_block * es = sb->s_es;
 268
 269 #ifdef EXT2FS_DEBUG
 270         static int goal_hits = 0, goal_attempts = 0;
 271 #endif
 272         if (!sb) {
 273                 printf ("ext2_new_block: nonexistent device");
 274                 return 0;
 275         }
 276         lock_super (VFSTOUFS(mp)->um_devvp);
 277
 278         ext2_debug ("goal=%lu.\n", goal);
 279
 280 repeat:
 281         /*
 282          * First, test whether the goal block is free.
 283          */
 284         if (goal < es->s_first_data_block || goal >= es->s_blocks_count)
 285                 goal = es->s_first_data_block;
 286         i = (goal - es->s_first_data_block) / EXT2_BLOCKS_PER_GROUP(sb);
 287         gdp = get_group_desc (mp, i, &bh2);
 288         if (gdp->bg_free_blocks_count > 0) {
 289                 j = ((goal - es->s_first_data_block) % EXT2_BLOCKS_PER_GROUP(sb));
 290 #ifdef EXT2FS_DEBUG
 291                 if (j)
 292                         goal_attempts++;
 293 #endif
 294                 bitmap_nr = load_block_bitmap (mp, i);
 295                 bh = sb->s_block_bitmap[bitmap_nr];
 296
 297                 ext2_debug ("goal is at %d:%d.\n", i, j);
 298
 299                 if (!test_bit(j, bh->b_data)) {
 300 #ifdef EXT2FS_DEBUG
 301                         goal_hits++;
 302                         ext2_debug ("goal bit allocated.\n");
 303 #endif
 304                         goto got_block;
 305                 }
 306                 if (j) {
 307                         /*
 308                          * The goal was occupied; search forward for a free
 309                          * block within the next XX blocks.
 310                          *
 311                          * end_goal is more or less random, but it has to be
 312                          * less than EXT2_BLOCKS_PER_GROUP. Aligning up to the
 313                          * next 64-bit boundary is simple..
 314                          */
 315                         int end_goal = (j + 63) & ~63;
 316                         j = find_next_zero_bit(bh->b_data, end_goal, j);
 317                         if (j < end_goal)
 318                                 goto got_block;
 319                 }
 320
 321                 ext2_debug ("Bit not found near goal\n");
 322
 323                 /*
 324                  * There has been no free block found in the near vicinity
 325                  * of the goal: do a search forward through the block groups,
 326                  * searching in each group first for an entire free byte in
 327                  * the bitmap and then for any free bit.
 328                  *
 329                  * Search first in the remainder of the current group; then,
 330                  * cyclicly search through the rest of the groups.
 331                  */
 332                 p = ((char *) bh->b_data) + (j >> 3);
 333                 r = memscan(p, 0, (EXT2_BLOCKS_PER_GROUP(sb) - j + 7) >> 3);
 334                 k = (r - ((char *) bh->b_data)) << 3;
 335                 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
 336                         j = k;
 337                         goto search_back;
 338                 }
 339                 k = find_next_zero_bit ((unsigned long *) bh->b_data,
 340                                         EXT2_BLOCKS_PER_GROUP(sb),
 341                                         j);
 342                 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
 343                         j = k;
 344                         goto got_block;
 345                 }
 346         }
 347
 348         ext2_debug ("Bit not found in block group %d.\n", i);
 349
 350         /*
 351          * Now search the rest of the groups.  We assume that
 352          * i and gdp correctly point to the last group visited.
 353          */
 354         for (k = 0; k < sb->s_groups_count; k++) {
 355                 i++;
 356                 if (i >= sb->s_groups_count)
 357                         i = 0;
 358                 gdp = get_group_desc (mp, i, &bh2);
 359                 if (gdp->bg_free_blocks_count > 0)
 360                         break;
 361         }
 362         if (k >= sb->s_groups_count) {
 363                 unlock_super (VFSTOUFS(mp)->um_devvp);
 364                 return 0;
 365         }
 366         bitmap_nr = load_block_bitmap (mp, i);
 367         bh = sb->s_block_bitmap[bitmap_nr];
 368         r = memscan(bh->b_data, 0, EXT2_BLOCKS_PER_GROUP(sb) >> 3);
 369         j = (r - bh->b_data) << 3;
 370
 371         if (j < EXT2_BLOCKS_PER_GROUP(sb))
 372                 goto search_back;
 373         else
 374                 j = find_first_zero_bit ((unsigned long *) bh->b_data,
 375                                          EXT2_BLOCKS_PER_GROUP(sb));
 376         if (j >= EXT2_BLOCKS_PER_GROUP(sb)) {
 377                 printf ( "ext2_new_block: "
 378                          "Free blocks count corrupted for block group %d", i);
 379                 unlock_super (VFSTOUFS(mp)->um_devvp);
 380                 return 0;
 381         }
 382
 383 search_back:
 384         /*
 385          * We have succeeded in finding a free byte in the block
 386          * bitmap.  Now search backwards up to 7 bits to find the
 387          * start of this group of free blocks.
 388          */
 389         for (k = 0; k < 7 && j > 0 && !test_bit (j - 1, bh->b_data); k++, j--);
 390
 391 got_block:
 392
 393         ext2_debug ("using block group %d(%d)\n", i, gdp->bg_free_blocks_count);
 394
 395         tmp = j + i * EXT2_BLOCKS_PER_GROUP(sb) + es->s_first_data_block;
 396
 397         if (/* test_opt (sb, CHECK_STRICT) && we are always strict. */
 398             (tmp == gdp->bg_block_bitmap ||
 399              tmp == gdp->bg_inode_bitmap ||
 400              in_range (tmp, gdp->bg_inode_table, sb->s_itb_per_group)))
 401                 panic ( "ext2_new_block: "
 402                             "Allocating block in system zone - "
 403                             "%dth block = %u in group %u", j, tmp, i);
 404
 405         if (set_bit (j, bh->b_data)) {
 406                 printf ( "ext2_new_block: "
 407                          "bit already set for block %d", j);
 408                 goto repeat;
 409         }
 410
 411         ext2_debug ("found bit %d\n", j);
 412
 413         /*
 414          * Do block preallocation now if required.
 415          */
 416 #ifdef EXT2_PREALLOCATE
 417         if (prealloc_block) {
 418                 *prealloc_count = 0;
 419                 *prealloc_block = tmp + 1;
 420                 for (k = 1;
 421                      k < 8 && (j + k) < EXT2_BLOCKS_PER_GROUP(sb); k++) {
 422                         if (set_bit (j + k, bh->b_data))
 423                                 break;
 424                         (*prealloc_count)++;
 425                 }
 426                 gdp->bg_free_blocks_count -= *prealloc_count;
 427                 es->s_free_blocks_count -= *prealloc_count;
 428                 ext2_debug ("Preallocated a further %lu bits.\n",
 429                             *prealloc_count);
 430         }
 431 #endif
 432
 433         j = tmp;
 434
 435         mark_buffer_dirty(bh);
 436 /****
 437         if (sb->s_flags & MS_SYNCHRONOUS) {
 438                 ll_rw_block (WRITE, 1, &bh);
 439                 wait_on_buffer (bh);
 440         }
 441 ****/
 442         if (j >= es->s_blocks_count) {
 443                 printf ( "ext2_new_block: "
 444                             "block >= blocks count - "
 445                             "block_group = %d, block=%d", i, j);
 446                 unlock_super (VFSTOUFS(mp)->um_devvp);
 447                 return 0;
 448         }
 449
 450         ext2_debug ("allocating block %d. "
 451                     "Goal hits %d of %d.\n", j, goal_hits, goal_attempts);
 452
 453         gdp->bg_free_blocks_count--;
 454         mark_buffer_dirty(bh2);
 455         es->s_free_blocks_count--;
 456         sb->s_dirt = 1;
 457         unlock_super (VFSTOUFS(mp)->um_devvp);
 458         return j;
 459 }
 460
 461 #ifdef unused
 462 static unsigned long
 463 ext2_count_free_blocks(struct mount * mp)
 464 {
 465         struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
 466 #ifdef EXT2FS_DEBUG
 467         struct ext2_super_block * es;
 468         unsigned long desc_count, bitmap_count, x;
 469         int bitmap_nr;
 470         struct ext2_group_desc * gdp;
 471         int i;
 472
 473         lock_super (VFSTOUFS(mp)->um_devvp);
 474         es = sb->s_es;
 475         desc_count = 0;
 476         bitmap_count = 0;
 477         gdp = NULL;
 478         for (i = 0; i < sb->s_groups_count; i++) {
 479                 gdp = get_group_desc (mp, i, NULL);
 480                 desc_count += gdp->bg_free_blocks_count;
 481                 bitmap_nr = load_block_bitmap (mp, i);
 482                 x = ext2_count_free (sb->s_block_bitmap[bitmap_nr],
 483                                      sb->s_blocksize);
 484                 ext2_debug ("group %d: stored = %d, counted = %lu\n",
 485                         i, gdp->bg_free_blocks_count, x);
 486                 bitmap_count += x;
 487         }
 488         ext2_debug( "stored = %lu, computed = %lu, %lu\n",
 489                es->s_free_blocks_count, desc_count, bitmap_count);
 490         unlock_super (VFSTOUFS(mp)->um_devvp);
 491         return bitmap_count;
 492 #else
 493         return sb->s_es->s_free_blocks_count;
 494 #endif
 495 }
 496 #endif /* unused */
 497
 498 static __inline int
 499 block_in_use (unsigned long block, struct ext2_sb_info *sb,
 500               unsigned char * map)
 501 {
 502         return test_bit ((block - sb->s_es->s_first_data_block) %
 503                          EXT2_BLOCKS_PER_GROUP(sb), map);
 504 }
 505
 506 static int
 507 test_root(int a, int b)
 508 {
 509         if (a == 0)
 510                 return 1;
 511         while (1) {
 512                 if (a == 1)
 513                         return 1;
 514                 if (a % b)
 515                         return 0;
 516                 a = a / b;
 517         }
 518 }
 519
 520 int
 521 ext2_group_sparse(int group)
 522 {
 523         return (test_root(group, 3) || test_root(group, 5) ||
 524                 test_root(group, 7));
 525 }
 526
 527 #ifdef unused
 528 static void
 529 ext2_check_blocks_bitmap(struct mount * mp)
 530 {
 531         struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
 532         struct buffer_head * bh;
 533         struct ext2_super_block * es;
 534         unsigned long desc_count, bitmap_count, x;
 535         unsigned long desc_blocks;
 536         int bitmap_nr;
 537         struct ext2_group_desc * gdp;
 538         int i, j;
 539
 540         lock_super (VFSTOUFS(mp)->um_devvp);
 541         es = sb->s_es;
 542         desc_count = 0;
 543         bitmap_count = 0;
 544         gdp = NULL;
 545         desc_blocks = (sb->s_groups_count + EXT2_DESC_PER_BLOCK(sb) - 1) /
 546                       EXT2_DESC_PER_BLOCK(sb);
 547         for (i = 0; i < sb->s_groups_count; i++) {
 548                 gdp = get_group_desc (mp, i, NULL);
 549                 desc_count += gdp->bg_free_blocks_count;
 550                 bitmap_nr = load_block_bitmap (mp, i);
 551                 bh = sb->s_block_bitmap[bitmap_nr];
 552
 553                 if (!(es->s_feature_ro_compat &
 554                      EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER) ||
 555                     ext2_group_sparse(i)) {
 556                         if (!test_bit (0, bh->b_data))
 557                                 printf ("ext2_check_blocks_bitmap: "
 558                                             "Superblock in group %d "
 559                                             "is marked free", i);
 560
 561                         for (j = 0; j < desc_blocks; j++)
 562                                 if (!test_bit (j + 1, bh->b_data))
 563                                         printf ("ext2_check_blocks_bitmap: "
 564                                             "Descriptor block #%d in group "
 565                                             "%d is marked free", j, i);
 566                 }
 567
 568                 if (!block_in_use (gdp->bg_block_bitmap, sb, bh->b_data))
 569                         printf ("ext2_check_blocks_bitmap: "
 570                                     "Block bitmap for group %d is marked free",
 571                                     i);
 572
 573                 if (!block_in_use (gdp->bg_inode_bitmap, sb, bh->b_data))
 574                         printf ("ext2_check_blocks_bitmap: "
 575                                     "Inode bitmap for group %d is marked free",
 576                                     i);
 577
 578                 for (j = 0; j < sb->s_itb_per_group; j++)
 579                         if (!block_in_use (gdp->bg_inode_table + j, sb, bh->b_data))
 580                                 printf ("ext2_check_blocks_bitmap: "
 581                                             "Block #%d of the inode table in "
 582                                             "group %d is marked free", j, i);
 583
 584                 x = ext2_count_free (bh, sb->s_blocksize);
 585                 if (gdp->bg_free_blocks_count != x)
 586                         printf ("ext2_check_blocks_bitmap: "
 587                                     "Wrong free blocks count for group %d, "
 588                                     "stored = %d, counted = %lu", i,
 589                                     gdp->bg_free_blocks_count, x);
 590                 bitmap_count += x;
 591         }
 592         if (es->s_free_blocks_count != bitmap_count)
 593                 printf ("ext2_check_blocks_bitmap: "
 594                             "Wrong free blocks count in super block, "
 595                             "stored = %lu, counted = %lu",
 596                             (unsigned long) es->s_free_blocks_count, bitmap_count);
 597         unlock_super (VFSTOUFS(mp)->um_devvp);
 598 }
 599 #endif /* unused */
 600
 601 /*
 602  *  this function is taken from
 603  *  linux/fs/ext2/bitmap.c
 604  */
 605
 606 static int nibblemap[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
 607
 608 unsigned long ext2_count_free (struct buffer_head * map, unsigned int numchars)
 609 {
 610         unsigned int i;
 611         unsigned long sum = 0;
 612
 613         if (!map)
 614                 return (0);
 615         for (i = 0; i < numchars; i++)
 616                 sum += nibblemap[map->b_data[i] & 0xf] +
 617                         nibblemap[(map->b_data[i] >> 4) & 0xf];
 618         return (sum);
 619 }