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/sched.h> 17 #include <linux/bitops.h> 18 #include <asm/byteorder.h> 19 20 #include "swab.h" 21 #include "util.h" 22 23 #undef UFS_BALLOC_DEBUG 24 25 #ifdef UFS_BALLOC_DEBUG 26 #define UFSD(x) printk("(%s, %d), %s:", __FILE__, __LINE__, __FUNCTION__); printk x; 27 #else 28 #define UFSD(x) 29 #endif 30 31 static unsigned ufs_add_fragments (struct inode *, unsigned, unsigned, unsigned, int *); 32 static unsigned ufs_alloc_fragments (struct inode *, unsigned, unsigned, unsigned, int *); 33 static unsigned ufs_alloccg_block (struct inode *, struct ufs_cg_private_info *, unsigned, int *); 34 static unsigned ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, unsigned, unsigned); 35 static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[]; 36 static void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int); 37 38 /* 39 * Free 'count' fragments from fragment number 'fragment' 40 */ 41 void ufs_free_fragments (struct inode * inode, unsigned fragment, unsigned count) { 42 struct super_block * sb; 43 struct ufs_sb_private_info * uspi; 44 struct ufs_super_block_first * usb1; 45 struct ufs_cg_private_info * ucpi; 46 struct ufs_cylinder_group * ucg; 47 unsigned cgno, bit, end_bit, bbase, blkmap, i, blkno, cylno; 48 49 sb = inode->i_sb; 50 uspi = UFS_SB(sb)->s_uspi; 51 usb1 = ubh_get_usb_first(USPI_UBH); 52 53 UFSD(("ENTER, fragment %u, count %u\n", fragment, count)) 54 55 if (ufs_fragnum(fragment) + count > uspi->s_fpg) 56 ufs_error (sb, "ufs_free_fragments", "internal error"); 57 58 lock_super(sb); 59 60 cgno = ufs_dtog(fragment); 61 bit = ufs_dtogd(fragment); 62 if (cgno >= uspi->s_ncg) { 63 ufs_panic (sb, "ufs_free_fragments", "freeing blocks are outside device"); 64 goto failed; 65 } 66 67 ucpi = ufs_load_cylinder (sb, cgno); 68 if (!ucpi) 69 goto failed; 70 ucg = ubh_get_ucg (UCPI_UBH); 71 if (!ufs_cg_chkmagic(sb, ucg)) { 72 ufs_panic (sb, "ufs_free_fragments", "internal error, bad magic number on cg %u", cgno); 73 goto failed; 74 } 75 76 end_bit = bit + count; 77 bbase = ufs_blknum (bit); 78 blkmap = ubh_blkmap (UCPI_UBH, ucpi->c_freeoff, bbase); 79 ufs_fragacct (sb, blkmap, ucg->cg_frsum, -1); 80 for (i = bit; i < end_bit; i++) { 81 if (ubh_isclr (UCPI_UBH, ucpi->c_freeoff, i)) 82 ubh_setbit (UCPI_UBH, ucpi->c_freeoff, i); 83 else ufs_error (sb, "ufs_free_fragments", 84 "bit already cleared for fragment %u", i); 85 } 86 87 DQUOT_FREE_BLOCK (inode, count); 88 89 90 fs32_add(sb, &ucg->cg_cs.cs_nffree, count); 91 fs32_add(sb, &usb1->fs_cstotal.cs_nffree, count); 92 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count); 93 blkmap = ubh_blkmap (UCPI_UBH, ucpi->c_freeoff, bbase); 94 ufs_fragacct(sb, blkmap, ucg->cg_frsum, 1); 95 96 /* 97 * Trying to reassemble free fragments into block 98 */ 99 blkno = ufs_fragstoblks (bbase); 100 if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, blkno)) { 101 fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb); 102 fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, uspi->s_fpb); 103 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, uspi->s_fpb); 104 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD) 105 ufs_clusteracct (sb, ucpi, blkno, 1); 106 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1); 107 fs32_add(sb, &usb1->fs_cstotal.cs_nbfree, 1); 108 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1); 109 cylno = ufs_cbtocylno (bbase); 110 fs16_add(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(bbase)), 1); 111 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1); 112 } 113 114 ubh_mark_buffer_dirty (USPI_UBH); 115 ubh_mark_buffer_dirty (UCPI_UBH); 116 if (sb->s_flags & MS_SYNCHRONOUS) { 117 ubh_wait_on_buffer (UCPI_UBH); 118 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi); 119 ubh_wait_on_buffer (UCPI_UBH); 120 } 121 sb->s_dirt = 1; 122 123 unlock_super (sb); 124 UFSD(("EXIT\n")) 125 return; 126 127 failed: 128 unlock_super (sb); 129 UFSD(("EXIT (FAILED)\n")) 130 return; 131 } 132 133 /* 134 * Free 'count' fragments from fragment number 'fragment' (free whole blocks) 135 */ 136 void ufs_free_blocks (struct inode * inode, unsigned fragment, unsigned count) { 137 struct super_block * sb; 138 struct ufs_sb_private_info * uspi; 139 struct ufs_super_block_first * usb1; 140 struct ufs_cg_private_info * ucpi; 141 struct ufs_cylinder_group * ucg; 142 unsigned overflow, cgno, bit, end_bit, blkno, i, cylno; 143 144 sb = inode->i_sb; 145 uspi = UFS_SB(sb)->s_uspi; 146 usb1 = ubh_get_usb_first(USPI_UBH); 147 148 UFSD(("ENTER, fragment %u, count %u\n", fragment, count)) 149 150 if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) { 151 ufs_error (sb, "ufs_free_blocks", "internal error, " 152 "fragment %u, count %u\n", fragment, count); 153 goto failed; 154 } 155 156 lock_super(sb); 157 158 do_more: 159 overflow = 0; 160 cgno = ufs_dtog (fragment); 161 bit = ufs_dtogd (fragment); 162 if (cgno >= uspi->s_ncg) { 163 ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device"); 164 goto failed; 165 } 166 end_bit = bit + count; 167 if (end_bit > uspi->s_fpg) { 168 overflow = bit + count - uspi->s_fpg; 169 count -= overflow; 170 end_bit -= overflow; 171 } 172 173 ucpi = ufs_load_cylinder (sb, cgno); 174 if (!ucpi) 175 goto failed; 176 ucg = ubh_get_ucg (UCPI_UBH); 177 if (!ufs_cg_chkmagic(sb, ucg)) { 178 ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno); 179 goto failed; 180 } 181 182 for (i = bit; i < end_bit; i += uspi->s_fpb) { 183 blkno = ufs_fragstoblks(i); 184 if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, blkno)) { 185 ufs_error(sb, "ufs_free_blocks", "freeing free fragment"); 186 } 187 ubh_setblock(UCPI_UBH, ucpi->c_freeoff, blkno); 188 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD) 189 ufs_clusteracct (sb, ucpi, blkno, 1); 190 DQUOT_FREE_BLOCK(inode, uspi->s_fpb); 191 192 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1); 193 fs32_add(sb, &usb1->fs_cstotal.cs_nbfree, 1); 194 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1); 195 cylno = ufs_cbtocylno(i); 196 fs16_add(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(i)), 1); 197 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1); 198 } 199 200 ubh_mark_buffer_dirty (USPI_UBH); 201 ubh_mark_buffer_dirty (UCPI_UBH); 202 if (sb->s_flags & MS_SYNCHRONOUS) { 203 ubh_wait_on_buffer (UCPI_UBH); 204 ubh_ll_rw_block (WRITE, 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_UBH); 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_UBH); 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_wait_on_buffer (UCPI_UBH); 463 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi); 464 ubh_wait_on_buffer (UCPI_UBH); 465 } 466 sb->s_dirt = 1; 467 468 UFSD(("EXIT, fragment %u\n", fragment)) 469 470 return fragment; 471 } 472 473 #define UFS_TEST_FREE_SPACE_CG \ 474 ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \ 475 if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \ 476 goto cg_found; \ 477 for (k = count; k < uspi->s_fpb; k++) \ 478 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \ 479 goto cg_found; 480 481 static unsigned ufs_alloc_fragments (struct inode * inode, unsigned cgno, 482 unsigned goal, unsigned count, int * err) 483 { 484 struct super_block * sb; 485 struct ufs_sb_private_info * uspi; 486 struct ufs_super_block_first * usb1; 487 struct ufs_cg_private_info * ucpi; 488 struct ufs_cylinder_group * ucg; 489 unsigned oldcg, i, j, k, result, allocsize; 490 491 UFSD(("ENTER, ino %lu, cgno %u, goal %u, count %u\n", inode->i_ino, cgno, goal, count)) 492 493 sb = inode->i_sb; 494 uspi = UFS_SB(sb)->s_uspi; 495 usb1 = ubh_get_usb_first(USPI_UBH); 496 oldcg = cgno; 497 498 /* 499 * 1. searching on preferred cylinder group 500 */ 501 UFS_TEST_FREE_SPACE_CG 502 503 /* 504 * 2. quadratic rehash 505 */ 506 for (j = 1; j < uspi->s_ncg; j *= 2) { 507 cgno += j; 508 if (cgno >= uspi->s_ncg) 509 cgno -= uspi->s_ncg; 510 UFS_TEST_FREE_SPACE_CG 511 } 512 513 /* 514 * 3. brute force search 515 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step ) 516 */ 517 cgno = (oldcg + 1) % uspi->s_ncg; 518 for (j = 2; j < uspi->s_ncg; j++) { 519 cgno++; 520 if (cgno >= uspi->s_ncg) 521 cgno = 0; 522 UFS_TEST_FREE_SPACE_CG 523 } 524 525 UFSD(("EXIT (FAILED)\n")) 526 return 0; 527 528 cg_found: 529 ucpi = ufs_load_cylinder (sb, cgno); 530 if (!ucpi) 531 return 0; 532 ucg = ubh_get_ucg (UCPI_UBH); 533 if (!ufs_cg_chkmagic(sb, ucg)) 534 ufs_panic (sb, "ufs_alloc_fragments", 535 "internal error, bad magic number on cg %u", cgno); 536 ucg->cg_time = cpu_to_fs32(sb, get_seconds()); 537 538 if (count == uspi->s_fpb) { 539 result = ufs_alloccg_block (inode, ucpi, goal, err); 540 if (result == (unsigned)-1) 541 return 0; 542 goto succed; 543 } 544 545 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++) 546 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0) 547 break; 548 549 if (allocsize == uspi->s_fpb) { 550 result = ufs_alloccg_block (inode, ucpi, goal, err); 551 if (result == (unsigned)-1) 552 return 0; 553 goal = ufs_dtogd (result); 554 for (i = count; i < uspi->s_fpb; i++) 555 ubh_setbit (UCPI_UBH, ucpi->c_freeoff, goal + i); 556 i = uspi->s_fpb - count; 557 DQUOT_FREE_BLOCK(inode, i); 558 559 fs32_add(sb, &ucg->cg_cs.cs_nffree, i); 560 fs32_add(sb, &usb1->fs_cstotal.cs_nffree, i); 561 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i); 562 fs32_add(sb, &ucg->cg_frsum[i], 1); 563 goto succed; 564 } 565 566 result = ufs_bitmap_search (sb, ucpi, goal, allocsize); 567 if (result == (unsigned)-1) 568 return 0; 569 if(DQUOT_ALLOC_BLOCK(inode, count)) { 570 *err = -EDQUOT; 571 return 0; 572 } 573 for (i = 0; i < count; i++) 574 ubh_clrbit (UCPI_UBH, ucpi->c_freeoff, result + i); 575 576 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count); 577 fs32_sub(sb, &usb1->fs_cstotal.cs_nffree, count); 578 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count); 579 fs32_sub(sb, &ucg->cg_frsum[allocsize], 1); 580 581 if (count != allocsize) 582 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1); 583 584 succed: 585 ubh_mark_buffer_dirty (USPI_UBH); 586 ubh_mark_buffer_dirty (UCPI_UBH); 587 if (sb->s_flags & MS_SYNCHRONOUS) { 588 ubh_wait_on_buffer (UCPI_UBH); 589 ubh_ll_rw_block (WRITE, 1, (struct ufs_buffer_head **)&ucpi); 590 ubh_wait_on_buffer (UCPI_UBH); 591 } 592 sb->s_dirt = 1; 593 594 result += cgno * uspi->s_fpg; 595 UFSD(("EXIT3, result %u\n", result)) 596 return result; 597 } 598 599 static unsigned ufs_alloccg_block (struct inode * inode, 600 struct ufs_cg_private_info * ucpi, unsigned goal, int * err) 601 { 602 struct super_block * sb; 603 struct ufs_sb_private_info * uspi; 604 struct ufs_super_block_first * usb1; 605 struct ufs_cylinder_group * ucg; 606 unsigned result, cylno, blkno; 607 608 UFSD(("ENTER, goal %u\n", goal)) 609 610 sb = inode->i_sb; 611 uspi = UFS_SB(sb)->s_uspi; 612 usb1 = ubh_get_usb_first(USPI_UBH); 613 ucg = ubh_get_ucg(UCPI_UBH); 614 615 if (goal == 0) { 616 goal = ucpi->c_rotor; 617 goto norot; 618 } 619 goal = ufs_blknum (goal); 620 goal = ufs_dtogd (goal); 621 622 /* 623 * If the requested block is available, use it. 624 */ 625 if (ubh_isblockset(UCPI_UBH, ucpi->c_freeoff, ufs_fragstoblks(goal))) { 626 result = goal; 627 goto gotit; 628 } 629 630 norot: 631 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb); 632 if (result == (unsigned)-1) 633 return (unsigned)-1; 634 ucpi->c_rotor = result; 635 gotit: 636 blkno = ufs_fragstoblks(result); 637 ubh_clrblock (UCPI_UBH, ucpi->c_freeoff, blkno); 638 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD) 639 ufs_clusteracct (sb, ucpi, blkno, -1); 640 if(DQUOT_ALLOC_BLOCK(inode, uspi->s_fpb)) { 641 *err = -EDQUOT; 642 return (unsigned)-1; 643 } 644 645 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1); 646 fs32_sub(sb, &usb1->fs_cstotal.cs_nbfree, 1); 647 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1); 648 cylno = ufs_cbtocylno(result); 649 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno, ufs_cbtorpos(result)), 1); 650 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1); 651 652 UFSD(("EXIT, result %u\n", result)) 653 654 return result; 655 } 656 657 static unsigned ufs_bitmap_search (struct super_block * sb, 658 struct ufs_cg_private_info * ucpi, unsigned goal, unsigned count) 659 { 660 struct ufs_sb_private_info * uspi; 661 struct ufs_super_block_first * usb1; 662 struct ufs_cylinder_group * ucg; 663 unsigned start, length, location, result; 664 unsigned possition, fragsize, blockmap, mask; 665 666 UFSD(("ENTER, cg %u, goal %u, count %u\n", ucpi->c_cgx, goal, count)) 667 668 uspi = UFS_SB(sb)->s_uspi; 669 usb1 = ubh_get_usb_first (USPI_UBH); 670 ucg = ubh_get_ucg(UCPI_UBH); 671 672 if (goal) 673 start = ufs_dtogd(goal) >> 3; 674 else 675 start = ucpi->c_frotor >> 3; 676 677 length = ((uspi->s_fpg + 7) >> 3) - start; 678 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff + start, length, 679 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other, 680 1 << (count - 1 + (uspi->s_fpb & 7))); 681 if (location == 0) { 682 length = start + 1; 683 location = ubh_scanc(UCPI_UBH, ucpi->c_freeoff, length, 684 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other, 685 1 << (count - 1 + (uspi->s_fpb & 7))); 686 if (location == 0) { 687 ufs_error (sb, "ufs_bitmap_search", 688 "bitmap corrupted on cg %u, start %u, length %u, count %u, freeoff %u\n", 689 ucpi->c_cgx, start, length, count, ucpi->c_freeoff); 690 return (unsigned)-1; 691 } 692 start = 0; 693 } 694 result = (start + length - location) << 3; 695 ucpi->c_frotor = result; 696 697 /* 698 * found the byte in the map 699 */ 700 blockmap = ubh_blkmap(UCPI_UBH, ucpi->c_freeoff, result); 701 fragsize = 0; 702 for (possition = 0, mask = 1; possition < 8; possition++, mask <<= 1) { 703 if (blockmap & mask) { 704 if (!(possition & uspi->s_fpbmask)) 705 fragsize = 1; 706 else 707 fragsize++; 708 } 709 else { 710 if (fragsize == count) { 711 result += possition - count; 712 UFSD(("EXIT, result %u\n", result)) 713 return result; 714 } 715 fragsize = 0; 716 } 717 } 718 if (fragsize == count) { 719 result += possition - count; 720 UFSD(("EXIT, result %u\n", result)) 721 return result; 722 } 723 ufs_error (sb, "ufs_bitmap_search", "block not in map on cg %u\n", ucpi->c_cgx); 724 UFSD(("EXIT (FAILED)\n")) 725 return (unsigned)-1; 726 } 727 728 static void ufs_clusteracct(struct super_block * sb, 729 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt) 730 { 731 struct ufs_sb_private_info * uspi; 732 int i, start, end, forw, back; 733 734 uspi = UFS_SB(sb)->s_uspi; 735 if (uspi->s_contigsumsize <= 0) 736 return; 737 738 if (cnt > 0) 739 ubh_setbit(UCPI_UBH, ucpi->c_clusteroff, blkno); 740 else 741 ubh_clrbit(UCPI_UBH, ucpi->c_clusteroff, blkno); 742 743 /* 744 * Find the size of the cluster going forward. 745 */ 746 start = blkno + 1; 747 end = start + uspi->s_contigsumsize; 748 if ( end >= ucpi->c_nclusterblks) 749 end = ucpi->c_nclusterblks; 750 i = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_clusteroff, end, start); 751 if (i > end) 752 i = end; 753 forw = i - start; 754 755 /* 756 * Find the size of the cluster going backward. 757 */ 758 start = blkno - 1; 759 end = start - uspi->s_contigsumsize; 760 if (end < 0 ) 761 end = -1; 762 i = ubh_find_last_zero_bit (UCPI_UBH, ucpi->c_clusteroff, start, end); 763 if ( i < end) 764 i = end; 765 back = start - i; 766 767 /* 768 * Account for old cluster and the possibly new forward and 769 * back clusters. 770 */ 771 i = back + forw + 1; 772 if (i > uspi->s_contigsumsize) 773 i = uspi->s_contigsumsize; 774 fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (i << 2)), cnt); 775 if (back > 0) 776 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (back << 2)), cnt); 777 if (forw > 0) 778 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH, ucpi->c_clustersumoff + (forw << 2)), cnt); 779 } 780 781 782 static unsigned char ufs_fragtable_8fpb[] = { 783 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08, 784 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10, 785 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 786 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20, 787 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 788 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11, 789 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A, 790 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40, 791 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 792 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11, 793 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09, 794 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21, 795 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A, 796 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12, 797 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C, 798 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80, 799 }; 800 801 static unsigned char ufs_fragtable_other[] = { 802 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A, 803 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 804 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 805 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA, 806 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 807 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 808 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE, 809 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE, 810 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 811 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 812 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E, 813 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE, 814 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA, 815 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE, 816 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE, 817 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A, 818 }; 819