1 /* 2 * balloc.c 3 * 4 * PURPOSE 5 * Block allocation handling routines for the OSTA-UDF(tm) filesystem. 6 * 7 * COPYRIGHT 8 * This file is distributed under the terms of the GNU General Public 9 * License (GPL). Copies of the GPL can be obtained from: 10 * ftp://prep.ai.mit.edu/pub/gnu/GPL 11 * Each contributing author retains all rights to their own work. 12 * 13 * (C) 1999-2001 Ben Fennema 14 * (C) 1999 Stelias Computing Inc 15 * 16 * HISTORY 17 * 18 * 02/24/99 blf Created. 19 * 20 */ 21 22 #include "udfdecl.h" 23 24 #include <linux/quotaops.h> 25 #include <linux/buffer_head.h> 26 #include <linux/bitops.h> 27 28 #include "udf_i.h" 29 #include "udf_sb.h" 30 31 #define udf_clear_bit(nr, addr) ext2_clear_bit(nr, addr) 32 #define udf_set_bit(nr, addr) ext2_set_bit(nr, addr) 33 #define udf_test_bit(nr, addr) ext2_test_bit(nr, addr) 34 #define udf_find_first_one_bit(addr, size) find_first_one_bit(addr, size) 35 #define udf_find_next_one_bit(addr, size, offset) \ 36 find_next_one_bit(addr, size, offset) 37 38 #define leBPL_to_cpup(x) leNUM_to_cpup(BITS_PER_LONG, x) 39 #define leNUM_to_cpup(x, y) xleNUM_to_cpup(x, y) 40 #define xleNUM_to_cpup(x, y) (le ## x ## _to_cpup(y)) 41 #define uintBPL_t uint(BITS_PER_LONG) 42 #define uint(x) xuint(x) 43 #define xuint(x) __le ## x 44 45 static inline int find_next_one_bit(void *addr, int size, int offset) 46 { 47 uintBPL_t *p = ((uintBPL_t *) addr) + (offset / BITS_PER_LONG); 48 int result = offset & ~(BITS_PER_LONG - 1); 49 unsigned long tmp; 50 51 if (offset >= size) 52 return size; 53 size -= result; 54 offset &= (BITS_PER_LONG - 1); 55 if (offset) { 56 tmp = leBPL_to_cpup(p++); 57 tmp &= ~0UL << offset; 58 if (size < BITS_PER_LONG) 59 goto found_first; 60 if (tmp) 61 goto found_middle; 62 size -= BITS_PER_LONG; 63 result += BITS_PER_LONG; 64 } 65 while (size & ~(BITS_PER_LONG - 1)) { 66 tmp = leBPL_to_cpup(p++); 67 if (tmp) 68 goto found_middle; 69 result += BITS_PER_LONG; 70 size -= BITS_PER_LONG; 71 } 72 if (!size) 73 return result; 74 tmp = leBPL_to_cpup(p); 75 found_first: 76 tmp &= ~0UL >> (BITS_PER_LONG - size); 77 found_middle: 78 return result + ffz(~tmp); 79 } 80 81 #define find_first_one_bit(addr, size)\ 82 find_next_one_bit((addr), (size), 0) 83 84 static int read_block_bitmap(struct super_block *sb, 85 struct udf_bitmap *bitmap, unsigned int block, 86 unsigned long bitmap_nr) 87 { 88 struct buffer_head *bh = NULL; 89 int retval = 0; 90 struct kernel_lb_addr loc; 91 92 loc.logicalBlockNum = bitmap->s_extPosition; 93 loc.partitionReferenceNum = UDF_SB(sb)->s_partition; 94 95 bh = udf_tread(sb, udf_get_lb_pblock(sb, &loc, block)); 96 if (!bh) 97 retval = -EIO; 98 99 bitmap->s_block_bitmap[bitmap_nr] = bh; 100 return retval; 101 } 102 103 static int __load_block_bitmap(struct super_block *sb, 104 struct udf_bitmap *bitmap, 105 unsigned int block_group) 106 { 107 int retval = 0; 108 int nr_groups = bitmap->s_nr_groups; 109 110 if (block_group >= nr_groups) { 111 udf_debug("block_group (%d) > nr_groups (%d)\n", block_group, 112 nr_groups); 113 } 114 115 if (bitmap->s_block_bitmap[block_group]) { 116 return block_group; 117 } else { 118 retval = read_block_bitmap(sb, bitmap, block_group, 119 block_group); 120 if (retval < 0) 121 return retval; 122 return block_group; 123 } 124 } 125 126 static inline int load_block_bitmap(struct super_block *sb, 127 struct udf_bitmap *bitmap, 128 unsigned int block_group) 129 { 130 int slot; 131 132 slot = __load_block_bitmap(sb, bitmap, block_group); 133 134 if (slot < 0) 135 return slot; 136 137 if (!bitmap->s_block_bitmap[slot]) 138 return -EIO; 139 140 return slot; 141 } 142 143 static void udf_add_free_space(struct super_block *sb, u16 partition, u32 cnt) 144 { 145 struct udf_sb_info *sbi = UDF_SB(sb); 146 struct logicalVolIntegrityDesc *lvid; 147 148 if (!sbi->s_lvid_bh) 149 return; 150 151 lvid = (struct logicalVolIntegrityDesc *)sbi->s_lvid_bh->b_data; 152 le32_add_cpu(&lvid->freeSpaceTable[partition], cnt); 153 udf_updated_lvid(sb); 154 } 155 156 static void udf_bitmap_free_blocks(struct super_block *sb, 157 struct inode *inode, 158 struct udf_bitmap *bitmap, 159 struct kernel_lb_addr *bloc, 160 uint32_t offset, 161 uint32_t count) 162 { 163 struct udf_sb_info *sbi = UDF_SB(sb); 164 struct buffer_head *bh = NULL; 165 struct udf_part_map *partmap; 166 unsigned long block; 167 unsigned long block_group; 168 unsigned long bit; 169 unsigned long i; 170 int bitmap_nr; 171 unsigned long overflow; 172 173 mutex_lock(&sbi->s_alloc_mutex); 174 partmap = &sbi->s_partmaps[bloc->partitionReferenceNum]; 175 if (bloc->logicalBlockNum < 0 || 176 (bloc->logicalBlockNum + count) > 177 partmap->s_partition_len) { 178 udf_debug("%d < %d || %d + %d > %d\n", 179 bloc->logicalBlockNum, 0, bloc->logicalBlockNum, 180 count, partmap->s_partition_len); 181 goto error_return; 182 } 183 184 block = bloc->logicalBlockNum + offset + 185 (sizeof(struct spaceBitmapDesc) << 3); 186 187 do { 188 overflow = 0; 189 block_group = block >> (sb->s_blocksize_bits + 3); 190 bit = block % (sb->s_blocksize << 3); 191 192 /* 193 * Check to see if we are freeing blocks across a group boundary. 194 */ 195 if (bit + count > (sb->s_blocksize << 3)) { 196 overflow = bit + count - (sb->s_blocksize << 3); 197 count -= overflow; 198 } 199 bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 200 if (bitmap_nr < 0) 201 goto error_return; 202 203 bh = bitmap->s_block_bitmap[bitmap_nr]; 204 for (i = 0; i < count; i++) { 205 if (udf_set_bit(bit + i, bh->b_data)) { 206 udf_debug("bit %ld already set\n", bit + i); 207 udf_debug("byte=%2x\n", 208 ((char *)bh->b_data)[(bit + i) >> 3]); 209 } else { 210 if (inode) 211 dquot_free_block(inode, 1); 212 udf_add_free_space(sb, sbi->s_partition, 1); 213 } 214 } 215 mark_buffer_dirty(bh); 216 if (overflow) { 217 block += count; 218 count = overflow; 219 } 220 } while (overflow); 221 222 error_return: 223 mutex_unlock(&sbi->s_alloc_mutex); 224 } 225 226 static int udf_bitmap_prealloc_blocks(struct super_block *sb, 227 struct inode *inode, 228 struct udf_bitmap *bitmap, 229 uint16_t partition, uint32_t first_block, 230 uint32_t block_count) 231 { 232 struct udf_sb_info *sbi = UDF_SB(sb); 233 int alloc_count = 0; 234 int bit, block, block_group, group_start; 235 int nr_groups, bitmap_nr; 236 struct buffer_head *bh; 237 __u32 part_len; 238 239 mutex_lock(&sbi->s_alloc_mutex); 240 part_len = sbi->s_partmaps[partition].s_partition_len; 241 if (first_block >= part_len) 242 goto out; 243 244 if (first_block + block_count > part_len) 245 block_count = part_len - first_block; 246 247 do { 248 nr_groups = udf_compute_nr_groups(sb, partition); 249 block = first_block + (sizeof(struct spaceBitmapDesc) << 3); 250 block_group = block >> (sb->s_blocksize_bits + 3); 251 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 252 253 bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 254 if (bitmap_nr < 0) 255 goto out; 256 bh = bitmap->s_block_bitmap[bitmap_nr]; 257 258 bit = block % (sb->s_blocksize << 3); 259 260 while (bit < (sb->s_blocksize << 3) && block_count > 0) { 261 if (!udf_test_bit(bit, bh->b_data)) 262 goto out; 263 else if (dquot_prealloc_block(inode, 1)) 264 goto out; 265 else if (!udf_clear_bit(bit, bh->b_data)) { 266 udf_debug("bit already cleared for block %d\n", bit); 267 dquot_free_block(inode, 1); 268 goto out; 269 } 270 block_count--; 271 alloc_count++; 272 bit++; 273 block++; 274 } 275 mark_buffer_dirty(bh); 276 } while (block_count > 0); 277 278 out: 279 udf_add_free_space(sb, partition, -alloc_count); 280 mutex_unlock(&sbi->s_alloc_mutex); 281 return alloc_count; 282 } 283 284 static int udf_bitmap_new_block(struct super_block *sb, 285 struct inode *inode, 286 struct udf_bitmap *bitmap, uint16_t partition, 287 uint32_t goal, int *err) 288 { 289 struct udf_sb_info *sbi = UDF_SB(sb); 290 int newbit, bit = 0, block, block_group, group_start; 291 int end_goal, nr_groups, bitmap_nr, i; 292 struct buffer_head *bh = NULL; 293 char *ptr; 294 int newblock = 0; 295 296 *err = -ENOSPC; 297 mutex_lock(&sbi->s_alloc_mutex); 298 299 repeat: 300 if (goal >= sbi->s_partmaps[partition].s_partition_len) 301 goal = 0; 302 303 nr_groups = bitmap->s_nr_groups; 304 block = goal + (sizeof(struct spaceBitmapDesc) << 3); 305 block_group = block >> (sb->s_blocksize_bits + 3); 306 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 307 308 bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 309 if (bitmap_nr < 0) 310 goto error_return; 311 bh = bitmap->s_block_bitmap[bitmap_nr]; 312 ptr = memscan((char *)bh->b_data + group_start, 0xFF, 313 sb->s_blocksize - group_start); 314 315 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) { 316 bit = block % (sb->s_blocksize << 3); 317 if (udf_test_bit(bit, bh->b_data)) 318 goto got_block; 319 320 end_goal = (bit + 63) & ~63; 321 bit = udf_find_next_one_bit(bh->b_data, end_goal, bit); 322 if (bit < end_goal) 323 goto got_block; 324 325 ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF, 326 sb->s_blocksize - ((bit + 7) >> 3)); 327 newbit = (ptr - ((char *)bh->b_data)) << 3; 328 if (newbit < sb->s_blocksize << 3) { 329 bit = newbit; 330 goto search_back; 331 } 332 333 newbit = udf_find_next_one_bit(bh->b_data, 334 sb->s_blocksize << 3, bit); 335 if (newbit < sb->s_blocksize << 3) { 336 bit = newbit; 337 goto got_block; 338 } 339 } 340 341 for (i = 0; i < (nr_groups * 2); i++) { 342 block_group++; 343 if (block_group >= nr_groups) 344 block_group = 0; 345 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 346 347 bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 348 if (bitmap_nr < 0) 349 goto error_return; 350 bh = bitmap->s_block_bitmap[bitmap_nr]; 351 if (i < nr_groups) { 352 ptr = memscan((char *)bh->b_data + group_start, 0xFF, 353 sb->s_blocksize - group_start); 354 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) { 355 bit = (ptr - ((char *)bh->b_data)) << 3; 356 break; 357 } 358 } else { 359 bit = udf_find_next_one_bit((char *)bh->b_data, 360 sb->s_blocksize << 3, 361 group_start << 3); 362 if (bit < sb->s_blocksize << 3) 363 break; 364 } 365 } 366 if (i >= (nr_groups * 2)) { 367 mutex_unlock(&sbi->s_alloc_mutex); 368 return newblock; 369 } 370 if (bit < sb->s_blocksize << 3) 371 goto search_back; 372 else 373 bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, 374 group_start << 3); 375 if (bit >= sb->s_blocksize << 3) { 376 mutex_unlock(&sbi->s_alloc_mutex); 377 return 0; 378 } 379 380 search_back: 381 i = 0; 382 while (i < 7 && bit > (group_start << 3) && 383 udf_test_bit(bit - 1, bh->b_data)) { 384 ++i; 385 --bit; 386 } 387 388 got_block: 389 390 /* 391 * Check quota for allocation of this block. 392 */ 393 if (inode) { 394 int ret = dquot_alloc_block(inode, 1); 395 396 if (ret) { 397 mutex_unlock(&sbi->s_alloc_mutex); 398 *err = ret; 399 return 0; 400 } 401 } 402 403 newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) - 404 (sizeof(struct spaceBitmapDesc) << 3); 405 406 if (!udf_clear_bit(bit, bh->b_data)) { 407 udf_debug("bit already cleared for block %d\n", bit); 408 goto repeat; 409 } 410 411 mark_buffer_dirty(bh); 412 413 udf_add_free_space(sb, partition, -1); 414 mutex_unlock(&sbi->s_alloc_mutex); 415 *err = 0; 416 return newblock; 417 418 error_return: 419 *err = -EIO; 420 mutex_unlock(&sbi->s_alloc_mutex); 421 return 0; 422 } 423 424 static void udf_table_free_blocks(struct super_block *sb, 425 struct inode *inode, 426 struct inode *table, 427 struct kernel_lb_addr *bloc, 428 uint32_t offset, 429 uint32_t count) 430 { 431 struct udf_sb_info *sbi = UDF_SB(sb); 432 struct udf_part_map *partmap; 433 uint32_t start, end; 434 uint32_t elen; 435 struct kernel_lb_addr eloc; 436 struct extent_position oepos, epos; 437 int8_t etype; 438 int i; 439 struct udf_inode_info *iinfo; 440 441 mutex_lock(&sbi->s_alloc_mutex); 442 partmap = &sbi->s_partmaps[bloc->partitionReferenceNum]; 443 if (bloc->logicalBlockNum < 0 || 444 (bloc->logicalBlockNum + count) > 445 partmap->s_partition_len) { 446 udf_debug("%d < %d || %d + %d > %d\n", 447 bloc->logicalBlockNum, 0, bloc->logicalBlockNum, count, 448 partmap->s_partition_len); 449 goto error_return; 450 } 451 452 iinfo = UDF_I(table); 453 /* We do this up front - There are some error conditions that 454 could occure, but.. oh well */ 455 if (inode) 456 dquot_free_block(inode, count); 457 udf_add_free_space(sb, sbi->s_partition, count); 458 459 start = bloc->logicalBlockNum + offset; 460 end = bloc->logicalBlockNum + offset + count - 1; 461 462 epos.offset = oepos.offset = sizeof(struct unallocSpaceEntry); 463 elen = 0; 464 epos.block = oepos.block = iinfo->i_location; 465 epos.bh = oepos.bh = NULL; 466 467 while (count && 468 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 469 if (((eloc.logicalBlockNum + 470 (elen >> sb->s_blocksize_bits)) == start)) { 471 if ((0x3FFFFFFF - elen) < 472 (count << sb->s_blocksize_bits)) { 473 uint32_t tmp = ((0x3FFFFFFF - elen) >> 474 sb->s_blocksize_bits); 475 count -= tmp; 476 start += tmp; 477 elen = (etype << 30) | 478 (0x40000000 - sb->s_blocksize); 479 } else { 480 elen = (etype << 30) | 481 (elen + 482 (count << sb->s_blocksize_bits)); 483 start += count; 484 count = 0; 485 } 486 udf_write_aext(table, &oepos, &eloc, elen, 1); 487 } else if (eloc.logicalBlockNum == (end + 1)) { 488 if ((0x3FFFFFFF - elen) < 489 (count << sb->s_blocksize_bits)) { 490 uint32_t tmp = ((0x3FFFFFFF - elen) >> 491 sb->s_blocksize_bits); 492 count -= tmp; 493 end -= tmp; 494 eloc.logicalBlockNum -= tmp; 495 elen = (etype << 30) | 496 (0x40000000 - sb->s_blocksize); 497 } else { 498 eloc.logicalBlockNum = start; 499 elen = (etype << 30) | 500 (elen + 501 (count << sb->s_blocksize_bits)); 502 end -= count; 503 count = 0; 504 } 505 udf_write_aext(table, &oepos, &eloc, elen, 1); 506 } 507 508 if (epos.bh != oepos.bh) { 509 i = -1; 510 oepos.block = epos.block; 511 brelse(oepos.bh); 512 get_bh(epos.bh); 513 oepos.bh = epos.bh; 514 oepos.offset = 0; 515 } else { 516 oepos.offset = epos.offset; 517 } 518 } 519 520 if (count) { 521 /* 522 * NOTE: we CANNOT use udf_add_aext here, as it can try to 523 * allocate a new block, and since we hold the super block 524 * lock already very bad things would happen :) 525 * 526 * We copy the behavior of udf_add_aext, but instead of 527 * trying to allocate a new block close to the existing one, 528 * we just steal a block from the extent we are trying to add. 529 * 530 * It would be nice if the blocks were close together, but it 531 * isn't required. 532 */ 533 534 int adsize; 535 struct short_ad *sad = NULL; 536 struct long_ad *lad = NULL; 537 struct allocExtDesc *aed; 538 539 eloc.logicalBlockNum = start; 540 elen = EXT_RECORDED_ALLOCATED | 541 (count << sb->s_blocksize_bits); 542 543 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 544 adsize = sizeof(struct short_ad); 545 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 546 adsize = sizeof(struct long_ad); 547 else { 548 brelse(oepos.bh); 549 brelse(epos.bh); 550 goto error_return; 551 } 552 553 if (epos.offset + (2 * adsize) > sb->s_blocksize) { 554 unsigned char *sptr, *dptr; 555 int loffset; 556 557 brelse(oepos.bh); 558 oepos = epos; 559 560 /* Steal a block from the extent being free'd */ 561 epos.block.logicalBlockNum = eloc.logicalBlockNum; 562 eloc.logicalBlockNum++; 563 elen -= sb->s_blocksize; 564 565 epos.bh = udf_tread(sb, 566 udf_get_lb_pblock(sb, &epos.block, 0)); 567 if (!epos.bh) { 568 brelse(oepos.bh); 569 goto error_return; 570 } 571 aed = (struct allocExtDesc *)(epos.bh->b_data); 572 aed->previousAllocExtLocation = 573 cpu_to_le32(oepos.block.logicalBlockNum); 574 if (epos.offset + adsize > sb->s_blocksize) { 575 loffset = epos.offset; 576 aed->lengthAllocDescs = cpu_to_le32(adsize); 577 sptr = iinfo->i_ext.i_data + epos.offset 578 - adsize; 579 dptr = epos.bh->b_data + 580 sizeof(struct allocExtDesc); 581 memcpy(dptr, sptr, adsize); 582 epos.offset = sizeof(struct allocExtDesc) + 583 adsize; 584 } else { 585 loffset = epos.offset + adsize; 586 aed->lengthAllocDescs = cpu_to_le32(0); 587 if (oepos.bh) { 588 sptr = oepos.bh->b_data + epos.offset; 589 aed = (struct allocExtDesc *) 590 oepos.bh->b_data; 591 le32_add_cpu(&aed->lengthAllocDescs, 592 adsize); 593 } else { 594 sptr = iinfo->i_ext.i_data + 595 epos.offset; 596 iinfo->i_lenAlloc += adsize; 597 mark_inode_dirty(table); 598 } 599 epos.offset = sizeof(struct allocExtDesc); 600 } 601 if (sbi->s_udfrev >= 0x0200) 602 udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, 603 3, 1, epos.block.logicalBlockNum, 604 sizeof(struct tag)); 605 else 606 udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, 607 2, 1, epos.block.logicalBlockNum, 608 sizeof(struct tag)); 609 610 switch (iinfo->i_alloc_type) { 611 case ICBTAG_FLAG_AD_SHORT: 612 sad = (struct short_ad *)sptr; 613 sad->extLength = cpu_to_le32( 614 EXT_NEXT_EXTENT_ALLOCDECS | 615 sb->s_blocksize); 616 sad->extPosition = 617 cpu_to_le32(epos.block.logicalBlockNum); 618 break; 619 case ICBTAG_FLAG_AD_LONG: 620 lad = (struct long_ad *)sptr; 621 lad->extLength = cpu_to_le32( 622 EXT_NEXT_EXTENT_ALLOCDECS | 623 sb->s_blocksize); 624 lad->extLocation = 625 cpu_to_lelb(epos.block); 626 break; 627 } 628 if (oepos.bh) { 629 udf_update_tag(oepos.bh->b_data, loffset); 630 mark_buffer_dirty(oepos.bh); 631 } else { 632 mark_inode_dirty(table); 633 } 634 } 635 636 /* It's possible that stealing the block emptied the extent */ 637 if (elen) { 638 udf_write_aext(table, &epos, &eloc, elen, 1); 639 640 if (!epos.bh) { 641 iinfo->i_lenAlloc += adsize; 642 mark_inode_dirty(table); 643 } else { 644 aed = (struct allocExtDesc *)epos.bh->b_data; 645 le32_add_cpu(&aed->lengthAllocDescs, adsize); 646 udf_update_tag(epos.bh->b_data, epos.offset); 647 mark_buffer_dirty(epos.bh); 648 } 649 } 650 } 651 652 brelse(epos.bh); 653 brelse(oepos.bh); 654 655 error_return: 656 mutex_unlock(&sbi->s_alloc_mutex); 657 return; 658 } 659 660 static int udf_table_prealloc_blocks(struct super_block *sb, 661 struct inode *inode, 662 struct inode *table, uint16_t partition, 663 uint32_t first_block, uint32_t block_count) 664 { 665 struct udf_sb_info *sbi = UDF_SB(sb); 666 int alloc_count = 0; 667 uint32_t elen, adsize; 668 struct kernel_lb_addr eloc; 669 struct extent_position epos; 670 int8_t etype = -1; 671 struct udf_inode_info *iinfo; 672 673 if (first_block >= sbi->s_partmaps[partition].s_partition_len) 674 return 0; 675 676 iinfo = UDF_I(table); 677 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 678 adsize = sizeof(struct short_ad); 679 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 680 adsize = sizeof(struct long_ad); 681 else 682 return 0; 683 684 mutex_lock(&sbi->s_alloc_mutex); 685 epos.offset = sizeof(struct unallocSpaceEntry); 686 epos.block = iinfo->i_location; 687 epos.bh = NULL; 688 eloc.logicalBlockNum = 0xFFFFFFFF; 689 690 while (first_block != eloc.logicalBlockNum && 691 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 692 udf_debug("eloc=%d, elen=%d, first_block=%d\n", 693 eloc.logicalBlockNum, elen, first_block); 694 ; /* empty loop body */ 695 } 696 697 if (first_block == eloc.logicalBlockNum) { 698 epos.offset -= adsize; 699 700 alloc_count = (elen >> sb->s_blocksize_bits); 701 if (inode && dquot_prealloc_block(inode, 702 alloc_count > block_count ? block_count : alloc_count)) 703 alloc_count = 0; 704 else if (alloc_count > block_count) { 705 alloc_count = block_count; 706 eloc.logicalBlockNum += alloc_count; 707 elen -= (alloc_count << sb->s_blocksize_bits); 708 udf_write_aext(table, &epos, &eloc, 709 (etype << 30) | elen, 1); 710 } else 711 udf_delete_aext(table, epos, eloc, 712 (etype << 30) | elen); 713 } else { 714 alloc_count = 0; 715 } 716 717 brelse(epos.bh); 718 719 if (alloc_count) 720 udf_add_free_space(sb, partition, -alloc_count); 721 mutex_unlock(&sbi->s_alloc_mutex); 722 return alloc_count; 723 } 724 725 static int udf_table_new_block(struct super_block *sb, 726 struct inode *inode, 727 struct inode *table, uint16_t partition, 728 uint32_t goal, int *err) 729 { 730 struct udf_sb_info *sbi = UDF_SB(sb); 731 uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF; 732 uint32_t newblock = 0, adsize; 733 uint32_t elen, goal_elen = 0; 734 struct kernel_lb_addr eloc, uninitialized_var(goal_eloc); 735 struct extent_position epos, goal_epos; 736 int8_t etype; 737 struct udf_inode_info *iinfo = UDF_I(table); 738 739 *err = -ENOSPC; 740 741 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 742 adsize = sizeof(struct short_ad); 743 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 744 adsize = sizeof(struct long_ad); 745 else 746 return newblock; 747 748 mutex_lock(&sbi->s_alloc_mutex); 749 if (goal >= sbi->s_partmaps[partition].s_partition_len) 750 goal = 0; 751 752 /* We search for the closest matching block to goal. If we find 753 a exact hit, we stop. Otherwise we keep going till we run out 754 of extents. We store the buffer_head, bloc, and extoffset 755 of the current closest match and use that when we are done. 756 */ 757 epos.offset = sizeof(struct unallocSpaceEntry); 758 epos.block = iinfo->i_location; 759 epos.bh = goal_epos.bh = NULL; 760 761 while (spread && 762 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 763 if (goal >= eloc.logicalBlockNum) { 764 if (goal < eloc.logicalBlockNum + 765 (elen >> sb->s_blocksize_bits)) 766 nspread = 0; 767 else 768 nspread = goal - eloc.logicalBlockNum - 769 (elen >> sb->s_blocksize_bits); 770 } else { 771 nspread = eloc.logicalBlockNum - goal; 772 } 773 774 if (nspread < spread) { 775 spread = nspread; 776 if (goal_epos.bh != epos.bh) { 777 brelse(goal_epos.bh); 778 goal_epos.bh = epos.bh; 779 get_bh(goal_epos.bh); 780 } 781 goal_epos.block = epos.block; 782 goal_epos.offset = epos.offset - adsize; 783 goal_eloc = eloc; 784 goal_elen = (etype << 30) | elen; 785 } 786 } 787 788 brelse(epos.bh); 789 790 if (spread == 0xFFFFFFFF) { 791 brelse(goal_epos.bh); 792 mutex_unlock(&sbi->s_alloc_mutex); 793 return 0; 794 } 795 796 /* Only allocate blocks from the beginning of the extent. 797 That way, we only delete (empty) extents, never have to insert an 798 extent because of splitting */ 799 /* This works, but very poorly.... */ 800 801 newblock = goal_eloc.logicalBlockNum; 802 goal_eloc.logicalBlockNum++; 803 goal_elen -= sb->s_blocksize; 804 if (inode) { 805 *err = dquot_alloc_block(inode, 1); 806 if (*err) { 807 brelse(goal_epos.bh); 808 mutex_unlock(&sbi->s_alloc_mutex); 809 return 0; 810 } 811 } 812 813 if (goal_elen) 814 udf_write_aext(table, &goal_epos, &goal_eloc, goal_elen, 1); 815 else 816 udf_delete_aext(table, goal_epos, goal_eloc, goal_elen); 817 brelse(goal_epos.bh); 818 819 udf_add_free_space(sb, partition, -1); 820 821 mutex_unlock(&sbi->s_alloc_mutex); 822 *err = 0; 823 return newblock; 824 } 825 826 void udf_free_blocks(struct super_block *sb, struct inode *inode, 827 struct kernel_lb_addr *bloc, uint32_t offset, 828 uint32_t count) 829 { 830 uint16_t partition = bloc->partitionReferenceNum; 831 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 832 833 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) { 834 udf_bitmap_free_blocks(sb, inode, map->s_uspace.s_bitmap, 835 bloc, offset, count); 836 } else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) { 837 udf_table_free_blocks(sb, inode, map->s_uspace.s_table, 838 bloc, offset, count); 839 } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) { 840 udf_bitmap_free_blocks(sb, inode, map->s_fspace.s_bitmap, 841 bloc, offset, count); 842 } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) { 843 udf_table_free_blocks(sb, inode, map->s_fspace.s_table, 844 bloc, offset, count); 845 } 846 } 847 848 inline int udf_prealloc_blocks(struct super_block *sb, 849 struct inode *inode, 850 uint16_t partition, uint32_t first_block, 851 uint32_t block_count) 852 { 853 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 854 855 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) 856 return udf_bitmap_prealloc_blocks(sb, inode, 857 map->s_uspace.s_bitmap, 858 partition, first_block, 859 block_count); 860 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) 861 return udf_table_prealloc_blocks(sb, inode, 862 map->s_uspace.s_table, 863 partition, first_block, 864 block_count); 865 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) 866 return udf_bitmap_prealloc_blocks(sb, inode, 867 map->s_fspace.s_bitmap, 868 partition, first_block, 869 block_count); 870 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) 871 return udf_table_prealloc_blocks(sb, inode, 872 map->s_fspace.s_table, 873 partition, first_block, 874 block_count); 875 else 876 return 0; 877 } 878 879 inline int udf_new_block(struct super_block *sb, 880 struct inode *inode, 881 uint16_t partition, uint32_t goal, int *err) 882 { 883 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 884 885 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) 886 return udf_bitmap_new_block(sb, inode, 887 map->s_uspace.s_bitmap, 888 partition, goal, err); 889 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) 890 return udf_table_new_block(sb, inode, 891 map->s_uspace.s_table, 892 partition, goal, err); 893 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) 894 return udf_bitmap_new_block(sb, inode, 895 map->s_fspace.s_bitmap, 896 partition, goal, err); 897 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) 898 return udf_table_new_block(sb, inode, 899 map->s_fspace.s_table, 900 partition, goal, err); 901 else { 902 *err = -EIO; 903 return 0; 904 } 905 } 906