xref: /minix/sys/fs/udf/udf_allocation.c (revision 0a6a1f1d)
1 /* $NetBSD: udf_allocation.c,v 1.38 2015/08/24 08:30:17 hannken 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.38 2015/08/24 08:30:17 hannken Exp $");
32 #endif /* not lint */
33 
34 
35 #if defined(_KERNEL_OPT)
36 #include "opt_compat_netbsd.h"
37 #endif
38 
39 /* TODO strip */
40 #include <sys/param.h>
41 #include <sys/systm.h>
42 #include <sys/sysctl.h>
43 #include <sys/namei.h>
44 #include <sys/proc.h>
45 #include <sys/kernel.h>
46 #include <sys/vnode.h>
47 #include <miscfs/genfs/genfs_node.h>
48 #include <sys/mount.h>
49 #include <sys/buf.h>
50 #include <sys/file.h>
51 #include <sys/device.h>
52 #include <sys/disklabel.h>
53 #include <sys/ioctl.h>
54 #include <sys/malloc.h>
55 #include <sys/dirent.h>
56 #include <sys/stat.h>
57 #include <sys/conf.h>
58 #include <sys/kauth.h>
59 #include <sys/kthread.h>
60 #include <dev/clock_subr.h>
61 
62 #include <fs/udf/ecma167-udf.h>
63 #include <fs/udf/udf_mount.h>
64 
65 #include "udf.h"
66 #include "udf_subr.h"
67 #include "udf_bswap.h"
68 
69 
70 #define VTOI(vnode) ((struct udf_node *) vnode->v_data)
71 
72 static void udf_record_allocation_in_node(struct udf_mount *ump,
73 	struct buf *buf, uint16_t vpart_num, uint64_t *mapping,
74 	struct long_ad *node_ad_cpy);
75 
76 static void udf_collect_free_space_for_vpart(struct udf_mount *ump,
77 	uint16_t vpart_num, uint32_t num_lb);
78 
79 static int udf_ads_merge(uint32_t max_len, uint32_t lb_size, struct long_ad *a1, struct long_ad *a2);
80 static void udf_wipe_adslots(struct udf_node *udf_node);
81 static void udf_count_alloc_exts(struct udf_node *udf_node);
82 
83 
84 /* --------------------------------------------------------------------- */
85 
86 #if 0
87 #if 1
88 static void
89 udf_node_dump(struct udf_node *udf_node) {
90 	struct file_entry    *fe;
91 	struct extfile_entry *efe;
92 	struct icb_tag *icbtag;
93 	struct long_ad s_ad;
94 	uint64_t inflen;
95 	uint32_t icbflags, addr_type;
96 	uint32_t len, lb_num;
97 	uint32_t flags;
98 	int part_num;
99 	int lb_size, eof, slot;
100 
101 	if ((udf_verbose & UDF_DEBUG_NODEDUMP) == 0)
102 		return;
103 
104 	lb_size = udf_rw32(udf_node->ump->logical_vol->lb_size);
105 
106 	fe  = udf_node->fe;
107 	efe = udf_node->efe;
108 	if (fe) {
109 		icbtag = &fe->icbtag;
110 		inflen = udf_rw64(fe->inf_len);
111 	} else {
112 		icbtag = &efe->icbtag;
113 		inflen = udf_rw64(efe->inf_len);
114 	}
115 
116 	icbflags   = udf_rw16(icbtag->flags);
117 	addr_type  = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
118 
119 	printf("udf_node_dump %p :\n", udf_node);
120 
121 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
122 		printf("\tIntern alloc, len = %"PRIu64"\n", inflen);
123 		return;
124 	}
125 
126 	printf("\tInflen  = %"PRIu64"\n", inflen);
127 	printf("\t\t");
128 
129 	slot = 0;
130 	for (;;) {
131 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
132 		if (eof)
133 			break;
134 		part_num = udf_rw16(s_ad.loc.part_num);
135 		lb_num = udf_rw32(s_ad.loc.lb_num);
136 		len   = udf_rw32(s_ad.len);
137 		flags = UDF_EXT_FLAGS(len);
138 		len   = UDF_EXT_LEN(len);
139 
140 		printf("[");
141 		if (part_num >= 0)
142 			printf("part %d, ", part_num);
143 		printf("lb_num %d, len %d", lb_num, len);
144 		if (flags)
145 			printf(", flags %d", flags>>30);
146 		printf("] ");
147 
148 		if (flags == UDF_EXT_REDIRECT) {
149 			printf("\n\textent END\n\tallocation extent\n\t\t");
150 		}
151 
152 		slot++;
153 	}
154 	printf("\n\tl_ad END\n\n");
155 }
156 #else
157 #define udf_node_dump(a)
158 #endif
159 
160 
161 static void
162 udf_assert_allocated(struct udf_mount *ump, uint16_t vpart_num,
163 	uint32_t lb_num, uint32_t num_lb)
164 {
165 	struct udf_bitmap *bitmap;
166 	struct part_desc *pdesc;
167 	uint32_t ptov;
168 	uint32_t bitval;
169 	uint8_t *bpos;
170 	int bit;
171 	int phys_part;
172 	int ok;
173 
174 	DPRINTF(PARANOIA, ("udf_assert_allocated: check virt lbnum %d "
175 			  "part %d + %d sect\n", lb_num, vpart_num, num_lb));
176 
177 	/* get partition backing up this vpart_num */
178 	pdesc = ump->partitions[ump->vtop[vpart_num]];
179 
180 	switch (ump->vtop_tp[vpart_num]) {
181 	case UDF_VTOP_TYPE_PHYS :
182 	case UDF_VTOP_TYPE_SPARABLE :
183 		/* free space to freed or unallocated space bitmap */
184 		ptov      = udf_rw32(pdesc->start_loc);
185 		phys_part = ump->vtop[vpart_num];
186 
187 		/* use unallocated bitmap */
188 		bitmap = &ump->part_unalloc_bits[phys_part];
189 
190 		/* if no bitmaps are defined, bail out */
191 		if (bitmap->bits == NULL)
192 			break;
193 
194 		/* check bits */
195 		KASSERT(bitmap->bits);
196 		ok = 1;
197 		bpos = bitmap->bits + lb_num/8;
198 		bit  = lb_num % 8;
199 		while (num_lb > 0) {
200 			bitval = (1 << bit);
201 			DPRINTF(PARANOIA, ("XXX : check %d, %p, bit %d\n",
202 				lb_num, bpos, bit));
203 			KASSERT(bitmap->bits + lb_num/8 == bpos);
204 			if (*bpos & bitval) {
205 				printf("\tlb_num %d is NOT marked busy\n",
206 					lb_num);
207 				ok = 0;
208 			}
209 			lb_num++; num_lb--;
210 			bit = (bit + 1) % 8;
211 			if (bit == 0)
212 				bpos++;
213 		}
214 		if (!ok) {
215 			/* KASSERT(0); */
216 		}
217 
218 		break;
219 	case UDF_VTOP_TYPE_VIRT :
220 		/* TODO check space */
221 		KASSERT(num_lb == 1);
222 		break;
223 	case UDF_VTOP_TYPE_META :
224 		/* TODO check space in the metadata bitmap */
225 	default:
226 		/* not implemented */
227 		break;
228 	}
229 }
230 
231 
232 static void
233 udf_node_sanity_check(struct udf_node *udf_node,
234 		uint64_t *cnt_inflen, uint64_t *cnt_logblksrec)
235 {
236 	union dscrptr *dscr;
237 	struct file_entry    *fe;
238 	struct extfile_entry *efe;
239 	struct icb_tag *icbtag;
240 	struct long_ad  s_ad;
241 	uint64_t inflen, logblksrec;
242 	uint32_t icbflags, addr_type;
243 	uint32_t len, lb_num, l_ea, l_ad, max_l_ad;
244 	uint16_t part_num;
245 	uint8_t *data_pos;
246 	int dscr_size, lb_size, flags, whole_lb;
247 	int i, slot, eof;
248 
249 //	KASSERT(mutex_owned(&udf_node->ump->allocate_mutex));
250 
251 	if (1)
252 		udf_node_dump(udf_node);
253 
254 	lb_size = udf_rw32(udf_node->ump->logical_vol->lb_size);
255 
256 	fe  = udf_node->fe;
257 	efe = udf_node->efe;
258 	if (fe) {
259 		dscr       = (union dscrptr *) 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 		dscr       = (union dscrptr *) efe;
268 		icbtag     = &efe->icbtag;
269 		inflen     = udf_rw64(efe->inf_len);
270 		dscr_size  = sizeof(struct extfile_entry) -1;
271 		logblksrec = udf_rw64(efe->logblks_rec);
272 		l_ad       = udf_rw32(efe->l_ad);
273 		l_ea       = udf_rw32(efe->l_ea);
274 	}
275 	data_pos  = (uint8_t *) dscr + dscr_size + l_ea;
276 	max_l_ad   = lb_size - dscr_size - l_ea;
277 	icbflags   = udf_rw16(icbtag->flags);
278 	addr_type  = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
279 
280 	/* check if tail is zero */
281 	DPRINTF(PARANOIA, ("Sanity check blank tail\n"));
282 	for (i = l_ad; i < max_l_ad; i++) {
283 		if (data_pos[i] != 0)
284 			printf( "sanity_check: violation: node byte %d "
285 				"has value %d\n", i, data_pos[i]);
286 	}
287 
288 	/* reset counters */
289 	*cnt_inflen     = 0;
290 	*cnt_logblksrec = 0;
291 
292 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
293 		KASSERT(l_ad <= max_l_ad);
294 		KASSERT(l_ad == inflen);
295 		*cnt_inflen = inflen;
296 		return;
297 	}
298 
299 	/* start counting */
300 	whole_lb = 1;
301 	slot = 0;
302 	for (;;) {
303 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
304 		if (eof)
305 			break;
306 		KASSERT(whole_lb == 1);
307 
308 		part_num = udf_rw16(s_ad.loc.part_num);
309 		lb_num = udf_rw32(s_ad.loc.lb_num);
310 		len   = udf_rw32(s_ad.len);
311 		flags = UDF_EXT_FLAGS(len);
312 		len   = UDF_EXT_LEN(len);
313 
314 		if (flags != UDF_EXT_REDIRECT) {
315 			*cnt_inflen += len;
316 			if (flags == UDF_EXT_ALLOCATED) {
317 				*cnt_logblksrec += (len + lb_size -1) / lb_size;
318 			}
319 		} else {
320 			KASSERT(len == lb_size);
321 		}
322 		/* check allocation */
323 		if (flags == UDF_EXT_ALLOCATED)
324 			udf_assert_allocated(udf_node->ump, part_num, lb_num,
325 				(len + lb_size - 1) / lb_size);
326 
327 		/* check whole lb */
328 		whole_lb = ((len % lb_size) == 0);
329 
330 		slot++;
331 	}
332 	/* rest should be zero (ad_off > l_ad < max_l_ad - adlen) */
333 
334 	KASSERT(*cnt_inflen == inflen);
335 	KASSERT(*cnt_logblksrec == logblksrec);
336 
337 //	KASSERT(mutex_owned(&udf_node->ump->allocate_mutex));
338 }
339 #else
340 static void
udf_node_sanity_check(struct udf_node * udf_node,uint64_t * cnt_inflen,uint64_t * cnt_logblksrec)341 udf_node_sanity_check(struct udf_node *udf_node,
342 		uint64_t *cnt_inflen, uint64_t *cnt_logblksrec) {
343 	struct file_entry    *fe;
344 	struct extfile_entry *efe;
345 	uint64_t inflen, logblksrec;
346 
347 	fe  = udf_node->fe;
348 	efe = udf_node->efe;
349 	if (fe) {
350 		inflen = udf_rw64(fe->inf_len);
351 		logblksrec = udf_rw64(fe->logblks_rec);
352 	} else {
353 		inflen = udf_rw64(efe->inf_len);
354 		logblksrec = udf_rw64(efe->logblks_rec);
355 	}
356 	*cnt_logblksrec = logblksrec;
357 	*cnt_inflen     = inflen;
358 }
359 #endif
360 
361 /* --------------------------------------------------------------------- */
362 
363 void
udf_calc_freespace(struct udf_mount * ump,uint64_t * sizeblks,uint64_t * freeblks)364 udf_calc_freespace(struct udf_mount *ump, uint64_t *sizeblks, uint64_t *freeblks)
365 {
366 	struct logvol_int_desc *lvid;
367 	uint32_t *pos1, *pos2;
368 	int vpart, num_vpart;
369 
370 	lvid = ump->logvol_integrity;
371 	*freeblks = *sizeblks = 0;
372 
373 	/*
374 	 * Sequentials media report free space directly (CD/DVD/BD-R), for the
375 	 * other media we need the logical volume integrity.
376 	 *
377 	 * We sum all free space up here regardless of type.
378 	 */
379 
380 	KASSERT(lvid);
381 	num_vpart = udf_rw32(lvid->num_part);
382 
383 	if (ump->discinfo.mmc_cur & MMC_CAP_SEQUENTIAL) {
384 		/* use track info directly summing if there are 2 open */
385 		/* XXX assumption at most two tracks open */
386 		*freeblks = ump->data_track.free_blocks;
387 		if (ump->data_track.tracknr != ump->metadata_track.tracknr)
388 			*freeblks += ump->metadata_track.free_blocks;
389 		*sizeblks = ump->discinfo.last_possible_lba;
390 	} else {
391 		/* free and used space for mountpoint based on logvol integrity */
392 		for (vpart = 0; vpart < num_vpart; vpart++) {
393 			pos1 = &lvid->tables[0] + vpart;
394 			pos2 = &lvid->tables[0] + num_vpart + vpart;
395 			if (udf_rw32(*pos1) != (uint32_t) -1) {
396 				*freeblks += udf_rw32(*pos1);
397 				*sizeblks += udf_rw32(*pos2);
398 			}
399 		}
400 	}
401 	/* adjust for accounted uncommitted blocks */
402 	for (vpart = 0; vpart < num_vpart; vpart++)
403 		*freeblks -= ump->uncommitted_lbs[vpart];
404 
405 	if (*freeblks > UDF_DISC_SLACK) {
406 		*freeblks -= UDF_DISC_SLACK;
407 	} else {
408 		*freeblks = 0;
409 	}
410 }
411 
412 
413 static void
udf_calc_vpart_freespace(struct udf_mount * ump,uint16_t vpart_num,uint64_t * freeblks)414 udf_calc_vpart_freespace(struct udf_mount *ump, uint16_t vpart_num, uint64_t *freeblks)
415 {
416 	struct logvol_int_desc *lvid;
417 	uint32_t *pos1;
418 
419 	lvid = ump->logvol_integrity;
420 	*freeblks = 0;
421 
422 	/*
423 	 * Sequentials media report free space directly (CD/DVD/BD-R), for the
424 	 * other media we need the logical volume integrity.
425 	 *
426 	 * We sum all free space up here regardless of type.
427 	 */
428 
429 	KASSERT(lvid);
430 	if (ump->discinfo.mmc_cur & MMC_CAP_SEQUENTIAL) {
431 		/* XXX assumption at most two tracks open */
432 		if (vpart_num == ump->data_part) {
433 			*freeblks = ump->data_track.free_blocks;
434 		} else {
435 			*freeblks = ump->metadata_track.free_blocks;
436 		}
437 	} else {
438 		/* free and used space for mountpoint based on logvol integrity */
439 		pos1 = &lvid->tables[0] + vpart_num;
440 		if (udf_rw32(*pos1) != (uint32_t) -1)
441 			*freeblks += udf_rw32(*pos1);
442 	}
443 
444 	/* adjust for accounted uncommitted blocks */
445 	if (*freeblks > ump->uncommitted_lbs[vpart_num]) {
446 		*freeblks -= ump->uncommitted_lbs[vpart_num];
447 	} else {
448 		*freeblks = 0;
449 	}
450 }
451 
452 /* --------------------------------------------------------------------- */
453 
454 int
udf_translate_vtop(struct udf_mount * ump,struct long_ad * icb_loc,uint32_t * lb_numres,uint32_t * extres)455 udf_translate_vtop(struct udf_mount *ump, struct long_ad *icb_loc,
456 		   uint32_t *lb_numres, uint32_t *extres)
457 {
458 	struct part_desc       *pdesc;
459 	struct spare_map_entry *sme;
460 	struct long_ad s_icb_loc;
461 	uint64_t foffset, end_foffset;
462 	uint32_t lb_size, len;
463 	uint32_t lb_num, lb_rel, lb_packet;
464 	uint32_t udf_rw32_lbmap, ext_offset;
465 	uint16_t vpart;
466 	int rel, part, error, eof, slot, flags;
467 
468 	assert(ump && icb_loc && lb_numres);
469 
470 	vpart  = udf_rw16(icb_loc->loc.part_num);
471 	lb_num = udf_rw32(icb_loc->loc.lb_num);
472 	if (vpart > UDF_VTOP_RAWPART)
473 		return EINVAL;
474 
475 translate_again:
476 	part = ump->vtop[vpart];
477 	pdesc = ump->partitions[part];
478 
479 	switch (ump->vtop_tp[vpart]) {
480 	case UDF_VTOP_TYPE_RAW :
481 		/* 1:1 to the end of the device */
482 		*lb_numres = lb_num;
483 		*extres = INT_MAX;
484 		return 0;
485 	case UDF_VTOP_TYPE_PHYS :
486 		/* transform into its disc logical block */
487 		if (lb_num > udf_rw32(pdesc->part_len))
488 			return EINVAL;
489 		*lb_numres = lb_num + udf_rw32(pdesc->start_loc);
490 
491 		/* extent from here to the end of the partition */
492 		*extres = udf_rw32(pdesc->part_len) - lb_num;
493 		return 0;
494 	case UDF_VTOP_TYPE_VIRT :
495 		/* only maps one logical block, lookup in VAT */
496 		if (lb_num >= ump->vat_entries)		/* XXX > or >= ? */
497 			return EINVAL;
498 
499 		/* lookup in virtual allocation table file */
500 		mutex_enter(&ump->allocate_mutex);
501 		error = udf_vat_read(ump->vat_node,
502 				(uint8_t *) &udf_rw32_lbmap, 4,
503 				ump->vat_offset + lb_num * 4);
504 		mutex_exit(&ump->allocate_mutex);
505 
506 		if (error)
507 			return error;
508 
509 		lb_num = udf_rw32(udf_rw32_lbmap);
510 
511 		/* transform into its disc logical block */
512 		if (lb_num > udf_rw32(pdesc->part_len))
513 			return EINVAL;
514 		*lb_numres = lb_num + udf_rw32(pdesc->start_loc);
515 
516 		/* just one logical block */
517 		*extres = 1;
518 		return 0;
519 	case UDF_VTOP_TYPE_SPARABLE :
520 		/* check if the packet containing the lb_num is remapped */
521 		lb_packet = lb_num / ump->sparable_packet_size;
522 		lb_rel    = lb_num % ump->sparable_packet_size;
523 
524 		for (rel = 0; rel < udf_rw16(ump->sparing_table->rt_l); rel++) {
525 			sme = &ump->sparing_table->entries[rel];
526 			if (lb_packet == udf_rw32(sme->org)) {
527 				/* NOTE maps to absolute disc logical block! */
528 				*lb_numres = udf_rw32(sme->map) + lb_rel;
529 				*extres    = ump->sparable_packet_size - lb_rel;
530 				return 0;
531 			}
532 		}
533 
534 		/* transform into its disc logical block */
535 		if (lb_num > udf_rw32(pdesc->part_len))
536 			return EINVAL;
537 		*lb_numres = lb_num + udf_rw32(pdesc->start_loc);
538 
539 		/* rest of block */
540 		*extres = ump->sparable_packet_size - lb_rel;
541 		return 0;
542 	case UDF_VTOP_TYPE_META :
543 		/* we have to look into the file's allocation descriptors */
544 
545 		/* use metadatafile allocation mutex */
546 		lb_size = udf_rw32(ump->logical_vol->lb_size);
547 
548 		UDF_LOCK_NODE(ump->metadata_node, 0);
549 
550 		/* get first overlapping extent */
551 		foffset = 0;
552 		slot    = 0;
553 		for (;;) {
554 			udf_get_adslot(ump->metadata_node,
555 				slot, &s_icb_loc, &eof);
556 			DPRINTF(ADWLK, ("slot %d, eof = %d, flags = %d, "
557 				"len = %d, lb_num = %d, part = %d\n",
558 				slot, eof,
559 				UDF_EXT_FLAGS(udf_rw32(s_icb_loc.len)),
560 				UDF_EXT_LEN(udf_rw32(s_icb_loc.len)),
561 				udf_rw32(s_icb_loc.loc.lb_num),
562 				udf_rw16(s_icb_loc.loc.part_num)));
563 			if (eof) {
564 				DPRINTF(TRANSLATE,
565 					("Meta partition translation "
566 					 "failed: can't seek location\n"));
567 				UDF_UNLOCK_NODE(ump->metadata_node, 0);
568 				return EINVAL;
569 			}
570 			len   = udf_rw32(s_icb_loc.len);
571 			flags = UDF_EXT_FLAGS(len);
572 			len   = UDF_EXT_LEN(len);
573 
574 			if (flags == UDF_EXT_REDIRECT) {
575 				slot++;
576 				continue;
577 			}
578 
579 			end_foffset = foffset + len;
580 
581 			if (end_foffset > (uint64_t) lb_num * lb_size)
582 				break;	/* found */
583 			foffset = end_foffset;
584 			slot++;
585 		}
586 		/* found overlapping slot */
587 		ext_offset = lb_num * lb_size - foffset;
588 
589 		/* process extent offset */
590 		lb_num   = udf_rw32(s_icb_loc.loc.lb_num);
591 		vpart    = udf_rw16(s_icb_loc.loc.part_num);
592 		lb_num  += (ext_offset + lb_size -1) / lb_size;
593 		ext_offset = 0;
594 
595 		UDF_UNLOCK_NODE(ump->metadata_node, 0);
596 		if (flags != UDF_EXT_ALLOCATED) {
597 			DPRINTF(TRANSLATE, ("Metadata partition translation "
598 					    "failed: not allocated\n"));
599 			return EINVAL;
600 		}
601 
602 		/*
603 		 * vpart and lb_num are updated, translate again since we
604 		 * might be mapped on sparable media
605 		 */
606 		goto translate_again;
607 	default:
608 		printf("UDF vtop translation scheme %d unimplemented yet\n",
609 			ump->vtop_tp[vpart]);
610 	}
611 
612 	return EINVAL;
613 }
614 
615 
616 /* XXX  provisional primitive braindead version */
617 /* TODO use ext_res */
618 void
udf_translate_vtop_list(struct udf_mount * ump,uint32_t sectors,uint16_t vpart_num,uint64_t * lmapping,uint64_t * pmapping)619 udf_translate_vtop_list(struct udf_mount *ump, uint32_t sectors,
620 	uint16_t vpart_num, uint64_t *lmapping, uint64_t *pmapping)
621 {
622 	struct long_ad loc;
623 	uint32_t lb_numres, ext_res;
624 	int sector;
625 
626 	for (sector = 0; sector < sectors; sector++) {
627 		memset(&loc, 0, sizeof(struct long_ad));
628 		loc.loc.part_num = udf_rw16(vpart_num);
629 		loc.loc.lb_num   = udf_rw32(*lmapping);
630 		udf_translate_vtop(ump, &loc, &lb_numres, &ext_res);
631 		*pmapping = lb_numres;
632 		lmapping++; pmapping++;
633 	}
634 }
635 
636 
637 /* --------------------------------------------------------------------- */
638 
639 /*
640  * Translate an extent (in logical_blocks) into logical block numbers; used
641  * for read and write operations. DOESNT't check extents.
642  */
643 
644 int
udf_translate_file_extent(struct udf_node * udf_node,uint32_t from,uint32_t num_lb,uint64_t * map)645 udf_translate_file_extent(struct udf_node *udf_node,
646 		          uint32_t from, uint32_t num_lb,
647 			  uint64_t *map)
648 {
649 	struct udf_mount *ump;
650 	struct icb_tag *icbtag;
651 	struct long_ad t_ad, s_ad;
652 	uint64_t transsec;
653 	uint64_t foffset, end_foffset;
654 	uint32_t transsec32;
655 	uint32_t lb_size;
656 	uint32_t ext_offset;
657 	uint32_t lb_num, len;
658 	uint32_t overlap, translen;
659 	uint16_t vpart_num;
660 	int eof, error, flags;
661 	int slot, addr_type, icbflags;
662 
663 	if (!udf_node)
664 		return ENOENT;
665 
666 	KASSERT(num_lb > 0);
667 
668 	UDF_LOCK_NODE(udf_node, 0);
669 
670 	/* initialise derivative vars */
671 	ump = udf_node->ump;
672 	lb_size = udf_rw32(ump->logical_vol->lb_size);
673 
674 	if (udf_node->fe) {
675 		icbtag = &udf_node->fe->icbtag;
676 	} else {
677 		icbtag = &udf_node->efe->icbtag;
678 	}
679 	icbflags  = udf_rw16(icbtag->flags);
680 	addr_type = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
681 
682 	/* do the work */
683 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
684 		*map = UDF_TRANS_INTERN;
685 		UDF_UNLOCK_NODE(udf_node, 0);
686 		return 0;
687 	}
688 
689 	/* find first overlapping extent */
690 	foffset = 0;
691 	slot    = 0;
692 	for (;;) {
693 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
694 		DPRINTF(ADWLK, ("slot %d, eof = %d, flags = %d, len = %d, "
695 			"lb_num = %d, part = %d\n", slot, eof,
696 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)),
697 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
698 			udf_rw32(s_ad.loc.lb_num),
699 			udf_rw16(s_ad.loc.part_num)));
700 		if (eof) {
701 			DPRINTF(TRANSLATE,
702 				("Translate file extent "
703 				 "failed: can't seek location\n"));
704 			UDF_UNLOCK_NODE(udf_node, 0);
705 			return EINVAL;
706 		}
707 		len    = udf_rw32(s_ad.len);
708 		flags  = UDF_EXT_FLAGS(len);
709 		len    = UDF_EXT_LEN(len);
710 		lb_num = udf_rw32(s_ad.loc.lb_num);
711 
712 		if (flags == UDF_EXT_REDIRECT) {
713 			slot++;
714 			continue;
715 		}
716 
717 		end_foffset = foffset + len;
718 
719 		if (end_foffset > (uint64_t) from * lb_size)
720 			break;	/* found */
721 		foffset = end_foffset;
722 		slot++;
723 	}
724 	/* found overlapping slot */
725 	ext_offset = (uint64_t) from * lb_size - foffset;
726 
727 	for (;;) {
728 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
729 		DPRINTF(ADWLK, ("slot %d, eof = %d, flags = %d, len = %d, "
730 			"lb_num = %d, part = %d\n", slot, eof,
731 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)),
732 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
733 			udf_rw32(s_ad.loc.lb_num),
734 			udf_rw16(s_ad.loc.part_num)));
735 		if (eof) {
736 			DPRINTF(TRANSLATE,
737 				("Translate file extent "
738 				 "failed: past eof\n"));
739 			UDF_UNLOCK_NODE(udf_node, 0);
740 			return EINVAL;
741 		}
742 
743 		len    = udf_rw32(s_ad.len);
744 		flags  = UDF_EXT_FLAGS(len);
745 		len    = UDF_EXT_LEN(len);
746 
747 		lb_num    = udf_rw32(s_ad.loc.lb_num);
748 		vpart_num = udf_rw16(s_ad.loc.part_num);
749 
750 		end_foffset = foffset + len;
751 
752 		/* process extent, don't forget to advance on ext_offset! */
753 		lb_num  += (ext_offset + lb_size -1) / lb_size;
754 		overlap  = (len - ext_offset + lb_size -1) / lb_size;
755 		ext_offset = 0;
756 
757 		/*
758 		 * note that the while(){} is nessisary for the extent that
759 		 * the udf_translate_vtop() returns doens't have to span the
760 		 * whole extent.
761 		 */
762 
763 		overlap = MIN(overlap, num_lb);
764 		while (overlap && (flags != UDF_EXT_REDIRECT)) {
765 			switch (flags) {
766 			case UDF_EXT_FREE :
767 			case UDF_EXT_ALLOCATED_BUT_NOT_USED :
768 				transsec = UDF_TRANS_ZERO;
769 				translen = overlap;
770 				while (overlap && num_lb && translen) {
771 					*map++ = transsec;
772 					lb_num++;
773 					overlap--; num_lb--; translen--;
774 				}
775 				break;
776 			case UDF_EXT_ALLOCATED :
777 				t_ad.loc.lb_num   = udf_rw32(lb_num);
778 				t_ad.loc.part_num = udf_rw16(vpart_num);
779 				error = udf_translate_vtop(ump,
780 						&t_ad, &transsec32, &translen);
781 				transsec = transsec32;
782 				if (error) {
783 					UDF_UNLOCK_NODE(udf_node, 0);
784 					return error;
785 				}
786 				while (overlap && num_lb && translen) {
787 					*map++ = transsec;
788 					lb_num++; transsec++;
789 					overlap--; num_lb--; translen--;
790 				}
791 				break;
792 			default:
793 				DPRINTF(TRANSLATE,
794 					("Translate file extent "
795 					 "failed: bad flags %x\n", flags));
796 				UDF_UNLOCK_NODE(udf_node, 0);
797 				return EINVAL;
798 			}
799 		}
800 		if (num_lb == 0)
801 			break;
802 
803 		if (flags != UDF_EXT_REDIRECT)
804 			foffset = end_foffset;
805 		slot++;
806 	}
807 	UDF_UNLOCK_NODE(udf_node, 0);
808 
809 	return 0;
810 }
811 
812 /* --------------------------------------------------------------------- */
813 
814 static int
udf_search_free_vatloc(struct udf_mount * ump,uint32_t * lbnumres)815 udf_search_free_vatloc(struct udf_mount *ump, uint32_t *lbnumres)
816 {
817 	uint32_t lb_size, lb_num, lb_map, udf_rw32_lbmap;
818 	uint8_t *blob;
819 	int entry, chunk, found, error;
820 
821 	KASSERT(ump);
822 	KASSERT(ump->logical_vol);
823 
824 	lb_size = udf_rw32(ump->logical_vol->lb_size);
825 	blob = malloc(lb_size, M_UDFTEMP, M_WAITOK);
826 
827 	/* TODO static allocation of search chunk */
828 
829 	lb_num = MIN(ump->vat_entries, ump->vat_last_free_lb);
830 	found  = 0;
831 	error  = 0;
832 	entry  = 0;
833 	do {
834 		chunk = MIN(lb_size, (ump->vat_entries - lb_num) * 4);
835 		if (chunk <= 0)
836 			break;
837 		/* load in chunk */
838 		error = udf_vat_read(ump->vat_node, blob, chunk,
839 				ump->vat_offset + lb_num * 4);
840 
841 		if (error)
842 			break;
843 
844 		/* search this chunk */
845 		for (entry=0; entry < chunk /4; entry++, lb_num++) {
846 			udf_rw32_lbmap = *((uint32_t *) (blob + entry * 4));
847 			lb_map = udf_rw32(udf_rw32_lbmap);
848 			if (lb_map == 0xffffffff) {
849 				found = 1;
850 				break;
851 			}
852 		}
853 	} while (!found);
854 	if (error) {
855 		printf("udf_search_free_vatloc: error reading in vat chunk "
856 			"(lb %d, size %d)\n", lb_num, chunk);
857 	}
858 
859 	if (!found) {
860 		/* extend VAT */
861 		DPRINTF(WRITE, ("udf_search_free_vatloc: extending\n"));
862 		lb_num = ump->vat_entries;
863 		ump->vat_entries++;
864 	}
865 
866 	/* mark entry with initialiser just in case */
867 	lb_map = udf_rw32(0xfffffffe);
868 	udf_vat_write(ump->vat_node, (uint8_t *) &lb_map, 4,
869 		ump->vat_offset + lb_num *4);
870 	ump->vat_last_free_lb = lb_num;
871 
872 	free(blob, M_UDFTEMP);
873 	*lbnumres = lb_num;
874 	return 0;
875 }
876 
877 
878 static void
udf_bitmap_allocate(struct udf_bitmap * bitmap,int ismetadata,uint32_t * num_lb,uint64_t * lmappos)879 udf_bitmap_allocate(struct udf_bitmap *bitmap, int ismetadata,
880 	uint32_t *num_lb, uint64_t *lmappos)
881 {
882 	uint32_t offset, lb_num, bit;
883 	int32_t  diff;
884 	uint8_t *bpos;
885 	int pass;
886 
887 	if (!ismetadata) {
888 		/* heuristic to keep the two pointers not too close */
889 		diff = bitmap->data_pos - bitmap->metadata_pos;
890 		if ((diff >= 0) && (diff < 1024))
891 			bitmap->data_pos = bitmap->metadata_pos + 1024;
892 	}
893 	offset = ismetadata ? bitmap->metadata_pos : bitmap->data_pos;
894 	offset &= ~7;
895 	for (pass = 0; pass < 2; pass++) {
896 		if (offset >= bitmap->max_offset)
897 			offset = 0;
898 
899 		while (offset < bitmap->max_offset) {
900 			if (*num_lb == 0)
901 				break;
902 
903 			/* use first bit not set */
904 			bpos  = bitmap->bits + offset/8;
905 			bit = ffs(*bpos);	/* returns 0 or 1..8 */
906 			if (bit == 0) {
907 				offset += 8;
908 				continue;
909 			}
910 
911 			/* check for ffs overshoot */
912 			if (offset + bit-1 >= bitmap->max_offset) {
913 				offset = bitmap->max_offset;
914 				break;
915 			}
916 
917 			DPRINTF(PARANOIA, ("XXX : allocate %d, %p, bit %d\n",
918 				offset + bit -1, bpos, bit-1));
919 			*bpos &= ~(1 << (bit-1));
920 			lb_num = offset + bit-1;
921 			*lmappos++ = lb_num;
922 			*num_lb = *num_lb - 1;
923 			// offset = (offset & ~7);
924 		}
925 	}
926 
927 	if (ismetadata) {
928 		bitmap->metadata_pos = offset;
929 	} else {
930 		bitmap->data_pos = offset;
931 	}
932 }
933 
934 
935 static void
udf_bitmap_free(struct udf_bitmap * bitmap,uint32_t lb_num,uint32_t num_lb)936 udf_bitmap_free(struct udf_bitmap *bitmap, uint32_t lb_num, uint32_t num_lb)
937 {
938 	uint32_t offset;
939 	uint32_t bit, bitval;
940 	uint8_t *bpos;
941 
942 	offset = lb_num;
943 
944 	/* starter bits */
945 	bpos = bitmap->bits + offset/8;
946 	bit = offset % 8;
947 	while ((bit != 0) && (num_lb > 0)) {
948 		bitval = (1 << bit);
949 		KASSERT((*bpos & bitval) == 0);
950 		DPRINTF(PARANOIA, ("XXX : free %d, %p, %d\n",
951 			offset, bpos, bit));
952 		*bpos |= bitval;
953 		offset++; num_lb--;
954 		bit = (bit + 1) % 8;
955 	}
956 	if (num_lb == 0)
957 		return;
958 
959 	/* whole bytes */
960 	KASSERT(bit == 0);
961 	bpos = bitmap->bits + offset / 8;
962 	while (num_lb >= 8) {
963 		KASSERT((*bpos == 0));
964 		DPRINTF(PARANOIA, ("XXX : free %d + 8, %p\n", offset, bpos));
965 		*bpos = 255;
966 		offset += 8; num_lb -= 8;
967 		bpos++;
968 	}
969 
970 	/* stop bits */
971 	KASSERT(num_lb < 8);
972 	bit = 0;
973 	while (num_lb > 0) {
974 		bitval = (1 << bit);
975 		KASSERT((*bpos & bitval) == 0);
976 		DPRINTF(PARANOIA, ("XXX : free %d, %p, %d\n",
977 			offset, bpos, bit));
978 		*bpos |= bitval;
979 		offset++; num_lb--;
980 		bit = (bit + 1) % 8;
981 	}
982 }
983 
984 
985 static uint32_t
udf_bitmap_check_trunc_free(struct udf_bitmap * bitmap,uint32_t to_trunc)986 udf_bitmap_check_trunc_free(struct udf_bitmap *bitmap, uint32_t to_trunc)
987 {
988 	uint32_t seq_free, offset;
989 	uint8_t *bpos;
990 	uint8_t  bit, bitval;
991 
992 	DPRINTF(RESERVE, ("\ttrying to trunc %d bits from bitmap\n", to_trunc));
993 	offset = bitmap->max_offset - to_trunc;
994 
995 	/* starter bits (if any) */
996 	bpos = bitmap->bits + offset/8;
997 	bit = offset % 8;
998 	seq_free = 0;
999 	while (to_trunc > 0) {
1000 		seq_free++;
1001 		bitval = (1 << bit);
1002 		if (!(*bpos & bitval))
1003 			seq_free = 0;
1004 		offset++; to_trunc--;
1005 		bit++;
1006 		if (bit == 8) {
1007 			bpos++;
1008 			bit = 0;
1009 		}
1010 	}
1011 
1012 	DPRINTF(RESERVE, ("\tfound %d sequential free bits in bitmap\n", seq_free));
1013 	return seq_free;
1014 }
1015 
1016 /* --------------------------------------------------------------------- */
1017 
1018 /*
1019  * We check for overall disc space with a margin to prevent critical
1020  * conditions.  If disc space is low we try to force a sync() to improve our
1021  * estimates.  When confronted with meta-data partition size shortage we know
1022  * we have to check if it can be extended and we need to extend it when
1023  * needed.
1024  *
1025  * A 2nd strategy we could use when disc space is getting low on a disc
1026  * formatted with a meta-data partition is to see if there are sparse areas in
1027  * the meta-data partition and free blocks there for extra data.
1028  */
1029 
1030 void
udf_do_reserve_space(struct udf_mount * ump,struct udf_node * udf_node,uint16_t vpart_num,uint32_t num_lb)1031 udf_do_reserve_space(struct udf_mount *ump, struct udf_node *udf_node,
1032 	uint16_t vpart_num, uint32_t num_lb)
1033 {
1034 	ump->uncommitted_lbs[vpart_num] += num_lb;
1035 	if (udf_node)
1036 		udf_node->uncommitted_lbs += num_lb;
1037 }
1038 
1039 
1040 void
udf_do_unreserve_space(struct udf_mount * ump,struct udf_node * udf_node,uint16_t vpart_num,uint32_t num_lb)1041 udf_do_unreserve_space(struct udf_mount *ump, struct udf_node *udf_node,
1042 	uint16_t vpart_num, uint32_t num_lb)
1043 {
1044 	ump->uncommitted_lbs[vpart_num] -= num_lb;
1045 	if (ump->uncommitted_lbs[vpart_num] < 0) {
1046 		DPRINTF(RESERVE, ("UDF: underflow on partition reservation, "
1047 			"part %d: %d\n", vpart_num,
1048 			ump->uncommitted_lbs[vpart_num]));
1049 		ump->uncommitted_lbs[vpart_num] = 0;
1050 	}
1051 	if (udf_node) {
1052 		udf_node->uncommitted_lbs -= num_lb;
1053 		if (udf_node->uncommitted_lbs < 0) {
1054 			DPRINTF(RESERVE, ("UDF: underflow of node "
1055 				"reservation : %d\n",
1056 				udf_node->uncommitted_lbs));
1057 			udf_node->uncommitted_lbs = 0;
1058 		}
1059 	}
1060 }
1061 
1062 
1063 int
udf_reserve_space(struct udf_mount * ump,struct udf_node * udf_node,int udf_c_type,uint16_t vpart_num,uint32_t num_lb,int can_fail)1064 udf_reserve_space(struct udf_mount *ump, struct udf_node *udf_node,
1065 	int udf_c_type, uint16_t vpart_num, uint32_t num_lb, int can_fail)
1066 {
1067 	uint64_t freeblks;
1068 	uint64_t slack;
1069 	int i, error;
1070 
1071 	slack = 0;
1072 	if (can_fail)
1073 		slack = UDF_DISC_SLACK;
1074 
1075 	error = 0;
1076 	mutex_enter(&ump->allocate_mutex);
1077 
1078 	/* check if there is enough space available */
1079 	for (i = 0; i < 3; i++) {	/* XXX arbitrary number */
1080 		udf_calc_vpart_freespace(ump, vpart_num, &freeblks);
1081 		if (num_lb + slack < freeblks)
1082 			break;
1083 		/* issue SYNC */
1084 		DPRINTF(RESERVE, ("udf_reserve_space: issuing sync\n"));
1085 		mutex_exit(&ump->allocate_mutex);
1086 		udf_do_sync(ump, FSCRED, 0);
1087 		/* 1/8 second wait */
1088 		kpause("udfsync2", false, hz/8, NULL);
1089 		mutex_enter(&ump->allocate_mutex);
1090 	}
1091 
1092 	/* check if there is enough space available now */
1093 	udf_calc_vpart_freespace(ump, vpart_num, &freeblks);
1094 	if (num_lb + slack >= freeblks) {
1095 		DPRINTF(RESERVE, ("udf_reserve_space: try to redistribute "
1096 				  "partition space\n"));
1097 		DPRINTF(RESERVE, ("\tvpart %d, type %d is full\n",
1098 				vpart_num, ump->vtop_alloc[vpart_num]));
1099 		/* Try to redistribute space if possible */
1100 		udf_collect_free_space_for_vpart(ump, vpart_num, num_lb + slack);
1101 	}
1102 
1103 	/* check if there is enough space available now */
1104 	udf_calc_vpart_freespace(ump, vpart_num, &freeblks);
1105 	if (num_lb + slack <= freeblks) {
1106 		udf_do_reserve_space(ump, udf_node, vpart_num, num_lb);
1107 	} else {
1108 		DPRINTF(RESERVE, ("udf_reserve_space: out of disc space\n"));
1109 		error = ENOSPC;
1110 	}
1111 
1112 	mutex_exit(&ump->allocate_mutex);
1113 	return error;
1114 }
1115 
1116 
1117 void
udf_cleanup_reservation(struct udf_node * udf_node)1118 udf_cleanup_reservation(struct udf_node *udf_node)
1119 {
1120 	struct udf_mount *ump = udf_node->ump;
1121 	int vpart_num;
1122 
1123 	mutex_enter(&ump->allocate_mutex);
1124 
1125 	/* compensate for overlapping blocks */
1126 	DPRINTF(RESERVE, ("UDF: overlapped %d blocks in count\n", udf_node->uncommitted_lbs));
1127 
1128 	vpart_num = udf_get_record_vpart(ump, udf_get_c_type(udf_node));
1129 	udf_do_unreserve_space(ump, udf_node, vpart_num, udf_node->uncommitted_lbs);
1130 
1131 	DPRINTF(RESERVE, ("\ttotal now %d\n", ump->uncommitted_lbs[vpart_num]));
1132 
1133 	/* sanity */
1134 	if (ump->uncommitted_lbs[vpart_num] < 0)
1135 		ump->uncommitted_lbs[vpart_num] = 0;
1136 
1137 	mutex_exit(&ump->allocate_mutex);
1138 }
1139 
1140 /* --------------------------------------------------------------------- */
1141 
1142 /*
1143  * Allocate an extent of given length on given virt. partition. It doesn't
1144  * have to be one stretch.
1145  */
1146 
1147 int
udf_allocate_space(struct udf_mount * ump,struct udf_node * udf_node,int udf_c_type,uint16_t vpart_num,uint32_t num_lb,uint64_t * lmapping)1148 udf_allocate_space(struct udf_mount *ump, struct udf_node *udf_node,
1149 	int udf_c_type, uint16_t vpart_num, uint32_t num_lb, uint64_t *lmapping)
1150 {
1151 	struct mmc_trackinfo *alloc_track, *other_track;
1152 	struct udf_bitmap *bitmap;
1153 	struct part_desc *pdesc;
1154 	struct logvol_int_desc *lvid;
1155 	uint64_t *lmappos;
1156 	uint32_t ptov, lb_num, *freepos, free_lbs;
1157 	int lb_size __diagused, alloc_num_lb;
1158 	int alloc_type, error;
1159 	int is_node;
1160 
1161 	DPRINTF(CALL, ("udf_allocate_space(ctype %d, vpart %d, num_lb %d\n",
1162 		udf_c_type, vpart_num, num_lb));
1163 	mutex_enter(&ump->allocate_mutex);
1164 
1165 	lb_size = udf_rw32(ump->logical_vol->lb_size);
1166 	KASSERT(lb_size == ump->discinfo.sector_size);
1167 
1168 	alloc_type =  ump->vtop_alloc[vpart_num];
1169 	is_node    = (udf_c_type == UDF_C_NODE);
1170 
1171 	lmappos = lmapping;
1172 	error = 0;
1173 	switch (alloc_type) {
1174 	case UDF_ALLOC_VAT :
1175 		/* search empty slot in VAT file */
1176 		KASSERT(num_lb == 1);
1177 		error = udf_search_free_vatloc(ump, &lb_num);
1178 		if (!error) {
1179 			*lmappos = lb_num;
1180 
1181 			/* reserve on the backing sequential partition since
1182 			 * that partition is credited back later */
1183 			udf_do_reserve_space(ump, udf_node,
1184 				ump->vtop[vpart_num], num_lb);
1185 		}
1186 		break;
1187 	case UDF_ALLOC_SEQUENTIAL :
1188 		/* sequential allocation on recordable media */
1189 		/* get partition backing up this vpart_num_num */
1190 		pdesc = ump->partitions[ump->vtop[vpart_num]];
1191 
1192 		/* calculate offset from physical base partition */
1193 		ptov  = udf_rw32(pdesc->start_loc);
1194 
1195 		/* get our track descriptors */
1196 		if (vpart_num == ump->node_part) {
1197 			alloc_track = &ump->metadata_track;
1198 			other_track = &ump->data_track;
1199 		} else {
1200 			alloc_track = &ump->data_track;
1201 			other_track = &ump->metadata_track;
1202 		}
1203 
1204 		/* allocate */
1205 		for (lb_num = 0; lb_num < num_lb; lb_num++) {
1206 			*lmappos++ = alloc_track->next_writable - ptov;
1207 			alloc_track->next_writable++;
1208 			alloc_track->free_blocks--;
1209 		}
1210 
1211 		/* keep other track up-to-date */
1212 		if (alloc_track->tracknr == other_track->tracknr)
1213 			memcpy(other_track, alloc_track,
1214 				sizeof(struct mmc_trackinfo));
1215 		break;
1216 	case UDF_ALLOC_SPACEMAP :
1217 		/* try to allocate on unallocated bits */
1218 		alloc_num_lb = num_lb;
1219 		bitmap = &ump->part_unalloc_bits[vpart_num];
1220 		udf_bitmap_allocate(bitmap, is_node, &alloc_num_lb, lmappos);
1221 		ump->lvclose |= UDF_WRITE_PART_BITMAPS;
1222 
1223 		/* have we allocated all? */
1224 		if (alloc_num_lb) {
1225 			/* TODO convert freed to unalloc and try again */
1226 			/* free allocated piece for now */
1227 			lmappos = lmapping;
1228 			for (lb_num=0; lb_num < num_lb-alloc_num_lb; lb_num++) {
1229 				udf_bitmap_free(bitmap, *lmappos++, 1);
1230 			}
1231 			error = ENOSPC;
1232 		}
1233 		if (!error) {
1234 			/* adjust freecount */
1235 			lvid = ump->logvol_integrity;
1236 			freepos = &lvid->tables[0] + vpart_num;
1237 			free_lbs = udf_rw32(*freepos);
1238 			*freepos = udf_rw32(free_lbs - num_lb);
1239 		}
1240 		break;
1241 	case UDF_ALLOC_METABITMAP :		/* UDF 2.50, 2.60 BluRay-RE */
1242 		/* allocate on metadata unallocated bits */
1243 		alloc_num_lb = num_lb;
1244 		bitmap = &ump->metadata_unalloc_bits;
1245 		udf_bitmap_allocate(bitmap, is_node, &alloc_num_lb, lmappos);
1246 		ump->lvclose |= UDF_WRITE_PART_BITMAPS;
1247 
1248 		/* have we allocated all? */
1249 		if (alloc_num_lb) {
1250 			/* YIKES! TODO we need to extend the metadata partition */
1251 			/* free allocated piece for now */
1252 			lmappos = lmapping;
1253 			for (lb_num=0; lb_num < num_lb-alloc_num_lb; lb_num++) {
1254 				udf_bitmap_free(bitmap, *lmappos++, 1);
1255 			}
1256 			error = ENOSPC;
1257 		}
1258 		if (!error) {
1259 			/* adjust freecount */
1260 			lvid = ump->logvol_integrity;
1261 			freepos = &lvid->tables[0] + vpart_num;
1262 			free_lbs = udf_rw32(*freepos);
1263 			*freepos = udf_rw32(free_lbs - num_lb);
1264 		}
1265 		break;
1266 	case UDF_ALLOC_METASEQUENTIAL :		/* UDF 2.60       BluRay-R  */
1267 	case UDF_ALLOC_RELAXEDSEQUENTIAL :	/* UDF 2.50/~meta BluRay-R  */
1268 		printf("ALERT: udf_allocate_space : allocation %d "
1269 				"not implemented yet!\n", alloc_type);
1270 		/* TODO implement, doesn't have to be contiguous */
1271 		error = ENOSPC;
1272 		break;
1273 	}
1274 
1275 	if (!error) {
1276 		/* credit our partition since we have committed the space */
1277 		udf_do_unreserve_space(ump, udf_node, vpart_num, num_lb);
1278 	}
1279 
1280 #ifdef DEBUG
1281 	if (udf_verbose & UDF_DEBUG_ALLOC) {
1282 		lmappos = lmapping;
1283 		printf("udf_allocate_space, allocated logical lba :\n");
1284 		for (lb_num = 0; lb_num < num_lb; lb_num++) {
1285 			printf("%s %"PRIu64, (lb_num > 0)?",":"",
1286 				*lmappos++);
1287 		}
1288 		printf("\n");
1289 	}
1290 #endif
1291 	mutex_exit(&ump->allocate_mutex);
1292 
1293 	return error;
1294 }
1295 
1296 /* --------------------------------------------------------------------- */
1297 
1298 void
udf_free_allocated_space(struct udf_mount * ump,uint32_t lb_num,uint16_t vpart_num,uint32_t num_lb)1299 udf_free_allocated_space(struct udf_mount *ump, uint32_t lb_num,
1300 	uint16_t vpart_num, uint32_t num_lb)
1301 {
1302 	struct udf_bitmap *bitmap;
1303 	struct logvol_int_desc *lvid;
1304 	uint32_t lb_map, udf_rw32_lbmap;
1305 	uint32_t *freepos, free_lbs;
1306 	int phys_part;
1307 	int error __diagused;
1308 
1309 	DPRINTF(ALLOC, ("udf_free_allocated_space: freeing virt lbnum %d "
1310 			  "part %d + %d sect\n", lb_num, vpart_num, num_lb));
1311 
1312 	/* no use freeing zero length */
1313 	if (num_lb == 0)
1314 		return;
1315 
1316 	mutex_enter(&ump->allocate_mutex);
1317 
1318 	switch (ump->vtop_tp[vpart_num]) {
1319 	case UDF_VTOP_TYPE_PHYS :
1320 	case UDF_VTOP_TYPE_SPARABLE :
1321 		/* free space to freed or unallocated space bitmap */
1322 		phys_part = ump->vtop[vpart_num];
1323 
1324 		/* first try freed space bitmap */
1325 		bitmap    = &ump->part_freed_bits[phys_part];
1326 
1327 		/* if not defined, use unallocated bitmap */
1328 		if (bitmap->bits == NULL)
1329 			bitmap = &ump->part_unalloc_bits[phys_part];
1330 
1331 		/* if no bitmaps are defined, bail out; XXX OK? */
1332 		if (bitmap->bits == NULL)
1333 			break;
1334 
1335 		/* free bits if its defined */
1336 		KASSERT(bitmap->bits);
1337 		ump->lvclose |= UDF_WRITE_PART_BITMAPS;
1338 		udf_bitmap_free(bitmap, lb_num, num_lb);
1339 
1340 		/* adjust freecount */
1341 		lvid = ump->logvol_integrity;
1342 		freepos = &lvid->tables[0] + vpart_num;
1343 		free_lbs = udf_rw32(*freepos);
1344 		*freepos = udf_rw32(free_lbs + num_lb);
1345 		break;
1346 	case UDF_VTOP_TYPE_VIRT :
1347 		/* free this VAT entry */
1348 		KASSERT(num_lb == 1);
1349 
1350 		lb_map = 0xffffffff;
1351 		udf_rw32_lbmap = udf_rw32(lb_map);
1352 		error = udf_vat_write(ump->vat_node,
1353 			(uint8_t *) &udf_rw32_lbmap, 4,
1354 			ump->vat_offset + lb_num * 4);
1355 		KASSERT(error == 0);
1356 		ump->vat_last_free_lb = MIN(ump->vat_last_free_lb, lb_num);
1357 		break;
1358 	case UDF_VTOP_TYPE_META :
1359 		/* free space in the metadata bitmap */
1360 		bitmap = &ump->metadata_unalloc_bits;
1361 		KASSERT(bitmap->bits);
1362 
1363 		ump->lvclose |= UDF_WRITE_PART_BITMAPS;
1364 		udf_bitmap_free(bitmap, lb_num, num_lb);
1365 
1366 		/* adjust freecount */
1367 		lvid = ump->logvol_integrity;
1368 		freepos = &lvid->tables[0] + vpart_num;
1369 		free_lbs = udf_rw32(*freepos);
1370 		*freepos = udf_rw32(free_lbs + num_lb);
1371 		break;
1372 	default:
1373 		printf("ALERT: udf_free_allocated_space : allocation %d "
1374 			"not implemented yet!\n", ump->vtop_tp[vpart_num]);
1375 		break;
1376 	}
1377 
1378 	mutex_exit(&ump->allocate_mutex);
1379 }
1380 
1381 /* --------------------------------------------------------------------- */
1382 
1383 /*
1384  * Special function to synchronise the metadatamirror file when they change on
1385  * resizing. When the metadatafile is actually duplicated, this action is a
1386  * no-op since they describe different extents on the disc.
1387  */
1388 
1389 void
udf_synchronise_metadatamirror_node(struct udf_mount * ump)1390 udf_synchronise_metadatamirror_node(struct udf_mount *ump)
1391 {
1392 	struct udf_node *meta_node, *metamirror_node;
1393 	struct long_ad s_ad;
1394 	uint32_t len, flags;
1395 	int slot, cpy_slot;
1396 	int error, eof;
1397 
1398 	if (ump->metadata_flags & METADATA_DUPLICATED)
1399 		return;
1400 
1401 	meta_node       = ump->metadata_node;
1402 	metamirror_node = ump->metadatamirror_node;
1403 
1404 	/* 1) wipe mirror node */
1405 	udf_wipe_adslots(metamirror_node);
1406 
1407 	/* 2) copy all node descriptors from the meta_node */
1408 	slot     = 0;
1409 	cpy_slot = 0;
1410 	for (;;) {
1411 		udf_get_adslot(meta_node, slot, &s_ad, &eof);
1412 		if (eof)
1413 			break;
1414 		len   = udf_rw32(s_ad.len);
1415 		flags = UDF_EXT_FLAGS(len);
1416 		len   = UDF_EXT_LEN(len);
1417 
1418 		if (flags == UDF_EXT_REDIRECT) {
1419 			slot++;
1420 			continue;
1421 		}
1422 
1423 		error = udf_append_adslot(metamirror_node, &cpy_slot, &s_ad);
1424 		if (error) {
1425 			/* WTF, this shouldn't happen, what to do now? */
1426 			panic("udf_synchronise_metadatamirror_node failed!");
1427 		}
1428 		cpy_slot++;
1429 		slot++;
1430 	}
1431 
1432 	/* 3) adjust metamirror_node size */
1433 	if (meta_node->fe) {
1434 		KASSERT(metamirror_node->fe);
1435 		metamirror_node->fe->inf_len = meta_node->fe->inf_len;
1436 	} else {
1437 		KASSERT(meta_node->efe);
1438 		KASSERT(metamirror_node->efe);
1439 		metamirror_node->efe->inf_len  = meta_node->efe->inf_len;
1440 		metamirror_node->efe->obj_size = meta_node->efe->obj_size;
1441 	}
1442 
1443 	/* for sanity */
1444 	udf_count_alloc_exts(metamirror_node);
1445 }
1446 
1447 /* --------------------------------------------------------------------- */
1448 
1449 /*
1450  * When faced with an out of space but there is still space available on other
1451  * partitions, try to redistribute the space. This is only defined for media
1452  * using Metadata partitions.
1453  *
1454  * There are two formats to deal with. Either its a `normal' metadata
1455  * partition and we can move blocks between a metadata bitmap and its
1456  * companion data spacemap OR its a UDF 2.60 formatted BluRay-R disc with POW
1457  * and a metadata partition.
1458  */
1459 
1460 /* implementation limit: ump->datapart is the companion partition */
1461 static uint32_t
udf_trunc_metadatapart(struct udf_mount * ump,uint32_t num_lb)1462 udf_trunc_metadatapart(struct udf_mount *ump, uint32_t num_lb)
1463 {
1464 	struct udf_node *bitmap_node;
1465 	struct udf_bitmap *bitmap;
1466 	struct space_bitmap_desc *sbd, *new_sbd;
1467 	struct logvol_int_desc *lvid;
1468 	uint64_t inf_len;
1469 	uint64_t meta_free_lbs, data_free_lbs, to_trunc;
1470 	uint32_t *freepos, *sizepos;
1471 	uint32_t unit, lb_size;
1472 	uint16_t meta_vpart_num, data_vpart_num, num_vpart;
1473 	int err __diagused;
1474 
1475 	unit = ump->metadata_alloc_unit_size;
1476 	lb_size = udf_rw32(ump->logical_vol->lb_size);
1477 	lvid = ump->logvol_integrity;
1478 
1479 	/* XXX
1480 	 *
1481 	 * the following checks will fail for BD-R UDF 2.60! but they are
1482 	 * read-only for now anyway! Its even doubtfull if it is to be allowed
1483 	 * for these discs.
1484 	 */
1485 
1486 	/* lookup vpart for metadata partition */
1487 	meta_vpart_num = ump->node_part;
1488 	KASSERT(ump->vtop_alloc[meta_vpart_num] == UDF_ALLOC_METABITMAP);
1489 
1490 	/* lookup vpart for data partition */
1491 	data_vpart_num = ump->data_part;
1492 	KASSERT(ump->vtop_alloc[data_vpart_num] == UDF_ALLOC_SPACEMAP);
1493 
1494 	udf_calc_vpart_freespace(ump, data_vpart_num, &data_free_lbs);
1495 	udf_calc_vpart_freespace(ump, meta_vpart_num, &meta_free_lbs);
1496 
1497 	DPRINTF(RESERVE, ("\tfree space on data partition     %"PRIu64" blks\n", data_free_lbs));
1498 	DPRINTF(RESERVE, ("\tfree space on metadata partition %"PRIu64" blks\n", meta_free_lbs));
1499 
1500 	/* give away some of the free meta space, in unit block sizes */
1501 	to_trunc = meta_free_lbs/4;			/* give out a quarter */
1502 	to_trunc = MAX(to_trunc, num_lb);
1503 	to_trunc = unit * ((to_trunc + unit-1) / unit);	/* round up */
1504 
1505 	/* scale down if needed and bail out when out of space */
1506 	if (to_trunc >= meta_free_lbs)
1507 		return num_lb;
1508 
1509 	/* check extent of bits marked free at the end of the map */
1510 	bitmap = &ump->metadata_unalloc_bits;
1511 	to_trunc = udf_bitmap_check_trunc_free(bitmap, to_trunc);
1512 	to_trunc = unit * (to_trunc / unit);		/* round down again */
1513 	if (to_trunc == 0)
1514 		return num_lb;
1515 
1516 	DPRINTF(RESERVE, ("\ttruncating %"PRIu64" lbs from the metadata bitmap\n",
1517 		to_trunc));
1518 
1519 	/* get length of the metadata bitmap node file */
1520 	bitmap_node = ump->metadatabitmap_node;
1521 	if (bitmap_node->fe) {
1522 		inf_len = udf_rw64(bitmap_node->fe->inf_len);
1523 	} else {
1524 		KASSERT(bitmap_node->efe);
1525 		inf_len = udf_rw64(bitmap_node->efe->inf_len);
1526 	}
1527 	inf_len -= to_trunc/8;
1528 
1529 	/* as per [UDF 2.60/2.2.13.6] : */
1530 	/* 1) update the SBD in the metadata bitmap file */
1531 	sbd = (struct space_bitmap_desc *) bitmap->blob;
1532 	sbd->num_bits  = udf_rw32(udf_rw32(sbd->num_bits)  - to_trunc);
1533 	sbd->num_bytes = udf_rw32(udf_rw32(sbd->num_bytes) - to_trunc/8);
1534 	bitmap->max_offset = udf_rw32(sbd->num_bits);
1535 
1536 	num_vpart = udf_rw32(lvid->num_part);
1537 	freepos = &lvid->tables[0] + meta_vpart_num;
1538 	sizepos = &lvid->tables[0] + num_vpart + meta_vpart_num;
1539 	*freepos = udf_rw32(*freepos) - to_trunc;
1540 	*sizepos = udf_rw32(*sizepos) - to_trunc;
1541 
1542 	/* realloc bitmap for better memory usage */
1543 	new_sbd = realloc(sbd, inf_len, M_UDFVOLD,
1544 		M_CANFAIL | M_WAITOK);
1545 	if (new_sbd) {
1546 		/* update pointers */
1547 		ump->metadata_unalloc_dscr = new_sbd;
1548 		bitmap->blob = (uint8_t *) new_sbd;
1549 	}
1550 	ump->lvclose |= UDF_WRITE_PART_BITMAPS;
1551 
1552 	/*
1553 	 * The truncated space is secured now and can't be allocated anymore.
1554 	 * Release the allocate mutex so we can shrink the nodes the normal
1555 	 * way.
1556 	 */
1557 	mutex_exit(&ump->allocate_mutex);
1558 
1559 	/* 2) trunc the metadata bitmap information file, freeing blocks */
1560 	err = udf_shrink_node(bitmap_node, inf_len);
1561 	KASSERT(err == 0);
1562 
1563 	/* 3) trunc the metadata file and mirror file, freeing blocks */
1564 	inf_len = (uint64_t) udf_rw32(sbd->num_bits) * lb_size;	/* [4/14.12.4] */
1565 	err = udf_shrink_node(ump->metadata_node, inf_len);
1566 	KASSERT(err == 0);
1567 	if (ump->metadatamirror_node) {
1568 		if (ump->metadata_flags & METADATA_DUPLICATED) {
1569 			err = udf_shrink_node(ump->metadatamirror_node, inf_len);
1570 		} else {
1571 			/* extents will be copied on writeout */
1572 		}
1573 		KASSERT(err == 0);
1574 	}
1575 	ump->lvclose |= UDF_WRITE_METAPART_NODES;
1576 
1577 	/* relock before exit */
1578 	mutex_enter(&ump->allocate_mutex);
1579 
1580 	if (to_trunc > num_lb)
1581 		return 0;
1582 	return num_lb - to_trunc;
1583 }
1584 
1585 
1586 static void
udf_sparsify_metadatapart(struct udf_mount * ump,uint32_t num_lb)1587 udf_sparsify_metadatapart(struct udf_mount *ump, uint32_t num_lb)
1588 {
1589 	/* NOT IMPLEMENTED, fail */
1590 }
1591 
1592 
1593 static void
udf_collect_free_space_for_vpart(struct udf_mount * ump,uint16_t vpart_num,uint32_t num_lb)1594 udf_collect_free_space_for_vpart(struct udf_mount *ump,
1595 	uint16_t vpart_num, uint32_t num_lb)
1596 {
1597 	/* allocate mutex is helt */
1598 
1599 	/* only defined for metadata partitions */
1600 	if (ump->vtop_tp[ump->node_part] != UDF_VTOP_TYPE_META) {
1601 		DPRINTF(RESERVE, ("\tcan't grow/shrink; no metadata partitioning\n"));
1602 		return;
1603 	}
1604 
1605 	/* UDF 2.60 BD-R+POW? */
1606 	if (ump->vtop_alloc[ump->node_part] == UDF_ALLOC_METASEQUENTIAL) {
1607 		DPRINTF(RESERVE, ("\tUDF 2.60 BD-R+POW track grow not implemented yet\n"));
1608 		return;
1609 	}
1610 
1611 	if (ump->vtop_tp[vpart_num] == UDF_VTOP_TYPE_META) {
1612 		/* try to grow the meta partition */
1613 		DPRINTF(RESERVE, ("\ttrying to grow the meta partition\n"));
1614 		/* as per [UDF 2.60/2.2.13.5] : extend bitmap and metadata file(s) */
1615 		DPRINTF(NOTIMPL, ("\tgrowing meta partition not implemented yet\n"));
1616 	} else {
1617 		/* try to shrink the metadata partition */
1618 		DPRINTF(RESERVE, ("\ttrying to shrink the meta partition\n"));
1619 		/* as per [UDF 2.60/2.2.13.6] : either trunc or make sparse */
1620 		num_lb = udf_trunc_metadatapart(ump, num_lb);
1621 		if (num_lb)
1622 			udf_sparsify_metadatapart(ump, num_lb);
1623 	}
1624 
1625 	/* allocate mutex should still be helt */
1626 }
1627 
1628 /* --------------------------------------------------------------------- */
1629 
1630 /*
1631  * Allocate a buf on disc for direct write out. The space doesn't have to be
1632  * contiguous as the caller takes care of this.
1633  */
1634 
1635 void
udf_late_allocate_buf(struct udf_mount * ump,struct buf * buf,uint64_t * lmapping,struct long_ad * node_ad_cpy,uint16_t * vpart_nump)1636 udf_late_allocate_buf(struct udf_mount *ump, struct buf *buf,
1637 	uint64_t *lmapping, struct long_ad *node_ad_cpy, uint16_t *vpart_nump)
1638 {
1639 	struct udf_node  *udf_node = VTOI(buf->b_vp);
1640 	int lb_size, udf_c_type;
1641 	int vpart_num, num_lb;
1642 	int error, s;
1643 
1644 	/*
1645 	 * for each sector in the buf, allocate a sector on disc and record
1646 	 * its position in the provided mapping array.
1647 	 *
1648 	 * If its userdata or FIDs, record its location in its node.
1649 	 */
1650 
1651 	lb_size    = udf_rw32(ump->logical_vol->lb_size);
1652 	num_lb     = (buf->b_bcount + lb_size -1) / lb_size;
1653 	udf_c_type = buf->b_udf_c_type;
1654 
1655 	KASSERT(lb_size == ump->discinfo.sector_size);
1656 
1657 	/* select partition to record the buffer on */
1658 	vpart_num = *vpart_nump = udf_get_record_vpart(ump, udf_c_type);
1659 
1660 	if (udf_c_type == UDF_C_NODE) {
1661 		/* if not VAT, its allready allocated */
1662 		if (ump->vtop_alloc[ump->node_part] != UDF_ALLOC_VAT)
1663 			return;
1664 
1665 		/* allocate on its backing sequential partition */
1666 		vpart_num = ump->data_part;
1667 	}
1668 
1669 	/* XXX can this still happen? */
1670 	/* do allocation on the selected partition */
1671 	error = udf_allocate_space(ump, udf_node, udf_c_type,
1672 			vpart_num, num_lb, lmapping);
1673 	if (error) {
1674 		/*
1675 		 * ARGH! we haven't done our accounting right! it should
1676 		 * allways succeed.
1677 		 */
1678 		panic("UDF disc allocation accounting gone wrong");
1679 	}
1680 
1681 	/* If its userdata or FIDs, record its allocation in its node. */
1682 	if ((udf_c_type == UDF_C_USERDATA) ||
1683 	    (udf_c_type == UDF_C_FIDS) ||
1684 	    (udf_c_type == UDF_C_METADATA_SBM))
1685 	{
1686 		udf_record_allocation_in_node(ump, buf, vpart_num, lmapping,
1687 			node_ad_cpy);
1688 		/* decrement our outstanding bufs counter */
1689 		s = splbio();
1690 			udf_node->outstanding_bufs--;
1691 		splx(s);
1692 	}
1693 }
1694 
1695 /* --------------------------------------------------------------------- */
1696 
1697 /*
1698  * Try to merge a1 with the new piece a2. udf_ads_merge returns error when not
1699  * possible (anymore); a2 returns the rest piece.
1700  */
1701 
1702 static int
udf_ads_merge(uint32_t max_len,uint32_t lb_size,struct long_ad * a1,struct long_ad * a2)1703 udf_ads_merge(uint32_t max_len, uint32_t lb_size, struct long_ad *a1, struct long_ad *a2)
1704 {
1705 	uint32_t merge_len;
1706 	uint32_t a1_len, a2_len;
1707 	uint32_t a1_flags, a2_flags;
1708 	uint32_t a1_lbnum, a2_lbnum;
1709 	uint16_t a1_part, a2_part;
1710 
1711 	a1_flags = UDF_EXT_FLAGS(udf_rw32(a1->len));
1712 	a1_len   = UDF_EXT_LEN(udf_rw32(a1->len));
1713 	a1_lbnum = udf_rw32(a1->loc.lb_num);
1714 	a1_part  = udf_rw16(a1->loc.part_num);
1715 
1716 	a2_flags = UDF_EXT_FLAGS(udf_rw32(a2->len));
1717 	a2_len   = UDF_EXT_LEN(udf_rw32(a2->len));
1718 	a2_lbnum = udf_rw32(a2->loc.lb_num);
1719 	a2_part  = udf_rw16(a2->loc.part_num);
1720 
1721 	/* defines same space */
1722 	if (a1_flags != a2_flags)
1723 		return 1;
1724 
1725 	if (a1_flags != UDF_EXT_FREE) {
1726 		/* the same partition */
1727 		if (a1_part != a2_part)
1728 			return 1;
1729 
1730 		/* a2 is successor of a1 */
1731 		if (a1_lbnum * lb_size + a1_len != a2_lbnum * lb_size)
1732 			return 1;
1733 	}
1734 
1735 	/* merge as most from a2 if possible */
1736 	merge_len = MIN(a2_len, max_len - a1_len);
1737 	a1_len   += merge_len;
1738 	a2_len   -= merge_len;
1739 	a2_lbnum += merge_len/lb_size;
1740 
1741 	a1->len = udf_rw32(a1_len | a1_flags);
1742 	a2->len = udf_rw32(a2_len | a2_flags);
1743 	a2->loc.lb_num = udf_rw32(a2_lbnum);
1744 
1745 	if (a2_len > 0)
1746 		return 1;
1747 
1748 	/* there is space over to merge */
1749 	return 0;
1750 }
1751 
1752 /* --------------------------------------------------------------------- */
1753 
1754 static void
udf_wipe_adslots(struct udf_node * udf_node)1755 udf_wipe_adslots(struct udf_node *udf_node)
1756 {
1757 	struct file_entry      *fe;
1758 	struct extfile_entry   *efe;
1759 	struct alloc_ext_entry *ext;
1760 	uint32_t lb_size, dscr_size, l_ea, max_l_ad, crclen;
1761 	uint8_t *data_pos;
1762 	int extnr;
1763 
1764 	lb_size = udf_rw32(udf_node->ump->logical_vol->lb_size);
1765 
1766 	fe  = udf_node->fe;
1767 	efe = udf_node->efe;
1768 	if (fe) {
1769 		dscr_size  = sizeof(struct file_entry) -1;
1770 		l_ea       = udf_rw32(fe->l_ea);
1771 		data_pos = (uint8_t *) fe + dscr_size + l_ea;
1772 	} else {
1773 		dscr_size  = sizeof(struct extfile_entry) -1;
1774 		l_ea       = udf_rw32(efe->l_ea);
1775 		data_pos = (uint8_t *) efe + dscr_size + l_ea;
1776 	}
1777 	max_l_ad = lb_size - dscr_size - l_ea;
1778 
1779 	/* wipe fe/efe */
1780 	memset(data_pos, 0, max_l_ad);
1781 	crclen = dscr_size - UDF_DESC_TAG_LENGTH + l_ea;
1782 	if (fe) {
1783 		fe->l_ad         = udf_rw32(0);
1784 		fe->logblks_rec  = udf_rw64(0);
1785 		fe->tag.desc_crc_len = udf_rw16(crclen);
1786 	} else {
1787 		efe->l_ad        = udf_rw32(0);
1788 		efe->logblks_rec = udf_rw64(0);
1789 		efe->tag.desc_crc_len = udf_rw16(crclen);
1790 	}
1791 
1792 	/* wipe all allocation extent entries */
1793 	for (extnr = 0; extnr < udf_node->num_extensions; extnr++) {
1794 		ext = udf_node->ext[extnr];
1795 		dscr_size  = sizeof(struct alloc_ext_entry) -1;
1796 		data_pos = (uint8_t *) ext->data;
1797 		max_l_ad = lb_size - dscr_size;
1798 		memset(data_pos, 0, max_l_ad);
1799 		ext->l_ad = udf_rw32(0);
1800 
1801 		crclen = dscr_size - UDF_DESC_TAG_LENGTH;
1802 		ext->tag.desc_crc_len = udf_rw16(crclen);
1803 	}
1804 	udf_node->i_flags |= IN_NODE_REBUILD;
1805 }
1806 
1807 /* --------------------------------------------------------------------- */
1808 
1809 void
udf_get_adslot(struct udf_node * udf_node,int slot,struct long_ad * icb,int * eof)1810 udf_get_adslot(struct udf_node *udf_node, int slot, struct long_ad *icb,
1811 	int *eof) {
1812 	struct file_entry      *fe;
1813 	struct extfile_entry   *efe;
1814 	struct alloc_ext_entry *ext;
1815 	struct icb_tag *icbtag;
1816 	struct short_ad *short_ad;
1817 	struct long_ad *long_ad, l_icb;
1818 	uint32_t offset;
1819 	uint32_t dscr_size, l_ea, l_ad, flags;
1820 	uint8_t *data_pos;
1821 	int icbflags, addr_type, adlen, extnr;
1822 
1823 	fe  = udf_node->fe;
1824 	efe = udf_node->efe;
1825 	if (fe) {
1826 		icbtag  = &fe->icbtag;
1827 		dscr_size  = sizeof(struct file_entry) -1;
1828 		l_ea       = udf_rw32(fe->l_ea);
1829 		l_ad       = udf_rw32(fe->l_ad);
1830 		data_pos = (uint8_t *) fe + dscr_size + l_ea;
1831 	} else {
1832 		icbtag  = &efe->icbtag;
1833 		dscr_size  = sizeof(struct extfile_entry) -1;
1834 		l_ea       = udf_rw32(efe->l_ea);
1835 		l_ad       = udf_rw32(efe->l_ad);
1836 		data_pos = (uint8_t *) efe + dscr_size + l_ea;
1837 	}
1838 
1839 	icbflags  = udf_rw16(icbtag->flags);
1840 	addr_type = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
1841 
1842 	/* just in case we're called on an intern, its EOF */
1843 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
1844 		memset(icb, 0, sizeof(struct long_ad));
1845 		*eof = 1;
1846 		return;
1847 	}
1848 
1849 	adlen = 0;
1850 	if (addr_type == UDF_ICB_SHORT_ALLOC) {
1851 		adlen = sizeof(struct short_ad);
1852 	} else if (addr_type == UDF_ICB_LONG_ALLOC) {
1853 		adlen = sizeof(struct long_ad);
1854 	}
1855 
1856 	/* if offset too big, we go to the allocation extensions */
1857 	offset = slot * adlen;
1858 	extnr  = -1;
1859 	while (offset >= l_ad) {
1860 		/* check if our last entry is a redirect */
1861 		if (addr_type == UDF_ICB_SHORT_ALLOC) {
1862 			short_ad = (struct short_ad *) (data_pos + l_ad-adlen);
1863 			l_icb.len          = short_ad->len;
1864 			l_icb.loc.part_num = udf_node->loc.loc.part_num;
1865 			l_icb.loc.lb_num   = short_ad->lb_num;
1866 		} else {
1867 			KASSERT(addr_type == UDF_ICB_LONG_ALLOC);
1868 			long_ad = (struct long_ad *) (data_pos + l_ad-adlen);
1869 			l_icb = *long_ad;
1870 		}
1871 		flags = UDF_EXT_FLAGS(udf_rw32(l_icb.len));
1872 		if (flags != UDF_EXT_REDIRECT) {
1873 			l_ad = 0;	/* force EOF */
1874 			break;
1875 		}
1876 
1877 		/* advance to next extent */
1878 		extnr++;
1879 		if (extnr >= udf_node->num_extensions) {
1880 			l_ad = 0;	/* force EOF */
1881 			break;
1882 		}
1883 		offset = offset - l_ad;
1884 		ext  = udf_node->ext[extnr];
1885 		dscr_size  = sizeof(struct alloc_ext_entry) -1;
1886 		l_ad = udf_rw32(ext->l_ad);
1887 		data_pos = (uint8_t *) ext + dscr_size;
1888 	}
1889 
1890 	/* XXX l_ad == 0 should be enough to check */
1891 	*eof = (offset >= l_ad) || (l_ad == 0);
1892 	if (*eof) {
1893 		DPRINTF(PARANOIDADWLK, ("returning EOF, extnr %d, offset %d, "
1894 			"l_ad %d\n", extnr, offset, l_ad));
1895 		memset(icb, 0, sizeof(struct long_ad));
1896 		return;
1897 	}
1898 
1899 	/* get the element */
1900 	if (addr_type == UDF_ICB_SHORT_ALLOC) {
1901 		short_ad = (struct short_ad *) (data_pos + offset);
1902 		icb->len          = short_ad->len;
1903 		icb->loc.part_num = udf_node->loc.loc.part_num;
1904 		icb->loc.lb_num   = short_ad->lb_num;
1905 	} else if (addr_type == UDF_ICB_LONG_ALLOC) {
1906 		long_ad = (struct long_ad *) (data_pos + offset);
1907 		*icb = *long_ad;
1908 	}
1909 	DPRINTF(PARANOIDADWLK, ("returning element : v %d, lb %d, len %d, "
1910 		"flags %d\n", icb->loc.part_num, icb->loc.lb_num,
1911 		UDF_EXT_LEN(icb->len), UDF_EXT_FLAGS(icb->len)));
1912 }
1913 
1914 /* --------------------------------------------------------------------- */
1915 
1916 int
udf_append_adslot(struct udf_node * udf_node,int * slot,struct long_ad * icb)1917 udf_append_adslot(struct udf_node *udf_node, int *slot, struct long_ad *icb) {
1918 	struct udf_mount *ump = udf_node->ump;
1919 	union dscrptr          *dscr, *extdscr;
1920 	struct file_entry      *fe;
1921 	struct extfile_entry   *efe;
1922 	struct alloc_ext_entry *ext;
1923 	struct icb_tag *icbtag;
1924 	struct short_ad *short_ad;
1925 	struct long_ad *long_ad, o_icb, l_icb;
1926 	uint64_t logblks_rec, *logblks_rec_p;
1927 	uint64_t lmapping;
1928 	uint32_t offset, rest, len, lb_num;
1929 	uint32_t lb_size, dscr_size, l_ea, l_ad, *l_ad_p, max_l_ad, crclen;
1930 	uint32_t flags;
1931 	uint16_t vpart_num;
1932 	uint8_t *data_pos;
1933 	int icbflags, addr_type, adlen, extnr;
1934 	int error;
1935 
1936 	lb_size = udf_rw32(ump->logical_vol->lb_size);
1937 	vpart_num = udf_rw16(udf_node->loc.loc.part_num);
1938 
1939 	/* determine what descriptor we are in */
1940 	fe  = udf_node->fe;
1941 	efe = udf_node->efe;
1942 	if (fe) {
1943 		icbtag  = &fe->icbtag;
1944 		dscr      = (union dscrptr *) fe;
1945 		dscr_size = sizeof(struct file_entry) -1;
1946 
1947 		l_ea      = udf_rw32(fe->l_ea);
1948 		l_ad_p    = &fe->l_ad;
1949 		logblks_rec_p = &fe->logblks_rec;
1950 	} else {
1951 		icbtag    = &efe->icbtag;
1952 		dscr      = (union dscrptr *) efe;
1953 		dscr_size = sizeof(struct extfile_entry) -1;
1954 
1955 		l_ea      = udf_rw32(efe->l_ea);
1956 		l_ad_p    = &efe->l_ad;
1957 		logblks_rec_p = &efe->logblks_rec;
1958 	}
1959 	data_pos  = (uint8_t *) dscr + dscr_size + l_ea;
1960 	max_l_ad = lb_size - dscr_size - l_ea;
1961 
1962 	icbflags  = udf_rw16(icbtag->flags);
1963 	addr_type = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
1964 
1965 	/* just in case we're called on an intern, its EOF */
1966 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
1967 		panic("udf_append_adslot on UDF_ICB_INTERN_ALLOC\n");
1968 	}
1969 
1970 	adlen = 0;
1971 	if (addr_type == UDF_ICB_SHORT_ALLOC) {
1972 		adlen = sizeof(struct short_ad);
1973 	} else if (addr_type == UDF_ICB_LONG_ALLOC) {
1974 		adlen = sizeof(struct long_ad);
1975 	}
1976 
1977 	/* clean up given long_ad since it can be a synthesized one */
1978 	flags = UDF_EXT_FLAGS(udf_rw32(icb->len));
1979 	if (flags == UDF_EXT_FREE) {
1980 		icb->loc.part_num = udf_rw16(0);
1981 		icb->loc.lb_num   = udf_rw32(0);
1982 	}
1983 
1984 	/* if offset too big, we go to the allocation extensions */
1985 	l_ad   = udf_rw32(*l_ad_p);
1986 	offset = (*slot) * adlen;
1987 	extnr  = -1;
1988 	while (offset >= l_ad) {
1989 		/* check if our last entry is a redirect */
1990 		if (addr_type == UDF_ICB_SHORT_ALLOC) {
1991 			short_ad = (struct short_ad *) (data_pos + l_ad-adlen);
1992 			l_icb.len          = short_ad->len;
1993 			l_icb.loc.part_num = udf_node->loc.loc.part_num;
1994 			l_icb.loc.lb_num   = short_ad->lb_num;
1995 		} else {
1996 			KASSERT(addr_type == UDF_ICB_LONG_ALLOC);
1997 			long_ad = (struct long_ad *) (data_pos + l_ad-adlen);
1998 			l_icb = *long_ad;
1999 		}
2000 		flags = UDF_EXT_FLAGS(udf_rw32(l_icb.len));
2001 		if (flags != UDF_EXT_REDIRECT) {
2002 			/* only one past the last one is adressable */
2003 			break;
2004 		}
2005 
2006 		/* advance to next extent */
2007 		extnr++;
2008 		KASSERT(extnr < udf_node->num_extensions);
2009 		offset = offset - l_ad;
2010 
2011 		ext  = udf_node->ext[extnr];
2012 		dscr = (union dscrptr *) ext;
2013 		dscr_size  = sizeof(struct alloc_ext_entry) -1;
2014 		max_l_ad = lb_size - dscr_size;
2015 		l_ad_p = &ext->l_ad;
2016 		l_ad   = udf_rw32(*l_ad_p);
2017 		data_pos = (uint8_t *) ext + dscr_size;
2018 	}
2019 	DPRINTF(PARANOIDADWLK, ("append, ext %d, offset %d, l_ad %d\n",
2020 		extnr, offset, udf_rw32(*l_ad_p)));
2021 	KASSERT(l_ad == udf_rw32(*l_ad_p));
2022 
2023 	/* offset is offset within the current (E)FE/AED */
2024 	l_ad   = udf_rw32(*l_ad_p);
2025 	crclen = udf_rw16(dscr->tag.desc_crc_len);
2026 	logblks_rec = udf_rw64(*logblks_rec_p);
2027 
2028 	/* overwriting old piece? */
2029 	if (offset < l_ad) {
2030 		/* overwrite entry; compensate for the old element */
2031 		if (addr_type == UDF_ICB_SHORT_ALLOC) {
2032 			short_ad = (struct short_ad *) (data_pos + offset);
2033 			o_icb.len          = short_ad->len;
2034 			o_icb.loc.part_num = udf_rw16(0);	/* ignore */
2035 			o_icb.loc.lb_num   = short_ad->lb_num;
2036 		} else if (addr_type == UDF_ICB_LONG_ALLOC) {
2037 			long_ad = (struct long_ad *) (data_pos + offset);
2038 			o_icb = *long_ad;
2039 		} else {
2040 			panic("Invalid address type in udf_append_adslot\n");
2041 		}
2042 
2043 		len = udf_rw32(o_icb.len);
2044 		if (UDF_EXT_FLAGS(len) == UDF_EXT_ALLOCATED) {
2045 			/* adjust counts */
2046 			len = UDF_EXT_LEN(len);
2047 			logblks_rec -= (len + lb_size -1) / lb_size;
2048 		}
2049 	}
2050 
2051 	/* check if we're not appending a redirection */
2052 	flags = UDF_EXT_FLAGS(udf_rw32(icb->len));
2053 	KASSERT(flags != UDF_EXT_REDIRECT);
2054 
2055 	/* round down available space */
2056 	rest = adlen * ((max_l_ad - offset) / adlen);
2057 	if (rest <= adlen) {
2058 		/* have to append aed, see if we already have a spare one */
2059 		extnr++;
2060 		ext = udf_node->ext[extnr];
2061 		l_icb = udf_node->ext_loc[extnr];
2062 		if (ext == NULL) {
2063 			DPRINTF(ALLOC,("adding allocation extent %d\n", extnr));
2064 
2065 			error = udf_reserve_space(ump, NULL, UDF_C_NODE,
2066 					vpart_num, 1, /* can fail */ false);
2067 			if (error) {
2068 				printf("UDF: couldn't reserve space for AED!\n");
2069 				return error;
2070 			}
2071 			error = udf_allocate_space(ump, NULL, UDF_C_NODE,
2072 					vpart_num, 1, &lmapping);
2073 			lb_num = lmapping;
2074 			if (error)
2075 				panic("UDF: couldn't allocate AED!\n");
2076 
2077 			/* initialise pointer to location */
2078 			memset(&l_icb, 0, sizeof(struct long_ad));
2079 			l_icb.len = udf_rw32(lb_size | UDF_EXT_REDIRECT);
2080 			l_icb.loc.lb_num   = udf_rw32(lb_num);
2081 			l_icb.loc.part_num = udf_rw16(vpart_num);
2082 
2083 			/* create new aed descriptor */
2084 			udf_create_logvol_dscr(ump, udf_node, &l_icb, &extdscr);
2085 			ext = &extdscr->aee;
2086 
2087 			udf_inittag(ump, &ext->tag, TAGID_ALLOCEXTENT, lb_num);
2088 			dscr_size  = sizeof(struct alloc_ext_entry) -1;
2089 			max_l_ad = lb_size - dscr_size;
2090 			memset(ext->data, 0, max_l_ad);
2091 			ext->l_ad = udf_rw32(0);
2092 			ext->tag.desc_crc_len =
2093 				udf_rw16(dscr_size - UDF_DESC_TAG_LENGTH);
2094 
2095 			/* declare aed */
2096 			udf_node->num_extensions++;
2097 			udf_node->ext_loc[extnr] = l_icb;
2098 			udf_node->ext[extnr] = ext;
2099 		}
2100 		/* add redirect and adjust l_ad and crclen for old descr */
2101 		if (addr_type == UDF_ICB_SHORT_ALLOC) {
2102 			short_ad = (struct short_ad *) (data_pos + offset);
2103 			short_ad->len    = l_icb.len;
2104 			short_ad->lb_num = l_icb.loc.lb_num;
2105 		} else if (addr_type == UDF_ICB_LONG_ALLOC) {
2106 			long_ad = (struct long_ad *) (data_pos + offset);
2107 			*long_ad = l_icb;
2108 		}
2109 		l_ad   += adlen;
2110 		crclen += adlen;
2111 		dscr->tag.desc_crc_len = udf_rw16(crclen);
2112 		*l_ad_p = udf_rw32(l_ad);
2113 
2114 		/* advance to the new extension */
2115 		KASSERT(ext != NULL);
2116 		dscr = (union dscrptr *) ext;
2117 		dscr_size  = sizeof(struct alloc_ext_entry) -1;
2118 		max_l_ad = lb_size - dscr_size;
2119 		data_pos = (uint8_t *) dscr + dscr_size;
2120 
2121 		l_ad_p = &ext->l_ad;
2122 		l_ad   = udf_rw32(*l_ad_p);
2123 		crclen = udf_rw16(dscr->tag.desc_crc_len);
2124 		offset = 0;
2125 
2126 		/* adjust callees slot count for link insert */
2127 		*slot += 1;
2128 	}
2129 
2130 	/* write out the element */
2131 	DPRINTF(PARANOIDADWLK, ("adding element : %p : v %d, lb %d, "
2132 			"len %d, flags %d\n", data_pos + offset,
2133 			icb->loc.part_num, icb->loc.lb_num,
2134 			UDF_EXT_LEN(icb->len), UDF_EXT_FLAGS(icb->len)));
2135 	if (addr_type == UDF_ICB_SHORT_ALLOC) {
2136 		short_ad = (struct short_ad *) (data_pos + offset);
2137 		short_ad->len    = icb->len;
2138 		short_ad->lb_num = icb->loc.lb_num;
2139 	} else if (addr_type == UDF_ICB_LONG_ALLOC) {
2140 		long_ad = (struct long_ad *) (data_pos + offset);
2141 		*long_ad = *icb;
2142 	}
2143 
2144 	/* adjust logblks recorded count */
2145 	len = udf_rw32(icb->len);
2146 	flags = UDF_EXT_FLAGS(len);
2147 	if (flags == UDF_EXT_ALLOCATED)
2148 		logblks_rec += (UDF_EXT_LEN(len) + lb_size -1) / lb_size;
2149 	*logblks_rec_p = udf_rw64(logblks_rec);
2150 
2151 	/* adjust l_ad and crclen when needed */
2152 	if (offset >= l_ad) {
2153 		l_ad   += adlen;
2154 		crclen += adlen;
2155 		dscr->tag.desc_crc_len = udf_rw16(crclen);
2156 		*l_ad_p = udf_rw32(l_ad);
2157 	}
2158 
2159 	return 0;
2160 }
2161 
2162 /* --------------------------------------------------------------------- */
2163 
2164 static void
udf_count_alloc_exts(struct udf_node * udf_node)2165 udf_count_alloc_exts(struct udf_node *udf_node)
2166 {
2167 	struct long_ad s_ad;
2168 	uint32_t lb_num, len, flags;
2169 	uint16_t vpart_num;
2170 	int slot, eof;
2171 	int num_extents, extnr;
2172 
2173 	if (udf_node->num_extensions == 0)
2174 		return;
2175 
2176 	/* count number of allocation extents in use */
2177 	num_extents = 0;
2178 	slot = 0;
2179 	for (;;) {
2180 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
2181 		if (eof)
2182 			break;
2183 		len   = udf_rw32(s_ad.len);
2184 		flags = UDF_EXT_FLAGS(len);
2185 
2186 		if (flags == UDF_EXT_REDIRECT)
2187 			num_extents++;
2188 
2189 		slot++;
2190 	}
2191 
2192 	DPRINTF(ALLOC, ("udf_count_alloc_ext counted %d live extents\n",
2193 		num_extents));
2194 
2195 	/* XXX choice: we could delay freeing them on node writeout */
2196 	/* free excess entries */
2197 	extnr = num_extents;
2198 	for (;extnr < udf_node->num_extensions; extnr++) {
2199 		DPRINTF(ALLOC, ("freeing alloc ext %d\n", extnr));
2200 		/* free dscriptor */
2201 		s_ad = udf_node->ext_loc[extnr];
2202 		udf_free_logvol_dscr(udf_node->ump, &s_ad,
2203 			udf_node->ext[extnr]);
2204 		udf_node->ext[extnr] = NULL;
2205 
2206 		/* free disc space */
2207 		lb_num    = udf_rw32(s_ad.loc.lb_num);
2208 		vpart_num = udf_rw16(s_ad.loc.part_num);
2209 		udf_free_allocated_space(udf_node->ump, lb_num, vpart_num, 1);
2210 
2211 		memset(&udf_node->ext_loc[extnr], 0, sizeof(struct long_ad));
2212 	}
2213 
2214 	/* set our new number of allocation extents */
2215 	udf_node->num_extensions = num_extents;
2216 }
2217 
2218 
2219 /* --------------------------------------------------------------------- */
2220 
2221 /*
2222  * Adjust the node's allocation descriptors to reflect the new mapping; do
2223  * take note that we might glue to existing allocation descriptors.
2224  *
2225  * XXX Note there can only be one allocation being recorded/mount; maybe
2226  * explicit allocation in shedule thread?
2227  */
2228 
2229 static void
udf_record_allocation_in_node(struct udf_mount * ump,struct buf * buf,uint16_t vpart_num,uint64_t * mapping,struct long_ad * node_ad_cpy)2230 udf_record_allocation_in_node(struct udf_mount *ump, struct buf *buf,
2231 	uint16_t vpart_num, uint64_t *mapping, struct long_ad *node_ad_cpy)
2232 {
2233 	struct vnode    *vp = buf->b_vp;
2234 	struct udf_node *udf_node = VTOI(vp);
2235 	struct file_entry      *fe;
2236 	struct extfile_entry   *efe;
2237 	struct icb_tag  *icbtag;
2238 	struct long_ad   s_ad, c_ad;
2239 	uint64_t inflen, from, till;
2240 	uint64_t foffset, end_foffset, restart_foffset;
2241 	uint64_t orig_inflen, orig_lbrec, new_inflen, new_lbrec;
2242 	uint32_t max_len;
2243 	uint32_t num_lb, len, flags, lb_num;
2244 	uint32_t run_start;
2245 	uint32_t slot_offset, replace_len, replace;
2246 	int addr_type, icbflags;
2247 //	int udf_c_type = buf->b_udf_c_type;
2248 	int lb_size, run_length, eof;
2249 	int slot, cpy_slot, cpy_slots, restart_slot;
2250 	int error;
2251 
2252 	DPRINTF(ALLOC, ("udf_record_allocation_in_node\n"));
2253 
2254 #if 0
2255 	/* XXX disable sanity check for now */
2256 	/* sanity check ... should be panic ? */
2257 	if ((udf_c_type != UDF_C_USERDATA) && (udf_c_type != UDF_C_FIDS))
2258 		return;
2259 #endif
2260 
2261 	lb_size = udf_rw32(udf_node->ump->logical_vol->lb_size);
2262 	max_len = ((UDF_EXT_MAXLEN / lb_size) * lb_size);
2263 
2264 	/* do the job */
2265 	UDF_LOCK_NODE(udf_node, 0);	/* XXX can deadlock ? */
2266 	udf_node_sanity_check(udf_node, &orig_inflen, &orig_lbrec);
2267 
2268 	fe  = udf_node->fe;
2269 	efe = udf_node->efe;
2270 	if (fe) {
2271 		icbtag = &fe->icbtag;
2272 		inflen = udf_rw64(fe->inf_len);
2273 	} else {
2274 		icbtag = &efe->icbtag;
2275 		inflen = udf_rw64(efe->inf_len);
2276 	}
2277 
2278 	/* do check if `till' is not past file information length */
2279 	from = buf->b_lblkno * lb_size;
2280 	till = MIN(inflen, from + buf->b_resid);
2281 
2282 	num_lb = (till - from + lb_size -1) / lb_size;
2283 
2284 	DPRINTF(ALLOC, ("record allocation from %"PRIu64" + %d\n", from, buf->b_bcount));
2285 
2286 	icbflags  = udf_rw16(icbtag->flags);
2287 	addr_type = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
2288 
2289 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
2290 		/* nothing to do */
2291 		/* XXX clean up rest of node? just in case? */
2292 		UDF_UNLOCK_NODE(udf_node, 0);
2293 		return;
2294 	}
2295 
2296 	slot     = 0;
2297 	cpy_slot = 0;
2298 	foffset  = 0;
2299 
2300 	/* 1) copy till first overlap piece to the rewrite buffer */
2301 	for (;;) {
2302 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
2303 		if (eof) {
2304 			DPRINTF(WRITE,
2305 				("Record allocation in node "
2306 				 "failed: encountered EOF\n"));
2307 			UDF_UNLOCK_NODE(udf_node, 0);
2308 			buf->b_error = EINVAL;
2309 			return;
2310 		}
2311 		len   = udf_rw32(s_ad.len);
2312 		flags = UDF_EXT_FLAGS(len);
2313 		len   = UDF_EXT_LEN(len);
2314 
2315 		if (flags == UDF_EXT_REDIRECT) {
2316 			slot++;
2317 			continue;
2318 		}
2319 
2320 		end_foffset = foffset + len;
2321 		if (end_foffset > from)
2322 			break;	/* found */
2323 
2324 		node_ad_cpy[cpy_slot++] = s_ad;
2325 
2326 		DPRINTF(ALLOC, ("\t1: vp %d, lb %d, len %d, flags %d "
2327 			"-> stack\n",
2328 			udf_rw16(s_ad.loc.part_num),
2329 			udf_rw32(s_ad.loc.lb_num),
2330 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
2331 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2332 
2333 		foffset = end_foffset;
2334 		slot++;
2335 	}
2336 	restart_slot    = slot;
2337 	restart_foffset = foffset;
2338 
2339 	/* 2) trunc overlapping slot at overlap and copy it */
2340 	slot_offset = from - foffset;
2341 	if (slot_offset > 0) {
2342 		DPRINTF(ALLOC, ("\tslot_offset = %d, flags = %d (%d)\n",
2343 				slot_offset, flags >> 30, flags));
2344 
2345 		s_ad.len = udf_rw32(slot_offset | flags);
2346 		node_ad_cpy[cpy_slot++] = s_ad;
2347 
2348 		DPRINTF(ALLOC, ("\t2: vp %d, lb %d, len %d, flags %d "
2349 			"-> stack\n",
2350 			udf_rw16(s_ad.loc.part_num),
2351 			udf_rw32(s_ad.loc.lb_num),
2352 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
2353 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2354 	}
2355 	foffset += slot_offset;
2356 
2357 	/* 3) insert new mappings */
2358 	memset(&s_ad, 0, sizeof(struct long_ad));
2359 	lb_num = 0;
2360 	for (lb_num = 0; lb_num < num_lb; lb_num++) {
2361 		run_start  = mapping[lb_num];
2362 		run_length = 1;
2363 		while (lb_num < num_lb-1) {
2364 			if (mapping[lb_num+1] != mapping[lb_num]+1)
2365 				if (mapping[lb_num+1] != mapping[lb_num])
2366 					break;
2367 			run_length++;
2368 			lb_num++;
2369 		}
2370 		/* insert slot for this mapping */
2371 		len = run_length * lb_size;
2372 
2373 		/* bounds checking */
2374 		if (foffset + len > till)
2375 			len = till - foffset;
2376 		KASSERT(foffset + len <= inflen);
2377 
2378 		s_ad.len = udf_rw32(len | UDF_EXT_ALLOCATED);
2379 		s_ad.loc.part_num = udf_rw16(vpart_num);
2380 		s_ad.loc.lb_num   = udf_rw32(run_start);
2381 
2382 		foffset += len;
2383 
2384 		/* paranoia */
2385 		if (len == 0) {
2386 			DPRINTF(WRITE,
2387 				("Record allocation in node "
2388 				 "failed: insert failed\n"));
2389 			UDF_UNLOCK_NODE(udf_node, 0);
2390 			buf->b_error = EINVAL;
2391 			return;
2392 		}
2393 		node_ad_cpy[cpy_slot++] = s_ad;
2394 
2395 		DPRINTF(ALLOC, ("\t3: insert new mapping vp %d lb %d, len %d, "
2396 				"flags %d -> stack\n",
2397 			udf_rw16(s_ad.loc.part_num), udf_rw32(s_ad.loc.lb_num),
2398 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
2399 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2400 	}
2401 
2402 	/* 4) pop replaced length */
2403 	slot    = restart_slot;
2404 	foffset = restart_foffset;
2405 
2406 	replace_len = till - foffset;	/* total amount of bytes to pop */
2407 	slot_offset = from - foffset;	/* offset in first encounted slot */
2408 	KASSERT((slot_offset % lb_size) == 0);
2409 
2410 	for (;;) {
2411 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
2412 		if (eof)
2413 			break;
2414 
2415 		len    = udf_rw32(s_ad.len);
2416 		flags  = UDF_EXT_FLAGS(len);
2417 		len    = UDF_EXT_LEN(len);
2418 		lb_num = udf_rw32(s_ad.loc.lb_num);
2419 
2420 		if (flags == UDF_EXT_REDIRECT) {
2421 			slot++;
2422 			continue;
2423 		}
2424 
2425 		DPRINTF(ALLOC, ("\t4i: got slot %d, slot_offset %d, "
2426 				"replace_len %d, "
2427 				"vp %d, lb %d, len %d, flags %d\n",
2428 			slot, slot_offset, replace_len,
2429 			udf_rw16(s_ad.loc.part_num),
2430 			udf_rw32(s_ad.loc.lb_num),
2431 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
2432 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2433 
2434 		/* adjust for slot offset */
2435 		if (slot_offset) {
2436 			DPRINTF(ALLOC, ("\t4s: skipping %d\n", slot_offset));
2437 			lb_num += slot_offset / lb_size;
2438 			len    -= slot_offset;
2439 			foffset += slot_offset;
2440 			replace_len -= slot_offset;
2441 
2442 			/* mark adjusted */
2443 			slot_offset = 0;
2444 		}
2445 
2446 		/* advance for (the rest of) this slot */
2447 		replace = MIN(len, replace_len);
2448 		DPRINTF(ALLOC, ("\t4d: replacing %d\n", replace));
2449 
2450 		/* advance for this slot */
2451 		if (replace) {
2452 			/* note: dont round DOWN on num_lb since we then
2453 			 * forget the last partial one */
2454 			num_lb = (replace + lb_size - 1) / lb_size;
2455 			if (flags != UDF_EXT_FREE) {
2456 				udf_free_allocated_space(ump, lb_num,
2457 					udf_rw16(s_ad.loc.part_num), num_lb);
2458 			}
2459 			lb_num      += num_lb;
2460 			len         -= replace;
2461 			foffset     += replace;
2462 			replace_len -= replace;
2463 		}
2464 
2465 		/* do we have a slot tail ? */
2466 		if (len) {
2467 			KASSERT(foffset % lb_size == 0);
2468 
2469 			/* we arrived at our point, push remainder */
2470 			s_ad.len        = udf_rw32(len | flags);
2471 			s_ad.loc.lb_num = udf_rw32(lb_num);
2472 			if (flags == UDF_EXT_FREE)
2473 				s_ad.loc.lb_num = udf_rw32(0);
2474 			node_ad_cpy[cpy_slot++] = s_ad;
2475 			foffset += len;
2476 			slot++;
2477 
2478 			DPRINTF(ALLOC, ("\t4: vp %d, lb %d, len %d, flags %d "
2479 				"-> stack\n",
2480 				udf_rw16(s_ad.loc.part_num),
2481 				udf_rw32(s_ad.loc.lb_num),
2482 				UDF_EXT_LEN(udf_rw32(s_ad.len)),
2483 				UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2484 			break;
2485 		}
2486 
2487 		slot++;
2488 	}
2489 
2490 	/* 5) copy remainder */
2491 	for (;;) {
2492 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
2493 		if (eof)
2494 			break;
2495 
2496 		len   = udf_rw32(s_ad.len);
2497 		flags = UDF_EXT_FLAGS(len);
2498 		len   = UDF_EXT_LEN(len);
2499 
2500 		if (flags == UDF_EXT_REDIRECT) {
2501 			slot++;
2502 			continue;
2503 		}
2504 
2505 		node_ad_cpy[cpy_slot++] = s_ad;
2506 
2507 		DPRINTF(ALLOC, ("\t5: insert new mapping "
2508 			"vp %d lb %d, len %d, flags %d "
2509 			"-> stack\n",
2510 		udf_rw16(s_ad.loc.part_num),
2511 		udf_rw32(s_ad.loc.lb_num),
2512 		UDF_EXT_LEN(udf_rw32(s_ad.len)),
2513 		UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2514 
2515 		slot++;
2516 	}
2517 
2518 	/* 6) reset node descriptors */
2519 	udf_wipe_adslots(udf_node);
2520 
2521 	/* 7) copy back extents; merge when possible. Recounting on the fly */
2522 	cpy_slots = cpy_slot;
2523 
2524 	c_ad = node_ad_cpy[0];
2525 	slot = 0;
2526 	DPRINTF(ALLOC, ("\t7s: stack -> got mapping vp %d "
2527 		"lb %d, len %d, flags %d\n",
2528 	udf_rw16(c_ad.loc.part_num),
2529 	udf_rw32(c_ad.loc.lb_num),
2530 	UDF_EXT_LEN(udf_rw32(c_ad.len)),
2531 	UDF_EXT_FLAGS(udf_rw32(c_ad.len)) >> 30));
2532 
2533 	for (cpy_slot = 1; cpy_slot < cpy_slots; cpy_slot++) {
2534 		s_ad = node_ad_cpy[cpy_slot];
2535 
2536 		DPRINTF(ALLOC, ("\t7i: stack -> got mapping vp %d "
2537 			"lb %d, len %d, flags %d\n",
2538 		udf_rw16(s_ad.loc.part_num),
2539 		udf_rw32(s_ad.loc.lb_num),
2540 		UDF_EXT_LEN(udf_rw32(s_ad.len)),
2541 		UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
2542 
2543 		/* see if we can merge */
2544 		if (udf_ads_merge(max_len, lb_size, &c_ad, &s_ad)) {
2545 			/* not mergable (anymore) */
2546 			DPRINTF(ALLOC, ("\t7: appending vp %d lb %d, "
2547 				"len %d, flags %d\n",
2548 			udf_rw16(c_ad.loc.part_num),
2549 			udf_rw32(c_ad.loc.lb_num),
2550 			UDF_EXT_LEN(udf_rw32(c_ad.len)),
2551 			UDF_EXT_FLAGS(udf_rw32(c_ad.len)) >> 30));
2552 
2553 			error = udf_append_adslot(udf_node, &slot, &c_ad);
2554 			if (error) {
2555 				buf->b_error = error;
2556 				goto out;
2557 			}
2558 			c_ad = s_ad;
2559 			slot++;
2560 		}
2561 	}
2562 
2563 	/* 8) push rest slot (if any) */
2564 	if (UDF_EXT_LEN(c_ad.len) > 0) {
2565 		DPRINTF(ALLOC, ("\t8: last append vp %d lb %d, "
2566 				"len %d, flags %d\n",
2567 		udf_rw16(c_ad.loc.part_num),
2568 		udf_rw32(c_ad.loc.lb_num),
2569 		UDF_EXT_LEN(udf_rw32(c_ad.len)),
2570 		UDF_EXT_FLAGS(udf_rw32(c_ad.len)) >> 30));
2571 
2572 		error = udf_append_adslot(udf_node, &slot, &c_ad);
2573 		if (error) {
2574 			buf->b_error = error;
2575 			goto out;
2576 		}
2577 	}
2578 
2579 out:
2580 	udf_count_alloc_exts(udf_node);
2581 
2582 	/* the node's descriptors should now be sane */
2583 	udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
2584 	UDF_UNLOCK_NODE(udf_node, 0);
2585 
2586 	KASSERT(orig_inflen == new_inflen);
2587 	KASSERT(new_lbrec >= orig_lbrec);
2588 
2589 	return;
2590 }
2591 
2592 /* --------------------------------------------------------------------- */
2593 
2594 int
udf_grow_node(struct udf_node * udf_node,uint64_t new_size)2595 udf_grow_node(struct udf_node *udf_node, uint64_t new_size)
2596 {
2597 	struct vnode *vp = udf_node->vnode;
2598 	struct udf_mount *ump = udf_node->ump;
2599 	struct file_entry    *fe;
2600 	struct extfile_entry *efe;
2601 	struct icb_tag  *icbtag;
2602 	struct long_ad c_ad, s_ad;
2603 	uint64_t size_diff, old_size, inflen, objsize, chunk, append_len;
2604 	uint64_t foffset, end_foffset;
2605 	uint64_t orig_inflen, orig_lbrec, new_inflen, new_lbrec;
2606 	uint32_t lb_size, unit_size, dscr_size, crclen, lastblock_grow;
2607 	uint32_t icbflags, len, flags, max_len;
2608 	uint32_t max_l_ad, l_ad, l_ea;
2609 	uint16_t my_part, dst_part;
2610 	uint8_t *evacuated_data;
2611 	int addr_type;
2612 	int slot;
2613 	int eof, error;
2614 
2615 	DPRINTF(ALLOC, ("udf_grow_node\n"));
2616 
2617 	UDF_LOCK_NODE(udf_node, 0);
2618 	udf_node_sanity_check(udf_node, &orig_inflen, &orig_lbrec);
2619 
2620 	lb_size = udf_rw32(ump->logical_vol->lb_size);
2621 
2622 	/* max_len in unit's IFF its a metadata node or metadata mirror node */
2623 	unit_size = lb_size;
2624 	if ((udf_node == ump->metadata_node) || (udf_node == ump->metadatamirror_node))
2625 		unit_size = ump->metadata_alloc_unit_size * lb_size;
2626 	max_len = ((UDF_EXT_MAXLEN / unit_size) * unit_size);
2627 
2628 	fe  = udf_node->fe;
2629 	efe = udf_node->efe;
2630 	if (fe) {
2631 		icbtag  = &fe->icbtag;
2632 		inflen  = udf_rw64(fe->inf_len);
2633 		objsize = inflen;
2634 		dscr_size  = sizeof(struct file_entry) -1;
2635 		l_ea       = udf_rw32(fe->l_ea);
2636 		l_ad       = udf_rw32(fe->l_ad);
2637 	} else {
2638 		icbtag  = &efe->icbtag;
2639 		inflen  = udf_rw64(efe->inf_len);
2640 		objsize = udf_rw64(efe->obj_size);
2641 		dscr_size  = sizeof(struct extfile_entry) -1;
2642 		l_ea       = udf_rw32(efe->l_ea);
2643 		l_ad       = udf_rw32(efe->l_ad);
2644 	}
2645 	max_l_ad = lb_size - dscr_size - l_ea;
2646 
2647 	icbflags   = udf_rw16(icbtag->flags);
2648 	addr_type  = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
2649 
2650 	old_size  = inflen;
2651 	size_diff = new_size - old_size;
2652 
2653 	DPRINTF(ALLOC, ("\tfrom %"PRIu64" to %"PRIu64"\n", old_size, new_size));
2654 
2655 	evacuated_data = NULL;
2656 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
2657 		if (l_ad + size_diff <= max_l_ad) {
2658 			/* only reflect size change directly in the node */
2659 			inflen  += size_diff;
2660 			objsize += size_diff;
2661 			l_ad    += size_diff;
2662 			crclen = dscr_size - UDF_DESC_TAG_LENGTH + l_ea + l_ad;
2663 			if (fe) {
2664 				fe->inf_len   = udf_rw64(inflen);
2665 				fe->l_ad      = udf_rw32(l_ad);
2666 				fe->tag.desc_crc_len = udf_rw16(crclen);
2667 			} else {
2668 				efe->inf_len  = udf_rw64(inflen);
2669 				efe->obj_size = udf_rw64(objsize);
2670 				efe->l_ad     = udf_rw32(l_ad);
2671 				efe->tag.desc_crc_len = udf_rw16(crclen);
2672 			}
2673 			error = 0;
2674 
2675 			/* set new size for uvm */
2676 			uvm_vnp_setwritesize(vp, new_size);
2677 			uvm_vnp_setsize(vp, new_size);
2678 
2679 #if 0
2680 			/* zero append space in buffer */
2681 			ubc_zerorange(&vp->v_uobj, old_size,
2682 			    new_size - old_size, UBC_UNMAP_FLAG(vp));
2683 #endif
2684 
2685 			udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
2686 
2687 			/* unlock */
2688 			UDF_UNLOCK_NODE(udf_node, 0);
2689 
2690 			KASSERT(new_inflen == orig_inflen + size_diff);
2691 			KASSERT(new_lbrec == orig_lbrec);
2692 			KASSERT(new_lbrec == 0);
2693 			return 0;
2694 		}
2695 
2696 		DPRINTF(ALLOC, ("\tCONVERT from internal\n"));
2697 
2698 		if (old_size > 0) {
2699 			/* allocate some space and copy in the stuff to keep */
2700 			evacuated_data = malloc(lb_size, M_UDFTEMP, M_WAITOK);
2701 			memset(evacuated_data, 0, lb_size);
2702 
2703 			/* node is locked, so safe to exit mutex */
2704 			UDF_UNLOCK_NODE(udf_node, 0);
2705 
2706 			/* read in using the `normal' vn_rdwr() */
2707 			error = vn_rdwr(UIO_READ, udf_node->vnode,
2708 					evacuated_data, old_size, 0,
2709 					UIO_SYSSPACE, IO_ALTSEMANTICS | IO_NODELOCKED,
2710 					FSCRED, NULL, NULL);
2711 
2712 			/* enter again */
2713 			UDF_LOCK_NODE(udf_node, 0);
2714 		}
2715 
2716 		/* convert to a normal alloc and select type */
2717 		my_part  = udf_rw16(udf_node->loc.loc.part_num);
2718 		dst_part = udf_get_record_vpart(ump, udf_get_c_type(udf_node));
2719 		addr_type = UDF_ICB_SHORT_ALLOC;
2720 		if (dst_part != my_part)
2721 			addr_type = UDF_ICB_LONG_ALLOC;
2722 
2723 		icbflags &= ~UDF_ICB_TAG_FLAGS_ALLOC_MASK;
2724 		icbflags |= addr_type;
2725 		icbtag->flags = udf_rw16(icbflags);
2726 
2727 		/* wipe old descriptor space */
2728 		udf_wipe_adslots(udf_node);
2729 
2730 		memset(&c_ad, 0, sizeof(struct long_ad));
2731 		c_ad.len          = udf_rw32(old_size | UDF_EXT_FREE);
2732 		c_ad.loc.part_num = udf_rw16(0); /* not relevant */
2733 		c_ad.loc.lb_num   = udf_rw32(0); /* not relevant */
2734 
2735 		slot = 0;
2736 	} else {
2737 		/* goto the last entry (if any) */
2738 		slot     = 0;
2739 		foffset  = 0;
2740 		memset(&c_ad, 0, sizeof(struct long_ad));
2741 		for (;;) {
2742 			udf_get_adslot(udf_node, slot, &c_ad, &eof);
2743 			if (eof)
2744 				break;
2745 
2746 			len   = udf_rw32(c_ad.len);
2747 			flags = UDF_EXT_FLAGS(len);
2748 			len   = UDF_EXT_LEN(len);
2749 
2750 			end_foffset = foffset + len;
2751 			if (flags != UDF_EXT_REDIRECT)
2752 				foffset = end_foffset;
2753 
2754 			slot++;
2755 		}
2756 		/* at end of adslots */
2757 
2758 		/* special case if the old size was zero, then there is no last slot */
2759 		if (old_size == 0) {
2760 			c_ad.len          = udf_rw32(0 | UDF_EXT_FREE);
2761 			c_ad.loc.part_num = udf_rw16(0); /* not relevant */
2762 			c_ad.loc.lb_num   = udf_rw32(0); /* not relevant */
2763 		} else {
2764 			/* refetch last slot */
2765 			slot--;
2766 			udf_get_adslot(udf_node, slot, &c_ad, &eof);
2767 		}
2768 	}
2769 
2770 	/*
2771 	 * If the length of the last slot is not a multiple of lb_size, adjust
2772 	 * length so that it is; don't forget to adjust `append_len'! relevant for
2773 	 * extending existing files
2774 	 */
2775 	len   = udf_rw32(c_ad.len);
2776 	flags = UDF_EXT_FLAGS(len);
2777 	len   = UDF_EXT_LEN(len);
2778 
2779 	lastblock_grow = 0;
2780 	if (len % lb_size > 0) {
2781 		lastblock_grow = lb_size - (len % lb_size);
2782 		lastblock_grow = MIN(size_diff, lastblock_grow);
2783 		len += lastblock_grow;
2784 		c_ad.len = udf_rw32(len | flags);
2785 
2786 		/* TODO zero appened space in buffer! */
2787 		/* using ubc_zerorange(&vp->v_uobj, old_size, */
2788 		/*    new_size - old_size, UBC_UNMAP_FLAG(vp)); ? */
2789 	}
2790 	memset(&s_ad, 0, sizeof(struct long_ad));
2791 
2792 	/* size_diff can be bigger than allowed, so grow in chunks */
2793 	append_len = size_diff - lastblock_grow;
2794 	while (append_len > 0) {
2795 		chunk = MIN(append_len, max_len);
2796 		s_ad.len = udf_rw32(chunk | UDF_EXT_FREE);
2797 		s_ad.loc.part_num = udf_rw16(0);
2798 		s_ad.loc.lb_num   = udf_rw32(0);
2799 
2800 		if (udf_ads_merge(max_len, lb_size, &c_ad, &s_ad)) {
2801 			/* not mergable (anymore) */
2802 			error = udf_append_adslot(udf_node, &slot, &c_ad);
2803 			if (error)
2804 				goto errorout;
2805 			slot++;
2806 			c_ad = s_ad;
2807 			memset(&s_ad, 0, sizeof(struct long_ad));
2808 		}
2809 		append_len -= chunk;
2810 	}
2811 
2812 	/* if there is a rest piece in the accumulator, append it */
2813 	if (UDF_EXT_LEN(udf_rw32(c_ad.len)) > 0) {
2814 		error = udf_append_adslot(udf_node, &slot, &c_ad);
2815 		if (error)
2816 			goto errorout;
2817 		slot++;
2818 	}
2819 
2820 	/* if there is a rest piece that didn't fit, append it */
2821 	if (UDF_EXT_LEN(udf_rw32(s_ad.len)) > 0) {
2822 		error = udf_append_adslot(udf_node, &slot, &s_ad);
2823 		if (error)
2824 			goto errorout;
2825 		slot++;
2826 	}
2827 
2828 	inflen  += size_diff;
2829 	objsize += size_diff;
2830 	if (fe) {
2831 		fe->inf_len   = udf_rw64(inflen);
2832 	} else {
2833 		efe->inf_len  = udf_rw64(inflen);
2834 		efe->obj_size = udf_rw64(objsize);
2835 	}
2836 	error = 0;
2837 
2838 	if (evacuated_data) {
2839 		/* set new write size for uvm */
2840 		uvm_vnp_setwritesize(vp, old_size);
2841 
2842 		/* write out evacuated data */
2843 		error = vn_rdwr(UIO_WRITE, udf_node->vnode,
2844 				evacuated_data, old_size, 0,
2845 				UIO_SYSSPACE, IO_ALTSEMANTICS | IO_NODELOCKED,
2846 				FSCRED, NULL, NULL);
2847 		uvm_vnp_setsize(vp, old_size);
2848 	}
2849 
2850 errorout:
2851 	if (evacuated_data)
2852 		free(evacuated_data, M_UDFTEMP);
2853 
2854 	udf_count_alloc_exts(udf_node);
2855 
2856 	udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
2857 	UDF_UNLOCK_NODE(udf_node, 0);
2858 
2859 	KASSERT(new_inflen == orig_inflen + size_diff);
2860 	KASSERT(new_lbrec == orig_lbrec);
2861 
2862 	return error;
2863 }
2864 
2865 /* --------------------------------------------------------------------- */
2866 
2867 int
udf_shrink_node(struct udf_node * udf_node,uint64_t new_size)2868 udf_shrink_node(struct udf_node *udf_node, uint64_t new_size)
2869 {
2870 	struct vnode *vp = udf_node->vnode;
2871 	struct udf_mount *ump = udf_node->ump;
2872 	struct file_entry    *fe;
2873 	struct extfile_entry *efe;
2874 	struct icb_tag  *icbtag;
2875 	struct long_ad c_ad, s_ad, *node_ad_cpy;
2876 	uint64_t size_diff, old_size, inflen, objsize;
2877 	uint64_t foffset, end_foffset;
2878 	uint64_t orig_inflen, orig_lbrec, new_inflen, new_lbrec;
2879 	uint32_t lb_size, unit_size, dscr_size, crclen;
2880 	uint32_t slot_offset, slot_offset_lb;
2881 	uint32_t len, flags, max_len;
2882 	uint32_t num_lb, lb_num;
2883 	uint32_t max_l_ad, l_ad, l_ea;
2884 	uint16_t vpart_num;
2885 	uint8_t *data_pos;
2886 	int icbflags, addr_type;
2887 	int slot, cpy_slot, cpy_slots;
2888 	int eof, error;
2889 
2890 	DPRINTF(ALLOC, ("udf_shrink_node\n"));
2891 
2892 	UDF_LOCK_NODE(udf_node, 0);
2893 	udf_node_sanity_check(udf_node, &orig_inflen, &orig_lbrec);
2894 
2895 	lb_size = udf_rw32(ump->logical_vol->lb_size);
2896 
2897 	/* max_len in unit's IFF its a metadata node or metadata mirror node */
2898 	unit_size = lb_size;
2899 	if ((udf_node == ump->metadata_node) || (udf_node == ump->metadatamirror_node))
2900 		unit_size = ump->metadata_alloc_unit_size * lb_size;
2901 	max_len = ((UDF_EXT_MAXLEN / unit_size) * unit_size);
2902 
2903 	/* do the work */
2904 	fe  = udf_node->fe;
2905 	efe = udf_node->efe;
2906 	if (fe) {
2907 		icbtag  = &fe->icbtag;
2908 		inflen  = udf_rw64(fe->inf_len);
2909 		objsize = inflen;
2910 		dscr_size  = sizeof(struct file_entry) -1;
2911 		l_ea       = udf_rw32(fe->l_ea);
2912 		l_ad       = udf_rw32(fe->l_ad);
2913 		data_pos = (uint8_t *) fe + dscr_size + l_ea;
2914 	} else {
2915 		icbtag  = &efe->icbtag;
2916 		inflen  = udf_rw64(efe->inf_len);
2917 		objsize = udf_rw64(efe->obj_size);
2918 		dscr_size  = sizeof(struct extfile_entry) -1;
2919 		l_ea       = udf_rw32(efe->l_ea);
2920 		l_ad       = udf_rw32(efe->l_ad);
2921 		data_pos = (uint8_t *) efe + dscr_size + l_ea;
2922 	}
2923 	max_l_ad = lb_size - dscr_size - l_ea;
2924 
2925 	icbflags   = udf_rw16(icbtag->flags);
2926 	addr_type  = icbflags & UDF_ICB_TAG_FLAGS_ALLOC_MASK;
2927 
2928 	old_size  = inflen;
2929 	size_diff = old_size - new_size;
2930 
2931 	DPRINTF(ALLOC, ("\tfrom %"PRIu64" to %"PRIu64"\n", old_size, new_size));
2932 
2933 	/* shrink the node to its new size */
2934 	if (addr_type == UDF_ICB_INTERN_ALLOC) {
2935 		/* only reflect size change directly in the node */
2936 		KASSERT(new_size <= max_l_ad);
2937 		inflen  -= size_diff;
2938 		objsize -= size_diff;
2939 		l_ad    -= size_diff;
2940 		crclen = dscr_size - UDF_DESC_TAG_LENGTH + l_ea + l_ad;
2941 		if (fe) {
2942 			fe->inf_len   = udf_rw64(inflen);
2943 			fe->l_ad      = udf_rw32(l_ad);
2944 			fe->tag.desc_crc_len = udf_rw16(crclen);
2945 		} else {
2946 			efe->inf_len  = udf_rw64(inflen);
2947 			efe->obj_size = udf_rw64(objsize);
2948 			efe->l_ad     = udf_rw32(l_ad);
2949 			efe->tag.desc_crc_len = udf_rw16(crclen);
2950 		}
2951 		error = 0;
2952 
2953 		/* clear the space in the descriptor */
2954 		KASSERT(old_size >= new_size);
2955 		memset(data_pos + new_size, 0, old_size - new_size);
2956 
2957 		/* TODO zero appened space in buffer! */
2958 		/* using ubc_zerorange(&vp->v_uobj, old_size, */
2959 		/*    old_size - new_size, UBC_UNMAP_FLAG(vp)); ? */
2960 
2961 		/* set new size for uvm */
2962 		uvm_vnp_setsize(vp, new_size);
2963 
2964 		udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
2965 		UDF_UNLOCK_NODE(udf_node, 0);
2966 
2967 		KASSERT(new_inflen == orig_inflen - size_diff);
2968 		KASSERT(new_lbrec == orig_lbrec);
2969 		KASSERT(new_lbrec == 0);
2970 
2971 		return 0;
2972 	}
2973 
2974 	/* setup node cleanup extents copy space */
2975 	node_ad_cpy = malloc(lb_size * UDF_MAX_ALLOC_EXTENTS,
2976 		M_UDFMNT, M_WAITOK);
2977 	memset(node_ad_cpy, 0, lb_size * UDF_MAX_ALLOC_EXTENTS);
2978 
2979 	/*
2980 	 * Shrink the node by releasing the allocations and truncate the last
2981 	 * allocation to the new size. If the new size fits into the
2982 	 * allocation descriptor itself, transform it into an
2983 	 * UDF_ICB_INTERN_ALLOC.
2984 	 */
2985 	slot     = 0;
2986 	cpy_slot = 0;
2987 	foffset  = 0;
2988 
2989 	/* 1) copy till first overlap piece to the rewrite buffer */
2990 	for (;;) {
2991 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
2992 		if (eof) {
2993 			DPRINTF(WRITE,
2994 				("Shrink node failed: "
2995 				 "encountered EOF\n"));
2996 			error = EINVAL;
2997 			goto errorout; /* panic? */
2998 		}
2999 		len   = udf_rw32(s_ad.len);
3000 		flags = UDF_EXT_FLAGS(len);
3001 		len   = UDF_EXT_LEN(len);
3002 
3003 		if (flags == UDF_EXT_REDIRECT) {
3004 			slot++;
3005 			continue;
3006 		}
3007 
3008 		end_foffset = foffset + len;
3009 		if (end_foffset > new_size)
3010 			break;	/* found */
3011 
3012 		node_ad_cpy[cpy_slot++] = s_ad;
3013 
3014 		DPRINTF(ALLOC, ("\t1: vp %d, lb %d, len %d, flags %d "
3015 			"-> stack\n",
3016 			udf_rw16(s_ad.loc.part_num),
3017 			udf_rw32(s_ad.loc.lb_num),
3018 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
3019 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
3020 
3021 		foffset = end_foffset;
3022 		slot++;
3023 	}
3024 	slot_offset = new_size - foffset;
3025 
3026 	/* 2) trunc overlapping slot at overlap and copy it */
3027 	if (slot_offset > 0) {
3028 		lb_num    = udf_rw32(s_ad.loc.lb_num);
3029 		vpart_num = udf_rw16(s_ad.loc.part_num);
3030 
3031 		if (flags == UDF_EXT_ALLOCATED) {
3032 			/* calculate extent in lb, and offset in lb */
3033 			num_lb = (len + lb_size -1) / lb_size;
3034 			slot_offset_lb = (slot_offset + lb_size -1) / lb_size;
3035 
3036 			/* adjust our slot */
3037 			lb_num += slot_offset_lb;
3038 			num_lb -= slot_offset_lb;
3039 
3040 			udf_free_allocated_space(ump, lb_num, vpart_num, num_lb);
3041 		}
3042 
3043 		s_ad.len = udf_rw32(slot_offset | flags);
3044 		node_ad_cpy[cpy_slot++] = s_ad;
3045 		slot++;
3046 
3047 		DPRINTF(ALLOC, ("\t2: vp %d, lb %d, len %d, flags %d "
3048 			"-> stack\n",
3049 			udf_rw16(s_ad.loc.part_num),
3050 			udf_rw32(s_ad.loc.lb_num),
3051 			UDF_EXT_LEN(udf_rw32(s_ad.len)),
3052 			UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
3053 	}
3054 
3055 	/* 3) delete remainder */
3056 	for (;;) {
3057 		udf_get_adslot(udf_node, slot, &s_ad, &eof);
3058 		if (eof)
3059 			break;
3060 
3061 		len       = udf_rw32(s_ad.len);
3062 		flags     = UDF_EXT_FLAGS(len);
3063 		len       = UDF_EXT_LEN(len);
3064 
3065 		if (flags == UDF_EXT_REDIRECT) {
3066 			slot++;
3067 			continue;
3068 		}
3069 
3070 		DPRINTF(ALLOC, ("\t3: delete remainder "
3071 			"vp %d lb %d, len %d, flags %d\n",
3072 		udf_rw16(s_ad.loc.part_num),
3073 		udf_rw32(s_ad.loc.lb_num),
3074 		UDF_EXT_LEN(udf_rw32(s_ad.len)),
3075 		UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
3076 
3077 		if (flags == UDF_EXT_ALLOCATED) {
3078 			lb_num    = udf_rw32(s_ad.loc.lb_num);
3079 			vpart_num = udf_rw16(s_ad.loc.part_num);
3080 			num_lb    = (len + lb_size - 1) / lb_size;
3081 
3082 			udf_free_allocated_space(ump, lb_num, vpart_num,
3083 				num_lb);
3084 		}
3085 
3086 		slot++;
3087 	}
3088 
3089 	/* 4) if it will fit into the descriptor then convert */
3090 	if (new_size < max_l_ad) {
3091 		/*
3092 		 * resque/evacuate old piece by reading it in, and convert it
3093 		 * to internal alloc.
3094 		 */
3095 		if (new_size == 0) {
3096 			/* XXX/TODO only for zero sizing now */
3097 			udf_wipe_adslots(udf_node);
3098 
3099 			icbflags &= ~UDF_ICB_TAG_FLAGS_ALLOC_MASK;
3100 			icbflags |=  UDF_ICB_INTERN_ALLOC;
3101 			icbtag->flags = udf_rw16(icbflags);
3102 
3103 			inflen  -= size_diff;	KASSERT(inflen == 0);
3104 			objsize -= size_diff;
3105 			l_ad     = new_size;
3106 			crclen = dscr_size - UDF_DESC_TAG_LENGTH + l_ea + l_ad;
3107 			if (fe) {
3108 				fe->inf_len   = udf_rw64(inflen);
3109 				fe->l_ad      = udf_rw32(l_ad);
3110 				fe->tag.desc_crc_len = udf_rw16(crclen);
3111 			} else {
3112 				efe->inf_len  = udf_rw64(inflen);
3113 				efe->obj_size = udf_rw64(objsize);
3114 				efe->l_ad     = udf_rw32(l_ad);
3115 				efe->tag.desc_crc_len = udf_rw16(crclen);
3116 			}
3117 			/* eventually copy in evacuated piece */
3118 			/* set new size for uvm */
3119 			uvm_vnp_setsize(vp, new_size);
3120 
3121 			free(node_ad_cpy, M_UDFMNT);
3122 			udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
3123 
3124 			UDF_UNLOCK_NODE(udf_node, 0);
3125 
3126 			KASSERT(new_inflen == orig_inflen - size_diff);
3127 			KASSERT(new_inflen == 0);
3128 			KASSERT(new_lbrec == 0);
3129 
3130 			return 0;
3131 		}
3132 
3133 		printf("UDF_SHRINK_NODE: could convert to internal alloc!\n");
3134 	}
3135 
3136 	/* 5) reset node descriptors */
3137 	udf_wipe_adslots(udf_node);
3138 
3139 	/* 6) copy back extents; merge when possible. Recounting on the fly */
3140 	cpy_slots = cpy_slot;
3141 
3142 	c_ad = node_ad_cpy[0];
3143 	slot = 0;
3144 	for (cpy_slot = 1; cpy_slot < cpy_slots; cpy_slot++) {
3145 		s_ad = node_ad_cpy[cpy_slot];
3146 
3147 		DPRINTF(ALLOC, ("\t6: stack -> got mapping vp %d "
3148 			"lb %d, len %d, flags %d\n",
3149 		udf_rw16(s_ad.loc.part_num),
3150 		udf_rw32(s_ad.loc.lb_num),
3151 		UDF_EXT_LEN(udf_rw32(s_ad.len)),
3152 		UDF_EXT_FLAGS(udf_rw32(s_ad.len)) >> 30));
3153 
3154 		/* see if we can merge */
3155 		if (udf_ads_merge(max_len, lb_size, &c_ad, &s_ad)) {
3156 			/* not mergable (anymore) */
3157 			DPRINTF(ALLOC, ("\t6: appending vp %d lb %d, "
3158 				"len %d, flags %d\n",
3159 			udf_rw16(c_ad.loc.part_num),
3160 			udf_rw32(c_ad.loc.lb_num),
3161 			UDF_EXT_LEN(udf_rw32(c_ad.len)),
3162 			UDF_EXT_FLAGS(udf_rw32(c_ad.len)) >> 30));
3163 
3164 			error = udf_append_adslot(udf_node, &slot, &c_ad);
3165 			if (error)
3166 				goto errorout; /* panic? */
3167 			c_ad = s_ad;
3168 			slot++;
3169 		}
3170 	}
3171 
3172 	/* 7) push rest slot (if any) */
3173 	if (UDF_EXT_LEN(c_ad.len) > 0) {
3174 		DPRINTF(ALLOC, ("\t7: last append vp %d lb %d, "
3175 				"len %d, flags %d\n",
3176 		udf_rw16(c_ad.loc.part_num),
3177 		udf_rw32(c_ad.loc.lb_num),
3178 		UDF_EXT_LEN(udf_rw32(c_ad.len)),
3179 		UDF_EXT_FLAGS(udf_rw32(c_ad.len)) >> 30));
3180 
3181 		error = udf_append_adslot(udf_node, &slot, &c_ad);
3182 		if (error)
3183 			goto errorout; /* panic? */
3184 		;
3185 	}
3186 
3187 	inflen  -= size_diff;
3188 	objsize -= size_diff;
3189 	if (fe) {
3190 		fe->inf_len   = udf_rw64(inflen);
3191 	} else {
3192 		efe->inf_len  = udf_rw64(inflen);
3193 		efe->obj_size = udf_rw64(objsize);
3194 	}
3195 	error = 0;
3196 
3197 	/* set new size for uvm */
3198 	uvm_vnp_setsize(vp, new_size);
3199 
3200 errorout:
3201 	free(node_ad_cpy, M_UDFMNT);
3202 
3203 	udf_count_alloc_exts(udf_node);
3204 
3205 	udf_node_sanity_check(udf_node, &new_inflen, &new_lbrec);
3206 	UDF_UNLOCK_NODE(udf_node, 0);
3207 
3208 	KASSERT(new_inflen == orig_inflen - size_diff);
3209 
3210 	return error;
3211 }
3212 
3213