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