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 unsigned ufs_new_fragments(struct inode * inode, __fs32 * p, unsigned fragment, 279 unsigned goal, unsigned count, int * err, struct page *locked_page) 280 { 281 struct super_block * sb; 282 struct ufs_sb_private_info * uspi; 283 struct ufs_super_block_first * usb1; 284 unsigned cgno, oldcount, newcount, tmp, request, result; 285 286 UFSD("ENTER, ino %lu, fragment %u, goal %u, count %u\n", inode->i_ino, fragment, goal, count); 287 288 sb = inode->i_sb; 289 uspi = UFS_SB(sb)->s_uspi; 290 usb1 = ubh_get_usb_first(uspi); 291 *err = -ENOSPC; 292 293 lock_super (sb); 294 295 tmp = fs32_to_cpu(sb, *p); 296 if (count + ufs_fragnum(fragment) > uspi->s_fpb) { 297 ufs_warning (sb, "ufs_new_fragments", "internal warning" 298 " fragment %u, count %u", fragment, count); 299 count = uspi->s_fpb - ufs_fragnum(fragment); 300 } 301 oldcount = ufs_fragnum (fragment); 302 newcount = oldcount + count; 303 304 /* 305 * Somebody else has just allocated our fragments 306 */ 307 if (oldcount) { 308 if (!tmp) { 309 ufs_error (sb, "ufs_new_fragments", "internal error, " 310 "fragment %u, tmp %u\n", fragment, tmp); 311 unlock_super (sb); 312 return (unsigned)-1; 313 } 314 if (fragment < UFS_I(inode)->i_lastfrag) { 315 UFSD("EXIT (ALREADY ALLOCATED)\n"); 316 unlock_super (sb); 317 return 0; 318 } 319 } 320 else { 321 if (tmp) { 322 UFSD("EXIT (ALREADY ALLOCATED)\n"); 323 unlock_super(sb); 324 return 0; 325 } 326 } 327 328 /* 329 * There is not enough space for user on the device 330 */ 331 if (!capable(CAP_SYS_RESOURCE) && ufs_freespace(uspi, UFS_MINFREE) <= 0) { 332 unlock_super (sb); 333 UFSD("EXIT (FAILED)\n"); 334 return 0; 335 } 336 337 if (goal >= uspi->s_size) 338 goal = 0; 339 if (goal == 0) 340 cgno = ufs_inotocg (inode->i_ino); 341 else 342 cgno = ufs_dtog (goal); 343 344 /* 345 * allocate new fragment 346 */ 347 if (oldcount == 0) { 348 result = ufs_alloc_fragments (inode, cgno, goal, count, err); 349 if (result) { 350 *p = cpu_to_fs32(sb, result); 351 *err = 0; 352 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count); 353 } 354 unlock_super(sb); 355 UFSD("EXIT, result %u\n", result); 356 return result; 357 } 358 359 /* 360 * resize block 361 */ 362 result = ufs_add_fragments (inode, tmp, oldcount, newcount, err); 363 if (result) { 364 *err = 0; 365 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count); 366 unlock_super(sb); 367 UFSD("EXIT, result %u\n", result); 368 return result; 369 } 370 371 /* 372 * allocate new block and move data 373 */ 374 switch (fs32_to_cpu(sb, usb1->fs_optim)) { 375 case UFS_OPTSPACE: 376 request = newcount; 377 if (uspi->s_minfree < 5 || uspi->cs_total.cs_nffree 378 > uspi->s_dsize * uspi->s_minfree / (2 * 100)) 379 break; 380 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME); 381 break; 382 default: 383 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME); 384 385 case UFS_OPTTIME: 386 request = uspi->s_fpb; 387 if (uspi->cs_total.cs_nffree < uspi->s_dsize * 388 (uspi->s_minfree - 2) / 100) 389 break; 390 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME); 391 break; 392 } 393 result = ufs_alloc_fragments (inode, cgno, goal, request, err); 394 if (result) { 395 ufs_change_blocknr(inode, fragment - oldcount, oldcount, tmp, 396 result, locked_page); 397 398 *p = cpu_to_fs32(sb, result); 399 *err = 0; 400 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count); 401 unlock_super(sb); 402 if (newcount < request) 403 ufs_free_fragments (inode, result + newcount, request - newcount); 404 ufs_free_fragments (inode, tmp, oldcount); 405 UFSD("EXIT, result %u\n", result); 406 return result; 407 } 408 409 unlock_super(sb); 410 UFSD("EXIT (FAILED)\n"); 411 return 0; 412 } 413 414 static unsigned 415 ufs_add_fragments (struct inode * inode, unsigned fragment, 416 unsigned oldcount, unsigned newcount, int * err) 417 { 418 struct super_block * sb; 419 struct ufs_sb_private_info * uspi; 420 struct ufs_super_block_first * usb1; 421 struct ufs_cg_private_info * ucpi; 422 struct ufs_cylinder_group * ucg; 423 unsigned cgno, fragno, fragoff, count, fragsize, i; 424 425 UFSD("ENTER, fragment %u, oldcount %u, newcount %u\n", fragment, oldcount, newcount); 426 427 sb = inode->i_sb; 428 uspi = UFS_SB(sb)->s_uspi; 429 usb1 = ubh_get_usb_first (uspi); 430 count = newcount - oldcount; 431 432 cgno = ufs_dtog(fragment); 433 if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count) 434 return 0; 435 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb) 436 return 0; 437 ucpi = ufs_load_cylinder (sb, cgno); 438 if (!ucpi) 439 return 0; 440 ucg = ubh_get_ucg (UCPI_UBH(ucpi)); 441 if (!ufs_cg_chkmagic(sb, ucg)) { 442 ufs_panic (sb, "ufs_add_fragments", 443 "internal error, bad magic number on cg %u", cgno); 444 return 0; 445 } 446 447 fragno = ufs_dtogd (fragment); 448 fragoff = ufs_fragnum (fragno); 449 for (i = oldcount; i < newcount; i++) 450 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i)) 451 return 0; 452 /* 453 * Block can be extended 454 */ 455 ucg->cg_time = cpu_to_fs32(sb, get_seconds()); 456 for (i = newcount; i < (uspi->s_fpb - fragoff); i++) 457 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i)) 458 break; 459 fragsize = i - oldcount; 460 if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize])) 461 ufs_panic (sb, "ufs_add_fragments", 462 "internal error or corrupted bitmap on cg %u", cgno); 463 fs32_sub(sb, &ucg->cg_frsum[fragsize], 1); 464 if (fragsize != count) 465 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1); 466 for (i = oldcount; i < newcount; i++) 467 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i); 468 if(DQUOT_ALLOC_BLOCK(inode, count)) { 469 *err = -EDQUOT; 470 return 0; 471 } 472 473 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count); 474 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count); 475 uspi->cs_total.cs_nffree -= count; 476 477 ubh_mark_buffer_dirty (USPI_UBH(uspi)); 478 ubh_mark_buffer_dirty (UCPI_UBH(ucpi)); 479 if (sb->s_flags & MS_SYNCHRONOUS) { 480 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi)); 481 ubh_wait_on_buffer (UCPI_UBH(ucpi)); 482 } 483 sb->s_dirt = 1; 484 485 UFSD("EXIT, fragment %u\n", fragment); 486 487 return fragment; 488 } 489 490 #define UFS_TEST_FREE_SPACE_CG \ 491 ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \ 492 if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \ 493 goto cg_found; \ 494 for (k = count; k < uspi->s_fpb; k++) \ 495 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \ 496 goto cg_found; 497 498 static unsigned ufs_alloc_fragments (struct inode * inode, unsigned cgno, 499 unsigned goal, unsigned count, int * err) 500 { 501 struct super_block * sb; 502 struct ufs_sb_private_info * uspi; 503 struct ufs_super_block_first * usb1; 504 struct ufs_cg_private_info * ucpi; 505 struct ufs_cylinder_group * ucg; 506 unsigned oldcg, i, j, k, result, allocsize; 507 508 UFSD("ENTER, ino %lu, cgno %u, goal %u, count %u\n", inode->i_ino, cgno, goal, count); 509 510 sb = inode->i_sb; 511 uspi = UFS_SB(sb)->s_uspi; 512 usb1 = ubh_get_usb_first(uspi); 513 oldcg = cgno; 514 515 /* 516 * 1. searching on preferred cylinder group 517 */ 518 UFS_TEST_FREE_SPACE_CG 519 520 /* 521 * 2. quadratic rehash 522 */ 523 for (j = 1; j < uspi->s_ncg; j *= 2) { 524 cgno += j; 525 if (cgno >= uspi->s_ncg) 526 cgno -= uspi->s_ncg; 527 UFS_TEST_FREE_SPACE_CG 528 } 529 530 /* 531 * 3. brute force search 532 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step ) 533 */ 534 cgno = (oldcg + 1) % uspi->s_ncg; 535 for (j = 2; j < uspi->s_ncg; j++) { 536 cgno++; 537 if (cgno >= uspi->s_ncg) 538 cgno = 0; 539 UFS_TEST_FREE_SPACE_CG 540 } 541 542 UFSD("EXIT (FAILED)\n"); 543 return 0; 544 545 cg_found: 546 ucpi = ufs_load_cylinder (sb, cgno); 547 if (!ucpi) 548 return 0; 549 ucg = ubh_get_ucg (UCPI_UBH(ucpi)); 550 if (!ufs_cg_chkmagic(sb, ucg)) 551 ufs_panic (sb, "ufs_alloc_fragments", 552 "internal error, bad magic number on cg %u", cgno); 553 ucg->cg_time = cpu_to_fs32(sb, get_seconds()); 554 555 if (count == uspi->s_fpb) { 556 result = ufs_alloccg_block (inode, ucpi, goal, err); 557 if (result == (unsigned)-1) 558 return 0; 559 goto succed; 560 } 561 562 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++) 563 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0) 564 break; 565 566 if (allocsize == uspi->s_fpb) { 567 result = ufs_alloccg_block (inode, ucpi, goal, err); 568 if (result == (unsigned)-1) 569 return 0; 570 goal = ufs_dtogd (result); 571 for (i = count; i < uspi->s_fpb; i++) 572 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, goal + i); 573 i = uspi->s_fpb - count; 574 DQUOT_FREE_BLOCK(inode, i); 575 576 fs32_add(sb, &ucg->cg_cs.cs_nffree, i); 577 uspi->cs_total.cs_nffree += i; 578 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i); 579 fs32_add(sb, &ucg->cg_frsum[i], 1); 580 goto succed; 581 } 582 583 result = ufs_bitmap_search (sb, ucpi, goal, allocsize); 584 if (result == (unsigned)-1) 585 return 0; 586 if(DQUOT_ALLOC_BLOCK(inode, count)) { 587 *err = -EDQUOT; 588 return 0; 589 } 590 for (i = 0; i < count; i++) 591 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, result + i); 592 593 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count); 594 uspi->cs_total.cs_nffree -= count; 595 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count); 596 fs32_sub(sb, &ucg->cg_frsum[allocsize], 1); 597 598 if (count != allocsize) 599 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1); 600 601 succed: 602 ubh_mark_buffer_dirty (USPI_UBH(uspi)); 603 ubh_mark_buffer_dirty (UCPI_UBH(ucpi)); 604 if (sb->s_flags & MS_SYNCHRONOUS) { 605 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi)); 606 ubh_wait_on_buffer (UCPI_UBH(ucpi)); 607 } 608 sb->s_dirt = 1; 609 610 result += cgno * uspi->s_fpg; 611 UFSD("EXIT3, result %u\n", result); 612 return result; 613 } 614 615 static unsigned ufs_alloccg_block (struct inode * inode, 616 struct ufs_cg_private_info * ucpi, unsigned goal, int * err) 617 { 618 struct super_block * sb; 619 struct ufs_sb_private_info * uspi; 620 struct ufs_super_block_first * usb1; 621 struct ufs_cylinder_group * ucg; 622 unsigned result, cylno, blkno; 623 624 UFSD("ENTER, goal %u\n", goal); 625 626 sb = inode->i_sb; 627 uspi = UFS_SB(sb)->s_uspi; 628 usb1 = ubh_get_usb_first(uspi); 629 ucg = ubh_get_ucg(UCPI_UBH(ucpi)); 630 631 if (goal == 0) { 632 goal = ucpi->c_rotor; 633 goto norot; 634 } 635 goal = ufs_blknum (goal); 636 goal = ufs_dtogd (goal); 637 638 /* 639 * If the requested block is available, use it. 640 */ 641 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, ufs_fragstoblks(goal))) { 642 result = goal; 643 goto gotit; 644 } 645 646 norot: 647 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb); 648 if (result == (unsigned)-1) 649 return (unsigned)-1; 650 ucpi->c_rotor = result; 651 gotit: 652 blkno = ufs_fragstoblks(result); 653 ubh_clrblock (UCPI_UBH(ucpi), ucpi->c_freeoff, blkno); 654 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD) 655 ufs_clusteracct (sb, ucpi, blkno, -1); 656 if(DQUOT_ALLOC_BLOCK(inode, uspi->s_fpb)) { 657 *err = -EDQUOT; 658 return (unsigned)-1; 659 } 660 661 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1); 662 uspi->cs_total.cs_nbfree--; 663 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1); 664 cylno = ufs_cbtocylno(result); 665 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(result)), 1); 666 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1); 667 668 UFSD("EXIT, result %u\n", result); 669 670 return result; 671 } 672 673 static unsigned ubh_scanc(struct ufs_sb_private_info *uspi, 674 struct ufs_buffer_head *ubh, 675 unsigned begin, unsigned size, 676 unsigned char *table, unsigned char mask) 677 { 678 unsigned rest, offset; 679 unsigned char *cp; 680 681 682 offset = begin & ~uspi->s_fmask; 683 begin >>= uspi->s_fshift; 684 for (;;) { 685 if ((offset + size) < uspi->s_fsize) 686 rest = size; 687 else 688 rest = uspi->s_fsize - offset; 689 size -= rest; 690 cp = ubh->bh[begin]->b_data + offset; 691 while ((table[*cp++] & mask) == 0 && --rest) 692 ; 693 if (rest || !size) 694 break; 695 begin++; 696 offset = 0; 697 } 698 return (size + rest); 699 } 700 701 /* 702 * Find a block of the specified size in the specified cylinder group. 703 * @sp: pointer to super block 704 * @ucpi: pointer to cylinder group info 705 * @goal: near which block we want find new one 706 * @count: specified size 707 */ 708 static unsigned ufs_bitmap_search(struct super_block *sb, 709 struct ufs_cg_private_info *ucpi, 710 unsigned goal, unsigned count) 711 { 712 /* 713 * Bit patterns for identifying fragments in the block map 714 * used as ((map & mask_arr) == want_arr) 715 */ 716 static const int mask_arr[9] = { 717 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff 718 }; 719 static const int want_arr[9] = { 720 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe 721 }; 722 struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi; 723 struct ufs_super_block_first *usb1; 724 struct ufs_cylinder_group *ucg; 725 unsigned start, length, loc, result; 726 unsigned pos, want, blockmap, mask, end; 727 728 UFSD("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count); 729 730 usb1 = ubh_get_usb_first (uspi); 731 ucg = ubh_get_ucg(UCPI_UBH(ucpi)); 732 733 if (goal) 734 start = ufs_dtogd(goal) >> 3; 735 else 736 start = ucpi->c_frotor >> 3; 737 738 length = ((uspi->s_fpg + 7) >> 3) - start; 739 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length, 740 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other, 741 1 << (count - 1 + (uspi->s_fpb & 7))); 742 if (loc == 0) { 743 length = start + 1; 744 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length, 745 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : 746 ufs_fragtable_other, 747 1 << (count - 1 + (uspi->s_fpb & 7))); 748 if (loc == 0) { 749 ufs_error(sb, "ufs_bitmap_search", 750 "bitmap corrupted on cg %u, start %u," 751 " length %u, count %u, freeoff %u\n", 752 ucpi->c_cgx, start, length, count, 753 ucpi->c_freeoff); 754 return (unsigned)-1; 755 } 756 start = 0; 757 } 758 result = (start + length - loc) << 3; 759 ucpi->c_frotor = result; 760 761 /* 762 * found the byte in the map 763 */ 764 765 for (end = result + 8; result < end; result += uspi->s_fpb) { 766 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result); 767 blockmap <<= 1; 768 mask = mask_arr[count]; 769 want = want_arr[count]; 770 for (pos = 0; pos <= uspi->s_fpb - count; pos++) { 771 if ((blockmap & mask) == want) { 772 UFSD("EXIT, result %u\n", result); 773 return result + pos; 774 } 775 mask <<= 1; 776 want <<= 1; 777 } 778 } 779 780 ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n", 781 ucpi->c_cgx); 782 UFSD("EXIT (FAILED)\n"); 783 return (unsigned)-1; 784 } 785 786 static void ufs_clusteracct(struct super_block * sb, 787 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt) 788 { 789 struct ufs_sb_private_info * uspi; 790 int i, start, end, forw, back; 791 792 uspi = UFS_SB(sb)->s_uspi; 793 if (uspi->s_contigsumsize <= 0) 794 return; 795 796 if (cnt > 0) 797 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno); 798 else 799 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno); 800 801 /* 802 * Find the size of the cluster going forward. 803 */ 804 start = blkno + 1; 805 end = start + uspi->s_contigsumsize; 806 if ( end >= ucpi->c_nclusterblks) 807 end = ucpi->c_nclusterblks; 808 i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start); 809 if (i > end) 810 i = end; 811 forw = i - start; 812 813 /* 814 * Find the size of the cluster going backward. 815 */ 816 start = blkno - 1; 817 end = start - uspi->s_contigsumsize; 818 if (end < 0 ) 819 end = -1; 820 i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end); 821 if ( i < end) 822 i = end; 823 back = start - i; 824 825 /* 826 * Account for old cluster and the possibly new forward and 827 * back clusters. 828 */ 829 i = back + forw + 1; 830 if (i > uspi->s_contigsumsize) 831 i = uspi->s_contigsumsize; 832 fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt); 833 if (back > 0) 834 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt); 835 if (forw > 0) 836 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt); 837 } 838 839 840 static unsigned char ufs_fragtable_8fpb[] = { 841 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08, 842 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10, 843 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 844 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20, 845 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 846 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11, 847 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A, 848 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40, 849 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 850 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11, 851 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 852 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21, 853 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A, 854 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12, 855 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C, 856 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80, 857 }; 858 859 static unsigned char ufs_fragtable_other[] = { 860 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A, 861 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 862 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 863 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA, 864 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 865 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 866 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE, 867 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE, 868 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 869 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 870 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 871 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE, 872 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA, 873 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE, 874 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE, 875 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A, 876 }; 877