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