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