xref: /titanic_52/usr/src/uts/common/fs/udfs/udf_alloc.c (revision ad9a7bd3532cf0ef931ded51a5ffe5d0496aad88)

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <sys/types.h>
#include <sys/t_lock.h>
#include <sys/param.h>
#include <sys/time.h>
#include <sys/systm.h>
#include <sys/sysmacros.h>
#include <sys/resource.h>
#include <sys/signal.h>
#include <sys/cred.h>
#include <sys/user.h>
#include <sys/buf.h>
#include <sys/vfs.h>
#include <sys/stat.h>
#include <sys/vnode.h>
#include <sys/mode.h>
#include <sys/proc.h>
#include <sys/disp.h>
#include <sys/file.h>
#include <sys/fcntl.h>
#include <sys/flock.h>
#include <sys/kmem.h>
#include <sys/uio.h>
#include <sys/dnlc.h>
#include <sys/conf.h>
#include <sys/errno.h>
#include <sys/mman.h>
#include <sys/fbuf.h>
#include <sys/pathname.h>
#include <sys/debug.h>
#include <sys/vmsystm.h>
#include <sys/cmn_err.h>
#include <sys/dirent.h>
#include <sys/errno.h>
#include <sys/modctl.h>
#include <sys/statvfs.h>
#include <sys/mount.h>
#include <sys/sunddi.h>
#include <sys/bootconf.h>
#include <sys/policy.h>

#include <vm/hat.h>
#include <vm/page.h>
#include <vm/pvn.h>
#include <vm/as.h>
#include <vm/seg.h>
#include <vm/seg_map.h>
#include <vm/seg_kmem.h>
#include <vm/seg_vn.h>
#include <vm/rm.h>
#include <vm/page.h>
#include <sys/swap.h>

#include <fs/fs_subr.h>

#include <sys/fs/udf_volume.h>
#include <sys/fs/udf_inode.h>

#ifdef	DEBUG
extern struct ud_inode *ud_search_icache(struct vfs *, uint16_t, uint32_t);
#endif

int32_t ud_alloc_space_bmap(struct vfs *, struct ud_part *,
	uint32_t, uint32_t, uint32_t *, uint32_t *, int32_t);
int32_t ud_check_free_and_mark_used(struct vfs *,
	struct ud_part *, uint32_t, uint32_t *);
int32_t ud_check_free(uint8_t *, uint8_t *, uint32_t, uint32_t);
void ud_mark_used(uint8_t *, uint32_t, uint32_t);
void ud_mark_free(uint8_t *, uint32_t, uint32_t);
int32_t ud_alloc_space_stbl(struct vfs *, struct ud_part *,
	uint32_t, uint32_t, uint32_t *, uint32_t *, int32_t);
int32_t ud_free_space_bmap(struct vfs *,
	struct ud_part *, uint32_t, uint32_t);
int32_t ud_free_space_stbl(struct vfs *,
	struct ud_part *, uint32_t, uint32_t);


/*
 * WORKSAROUND to the buffer cache crap
 * If the requested block exists in the buffer cache
 * buffer cache does not care about the count
 * it just returns the old buffer(does not even
 * set resid value). Same problem exists if the
 * block that is requested is not the first block
 * in the cached buffer then this will return
 * a different buffer. We work around the above by
 * using a fixed size request to the buffer cache
 * all the time. This is currently udf_lbsize.
 * (Actually it is restricted to udf_lbsize
 * because iget always does udf_lbsize requests)
 */


/*
 * allocate blkcount blocks continuously
 * near "proximity" block in partion defined by prn.
 * if proximity != 0 means less_is_ok = 0
 * return the starting block no and count
 * of blocks allocated in start_blkno & size
 * if less_is_ok == 0 then allocate only if
 * entire requirement can be met.
 */
int32_t
ud_alloc_space(struct vfs *vfsp, uint16_t prn,
	uint32_t proximity, uint32_t blkcount,
	uint32_t *start_blkno, uint32_t *size,
	int32_t less_is_ok, int32_t metadata)
{
	int32_t i, error = 0;
	struct udf_vfs *udf_vfsp;
	struct ud_part *ud_part;

	ud_printf("ud_alloc_space\n");


/*
 * prom_printf("ud_alloc_space %x %x %x %x\n",
 * proximity, blkcount, less_is_ok, metadata);
 */

	if (blkcount == 0) {
		*start_blkno = 0;
		*size = 0;
		return (0);
	}

	udf_vfsp = (struct udf_vfs *)vfsp->vfs_data;
	ud_part = udf_vfsp->udf_parts;
	for (i = 0; i < udf_vfsp->udf_npart; i++) {
		if (prn == ud_part->udp_number) {
			break;
		}
		ud_part ++;
	}

	if (i == udf_vfsp->udf_npart) {
		return (1);
	}
	*start_blkno = 0;
	*size = 0;
	if (metadata) {
		error = ud_alloc_from_cache(udf_vfsp, ud_part, start_blkno);
		if (error == 0) {
			*size = 1;
			return (0);
		}
	}
	if (ud_part->udp_nfree != 0) {
		if (ud_part->udp_flags == UDP_BITMAPS) {
			error = ud_alloc_space_bmap(vfsp, ud_part, proximity,
			    blkcount, start_blkno, size, less_is_ok);
		} else {
			error = ud_alloc_space_stbl(vfsp, ud_part, proximity,
			    blkcount, start_blkno, size, less_is_ok);
		}
		if (error == 0) {
			mutex_enter(&udf_vfsp->udf_lock);
			ASSERT(ud_part->udp_nfree >= *size);
			ASSERT(udf_vfsp->udf_freeblks >= *size);
			ud_part->udp_nfree -= *size;
			udf_vfsp->udf_freeblks -= *size;
			mutex_exit(&udf_vfsp->udf_lock);
		}
	} else {
		error = ENOSPC;
	}
/*
 * prom_printf("end %x %x %x\n", error, *start_blkno, *size);
 */

	return (error);
}

