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 vfs_dq_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 (vfs_dq_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 vfs_dq_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 && vfs_dq_alloc_block(inode, 1)) { 394 mutex_unlock(&sbi->s_alloc_mutex); 395 *err = -EDQUOT; 396 return 0; 397 } 398 399 newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) - 400 (sizeof(struct spaceBitmapDesc) << 3); 401 402 if (!udf_clear_bit(bit, bh->b_data)) { 403 udf_debug("bit already cleared for block %d\n", bit); 404 goto repeat; 405 } 406 407 mark_buffer_dirty(bh); 408 409 udf_add_free_space(sb, partition, -1); 410 mutex_unlock(&sbi->s_alloc_mutex); 411 *err = 0; 412 return newblock; 413 414 error_return: 415 *err = -EIO; 416 mutex_unlock(&sbi->s_alloc_mutex); 417 return 0; 418 } 419 420 static void udf_table_free_blocks(struct super_block *sb, 421 struct inode *inode, 422 struct inode *table, 423 struct kernel_lb_addr *bloc, 424 uint32_t offset, 425 uint32_t count) 426 { 427 struct udf_sb_info *sbi = UDF_SB(sb); 428 struct udf_part_map *partmap; 429 uint32_t start, end; 430 uint32_t elen; 431 struct kernel_lb_addr eloc; 432 struct extent_position oepos, epos; 433 int8_t etype; 434 int i; 435 struct udf_inode_info *iinfo; 436 437 mutex_lock(&sbi->s_alloc_mutex); 438 partmap = &sbi->s_partmaps[bloc->partitionReferenceNum]; 439 if (bloc->logicalBlockNum < 0 || 440 (bloc->logicalBlockNum + count) > 441 partmap->s_partition_len) { 442 udf_debug("%d < %d || %d + %d > %d\n", 443 bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count, 444 partmap->s_partition_len); 445 goto error_return; 446 } 447 448 iinfo = UDF_I(table); 449 /* We do this up front - There are some error conditions that 450 could occure, but.. oh well */ 451 if (inode) 452 vfs_dq_free_block(inode, count); 453 udf_add_free_space(sb, sbi->s_partition, count); 454 455 start = bloc->logicalBlockNum + offset; 456 end = bloc->logicalBlockNum + offset + count - 1; 457 458 epos.offset = oepos.offset = sizeof(struct unallocSpaceEntry); 459 elen = 0; 460 epos.block = oepos.block = iinfo->i_location; 461 epos.bh = oepos.bh = NULL; 462 463 while (count && 464 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 465 if (((eloc.logicalBlockNum + 466 (elen >> sb->s_blocksize_bits)) == start)) { 467 if ((0x3FFFFFFF - elen) < 468 (count << sb->s_blocksize_bits)) { 469 uint32_t tmp = ((0x3FFFFFFF - elen) >> 470 sb->s_blocksize_bits); 471 count -= tmp; 472 start += tmp; 473 elen = (etype << 30) | 474 (0x40000000 - sb->s_blocksize); 475 } else { 476 elen = (etype << 30) | 477 (elen + 478 (count << sb->s_blocksize_bits)); 479 start += count; 480 count = 0; 481 } 482 udf_write_aext(table, &oepos, &eloc, elen, 1); 483 } else if (eloc.logicalBlockNum == (end + 1)) { 484 if ((0x3FFFFFFF - elen) < 485 (count << sb->s_blocksize_bits)) { 486 uint32_t tmp = ((0x3FFFFFFF - elen) >> 487 sb->s_blocksize_bits); 488 count -= tmp; 489 end -= tmp; 490 eloc.logicalBlockNum -= tmp; 491 elen = (etype << 30) | 492 (0x40000000 - sb->s_blocksize); 493 } else { 494 eloc.logicalBlockNum = start; 495 elen = (etype << 30) | 496 (elen + 497 (count << sb->s_blocksize_bits)); 498 end -= count; 499 count = 0; 500 } 501 udf_write_aext(table, &oepos, &eloc, elen, 1); 502 } 503 504 if (epos.bh != oepos.bh) { 505 i = -1; 506 oepos.block = epos.block; 507 brelse(oepos.bh); 508 get_bh(epos.bh); 509 oepos.bh = epos.bh; 510 oepos.offset = 0; 511 } else { 512 oepos.offset = epos.offset; 513 } 514 } 515 516 if (count) { 517 /* 518 * NOTE: we CANNOT use udf_add_aext here, as it can try to 519 * allocate a new block, and since we hold the super block 520 * lock already very bad things would happen :) 521 * 522 * We copy the behavior of udf_add_aext, but instead of 523 * trying to allocate a new block close to the existing one, 524 * we just steal a block from the extent we are trying to add. 525 * 526 * It would be nice if the blocks were close together, but it 527 * isn't required. 528 */ 529 530 int adsize; 531 struct short_ad *sad = NULL; 532 struct long_ad *lad = NULL; 533 struct allocExtDesc *aed; 534 535 eloc.logicalBlockNum = start; 536 elen = EXT_RECORDED_ALLOCATED | 537 (count << sb->s_blocksize_bits); 538 539 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 540 adsize = sizeof(struct short_ad); 541 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 542 adsize = sizeof(struct long_ad); 543 else { 544 brelse(oepos.bh); 545 brelse(epos.bh); 546 goto error_return; 547 } 548 549 if (epos.offset + (2 * adsize) > sb->s_blocksize) { 550 char *sptr, *dptr; 551 int loffset; 552 553 brelse(oepos.bh); 554 oepos = epos; 555 556 /* Steal a block from the extent being free'd */ 557 epos.block.logicalBlockNum = eloc.logicalBlockNum; 558 eloc.logicalBlockNum++; 559 elen -= sb->s_blocksize; 560 561 epos.bh = udf_tread(sb, 562 udf_get_lb_pblock(sb, &epos.block, 0)); 563 if (!epos.bh) { 564 brelse(oepos.bh); 565 goto error_return; 566 } 567 aed = (struct allocExtDesc *)(epos.bh->b_data); 568 aed->previousAllocExtLocation = 569 cpu_to_le32(oepos.block.logicalBlockNum); 570 if (epos.offset + adsize > sb->s_blocksize) { 571 loffset = epos.offset; 572 aed->lengthAllocDescs = cpu_to_le32(adsize); 573 sptr = iinfo->i_ext.i_data + epos.offset 574 - adsize; 575 dptr = epos.bh->b_data + 576 sizeof(struct allocExtDesc); 577 memcpy(dptr, sptr, adsize); 578 epos.offset = sizeof(struct allocExtDesc) + 579 adsize; 580 } else { 581 loffset = epos.offset + adsize; 582 aed->lengthAllocDescs = cpu_to_le32(0); 583 if (oepos.bh) { 584 sptr = oepos.bh->b_data + epos.offset; 585 aed = (struct allocExtDesc *) 586 oepos.bh->b_data; 587 le32_add_cpu(&aed->lengthAllocDescs, 588 adsize); 589 } else { 590 sptr = iinfo->i_ext.i_data + 591 epos.offset; 592 iinfo->i_lenAlloc += adsize; 593 mark_inode_dirty(table); 594 } 595 epos.offset = sizeof(struct allocExtDesc); 596 } 597 if (sbi->s_udfrev >= 0x0200) 598 udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, 599 3, 1, epos.block.logicalBlockNum, 600 sizeof(struct tag)); 601 else 602 udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, 603 2, 1, epos.block.logicalBlockNum, 604 sizeof(struct tag)); 605 606 switch (iinfo->i_alloc_type) { 607 case ICBTAG_FLAG_AD_SHORT: 608 sad = (struct short_ad *)sptr; 609 sad->extLength = cpu_to_le32( 610 EXT_NEXT_EXTENT_ALLOCDECS | 611 sb->s_blocksize); 612 sad->extPosition = 613 cpu_to_le32(epos.block.logicalBlockNum); 614 break; 615 case ICBTAG_FLAG_AD_LONG: 616 lad = (struct long_ad *)sptr; 617 lad->extLength = cpu_to_le32( 618 EXT_NEXT_EXTENT_ALLOCDECS | 619 sb->s_blocksize); 620 lad->extLocation = 621 cpu_to_lelb(epos.block); 622 break; 623 } 624 if (oepos.bh) { 625 udf_update_tag(oepos.bh->b_data, loffset); 626 mark_buffer_dirty(oepos.bh); 627 } else { 628 mark_inode_dirty(table); 629 } 630 } 631 632 /* It's possible that stealing the block emptied the extent */ 633 if (elen) { 634 udf_write_aext(table, &epos, &eloc, elen, 1); 635 636 if (!epos.bh) { 637 iinfo->i_lenAlloc += adsize; 638 mark_inode_dirty(table); 639 } else { 640 aed = (struct allocExtDesc *)epos.bh->b_data; 641 le32_add_cpu(&aed->lengthAllocDescs, adsize); 642 udf_update_tag(epos.bh->b_data, epos.offset); 643 mark_buffer_dirty(epos.bh); 644 } 645 } 646 } 647 648 brelse(epos.bh); 649 brelse(oepos.bh); 650 651 error_return: 652 mutex_unlock(&sbi->s_alloc_mutex); 653 return; 654 } 655 656 static int udf_table_prealloc_blocks(struct super_block *sb, 657 struct inode *inode, 658 struct inode *table, uint16_t partition, 659 uint32_t first_block, uint32_t block_count) 660 { 661 struct udf_sb_info *sbi = UDF_SB(sb); 662 int alloc_count = 0; 663 uint32_t elen, adsize; 664 struct kernel_lb_addr eloc; 665 struct extent_position epos; 666 int8_t etype = -1; 667 struct udf_inode_info *iinfo; 668 669 if (first_block >= sbi->s_partmaps[partition].s_partition_len) 670 return 0; 671 672 iinfo = UDF_I(table); 673 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 674 adsize = sizeof(struct short_ad); 675 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 676 adsize = sizeof(struct long_ad); 677 else 678 return 0; 679 680 mutex_lock(&sbi->s_alloc_mutex); 681 epos.offset = sizeof(struct unallocSpaceEntry); 682 epos.block = iinfo->i_location; 683 epos.bh = NULL; 684 eloc.logicalBlockNum = 0xFFFFFFFF; 685 686 while (first_block != eloc.logicalBlockNum && 687 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 688 udf_debug("eloc=%d, elen=%d, first_block=%d\n", 689 eloc.logicalBlockNum, elen, first_block); 690 ; /* empty loop body */ 691 } 692 693 if (first_block == eloc.logicalBlockNum) { 694 epos.offset -= adsize; 695 696 alloc_count = (elen >> sb->s_blocksize_bits); 697 if (inode && vfs_dq_prealloc_block(inode, 698 alloc_count > block_count ? block_count : alloc_count)) 699 alloc_count = 0; 700 else if (alloc_count > block_count) { 701 alloc_count = block_count; 702 eloc.logicalBlockNum += alloc_count; 703 elen -= (alloc_count << sb->s_blocksize_bits); 704 udf_write_aext(table, &epos, &eloc, 705 (etype << 30) | elen, 1); 706 } else 707 udf_delete_aext(table, epos, eloc, 708 (etype << 30) | elen); 709 } else { 710 alloc_count = 0; 711 } 712 713 brelse(epos.bh); 714 715 if (alloc_count) 716 udf_add_free_space(sb, partition, -alloc_count); 717 mutex_unlock(&sbi->s_alloc_mutex); 718 return alloc_count; 719 } 720 721 static int udf_table_new_block(struct super_block *sb, 722 struct inode *inode, 723 struct inode *table, uint16_t partition, 724 uint32_t goal, int *err) 725 { 726 struct udf_sb_info *sbi = UDF_SB(sb); 727 uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF; 728 uint32_t newblock = 0, adsize; 729 uint32_t elen, goal_elen = 0; 730 struct kernel_lb_addr eloc, uninitialized_var(goal_eloc); 731 struct extent_position epos, goal_epos; 732 int8_t etype; 733 struct udf_inode_info *iinfo = UDF_I(table); 734 735 *err = -ENOSPC; 736 737 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 738 adsize = sizeof(struct short_ad); 739 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 740 adsize = sizeof(struct long_ad); 741 else 742 return newblock; 743 744 mutex_lock(&sbi->s_alloc_mutex); 745 if (goal >= sbi->s_partmaps[partition].s_partition_len) 746 goal = 0; 747 748 /* We search for the closest matching block to goal. If we find 749 a exact hit, we stop. Otherwise we keep going till we run out 750 of extents. We store the buffer_head, bloc, and extoffset 751 of the current closest match and use that when we are done. 752 */ 753 epos.offset = sizeof(struct unallocSpaceEntry); 754 epos.block = iinfo->i_location; 755 epos.bh = goal_epos.bh = NULL; 756 757 while (spread && 758 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 759 if (goal >= eloc.logicalBlockNum) { 760 if (goal < eloc.logicalBlockNum + 761 (elen >> sb->s_blocksize_bits)) 762 nspread = 0; 763 else 764 nspread = goal - eloc.logicalBlockNum - 765 (elen >> sb->s_blocksize_bits); 766 } else { 767 nspread = eloc.logicalBlockNum - goal; 768 } 769 770 if (nspread < spread) { 771 spread = nspread; 772 if (goal_epos.bh != epos.bh) { 773 brelse(goal_epos.bh); 774 goal_epos.bh = epos.bh; 775 get_bh(goal_epos.bh); 776 } 777 goal_epos.block = epos.block; 778 goal_epos.offset = epos.offset - adsize; 779 goal_eloc = eloc; 780 goal_elen = (etype << 30) | elen; 781 } 782 } 783 784 brelse(epos.bh); 785 786 if (spread == 0xFFFFFFFF) { 787 brelse(goal_epos.bh); 788 mutex_unlock(&sbi->s_alloc_mutex); 789 return 0; 790 } 791 792 /* Only allocate blocks from the beginning of the extent. 793 That way, we only delete (empty) extents, never have to insert an 794 extent because of splitting */ 795 /* This works, but very poorly.... */ 796 797 newblock = goal_eloc.logicalBlockNum; 798 goal_eloc.logicalBlockNum++; 799 goal_elen -= sb->s_blocksize; 800 801 if (inode && vfs_dq_alloc_block(inode, 1)) { 802 brelse(goal_epos.bh); 803 mutex_unlock(&sbi->s_alloc_mutex); 804 *err = -EDQUOT; 805 return 0; 806 } 807 808 if (goal_elen) 809 udf_write_aext(table, &goal_epos, &goal_eloc, goal_elen, 1); 810 else 811 udf_delete_aext(table, goal_epos, goal_eloc, goal_elen); 812 brelse(goal_epos.bh); 813 814 udf_add_free_space(sb, partition, -1); 815 816 mutex_unlock(&sbi->s_alloc_mutex); 817 *err = 0; 818 return newblock; 819 } 820 821 void udf_free_blocks(struct super_block *sb, struct inode *inode, 822 struct kernel_lb_addr *bloc, uint32_t offset, 823 uint32_t count) 824 { 825 uint16_t partition = bloc->partitionReferenceNum; 826 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 827 828 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) { 829 udf_bitmap_free_blocks(sb, inode, map->s_uspace.s_bitmap, 830 bloc, offset, count); 831 } else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) { 832 udf_table_free_blocks(sb, inode, map->s_uspace.s_table, 833 bloc, offset, count); 834 } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) { 835 udf_bitmap_free_blocks(sb, inode, map->s_fspace.s_bitmap, 836 bloc, offset, count); 837 } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) { 838 udf_table_free_blocks(sb, inode, map->s_fspace.s_table, 839 bloc, offset, count); 840 } 841 } 842 843 inline int udf_prealloc_blocks(struct super_block *sb, 844 struct inode *inode, 845 uint16_t partition, uint32_t first_block, 846 uint32_t block_count) 847 { 848 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 849 850 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) 851 return udf_bitmap_prealloc_blocks(sb, inode, 852 map->s_uspace.s_bitmap, 853 partition, first_block, 854 block_count); 855 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) 856 return udf_table_prealloc_blocks(sb, inode, 857 map->s_uspace.s_table, 858 partition, first_block, 859 block_count); 860 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) 861 return udf_bitmap_prealloc_blocks(sb, inode, 862 map->s_fspace.s_bitmap, 863 partition, first_block, 864 block_count); 865 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) 866 return udf_table_prealloc_blocks(sb, inode, 867 map->s_fspace.s_table, 868 partition, first_block, 869 block_count); 870 else 871 return 0; 872 } 873 874 inline int udf_new_block(struct super_block *sb, 875 struct inode *inode, 876 uint16_t partition, uint32_t goal, int *err) 877 { 878 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 879 880 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) 881 return udf_bitmap_new_block(sb, inode, 882 map->s_uspace.s_bitmap, 883 partition, goal, err); 884 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) 885 return udf_table_new_block(sb, inode, 886 map->s_uspace.s_table, 887 partition, goal, err); 888 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) 889 return udf_bitmap_new_block(sb, inode, 890 map->s_fspace.s_bitmap, 891 partition, goal, err); 892 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) 893 return udf_table_new_block(sb, inode, 894 map->s_fspace.s_table, 895 partition, goal, err); 896 else { 897 *err = -EIO; 898 return 0; 899 } 900 } 901