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