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