]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * balloc.c | |
3 | * | |
4 | * PURPOSE | |
5 | * Block allocation handling routines for the OSTA-UDF(tm) filesystem. | |
6 | * | |
1da177e4 LT |
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 | ||
4b11111a MS |
31 | #define udf_clear_bit(nr, addr) ext2_clear_bit(nr, addr) |
32 | #define udf_set_bit(nr, addr) ext2_set_bit(nr, addr) | |
1da177e4 LT |
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) | |
4b11111a MS |
35 | #define udf_find_next_one_bit(addr, size, offset) \ |
36 | find_next_one_bit(addr, size, offset) | |
1da177e4 LT |
37 | |
38 | #define leBPL_to_cpup(x) leNUM_to_cpup(BITS_PER_LONG, x) | |
4b11111a MS |
39 | #define leNUM_to_cpup(x, y) xleNUM_to_cpup(x, y) |
40 | #define xleNUM_to_cpup(x, y) (le ## x ## _to_cpup(y)) | |
1da177e4 LT |
41 | #define uintBPL_t uint(BITS_PER_LONG) |
42 | #define uint(x) xuint(x) | |
43 | #define xuint(x) __le ## x | |
44 | ||
cb00ea35 | 45 | static inline int find_next_one_bit(void *addr, int size, int offset) |
1da177e4 | 46 | { |
cb00ea35 CG |
47 | uintBPL_t *p = ((uintBPL_t *) addr) + (offset / BITS_PER_LONG); |
48 | int result = offset & ~(BITS_PER_LONG - 1); | |
1da177e4 LT |
49 | unsigned long tmp; |
50 | ||
51 | if (offset >= size) | |
52 | return size; | |
53 | size -= result; | |
cb00ea35 CG |
54 | offset &= (BITS_PER_LONG - 1); |
55 | if (offset) { | |
1da177e4 LT |
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 | } | |
cb00ea35 | 65 | while (size & ~(BITS_PER_LONG - 1)) { |
4b11111a MS |
66 | tmp = leBPL_to_cpup(p++); |
67 | if (tmp) | |
1da177e4 LT |
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); | |
28de7948 | 75 | found_first: |
cb00ea35 | 76 | tmp &= ~0UL >> (BITS_PER_LONG - size); |
28de7948 | 77 | found_middle: |
1da177e4 LT |
78 | return result + ffz(~tmp); |
79 | } | |
80 | ||
81 | #define find_first_one_bit(addr, size)\ | |
82 | find_next_one_bit((addr), (size), 0) | |
83 | ||
cb00ea35 CG |
84 | static int read_block_bitmap(struct super_block *sb, |
85 | struct udf_bitmap *bitmap, unsigned int block, | |
86 | unsigned long bitmap_nr) | |
1da177e4 LT |
87 | { |
88 | struct buffer_head *bh = NULL; | |
89 | int retval = 0; | |
5ca4e4be | 90 | struct kernel_lb_addr loc; |
1da177e4 LT |
91 | |
92 | loc.logicalBlockNum = bitmap->s_extPosition; | |
6c79e987 | 93 | loc.partitionReferenceNum = UDF_SB(sb)->s_partition; |
1da177e4 | 94 | |
97e961fd | 95 | bh = udf_tread(sb, udf_get_lb_pblock(sb, &loc, block)); |
4b11111a | 96 | if (!bh) |
1da177e4 | 97 | retval = -EIO; |
4b11111a | 98 | |
1da177e4 LT |
99 | bitmap->s_block_bitmap[bitmap_nr] = bh; |
100 | return retval; | |
101 | } | |
102 | ||
cb00ea35 CG |
103 | static int __load_block_bitmap(struct super_block *sb, |
104 | struct udf_bitmap *bitmap, | |
105 | unsigned int block_group) | |
1da177e4 LT |
106 | { |
107 | int retval = 0; | |
108 | int nr_groups = bitmap->s_nr_groups; | |
109 | ||
cb00ea35 CG |
110 | if (block_group >= nr_groups) { |
111 | udf_debug("block_group (%d) > nr_groups (%d)\n", block_group, | |
112 | nr_groups); | |
1da177e4 LT |
113 | } |
114 | ||
28de7948 | 115 | if (bitmap->s_block_bitmap[block_group]) { |
1da177e4 | 116 | return block_group; |
28de7948 CG |
117 | } else { |
118 | retval = read_block_bitmap(sb, bitmap, block_group, | |
119 | block_group); | |
1da177e4 LT |
120 | if (retval < 0) |
121 | return retval; | |
122 | return block_group; | |
123 | } | |
124 | } | |
125 | ||
cb00ea35 CG |
126 | static inline int load_block_bitmap(struct super_block *sb, |
127 | struct udf_bitmap *bitmap, | |
128 | unsigned int block_group) | |
1da177e4 LT |
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 | ||
146bca72 | 143 | static void udf_add_free_space(struct super_block *sb, u16 partition, u32 cnt) |
742ba02a | 144 | { |
146bca72 | 145 | struct udf_sb_info *sbi = UDF_SB(sb); |
742ba02a MS |
146 | struct logicalVolIntegrityDesc *lvid; |
147 | ||
146bca72 JK |
148 | if (!sbi->s_lvid_bh) |
149 | return; | |
742ba02a MS |
150 | |
151 | lvid = (struct logicalVolIntegrityDesc *)sbi->s_lvid_bh->b_data; | |
c2104fda | 152 | le32_add_cpu(&lvid->freeSpaceTable[partition], cnt); |
146bca72 | 153 | udf_updated_lvid(sb); |
742ba02a MS |
154 | } |
155 | ||
cb00ea35 CG |
156 | static void udf_bitmap_free_blocks(struct super_block *sb, |
157 | struct inode *inode, | |
158 | struct udf_bitmap *bitmap, | |
97e961fd PE |
159 | struct kernel_lb_addr *bloc, |
160 | uint32_t offset, | |
cb00ea35 | 161 | uint32_t count) |
1da177e4 LT |
162 | { |
163 | struct udf_sb_info *sbi = UDF_SB(sb); | |
cb00ea35 | 164 | struct buffer_head *bh = NULL; |
97e961fd | 165 | struct udf_part_map *partmap; |
1da177e4 LT |
166 | unsigned long block; |
167 | unsigned long block_group; | |
168 | unsigned long bit; | |
169 | unsigned long i; | |
170 | int bitmap_nr; | |
171 | unsigned long overflow; | |
172 | ||
1e7933de | 173 | mutex_lock(&sbi->s_alloc_mutex); |
97e961fd PE |
174 | partmap = &sbi->s_partmaps[bloc->partitionReferenceNum]; |
175 | if (bloc->logicalBlockNum < 0 || | |
176 | (bloc->logicalBlockNum + count) > | |
177 | partmap->s_partition_len) { | |
28de7948 | 178 | udf_debug("%d < %d || %d + %d > %d\n", |
97e961fd PE |
179 | bloc->logicalBlockNum, 0, bloc->logicalBlockNum, |
180 | count, partmap->s_partition_len); | |
1da177e4 LT |
181 | goto error_return; |
182 | } | |
183 | ||
97e961fd | 184 | block = bloc->logicalBlockNum + offset + |
4b11111a | 185 | (sizeof(struct spaceBitmapDesc) << 3); |
1da177e4 | 186 | |
4daa1b87 MS |
187 | do { |
188 | overflow = 0; | |
189 | block_group = block >> (sb->s_blocksize_bits + 3); | |
190 | bit = block % (sb->s_blocksize << 3); | |
191 | ||
192 | /* | |
193 | * Check to see if we are freeing blocks across a group boundary. | |
194 | */ | |
195 | if (bit + count > (sb->s_blocksize << 3)) { | |
196 | overflow = bit + count - (sb->s_blocksize << 3); | |
197 | count -= overflow; | |
1da177e4 | 198 | } |
4daa1b87 MS |
199 | bitmap_nr = load_block_bitmap(sb, bitmap, block_group); |
200 | if (bitmap_nr < 0) | |
201 | goto error_return; | |
202 | ||
203 | bh = bitmap->s_block_bitmap[bitmap_nr]; | |
204 | for (i = 0; i < count; i++) { | |
205 | if (udf_set_bit(bit + i, bh->b_data)) { | |
206 | udf_debug("bit %ld already set\n", bit + i); | |
207 | udf_debug("byte=%2x\n", | |
208 | ((char *)bh->b_data)[(bit + i) >> 3]); | |
209 | } else { | |
210 | if (inode) | |
bacfb7c2 | 211 | vfs_dq_free_block(inode, 1); |
146bca72 | 212 | udf_add_free_space(sb, sbi->s_partition, 1); |
4daa1b87 MS |
213 | } |
214 | } | |
215 | mark_buffer_dirty(bh); | |
216 | if (overflow) { | |
217 | block += count; | |
218 | count = overflow; | |
219 | } | |
220 | } while (overflow); | |
221 | ||
28de7948 | 222 | error_return: |
1e7933de | 223 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
224 | } |
225 | ||
cb00ea35 CG |
226 | static int udf_bitmap_prealloc_blocks(struct super_block *sb, |
227 | struct inode *inode, | |
228 | struct udf_bitmap *bitmap, | |
229 | uint16_t partition, uint32_t first_block, | |
230 | uint32_t block_count) | |
1da177e4 LT |
231 | { |
232 | struct udf_sb_info *sbi = UDF_SB(sb); | |
233 | int alloc_count = 0; | |
234 | int bit, block, block_group, group_start; | |
235 | int nr_groups, bitmap_nr; | |
236 | struct buffer_head *bh; | |
6c79e987 | 237 | __u32 part_len; |
1da177e4 | 238 | |
1e7933de | 239 | mutex_lock(&sbi->s_alloc_mutex); |
6c79e987 MS |
240 | part_len = sbi->s_partmaps[partition].s_partition_len; |
241 | if (first_block < 0 || first_block >= part_len) | |
1da177e4 LT |
242 | goto out; |
243 | ||
6c79e987 MS |
244 | if (first_block + block_count > part_len) |
245 | block_count = part_len - first_block; | |
1da177e4 | 246 | |
4daa1b87 MS |
247 | do { |
248 | nr_groups = udf_compute_nr_groups(sb, partition); | |
249 | block = first_block + (sizeof(struct spaceBitmapDesc) << 3); | |
250 | block_group = block >> (sb->s_blocksize_bits + 3); | |
251 | group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); | |
1da177e4 | 252 | |
4daa1b87 MS |
253 | bitmap_nr = load_block_bitmap(sb, bitmap, block_group); |
254 | if (bitmap_nr < 0) | |
255 | goto out; | |
256 | bh = bitmap->s_block_bitmap[bitmap_nr]; | |
1da177e4 | 257 | |
4daa1b87 | 258 | bit = block % (sb->s_blocksize << 3); |
1da177e4 | 259 | |
4daa1b87 MS |
260 | while (bit < (sb->s_blocksize << 3) && block_count > 0) { |
261 | if (!udf_test_bit(bit, bh->b_data)) | |
262 | goto out; | |
bacfb7c2 | 263 | else if (vfs_dq_prealloc_block(inode, 1)) |
4daa1b87 MS |
264 | goto out; |
265 | else if (!udf_clear_bit(bit, bh->b_data)) { | |
266 | udf_debug("bit already cleared for block %d\n", bit); | |
bacfb7c2 | 267 | vfs_dq_free_block(inode, 1); |
4daa1b87 MS |
268 | goto out; |
269 | } | |
270 | block_count--; | |
271 | alloc_count++; | |
272 | bit++; | |
273 | block++; | |
1da177e4 | 274 | } |
4daa1b87 MS |
275 | mark_buffer_dirty(bh); |
276 | } while (block_count > 0); | |
277 | ||
28de7948 | 278 | out: |
146bca72 | 279 | udf_add_free_space(sb, partition, -alloc_count); |
1e7933de | 280 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
281 | return alloc_count; |
282 | } | |
283 | ||
cb00ea35 CG |
284 | static int udf_bitmap_new_block(struct super_block *sb, |
285 | struct inode *inode, | |
286 | struct udf_bitmap *bitmap, uint16_t partition, | |
287 | uint32_t goal, int *err) | |
1da177e4 LT |
288 | { |
289 | struct udf_sb_info *sbi = UDF_SB(sb); | |
cb00ea35 | 290 | int newbit, bit = 0, block, block_group, group_start; |
1da177e4 LT |
291 | int end_goal, nr_groups, bitmap_nr, i; |
292 | struct buffer_head *bh = NULL; | |
293 | char *ptr; | |
294 | int newblock = 0; | |
295 | ||
296 | *err = -ENOSPC; | |
1e7933de | 297 | mutex_lock(&sbi->s_alloc_mutex); |
1da177e4 | 298 | |
28de7948 | 299 | repeat: |
6c79e987 | 300 | if (goal < 0 || goal >= sbi->s_partmaps[partition].s_partition_len) |
1da177e4 LT |
301 | goal = 0; |
302 | ||
303 | nr_groups = bitmap->s_nr_groups; | |
304 | block = goal + (sizeof(struct spaceBitmapDesc) << 3); | |
305 | block_group = block >> (sb->s_blocksize_bits + 3); | |
306 | group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); | |
307 | ||
308 | bitmap_nr = load_block_bitmap(sb, bitmap, block_group); | |
309 | if (bitmap_nr < 0) | |
310 | goto error_return; | |
311 | bh = bitmap->s_block_bitmap[bitmap_nr]; | |
28de7948 CG |
312 | ptr = memscan((char *)bh->b_data + group_start, 0xFF, |
313 | sb->s_blocksize - group_start); | |
1da177e4 | 314 | |
cb00ea35 | 315 | if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) { |
1da177e4 | 316 | bit = block % (sb->s_blocksize << 3); |
28de7948 | 317 | if (udf_test_bit(bit, bh->b_data)) |
1da177e4 | 318 | goto got_block; |
28de7948 | 319 | |
1da177e4 LT |
320 | end_goal = (bit + 63) & ~63; |
321 | bit = udf_find_next_one_bit(bh->b_data, end_goal, bit); | |
322 | if (bit < end_goal) | |
323 | goto got_block; | |
28de7948 | 324 | |
4b11111a MS |
325 | ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF, |
326 | sb->s_blocksize - ((bit + 7) >> 3)); | |
1da177e4 | 327 | newbit = (ptr - ((char *)bh->b_data)) << 3; |
cb00ea35 | 328 | if (newbit < sb->s_blocksize << 3) { |
1da177e4 LT |
329 | bit = newbit; |
330 | goto search_back; | |
331 | } | |
28de7948 | 332 | |
4b11111a MS |
333 | newbit = udf_find_next_one_bit(bh->b_data, |
334 | sb->s_blocksize << 3, bit); | |
cb00ea35 | 335 | if (newbit < sb->s_blocksize << 3) { |
1da177e4 LT |
336 | bit = newbit; |
337 | goto got_block; | |
338 | } | |
339 | } | |
340 | ||
cb00ea35 CG |
341 | for (i = 0; i < (nr_groups * 2); i++) { |
342 | block_group++; | |
1da177e4 LT |
343 | if (block_group >= nr_groups) |
344 | block_group = 0; | |
345 | group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc); | |
346 | ||
347 | bitmap_nr = load_block_bitmap(sb, bitmap, block_group); | |
348 | if (bitmap_nr < 0) | |
349 | goto error_return; | |
350 | bh = bitmap->s_block_bitmap[bitmap_nr]; | |
cb00ea35 | 351 | if (i < nr_groups) { |
28de7948 CG |
352 | ptr = memscan((char *)bh->b_data + group_start, 0xFF, |
353 | sb->s_blocksize - group_start); | |
cb00ea35 | 354 | if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) { |
1da177e4 LT |
355 | bit = (ptr - ((char *)bh->b_data)) << 3; |
356 | break; | |
357 | } | |
cb00ea35 | 358 | } else { |
28de7948 CG |
359 | bit = udf_find_next_one_bit((char *)bh->b_data, |
360 | sb->s_blocksize << 3, | |
361 | group_start << 3); | |
1da177e4 LT |
362 | if (bit < sb->s_blocksize << 3) |
363 | break; | |
364 | } | |
365 | } | |
cb00ea35 | 366 | if (i >= (nr_groups * 2)) { |
1e7933de | 367 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
368 | return newblock; |
369 | } | |
370 | if (bit < sb->s_blocksize << 3) | |
371 | goto search_back; | |
372 | else | |
4b11111a MS |
373 | bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, |
374 | group_start << 3); | |
cb00ea35 | 375 | if (bit >= sb->s_blocksize << 3) { |
1e7933de | 376 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
377 | return 0; |
378 | } | |
379 | ||
28de7948 | 380 | search_back: |
4b11111a MS |
381 | i = 0; |
382 | while (i < 7 && bit > (group_start << 3) && | |
383 | udf_test_bit(bit - 1, bh->b_data)) { | |
384 | ++i; | |
385 | --bit; | |
386 | } | |
1da177e4 | 387 | |
28de7948 | 388 | got_block: |
1da177e4 LT |
389 | |
390 | /* | |
391 | * Check quota for allocation of this block. | |
392 | */ | |
bacfb7c2 | 393 | if (inode && vfs_dq_alloc_block(inode, 1)) { |
1e7933de | 394 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
395 | *err = -EDQUOT; |
396 | return 0; | |
397 | } | |
398 | ||
399 | newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) - | |
28de7948 | 400 | (sizeof(struct spaceBitmapDesc) << 3); |
1da177e4 | 401 | |
cb00ea35 | 402 | if (!udf_clear_bit(bit, bh->b_data)) { |
1da177e4 LT |
403 | udf_debug("bit already cleared for block %d\n", bit); |
404 | goto repeat; | |
405 | } | |
406 | ||
407 | mark_buffer_dirty(bh); | |
408 | ||
146bca72 | 409 | udf_add_free_space(sb, partition, -1); |
1e7933de | 410 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
411 | *err = 0; |
412 | return newblock; | |
413 | ||
28de7948 | 414 | error_return: |
1da177e4 | 415 | *err = -EIO; |
1e7933de | 416 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
417 | return 0; |
418 | } | |
419 | ||
cb00ea35 CG |
420 | static void udf_table_free_blocks(struct super_block *sb, |
421 | struct inode *inode, | |
422 | struct inode *table, | |
97e961fd PE |
423 | struct kernel_lb_addr *bloc, |
424 | uint32_t offset, | |
cb00ea35 | 425 | uint32_t count) |
1da177e4 LT |
426 | { |
427 | struct udf_sb_info *sbi = UDF_SB(sb); | |
97e961fd | 428 | struct udf_part_map *partmap; |
1da177e4 | 429 | uint32_t start, end; |
ff116fc8 | 430 | uint32_t elen; |
5ca4e4be | 431 | struct kernel_lb_addr eloc; |
ff116fc8 | 432 | struct extent_position oepos, epos; |
1da177e4 LT |
433 | int8_t etype; |
434 | int i; | |
48d6d8ff | 435 | struct udf_inode_info *iinfo; |
1da177e4 | 436 | |
1e7933de | 437 | mutex_lock(&sbi->s_alloc_mutex); |
97e961fd PE |
438 | partmap = &sbi->s_partmaps[bloc->partitionReferenceNum]; |
439 | if (bloc->logicalBlockNum < 0 || | |
440 | (bloc->logicalBlockNum + count) > | |
441 | partmap->s_partition_len) { | |
28de7948 CG |
442 | udf_debug("%d < %d || %d + %d > %d\n", |
443 | bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count, | |
97e961fd | 444 | partmap->s_partition_len); |
1da177e4 LT |
445 | goto error_return; |
446 | } | |
447 | ||
48d6d8ff | 448 | iinfo = UDF_I(table); |
4b11111a MS |
449 | /* We do this up front - There are some error conditions that |
450 | could occure, but.. oh well */ | |
1da177e4 | 451 | if (inode) |
bacfb7c2 | 452 | vfs_dq_free_block(inode, count); |
146bca72 | 453 | udf_add_free_space(sb, sbi->s_partition, count); |
1da177e4 | 454 | |
97e961fd PE |
455 | start = bloc->logicalBlockNum + offset; |
456 | end = bloc->logicalBlockNum + offset + count - 1; | |
1da177e4 | 457 | |
ff116fc8 | 458 | epos.offset = oepos.offset = sizeof(struct unallocSpaceEntry); |
1da177e4 | 459 | elen = 0; |
48d6d8ff | 460 | epos.block = oepos.block = iinfo->i_location; |
ff116fc8 | 461 | epos.bh = oepos.bh = NULL; |
1da177e4 | 462 | |
28de7948 CG |
463 | while (count && |
464 | (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { | |
4b11111a MS |
465 | if (((eloc.logicalBlockNum + |
466 | (elen >> sb->s_blocksize_bits)) == start)) { | |
467 | if ((0x3FFFFFFF - elen) < | |
468 | (count << sb->s_blocksize_bits)) { | |
469 | uint32_t tmp = ((0x3FFFFFFF - elen) >> | |
470 | sb->s_blocksize_bits); | |
471 | count -= tmp; | |
472 | start += tmp; | |
473 | elen = (etype << 30) | | |
474 | (0x40000000 - sb->s_blocksize); | |
cb00ea35 | 475 | } else { |
4b11111a MS |
476 | elen = (etype << 30) | |
477 | (elen + | |
478 | (count << sb->s_blocksize_bits)); | |
1da177e4 LT |
479 | start += count; |
480 | count = 0; | |
481 | } | |
97e961fd | 482 | udf_write_aext(table, &oepos, &eloc, elen, 1); |
cb00ea35 | 483 | } else if (eloc.logicalBlockNum == (end + 1)) { |
4b11111a MS |
484 | if ((0x3FFFFFFF - elen) < |
485 | (count << sb->s_blocksize_bits)) { | |
486 | uint32_t tmp = ((0x3FFFFFFF - elen) >> | |
487 | sb->s_blocksize_bits); | |
488 | count -= tmp; | |
489 | end -= tmp; | |
490 | eloc.logicalBlockNum -= tmp; | |
491 | elen = (etype << 30) | | |
492 | (0x40000000 - sb->s_blocksize); | |
cb00ea35 | 493 | } else { |
1da177e4 | 494 | eloc.logicalBlockNum = start; |
4b11111a MS |
495 | elen = (etype << 30) | |
496 | (elen + | |
497 | (count << sb->s_blocksize_bits)); | |
1da177e4 LT |
498 | end -= count; |
499 | count = 0; | |
500 | } | |
97e961fd | 501 | udf_write_aext(table, &oepos, &eloc, elen, 1); |
1da177e4 LT |
502 | } |
503 | ||
cb00ea35 | 504 | if (epos.bh != oepos.bh) { |
1da177e4 | 505 | i = -1; |
ff116fc8 | 506 | oepos.block = epos.block; |
3bf25cb4 JK |
507 | brelse(oepos.bh); |
508 | get_bh(epos.bh); | |
ff116fc8 JK |
509 | oepos.bh = epos.bh; |
510 | oepos.offset = 0; | |
28de7948 | 511 | } else { |
ff116fc8 | 512 | oepos.offset = epos.offset; |
28de7948 | 513 | } |
1da177e4 LT |
514 | } |
515 | ||
cb00ea35 | 516 | if (count) { |
28de7948 | 517 | /* |
4b11111a MS |
518 | * NOTE: we CANNOT use udf_add_aext here, as it can try to |
519 | * allocate a new block, and since we hold the super block | |
520 | * lock already very bad things would happen :) | |
28de7948 CG |
521 | * |
522 | * We copy the behavior of udf_add_aext, but instead of | |
523 | * trying to allocate a new block close to the existing one, | |
524 | * we just steal a block from the extent we are trying to add. | |
525 | * | |
526 | * It would be nice if the blocks were close together, but it | |
527 | * isn't required. | |
cb00ea35 | 528 | */ |
1da177e4 LT |
529 | |
530 | int adsize; | |
5ca4e4be PE |
531 | struct short_ad *sad = NULL; |
532 | struct long_ad *lad = NULL; | |
1da177e4 LT |
533 | struct allocExtDesc *aed; |
534 | ||
535 | eloc.logicalBlockNum = start; | |
28de7948 CG |
536 | elen = EXT_RECORDED_ALLOCATED | |
537 | (count << sb->s_blocksize_bits); | |
1da177e4 | 538 | |
48d6d8ff | 539 | if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) |
5ca4e4be | 540 | adsize = sizeof(struct short_ad); |
48d6d8ff | 541 | else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) |
5ca4e4be | 542 | adsize = sizeof(struct long_ad); |
48d6d8ff | 543 | else { |
3bf25cb4 JK |
544 | brelse(oepos.bh); |
545 | brelse(epos.bh); | |
1da177e4 LT |
546 | goto error_return; |
547 | } | |
548 | ||
cb00ea35 | 549 | if (epos.offset + (2 * adsize) > sb->s_blocksize) { |
1da177e4 LT |
550 | char *sptr, *dptr; |
551 | int loffset; | |
cb00ea35 | 552 | |
3bf25cb4 | 553 | brelse(oepos.bh); |
ff116fc8 | 554 | oepos = epos; |
1da177e4 LT |
555 | |
556 | /* Steal a block from the extent being free'd */ | |
ff116fc8 | 557 | epos.block.logicalBlockNum = eloc.logicalBlockNum; |
cb00ea35 | 558 | eloc.logicalBlockNum++; |
1da177e4 LT |
559 | elen -= sb->s_blocksize; |
560 | ||
4b11111a | 561 | epos.bh = udf_tread(sb, |
97e961fd | 562 | udf_get_lb_pblock(sb, &epos.block, 0)); |
4b11111a | 563 | if (!epos.bh) { |
3bf25cb4 | 564 | brelse(oepos.bh); |
1da177e4 LT |
565 | goto error_return; |
566 | } | |
ff116fc8 | 567 | aed = (struct allocExtDesc *)(epos.bh->b_data); |
4b11111a MS |
568 | aed->previousAllocExtLocation = |
569 | cpu_to_le32(oepos.block.logicalBlockNum); | |
cb00ea35 | 570 | if (epos.offset + adsize > sb->s_blocksize) { |
ff116fc8 | 571 | loffset = epos.offset; |
1da177e4 | 572 | aed->lengthAllocDescs = cpu_to_le32(adsize); |
48d6d8ff | 573 | sptr = iinfo->i_ext.i_data + epos.offset |
c0b34438 | 574 | - adsize; |
4b11111a MS |
575 | dptr = epos.bh->b_data + |
576 | sizeof(struct allocExtDesc); | |
1da177e4 | 577 | memcpy(dptr, sptr, adsize); |
4b11111a MS |
578 | epos.offset = sizeof(struct allocExtDesc) + |
579 | adsize; | |
cb00ea35 | 580 | } else { |
ff116fc8 | 581 | loffset = epos.offset + adsize; |
1da177e4 | 582 | aed->lengthAllocDescs = cpu_to_le32(0); |
cb00ea35 | 583 | if (oepos.bh) { |
f5cc15da | 584 | sptr = oepos.bh->b_data + epos.offset; |
4b11111a MS |
585 | aed = (struct allocExtDesc *) |
586 | oepos.bh->b_data; | |
c2104fda | 587 | le32_add_cpu(&aed->lengthAllocDescs, |
588 | adsize); | |
cb00ea35 | 589 | } else { |
48d6d8ff | 590 | sptr = iinfo->i_ext.i_data + |
c0b34438 | 591 | epos.offset; |
48d6d8ff | 592 | iinfo->i_lenAlloc += adsize; |
1da177e4 LT |
593 | mark_inode_dirty(table); |
594 | } | |
f5cc15da | 595 | epos.offset = sizeof(struct allocExtDesc); |
1da177e4 | 596 | } |
6c79e987 | 597 | if (sbi->s_udfrev >= 0x0200) |
4b11111a MS |
598 | udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, |
599 | 3, 1, epos.block.logicalBlockNum, | |
5ca4e4be | 600 | sizeof(struct tag)); |
1da177e4 | 601 | else |
4b11111a MS |
602 | udf_new_tag(epos.bh->b_data, TAG_IDENT_AED, |
603 | 2, 1, epos.block.logicalBlockNum, | |
5ca4e4be | 604 | sizeof(struct tag)); |
28de7948 | 605 | |
48d6d8ff | 606 | switch (iinfo->i_alloc_type) { |
4b11111a | 607 | case ICBTAG_FLAG_AD_SHORT: |
5ca4e4be | 608 | sad = (struct short_ad *)sptr; |
4b11111a MS |
609 | sad->extLength = cpu_to_le32( |
610 | EXT_NEXT_EXTENT_ALLOCDECS | | |
611 | sb->s_blocksize); | |
612 | sad->extPosition = | |
613 | cpu_to_le32(epos.block.logicalBlockNum); | |
614 | break; | |
615 | case ICBTAG_FLAG_AD_LONG: | |
5ca4e4be | 616 | lad = (struct long_ad *)sptr; |
4b11111a MS |
617 | lad->extLength = cpu_to_le32( |
618 | EXT_NEXT_EXTENT_ALLOCDECS | | |
619 | sb->s_blocksize); | |
620 | lad->extLocation = | |
621 | cpu_to_lelb(epos.block); | |
622 | break; | |
1da177e4 | 623 | } |
cb00ea35 | 624 | if (oepos.bh) { |
ff116fc8 JK |
625 | udf_update_tag(oepos.bh->b_data, loffset); |
626 | mark_buffer_dirty(oepos.bh); | |
28de7948 | 627 | } else { |
1da177e4 | 628 | mark_inode_dirty(table); |
28de7948 | 629 | } |
1da177e4 LT |
630 | } |
631 | ||
4b11111a MS |
632 | /* It's possible that stealing the block emptied the extent */ |
633 | if (elen) { | |
97e961fd | 634 | udf_write_aext(table, &epos, &eloc, elen, 1); |
1da177e4 | 635 | |
cb00ea35 | 636 | if (!epos.bh) { |
48d6d8ff | 637 | iinfo->i_lenAlloc += adsize; |
1da177e4 | 638 | mark_inode_dirty(table); |
cb00ea35 | 639 | } else { |
ff116fc8 | 640 | aed = (struct allocExtDesc *)epos.bh->b_data; |
c2104fda | 641 | le32_add_cpu(&aed->lengthAllocDescs, adsize); |
ff116fc8 JK |
642 | udf_update_tag(epos.bh->b_data, epos.offset); |
643 | mark_buffer_dirty(epos.bh); | |
1da177e4 LT |
644 | } |
645 | } | |
646 | } | |
647 | ||
3bf25cb4 JK |
648 | brelse(epos.bh); |
649 | brelse(oepos.bh); | |
1da177e4 | 650 | |
28de7948 | 651 | error_return: |
1e7933de | 652 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
653 | return; |
654 | } | |
655 | ||
cb00ea35 CG |
656 | static int udf_table_prealloc_blocks(struct super_block *sb, |
657 | struct inode *inode, | |
658 | struct inode *table, uint16_t partition, | |
659 | uint32_t first_block, uint32_t block_count) | |
1da177e4 LT |
660 | { |
661 | struct udf_sb_info *sbi = UDF_SB(sb); | |
662 | int alloc_count = 0; | |
ff116fc8 | 663 | uint32_t elen, adsize; |
5ca4e4be | 664 | struct kernel_lb_addr eloc; |
ff116fc8 | 665 | struct extent_position epos; |
1da177e4 | 666 | int8_t etype = -1; |
48d6d8ff | 667 | struct udf_inode_info *iinfo; |
1da177e4 | 668 | |
4b11111a MS |
669 | if (first_block < 0 || |
670 | first_block >= sbi->s_partmaps[partition].s_partition_len) | |
1da177e4 LT |
671 | return 0; |
672 | ||
48d6d8ff MS |
673 | iinfo = UDF_I(table); |
674 | if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) | |
5ca4e4be | 675 | adsize = sizeof(struct short_ad); |
48d6d8ff | 676 | else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) |
5ca4e4be | 677 | adsize = sizeof(struct long_ad); |
1da177e4 LT |
678 | else |
679 | return 0; | |
680 | ||
1e7933de | 681 | mutex_lock(&sbi->s_alloc_mutex); |
ff116fc8 | 682 | epos.offset = sizeof(struct unallocSpaceEntry); |
48d6d8ff | 683 | epos.block = iinfo->i_location; |
ff116fc8 | 684 | epos.bh = NULL; |
1da177e4 LT |
685 | eloc.logicalBlockNum = 0xFFFFFFFF; |
686 | ||
28de7948 CG |
687 | while (first_block != eloc.logicalBlockNum && |
688 | (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { | |
1da177e4 | 689 | udf_debug("eloc=%d, elen=%d, first_block=%d\n", |
cb00ea35 | 690 | eloc.logicalBlockNum, elen, first_block); |
28de7948 | 691 | ; /* empty loop body */ |
1da177e4 LT |
692 | } |
693 | ||
cb00ea35 | 694 | if (first_block == eloc.logicalBlockNum) { |
ff116fc8 | 695 | epos.offset -= adsize; |
1da177e4 LT |
696 | |
697 | alloc_count = (elen >> sb->s_blocksize_bits); | |
bacfb7c2 | 698 | if (inode && vfs_dq_prealloc_block(inode, |
4b11111a | 699 | alloc_count > block_count ? block_count : alloc_count)) |
1da177e4 | 700 | alloc_count = 0; |
4b11111a | 701 | else if (alloc_count > block_count) { |
1da177e4 LT |
702 | alloc_count = block_count; |
703 | eloc.logicalBlockNum += alloc_count; | |
704 | elen -= (alloc_count << sb->s_blocksize_bits); | |
97e961fd | 705 | udf_write_aext(table, &epos, &eloc, |
4b11111a MS |
706 | (etype << 30) | elen, 1); |
707 | } else | |
708 | udf_delete_aext(table, epos, eloc, | |
709 | (etype << 30) | elen); | |
28de7948 | 710 | } else { |
1da177e4 | 711 | alloc_count = 0; |
28de7948 | 712 | } |
1da177e4 | 713 | |
3bf25cb4 | 714 | brelse(epos.bh); |
1da177e4 | 715 | |
146bca72 JK |
716 | if (alloc_count) |
717 | udf_add_free_space(sb, partition, -alloc_count); | |
1e7933de | 718 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
719 | return alloc_count; |
720 | } | |
721 | ||
cb00ea35 CG |
722 | static int udf_table_new_block(struct super_block *sb, |
723 | struct inode *inode, | |
724 | struct inode *table, uint16_t partition, | |
725 | uint32_t goal, int *err) | |
1da177e4 LT |
726 | { |
727 | struct udf_sb_info *sbi = UDF_SB(sb); | |
728 | uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF; | |
729 | uint32_t newblock = 0, adsize; | |
ff116fc8 | 730 | uint32_t elen, goal_elen = 0; |
5ca4e4be | 731 | struct kernel_lb_addr eloc, uninitialized_var(goal_eloc); |
ff116fc8 | 732 | struct extent_position epos, goal_epos; |
1da177e4 | 733 | int8_t etype; |
48d6d8ff | 734 | struct udf_inode_info *iinfo = UDF_I(table); |
1da177e4 LT |
735 | |
736 | *err = -ENOSPC; | |
737 | ||
48d6d8ff | 738 | if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT) |
5ca4e4be | 739 | adsize = sizeof(struct short_ad); |
48d6d8ff | 740 | else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG) |
5ca4e4be | 741 | adsize = sizeof(struct long_ad); |
1da177e4 LT |
742 | else |
743 | return newblock; | |
744 | ||
1e7933de | 745 | mutex_lock(&sbi->s_alloc_mutex); |
6c79e987 | 746 | if (goal < 0 || goal >= sbi->s_partmaps[partition].s_partition_len) |
1da177e4 LT |
747 | goal = 0; |
748 | ||
4b11111a MS |
749 | /* We search for the closest matching block to goal. If we find |
750 | a exact hit, we stop. Otherwise we keep going till we run out | |
751 | of extents. We store the buffer_head, bloc, and extoffset | |
752 | of the current closest match and use that when we are done. | |
cb00ea35 | 753 | */ |
ff116fc8 | 754 | epos.offset = sizeof(struct unallocSpaceEntry); |
48d6d8ff | 755 | epos.block = iinfo->i_location; |
ff116fc8 | 756 | epos.bh = goal_epos.bh = NULL; |
1da177e4 | 757 | |
28de7948 CG |
758 | while (spread && |
759 | (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) { | |
cb00ea35 | 760 | if (goal >= eloc.logicalBlockNum) { |
4b11111a MS |
761 | if (goal < eloc.logicalBlockNum + |
762 | (elen >> sb->s_blocksize_bits)) | |
1da177e4 LT |
763 | nspread = 0; |
764 | else | |
765 | nspread = goal - eloc.logicalBlockNum - | |
28de7948 CG |
766 | (elen >> sb->s_blocksize_bits); |
767 | } else { | |
1da177e4 | 768 | nspread = eloc.logicalBlockNum - goal; |
28de7948 | 769 | } |
1da177e4 | 770 | |
cb00ea35 | 771 | if (nspread < spread) { |
1da177e4 | 772 | spread = nspread; |
cb00ea35 | 773 | if (goal_epos.bh != epos.bh) { |
3bf25cb4 | 774 | brelse(goal_epos.bh); |
ff116fc8 | 775 | goal_epos.bh = epos.bh; |
3bf25cb4 | 776 | get_bh(goal_epos.bh); |
1da177e4 | 777 | } |
ff116fc8 JK |
778 | goal_epos.block = epos.block; |
779 | goal_epos.offset = epos.offset - adsize; | |
1da177e4 LT |
780 | goal_eloc = eloc; |
781 | goal_elen = (etype << 30) | elen; | |
782 | } | |
783 | } | |
784 | ||
3bf25cb4 | 785 | brelse(epos.bh); |
1da177e4 | 786 | |
cb00ea35 | 787 | if (spread == 0xFFFFFFFF) { |
3bf25cb4 | 788 | brelse(goal_epos.bh); |
1e7933de | 789 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
790 | return 0; |
791 | } | |
792 | ||
793 | /* Only allocate blocks from the beginning of the extent. | |
794 | That way, we only delete (empty) extents, never have to insert an | |
795 | extent because of splitting */ | |
796 | /* This works, but very poorly.... */ | |
797 | ||
798 | newblock = goal_eloc.logicalBlockNum; | |
cb00ea35 | 799 | goal_eloc.logicalBlockNum++; |
1da177e4 LT |
800 | goal_elen -= sb->s_blocksize; |
801 | ||
bacfb7c2 | 802 | if (inode && vfs_dq_alloc_block(inode, 1)) { |
3bf25cb4 | 803 | brelse(goal_epos.bh); |
1e7933de | 804 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
805 | *err = -EDQUOT; |
806 | return 0; | |
807 | } | |
808 | ||
809 | if (goal_elen) | |
97e961fd | 810 | udf_write_aext(table, &goal_epos, &goal_eloc, goal_elen, 1); |
1da177e4 | 811 | else |
ff116fc8 | 812 | udf_delete_aext(table, goal_epos, goal_eloc, goal_elen); |
3bf25cb4 | 813 | brelse(goal_epos.bh); |
1da177e4 | 814 | |
146bca72 | 815 | udf_add_free_space(sb, partition, -1); |
1da177e4 | 816 | |
1e7933de | 817 | mutex_unlock(&sbi->s_alloc_mutex); |
1da177e4 LT |
818 | *err = 0; |
819 | return newblock; | |
820 | } | |
821 | ||
97e961fd PE |
822 | void udf_free_blocks(struct super_block *sb, struct inode *inode, |
823 | struct kernel_lb_addr *bloc, uint32_t offset, | |
824 | uint32_t count) | |
1da177e4 | 825 | { |
97e961fd | 826 | uint16_t partition = bloc->partitionReferenceNum; |
6c79e987 | 827 | struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; |
1da177e4 | 828 | |
6c79e987 | 829 | if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) { |
e650b94a JK |
830 | udf_bitmap_free_blocks(sb, inode, map->s_uspace.s_bitmap, |
831 | bloc, offset, count); | |
6c79e987 | 832 | } else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) { |
e650b94a JK |
833 | udf_table_free_blocks(sb, inode, map->s_uspace.s_table, |
834 | bloc, offset, count); | |
6c79e987 | 835 | } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) { |
e650b94a JK |
836 | udf_bitmap_free_blocks(sb, inode, map->s_fspace.s_bitmap, |
837 | bloc, offset, count); | |
6c79e987 | 838 | } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) { |
e650b94a JK |
839 | udf_table_free_blocks(sb, inode, map->s_fspace.s_table, |
840 | bloc, offset, count); | |
28de7948 | 841 | } |
1da177e4 LT |
842 | } |
843 | ||
cb00ea35 CG |
844 | inline int udf_prealloc_blocks(struct super_block *sb, |
845 | struct inode *inode, | |
846 | uint16_t partition, uint32_t first_block, | |
847 | uint32_t block_count) | |
1da177e4 | 848 | { |
6c79e987 MS |
849 | struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; |
850 | ||
4b11111a | 851 | if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) |
1da177e4 | 852 | return udf_bitmap_prealloc_blocks(sb, inode, |
6c79e987 | 853 | map->s_uspace.s_bitmap, |
4b11111a MS |
854 | partition, first_block, |
855 | block_count); | |
856 | else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) | |
1da177e4 | 857 | return udf_table_prealloc_blocks(sb, inode, |
6c79e987 | 858 | map->s_uspace.s_table, |
4b11111a MS |
859 | partition, first_block, |
860 | block_count); | |
861 | else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) | |
1da177e4 | 862 | return udf_bitmap_prealloc_blocks(sb, inode, |
6c79e987 | 863 | map->s_fspace.s_bitmap, |
4b11111a MS |
864 | partition, first_block, |
865 | block_count); | |
866 | else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) | |
1da177e4 | 867 | return udf_table_prealloc_blocks(sb, inode, |
6c79e987 | 868 | map->s_fspace.s_table, |
4b11111a MS |
869 | partition, first_block, |
870 | block_count); | |
871 | else | |
1da177e4 LT |
872 | return 0; |
873 | } | |
874 | ||
cb00ea35 CG |
875 | inline int udf_new_block(struct super_block *sb, |
876 | struct inode *inode, | |
877 | uint16_t partition, uint32_t goal, int *err) | |
1da177e4 | 878 | { |
6c79e987 | 879 | struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition]; |
3bf25cb4 | 880 | |
4b11111a MS |
881 | if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) |
882 | return udf_bitmap_new_block(sb, inode, | |
6c79e987 | 883 | map->s_uspace.s_bitmap, |
28de7948 | 884 | partition, goal, err); |
4b11111a | 885 | else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) |
1da177e4 | 886 | return udf_table_new_block(sb, inode, |
6c79e987 | 887 | map->s_uspace.s_table, |
28de7948 | 888 | partition, goal, err); |
4b11111a | 889 | else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) |
1da177e4 | 890 | return udf_bitmap_new_block(sb, inode, |
6c79e987 | 891 | map->s_fspace.s_bitmap, |
28de7948 | 892 | partition, goal, err); |
4b11111a | 893 | else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) |
1da177e4 | 894 | return udf_table_new_block(sb, inode, |
6c79e987 | 895 | map->s_fspace.s_table, |
28de7948 | 896 | partition, goal, err); |
4b11111a | 897 | else { |
1da177e4 LT |
898 | *err = -EIO; |
899 | return 0; | |
900 | } | |
901 | } |