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