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