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