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