?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
ACPI: Introduce acpi_get_pci_dev()
[linux-2.6/linux-acpi-2.6.git] / fs / udf / balloc.c
blobe48e9a3af76312d683723658ed42c51db7d8a740
1 /*
2 * balloc.c
3 *
4 * PURPOSE
5 * Block allocation handling routines for the OSTA-UDF(tm) filesystem.
6 *
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
31 #define udf_clear_bit(nr, addr) ext2_clear_bit(nr, addr)
32 #define udf_set_bit(nr, addr) ext2_set_bit(nr, addr)
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)
35 #define udf_find_next_one_bit(addr, size, offset) \
36 find_next_one_bit(addr, size, offset)
37
38 #define leBPL_to_cpup(x) leNUM_to_cpup(BITS_PER_LONG, x)
39 #define leNUM_to_cpup(x, y) xleNUM_to_cpup(x, y)
40 #define xleNUM_to_cpup(x, y) (le ## x ## _to_cpup(y))
41 #define uintBPL_t uint(BITS_PER_LONG)
42 #define uint(x) xuint(x)
43 #define xuint(x) __le ## x
44
45 static inline int find_next_one_bit(void *addr, int size, int offset)
46 {
47 uintBPL_t *p = ((uintBPL_t *) addr) + (offset / BITS_PER_LONG);
48 int result = offset & ~(BITS_PER_LONG - 1);
49 unsigned long tmp;
50
51 if (offset >= size)
52 return size;
53 size -= result;
54 offset &= (BITS_PER_LONG - 1);
55 if (offset) {
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 }
65 while (size & ~(BITS_PER_LONG - 1)) {
66 tmp = leBPL_to_cpup(p++);
67 if (tmp)
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);
75 found_first:
76 tmp &= ~0UL >> (BITS_PER_LONG - size);
77 found_middle:
78 return result + ffz(~tmp);
79 }
80
81 #define find_first_one_bit(addr, size)\
82 find_next_one_bit((addr), (size), 0)
83
84 static int read_block_bitmap(struct super_block *sb,
85 struct udf_bitmap *bitmap, unsigned int block,
86 unsigned long bitmap_nr)
87 {
88 struct buffer_head *bh = NULL;
89 int retval = 0;
90 struct kernel_lb_addr loc;
91
92 loc.logicalBlockNum = bitmap->s_extPosition;
93 loc.partitionReferenceNum = UDF_SB(sb)->s_partition;
94
95 bh = udf_tread(sb, udf_get_lb_pblock(sb, &loc, block));
96 if (!bh)
97 retval = -EIO;
98
99 bitmap->s_block_bitmap[bitmap_nr] = bh;
100 return retval;
101 }
102
103 static int __load_block_bitmap(struct super_block *sb,
104 struct udf_bitmap *bitmap,
105 unsigned int block_group)
106 {
107 int retval = 0;
108 int nr_groups = bitmap->s_nr_groups;
109
110 if (block_group >= nr_groups) {
111 udf_debug("block_group (%d) > nr_groups (%d)\n", block_group,
112 nr_groups);
113 }
114
115 if (bitmap->s_block_bitmap[block_group]) {
116 return block_group;
117 } else {
118 retval = read_block_bitmap(sb, bitmap, block_group,
119 block_group);
120 if (retval < 0)
121 return retval;
122 return block_group;
123 }
124 }
125
126 static inline int load_block_bitmap(struct super_block *sb,
127 struct udf_bitmap *bitmap,
128 unsigned int block_group)
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
143 static void udf_add_free_space(struct super_block *sb, u16 partition, u32 cnt)
144 {
145 struct udf_sb_info *sbi = UDF_SB(sb);
146 struct logicalVolIntegrityDesc *lvid;
147
148 if (!sbi->s_lvid_bh)
149 return;
150
151 lvid = (struct logicalVolIntegrityDesc *)sbi->s_lvid_bh->b_data;
152 le32_add_cpu(&lvid->freeSpaceTable[partition], cnt);
153 udf_updated_lvid(sb);
154 }
155
156 static void udf_bitmap_free_blocks(struct super_block *sb,
157 struct inode *inode,
158 struct udf_bitmap *bitmap,
159 struct kernel_lb_addr *bloc,
160 uint32_t offset,
161 uint32_t count)
162 {
163 struct udf_sb_info *sbi = UDF_SB(sb);
164 struct buffer_head *bh = NULL;
165 struct udf_part_map *partmap;
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
173 mutex_lock(&sbi->s_alloc_mutex);
174 partmap = &sbi->s_partmaps[bloc->partitionReferenceNum];
175 if (bloc->logicalBlockNum < 0 ||
176 (bloc->logicalBlockNum + count) >
177 partmap->s_partition_len) {
178 udf_debug("%d < %d || %d + %d > %d\n",
179 bloc->logicalBlockNum, 0, bloc->logicalBlockNum,
180 count, partmap->s_partition_len);
181 goto error_return;
182 }
183
184 block = bloc->logicalBlockNum + offset +
185 (sizeof(struct spaceBitmapDesc) << 3);
186
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;
198 }
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)
211 vfs_dq_free_block(inode, 1);
212 udf_add_free_space(sb, sbi->s_partition, 1);
213 }
214 }
215 mark_buffer_dirty(bh);
216 if (overflow) {
217 block += count;
218 count = overflow;
219 }
220 } while (overflow);
221
222 error_return:
223 mutex_unlock(&sbi->s_alloc_mutex);
224 }
225
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)
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;
237 __u32 part_len;
238
239 mutex_lock(&sbi->s_alloc_mutex);
240 part_len = sbi->s_partmaps[partition].s_partition_len;
241 if (first_block < 0 || first_block >= part_len)
242 goto out;
243
244 if (first_block + block_count > part_len)
245 block_count = part_len - first_block;
246
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);
252
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];
257
258 bit = block % (sb->s_blocksize << 3);
259
260 while (bit < (sb->s_blocksize << 3) && block_count > 0) {
261 if (!udf_test_bit(bit, bh->b_data))
262 goto out;
263 else if (vfs_dq_prealloc_block(inode, 1))
264 goto out;
265 else if (!udf_clear_bit(bit, bh->b_data)) {
266 udf_debug("bit already cleared for block %d\n", bit);
267 vfs_dq_free_block(inode, 1);
268 goto out;
269 }
270 block_count--;
271 alloc_count++;
272 bit++;
273 block++;
274 }
275 mark_buffer_dirty(bh);
276 } while (block_count > 0);
277
278 out:
279 udf_add_free_space(sb, partition, -alloc_count);
280 mutex_unlock(&sbi->s_alloc_mutex);
281 return alloc_count;
282 }
283
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)
288 {
289 struct udf_sb_info *sbi = UDF_SB(sb);
290 int newbit, bit = 0, block, block_group, group_start;
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;
297 mutex_lock(&sbi->s_alloc_mutex);
298
299 repeat:
300 if (goal < 0 || goal >= sbi->s_partmaps[partition].s_partition_len)
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];
312 ptr = memscan((char *)bh->b_data + group_start, 0xFF,
313 sb->s_blocksize - group_start);
314
315 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) {
316 bit = block % (sb->s_blocksize << 3);
317 if (udf_test_bit(bit, bh->b_data))
318 goto got_block;
319
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;
324
325 ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF,
326 sb->s_blocksize - ((bit + 7) >> 3));
327 newbit = (ptr - ((char *)bh->b_data)) << 3;
328 if (newbit < sb->s_blocksize << 3) {
329 bit = newbit;
330 goto search_back;
331 }
332
333 newbit = udf_find_next_one_bit(bh->b_data,
334 sb->s_blocksize << 3, bit);
335 if (newbit < sb->s_blocksize << 3) {
336 bit = newbit;
337 goto got_block;
338 }
339 }
340
341 for (i = 0; i < (nr_groups * 2); i++) {
342 block_group++;
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];
351 if (i < nr_groups) {
352 ptr = memscan((char *)bh->b_data + group_start, 0xFF,
353 sb->s_blocksize - group_start);
354 if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize) {
355 bit = (ptr - ((char *)bh->b_data)) << 3;
356 break;
357 }
358 } else {
359 bit = udf_find_next_one_bit((char *)bh->b_data,
360 sb->s_blocksize << 3,
361 group_start << 3);
362 if (bit < sb->s_blocksize << 3)
363 break;
364 }
365 }
366 if (i >= (nr_groups * 2)) {
367 mutex_unlock(&sbi->s_alloc_mutex);
368 return newblock;
369 }
370 if (bit < sb->s_blocksize << 3)
371 goto search_back;
372 else
373 bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3,
374 group_start << 3);
375 if (bit >= sb->s_blocksize << 3) {
376 mutex_unlock(&sbi->s_alloc_mutex);
377 return 0;
378 }
379
380 search_back:
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 }
387
388 got_block:
389
390 /*
391 * Check quota for allocation of this block.
392 */
393 if (inode && vfs_dq_alloc_block(inode, 1)) {
394 mutex_unlock(&sbi->s_alloc_mutex);
395 *err = -EDQUOT;
396 return 0;
397 }
398
399 newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) -
400 (sizeof(struct spaceBitmapDesc) << 3);
401
402 if (!udf_clear_bit(bit, bh->b_data)) {
403 udf_debug("bit already cleared for block %d\n", bit);
404 goto repeat;
405 }
406
407 mark_buffer_dirty(bh);
408
409 udf_add_free_space(sb, partition, -1);
410 mutex_unlock(&sbi->s_alloc_mutex);
411 *err = 0;
412 return newblock;
413
414 error_return:
415 *err = -EIO;
416 mutex_unlock(&sbi->s_alloc_mutex);
417 return 0;
418 }
419
420 static void udf_table_free_blocks(struct super_block *sb,
421 struct inode *inode,
422 struct inode *table,
423 struct kernel_lb_addr *bloc,
424 uint32_t offset,
425 uint32_t count)
426 {
427 struct udf_sb_info *sbi = UDF_SB(sb);
428 struct udf_part_map *partmap;
429 uint32_t start, end;
430 uint32_t elen;
431 struct kernel_lb_addr eloc;
432 struct extent_position oepos, epos;
433 int8_t etype;
434 int i;
435 struct udf_inode_info *iinfo;
436
437 mutex_lock(&sbi->s_alloc_mutex);
438 partmap = &sbi->s_partmaps[bloc->partitionReferenceNum];
439 if (bloc->logicalBlockNum < 0 ||
440 (bloc->logicalBlockNum + count) >
441 partmap->s_partition_len) {
442 udf_debug("%d < %d || %d + %d > %d\n",
443 bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count,
444 partmap->s_partition_len);
445 goto error_return;
446 }
447
448 iinfo = UDF_I(table);
449 /* We do this up front - There are some error conditions that
450 could occure, but.. oh well */
451 if (inode)
452 vfs_dq_free_block(inode, count);
453 udf_add_free_space(sb, sbi->s_partition, count);
454
455 start = bloc->logicalBlockNum + offset;
456 end = bloc->logicalBlockNum + offset + count - 1;
457
458 epos.offset = oepos.offset = sizeof(struct unallocSpaceEntry);
459 elen = 0;
460 epos.block = oepos.block = iinfo->i_location;
461 epos.bh = oepos.bh = NULL;
462
463 while (count &&
464 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) {
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);
475 } else {
476 elen = (etype << 30) |
477 (elen +
478 (count << sb->s_blocksize_bits));
479 start += count;
480 count = 0;
481 }
482 udf_write_aext(table, &oepos, &eloc, elen, 1);
483 } else if (eloc.logicalBlockNum == (end + 1)) {
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);
493 } else {
494 eloc.logicalBlockNum = start;
495 elen = (etype << 30) |
496 (elen +
497 (count << sb->s_blocksize_bits));
498 end -= count;
499 count = 0;
500 }
501 udf_write_aext(table, &oepos, &eloc, elen, 1);
502 }
503
504 if (epos.bh != oepos.bh) {
505 i = -1;
506 oepos.block = epos.block;
507 brelse(oepos.bh);
508 get_bh(epos.bh);
509 oepos.bh = epos.bh;
510 oepos.offset = 0;
511 } else {
512 oepos.offset = epos.offset;
513 }
514 }
515
516 if (count) {
517 /*
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 :)
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.
528 */
529
530 int adsize;
531 struct short_ad *sad = NULL;
532 struct long_ad *lad = NULL;
533 struct allocExtDesc *aed;
534
535 eloc.logicalBlockNum = start;
536 elen = EXT_RECORDED_ALLOCATED |
537 (count << sb->s_blocksize_bits);
538
539 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
540 adsize = sizeof(struct short_ad);
541 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
542 adsize = sizeof(struct long_ad);
543 else {
544 brelse(oepos.bh);
545 brelse(epos.bh);
546 goto error_return;
547 }
548
549 if (epos.offset + (2 * adsize) > sb->s_blocksize) {
550 char *sptr, *dptr;
551 int loffset;
552
553 brelse(oepos.bh);
554 oepos = epos;
555
556 /* Steal a block from the extent being free'd */
557 epos.block.logicalBlockNum = eloc.logicalBlockNum;
558 eloc.logicalBlockNum++;
559 elen -= sb->s_blocksize;
560
561 epos.bh = udf_tread(sb,
562 udf_get_lb_pblock(sb, &epos.block, 0));
563 if (!epos.bh) {
564 brelse(oepos.bh);
565 goto error_return;
566 }
567 aed = (struct allocExtDesc *)(epos.bh->b_data);
568 aed->previousAllocExtLocation =
569 cpu_to_le32(oepos.block.logicalBlockNum);
570 if (epos.offset + adsize > sb->s_blocksize) {
571 loffset = epos.offset;
572 aed->lengthAllocDescs = cpu_to_le32(adsize);
573 sptr = iinfo->i_ext.i_data + epos.offset
574 - adsize;
575 dptr = epos.bh->b_data +
576 sizeof(struct allocExtDesc);
577 memcpy(dptr, sptr, adsize);
578 epos.offset = sizeof(struct allocExtDesc) +
579 adsize;
580 } else {
581 loffset = epos.offset + adsize;
582 aed->lengthAllocDescs = cpu_to_le32(0);
583 if (oepos.bh) {
584 sptr = oepos.bh->b_data + epos.offset;
585 aed = (struct allocExtDesc *)
586 oepos.bh->b_data;
587 le32_add_cpu(&aed->lengthAllocDescs,
588 adsize);
589 } else {
590 sptr = iinfo->i_ext.i_data +
591 epos.offset;
592 iinfo->i_lenAlloc += adsize;
593 mark_inode_dirty(table);
594 }
595 epos.offset = sizeof(struct allocExtDesc);
596 }
597 if (sbi->s_udfrev >= 0x0200)
598 udf_new_tag(epos.bh->b_data, TAG_IDENT_AED,
599 3, 1, epos.block.logicalBlockNum,
600 sizeof(struct tag));
601 else
602 udf_new_tag(epos.bh->b_data, TAG_IDENT_AED,
603 2, 1, epos.block.logicalBlockNum,
604 sizeof(struct tag));
605
606 switch (iinfo->i_alloc_type) {
607 case ICBTAG_FLAG_AD_SHORT:
608 sad = (struct short_ad *)sptr;
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:
616 lad = (struct long_ad *)sptr;
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;
623 }
624 if (oepos.bh) {
625 udf_update_tag(oepos.bh->b_data, loffset);
626 mark_buffer_dirty(oepos.bh);
627 } else {
628 mark_inode_dirty(table);
629 }
630 }
631
632 /* It's possible that stealing the block emptied the extent */
633 if (elen) {
634 udf_write_aext(table, &epos, &eloc, elen, 1);
635
636 if (!epos.bh) {
637 iinfo->i_lenAlloc += adsize;
638 mark_inode_dirty(table);
639 } else {
640 aed = (struct allocExtDesc *)epos.bh->b_data;
641 le32_add_cpu(&aed->lengthAllocDescs, adsize);
642 udf_update_tag(epos.bh->b_data, epos.offset);
643 mark_buffer_dirty(epos.bh);
644 }
645 }
646 }
647
648 brelse(epos.bh);
649 brelse(oepos.bh);
650
651 error_return:
652 mutex_unlock(&sbi->s_alloc_mutex);
653 return;
654 }
655
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)
660 {
661 struct udf_sb_info *sbi = UDF_SB(sb);
662 int alloc_count = 0;
663 uint32_t elen, adsize;
664 struct kernel_lb_addr eloc;
665 struct extent_position epos;
666 int8_t etype = -1;
667 struct udf_inode_info *iinfo;
668
669 if (first_block < 0 ||
670 first_block >= sbi->s_partmaps[partition].s_partition_len)
671 return 0;
672
673 iinfo = UDF_I(table);
674 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
675 adsize = sizeof(struct short_ad);
676 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
677 adsize = sizeof(struct long_ad);
678 else
679 return 0;
680
681 mutex_lock(&sbi->s_alloc_mutex);
682 epos.offset = sizeof(struct unallocSpaceEntry);
683 epos.block = iinfo->i_location;
684 epos.bh = NULL;
685 eloc.logicalBlockNum = 0xFFFFFFFF;
686
687 while (first_block != eloc.logicalBlockNum &&
688 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) {
689 udf_debug("eloc=%d, elen=%d, first_block=%d\n",
690 eloc.logicalBlockNum, elen, first_block);
691 ; /* empty loop body */
692 }
693
694 if (first_block == eloc.logicalBlockNum) {
695 epos.offset -= adsize;
696
697 alloc_count = (elen >> sb->s_blocksize_bits);
698 if (inode && vfs_dq_prealloc_block(inode,
699 alloc_count > block_count ? block_count : alloc_count))
700 alloc_count = 0;
701 else if (alloc_count > block_count) {
702 alloc_count = block_count;
703 eloc.logicalBlockNum += alloc_count;
704 elen -= (alloc_count << sb->s_blocksize_bits);
705 udf_write_aext(table, &epos, &eloc,
706 (etype << 30) | elen, 1);
707 } else
708 udf_delete_aext(table, epos, eloc,
709 (etype << 30) | elen);
710 } else {
711 alloc_count = 0;
712 }
713
714 brelse(epos.bh);
715
716 if (alloc_count)
717 udf_add_free_space(sb, partition, -alloc_count);
718 mutex_unlock(&sbi->s_alloc_mutex);
719 return alloc_count;
720 }
721
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)
726 {
727 struct udf_sb_info *sbi = UDF_SB(sb);
728 uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF;
729 uint32_t newblock = 0, adsize;
730 uint32_t elen, goal_elen = 0;
731 struct kernel_lb_addr eloc, uninitialized_var(goal_eloc);
732 struct extent_position epos, goal_epos;
733 int8_t etype;
734 struct udf_inode_info *iinfo = UDF_I(table);
735
736 *err = -ENOSPC;
737
738 if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_SHORT)
739 adsize = sizeof(struct short_ad);
740 else if (iinfo->i_alloc_type == ICBTAG_FLAG_AD_LONG)
741 adsize = sizeof(struct long_ad);
742 else
743 return newblock;
744
745 mutex_lock(&sbi->s_alloc_mutex);
746 if (goal < 0 || goal >= sbi->s_partmaps[partition].s_partition_len)
747 goal = 0;
748
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.
753 */
754 epos.offset = sizeof(struct unallocSpaceEntry);
755 epos.block = iinfo->i_location;
756 epos.bh = goal_epos.bh = NULL;
757
758 while (spread &&
759 (etype = udf_next_aext(table, &epos, &eloc, &elen, 1)) != -1) {
760 if (goal >= eloc.logicalBlockNum) {
761 if (goal < eloc.logicalBlockNum +
762 (elen >> sb->s_blocksize_bits))
763 nspread = 0;
764 else
765 nspread = goal - eloc.logicalBlockNum -
766 (elen >> sb->s_blocksize_bits);
767 } else {
768 nspread = eloc.logicalBlockNum - goal;
769 }
770
771 if (nspread < spread) {
772 spread = nspread;
773 if (goal_epos.bh != epos.bh) {
774 brelse(goal_epos.bh);
775 goal_epos.bh = epos.bh;
776 get_bh(goal_epos.bh);
777 }
778 goal_epos.block = epos.block;
779 goal_epos.offset = epos.offset - adsize;
780 goal_eloc = eloc;
781 goal_elen = (etype << 30) | elen;
782 }
783 }
784
785 brelse(epos.bh);
786
787 if (spread == 0xFFFFFFFF) {
788 brelse(goal_epos.bh);
789 mutex_unlock(&sbi->s_alloc_mutex);
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;
799 goal_eloc.logicalBlockNum++;
800 goal_elen -= sb->s_blocksize;
801
802 if (inode && vfs_dq_alloc_block(inode, 1)) {
803 brelse(goal_epos.bh);
804 mutex_unlock(&sbi->s_alloc_mutex);
805 *err = -EDQUOT;
806 return 0;
807 }
808
809 if (goal_elen)
810 udf_write_aext(table, &goal_epos, &goal_eloc, goal_elen, 1);
811 else
812 udf_delete_aext(table, goal_epos, goal_eloc, goal_elen);
813 brelse(goal_epos.bh);
814
815 udf_add_free_space(sb, partition, -1);
816
817 mutex_unlock(&sbi->s_alloc_mutex);
818 *err = 0;
819 return newblock;
820 }
821
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)
825 {
826 uint16_t partition = bloc->partitionReferenceNum;
827 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
828
829 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP) {
830 udf_bitmap_free_blocks(sb, inode, map->s_uspace.s_bitmap,
831 bloc, offset, count);
832 } else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE) {
833 udf_table_free_blocks(sb, inode, map->s_uspace.s_table,
834 bloc, offset, count);
835 } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP) {
836 udf_bitmap_free_blocks(sb, inode, map->s_fspace.s_bitmap,
837 bloc, offset, count);
838 } else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE) {
839 udf_table_free_blocks(sb, inode, map->s_fspace.s_table,
840 bloc, offset, count);
841 }
842 }
843
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)
848 {
849 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
850
851 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP)
852 return udf_bitmap_prealloc_blocks(sb, inode,
853 map->s_uspace.s_bitmap,
854 partition, first_block,
855 block_count);
856 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE)
857 return udf_table_prealloc_blocks(sb, inode,
858 map->s_uspace.s_table,
859 partition, first_block,
860 block_count);
861 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP)
862 return udf_bitmap_prealloc_blocks(sb, inode,
863 map->s_fspace.s_bitmap,
864 partition, first_block,
865 block_count);
866 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE)
867 return udf_table_prealloc_blocks(sb, inode,
868 map->s_fspace.s_table,
869 partition, first_block,
870 block_count);
871 else
872 return 0;
873 }
874
875 inline int udf_new_block(struct super_block *sb,
876 struct inode *inode,
877 uint16_t partition, uint32_t goal, int *err)
878 {
879 struct udf_part_map *map = &UDF_SB(sb)->s_partmaps[partition];
880
881 if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_BITMAP)
882 return udf_bitmap_new_block(sb, inode,
883 map->s_uspace.s_bitmap,
884 partition, goal, err);
885 else if (map->s_partition_flags & UDF_PART_FLAG_UNALLOC_TABLE)
886 return udf_table_new_block(sb, inode,
887 map->s_uspace.s_table,
888 partition, goal, err);
889 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_BITMAP)
890 return udf_bitmap_new_block(sb, inode,
891 map->s_fspace.s_bitmap,
892 partition, goal, err);
893 else if (map->s_partition_flags & UDF_PART_FLAG_FREED_TABLE)
894 return udf_table_new_block(sb, inode,
895 map->s_fspace.s_table,
896 partition, goal, err);
897 else {
898 *err = -EIO;
899 return 0;
900 }
901 }
Linux ACPI git tree (mirror)