1// SPDX-License-Identifier: GPL-2.0 2/* 3 * linux/fs/ufs/balloc.c 4 * 5 * Copyright (C) 1998 6 * Daniel Pirkl <daniel.pirkl@email.cz> 7 * Charles University, Faculty of Mathematics and Physics 8 * 9 * UFS2 write support Evgeniy Dushistov <dushistov@mail.ru>, 2007 10 */ 11 12#include <linux/fs.h> 13#include <linux/stat.h> 14#include <linux/time.h> 15#include <linux/string.h> 16#include <linux/buffer_head.h> 17#include <linux/capability.h> 18#include <linux/bitops.h> 19#include <linux/bio.h> 20#include <asm/byteorder.h> 21 22#include "ufs_fs.h" 23#include "ufs.h" 24#include "swab.h" 25#include "util.h" 26 27#define INVBLOCK ((u64)-1L) 28 29static u64 ufs_add_fragments(struct inode *, u64, unsigned, unsigned); 30static u64 ufs_alloc_fragments(struct inode *, unsigned, u64, unsigned, int *); 31static u64 ufs_alloccg_block(struct inode *, struct ufs_cg_private_info *, u64, int *); 32static u64 ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, u64, unsigned); 33static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[]; 34static void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int); 35 36/* 37 * Free 'count' fragments from fragment number 'fragment' 38 */ 39void ufs_free_fragments(struct inode *inode, u64 fragment, unsigned count) 40{ 41 struct super_block * sb; 42 struct ufs_sb_private_info * uspi; 43 struct ufs_cg_private_info * ucpi; 44 struct ufs_cylinder_group * ucg; 45 unsigned cgno, bit, end_bit, bbase, blkmap, i; 46 u64 blkno; 47 48 sb = inode->i_sb; 49 uspi = UFS_SB(sb)->s_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 inode_sub_bytes(inode, count << uspi->s_fshift); 88 fs32_add(sb, &ucg->cg_cs.cs_nffree, count); 89 uspi->cs_total.cs_nffree += count; 90 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count); 91 blkmap = ubh_blkmap (UCPI_UBH(ucpi), ucpi->c_freeoff, bbase); 92 ufs_fragacct(sb, blkmap, ucg->cg_frsum, 1); 93 94 /* 95 * Trying to reassemble free fragments into block 96 */ 97 blkno = ufs_fragstoblks (bbase); 98 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) { 99 fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb); 100 uspi->cs_total.cs_nffree -= uspi->s_fpb; 101 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, uspi->s_fpb); 102 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD) 103 ufs_clusteracct (sb, ucpi, blkno, 1); 104 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1); 105 uspi->cs_total.cs_nbfree++; 106 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1); 107 if (uspi->fs_magic != UFS2_MAGIC) { 108 unsigned cylno = ufs_cbtocylno (bbase); 109 110 fs16_add(sb, &ubh_cg_blks(ucpi, cylno, 111 ufs_cbtorpos(bbase)), 1); 112 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1); 113 } 114 } 115 116 ubh_mark_buffer_dirty (USPI_UBH(uspi)); 117 ubh_mark_buffer_dirty (UCPI_UBH(ucpi)); 118 if (sb->s_flags & SB_SYNCHRONOUS) 119 ubh_sync_block(UCPI_UBH(ucpi)); 120 ufs_mark_sb_dirty(sb); 121 122 mutex_unlock(&UFS_SB(sb)->s_lock); 123 UFSD("EXIT\n"); 124 return; 125 126failed: 127 mutex_unlock(&UFS_SB(sb)->s_lock); 128 UFSD("EXIT (FAILED)\n"); 129 return; 130} 131 132/* 133 * Free 'count' fragments from fragment number 'fragment' (free whole blocks) 134 */ 135void ufs_free_blocks(struct inode *inode, u64 fragment, unsigned count) 136{ 137 struct super_block * sb; 138 struct ufs_sb_private_info * uspi; 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 147 UFSD("ENTER, fragment %llu, count %u\n", 148 (unsigned long long)fragment, count); 149 150 if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) { 151 ufs_error (sb, "ufs_free_blocks", "internal error, " 152 "fragment %llu, count %u\n", 153 (unsigned long long)fragment, count); 154 goto failed; 155 } 156 157 mutex_lock(&UFS_SB(sb)->s_lock); 158 159do_more: 160 overflow = 0; 161 cgno = ufs_dtog(uspi, fragment); 162 bit = ufs_dtogd(uspi, fragment); 163 if (cgno >= uspi->s_ncg) { 164 ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device"); 165 goto failed_unlock; 166 } 167 end_bit = bit + count; 168 if (end_bit > uspi->s_fpg) { 169 overflow = bit + count - uspi->s_fpg; 170 count -= overflow; 171 end_bit -= overflow; 172 } 173 174 ucpi = ufs_load_cylinder (sb, cgno); 175 if (!ucpi) 176 goto failed_unlock; 177 ucg = ubh_get_ucg (UCPI_UBH(ucpi)); 178 if (!ufs_cg_chkmagic(sb, ucg)) { 179 ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno); 180 goto failed_unlock; 181 } 182 183 for (i = bit; i < end_bit; i += uspi->s_fpb) { 184 blkno = ufs_fragstoblks(i); 185 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) { 186 ufs_error(sb, "ufs_free_blocks", "freeing free fragment"); 187 } 188 ubh_setblock(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno); 189 inode_sub_bytes(inode, uspi->s_fpb << uspi->s_fshift); 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 & SB_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 222failed_unlock: 223 mutex_unlock(&UFS_SB(sb)->s_lock); 224failed: 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 */ 239static 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_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_SHIFT - inode->i_blkbits); 263 for (i = beg; i < end; i = (i | mask) + 1) { 264 index = i >> (PAGE_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 (bh_read(bh, 0) < 0) { 299 ufs_error(inode->i_sb, __func__, 300 "read of block failed\n"); 301 break; 302 } 303 304 UFSD(" change from %llu to %llu, pos %u\n", 305 (unsigned long long)(pos + oldb), 306 (unsigned long long)(pos + newb), pos); 307 308 bh->b_blocknr = newb + pos; 309 clean_bdev_bh_alias(bh); 310 mark_buffer_dirty(bh); 311 ++j; 312 bh = bh->b_this_page; 313 } while (bh != head); 314 315 if (likely(cur_index != index)) 316 ufs_put_locked_page(page); 317 } 318 UFSD("EXIT\n"); 319} 320 321static void ufs_clear_frags(struct inode *inode, sector_t beg, unsigned int n, 322 int sync) 323{ 324 struct buffer_head *bh; 325 sector_t end = beg + n; 326 327 for (; beg < end; ++beg) { 328 bh = sb_getblk(inode->i_sb, beg); 329 lock_buffer(bh); 330 memset(bh->b_data, 0, inode->i_sb->s_blocksize); 331 set_buffer_uptodate(bh); 332 mark_buffer_dirty(bh); 333 unlock_buffer(bh); 334 if (IS_SYNC(inode) || sync) 335 sync_dirty_buffer(bh); 336 brelse(bh); 337 } 338} 339 340u64 ufs_new_fragments(struct inode *inode, void *p, u64 fragment, 341 u64 goal, unsigned count, int *err, 342 struct page *locked_page) 343{ 344 struct super_block * sb; 345 struct ufs_sb_private_info * uspi; 346 struct ufs_super_block_first * usb1; 347 unsigned cgno, oldcount, newcount; 348 u64 tmp, request, result; 349 350 UFSD("ENTER, ino %lu, fragment %llu, goal %llu, count %u\n", 351 inode->i_ino, (unsigned long long)fragment, 352 (unsigned long long)goal, count); 353 354 sb = inode->i_sb; 355 uspi = UFS_SB(sb)->s_uspi; 356 usb1 = ubh_get_usb_first(uspi); 357 *err = -ENOSPC; 358 359 mutex_lock(&UFS_SB(sb)->s_lock); 360 tmp = ufs_data_ptr_to_cpu(sb, p); 361 362 if (count + ufs_fragnum(fragment) > uspi->s_fpb) { 363 ufs_warning(sb, "ufs_new_fragments", "internal warning" 364 " fragment %llu, count %u", 365 (unsigned long long)fragment, count); 366 count = uspi->s_fpb - ufs_fragnum(fragment); 367 } 368 oldcount = ufs_fragnum (fragment); 369 newcount = oldcount + count; 370 371 /* 372 * Somebody else has just allocated our fragments 373 */ 374 if (oldcount) { 375 if (!tmp) { 376 ufs_error(sb, "ufs_new_fragments", "internal error, " 377 "fragment %llu, tmp %llu\n", 378 (unsigned long long)fragment, 379 (unsigned long long)tmp); 380 mutex_unlock(&UFS_SB(sb)->s_lock); 381 return INVBLOCK; 382 } 383 if (fragment < UFS_I(inode)->i_lastfrag) { 384 UFSD("EXIT (ALREADY ALLOCATED)\n"); 385 mutex_unlock(&UFS_SB(sb)->s_lock); 386 return 0; 387 } 388 } 389 else { 390 if (tmp) { 391 UFSD("EXIT (ALREADY ALLOCATED)\n"); 392 mutex_unlock(&UFS_SB(sb)->s_lock); 393 return 0; 394 } 395 } 396 397 /* 398 * There is not enough space for user on the device 399 */ 400 if (unlikely(ufs_freefrags(uspi) <= uspi->s_root_blocks)) { 401 if (!capable(CAP_SYS_RESOURCE)) { 402 mutex_unlock(&UFS_SB(sb)->s_lock); 403 UFSD("EXIT (FAILED)\n"); 404 return 0; 405 } 406 } 407 408 if (goal >= uspi->s_size) 409 goal = 0; 410 if (goal == 0) 411 cgno = ufs_inotocg (inode->i_ino); 412 else 413 cgno = ufs_dtog(uspi, goal); 414 415 /* 416 * allocate new fragment 417 */ 418 if (oldcount == 0) { 419 result = ufs_alloc_fragments (inode, cgno, goal, count, err); 420 if (result) { 421 ufs_clear_frags(inode, result + oldcount, 422 newcount - oldcount, locked_page != NULL); 423 *err = 0; 424 write_seqlock(&UFS_I(inode)->meta_lock); 425 ufs_cpu_to_data_ptr(sb, p, result); 426 UFS_I(inode)->i_lastfrag = 427 max(UFS_I(inode)->i_lastfrag, fragment + count); 428 write_sequnlock(&UFS_I(inode)->meta_lock); 429 } 430 mutex_unlock(&UFS_SB(sb)->s_lock); 431 UFSD("EXIT, result %llu\n", (unsigned long long)result); 432 return result; 433 } 434 435 /* 436 * resize block 437 */ 438 result = ufs_add_fragments(inode, tmp, oldcount, newcount); 439 if (result) { 440 *err = 0; 441 read_seqlock_excl(&UFS_I(inode)->meta_lock); 442 UFS_I(inode)->i_lastfrag = max(UFS_I(inode)->i_lastfrag, 443 fragment + count); 444 read_sequnlock_excl(&UFS_I(inode)->meta_lock); 445 ufs_clear_frags(inode, result + oldcount, newcount - oldcount, 446 locked_page != NULL); 447 mutex_unlock(&UFS_SB(sb)->s_lock); 448 UFSD("EXIT, result %llu\n", (unsigned long long)result); 449 return result; 450 } 451 452 /* 453 * allocate new block and move data 454 */ 455 if (fs32_to_cpu(sb, usb1->fs_optim) == UFS_OPTSPACE) { 456 request = newcount; 457 if (uspi->cs_total.cs_nffree < uspi->s_space_to_time) 458 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME); 459 } else { 460 request = uspi->s_fpb; 461 if (uspi->cs_total.cs_nffree > uspi->s_time_to_space) 462 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTSPACE); 463 } 464 result = ufs_alloc_fragments (inode, cgno, goal, request, err); 465 if (result) { 466 ufs_clear_frags(inode, result + oldcount, newcount - oldcount, 467 locked_page != NULL); 468 mutex_unlock(&UFS_SB(sb)->s_lock); 469 ufs_change_blocknr(inode, fragment - oldcount, oldcount, 470 uspi->s_sbbase + tmp, 471 uspi->s_sbbase + result, locked_page); 472 *err = 0; 473 write_seqlock(&UFS_I(inode)->meta_lock); 474 ufs_cpu_to_data_ptr(sb, p, result); 475 UFS_I(inode)->i_lastfrag = max(UFS_I(inode)->i_lastfrag, 476 fragment + count); 477 write_sequnlock(&UFS_I(inode)->meta_lock); 478 if (newcount < request) 479 ufs_free_fragments (inode, result + newcount, request - newcount); 480 ufs_free_fragments (inode, tmp, oldcount); 481 UFSD("EXIT, result %llu\n", (unsigned long long)result); 482 return result; 483 } 484 485 mutex_unlock(&UFS_SB(sb)->s_lock); 486 UFSD("EXIT (FAILED)\n"); 487 return 0; 488} 489 490static bool try_add_frags(struct inode *inode, unsigned frags) 491{ 492 unsigned size = frags * i_blocksize(inode); 493 spin_lock(&inode->i_lock); 494 __inode_add_bytes(inode, size); 495 if (unlikely((u32)inode->i_blocks != inode->i_blocks)) { 496 __inode_sub_bytes(inode, size); 497 spin_unlock(&inode->i_lock); 498 return false; 499 } 500 spin_unlock(&inode->i_lock); 501 return true; 502} 503 504static u64 ufs_add_fragments(struct inode *inode, u64 fragment, 505 unsigned oldcount, unsigned newcount) 506{ 507 struct super_block * sb; 508 struct ufs_sb_private_info * uspi; 509 struct ufs_cg_private_info * ucpi; 510 struct ufs_cylinder_group * ucg; 511 unsigned cgno, fragno, fragoff, count, fragsize, i; 512 513 UFSD("ENTER, fragment %llu, oldcount %u, newcount %u\n", 514 (unsigned long long)fragment, oldcount, newcount); 515 516 sb = inode->i_sb; 517 uspi = UFS_SB(sb)->s_uspi; 518 count = newcount - oldcount; 519 520 cgno = ufs_dtog(uspi, fragment); 521 if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count) 522 return 0; 523 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb) 524 return 0; 525 ucpi = ufs_load_cylinder (sb, cgno); 526 if (!ucpi) 527 return 0; 528 ucg = ubh_get_ucg (UCPI_UBH(ucpi)); 529 if (!ufs_cg_chkmagic(sb, ucg)) { 530 ufs_panic (sb, "ufs_add_fragments", 531 "internal error, bad magic number on cg %u", cgno); 532 return 0; 533 } 534 535 fragno = ufs_dtogd(uspi, fragment); 536 fragoff = ufs_fragnum (fragno); 537 for (i = oldcount; i < newcount; i++) 538 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i)) 539 return 0; 540 541 if (!try_add_frags(inode, count)) 542 return 0; 543 /* 544 * Block can be extended 545 */ 546 ucg->cg_time = ufs_get_seconds(sb); 547 for (i = newcount; i < (uspi->s_fpb - fragoff); i++) 548 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i)) 549 break; 550 fragsize = i - oldcount; 551 if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize])) 552 ufs_panic (sb, "ufs_add_fragments", 553 "internal error or corrupted bitmap on cg %u", cgno); 554 fs32_sub(sb, &ucg->cg_frsum[fragsize], 1); 555 if (fragsize != count) 556 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1); 557 for (i = oldcount; i < newcount; i++) 558 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i); 559 560 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count); 561 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count); 562 uspi->cs_total.cs_nffree -= count; 563 564 ubh_mark_buffer_dirty (USPI_UBH(uspi)); 565 ubh_mark_buffer_dirty (UCPI_UBH(ucpi)); 566 if (sb->s_flags & SB_SYNCHRONOUS) 567 ubh_sync_block(UCPI_UBH(ucpi)); 568 ufs_mark_sb_dirty(sb); 569 570 UFSD("EXIT, fragment %llu\n", (unsigned long long)fragment); 571 572 return fragment; 573} 574 575#define UFS_TEST_FREE_SPACE_CG \ 576 ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \ 577 if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \ 578 goto cg_found; \ 579 for (k = count; k < uspi->s_fpb; k++) \ 580 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \ 581 goto cg_found; 582 583static u64 ufs_alloc_fragments(struct inode *inode, unsigned cgno, 584 u64 goal, unsigned count, int *err) 585{ 586 struct super_block * sb; 587 struct ufs_sb_private_info * uspi; 588 struct ufs_cg_private_info * ucpi; 589 struct ufs_cylinder_group * ucg; 590 unsigned oldcg, i, j, k, allocsize; 591 u64 result; 592 593 UFSD("ENTER, ino %lu, cgno %u, goal %llu, count %u\n", 594 inode->i_ino, cgno, (unsigned long long)goal, count); 595 596 sb = inode->i_sb; 597 uspi = UFS_SB(sb)->s_uspi; 598 oldcg = cgno; 599 600 /* 601 * 1. searching on preferred cylinder group 602 */ 603 UFS_TEST_FREE_SPACE_CG 604 605 /* 606 * 2. quadratic rehash 607 */ 608 for (j = 1; j < uspi->s_ncg; j *= 2) { 609 cgno += j; 610 if (cgno >= uspi->s_ncg) 611 cgno -= uspi->s_ncg; 612 UFS_TEST_FREE_SPACE_CG 613 } 614 615 /* 616 * 3. brute force search 617 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step ) 618 */ 619 cgno = (oldcg + 1) % uspi->s_ncg; 620 for (j = 2; j < uspi->s_ncg; j++) { 621 cgno++; 622 if (cgno >= uspi->s_ncg) 623 cgno = 0; 624 UFS_TEST_FREE_SPACE_CG 625 } 626 627 UFSD("EXIT (FAILED)\n"); 628 return 0; 629 630cg_found: 631 ucpi = ufs_load_cylinder (sb, cgno); 632 if (!ucpi) 633 return 0; 634 ucg = ubh_get_ucg (UCPI_UBH(ucpi)); 635 if (!ufs_cg_chkmagic(sb, ucg)) 636 ufs_panic (sb, "ufs_alloc_fragments", 637 "internal error, bad magic number on cg %u", cgno); 638 ucg->cg_time = ufs_get_seconds(sb); 639 640 if (count == uspi->s_fpb) { 641 result = ufs_alloccg_block (inode, ucpi, goal, err); 642 if (result == INVBLOCK) 643 return 0; 644 goto succed; 645 } 646 647 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++) 648 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0) 649 break; 650 651 if (allocsize == uspi->s_fpb) { 652 result = ufs_alloccg_block (inode, ucpi, goal, err); 653 if (result == INVBLOCK) 654 return 0; 655 goal = ufs_dtogd(uspi, result); 656 for (i = count; i < uspi->s_fpb; i++) 657 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, goal + i); 658 i = uspi->s_fpb - count; 659 660 inode_sub_bytes(inode, i << uspi->s_fshift); 661 fs32_add(sb, &ucg->cg_cs.cs_nffree, i); 662 uspi->cs_total.cs_nffree += i; 663 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i); 664 fs32_add(sb, &ucg->cg_frsum[i], 1); 665 goto succed; 666 } 667 668 result = ufs_bitmap_search (sb, ucpi, goal, allocsize); 669 if (result == INVBLOCK) 670 return 0; 671 if (!try_add_frags(inode, count)) 672 return 0; 673 for (i = 0; i < count; i++) 674 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, result + i); 675 676 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count); 677 uspi->cs_total.cs_nffree -= count; 678 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count); 679 fs32_sub(sb, &ucg->cg_frsum[allocsize], 1); 680 681 if (count != allocsize) 682 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1); 683 684succed: 685 ubh_mark_buffer_dirty (USPI_UBH(uspi)); 686 ubh_mark_buffer_dirty (UCPI_UBH(ucpi)); 687 if (sb->s_flags & SB_SYNCHRONOUS) 688 ubh_sync_block(UCPI_UBH(ucpi)); 689 ufs_mark_sb_dirty(sb); 690 691 result += cgno * uspi->s_fpg; 692 UFSD("EXIT3, result %llu\n", (unsigned long long)result); 693 return result; 694} 695 696static u64 ufs_alloccg_block(struct inode *inode, 697 struct ufs_cg_private_info *ucpi, 698 u64 goal, int *err) 699{ 700 struct super_block * sb; 701 struct ufs_sb_private_info * uspi; 702 struct ufs_cylinder_group * ucg; 703 u64 result, blkno; 704 705 UFSD("ENTER, goal %llu\n", (unsigned long long)goal); 706 707 sb = inode->i_sb; 708 uspi = UFS_SB(sb)->s_uspi; 709 ucg = ubh_get_ucg(UCPI_UBH(ucpi)); 710 711 if (goal == 0) { 712 goal = ucpi->c_rotor; 713 goto norot; 714 } 715 goal = ufs_blknum (goal); 716 goal = ufs_dtogd(uspi, goal); 717 718 /* 719 * If the requested block is available, use it. 720 */ 721 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, ufs_fragstoblks(goal))) { 722 result = goal; 723 goto gotit; 724 } 725 726norot: 727 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb); 728 if (result == INVBLOCK) 729 return INVBLOCK; 730 ucpi->c_rotor = result; 731gotit: 732 if (!try_add_frags(inode, uspi->s_fpb)) 733 return 0; 734 blkno = ufs_fragstoblks(result); 735 ubh_clrblock (UCPI_UBH(ucpi), ucpi->c_freeoff, blkno); 736 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD) 737 ufs_clusteracct (sb, ucpi, blkno, -1); 738 739 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1); 740 uspi->cs_total.cs_nbfree--; 741 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1); 742 743 if (uspi->fs_magic != UFS2_MAGIC) { 744 unsigned cylno = ufs_cbtocylno((unsigned)result); 745 746 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno, 747 ufs_cbtorpos((unsigned)result)), 1); 748 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1); 749 } 750 751 UFSD("EXIT, result %llu\n", (unsigned long long)result); 752 753 return result; 754} 755 756static unsigned ubh_scanc(struct ufs_sb_private_info *uspi, 757 struct ufs_buffer_head *ubh, 758 unsigned begin, unsigned size, 759 unsigned char *table, unsigned char mask) 760{ 761 unsigned rest, offset; 762 unsigned char *cp; 763 764 765 offset = begin & ~uspi->s_fmask; 766 begin >>= uspi->s_fshift; 767 for (;;) { 768 if ((offset + size) < uspi->s_fsize) 769 rest = size; 770 else 771 rest = uspi->s_fsize - offset; 772 size -= rest; 773 cp = ubh->bh[begin]->b_data + offset; 774 while ((table[*cp++] & mask) == 0 && --rest) 775 ; 776 if (rest || !size) 777 break; 778 begin++; 779 offset = 0; 780 } 781 return (size + rest); 782} 783 784/* 785 * Find a block of the specified size in the specified cylinder group. 786 * @sp: pointer to super block 787 * @ucpi: pointer to cylinder group info 788 * @goal: near which block we want find new one 789 * @count: specified size 790 */ 791static u64 ufs_bitmap_search(struct super_block *sb, 792 struct ufs_cg_private_info *ucpi, 793 u64 goal, unsigned count) 794{ 795 /* 796 * Bit patterns for identifying fragments in the block map 797 * used as ((map & mask_arr) == want_arr) 798 */ 799 static const int mask_arr[9] = { 800 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff 801 }; 802 static const int want_arr[9] = { 803 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe 804 }; 805 struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi; 806 unsigned start, length, loc; 807 unsigned pos, want, blockmap, mask, end; 808 u64 result; 809 810 UFSD("ENTER, cg %u, goal %llu, count %u\n", ucpi->c_cgx, 811 (unsigned long long)goal, count); 812 813 if (goal) 814 start = ufs_dtogd(uspi, goal) >> 3; 815 else 816 start = ucpi->c_frotor >> 3; 817 818 length = ((uspi->s_fpg + 7) >> 3) - start; 819 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length, 820 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other, 821 1 << (count - 1 + (uspi->s_fpb & 7))); 822 if (loc == 0) { 823 length = start + 1; 824 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length, 825 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : 826 ufs_fragtable_other, 827 1 << (count - 1 + (uspi->s_fpb & 7))); 828 if (loc == 0) { 829 ufs_error(sb, "ufs_bitmap_search", 830 "bitmap corrupted on cg %u, start %u," 831 " length %u, count %u, freeoff %u\n", 832 ucpi->c_cgx, start, length, count, 833 ucpi->c_freeoff); 834 return INVBLOCK; 835 } 836 start = 0; 837 } 838 result = (start + length - loc) << 3; 839 ucpi->c_frotor = result; 840 841 /* 842 * found the byte in the map 843 */ 844 845 for (end = result + 8; result < end; result += uspi->s_fpb) { 846 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result); 847 blockmap <<= 1; 848 mask = mask_arr[count]; 849 want = want_arr[count]; 850 for (pos = 0; pos <= uspi->s_fpb - count; pos++) { 851 if ((blockmap & mask) == want) { 852 UFSD("EXIT, result %llu\n", 853 (unsigned long long)result); 854 return result + pos; 855 } 856 mask <<= 1; 857 want <<= 1; 858 } 859 } 860 861 ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n", 862 ucpi->c_cgx); 863 UFSD("EXIT (FAILED)\n"); 864 return INVBLOCK; 865} 866 867static void ufs_clusteracct(struct super_block * sb, 868 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt) 869{ 870 struct ufs_sb_private_info * uspi; 871 int i, start, end, forw, back; 872 873 uspi = UFS_SB(sb)->s_uspi; 874 if (uspi->s_contigsumsize <= 0) 875 return; 876 877 if (cnt > 0) 878 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno); 879 else 880 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno); 881 882 /* 883 * Find the size of the cluster going forward. 884 */ 885 start = blkno + 1; 886 end = start + uspi->s_contigsumsize; 887 if ( end >= ucpi->c_nclusterblks) 888 end = ucpi->c_nclusterblks; 889 i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start); 890 if (i > end) 891 i = end; 892 forw = i - start; 893 894 /* 895 * Find the size of the cluster going backward. 896 */ 897 start = blkno - 1; 898 end = start - uspi->s_contigsumsize; 899 if (end < 0 ) 900 end = -1; 901 i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end); 902 if ( i < end) 903 i = end; 904 back = start - i; 905 906 /* 907 * Account for old cluster and the possibly new forward and 908 * back clusters. 909 */ 910 i = back + forw + 1; 911 if (i > uspi->s_contigsumsize) 912 i = uspi->s_contigsumsize; 913 fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt); 914 if (back > 0) 915 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt); 916 if (forw > 0) 917 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt); 918} 919 920 921static unsigned char ufs_fragtable_8fpb[] = { 922 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08, 923 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10, 924 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 925 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20, 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 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A, 929 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40, 930 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 931 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11, 932 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 933 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21, 934 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A, 935 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12, 936 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C, 937 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80, 938}; 939 940static unsigned char ufs_fragtable_other[] = { 941 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A, 942 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 943 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 944 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA, 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 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE, 948 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE, 949 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 950 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 951 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 952 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE, 953 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA, 954 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE, 955 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE, 956 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A, 957}; 958