5 * Block allocation handling routines for the OSTA-UDF(tm) filesystem.
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.
13 * (C) 1999-2001 Ben Fennema
14 * (C) 1999 Stelias Computing Inc
18 * 02/24/99 blf Created.
24 #include <linux/bitops.h>
29 #define udf_clear_bit __test_and_clear_bit_le
30 #define udf_set_bit __test_and_set_bit_le
31 #define udf_test_bit test_bit_le
32 #define udf_find_next_one_bit find_next_bit_le
34 static int read_block_bitmap(struct super_block *sb,
35 struct udf_bitmap *bitmap, unsigned int block,
36 unsigned long bitmap_nr)
38 struct buffer_head *bh = NULL;
40 int max_bits, off, count;
41 struct kernel_lb_addr loc;
43 loc.logicalBlockNum = bitmap->s_extPosition;
44 loc.partitionReferenceNum = UDF_SB(sb)->s_partition;
46 bh = udf_tread(sb, udf_get_lb_pblock(sb, &loc, block));
47 bitmap->s_block_bitmap[bitmap_nr] = bh;
51 /* Check consistency of Space Bitmap buffer. */
52 max_bits = sb->s_blocksize * 8;
54 off = sizeof(struct spaceBitmapDesc) << 3;
55 count = min(max_bits - off, bitmap->s_nr_groups);
58 * Rough check if bitmap number is too big to have any bitmap
62 (bitmap->s_nr_groups >> (sb->s_blocksize_bits + 3)) + 2)
65 count = bitmap->s_nr_groups - bitmap_nr * max_bits +
66 (sizeof(struct spaceBitmapDesc) << 3);
67 count = min(count, max_bits);
70 for (i = 0; i < count; i++)
71 if (udf_test_bit(i + off, bh->b_data))
76 static int __load_block_bitmap(struct super_block *sb,
77 struct udf_bitmap *bitmap,
78 unsigned int block_group)
81 int nr_groups = bitmap->s_nr_groups;
83 if (block_group >= nr_groups) {
84 udf_debug("block_group (%d) > nr_groups (%d)\n",
85 block_group, nr_groups);
88 if (bitmap->s_block_bitmap[block_group])
91 retval = read_block_bitmap(sb, bitmap, block_group, block_group);
98 static inline int load_block_bitmap(struct super_block *sb,
99 struct udf_bitmap *bitmap,
100 unsigned int block_group)
104 slot = __load_block_bitmap(sb, bitmap, block_group);
109 if (!bitmap->s_block_bitmap[slot])
115 static void udf_add_free_space(struct super_block *sb, u16 partition, u32 cnt)
117 struct udf_sb_info *sbi = UDF_SB(sb);
118 struct logicalVolIntegrityDesc *lvid;
123 lvid = (struct logicalVolIntegrityDesc *)sbi->s_lvid_bh->b_data;
124 le32_add_cpu(&lvid->freeSpaceTable[partition], cnt);
125 udf_updated_lvid(sb);
128 static void udf_bitmap_free_blocks(struct super_block *sb,
129 struct udf_bitmap *bitmap,
130 struct kernel_lb_addr *bloc,
134 struct udf_sb_info *sbi = UDF_SB(sb);
135 struct buffer_head *bh = NULL;
136 struct udf_part_map *partmap;
138 unsigned long block_group;
142 unsigned long overflow;
144 mutex_lock(&sbi->s_alloc_mutex);
145 partmap = &sbi->s_partmaps[bloc->partitionReferenceNum];
146 if (bloc->logicalBlockNum + count < count ||
147 (bloc->logicalBlockNum + count) > partmap->s_partition_len) {
148 udf_debug("%d < %d || %d + %d > %d\n",
149 bloc->logicalBlockNum, 0,
150 bloc->logicalBlockNum, count,
151 partmap->s_partition_len);
155 block = bloc->logicalBlockNum + offset +
156 (sizeof(struct spaceBitmapDesc) << 3);
160 block_group = block >> (sb->s_blocksize_bits + 3);
161 bit = block % (sb->s_blocksize << 3);
164 * Check to see if we are freeing blocks across a group boundary.
166 if (bit + count > (sb->s_blocksize << 3)) {
167 overflow = bit + count - (sb->s_blocksize << 3);
170 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
174 bh = bitmap->s_block_bitmap[bitmap_nr];
175 for (i = 0; i < count; i++) {
176 if (udf_set_bit(bit + i, bh->b_data)) {
177 udf_debug("bit %ld already set\n", bit + i);
178 udf_debug("byte=%2x\n",
179 ((char *)bh->b_data)[(bit + i) >> 3]);
182 udf_add_free_space(sb, sbi->s_partition, count);
183 mark_buffer_dirty(bh);
191 mutex_unlock(&sbi->s_alloc_mutex);
194 static int udf_bitmap_prealloc_blocks(struct super_block *sb,
195 struct udf_bitmap *bitmap,
196 uint16_t partition, uint32_t first_block,
197 uint32_t block_count)
199 struct udf_sb_info *sbi = UDF_SB(sb);
201 int bit, block, block_group, group_start;
202 int nr_groups, bitmap_nr;
203 struct buffer_head *bh;
206 mutex_lock(&sbi->s_alloc_mutex);
207 part_len = sbi->s_partmaps[partition].s_partition_len;
208 if (first_block >= part_len)
211 if (first_block + block_count > part_len)
212 block_count = part_len - first_block;
215 nr_groups = udf_compute_nr_groups(sb, partition);
216 block = first_block + (sizeof(struct spaceBitmapDesc) << 3);
217 block_group = block >> (sb->s_blocksize_bits + 3);
218 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);
220 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
223 bh = bitmap->s_block_bitmap[bitmap_nr];
225 bit = block % (sb->s_blocksize << 3);
227 while (bit < (sb->s_blocksize << 3) && block_count > 0) {
228 if (!udf_clear_bit(bit, bh->b_data))
235 mark_buffer_dirty(bh);
236 } while (block_count > 0);
239 udf_add_free_space(sb, partition, -alloc_count);
240 mutex_unlock(&sbi->s_alloc_mutex);
244 static int udf_bitmap_new_block(struct super_block *sb,
245 struct udf_bitmap *bitmap, uint16_t partition,
246 uint32_t goal, int *err)
248 struct udf_sb_info *sbi = UDF_SB(sb);
249 int newbit, bit = 0, block, block_group, group_start;
250 int end_goal, nr_groups, bitmap_nr, i;
251 struct buffer_head *bh = NULL;
256 mutex_lock(&sbi->s_alloc_mutex);
259 if (goal >= sbi->s_partmaps[partition].s_partition_len)
262 nr_groups = bitmap->s_nr_groups;
263 block = goal + (sizeof(struct spaceBitmapDesc) << 3);
264 block_group = block >> (sb->s_blocksize_bits + 3);
265 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);
267 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
270 bh = bitmap->s_block_bitmap[bitmap_nr];
271 ptr = memscan((char *)bh->b_data + group_start, 0xFF,
272 sb->s_blocksize - group_start);
274 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) {
275 bit = block % (sb->s_blocksize << 3);
276 if (udf_test_bit(bit, bh->b_data))
279 end_goal = (bit + 63) & ~63;
280 bit = udf_find_next_one_bit(bh->b_data, end_goal, bit);
284 ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF,
285 sb->s_blocksize - ((bit + 7) >> 3));
286 newbit = (ptr - ((char *)bh->b_data)) << 3;
287 if (newbit < sb->s_blocksize << 3) {
292 newbit = udf_find_next_one_bit(bh->b_data,
293 sb->s_blocksize << 3, bit);
294 if (newbit < sb->s_blocksize << 3) {
300 for (i = 0; i < (nr_groups * 2); i++) {
302 if (block_group >= nr_groups)
304 group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);
306 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
309 bh = bitmap->s_block_bitmap[bitmap_nr];
311 ptr = memscan((char *)bh->b_data + group_start, 0xFF,
312 sb->s_blocksize - group_start);
313 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) {
314 bit = (ptr - ((char *)bh->b_data)) << 3;
318 bit = udf_find_next_one_bit(bh->b_data,
319 sb->s_blocksize << 3,
321 if (bit < sb->s_blocksize << 3)
325 if (i >= (nr_groups * 2)) {
326 mutex_unlock(&sbi->s_alloc_mutex);
329 if (bit < sb->s_blocksize << 3)
332 bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3,
334 if (bit >= sb->s_blocksize << 3) {
335 mutex_unlock(&sbi->s_alloc_mutex);
341 while (i < 7 && bit > (group_start << 3) &&
342 udf_test_bit(bit - 1, bh->b_data)) {
348 newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) -
349 (sizeof(struct spaceBitmapDesc) << 3);
351 if (!udf_clear_bit(bit, bh->b_data)) {
352 udf_debug("bit already cleared for block %d\n", bit);
356 mark_buffer_dirty(bh);
358 udf_add_free_space(sb, partition, -1);
359 mutex_unlock(&sbi->s_alloc_mutex);
365 mutex_unlock(&sbi->s_alloc_mutex);
369 static void udf_table_free_blocks(struct super_block *sb,
371 struct kernel_lb_addr *bloc,
375 struct udf_sb_info *sbi = UDF_SB(sb);
376 struct udf_part_map *partmap;
379 struct kernel_lb_addr eloc;
380 struct extent_position oepos, epos;
382 struct udf_inode_info *iinfo;
384 mutex_lock(&sbi->s_alloc_mutex);
385 partmap = &sbi->s_partmaps[bloc->partitionReferenceNum];
386 if (bloc->logicalBlockNum + count < count ||
387 (bloc->logicalBlockNum + count) > partmap->s_partition_len) {
388 udf_debug("%d < %d || %d + %d > %d\n",
389 bloc->logicalBlockNum, 0,
390 bloc->logicalBlockNum, count,
391 partmap->s_partition_len);
395 iinfo = UDF_I(table);
396 udf_add_free_space(sb, sbi->s_partition, count);
398 start = bloc->logicalBlockNum + offset;
399 end = bloc->logicalBlockNum + offset + count - 1;
401 epos.offset = oepos.offset = sizeof(struct unallocSpaceEntry);
403 epos.block = oepos.block = iinfo->i_location;
404 epos.bh = oepos.bh = NULL;
407 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) {
408 if (((eloc.logicalBlockNum +
409 (elen >> sb->s_blocksize_bits)) == start)) {
410 if ((0x3FFFFFFF - elen) <
411 (count << sb->s_blocksize_bits)) {
412 uint32_t tmp = ((0x3FFFFFFF - elen) >>
413 sb->s_blocksize_bits);
416 elen = (etype << 30) |
417 (0x40000000 - sb->s_blocksize);
419 elen = (etype << 30) |
421 (count << sb->s_blocksize_bits));
425 udf_write_aext(table, &oepos, &eloc, elen, 1);
426 } else if (eloc.logicalBlockNum == (end + 1)) {
427 if ((0x3FFFFFFF - elen) <
428 (count << sb->s_blocksize_bits)) {
429 uint32_t tmp = ((0x3FFFFFFF - elen) >>
430 sb->s_blocksize_bits);
433 eloc.logicalBlockNum -= tmp;
434 elen = (etype << 30) |
435 (0x40000000 - sb->s_blocksize);
437 eloc.logicalBlockNum = start;
438 elen = (etype << 30) |
440 (count << sb->s_blocksize_bits));
444 udf_write_aext(table, &oepos, &eloc, elen, 1);
447 if (epos.bh != oepos.bh) {
448 oepos.block = epos.block;
454 oepos.offset = epos.offset;
460 * NOTE: we CANNOT use udf_add_aext here, as it can try to
461 * allocate a new block, and since we hold the super block
462 * lock already very bad things would happen :)
464 * We copy the behavior of udf_add_aext, but instead of
465 * trying to allocate a new block close to the existing one,
466 * we just steal a block from the extent we are trying to add.
468 * It would be nice if the blocks were close together, but it
474 eloc.logicalBlockNum = start;
475 elen = EXT_RECORDED_ALLOCATED |
476 (count << sb->s_blocksize_bits);
478 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
479 adsize = sizeof(struct short_ad);
480 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
481 adsize = sizeof(struct long_ad);
488 if (epos.offset + (2 * adsize) > sb->s_blocksize) {
489 /* Steal a block from the extent being free'd */
490 udf_setup_indirect_aext(table, eloc.logicalBlockNum,
493 eloc.logicalBlockNum++;
494 elen -= sb->s_blocksize;
497 /* It's possible that stealing the block emptied the extent */
499 __udf_add_aext(table, &epos, &eloc, elen, 1);
506 mutex_unlock(&sbi->s_alloc_mutex);
510 static int udf_table_prealloc_blocks(struct super_block *sb,
511 struct inode *table, uint16_t partition,
512 uint32_t first_block, uint32_t block_count)
514 struct udf_sb_info *sbi = UDF_SB(sb);
516 uint32_t elen, adsize;
517 struct kernel_lb_addr eloc;
518 struct extent_position epos;
520 struct udf_inode_info *iinfo;
522 if (first_block >= sbi->s_partmaps[partition].s_partition_len)
525 iinfo = UDF_I(table);
526 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
527 adsize = sizeof(struct short_ad);
528 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
529 adsize = sizeof(struct long_ad);
533 mutex_lock(&sbi->s_alloc_mutex);
534 epos.offset = sizeof(struct unallocSpaceEntry);
535 epos.block = iinfo->i_location;
537 eloc.logicalBlockNum = 0xFFFFFFFF;
539 while (first_block != eloc.logicalBlockNum &&
540 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) {
541 udf_debug("eloc=%d, elen=%d, first_block=%d\n",
542 eloc.logicalBlockNum, elen, first_block);
543 ; /* empty loop body */
546 if (first_block == eloc.logicalBlockNum) {
547 epos.offset -= adsize;
549 alloc_count = (elen >> sb->s_blocksize_bits);
550 if (alloc_count > block_count) {
551 alloc_count = block_count;
552 eloc.logicalBlockNum += alloc_count;
553 elen -= (alloc_count << sb->s_blocksize_bits);
554 udf_write_aext(table, &epos, &eloc,
555 (etype << 30) | elen, 1);
557 udf_delete_aext(table, epos);
565 udf_add_free_space(sb, partition, -alloc_count);
566 mutex_unlock(&sbi->s_alloc_mutex);
570 static int udf_table_new_block(struct super_block *sb,
571 struct inode *table, uint16_t partition,
572 uint32_t goal, int *err)
574 struct udf_sb_info *sbi = UDF_SB(sb);
575 uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF;
576 uint32_t newblock = 0, adsize;
577 uint32_t elen, goal_elen = 0;
578 struct kernel_lb_addr eloc, goal_eloc;
579 struct extent_position epos, goal_epos;
581 struct udf_inode_info *iinfo = UDF_I(table);
585 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
586 adsize = sizeof(struct short_ad);
587 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
588 adsize = sizeof(struct long_ad);
592 mutex_lock(&sbi->s_alloc_mutex);
593 if (goal >= sbi->s_partmaps[partition].s_partition_len)
596 /* We search for the closest matching block to goal. If we find
597 a exact hit, we stop. Otherwise we keep going till we run out
598 of extents. We store the buffer_head, bloc, and extoffset
599 of the current closest match and use that when we are done.
601 epos.offset = sizeof(struct unallocSpaceEntry);
602 epos.block = iinfo->i_location;
603 epos.bh = goal_epos.bh = NULL;
606 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) {
607 if (goal >= eloc.logicalBlockNum) {
608 if (goal < eloc.logicalBlockNum +
609 (elen >> sb->s_blocksize_bits))
612 nspread = goal - eloc.logicalBlockNum -
613 (elen >> sb->s_blocksize_bits);
615 nspread = eloc.logicalBlockNum - goal;
618 if (nspread < spread) {
620 if (goal_epos.bh != epos.bh) {
621 brelse(goal_epos.bh);
622 goal_epos.bh = epos.bh;
623 get_bh(goal_epos.bh);
625 goal_epos.block = epos.block;
626 goal_epos.offset = epos.offset - adsize;
628 goal_elen = (etype << 30) | elen;
634 if (spread == 0xFFFFFFFF) {
635 brelse(goal_epos.bh);
636 mutex_unlock(&sbi->s_alloc_mutex);
640 /* Only allocate blocks from the beginning of the extent.
641 That way, we only delete (empty) extents, never have to insert an
642 extent because of splitting */
643 /* This works, but very poorly.... */
645 newblock = goal_eloc.logicalBlockNum;
646 goal_eloc.logicalBlockNum++;
647 goal_elen -= sb->s_blocksize;
650 udf_write_aext(table, &goal_epos, &goal_eloc, goal_elen, 1);
652 udf_delete_aext(table, goal_epos);
653 brelse(goal_epos.bh);
655 udf_add_free_space(sb, partition, -1);
657 mutex_unlock(&sbi->s_alloc_mutex);
662 void udf_free_blocks(struct super_block *sb, struct inode *inode,
663 struct kernel_lb_addr *bloc, uint32_t offset,
666 uint16_t partition = bloc->partitionReferenceNum;
667 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
669 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) {
670 udf_bitmap_free_blocks(sb, map->s_uspace.s_bitmap,
671 bloc, offset, count);
672 } else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) {
673 udf_table_free_blocks(sb, map->s_uspace.s_table,
674 bloc, offset, count);
675 } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) {
676 udf_bitmap_free_blocks(sb, map->s_fspace.s_bitmap,
677 bloc, offset, count);
678 } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) {
679 udf_table_free_blocks(sb, map->s_fspace.s_table,
680 bloc, offset, count);
684 inode_sub_bytes(inode,
685 ((sector_t)count) << sb->s_blocksize_bits);
689 inline int udf_prealloc_blocks(struct super_block *sb,
691 uint16_t partition, uint32_t first_block,
692 uint32_t block_count)
694 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
697 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP)
698 allocated = udf_bitmap_prealloc_blocks(sb,
699 map->s_uspace.s_bitmap,
700 partition, first_block,
702 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE)
703 allocated = udf_table_prealloc_blocks(sb,
704 map->s_uspace.s_table,
705 partition, first_block,
707 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP)
708 allocated = udf_bitmap_prealloc_blocks(sb,
709 map->s_fspace.s_bitmap,
710 partition, first_block,
712 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE)
713 allocated = udf_table_prealloc_blocks(sb,
714 map->s_fspace.s_table,
715 partition, first_block,
720 if (inode && allocated > 0)
721 inode_add_bytes(inode, allocated << sb->s_blocksize_bits);
725 inline int udf_new_block(struct super_block *sb,
727 uint16_t partition, uint32_t goal, int *err)
729 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
732 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP)
733 block = udf_bitmap_new_block(sb,
734 map->s_uspace.s_bitmap,
735 partition, goal, err);
736 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE)
737 block = udf_table_new_block(sb,
738 map->s_uspace.s_table,
739 partition, goal, err);
740 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP)
741 block = udf_bitmap_new_block(sb,
742 map->s_fspace.s_bitmap,
743 partition, goal, err);
744 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE)
745 block = udf_table_new_block(sb,
746 map->s_fspace.s_table,
747 partition, goal, err);
753 inode_add_bytes(inode, sb->s_blocksize);