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