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 #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 ubh_scanc(struct ufs_sb_private_info *uspi,
 730                           struct ufs_buffer_head *ubh,
 731                           unsigned begin, unsigned size,
 732                           unsigned char *table, unsigned char mask)
 733 {
 734         unsigned rest, offset;
 735         unsigned char *cp;
 736
 737
 738         offset = begin & ~uspi->s_fmask;
 739         begin >>= uspi->s_fshift;
 740         for (;;) {
 741                 if ((offset + size) < uspi->s_fsize)
 742                         rest = size;
 743                 else
 744                         rest = uspi->s_fsize - offset;
 745                 size -= rest;
 746                 cp = ubh->bh[begin]->b_data + offset;
 747                 while ((table[*cp++] & mask) == 0 && --rest)
 748                         ;
 749                 if (rest || !size)
 750                         break;
 751                 begin++;
 752                 offset = 0;
 753         }
 754         return (size + rest);
 755 }
 756
 757 /*
 758  * Find a block of the specified size in the specified cylinder group.
 759  * @sp: pointer to super block
 760  * @ucpi: pointer to cylinder group info
 761  * @goal: near which block we want find new one
 762  * @count: specified size
 763  */
 764 static unsigned ufs_bitmap_search(struct super_block *sb,
 765                                   struct ufs_cg_private_info *ucpi,
 766                                   unsigned goal, unsigned count)
 767 {
 768         /*
 769          * Bit patterns for identifying fragments in the block map
 770          * used as ((map & mask_arr) == want_arr)
 771          */
 772         static const int mask_arr[9] = {
 773                 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
 774         };
 775         static const int want_arr[9] = {
 776                 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
 777         };
 778         struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi;
 779         struct ufs_super_block_first *usb1;
 780         struct ufs_cylinder_group *ucg;
 781         unsigned start, length, loc, result;
 782         unsigned pos, want, blockmap, mask, end;
 783
 784         UFSD(("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count));
 785
 786         usb1 = ubh_get_usb_first (uspi);
 787         ucg = ubh_get_ucg(UCPI_UBH(ucpi));
 788
 789         if (goal)
 790                 start = ufs_dtogd(goal) >> 3;
 791         else
 792                 start = ucpi->c_frotor >> 3;
 793
 794         length = ((uspi->s_fpg + 7) >> 3) - start;
 795         loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length,
 796                 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
 797                 1 << (count - 1 + (uspi->s_fpb & 7)));
 798         if (loc == 0) {
 799                 length = start + 1;
 800                 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length,
 801                                 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb :
 802                                 ufs_fragtable_other,
 803                                 1 << (count - 1 + (uspi->s_fpb & 7)));
 804                 if (loc == 0) {
 805                         ufs_error(sb, "ufs_bitmap_search",
 806                                   "bitmap corrupted on cg %u, start %u,"
 807                                   " length %u, count %u, freeoff %u\n",
 808                                   ucpi->c_cgx, start, length, count,
 809                                   ucpi->c_freeoff);
 810                         return (unsigned)-1;
 811                 }
 812                 start = 0;
 813         }
 814         result = (start + length - loc) << 3;
 815         ucpi->c_frotor = result;
 816
 817         /*
 818          * found the byte in the map
 819          */
 820
 821         for (end = result + 8; result < end; result += uspi->s_fpb) {
 822                 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result);
 823                 blockmap <<= 1;
 824                 mask = mask_arr[count];
 825                 want = want_arr[count];
 826                 for (pos = 0; pos <= uspi->s_fpb - count; pos++) {
 827                         if ((blockmap & mask) == want) {
 828                                 UFSD(("EXIT, result %u\n", result));
 829                                 return result + pos;
 830                         }
 831                         mask <<= 1;
 832                         want <<= 1;
 833                 }
 834         }
 835
 836         ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n",
 837                   ucpi->c_cgx);
 838         UFSD(("EXIT (FAILED)\n"));
 839         return (unsigned)-1;
 840 }
 841
 842 static void ufs_clusteracct(struct super_block * sb,
 843         struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
 844 {
 845         struct ufs_sb_private_info * uspi;
 846         int i, start, end, forw, back;
 847
 848         uspi = UFS_SB(sb)->s_uspi;
 849         if (uspi->s_contigsumsize <= 0)
 850                 return;
 851
 852         if (cnt > 0)
 853                 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
 854         else
 855                 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
 856
 857         /*
 858          * Find the size of the cluster going forward.
 859          */
 860         start = blkno + 1;
 861         end = start + uspi->s_contigsumsize;
 862         if ( end >= ucpi->c_nclusterblks)
 863                 end = ucpi->c_nclusterblks;
 864         i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start);
 865         if (i > end)
 866                 i = end;
 867         forw = i - start;
 868
 869         /*
 870          * Find the size of the cluster going backward.
 871          */
 872         start = blkno - 1;
 873         end = start - uspi->s_contigsumsize;
 874         if (end < 0 )
 875                 end = -1;
 876         i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end);
 877         if ( i < end)
 878                 i = end;
 879         back = start - i;
 880
 881         /*
 882          * Account for old cluster and the possibly new forward and
 883          * back clusters.
 884          */
 885         i = back + forw + 1;
 886         if (i > uspi->s_contigsumsize)
 887                 i = uspi->s_contigsumsize;
 888         fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt);
 889         if (back > 0)
 890                 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt);
 891         if (forw > 0)
 892                 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt);
 893 }
 894
 895
 896 static unsigned char ufs_fragtable_8fpb[] = {
 897         0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
 898         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
 899         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 900         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
 901         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 902         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 903         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
 904         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
 905         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 906         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 907         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 908         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
 909         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
 910         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
 911         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
 912         0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
 913 };
 914
 915 static unsigned char ufs_fragtable_other[] = {
 916         0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
 917         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 918         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 919         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
 920         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 921         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 922         0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
 923         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
 924         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 925         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 926         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 927         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
 928         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
 929         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
 930         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
 931         0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
 932 };