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