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 struct kernel_lb_addr loc
;
42 loc
.logicalBlockNum
= bitmap
->s_extPosition
;
43 loc
.partitionReferenceNum
= UDF_SB(sb
)->s_partition
;
45 bh
= udf_tread(sb
, udf_get_lb_pblock(sb
, &loc
, block
));
49 bitmap
->s_block_bitmap
[bitmap_nr
] = bh
;
53 static int __load_block_bitmap(struct super_block
*sb
,
54 struct udf_bitmap
*bitmap
,
55 unsigned int block_group
)
58 int nr_groups
= bitmap
->s_nr_groups
;
60 if (block_group
>= nr_groups
) {
61 udf_debug("block_group (%u) > nr_groups (%d)\n",
62 block_group
, nr_groups
);
65 if (bitmap
->s_block_bitmap
[block_group
])
68 retval
= read_block_bitmap(sb
, bitmap
, block_group
, block_group
);
75 static inline int load_block_bitmap(struct super_block
*sb
,
76 struct udf_bitmap
*bitmap
,
77 unsigned int block_group
)
81 slot
= __load_block_bitmap(sb
, bitmap
, block_group
);
86 if (!bitmap
->s_block_bitmap
[slot
])
92 static void udf_add_free_space(struct super_block
*sb
, u16 partition
, u32 cnt
)
94 struct udf_sb_info
*sbi
= UDF_SB(sb
);
95 struct logicalVolIntegrityDesc
*lvid
;
100 lvid
= (struct logicalVolIntegrityDesc
*)sbi
->s_lvid_bh
->b_data
;
101 le32_add_cpu(&lvid
->freeSpaceTable
[partition
], cnt
);
102 udf_updated_lvid(sb
);
105 static void udf_bitmap_free_blocks(struct super_block
*sb
,
106 struct udf_bitmap
*bitmap
,
107 struct kernel_lb_addr
*bloc
,
111 struct udf_sb_info
*sbi
= UDF_SB(sb
);
112 struct buffer_head
*bh
= NULL
;
113 struct udf_part_map
*partmap
;
115 unsigned long block_group
;
119 unsigned long overflow
;
121 mutex_lock(&sbi
->s_alloc_mutex
);
122 partmap
= &sbi
->s_partmaps
[bloc
->partitionReferenceNum
];
123 if (bloc
->logicalBlockNum
+ count
< count
||
124 (bloc
->logicalBlockNum
+ count
) > partmap
->s_partition_len
) {
125 udf_debug("%u < %d || %u + %u > %u\n",
126 bloc
->logicalBlockNum
, 0,
127 bloc
->logicalBlockNum
, count
,
128 partmap
->s_partition_len
);
132 block
= bloc
->logicalBlockNum
+ offset
+
133 (sizeof(struct spaceBitmapDesc
) << 3);
137 block_group
= block
>> (sb
->s_blocksize_bits
+ 3);
138 bit
= block
% (sb
->s_blocksize
<< 3);
141 * Check to see if we are freeing blocks across a group boundary.
143 if (bit
+ count
> (sb
->s_blocksize
<< 3)) {
144 overflow
= bit
+ count
- (sb
->s_blocksize
<< 3);
147 bitmap_nr
= load_block_bitmap(sb
, bitmap
, block_group
);
151 bh
= bitmap
->s_block_bitmap
[bitmap_nr
];
152 for (i
= 0; i
< count
; i
++) {
153 if (udf_set_bit(bit
+ i
, bh
->b_data
)) {
154 udf_debug("bit %lu already set\n", bit
+ i
);
155 udf_debug("byte=%2x\n",
156 ((__u8
*)bh
->b_data
)[(bit
+ i
) >> 3]);
159 udf_add_free_space(sb
, sbi
->s_partition
, count
);
160 mark_buffer_dirty(bh
);
168 mutex_unlock(&sbi
->s_alloc_mutex
);
171 static int udf_bitmap_prealloc_blocks(struct super_block
*sb
,
172 struct udf_bitmap
*bitmap
,
173 uint16_t partition
, uint32_t first_block
,
174 uint32_t block_count
)
176 struct udf_sb_info
*sbi
= UDF_SB(sb
);
178 int bit
, block
, block_group
;
180 struct buffer_head
*bh
;
183 mutex_lock(&sbi
->s_alloc_mutex
);
184 part_len
= sbi
->s_partmaps
[partition
].s_partition_len
;
185 if (first_block
>= part_len
)
188 if (first_block
+ block_count
> part_len
)
189 block_count
= part_len
- first_block
;
192 block
= first_block
+ (sizeof(struct spaceBitmapDesc
) << 3);
193 block_group
= block
>> (sb
->s_blocksize_bits
+ 3);
195 bitmap_nr
= load_block_bitmap(sb
, bitmap
, block_group
);
198 bh
= bitmap
->s_block_bitmap
[bitmap_nr
];
200 bit
= block
% (sb
->s_blocksize
<< 3);
202 while (bit
< (sb
->s_blocksize
<< 3) && block_count
> 0) {
203 if (!udf_clear_bit(bit
, bh
->b_data
))
210 mark_buffer_dirty(bh
);
211 } while (block_count
> 0);
214 udf_add_free_space(sb
, partition
, -alloc_count
);
215 mutex_unlock(&sbi
->s_alloc_mutex
);
219 static udf_pblk_t
udf_bitmap_new_block(struct super_block
*sb
,
220 struct udf_bitmap
*bitmap
, uint16_t partition
,
221 uint32_t goal
, int *err
)
223 struct udf_sb_info
*sbi
= UDF_SB(sb
);
226 int block_group
, group_start
;
227 int end_goal
, nr_groups
, bitmap_nr
, i
;
228 struct buffer_head
*bh
= NULL
;
230 udf_pblk_t newblock
= 0;
233 mutex_lock(&sbi
->s_alloc_mutex
);
236 if (goal
>= sbi
->s_partmaps
[partition
].s_partition_len
)
239 nr_groups
= bitmap
->s_nr_groups
;
240 block
= goal
+ (sizeof(struct spaceBitmapDesc
) << 3);
241 block_group
= block
>> (sb
->s_blocksize_bits
+ 3);
242 group_start
= block_group
? 0 : sizeof(struct spaceBitmapDesc
);
244 bitmap_nr
= load_block_bitmap(sb
, bitmap
, block_group
);
247 bh
= bitmap
->s_block_bitmap
[bitmap_nr
];
248 ptr
= memscan((char *)bh
->b_data
+ group_start
, 0xFF,
249 sb
->s_blocksize
- group_start
);
251 if ((ptr
- ((char *)bh
->b_data
)) < sb
->s_blocksize
) {
252 bit
= block
% (sb
->s_blocksize
<< 3);
253 if (udf_test_bit(bit
, bh
->b_data
))
256 end_goal
= (bit
+ 63) & ~63;
257 bit
= udf_find_next_one_bit(bh
->b_data
, end_goal
, bit
);
261 ptr
= memscan((char *)bh
->b_data
+ (bit
>> 3), 0xFF,
262 sb
->s_blocksize
- ((bit
+ 7) >> 3));
263 newbit
= (ptr
- ((char *)bh
->b_data
)) << 3;
264 if (newbit
< sb
->s_blocksize
<< 3) {
269 newbit
= udf_find_next_one_bit(bh
->b_data
,
270 sb
->s_blocksize
<< 3, bit
);
271 if (newbit
< sb
->s_blocksize
<< 3) {
277 for (i
= 0; i
< (nr_groups
* 2); i
++) {
279 if (block_group
>= nr_groups
)
281 group_start
= block_group
? 0 : sizeof(struct spaceBitmapDesc
);
283 bitmap_nr
= load_block_bitmap(sb
, bitmap
, block_group
);
286 bh
= bitmap
->s_block_bitmap
[bitmap_nr
];
288 ptr
= memscan((char *)bh
->b_data
+ group_start
, 0xFF,
289 sb
->s_blocksize
- group_start
);
290 if ((ptr
- ((char *)bh
->b_data
)) < sb
->s_blocksize
) {
291 bit
= (ptr
- ((char *)bh
->b_data
)) << 3;
295 bit
= udf_find_next_one_bit(bh
->b_data
,
296 sb
->s_blocksize
<< 3,
298 if (bit
< sb
->s_blocksize
<< 3)
302 if (i
>= (nr_groups
* 2)) {
303 mutex_unlock(&sbi
->s_alloc_mutex
);
306 if (bit
< sb
->s_blocksize
<< 3)
309 bit
= udf_find_next_one_bit(bh
->b_data
, sb
->s_blocksize
<< 3,
311 if (bit
>= sb
->s_blocksize
<< 3) {
312 mutex_unlock(&sbi
->s_alloc_mutex
);
318 while (i
< 7 && bit
> (group_start
<< 3) &&
319 udf_test_bit(bit
- 1, bh
->b_data
)) {
325 newblock
= bit
+ (block_group
<< (sb
->s_blocksize_bits
+ 3)) -
326 (sizeof(struct spaceBitmapDesc
) << 3);
328 if (newblock
>= sbi
->s_partmaps
[partition
].s_partition_len
) {
330 * Ran off the end of the bitmap, and bits following are
331 * non-compliant (not all zero)
333 udf_err(sb
, "bitmap for partition %d corrupted (block %u marked"
334 " as free, partition length is %u)\n", partition
,
335 newblock
, sbi
->s_partmaps
[partition
].s_partition_len
);
339 if (!udf_clear_bit(bit
, bh
->b_data
)) {
340 udf_debug("bit already cleared for block %d\n", bit
);
344 mark_buffer_dirty(bh
);
346 udf_add_free_space(sb
, partition
, -1);
347 mutex_unlock(&sbi
->s_alloc_mutex
);
353 mutex_unlock(&sbi
->s_alloc_mutex
);
357 static void udf_table_free_blocks(struct super_block
*sb
,
359 struct kernel_lb_addr
*bloc
,
363 struct udf_sb_info
*sbi
= UDF_SB(sb
);
364 struct udf_part_map
*partmap
;
367 struct kernel_lb_addr eloc
;
368 struct extent_position oepos
, epos
;
370 struct udf_inode_info
*iinfo
;
372 mutex_lock(&sbi
->s_alloc_mutex
);
373 partmap
= &sbi
->s_partmaps
[bloc
->partitionReferenceNum
];
374 if (bloc
->logicalBlockNum
+ count
< count
||
375 (bloc
->logicalBlockNum
+ count
) > partmap
->s_partition_len
) {
376 udf_debug("%u < %d || %u + %u > %u\n",
377 bloc
->logicalBlockNum
, 0,
378 bloc
->logicalBlockNum
, count
,
379 partmap
->s_partition_len
);
383 iinfo
= UDF_I(table
);
384 udf_add_free_space(sb
, sbi
->s_partition
, count
);
386 start
= bloc
->logicalBlockNum
+ offset
;
387 end
= bloc
->logicalBlockNum
+ offset
+ count
- 1;
389 epos
.offset
= oepos
.offset
= sizeof(struct unallocSpaceEntry
);
391 epos
.block
= oepos
.block
= iinfo
->i_location
;
392 epos
.bh
= oepos
.bh
= NULL
;
395 (etype
= udf_next_aext(table
, &epos
, &eloc
, &elen
, 1)) != -1) {
396 if (((eloc
.logicalBlockNum
+
397 (elen
>> sb
->s_blocksize_bits
)) == start
)) {
398 if ((0x3FFFFFFF - elen
) <
399 (count
<< sb
->s_blocksize_bits
)) {
400 uint32_t tmp
= ((0x3FFFFFFF - elen
) >>
401 sb
->s_blocksize_bits
);
404 elen
= (etype
<< 30) |
405 (0x40000000 - sb
->s_blocksize
);
407 elen
= (etype
<< 30) |
409 (count
<< sb
->s_blocksize_bits
));
413 udf_write_aext(table
, &oepos
, &eloc
, elen
, 1);
414 } else if (eloc
.logicalBlockNum
== (end
+ 1)) {
415 if ((0x3FFFFFFF - elen
) <
416 (count
<< sb
->s_blocksize_bits
)) {
417 uint32_t tmp
= ((0x3FFFFFFF - elen
) >>
418 sb
->s_blocksize_bits
);
421 eloc
.logicalBlockNum
-= tmp
;
422 elen
= (etype
<< 30) |
423 (0x40000000 - sb
->s_blocksize
);
425 eloc
.logicalBlockNum
= start
;
426 elen
= (etype
<< 30) |
428 (count
<< sb
->s_blocksize_bits
));
432 udf_write_aext(table
, &oepos
, &eloc
, elen
, 1);
435 if (epos
.bh
!= oepos
.bh
) {
436 oepos
.block
= epos
.block
;
442 oepos
.offset
= epos
.offset
;
448 * NOTE: we CANNOT use udf_add_aext here, as it can try to
449 * allocate a new block, and since we hold the super block
450 * lock already very bad things would happen :)
452 * We copy the behavior of udf_add_aext, but instead of
453 * trying to allocate a new block close to the existing one,
454 * we just steal a block from the extent we are trying to add.
456 * It would be nice if the blocks were close together, but it
462 eloc
.logicalBlockNum
= start
;
463 elen
= EXT_RECORDED_ALLOCATED
|
464 (count
<< sb
->s_blocksize_bits
);
466 if (iinfo
->i_alloc_type
== ICBTAG_FLAG_AD_SHORT
)
467 adsize
= sizeof(struct short_ad
);
468 else if (iinfo
->i_alloc_type
== ICBTAG_FLAG_AD_LONG
)
469 adsize
= sizeof(struct long_ad
);
476 if (epos
.offset
+ (2 * adsize
) > sb
->s_blocksize
) {
477 /* Steal a block from the extent being free'd */
478 udf_setup_indirect_aext(table
, eloc
.logicalBlockNum
,
481 eloc
.logicalBlockNum
++;
482 elen
-= sb
->s_blocksize
;
485 /* It's possible that stealing the block emptied the extent */
487 __udf_add_aext(table
, &epos
, &eloc
, elen
, 1);
494 mutex_unlock(&sbi
->s_alloc_mutex
);
498 static int udf_table_prealloc_blocks(struct super_block
*sb
,
499 struct inode
*table
, uint16_t partition
,
500 uint32_t first_block
, uint32_t block_count
)
502 struct udf_sb_info
*sbi
= UDF_SB(sb
);
504 uint32_t elen
, adsize
;
505 struct kernel_lb_addr eloc
;
506 struct extent_position epos
;
508 struct udf_inode_info
*iinfo
;
510 if (first_block
>= sbi
->s_partmaps
[partition
].s_partition_len
)
513 iinfo
= UDF_I(table
);
514 if (iinfo
->i_alloc_type
== ICBTAG_FLAG_AD_SHORT
)
515 adsize
= sizeof(struct short_ad
);
516 else if (iinfo
->i_alloc_type
== ICBTAG_FLAG_AD_LONG
)
517 adsize
= sizeof(struct long_ad
);
521 mutex_lock(&sbi
->s_alloc_mutex
);
522 epos
.offset
= sizeof(struct unallocSpaceEntry
);
523 epos
.block
= iinfo
->i_location
;
525 eloc
.logicalBlockNum
= 0xFFFFFFFF;
527 while (first_block
!= eloc
.logicalBlockNum
&&
528 (etype
= udf_next_aext(table
, &epos
, &eloc
, &elen
, 1)) != -1) {
529 udf_debug("eloc=%u, elen=%u, first_block=%u\n",
530 eloc
.logicalBlockNum
, elen
, first_block
);
531 ; /* empty loop body */
534 if (first_block
== eloc
.logicalBlockNum
) {
535 epos
.offset
-= adsize
;
537 alloc_count
= (elen
>> sb
->s_blocksize_bits
);
538 if (alloc_count
> block_count
) {
539 alloc_count
= block_count
;
540 eloc
.logicalBlockNum
+= alloc_count
;
541 elen
-= (alloc_count
<< sb
->s_blocksize_bits
);
542 udf_write_aext(table
, &epos
, &eloc
,
543 (etype
<< 30) | elen
, 1);
545 udf_delete_aext(table
, epos
);
553 udf_add_free_space(sb
, partition
, -alloc_count
);
554 mutex_unlock(&sbi
->s_alloc_mutex
);
558 static udf_pblk_t
udf_table_new_block(struct super_block
*sb
,
559 struct inode
*table
, uint16_t partition
,
560 uint32_t goal
, int *err
)
562 struct udf_sb_info
*sbi
= UDF_SB(sb
);
563 uint32_t spread
= 0xFFFFFFFF, nspread
= 0xFFFFFFFF;
564 udf_pblk_t newblock
= 0;
566 uint32_t elen
, goal_elen
= 0;
567 struct kernel_lb_addr eloc
, uninitialized_var(goal_eloc
);
568 struct extent_position epos
, goal_epos
;
570 struct udf_inode_info
*iinfo
= UDF_I(table
);
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
);
581 mutex_lock(&sbi
->s_alloc_mutex
);
582 if (goal
>= sbi
->s_partmaps
[partition
].s_partition_len
)
585 /* We search for the closest matching block to goal. If we find
586 a exact hit, we stop. Otherwise we keep going till we run out
587 of extents. We store the buffer_head, bloc, and extoffset
588 of the current closest match and use that when we are done.
590 epos
.offset
= sizeof(struct unallocSpaceEntry
);
591 epos
.block
= iinfo
->i_location
;
592 epos
.bh
= goal_epos
.bh
= NULL
;
595 (etype
= udf_next_aext(table
, &epos
, &eloc
, &elen
, 1)) != -1) {
596 if (goal
>= eloc
.logicalBlockNum
) {
597 if (goal
< eloc
.logicalBlockNum
+
598 (elen
>> sb
->s_blocksize_bits
))
601 nspread
= goal
- eloc
.logicalBlockNum
-
602 (elen
>> sb
->s_blocksize_bits
);
604 nspread
= eloc
.logicalBlockNum
- goal
;
607 if (nspread
< spread
) {
609 if (goal_epos
.bh
!= epos
.bh
) {
610 brelse(goal_epos
.bh
);
611 goal_epos
.bh
= epos
.bh
;
612 get_bh(goal_epos
.bh
);
614 goal_epos
.block
= epos
.block
;
615 goal_epos
.offset
= epos
.offset
- adsize
;
617 goal_elen
= (etype
<< 30) | elen
;
623 if (spread
== 0xFFFFFFFF) {
624 brelse(goal_epos
.bh
);
625 mutex_unlock(&sbi
->s_alloc_mutex
);
629 /* Only allocate blocks from the beginning of the extent.
630 That way, we only delete (empty) extents, never have to insert an
631 extent because of splitting */
632 /* This works, but very poorly.... */
634 newblock
= goal_eloc
.logicalBlockNum
;
635 goal_eloc
.logicalBlockNum
++;
636 goal_elen
-= sb
->s_blocksize
;
639 udf_write_aext(table
, &goal_epos
, &goal_eloc
, goal_elen
, 1);
641 udf_delete_aext(table
, goal_epos
);
642 brelse(goal_epos
.bh
);
644 udf_add_free_space(sb
, partition
, -1);
646 mutex_unlock(&sbi
->s_alloc_mutex
);
651 void udf_free_blocks(struct super_block
*sb
, struct inode
*inode
,
652 struct kernel_lb_addr
*bloc
, uint32_t offset
,
655 uint16_t partition
= bloc
->partitionReferenceNum
;
656 struct udf_part_map
*map
= &UDF_SB(sb
)->s_partmaps
[partition
];
658 if (map
->s_partition_flags
& UDF_PART_FLAG_UNALLOC_BITMAP
) {
659 udf_bitmap_free_blocks(sb
, map
->s_uspace
.s_bitmap
,
660 bloc
, offset
, count
);
661 } else if (map
->s_partition_flags
& UDF_PART_FLAG_UNALLOC_TABLE
) {
662 udf_table_free_blocks(sb
, map
->s_uspace
.s_table
,
663 bloc
, offset
, count
);
667 inode_sub_bytes(inode
,
668 ((sector_t
)count
) << sb
->s_blocksize_bits
);
672 inline int udf_prealloc_blocks(struct super_block
*sb
,
674 uint16_t partition
, uint32_t first_block
,
675 uint32_t block_count
)
677 struct udf_part_map
*map
= &UDF_SB(sb
)->s_partmaps
[partition
];
680 if (map
->s_partition_flags
& UDF_PART_FLAG_UNALLOC_BITMAP
)
681 allocated
= udf_bitmap_prealloc_blocks(sb
,
682 map
->s_uspace
.s_bitmap
,
683 partition
, first_block
,
685 else if (map
->s_partition_flags
& UDF_PART_FLAG_UNALLOC_TABLE
)
686 allocated
= udf_table_prealloc_blocks(sb
,
687 map
->s_uspace
.s_table
,
688 partition
, first_block
,
693 if (inode
&& allocated
> 0)
694 inode_add_bytes(inode
, allocated
<< sb
->s_blocksize_bits
);
698 inline udf_pblk_t
udf_new_block(struct super_block
*sb
,
700 uint16_t partition
, uint32_t goal
, int *err
)
702 struct udf_part_map
*map
= &UDF_SB(sb
)->s_partmaps
[partition
];
705 if (map
->s_partition_flags
& UDF_PART_FLAG_UNALLOC_BITMAP
)
706 block
= udf_bitmap_new_block(sb
,
707 map
->s_uspace
.s_bitmap
,
708 partition
, goal
, err
);
709 else if (map
->s_partition_flags
& UDF_PART_FLAG_UNALLOC_TABLE
)
710 block
= udf_table_new_block(sb
,
711 map
->s_uspace
.s_table
,
712 partition
, goal
, err
);
718 inode_add_bytes(inode
, sb
->s_blocksize
);