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