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