fs/ufs/balloc.c

   1 /*
   2  *  linux/fs/ufs/balloc.c
   3  *
   4  * Copyright (C) 1998
   5  * Daniel Pirkl <daniel.pirkl@email.cz>
   6  * Charles University, Faculty of Mathematics and Physics
   7  */
   8
   9 #include <linux/fs.h>
  10 #include <linux/ufs_fs.h>
  11 #include <linux/stat.h>
  12 #include <linux/sched.h>
  13 #include <linux/string.h>
  14 #include <linux/locks.h>
  15 #include <linux/quotaops.h>
  16 #include <asm/bitops.h>
  17 #include <asm/byteorder.h>
  18
  19 #include "swab.h"
  20 #include "util.h"
  21
  22 #undef UFS_BALLOC_DEBUG
  23
  24 #ifdef UFS_BALLOC_DEBUG
  25 #define UFSD(x) printk("(%s, %d), %s:", __FILE__, __LINE__, __FUNCTION__); printk x;
  26 #else
  27 #define UFSD(x)
  28 #endif
  29
  30 unsigned ufs_add_fragments (struct inode *, unsigned, unsigned, unsigned, int *);
  31 unsigned ufs_alloc_fragments (struct inode *, unsigned, unsigned, unsigned, int *);
  32 unsigned ufs_alloccg_block (struct inode *, struct ufs_cg_private_info *, unsigned, int *);
  33 unsigned ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, unsigned, unsigned);
  34 static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[];
  35 void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int);
  36
  37 /*
  38  * Free 'count' fragments from fragment number 'fragment'
  39  */
  40 void ufs_free_fragments (struct inode * inode, unsigned fragment, unsigned count) {
  41         struct super_block * sb;
  42         struct ufs_sb_private_info * uspi;
  43         struct ufs_super_block_first * usb1;
  44         struct ufs_cg_private_info * ucpi;
  45         struct ufs_cylinder_group * ucg;
  46         unsigned cgno, bit, end_bit, bbase, blkmap, i, blkno, cylno;
  47         unsigned swab;
  48
  49         sb = inode->i_sb;
  50         uspi = sb->u.ufs_sb.s_uspi;
  51         swab = sb->u.ufs_sb.s_swab;
  52         usb1 = ubh_get_usb_first(USPI_UBH);
  53
  54         UFSD(("ENTER, fragment %u, count %u\n", fragment, count))
  55
  56         if (ufs_fragnum(fragment) + count > uspi->s_fpg)
  57                 ufs_error (sb, "ufs_free_fragments", "internal error");
  58
  59         lock_super(sb);
  60
  61         cgno = ufs_dtog(fragment);
  62         bit = ufs_dtogd(fragment);
  63         if (cgno >= uspi->s_ncg) {
  64                 ufs_panic (sb, "ufs_free_fragments", "freeing blocks are outside device");
  65                 goto failed;
  66         }
  67
  68         ucpi = ufs_load_cylinder (sb, cgno);
  69         if (!ucpi)
  70                 goto failed;
  71         ucg = ubh_get_ucg (UCPI_UBH);
  72         if (!ufs_cg_chkmagic (ucg)) {
  73                 ufs_panic (sb, "ufs_free_fragments", "internal error, bad magic number on cg %u", cgno);
  74                 goto failed;
  75         }
  76
  77         end_bit = bit + count;
  78         bbase = ufs_blknum (bit);
  79         blkmap = ubh_blkmap (UCPI_UBH, ucpi->c_freeoff, bbase);
  80         ufs_fragacct (sb, blkmap, ucg->cg_frsum, -1);
  81         for (i = bit; i < end_bit; i++) {
  82                 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, i))
  83                         ubh_setbit (UCPI_UBH, ucpi->c_freeoff, i);
  84                 else ufs_error (sb, "ufs_free_fragments",
  85                         "bit already cleared for fragment %u", i);
  86         }
  87
  88         DQUOT_FREE_BLOCK (sb, inode, count);
  89         ADD_SWAB32(ucg->cg_cs.cs_nffree, count);
  90         ADD_SWAB32(usb1->fs_cstotal.cs_nffree, count);
  91         ADD_SWAB32(sb->fs_cs(cgno).cs_nffree, count);
  92         blkmap = ubh_blkmap (UCPI_UBH, ucpi->c_freeoff, bbase);
  93         ufs_fragacct(sb, blkmap, ucg->cg_frsum, 1);
  94
  95         /*
  96          * Trying to reassemble free fragments into block
  97          */
  98         blkno = ufs_fragstoblks (bbase);
  99         if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, blkno)) {
 100                 SUB_SWAB32(ucg->cg_cs.cs_nffree, uspi->s_fpb);
 101                 SUB_SWAB32(usb1->fs_cstotal.cs_nffree, uspi->s_fpb);
 102                 SUB_SWAB32(sb->fs_cs(cgno).cs_nffree, uspi->s_fpb);
 103                 if ((sb->u.ufs_sb.s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
 104                         ufs_clusteracct (sb, ucpi, blkno, 1);
 105                 INC_SWAB32(ucg->cg_cs.cs_nbfree);
 106                 INC_SWAB32(usb1->fs_cstotal.cs_nbfree);
 107                 INC_SWAB32(sb->fs_cs(cgno).cs_nbfree);
 108                 cylno = ufs_cbtocylno (bbase);
 109                 INC_SWAB16(ubh_cg_blks (ucpi, cylno, ufs_cbtorpos(bbase)));
 110                 INC_SWAB32(ubh_cg_blktot (ucpi, cylno));
 111         }
 112
 113         ubh_mark_buffer_dirty (USPI_UBH, 1);
 114         ubh_mark_buffer_dirty (UCPI_UBH, 1);
 115         if (sb->s_flags & MS_SYNCHRONOUS) {
 116                 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi);
 117                 ubh_wait_on_buffer (UCPI_UBH);
 118         }
 119         sb->s_dirt = 1;
 120
 121         unlock_super (sb);
 122         UFSD(("EXIT\n"))
 123         return;
 124
 125 failed:
 126         unlock_super (sb);
 127         UFSD(("EXIT (FAILED)\n"))
 128         return;
 129 }
 130
 131 /*
 132  * Free 'count' fragments from fragment number 'fragment' (free whole blocks)
 133  */
 134 void ufs_free_blocks (struct inode * inode, unsigned fragment, unsigned count) {
 135         struct super_block * sb;
 136         struct ufs_sb_private_info * uspi;
 137         struct ufs_super_block_first * usb1;
 138         struct ufs_cg_private_info * ucpi;
 139         struct ufs_cylinder_group * ucg;
 140         unsigned overflow, cgno, bit, end_bit, blkno, i, cylno;
 141         unsigned swab;
 142
 143         sb = inode->i_sb;
 144         uspi = sb->u.ufs_sb.s_uspi;
 145         swab = sb->u.ufs_sb.s_swab;
 146         usb1 = ubh_get_usb_first(USPI_UBH);
 147
 148         UFSD(("ENTER, fragment %u, count %u\n", fragment, count))
 149
 150         if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) {
 151                 ufs_error (sb, "ufs_free_blocks", "internal error, "
 152                         "fragment %u, count %u\n", fragment, count);
 153                 goto failed;
 154         }
 155
 156         lock_super(sb);
 157
 158 do_more:
 159         overflow = 0;
 160         cgno = ufs_dtog (fragment);
 161         bit = ufs_dtogd (fragment);
 162         if (cgno >= uspi->s_ncg) {
 163                 ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device");
 164                 goto failed;
 165         }
 166         end_bit = bit + count;
 167         if (end_bit > uspi->s_fpg) {
 168                 overflow = bit + count - uspi->s_fpg;
 169                 count -= overflow;
 170                 end_bit -= overflow;
 171         }
 172
 173         ucpi = ufs_load_cylinder (sb, cgno);
 174         if (!ucpi)
 175                 goto failed;
 176         ucg = ubh_get_ucg (UCPI_UBH);
 177         if (!ufs_cg_chkmagic (ucg)) {
 178                 ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno);
 179                 goto failed;
 180         }
 181
 182         for (i = bit; i < end_bit; i += uspi->s_fpb) {
 183                 blkno = ufs_fragstoblks(i);
 184                 if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, blkno)) {
 185                         ufs_error(sb, "ufs_free_blocks", "freeing free fragment");
 186                 }
 187                 ubh_setblock(UCPI_UBH, ucpi->c_freeoff, blkno);
 188                 if ((sb->u.ufs_sb.s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
 189                         ufs_clusteracct (sb, ucpi, blkno, 1);
 190                 DQUOT_FREE_BLOCK(sb, inode, uspi->s_fpb);
 191                 INC_SWAB32(ucg->cg_cs.cs_nbfree);
 192                 INC_SWAB32(usb1->fs_cstotal.cs_nbfree);
 193                 INC_SWAB32(sb->fs_cs(cgno).cs_nbfree);
 194                 cylno = ufs_cbtocylno(i);
 195                 INC_SWAB16(ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(i)));
 196                 INC_SWAB32(ubh_cg_blktot(ucpi, cylno));
 197         }
 198
 199         ubh_mark_buffer_dirty (USPI_UBH, 1);
 200         ubh_mark_buffer_dirty (UCPI_UBH, 1);
 201         if (sb->s_flags & MS_SYNCHRONOUS) {
 202                 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi);
 203                 ubh_wait_on_buffer (UCPI_UBH);
 204         }
 205
 206         if (overflow) {
 207                 fragment += count;
 208                 count = overflow;
 209                 goto do_more;
 210         }
 211
 212         sb->s_dirt = 1;
 213         unlock_super (sb);
 214         UFSD(("EXIT\n"))
 215         return;
 216
 217 failed:
 218         unlock_super (sb);
 219         UFSD(("EXIT (FAILED)\n"))
 220         return;
 221 }
 222
 223
 224
 225 #define NULLIFY_FRAGMENTS \
 226         for (i = oldcount; i < newcount; i++) { \
 227                 bh = getblk (sb->s_dev, result + i, sb->s_blocksize); \
 228                 memset (bh->b_data, 0, sb->s_blocksize); \
 229                 mark_buffer_uptodate(bh, 1); \
 230                 mark_buffer_dirty (bh, 1); \
 231                 if (IS_SYNC(inode)) { \
 232                         ll_rw_block (WRITE, 1, &bh); \
 233                         wait_on_buffer (bh); \
 234                 } \
 235                 brelse (bh); \
 236         }
 237
 238 unsigned ufs_new_fragments (struct inode * inode, u32 * p, unsigned fragment,
 239         unsigned goal, unsigned count, int * err )
 240 {
 241         struct super_block * sb;
 242         struct ufs_sb_private_info * uspi;
 243         struct ufs_super_block_first * usb1;
 244         struct buffer_head * bh;
 245         unsigned cgno, oldcount, newcount, tmp, request, i, result;
 246         unsigned swab;
 247
 248         UFSD(("ENTER, ino %lu, fragment %u, goal %u, count %u\n", inode->i_ino, fragment, goal, count))
 249
 250         sb = inode->i_sb;
 251         swab = sb->u.ufs_sb.s_swab;
 252         uspi = sb->u.ufs_sb.s_uspi;
 253         usb1 = ubh_get_usb_first(USPI_UBH);
 254         *err = -ENOSPC;
 255
 256         lock_super (sb);
 257
 258         tmp = SWAB32(*p);
 259         if (count + ufs_fragnum(fragment) > uspi->s_fpb) {
 260                 ufs_warning (sb, "ufs_new_fragments", "internal warning"
 261                         " fragment %u, count %u", fragment, count);
 262                 count = uspi->s_fpb - ufs_fragnum(fragment);
 263         }
 264         oldcount = ufs_fragnum (fragment);
 265         newcount = oldcount + count;
 266
 267         /*
 268          * Somebody else has just allocated our fragments
 269          */
 270         if (oldcount) {
 271                 if (!tmp) {
 272                         ufs_error (sb, "ufs_new_fragments", "internal error, "
 273                                 "fragment %u, tmp %u\n", fragment, tmp);
 274                         return (unsigned)-1;
 275                 }
 276                 if (fragment < inode->u.ufs_i.i_lastfrag) {
 277                         UFSD(("EXIT (ALREADY ALLOCATED)\n"))
 278                         unlock_super (sb);
 279                         return 0;
 280                 }
 281         }
 282         else {
 283                 if (tmp) {
 284                         UFSD(("EXIT (ALREADY ALLOCATED)\n"))
 285                         unlock_super(sb);
 286                         return 0;
 287                 }
 288         }
 289
 290         /*
 291          * There is not enough space for user on the device
 292          */
 293         if (!fsuser() && ufs_freespace(usb1, UFS_MINFREE) <= 0) {
 294                 unlock_super (sb);
 295                 UFSD(("EXIT (FAILED)\n"))
 296                 return 0;
 297         }
 298
 299         if (goal >= uspi->s_size)
 300                 goal = 0;
 301         if (goal == 0)
 302                 cgno = ufs_inotocg (inode->i_ino);
 303         else
 304                 cgno = ufs_dtog (goal);
 305
 306         /*
 307          * allocate new fragment
 308          */
 309         if (oldcount == 0) {
 310                 result = ufs_alloc_fragments (inode, cgno, goal, count, err);
 311                 if (result) {
 312                         *p = SWAB32(result);
 313                         *err = 0;
 314                         inode->i_blocks += count << uspi->s_nspfshift;
 315                         inode->u.ufs_i.i_lastfrag = max (inode->u.ufs_i.i_lastfrag, fragment + count);
 316                         NULLIFY_FRAGMENTS
 317                 }
 318                 unlock_super(sb);
 319                 UFSD(("EXIT, result %u\n", result))
 320                 return result;
 321         }
 322
 323         /*
 324          * resize block
 325          */
 326         result = ufs_add_fragments (inode, tmp, oldcount, newcount, err);
 327         if (result) {
 328                 *err = 0;
 329                 inode->i_blocks += count << uspi->s_nspfshift;
 330                 inode->u.ufs_i.i_lastfrag = max (inode->u.ufs_i.i_lastfrag, fragment + count);
 331                 NULLIFY_FRAGMENTS
 332                 unlock_super(sb);
 333                 UFSD(("EXIT, result %u\n", result))
 334                 return result;
 335         }
 336
 337         /*
 338          * allocate new block and move data
 339          */
 340         switch (SWAB32(usb1->fs_optim)) {
 341             case UFS_OPTSPACE:
 342                 request = newcount;
 343                 if (uspi->s_minfree < 5 || SWAB32(usb1->fs_cstotal.cs_nffree)
 344                     > uspi->s_dsize * uspi->s_minfree / (2 * 100) )
 345                         break;
 346                 usb1->fs_optim = SWAB32(UFS_OPTTIME);
 347                 break;
 348             default:
 349                 usb1->fs_optim = SWAB32(UFS_OPTTIME);
 350
 351             case UFS_OPTTIME:
 352                 request = uspi->s_fpb;
 353                 if (SWAB32(usb1->fs_cstotal.cs_nffree) < uspi->s_dsize *
 354                     (uspi->s_minfree - 2) / 100)
 355                         break;
 356                 usb1->fs_optim = SWAB32(UFS_OPTSPACE);
 357                 break;
 358         }
 359         result = ufs_alloc_fragments (inode, cgno, goal, request, err);
 360         if (result) {
 361                 for (i = 0; i < oldcount; i++) {
 362                         bh = bread (sb->s_dev, tmp + i, sb->s_blocksize);
 363                         mark_buffer_clean (bh);
 364                         bh->b_blocknr = result + i;
 365                         mark_buffer_dirty (bh, 0);
 366                         if (IS_SYNC(inode)) {
 367                                 ll_rw_block (WRITE, 1, &bh);
 368                                 wait_on_buffer (bh);
 369                         }
 370                         brelse (bh);
 371                 }
 372                 *p = SWAB32(result);
 373                 *err = 0;
 374                 inode->i_blocks += count << uspi->s_nspfshift;
 375                 inode->u.ufs_i.i_lastfrag = max (inode->u.ufs_i.i_lastfrag, fragment + count);
 376                 NULLIFY_FRAGMENTS
 377                 unlock_super(sb);
 378                 if (newcount < request)
 379                         ufs_free_fragments (inode, result + newcount, request - newcount);
 380                 ufs_free_fragments (inode, tmp, oldcount);
 381                 UFSD(("EXIT, result %u\n", result))
 382                 return result;
 383         }
 384
 385         unlock_super(sb);
 386         UFSD(("EXIT (FAILED)\n"))
 387         return 0;
 388 }
 389
 390 unsigned ufs_add_fragments (struct inode * inode, unsigned fragment,
 391         unsigned oldcount, unsigned newcount, int * err)
 392 {
 393         struct super_block * sb;
 394         struct ufs_sb_private_info * uspi;
 395         struct ufs_super_block_first * usb1;
 396         struct ufs_cg_private_info * ucpi;
 397         struct ufs_cylinder_group * ucg;
 398         unsigned cgno, fragno, fragoff, count, fragsize, i;
 399         unsigned swab;
 400
 401         UFSD(("ENTER, fragment %u, oldcount %u, newcount %u\n", fragment, oldcount, newcount))
 402
 403         sb = inode->i_sb;
 404         swab = sb->u.ufs_sb.s_swab;
 405         uspi = sb->u.ufs_sb.s_uspi;
 406         usb1 = ubh_get_usb_first (USPI_UBH);
 407         count = newcount - oldcount;
 408
 409         cgno = ufs_dtog(fragment);
 410         if (sb->fs_cs(cgno).cs_nffree < count)
 411                 return 0;
 412         if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
 413                 return 0;
 414         ucpi = ufs_load_cylinder (sb, cgno);
 415         if (!ucpi)
 416                 return 0;
 417         ucg = ubh_get_ucg (UCPI_UBH);
 418         if (!ufs_cg_chkmagic(ucg)) {
 419                 ufs_panic (sb, "ufs_add_fragments",
 420                         "internal error, bad magic number on cg %u", cgno);
 421                 return 0;
 422         }
 423
 424         fragno = ufs_dtogd (fragment);
 425         fragoff = ufs_fragnum (fragno);
 426         for (i = oldcount; i < newcount; i++)
 427                 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
 428                         return 0;
 429         /*
 430          * Block can be extended
 431          */
 432         ucg->cg_time = SWAB32(CURRENT_TIME);
 433         for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
 434                 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
 435                         break;
 436         fragsize = i - oldcount;
 437         if (!SWAB32(ucg->cg_frsum[fragsize]))
 438                 ufs_panic (sb, "ufs_add_fragments",
 439                         "internal error or corrupted bitmap on cg %u", cgno);
 440         DEC_SWAB32(ucg->cg_frsum[fragsize]);
 441         if (fragsize != count)
 442                 INC_SWAB32(ucg->cg_frsum[fragsize - count]);
 443         for (i = oldcount; i < newcount; i++)
 444                 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, fragno + i);
 445         if(DQUOT_ALLOC_BLOCK(sb, inode, count)) {
 446                 *err = -EDQUOT;
 447                 return 0;
 448         }
 449         SUB_SWAB32(ucg->cg_cs.cs_nffree, count);
 450         SUB_SWAB32(sb->fs_cs(cgno).cs_nffree, count);
 451         SUB_SWAB32(usb1->fs_cstotal.cs_nffree, count);
 452
 453         ubh_mark_buffer_dirty (USPI_UBH, 1);
 454         ubh_mark_buffer_dirty (UCPI_UBH, 1);
 455         if (sb->s_flags & MS_SYNCHRONOUS) {
 456                 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi);
 457                 ubh_wait_on_buffer (UCPI_UBH);
 458         }
 459         sb->s_dirt = 1;
 460
 461         UFSD(("EXIT, fragment %u\n", fragment))
 462
 463         return fragment;
 464 }
 465
 466 #define UFS_TEST_FREE_SPACE_CG \
 467         ucg = (struct ufs_cylinder_group *) sb->u.ufs_sb.s_ucg[cgno]->b_data; \
 468         if (SWAB32(ucg->cg_cs.cs_nbfree)) \
 469                 goto cg_found; \
 470         for (k = count; k < uspi->s_fpb; k++) \
 471                 if (SWAB32(ucg->cg_frsum[k])) \
 472                         goto cg_found;
 473
 474 unsigned ufs_alloc_fragments (struct inode * inode, unsigned cgno,
 475         unsigned goal, unsigned count, int * err)
 476 {
 477         struct super_block * sb;
 478         struct ufs_sb_private_info * uspi;
 479         struct ufs_super_block_first * usb1;
 480         struct ufs_cg_private_info * ucpi;
 481         struct ufs_cylinder_group * ucg;
 482         unsigned oldcg, i, j, k, result, allocsize;
 483         unsigned swab;
 484
 485         UFSD(("ENTER, ino %lu, cgno %u, goal %u, count %u\n", inode->i_ino, cgno, goal, count))
 486
 487         sb = inode->i_sb;
 488         swab = sb->u.ufs_sb.s_swab;
 489         uspi = sb->u.ufs_sb.s_uspi;
 490         usb1 = ubh_get_usb_first(USPI_UBH);
 491         oldcg = cgno;
 492
 493         /*
 494          * 1. searching on preferred cylinder group
 495          */
 496         UFS_TEST_FREE_SPACE_CG
 497
 498         /*
 499          * 2. quadratic rehash
 500          */
 501         for (j = 1; j < uspi->s_ncg; j *= 2) {
 502                 cgno += j;
 503                 if (cgno >= uspi->s_ncg)
 504                         cgno -= uspi->s_ncg;
 505                 UFS_TEST_FREE_SPACE_CG
 506         }
 507
 508         /*
 509          * 3. brute force search
 510          * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
 511          */
 512         cgno = (oldcg + 1) % uspi->s_ncg;
 513         for (j = 2; j < uspi->s_ncg; j++) {
 514                 cgno++;
 515                 if (cgno >= uspi->s_ncg)
 516                         cgno = 0;
 517                 UFS_TEST_FREE_SPACE_CG
 518         }
 519
 520         UFSD(("EXIT (FAILED)\n"))
 521         return 0;
 522
 523 cg_found:
 524         ucpi = ufs_load_cylinder (sb, cgno);
 525         if (!ucpi)
 526                 return 0;
 527         ucg = ubh_get_ucg (UCPI_UBH);
 528         if (!ufs_cg_chkmagic(ucg))
 529                 ufs_panic (sb, "ufs_alloc_fragments",
 530                         "internal error, bad magic number on cg %u", cgno);
 531         ucg->cg_time = SWAB32(CURRENT_TIME);
 532
 533         if (count == uspi->s_fpb) {
 534                 result = ufs_alloccg_block (inode, ucpi, goal, err);
 535                 if (result == (unsigned)-1)
 536                         return 0;
 537                 goto succed;
 538         }
 539
 540         for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
 541                 if (SWAB32(ucg->cg_frsum[allocsize]) != 0)
 542                         break;
 543
 544         if (allocsize == uspi->s_fpb) {
 545                 result = ufs_alloccg_block (inode, ucpi, goal, err);
 546                 if (result == (unsigned)-1)
 547                         return 0;
 548                 goal = ufs_dtogd (result);
 549                 for (i = count; i < uspi->s_fpb; i++)
 550                         ubh_setbit (UCPI_UBH, ucpi->c_freeoff, goal + i);
 551                 i = uspi->s_fpb - count;
 552                 DQUOT_FREE_BLOCK(sb, inode, i);
 553                 ADD_SWAB32(ucg->cg_cs.cs_nffree, i);
 554                 ADD_SWAB32(usb1->fs_cstotal.cs_nffree, i);
 555                 ADD_SWAB32(sb->fs_cs(cgno).cs_nffree, i);
 556                 INC_SWAB32(ucg->cg_frsum[i]);
 557                 goto succed;
 558         }
 559
 560         result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
 561         if (result == (unsigned)-1)
 562                 return 0;
 563         if(DQUOT_ALLOC_BLOCK(sb, inode, count)) {
 564                 *err = -EDQUOT;
 565                 return 0;
 566         }
 567         for (i = 0; i < count; i++)
 568                 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, result + i);
 569         SUB_SWAB32(ucg->cg_cs.cs_nffree, count);
 570         SUB_SWAB32(usb1->fs_cstotal.cs_nffree, count);
 571         SUB_SWAB32(sb->fs_cs(cgno).cs_nffree, count);
 572         DEC_SWAB32(ucg->cg_frsum[allocsize]);
 573         if (count != allocsize)
 574                 INC_SWAB32(ucg->cg_frsum[allocsize - count]);
 575
 576 succed:
 577         ubh_mark_buffer_dirty (USPI_UBH, 1);
 578         ubh_mark_buffer_dirty (UCPI_UBH, 1);
 579         if (sb->s_flags & MS_SYNCHRONOUS) {
 580                 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi);
 581                 ubh_wait_on_buffer (UCPI_UBH);
 582         }
 583         sb->s_dirt = 1;
 584
 585         result += cgno * uspi->s_fpg;
 586         UFSD(("EXIT3, result %u\n", result))
 587         return result;
 588 }
 589
 590 unsigned ufs_alloccg_block (struct inode * inode,
 591         struct ufs_cg_private_info * ucpi, unsigned goal, int * err)
 592 {
 593         struct super_block * sb;
 594         struct ufs_sb_private_info * uspi;
 595         struct ufs_super_block_first * usb1;
 596         struct ufs_cylinder_group * ucg;
 597         unsigned result, cylno, blkno;
 598         unsigned swab;
 599
 600         UFSD(("ENTER, goal %u\n", goal))
 601
 602         sb = inode->i_sb;
 603         swab = sb->u.ufs_sb.s_swab;
 604         uspi = sb->u.ufs_sb.s_uspi;
 605         usb1 = ubh_get_usb_first(USPI_UBH);
 606         ucg = ubh_get_ucg(UCPI_UBH);
 607
 608         if (goal == 0) {
 609                 goal = ucpi->c_rotor;
 610                 goto norot;
 611         }
 612         goal = ufs_blknum (goal);
 613         goal = ufs_dtogd (goal);
 614
 615         /*
 616          * If the requested block is available, use it.
 617          */
 618         if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, ufs_fragstoblks(goal))) {
 619                 result = goal;
 620                 goto gotit;
 621         }
 622
 623 norot:
 624         result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
 625         if (result == (unsigned)-1)
 626                 return (unsigned)-1;
 627         ucpi->c_rotor = result;
 628 gotit:
 629         blkno = ufs_fragstoblks(result);
 630         ubh_clrblock (UCPI_UBH, ucpi->c_freeoff, blkno);
 631         if ((sb->u.ufs_sb.s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
 632                 ufs_clusteracct (sb, ucpi, blkno, -1);
 633         if(DQUOT_ALLOC_BLOCK(sb, inode, uspi->s_fpb)) {
 634                 *err = -EDQUOT;
 635                 return (unsigned)-1;
 636         }
 637         DEC_SWAB32(ucg->cg_cs.cs_nbfree);
 638         DEC_SWAB32(usb1->fs_cstotal.cs_nbfree);
 639         DEC_SWAB32(sb->fs_cs(ucpi->c_cgx).cs_nbfree);
 640         cylno = ufs_cbtocylno(result);
 641         DEC_SWAB16(ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(result)));
 642         DEC_SWAB32(ubh_cg_blktot(ucpi, cylno));
 643
 644         UFSD(("EXIT, result %u\n", result))
 645
 646         return result;
 647 }
 648
 649 unsigned ufs_bitmap_search (struct super_block * sb,
 650         struct ufs_cg_private_info * ucpi, unsigned goal, unsigned count)
 651 {
 652         struct ufs_sb_private_info * uspi;
 653         struct ufs_super_block_first * usb1;
 654         struct ufs_cylinder_group * ucg;
 655         unsigned start, length, location, result;
 656         unsigned possition, fragsize, blockmap, mask;
 657         unsigned swab;
 658
 659         UFSD(("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count))
 660
 661         swab = sb->u.ufs_sb.s_swab;
 662         uspi = sb->u.ufs_sb.s_uspi;
 663         usb1 = ubh_get_usb_first (USPI_UBH);
 664         ucg = ubh_get_ucg(UCPI_UBH);
 665
 666         if (goal)
 667                 start = ufs_dtogd(goal) >> 3;
 668         else
 669                 start = ucpi->c_frotor >> 3;
 670
 671         length = howmany(uspi->s_fpg, 8) - start;
 672         location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff + start, length,
 673                 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
 674                 1 << (count - 1 + (uspi->s_fpb & 7)));
 675         if (location == 0) {
 676                 length = start + 1;
 677                 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff, length,
 678                         (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
 679                         1 << (count - 1 + (uspi->s_fpb & 7)));
 680                 if (location == 0) {
 681                         ufs_error (sb, "ufs_bitmap_search",
 682                         "bitmap corrupted on cg %u, start %u, length %u, count %u, freeoff %u\n",
 683                         ucpi->c_cgx, start, length, count, ucpi->c_freeoff);
 684                         return (unsigned)-1;
 685                 }
 686                 start = 0;
 687         }
 688         result = (start + length - location) << 3;
 689         ucpi->c_frotor = result;
 690
 691         /*
 692          * found the byte in the map
 693          */
 694         blockmap = ubh_blkmap(UCPI_UBH, ucpi->c_freeoff, result);
 695         fragsize = 0;
 696         for (possition = 0, mask = 1; possition < 8; possition++, mask <<= 1) {
 697                 if (blockmap & mask) {
 698                         if (!(possition & uspi->s_fpbmask))
 699                                 fragsize = 1;
 700                         else
 701                                 fragsize++;
 702                 }
 703                 else {
 704                         if (fragsize == count) {
 705                                 result += possition - count;
 706                                 UFSD(("EXIT, result %u\n", result))
 707                                 return result;
 708                         }
 709                         fragsize = 0;
 710                 }
 711         }
 712         if (fragsize == count) {
 713                 result += possition - count;
 714                 UFSD(("EXIT, result %u\n", result))
 715                 return result;
 716         }
 717         ufs_error (sb, "ufs_bitmap_search", "block not in map on cg %u\n", ucpi->c_cgx);
 718         UFSD(("EXIT (FAILED)\n"))
 719         return (unsigned)-1;
 720 }
 721
 722 void ufs_clusteracct(struct super_block * sb,
 723         struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
 724 {
 725         struct ufs_sb_private_info * uspi;
 726         int i, start, end, forw, back;
 727         unsigned swab;
 728
 729
 730         uspi = sb->u.ufs_sb.s_uspi;
 731         swab = sb->u.ufs_sb.s_swab;
 732
 733         if (uspi->s_contigsumsize <= 0)
 734                 return;
 735
 736         if (cnt > 0)
 737                 ubh_setbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
 738         else
 739                 ubh_clrbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
 740
 741         /*
 742          * Find the size of the cluster going forward.
 743          */
 744         start = blkno + 1;
 745         end = start + uspi->s_contigsumsize;
 746         if ( end >= ucpi->c_nclusterblks)
 747                 end = ucpi->c_nclusterblks;
 748         i = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_clusteroff, end, start);
 749         if (i > end)
 750                 i = end;
 751         forw = i - start;
 752
 753         /*
 754          * Find the size of the cluster going backward.
 755          */
 756         start = blkno - 1;
 757         end = start - uspi->s_contigsumsize;
 758         if (end < 0 )
 759                 end = -1;
 760         i = ubh_find_last_zero_bit (UCPI_UBH, ucpi->c_clusteroff, start, end);
 761         if ( i < end)
 762                 i = end;
 763         back = start - i;
 764
 765         /*
 766          * Account for old cluster and the possibly new forward and
 767          * back clusters.
 768          */
 769         i = back + forw + 1;
 770         if (i > uspi->s_contigsumsize)
 771                 i = uspi->s_contigsumsize;
 772         ADD_SWAB32(*((u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (i << 2))), cnt);
 773         if (back > 0)
 774                 SUB_SWAB32(*((u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (back << 2))), cnt);
 775         if (forw > 0)
 776                 SUB_SWAB32(*((u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (forw << 2))), cnt);
 777 }
 778
 779
 780 static unsigned char ufs_fragtable_8fpb[] = {
 781         0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
 782         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
 783         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 784         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
 785         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 786         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 787         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
 788         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
 789         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 790         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 791         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 792         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
 793         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
 794         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
 795         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
 796         0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
 797 };
 798
 799 static unsigned char ufs_fragtable_other[] = {
 800         0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
 801         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 802         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 803         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
 804         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 805         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 806         0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
 807         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
 808         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 809         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 810         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 811         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
 812         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
 813         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
 814         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
 815         0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
 816 };