#ifdef	SKIP_USED_BLOCKS
/*
 * This table is manually constructed
 */
int8_t skip[256] = {
8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
#endif

#define	HDR_BLKS	(24 * 8)

int32_t
ud_alloc_space_bmap(struct vfs *vfsp,
	struct ud_part *ud_part, uint32_t proximity,
	uint32_t blkcount, uint32_t *start_blkno,
	uint32_t *size, int32_t less_is_ok)
{
	struct buf *bp = NULL;
	struct udf_vfs *udf_vfsp;
	uint32_t old_loc, old_size, new_size;
	uint8_t *addr, *eaddr;
	uint32_t loop_count, loop_begin, loop_end;
	uint32_t bno, begin, dummy, temp, lbsz, bb_count;
	uint32_t bblk = 0, eblk = 0;
	int32_t fragmented;

	ud_printf("ud_alloc_space_bmap\n");

	ASSERT(ud_part);
	ASSERT(ud_part->udp_flags == UDP_BITMAPS);

	if (ud_part->udp_unall_len == 0) {
		return (ENOSPC);
	}
	udf_vfsp = (struct udf_vfs *)vfsp->vfs_data;
	lbsz = udf_vfsp->udf_lbsize;
	bb_count = udf_vfsp->udf_lbsize << 3;

	if (proximity != 0) {
		/*
		 * directly try allocating
		 * at proximity
		 */
		temp = blkcount;
		if (ud_check_free_and_mark_used(vfsp,
		    ud_part, proximity, &temp) == 0) {
			if (temp != 0) {
				*start_blkno = proximity;
				*size = temp;
				return (0);
			}
		}
		*start_blkno = 0;
		*size = 0;
	}

	mutex_enter(&udf_vfsp->udf_lock);
	fragmented = udf_vfsp->udf_fragmented;
	mutex_exit(&udf_vfsp->udf_lock);
retry:
	old_loc = old_size = 0;

	mutex_enter(&udf_vfsp->udf_lock);
	loop_begin = (ud_part->udp_last_alloc + CLSTR_MASK) & ~CLSTR_MASK;
	mutex_exit(&udf_vfsp->udf_lock);

	loop_end = ud_part->udp_nblocks + HDR_BLKS;
	loop_count = (loop_begin) ? 2 : 1;
	while (loop_count--) {
		for (bno = loop_begin + HDR_BLKS; bno + blkcount < loop_end; ) {


			/*
			 * Each bread is restricted to lbsize
			 * due to the way bread is implemented
			 */
			if ((bp == NULL) ||
			    ((eblk - bno) < blkcount)) {
				if (bp != NULL) {
					brelse(bp);
				}
				begin = ud_part->udp_unall_loc +
				    bno / bb_count;
				bp = ud_bread(vfsp->vfs_dev,
				    ud_xlate_to_daddr(udf_vfsp,
				    ud_part->udp_number,
				    begin, 1, &dummy) <<
				    udf_vfsp->udf_l2d_shift, lbsz);
				if (bp->b_flags & B_ERROR) {
					brelse(bp);
					return (EIO);
				}
				bblk = begin * bb_count;
				eblk = bblk + bb_count;
				addr = (uint8_t *)bp->b_un.b_addr;
				eaddr = addr + bp->b_bcount;
			}

			if (blkcount > (eblk - bno)) {
				temp = eblk - bno;
			} else {
				temp = blkcount;
			}
			if ((new_size = ud_check_free(addr, eaddr,
			    bno - bblk, temp)) == temp) {
				ud_mark_used(addr, bno - bblk, temp);
				bdwrite(bp);
				*start_blkno = bno - HDR_BLKS;
				*size = temp;
				mutex_enter(&udf_vfsp->udf_lock);
				ud_part->udp_last_alloc =
				    bno + temp - HDR_BLKS;
				mutex_exit(&udf_vfsp->udf_lock);
				return (0);
			}
			if (less_is_ok) {
				if (old_size < new_size) {
					old_loc = bno - HDR_BLKS;
					old_size = new_size;
				}
			}
			if (new_size != 0) {
				bno += new_size;
			} else {
#ifdef	SKIP_USED_BLOCKS
				/*
				 * Skipping 0's
				 * implement a allocated block skip
				 * using a while loop with an
				 * preinitialised array of 256 elements
				 * for number of blocks skipped
				 */
				bno &= ~3;
				while (skip[addr[(bno - bblk) >> 3]] == 8)
					bno += 8;
				bno += skip[addr[(bno - bblk) >> 3]];
#else
				bno++;
#endif
			}
			if (!fragmented) {
				bno = (bno + CLSTR_MASK) & ~CLSTR_MASK;
			}
		}
		if (bp != NULL) {
			brelse(bp);
			bp = NULL;
		}
		if (loop_count) {
			loop_end = loop_begin + HDR_BLKS;
			loop_begin = 0;
		}
	}
	if ((old_size == 0) && (!fragmented)) {
		mutex_enter(&udf_vfsp->udf_lock);
		fragmented = udf_vfsp->udf_fragmented = 1;
		mutex_exit(&udf_vfsp->udf_lock);
		goto retry;
	}
	if (less_is_ok && (old_size != 0)) {

		/*
		 * Check once again
		 * somebody else might have
		 * already allocated behind us
		 */
		if (ud_check_free_and_mark_used(vfsp,
		    ud_part, old_loc, &old_size) == 0) {
			if (old_size != 0) {
				*start_blkno = old_loc;
				*size = old_size;
				mutex_enter(&udf_vfsp->udf_lock);
				ud_part->udp_last_alloc = old_loc + old_size;
				mutex_exit(&udf_vfsp->udf_lock);
				return (0);
			}
		}

		/*
		 * Failed what ever the reason
		 */
		goto retry;
	}
	return (ENOSPC);
}

/*
 * start is the block from the begining
 * of the partition ud_part
 */
int32_t
ud_check_free_and_mark_used(struct vfs *vfsp,
	struct ud_part *ud_part, uint32_t start, uint32_t *count)
{
	struct buf *bp;
	struct udf_vfs *udf_vfsp;
	uint32_t begin, dummy, bb_count;

	/*
	 * Adjust start for the header
	 */
	start += HDR_BLKS;
	udf_vfsp = (struct udf_vfs *)vfsp->vfs_data;
	bb_count = udf_vfsp->udf_lbsize << 3;

	/*
	 * Read just on block worth of bitmap
	 */
	begin = ud_part->udp_unall_loc + (start / bb_count);
	bp = ud_bread(vfsp->vfs_dev,
	    ud_xlate_to_daddr(udf_vfsp, ud_part->udp_number,
	    begin, 1, &dummy) << udf_vfsp->udf_l2d_shift,
	    udf_vfsp->udf_lbsize);
	if (bp->b_flags & B_ERROR) {
		brelse(bp);
		return (EIO);
	}

	/*
	 * Adjust the count if necessary
	 */
	start -= begin * bb_count;
	if ((start + *count) > bb_count) {
		*count = bb_count - start;
		ASSERT(*count > 0);
	}
	if (ud_check_free((uint8_t *)bp->b_un.b_addr,
	    (uint8_t *)bp->b_un.b_addr + bp->b_bcount, start,
	    *count) != *count) {
		brelse(bp);
		return (1);
	}
	ud_mark_used((uint8_t *)bp->b_un.b_addr, start, *count);
	bdwrite(bp);

	return (0);
}

int32_t
ud_check_free(uint8_t *addr, uint8_t *eaddr, uint32_t start, uint32_t count)
{
	int32_t i = 0;

	for (i = 0; i < count; i++) {
		if (&addr[start >> 3] >= eaddr) {
			break;
		}
		if ((addr[start >> 3] & (1 << (start & 0x7))) == 0) {
			break;
		}
		start ++;
	}
	return (i);
}

void
ud_mark_used(uint8_t *addr, uint32_t start, uint32_t count)
{
	int32_t i = 0;

	for (i = 0; i < count; i++) {
		addr[start >> 3] &= ~(1 << (start & 0x7));
		start++;
	}
}

void
ud_mark_free(uint8_t *addr, uint32_t start, uint32_t count)
{
	int32_t i = 0;

	for (i = 0; i < count; i++) {
		addr[start >> 3] |= (1 << (start & 0x7));
		start++;
	}
}

/* ARGSUSED */
int32_t
ud_alloc_space_stbl(struct vfs *vfsp,
	struct ud_part *ud_part, uint32_t proximity,
	uint32_t blkcount, uint32_t *start_blkno,
	uint32_t *size, int32_t less_is_ok)
{
	uint16_t adesc;
	uint32_t temp, sz;
	int32_t error, index, count, larg_index, larg_sz;
	struct buf *bp;
	struct udf_vfs *udf_vfsp;
	struct unall_space_ent *use;

	ASSERT(ud_part);
	ASSERT(ud_part->udp_flags == UDP_SPACETBLS);

	ud_printf("ud_alloc_space_stbl\n");

	if (ud_part->udp_unall_len == 0) {
		return (ENOSPC);
	}

	udf_vfsp = (struct udf_vfs *)vfsp->vfs_data;
	ASSERT((ud_part->udp_unall_len + 40) <= udf_vfsp->udf_lbsize);

	bp = ud_bread(vfsp->vfs_dev,
	    ud_xlate_to_daddr(udf_vfsp, ud_part->udp_number,
	    ud_part->udp_unall_loc, 1, &temp), udf_vfsp->udf_lbsize);

	use = (struct unall_space_ent *)bp->b_un.b_addr;
	sz = SWAP_32(use->use_len_ad);
	adesc = SWAP_16(use->use_icb_tag.itag_flags) & 0x7;
	if (adesc == ICB_FLAG_SHORT_AD) {
		struct short_ad *sad;

		sad = (struct short_ad *)use->use_ad;
		count = sz / sizeof (struct short_ad);

		/*
		 * Search the entire list for
		 * a extent which can give the entire data
		 * Do only first fit
		 */
		larg_index = larg_sz = 0;
		for (index = 0; index < count; index++, sad++) {
			temp = SWAP_32(sad->sad_ext_len) >>
			    udf_vfsp->udf_l2b_shift;
			if (temp == blkcount) {
				/*
				 * We found the right fit
				 * return the values and
				 * compress the table
				 */
				less_is_ok = 1;
				larg_index = index;
				larg_sz = temp;
				goto compress_sad;
			} else if (temp > blkcount) {
				/*
				 * We found an entry larger than the
				 * requirement. Change the start block
				 * number and the count to reflect the
				 * allocation
				 */
				*start_blkno = SWAP_32(sad->sad_ext_loc);
				*size = blkcount;
				temp = (temp - blkcount) <<
				    udf_vfsp->udf_l2b_shift;
				sad->sad_ext_len = SWAP_32(temp);
				temp = SWAP_32(sad->sad_ext_loc) + blkcount;
				sad->sad_ext_loc = SWAP_32(temp);
				goto end;
			}
			/*
			 * Let us keep track of the largest
			 * extent available if less_is_ok.
			 */
			if (less_is_ok) {
				if (temp > larg_sz) {
					larg_sz = temp;
					larg_index = index;
				}
			}
		}
compress_sad:
		if ((less_is_ok) && (larg_sz != 0)) {
			/*
			 * If we came here we could
			 * not find a extent to cover the entire size
			 * return whatever could be allocated
			 * and compress the table
			 */
			sad = (struct short_ad *)use->use_ad;
			sad += larg_index;
			*start_blkno = SWAP_32(sad->sad_ext_loc);
			*size = larg_sz;
			for (index = larg_index; index < count;
			    index++, sad++) {
				*sad = *(sad+1);
			}
			sz -= sizeof (struct short_ad);
			use->use_len_ad = SWAP_32(sz);
		} else {
			error = ENOSPC;
		}
		goto end;
	} else if (adesc == ICB_FLAG_LONG_AD) {
		struct long_ad *lad;

		lad = (struct long_ad *)use->use_ad;
		count = sz / sizeof (struct long_ad);

		/*
		 * Search the entire list for
		 * a extent which can give the entire data
		 * Do only first fit
		 */
		larg_index = larg_sz = 0;
		for (index = 0; index < count; index++, lad++) {
			temp = SWAP_32(lad->lad_ext_len) >>
			    udf_vfsp->udf_l2b_shift;
			if (temp == blkcount) {
				/*
				 * We found the right fit
				 * return the values and
				 * compress the table
				 */
				less_is_ok = 1;
				larg_index = index;
				larg_sz = temp;
				goto compress_lad;
			} else if (temp > blkcount) {
				/*
				 * We found an entry larger than the
				 * requirement. Change the start block
				 * number and the count to reflect the
				 * allocation
				 */
				*start_blkno = SWAP_32(lad->lad_ext_loc);
				*size = blkcount;
				temp = (temp - blkcount) <<
				    udf_vfsp->udf_l2b_shift;
				lad->lad_ext_len = SWAP_32(temp);
				temp = SWAP_32(lad->lad_ext_loc) + blkcount;
				lad->lad_ext_loc = SWAP_32(temp);
				goto end;
			}
			/*
			 * Let us keep track of the largest
			 * extent available if less_is_ok.
			 */
			if (less_is_ok) {
				if (temp > larg_sz) {
					larg_sz = temp;
					larg_index = index;
				}
			}
		}
compress_lad:
		if ((less_is_ok) && (larg_sz != 0)) {
			/*
			 * If we came here we could
			 * not find a extent to cover the entire size
			 * return whatever could be allocated
			 * and compress the table
			 */
			lad = (struct long_ad *)use->use_ad;
			lad += larg_index;
			*start_blkno = SWAP_32(lad->lad_ext_loc);
			*size = larg_sz;
			for (index = larg_index; index < count;
			    index++, lad++) {
				*lad = *(lad+1);
			}
			sz -= sizeof (struct long_ad);
			use->use_len_ad = SWAP_32(sz);
		} else {
			error = ENOSPC;
		}
		goto end;
	} else {
		error = ENOSPC;
	}
end:
	if (!error) {
		bdwrite(bp);
	} else {
		brelse(bp);
	}
	return (error);
}


/*
 * release blkcount blocks starting from beginblk
 * Call appropriate bmap/space table fucntions
 */
void
ud_free_space(struct vfs *vfsp, uint16_t prn,
	uint32_t beginblk, uint32_t blkcount)
{
	int32_t i, error;
	struct ud_part *ud_part;
	struct udf_vfs *udf_vfsp;

	ud_printf("ud_free_space\n");

	if (blkcount == 0) {
		return;
	}

	udf_vfsp = (struct udf_vfs *)vfsp->vfs_data;
	ud_part = udf_vfsp->udf_parts;
	for (i = 0; i < udf_vfsp->udf_npart; i++) {
		if (prn == ud_part->udp_number) {
			break;
		}
		ud_part ++;
	}

	if (i == udf_vfsp->udf_npart) {
		return;
	}

	if (ud_part->udp_flags == UDP_BITMAPS) {
		error = ud_free_space_bmap(vfsp, ud_part, beginblk, blkcount);
	} else {
		error = ud_free_space_stbl(vfsp, ud_part, beginblk, blkcount);
	}

	if (error) {
		udf_vfsp->udf_mark_bad = 1;
	}
}

/*
 * If there is a freed table then
 * release blocks to the freed table
 * other wise release to the un allocated table.
 * Findout the offset into the bitmap and
 * mark the blocks as free blocks
 */
int32_t
ud_free_space_bmap(struct vfs *vfsp,
	struct ud_part *ud_part,
	uint32_t beginblk, uint32_t blkcount)
{
	struct buf *bp;
	struct udf_vfs *udf_vfsp;
	uint32_t block, begin, end, blkno, count, map_end_blk, dummy;

	ud_printf("ud_free_space_bmap\n");

	ASSERT(ud_part);
	ASSERT(ud_part->udp_flags == UDP_BITMAPS);
/*
 * prom_printf("%x %x\n", udblock, udcount);
 */

	udf_vfsp = (struct udf_vfs *)vfsp->vfs_data;
	if ((ud_part->udp_freed_len == 0) &&
	    (ud_part->udp_unall_len == 0)) {
		return (ENOSPC);
	}
	/*
	 * decide unallocated/freed table to use
	 */
	if (ud_part->udp_freed_len == 0) {
		begin = ud_part->udp_unall_loc;
		map_end_blk = ud_part->udp_unall_len << 3;
	} else {
		begin = ud_part->udp_freed_loc;
		map_end_blk = ud_part->udp_freed_len << 3;
	}

	if (beginblk + blkcount > map_end_blk) {
		return (ENOSPC);
	}

	/* adjust for the bitmap header */
	beginblk += HDR_BLKS;

	end = begin + ((beginblk + blkcount) / (udf_vfsp->udf_lbsize << 3));
	begin += (beginblk / (udf_vfsp->udf_lbsize << 3));

	for (block = begin; block <= end; block++) {

		bp = ud_bread(vfsp->vfs_dev,
		    ud_xlate_to_daddr(udf_vfsp, ud_part->udp_number, block, 1,
		    &dummy) << udf_vfsp->udf_l2d_shift, udf_vfsp->udf_lbsize);
		if (bp->b_flags & B_ERROR) {
			brelse(bp);
			return (EIO);
		}
		ASSERT(dummy == 1);

		mutex_enter(&udf_vfsp->udf_lock);

		/*
		 * add freed blocks to the bitmap
		 */

		blkno = beginblk - (block * (udf_vfsp->udf_lbsize << 3));
		if (blkno + blkcount > (udf_vfsp->udf_lbsize << 3)) {
			count = (udf_vfsp->udf_lbsize << 3) - blkno;
		} else {
			count = blkcount;
		}

/*
 * if (begin != end) {
 *	printf("%x %x %x %x %x %x\n",
 *		begin, end, block, blkno, count);
 *	printf("%x %x %x\n", bp->b_un.b_addr, blkno, count);
 * }
 */

		ud_mark_free((uint8_t *)bp->b_un.b_addr, blkno, count);

		beginblk += count;
		blkcount -= count;

		if (ud_part->udp_freed_len == 0) {
			ud_part->udp_nfree += count;
			udf_vfsp->udf_freeblks += count;
		}
		mutex_exit(&udf_vfsp->udf_lock);

		bdwrite(bp);
	}

	return (0);
}


/* ARGSUSED */
/*
 * search the entire table if there is
 * a entry with which we can merge the
 * current entry. Other wise create
 * a new entry at the end of the table
 */
int32_t
ud_free_space_stbl(struct vfs *vfsp,
	struct ud_part *ud_part,
	uint32_t beginblk, uint32_t blkcount)
{
	uint16_t adesc;
	int32_t error = 0, index, count;
	uint32_t block, dummy, sz;
	struct buf *bp;
	struct udf_vfs *udf_vfsp;
	struct unall_space_ent *use;

	ud_printf("ud_free_space_stbl\n");

	ASSERT(ud_part);
	ASSERT(ud_part->udp_flags == UDP_SPACETBLS);

	if ((ud_part->udp_freed_len == 0) && (ud_part->udp_unall_len == 0)) {
		return (ENOSPC);
	}

	if (ud_part->udp_freed_len != 0) {
		block = ud_part->udp_freed_loc;
	} else {
		block = ud_part->udp_unall_loc;
	}

	udf_vfsp = (struct udf_vfs *)vfsp->vfs_data;
	ASSERT((ud_part->udp_unall_len + 40) <= udf_vfsp->udf_lbsize);

	bp = ud_bread(vfsp->vfs_dev,
	    ud_xlate_to_daddr(udf_vfsp, ud_part->udp_number, block, 1, &dummy),
	    udf_vfsp->udf_lbsize);

	use = (struct unall_space_ent *)bp->b_un.b_addr;
	sz = SWAP_32(use->use_len_ad);
	adesc = SWAP_16(use->use_icb_tag.itag_flags) & 0x7;
	if (adesc == ICB_FLAG_SHORT_AD) {
		struct short_ad *sad;

		sad = (struct short_ad *)use->use_ad;
		count = sz / sizeof (struct short_ad);
		/*
		 * Check if the blocks being freed
		 * are continuous with any of the
		 * existing extents
		 */
		for (index = 0; index < count; index++, sad++) {
			if (beginblk == (SWAP_32(sad->sad_ext_loc) +
			    (SWAP_32(sad->sad_ext_len) /
			    udf_vfsp->udf_lbsize))) {
				dummy = SWAP_32(sad->sad_ext_len) +
				    blkcount * udf_vfsp->udf_lbsize;
				sad->sad_ext_len = SWAP_32(dummy);
				goto end;
			} else if ((beginblk + blkcount) ==
			    SWAP_32(sad->sad_ext_loc)) {
				sad->sad_ext_loc = SWAP_32(beginblk);
				goto end;
			}
		}

		/*
		 * We need to add a new entry
		 * Check if we space.
		 */
		if ((40 + sz + sizeof (struct short_ad)) >
		    udf_vfsp->udf_lbsize) {
			error = ENOSPC;
			goto end;
		}

		/*
		 * We have enough space
		 * just add the entry at the end
		 */
		dummy = SWAP_32(use->use_len_ad);
		sad = (struct short_ad *)&use->use_ad[dummy];
		sz = blkcount * udf_vfsp->udf_lbsize;
		sad->sad_ext_len = SWAP_32(sz);
		sad->sad_ext_loc = SWAP_32(beginblk);
		dummy += sizeof (struct short_ad);
		use->use_len_ad = SWAP_32(dummy);
	} else if (adesc == ICB_FLAG_LONG_AD) {
		struct long_ad *lad;

		lad = (struct long_ad *)use->use_ad;
		count = sz / sizeof (struct long_ad);
		/*
		 * Check if the blocks being freed
		 * are continuous with any of the
		 * existing extents
		 */
		for (index = 0; index < count; index++, lad++) {
			if (beginblk == (SWAP_32(lad->lad_ext_loc) +
			    (SWAP_32(lad->lad_ext_len) /
			    udf_vfsp->udf_lbsize))) {
				dummy = SWAP_32(lad->lad_ext_len) +
				    blkcount * udf_vfsp->udf_lbsize;
				lad->lad_ext_len = SWAP_32(dummy);
				goto end;
			} else if ((beginblk + blkcount) ==
			    SWAP_32(lad->lad_ext_loc)) {
				lad->lad_ext_loc = SWAP_32(beginblk);
				goto end;
			}
		}

		/*
		 * We need to add a new entry
		 * Check if we space.
		 */
		if ((40 + sz + sizeof (struct long_ad)) >
		    udf_vfsp->udf_lbsize) {
			error = ENOSPC;
			goto end;
		}

		/*
		 * We have enough space
		 * just add the entry at the end
		 */
		dummy = SWAP_32(use->use_len_ad);
		lad = (struct long_ad *)&use->use_ad[dummy];
		sz = blkcount * udf_vfsp->udf_lbsize;
		lad->lad_ext_len = SWAP_32(sz);
		lad->lad_ext_loc = SWAP_32(beginblk);
		lad->lad_ext_prn = SWAP_16(ud_part->udp_number);
		dummy += sizeof (struct long_ad);
		use->use_len_ad = SWAP_32(dummy);
	} else {
		error = ENOSPC;
		goto end;
	}

end:
	if (!error) {
		bdwrite(bp);
	} else {
		brelse(bp);
	}
	return (error);
}

/* ARGSUSED */
int32_t
ud_ialloc(struct ud_inode *pip,
	struct ud_inode **ipp, struct vattr *vap, struct cred *cr)
{
	int32_t err;
	uint32_t blkno, size, loc;
	uint32_t imode, ichar, lbsize, ea_len, dummy;
	uint16_t prn, flags;
	struct buf *bp;
	struct file_entry *fe;
	struct timespec32 time;
	struct timespec32 settime;
	struct icb_tag *icb;
	struct ext_attr_hdr *eah;
	struct dev_spec_ear *ds;
	struct udf_vfs *udf_vfsp;
	timestruc_t now;
	uid_t uid;
	gid_t gid;


	ASSERT(pip);
	ASSERT(vap != NULL);

	ud_printf("ud_ialloc\n");

	if (((vap->va_mask & AT_ATIME) && TIMESPEC_OVERFLOW(&vap->va_atime)) ||
	    ((vap->va_mask & AT_MTIME) && TIMESPEC_OVERFLOW(&vap->va_mtime)))
		return (EOVERFLOW);

	udf_vfsp = pip->i_udf;
	lbsize = udf_vfsp->udf_lbsize;
	prn = pip->i_icb_prn;

	if ((err = ud_alloc_space(pip->i_vfs, prn,
	    0, 1, &blkno, &size, 0, 1)) != 0) {
		return (err);
	}
	loc = ud_xlate_to_daddr(udf_vfsp, prn, blkno, 1, &dummy);
	ASSERT(dummy == 1);

	bp = ud_bread(pip->i_dev, loc << udf_vfsp->udf_l2d_shift, lbsize);
	if (bp->b_flags & B_ERROR) {
		ud_free_space(pip->i_vfs, prn, blkno, size);
		return (EIO);
	}
	bzero(bp->b_un.b_addr, bp->b_bcount);
	fe = (struct file_entry *)bp->b_un.b_addr;

	uid = crgetuid(cr);
	fe->fe_uid = SWAP_32(uid);

	/*
	 * To determine the group-id of the created file:
	 * 1) If the gid is set in the attribute list (non-Sun & pre-4.0
	 *	clients are not likely to set the gid), then use it if
	 *	the process is privileged, belongs to the target group,
	 *	or the group is the same as the parent directory.
	 * 2) If the filesystem was not mounted with the Old-BSD-compatible
	 *	GRPID option, and the directory's set-gid bit is clear,
	 *	then use the process's gid.
	 * 3) Otherwise, set the group-id to the gid of the parent directory.
	 */
	if ((vap->va_mask & AT_GID) &&
	    ((vap->va_gid == pip->i_gid) || groupmember(vap->va_gid, cr) ||
	    secpolicy_vnode_create_gid(cr) == 0)) {
		/*
		 * XXX - is this only the case when a 4.0 NFS client, or a
		 * client derived from that code, makes a call over the wire?
		 */
		fe->fe_gid = SWAP_32(vap->va_gid);
	} else {
		gid = crgetgid(cr);
		fe->fe_gid = (pip->i_char & ISGID) ?
		    SWAP_32(pip->i_gid) : SWAP_32(gid);
	}

	imode = MAKEIMODE(vap->va_type, vap->va_mode);
	ichar = imode & (VSUID | VSGID | VSVTX);
	imode = UD_UPERM2DPERM(imode);

	/*
	 * Under solaris only the owner can
	 * change the attributes of files so set
	 * the change attribute bit only for user
	 */
	imode |= IATTR;

	/*
	 * File delete permissions on Solaris are
	 * the permissions on the directory but not the file
	 * when we create a file just inherit the directorys
	 * write permission to be the file delete permissions
	 * Atleast we will be consistent in the files we create
	 */
	imode |= (pip->i_perm & (IWRITE | IWRITE >> 5 | IWRITE >> 10)) << 3;

	fe->fe_perms = SWAP_32(imode);

	/*
	 * udf does not have a "." entry in dir's
	 * so even directories have only one link
	 */
	fe->fe_lcount = SWAP_16(1);

	fe->fe_info_len = 0;
	fe->fe_lbr = 0;

	gethrestime(&now);
	time.tv_sec = now.tv_sec;
	time.tv_nsec = now.tv_nsec;
	if (vap->va_mask & AT_ATIME) {
		TIMESPEC_TO_TIMESPEC32(&settime, &vap->va_atime)
		ud_utime2dtime(&settime, &fe->fe_acc_time);
	} else
		ud_utime2dtime(&time, &fe->fe_acc_time);
	if (vap->va_mask & AT_MTIME) {
		TIMESPEC_TO_TIMESPEC32(&settime, &vap->va_mtime)
		ud_utime2dtime(&settime, &fe->fe_mod_time);
	} else
		ud_utime2dtime(&time, &fe->fe_mod_time);
	ud_utime2dtime(&time, &fe->fe_attr_time);

	ud_update_regid(&fe->fe_impl_id);

	mutex_enter(&udf_vfsp->udf_lock);
	fe->fe_uniq_id = SWAP_64(udf_vfsp->udf_maxuniq);
	udf_vfsp->udf_maxuniq++;
	mutex_exit(&udf_vfsp->udf_lock);

	ea_len = 0;
	if ((vap->va_type == VBLK) || (vap->va_type == VCHR)) {
		eah = (struct ext_attr_hdr *)fe->fe_spec;
		ea_len = (sizeof (struct ext_attr_hdr) + 3) & ~3;
		eah->eah_ial = SWAP_32(ea_len);

		ds = (struct dev_spec_ear *)&fe->fe_spec[ea_len];
		ea_len += ud_make_dev_spec_ear(ds,
		    getmajor(vap->va_rdev), getminor(vap->va_rdev));
		ea_len = (ea_len + 3) & ~3;
		eah->eah_aal = SWAP_32(ea_len);
		ud_make_tag(udf_vfsp, &eah->eah_tag,
		    UD_EXT_ATTR_HDR, blkno, ea_len);
	}

	fe->fe_len_ear = SWAP_32(ea_len);
	fe->fe_len_adesc = 0;

	icb = &fe->fe_icb_tag;
	icb->itag_prnde = 0;
	icb->itag_strategy = SWAP_16(STRAT_TYPE4);
	icb->itag_param = 0;
	icb->itag_max_ent = SWAP_16(1);
	switch (vap->va_type) {
		case VREG :
			icb->itag_ftype = FTYPE_FILE;
			break;
		case VDIR :
			icb->itag_ftype = FTYPE_DIRECTORY;
			break;
		case VBLK :
			icb->itag_ftype = FTYPE_BLOCK_DEV;
			break;
		case VCHR :
			icb->itag_ftype = FTYPE_CHAR_DEV;
			break;
		case VLNK :
			icb->itag_ftype = FTYPE_SYMLINK;
			break;
		case VFIFO :
			icb->itag_ftype = FTYPE_FIFO;
			break;
		case VSOCK :
			icb->itag_ftype = FTYPE_C_ISSOCK;
			break;
		default :
			brelse(bp);
			goto error;
	}
	icb->itag_lb_loc = 0;
	icb->itag_lb_prn = 0;
	flags = ICB_FLAG_ONE_AD;
	if ((pip->i_char & ISGID) && (vap->va_type == VDIR)) {
		ichar |= ISGID;
	} else {
		if ((ichar & ISGID) &&
		    secpolicy_vnode_setids_setgids(cr,
		    (gid_t)SWAP_32(fe->fe_gid)) != 0) {
			ichar &= ~ISGID;
		}
	}
	if (ichar & ISUID) {
		flags |= ICB_FLAG_SETUID;
	}
	if (ichar & ISGID) {
		flags |= ICB_FLAG_SETGID;
	}
	if (ichar & ISVTX) {
		flags |= ICB_FLAG_STICKY;
	}
	icb->itag_flags = SWAP_16(flags);
	ud_make_tag(udf_vfsp, &fe->fe_tag, UD_FILE_ENTRY, blkno,
	    offsetof(struct file_entry, fe_spec) +
	    SWAP_32(fe->fe_len_ear) + SWAP_32(fe->fe_len_adesc));

	BWRITE2(bp);

	mutex_enter(&udf_vfsp->udf_lock);
	if (vap->va_type == VDIR) {
		udf_vfsp->udf_ndirs++;
	} else {
		udf_vfsp->udf_nfiles++;
	}
	mutex_exit(&udf_vfsp->udf_lock);

#ifdef	DEBUG
	{
		struct ud_inode *ip;

		if ((ip = ud_search_icache(pip->i_vfs, prn, blkno)) != NULL) {
			cmn_err(CE_NOTE, "duplicate %p %x\n",
			    (void *)ip, (uint32_t)ip->i_icb_lbano);
		}
	}
#endif

	if ((err = ud_iget(pip->i_vfs, prn, blkno, ipp, bp, cr)) != 0) {
error:
		ud_free_space(pip->i_vfs, prn, blkno, size);
		return (err);
	}

	return (0);

noinodes:
	cmn_err(CE_NOTE, "%s: out of inodes\n", pip->i_udf->udf_volid);
	return (ENOSPC);
}


void
ud_ifree(struct ud_inode *ip, vtype_t type)
{
	struct udf_vfs *udf_vfsp;
	struct buf *bp;

	ud_printf("ud_ifree\n");

	if (ip->i_vfs == NULL) {
		return;
	}

	udf_vfsp = (struct udf_vfs *)ip->i_vfs->vfs_data;
	bp = ud_bread(ip->i_dev, ip->i_icb_lbano <<
	    udf_vfsp->udf_l2d_shift, udf_vfsp->udf_lbsize);
	if (bp->b_flags & B_ERROR) {
		/*
		 * Error get rid of bp
		 */
		brelse(bp);
	} else {
		/*
		 * Just trash the inode
		 */
		bzero(bp->b_un.b_addr, 0x10);
		BWRITE(bp);
	}
	ud_free_space(ip->i_vfs, ip->i_icb_prn, ip->i_icb_block, 1);
	mutex_enter(&udf_vfsp->udf_lock);
	if (type == VDIR) {
		if (udf_vfsp->udf_ndirs > 1) {
			udf_vfsp->udf_ndirs--;
		}
	} else {
		if (udf_vfsp->udf_nfiles > 0) {
			udf_vfsp->udf_nfiles --;
		}
	}
	mutex_exit(&udf_vfsp->udf_lock);
}


/*
 * Free storage space associated with the specified inode.  The portion
 * to be freed is specified by lp->l_start and lp->l_len (already
 * normalized to a "whence" of 0).
 *
 * This is an experimental facility whose continued existence is not
 * guaranteed.  Currently, we only support the special case
 * of l_len == 0, meaning free to end of file.
 *
 * Blocks are freed in reverse order.  This FILO algorithm will tend to
 * maintain a contiguous free list much longer than FIFO.
 * See also ufs_itrunc() in ufs_inode.c.
 *
 * Bug: unused bytes in the last retained block are not cleared.
 * This may result in a "hole" in the file that does not read as zeroes.
 */
int32_t
ud_freesp(struct vnode *vp,
	struct flock64 *lp,
	int32_t flag, struct cred *cr)
{
	int32_t i;
	struct ud_inode *ip = VTOI(vp);
	int32_t error;

	ASSERT(vp->v_type == VREG);
	ASSERT(lp->l_start >= (offset_t)0);	/* checked by convoff */

	ud_printf("udf_freesp\n");

	if (lp->l_len != 0) {
		return (EINVAL);
	}

	rw_enter(&ip->i_contents, RW_READER);
	if (ip->i_size == (u_offset_t)lp->l_start) {
		rw_exit(&ip->i_contents);
		return (0);
	}

	/*
	 * Check if there is any active mandatory lock on the
	 * range that will be truncated/expanded.
	 */
	if (MANDLOCK(vp, ip->i_char)) {
		offset_t save_start;

		save_start = lp->l_start;

		if (ip->i_size < lp->l_start) {
			/*
			 * "Truncate up" case: need to make sure there
			 * is no lock beyond current end-of-file. To
			 * do so, we need to set l_start to the size
			 * of the file temporarily.
			 */
			lp->l_start = ip->i_size;
		}
		lp->l_type = F_WRLCK;
		lp->l_sysid = 0;
		lp->l_pid = ttoproc(curthread)->p_pid;
		i = (flag & (FNDELAY|FNONBLOCK)) ? 0 : SLPFLCK;
		rw_exit(&ip->i_contents);
		if ((i = reclock(vp, lp, i, 0, lp->l_start, NULL)) != 0 ||
		    lp->l_type != F_UNLCK) {
			return (i ? i : EAGAIN);
		}
		rw_enter(&ip->i_contents, RW_READER);

		lp->l_start = save_start;
	}
	/*
	 * Make sure a write isn't in progress (allocating blocks)
	 * by acquiring i_rwlock (we promised ufs_bmap we wouldn't
	 * truncate while it was allocating blocks).
	 * Grab the locks in the right order.
	 */
	rw_exit(&ip->i_contents);
	rw_enter(&ip->i_rwlock, RW_WRITER);
	rw_enter(&ip->i_contents, RW_WRITER);
	error = ud_itrunc(ip, lp->l_start, 0, cr);
	rw_exit(&ip->i_contents);
	rw_exit(&ip->i_rwlock);
	return (error);
}



/*
 * Cache is implemented by
 * allocating a cluster of blocks
 */
int32_t
ud_alloc_from_cache(struct udf_vfs *udf_vfsp,
	struct ud_part *part, uint32_t *blkno)
{
	uint32_t bno, sz;
	int32_t error, index, free = 0;

	ud_printf("ud_alloc_from_cache\n");

	ASSERT(udf_vfsp);

	mutex_enter(&udf_vfsp->udf_lock);
	if (part->udp_cache_count == 0) {
		mutex_exit(&udf_vfsp->udf_lock);
		/* allocate new cluster */
		if ((error = ud_alloc_space(udf_vfsp->udf_vfs,
		    part->udp_number, 0, CLSTR_SIZE, &bno, &sz, 1, 0)) != 0) {
			return (error);
		}
		if (sz == 0) {
			return (ENOSPC);
		}
		mutex_enter(&udf_vfsp->udf_lock);
		if (part->udp_cache_count == 0) {
			for (index = 0; index < sz; index++, bno++) {
				part->udp_cache[index] = bno;
			}
			part->udp_cache_count = sz;
		} else {
			free = 1;
		}
	}
	part->udp_cache_count--;
	*blkno = part->udp_cache[part->udp_cache_count];
	mutex_exit(&udf_vfsp->udf_lock);
	if (free) {
		ud_free_space(udf_vfsp->udf_vfs, part->udp_number, bno, sz);
	}
	return (0);
}

/*
 * Will be called from unmount
 */
int32_t
ud_release_cache(struct udf_vfs *udf_vfsp)
{
	int32_t i, error = 0;
	struct ud_part *part;
	uint32_t start, nblks;

	ud_printf("ud_release_cache\n");

	mutex_enter(&udf_vfsp->udf_lock);
	part = udf_vfsp->udf_parts;
	for (i = 0; i < udf_vfsp->udf_npart; i++, part++) {
		if (part->udp_cache_count) {
			nblks = part->udp_cache_count;
			start = part->udp_cache[0];
			part->udp_cache_count = 0;
			mutex_exit(&udf_vfsp->udf_lock);
			ud_free_space(udf_vfsp->udf_vfs,
			    part->udp_number, start, nblks);
			mutex_enter(&udf_vfsp->udf_lock);
		}
	}
	mutex_exit(&udf_vfsp->udf_lock);
	return (error);
}