Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/roland...
[linux-2.6] / fs / udf / balloc.c
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 }