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