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