1 /*
2 * balloc.c
3 *
4 * PURPOSE
5 * Block allocation handling routines for the OSTA-UDF(tm) filesystem.
6 *
7 * CONTACTS
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
11 *
12 * COPYRIGHT
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.
17 *
18 * (C) 1999-2000 Ben Fennema
19 * (C) 1999 Stelias Computing Inc
20 *
21 * HISTORY
22 *
23 * 02/24/99 blf Created.
24 *
25 */
26
27 #include "udfdecl.h"
28 #include <linux/fs.h>
29 #include <linux/locks.h>
30 #include <linux/quotaops.h>
31 #include <linux/udf_fs.h>
32
33 #include <asm/bitops.h>
34
35 #include "udf_i.h"
36 #include "udf_sb.h"
37
38 #define udf_clear_bit(nr,addr) ext2_clear_bit(nr,addr)
39 #define udf_set_bit(nr,addr) ext2_set_bit(nr,addr)
40 #define udf_test_bit(nr, addr) ext2_test_bit(nr, addr)
41 #define udf_find_first_one_bit(addr, size) find_first_one_bit(addr, size)
42 #define udf_find_next_one_bit(addr, size, offset) find_next_one_bit(addr, size, offset)
43
44 #define leBPL_to_cpup(x) leNUM_to_cpup(BITS_PER_LONG, x)
45 #define leNUM_to_cpup(x,y) xleNUM_to_cpup(x,y)
46 #define xleNUM_to_cpup(x,y) (le ## x ## _to_cpup(y))
47
48 extern inline int find_next_one_bit (void * addr, int size, int offset)
49 {
50 unsigned long * p = ((unsigned long *) addr) + (offset / BITS_PER_LONG);
51 unsigned long result = offset & ~(BITS_PER_LONG-1);
52 unsigned long tmp;
53
54 if (offset >= size)
55 return size;
56 size -= result;
57 offset &= (BITS_PER_LONG-1);
58 if (offset)
59 {
60 tmp = leBPL_to_cpup(p++);
61 tmp &= ~0UL << offset;
62 if (size < BITS_PER_LONG)
63 goto found_first;
64 if (tmp)
65 goto found_middle;
66 size -= BITS_PER_LONG;
67 result += BITS_PER_LONG;
68 }
69 while (size & ~(BITS_PER_LONG-1))
70 {
71 if ((tmp = leBPL_to_cpup(p++)))
72 goto found_middle;
73 result += BITS_PER_LONG;
74 size -= BITS_PER_LONG;
75 }
76 if (!size)
77 return result;
78 tmp = leBPL_to_cpup(p);
79 found_first:
80 tmp &= ~0UL >> (BITS_PER_LONG-size);
81 found_middle:
82 return result + ffz(~tmp);
83 }
84
85 #define find_first_one_bit(addr, size)\
86 find_next_one_bit((addr), (size), 0)
87
88 static int read_block_bitmap(struct super_block * sb, Uint32 bitmap,
89 unsigned int block, unsigned long bitmap_nr)
90 {
91 struct buffer_head *bh = NULL;
92 int retval = 0;
93 lb_addr loc;
94
95 loc.logicalBlockNum = bitmap;
96 loc.partitionReferenceNum = UDF_SB_PARTITION(sb);
97
98 bh = udf_tread(sb, udf_get_lb_pblock(sb, loc, block), sb->s_blocksize);
99 if (!bh)
100 {
101 retval = -EIO;
102 }
103 UDF_SB_BLOCK_BITMAP_NUMBER(sb, bitmap_nr) = block;
104 UDF_SB_BLOCK_BITMAP(sb, bitmap_nr) = bh;
105 return retval;
106 }
107
108 static int __load_block_bitmap(struct super_block * sb, Uint32 bitmap,
109 unsigned int block_group)
110 {
111 int i, j, retval = 0;
112 unsigned long block_bitmap_number;
113 struct buffer_head * block_bitmap = NULL;
114 int nr_groups = (UDF_SB_PARTLEN(sb, UDF_SB_PARTITION(sb)) +
115 (sizeof(struct SpaceBitmapDesc) << 3) + (sb->s_blocksize * 8) - 1) / (sb->s_blocksize * 8);
116
117 if (block_group >= nr_groups)
118 {
119 udf_debug("block_group (%d) > nr_groups (%d)\n", block_group, nr_groups);
120 }
121
122 if (nr_groups <= UDF_MAX_BLOCK_LOADED)
123 {
124 if (UDF_SB_BLOCK_BITMAP(sb, block_group))
125 {
126 if (UDF_SB_BLOCK_BITMAP_NUMBER(sb, block_group) == block_group)
127 return block_group;
128 }
129 retval = read_block_bitmap(sb, bitmap, block_group, block_group);
130 if (retval < 0)
131 return retval;
132 return block_group;
133 }
134
135 for (i=0; i<UDF_SB_LOADED_BLOCK_BITMAPS(sb) &&
136 UDF_SB_BLOCK_BITMAP_NUMBER(sb, i) != block_group; i++)
137 {
138 ;
139 }
140 if (i < UDF_SB_LOADED_BLOCK_BITMAPS(sb) &&
141 UDF_SB_BLOCK_BITMAP_NUMBER(sb, i) == block_group)
142 {
143 block_bitmap_number = UDF_SB_BLOCK_BITMAP_NUMBER(sb, i);
144 block_bitmap = UDF_SB_BLOCK_BITMAP(sb, i);
145 for (j=i; j>0; j--)
146 {
147 UDF_SB_BLOCK_BITMAP_NUMBER(sb, j) = UDF_SB_BLOCK_BITMAP_NUMBER(sb, j-1);
148 UDF_SB_BLOCK_BITMAP(sb, j) = UDF_SB_BLOCK_BITMAP(sb, j-1);
149 }
150 UDF_SB_BLOCK_BITMAP_NUMBER(sb, 0) = block_bitmap_number;
151 UDF_SB_BLOCK_BITMAP(sb, 0) = block_bitmap;
152
153 if (!block_bitmap)
154 retval = read_block_bitmap(sb, bitmap, block_group, 0);
155 }
156 else
157 {
158 if (UDF_SB_LOADED_BLOCK_BITMAPS(sb) < UDF_MAX_BLOCK_LOADED)
159 UDF_SB_LOADED_BLOCK_BITMAPS(sb) ++;
160 else
161 brelse(UDF_SB_BLOCK_BITMAP(sb, UDF_MAX_BLOCK_LOADED-1));
162 for (j=UDF_SB_LOADED_BLOCK_BITMAPS(sb)-1; j>0; j--)
163 {
164 UDF_SB_BLOCK_BITMAP_NUMBER(sb, j) = UDF_SB_BLOCK_BITMAP_NUMBER(sb, j-1);
165 UDF_SB_BLOCK_BITMAP(sb, j) = UDF_SB_BLOCK_BITMAP(sb, j-1);
166 }
167 retval = read_block_bitmap(sb, bitmap, block_group, 0);
168 }
169 return retval;
170 }
171
172 static inline int load_block_bitmap(struct super_block *sb, Uint32 bitmap,
173 unsigned int block_group)
174 {
175 int slot;
176 int nr_groups = (UDF_SB_PARTLEN(sb, UDF_SB_PARTITION(sb)) +
177 (sizeof(struct SpaceBitmapDesc) << 3) + (sb->s_blocksize * 8) - 1) / (sb->s_blocksize * 8);
178
179 if (UDF_SB_LOADED_BLOCK_BITMAPS(sb) > 0 &&
180 UDF_SB_BLOCK_BITMAP_NUMBER(sb, 0) == block_group &&
181 UDF_SB_BLOCK_BITMAP(sb, block_group))
182 {
183 return 0;
184 }
185 else if (nr_groups <= UDF_MAX_BLOCK_LOADED &&
186 UDF_SB_BLOCK_BITMAP_NUMBER(sb, block_group) == block_group &&
187 UDF_SB_BLOCK_BITMAP(sb, block_group))
188 {
189 slot = block_group;
190 }
191 else
192 {
193 slot = __load_block_bitmap(sb, bitmap, block_group);
194 }
195
196 if (slot < 0)
197 return slot;
198
199 if (!UDF_SB_BLOCK_BITMAP(sb, slot))
200 return -EIO;
201
202 return slot;
203 }
204
205 static void udf_bitmap_free_blocks(const struct inode * inode, Uint32 bitmap,
206 lb_addr bloc, Uint32 offset, Uint32 count)
207 {
208 struct buffer_head * bh = NULL;
209 unsigned long block;
210 unsigned long block_group;
211 unsigned long bit;
212 unsigned long i;
213 int bitmap_nr;
214 unsigned long overflow;
215 struct super_block * sb;
216
217 sb = inode->i_sb;
218 if (!sb)
219 {
220 udf_debug("nonexistent device");
221 return;
222 }
223
224 lock_super(sb);
225 if (bloc.logicalBlockNum < 0 ||
226 (bloc.logicalBlockNum + count) > UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum))
227 {
228 udf_debug("%d < %d || %d + %d > %d\n",
229 bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count,
230 UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum));
231 goto error_return;
232 }
233
234 block = bloc.logicalBlockNum + offset + (sizeof(struct SpaceBitmapDesc) << 3);
235
236 do_more:
237 overflow = 0;
238 block_group = block >> (sb->s_blocksize_bits + 3);
239 bit = block % (sb->s_blocksize << 3);
240
241 /*
242 * Check to see if we are freeing blocks across a group boundary.
243 */
244 if (bit + count > (sb->s_blocksize << 3))
245 {
246 overflow = bit + count - (sb->s_blocksize << 3);
247 count -= overflow;
248 }
249 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
250 if (bitmap_nr < 0)
251 goto error_return;
252
253 bh = UDF_SB_BLOCK_BITMAP(sb, bitmap_nr);
254 for (i=0; i < count; i++)
255 {
256 if (udf_set_bit(bit + i, bh->b_data))
257 {
258 udf_debug("bit %ld already set\n", bit + i);
259 udf_debug("byte=%2x\n", ((char *)bh->b_data)[(bit + i) >> 3]);
260 }
261 else
262 {
263 DQUOT_FREE_BLOCK(sb, inode, 1);
264 if (UDF_SB_LVIDBH(sb))
265 {
266 UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)] =
267 cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)])+1);
268 }
269 }
270 }
271 mark_buffer_dirty(bh);
272 if (overflow)
273 {
274 block += count;
275 count = overflow;
276 goto do_more;
277 }
278 error_return:
279 sb->s_dirt = 1;
280 if (UDF_SB_LVIDBH(sb))
281 mark_buffer_dirty(UDF_SB_LVIDBH(sb));
282 unlock_super(sb);
283 return;
284 }
285
286 static int udf_bitmap_prealloc_blocks(const struct inode * inode, Uint32 bitmap,
287 Uint16 partition, Uint32 first_block, Uint32 block_count)
288 {
289 int alloc_count = 0;
290 int bit, block, block_group, group_start;
291 int nr_groups, bitmap_nr;
292 struct buffer_head *bh;
293 struct super_block *sb;
294
295 sb = inode->i_sb;
296 if (!sb)
297 {
298 udf_debug("nonexistent device\n");
299 return 0;
300 }
301 lock_super(sb);
302
303 if (first_block < 0 || first_block >= UDF_SB_PARTLEN(sb, partition))
304 goto out;
305
306 repeat:
307 nr_groups = (UDF_SB_PARTLEN(sb, partition) +
308 (sizeof(struct SpaceBitmapDesc) << 3) + (sb->s_blocksize * 8) - 1) / (sb->s_blocksize * 8);
309 block = first_block + (sizeof(struct SpaceBitmapDesc) << 3);
310 block_group = block >> (sb->s_blocksize_bits + 3);
311 group_start = block_group ? 0 : sizeof(struct SpaceBitmapDesc);
312
313 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
314 if (bitmap_nr < 0)
315 goto out;
316 bh = UDF_SB_BLOCK_BITMAP(sb, bitmap_nr);
317
318 bit = block % (sb->s_blocksize << 3);
319
320 while (bit < (sb->s_blocksize << 3) && block_count > 0)
321 {
322 if (!udf_test_bit(bit, bh->b_data))
323 goto out;
324 else if (DQUOT_PREALLOC_BLOCK(sb, inode, 1))
325 goto out;
326 else if (!udf_clear_bit(bit, bh->b_data))
327 {
328 udf_debug("bit already cleared for block %d\n", bit);
329 DQUOT_FREE_BLOCK(sb, inode, 1);
330 goto out;
331 }
332 block_count --;
333 alloc_count ++;
334 bit ++;
335 block ++;
336 }
337 mark_buffer_dirty(bh);
338 if (block_count > 0)
339 goto repeat;
340 out:
341 if (UDF_SB_LVIDBH(sb))
342 {
343 UDF_SB_LVID(sb)->freeSpaceTable[partition] =
344 cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-alloc_count);
345 mark_buffer_dirty(UDF_SB_LVIDBH(sb));
346 }
347 sb->s_dirt = 1;
348 unlock_super(sb);
349 return alloc_count;
350 }
351
352 static int udf_bitmap_new_block(const struct inode * inode, Uint32 bitmap,
353 Uint16 partition, Uint32 goal, int *err)
354 {
355 int tmp, newbit, bit=0, block, block_group, group_start;
356 int end_goal, nr_groups, bitmap_nr, i;
357 struct buffer_head *bh = NULL;
358 struct super_block *sb;
359 char *ptr;
360 int newblock = 0;
361
362 *err = -ENOSPC;
363 sb = inode->i_sb;
364 if (!sb)
365 {
366 udf_debug("nonexistent device\n");
367 return newblock;
368 }
369 lock_super(sb);
370
371 repeat:
372 if (goal < 0 || goal >= UDF_SB_PARTLEN(sb, partition))
373 goal = 0;
374
375 nr_groups = (UDF_SB_PARTLEN(sb, partition) +
376 (sizeof(struct SpaceBitmapDesc) << 3) + (sb->s_blocksize * 8) - 1) / (sb->s_blocksize * 8);
377 block = goal + (sizeof(struct SpaceBitmapDesc) << 3);
378 block_group = block >> (sb->s_blocksize_bits + 3);
379 group_start = block_group ? 0 : sizeof(struct SpaceBitmapDesc);
380
381 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
382 if (bitmap_nr < 0)
383 goto error_return;
384 bh = UDF_SB_BLOCK_BITMAP(sb, bitmap_nr);
385 ptr = memscan((char *)bh->b_data + group_start, 0xFF, sb->s_blocksize - group_start);
386
387 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize)
388 {
389 bit = block % (sb->s_blocksize << 3);
390
391 if (udf_test_bit(bit, bh->b_data))
392 {
393 goto got_block;
394 }
395 end_goal = (bit + 63) & ~63;
396 bit = udf_find_next_one_bit(bh->b_data, end_goal, bit);
397 if (bit < end_goal)
398 goto got_block;
399 ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF, sb->s_blocksize - ((bit + 7) >> 3));
400 newbit = (ptr - ((char *)bh->b_data)) << 3;
401 if (newbit < sb->s_blocksize << 3)
402 {
403 bit = newbit;
404 goto search_back;
405 }
406 newbit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, bit);
407 if (newbit < sb->s_blocksize << 3)
408 {
409 bit = newbit;
410 goto got_block;
411 }
412 }
413
414 for (i=0; i<(nr_groups*2); i++)
415 {
416 block_group ++;
417 if (block_group >= nr_groups)
418 block_group = 0;
419 group_start = block_group ? 0 : sizeof(struct SpaceBitmapDesc);
420
421 bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
422 if (bitmap_nr < 0)
423 goto error_return;
424 bh = UDF_SB_BLOCK_BITMAP(sb, bitmap_nr);
425 if (i < nr_groups)
426 {
427 ptr = memscan((char *)bh->b_data + group_start, 0xFF, sb->s_blocksize - group_start);
428 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize)
429 {
430 bit = (ptr - ((char *)bh->b_data)) << 3;
431 break;
432 }
433 }
434 else
435 {
436 bit = udf_find_next_one_bit((char *)bh->b_data, sb->s_blocksize << 3, group_start << 3);
437 if (bit < sb->s_blocksize << 3)
438 break;
439 }
440 }
441 if (i >= (nr_groups*2))
442 {
443 unlock_super(sb);
444 return newblock;
445 }
446 if (bit < sb->s_blocksize << 3)
447 goto search_back;
448 else
449 bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, group_start << 3);
450 if (bit >= sb->s_blocksize << 3)
451 {
452 unlock_super(sb);
453 return 0;
454 }
455
456 search_back:
457 for (i=0; i<7 && bit > (group_start << 3) && udf_test_bit(bit - 1, bh->b_data); i++, bit--);
458
459 got_block:
460
461 /*
462 * Check quota for allocation of this block.
463 */
464 if (DQUOT_ALLOC_BLOCK(sb, inode, 1))
465 {
466 unlock_super(sb);
467 *err = -EDQUOT;
468 return 0;
469 }
470
471 newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) -
472 (sizeof(struct SpaceBitmapDesc) << 3);
473
474 tmp = udf_get_pblock(sb, newblock, partition, 0);
475 if (!udf_clear_bit(bit, bh->b_data))
476 {
477 udf_debug("bit already cleared for block %d\n", bit);
478 goto repeat;
479 }
480
481 mark_buffer_dirty(bh);
482
483 if (UDF_SB_LVIDBH(sb))
484 {
485 UDF_SB_LVID(sb)->freeSpaceTable[partition] =
486 cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-1);
487 mark_buffer_dirty(UDF_SB_LVIDBH(sb));
488 }
489 sb->s_dirt = 1;
490 unlock_super(sb);
491 *err = 0;
492 return newblock;
493
494 error_return:
495 *err = -EIO;
496 unlock_super(sb);
497 return 0;
498 }
499
500 inline void udf_free_blocks(const struct inode * inode, lb_addr bloc,
501 Uint32 offset, Uint32 count)
502 {
503 if (UDF_SB_PARTFLAGS(inode->i_sb, bloc.partitionReferenceNum) & UDF_PART_FLAG_UNALLOC_BITMAP)
504 {
505 return udf_bitmap_free_blocks(inode,
506 UDF_SB_PARTMAPS(inode->i_sb)[bloc.partitionReferenceNum].s_uspace.bitmap,
507 bloc, offset, count);
508 }
509 else if (UDF_SB_PARTFLAGS(inode->i_sb, bloc.partitionReferenceNum) & UDF_PART_FLAG_FREED_BITMAP)
510 {
511 return udf_bitmap_free_blocks(inode,
512 UDF_SB_PARTMAPS(inode->i_sb)[bloc.partitionReferenceNum].s_fspace.bitmap,
513 bloc, offset, count);
514 }
515 else
516 return;
517 }
518
519 inline int udf_prealloc_blocks(const struct inode * inode, Uint16 partition,
520 Uint32 first_block, Uint32 block_count)
521 {
522 if (UDF_SB_PARTFLAGS(inode->i_sb, partition) & UDF_PART_FLAG_UNALLOC_BITMAP)
523 {
524 return udf_bitmap_prealloc_blocks(inode,
525 UDF_SB_PARTMAPS(inode->i_sb)[partition].s_uspace.bitmap,
526 partition, first_block, block_count);
527 }
528 else if (UDF_SB_PARTFLAGS(inode->i_sb, partition) & UDF_PART_FLAG_FREED_BITMAP)
529 {
530 return udf_bitmap_prealloc_blocks(inode,
531 UDF_SB_PARTMAPS(inode->i_sb)[partition].s_fspace.bitmap,
532 partition, first_block, block_count);
533 }
534 else
535 return 0;
536 }
537
538 inline int udf_new_block(const struct inode * inode, Uint16 partition,
539 Uint32 goal, int *err)
540 {
541 if (UDF_SB_PARTFLAGS(inode->i_sb, partition) & UDF_PART_FLAG_UNALLOC_BITMAP)
542 {
543 return udf_bitmap_new_block(inode,
544 UDF_SB_PARTMAPS(inode->i_sb)[partition].s_uspace.bitmap,
545 partition, goal, err);
546 }
547 else if (UDF_SB_PARTFLAGS(inode->i_sb, partition) & UDF_PART_FLAG_FREED_BITMAP)
548 {
549 return udf_bitmap_new_block(inode,
550 UDF_SB_PARTMAPS(inode->i_sb)[partition].s_fspace.bitmap,
551 partition, goal, err);
552 }
553 else
554 {
555 *err = -EIO;
556 return 0;
557 }
558 }
559
560
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.