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