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);
 114         ubh_mark_buffer_dirty (UCPI_UBH);
 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);
 200         ubh_mark_buffer_dirty (UCPI_UBH);
 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); \
 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                         if(bh)
 364                         {
 365                                 mark_buffer_clean (bh);
 366                                 bh->b_blocknr = result + i;
 367                                 mark_buffer_dirty (bh);
 368                                 if (IS_SYNC(inode)) {
 369                                         ll_rw_block (WRITE, 1, &bh);
 370                                         wait_on_buffer (bh);
 371                                 }
 372                                 brelse (bh);
 373                         }
 374                         else
 375                         {
 376                                 printk(KERN_ERR "ufs_new_fragments: bread fail\n");
 377                                 return 0;
 378                         }
 379                 }
 380                 *p = SWAB32(result);
 381                 *err = 0;
 382                 inode->i_blocks += count << uspi->s_nspfshift;
 383                 inode->u.ufs_i.i_lastfrag = max (inode->u.ufs_i.i_lastfrag, fragment + count);
 384                 NULLIFY_FRAGMENTS
 385                 unlock_super(sb);
 386                 if (newcount < request)
 387                         ufs_free_fragments (inode, result + newcount, request - newcount);
 388                 ufs_free_fragments (inode, tmp, oldcount);
 389                 UFSD(("EXIT, result %u\n", result))
 390                 return result;
 391         }
 392
 393         unlock_super(sb);
 394         UFSD(("EXIT (FAILED)\n"))
 395         return 0;
 396 }
 397
 398 unsigned ufs_add_fragments (struct inode * inode, unsigned fragment,
 399         unsigned oldcount, unsigned newcount, int * err)
 400 {
 401         struct super_block * sb;
 402         struct ufs_sb_private_info * uspi;
 403         struct ufs_super_block_first * usb1;
 404         struct ufs_cg_private_info * ucpi;
 405         struct ufs_cylinder_group * ucg;
 406         unsigned cgno, fragno, fragoff, count, fragsize, i;
 407         unsigned swab;
 408
 409         UFSD(("ENTER, fragment %u, oldcount %u, newcount %u\n", fragment, oldcount, newcount))
 410
 411         sb = inode->i_sb;
 412         swab = sb->u.ufs_sb.s_swab;
 413         uspi = sb->u.ufs_sb.s_uspi;
 414         usb1 = ubh_get_usb_first (USPI_UBH);
 415         count = newcount - oldcount;
 416
 417         cgno = ufs_dtog(fragment);
 418         if (sb->fs_cs(cgno).cs_nffree < count)
 419                 return 0;
 420         if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
 421                 return 0;
 422         ucpi = ufs_load_cylinder (sb, cgno);
 423         if (!ucpi)
 424                 return 0;
 425         ucg = ubh_get_ucg (UCPI_UBH);
 426         if (!ufs_cg_chkmagic(ucg)) {
 427                 ufs_panic (sb, "ufs_add_fragments",
 428                         "internal error, bad magic number on cg %u", cgno);
 429                 return 0;
 430         }
 431
 432         fragno = ufs_dtogd (fragment);
 433         fragoff = ufs_fragnum (fragno);
 434         for (i = oldcount; i < newcount; i++)
 435                 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
 436                         return 0;
 437         /*
 438          * Block can be extended
 439          */
 440         ucg->cg_time = SWAB32(CURRENT_TIME);
 441         for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
 442                 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, fragno + i))
 443                         break;
 444         fragsize = i - oldcount;
 445         if (!SWAB32(ucg->cg_frsum[fragsize]))
 446                 ufs_panic (sb, "ufs_add_fragments",
 447                         "internal error or corrupted bitmap on cg %u", cgno);
 448         DEC_SWAB32(ucg->cg_frsum[fragsize]);
 449         if (fragsize != count)
 450                 INC_SWAB32(ucg->cg_frsum[fragsize - count]);
 451         for (i = oldcount; i < newcount; i++)
 452                 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, fragno + i);
 453         if(DQUOT_ALLOC_BLOCK(sb, inode, count)) {
 454                 *err = -EDQUOT;
 455                 return 0;
 456         }
 457         SUB_SWAB32(ucg->cg_cs.cs_nffree, count);
 458         SUB_SWAB32(sb->fs_cs(cgno).cs_nffree, count);
 459         SUB_SWAB32(usb1->fs_cstotal.cs_nffree, count);
 460
 461         ubh_mark_buffer_dirty (USPI_UBH);
 462         ubh_mark_buffer_dirty (UCPI_UBH);
 463         if (sb->s_flags & MS_SYNCHRONOUS) {
 464                 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi);
 465                 ubh_wait_on_buffer (UCPI_UBH);
 466         }
 467         sb->s_dirt = 1;
 468
 469         UFSD(("EXIT, fragment %u\n", fragment))
 470
 471         return fragment;
 472 }
 473
 474 #define UFS_TEST_FREE_SPACE_CG \
 475         ucg = (struct ufs_cylinder_group *) sb->u.ufs_sb.s_ucg[cgno]->b_data; \
 476         if (SWAB32(ucg->cg_cs.cs_nbfree)) \
 477                 goto cg_found; \
 478         for (k = count; k < uspi->s_fpb; k++) \
 479                 if (SWAB32(ucg->cg_frsum[k])) \
 480                         goto cg_found;
 481
 482 unsigned ufs_alloc_fragments (struct inode * inode, unsigned cgno,
 483         unsigned goal, unsigned count, int * err)
 484 {
 485         struct super_block * sb;
 486         struct ufs_sb_private_info * uspi;
 487         struct ufs_super_block_first * usb1;
 488         struct ufs_cg_private_info * ucpi;
 489         struct ufs_cylinder_group * ucg;
 490         unsigned oldcg, i, j, k, result, allocsize;
 491         unsigned swab;
 492
 493         UFSD(("ENTER, ino %lu, cgno %u, goal %u, count %u\n", inode->i_ino, cgno, goal, count))
 494
 495         sb = inode->i_sb;
 496         swab = sb->u.ufs_sb.s_swab;
 497         uspi = sb->u.ufs_sb.s_uspi;
 498         usb1 = ubh_get_usb_first(USPI_UBH);
 499         oldcg = cgno;
 500
 501         /*
 502          * 1. searching on preferred cylinder group
 503          */
 504         UFS_TEST_FREE_SPACE_CG
 505
 506         /*
 507          * 2. quadratic rehash
 508          */
 509         for (j = 1; j < uspi->s_ncg; j *= 2) {
 510                 cgno += j;
 511                 if (cgno >= uspi->s_ncg)
 512                         cgno -= uspi->s_ncg;
 513                 UFS_TEST_FREE_SPACE_CG
 514         }
 515
 516         /*
 517          * 3. brute force search
 518          * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
 519          */
 520         cgno = (oldcg + 1) % uspi->s_ncg;
 521         for (j = 2; j < uspi->s_ncg; j++) {
 522                 cgno++;
 523                 if (cgno >= uspi->s_ncg)
 524                         cgno = 0;
 525                 UFS_TEST_FREE_SPACE_CG
 526         }
 527
 528         UFSD(("EXIT (FAILED)\n"))
 529         return 0;
 530
 531 cg_found:
 532         ucpi = ufs_load_cylinder (sb, cgno);
 533         if (!ucpi)
 534                 return 0;
 535         ucg = ubh_get_ucg (UCPI_UBH);
 536         if (!ufs_cg_chkmagic(ucg))
 537                 ufs_panic (sb, "ufs_alloc_fragments",
 538                         "internal error, bad magic number on cg %u", cgno);
 539         ucg->cg_time = SWAB32(CURRENT_TIME);
 540
 541         if (count == uspi->s_fpb) {
 542                 result = ufs_alloccg_block (inode, ucpi, goal, err);
 543                 if (result == (unsigned)-1)
 544                         return 0;
 545                 goto succed;
 546         }
 547
 548         for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
 549                 if (SWAB32(ucg->cg_frsum[allocsize]) != 0)
 550                         break;
 551
 552         if (allocsize == uspi->s_fpb) {
 553                 result = ufs_alloccg_block (inode, ucpi, goal, err);
 554                 if (result == (unsigned)-1)
 555                         return 0;
 556                 goal = ufs_dtogd (result);
 557                 for (i = count; i < uspi->s_fpb; i++)
 558                         ubh_setbit (UCPI_UBH, ucpi->c_freeoff, goal + i);
 559                 i = uspi->s_fpb - count;
 560                 DQUOT_FREE_BLOCK(sb, inode, i);
 561                 ADD_SWAB32(ucg->cg_cs.cs_nffree, i);
 562                 ADD_SWAB32(usb1->fs_cstotal.cs_nffree, i);
 563                 ADD_SWAB32(sb->fs_cs(cgno).cs_nffree, i);
 564                 INC_SWAB32(ucg->cg_frsum[i]);
 565                 goto succed;
 566         }
 567
 568         result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
 569         if (result == (unsigned)-1)
 570                 return 0;
 571         if(DQUOT_ALLOC_BLOCK(sb, inode, count)) {
 572                 *err = -EDQUOT;
 573                 return 0;
 574         }
 575         for (i = 0; i < count; i++)
 576                 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, result + i);
 577         SUB_SWAB32(ucg->cg_cs.cs_nffree, count);
 578         SUB_SWAB32(usb1->fs_cstotal.cs_nffree, count);
 579         SUB_SWAB32(sb->fs_cs(cgno).cs_nffree, count);
 580         DEC_SWAB32(ucg->cg_frsum[allocsize]);
 581         if (count != allocsize)
 582                 INC_SWAB32(ucg->cg_frsum[allocsize - count]);
 583
 584 succed:
 585         ubh_mark_buffer_dirty (USPI_UBH);
 586         ubh_mark_buffer_dirty (UCPI_UBH);
 587         if (sb->s_flags & MS_SYNCHRONOUS) {
 588                 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi);
 589                 ubh_wait_on_buffer (UCPI_UBH);
 590         }
 591         sb->s_dirt = 1;
 592
 593         result += cgno * uspi->s_fpg;
 594         UFSD(("EXIT3, result %u\n", result))
 595         return result;
 596 }
 597
 598 unsigned ufs_alloccg_block (struct inode * inode,
 599         struct ufs_cg_private_info * ucpi, unsigned goal, int * err)
 600 {
 601         struct super_block * sb;
 602         struct ufs_sb_private_info * uspi;
 603         struct ufs_super_block_first * usb1;
 604         struct ufs_cylinder_group * ucg;
 605         unsigned result, cylno, blkno;
 606         unsigned swab;
 607
 608         UFSD(("ENTER, goal %u\n", goal))
 609
 610         sb = inode->i_sb;
 611         swab = sb->u.ufs_sb.s_swab;
 612         uspi = sb->u.ufs_sb.s_uspi;
 613         usb1 = ubh_get_usb_first(USPI_UBH);
 614         ucg = ubh_get_ucg(UCPI_UBH);
 615
 616         if (goal == 0) {
 617                 goal = ucpi->c_rotor;
 618                 goto norot;
 619         }
 620         goal = ufs_blknum (goal);
 621         goal = ufs_dtogd (goal);
 622
 623         /*
 624          * If the requested block is available, use it.
 625          */
 626         if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, ufs_fragstoblks(goal))) {
 627                 result = goal;
 628                 goto gotit;
 629         }
 630
 631 norot:
 632         result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
 633         if (result == (unsigned)-1)
 634                 return (unsigned)-1;
 635         ucpi->c_rotor = result;
 636 gotit:
 637         blkno = ufs_fragstoblks(result);
 638         ubh_clrblock (UCPI_UBH, ucpi->c_freeoff, blkno);
 639         if ((sb->u.ufs_sb.s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
 640                 ufs_clusteracct (sb, ucpi, blkno, -1);
 641         if(DQUOT_ALLOC_BLOCK(sb, inode, uspi->s_fpb)) {
 642                 *err = -EDQUOT;
 643                 return (unsigned)-1;
 644         }
 645         DEC_SWAB32(ucg->cg_cs.cs_nbfree);
 646         DEC_SWAB32(usb1->fs_cstotal.cs_nbfree);
 647         DEC_SWAB32(sb->fs_cs(ucpi->c_cgx).cs_nbfree);
 648         cylno = ufs_cbtocylno(result);
 649         DEC_SWAB16(ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(result)));
 650         DEC_SWAB32(ubh_cg_blktot(ucpi, cylno));
 651
 652         UFSD(("EXIT, result %u\n", result))
 653
 654         return result;
 655 }
 656
 657 unsigned ufs_bitmap_search (struct super_block * sb,
 658         struct ufs_cg_private_info * ucpi, unsigned goal, unsigned count)
 659 {
 660         struct ufs_sb_private_info * uspi;
 661         struct ufs_super_block_first * usb1;
 662         struct ufs_cylinder_group * ucg;
 663         unsigned start, length, location, result;
 664         unsigned possition, fragsize, blockmap, mask;
 665         unsigned swab;
 666
 667         UFSD(("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count))
 668
 669         swab = sb->u.ufs_sb.s_swab;
 670         uspi = sb->u.ufs_sb.s_uspi;
 671         usb1 = ubh_get_usb_first (USPI_UBH);
 672         ucg = ubh_get_ucg(UCPI_UBH);
 673
 674         if (goal)
 675                 start = ufs_dtogd(goal) >> 3;
 676         else
 677                 start = ucpi->c_frotor >> 3;
 678
 679         length = ((uspi->s_fpg + 7) >> 3) - start;
 680         location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff + start, length,
 681                 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
 682                 1 << (count - 1 + (uspi->s_fpb & 7)));
 683         if (location == 0) {
 684                 length = start + 1;
 685                 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff, length,
 686                         (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
 687                         1 << (count - 1 + (uspi->s_fpb & 7)));
 688                 if (location == 0) {
 689                         ufs_error (sb, "ufs_bitmap_search",
 690                         "bitmap corrupted on cg %u, start %u, length %u, count %u, freeoff %u\n",
 691                         ucpi->c_cgx, start, length, count, ucpi->c_freeoff);
 692                         return (unsigned)-1;
 693                 }
 694                 start = 0;
 695         }
 696         result = (start + length - location) << 3;
 697         ucpi->c_frotor = result;
 698
 699         /*
 700          * found the byte in the map
 701          */
 702         blockmap = ubh_blkmap(UCPI_UBH, ucpi->c_freeoff, result);
 703         fragsize = 0;
 704         for (possition = 0, mask = 1; possition < 8; possition++, mask <<= 1) {
 705                 if (blockmap & mask) {
 706                         if (!(possition & uspi->s_fpbmask))
 707                                 fragsize = 1;
 708                         else
 709                                 fragsize++;
 710                 }
 711                 else {
 712                         if (fragsize == count) {
 713                                 result += possition - count;
 714                                 UFSD(("EXIT, result %u\n", result))
 715                                 return result;
 716                         }
 717                         fragsize = 0;
 718                 }
 719         }
 720         if (fragsize == count) {
 721                 result += possition - count;
 722                 UFSD(("EXIT, result %u\n", result))
 723                 return result;
 724         }
 725         ufs_error (sb, "ufs_bitmap_search", "block not in map on cg %u\n", ucpi->c_cgx);
 726         UFSD(("EXIT (FAILED)\n"))
 727         return (unsigned)-1;
 728 }
 729
 730 void ufs_clusteracct(struct super_block * sb,
 731         struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
 732 {
 733         struct ufs_sb_private_info * uspi;
 734         int i, start, end, forw, back;
 735         unsigned swab;
 736
 737
 738         uspi = sb->u.ufs_sb.s_uspi;
 739         swab = sb->u.ufs_sb.s_swab;
 740
 741         if (uspi->s_contigsumsize <= 0)
 742                 return;
 743
 744         if (cnt > 0)
 745                 ubh_setbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
 746         else
 747                 ubh_clrbit(UCPI_UBH, ucpi->c_clusteroff, blkno);
 748
 749         /*
 750          * Find the size of the cluster going forward.
 751          */
 752         start = blkno + 1;
 753         end = start + uspi->s_contigsumsize;
 754         if ( end >= ucpi->c_nclusterblks)
 755                 end = ucpi->c_nclusterblks;
 756         i = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_clusteroff, end, start);
 757         if (i > end)
 758                 i = end;
 759         forw = i - start;
 760
 761         /*
 762          * Find the size of the cluster going backward.
 763          */
 764         start = blkno - 1;
 765         end = start - uspi->s_contigsumsize;
 766         if (end < 0 )
 767                 end = -1;
 768         i = ubh_find_last_zero_bit (UCPI_UBH, ucpi->c_clusteroff, start, end);
 769         if ( i < end)
 770                 i = end;
 771         back = start - i;
 772
 773         /*
 774          * Account for old cluster and the possibly new forward and
 775          * back clusters.
 776          */
 777         i = back + forw + 1;
 778         if (i > uspi->s_contigsumsize)
 779                 i = uspi->s_contigsumsize;
 780         ADD_SWAB32(*((u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (i << 2))), cnt);
 781         if (back > 0)
 782                 SUB_SWAB32(*((u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (back << 2))), cnt);
 783         if (forw > 0)
 784                 SUB_SWAB32(*((u32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (forw << 2))), cnt);
 785 }
 786
 787
 788 static unsigned char ufs_fragtable_8fpb[] = {
 789         0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
 790         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
 791         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 792         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
 793         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 794         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 795         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
 796         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
 797         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 798         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 799         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 800         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
 801         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
 802         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
 803         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
 804         0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
 805 };
 806
 807 static unsigned char ufs_fragtable_other[] = {
 808         0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
 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         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
 812         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 813         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 814         0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
 815         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
 816         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 817         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 818         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 819         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
 820         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
 821         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
 822         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
 823         0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
 824 };