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