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