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 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 bool udf_add_free_space(struct udf_sb_info *sbi, 144 u16 partition, u32 cnt) 145 { 146 struct logicalVolIntegrityDesc *lvid; 147 148 if (sbi->s_lvid_bh == NULL) 149 return false; 150 151 lvid = (struct logicalVolIntegrityDesc *)sbi->s_lvid_bh->b_data; 152 le32_add_cpu(&lvid->freeSpaceTable[partition], cnt); 153 return true; 154 } 155 156 static void udf_bitmap_free_blocks(struct super_block *sb, 157 struct inode *inode, 158 struct udf_bitmap *bitmap, 159 kernel_lb_addr bloc, uint32_t offset, 160 uint32_t count) 161 { 162 struct udf_sb_info *sbi = UDF_SB(sb); 163 struct buffer_head *bh = NULL; 164 unsigned long block; 165 unsigned long block_group; 166 unsigned long bit; 167 unsigned long i; 168 int bitmap_nr; 169 unsigned long overflow; 170 171 mutex_lock(&sbi->s_alloc_mutex); 172 if (bloc.logicalBlockNum < 0 || 173 (bloc.logicalBlockNum + count) > 174 sbi->s_partmaps[bloc.partitionReferenceNum].s_partition_len) { 175 udf_debug("%d < %d || %d + %d > %d\n", 176 bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count, 177 sbi->s_partmaps[bloc.partitionReferenceNum]. 178 s_partition_len); 179 goto error_return; 180 } 181 182 block = bloc.logicalBlockNum + offset + 183 (sizeof(struct spaceBitmapDesc) << 3); 184 185 do { 186 overflow = 0; 187 block_group = block >> (sb->s_blocksize_bits + 3); 188 bit = block % (sb->s_blocksize << 3); 189 190 /* 191 * Check to see if we are freeing blocks across a group boundary. 192 */ 193 if (bit + count > (sb->s_blocksize << 3)) { 194 overflow = bit + count - (sb->s_blocksize << 3); 195 count -= overflow; 196 } 197 bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 198 if (bitmap_nr < 0) 199 goto error_return; 200 201 bh = bitmap->s_block_bitmap[bitmap_nr]; 202 for (i = 0; i < count; i++) { 203 if (udf_set_bit(bit + i, bh->b_data)) { 204 udf_debug("bit %ld already set\n", bit + i); 205 udf_debug("byte=%2x\n", 206 ((char *)bh->b_data)[(bit + i) >> 3]); 207 } else { 208 if (inode) 209 DQUOT_FREE_BLOCK(inode, 1); 210 udf_add_free_space(sbi, sbi->s_partition, 1); 211 } 212 } 213 mark_buffer_dirty(bh); 214 if (overflow) { 215 block += count; 216 count = overflow; 217 } 218 } while (overflow); 219 220 error_return: 221 sb->s_dirt = 1; 222 if (sbi->s_lvid_bh) 223 mark_buffer_dirty(sbi->s_lvid_bh); 224 mutex_unlock(&sbi->s_alloc_mutex); 225 } 226 227 static int udf_bitmap_prealloc_blocks(struct super_block *sb, 228 struct inode *inode, 229 struct udf_bitmap *bitmap, 230 uint16_t partition, uint32_t first_block, 231 uint32_t block_count) 232 { 233 struct udf_sb_info *sbi = UDF_SB(sb); 234 int alloc_count = 0; 235 int bit, block, block_group, group_start; 236 int nr_groups, bitmap_nr; 237 struct buffer_head *bh; 238 __u32 part_len; 239 240 mutex_lock(&sbi->s_alloc_mutex); 241 part_len = sbi->s_partmaps[partition].s_partition_len; 242 if (first_block < 0 || first_block >= part_len) 243 goto out; 244 245 if (first_block + block_count > part_len) 246 block_count = part_len - first_block; 247 248 do { 249 nr_groups = udf_compute_nr_groups(sb, partition); 250 block = first_block + (sizeof(struct spaceBitmapDesc) << 3); 251 block_group = block >> (sb->s_blocksize_bits + 3); 252 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 253 254 bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 255 if (bitmap_nr < 0) 256 goto out; 257 bh = bitmap->s_block_bitmap[bitmap_nr]; 258 259 bit = block % (sb->s_blocksize << 3); 260 261 while (bit < (sb->s_blocksize << 3) && block_count > 0) { 262 if (!udf_test_bit(bit, bh->b_data)) 263 goto out; 264 else if (DQUOT_PREALLOC_BLOCK(inode, 1)) 265 goto out; 266 else if (!udf_clear_bit(bit, bh->b_data)) { 267 udf_debug("bit already cleared for block %d\n", bit); 268 DQUOT_FREE_BLOCK(inode, 1); 269 goto out; 270 } 271 block_count--; 272 alloc_count++; 273 bit++; 274 block++; 275 } 276 mark_buffer_dirty(bh); 277 } while (block_count > 0); 278 279 out: 280 if (udf_add_free_space(sbi, partition, -alloc_count)) 281 mark_buffer_dirty(sbi->s_lvid_bh); 282 sb->s_dirt = 1; 283 mutex_unlock(&sbi->s_alloc_mutex); 284 return alloc_count; 285 } 286 287 static int udf_bitmap_new_block(struct super_block *sb, 288 struct inode *inode, 289 struct udf_bitmap *bitmap, uint16_t partition, 290 uint32_t goal, int *err) 291 { 292 struct udf_sb_info *sbi = UDF_SB(sb); 293 int newbit, bit = 0, block, block_group, group_start; 294 int end_goal, nr_groups, bitmap_nr, i; 295 struct buffer_head *bh = NULL; 296 char *ptr; 297 int newblock = 0; 298 299 *err = -ENOSPC; 300 mutex_lock(&sbi->s_alloc_mutex); 301 302 repeat: 303 if (goal < 0 || goal >= sbi->s_partmaps[partition].s_partition_len) 304 goal = 0; 305 306 nr_groups = bitmap->s_nr_groups; 307 block = goal + (sizeof(struct spaceBitmapDesc) << 3); 308 block_group = block >> (sb->s_blocksize_bits + 3); 309 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 310 311 bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 312 if (bitmap_nr < 0) 313 goto error_return; 314 bh = bitmap->s_block_bitmap[bitmap_nr]; 315 ptr = memscan((char *)bh->b_data + group_start, 0xFF, 316 sb->s_blocksize - group_start); 317 318 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) { 319 bit = block % (sb->s_blocksize << 3); 320 if (udf_test_bit(bit, bh->b_data)) 321 goto got_block; 322 323 end_goal = (bit + 63) & ~63; 324 bit = udf_find_next_one_bit(bh->b_data, end_goal, bit); 325 if (bit < end_goal) 326 goto got_block; 327 328 ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF, 329 sb->s_blocksize - ((bit + 7) >> 3)); 330 newbit = (ptr - ((char *)bh->b_data)) << 3; 331 if (newbit < sb->s_blocksize << 3) { 332 bit = newbit; 333 goto search_back; 334 } 335 336 newbit = udf_find_next_one_bit(bh->b_data, 337 sb->s_blocksize << 3, bit); 338 if (newbit < sb->s_blocksize << 3) { 339 bit = newbit; 340 goto got_block; 341 } 342 } 343 344 for (i = 0; i < (nr_groups * 2); i++) { 345 block_group++; 346 if (block_group >= nr_groups) 347 block_group = 0; 348 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); 349 350 bitmap_nr = load_block_bitmap(sb, bitmap, block_group); 351 if (bitmap_nr < 0) 352 goto error_return; 353 bh = bitmap->s_block_bitmap[bitmap_nr]; 354 if (i < nr_groups) { 355 ptr = memscan((char *)bh->b_data + group_start, 0xFF, 356 sb->s_blocksize - group_start); 357 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) { 358 bit = (ptr - ((char *)bh->b_data)) << 3; 359 break; 360 } 361 } else { 362 bit = udf_find_next_one_bit((char *)bh->b_data, 363 sb->s_blocksize << 3, 364 group_start << 3); 365 if (bit < sb->s_blocksize << 3) 366 break; 367 } 368 } 369 if (i >= (nr_groups * 2)) { 370 mutex_unlock(&sbi->s_alloc_mutex); 371 return newblock; 372 } 373 if (bit < sb->s_blocksize << 3) 374 goto search_back; 375 else 376 bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, 377 group_start << 3); 378 if (bit >= sb->s_blocksize << 3) { 379 mutex_unlock(&sbi->s_alloc_mutex); 380 return 0; 381 } 382 383 search_back: 384 i = 0; 385 while (i < 7 && bit > (group_start << 3) && 386 udf_test_bit(bit - 1, bh->b_data)) { 387 ++i; 388 --bit; 389 } 390 391 got_block: 392 393 /* 394 * Check quota for allocation of this block. 395 */ 396 if (inode && DQUOT_ALLOC_BLOCK(inode, 1)) { 397 mutex_unlock(&sbi->s_alloc_mutex); 398 *err = -EDQUOT; 399 return 0; 400 } 401 402 newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) - 403 (sizeof(struct spaceBitmapDesc) << 3); 404 405 if (!udf_clear_bit(bit, bh->b_data)) { 406 udf_debug("bit already cleared for block %d\n", bit); 407 goto repeat; 408 } 409 410 mark_buffer_dirty(bh); 411 412 if (udf_add_free_space(sbi, partition, -1)) 413 mark_buffer_dirty(sbi->s_lvid_bh); 414 sb->s_dirt = 1; 415 mutex_unlock(&sbi->s_alloc_mutex); 416 *err = 0; 417 return newblock; 418 419 error_return: 420 *err = -EIO; 421 mutex_unlock(&sbi->s_alloc_mutex); 422 return 0; 423 } 424 425 static void udf_table_free_blocks(struct super_block *sb, 426 struct inode *inode, 427 struct inode *table, 428 kernel_lb_addr bloc, uint32_t offset, 429 uint32_t count) 430 { 431 struct udf_sb_info *sbi = UDF_SB(sb); 432 uint32_t start, end; 433 uint32_t elen; 434 kernel_lb_addr eloc; 435 struct extent_position oepos, epos; 436 int8_t etype; 437 int i; 438 struct udf_inode_info *iinfo; 439 440 mutex_lock(&sbi->s_alloc_mutex); 441 if (bloc.logicalBlockNum < 0 || 442 (bloc.logicalBlockNum + count) > 443 sbi->s_partmaps[bloc.partitionReferenceNum].s_partition_len) { 444 udf_debug("%d < %d || %d + %d > %d\n", 445 bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count, 446 sbi->s_partmaps[bloc.partitionReferenceNum]. 447 s_partition_len); 448 goto error_return; 449 } 450 451 iinfo = UDF_I(table); 452 /* We do this up front - There are some error conditions that 453 could occure, but.. oh well */ 454 if (inode) 455 DQUOT_FREE_BLOCK(inode, count); 456 if (udf_add_free_space(sbi, sbi->s_partition, count)) 457 mark_buffer_dirty(sbi->s_lvid_bh); 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 short_ad *sad = NULL; 536 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(short_ad); 545 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 546 adsize = sizeof(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 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(tag)); 605 else 606 udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, 607 2, 1, epos.block.logicalBlockNum, 608 sizeof(tag)); 609 610 switch (iinfo->i_alloc_type) { 611 case ICBTAG_FLAG_AD_SHORT: 612 sad = (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 = (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 sb->s_dirt = 1; 657 mutex_unlock(&sbi->s_alloc_mutex); 658 return; 659 } 660 661 static int udf_table_prealloc_blocks(struct super_block *sb, 662 struct inode *inode, 663 struct inode *table, uint16_t partition, 664 uint32_t first_block, uint32_t block_count) 665 { 666 struct udf_sb_info *sbi = UDF_SB(sb); 667 int alloc_count = 0; 668 uint32_t elen, adsize; 669 kernel_lb_addr eloc; 670 struct extent_position epos; 671 int8_t etype = -1; 672 struct udf_inode_info *iinfo; 673 674 if (first_block < 0 || 675 first_block >= sbi->s_partmaps[partition].s_partition_len) 676 return 0; 677 678 iinfo = UDF_I(table); 679 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 680 adsize = sizeof(short_ad); 681 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 682 adsize = sizeof(long_ad); 683 else 684 return 0; 685 686 mutex_lock(&sbi->s_alloc_mutex); 687 epos.offset = sizeof(struct unallocSpaceEntry); 688 epos.block = iinfo->i_location; 689 epos.bh = NULL; 690 eloc.logicalBlockNum = 0xFFFFFFFF; 691 692 while (first_block != eloc.logicalBlockNum && 693 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 694 udf_debug("eloc=%d, elen=%d, first_block=%d\n", 695 eloc.logicalBlockNum, elen, first_block); 696 ; /* empty loop body */ 697 } 698 699 if (first_block == eloc.logicalBlockNum) { 700 epos.offset -= adsize; 701 702 alloc_count = (elen >> sb->s_blocksize_bits); 703 if (inode && DQUOT_PREALLOC_BLOCK(inode, 704 alloc_count > block_count ? block_count : alloc_count)) 705 alloc_count = 0; 706 else if (alloc_count > block_count) { 707 alloc_count = block_count; 708 eloc.logicalBlockNum += alloc_count; 709 elen -= (alloc_count << sb->s_blocksize_bits); 710 udf_write_aext(table, &epos, eloc, 711 (etype << 30) | elen, 1); 712 } else 713 udf_delete_aext(table, epos, eloc, 714 (etype << 30) | elen); 715 } else { 716 alloc_count = 0; 717 } 718 719 brelse(epos.bh); 720 721 if (alloc_count && udf_add_free_space(sbi, partition, -alloc_count)) { 722 mark_buffer_dirty(sbi->s_lvid_bh); 723 sb->s_dirt = 1; 724 } 725 mutex_unlock(&sbi->s_alloc_mutex); 726 return alloc_count; 727 } 728 729 static int udf_table_new_block(struct super_block *sb, 730 struct inode *inode, 731 struct inode *table, uint16_t partition, 732 uint32_t goal, int *err) 733 { 734 struct udf_sb_info *sbi = UDF_SB(sb); 735 uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF; 736 uint32_t newblock = 0, adsize; 737 uint32_t elen, goal_elen = 0; 738 kernel_lb_addr eloc, uninitialized_var(goal_eloc); 739 struct extent_position epos, goal_epos; 740 int8_t etype; 741 struct udf_inode_info *iinfo = UDF_I(table); 742 743 *err = -ENOSPC; 744 745 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) 746 adsize = sizeof(short_ad); 747 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) 748 adsize = sizeof(long_ad); 749 else 750 return newblock; 751 752 mutex_lock(&sbi->s_alloc_mutex); 753 if (goal < 0 || goal >= sbi->s_partmaps[partition].s_partition_len) 754 goal = 0; 755 756 /* We search for the closest matching block to goal. If we find 757 a exact hit, we stop. Otherwise we keep going till we run out 758 of extents. We store the buffer_head, bloc, and extoffset 759 of the current closest match and use that when we are done. 760 */ 761 epos.offset = sizeof(struct unallocSpaceEntry); 762 epos.block = iinfo->i_location; 763 epos.bh = goal_epos.bh = NULL; 764 765 while (spread && 766 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { 767 if (goal >= eloc.logicalBlockNum) { 768 if (goal < eloc.logicalBlockNum + 769 (elen >> sb->s_blocksize_bits)) 770 nspread = 0; 771 else 772 nspread = goal - eloc.logicalBlockNum - 773 (elen >> sb->s_blocksize_bits); 774 } else { 775 nspread = eloc.logicalBlockNum - goal; 776 } 777 778 if (nspread < spread) { 779 spread = nspread; 780 if (goal_epos.bh != epos.bh) { 781 brelse(goal_epos.bh); 782 goal_epos.bh = epos.bh; 783 get_bh(goal_epos.bh); 784 } 785 goal_epos.block = epos.block; 786 goal_epos.offset = epos.offset - adsize; 787 goal_eloc = eloc; 788 goal_elen = (etype << 30) | elen; 789 } 790 } 791 792 brelse(epos.bh); 793 794 if (spread == 0xFFFFFFFF) { 795 brelse(goal_epos.bh); 796 mutex_unlock(&sbi->s_alloc_mutex); 797 return 0; 798 } 799 800 /* Only allocate blocks from the beginning of the extent. 801 That way, we only delete (empty) extents, never have to insert an 802 extent because of splitting */ 803 /* This works, but very poorly.... */ 804 805 newblock = goal_eloc.logicalBlockNum; 806 goal_eloc.logicalBlockNum++; 807 goal_elen -= sb->s_blocksize; 808 809 if (inode && DQUOT_ALLOC_BLOCK(inode, 1)) { 810 brelse(goal_epos.bh); 811 mutex_unlock(&sbi->s_alloc_mutex); 812 *err = -EDQUOT; 813 return 0; 814 } 815 816 if (goal_elen) 817 udf_write_aext(table, &goal_epos, goal_eloc, goal_elen, 1); 818 else 819 udf_delete_aext(table, goal_epos, goal_eloc, goal_elen); 820 brelse(goal_epos.bh); 821 822 if (udf_add_free_space(sbi, partition, -1)) 823 mark_buffer_dirty(sbi->s_lvid_bh); 824 825 sb->s_dirt = 1; 826 mutex_unlock(&sbi->s_alloc_mutex); 827 *err = 0; 828 return newblock; 829 } 830 831 inline void udf_free_blocks(struct super_block *sb, 832 struct inode *inode, 833 kernel_lb_addr bloc, uint32_t offset, 834 uint32_t count) 835 { 836 uint16_t partition = bloc.partitionReferenceNum; 837 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 838 839 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) { 840 return udf_bitmap_free_blocks(sb, inode, 841 map->s_uspace.s_bitmap, 842 bloc, offset, count); 843 } else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) { 844 return udf_table_free_blocks(sb, inode, 845 map->s_uspace.s_table, 846 bloc, offset, count); 847 } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) { 848 return udf_bitmap_free_blocks(sb, inode, 849 map->s_fspace.s_bitmap, 850 bloc, offset, count); 851 } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) { 852 return udf_table_free_blocks(sb, inode, 853 map->s_fspace.s_table, 854 bloc, offset, count); 855 } else { 856 return; 857 } 858 } 859 860 inline int udf_prealloc_blocks(struct super_block *sb, 861 struct inode *inode, 862 uint16_t partition, uint32_t first_block, 863 uint32_t block_count) 864 { 865 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 866 867 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) 868 return udf_bitmap_prealloc_blocks(sb, inode, 869 map->s_uspace.s_bitmap, 870 partition, first_block, 871 block_count); 872 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) 873 return udf_table_prealloc_blocks(sb, inode, 874 map->s_uspace.s_table, 875 partition, first_block, 876 block_count); 877 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) 878 return udf_bitmap_prealloc_blocks(sb, inode, 879 map->s_fspace.s_bitmap, 880 partition, first_block, 881 block_count); 882 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) 883 return udf_table_prealloc_blocks(sb, inode, 884 map->s_fspace.s_table, 885 partition, first_block, 886 block_count); 887 else 888 return 0; 889 } 890 891 inline int udf_new_block(struct super_block *sb, 892 struct inode *inode, 893 uint16_t partition, uint32_t goal, int *err) 894 { 895 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; 896 897 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) 898 return udf_bitmap_new_block(sb, inode, 899 map->s_uspace.s_bitmap, 900 partition, goal, err); 901 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) 902 return udf_table_new_block(sb, inode, 903 map->s_uspace.s_table, 904 partition, goal, err); 905 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) 906 return udf_bitmap_new_block(sb, inode, 907 map->s_fspace.s_bitmap, 908 partition, goal, err); 909 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) 910 return udf_table_new_block(sb, inode, 911 map->s_fspace.s_table, 912 partition, goal, err); 913 else { 914 *err = -EIO; 915 return 0; 916 } 917 } 918