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