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