xref: /netbsd-src/sys/fs/udf/udf_allocation.c (revision cac8e449158efc7261bebc8657cbb0125a2cfdde)
1 /* $NetBSD: udf_allocation.c,v 1.16 2008/07/28 19:41:13 reinoud Exp $ */
2 
3 /*
4  * Copyright (c) 2006, 2008 Reinoud Zandijk
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  *
27  */
28 
29 #include <sys/cdefs.h>
30 #ifndef lint
31 __KERNEL_RCSID(0, "$NetBSD: udf_allocation.c,v 1.16 2008/07/28 19:41:13 reinoud Exp $");
32 #endif /* not lint */
33 
34 
35 #if defined(_KERNEL_OPT)
36 #include "opt_quota.h"
37 #include "opt_compat_netbsd.h"
38 #endif
39 
40 /* TODO strip */
41 #include <sys/param.h>
42 #include <sys/systm.h>
43 #include <sys/sysctl.h>
44 #include <sys/namei.h>
45 #include <sys/proc.h>
46 #include <sys/kernel.h>
47 #include <sys/vnode.h>
48 #include <miscfs/genfs/genfs_node.h>
49 #include <sys/mount.h>
50 #include <sys/buf.h>
51 #include <sys/file.h>
52 #include <sys/device.h>
53 #include <sys/disklabel.h>
54 #include <sys/ioctl.h>
55 #include <sys/malloc.h>
56 #include <sys/dirent.h>
57 #include <sys/stat.h>
58 #include <sys/conf.h>
59 #include <sys/kauth.h>
60 #include <sys/kthread.h>
61 #include <dev/clock_subr.h>
62 
63 #include <fs/udf/ecma167-udf.h>
64 #include <fs/udf/udf_mount.h>
65 
66 #if defined(_KERNEL_OPT)
67 #include "opt_udf.h"
68 #endif
69 
70 #include "udf.h"
71 #include "udf_subr.h"
72 #include "udf_bswap.h"
73 
74 
75 #define VTOI(vnode) ((struct udf_node *) vnode->v_data)
76 
77 static void udf_record_allocation_in_node(struct udf_mount *ump,
78 	struct buf *buf, uint16_t vpart_num, uint64_t *mapping,
79 	struct long_ad *node_ad_cpy);
80 
81 /*
82  * IDEA/BUSY: Each udf_node gets its own extentwalker state for all operations;
83  * this will hopefully/likely reduce O(nlog(n)) to O(1) for most functionality
84  * since actions are most likely sequencial and thus seeking doesn't need
85  * searching for the same or adjacent position again.
86  */
87 
88 /* --------------------------------------------------------------------- */
89 
90 #if 0
91 #if 1
92 static void
93 udf_node_dump(struct udf_node *udf_node) {
94 	struct file_entry    *fe;
95 	struct extfile_entry *efe;
96 	struct icb_tag *icbtag;
97 	struct long_ad s_ad;
98 	uint64_t inflen;
99 	uint32_t icbflags, addr_type;
100 	uint32_t len, lb_num;
101 	uint32_t flags;
102 	int part_num;
103 	int lb_size, eof, slot;
104 
105 	if ((udf_verbose & UDF_DEBUG_NODEDUMP) == 0)
106 		return;
107 
108 	lb_size = udf_rw32(udf_node->ump->logical_vol->lb_size);
109 
110 	fe  = udf_node->fe;
111 	efe = udf_node->efe;
112 	if (fe) {
113 		icbtag = &fe->icbtag;
114 		inflen = udf_rw64(fe->inf_len);
115 	} else {
116 		icbtag = &efe->icbtag;
117 		inflen = udf_rw64(efe->inf_len);
118 	}
119 
120 	icbflags   = udf_rw16(icbtag->flags);
121 	addr_type  = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
122 
123 	printf("udf_node_dump %p :\n", udf_node);
124 
125 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
126 		printf("\tIntern alloc, len = %"PRIu64"\n", inflen);
127 		return;
128 	}
129 
130 	printf("\tInflen  = %"PRIu64"\n", inflen);
131 	printf("\t\t");
132 
133 	slot = 0;
134 	for (;;) {
135 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
136 		if (eof)
137 			break;
138 		part_num = udf_rw16(s_ad.loc.part_num);
139 		lb_num = udf_rw32(s_ad.loc.lb_num);
140 		len   = udf_rw32(s_ad.len);
141 		flags = UDF_EXT_FLAGS(len);
142 		len   = UDF_EXT_LEN(len);
143 
144 		printf("[");
145 		if (part_num >= 0)
146 			printf("part %d, ", part_num);
147 		printf("lb_num %d, len %d", lb_num, len);
148 		if (flags)
149 			printf(", flags %d", flags>>30);
150 		printf("] ");
151 
152 		if (flags == UDF_EXT_REDIRECT) {
153 			printf("\n\textent END\n\tallocation extent\n\t\t");
154 		}
155 
156 		slot++;
157 	}
158 	printf("\n\tl_ad END\n\n");
159 }
160 #else
161 #define udf_node_dump(a)
162 #endif
163 
164 
165 static void
166 udf_assert_allocated(struct udf_mount *ump, uint16_t vpart_num,
167 	uint32_t lb_num, uint32_t num_lb)
168 {
169 	struct udf_bitmap *bitmap;
170 	struct part_desc *pdesc;
171 	uint32_t ptov;
172 	uint32_t bitval;
173 	uint8_t *bpos;
174 	int bit;
175 	int phys_part;
176 	int ok;
177 
178 	DPRINTF(PARANOIA, ("udf_assert_allocated: check virt lbnum %d "
179 			  "part %d + %d sect\n", lb_num, vpart_num, num_lb));
180 
181 	/* get partition backing up this vpart_num */
182 	pdesc = ump->partitions[ump->vtop[vpart_num]];
183 
184 	switch (ump->vtop_tp[vpart_num]) {
185 	case UDF_VTOP_TYPE_PHYS :
186 	case UDF_VTOP_TYPE_SPARABLE :
187 		/* free space to freed or unallocated space bitmap */
188 		ptov      = udf_rw32(pdesc->start_loc);
189 		phys_part = ump->vtop[vpart_num];
190 
191 		/* use unallocated bitmap */
192 		bitmap = &ump->part_unalloc_bits[phys_part];
193 
194 		/* if no bitmaps are defined, bail out */
195 		if (bitmap->bits == NULL)
196 			break;
197 
198 		/* check bits */
199 		KASSERT(bitmap->bits);
200 		ok = 1;
201 		bpos = bitmap->bits + lb_num/8;
202 		bit  = lb_num % 8;
203 		while (num_lb > 0) {
204 			bitval = (1 << bit);
205 			DPRINTF(PARANOIA, ("XXX : check %d, %p, bit %d\n",
206 				lb_num, bpos, bit));
207 			KASSERT(bitmap->bits + lb_num/8 == bpos);
208 			if (*bpos & bitval) {
209 				printf("\tlb_num %d is NOT marked busy\n",
210 					lb_num);
211 				ok = 0;
212 			}
213 			lb_num++; num_lb--;
214 			bit = (bit + 1) % 8;
215 			if (bit == 0)
216 				bpos++;
217 		}
218 		if (!ok) {
219 			/* KASSERT(0); */
220 		}
221 
222 		break;
223 	case UDF_VTOP_TYPE_VIRT :
224 		/* TODO check space */
225 		KASSERT(num_lb == 1);
226 		break;
227 	case UDF_VTOP_TYPE_META :
228 		/* TODO check space in the metadata bitmap */
229 	default:
230 		/* not implemented */
231 		break;
232 	}
233 }
234 
235 
236 static void
237 udf_node_sanity_check(struct udf_node *udf_node,
238 		uint64_t *cnt_inflen, uint64_t *cnt_logblksrec) {
239 	struct file_entry    *fe;
240 	struct extfile_entry *efe;
241 	struct icb_tag *icbtag;
242 	struct long_ad  s_ad;
243 	uint64_t inflen, logblksrec;
244 	uint32_t icbflags, addr_type;
245 	uint32_t len, lb_num, l_ea, l_ad, max_l_ad;
246 	uint16_t part_num;
247 	int dscr_size, lb_size, flags, whole_lb;
248 	int slot, eof;
249 
250 //	KASSERT(mutex_owned(&udf_node->ump->allocate_mutex));
251 
252 	if (1)
253 		udf_node_dump(udf_node);
254 
255 	lb_size = udf_rw32(udf_node->ump->logical_vol->lb_size);
256 
257 	fe  = udf_node->fe;
258 	efe = udf_node->efe;
259 	if (fe) {
260 		icbtag = &fe->icbtag;
261 		inflen = udf_rw64(fe->inf_len);
262 		dscr_size  = sizeof(struct file_entry) -1;
263 		logblksrec = udf_rw64(fe->logblks_rec);
264 		l_ad       = udf_rw32(fe->l_ad);
265 		l_ea       = udf_rw32(fe->l_ea);
266 	} else {
267 		icbtag = &efe->icbtag;
268 		inflen = udf_rw64(efe->inf_len);
269 		dscr_size  = sizeof(struct extfile_entry) -1;
270 		logblksrec = udf_rw64(efe->logblks_rec);
271 		l_ad       = udf_rw32(efe->l_ad);
272 		l_ea       = udf_rw32(efe->l_ea);
273 	}
274 	max_l_ad   = lb_size - dscr_size - l_ea;
275 	icbflags   = udf_rw16(icbtag->flags);
276 	addr_type  = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
277 
278 	/* reset counters */
279 	*cnt_inflen     = 0;
280 	*cnt_logblksrec = 0;
281 
282 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
283 		KASSERT(l_ad <= max_l_ad);
284 		KASSERT(l_ad == inflen);
285 		*cnt_inflen = inflen;
286 		return;
287 	}
288 
289 	/* start counting */
290 	whole_lb = 1;
291 	slot = 0;
292 	for (;;) {
293 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
294 		if (eof)
295 			break;
296 		KASSERT(whole_lb == 1);
297 
298 		part_num = udf_rw16(s_ad.loc.part_num);
299 		lb_num = udf_rw32(s_ad.loc.lb_num);
300 		len   = udf_rw32(s_ad.len);
301 		flags = UDF_EXT_FLAGS(len);
302 		len   = UDF_EXT_LEN(len);
303 
304 		if (flags != UDF_EXT_REDIRECT) {
305 			*cnt_inflen += len;
306 			if (flags == UDF_EXT_ALLOCATED) {
307 				*cnt_logblksrec += (len + lb_size -1) / lb_size;
308 			}
309 		} else {
310 			KASSERT(len == lb_size);
311 		}
312 		/* check allocation */
313 		if (flags == UDF_EXT_ALLOCATED)
314 			udf_assert_allocated(udf_node->ump, part_num, lb_num,
315 				(len + lb_size - 1) / lb_size);
316 
317 		/* check whole lb */
318 		whole_lb = ((len % lb_size) == 0);
319 
320 		slot++;
321 	}
322 	/* rest should be zero (ad_off > l_ad < max_l_ad - adlen) */
323 
324 	KASSERT(*cnt_inflen == inflen);
325 	KASSERT(*cnt_logblksrec == logblksrec);
326 
327 //	KASSERT(mutex_owned(&udf_node->ump->allocate_mutex));
328 }
329 #else
330 static void
331 udf_node_sanity_check(struct udf_node *udf_node,
332 		uint64_t *cnt_inflen, uint64_t *cnt_logblksrec) {
333 	struct file_entry    *fe;
334 	struct extfile_entry *efe;
335 	struct icb_tag *icbtag;
336 	uint64_t inflen, logblksrec;
337 	int dscr_size, lb_size;
338 
339 	lb_size = udf_rw32(udf_node->ump->logical_vol->lb_size);
340 
341 	fe  = udf_node->fe;
342 	efe = udf_node->efe;
343 	if (fe) {
344 		icbtag = &fe->icbtag;
345 		inflen = udf_rw64(fe->inf_len);
346 		dscr_size  = sizeof(struct file_entry) -1;
347 		logblksrec = udf_rw64(fe->logblks_rec);
348 	} else {
349 		icbtag = &efe->icbtag;
350 		inflen = udf_rw64(efe->inf_len);
351 		dscr_size  = sizeof(struct extfile_entry) -1;
352 		logblksrec = udf_rw64(efe->logblks_rec);
353 	}
354 	*cnt_logblksrec = logblksrec;
355 	*cnt_inflen     = inflen;
356 }
357 #endif
358 
359 /* --------------------------------------------------------------------- */
360 
361 int
362 udf_translate_vtop(struct udf_mount *ump, struct long_ad *icb_loc,
363 		   uint32_t *lb_numres, uint32_t *extres)
364 {
365 	struct part_desc       *pdesc;
366 	struct spare_map_entry *sme;
367 	struct long_ad s_icb_loc;
368 	uint64_t foffset, end_foffset;
369 	uint32_t lb_size, len;
370 	uint32_t lb_num, lb_rel, lb_packet;
371 	uint32_t udf_rw32_lbmap, ext_offset;
372 	uint16_t vpart;
373 	int rel, part, error, eof, slot, flags;
374 
375 	assert(ump && icb_loc && lb_numres);
376 
377 	vpart  = udf_rw16(icb_loc->loc.part_num);
378 	lb_num = udf_rw32(icb_loc->loc.lb_num);
379 	if (vpart > UDF_VTOP_RAWPART)
380 		return EINVAL;
381 
382 translate_again:
383 	part = ump->vtop[vpart];
384 	pdesc = ump->partitions[part];
385 
386 	switch (ump->vtop_tp[vpart]) {
387 	case UDF_VTOP_TYPE_RAW :
388 		/* 1:1 to the end of the device */
389 		*lb_numres = lb_num;
390 		*extres = INT_MAX;
391 		return 0;
392 	case UDF_VTOP_TYPE_PHYS :
393 		/* transform into its disc logical block */
394 		if (lb_num > udf_rw32(pdesc->part_len))
395 			return EINVAL;
396 		*lb_numres = lb_num + udf_rw32(pdesc->start_loc);
397 
398 		/* extent from here to the end of the partition */
399 		*extres = udf_rw32(pdesc->part_len) - lb_num;
400 		return 0;
401 	case UDF_VTOP_TYPE_VIRT :
402 		/* only maps one logical block, lookup in VAT */
403 		if (lb_num >= ump->vat_entries)		/* XXX > or >= ? */
404 			return EINVAL;
405 
406 		/* lookup in virtual allocation table file */
407 		mutex_enter(&ump->allocate_mutex);
408 		error = udf_vat_read(ump->vat_node,
409 				(uint8_t *) &udf_rw32_lbmap, 4,
410 				ump->vat_offset + lb_num * 4);
411 		mutex_exit(&ump->allocate_mutex);
412 
413 		if (error)
414 			return error;
415 
416 		lb_num = udf_rw32(udf_rw32_lbmap);
417 
418 		/* transform into its disc logical block */
419 		if (lb_num > udf_rw32(pdesc->part_len))
420 			return EINVAL;
421 		*lb_numres = lb_num + udf_rw32(pdesc->start_loc);
422 
423 		/* just one logical block */
424 		*extres = 1;
425 		return 0;
426 	case UDF_VTOP_TYPE_SPARABLE :
427 		/* check if the packet containing the lb_num is remapped */
428 		lb_packet = lb_num / ump->sparable_packet_size;
429 		lb_rel    = lb_num % ump->sparable_packet_size;
430 
431 		for (rel = 0; rel < udf_rw16(ump->sparing_table->rt_l); rel++) {
432 			sme = &ump->sparing_table->entries[rel];
433 			if (lb_packet == udf_rw32(sme->org)) {
434 				/* NOTE maps to absolute disc logical block! */
435 				*lb_numres = udf_rw32(sme->map) + lb_rel;
436 				*extres    = ump->sparable_packet_size - lb_rel;
437 				return 0;
438 			}
439 		}
440 
441 		/* transform into its disc logical block */
442 		if (lb_num > udf_rw32(pdesc->part_len))
443 			return EINVAL;
444 		*lb_numres = lb_num + udf_rw32(pdesc->start_loc);
445 
446 		/* rest of block */
447 		*extres = ump->sparable_packet_size - lb_rel;
448 		return 0;
449 	case UDF_VTOP_TYPE_META :
450 		/* we have to look into the file's allocation descriptors */
451 
452 		/* use metadatafile allocation mutex */
453 		lb_size = udf_rw32(ump->logical_vol->lb_size);
454 
455 		UDF_LOCK_NODE(ump->metadata_node, 0);
456 
457 		/* get first overlapping extent */
458 		foffset = 0;
459 		slot    = 0;
460 		for (;;) {
461 			udf_get_adslot(ump->metadata_node,
462 				slot, &s_icb_loc, &eof);
463 			DPRINTF(ADWLK, ("slot %d, eof = %d, flags = %d, "
464 				"len = %d, lb_num = %d, part = %d\n",
465 				slot, eof,
466 				UDF_EXT_FLAGS(udf_rw32(s_icb_loc.len)),
467 				UDF_EXT_LEN(udf_rw32(s_icb_loc.len)),
468 				udf_rw32(s_icb_loc.loc.lb_num),
469 				udf_rw16(s_icb_loc.loc.part_num)));
470 			if (eof) {
471 				DPRINTF(TRANSLATE,
472 					("Meta partition translation "
473 					 "failed: can't seek location\n"));
474 				UDF_UNLOCK_NODE(ump->metadata_node, 0);
475 				return EINVAL;
476 			}
477 			len   = udf_rw32(s_icb_loc.len);
478 			flags = UDF_EXT_FLAGS(len);
479 			len   = UDF_EXT_LEN(len);
480 
481 			if (flags == UDF_EXT_REDIRECT) {
482 				slot++;
483 				continue;
484 			}
485 
486 			end_foffset = foffset + len;
487 
488 			if (end_foffset > lb_num * lb_size)
489 				break;	/* found */
490 			foffset = end_foffset;
491 			slot++;
492 		}
493 		/* found overlapping slot */
494 		ext_offset = lb_num * lb_size - foffset;
495 
496 		/* process extent offset */
497 		lb_num   = udf_rw32(s_icb_loc.loc.lb_num);
498 		vpart    = udf_rw16(s_icb_loc.loc.part_num);
499 		lb_num  += (ext_offset + lb_size -1) / lb_size;
500 		len     -= ext_offset;
501 		ext_offset = 0;
502 
503 		flags = UDF_EXT_FLAGS(s_icb_loc.len);
504 
505 		UDF_UNLOCK_NODE(ump->metadata_node, 0);
506 		if (flags != UDF_EXT_ALLOCATED) {
507 			DPRINTF(TRANSLATE, ("Metadata partition translation "
508 					    "failed: not allocated\n"));
509 			return EINVAL;
510 		}
511 
512 		/*
513 		 * vpart and lb_num are updated, translate again since we
514 		 * might be mapped on sparable media
515 		 */
516 		goto translate_again;
517 	default:
518 		printf("UDF vtop translation scheme %d unimplemented yet\n",
519 			ump->vtop_tp[vpart]);
520 	}
521 
522 	return EINVAL;
523 }
524 
525 
526 /* XXX  provisional primitive braindead version */
527 /* TODO use ext_res */
528 void
529 udf_translate_vtop_list(struct udf_mount *ump, uint32_t sectors,
530 	uint16_t vpart_num, uint64_t *lmapping, uint64_t *pmapping)
531 {
532 	struct long_ad loc;
533 	uint32_t lb_numres, ext_res;
534 	int sector;
535 
536 	for (sector = 0; sector < sectors; sector++) {
537 		memset(&loc, 0, sizeof(struct long_ad));
538 		loc.loc.part_num = udf_rw16(vpart_num);
539 		loc.loc.lb_num   = udf_rw32(*lmapping);
540 		udf_translate_vtop(ump, &loc, &lb_numres, &ext_res);
541 		*pmapping = lb_numres;
542 		lmapping++; pmapping++;
543 	}
544 }
545 
546 
547 /* --------------------------------------------------------------------- */
548 
549 /*
550  * Translate an extent (in logical_blocks) into logical block numbers; used
551  * for read and write operations. DOESNT't check extents.
552  */
553 
554 int
555 udf_translate_file_extent(struct udf_node *udf_node,
556 		          uint32_t from, uint32_t num_lb,
557 			  uint64_t *map)
558 {
559 	struct udf_mount *ump;
560 	struct icb_tag *icbtag;
561 	struct long_ad t_ad, s_ad;
562 	uint64_t transsec;
563 	uint64_t foffset, end_foffset;
564 	uint32_t transsec32;
565 	uint32_t lb_size;
566 	uint32_t ext_offset;
567 	uint32_t lb_num, len;
568 	uint32_t overlap, translen;
569 	uint16_t vpart_num;
570 	int eof, error, flags;
571 	int slot, addr_type, icbflags;
572 
573 	if (!udf_node)
574 		return ENOENT;
575 
576 	KASSERT(num_lb > 0);
577 
578 	UDF_LOCK_NODE(udf_node, 0);
579 
580 	/* initialise derivative vars */
581 	ump = udf_node->ump;
582 	lb_size = udf_rw32(ump->logical_vol->lb_size);
583 
584 	if (udf_node->fe) {
585 		icbtag = &udf_node->fe->icbtag;
586 	} else {
587 		icbtag = &udf_node->efe->icbtag;
588 	}
589 	icbflags  = udf_rw16(icbtag->flags);
590 	addr_type = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
591 
592 	/* do the work */
593 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
594 		*map = UDF_TRANS_INTERN;
595 		UDF_UNLOCK_NODE(udf_node, 0);
596 		return 0;
597 	}
598 
599 	/* find first overlapping extent */
600 	foffset = 0;
601 	slot    = 0;
602 	for (;;) {
603 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
604 		DPRINTF(ADWLK, ("slot %d, eof = %d, flags = %d, len = %d, "
605 			"lb_num = %d, part = %d\n", slot, eof,
606 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)),
607 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
608 			udf_rw32(s_ad.loc.lb_num),
609 			udf_rw16(s_ad.loc.part_num)));
610 		if (eof) {
611 			DPRINTF(TRANSLATE,
612 				("Translate file extent "
613 				 "failed: can't seek location\n"));
614 			UDF_UNLOCK_NODE(udf_node, 0);
615 			return EINVAL;
616 		}
617 		len    = udf_rw32(s_ad.len);
618 		flags  = UDF_EXT_FLAGS(len);
619 		len    = UDF_EXT_LEN(len);
620 		lb_num = udf_rw32(s_ad.loc.lb_num);
621 
622 		if (flags == UDF_EXT_REDIRECT) {
623 			slot++;
624 			continue;
625 		}
626 
627 		end_foffset = foffset + len;
628 
629 		if (end_foffset > from * lb_size)
630 			break;	/* found */
631 		foffset = end_foffset;
632 		slot++;
633 	}
634 	/* found overlapping slot */
635 	ext_offset = from * lb_size - foffset;
636 
637 	for (;;) {
638 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
639 		DPRINTF(ADWLK, ("slot %d, eof = %d, flags = %d, len = %d, "
640 			"lb_num = %d, part = %d\n", slot, eof,
641 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)),
642 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
643 			udf_rw32(s_ad.loc.lb_num),
644 			udf_rw16(s_ad.loc.part_num)));
645 		if (eof) {
646 			DPRINTF(TRANSLATE,
647 				("Translate file extent "
648 				 "failed: past eof\n"));
649 			UDF_UNLOCK_NODE(udf_node, 0);
650 			return EINVAL;
651 		}
652 
653 		len    = udf_rw32(s_ad.len);
654 		flags  = UDF_EXT_FLAGS(len);
655 		len    = UDF_EXT_LEN(len);
656 
657 		lb_num    = udf_rw32(s_ad.loc.lb_num);
658 		vpart_num = udf_rw16(s_ad.loc.part_num);
659 
660 		end_foffset = foffset + len;
661 
662 		/* process extent, don't forget to advance on ext_offset! */
663 		lb_num  += (ext_offset + lb_size -1) / lb_size;
664 		overlap  = (len - ext_offset + lb_size -1) / lb_size;
665 		ext_offset = 0;
666 
667 		/*
668 		 * note that the while(){} is nessisary for the extent that
669 		 * the udf_translate_vtop() returns doens't have to span the
670 		 * whole extent.
671 		 */
672 
673 		overlap = MIN(overlap, num_lb);
674 		while (overlap && (flags != UDF_EXT_REDIRECT)) {
675 			switch (flags) {
676 			case UDF_EXT_FREE :
677 			case UDF_EXT_ALLOCATED_BUT_NOT_USED :
678 				transsec = UDF_TRANS_ZERO;
679 				translen = overlap;
680 				while (overlap && num_lb && translen) {
681 					*map++ = transsec;
682 					lb_num++;
683 					overlap--; num_lb--; translen--;
684 				}
685 				break;
686 			case UDF_EXT_ALLOCATED :
687 				t_ad.loc.lb_num   = udf_rw32(lb_num);
688 				t_ad.loc.part_num = udf_rw16(vpart_num);
689 				error = udf_translate_vtop(ump,
690 						&t_ad, &transsec32, &translen);
691 				transsec = transsec32;
692 				if (error) {
693 					UDF_UNLOCK_NODE(udf_node, 0);
694 					return error;
695 				}
696 				while (overlap && num_lb && translen) {
697 					*map++ = transsec;
698 					lb_num++; transsec++;
699 					overlap--; num_lb--; translen--;
700 				}
701 				break;
702 			default:
703 				DPRINTF(TRANSLATE,
704 					("Translate file extent "
705 					 "failed: bad flags %x\n", flags));
706 				UDF_UNLOCK_NODE(udf_node, 0);
707 				return EINVAL;
708 			}
709 		}
710 		if (num_lb == 0)
711 			break;
712 
713 		if (flags != UDF_EXT_REDIRECT)
714 			foffset = end_foffset;
715 		slot++;
716 	}
717 	UDF_UNLOCK_NODE(udf_node, 0);
718 
719 	return 0;
720 }
721 
722 /* --------------------------------------------------------------------- */
723 
724 static int
725 udf_search_free_vatloc(struct udf_mount *ump, uint32_t *lbnumres)
726 {
727 	uint32_t lb_size, lb_num, lb_map, udf_rw32_lbmap;
728 	uint8_t *blob;
729 	int entry, chunk, found, error;
730 
731 	KASSERT(ump);
732 	KASSERT(ump->logical_vol);
733 
734 	lb_size = udf_rw32(ump->logical_vol->lb_size);
735 	blob = malloc(lb_size, M_UDFTEMP, M_WAITOK);
736 
737 	/* TODO static allocation of search chunk */
738 
739 	lb_num = MIN(ump->vat_entries, ump->vat_last_free_lb);
740 	found  = 0;
741 	error  = 0;
742 	entry  = 0;
743 	do {
744 		chunk = MIN(lb_size, (ump->vat_entries - lb_num) * 4);
745 		if (chunk <= 0)
746 			break;
747 		/* load in chunk */
748 		error = udf_vat_read(ump->vat_node, blob, chunk,
749 				ump->vat_offset + lb_num * 4);
750 
751 		if (error)
752 			break;
753 
754 		/* search this chunk */
755 		for (entry=0; entry < chunk /4; entry++, lb_num++) {
756 			udf_rw32_lbmap = *((uint32_t *) (blob + entry * 4));
757 			lb_map = udf_rw32(udf_rw32_lbmap);
758 			if (lb_map == 0xffffffff) {
759 				found = 1;
760 				break;
761 			}
762 		}
763 	} while (!found);
764 	if (error) {
765 		printf("udf_search_free_vatloc: error reading in vat chunk "
766 			"(lb %d, size %d)\n", lb_num, chunk);
767 	}
768 
769 	if (!found) {
770 		/* extend VAT */
771 		DPRINTF(WRITE, ("udf_search_free_vatloc: extending\n"));
772 		lb_num = ump->vat_entries;
773 		ump->vat_entries++;
774 	}
775 
776 	/* mark entry with initialiser just in case */
777 	lb_map = udf_rw32(0xfffffffe);
778 	udf_vat_write(ump->vat_node, (uint8_t *) &lb_map, 4,
779 		ump->vat_offset + lb_num *4);
780 	ump->vat_last_free_lb = lb_num;
781 
782 	free(blob, M_UDFTEMP);
783 	*lbnumres = lb_num;
784 	return 0;
785 }
786 
787 
788 static void
789 udf_bitmap_allocate(struct udf_bitmap *bitmap, int ismetadata,
790 	uint32_t *num_lb, uint64_t *lmappos)
791 {
792 	uint32_t offset, lb_num, bit;
793 	int32_t  diff;
794 	uint8_t *bpos;
795 	int pass;
796 
797 	if (!ismetadata) {
798 		/* heuristic to keep the two pointers not too close */
799 		diff = bitmap->data_pos - bitmap->metadata_pos;
800 		if ((diff >= 0) && (diff < 1024))
801 			bitmap->data_pos = bitmap->metadata_pos + 1024;
802 	}
803 	offset = ismetadata ? bitmap->metadata_pos : bitmap->data_pos;
804 	offset &= ~7;
805 	for (pass = 0; pass < 2; pass++) {
806 		if (offset >= bitmap->max_offset)
807 			offset = 0;
808 
809 		while (offset < bitmap->max_offset) {
810 			if (*num_lb == 0)
811 				break;
812 
813 			/* use first bit not set */
814 			bpos  = bitmap->bits + offset/8;
815 			bit = ffs(*bpos);	/* returns 0 or 1..8 */
816 			if (bit == 0) {
817 				offset += 8;
818 				continue;
819 			}
820 			DPRINTF(PARANOIA, ("XXX : allocate %d, %p, bit %d\n",
821 				offset + bit -1, bpos, bit-1));
822 			*bpos &= ~(1 << (bit-1));
823 			lb_num = offset + bit-1;
824 			*lmappos++ = lb_num;
825 			*num_lb = *num_lb - 1;
826 			// offset = (offset & ~7);
827 		}
828 	}
829 
830 	if (ismetadata) {
831 		bitmap->metadata_pos = offset;
832 	} else {
833 		bitmap->data_pos = offset;
834 	}
835 }
836 
837 
838 static void
839 udf_bitmap_free(struct udf_bitmap *bitmap, uint32_t lb_num, uint32_t num_lb)
840 {
841 	uint32_t offset;
842 	uint32_t bit, bitval;
843 	uint8_t *bpos;
844 
845 	offset = lb_num;
846 
847 	/* starter bits */
848 	bpos = bitmap->bits + offset/8;
849 	bit = offset % 8;
850 	while ((bit != 0) && (num_lb > 0)) {
851 		bitval = (1 << bit);
852 		KASSERT((*bpos & bitval) == 0);
853 		DPRINTF(PARANOIA, ("XXX : free %d, %p, %d\n",
854 			offset, bpos, bit));
855 		*bpos |= bitval;
856 		offset++; num_lb--;
857 		bit = (bit + 1) % 8;
858 	}
859 	if (num_lb == 0)
860 		return;
861 
862 	/* whole bytes */
863 	KASSERT(bit == 0);
864 	bpos = bitmap->bits + offset / 8;
865 	while (num_lb >= 8) {
866 		KASSERT((*bpos == 0));
867 		DPRINTF(PARANOIA, ("XXX : free %d + 8, %p\n", offset, bpos));
868 		*bpos = 255;
869 		offset += 8; num_lb -= 8;
870 		bpos++;
871 	}
872 
873 	/* stop bits */
874 	KASSERT(num_lb < 8);
875 	bit = 0;
876 	while (num_lb > 0) {
877 		bitval = (1 << bit);
878 		KASSERT((*bpos & bitval) == 0);
879 		DPRINTF(PARANOIA, ("XXX : free %d, %p, %d\n",
880 			offset, bpos, bit));
881 		*bpos |= bitval;
882 		offset++; num_lb--;
883 		bit = (bit + 1) % 8;
884 	}
885 }
886 
887 
888 /* allocate a contiguous sequence of sectornumbers */
889 static int
890 udf_allocate_space(struct udf_mount *ump, int ismetadata, int alloc_type,
891 	int num_lb, uint16_t *alloc_partp,
892 	uint64_t *lmapping)
893 {
894 	struct mmc_trackinfo *alloc_track, *other_track;
895 	struct udf_bitmap *bitmap;
896 	struct part_desc *pdesc;
897 	struct logvol_int_desc *lvid;
898 	uint64_t *lmappos;
899 	uint32_t ptov, lb_num, *freepos, free_lbs;
900 	int lb_size, alloc_num_lb;
901 	int alloc_part;
902 	int error;
903 
904 	mutex_enter(&ump->allocate_mutex);
905 
906 	lb_size = udf_rw32(ump->logical_vol->lb_size);
907 	KASSERT(lb_size == ump->discinfo.sector_size);
908 
909 	if (ismetadata) {
910 		alloc_part  = ump->metadata_part;
911 		alloc_track = &ump->metadata_track;
912 		other_track = &ump->data_track;
913 	} else {
914 		alloc_part  = ump->data_part;
915 		alloc_track = &ump->data_track;
916 		other_track = &ump->metadata_track;
917 	}
918 	*alloc_partp = alloc_part;
919 
920 	/* XXX check disc space */
921 
922 	lmappos = lmapping;
923 	error = 0;
924 	switch (alloc_type) {
925 	case UDF_ALLOC_VAT :
926 		/* search empty slot in VAT file */
927 		KASSERT(num_lb == 1);
928 		error = udf_search_free_vatloc(ump, &lb_num);
929 		if (!error)
930 			*lmappos = lb_num;
931 		break;
932 	case UDF_ALLOC_SEQUENTIAL :
933 		/* sequential allocation on recordable media */
934 		/* get partition backing up this vpart_num */
935 		pdesc = ump->partitions[ump->vtop[alloc_part]];
936 
937 		/* calculate offset from physical base partition */
938 		ptov  = udf_rw32(pdesc->start_loc);
939 
940 		for (lb_num = 0; lb_num < num_lb; lb_num++) {
941 			*lmappos++ = alloc_track->next_writable - ptov;
942 			alloc_track->next_writable++;
943 			alloc_track->free_blocks--;
944 		}
945 		if (alloc_track->tracknr == other_track->tracknr)
946 			memcpy(other_track, alloc_track,
947 				sizeof(struct mmc_trackinfo));
948 		break;
949 	case UDF_ALLOC_SPACEMAP :
950 		/* try to allocate on unallocated bits */
951 		alloc_num_lb = num_lb;
952 		bitmap = &ump->part_unalloc_bits[alloc_part];
953 		udf_bitmap_allocate(bitmap, ismetadata, &alloc_num_lb, lmappos);
954 		ump->lvclose |= UDF_WRITE_PART_BITMAPS;
955 
956 		/* have we allocated all? */
957 		if (alloc_num_lb) {
958 			/* TODO convert freed to unalloc and try again */
959 			/* free allocated piece for now */
960 			lmappos = lmapping;
961 			for (lb_num=0; lb_num < num_lb-alloc_num_lb; lb_num++) {
962 				udf_bitmap_free(bitmap, *lmappos++, 1);
963 			}
964 			error = ENOSPC;
965 		}
966 		if (!error) {
967 			/* adjust freecount */
968 			lvid = ump->logvol_integrity;
969 			freepos = &lvid->tables[0] + alloc_part;
970 			free_lbs = udf_rw32(*freepos);
971 			*freepos = udf_rw32(free_lbs - num_lb);
972 		}
973 		break;
974 	case UDF_ALLOC_METABITMAP :		/* UDF 2.50, 2.60 BluRay-RE */
975 		/* allocate on metadata unallocated bits */
976 		alloc_num_lb = num_lb;
977 		bitmap = &ump->metadata_unalloc_bits;
978 		udf_bitmap_allocate(bitmap, ismetadata, &num_lb, lmappos);
979 		ump->lvclose |= UDF_WRITE_PART_BITMAPS;
980 
981 		/* have we allocated all? */
982 		if (num_lb) {
983 			/* YIKES! TODO we need to extend the metadata partition */
984 			/* free allocated piece for now */
985 			lmappos = lmapping;
986 			for (lb_num=0; lb_num < num_lb-alloc_num_lb; lb_num++) {
987 				udf_bitmap_free(bitmap, *lmappos++, 1);
988 			}
989 			error = ENOSPC;
990 		}
991 		if (!error) {
992 			/* adjust freecount */
993 			lvid = ump->logvol_integrity;
994 			freepos = &lvid->tables[0] + alloc_part;
995 			free_lbs = udf_rw32(*freepos);
996 			*freepos = udf_rw32(free_lbs - num_lb);
997 		}
998 		break;
999 	case UDF_ALLOC_METASEQUENTIAL :		/* UDF 2.60       BluRay-R  */
1000 	case UDF_ALLOC_RELAXEDSEQUENTIAL :	/* UDF 2.50/~meta BluRay-R  */
1001 		printf("ALERT: udf_allocate_space : allocation %d "
1002 				"not implemented yet!\n", alloc_type);
1003 		/* TODO implement, doesn't have to be contiguous */
1004 		error = ENOSPC;
1005 		break;
1006 	}
1007 
1008 #ifdef DEBUG
1009 	if (udf_verbose & UDF_DEBUG_ALLOC) {
1010 		lmappos = lmapping;
1011 		printf("udf_allocate_space, allocated logical lba :\n");
1012 		for (lb_num = 0; lb_num < num_lb; lb_num++) {
1013 			printf("%s %"PRIu64",", (lb_num > 0)?",":"",
1014 				*lmappos++);
1015 		}
1016 		printf("\n");
1017 	}
1018 #endif
1019 	mutex_exit(&ump->allocate_mutex);
1020 
1021 	return error;
1022 }
1023 
1024 /* --------------------------------------------------------------------- */
1025 
1026 void
1027 udf_free_allocated_space(struct udf_mount *ump, uint32_t lb_num,
1028 	uint16_t vpart_num, uint32_t num_lb)
1029 {
1030 	struct udf_bitmap *bitmap;
1031 	struct part_desc *pdesc;
1032 	struct logvol_int_desc *lvid;
1033 	uint32_t ptov, lb_map, udf_rw32_lbmap;
1034 	uint32_t *freepos, free_lbs;
1035 	int phys_part;
1036 	int error;
1037 
1038 	DPRINTF(ALLOC, ("udf_free_allocated_space: freeing virt lbnum %d "
1039 			  "part %d + %d sect\n", lb_num, vpart_num, num_lb));
1040 
1041 	/* no use freeing zero length */
1042 	if (num_lb == 0)
1043 		return;
1044 
1045 	mutex_enter(&ump->allocate_mutex);
1046 
1047 	/* get partition backing up this vpart_num */
1048 	pdesc = ump->partitions[ump->vtop[vpart_num]];
1049 
1050 	switch (ump->vtop_tp[vpart_num]) {
1051 	case UDF_VTOP_TYPE_PHYS :
1052 	case UDF_VTOP_TYPE_SPARABLE :
1053 		/* free space to freed or unallocated space bitmap */
1054 		ptov      = udf_rw32(pdesc->start_loc);
1055 		phys_part = ump->vtop[vpart_num];
1056 
1057 		/* first try freed space bitmap */
1058 		bitmap    = &ump->part_freed_bits[phys_part];
1059 
1060 		/* if not defined, use unallocated bitmap */
1061 		if (bitmap->bits == NULL)
1062 			bitmap = &ump->part_unalloc_bits[phys_part];
1063 
1064 		/* if no bitmaps are defined, bail out */
1065 		if (bitmap->bits == NULL)
1066 			break;
1067 
1068 		/* free bits if its defined */
1069 		KASSERT(bitmap->bits);
1070 		ump->lvclose |= UDF_WRITE_PART_BITMAPS;
1071 		udf_bitmap_free(bitmap, lb_num, num_lb);
1072 
1073 		/* adjust freecount */
1074 		lvid = ump->logvol_integrity;
1075 		freepos = &lvid->tables[0] + vpart_num;
1076 		free_lbs = udf_rw32(*freepos);
1077 		*freepos = udf_rw32(free_lbs + num_lb);
1078 		break;
1079 	case UDF_VTOP_TYPE_VIRT :
1080 		/* free this VAT entry */
1081 		KASSERT(num_lb == 1);
1082 
1083 		lb_map = 0xffffffff;
1084 		udf_rw32_lbmap = udf_rw32(lb_map);
1085 		error = udf_vat_write(ump->vat_node,
1086 			(uint8_t *) &udf_rw32_lbmap, 4,
1087 			ump->vat_offset + lb_num * 4);
1088 		KASSERT(error == 0);
1089 		ump->vat_last_free_lb = MIN(ump->vat_last_free_lb, lb_num);
1090 		break;
1091 	case UDF_VTOP_TYPE_META :
1092 		/* free space in the metadata bitmap */
1093 	default:
1094 		printf("ALERT: udf_free_allocated_space : allocation %d "
1095 			"not implemented yet!\n", ump->vtop_tp[vpart_num]);
1096 		break;
1097 	}
1098 
1099 	mutex_exit(&ump->allocate_mutex);
1100 }
1101 
1102 /* --------------------------------------------------------------------- */
1103 
1104 int
1105 udf_pre_allocate_space(struct udf_mount *ump, int udf_c_type, int num_lb,
1106 	uint16_t *alloc_partp, uint64_t *lmapping)
1107 {
1108 	int ismetadata, alloc_type;
1109 
1110 	ismetadata = (udf_c_type == UDF_C_NODE);
1111 	alloc_type = ismetadata? ump->meta_alloc : ump->data_alloc;
1112 
1113 #ifdef DIAGNOSTIC
1114 	if ((alloc_type == UDF_ALLOC_VAT) && (udf_c_type != UDF_C_NODE)) {
1115 		panic("udf_pre_allocate_space: bad c_type on VAT!\n");
1116 	}
1117 #endif
1118 
1119 	/* reserve size for VAT allocated data */
1120 	if (alloc_type == UDF_ALLOC_VAT) {
1121 		mutex_enter(&ump->allocate_mutex);
1122 			ump->uncomitted_lb += num_lb;
1123 		mutex_exit(&ump->allocate_mutex);
1124 	}
1125 
1126 	return udf_allocate_space(ump, ismetadata, alloc_type,
1127 		num_lb, alloc_partp, lmapping);
1128 }
1129 
1130 /* --------------------------------------------------------------------- */
1131 
1132 /*
1133  * Allocate a buf on disc for direct write out. The space doesn't have to be
1134  * contiguous as the caller takes care of this.
1135  */
1136 
1137 void
1138 udf_late_allocate_buf(struct udf_mount *ump, struct buf *buf,
1139 	uint64_t *lmapping, struct long_ad *node_ad_cpy, uint16_t *vpart_num)
1140 {
1141 	struct udf_node  *udf_node = VTOI(buf->b_vp);
1142 	int lb_size, blks, udf_c_type;
1143 	int ismetadata, alloc_type;
1144 	int num_lb;
1145 	int error, s;
1146 
1147 	/*
1148 	 * for each sector in the buf, allocate a sector on disc and record
1149 	 * its position in the provided mapping array.
1150 	 *
1151 	 * If its userdata or FIDs, record its location in its node.
1152 	 */
1153 
1154 	lb_size    = udf_rw32(ump->logical_vol->lb_size);
1155 	num_lb     = (buf->b_bcount + lb_size -1) / lb_size;
1156 	blks       = lb_size / DEV_BSIZE;
1157 	udf_c_type = buf->b_udf_c_type;
1158 
1159 	KASSERT(lb_size == ump->discinfo.sector_size);
1160 
1161 	ismetadata = (udf_c_type == UDF_C_NODE);
1162 	alloc_type = ismetadata? ump->meta_alloc : ump->data_alloc;
1163 
1164 #ifdef DIAGNOSTIC
1165 	if ((alloc_type == UDF_ALLOC_VAT) && (udf_c_type != UDF_C_NODE)) {
1166 		panic("udf_late_allocate_buf: bad c_type on VAT!\n");
1167 	}
1168 #endif
1169 
1170 	if (udf_c_type == UDF_C_NODE) {
1171 		/* if not VAT, its allready allocated */
1172 		if (alloc_type != UDF_ALLOC_VAT)
1173 			return;
1174 
1175 		/* allocate sequential */
1176 		alloc_type = UDF_ALLOC_SEQUENTIAL;
1177 	}
1178 
1179 	/* returns vpart_num on wich the allocation was done */
1180 	error = udf_allocate_space(ump, ismetadata, alloc_type,
1181 			num_lb, vpart_num, lmapping);
1182 	if (error) {
1183 		/* ARGH! we've not done our accounting right! */
1184 		panic("UDF disc allocation accounting gone wrong");
1185 	}
1186 
1187 	/* commit our sector count */
1188 	mutex_enter(&ump->allocate_mutex);
1189 		if (num_lb > ump->uncomitted_lb) {
1190 			ump->uncomitted_lb = 0;
1191 		} else {
1192 			ump->uncomitted_lb -= num_lb;
1193 		}
1194 	mutex_exit(&ump->allocate_mutex);
1195 
1196 	/* If its userdata or FIDs, record its allocation in its node. */
1197 	if ((udf_c_type == UDF_C_USERDATA) ||
1198 	    (udf_c_type == UDF_C_FIDS) ||
1199 	    (udf_c_type == UDF_C_METADATA_SBM))
1200 	{
1201 		udf_record_allocation_in_node(ump, buf, *vpart_num, lmapping,
1202 			node_ad_cpy);
1203 		/* decrement our outstanding bufs counter */
1204 		s = splbio();
1205 			udf_node->outstanding_bufs--;
1206 		splx(s);
1207 	}
1208 }
1209 
1210 /* --------------------------------------------------------------------- */
1211 
1212 /*
1213  * Try to merge a1 with the new piece a2. udf_ads_merge returns error when not
1214  * possible (anymore); a2 returns the rest piece.
1215  */
1216 
1217 static int
1218 udf_ads_merge(uint32_t lb_size, struct long_ad *a1, struct long_ad *a2)
1219 {
1220 	uint32_t max_len, merge_len;
1221 	uint32_t a1_len, a2_len;
1222 	uint32_t a1_flags, a2_flags;
1223 	uint32_t a1_lbnum, a2_lbnum;
1224 	uint16_t a1_part, a2_part;
1225 
1226 	max_len = ((UDF_EXT_MAXLEN / lb_size) * lb_size);
1227 
1228 	a1_flags = UDF_EXT_FLAGS(udf_rw32(a1->len));
1229 	a1_len   = UDF_EXT_LEN(udf_rw32(a1->len));
1230 	a1_lbnum = udf_rw32(a1->loc.lb_num);
1231 	a1_part  = udf_rw16(a1->loc.part_num);
1232 
1233 	a2_flags = UDF_EXT_FLAGS(udf_rw32(a2->len));
1234 	a2_len   = UDF_EXT_LEN(udf_rw32(a2->len));
1235 	a2_lbnum = udf_rw32(a2->loc.lb_num);
1236 	a2_part  = udf_rw16(a2->loc.part_num);
1237 
1238 	/* defines same space */
1239 	if (a1_flags != a2_flags)
1240 		return 1;
1241 
1242 	if (a1_flags != UDF_EXT_FREE) {
1243 		/* the same partition */
1244 		if (a1_part != a2_part)
1245 			return 1;
1246 
1247 		/* a2 is successor of a1 */
1248 		if (a1_lbnum * lb_size + a1_len != a2_lbnum * lb_size)
1249 			return 1;
1250 	}
1251 
1252 	/* merge as most from a2 if possible */
1253 	merge_len = MIN(a2_len, max_len - a1_len);
1254 	a1_len   += merge_len;
1255 	a2_len   -= merge_len;
1256 	a2_lbnum += merge_len/lb_size;
1257 
1258 	a1->len = udf_rw32(a1_len | a1_flags);
1259 	a2->len = udf_rw32(a2_len | a2_flags);
1260 	a2->loc.lb_num = udf_rw32(a2_lbnum);
1261 
1262 	if (a2_len > 0)
1263 		return 1;
1264 
1265 	/* there is space over to merge */
1266 	return 0;
1267 }
1268 
1269 /* --------------------------------------------------------------------- */
1270 
1271 static void
1272 udf_wipe_adslots(struct udf_node *udf_node)
1273 {
1274 	struct file_entry      *fe;
1275 	struct extfile_entry   *efe;
1276 	struct alloc_ext_entry *ext;
1277 	uint64_t inflen, objsize;
1278 	uint32_t lb_size, dscr_size, l_ea, l_ad, max_l_ad, crclen;
1279 	uint8_t *data_pos;
1280 	int extnr;
1281 
1282 	lb_size = udf_rw32(udf_node->ump->logical_vol->lb_size);
1283 
1284 	fe  = udf_node->fe;
1285 	efe = udf_node->efe;
1286 	if (fe) {
1287 		inflen  = udf_rw64(fe->inf_len);
1288 		objsize = inflen;
1289 		dscr_size  = sizeof(struct file_entry) -1;
1290 		l_ea       = udf_rw32(fe->l_ea);
1291 		l_ad       = udf_rw32(fe->l_ad);
1292 		data_pos = (uint8_t *) fe + dscr_size + l_ea;
1293 	} else {
1294 		inflen  = udf_rw64(efe->inf_len);
1295 		objsize = udf_rw64(efe->obj_size);
1296 		dscr_size  = sizeof(struct extfile_entry) -1;
1297 		l_ea       = udf_rw32(efe->l_ea);
1298 		l_ad       = udf_rw32(efe->l_ad);
1299 		data_pos = (uint8_t *) efe + dscr_size + l_ea;
1300 	}
1301 	max_l_ad = lb_size - dscr_size - l_ea;
1302 
1303 	/* wipe fe/efe */
1304 	memset(data_pos, 0, max_l_ad);
1305 	crclen = dscr_size - UDF_DESC_TAG_LENGTH + l_ea;
1306 	if (fe) {
1307 		fe->l_ad         = udf_rw32(0);
1308 		fe->logblks_rec  = udf_rw64(0);
1309 		fe->tag.desc_crc_len = udf_rw32(crclen);
1310 	} else {
1311 		efe->l_ad        = udf_rw32(0);
1312 		efe->logblks_rec = udf_rw64(0);
1313 		efe->tag.desc_crc_len = udf_rw32(crclen);
1314 	}
1315 
1316 	/* wipe all allocation extent entries */
1317 	for (extnr = 0; extnr < udf_node->num_extensions; extnr++) {
1318 		ext = udf_node->ext[extnr];
1319 		dscr_size  = sizeof(struct alloc_ext_entry) -1;
1320 		data_pos = (uint8_t *) ext->data;
1321 		max_l_ad = lb_size - dscr_size;
1322 		memset(data_pos, 0, max_l_ad);
1323 		ext->l_ad = udf_rw32(0);
1324 
1325 		crclen = dscr_size - UDF_DESC_TAG_LENGTH;
1326 		ext->tag.desc_crc_len = udf_rw32(crclen);
1327 	}
1328 	udf_node->i_flags |= IN_NODE_REBUILD;
1329 }
1330 
1331 /* --------------------------------------------------------------------- */
1332 
1333 void
1334 udf_get_adslot(struct udf_node *udf_node, int slot, struct long_ad *icb,
1335 	int *eof) {
1336 	struct file_entry      *fe;
1337 	struct extfile_entry   *efe;
1338 	struct alloc_ext_entry *ext;
1339 	struct icb_tag *icbtag;
1340 	struct short_ad *short_ad;
1341 	struct long_ad *long_ad, l_icb;
1342 	uint32_t offset;
1343 	uint32_t lb_size, dscr_size, l_ea, l_ad, flags;
1344 	uint8_t *data_pos;
1345 	int icbflags, addr_type, adlen, extnr;
1346 
1347 	/* determine what descriptor we are in */
1348 	lb_size = udf_rw32(udf_node->ump->logical_vol->lb_size);
1349 
1350 	fe  = udf_node->fe;
1351 	efe = udf_node->efe;
1352 	if (fe) {
1353 		icbtag  = &fe->icbtag;
1354 		dscr_size  = sizeof(struct file_entry) -1;
1355 		l_ea       = udf_rw32(fe->l_ea);
1356 		l_ad       = udf_rw32(fe->l_ad);
1357 		data_pos = (uint8_t *) fe + dscr_size + l_ea;
1358 	} else {
1359 		icbtag  = &efe->icbtag;
1360 		dscr_size  = sizeof(struct extfile_entry) -1;
1361 		l_ea       = udf_rw32(efe->l_ea);
1362 		l_ad       = udf_rw32(efe->l_ad);
1363 		data_pos = (uint8_t *) efe + dscr_size + l_ea;
1364 	}
1365 
1366 	icbflags  = udf_rw16(icbtag->flags);
1367 	addr_type = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
1368 
1369 	/* just in case we're called on an intern, its EOF */
1370 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
1371 		memset(icb, 0, sizeof(struct long_ad));
1372 		*eof = 1;
1373 		return;
1374 	}
1375 
1376 	adlen = 0;
1377 	if (addr_type == UDF_ICB_SHORT_ALLOC) {
1378 		adlen = sizeof(struct short_ad);
1379 	} else if (addr_type == UDF_ICB_LONG_ALLOC) {
1380 		adlen = sizeof(struct long_ad);
1381 	}
1382 
1383 	/* if offset too big, we go to the allocation extensions */
1384 	offset = slot * adlen;
1385 	extnr  = -1;
1386 	while (offset >= l_ad) {
1387 		/* check if our last entry is a redirect */
1388 		if (addr_type == UDF_ICB_SHORT_ALLOC) {
1389 			short_ad = (struct short_ad *) (data_pos + l_ad-adlen);
1390 			l_icb.len          = short_ad->len;
1391 			l_icb.loc.part_num = udf_node->loc.loc.part_num;
1392 			l_icb.loc.lb_num   = short_ad->lb_num;
1393 		} else {
1394 			KASSERT(addr_type == UDF_ICB_LONG_ALLOC);
1395 			long_ad = (struct long_ad *) (data_pos + l_ad-adlen);
1396 			l_icb = *long_ad;
1397 		}
1398 		flags = UDF_EXT_FLAGS(udf_rw32(l_icb.len));
1399 		if (flags != UDF_EXT_REDIRECT) {
1400 			l_ad = 0;	/* force EOF */
1401 			break;
1402 		}
1403 
1404 		/* advance to next extent */
1405 		extnr++;
1406 		if (extnr >= udf_node->num_extensions) {
1407 			l_ad = 0;	/* force EOF */
1408 			break;
1409 		}
1410 		offset = offset - l_ad;
1411 		ext  = udf_node->ext[extnr];
1412 		dscr_size  = sizeof(struct alloc_ext_entry) -1;
1413 		l_ad = udf_rw32(ext->l_ad);
1414 		data_pos = (uint8_t *) ext + dscr_size;
1415 	}
1416 
1417 	/* XXX l_ad == 0 should be enough to check */
1418 	*eof = (offset >= l_ad) || (l_ad == 0);
1419 	if (*eof) {
1420 		DPRINTF(PARANOIDADWLK, ("returning EOF, extnr %d, offset %d, "
1421 			"l_ad %d\n", extnr, offset, l_ad));
1422 		memset(icb, 0, sizeof(struct long_ad));
1423 		return;
1424 	}
1425 
1426 	/* get the element */
1427 	if (addr_type == UDF_ICB_SHORT_ALLOC) {
1428 		short_ad = (struct short_ad *) (data_pos + offset);
1429 		icb->len          = short_ad->len;
1430 		icb->loc.part_num = udf_node->loc.loc.part_num;
1431 		icb->loc.lb_num   = short_ad->lb_num;
1432 	} else if (addr_type == UDF_ICB_LONG_ALLOC) {
1433 		long_ad = (struct long_ad *) (data_pos + offset);
1434 		*icb = *long_ad;
1435 	}
1436 	DPRINTF(PARANOIDADWLK, ("returning element : v %d, lb %d, len %d, "
1437 		"flags %d\n", icb->loc.part_num, icb->loc.lb_num,
1438 		UDF_EXT_LEN(icb->len), UDF_EXT_FLAGS(icb->len)));
1439 }
1440 
1441 /* --------------------------------------------------------------------- */
1442 
1443 int
1444 udf_append_adslot(struct udf_node *udf_node, int *slot, struct long_ad *icb) {
1445 	struct udf_mount *ump = udf_node->ump;
1446 	union dscrptr          *dscr, *extdscr;
1447 	struct file_entry      *fe;
1448 	struct extfile_entry   *efe;
1449 	struct alloc_ext_entry *ext;
1450 	struct icb_tag *icbtag;
1451 	struct short_ad *short_ad;
1452 	struct long_ad *long_ad, o_icb, l_icb;
1453 	uint64_t logblks_rec, *logblks_rec_p;
1454 	uint64_t lmapping;
1455 	uint32_t offset, rest, len, lb_num;
1456 	uint32_t lb_size, dscr_size, l_ea, l_ad, *l_ad_p, max_l_ad, crclen;
1457 	uint32_t flags;
1458 	uint16_t vpart_num;
1459 	uint8_t *data_pos;
1460 	int icbflags, addr_type, adlen, extnr;
1461 	int error;
1462 
1463 	/* determine what descriptor we are in */
1464 	lb_size = udf_rw32(ump->logical_vol->lb_size);
1465 
1466 	fe  = udf_node->fe;
1467 	efe = udf_node->efe;
1468 	if (fe) {
1469 		icbtag  = &fe->icbtag;
1470 		dscr      = (union dscrptr *) fe;
1471 		dscr_size = sizeof(struct file_entry) -1;
1472 
1473 		l_ea      = udf_rw32(fe->l_ea);
1474 		l_ad_p    = &fe->l_ad;
1475 		logblks_rec_p = &fe->logblks_rec;
1476 	} else {
1477 		icbtag    = &efe->icbtag;
1478 		dscr      = (union dscrptr *) efe;
1479 		dscr_size = sizeof(struct extfile_entry) -1;
1480 
1481 		l_ea      = udf_rw32(efe->l_ea);
1482 		l_ad_p    = &efe->l_ad;
1483 		logblks_rec_p = &efe->logblks_rec;
1484 	}
1485 	data_pos  = (uint8_t *) dscr + dscr_size + l_ea;
1486 	max_l_ad = lb_size - dscr_size - l_ea;
1487 
1488 	icbflags  = udf_rw16(icbtag->flags);
1489 	addr_type = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
1490 
1491 	/* just in case we're called on an intern, its EOF */
1492 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
1493 		panic("udf_append_adslot on UDF_ICB_INTERN_ALLOC\n");
1494 	}
1495 
1496 	adlen = 0;
1497 	if (addr_type == UDF_ICB_SHORT_ALLOC) {
1498 		adlen = sizeof(struct short_ad);
1499 	} else if (addr_type == UDF_ICB_LONG_ALLOC) {
1500 		adlen = sizeof(struct long_ad);
1501 	}
1502 
1503 	/* clean up given long_ad */
1504 #ifdef DIAGNOSTIC
1505 	flags = UDF_EXT_FLAGS(udf_rw32(icb->len));
1506 	if (flags == UDF_EXT_FREE) {
1507 		if ((udf_rw16(icb->loc.part_num) != 0) ||
1508 		    (udf_rw32(icb->loc.lb_num) != 0))
1509 			printf("UDF: warning, cleaning long_ad marked free\n");
1510 		icb->loc.part_num = udf_rw16(0);
1511 		icb->loc.lb_num   = udf_rw32(0);
1512 	}
1513 #endif
1514 
1515 	/* if offset too big, we go to the allocation extensions */
1516 	l_ad   = udf_rw32(*l_ad_p);
1517 	offset = (*slot) * adlen;
1518 	extnr  = -1;
1519 	while (offset >= l_ad) {
1520 		/* check if our last entry is a redirect */
1521 		if (addr_type == UDF_ICB_SHORT_ALLOC) {
1522 			short_ad = (struct short_ad *) (data_pos + l_ad-adlen);
1523 			l_icb.len          = short_ad->len;
1524 			l_icb.loc.part_num = udf_node->loc.loc.part_num;
1525 			l_icb.loc.lb_num   = short_ad->lb_num;
1526 		} else {
1527 			KASSERT(addr_type == UDF_ICB_LONG_ALLOC);
1528 			long_ad = (struct long_ad *) (data_pos + l_ad-adlen);
1529 			l_icb = *long_ad;
1530 		}
1531 		flags = UDF_EXT_FLAGS(udf_rw32(l_icb.len));
1532 		if (flags != UDF_EXT_REDIRECT) {
1533 			/* only one past the last one is adressable */
1534 			break;
1535 		}
1536 
1537 		/* advance to next extent */
1538 		extnr++;
1539 		KASSERT(extnr < udf_node->num_extensions);
1540 		offset = offset - l_ad;
1541 
1542 		ext  = udf_node->ext[extnr];
1543 		dscr = (union dscrptr *) ext;
1544 		dscr_size  = sizeof(struct alloc_ext_entry) -1;
1545 		max_l_ad = lb_size - dscr_size;
1546 		l_ad_p = &ext->l_ad;
1547 		l_ad   = udf_rw32(*l_ad_p);
1548 		data_pos = (uint8_t *) ext + dscr_size;
1549 	}
1550 	DPRINTF(PARANOIDADWLK, ("append, ext %d, offset %d, l_ad %d\n",
1551 		extnr, offset, udf_rw32(*l_ad_p)));
1552 	KASSERT(l_ad == udf_rw32(*l_ad_p));
1553 
1554 	/* offset is offset within the current (E)FE/AED */
1555 	l_ad   = udf_rw32(*l_ad_p);
1556 	crclen = udf_rw32(dscr->tag.desc_crc_len);
1557 	logblks_rec = udf_rw64(*logblks_rec_p);
1558 
1559 	/* overwriting old piece? */
1560 	if (offset < l_ad) {
1561 		/* overwrite entry; compensate for the old element */
1562 		if (addr_type == UDF_ICB_SHORT_ALLOC) {
1563 			short_ad = (struct short_ad *) (data_pos + offset);
1564 			o_icb.len          = short_ad->len;
1565 			o_icb.loc.part_num = udf_rw16(0);	/* ignore */
1566 			o_icb.loc.lb_num   = short_ad->lb_num;
1567 		} else if (addr_type == UDF_ICB_LONG_ALLOC) {
1568 			long_ad = (struct long_ad *) (data_pos + offset);
1569 			o_icb = *long_ad;
1570 		} else {
1571 			panic("Invalid address type in udf_append_adslot\n");
1572 		}
1573 
1574 		len = udf_rw32(o_icb.len);
1575 		if (UDF_EXT_FLAGS(len) == UDF_EXT_ALLOCATED) {
1576 			/* adjust counts */
1577 			len = UDF_EXT_LEN(len);
1578 			logblks_rec -= (len + lb_size -1) / lb_size;
1579 		}
1580 	}
1581 
1582 	/* check if we're not appending a redirection */
1583 	flags = UDF_EXT_FLAGS(udf_rw32(icb->len));
1584 	KASSERT(flags != UDF_EXT_REDIRECT);
1585 
1586 	/* round down available space */
1587 	rest = adlen * ((max_l_ad - offset) / adlen);
1588 	if (rest <= adlen) {
1589 		/* have to append aed, see if we already have a spare one */
1590 		extnr++;
1591 		ext = udf_node->ext[extnr];
1592 		l_icb = udf_node->ext_loc[extnr];
1593 		if (ext == NULL) {
1594 			DPRINTF(ALLOC,("adding allocation extent %d\n", extnr));
1595 			error = udf_pre_allocate_space(ump, UDF_C_NODE, 1,
1596 					&vpart_num, &lmapping);
1597 			lb_num = lmapping;
1598 			if (error)
1599 				return error;
1600 
1601 			/* initialise pointer to location */
1602 			memset(&l_icb, 0, sizeof(struct long_ad));
1603 			l_icb.len = udf_rw32(lb_size | UDF_EXT_REDIRECT);
1604 			l_icb.loc.lb_num   = udf_rw32(lb_num);
1605 			l_icb.loc.part_num = udf_rw16(vpart_num);
1606 
1607 			/* create new aed descriptor */
1608 			udf_create_logvol_dscr(ump, udf_node, &l_icb, &extdscr);
1609 			ext = &extdscr->aee;
1610 
1611 			udf_inittag(ump, &ext->tag, TAGID_ALLOCEXTENT, lb_num);
1612 			dscr_size  = sizeof(struct alloc_ext_entry) -1;
1613 			max_l_ad = lb_size - dscr_size;
1614 			memset(ext->data, 0, max_l_ad);
1615 			ext->l_ad = udf_rw32(0);
1616 			ext->tag.desc_crc_len =
1617 				udf_rw32(dscr_size - UDF_DESC_TAG_LENGTH);
1618 
1619 			/* declare aed */
1620 			udf_node->num_extensions++;
1621 			udf_node->ext_loc[extnr] = l_icb;
1622 			udf_node->ext[extnr] = ext;
1623 		}
1624 		/* add redirect and adjust l_ad and crclen for old descr */
1625 		if (addr_type == UDF_ICB_SHORT_ALLOC) {
1626 			short_ad = (struct short_ad *) (data_pos + offset);
1627 			short_ad->len    = l_icb.len;
1628 			short_ad->lb_num = l_icb.loc.lb_num;
1629 		} else if (addr_type == UDF_ICB_LONG_ALLOC) {
1630 			long_ad = (struct long_ad *) (data_pos + offset);
1631 			*long_ad = l_icb;
1632 		}
1633 		l_ad   += adlen;
1634 		crclen += adlen;
1635 		dscr->tag.desc_crc_len = udf_rw32(crclen);
1636 		*l_ad_p = udf_rw32(l_ad);
1637 
1638 		/* advance to the new extension */
1639 		KASSERT(ext != NULL);
1640 		dscr = (union dscrptr *) ext;
1641 		dscr_size  = sizeof(struct alloc_ext_entry) -1;
1642 		max_l_ad = lb_size - dscr_size;
1643 		data_pos = (uint8_t *) dscr + dscr_size;
1644 
1645 		l_ad_p = &ext->l_ad;
1646 		l_ad   = udf_rw32(*l_ad_p);
1647 		crclen = udf_rw32(dscr->tag.desc_crc_len);
1648 		offset = 0;
1649 
1650 		/* adjust callees slot count for link insert */
1651 		*slot += 1;
1652 	}
1653 
1654 	/* write out the element */
1655 	DPRINTF(PARANOIDADWLK, ("adding element : %p : v %d, lb %d, "
1656 			"len %d, flags %d\n", data_pos + offset,
1657 			icb->loc.part_num, icb->loc.lb_num,
1658 			UDF_EXT_LEN(icb->len), UDF_EXT_FLAGS(icb->len)));
1659 	if (addr_type == UDF_ICB_SHORT_ALLOC) {
1660 		short_ad = (struct short_ad *) (data_pos + offset);
1661 		short_ad->len    = icb->len;
1662 		short_ad->lb_num = icb->loc.lb_num;
1663 	} else if (addr_type == UDF_ICB_LONG_ALLOC) {
1664 		long_ad = (struct long_ad *) (data_pos + offset);
1665 		*long_ad = *icb;
1666 	}
1667 
1668 	/* adjust logblks recorded count */
1669 	flags = UDF_EXT_FLAGS(udf_rw32(icb->len));
1670 	if (flags == UDF_EXT_ALLOCATED)
1671 		logblks_rec += (UDF_EXT_LEN(icb->len) + lb_size -1) / lb_size;
1672 	*logblks_rec_p = udf_rw64(logblks_rec);
1673 
1674 	/* adjust l_ad and crclen when needed */
1675 	if (offset >= l_ad) {
1676 		l_ad   += adlen;
1677 		crclen += adlen;
1678 		dscr->tag.desc_crc_len = udf_rw32(crclen);
1679 		*l_ad_p = udf_rw32(l_ad);
1680 	}
1681 
1682 	return 0;
1683 }
1684 
1685 /* --------------------------------------------------------------------- */
1686 
1687 static void
1688 udf_count_alloc_exts(struct udf_node *udf_node)
1689 {
1690 	struct long_ad s_ad;
1691 	uint32_t lb_num, len, flags;
1692 	uint16_t vpart_num;
1693 	int slot, eof;
1694 	int num_extents, extnr;
1695 	int lb_size;
1696 
1697 	if (udf_node->num_extensions == 0)
1698 		return;
1699 
1700 	lb_size = udf_rw32(udf_node->ump->logical_vol->lb_size);
1701 	/* count number of allocation extents in use */
1702 	num_extents = 0;
1703 	slot = 0;
1704 	for (;;) {
1705 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
1706 		if (eof)
1707 			break;
1708 		len   = udf_rw32(s_ad.len);
1709 		flags = UDF_EXT_FLAGS(len);
1710 
1711 		if (flags == UDF_EXT_REDIRECT)
1712 			num_extents++;
1713 
1714 		slot++;
1715 	}
1716 
1717 	DPRINTF(ALLOC, ("udf_count_alloc_ext counted %d live extents\n",
1718 		num_extents));
1719 
1720 	/* XXX choice: we could delay freeing them on node writeout */
1721 	/* free excess entries */
1722 	extnr = num_extents;
1723 	for (;extnr < udf_node->num_extensions; extnr++) {
1724 		DPRINTF(ALLOC, ("freeing alloc ext %d\n", extnr));
1725 		/* free dscriptor */
1726 		s_ad = udf_node->ext_loc[extnr];
1727 		udf_free_logvol_dscr(udf_node->ump, &s_ad,
1728 			udf_node->ext[extnr]);
1729 		udf_node->ext[extnr] = NULL;
1730 
1731 		/* free disc space */
1732 		lb_num    = udf_rw32(s_ad.loc.lb_num);
1733 		vpart_num = udf_rw16(s_ad.loc.part_num);
1734 		udf_free_allocated_space(udf_node->ump, lb_num, vpart_num, 1);
1735 
1736 		memset(&udf_node->ext_loc[extnr], 0, sizeof(struct long_ad));
1737 	}
1738 
1739 	/* set our new number of allocation extents */
1740 	udf_node->num_extensions = num_extents;
1741 }
1742 
1743 
1744 /* --------------------------------------------------------------------- */
1745 
1746 /*
1747  * Adjust the node's allocation descriptors to reflect the new mapping; do
1748  * take note that we might glue to existing allocation descriptors.
1749  *
1750  * XXX Note there can only be one allocation being recorded/mount; maybe
1751  * explicit allocation in shedule thread?
1752  */
1753 
1754 static void
1755 udf_record_allocation_in_node(struct udf_mount *ump, struct buf *buf,
1756 	uint16_t vpart_num, uint64_t *mapping, struct long_ad *node_ad_cpy)
1757 {
1758 	struct vnode    *vp = buf->b_vp;
1759 	struct udf_node *udf_node = VTOI(vp);
1760 	struct file_entry      *fe;
1761 	struct extfile_entry   *efe;
1762 	struct icb_tag  *icbtag;
1763 	struct long_ad   s_ad, c_ad;
1764 	uint64_t inflen, from, till;
1765 	uint64_t foffset, end_foffset, restart_foffset;
1766 	uint64_t orig_inflen, orig_lbrec, new_inflen, new_lbrec;
1767 	uint32_t num_lb, len, flags, lb_num;
1768 	uint32_t run_start;
1769 	uint32_t slot_offset, replace_len, replace;
1770 	int addr_type, icbflags;
1771 //	int udf_c_type = buf->b_udf_c_type;
1772 	int lb_size, run_length, eof;
1773 	int slot, cpy_slot, cpy_slots, restart_slot;
1774 	int error;
1775 
1776 	DPRINTF(ALLOC, ("udf_record_allocation_in_node\n"));
1777 
1778 #if 0
1779 	/* XXX disable sanity check for now */
1780 	/* sanity check ... should be panic ? */
1781 	if ((udf_c_type != UDF_C_USERDATA) && (udf_c_type != UDF_C_FIDS))
1782 		return;
1783 #endif
1784 
1785 	lb_size = udf_rw32(udf_node->ump->logical_vol->lb_size);
1786 
1787 	/* do the job */
1788 	UDF_LOCK_NODE(udf_node, 0);	/* XXX can deadlock ? */
1789 	udf_node_sanity_check(udf_node, &orig_inflen, &orig_lbrec);
1790 
1791 	fe  = udf_node->fe;
1792 	efe = udf_node->efe;
1793 	if (fe) {
1794 		icbtag = &fe->icbtag;
1795 		inflen = udf_rw64(fe->inf_len);
1796 	} else {
1797 		icbtag = &efe->icbtag;
1798 		inflen = udf_rw64(efe->inf_len);
1799 	}
1800 
1801 	/* do check if `till' is not past file information length */
1802 	from = buf->b_lblkno * lb_size;
1803 	till = MIN(inflen, from + buf->b_resid);
1804 
1805 	num_lb = (till - from + lb_size -1) / lb_size;
1806 
1807 	DPRINTF(ALLOC, ("record allocation from %"PRIu64" + %d\n", from, buf->b_bcount));
1808 
1809 	icbflags  = udf_rw16(icbtag->flags);
1810 	addr_type = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
1811 
1812 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
1813 		/* nothing to do */
1814 		/* XXX clean up rest of node? just in case? */
1815 		UDF_UNLOCK_NODE(udf_node, 0);
1816 		return;
1817 	}
1818 
1819 	slot     = 0;
1820 	cpy_slot = 0;
1821 	foffset  = 0;
1822 
1823 	/* 1) copy till first overlap piece to the rewrite buffer */
1824 	for (;;) {
1825 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
1826 		if (eof) {
1827 			DPRINTF(WRITE,
1828 				("Record allocation in node "
1829 				 "failed: encountered EOF\n"));
1830 			UDF_UNLOCK_NODE(udf_node, 0);
1831 			buf->b_error = EINVAL;
1832 			return;
1833 		}
1834 		len   = udf_rw32(s_ad.len);
1835 		flags = UDF_EXT_FLAGS(len);
1836 		len   = UDF_EXT_LEN(len);
1837 
1838 		if (flags == UDF_EXT_REDIRECT) {
1839 			slot++;
1840 			continue;
1841 		}
1842 
1843 		end_foffset = foffset + len;
1844 		if (end_foffset > from)
1845 			break;	/* found */
1846 
1847 		node_ad_cpy[cpy_slot++] = s_ad;
1848 
1849 		DPRINTF(ALLOC, ("\t1: vp %d, lb %d, len %d, flags %d "
1850 			"-> stack\n",
1851 			udf_rw16(s_ad.loc.part_num),
1852 			udf_rw32(s_ad.loc.lb_num),
1853 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
1854 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
1855 
1856 		foffset = end_foffset;
1857 		slot++;
1858 	}
1859 	restart_slot    = slot;
1860 	restart_foffset = foffset;
1861 
1862 	/* 2) trunc overlapping slot at overlap and copy it */
1863 	slot_offset = from - foffset;
1864 	if (slot_offset > 0) {
1865 		DPRINTF(ALLOC, ("\tslot_offset = %d, flags = %d (%d)\n",
1866 				slot_offset, flags >> 30, flags));
1867 
1868 		s_ad.len = udf_rw32(slot_offset | flags);
1869 		node_ad_cpy[cpy_slot++] = s_ad;
1870 
1871 		DPRINTF(ALLOC, ("\t2: vp %d, lb %d, len %d, flags %d "
1872 			"-> stack\n",
1873 			udf_rw16(s_ad.loc.part_num),
1874 			udf_rw32(s_ad.loc.lb_num),
1875 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
1876 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
1877 	}
1878 	foffset += slot_offset;
1879 
1880 	/* 3) insert new mappings */
1881 	memset(&s_ad, 0, sizeof(struct long_ad));
1882 	lb_num = 0;
1883 	for (lb_num = 0; lb_num < num_lb; lb_num++) {
1884 		run_start  = mapping[lb_num];
1885 		run_length = 1;
1886 		while (lb_num < num_lb-1) {
1887 			if (mapping[lb_num+1] != mapping[lb_num]+1)
1888 				if (mapping[lb_num+1] != mapping[lb_num])
1889 					break;
1890 			run_length++;
1891 			lb_num++;
1892 		}
1893 		/* insert slot for this mapping */
1894 		len = run_length * lb_size;
1895 
1896 		/* bounds checking */
1897 		if (foffset + len > till)
1898 			len = till - foffset;
1899 		KASSERT(foffset + len <= inflen);
1900 
1901 		s_ad.len = udf_rw32(len | UDF_EXT_ALLOCATED);
1902 		s_ad.loc.part_num = udf_rw16(vpart_num);
1903 		s_ad.loc.lb_num   = udf_rw32(run_start);
1904 
1905 		foffset += len;
1906 
1907 		/* paranoia */
1908 		if (len == 0) {
1909 			DPRINTF(WRITE,
1910 				("Record allocation in node "
1911 				 "failed: insert failed\n"));
1912 			UDF_UNLOCK_NODE(udf_node, 0);
1913 			buf->b_error = EINVAL;
1914 			return;
1915 		}
1916 		node_ad_cpy[cpy_slot++] = s_ad;
1917 
1918 		DPRINTF(ALLOC, ("\t3: insert new mapping vp %d lb %d, len %d, "
1919 				"flags %d -> stack\n",
1920 			udf_rw16(s_ad.loc.part_num), udf_rw32(s_ad.loc.lb_num),
1921 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
1922 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
1923 	}
1924 
1925 	/* 4) pop replaced length */
1926 	slot    = restart_slot;
1927 	foffset = restart_foffset;
1928 
1929 	replace_len = till - foffset;	/* total amount of bytes to pop */
1930 	slot_offset = from - foffset;	/* offset in first encounted slot */
1931 	KASSERT((slot_offset % lb_size) == 0);
1932 
1933 	for (;;) {
1934 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
1935 		if (eof)
1936 			break;
1937 
1938 		len    = udf_rw32(s_ad.len);
1939 		flags  = UDF_EXT_FLAGS(len);
1940 		len    = UDF_EXT_LEN(len);
1941 		lb_num = udf_rw32(s_ad.loc.lb_num);
1942 
1943 		if (flags == UDF_EXT_REDIRECT) {
1944 			slot++;
1945 			continue;
1946 		}
1947 
1948 		DPRINTF(ALLOC, ("\t4i: got slot %d, slot_offset %d, "
1949 				"replace_len %d, "
1950 				"vp %d, lb %d, len %d, flags %d\n",
1951 			slot, slot_offset, replace_len,
1952 			udf_rw16(s_ad.loc.part_num),
1953 			udf_rw32(s_ad.loc.lb_num),
1954 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
1955 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
1956 
1957 		/* adjust for slot offset */
1958 		if (slot_offset) {
1959 			DPRINTF(ALLOC, ("\t4s: skipping %d\n", slot_offset));
1960 			lb_num += slot_offset / lb_size;
1961 			len    -= slot_offset;
1962 			foffset += slot_offset;
1963 			replace_len -= slot_offset;
1964 
1965 			/* mark adjusted */
1966 			slot_offset = 0;
1967 		}
1968 
1969 		/* advance for (the rest of) this slot */
1970 		replace = MIN(len, replace_len);
1971 		DPRINTF(ALLOC, ("\t4d: replacing %d\n", replace));
1972 
1973 		/* advance for this slot */
1974 		if (replace) {
1975 			/* note: dont round DOWN on num_lb since we then
1976 			 * forget the last partial one */
1977 			num_lb = (replace + lb_size - 1) / lb_size;
1978 			if (flags != UDF_EXT_FREE) {
1979 				udf_free_allocated_space(ump, lb_num,
1980 					udf_rw16(s_ad.loc.part_num), num_lb);
1981 			}
1982 			lb_num      += num_lb;
1983 			len         -= replace;
1984 			foffset     += replace;
1985 			replace_len -= replace;
1986 		}
1987 
1988 		/* do we have a slot tail ? */
1989 		if (len) {
1990 			KASSERT(foffset % lb_size == 0);
1991 
1992 			/* we arrived at our point, push remainder */
1993 			s_ad.len        = udf_rw32(len | flags);
1994 			s_ad.loc.lb_num = udf_rw32(lb_num);
1995 			if (flags == UDF_EXT_FREE)
1996 				s_ad.loc.lb_num = udf_rw32(0);
1997 			node_ad_cpy[cpy_slot++] = s_ad;
1998 			foffset += len;
1999 			slot++;
2000 
2001 			DPRINTF(ALLOC, ("\t4: vp %d, lb %d, len %d, flags %d "
2002 				"-> stack\n",
2003 				udf_rw16(s_ad.loc.part_num),
2004 				udf_rw32(s_ad.loc.lb_num),
2005 				UDF_EXT_LEN(udf_rw32(s_ad.len)),
2006 				UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2007 			break;
2008 		}
2009 
2010 		slot++;
2011 	}
2012 
2013 	/* 5) copy remainder */
2014 	for (;;) {
2015 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
2016 		if (eof)
2017 			break;
2018 
2019 		len   = udf_rw32(s_ad.len);
2020 		flags = UDF_EXT_FLAGS(len);
2021 		len   = UDF_EXT_LEN(len);
2022 
2023 		if (flags == UDF_EXT_REDIRECT) {
2024 			slot++;
2025 			continue;
2026 		}
2027 
2028 		node_ad_cpy[cpy_slot++] = s_ad;
2029 
2030 		DPRINTF(ALLOC, ("\t5: insert new mapping "
2031 			"vp %d lb %d, len %d, flags %d "
2032 			"-> stack\n",
2033 		udf_rw16(s_ad.loc.part_num),
2034 		udf_rw32(s_ad.loc.lb_num),
2035 		UDF_EXT_LEN(udf_rw32(s_ad.len)),
2036 		UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2037 
2038 		slot++;
2039 	}
2040 
2041 	/* 6) reset node descriptors */
2042 	udf_wipe_adslots(udf_node);
2043 
2044 	/* 7) copy back extents; merge when possible. Recounting on the fly */
2045 	cpy_slots = cpy_slot;
2046 
2047 	c_ad = node_ad_cpy[0];
2048 	slot = 0;
2049 	DPRINTF(ALLOC, ("\t7s: stack -> got mapping vp %d "
2050 		"lb %d, len %d, flags %d\n",
2051 	udf_rw16(c_ad.loc.part_num),
2052 	udf_rw32(c_ad.loc.lb_num),
2053 	UDF_EXT_LEN(udf_rw32(c_ad.len)),
2054 	UDF_EXT_FLAGS(udf_rw32(c_ad.len)) >> 30));
2055 
2056 	for (cpy_slot = 1; cpy_slot < cpy_slots; cpy_slot++) {
2057 		s_ad = node_ad_cpy[cpy_slot];
2058 
2059 		DPRINTF(ALLOC, ("\t7i: stack -> got mapping vp %d "
2060 			"lb %d, len %d, flags %d\n",
2061 		udf_rw16(s_ad.loc.part_num),
2062 		udf_rw32(s_ad.loc.lb_num),
2063 		UDF_EXT_LEN(udf_rw32(s_ad.len)),
2064 		UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2065 
2066 		/* see if we can merge */
2067 		if (udf_ads_merge(lb_size, &c_ad, &s_ad)) {
2068 			/* not mergable (anymore) */
2069 			DPRINTF(ALLOC, ("\t7: appending vp %d lb %d, "
2070 				"len %d, flags %d\n",
2071 			udf_rw16(c_ad.loc.part_num),
2072 			udf_rw32(c_ad.loc.lb_num),
2073 			UDF_EXT_LEN(udf_rw32(c_ad.len)),
2074 			UDF_EXT_FLAGS(udf_rw32(c_ad.len)) >> 30));
2075 
2076 			error = udf_append_adslot(udf_node, &slot, &c_ad);
2077 			if (error) {
2078 				buf->b_error = error;
2079 				goto out;
2080 			}
2081 			c_ad = s_ad;
2082 			slot++;
2083 		}
2084 	}
2085 
2086 	/* 8) push rest slot (if any) */
2087 	if (UDF_EXT_LEN(c_ad.len) > 0) {
2088 		DPRINTF(ALLOC, ("\t8: last append vp %d lb %d, "
2089 				"len %d, flags %d\n",
2090 		udf_rw16(c_ad.loc.part_num),
2091 		udf_rw32(c_ad.loc.lb_num),
2092 		UDF_EXT_LEN(udf_rw32(c_ad.len)),
2093 		UDF_EXT_FLAGS(udf_rw32(c_ad.len)) >> 30));
2094 
2095 		error = udf_append_adslot(udf_node, &slot, &c_ad);
2096 		if (error) {
2097 			buf->b_error = error;
2098 			goto out;
2099 		}
2100 	}
2101 
2102 out:
2103 	udf_count_alloc_exts(udf_node);
2104 
2105 	/* the node's descriptors should now be sane */
2106 	udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
2107 	UDF_UNLOCK_NODE(udf_node, 0);
2108 
2109 	KASSERT(orig_inflen == new_inflen);
2110 	KASSERT(new_lbrec >= orig_lbrec);
2111 
2112 	return;
2113 }
2114 
2115 /* --------------------------------------------------------------------- */
2116 
2117 int
2118 udf_grow_node(struct udf_node *udf_node, uint64_t new_size)
2119 {
2120 	union dscrptr *dscr;
2121 	struct vnode *vp = udf_node->vnode;
2122 	struct udf_mount *ump = udf_node->ump;
2123 	struct file_entry    *fe;
2124 	struct extfile_entry *efe;
2125 	struct icb_tag  *icbtag;
2126 	struct long_ad c_ad, s_ad;
2127 	uint64_t size_diff, old_size, inflen, objsize, chunk, append_len;
2128 	uint64_t foffset, end_foffset;
2129 	uint64_t orig_inflen, orig_lbrec, new_inflen, new_lbrec;
2130 	uint32_t lb_size, dscr_size, crclen, lastblock_grow;
2131 	uint32_t len, flags, max_len;
2132 	uint32_t max_l_ad, l_ad, l_ea;
2133 	uint8_t *data_pos, *evacuated_data;
2134 	int icbflags, addr_type;
2135 	int slot, cpy_slot;
2136 	int isdir, eof, error;
2137 
2138 	DPRINTF(ALLOC, ("udf_grow_node\n"));
2139 
2140 	UDF_LOCK_NODE(udf_node, 0);
2141 	udf_node_sanity_check(udf_node, &orig_inflen, &orig_lbrec);
2142 
2143 	lb_size = udf_rw32(ump->logical_vol->lb_size);
2144 	max_len = ((UDF_EXT_MAXLEN / lb_size) * lb_size);
2145 
2146 	fe  = udf_node->fe;
2147 	efe = udf_node->efe;
2148 	if (fe) {
2149 		dscr       = (union dscrptr *) fe;
2150 		icbtag  = &fe->icbtag;
2151 		inflen  = udf_rw64(fe->inf_len);
2152 		objsize = inflen;
2153 		dscr_size  = sizeof(struct file_entry) -1;
2154 		l_ea       = udf_rw32(fe->l_ea);
2155 		l_ad       = udf_rw32(fe->l_ad);
2156 	} else {
2157 		dscr       = (union dscrptr *) efe;
2158 		icbtag  = &efe->icbtag;
2159 		inflen  = udf_rw64(efe->inf_len);
2160 		objsize = udf_rw64(efe->obj_size);
2161 		dscr_size  = sizeof(struct extfile_entry) -1;
2162 		l_ea       = udf_rw32(efe->l_ea);
2163 		l_ad       = udf_rw32(efe->l_ad);
2164 	}
2165 	data_pos  = (uint8_t *) dscr + dscr_size + l_ea;
2166 	max_l_ad = lb_size - dscr_size - l_ea;
2167 
2168 	icbflags   = udf_rw16(icbtag->flags);
2169 	addr_type  = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
2170 
2171 	old_size  = inflen;
2172 	size_diff = new_size - old_size;
2173 
2174 	DPRINTF(ALLOC, ("\tfrom %"PRIu64" to %"PRIu64"\n", old_size, new_size));
2175 
2176 	evacuated_data = NULL;
2177 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
2178 		if (l_ad + size_diff <= max_l_ad) {
2179 			/* only reflect size change directly in the node */
2180 			inflen  += size_diff;
2181 			objsize += size_diff;
2182 			l_ad    += size_diff;
2183 			crclen = dscr_size - UDF_DESC_TAG_LENGTH + l_ea + l_ad;
2184 			if (fe) {
2185 				fe->inf_len   = udf_rw64(inflen);
2186 				fe->l_ad      = udf_rw32(l_ad);
2187 				fe->tag.desc_crc_len = udf_rw32(crclen);
2188 			} else {
2189 				efe->inf_len  = udf_rw64(inflen);
2190 				efe->obj_size = udf_rw64(objsize);
2191 				efe->l_ad     = udf_rw32(l_ad);
2192 				efe->tag.desc_crc_len = udf_rw32(crclen);
2193 			}
2194 			error = 0;
2195 
2196 			/* set new size for uvm */
2197 			uvm_vnp_setsize(vp, old_size);
2198 			uvm_vnp_setwritesize(vp, new_size);
2199 
2200 #if 0
2201 			/* zero append space in buffer */
2202 			uvm_vnp_zerorange(vp, old_size, new_size - old_size);
2203 #endif
2204 
2205 			udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
2206 
2207 			/* unlock */
2208 			UDF_UNLOCK_NODE(udf_node, 0);
2209 
2210 			KASSERT(new_inflen == orig_inflen + size_diff);
2211 			KASSERT(new_lbrec == orig_lbrec);
2212 			KASSERT(new_lbrec == 0);
2213 			return 0;
2214 		}
2215 
2216 		DPRINTF(ALLOC, ("\tCONVERT from internal\n"));
2217 
2218 		if (old_size > 0) {
2219 			/* allocate some space and copy in the stuff to keep */
2220 			evacuated_data = malloc(lb_size, M_UDFTEMP, M_WAITOK);
2221 			memset(evacuated_data, 0, lb_size);
2222 
2223 			/* node is locked, so safe to exit mutex */
2224 			UDF_UNLOCK_NODE(udf_node, 0);
2225 
2226 			/* read in using the `normal' vn_rdwr() */
2227 			error = vn_rdwr(UIO_READ, udf_node->vnode,
2228 					evacuated_data, old_size, 0,
2229 					UIO_SYSSPACE, IO_ALTSEMANTICS | IO_NODELOCKED,
2230 					FSCRED, NULL, NULL);
2231 
2232 			/* enter again */
2233 			UDF_LOCK_NODE(udf_node, 0);
2234 		}
2235 
2236 		/* convert to a normal alloc and select type */
2237 		isdir = (vp->v_type == VDIR);
2238 
2239 		icbflags &= ~UDF_ICB_TAG_FLAGS_ALLOC_MASK;
2240 		icbflags |=  isdir ? ump->meta_allocdscr : ump->data_allocdscr;
2241 		icbtag->flags = udf_rw16(icbflags);
2242 
2243 		/* wipe old descriptor space */
2244 		udf_wipe_adslots(udf_node);
2245 
2246 		memset(&c_ad, 0, sizeof(struct long_ad));
2247 		c_ad.len          = udf_rw32(old_size | UDF_EXT_FREE);
2248 		c_ad.loc.part_num = udf_rw16(0); /* not relevant */
2249 		c_ad.loc.lb_num   = udf_rw32(0); /* not relevant */
2250 
2251 		slot = 0;
2252 	} else {
2253 		/* goto the last entry (if any) */
2254 		slot     = 0;
2255 		cpy_slot = 0;
2256 		foffset  = 0;
2257 		memset(&c_ad, 0, sizeof(struct long_ad));
2258 		for (;;) {
2259 			udf_get_adslot(udf_node, slot, &c_ad, &eof);
2260 			if (eof)
2261 				break;
2262 
2263 			len   = udf_rw32(c_ad.len);
2264 			flags = UDF_EXT_FLAGS(len);
2265 			len   = UDF_EXT_LEN(len);
2266 
2267 			end_foffset = foffset + len;
2268 			if (flags != UDF_EXT_REDIRECT)
2269 				foffset = end_foffset;
2270 
2271 			slot++;
2272 		}
2273 		/* at end of adslots */
2274 
2275 		/* special case if the old size was zero, then there is no last slot */
2276 		if (old_size == 0) {
2277 			c_ad.len          = udf_rw32(0 | UDF_EXT_FREE);
2278 			c_ad.loc.part_num = udf_rw16(0); /* not relevant */
2279 			c_ad.loc.lb_num   = udf_rw32(0); /* not relevant */
2280 		} else {
2281 			/* refetch last slot */
2282 			slot--;
2283 			udf_get_adslot(udf_node, slot, &c_ad, &eof);
2284 		}
2285 	}
2286 
2287 	/*
2288 	 * If the length of the last slot is not a multiple of lb_size, adjust
2289 	 * length so that it is; don't forget to adjust `append_len'! relevant for
2290 	 * extending existing files
2291 	 */
2292 	len   = udf_rw32(c_ad.len);
2293 	flags = UDF_EXT_FLAGS(len);
2294 	len   = UDF_EXT_LEN(len);
2295 
2296 	lastblock_grow = 0;
2297 	if (len % lb_size > 0) {
2298 		lastblock_grow = lb_size - (len % lb_size);
2299 		lastblock_grow = MIN(size_diff, lastblock_grow);
2300 		len += lastblock_grow;
2301 		c_ad.len = udf_rw32(len | flags);
2302 
2303 		/* TODO zero appened space in buffer! */
2304 		/* using uvm_vnp_zerorange(vp, old_size, new_size - old_size); ? */
2305 	}
2306 	memset(&s_ad, 0, sizeof(struct long_ad));
2307 
2308 	/* size_diff can be bigger than allowed, so grow in chunks */
2309 	append_len = size_diff - lastblock_grow;
2310 	while (append_len > 0) {
2311 		chunk = MIN(append_len, max_len);
2312 		s_ad.len = udf_rw32(chunk | UDF_EXT_FREE);
2313 		s_ad.loc.part_num = udf_rw16(0);
2314 		s_ad.loc.lb_num   = udf_rw32(0);
2315 
2316 		if (udf_ads_merge(lb_size, &c_ad, &s_ad)) {
2317 			/* not mergable (anymore) */
2318 			error = udf_append_adslot(udf_node, &slot, &c_ad);
2319 			if (error)
2320 				goto errorout;
2321 			slot++;
2322 			c_ad = s_ad;
2323 			memset(&s_ad, 0, sizeof(struct long_ad));
2324 		}
2325 		append_len -= chunk;
2326 	}
2327 
2328 	/* if there is a rest piece in the accumulator, append it */
2329 	if (UDF_EXT_LEN(udf_rw32(c_ad.len)) > 0) {
2330 		error = udf_append_adslot(udf_node, &slot, &c_ad);
2331 		if (error)
2332 			goto errorout;
2333 		slot++;
2334 	}
2335 
2336 	/* if there is a rest piece that didn't fit, append it */
2337 	if (UDF_EXT_LEN(udf_rw32(s_ad.len)) > 0) {
2338 		error = udf_append_adslot(udf_node, &slot, &s_ad);
2339 		if (error)
2340 			goto errorout;
2341 		slot++;
2342 	}
2343 
2344 	inflen  += size_diff;
2345 	objsize += size_diff;
2346 	if (fe) {
2347 		fe->inf_len   = udf_rw64(inflen);
2348 	} else {
2349 		efe->inf_len  = udf_rw64(inflen);
2350 		efe->obj_size = udf_rw64(objsize);
2351 	}
2352 	error = 0;
2353 
2354 	if (evacuated_data) {
2355 		/* set new write size for uvm */
2356 		uvm_vnp_setwritesize(vp, old_size);
2357 
2358 		/* write out evacuated data */
2359 		error = vn_rdwr(UIO_WRITE, udf_node->vnode,
2360 				evacuated_data, old_size, 0,
2361 				UIO_SYSSPACE, IO_ALTSEMANTICS | IO_NODELOCKED,
2362 				FSCRED, NULL, NULL);
2363 		uvm_vnp_setsize(vp, old_size);
2364 	}
2365 
2366 errorout:
2367 	if (evacuated_data)
2368 		free(evacuated_data, M_UDFTEMP);
2369 
2370 	udf_count_alloc_exts(udf_node);
2371 
2372 	udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
2373 	UDF_UNLOCK_NODE(udf_node, 0);
2374 
2375 	KASSERT(new_inflen == orig_inflen + size_diff);
2376 	KASSERT(new_lbrec == orig_lbrec);
2377 
2378 	return error;
2379 }
2380 
2381 /* --------------------------------------------------------------------- */
2382 
2383 int
2384 udf_shrink_node(struct udf_node *udf_node, uint64_t new_size)
2385 {
2386 	struct vnode *vp = udf_node->vnode;
2387 	struct udf_mount *ump = udf_node->ump;
2388 	struct file_entry    *fe;
2389 	struct extfile_entry *efe;
2390 	struct icb_tag  *icbtag;
2391 	struct long_ad c_ad, s_ad, *node_ad_cpy;
2392 	uint64_t size_diff, old_size, inflen, objsize;
2393 	uint64_t foffset, end_foffset;
2394 	uint64_t orig_inflen, orig_lbrec, new_inflen, new_lbrec;
2395 	uint32_t lb_size, dscr_size, crclen;
2396 	uint32_t slot_offset;
2397 	uint32_t len, flags, max_len;
2398 	uint32_t num_lb, lb_num;
2399 	uint32_t max_l_ad, l_ad, l_ea;
2400 	uint16_t vpart_num;
2401 	uint8_t *data_pos;
2402 	int icbflags, addr_type;
2403 	int slot, cpy_slot, cpy_slots;
2404 	int eof, error;
2405 
2406 	DPRINTF(ALLOC, ("udf_shrink_node\n"));
2407 
2408 	UDF_LOCK_NODE(udf_node, 0);
2409 	udf_node_sanity_check(udf_node, &orig_inflen, &orig_lbrec);
2410 
2411 	lb_size = udf_rw32(ump->logical_vol->lb_size);
2412 	max_len = ((UDF_EXT_MAXLEN / lb_size) * lb_size);
2413 
2414 	/* do the work */
2415 	fe  = udf_node->fe;
2416 	efe = udf_node->efe;
2417 	if (fe) {
2418 		icbtag  = &fe->icbtag;
2419 		inflen  = udf_rw64(fe->inf_len);
2420 		objsize = inflen;
2421 		dscr_size  = sizeof(struct file_entry) -1;
2422 		l_ea       = udf_rw32(fe->l_ea);
2423 		l_ad       = udf_rw32(fe->l_ad);
2424 		data_pos = (uint8_t *) fe + dscr_size + l_ea;
2425 	} else {
2426 		icbtag  = &efe->icbtag;
2427 		inflen  = udf_rw64(efe->inf_len);
2428 		objsize = udf_rw64(efe->obj_size);
2429 		dscr_size  = sizeof(struct extfile_entry) -1;
2430 		l_ea       = udf_rw32(efe->l_ea);
2431 		l_ad       = udf_rw32(efe->l_ad);
2432 		data_pos = (uint8_t *) efe + dscr_size + l_ea;
2433 	}
2434 	max_l_ad = lb_size - dscr_size - l_ea;
2435 
2436 	icbflags   = udf_rw16(icbtag->flags);
2437 	addr_type  = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
2438 
2439 	old_size  = inflen;
2440 	size_diff = old_size - new_size;
2441 
2442 	DPRINTF(ALLOC, ("\tfrom %"PRIu64" to %"PRIu64"\n", old_size, new_size));
2443 
2444 	/* shrink the node to its new size */
2445 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
2446 		/* only reflect size change directly in the node */
2447 		KASSERT(new_size <= max_l_ad);
2448 		inflen  -= size_diff;
2449 		objsize -= size_diff;
2450 		l_ad    -= size_diff;
2451 		crclen = dscr_size - UDF_DESC_TAG_LENGTH + l_ea + l_ad;
2452 		if (fe) {
2453 			fe->inf_len   = udf_rw64(inflen);
2454 			fe->l_ad      = udf_rw32(l_ad);
2455 			fe->tag.desc_crc_len = udf_rw32(crclen);
2456 		} else {
2457 			efe->inf_len  = udf_rw64(inflen);
2458 			efe->obj_size = udf_rw64(objsize);
2459 			efe->l_ad     = udf_rw32(l_ad);
2460 			efe->tag.desc_crc_len = udf_rw32(crclen);
2461 		}
2462 		error = 0;
2463 
2464 		/* clear the space in the descriptor */
2465 		KASSERT(old_size > new_size);
2466 		memset(data_pos + new_size, 0, old_size - new_size);
2467 
2468 		/* TODO zero appened space in buffer! */
2469 		/* using uvm_vnp_zerorange(vp, old_size, old_size - new_size); ? */
2470 
2471 		/* set new size for uvm */
2472 		uvm_vnp_setsize(vp, new_size);
2473 
2474 		udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
2475 		UDF_UNLOCK_NODE(udf_node, 0);
2476 
2477 		KASSERT(new_inflen == orig_inflen - size_diff);
2478 		KASSERT(new_lbrec == orig_lbrec);
2479 		KASSERT(new_lbrec == 0);
2480 
2481 		return 0;
2482 	}
2483 
2484 	/* setup node cleanup extents copy space */
2485 	node_ad_cpy = malloc(lb_size * UDF_MAX_ALLOC_EXTENTS,
2486 		M_UDFMNT, M_WAITOK);
2487 	memset(node_ad_cpy, 0, lb_size * UDF_MAX_ALLOC_EXTENTS);
2488 
2489 	/*
2490 	 * Shrink the node by releasing the allocations and truncate the last
2491 	 * allocation to the new size. If the new size fits into the
2492 	 * allocation descriptor itself, transform it into an
2493 	 * UDF_ICB_INTERN_ALLOC.
2494 	 */
2495 	slot     = 0;
2496 	cpy_slot = 0;
2497 	foffset  = 0;
2498 
2499 	/* 1) copy till first overlap piece to the rewrite buffer */
2500 	for (;;) {
2501 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
2502 		if (eof) {
2503 			DPRINTF(WRITE,
2504 				("Shrink node failed: "
2505 				 "encountered EOF\n"));
2506 			error = EINVAL;
2507 			goto errorout; /* panic? */
2508 		}
2509 		len   = udf_rw32(s_ad.len);
2510 		flags = UDF_EXT_FLAGS(len);
2511 		len   = UDF_EXT_LEN(len);
2512 
2513 		if (flags == UDF_EXT_REDIRECT) {
2514 			slot++;
2515 			continue;
2516 		}
2517 
2518 		end_foffset = foffset + len;
2519 		if (end_foffset > new_size)
2520 			break;	/* found */
2521 
2522 		node_ad_cpy[cpy_slot++] = s_ad;
2523 
2524 		DPRINTF(ALLOC, ("\t1: vp %d, lb %d, len %d, flags %d "
2525 			"-> stack\n",
2526 			udf_rw16(s_ad.loc.part_num),
2527 			udf_rw32(s_ad.loc.lb_num),
2528 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
2529 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2530 
2531 		foffset = end_foffset;
2532 		slot++;
2533 	}
2534 	slot_offset = new_size - foffset;
2535 
2536 	/* 2) trunc overlapping slot at overlap and copy it */
2537 	if (slot_offset > 0) {
2538 		lb_num    = udf_rw32(s_ad.loc.lb_num);
2539 		vpart_num = udf_rw16(s_ad.loc.part_num);
2540 
2541 		if (flags == UDF_EXT_ALLOCATED) {
2542 			/* note: round DOWN on num_lb */
2543 			lb_num += (slot_offset + lb_size -1) / lb_size;
2544 			num_lb  = (len - slot_offset) / lb_size;
2545 
2546 			udf_free_allocated_space(ump, lb_num, vpart_num, num_lb);
2547 		}
2548 
2549 		s_ad.len = udf_rw32(slot_offset | flags);
2550 		node_ad_cpy[cpy_slot++] = s_ad;
2551 		slot++;
2552 
2553 		DPRINTF(ALLOC, ("\t2: vp %d, lb %d, len %d, flags %d "
2554 			"-> stack\n",
2555 			udf_rw16(s_ad.loc.part_num),
2556 			udf_rw32(s_ad.loc.lb_num),
2557 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
2558 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2559 	}
2560 
2561 	/* 3) delete remainder */
2562 	for (;;) {
2563 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
2564 		if (eof)
2565 			break;
2566 
2567 		len       = udf_rw32(s_ad.len);
2568 		flags     = UDF_EXT_FLAGS(len);
2569 		len       = UDF_EXT_LEN(len);
2570 
2571 		if (flags == UDF_EXT_REDIRECT) {
2572 			slot++;
2573 			continue;
2574 		}
2575 
2576 		DPRINTF(ALLOC, ("\t3: delete remainder "
2577 			"vp %d lb %d, len %d, flags %d\n",
2578 		udf_rw16(s_ad.loc.part_num),
2579 		udf_rw32(s_ad.loc.lb_num),
2580 		UDF_EXT_LEN(udf_rw32(s_ad.len)),
2581 		UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2582 
2583 		if (flags == UDF_EXT_ALLOCATED) {
2584 			lb_num    = udf_rw32(s_ad.loc.lb_num);
2585 			vpart_num = udf_rw16(s_ad.loc.part_num);
2586 			num_lb    = (len + lb_size - 1) / lb_size;
2587 
2588 			udf_free_allocated_space(ump, lb_num, vpart_num,
2589 				num_lb);
2590 		}
2591 
2592 		slot++;
2593 	}
2594 
2595 	/* 4) if it will fit into the descriptor then convert */
2596 	if (new_size < max_l_ad) {
2597 		/*
2598 		 * resque/evacuate old piece by reading it in, and convert it
2599 		 * to internal alloc.
2600 		 */
2601 		if (new_size == 0) {
2602 			/* XXX/TODO only for zero sizing now */
2603 			udf_wipe_adslots(udf_node);
2604 
2605 			icbflags &= ~UDF_ICB_TAG_FLAGS_ALLOC_MASK;
2606 			icbflags |=  UDF_ICB_INTERN_ALLOC;
2607 			icbtag->flags = udf_rw16(icbflags);
2608 
2609 			inflen  -= size_diff;	KASSERT(inflen == 0);
2610 			objsize -= size_diff;
2611 			l_ad     = new_size;
2612 			crclen = dscr_size - UDF_DESC_TAG_LENGTH + l_ea + l_ad;
2613 			if (fe) {
2614 				fe->inf_len   = udf_rw64(inflen);
2615 				fe->l_ad      = udf_rw32(l_ad);
2616 				fe->tag.desc_crc_len = udf_rw32(crclen);
2617 			} else {
2618 				efe->inf_len  = udf_rw64(inflen);
2619 				efe->obj_size = udf_rw64(objsize);
2620 				efe->l_ad     = udf_rw32(l_ad);
2621 				efe->tag.desc_crc_len = udf_rw32(crclen);
2622 			}
2623 			/* eventually copy in evacuated piece */
2624 			/* set new size for uvm */
2625 			uvm_vnp_setsize(vp, new_size);
2626 
2627 			free(node_ad_cpy, M_UDFMNT);
2628 			udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
2629 
2630 			UDF_UNLOCK_NODE(udf_node, 0);
2631 
2632 			KASSERT(new_inflen == orig_inflen - size_diff);
2633 			KASSERT(new_inflen == 0);
2634 			KASSERT(new_lbrec == 0);
2635 
2636 			return 0;
2637 		}
2638 
2639 		printf("UDF_SHRINK_NODE: could convert to internal alloc!\n");
2640 	}
2641 
2642 	/* 5) reset node descriptors */
2643 	udf_wipe_adslots(udf_node);
2644 
2645 	/* 6) copy back extents; merge when possible. Recounting on the fly */
2646 	cpy_slots = cpy_slot;
2647 
2648 	c_ad = node_ad_cpy[0];
2649 	slot = 0;
2650 	for (cpy_slot = 1; cpy_slot < cpy_slots; cpy_slot++) {
2651 		s_ad = node_ad_cpy[cpy_slot];
2652 
2653 		DPRINTF(ALLOC, ("\t6: stack -> got mapping vp %d "
2654 			"lb %d, len %d, flags %d\n",
2655 		udf_rw16(s_ad.loc.part_num),
2656 		udf_rw32(s_ad.loc.lb_num),
2657 		UDF_EXT_LEN(udf_rw32(s_ad.len)),
2658 		UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2659 
2660 		/* see if we can merge */
2661 		if (udf_ads_merge(lb_size, &c_ad, &s_ad)) {
2662 			/* not mergable (anymore) */
2663 			DPRINTF(ALLOC, ("\t6: appending vp %d lb %d, "
2664 				"len %d, flags %d\n",
2665 			udf_rw16(c_ad.loc.part_num),
2666 			udf_rw32(c_ad.loc.lb_num),
2667 			UDF_EXT_LEN(udf_rw32(c_ad.len)),
2668 			UDF_EXT_FLAGS(udf_rw32(c_ad.len)) >> 30));
2669 
2670 			error = udf_append_adslot(udf_node, &slot, &c_ad);
2671 			if (error)
2672 				goto errorout; /* panic? */
2673 			c_ad = s_ad;
2674 			slot++;
2675 		}
2676 	}
2677 
2678 	/* 7) push rest slot (if any) */
2679 	if (UDF_EXT_LEN(c_ad.len) > 0) {
2680 		DPRINTF(ALLOC, ("\t7: last append vp %d lb %d, "
2681 				"len %d, flags %d\n",
2682 		udf_rw16(c_ad.loc.part_num),
2683 		udf_rw32(c_ad.loc.lb_num),
2684 		UDF_EXT_LEN(udf_rw32(c_ad.len)),
2685 		UDF_EXT_FLAGS(udf_rw32(c_ad.len)) >> 30));
2686 
2687 		error = udf_append_adslot(udf_node, &slot, &c_ad);
2688 		if (error)
2689 			goto errorout; /* panic? */
2690 		;
2691 	}
2692 
2693 	inflen  -= size_diff;
2694 	objsize -= size_diff;
2695 	if (fe) {
2696 		fe->inf_len   = udf_rw64(inflen);
2697 	} else {
2698 		efe->inf_len  = udf_rw64(inflen);
2699 		efe->obj_size = udf_rw64(objsize);
2700 	}
2701 	error = 0;
2702 
2703 	/* set new size for uvm */
2704 	uvm_vnp_setsize(vp, new_size);
2705 
2706 errorout:
2707 	free(node_ad_cpy, M_UDFMNT);
2708 
2709 	udf_count_alloc_exts(udf_node);
2710 
2711 	udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
2712 	UDF_UNLOCK_NODE(udf_node, 0);
2713 
2714 	KASSERT(new_inflen == orig_inflen - size_diff);
2715 
2716 	return error;
2717 }
2718 
2719