5 * Block allocation handling routines for the OSTA-UDF(tm) filesystem.
8 * E-mail regarding any portion of the Linux UDF file system should be
9 * directed to the development team mailing list (run by majordomo):
10 * linux_udf@hootie.lvld.hp.com
13 * This file is distributed under the terms of the GNU General Public
14 * License (GPL). Copies of the GPL can be obtained from:
15 * ftp://prep.ai.mit.edu/pub/gnu/GPL
16 * Each contributing author retains all rights to their own work.
18 * (C) 1999 Ben Fennema
19 * (C) 1999 Stelias Computing Inc
23 * 02/24/99 blf Created.
29 #include <linux/locks.h>
30 #include <linux/udf_fs.h>
32 #include <asm/bitops.h>
37 static int read_block_bitmap(struct super_block
* sb
, unsigned int block
,
38 unsigned long bitmap_nr
)
40 struct buffer_head
*bh
= NULL
;
44 loc
.logicalBlockNum
= UDF_SB_PARTMAPS(sb
)[UDF_SB_PARTITION(sb
)].s_uspace_bitmap
;
45 loc
.partitionReferenceNum
= UDF_SB_PARTITION(sb
);
47 bh
= udf_tread(sb
, udf_get_lb_pblock(sb
, loc
, block
), sb
->s_blocksize
);
52 UDF_SB_BLOCK_BITMAP_NUMBER(sb
, bitmap_nr
) = block
;
53 UDF_SB_BLOCK_BITMAP(sb
, bitmap_nr
) = bh
;
57 static int load__block_bitmap(struct super_block
* sb
, unsigned int block_group
)
60 unsigned long block_bitmap_number
;
61 struct buffer_head
* block_bitmap
= NULL
;
62 int nr_groups
= (UDF_SB_PARTLEN(sb
, UDF_SB_PARTITION(sb
)) +
63 (sizeof(struct SpaceBitmapDesc
) << 3) + (sb
->s_blocksize
* 8) - 1) / (sb
->s_blocksize
* 8);
65 if (block_group
>= nr_groups
)
67 udf_debug("block_group (%d) > nr_groups (%d)\n", block_group
, nr_groups
);
70 if (nr_groups
<= UDF_MAX_BLOCK_LOADED
)
72 if (UDF_SB_BLOCK_BITMAP(sb
, block_group
))
74 if (UDF_SB_BLOCK_BITMAP_NUMBER(sb
, block_group
) == block_group
)
77 retval
= read_block_bitmap(sb
, block_group
, block_group
);
83 for (i
=0; i
<UDF_SB_LOADED_BLOCK_BITMAPS(sb
) &&
84 UDF_SB_BLOCK_BITMAP_NUMBER(sb
, i
) != block_group
; i
++)
88 if (i
< UDF_SB_LOADED_BLOCK_BITMAPS(sb
) &&
89 UDF_SB_BLOCK_BITMAP_NUMBER(sb
, i
) == block_group
)
91 block_bitmap_number
= UDF_SB_BLOCK_BITMAP_NUMBER(sb
, i
);
92 block_bitmap
= UDF_SB_BLOCK_BITMAP(sb
, i
);
95 UDF_SB_BLOCK_BITMAP_NUMBER(sb
, j
) = UDF_SB_BLOCK_BITMAP_NUMBER(sb
, j
-1);
96 UDF_SB_BLOCK_BITMAP(sb
, j
) = UDF_SB_BLOCK_BITMAP(sb
, j
-1);
98 UDF_SB_BLOCK_BITMAP_NUMBER(sb
, 0) = block_bitmap_number
;
99 UDF_SB_BLOCK_BITMAP(sb
, 0) = block_bitmap
;
102 retval
= read_block_bitmap(sb
, block_group
, 0);
106 if (UDF_SB_LOADED_BLOCK_BITMAPS(sb
) < UDF_MAX_BLOCK_LOADED
)
107 UDF_SB_LOADED_BLOCK_BITMAPS(sb
) ++;
109 brelse(UDF_SB_BLOCK_BITMAP(sb
, UDF_MAX_BLOCK_LOADED
-1));
110 for (j
=UDF_SB_LOADED_BLOCK_BITMAPS(sb
)-1; j
>0; j
--)
112 UDF_SB_BLOCK_BITMAP_NUMBER(sb
, j
) = UDF_SB_BLOCK_BITMAP_NUMBER(sb
, j
-1);
113 UDF_SB_BLOCK_BITMAP(sb
, j
) = UDF_SB_BLOCK_BITMAP(sb
, j
-1);
115 retval
= read_block_bitmap(sb
, block_group
, 0);
120 static inline int load_block_bitmap(struct super_block
*sb
,
121 unsigned int block_group
)
124 int nr_groups
= (UDF_SB_PARTLEN(sb
, UDF_SB_PARTITION(sb
)) +
125 (sizeof(struct SpaceBitmapDesc
) << 3) + (sb
->s_blocksize
* 8) - 1) / (sb
->s_blocksize
* 8);
127 if (UDF_SB_LOADED_BLOCK_BITMAPS(sb
) > 0 &&
128 UDF_SB_BLOCK_BITMAP_NUMBER(sb
, 0) == block_group
&&
129 UDF_SB_BLOCK_BITMAP(sb
, block_group
))
133 else if (nr_groups
<= UDF_MAX_BLOCK_LOADED
&&
134 UDF_SB_BLOCK_BITMAP_NUMBER(sb
, block_group
) == block_group
&&
135 UDF_SB_BLOCK_BITMAP(sb
, block_group
))
141 slot
= load__block_bitmap(sb
, block_group
);
147 if (!UDF_SB_BLOCK_BITMAP(sb
, slot
))
153 void udf_free_blocks(const struct inode
* inode
, lb_addr bloc
, Uint32 offset
,
156 struct buffer_head
* bh
= NULL
;
158 unsigned long block_group
;
162 unsigned long overflow
;
163 struct super_block
* sb
;
168 udf_debug("nonexistent device");
172 if (UDF_SB_PARTMAPS(sb
)[bloc
.partitionReferenceNum
].s_uspace_bitmap
== 0xFFFFFFFF)
176 if (bloc
.logicalBlockNum
< 0 ||
177 (bloc
.logicalBlockNum
+ count
) > UDF_SB_PARTLEN(sb
, bloc
.partitionReferenceNum
))
179 udf_debug("%d < %d || %d + %d > %d\n",
180 bloc
.logicalBlockNum
, 0, bloc
.logicalBlockNum
, count
,
181 UDF_SB_PARTLEN(sb
, bloc
.partitionReferenceNum
));
185 block
= bloc
.logicalBlockNum
+ offset
+ (sizeof(struct SpaceBitmapDesc
) << 3);
189 block_group
= block
>> (sb
->s_blocksize_bits
+ 3);
190 bit
= block
% (sb
->s_blocksize
<< 3);
193 * Check to see if we are freeing blocks across a group boundary.
195 if (bit
+ count
> (sb
->s_blocksize
<< 3))
197 overflow
= bit
+ count
- (sb
->s_blocksize
<< 3);
200 bitmap_nr
= load_block_bitmap(sb
, block_group
);
204 bh
= UDF_SB_BLOCK_BITMAP(sb
, bitmap_nr
);
205 for (i
=0; i
< count
; i
++)
207 if (udf_set_bit(bit
+ i
, bh
->b_data
))
209 udf_debug("bit %ld already set\n", bit
+ i
);
210 udf_debug("byte=%2x\n", ((char *)bh
->b_data
)[(bit
+ i
) >> 3]);
212 else if (UDF_SB_LVIDBH(sb
))
214 UDF_SB_LVID(sb
)->freeSpaceTable
[UDF_SB_PARTITION(sb
)] =
215 cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb
)->freeSpaceTable
[UDF_SB_PARTITION(sb
)])+1);
218 mark_buffer_dirty(bh
, 1);
227 if (UDF_SB_LVIDBH(sb
))
228 mark_buffer_dirty(UDF_SB_LVIDBH(sb
), 1);
233 int udf_alloc_blocks(const struct inode
* inode
, Uint16 partition
,
234 Uint32 first_block
, Uint32 block_count
)
237 int bit
, block
, block_group
, group_start
;
238 int nr_groups
, bitmap_nr
;
239 struct buffer_head
*bh
;
240 struct super_block
*sb
;
245 udf_debug("nonexistent device\n");
250 if (first_block
< 0 || first_block
>= UDF_SB_PARTLEN(sb
, partition
))
254 nr_groups
= (UDF_SB_PARTLEN(sb
, partition
) +
255 (sizeof(struct SpaceBitmapDesc
) << 3) + (sb
->s_blocksize
* 8) - 1) / (sb
->s_blocksize
* 8);
256 block
= first_block
+ (sizeof(struct SpaceBitmapDesc
) << 3);
257 block_group
= block
>> (sb
->s_blocksize_bits
+ 3);
258 group_start
= block_group
? 0 : sizeof(struct SpaceBitmapDesc
);
260 bitmap_nr
= load_block_bitmap(sb
, block_group
);
263 bh
= UDF_SB_BLOCK_BITMAP(sb
, bitmap_nr
);
265 bit
= block
% (sb
->s_blocksize
<< 3);
267 while (bit
< (sb
->s_blocksize
<< 3) && block_count
> 0)
269 if (!udf_test_bit(bit
, bh
->b_data
))
271 if (!udf_clear_bit(bit
, bh
->b_data
))
273 udf_debug("bit already cleared for block %d\n", bit
);
282 mark_buffer_dirty(bh
, 1);
286 if (UDF_SB_LVIDBH(sb
))
288 UDF_SB_LVID(sb
)->freeSpaceTable
[partition
] =
289 cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb
)->freeSpaceTable
[partition
])-alloc_count
);
290 mark_buffer_dirty(UDF_SB_LVIDBH(sb
), 1);
297 int udf_new_block(const struct inode
* inode
, Uint16 partition
, Uint32 goal
, int *err
)
299 int tmp
, newbit
, bit
=0, block
, block_group
, group_start
;
300 int end_goal
, nr_groups
, bitmap_nr
, i
;
301 struct buffer_head
*bh
= NULL
;
302 struct super_block
*sb
;
310 udf_debug("nonexistent device\n");
316 if (goal
< 0 || goal
>= UDF_SB_PARTLEN(sb
, partition
))
319 nr_groups
= (UDF_SB_PARTLEN(sb
, partition
) +
320 (sizeof(struct SpaceBitmapDesc
) << 3) + (sb
->s_blocksize
* 8) - 1) / (sb
->s_blocksize
* 8);
321 block
= goal
+ (sizeof(struct SpaceBitmapDesc
) << 3);
322 block_group
= block
>> (sb
->s_blocksize_bits
+ 3);
323 group_start
= block_group
? 0 : sizeof(struct SpaceBitmapDesc
);
325 bitmap_nr
= load_block_bitmap(sb
, block_group
);
328 bh
= UDF_SB_BLOCK_BITMAP(sb
, bitmap_nr
);
329 ptr
= memscan((char *)bh
->b_data
+ group_start
, 0xFF, sb
->s_blocksize
- group_start
);
331 if ((ptr
- ((char *)bh
->b_data
)) < sb
->s_blocksize
)
333 bit
= block
% (sb
->s_blocksize
<< 3);
335 if (udf_test_bit(bit
, bh
->b_data
))
339 end_goal
= (bit
+ 63) & ~63;
340 bit
= udf_find_next_one_bit(bh
->b_data
, end_goal
, bit
);
343 ptr
= memscan((char *)bh
->b_data
+ (bit
>> 3), 0xFF, sb
->s_blocksize
- ((bit
+ 7) >> 3));
344 newbit
= (ptr
- ((char *)bh
->b_data
)) << 3;
345 if (newbit
< sb
->s_blocksize
<< 3)
350 newbit
= udf_find_next_one_bit(bh
->b_data
, sb
->s_blocksize
<< 3, bit
);
351 if (newbit
< sb
->s_blocksize
<< 3)
358 for (i
=0; i
<(nr_groups
*2); i
++)
361 if (block_group
>= nr_groups
)
363 group_start
= block_group
? 0 : sizeof(struct SpaceBitmapDesc
);
365 bitmap_nr
= load_block_bitmap(sb
, block_group
);
368 bh
= UDF_SB_BLOCK_BITMAP(sb
, bitmap_nr
);
371 ptr
= memscan((char *)bh
->b_data
+ group_start
, 0xFF, sb
->s_blocksize
- group_start
);
372 if ((ptr
- ((char *)bh
->b_data
)) < sb
->s_blocksize
)
374 bit
= (ptr
- ((char *)bh
->b_data
)) << 3;
380 bit
= udf_find_next_one_bit((char *)bh
->b_data
, sb
->s_blocksize
<< 3, group_start
<< 3);
381 if (bit
< sb
->s_blocksize
<< 3)
385 if (i
>= (nr_groups
*2))
390 if (bit
< sb
->s_blocksize
<< 3)
393 bit
= udf_find_next_one_bit(bh
->b_data
, sb
->s_blocksize
<< 3, group_start
<< 3);
394 if (bit
>= sb
->s_blocksize
<< 3)
401 for (i
=0; i
<7 && bit
> (group_start
<< 3) && udf_test_bit(bit
- 1, bh
->b_data
); i
++, bit
--);
404 newblock
= bit
+ (block_group
<< (sb
->s_blocksize_bits
+ 3)) -
405 (sizeof(struct SpaceBitmapDesc
) << 3);
407 tmp
= udf_get_pblock(sb
, newblock
, partition
, 0);
408 if (!udf_clear_bit(bit
, bh
->b_data
))
410 udf_debug("bit already cleared for block %d\n", bit
);
414 mark_buffer_dirty(bh
, 1);
416 if (UDF_SB_LVIDBH(sb
))
418 UDF_SB_LVID(sb
)->freeSpaceTable
[partition
] =
419 cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb
)->freeSpaceTable
[partition
])-1);
420 mark_buffer_dirty(UDF_SB_LVIDBH(sb
), 1);