736 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * balloc.c4 *5 * PURPOSE6 * Block allocation handling routines for the OSTA-UDF(tm) filesystem.7 *8 * COPYRIGHT9 * (C) 1999-2001 Ben Fennema10 * (C) 1999 Stelias Computing Inc11 *12 * HISTORY13 *14 * 02/24/99 blf Created.15 *16 */17 18#include "udfdecl.h"19 20#include <linux/bitops.h>21#include <linux/overflow.h>22 23#include "udf_i.h"24#include "udf_sb.h"25 26#define udf_clear_bit __test_and_clear_bit_le27#define udf_set_bit __test_and_set_bit_le28#define udf_test_bit test_bit_le29#define udf_find_next_one_bit find_next_bit_le30 31static int read_block_bitmap(struct super_block *sb,32 struct udf_bitmap *bitmap, unsigned int block,33 unsigned long bitmap_nr)34{35 struct buffer_head *bh = NULL;36 int i;37 int max_bits, off, count;38 struct kernel_lb_addr loc;39 40 loc.logicalBlockNum = bitmap->s_extPosition;41 loc.partitionReferenceNum = UDF_SB(sb)->s_partition;42 43 bh = sb_bread(sb, udf_get_lb_pblock(sb, &loc, block));44 bitmap->s_block_bitmap[bitmap_nr] = bh;45 if (!bh)46 return -EIO;47 48 /* Check consistency of Space Bitmap buffer. */49 max_bits = sb->s_blocksize * 8;50 if (!bitmap_nr) {51 off = sizeof(struct spaceBitmapDesc) << 3;52 count = min(max_bits - off, bitmap->s_nr_groups);53 } else {54 /*55 * Rough check if bitmap number is too big to have any bitmap56 * blocks reserved.57 */58 if (bitmap_nr >59 (bitmap->s_nr_groups >> (sb->s_blocksize_bits + 3)) + 2)60 return 0;61 off = 0;62 count = bitmap->s_nr_groups - bitmap_nr * max_bits +63 (sizeof(struct spaceBitmapDesc) << 3);64 count = min(count, max_bits);65 }66 67 for (i = 0; i < count; i++)68 if (udf_test_bit(i + off, bh->b_data)) {69 bitmap->s_block_bitmap[bitmap_nr] =70 ERR_PTR(-EFSCORRUPTED);71 brelse(bh);72 return -EFSCORRUPTED;73 }74 return 0;75}76 77static int load_block_bitmap(struct super_block *sb,78 struct udf_bitmap *bitmap,79 unsigned int block_group)80{81 int retval = 0;82 int nr_groups = bitmap->s_nr_groups;83 84 if (block_group >= nr_groups) {85 udf_debug("block_group (%u) > nr_groups (%d)\n",86 block_group, nr_groups);87 }88 89 if (bitmap->s_block_bitmap[block_group]) {90 /*91 * The bitmap failed verification in the past. No point in92 * trying again.93 */94 if (IS_ERR(bitmap->s_block_bitmap[block_group]))95 return PTR_ERR(bitmap->s_block_bitmap[block_group]);96 return block_group;97 }98 99 retval = read_block_bitmap(sb, bitmap, block_group, block_group);100 if (retval < 0)101 return retval;102 103 return block_group;104}105 106static void udf_add_free_space(struct super_block *sb, u16 partition, u32 cnt)107{108 struct udf_sb_info *sbi = UDF_SB(sb);109 struct logicalVolIntegrityDesc *lvid;110 111 if (!sbi->s_lvid_bh)112 return;113 114 lvid = (struct logicalVolIntegrityDesc *)sbi->s_lvid_bh->b_data;115 le32_add_cpu(&lvid->freeSpaceTable[partition], cnt);116 udf_updated_lvid(sb);117}118 119static void udf_bitmap_free_blocks(struct super_block *sb,120 struct udf_bitmap *bitmap,121 struct kernel_lb_addr *bloc,122 uint32_t offset,123 uint32_t count)124{125 struct udf_sb_info *sbi = UDF_SB(sb);126 struct buffer_head *bh = NULL;127 unsigned long block;128 unsigned long block_group;129 unsigned long bit;130 unsigned long i;131 int bitmap_nr;132 unsigned long overflow;133 134 mutex_lock(&sbi->s_alloc_mutex);135 /* We make sure this cannot overflow when mounting the filesystem */136 block = bloc->logicalBlockNum + offset +137 (sizeof(struct spaceBitmapDesc) << 3);138 do {139 overflow = 0;140 block_group = block >> (sb->s_blocksize_bits + 3);141 bit = block % (sb->s_blocksize << 3);142 143 /*144 * Check to see if we are freeing blocks across a group boundary.145 */146 if (bit + count > (sb->s_blocksize << 3)) {147 overflow = bit + count - (sb->s_blocksize << 3);148 count -= overflow;149 }150 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);151 if (bitmap_nr < 0)152 goto error_return;153 154 bh = bitmap->s_block_bitmap[bitmap_nr];155 for (i = 0; i < count; i++) {156 if (udf_set_bit(bit + i, bh->b_data)) {157 udf_debug("bit %lu already set\n", bit + i);158 udf_debug("byte=%2x\n",159 ((__u8 *)bh->b_data)[(bit + i) >> 3]);160 }161 }162 udf_add_free_space(sb, sbi->s_partition, count);163 mark_buffer_dirty(bh);164 if (overflow) {165 block += count;166 count = overflow;167 }168 } while (overflow);169 170error_return:171 mutex_unlock(&sbi->s_alloc_mutex);172}173 174static int udf_bitmap_prealloc_blocks(struct super_block *sb,175 struct udf_bitmap *bitmap,176 uint16_t partition, uint32_t first_block,177 uint32_t block_count)178{179 struct udf_sb_info *sbi = UDF_SB(sb);180 int alloc_count = 0;181 int bit, block, block_group;182 int bitmap_nr;183 struct buffer_head *bh;184 __u32 part_len;185 186 mutex_lock(&sbi->s_alloc_mutex);187 part_len = sbi->s_partmaps[partition].s_partition_len;188 if (first_block >= part_len)189 goto out;190 191 if (first_block + block_count > part_len)192 block_count = part_len - first_block;193 194 do {195 block = first_block + (sizeof(struct spaceBitmapDesc) << 3);196 block_group = block >> (sb->s_blocksize_bits + 3);197 198 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);199 if (bitmap_nr < 0)200 goto out;201 bh = bitmap->s_block_bitmap[bitmap_nr];202 203 bit = block % (sb->s_blocksize << 3);204 205 while (bit < (sb->s_blocksize << 3) && block_count > 0) {206 if (!udf_clear_bit(bit, bh->b_data))207 goto out;208 block_count--;209 alloc_count++;210 bit++;211 block++;212 }213 mark_buffer_dirty(bh);214 } while (block_count > 0);215 216out:217 udf_add_free_space(sb, partition, -alloc_count);218 mutex_unlock(&sbi->s_alloc_mutex);219 return alloc_count;220}221 222static udf_pblk_t udf_bitmap_new_block(struct super_block *sb,223 struct udf_bitmap *bitmap, uint16_t partition,224 uint32_t goal, int *err)225{226 struct udf_sb_info *sbi = UDF_SB(sb);227 int newbit, bit = 0;228 udf_pblk_t block;229 int block_group, group_start;230 int end_goal, nr_groups, bitmap_nr, i;231 struct buffer_head *bh = NULL;232 char *ptr;233 udf_pblk_t newblock = 0;234 235 *err = -ENOSPC;236 mutex_lock(&sbi->s_alloc_mutex);237 238repeat:239 if (goal >= sbi->s_partmaps[partition].s_partition_len)240 goal = 0;241 242 nr_groups = bitmap->s_nr_groups;243 block = goal + (sizeof(struct spaceBitmapDesc) << 3);244 block_group = block >> (sb->s_blocksize_bits + 3);245 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);246 247 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);248 if (bitmap_nr < 0)249 goto error_return;250 bh = bitmap->s_block_bitmap[bitmap_nr];251 ptr = memscan((char *)bh->b_data + group_start, 0xFF,252 sb->s_blocksize - group_start);253 254 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) {255 bit = block % (sb->s_blocksize << 3);256 if (udf_test_bit(bit, bh->b_data))257 goto got_block;258 259 end_goal = (bit + 63) & ~63;260 bit = udf_find_next_one_bit(bh->b_data, end_goal, bit);261 if (bit < end_goal)262 goto got_block;263 264 ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF,265 sb->s_blocksize - ((bit + 7) >> 3));266 newbit = (ptr - ((char *)bh->b_data)) << 3;267 if (newbit < sb->s_blocksize << 3) {268 bit = newbit;269 goto search_back;270 }271 272 newbit = udf_find_next_one_bit(bh->b_data,273 sb->s_blocksize << 3, bit);274 if (newbit < sb->s_blocksize << 3) {275 bit = newbit;276 goto got_block;277 }278 }279 280 for (i = 0; i < (nr_groups * 2); i++) {281 block_group++;282 if (block_group >= nr_groups)283 block_group = 0;284 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);285 286 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);287 if (bitmap_nr < 0)288 goto error_return;289 bh = bitmap->s_block_bitmap[bitmap_nr];290 if (i < nr_groups) {291 ptr = memscan((char *)bh->b_data + group_start, 0xFF,292 sb->s_blocksize - group_start);293 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) {294 bit = (ptr - ((char *)bh->b_data)) << 3;295 break;296 }297 } else {298 bit = udf_find_next_one_bit(bh->b_data,299 sb->s_blocksize << 3,300 group_start << 3);301 if (bit < sb->s_blocksize << 3)302 break;303 }304 }305 if (i >= (nr_groups * 2)) {306 mutex_unlock(&sbi->s_alloc_mutex);307 return newblock;308 }309 if (bit < sb->s_blocksize << 3)310 goto search_back;311 else312 bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3,313 group_start << 3);314 if (bit >= sb->s_blocksize << 3) {315 mutex_unlock(&sbi->s_alloc_mutex);316 return 0;317 }318 319search_back:320 i = 0;321 while (i < 7 && bit > (group_start << 3) &&322 udf_test_bit(bit - 1, bh->b_data)) {323 ++i;324 --bit;325 }326 327got_block:328 newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) -329 (sizeof(struct spaceBitmapDesc) << 3);330 331 if (newblock >= sbi->s_partmaps[partition].s_partition_len) {332 /*333 * Ran off the end of the bitmap, and bits following are334 * non-compliant (not all zero)335 */336 udf_err(sb, "bitmap for partition %d corrupted (block %u marked"337 " as free, partition length is %u)\n", partition,338 newblock, sbi->s_partmaps[partition].s_partition_len);339 goto error_return;340 }341 342 if (!udf_clear_bit(bit, bh->b_data)) {343 udf_debug("bit already cleared for block %d\n", bit);344 goto repeat;345 }346 347 mark_buffer_dirty(bh);348 349 udf_add_free_space(sb, partition, -1);350 mutex_unlock(&sbi->s_alloc_mutex);351 *err = 0;352 return newblock;353 354error_return:355 *err = -EIO;356 mutex_unlock(&sbi->s_alloc_mutex);357 return 0;358}359 360static void udf_table_free_blocks(struct super_block *sb,361 struct inode *table,362 struct kernel_lb_addr *bloc,363 uint32_t offset,364 uint32_t count)365{366 struct udf_sb_info *sbi = UDF_SB(sb);367 uint32_t start, end;368 uint32_t elen;369 struct kernel_lb_addr eloc;370 struct extent_position oepos, epos;371 int8_t etype;372 struct udf_inode_info *iinfo;373 int ret = 0;374 375 mutex_lock(&sbi->s_alloc_mutex);376 iinfo = UDF_I(table);377 udf_add_free_space(sb, sbi->s_partition, count);378 379 start = bloc->logicalBlockNum + offset;380 end = bloc->logicalBlockNum + offset + count - 1;381 382 epos.offset = oepos.offset = sizeof(struct unallocSpaceEntry);383 elen = 0;384 epos.block = oepos.block = iinfo->i_location;385 epos.bh = oepos.bh = NULL;386 387 while (count) {388 ret = udf_next_aext(table, &epos, &eloc, &elen, &etype, 1);389 if (ret < 0)390 goto error_return;391 if (ret == 0)392 break;393 if (((eloc.logicalBlockNum +394 (elen >> sb->s_blocksize_bits)) == start)) {395 if ((0x3FFFFFFF - elen) <396 (count << sb->s_blocksize_bits)) {397 uint32_t tmp = ((0x3FFFFFFF - elen) >>398 sb->s_blocksize_bits);399 count -= tmp;400 start += tmp;401 elen = (etype << 30) |402 (0x40000000 - sb->s_blocksize);403 } else {404 elen = (etype << 30) |405 (elen +406 (count << sb->s_blocksize_bits));407 start += count;408 count = 0;409 }410 udf_write_aext(table, &oepos, &eloc, elen, 1);411 } else if (eloc.logicalBlockNum == (end + 1)) {412 if ((0x3FFFFFFF - elen) <413 (count << sb->s_blocksize_bits)) {414 uint32_t tmp = ((0x3FFFFFFF - elen) >>415 sb->s_blocksize_bits);416 count -= tmp;417 end -= tmp;418 eloc.logicalBlockNum -= tmp;419 elen = (etype << 30) |420 (0x40000000 - sb->s_blocksize);421 } else {422 eloc.logicalBlockNum = start;423 elen = (etype << 30) |424 (elen +425 (count << sb->s_blocksize_bits));426 end -= count;427 count = 0;428 }429 udf_write_aext(table, &oepos, &eloc, elen, 1);430 }431 432 if (epos.bh != oepos.bh) {433 oepos.block = epos.block;434 brelse(oepos.bh);435 get_bh(epos.bh);436 oepos.bh = epos.bh;437 oepos.offset = 0;438 } else {439 oepos.offset = epos.offset;440 }441 }442 443 if (count) {444 /*445 * NOTE: we CANNOT use udf_add_aext here, as it can try to446 * allocate a new block, and since we hold the super block447 * lock already very bad things would happen :)448 *449 * We copy the behavior of udf_add_aext, but instead of450 * trying to allocate a new block close to the existing one,451 * we just steal a block from the extent we are trying to add.452 *453 * It would be nice if the blocks were close together, but it454 * isn't required.455 */456 457 int adsize;458 459 eloc.logicalBlockNum = start;460 elen = EXT_RECORDED_ALLOCATED |461 (count << sb->s_blocksize_bits);462 463 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)464 adsize = sizeof(struct short_ad);465 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)466 adsize = sizeof(struct long_ad);467 else468 goto error_return;469 470 if (epos.offset + (2 * adsize) > sb->s_blocksize) {471 /* Steal a block from the extent being free'd */472 udf_setup_indirect_aext(table, eloc.logicalBlockNum,473 &epos);474 475 eloc.logicalBlockNum++;476 elen -= sb->s_blocksize;477 }478 479 /* It's possible that stealing the block emptied the extent */480 if (elen)481 __udf_add_aext(table, &epos, &eloc, elen, 1);482 }483 484error_return:485 brelse(epos.bh);486 brelse(oepos.bh);487 488 mutex_unlock(&sbi->s_alloc_mutex);489 return;490}491 492static int udf_table_prealloc_blocks(struct super_block *sb,493 struct inode *table, uint16_t partition,494 uint32_t first_block, uint32_t block_count)495{496 struct udf_sb_info *sbi = UDF_SB(sb);497 int alloc_count = 0;498 uint32_t elen, adsize;499 struct kernel_lb_addr eloc;500 struct extent_position epos;501 int8_t etype = -1;502 struct udf_inode_info *iinfo;503 int ret = 0;504 505 if (first_block >= sbi->s_partmaps[partition].s_partition_len)506 return 0;507 508 iinfo = UDF_I(table);509 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)510 adsize = sizeof(struct short_ad);511 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)512 adsize = sizeof(struct long_ad);513 else514 return 0;515 516 mutex_lock(&sbi->s_alloc_mutex);517 epos.offset = sizeof(struct unallocSpaceEntry);518 epos.block = iinfo->i_location;519 epos.bh = NULL;520 eloc.logicalBlockNum = 0xFFFFFFFF;521 522 while (first_block != eloc.logicalBlockNum) {523 ret = udf_next_aext(table, &epos, &eloc, &elen, &etype, 1);524 if (ret < 0)525 goto err_out;526 if (ret == 0)527 break;528 udf_debug("eloc=%u, elen=%u, first_block=%u\n",529 eloc.logicalBlockNum, elen, first_block);530 }531 532 if (first_block == eloc.logicalBlockNum) {533 epos.offset -= adsize;534 535 alloc_count = (elen >> sb->s_blocksize_bits);536 if (alloc_count > block_count) {537 alloc_count = block_count;538 eloc.logicalBlockNum += alloc_count;539 elen -= (alloc_count << sb->s_blocksize_bits);540 udf_write_aext(table, &epos, &eloc,541 (etype << 30) | elen, 1);542 } else543 udf_delete_aext(table, epos);544 } else {545 alloc_count = 0;546 }547 548err_out:549 brelse(epos.bh);550 551 if (alloc_count)552 udf_add_free_space(sb, partition, -alloc_count);553 mutex_unlock(&sbi->s_alloc_mutex);554 return alloc_count;555}556 557static udf_pblk_t udf_table_new_block(struct super_block *sb,558 struct inode *table, uint16_t partition,559 uint32_t goal, int *err)560{561 struct udf_sb_info *sbi = UDF_SB(sb);562 uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF;563 udf_pblk_t newblock = 0;564 uint32_t adsize;565 uint32_t elen, goal_elen = 0;566 struct kernel_lb_addr eloc, goal_eloc;567 struct extent_position epos, goal_epos;568 int8_t etype;569 struct udf_inode_info *iinfo = UDF_I(table);570 int ret = 0;571 572 *err = -ENOSPC;573 574 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)575 adsize = sizeof(struct short_ad);576 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)577 adsize = sizeof(struct long_ad);578 else579 return newblock;580 581 mutex_lock(&sbi->s_alloc_mutex);582 if (goal >= sbi->s_partmaps[partition].s_partition_len)583 goal = 0;584 585 /* We search for the closest matching block to goal. If we find586 a exact hit, we stop. Otherwise we keep going till we run out587 of extents. We store the buffer_head, bloc, and extoffset588 of the current closest match and use that when we are done.589 */590 epos.offset = sizeof(struct unallocSpaceEntry);591 epos.block = iinfo->i_location;592 epos.bh = goal_epos.bh = NULL;593 594 while (spread) {595 ret = udf_next_aext(table, &epos, &eloc, &elen, &etype, 1);596 if (ret <= 0)597 break;598 if (goal >= eloc.logicalBlockNum) {599 if (goal < eloc.logicalBlockNum +600 (elen >> sb->s_blocksize_bits))601 nspread = 0;602 else603 nspread = goal - eloc.logicalBlockNum -604 (elen >> sb->s_blocksize_bits);605 } else {606 nspread = eloc.logicalBlockNum - goal;607 }608 609 if (nspread < spread) {610 spread = nspread;611 if (goal_epos.bh != epos.bh) {612 brelse(goal_epos.bh);613 goal_epos.bh = epos.bh;614 get_bh(goal_epos.bh);615 }616 goal_epos.block = epos.block;617 goal_epos.offset = epos.offset - adsize;618 goal_eloc = eloc;619 goal_elen = (etype << 30) | elen;620 }621 }622 623 brelse(epos.bh);624 625 if (ret < 0 || spread == 0xFFFFFFFF) {626 brelse(goal_epos.bh);627 mutex_unlock(&sbi->s_alloc_mutex);628 if (ret < 0)629 *err = ret;630 return 0;631 }632 633 /* Only allocate blocks from the beginning of the extent.634 That way, we only delete (empty) extents, never have to insert an635 extent because of splitting */636 /* This works, but very poorly.... */637 638 newblock = goal_eloc.logicalBlockNum;639 goal_eloc.logicalBlockNum++;640 goal_elen -= sb->s_blocksize;641 642 if (goal_elen)643 udf_write_aext(table, &goal_epos, &goal_eloc, goal_elen, 1);644 else645 udf_delete_aext(table, goal_epos);646 brelse(goal_epos.bh);647 648 udf_add_free_space(sb, partition, -1);649 650 mutex_unlock(&sbi->s_alloc_mutex);651 *err = 0;652 return newblock;653}654 655void udf_free_blocks(struct super_block *sb, struct inode *inode,656 struct kernel_lb_addr *bloc, uint32_t offset,657 uint32_t count)658{659 uint16_t partition = bloc->partitionReferenceNum;660 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];661 uint32_t blk;662 663 if (check_add_overflow(bloc->logicalBlockNum, offset, &blk) ||664 check_add_overflow(blk, count, &blk) ||665 bloc->logicalBlockNum + count > map->s_partition_len) {666 udf_debug("Invalid request to free blocks: (%d, %u), off %u, "667 "len %u, partition len %u\n",668 partition, bloc->logicalBlockNum, offset, count,669 map->s_partition_len);670 return;671 }672 673 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) {674 udf_bitmap_free_blocks(sb, map->s_uspace.s_bitmap,675 bloc, offset, count);676 } else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) {677 udf_table_free_blocks(sb, map->s_uspace.s_table,678 bloc, offset, count);679 }680 681 if (inode) {682 inode_sub_bytes(inode,683 ((sector_t)count) << sb->s_blocksize_bits);684 }685}686 687inline int udf_prealloc_blocks(struct super_block *sb,688 struct inode *inode,689 uint16_t partition, uint32_t first_block,690 uint32_t block_count)691{692 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];693 int allocated;694 695 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP)696 allocated = udf_bitmap_prealloc_blocks(sb,697 map->s_uspace.s_bitmap,698 partition, first_block,699 block_count);700 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE)701 allocated = udf_table_prealloc_blocks(sb,702 map->s_uspace.s_table,703 partition, first_block,704 block_count);705 else706 return 0;707 708 if (inode && allocated > 0)709 inode_add_bytes(inode, allocated << sb->s_blocksize_bits);710 return allocated;711}712 713inline udf_pblk_t udf_new_block(struct super_block *sb,714 struct inode *inode,715 uint16_t partition, uint32_t goal, int *err)716{717 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];718 udf_pblk_t block;719 720 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP)721 block = udf_bitmap_new_block(sb,722 map->s_uspace.s_bitmap,723 partition, goal, err);724 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE)725 block = udf_table_new_block(sb,726 map->s_uspace.s_table,727 partition, goal, err);728 else {729 *err = -EIO;730 return 0;731 }732 if (inode && block)733 inode_add_bytes(inode, sb->s_blocksize);734 return block;735}736