fs/ufs/balloc.c

   1 /*
   2  *  linux/fs/ufs/balloc.c
   3  *
   4  * Copyright (C) 1998
   5  * Daniel Pirkl <[email protected]>
   6  * Charles University, Faculty of Mathematics and Physics
   7  *
   8  * UFS2 write support Evgeniy Dushistov <[email protected]>, 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         switch (fs32_to_cpu(sb, usb1->fs_optim)) {
 459             case UFS_OPTSPACE:
 460                 request = newcount;
 461                 if (uspi->s_minfree < 5 || uspi->cs_total.cs_nffree
 462                     > uspi->s_dsize * uspi->s_minfree / (2 * 100))
 463                         break;
 464                 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
 465                 break;
 466             default:
 467                 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
 468
 469             case UFS_OPTTIME:
 470                 request = uspi->s_fpb;
 471                 if (uspi->cs_total.cs_nffree < uspi->s_dsize *
 472                     (uspi->s_minfree - 2) / 100)
 473                         break;
 474                 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
 475                 break;
 476         }
 477         result = ufs_alloc_fragments (inode, cgno, goal, request, err);
 478         if (result) {
 479                 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
 480                                 locked_page != NULL);
 481                 mutex_unlock(&UFS_SB(sb)->s_lock);
 482                 ufs_change_blocknr(inode, fragment - oldcount, oldcount,
 483                                    uspi->s_sbbase + tmp,
 484                                    uspi->s_sbbase + result, locked_page);
 485                 *err = 0;
 486                 write_seqlock(&UFS_I(inode)->meta_lock);
 487                 ufs_cpu_to_data_ptr(sb, p, result);
 488                 UFS_I(inode)->i_lastfrag = max(UFS_I(inode)->i_lastfrag,
 489                                                 fragment + count);
 490                 write_sequnlock(&UFS_I(inode)->meta_lock);
 491                 if (newcount < request)
 492                         ufs_free_fragments (inode, result + newcount, request - newcount);
 493                 ufs_free_fragments (inode, tmp, oldcount);
 494                 UFSD("EXIT, result %llu\n", (unsigned long long)result);
 495                 return result;
 496         }
 497
 498         mutex_unlock(&UFS_SB(sb)->s_lock);
 499         UFSD("EXIT (FAILED)\n");
 500         return 0;
 501 }
 502
 503 static bool try_add_frags(struct inode *inode, unsigned frags)
 504 {
 505         unsigned size = frags * i_blocksize(inode);
 506         spin_lock(&inode->i_lock);
 507         __inode_add_bytes(inode, size);
 508         if (unlikely((u32)inode->i_blocks != inode->i_blocks)) {
 509                 __inode_sub_bytes(inode, size);
 510                 spin_unlock(&inode->i_lock);
 511                 return false;
 512         }
 513         spin_unlock(&inode->i_lock);
 514         return true;
 515 }
 516
 517 static u64 ufs_add_fragments(struct inode *inode, u64 fragment,
 518                              unsigned oldcount, unsigned newcount)
 519 {
 520         struct super_block * sb;
 521         struct ufs_sb_private_info * uspi;
 522         struct ufs_cg_private_info * ucpi;
 523         struct ufs_cylinder_group * ucg;
 524         unsigned cgno, fragno, fragoff, count, fragsize, i;
 525
 526         UFSD("ENTER, fragment %llu, oldcount %u, newcount %u\n",
 527              (unsigned long long)fragment, oldcount, newcount);
 528
 529         sb = inode->i_sb;
 530         uspi = UFS_SB(sb)->s_uspi;
 531         count = newcount - oldcount;
 532
 533         cgno = ufs_dtog(uspi, fragment);
 534         if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
 535                 return 0;
 536         if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
 537                 return 0;
 538         ucpi = ufs_load_cylinder (sb, cgno);
 539         if (!ucpi)
 540                 return 0;
 541         ucg = ubh_get_ucg (UCPI_UBH(ucpi));
 542         if (!ufs_cg_chkmagic(sb, ucg)) {
 543                 ufs_panic (sb, "ufs_add_fragments",
 544                         "internal error, bad magic number on cg %u", cgno);
 545                 return 0;
 546         }
 547
 548         fragno = ufs_dtogd(uspi, fragment);
 549         fragoff = ufs_fragnum (fragno);
 550         for (i = oldcount; i < newcount; i++)
 551                 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
 552                         return 0;
 553
 554         if (!try_add_frags(inode, count))
 555                 return 0;
 556         /*
 557          * Block can be extended
 558          */
 559         ucg->cg_time = cpu_to_fs32(sb, get_seconds());
 560         for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
 561                 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
 562                         break;
 563         fragsize = i - oldcount;
 564         if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
 565                 ufs_panic (sb, "ufs_add_fragments",
 566                         "internal error or corrupted bitmap on cg %u", cgno);
 567         fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
 568         if (fragsize != count)
 569                 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
 570         for (i = oldcount; i < newcount; i++)
 571                 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i);
 572
 573         fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
 574         fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
 575         uspi->cs_total.cs_nffree -= count;
 576
 577         ubh_mark_buffer_dirty (USPI_UBH(uspi));
 578         ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
 579         if (sb->s_flags & MS_SYNCHRONOUS)
 580                 ubh_sync_block(UCPI_UBH(ucpi));
 581         ufs_mark_sb_dirty(sb);
 582
 583         UFSD("EXIT, fragment %llu\n", (unsigned long long)fragment);
 584
 585         return fragment;
 586 }
 587
 588 #define UFS_TEST_FREE_SPACE_CG \
 589         ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
 590         if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
 591                 goto cg_found; \
 592         for (k = count; k < uspi->s_fpb; k++) \
 593                 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
 594                         goto cg_found;
 595
 596 static u64 ufs_alloc_fragments(struct inode *inode, unsigned cgno,
 597                                u64 goal, unsigned count, int *err)
 598 {
 599         struct super_block * sb;
 600         struct ufs_sb_private_info * uspi;
 601         struct ufs_cg_private_info * ucpi;
 602         struct ufs_cylinder_group * ucg;
 603         unsigned oldcg, i, j, k, allocsize;
 604         u64 result;
 605
 606         UFSD("ENTER, ino %lu, cgno %u, goal %llu, count %u\n",
 607              inode->i_ino, cgno, (unsigned long long)goal, count);
 608
 609         sb = inode->i_sb;
 610         uspi = UFS_SB(sb)->s_uspi;
 611         oldcg = cgno;
 612
 613         /*
 614          * 1. searching on preferred cylinder group
 615          */
 616         UFS_TEST_FREE_SPACE_CG
 617
 618         /*
 619          * 2. quadratic rehash
 620          */
 621         for (j = 1; j < uspi->s_ncg; j *= 2) {
 622                 cgno += j;
 623                 if (cgno >= uspi->s_ncg)
 624                         cgno -= uspi->s_ncg;
 625                 UFS_TEST_FREE_SPACE_CG
 626         }
 627
 628         /*
 629          * 3. brute force search
 630          * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
 631          */
 632         cgno = (oldcg + 1) % uspi->s_ncg;
 633         for (j = 2; j < uspi->s_ncg; j++) {
 634                 cgno++;
 635                 if (cgno >= uspi->s_ncg)
 636                         cgno = 0;
 637                 UFS_TEST_FREE_SPACE_CG
 638         }
 639
 640         UFSD("EXIT (FAILED)\n");
 641         return 0;
 642
 643 cg_found:
 644         ucpi = ufs_load_cylinder (sb, cgno);
 645         if (!ucpi)
 646                 return 0;
 647         ucg = ubh_get_ucg (UCPI_UBH(ucpi));
 648         if (!ufs_cg_chkmagic(sb, ucg))
 649                 ufs_panic (sb, "ufs_alloc_fragments",
 650                         "internal error, bad magic number on cg %u", cgno);
 651         ucg->cg_time = cpu_to_fs32(sb, get_seconds());
 652
 653         if (count == uspi->s_fpb) {
 654                 result = ufs_alloccg_block (inode, ucpi, goal, err);
 655                 if (result == INVBLOCK)
 656                         return 0;
 657                 goto succed;
 658         }
 659
 660         for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
 661                 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
 662                         break;
 663
 664         if (allocsize == uspi->s_fpb) {
 665                 result = ufs_alloccg_block (inode, ucpi, goal, err);
 666                 if (result == INVBLOCK)
 667                         return 0;
 668                 goal = ufs_dtogd(uspi, result);
 669                 for (i = count; i < uspi->s_fpb; i++)
 670                         ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, goal + i);
 671                 i = uspi->s_fpb - count;
 672
 673                 inode_sub_bytes(inode, i << uspi->s_fshift);
 674                 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
 675                 uspi->cs_total.cs_nffree += i;
 676                 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
 677                 fs32_add(sb, &ucg->cg_frsum[i], 1);
 678                 goto succed;
 679         }
 680
 681         result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
 682         if (result == INVBLOCK)
 683                 return 0;
 684         if (!try_add_frags(inode, count))
 685                 return 0;
 686         for (i = 0; i < count; i++)
 687                 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, result + i);
 688
 689         fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
 690         uspi->cs_total.cs_nffree -= count;
 691         fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
 692         fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
 693
 694         if (count != allocsize)
 695                 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
 696
 697 succed:
 698         ubh_mark_buffer_dirty (USPI_UBH(uspi));
 699         ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
 700         if (sb->s_flags & MS_SYNCHRONOUS)
 701                 ubh_sync_block(UCPI_UBH(ucpi));
 702         ufs_mark_sb_dirty(sb);
 703
 704         result += cgno * uspi->s_fpg;
 705         UFSD("EXIT3, result %llu\n", (unsigned long long)result);
 706         return result;
 707 }
 708
 709 static u64 ufs_alloccg_block(struct inode *inode,
 710                              struct ufs_cg_private_info *ucpi,
 711                              u64 goal, int *err)
 712 {
 713         struct super_block * sb;
 714         struct ufs_sb_private_info * uspi;
 715         struct ufs_cylinder_group * ucg;
 716         u64 result, blkno;
 717
 718         UFSD("ENTER, goal %llu\n", (unsigned long long)goal);
 719
 720         sb = inode->i_sb;
 721         uspi = UFS_SB(sb)->s_uspi;
 722         ucg = ubh_get_ucg(UCPI_UBH(ucpi));
 723
 724         if (goal == 0) {
 725                 goal = ucpi->c_rotor;
 726                 goto norot;
 727         }
 728         goal = ufs_blknum (goal);
 729         goal = ufs_dtogd(uspi, goal);
 730
 731         /*
 732          * If the requested block is available, use it.
 733          */
 734         if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, ufs_fragstoblks(goal))) {
 735                 result = goal;
 736                 goto gotit;
 737         }
 738
 739 norot:
 740         result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
 741         if (result == INVBLOCK)
 742                 return INVBLOCK;
 743         ucpi->c_rotor = result;
 744 gotit:
 745         if (!try_add_frags(inode, uspi->s_fpb))
 746                 return 0;
 747         blkno = ufs_fragstoblks(result);
 748         ubh_clrblock (UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
 749         if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
 750                 ufs_clusteracct (sb, ucpi, blkno, -1);
 751
 752         fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
 753         uspi->cs_total.cs_nbfree--;
 754         fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
 755
 756         if (uspi->fs_magic != UFS2_MAGIC) {
 757                 unsigned cylno = ufs_cbtocylno((unsigned)result);
 758
 759                 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno,
 760                                           ufs_cbtorpos((unsigned)result)), 1);
 761                 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
 762         }
 763
 764         UFSD("EXIT, result %llu\n", (unsigned long long)result);
 765
 766         return result;
 767 }
 768
 769 static unsigned ubh_scanc(struct ufs_sb_private_info *uspi,
 770                           struct ufs_buffer_head *ubh,
 771                           unsigned begin, unsigned size,
 772                           unsigned char *table, unsigned char mask)
 773 {
 774         unsigned rest, offset;
 775         unsigned char *cp;
 776
 777
 778         offset = begin & ~uspi->s_fmask;
 779         begin >>= uspi->s_fshift;
 780         for (;;) {
 781                 if ((offset + size) < uspi->s_fsize)
 782                         rest = size;
 783                 else
 784                         rest = uspi->s_fsize - offset;
 785                 size -= rest;
 786                 cp = ubh->bh[begin]->b_data + offset;
 787                 while ((table[*cp++] & mask) == 0 && --rest)
 788                         ;
 789                 if (rest || !size)
 790                         break;
 791                 begin++;
 792                 offset = 0;
 793         }
 794         return (size + rest);
 795 }
 796
 797 /*
 798  * Find a block of the specified size in the specified cylinder group.
 799  * @sp: pointer to super block
 800  * @ucpi: pointer to cylinder group info
 801  * @goal: near which block we want find new one
 802  * @count: specified size
 803  */
 804 static u64 ufs_bitmap_search(struct super_block *sb,
 805                              struct ufs_cg_private_info *ucpi,
 806                              u64 goal, unsigned count)
 807 {
 808         /*
 809          * Bit patterns for identifying fragments in the block map
 810          * used as ((map & mask_arr) == want_arr)
 811          */
 812         static const int mask_arr[9] = {
 813                 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
 814         };
 815         static const int want_arr[9] = {
 816                 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
 817         };
 818         struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi;
 819         unsigned start, length, loc;
 820         unsigned pos, want, blockmap, mask, end;
 821         u64 result;
 822
 823         UFSD("ENTER, cg %u, goal %llu, count %u\n", ucpi->c_cgx,
 824              (unsigned long long)goal, count);
 825
 826         if (goal)
 827                 start = ufs_dtogd(uspi, goal) >> 3;
 828         else
 829                 start = ucpi->c_frotor >> 3;
 830
 831         length = ((uspi->s_fpg + 7) >> 3) - start;
 832         loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length,
 833                 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
 834                 1 << (count - 1 + (uspi->s_fpb & 7)));
 835         if (loc == 0) {
 836                 length = start + 1;
 837                 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length,
 838                                 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb :
 839                                 ufs_fragtable_other,
 840                                 1 << (count - 1 + (uspi->s_fpb & 7)));
 841                 if (loc == 0) {
 842                         ufs_error(sb, "ufs_bitmap_search",
 843                                   "bitmap corrupted on cg %u, start %u,"
 844                                   " length %u, count %u, freeoff %u\n",
 845                                   ucpi->c_cgx, start, length, count,
 846                                   ucpi->c_freeoff);
 847                         return INVBLOCK;
 848                 }
 849                 start = 0;
 850         }
 851         result = (start + length - loc) << 3;
 852         ucpi->c_frotor = result;
 853
 854         /*
 855          * found the byte in the map
 856          */
 857
 858         for (end = result + 8; result < end; result += uspi->s_fpb) {
 859                 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result);
 860                 blockmap <<= 1;
 861                 mask = mask_arr[count];
 862                 want = want_arr[count];
 863                 for (pos = 0; pos <= uspi->s_fpb - count; pos++) {
 864                         if ((blockmap & mask) == want) {
 865                                 UFSD("EXIT, result %llu\n",
 866                                      (unsigned long long)result);
 867                                 return result + pos;
 868                         }
 869                         mask <<= 1;
 870                         want <<= 1;
 871                 }
 872         }
 873
 874         ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n",
 875                   ucpi->c_cgx);
 876         UFSD("EXIT (FAILED)\n");
 877         return INVBLOCK;
 878 }
 879
 880 static void ufs_clusteracct(struct super_block * sb,
 881         struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
 882 {
 883         struct ufs_sb_private_info * uspi;
 884         int i, start, end, forw, back;
 885
 886         uspi = UFS_SB(sb)->s_uspi;
 887         if (uspi->s_contigsumsize <= 0)
 888                 return;
 889
 890         if (cnt > 0)
 891                 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
 892         else
 893                 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
 894
 895         /*
 896          * Find the size of the cluster going forward.
 897          */
 898         start = blkno + 1;
 899         end = start + uspi->s_contigsumsize;
 900         if ( end >= ucpi->c_nclusterblks)
 901                 end = ucpi->c_nclusterblks;
 902         i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start);
 903         if (i > end)
 904                 i = end;
 905         forw = i - start;
 906
 907         /*
 908          * Find the size of the cluster going backward.
 909          */
 910         start = blkno - 1;
 911         end = start - uspi->s_contigsumsize;
 912         if (end < 0 )
 913                 end = -1;
 914         i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end);
 915         if ( i < end)
 916                 i = end;
 917         back = start - i;
 918
 919         /*
 920          * Account for old cluster and the possibly new forward and
 921          * back clusters.
 922          */
 923         i = back + forw + 1;
 924         if (i > uspi->s_contigsumsize)
 925                 i = uspi->s_contigsumsize;
 926         fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt);
 927         if (back > 0)
 928                 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt);
 929         if (forw > 0)
 930                 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt);
 931 }
 932
 933
 934 static unsigned char ufs_fragtable_8fpb[] = {
 935         0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
 936         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
 937         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 938         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
 939         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 940         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 941         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
 942         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
 943         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 944         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
 945         0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
 946         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
 947         0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
 948         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
 949         0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
 950         0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
 951 };
 952
 953 static unsigned char ufs_fragtable_other[] = {
 954         0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
 955         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 956         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 957         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
 958         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 959         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 960         0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
 961         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
 962         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 963         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 964         0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
 965         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
 966         0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
 967         0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
 968         0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
 969         0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
 970 };