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