SAFE public projects git trees. - safe/jmp/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/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 baseblk,
 231                                unsigned int count, unsigned int oldb,
 232                                unsigned int newb, struct page *locked_page)
 233 {
 234         unsigned int blk_per_page = 1 << (PAGE_CACHE_SHIFT - inode->i_blkbits);
 235         struct address_space *mapping = inode->i_mapping;
 236         pgoff_t index, cur_index;
 237         unsigned int i, 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 (i = 0; i < count; i += blk_per_page) {
 250                 index = (baseblk+i) >> (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                 j = i;
 260                 head = page_buffers(page);
 261                 bh = head;
 262                 do {
 263                         if (likely(bh->b_blocknr == j + oldb && j < count)) {
 264                                 unmap_underlying_metadata(bh->b_bdev,
 265                                                           bh->b_blocknr);
 266                                 bh->b_blocknr = newb + j++;
 267                                 mark_buffer_dirty(bh);
 268                         }
 269
 270                         bh = bh->b_this_page;
 271                 } while (bh != head);
 272
 273                 set_page_dirty(page);
 274
 275                 if (likely(cur_index != index))
 276                         ufs_put_locked_page(page);
 277         }
 278         UFSD("EXIT\n");
 279 }
 280
 281 static void ufs_clear_frags(struct inode *inode, sector_t beg, unsigned int n,
 282                             int sync)
 283 {
 284         struct buffer_head *bh;
 285         sector_t end = beg + n;
 286
 287         for (; beg < end; ++beg) {
 288                 bh = sb_getblk(inode->i_sb, beg);
 289                 lock_buffer(bh);
 290                 memset(bh->b_data, 0, inode->i_sb->s_blocksize);
 291                 set_buffer_uptodate(bh);
 292                 mark_buffer_dirty(bh);
 293                 unlock_buffer(bh);
 294                 if (IS_SYNC(inode) || sync)
 295                         sync_dirty_buffer(bh);
 296                 brelse(bh);
 297         }
 298 }
 299
 300 unsigned ufs_new_fragments(struct inode * inode, __fs32 * p, unsigned fragment,
 301                            unsigned goal, unsigned count, int * err, struct page *locked_page)
 302 {
 303         struct super_block * sb;
 304         struct ufs_sb_private_info * uspi;
 305         struct ufs_super_block_first * usb1;
 306         unsigned cgno, oldcount, newcount, tmp, request, result;
 307
 308         UFSD("ENTER, ino %lu, fragment %u, goal %u, count %u\n", inode->i_ino, fragment, goal, count);
 309
 310         sb = inode->i_sb;
 311         uspi = UFS_SB(sb)->s_uspi;
 312         usb1 = ubh_get_usb_first(uspi);
 313         *err = -ENOSPC;
 314
 315         lock_super (sb);
 316
 317         tmp = fs32_to_cpu(sb, *p);
 318         if (count + ufs_fragnum(fragment) > uspi->s_fpb) {
 319                 ufs_warning (sb, "ufs_new_fragments", "internal warning"
 320                         " fragment %u, count %u", fragment, count);
 321                 count = uspi->s_fpb - ufs_fragnum(fragment);
 322         }
 323         oldcount = ufs_fragnum (fragment);
 324         newcount = oldcount + count;
 325
 326         /*
 327          * Somebody else has just allocated our fragments
 328          */
 329         if (oldcount) {
 330                 if (!tmp) {
 331                         ufs_error (sb, "ufs_new_fragments", "internal error, "
 332                                 "fragment %u, tmp %u\n", fragment, tmp);
 333                         unlock_super (sb);
 334                         return (unsigned)-1;
 335                 }
 336                 if (fragment < UFS_I(inode)->i_lastfrag) {
 337                         UFSD("EXIT (ALREADY ALLOCATED)\n");
 338                         unlock_super (sb);
 339                         return 0;
 340                 }
 341         }
 342         else {
 343                 if (tmp) {
 344                         UFSD("EXIT (ALREADY ALLOCATED)\n");
 345                         unlock_super(sb);
 346                         return 0;
 347                 }
 348         }
 349
 350         /*
 351          * There is not enough space for user on the device
 352          */
 353         if (!capable(CAP_SYS_RESOURCE) && ufs_freespace(uspi, UFS_MINFREE) <= 0) {
 354                 unlock_super (sb);
 355                 UFSD("EXIT (FAILED)\n");
 356                 return 0;
 357         }
 358
 359         if (goal >= uspi->s_size)
 360                 goal = 0;
 361         if (goal == 0)
 362                 cgno = ufs_inotocg (inode->i_ino);
 363         else
 364                 cgno = ufs_dtog (goal);
 365
 366         /*
 367          * allocate new fragment
 368          */
 369         if (oldcount == 0) {
 370                 result = ufs_alloc_fragments (inode, cgno, goal, count, err);
 371                 if (result) {
 372                         *p = cpu_to_fs32(sb, result);
 373                         *err = 0;
 374                         UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
 375                         ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
 376                                         locked_page != NULL);
 377                 }
 378                 unlock_super(sb);
 379                 UFSD("EXIT, result %u\n", result);
 380                 return result;
 381         }
 382
 383         /*
 384          * resize block
 385          */
 386         result = ufs_add_fragments (inode, tmp, oldcount, newcount, err);
 387         if (result) {
 388                 *err = 0;
 389                 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
 390                 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
 391                                 locked_page != NULL);
 392                 unlock_super(sb);
 393                 UFSD("EXIT, result %u\n", result);
 394                 return result;
 395         }
 396
 397         /*
 398          * allocate new block and move data
 399          */
 400         switch (fs32_to_cpu(sb, usb1->fs_optim)) {
 401             case UFS_OPTSPACE:
 402                 request = newcount;
 403                 if (uspi->s_minfree < 5 || uspi->cs_total.cs_nffree
 404                     > uspi->s_dsize * uspi->s_minfree / (2 * 100))
 405                         break;
 406                 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
 407                 break;
 408             default:
 409                 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
 410
 411             case UFS_OPTTIME:
 412                 request = uspi->s_fpb;
 413                 if (uspi->cs_total.cs_nffree < uspi->s_dsize *
 414                     (uspi->s_minfree - 2) / 100)
 415                         break;
 416                 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
 417                 break;
 418         }
 419         result = ufs_alloc_fragments (inode, cgno, goal, request, err);
 420         if (result) {
 421                 ufs_change_blocknr(inode, fragment - oldcount, oldcount, tmp,
 422                                    result, locked_page);
 423
 424                 *p = cpu_to_fs32(sb, result);
 425                 *err = 0;
 426                 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
 427                 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
 428                                 locked_page != NULL);
 429                 unlock_super(sb);
 430                 if (newcount < request)
 431                         ufs_free_fragments (inode, result + newcount, request - newcount);
 432                 ufs_free_fragments (inode, tmp, oldcount);
 433                 UFSD("EXIT, result %u\n", result);
 434                 return result;
 435         }
 436
 437         unlock_super(sb);
 438         UFSD("EXIT (FAILED)\n");
 439         return 0;
 440 }
 441
 442 static unsigned
 443 ufs_add_fragments (struct inode * inode, unsigned fragment,
 444                    unsigned oldcount, unsigned newcount, int * err)
 445 {
 446         struct super_block * sb;
 447         struct ufs_sb_private_info * uspi;
 448         struct ufs_super_block_first * usb1;
 449         struct ufs_cg_private_info * ucpi;
 450         struct ufs_cylinder_group * ucg;
 451         unsigned cgno, fragno, fragoff, count, fragsize, i;
 452
 453         UFSD("ENTER, fragment %u, oldcount %u, newcount %u\n", fragment, oldcount, newcount);
 454
 455         sb = inode->i_sb;
 456         uspi = UFS_SB(sb)->s_uspi;
 457         usb1 = ubh_get_usb_first (uspi);
 458         count = newcount - oldcount;
 459
 460         cgno = ufs_dtog(fragment);
 461         if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
 462                 return 0;
 463         if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
 464                 return 0;
 465         ucpi = ufs_load_cylinder (sb, cgno);
 466         if (!ucpi)
 467                 return 0;
 468         ucg = ubh_get_ucg (UCPI_UBH(ucpi));
 469         if (!ufs_cg_chkmagic(sb, ucg)) {
 470                 ufs_panic (sb, "ufs_add_fragments",
 471                         "internal error, bad magic number on cg %u", cgno);
 472                 return 0;
 473         }
 474
 475         fragno = ufs_dtogd (fragment);
 476         fragoff = ufs_fragnum (fragno);
 477         for (i = oldcount; i < newcount; i++)
 478                 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
 479                         return 0;
 480         /*
 481          * Block can be extended
 482          */
 483         ucg->cg_time = cpu_to_fs32(sb, get_seconds());
 484         for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
 485                 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
 486                         break;
 487         fragsize = i - oldcount;
 488         if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
 489                 ufs_panic (sb, "ufs_add_fragments",
 490                         "internal error or corrupted bitmap on cg %u", cgno);
 491         fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
 492         if (fragsize != count)
 493                 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
 494         for (i = oldcount; i < newcount; i++)
 495                 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i);
 496         if(DQUOT_ALLOC_BLOCK(inode, count)) {
 497                 *err = -EDQUOT;
 498                 return 0;
 499         }
 500
 501         fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
 502         fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
 503         uspi->cs_total.cs_nffree -= count;
 504
 505         ubh_mark_buffer_dirty (USPI_UBH(uspi));
 506         ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
 507         if (sb->s_flags & MS_SYNCHRONOUS) {
 508                 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
 509                 ubh_wait_on_buffer (UCPI_UBH(ucpi));
 510         }
 511         sb->s_dirt = 1;
 512
 513         UFSD("EXIT, fragment %u\n", fragment);
 514
 515         return fragment;
 516 }
 517
 518 #define UFS_TEST_FREE_SPACE_CG \
 519         ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
 520         if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
 521                 goto cg_found; \
 522         for (k = count; k < uspi->s_fpb; k++) \
 523                 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
 524                         goto cg_found;
 525
 526 static unsigned ufs_alloc_fragments (struct inode * inode, unsigned cgno,
 527         unsigned goal, unsigned count, int * err)
 528 {
 529         struct super_block * sb;
 530         struct ufs_sb_private_info * uspi;
 531         struct ufs_super_block_first * usb1;
 532         struct ufs_cg_private_info * ucpi;
 533         struct ufs_cylinder_group * ucg;
 534         unsigned oldcg, i, j, k, result, allocsize;
 535
 536         UFSD("ENTER, ino %lu, cgno %u, goal %u, count %u\n", inode->i_ino, cgno, goal, count);
 537
 538         sb = inode->i_sb;
 539         uspi = UFS_SB(sb)->s_uspi;
 540         usb1 = ubh_get_usb_first(uspi);
 541         oldcg = cgno;
 542
 543         /*
 544          * 1. searching on preferred cylinder group
 545          */
 546         UFS_TEST_FREE_SPACE_CG
 547
 548         /*
 549          * 2. quadratic rehash
 550          */
 551         for (j = 1; j < uspi->s_ncg; j *= 2) {
 552                 cgno += j;
 553                 if (cgno >= uspi->s_ncg)
 554                         cgno -= uspi->s_ncg;
 555                 UFS_TEST_FREE_SPACE_CG
 556         }
 557
 558         /*
 559          * 3. brute force search
 560          * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
 561          */
 562         cgno = (oldcg + 1) % uspi->s_ncg;
 563         for (j = 2; j < uspi->s_ncg; j++) {
 564                 cgno++;
 565                 if (cgno >= uspi->s_ncg)
 566                         cgno = 0;
 567                 UFS_TEST_FREE_SPACE_CG
 568         }
 569
 570         UFSD("EXIT (FAILED)\n");
 571         return 0;
 572
 573 cg_found:
 574         ucpi = ufs_load_cylinder (sb, cgno);
 575         if (!ucpi)
 576                 return 0;
 577         ucg = ubh_get_ucg (UCPI_UBH(ucpi));
 578         if (!ufs_cg_chkmagic(sb, ucg))
 579                 ufs_panic (sb, "ufs_alloc_fragments",
 580                         "internal error, bad magic number on cg %u", cgno);
 581         ucg->cg_time = cpu_to_fs32(sb, get_seconds());
 582
 583         if (count == uspi->s_fpb) {
 584                 result = ufs_alloccg_block (inode, ucpi, goal, err);
 585                 if (result == (unsigned)-1)
 586                         return 0;
 587                 goto succed;
 588         }
 589
 590         for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
 591                 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
 592                         break;
 593
 594         if (allocsize == uspi->s_fpb) {
 595                 result = ufs_alloccg_block (inode, ucpi, goal, err);
 596                 if (result == (unsigned)-1)
 597                         return 0;
 598                 goal = ufs_dtogd (result);
 599                 for (i = count; i < uspi->s_fpb; i++)
 600                         ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, goal + i);
 601                 i = uspi->s_fpb - count;
 602                 DQUOT_FREE_BLOCK(inode, i);
 603
 604                 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
 605                 uspi->cs_total.cs_nffree += i;
 606                 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
 607                 fs32_add(sb, &ucg->cg_frsum[i], 1);
 608                 goto succed;
 609         }
 610
 611         result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
 612         if (result == (unsigned)-1)
 613                 return 0;
 614         if(DQUOT_ALLOC_BLOCK(inode, count)) {
 615                 *err = -EDQUOT;
 616                 return 0;
 617         }
 618         for (i = 0; i < count; i++)
 619                 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, result + i);
 620
 621         fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
 622         uspi->cs_total.cs_nffree -= count;
 623         fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
 624         fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
 625
 626         if (count != allocsize)
 627                 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
 628
 629 succed:
 630         ubh_mark_buffer_dirty (USPI_UBH(uspi));
 631         ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
 632         if (sb->s_flags & MS_SYNCHRONOUS) {
 633                 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
 634                 ubh_wait_on_buffer (UCPI_UBH(ucpi));
 635         }
 636         sb->s_dirt = 1;
 637
 638         result += cgno * uspi->s_fpg;
 639         UFSD("EXIT3, result %u\n", result);
 640         return result;
 641 }
 642
 643 static unsigned ufs_alloccg_block (struct inode * inode,
 644         struct ufs_cg_private_info * ucpi, unsigned goal, int * err)
 645 {
 646         struct super_block * sb;
 647         struct ufs_sb_private_info * uspi;
 648         struct ufs_super_block_first * usb1;
 649         struct ufs_cylinder_group * ucg;
 650         unsigned result, cylno, blkno;
 651
 652         UFSD("ENTER, goal %u\n", goal);
 653
 654         sb = inode->i_sb;
 655         uspi = UFS_SB(sb)->s_uspi;
 656         usb1 = ubh_get_usb_first(uspi);
 657         ucg = ubh_get_ucg(UCPI_UBH(ucpi));
 658
 659         if (goal == 0) {
 660                 goal = ucpi->c_rotor;
 661                 goto norot;
 662         }
 663         goal = ufs_blknum (goal);
 664         goal = ufs_dtogd (goal);
 665
 666         /*
 667          * If the requested block is available, use it.
 668          */
 669         if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, ufs_fragstoblks(goal))) {
 670                 result = goal;
 671                 goto gotit;
 672         }
 673
 674 norot:
 675         result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
 676         if (result == (unsigned)-1)
 677                 return (unsigned)-1;
 678         ucpi->c_rotor = result;
 679 gotit:
 680         blkno = ufs_fragstoblks(result);
 681         ubh_clrblock (UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
 682         if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
 683                 ufs_clusteracct (sb, ucpi, blkno, -1);
 684         if(DQUOT_ALLOC_BLOCK(inode, uspi->s_fpb)) {
 685                 *err = -EDQUOT;
 686                 return (unsigned)-1;
 687         }
 688
 689         fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
 690         uspi->cs_total.cs_nbfree--;
 691         fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
 692         cylno = ufs_cbtocylno(result);
 693         fs16_sub(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(result)), 1);
 694         fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
 695
 696         UFSD("EXIT, result %u\n", result);
 697
 698         return result;
 699 }
 700
 701 static unsigned ubh_scanc(struct ufs_sb_private_info *uspi,
 702                           struct ufs_buffer_head *ubh,
 703                           unsigned begin, unsigned size,
 704                           unsigned char *table, unsigned char mask)
 705 {
 706         unsigned rest, offset;
 707         unsigned char *cp;
 708
 709
 710         offset = begin & ~uspi->s_fmask;
 711         begin >>= uspi->s_fshift;
 712         for (;;) {
 713                 if ((offset + size) < uspi->s_fsize)
 714                         rest = size;
 715                 else
 716                         rest = uspi->s_fsize - offset;
 717                 size -= rest;
 718                 cp = ubh->bh[begin]->b_data + offset;
 719                 while ((table[*cp++] & mask) == 0 && --rest)
 720                         ;
 721                 if (rest || !size)
 722                         break;
 723                 begin++;
 724                 offset = 0;
 725         }
 726         return (size + rest);
 727 }
 728
 729 /*
 730  * Find a block of the specified size in the specified cylinder group.
 731  * @sp: pointer to super block
 732  * @ucpi: pointer to cylinder group info
 733  * @goal: near which block we want find new one
 734  * @count: specified size
 735  */
 736 static unsigned ufs_bitmap_search(struct super_block *sb,
 737                                   struct ufs_cg_private_info *ucpi,
 738                                   unsigned goal, unsigned count)
 739 {
 740         /*
 741          * Bit patterns for identifying fragments in the block map
 742          * used as ((map & mask_arr) == want_arr)
 743          */
 744         static const int mask_arr[9] = {
 745                 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
 746         };
 747         static const int want_arr[9] = {
 748                 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
 749         };
 750         struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi;
 751         struct ufs_super_block_first *usb1;
 752         struct ufs_cylinder_group *ucg;
 753         unsigned start, length, loc, result;
 754         unsigned pos, want, blockmap, mask, end;
 755
 756         UFSD("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count);
 757
 758         usb1 = ubh_get_usb_first (uspi);
 759         ucg = ubh_get_ucg(UCPI_UBH(ucpi));
 760
 761         if (goal)
 762                 start = ufs_dtogd(goal) >> 3;
 763         else
 764                 start = ucpi->c_frotor >> 3;
 765
 766         length = ((uspi->s_fpg + 7) >> 3) - start;
 767         loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length,
 768                 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
 769                 1 << (count - 1 + (uspi->s_fpb & 7)));
 770         if (loc == 0) {
 771                 length = start + 1;
 772                 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length,
 773                                 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb :
 774                                 ufs_fragtable_other,
 775                                 1 << (count - 1 + (uspi->s_fpb & 7)));
 776                 if (loc == 0) {
 777                         ufs_error(sb, "ufs_bitmap_search",
 778                                   "bitmap corrupted on cg %u, start %u,"
 779                                   " length %u, count %u, freeoff %u\n",
 780                                   ucpi->c_cgx, start, length, count,
 781                                   ucpi->c_freeoff);
 782                         return (unsigned)-1;
 783                 }
 784                 start = 0;
 785         }
 786         result = (start + length - loc) << 3;
 787         ucpi->c_frotor = result;
 788
 789         /*
 790          * found the byte in the map
 791          */
 792
 793         for (end = result + 8; result < end; result += uspi->s_fpb) {
 794                 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result);
 795                 blockmap <<= 1;
 796                 mask = mask_arr[count];
 797                 want = want_arr[count];
 798                 for (pos = 0; pos <= uspi->s_fpb - count; pos++) {
 799                         if ((blockmap & mask) == want) {
 800                                 UFSD("EXIT, result %u\n", result);
 801                                 return result + pos;
 802                         }
 803                         mask <<= 1;
 804                         want <<= 1;
 805                 }
 806         }
 807
 808         ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n",
 809                   ucpi->c_cgx);
 810         UFSD("EXIT (FAILED)\n");
 811         return (unsigned)-1;
 812 }
 813
 814 static void ufs_clusteracct(struct super_block * sb,
 815         struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
 816 {
 817         struct ufs_sb_private_info * uspi;
 818         int i, start, end, forw, back;
 819
 820         uspi = UFS_SB(sb)->s_uspi;
 821         if (uspi->s_contigsumsize <= 0)
 822                 return;
 823
 824         if (cnt > 0)
 825                 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
 826         else
 827                 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
 828
 829         /*
 830          * Find the size of the cluster going forward.
 831          */
 832         start = blkno + 1;
 833         end = start + uspi->s_contigsumsize;
 834         if ( end >= ucpi->c_nclusterblks)
 835                 end = ucpi->c_nclusterblks;
 836         i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start);
 837         if (i > end)
 838                 i = end;
 839         forw = i - start;
 840
 841         /*
 842          * Find the size of the cluster going backward.
 843          */
 844         start = blkno - 1;
 845         end = start - uspi->s_contigsumsize;
 846         if (end < 0 )
 847                 end = -1;
 848         i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end);
 849         if ( i < end)
 850                 i = end;
 851         back = start - i;
 852
 853         /*
 854          * Account for old cluster and the possibly new forward and
 855          * back clusters.
 856          */
 857         i = back + forw + 1;
 858         if (i > uspi->s_contigsumsize)
 859                 i = uspi->s_contigsumsize;
 860         fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt);
 861         if (back > 0)
 862                 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt);
 863         if (forw > 0)
 864                 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt);
 865 }
 866
 867
 868 static unsigned char ufs_fragtable_8fpb[] = {
 869         0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
 870         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
 871         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 872         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
 873         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 874         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 875         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
 876         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
 877         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 878         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 879         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 880         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
 881         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
 882         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
 883         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
 884         0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
 885 };
 886
 887 static unsigned char ufs_fragtable_other[] = {
 888         0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
 889         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 890         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 891         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
 892         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 893         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 894         0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
 895         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
 896         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 897         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 898         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 899         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
 900         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
 901         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
 902         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
 903         0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
 904 };