FREE_LOCK_INTERLOCKED(interlock);
s = FREE_LOCK_INTERLOCKED(interlock);
STATIC	struct dirrem *newdirrem __P((struct buf *, struct inode *,	    struct inode *, int, struct dirrem **));STATIC	void free_diradd __P((struct diradd *));STATIC	void free_allocindir __P((struct allocindir *, struct inodedep *));STATIC	int indir_trunc __P((struct inode *, ufs_daddr_t, int, ufs_lbn_t,	    long *));STATIC	void deallocate_dependencies __P((struct buf *, struct inodedep *));STATIC	void free_allocdirect __P((struct allocdirectlst *,	    struct allocdirect *, int));STATIC	int check_inode_unwritten __P((struct inodedep *));STATIC	int free_inodedep __P((struct inodedep *));STATIC	void handle_workitem_freeblocks __P((struct freeblks *));STATIC	void merge_inode_lists __P((struct inodedep *));STATIC	void setup_allocindir_phase2 __P((struct buf *, struct inode *,	    struct allocindir *));STATIC	struct allocindir *newallocindir __P((struct inode *, int, ufs_daddr_t,	    ufs_daddr_t));STATIC	void handle_workitem_freefrag __P((struct freefrag *));STATIC	struct freefrag *newfreefrag __P((struct inode *, ufs_daddr_t, long));STATIC	void allocdirect_merge __P((struct allocdirectlst *,	    struct allocdirect *, struct allocdirect *));STATIC	struct bmsafemap *bmsafemap_lookup __P((struct buf *));STATIC	int newblk_lookup __P((struct fs *, ufs_daddr_t, int,	    struct newblk **));STATIC	int inodedep_lookup __P((struct fs *, ino_t, int, struct inodedep **));STATIC	int pagedep_lookup __P((struct inode *, ufs_lbn_t, int,	    struct pagedep **));STATIC	void pause_timer __P((void *));STATIC	int request_cleanup __P((int, int));STATIC	int process_worklist_item __P((struct mount *, int));STATIC	void add_to_worklist __P((struct worklist *));STATIC struct buf *softdep_setup_pagecache __P((struct inode *, ufs_lbn_t,						long));STATIC void softdep_collect_pagecache __P((struct inode *));STATIC void softdep_free_pagecache __P((struct inode *));STATIC struct vnode *softdep_lookupvp(struct fs *, ino_t);STATIC struct buf *softdep_lookup_pcbp __P((struct vnode *, ufs_lbn_t));void softdep_pageiodone __P((struct buf *));/* * Exported softdep operations. */void softdep_disk_io_initiation __P((struct buf *));void softdep_disk_write_complete __P((struct buf *));void softdep_deallocate_dependencies __P((struct buf *));void softdep_move_dependencies __P((struct buf *, struct buf *));int softdep_count_dependencies __P((struct buf *bp, int, int));struct bio_ops bioops = {	softdep_disk_io_initiation,		/* io_start */	softdep_disk_write_complete,		/* io_complete */	softdep_deallocate_dependencies,	/* io_deallocate */	softdep_move_dependencies,		/* io_movedeps */	softdep_count_dependencies,		/* io_countdeps */	softdep_pageiodone,			/* io_pagedone */};/* * Locking primitives. * * For a uniprocessor, all we need to do is protect against disk * interrupts. For a multiprocessor, this lock would have to be * a mutex. A single mutex is used throughout this file, though * finer grain locking could be used if contention warranted it. * * For a multiprocessor, the sleep call would accept a lock and * release it after the sleep processing was complete. In a uniprocessor * implementation there is no such interlock, so we simple mark * the places where it needs to be done with the `interlocked' form * of the lock calls. Since the uniprocessor sleep already interlocks * the spl, there is nothing that really needs to be done. */#ifndef /* NOT */ DEBUGSTATIC struct lockit {	int	lkt_spl;} lk = { 0 };#define ACQUIRE_LOCK(lk)		(lk)->lkt_spl = splbio()#define FREE_LOCK(lk)			splx((lk)->lkt_spl)#define ACQUIRE_LOCK_INTERLOCKED(lk)#define FREE_LOCK_INTERLOCKED(lk)#else /* DEBUG */STATIC struct lockit {	int	lkt_spl;	pid_t	lkt_held;	int     lkt_line;} lk = { 0, -1 };STATIC int lockcnt;STATIC	void acquire_lock __P((struct lockit *, int));STATIC	void free_lock __P((struct lockit *, int));STATIC	void acquire_lock_interlocked __P((struct lockit *, int));STATIC	void free_lock_interlocked __P((struct lockit *, int));#define ACQUIRE_LOCK(lk)		acquire_lock(lk, __LINE__)#define FREE_LOCK(lk)			free_lock(lk, __LINE__)#define ACQUIRE_LOCK_INTERLOCKED(lk)	acquire_lock_interlocked(lk, __LINE__)#define FREE_LOCK_INTERLOCKED(lk)	free_lock_interlocked(lk, __LINE__)STATIC voidacquire_lock(lk, line)	struct lockit *lk;	int line;{	pid_t holder;	int original_line;	if (lk->lkt_held != -1) {		holder = lk->lkt_held;		original_line = lk->lkt_line;		FREE_LOCK(lk);		if (holder == CURPROC->p_pid)			panic("softdep_lock: locking against myself, acquired at line %d, relocked at line %d", original_line, line);		else			panic("softdep_lock: lock held by %d, acquired at line %d, relocked at line %d", holder, original_line, line);	}	lk->lkt_spl = splbio();	lk->lkt_held = CURPROC->p_pid;	lk->lkt_line = line;	lockcnt++;}STATIC voidfree_lock(lk, line)	struct lockit *lk;	int line;{	if (lk->lkt_held == -1)		panic("softdep_unlock: lock not held at line %d", line);	lk->lkt_held = -1;	splx(lk->lkt_spl);}STATIC voidacquire_lock_interlocked(lk, line)	struct lockit *lk;	int line;{	pid_t holder;	int original_line;	if (lk->lkt_held != -1) {		holder = lk->lkt_held;		original_line = lk->lkt_line;		FREE_LOCK_INTERLOCKED(lk);		if (holder == CURPROC->p_pid)			panic("softdep_lock: locking against myself, acquired at line %d, relocked at line %d", original_line, line);		else			panic("softdep_lock: lock held by %d, acquired at line %d, relocked at line %d", holder, original_line, line);	}	lk->lkt_held = CURPROC->p_pid;	lk->lkt_line = line;	lockcnt++;}STATIC voidfree_lock_interlocked(lk, line)	struct lockit *lk;	int line;{	if (lk->lkt_held == -1)		panic("softdep_unlock_interlocked: lock not held at line %d", line);	lk->lkt_held = -1;}#endif /* DEBUG *//* * Place holder for real semaphores. */struct sema {	int	value;	pid_t	holder;	char	*name;	int	prio;	int	timo;};STATIC	void sema_init __P((struct sema *, char *, int, int));STATIC	int sema_get __P((struct sema *, struct lockit *));STATIC	void sema_release __P((struct sema *));STATIC voidsema_init(semap, name, prio, timo)	struct sema *semap;	char *name;	int prio, timo;{	semap->holder = -1;	semap->value = 0;	semap->name = name;	semap->prio = prio;	semap->timo = timo;}STATIC intsema_get(semap, interlock)	struct sema *semap;	struct lockit *interlock;{	if (semap->value++ > 0) {		if (interlock != NULL)			FREE_LOCK_INTERLOCKED(interlock);		tsleep((caddr_t)semap, semap->prio, semap->name, semap->timo);		if (interlock != NULL) {			ACQUIRE_LOCK_INTERLOCKED(interlock);			FREE_LOCK(interlock);		}		return (0);	}	semap->holder = CURPROC->p_pid;	if (interlock != NULL)		FREE_LOCK(interlock);	return (1);}STATIC voidsema_release(semap)	struct sema *semap;{	if (semap->value <= 0 || semap->holder != CURPROC->p_pid) {		if (lk.lkt_held != -1)			FREE_LOCK(&lk);		panic("sema_release: not held");	}	if (--semap->value > 0) {		semap->value = 0;		wakeup(semap);	}	semap->holder = -1;}/* * Worklist queue management. * These routines require that the lock be held. */#ifndef /* NOT */ DEBUG#define WORKLIST_INSERT(head, item) do {	\	(item)->wk_state |= ONWORKLIST;		\	LIST_INSERT_HEAD(head, item, wk_list);	\} while (0)#define WORKLIST_REMOVE(item) do {		\	(item)->wk_state &= ~ONWORKLIST;	\	LIST_REMOVE(item, wk_list);		\} while (0)#define WORKITEM_FREE(item, type) FREE(item, DtoM(type))#else /* DEBUG */STATIC	void worklist_insert __P((struct workhead *, struct worklist *));STATIC	void worklist_remove __P((struct worklist *));STATIC	void workitem_free __P((struct worklist *, int));#define WORKLIST_INSERT(head, item) worklist_insert(head, item)#define WORKLIST_REMOVE(item) worklist_remove(item)#define WORKITEM_FREE(item, type) workitem_free((struct worklist *)item, type)STATIC voidworklist_insert(head, item)	struct workhead *head;	struct worklist *item;{	if (lk.lkt_held == -1)		panic("worklist_insert: lock not held");	if (item->wk_state & ONWORKLIST) {		FREE_LOCK(&lk);		panic("worklist_insert: already on list");	}	item->wk_state |= ONWORKLIST;	LIST_INSERT_HEAD(head, item, wk_list);}STATIC voidworklist_remove(item)	struct worklist *item;{	if (lk.lkt_held == -1)		panic("worklist_remove: lock not held");	if ((item->wk_state & ONWORKLIST) == 0) {		FREE_LOCK(&lk);		panic("worklist_remove: not on list");	}	item->wk_state &= ~ONWORKLIST;	LIST_REMOVE(item, wk_list);}STATIC voidworkitem_free(item, type)	struct worklist *item;	int type;{	if (item->wk_state & ONWORKLIST) {		if (lk.lkt_held != -1)			FREE_LOCK(&lk);		panic("workitem_free: still on list");	}	if (item->wk_type != type) {		if (lk.lkt_held != -1)			FREE_LOCK(&lk);		panic("workitem_free: type mismatch");	}	FREE(item, DtoM(type));}#endif /* DEBUG *//* * Workitem queue management */STATIC struct workhead softdep_workitem_pending;STATIC int num_on_worklist;	/* number of worklist items to be processed */STATIC int softdep_worklist_busy; /* 1 => trying to do unmount */STATIC int softdep_worklist_req; /* serialized waiters */STATIC int max_softdeps;	/* maximum number of structs before slowdown */STATIC int tickdelay = 2;	/* number of ticks to pause during slowdown */STATIC int proc_waiting;	/* tracks whether we have a timeout posted */STATIC int *stat_countp;	/* statistic to count in proc_waiting timeout */STATIC struct timeout proc_waiting_timeout; STATIC struct proc *filesys_syncer; /* proc of filesystem syncer process */STATIC int req_clear_inodedeps;	/* syncer process flush some inodedeps */#define FLUSH_INODES	1STATIC int req_clear_remove;	/* syncer process flush some freeblks */#define FLUSH_REMOVE	2/* * runtime statistics */STATIC int stat_worklist_push;	/* number of worklist cleanups */STATIC int stat_blk_limit_push;	/* number of times block limit neared */STATIC int stat_ino_limit_push;	/* number of times inode limit neared */STATIC int stat_blk_limit_hit;	/* number of times block slowdown imposed */STATIC int stat_ino_limit_hit;	/* number of times inode slowdown imposed */STATIC int stat_sync_limit_hit;	/* number of synchronous slowdowns imposed */STATIC int stat_indir_blk_ptrs;	/* bufs redirtied as indir ptrs not written */STATIC int stat_inode_bitmap;	/* bufs redirtied as inode bitmap not written */STATIC int stat_direct_blk_ptrs;/* bufs redirtied as direct ptrs not written */STATIC int stat_dir_entry;	/* bufs redirtied as dir entry cannot write */#ifdef DEBUG#include <uvm/uvm_extern.h>#include <sys/sysctl.h>struct ctldebug debug20 = { "max_softdeps", &max_softdeps };struct ctldebug debug21 = { "tickdelay", &tickdelay };struct ctldebug debug22 = { "worklist_push", &stat_worklist_push };struct ctldebug debug23 = { "blk_limit_push", &stat_blk_limit_push };struct ctldebug debug24 = { "ino_limit_push", &stat_ino_limit_push };struct ctldebug debug25 = { "blk_limit_hit", &stat_blk_limit_hit };struct ctldebug debug26 = { "ino_limit_hit", &stat_ino_limit_hit };struct ctldebug debug27 = { "sync_limit_hit", &stat_sync_limit_hit }; struct ctldebug debug28 = { "indir_blk_ptrs", &stat_indir_blk_ptrs };struct ctldebug debug29 = { "inode_bitmap", &stat_inode_bitmap };struct ctldebug debug30 = { "direct_blk_ptrs", &stat_direct_blk_ptrs };struct ctldebug debug31 = { "dir_entry", &stat_dir_entry };#endif /* DEBUG *//* * Add an item to the end of the work queue. * This routine requires that the lock be held. * This is the only routine that adds items to the list. * The following routine is the only one that removes items * and does so in order from first to last. */STATIC voidadd_to_worklist(wk)	struct worklist *wk;{	static struct worklist *worklist_tail;	if (wk->wk_state & ONWORKLIST) {		if (lk.lkt_held != -1)			FREE_LOCK(&lk);		panic("add_to_worklist: already on list");	}	wk->wk_state |= ONWORKLIST;	if (LIST_FIRST(&softdep_workitem_pending) == NULL)		LIST_INSERT_HEAD(&softdep_workitem_pending, wk, wk_list);	else		LIST_INSERT_AFTER(worklist_tail, wk, wk_list);	worklist_tail = wk;	num_on_worklist += 1;}/* * Process that runs once per second to handle items in the background queue. * * Note that we ensure that everything is done in the order in which they * appear in the queue. The code below depends on this property to ensure * that blocks of a file are freed before the inode itself is freed. This * ordering ensures that no new <vfsid, inum, lbn> triples will be generated * until all the old ones have been purged from the dependency lists. */int softdep_process_worklist(matchmnt)	struct mount *matchmnt;{	struct proc *p = CURPROC;	int matchcnt, loopcount;	struct timeval starttime;	/*	 * Record the process identifier of our caller so that we can give	 * this process preferential treatment in request_cleanup below.	 * We can't do this in softdep_initialize, because the syncer doesn't	 * have to run then.	 * NOTE! This function _could_ be called with a curproc != syncerproc.	 */	filesys_syncer = syncerproc;	matchcnt = 0;	/*	 * There is no danger of having multiple processes run this	 * code, but we have to single-thread it when softdep_flushfiles()	 * is in operation to get an accurate count of the number of items	 * related to its mount point that are in the list.	 */	if (matchmnt == NULL) {		if (softdep_worklist_busy < 0)			return(-1);		softdep_worklist_busy += 1;	}	/*	 * If requested, try removing inode or removal dependencies.	 */	if (req_clear_inodedeps) {		clear_inodedeps(p);		req_clear_inodedeps -= 1;		wakeup_one(&proc_waiting);	}	if (req_clear_remove) {		clear_remove(p);		req_clear_remove -= 1;		wakeup_one(&proc_waiting);	}	loopcount = 1;	starttime = time;	while (num_on_worklist > 0) {		matchcnt += process_worklist_item(matchmnt, 0);		/*		 * If a umount operation wants to run the worklist		 * accurately, abort.		 */		if (softdep_worklist_req && matchmnt == NULL) {			matchcnt = -1;			break;		}		/*		 * If requested, try removing inode or removal dependencies.		 */		if (req_clear_inodedeps) {			clear_inodedeps(p);			req_clear_inodedeps -= 1;			wakeup_one(&proc_waiting);		}		if (req_clear_remove) {			clear_remove(p);			req_clear_remove -= 1;			wakeup_one(&proc_waiting);		}		/*		 * We do not generally want to stop for buffer space, but if		 * we are really being a buffer hog, we will stop and wait.		 */#if 0		if (loopcount++ % 128 == 0)			bwillwrite();#endif		/*		 * Never allow processing to run for more than one		 * second. Otherwise the other syncer tasks may get		 * excessively backlogged.		 */		{			struct timeval diff;			timersub(&time, &starttime, &diff);			if (diff.tv_sec != 0 && matchmnt == NULL) {				matchcnt = -1;				break;			}		}	}	if (matchmnt == NULL) {		softdep_worklist_busy -= 1;		if (softdep_worklist_req && softdep_worklist_busy == 0)			wakeup(&softdep_worklist_req);	}	return (matchcnt);}/* * Process one item on the worklist. */STATIC intprocess_worklist_item(matchmnt, flags)	struct mount *matchmnt;	int flags;{	struct worklist *wk;	struct dirrem *dirrem;	struct mount *mp;	struct vnode *vp;	int matchcnt = 0;	ACQUIRE_LOCK(&lk);	/*	 * Normally we just process each item on the worklist in order.	 * However, if we are in a situation where we cannot lock any	 * inodes, we have to skip over any dirrem requests whose	 * vnodes are resident and locked.	 */	LIST_FOREACH(wk, &softdep_workitem_pending, wk_list) {		if ((flags & LK_NOWAIT) == 0 || wk->wk_type != D_DIRREM)			break;		dirrem = WK_DIRREM(wk);		vp = ufs_ihashlookup(VFSTOUFS(dirrem->dm_mnt)->um_dev,		    dirrem->dm_oldinum);		if (vp == NULL || !VOP_ISLOCKED(vp))			break;	}	if (wk == 0) {		FREE_LOCK(&lk);		return (0);	}	WORKLIST_REMOVE(wk);	num_on_worklist -= 1;	FREE_LOCK(&lk);	switch (wk->wk_type) {	case D_DIRREM:		/* removal of a directory entry */		mp = WK_DIRREM(wk)->dm_mnt;#if 0		if (vn_write_suspend_wait(NULL, mp, V_NOWAIT))			panic("%s: dirrem on suspended filesystem",				"process_worklist_item");#endif		if (mp == matchmnt)			matchcnt += 1;		handle_workitem_remove(WK_DIRREM(wk));		break;	case D_FREEBLKS:		/* releasing blocks and/or fragments from a file */		mp = WK_FREEBLKS(wk)->fb_mnt;#if 0		if (vn_write_suspend_wait(NULL, mp, V_NOWAIT))			panic("%s: freeblks on suspended filesystem",				"process_worklist_item");#endif		if (mp == matchmnt)			matchcnt += 1;		handle_workitem_freeblocks(WK_FREEBLKS(wk));		break;	case D_FREEFRAG:		/* releasing a fragment when replaced as a file grows */		mp = WK_FREEFRAG(wk)->ff_mnt;#if 0		if (vn_write_suspend_wait(NULL, mp, V_NOWAIT))			panic("%s: freefrag on suspended filesystem",				"process_worklist_item");#endif		if (mp == matchmnt)			matchcnt += 1;		handle_workitem_freefrag(WK_FREEFRAG(wk));		break;	case D_FREEFILE:		/* releasing an inode when its link count drops to 0 */		mp = WK_FREEFILE(wk)->fx_mnt;#if 0		if (vn_write_suspend_wait(NULL, mp, V_NOWAIT))			panic("%s: freefile on suspended filesystem",				"process_worklist_item");#endif		if (mp == matchmnt)			matchcnt += 1;		handle_workitem_freefile(WK_FREEFILE(wk));		break;	default:		panic("%s_process_worklist: Unknown type %s",		    "softdep", TYPENAME(wk->wk_type));		/* NOTREACHED */	}	return (matchcnt);}/* * Move dependencies from one buffer to another. */voidsoftdep_move_dependencies(oldbp, newbp)	struct buf *oldbp;	struct buf *newbp;{	struct worklist *wk, *wktail;	if (LIST_FIRST(&newbp->b_dep) != NULL)		panic("softdep_move_dependencies: need merge code");	wktail = 0;	ACQUIRE_LOCK(&lk);	while ((wk = LIST_FIRST(&oldbp->b_dep)) != NULL) {		LIST_REMOVE(wk, wk_list);		if (wktail == 0)			LIST_INSERT_HEAD(&newbp->b_dep, wk, wk_list);		else			LIST_INSERT_AFTER(wktail, wk, wk_list);		wktail = wk;	}	FREE_LOCK(&lk);}/* * Purge the work list of all items associated with a particular mount point. */intsoftdep_flushworklist(oldmnt, countp, p)	struct mount *oldmnt;	int *countp;	struct proc *p;{	struct vnode *devvp;	int count, error = 0;	/*	 * Await our turn to clear out the queue, then serialize access.	 */	while (softdep_worklist_busy) {		softdep_worklist_req += 1;		tsleep(&softdep_worklist_req, PRIBIO, "softflush", 0);		softdep_worklist_req -= 1;	}	softdep_worklist_busy = -1;	/*	 * Alternately flush the block device associated with the mount	 * point and process any dependencies that the flushing	 * creates. We continue until no more worklist dependencies	 * are found.	 */	*countp = 0;	devvp = VFSTOUFS(oldmnt)->um_devvp;	while ((count = softdep_process_worklist(oldmnt)) > 0) {		*countp += count;		vn_lock(devvp, LK_EXCLUSIVE | LK_RETRY, p);		error = VOP_FSYNC(devvp, p->p_ucred, MNT_WAIT, p);		VOP_UNLOCK(devvp, 0, p);		if (error)			break;	}	softdep_worklist_busy = 0;	if (softdep_worklist_req)		wakeup(&softdep_worklist_req);	return (error);}/* * Flush all vnodes and worklist items associated with a specified mount point. */intsoftdep_flushfiles(oldmnt, flags, p)	struct mount *oldmnt;	int flags;	struct proc *p;{	int error, count, loopcnt;	/*	 * Alternately flush the vnodes associated with the mount	 * point and process any dependencies that the flushing	 * creates. In theory, this loop can happen at most twice,	 * but we give it a few extra just to be sure.	 */	for (loopcnt = 10; loopcnt > 0; loopcnt--) {		/*		 * Do another flush in case any vnodes were brought in		 * as part of the cleanup operations.		 */		if ((error = ffs_flushfiles(oldmnt, flags, p)) != 0)			break;		if ((error = softdep_flushworklist(oldmnt, &count, p)) != 0 ||		    count == 0)			break;	}	/*	 * If we are unmounting then it is an error to fail. If we	 * are simply trying to downgrade to read-only, then filesystem	 * activity can keep us busy forever, so we just fail with EBUSY.	 */	if (loopcnt == 0) {		if (oldmnt->mnt_flag & MNT_UNMOUNT)			panic("softdep_flushfiles: looping");		error = EBUSY;	}	return (error);}/* * Structure hashing. *  * There are three types of structures that can be looked up: *	1) pagedep structures identified by mount point, inode number, *	   and logical block. *	2) inodedep structures identified by mount point and inode number. *	3) newblk structures identified by mount point and *	   physical block number. * * The "pagedep" and "inodedep" dependency structures are hashed * separately from the file blocks and inodes to which they correspond. * This separation helps when the in-memory copy of an inode or * file block must be replaced. It also obviates the need to access * an inode or file page when simply updating (or de-allocating) * dependency structures. Lookup of newblk structures is needed to * find newly allocated blocks when trying to associate them with * their allocdirect or allocindir structure. * * The lookup routines optionally create and hash a new instance when * an existing entry is not found. */#define DEPALLOC	0x0001	/* allocate structure if lookup fails */#define NODELAY         0x0002  /* cannot do background work *//* * Structures and routines associated with pagedep caching. */LIST_HEAD(pagedep_hashhead, pagedep) *pagedep_hashtbl;u_long	pagedep_hash;		/* size of hash table - 1 */#define	PAGEDEP_HASH(mp, inum, lbn) \	(&pagedep_hashtbl[((((register_t)(mp)) >> 13) + (inum) + (lbn)) & \	    pagedep_hash])STATIC struct sema pagedep_in_progress;/* * Look up a pagedep. Return 1 if found, 0 if not found. * If not found, allocate if DEPALLOC flag is passed. * Found or allocated entry is returned in pagedeppp. * This routine must be called with splbio interrupts blocked. */STATIC intpagedep_lookup(ip, lbn, flags, pagedeppp)	struct inode *ip;	ufs_lbn_t lbn;	int flags;	struct pagedep **pagedeppp;{	struct pagedep *pagedep;	struct pagedep_hashhead *pagedephd;	struct mount *mp;	int i;#ifdef DEBUG	if (lk.lkt_held == -1)		panic("pagedep_lookup: lock not held");#endif	mp = ITOV(ip)->v_mount;	pagedephd = PAGEDEP_HASH(mp, ip->i_number, lbn);top:	LIST_FOREACH(pagedep, pagedephd, pd_hash)		if (ip->i_number == pagedep->pd_ino &&		    lbn == pagedep->pd_lbn &&		    mp == pagedep->pd_mnt)			break;	if (pagedep) {		*pagedeppp = pagedep;		return (1);	}	if ((flags & DEPALLOC) == 0) {		*pagedeppp = NULL;		return (0);	}	if (sema_get(&pagedep_in_progress, &lk) == 0) {		ACQUIRE_LOCK(&lk);		goto top;	}	MALLOC(pagedep, struct pagedep *, sizeof(struct pagedep), M_PAGEDEP,		M_SOFTDEP_FLAGS);	bzero(pagedep, sizeof(struct pagedep));	pagedep->pd_list.wk_type = D_PAGEDEP;	pagedep->pd_mnt = mp;	pagedep->pd_ino = ip->i_number;	pagedep->pd_lbn = lbn;	LIST_INIT(&pagedep->pd_dirremhd);	LIST_INIT(&pagedep->pd_pendinghd);	for (i = 0; i < DAHASHSZ; i++)		LIST_INIT(&pagedep->pd_diraddhd[i]);	ACQUIRE_LOCK(&lk);	LIST_INSERT_HEAD(pagedephd, pagedep, pd_hash);	sema_release(&pagedep_in_progress);	*pagedeppp = pagedep;	return (0);}/* * Structures and routines associated with inodedep caching. */LIST_HEAD(inodedep_hashhead, inodedep) *inodedep_hashtbl;STATIC u_long	inodedep_hash;	/* size of hash table - 1 */STATIC long	num_inodedep;	/* number of inodedep allocated */#define	INODEDEP_HASH(fs, inum) \      (&inodedep_hashtbl[((((register_t)(fs)) >> 13) + (inum)) & inodedep_hash])STATIC struct sema inodedep_in_progress;/* * Look up a inodedep. Return 1 if found, 0 if not found. * If not found, allocate if DEPALLOC flag is passed. * Found or allocated entry is returned in inodedeppp. * This routine must be called with splbio interrupts blocked. */STATIC intinodedep_lookup(fs, inum, flags, inodedeppp)	struct fs *fs;	ino_t inum;	int flags;	struct inodedep **inodedeppp;{	struct inodedep *inodedep;	struct inodedep_hashhead *inodedephd;	int firsttry;#ifdef DEBUG	if (lk.lkt_held == -1)		panic("inodedep_lookup: lock not held");#endif	firsttry = 1;	inodedephd = INODEDEP_HASH(fs, inum);top:	LIST_FOREACH(inodedep, inodedephd, id_hash)		if (inum == inodedep->id_ino && fs == inodedep->id_fs)			break;	if (inodedep) {		*inodedeppp = inodedep;		return (1);	}	if ((flags & DEPALLOC) == 0) {		*inodedeppp = NULL;		return (0);	}	/*	 * If we are over our limit, try to improve the situation.	 */	if (num_inodedep > max_softdeps && firsttry && (flags & NODELAY) == 0 &&	    request_cleanup(FLUSH_INODES, 1)) {		firsttry = 0;		goto top;	}	if (sema_get(&inodedep_in_progress, &lk) == 0) {		ACQUIRE_LOCK(&lk);		goto top;	}	num_inodedep += 1;	MALLOC(inodedep, struct inodedep *, sizeof(struct inodedep),		M_INODEDEP, M_SOFTDEP_FLAGS);	inodedep->id_list.wk_type = D_INODEDEP;	inodedep->id_fs = fs;	inodedep->id_ino = inum;	inodedep->id_state = ALLCOMPLETE;	inodedep->id_nlinkdelta = 0;	inodedep->id_savedino = NULL;	inodedep->id_savedsize = -1;	inodedep->id_buf = NULL;	LIST_INIT(&inodedep->id_pendinghd);	LIST_INIT(&inodedep->id_inowait);	LIST_INIT(&inodedep->id_bufwait);	TAILQ_INIT(&inodedep->id_inoupdt);	TAILQ_INIT(&inodedep->id_newinoupdt);	ACQUIRE_LOCK(&lk);	LIST_INSERT_HEAD(inodedephd, inodedep, id_hash);	sema_release(&inodedep_in_progress);	*inodedeppp = inodedep;	return (0);}/* * Structures and routines associated with newblk caching. */LIST_HEAD(newblk_hashhead, newblk) *newblk_hashtbl;u_long	newblk_hash;		/* size of hash table - 1 */#define	NEWBLK_HASH(fs, inum) \	(&newblk_hashtbl[((((register_t)(fs)) >> 13) + (inum)) & newblk_hash])STATIC struct sema newblk_in_progress;/* * Look up a newblk. Return 1 if found, 0 if not found. * If not found, allocate if DEPALLOC flag is passed. * Found or allocated entry is returned in newblkpp. */STATIC intnewblk_lookup(fs, newblkno, flags, newblkpp)	struct fs *fs;	ufs_daddr_t newblkno;	int flags;	struct newblk **newblkpp;{	struct newblk *newblk;	struct newblk_hashhead *newblkhd;	newblkhd = NEWBLK_HASH(fs, newblkno);top:	LIST_FOREACH(newblk, newblkhd, nb_hash)		if (newblkno == newblk->nb_newblkno && fs == newblk->nb_fs)			break;	if (newblk) {		*newblkpp = newblk;		return (1);	}	if ((flags & DEPALLOC) == 0) {		*newblkpp = NULL;		return (0);	}	if (sema_get(&newblk_in_progress, 0) == 0)		goto top;	MALLOC(newblk, struct newblk *, sizeof(struct newblk),		M_NEWBLK, M_SOFTDEP_FLAGS);	newblk->nb_state = 0;	newblk->nb_fs = fs;	newblk->nb_newblkno = newblkno;	LIST_INSERT_HEAD(newblkhd, newblk, nb_hash);	sema_release(&newblk_in_progress);	*newblkpp = newblk;	return (0);}/* * Executed during filesystem system initialization before * mounting any file systems. */void softdep_initialize(){	int i;	LIST_INIT(&mkdirlisthd);	LIST_INIT(&softdep_workitem_pending);#ifdef KMEMSTATS	max_softdeps = min (desiredvnodes * 8,	    kmemstats[M_INODEDEP].ks_limit / (2 * sizeof(struct inodedep)));#else	max_softdeps = desiredvnodes * 4;#endif	pagedep_hashtbl = hashinit(desiredvnodes / 5, M_PAGEDEP, M_WAITOK,	    &pagedep_hash);	sema_init(&pagedep_in_progress, "pagedep", PRIBIO, 0);	inodedep_hashtbl = hashinit(desiredvnodes, M_INODEDEP, M_WAITOK,	    &inodedep_hash);	sema_init(&inodedep_in_progress, "inodedep", PRIBIO, 0);	newblk_hashtbl = hashinit(64, M_NEWBLK, M_WAITOK, &newblk_hash);	sema_init(&newblk_in_progress, "newblk", PRIBIO, 0);	timeout_set(&proc_waiting_timeout, pause_timer, 0);	pool_init(&sdpcpool, sizeof(struct buf), 0, 0, 0, "sdpcpool",	    0, pool_page_alloc_nointr, pool_page_free_nointr, M_TEMP);	for (i = 0; i < PCBPHASHSIZE; i++) {		LIST_INIT(&pcbphashhead[i]);	}}/* * Called at mount time to notify the dependency code that a * filesystem wishes to use it. */intsoftdep_mount(devvp, mp, fs, cred)	struct vnode *devvp;	struct mount *mp;	struct fs *fs;	struct ucred *cred;{	struct csum cstotal;	struct cg *cgp;	struct buf *bp;	int error, cyl;	/*	 * When doing soft updates, the counters in the	 * superblock may have gotten out of sync, so we have	 * to scan the cylinder groups and recalculate them.	 */	if ((fs->fs_flags & FS_UNCLEAN) == 0)		return (0);	bzero(&cstotal, sizeof cstotal);	for (cyl = 0; cyl < fs->fs_ncg; cyl++) {		if ((error = bread(devvp, fsbtodb(fs, cgtod(fs, cyl)),		    fs->fs_cgsize, cred, &bp)) != 0) {			brelse(bp);			return (error);		}		cgp = (struct cg *)bp->b_data;		cstotal.cs_nffree += cgp->cg_cs.cs_nffree;		cstotal.cs_nbfree += cgp->cg_cs.cs_nbfree;		cstotal.cs_nifree += cgp->cg_cs.cs_nifree;		cstotal.cs_ndir += cgp->cg_cs.cs_ndir;		fs->fs_cs(fs, cyl) = cgp->cg_cs;		brelse(bp);	}#ifdef DEBUG	if (bcmp(&cstotal, &fs->fs_cstotal, sizeof cstotal))		printf("ffs_mountfs: superblock updated for soft updates\n");#endif	bcopy(&cstotal, &fs->fs_cstotal, sizeof cstotal);	return (0);}/* * Protecting the freemaps (or bitmaps). *  * To eliminate the need to execute fsck before mounting a file system * after a power failure, one must (conservatively) guarantee that the * on-disk copy of the bitmaps never indicate that a live inode or block is * free.  So, when a block or inode is allocated, the bitmap should be * updated (on disk) before any new pointers.  When a block or inode is * freed, the bitmap should not be updated until all pointers have been * reset.  The latter dependency is handled by the delayed de-allocation * approach described below for block and inode de-allocation.  The former * dependency is handled by calling the following procedure when a block or * inode is allocated. When an inode is allocated an "inodedep" is created * with its DEPCOMPLETE flag cleared until its bitmap is written to disk. * Each "inodedep" is also inserted into the hash indexing structure so * that any additional link additions can be made dependent on the inode * allocation. *  * The ufs file system maintains a number of free block counts (e.g., per * cylinder group, per cylinder and per <cylinder, rotational position> pair) * in addition to the bitmaps.  These counts are used to improve efficiency * during allocation and therefore must be consistent with the bitmaps. * There is no convenient way to guarantee post-crash consistency of these * counts with simple update ordering, for two main reasons: (1) The counts * and bitmaps for a single cylinder group block are not in the same disk * sector.  If a disk write is interrupted (e.g., by power failure), one may * be written and the other not.  (2) Some of the counts are located in the * superblock rather than the cylinder group block. So, we focus our soft * updates implementation on protecting the bitmaps. When mounting a * filesystem, we recompute the auxiliary counts from the bitmaps. *//* * Called just after updating the cylinder group block to allocate an inode. */voidsoftdep_setup_inomapdep(bp, ip, newinum)	struct buf *bp;		/* buffer for cylgroup block with inode map */	struct inode *ip;	/* inode related to allocation */	ino_t newinum;		/* new inode number being allocated */{	struct inodedep *inodedep;	struct bmsafemap *bmsafemap;	/*	 * Create a dependency for the newly allocated inode.	 * Panic if it already exists as something is seriously wrong.	 * Otherwise add it to the dependency list for the buffer holding	 * the cylinder group map from which it was allocated.	 */	ACQUIRE_LOCK(&lk);	if (inodedep_lookup(ip->i_fs, newinum, DEPALLOC | NODELAY, &inodedep)	    != 0) {		FREE_LOCK(&lk);		panic("softdep_setup_inomapdep: found inode");	}	inodedep->id_buf = bp;	inodedep->id_state &= ~DEPCOMPLETE;	bmsafemap = bmsafemap_lookup(bp);	LIST_INSERT_HEAD(&bmsafemap->sm_inodedephd, inodedep, id_deps);	FREE_LOCK(&lk);}/* * Called just after updating the cylinder group block to * allocate block or fragment. */voidsoftdep_setup_blkmapdep(bp, fs, newblkno)	struct buf *bp;		/* buffer for cylgroup block with block map */	struct fs *fs;		/* filesystem doing allocation */	ufs_daddr_t newblkno;	/* number of newly allocated block */{	struct newblk *newblk;	struct bmsafemap *bmsafemap;	/*	 * Create a dependency for the newly allocated block.	 * Add it to the dependency list for the buffer holding	 * the cylinder group map from which it was allocated.	 */	if (newblk_lookup(fs, newblkno, DEPALLOC, &newblk) != 0)		panic("softdep_setup_blkmapdep: found block");	ACQUIRE_LOCK(&lk);	newblk->nb_bmsafemap = bmsafemap = bmsafemap_lookup(bp);	LIST_INSERT_HEAD(&bmsafemap->sm_newblkhd, newblk, nb_deps);	FREE_LOCK(&lk);}/* * Find the bmsafemap associated with a cylinder group buffer. * If none exists, create one. The buffer must be locked when * this routine is called and this routine must be called with * splbio interrupts blocked. */STATIC struct bmsafemap *bmsafemap_lookup(bp)	struct buf *bp;{	struct bmsafemap *bmsafemap;	struct worklist *wk;#ifdef DEBUG	if (lk.lkt_held == -1)		panic("bmsafemap_lookup: lock not held");#endif	LIST_FOREACH(wk, &bp->b_dep, wk_list)		if (wk->wk_type == D_BMSAFEMAP)			return (WK_BMSAFEMAP(wk));	FREE_LOCK(&lk);	MALLOC(bmsafemap, struct bmsafemap *, sizeof(struct bmsafemap),		M_BMSAFEMAP, M_SOFTDEP_FLAGS);	bmsafemap->sm_list.wk_type = D_BMSAFEMAP;	bmsafemap->sm_list.wk_state = 0;	bmsafemap->sm_buf = bp;	LIST_INIT(&bmsafemap->sm_allocdirecthd);	LIST_INIT(&bmsafemap->sm_allocindirhd);	LIST_INIT(&bmsafemap->sm_inodedephd);	LIST_INIT(&bmsafemap->sm_newblkhd);	ACQUIRE_LOCK(&lk);	WORKLIST_INSERT(&bp->b_dep, &bmsafemap->sm_list);	return (bmsafemap);}/* * Direct block allocation dependencies. *  * When a new block is allocated, the corresponding disk locations must be * initialized (with zeros or new data) before the on-disk inode points to * them.  Also, the freemap from which the block was allocated must be * updated (on disk) before the inode's pointer. These two dependencies are * independent of each other and are needed for all file blocks and indirect * blocks that are pointed to directly by the inode.  Just before the * "in-core" version of the inode is updated with a newly allocated block * number, a procedure (below) is called to setup allocation dependency * structures.  These structures are removed when the corresponding * dependencies are satisfied or when the block allocation becomes obsolete * (i.e., the file is deleted, the block is de-allocated, or the block is a * fragment that gets upgraded).  All of these cases are handled in * procedures described later. *  * When a file extension causes a fragment to be upgraded, either to a larger * fragment or to a full block, the on-disk location may change (if the * previous fragment could not simply be extended). In this case, the old * fragment must be de-allocated, but not until after the inode's pointer has * been updated. In most cases, this is handled by later procedures, which * will construct a "freefrag" structure to be added to the workitem queue * when the inode update is complete (or obsolete).  The main exception to * this is when an allocation occurs while a pending allocation dependency * (for the same block pointer) remains.  This case is handled in the main * allocation dependency setup procedure by immediately freeing the * unreferenced fragments. */ void softdep_setup_allocdirect(ip, lbn, newblkno, oldblkno, newsize, oldsize, bp)	struct inode *ip;	/* inode to which block is being added */	ufs_lbn_t lbn;		/* block pointer within inode */	ufs_daddr_t newblkno;	/* disk block number being added */	ufs_daddr_t oldblkno;	/* previous block number, 0 unless frag */	long newsize;		/* size of new block */	long oldsize;		/* size of new block */	struct buf *bp;		/* bp for allocated block */{	struct allocdirect *adp, *oldadp;	struct allocdirectlst *adphead;	struct bmsafemap *bmsafemap;	struct inodedep *inodedep;	struct pagedep *pagedep;	struct newblk *newblk;	MALLOC(adp, struct allocdirect *, sizeof(struct allocdirect),		M_ALLOCDIRECT, M_SOFTDEP_FLAGS);	bzero(adp, sizeof(struct allocdirect));	adp->ad_list.wk_type = D_ALLOCDIRECT;	adp->ad_lbn = lbn;	adp->ad_newblkno = newblkno;	adp->ad_oldblkno = oldblkno;	adp->ad_newsize = newsize;	adp->ad_oldsize = oldsize;	adp->ad_state = ATTACHED;	if (newblkno == oldblkno)		adp->ad_freefrag = NULL;	else		adp->ad_freefrag = newfreefrag(ip, oldblkno, oldsize);	if (newblk_lookup(ip->i_fs, newblkno, 0, &newblk) == 0)		panic("softdep_setup_allocdirect: lost block");	ACQUIRE_LOCK(&lk);	inodedep_lookup(ip->i_fs, ip->i_number, DEPALLOC | NODELAY, &inodedep);	adp->ad_inodedep = inodedep;	if (newblk->nb_state == DEPCOMPLETE) {		adp->ad_state |= DEPCOMPLETE;		adp->ad_buf = NULL;	} else {		bmsafemap = newblk->nb_bmsafemap;		adp->ad_buf = bmsafemap->sm_buf;		LIST_REMOVE(newblk, nb_deps);		LIST_INSERT_HEAD(&bmsafemap->sm_allocdirecthd, adp, ad_deps);	}	LIST_REMOVE(newblk, nb_hash);	FREE(newblk, M_NEWBLK);	/*	 * If we were not passed a bp to attach the dep to,	 * then this must be for a regular file.	 * Allocate a buffer to represent the page cache pages	 * that are the real dependency.  The pages themselves	 * cannot refer to the dependency since we don't want to	 * add a field to struct vm_page for this.	 */	if (bp == NULL) {		bp = softdep_setup_pagecache(ip, lbn, newsize);	}	WORKLIST_INSERT(&bp->b_dep, &adp->ad_list);	if (lbn >= NDADDR) {		/* allocating an indirect block */		if (oldblkno != 0) {			FREE_LOCK(&lk);			panic("softdep_setup_allocdirect: non-zero indir");		}	} else {		/*		 * Allocating a direct block.		 *		 * If we are allocating a directory block, then we must		 * allocate an associated pagedep to track additions and		 * deletions.		 */		if ((ip->i_ffs_mode & IFMT) == IFDIR &&		    pagedep_lookup(ip, lbn, DEPALLOC, &pagedep) == 0)			WORKLIST_INSERT(&bp->b_dep, &pagedep->pd_list);	}	/*	 * The list of allocdirects must be kept in sorted and ascending	 * order so that the rollback routines can quickly determine the	 * first uncommitted block (the size of the file stored on disk	 * ends at the end of the lowest committed fragment, or if there	 * are no fragments, at the end of the highest committed block).	 * Since files generally grow, the typical case is that the new	 * block is to be added at the end of the list. We speed this	 * special case by checking against the last allocdirect in the	 * list before laboriously traversing the list looking for the	 * insertion point.	 */	adphead = &inodedep->id_newinoupdt;	oldadp = TAILQ_LAST(adphead, allocdirectlst);	if (oldadp == NULL || oldadp->ad_lbn <= lbn) {		/* insert at end of list */		TAILQ_INSERT_TAIL(adphead, adp, ad_next);		if (oldadp != NULL && oldadp->ad_lbn == lbn)			allocdirect_merge(adphead, adp, oldadp);		FREE_LOCK(&lk);		return;	}	TAILQ_FOREACH(oldadp, adphead, ad_next) {		if (oldadp->ad_lbn >= lbn)			break;	}	if (oldadp == NULL) {		FREE_LOCK(&lk);		panic("softdep_setup_allocdirect: lost entry");	}	/* insert in middle of list */	TAILQ_INSERT_BEFORE(oldadp, adp, ad_next);	if (oldadp->ad_lbn == lbn)		allocdirect_merge(adphead, adp, oldadp);	FREE_LOCK(&lk);}/* * Replace an old allocdirect dependency with a newer one. * This routine must be called with splbio interrupts blocked. */STATIC voidallocdirect_merge(adphead, newadp, oldadp)	struct allocdirectlst *adphead;	/* head of list holding allocdirects */	struct allocdirect *newadp;	/* allocdirect being added */	struct allocdirect *oldadp;	/* existing allocdirect being checked */{	struct freefrag *freefrag;#ifdef DEBUG	if (lk.lkt_held == -1)		panic("allocdirect_merge: lock not held");#endif	if (newadp->ad_oldblkno != oldadp->ad_newblkno ||	    newadp->ad_oldsize != oldadp->ad_newsize ||	    newadp->ad_lbn >= NDADDR) {		FREE_LOCK(&lk);		panic("allocdirect_check: old %d != new %d || lbn %ld >= %d",		    newadp->ad_oldblkno, oldadp->ad_newblkno, newadp->ad_lbn,		    NDADDR);	}	newadp->ad_oldblkno = oldadp->ad_oldblkno;	newadp->ad_oldsize = oldadp->ad_oldsize;	/*	 * If the old dependency had a fragment to free or had never	 * previously had a block allocated, then the new dependency	 * can immediately post its freefrag and adopt the old freefrag.	 * This action is done by swapping the freefrag dependencies.	 * The new dependency gains the old one's freefrag, and the	 * old one gets the new one and then immediately puts it on	 * the worklist when it is freed by free_allocdirect. It is	 * not possible to do this swap when the old dependency had a	 * non-zero size but no previous fragment to free. This condition	 * arises when the new block is an extension of the old block.	 * Here, the first part of the fragment allocated to the new	 * dependency is part of the block currently claimed on disk by	 * the old dependency, so cannot legitimately be freed until the	 * conditions for the new dependency are fulfilled.	 */	if (oldadp->ad_freefrag != NULL || oldadp->ad_oldblkno == 0) {		freefrag = newadp->ad_freefrag;		newadp->ad_freefrag = oldadp->ad_freefrag;		oldadp->ad_freefrag = freefrag;	}	free_allocdirect(adphead, oldadp, 0);}		/* * Allocate a new freefrag structure if needed. */STATIC struct freefrag *newfreefrag(ip, blkno, size)	struct inode *ip;	ufs_daddr_t blkno;	long size;{	struct freefrag *freefrag;	struct fs *fs;	if (blkno == 0)		return (NULL);	fs = ip->i_fs;	if (fragnum(fs, blkno) + numfrags(fs, size) > fs->fs_frag)		panic("newfreefrag: frag size");	MALLOC(freefrag, struct freefrag *, sizeof(struct freefrag),		M_FREEFRAG, M_SOFTDEP_FLAGS);	freefrag->ff_list.wk_type = D_FREEFRAG;	freefrag->ff_state = ip->i_ffs_uid & ~ONWORKLIST; /* XXX - used below */	freefrag->ff_inum = ip->i_number;	freefrag->ff_mnt = ITOV(ip)->v_mount;	freefrag->ff_devvp = ip->i_devvp;	freefrag->ff_blkno = blkno;	freefrag->ff_fragsize = size;	return (freefrag);}/* * This workitem de-allocates fragments that were replaced during * file block allocation. */STATIC void handle_workitem_freefrag(freefrag)	struct freefrag *freefrag;{	struct inode tip;	tip.i_vnode = NULL;	tip.i_fs = VFSTOUFS(freefrag->ff_mnt)->um_fs;	tip.i_devvp = freefrag->ff_devvp;	tip.i_dev = freefrag->ff_devvp->v_rdev;	tip.i_number = freefrag->ff_inum;	tip.i_ffs_uid = freefrag->ff_state & ~ONWORKLIST; /* XXX - set above */	ffs_blkfree(&tip, freefrag->ff_blkno, freefrag->ff_fragsize);	FREE(freefrag, M_FREEFRAG);}/* * Indirect block allocation dependencies. *  * The same dependencies that exist for a direct block also exist when * a new block is allocated and pointed to by an entry in a block of * indirect pointers. The undo/redo states described above are also * used here. Because an indirect block contains many pointers that * may have dependencies, a second copy of the entire in-memory indirect * block is kept. The buffer cache copy is always completely up-to-date. * The second copy, which is used only as a source for disk writes, * contains only the safe pointers (i.e., those that have no remaining * update dependencies). The second copy is freed when all pointers * are safe. The cache is not allowed to replace indirect blocks with * pending update dependencies. If a buffer containing an indirect * block with dependencies is written, these routines will mark it * dirty again. It can only be successfully written once all the * dependencies are removed. The ffs_fsync routine in conjunction with * softdep_sync_metadata work together to get all the dependencies * removed so that a file can be successfully written to disk. Three * procedures are used when setting up indirect block pointer * dependencies. The division is necessary because of the organization * of the "balloc" routine and because of the distinction between file * pages and file metadata blocks. *//* * Allocate a new allocindir structure. */STATIC struct allocindir *newallocindir(ip, ptrno, newblkno, oldblkno)	struct inode *ip;	/* inode for file being extended */	int ptrno;		/* offset of pointer in indirect block */	ufs_daddr_t newblkno;	/* disk block number being added */	ufs_daddr_t oldblkno;	/* previous block number, 0 if none */{	struct allocindir *aip;	MALLOC(aip, struct allocindir *, sizeof(struct allocindir),		M_ALLOCINDIR, M_SOFTDEP_FLAGS);	bzero(aip,sizeof(struct allocindir));	aip->ai_list.wk_type = D_ALLOCINDIR;	aip->ai_state = ATTACHED;	aip->ai_offset = ptrno;	aip->ai_newblkno = newblkno;	aip->ai_oldblkno = oldblkno;	aip->ai_freefrag = newfreefrag(ip, oldblkno, ip->i_fs->fs_bsize);	return (aip);}/* * Called just before setting an indirect block pointer * to a newly allocated file page. */voidsoftdep_setup_allocindir_page(ip, lbn, bp, ptrno, newblkno, oldblkno, nbp)	struct inode *ip;	/* inode for file being extended */	ufs_lbn_t lbn;		/* allocated block number within file */	struct buf *bp;		/* buffer with indirect blk referencing page */	int ptrno;		/* offset of pointer in indirect block */	ufs_daddr_t newblkno;	/* disk block number being added */	ufs_daddr_t oldblkno;	/* previous block number, 0 if none */	struct buf *nbp;	/* buffer holding allocated page */{	struct allocindir *aip;	struct pagedep *pagedep;	aip = newallocindir(ip, ptrno, newblkno, oldblkno);	ACQUIRE_LOCK(&lk);	/*	 * If we are allocating a directory page, then we must	 * allocate an associated pagedep to track additions and	 * deletions.	 */	if ((ip->i_ffs_mode & IFMT) == IFDIR &&	    pagedep_lookup(ip, lbn, DEPALLOC, &pagedep) == 0)		WORKLIST_INSERT(&nbp->b_dep, &pagedep->pd_list);	if (nbp == NULL) {		nbp = softdep_setup_pagecache(ip, lbn, ip->i_fs->fs_bsize);	}	WORKLIST_INSERT(&nbp->b_dep, &aip->ai_list);	FREE_LOCK(&lk);	setup_allocindir_phase2(bp, ip, aip);}/* * Called just before setting an indirect block pointer to a * newly allocated indirect block. */voidsoftdep_setup_allocindir_meta(nbp, ip, bp, ptrno, newblkno)	struct buf *nbp;	/* newly allocated indirect block */	struct inode *ip;	/* inode for file being extended */	struct buf *bp;		/* indirect block referencing allocated block */	int ptrno;		/* offset of pointer in indirect block */	ufs_daddr_t newblkno;	/* disk block number being added */{	struct allocindir *aip;	aip = newallocindir(ip, ptrno, newblkno, 0);	ACQUIRE_LOCK(&lk);	WORKLIST_INSERT(&nbp->b_dep, &aip->ai_list);	FREE_LOCK(&lk);	setup_allocindir_phase2(bp, ip, aip);}/* * Called to finish the allocation of the "aip" allocated * by one of the two routines above. */STATIC void setup_allocindir_phase2(bp, ip, aip)	struct buf *bp;		/* in-memory copy of the indirect block */	struct inode *ip;	/* inode for file being extended */	struct allocindir *aip;	/* allocindir allocated by the above routines */{	struct worklist *wk;	struct indirdep *indirdep, *newindirdep;	struct bmsafemap *bmsafemap;	struct allocindir *oldaip;	struct freefrag *freefrag;	struct newblk *newblk;	if (bp->b_lblkno >= 0)		panic("setup_allocindir_phase2: not indir blk");	for (indirdep = NULL, newindirdep = NULL; ; ) {		ACQUIRE_LOCK(&lk);		LIST_FOREACH(wk, &bp->b_dep, wk_list) {			if (wk->wk_type != D_INDIRDEP)				continue;			indirdep = WK_INDIRDEP(wk);			break;		}		if (indirdep == NULL && newindirdep) {			indirdep = newindirdep;			WORKLIST_INSERT(&bp->b_dep, &indirdep->ir_list);			newindirdep = NULL;		}		FREE_LOCK(&lk);		if (indirdep) {			if (newblk_lookup(ip->i_fs, aip->ai_newblkno, 0,			    &newblk) == 0)				panic("setup_allocindir: lost block");			ACQUIRE_LOCK(&lk);			if (newblk->nb_state == DEPCOMPLETE) {				aip->ai_state |= DEPCOMPLETE;				aip->ai_buf = NULL;			} else {				bmsafemap = newblk->nb_bmsafemap;				aip->ai_buf = bmsafemap->sm_buf;				LIST_REMOVE(newblk, nb_deps);				LIST_INSERT_HEAD(&bmsafemap->sm_allocindirhd,				    aip, ai_deps);			}			LIST_REMOVE(newblk, nb_hash);			FREE(newblk, M_NEWBLK);			aip->ai_indirdep = indirdep;			/*			 * Check to see if there is an existing dependency			 * for this block. If there is, merge the old			 * dependency into the new one.			 */			if (aip->ai_oldblkno == 0)				oldaip = NULL;			else				LIST_FOREACH(oldaip, &indirdep->ir_deplisthd, ai_next)					if (oldaip->ai_offset == aip->ai_offset)						break;			freefrag = NULL;			if (oldaip != NULL) {				if (oldaip->ai_newblkno != aip->ai_oldblkno) {					FREE_LOCK(&lk);					panic("setup_allocindir_phase2: blkno");				}				aip->ai_oldblkno = oldaip->ai_oldblkno;				freefrag = aip->ai_freefrag;				aip->ai_freefrag = oldaip->ai_freefrag;				oldaip->ai_freefrag = NULL;				free_allocindir(oldaip, NULL);			}			LIST_INSERT_HEAD(&indirdep->ir_deplisthd, aip, ai_next);			((ufs_daddr_t *)indirdep->ir_savebp->b_data)			    [aip->ai_offset] = aip->ai_oldblkno;			FREE_LOCK(&lk);			if (freefrag != NULL)				handle_workitem_freefrag(freefrag);		}		if (newindirdep) {			if (indirdep->ir_savebp != NULL)				brelse(newindirdep->ir_savebp);			WORKITEM_FREE((caddr_t)newindirdep, D_INDIRDEP);		}		if (indirdep)			break;		MALLOC(newindirdep, struct indirdep *, sizeof(struct indirdep),			M_INDIRDEP, M_SOFTDEP_FLAGS);		newindirdep->ir_list.wk_type = D_INDIRDEP;		newindirdep->ir_state = ATTACHED;		LIST_INIT(&newindirdep->ir_deplisthd);		LIST_INIT(&newindirdep->ir_donehd);		if (bp->b_blkno == bp->b_lblkno) {			VOP_BMAP(bp->b_vp, bp->b_lblkno, NULL, &bp->b_blkno,				NULL);		}		newindirdep->ir_savebp =		    getblk(ip->i_devvp, bp->b_blkno, bp->b_bcount, 0, 0);#if 0		BUF_KERNPROC(newindirdep->ir_savebp);#endif		bcopy(bp->b_data, newindirdep->ir_savebp->b_data, bp->b_bcount);	}}/* * Block de-allocation dependencies. *  * When blocks are de-allocated, the on-disk pointers must be nullified before * the blocks are made available for use by other files.  (The true * requirement is that old pointers must be nullified before new on-disk * pointers are set.  We chose this slightly more stringent requirement to * reduce complexity.) Our implementation handles this dependency by updating * the inode (or indirect block) appropriately but delaying the actual block * de-allocation (i.e., freemap and free space count manipulation) until * after the updated versions reach stable storage.  After the disk is * updated, the blocks can be safely de-allocated whenever it is convenient. * This implementation handles only the common case of reducing a file's * length to zero. Other cases are handled by the conventional synchronous * write approach. * * The ffs implementation with which we worked double-checks * the state of the block pointers and file size as it reduces * a file's length.  Some of this code is replicated here in our * soft updates implementation.  The freeblks->fb_chkcnt field is * used to transfer a part of this information to the procedure * that eventually de-allocates the blocks. * * This routine should be called from the routine that shortens * a file's length, before the inode's size or block pointers * are modified. It will save the block pointer information for * later release and zero the inode so that the calling routine * can release it. */voidsoftdep_setup_freeblocks(ip, length)	struct inode *ip;	/* The inode whose length is to be reduced */	off_t length;		/* The new length for the file */{	struct freeblks *freeblks;	struct inodedep *inodedep;	struct allocdirect *adp;	struct vnode *vp;	struct buf *bp;	struct fs *fs;	int i, delay, error;	fs = ip->i_fs;	vp = ITOV(ip);	if (length != 0)		panic("softdep_setup_freeblocks: non-zero length");	MALLOC(freeblks, struct freeblks *, sizeof(struct freeblks),	    M_FREEBLKS, M_SOFTDEP_FLAGS);	bzero(freeblks, sizeof(struct freeblks));	freeblks->fb_list.wk_type = D_FREEBLKS;	freeblks->fb_uid = ip->i_ffs_uid;	freeblks->fb_previousinum = ip->i_number;	freeblks->fb_devvp = ip->i_devvp;	freeblks->fb_mnt = ITOV(ip)->v_mount;	freeblks->fb_oldsize = ip->i_ffs_size;	freeblks->fb_newsize = length;	freeblks->fb_chkcnt = ip->i_ffs_blocks;	for (i = 0; i < NDADDR; i++) {		freeblks->fb_dblks[i] = ip->i_ffs_db[i];		ip->i_ffs_db[i] = 0;	}	for (i = 0; i < NIADDR; i++) {		freeblks->fb_iblks[i] = ip->i_ffs_ib[i];		ip->i_ffs_ib[i] = 0;	}	ip->i_ffs_blocks = 0;	ip->i_ffs_size = 0;	/*	 * Push the zero'ed inode to to its disk buffer so that we are free	 * to delete its dependencies below. Once the dependencies are gone	 * the buffer can be safely released.	 */	if ((error = bread(ip->i_devvp,	    fsbtodb(fs, ino_to_fsba(fs, ip->i_number)),	    (int)fs->fs_bsize, NOCRED, &bp)) != 0)		softdep_error("softdep_setup_freeblocks", error);	*((struct dinode *)bp->b_data + ino_to_fsbo(fs, ip->i_number)) =	    ip->i_din.ffs_din;	/*	 * Find and eliminate any inode dependencies.	 */	ACQUIRE_LOCK(&lk);	(void) inodedep_lookup(fs, ip->i_number, DEPALLOC, &inodedep);	if ((inodedep->id_state & IOSTARTED) != 0) {		FREE_LOCK(&lk);		panic("softdep_setup_freeblocks: inode busy");	}	/*	 * Add the freeblks structure to the list of operations that	 * must await the zero'ed inode being written to disk. If we	 * still have a bitmap dependency (delay == 0), then the inode	 * has never been written to disk, so we can process the	 * freeblks below once we have deleted the dependencies.	 */	delay = (inodedep->id_state & DEPCOMPLETE);	if (delay)		WORKLIST_INSERT(&inodedep->id_bufwait, &freeblks->fb_list);	/*	 * Because the file length has been truncated to zero, any	 * pending block allocation dependency structures associated	 * with this inode are obsolete and can simply be de-allocated.	 * We must first merge the two dependency lists to get rid of	 * any duplicate freefrag structures, then purge the merged list.	 * We must remove any pagecache markers from the pagecache	 * hashtable first because any I/Os in flight will want to see	 * dependencies attached to their pagecache markers.  We cannot	 * free the pagecache markers until after we've freed all the	 * dependencies that reference them later.	 * If we still have a bitmap dependency, then the inode has never	 * been written to disk, so we can free any fragments without delay.	 */	softdep_collect_pagecache(ip);	merge_inode_lists(inodedep);	while ((adp = TAILQ_FIRST(&inodedep->id_inoupdt)) != 0)		free_allocdirect(&inodedep->id_inoupdt, adp, delay);	FREE_LOCK(&lk);	bdwrite(bp);	/*	 * We must wait for any I/O in progress to finish so that	 * all potential buffers on the dirty list will be visible.	 * Once they are all there, walk the list and get rid of	 * any dependencies.	 */	ACQUIRE_LOCK(&lk);	drain_output(vp, 1);	while (getdirtybuf(&LIST_FIRST(&vp->v_dirtyblkhd), MNT_WAIT)) {		bp = LIST_FIRST(&vp->v_dirtyblkhd);		(void) inodedep_lookup(fs, ip->i_number, 0, &inodedep);		deallocate_dependencies(bp, inodedep);		bp->b_flags |= B_INVAL | B_NOCACHE;		FREE_LOCK(&lk);		brelse(bp);		ACQUIRE_LOCK(&lk);	}	softdep_free_pagecache(ip);	if (inodedep_lookup(fs, ip->i_number, 0, &inodedep) != 0)		(void) free_inodedep(inodedep);	FREE_LOCK(&lk);	/*	 * If the inode has never been written to disk (delay == 0),	 * then we can process the freeblks now that we have deleted	 * the dependencies.	 */	if (!delay)		handle_workitem_freeblocks(freeblks);}/* * Reclaim any dependency structures from a buffer that is about to * be reallocated to a new vnode. The buffer must be locked, thus, * no I/O completion operations can occur while we are manipulating * its associated dependencies. The mutex is held so that other I/O's * associated with related dependencies do not occur. */STATIC voiddeallocate_dependencies(bp, inodedep)	struct buf *bp;	struct inodedep *inodedep;{	struct worklist *wk;	struct indirdep *indirdep;	struct allocindir *aip;	struct pagedep *pagedep;	struct dirrem *dirrem;	struct diradd *dap;	int i;	while ((wk = LIST_FIRST(&bp->b_dep)) != NULL) {		switch (wk->wk_type) {		case D_INDIRDEP:			indirdep = WK_INDIRDEP(wk);			/*			 * None of the indirect pointers will ever be visible,			 * so they can simply be tossed. GOINGAWAY ensures			 * that allocated pointers will be saved in the buffer			 * cache until they are freed. Note that they will			 * only be able to be found by their physical address			 * since the inode mapping the logical address will			 * be gone. The save buffer used for the safe copy			 * was allocated in setup_allocindir_phase2 using			 * the physical address so it could be used for this			 * purpose. Hence we swap the safe copy with the real			 * copy, allowing the safe copy to be freed and holding			 * on to the real copy for later use in indir_trunc.			 */			if (indirdep->ir_state & GOINGAWAY) {				FREE_LOCK(&lk);				panic("deallocate_dependencies: already gone");			}			indirdep->ir_state |= GOINGAWAY;			while ((aip = LIST_FIRST(&indirdep->ir_deplisthd)) != 0)				free_allocindir(aip, inodedep);			if (bp->b_lblkno >= 0 ||			    bp->b_blkno != indirdep->ir_savebp->b_lblkno) {				FREE_LOCK(&lk);				panic("deallocate_dependencies: not indir");			}			bcopy(bp->b_data, indirdep->ir_savebp->b_data,			    bp->b_bcount);			WORKLIST_REMOVE(wk);			WORKLIST_INSERT(&indirdep->ir_savebp->b_dep, wk);			continue;		case D_PAGEDEP:			pagedep = WK_PAGEDEP(wk);			/*			 * None of the directory additions will ever be			 * visible, so they can simply be tossed.			 */			for (i = 0; i < DAHASHSZ; i++)				while ((dap =				    LIST_FIRST(&pagedep->pd_diraddhd[i])))					free_diradd(dap);			while ((dap = LIST_FIRST(&pagedep->pd_pendinghd)) != 0)				free_diradd(dap);			/*			 * Copy any directory remove dependencies to the list			 * to be processed after the zero'ed inode is written.			 * If the inode has already been written, then they 			 * can be dumped directly onto the work list.			 */			LIST_FOREACH(dirrem, &pagedep->pd_dirremhd, dm_next) {				LIST_REMOVE(dirrem, dm_next);				dirrem->dm_dirinum = pagedep->pd_ino;				if (inodedep == NULL ||				    (inodedep->id_state & ALLCOMPLETE) ==				     ALLCOMPLETE)					add_to_worklist(&dirrem->dm_list);				else					WORKLIST_INSERT(&inodedep->id_bufwait,					    &dirrem->dm_list);			}			WORKLIST_REMOVE(&pagedep->pd_list);			LIST_REMOVE(pagedep, pd_hash);			WORKITEM_FREE(pagedep, D_PAGEDEP);			continue;		case D_ALLOCINDIR:			free_allocindir(WK_ALLOCINDIR(wk), inodedep);			continue;		case D_ALLOCDIRECT:		case D_INODEDEP:			FREE_LOCK(&lk);			panic("deallocate_dependencies: Unexpected type %s",			    TYPENAME(wk->wk_type));			/* NOTREACHED */		default:			FREE_LOCK(&lk);			panic("deallocate_dependencies: Unknown type %s",			    TYPENAME(wk->wk_type));			/* NOTREACHED */		}	}}/* * Free an allocdirect. Generate a new freefrag work request if appropriate. * This routine must be called with splbio interrupts blocked. */STATIC voidfree_allocdirect(adphead, adp, delay)	struct allocdirectlst *adphead;	struct allocdirect *adp;	int delay;{#ifdef DEBUG	if (lk.lkt_held == -1)		panic("free_allocdirect: lock not held");#endif	if ((adp->ad_state & DEPCOMPLETE) == 0)		LIST_REMOVE(adp, ad_deps);	TAILQ_REMOVE(adphead, adp, ad_next);	if ((adp->ad_state & COMPLETE) == 0)		WORKLIST_REMOVE(&adp->ad_list);	if (adp->ad_freefrag != NULL) {		if (delay)			WORKLIST_INSERT(&adp->ad_inodedep->id_bufwait,			    &adp->ad_freefrag->ff_list);		else			add_to_worklist(&adp->ad_freefrag->ff_list);	}	WORKITEM_FREE(adp, D_ALLOCDIRECT);}/* * Prepare an inode to be freed. The actual free operation is not * done until the zero'ed inode has been written to disk. */voidsoftdep_freefile(pvp, ino, mode)		struct vnode *pvp;		ino_t ino;		int mode;{	struct inode *ip = VTOI(pvp);	struct inodedep *inodedep;	struct freefile *freefile;	/*	 * This sets up the inode de-allocation dependency.	 */	MALLOC(freefile, struct freefile *, sizeof(struct freefile),		M_FREEFILE, M_SOFTDEP_FLAGS);	freefile->fx_list.wk_type = D_FREEFILE;	freefile->fx_list.wk_state = 0;	freefile->fx_mode = mode;	freefile->fx_oldinum = ino;	freefile->fx_devvp = ip->i_devvp;	freefile->fx_mnt = ITOV(ip)->v_mount;	/*	 * If the inodedep does not exist, then the zero'ed inode has	 * been written to disk. If the allocated inode has never been	 * written to disk, then the on-disk inode is zero'ed. In either	 * case we can free the file immediately.	 */	ACQUIRE_LOCK(&lk);	if (inodedep_lookup(ip->i_fs, ino, 0, &inodedep) == 0 ||	    check_inode_unwritten(inodedep)) {		FREE_LOCK(&lk);		handle_workitem_freefile(freefile);		return;	}	WORKLIST_INSERT(&inodedep->id_inowait, &freefile->fx_list);	FREE_LOCK(&lk);}/* * Check to see if an inode has never been written to disk. If * so free the inodedep and return success, otherwise return failure. * This routine must be called with splbio interrupts blocked. * * If we still have a bitmap dependency, then the inode has never * been written to disk. Drop the dependency as it is no longer * necessary since the inode is being deallocated. We set the * ALLCOMPLETE flags since the bitmap now properly shows that the * inode is not allocated. Even if the inode is actively being * written, it has been rolled back to its zero'ed state, so we * are ensured that a zero inode is what is on the disk. For short * lived files, this change will usually result in removing all the * dependencies from the inode so that it can be freed immediately. */STATIC intcheck_inode_unwritten(inodedep)	struct inodedep *inodedep;{	if ((inodedep->id_state & DEPCOMPLETE) != 0 ||	    LIST_FIRST(&inodedep->id_pendinghd) != NULL ||	    LIST_FIRST(&inodedep->id_bufwait) != NULL ||	    LIST_FIRST(&inodedep->id_inowait) != NULL ||	    TAILQ_FIRST(&inodedep->id_inoupdt) != NULL ||	    TAILQ_FIRST(&inodedep->id_newinoupdt) != NULL ||	    inodedep->id_nlinkdelta != 0)		return (0);	inodedep->id_state |= ALLCOMPLETE;	LIST_REMOVE(inodedep, id_deps);	inodedep->id_buf = NULL;	if (inodedep->id_state & ONWORKLIST)		WORKLIST_REMOVE(&inodedep->id_list);	if (inodedep->id_savedino != NULL) {		FREE(inodedep->id_savedino, M_INODEDEP);		inodedep->id_savedino = NULL;	}	if (free_inodedep(inodedep) == 0) {		FREE_LOCK(&lk);		panic("check_inode_unwritten: busy inode");	}	return (1);}/* * Try to free an inodedep structure. Return 1 if it could be freed. */STATIC intfree_inodedep(inodedep)	struct inodedep *inodedep;{	if ((inodedep->id_state & ONWORKLIST) != 0 ||	    (inodedep->id_state & ALLCOMPLETE) != ALLCOMPLETE ||	    LIST_FIRST(&inodedep->id_pendinghd) != NULL ||	    LIST_FIRST(&inodedep->id_bufwait) != NULL ||	    LIST_FIRST(&inodedep->id_inowait) != NULL ||	    TAILQ_FIRST(&inodedep->id_inoupdt) != NULL ||	    TAILQ_FIRST(&inodedep->id_newinoupdt) != NULL ||	    inodedep->id_nlinkdelta != 0 || inodedep->id_savedino != NULL)		return (0);	LIST_REMOVE(inodedep, id_hash);	WORKITEM_FREE(inodedep, D_INODEDEP);	num_inodedep -= 1;	return (1);}/* * This workitem routine performs the block de-allocation. * The workitem is added to the pending list after the updated * inode block has been written to disk.  As mentioned above, * checks regarding the number of blocks de-allocated (compared * to the number of blocks allocated for the file) are also * performed in this function. */STATIC voidhandle_workitem_freeblocks(freeblks)	struct freeblks *freeblks;{	struct inode tip;	ufs_daddr_t bn;	struct fs *fs;	int i, level, bsize;	long nblocks, blocksreleased = 0;	int error, allerror = 0;	ufs_lbn_t baselbns[NIADDR], tmpval;	tip.i_fs = fs = VFSTOUFS(freeblks->fb_mnt)->um_fs;	tip.i_number = freeblks->fb_previousinum;	tip.i_devvp = freeblks->fb_devvp;	tip.i_dev = freeblks->fb_devvp->v_rdev;	tip.i_ffs_size = freeblks->fb_oldsize;	tip.i_ffs_uid = freeblks->fb_uid;	tip.i_vnode = NULL;	tmpval = 1;	baselbns[0] = NDADDR;	for (i = 1; i < NIADDR; i++) {		tmpval *= NINDIR(fs);		baselbns[i] = baselbns[i - 1] + tmpval;	}	nblocks = btodb(fs->fs_bsize);	blocksreleased = 0;	/*	 * Indirect blocks first.	 */	for (level = (NIADDR - 1); level >= 0; level--) {		if ((bn = freeblks->fb_iblks[level]) == 0)			continue;		if ((error = indir_trunc(&tip, fsbtodb(fs, bn), level,		    baselbns[level], &blocksreleased)) == 0)			allerror = error;		ffs_blkfree(&tip, bn, fs->fs_bsize);		blocksreleased += nblocks;	}	/*	 * All direct blocks or frags.	 */	for (i = (NDADDR - 1); i >= 0; i--) {		if ((bn = freeblks->fb_dblks[i]) == 0)			continue;		bsize = blksize(fs, &tip, i);		ffs_blkfree(&tip, bn, bsize);		blocksreleased += btodb(bsize);	}#ifdef DIAGNOSTIC	if (freeblks->fb_chkcnt != blocksreleased)		printf("handle_workitem_freeblocks: block count");	if (allerror)		softdep_error("handle_workitem_freeblks", allerror);#endif /* DIAGNOSTIC */	WORKITEM_FREE(freeblks, D_FREEBLKS);}/* * Release blocks associated with the inode ip and stored in the indirect * block dbn. If level is greater than SINGLE, the block is an indirect block * and recursive calls to indirtrunc must be used to cleanse other indirect * blocks. */STATIC intindir_trunc(ip, dbn, level, lbn, countp)	struct inode *ip;	ufs_daddr_t dbn;	int level;	ufs_lbn_t lbn;	long *countp;{	struct buf *bp;	ufs_daddr_t *bap;	ufs_daddr_t nb;	struct fs *fs;	struct worklist *wk;	struct indirdep *indirdep;	int i, lbnadd, nblocks;	int error, allerror = 0;	fs = ip->i_fs;	lbnadd = 1;	for (i = level; i > 0; i--)		lbnadd *= NINDIR(fs);	/*	 * Get buffer of block pointers to be freed. This routine is not	 * called until the zero'ed inode has been written, so it is safe	 * to free blocks as they are encountered. Because the inode has	 * been zero'ed, calls to bmap on these blocks will fail. So, we	 * have to use the on-disk address and the block device for the	 * filesystem to look them up. If the file was deleted before its	 * indirect blocks were all written to disk, the routine that set	 * us up (deallocate_dependencies) will have arranged to leave	 * a complete copy of the indirect block in memory for our use.	 * Otherwise we have to read the blocks in from the disk.	 */	ACQUIRE_LOCK(&lk);	if ((bp = incore(ip->i_devvp, dbn)) != NULL &&	    (wk = LIST_FIRST(&bp->b_dep)) != NULL) {		if (wk->wk_type != D_INDIRDEP ||		    (indirdep = WK_INDIRDEP(wk))->ir_savebp != bp ||		    (indirdep->ir_state & GOINGAWAY) == 0) {			FREE_LOCK(&lk);			panic("indir_trunc: lost indirdep");		}		WORKLIST_REMOVE(wk);		WORKITEM_FREE(indirdep, D_INDIRDEP);		if (LIST_FIRST(&bp->b_dep) != NULL) {			FREE_LOCK(&lk);			panic("indir_trunc: dangling dep");		}		FREE_LOCK(&lk);	} else {		FREE_LOCK(&lk);		error = bread(ip->i_devvp, dbn, (int)fs->fs_bsize, NOCRED, &bp);		if (error)			return (error);	}	/*	 * Recursively free indirect blocks.	 */	bap = (ufs_daddr_t *)bp->b_data;	nblocks = btodb(fs->fs_bsize);	for (i = NINDIR(fs) - 1; i >= 0; i--) {		if ((nb = bap[i]) == 0)			continue;		if (level != 0) {			if ((error = indir_trunc(ip, fsbtodb(fs, nb),			     level - 1, lbn + (i * lbnadd), countp)) != 0)				allerror = error;		}		ffs_blkfree(ip, nb, fs->fs_bsize);		*countp += nblocks;	}	bp->b_flags |= B_INVAL | B_NOCACHE;	brelse(bp);	return (allerror);}/* * Free an allocindir. * This routine must be called with splbio interrupts blocked. */STATIC voidfree_allocindir(aip, inodedep)	struct allocindir *aip;	struct inodedep *inodedep;{	struct freefrag *freefrag;#ifdef DEBUG	if (lk.lkt_held == -1)		panic("free_allocindir: lock not held");#endif	if ((aip->ai_state & DEPCOMPLETE) == 0)		LIST_REMOVE(aip, ai_deps);	if (aip->ai_state & ONWORKLIST)		WORKLIST_REMOVE(&aip->ai_list);	LIST_REMOVE(aip, ai_next);	if ((freefrag = aip->ai_freefrag) != NULL) {		if (inodedep == NULL)			add_to_worklist(&freefrag->ff_list);		else			WORKLIST_INSERT(&inodedep->id_bufwait,			    &freefrag->ff_list);	}	WORKITEM_FREE(aip, D_ALLOCINDIR);}/* * Directory entry addition dependencies. *  * When adding a new directory entry, the inode (with its incremented link * count) must be written to disk before the directory entry's pointer to it. * Also, if the inode is newly allocated, the corresponding freemap must be * updated (on disk) before the directory entry's pointer. These requirements * are met via undo/redo on the directory entry's pointer, which consists * simply of the inode number. *  * As directory entries are added and deleted, the free space within a * directory block can become fragmented.  The ufs file system will compact * a fragmented directory block to make space for a new entry. When this * occurs, the offsets of previously added entries change. Any "diradd" * dependency structures corresponding to these entries must be updated with * the new offsets. *//* * This routine is called after the in-memory inode's link * count has been incremented, but before the directory entry's * pointer to the inode has been set. */void softdep_setup_directory_add(bp, dp, diroffset, newinum, newdirbp)	struct buf *bp;		/* buffer containing directory block */	struct inode *dp;	/* inode for directory */	off_t diroffset;	/* offset of new entry in directory */	long newinum;		/* inode referenced by new directory entry */	struct buf *newdirbp;	/* non-NULL => contents of new mkdir */{	int offset;		/* offset of new entry within directory block */	ufs_lbn_t lbn;		/* block in directory containing new entry */	struct fs *fs;	struct diradd *dap;	struct pagedep *pagedep;	struct inodedep *inodedep;	struct mkdir *mkdir1, *mkdir2;	/*	 * Whiteouts have no dependencies.	 */	if (newinum == WINO) {		if (newdirbp != NULL)			bdwrite(newdirbp);		return;	}	fs = dp->i_fs;	lbn = lblkno(fs, diroffset);	offset = blkoff(fs, diroffset);	MALLOC(dap, struct diradd *, sizeof(struct diradd), M_DIRADD,		M_SOFTDEP_FLAGS);	bzero(dap,sizeof(struct diradd));	dap->da_list.wk_type = D_DIRADD;	dap->da_offset = offset;	dap->da_newinum = newinum;	dap->da_state = ATTACHED;	if (newdirbp == NULL) {		dap->da_state |= DEPCOMPLETE;		ACQUIRE_LOCK(&lk);	} else {		dap->da_state |= MKDIR_BODY | MKDIR_PARENT;		MALLOC(mkdir1, struct mkdir *, sizeof(struct mkdir), M_MKDIR,		    M_SOFTDEP_FLAGS);		mkdir1->md_list.wk_type = D_MKDIR;		mkdir1->md_state = MKDIR_BODY;		mkdir1->md_diradd = dap;		MALLOC(mkdir2, struct mkdir *, sizeof(struct mkdir), M_MKDIR,		    M_SOFTDEP_FLAGS);		mkdir2->md_list.wk_type = D_MKDIR;		mkdir2->md_state = MKDIR_PARENT;		mkdir2->md_diradd = dap;		/*		 * Dependency on "." and ".." being written to disk.		 */		mkdir1->md_buf = newdirbp;		ACQUIRE_LOCK(&lk);		LIST_INSERT_HEAD(&mkdirlisthd, mkdir1, md_mkdirs);		WORKLIST_INSERT(&newdirbp->b_dep, &mkdir1->md_list);		FREE_LOCK(&lk);		bdwrite(newdirbp);		/*		 * Dependency on link count increase for parent directory		 */		ACQUIRE_LOCK(&lk);		if (inodedep_lookup(dp->i_fs, dp->i_number, 0, &inodedep) == 0		    || (inodedep->id_state & ALLCOMPLETE) == ALLCOMPLETE) {			dap->da_state &= ~MKDIR_PARENT;			WORKITEM_FREE(mkdir2, D_MKDIR);		} else {			LIST_INSERT_HEAD(&mkdirlisthd, mkdir2, md_mkdirs);			WORKLIST_INSERT(&inodedep->id_bufwait,&mkdir2->md_list);		}	}	/*	 * Link into parent directory pagedep to await its being written.	 */	if (pagedep_lookup(dp, lbn, DEPALLOC, &pagedep) == 0)		WORKLIST_INSERT(&bp->b_dep, &pagedep->pd_list);	dap->da_pagedep = pagedep;	LIST_INSERT_HEAD(&pagedep->pd_diraddhd[DIRADDHASH(offset)], dap,	    da_pdlist);	/*	 * Link into its inodedep. Put it on the id_bufwait list if the inode	 * is not yet written. If it is written, do the post-inode write	 * processing to put it on the id_pendinghd list.	 */	(void) inodedep_lookup(fs, newinum, DEPALLOC, &inodedep);	if ((inodedep->id_state & ALLCOMPLETE) == ALLCOMPLETE)		diradd_inode_written(dap, inodedep);	else		WORKLIST_INSERT(&inodedep->id_bufwait, &dap->da_list);	FREE_LOCK(&lk);}/* * This procedure is called to change the offset of a directory * entry when compacting a directory block which must be owned * exclusively by the caller. Note that the actual entry movement * must be done in this procedure to ensure that no I/O completions * occur while the move is in progress. */void softdep_change_directoryentry_offset(dp, base, oldloc, newloc, entrysize)	struct inode *dp;	/* inode for directory */	caddr_t base;		/* address of dp->i_offset */	caddr_t oldloc;		/* address of old directory location */	caddr_t newloc;		/* address of new directory location */	int entrysize;		/* size of directory entry */{	int offset, oldoffset, newoffset;	struct pagedep *pagedep;	struct diradd *dap;	ufs_lbn_t lbn;	ACQUIRE_LOCK(&lk);	lbn = lblkno(dp->i_fs, dp->i_offset);	offset = blkoff(dp->i_fs, dp->i_offset);	if (pagedep_lookup(dp, lbn, 0, &pagedep) == 0)		goto done;	oldoffset = offset + (oldloc - base);	newoffset = offset + (newloc - base);	LIST_FOREACH(dap, &pagedep->pd_diraddhd[DIRADDHASH(oldoffset)], da_pdlist) {		if (dap->da_offset != oldoffset)			continue;		dap->da_offset = newoffset;		if (DIRADDHASH(newoffset) == DIRADDHASH(oldoffset))			break;		LIST_REMOVE(dap, da_pdlist);		LIST_INSERT_HEAD(&pagedep->pd_diraddhd[DIRADDHASH(newoffset)],		    dap, da_pdlist);		break;	}	if (dap == NULL) {		LIST_FOREACH(dap, &pagedep->pd_pendinghd, da_pdlist) {			if (dap->da_offset == oldoffset) {				dap->da_offset = newoffset;				break;			}		}	}done:	bcopy(oldloc, newloc, entrysize);	FREE_LOCK(&lk);}/* * Free a diradd dependency structure. This routine must be called * with splbio interrupts blocked. */STATIC voidfree_diradd(dap)	struct diradd *dap;{	struct dirrem *dirrem;	struct pagedep *pagedep;	struct inodedep *inodedep;	struct mkdir *mkdir, *nextmd;#ifdef DEBUG	if (lk.lkt_held == -1)		panic("free_diradd: lock not held");#endif	WORKLIST_REMOVE(&dap->da_list);	LIST_REMOVE(dap, da_pdlist);	if ((dap->da_state & DIRCHG) == 0) {		pagedep = dap->da_pagedep;	} else {		dirrem = dap->da_previous;		pagedep = dirrem->dm_pagedep;		dirrem->dm_dirinum = pagedep->pd_ino;		add_to_worklist(&dirrem->dm_list);	}	if (inodedep_lookup(VFSTOUFS(pagedep->pd_mnt)->um_fs, dap->da_newinum,	    0, &inodedep) != 0)		(void) free_inodedep(inodedep);	if ((dap->da_state & (MKDIR_PARENT | MKDIR_BODY)) != 0) {		for (mkdir = LIST_FIRST(&mkdirlisthd); mkdir; mkdir = nextmd) {			nextmd = LIST_NEXT(mkdir, md_mkdirs);			if (mkdir->md_diradd != dap)				continue;			dap->da_state &= ~mkdir->md_state;			WORKLIST_REMOVE(&mkdir->md_list);			LIST_REMOVE(mkdir, md_mkdirs);			WORKITEM_FREE(mkdir, D_MKDIR);		}		if ((dap->da_state & (MKDIR_PARENT | MKDIR_BODY)) != 0) {			FREE_LOCK(&lk);			panic("free_diradd: unfound ref");		}	}	WORKITEM_FREE(dap, D_DIRADD);}/* * Directory entry removal dependencies. *  * When removing a directory entry, the entry's inode pointer must be * zero'ed on disk before the corresponding inode's link count is decremented * (possibly freeing the inode for re-use). This dependency is handled by * updating the directory entry but delaying the inode count reduction until * after the directory block has been written to disk. After this point, the * inode count can be decremented whenever it is convenient. *//* * This routine should be called immediately after removing * a directory entry.  The inode's link count should not be * decremented by the calling procedure -- the soft updates * code will do this task when it is safe. */void softdep_setup_remove(bp, dp, ip, isrmdir)	struct buf *bp;		/* buffer containing directory block */	struct inode *dp;	/* inode for the directory being modified */	struct inode *ip;	/* inode for directory entry being removed */	int isrmdir;		/* indicates if doing RMDIR */{	struct dirrem *dirrem, *prevdirrem;	/*	 * Allocate a new dirrem if appropriate and ACQUIRE_LOCK.	 */	dirrem = newdirrem(bp, dp, ip, isrmdir, &prevdirrem);	/*	 * If the COMPLETE flag is clear, then there were no active	 * entries and we want to roll back to a zeroed entry until	 * the new inode is committed to disk. If the COMPLETE flag is	 * set then we have deleted an entry that never made it to	 * disk. If the entry we deleted resulted from a name change,	 * then the old name still resides on disk. We cannot delete	 * its inode (returned to us in prevdirrem) until the zeroed	 * directory entry gets to disk. The new inode has never been	 * referenced on the disk, so can be deleted immediately.	 */	if ((dirrem->dm_state & COMPLETE) == 0) {		LIST_INSERT_HEAD(&dirrem->dm_pagedep->pd_dirremhd, dirrem,		    dm_next);		FREE_LOCK(&lk);	} else {		if (prevdirrem != NULL)			LIST_INSERT_HEAD(&dirrem->dm_pagedep->pd_dirremhd,			    prevdirrem, dm_next);		dirrem->dm_dirinum = dirrem->dm_pagedep->pd_ino;		FREE_LOCK(&lk);		handle_workitem_remove(dirrem);	}}/* * Allocate a new dirrem if appropriate and return it along with * its associated pagedep. Called without a lock, returns with lock. */STATIC long num_dirrem;		/* number of dirrem allocated */STATIC struct dirrem *newdirrem(bp, dp, ip, isrmdir, prevdirremp)	struct buf *bp;		/* buffer containing directory block */	struct inode *dp;	/* inode for the directory being modified */	struct inode *ip;	/* inode for directory entry being removed */	int isrmdir;		/* indicates if doing RMDIR */	struct dirrem **prevdirremp; /* previously referenced inode, if any */{	int offset;	ufs_lbn_t lbn;	struct diradd *dap;	struct dirrem *dirrem;	struct pagedep *pagedep;	/*	 * Whiteouts have no deletion dependencies.	 */	if (ip == NULL)		panic("newdirrem: whiteout");	/*	 * If we are over our limit, try to improve the situation.	 * Limiting the number of dirrem structures will also limit	 * the number of freefile and freeblks structures.	 */	if (num_dirrem > max_softdeps / 2)		(void) request_cleanup(FLUSH_REMOVE, 0);	num_dirrem += 1;	MALLOC(dirrem, struct dirrem *, sizeof(struct dirrem),		M_DIRREM, M_SOFTDEP_FLAGS);	bzero(dirrem,sizeof(struct dirrem));	dirrem->dm_list.wk_type = D_DIRREM;	dirrem->dm_state = isrmdir ? RMDIR : 0;	dirrem->dm_mnt = ITOV(ip)->v_mount;	dirrem->dm_oldinum = ip->i_number;	*prevdirremp = NULL;	ACQUIRE_LOCK(&lk);	lbn = lblkno(dp->i_fs, dp->i_offset);	offset = blkoff(dp->i_fs, dp->i_offset);	if (pagedep_lookup(dp, lbn, DEPALLOC, &pagedep) == 0)		WORKLIST_INSERT(&bp->b_dep, &pagedep->pd_list);	dirrem->dm_pagedep = pagedep;	/*	 * Check for a diradd dependency for the same directory entry.	 * If present, then both dependencies become obsolete and can	 * be de-allocated. Check for an entry on both the pd_dirraddhd	 * list and the pd_pendinghd list.	 */	LIST_FOREACH(dap, &pagedep->pd_diraddhd[DIRADDHASH(offset)], da_pdlist)		if (dap->da_offset == offset)			break;	if (dap == NULL) {		LIST_FOREACH(dap, &pagedep->pd_pendinghd, da_pdlist)			if (dap->da_offset == offset)				break;		if (dap == NULL)			return (dirrem);	}	/*	 * Must be ATTACHED at this point.	 */	if ((dap->da_state & ATTACHED) == 0) {		FREE_LOCK(&lk);		panic("newdirrem: not ATTACHED");	}	if (dap->da_newinum != ip->i_number) {		FREE_LOCK(&lk);		panic("newdirrem: inum %d should be %d",		    ip->i_number, dap->da_newinum);	}	/*	 * If we are deleting a changed name that never made it to disk,	 * then return the dirrem describing the previous inode (which	 * represents the inode currently referenced from this entry on disk).	 */	if ((dap->da_state & DIRCHG) != 0) {		*prevdirremp = dap->da_previous;		dap->da_state &= ~DIRCHG;		dap->da_pagedep = pagedep;	}	/*	 * We are deleting an entry that never made it to disk.	 * Mark it COMPLETE so we can delete its inode immediately.	 */	dirrem->dm_state |= COMPLETE;	free_diradd(dap);	return (dirrem);}