xref: /csrg-svn/sys/ufs/lfs/lfs_segment.c (revision 56086)
151188Sbostic /*
251188Sbostic  * Copyright (c) 1991 Regents of the University of California.
351188Sbostic  * All rights reserved.
451188Sbostic  *
551188Sbostic  * %sccs.include.redist.c%
651188Sbostic  *
7*56086Sbostic  *	@(#)lfs_segment.c	7.33 (Berkeley) 08/28/92
851188Sbostic  */
951188Sbostic 
1051490Sbostic #include <sys/param.h>
1151490Sbostic #include <sys/systm.h>
1251490Sbostic #include <sys/namei.h>
1352085Sbostic #include <sys/kernel.h>
1451490Sbostic #include <sys/resourcevar.h>
1551490Sbostic #include <sys/file.h>
1651490Sbostic #include <sys/stat.h>
1751490Sbostic #include <sys/buf.h>
1851490Sbostic #include <sys/proc.h>
1951490Sbostic #include <sys/conf.h>
2051490Sbostic #include <sys/vnode.h>
2151490Sbostic #include <sys/malloc.h>
2251490Sbostic #include <sys/mount.h>
2351188Sbostic 
2455033Smckusick #include <miscfs/specfs/specdev.h>
2555033Smckusick #include <miscfs/fifofs/fifo.h>
2655033Smckusick 
2751499Sbostic #include <ufs/ufs/quota.h>
2851499Sbostic #include <ufs/ufs/inode.h>
2951499Sbostic #include <ufs/ufs/dir.h>
3051499Sbostic #include <ufs/ufs/ufsmount.h>
3151490Sbostic 
3251499Sbostic #include <ufs/lfs/lfs.h>
3351499Sbostic #include <ufs/lfs/lfs_extern.h>
3451490Sbostic 
3555940Sbostic #define MAX_ACTIVE	10
3651188Sbostic /*
3751860Sbostic  * Determine if it's OK to start a partial in this segment, or if we need
3851860Sbostic  * to go on to a new segment.
3951301Sbostic  */
4051860Sbostic #define	LFS_PARTIAL_FITS(fs) \
4151860Sbostic 	((fs)->lfs_dbpseg - ((fs)->lfs_offset - (fs)->lfs_curseg) > \
4251860Sbostic 	1 << (fs)->lfs_fsbtodb)
4351188Sbostic 
4453347Sbostic void	 lfs_callback __P((struct buf *));
4552085Sbostic void	 lfs_gather __P((struct lfs *, struct segment *,
4652085Sbostic 	     struct vnode *, int (*) __P((struct lfs *, struct buf *))));
4755940Sbostic int	 lfs_gatherblock __P((struct segment *, struct buf *, int *));
4852085Sbostic void	 lfs_initseg __P((struct lfs *, struct segment *));
4952085Sbostic void	 lfs_iset __P((struct inode *, daddr_t, time_t));
5052085Sbostic int	 lfs_match_data __P((struct lfs *, struct buf *));
5152085Sbostic int	 lfs_match_dindir __P((struct lfs *, struct buf *));
5252085Sbostic int	 lfs_match_indir __P((struct lfs *, struct buf *));
5352085Sbostic int	 lfs_match_tindir __P((struct lfs *, struct buf *));
5452077Sbostic void	 lfs_newseg __P((struct lfs *));
5552085Sbostic void	 lfs_shellsort __P((struct buf **, daddr_t *, register int));
5655940Sbostic void	 lfs_supercallback __P((struct buf *));
5756027Sbostic void	 lfs_updatemeta __P((struct segment *));
5852085Sbostic void	 lfs_writefile __P((struct lfs *, struct segment *, struct vnode *));
5954264Sbostic int	 lfs_writeinode __P((struct lfs *, struct segment *, struct inode *));
6054264Sbostic int	 lfs_writeseg __P((struct lfs *, struct segment *));
6152085Sbostic void	 lfs_writesuper __P((struct lfs *, struct segment *));
6254264Sbostic void	 lfs_writevnodes __P((struct lfs *fs, struct mount *mp,
6354264Sbostic 	    struct segment *sp, int dirops));
6451188Sbostic 
6551860Sbostic int	lfs_allclean_wakeup;		/* Cleaner wakeup address. */
6651860Sbostic 
6752328Sbostic /*
6852328Sbostic  * Ifile and meta data blocks are not marked busy, so segment writes MUST be
6952328Sbostic  * single threaded.  Currently, there are two paths into lfs_segwrite, sync()
7052328Sbostic  * and getnewbuf().  They both mark the file system busy.  Lfs_vflush()
7152328Sbostic  * explicitly marks the file system busy.  So lfs_segwrite is safe.  I think.
7252328Sbostic  */
7352328Sbostic 
7451188Sbostic int
7552328Sbostic lfs_vflush(vp)
7652328Sbostic 	struct vnode *vp;
7752328Sbostic {
7852328Sbostic 	struct inode *ip;
7952328Sbostic 	struct lfs *fs;
8052328Sbostic 	struct segment *sp;
8152328Sbostic 	int error, s;
8252328Sbostic 
8354690Sbostic 	fs = VFSTOUFS(vp->v_mount)->um_lfs;
8454690Sbostic 	lfs_seglock(fs);
8552328Sbostic 
8652328Sbostic 	/*
8752328Sbostic 	 * Allocate a segment structure and enough space to hold pointers to
8852328Sbostic 	 * the maximum possible number of buffers which can be described in a
8952328Sbostic 	 * single summary block.
9052328Sbostic 	 */
9152328Sbostic 	sp = malloc(sizeof(struct segment), M_SEGMENT, M_WAITOK);
9252328Sbostic 	sp->bpp = malloc(((LFS_SUMMARY_SIZE - sizeof(SEGSUM)) /
9352328Sbostic 	    sizeof(daddr_t) + 1) * sizeof(struct buf *), M_SEGMENT, M_WAITOK);
9452328Sbostic 	sp->seg_flags = SEGM_CKP;
9556027Sbostic 	sp->vp = NULL;
9652328Sbostic 
9752328Sbostic 	/*
9852328Sbostic 	 * Keep a cumulative count of the outstanding I/O operations.  If the
9952328Sbostic 	 * disk drive catches up with us it could go to zero before we finish,
10052328Sbostic 	 * so we artificially increment it by one until we've scheduled all of
10152328Sbostic 	 * the writes we intend to do.
10252328Sbostic 	 */
10352328Sbostic 	s = splbio();
10452688Sbostic 	++fs->lfs_iocount;
10552328Sbostic 	splx(s);
10652328Sbostic 
10752328Sbostic 	ip = VTOI(vp);
10855551Sbostic 	do {
10955803Sbostic 		lfs_initseg(fs, sp);
11055551Sbostic 		do {
11155551Sbostic 			if (vp->v_dirtyblkhd != NULL)
11255551Sbostic 				lfs_writefile(fs, sp, vp);
11355551Sbostic 		} while (lfs_writeinode(fs, sp, ip));
11452328Sbostic 
11555551Sbostic 	} while (lfs_writeseg(fs, sp) && ip->i_number == LFS_IFILE_INUM);
11652328Sbostic 
11752328Sbostic 	/*
11852328Sbostic 	 * If the I/O count is non-zero, sleep until it reaches zero.  At the
11952328Sbostic 	 * moment, the user's process hangs around so we can sleep.
12052328Sbostic 	 */
12152328Sbostic 	s = splbio();
12252328Sbostic 	if (--fs->lfs_iocount && (error =
12352995Sbostic 	    tsleep(&fs->lfs_iocount, PRIBIO + 1, "lfs vflush", 0))) {
12452995Sbostic 		free(sp->bpp, M_SEGMENT);
12552995Sbostic 		free(sp, M_SEGMENT);
12652328Sbostic 		return (error);
12752995Sbostic 	}
12852328Sbostic 	splx(s);
12954690Sbostic 	lfs_segunlock(fs);
13052328Sbostic 
13152995Sbostic 	/*
13252995Sbostic 	 * XXX
13352995Sbostic 	 * Should be writing a checkpoint?
13452995Sbostic 	 */
13552328Sbostic 	free(sp->bpp, M_SEGMENT);
13652328Sbostic 	free(sp, M_SEGMENT);
13752328Sbostic 
13852328Sbostic 	return (0);
13952328Sbostic }
14052328Sbostic 
14154264Sbostic void
14254264Sbostic lfs_writevnodes(fs, mp, sp, dirops)
14354264Sbostic 	struct lfs *fs;
14454264Sbostic 	struct mount *mp;
14554264Sbostic 	struct segment *sp;
14654264Sbostic 	int dirops;
14754264Sbostic {
14854264Sbostic 	struct inode *ip;
14954264Sbostic 	struct vnode *vp;
15054264Sbostic 	int error, s;
15154264Sbostic 
15254264Sbostic loop:	for (vp = mp->mnt_mounth; vp; vp = vp->v_mountf) {
15354264Sbostic 		/*
15454264Sbostic 		 * If the vnode that we are about to sync is no longer
15554264Sbostic 		 * associated with this mount point, start over.
15654264Sbostic 		 */
15754264Sbostic 		if (vp->v_mount != mp)
15854264Sbostic 			goto loop;
15954264Sbostic 
16054264Sbostic 		if (dirops && !(vp->v_flag & VDIROP) ||
16154264Sbostic 		    !dirops && (vp->v_flag & VDIROP))
16254264Sbostic 			continue;
16354264Sbostic 		/*
16454264Sbostic 		 * XXX
16554264Sbostic 		 * Up the ref count so we don't get tossed out of
16654264Sbostic 		 * memory.
16754264Sbostic 		 */
16854264Sbostic 		VREF(vp);
16954264Sbostic 
17054264Sbostic 		/*
17154264Sbostic 		 * Write the inode/file if dirty and it's not the
17254264Sbostic 		 * the IFILE.
17354264Sbostic 		 */
17454264Sbostic 		ip = VTOI(vp);
17554264Sbostic 		if ((ip->i_flag & (IMOD | IACC | IUPD | ICHG) ||
17654264Sbostic 		    vp->v_dirtyblkhd != NULL) &&
17754264Sbostic 		    ip->i_number != LFS_IFILE_INUM) {
17854264Sbostic 			if (vp->v_dirtyblkhd != NULL)
17954264Sbostic 				lfs_writefile(fs, sp, vp);
18054264Sbostic 			(void) lfs_writeinode(fs, sp, ip);
18154264Sbostic 		}
18254264Sbostic 		vp->v_flag &= ~VDIROP;
18354264Sbostic 		vrele(vp);
18454264Sbostic 	}
18554264Sbostic }
18654264Sbostic 
18752328Sbostic int
18851215Sbostic lfs_segwrite(mp, do_ckp)
18952085Sbostic 	struct mount *mp;
19051860Sbostic 	int do_ckp;			/* Do a checkpoint. */
19151188Sbostic {
19255592Sbostic 	struct buf *bp;
19352085Sbostic 	struct inode *ip;
19451499Sbostic 	struct lfs *fs;
19552085Sbostic 	struct segment *sp;
19652085Sbostic 	struct vnode *vp;
19755592Sbostic 	SEGUSE *segusep;
19855592Sbostic 	daddr_t ibno;
19955940Sbostic 	CLEANERINFO *cip;
20055940Sbostic 	int clean, error, i, s;
20151188Sbostic 
20252328Sbostic 	fs = VFSTOUFS(mp)->um_lfs;
20355940Sbostic 
20455940Sbostic  	/*
20555940Sbostic  	 * If we have fewer than 2 clean segments, wait until cleaner
20655940Sbostic 	 * writes.
20755940Sbostic  	 */
20855940Sbostic 	do {
20955940Sbostic 		LFS_CLEANERINFO(cip, fs, bp);
21055940Sbostic 		clean = cip->clean;
21155940Sbostic 		brelse(bp);
21255940Sbostic 		if (clean <= 2) {
21355940Sbostic 			printf ("segs clean: %d\n", clean);
21455940Sbostic 			wakeup(&lfs_allclean_wakeup);
21555940Sbostic 			if (error = tsleep(&fs->lfs_avail, PRIBIO + 1,
21655940Sbostic 			    "lfs writer", 0))
21755940Sbostic 				return (error);
21855940Sbostic 		}
21955940Sbostic 	} while (clean <= 2 );
22054690Sbostic 	lfs_seglock(fs);
22152085Sbostic 
22251860Sbostic 	/*
22352328Sbostic 	 * Allocate a segment structure and enough space to hold pointers to
22452328Sbostic 	 * the maximum possible number of buffers which can be described in a
22552328Sbostic 	 * single summary block.
22652328Sbostic 	 */
22755940Sbostic 	do_ckp = do_ckp || fs->lfs_nactive > MAX_ACTIVE;
22852328Sbostic 	sp = malloc(sizeof(struct segment), M_SEGMENT, M_WAITOK);
22952328Sbostic 	sp->bpp = malloc(((LFS_SUMMARY_SIZE - sizeof(SEGSUM)) /
23052328Sbostic 	    sizeof(daddr_t) + 1) * sizeof(struct buf *), M_SEGMENT, M_WAITOK);
23152328Sbostic 	sp->seg_flags = do_ckp ? SEGM_CKP : 0;
23256027Sbostic 	sp->vp = NULL;
23352328Sbostic 	lfs_initseg(fs, sp);
23452328Sbostic 
23552328Sbostic 	/*
23652688Sbostic 	 * Keep a cumulative count of the outstanding I/O operations.  If the
23752688Sbostic 	 * disk drive catches up with us it could go to zero before we finish,
23852688Sbostic 	 * so we artificially increment it by one until we've scheduled all of
23952688Sbostic 	 * the writes we intend to do.  If not a checkpoint, we never do the
24052688Sbostic 	 * final decrement, avoiding the wakeup in the callback routine.
24151860Sbostic 	 */
24252688Sbostic 	s = splbio();
24355551Sbostic 	++fs->lfs_iocount;
24452688Sbostic 	splx(s);
24551342Sbostic 
24654264Sbostic 	lfs_writevnodes(fs, mp, sp, 0);
24754264Sbostic 	fs->lfs_writer = 1;
24854264Sbostic 	if (fs->lfs_dirops && (error =
24954264Sbostic 	    tsleep(&fs->lfs_writer, PRIBIO + 1, "lfs writer", 0))) {
25054264Sbostic 		free(sp->bpp, M_SEGMENT);
25154264Sbostic 		free(sp, M_SEGMENT);
25254264Sbostic 		fs->lfs_writer = 0;
25355551Sbostic 		return (error);
25454264Sbostic 	}
25551860Sbostic 
25654264Sbostic 	lfs_writevnodes(fs, mp, sp, 1);
25751860Sbostic 
25854264Sbostic 	/*
25955592Sbostic 	 * If we are doing a checkpoint, mark everything since the
26055592Sbostic 	 * last checkpoint as no longer ACTIVE.
26154264Sbostic 	 */
26255592Sbostic 	if (do_ckp)
26355592Sbostic 		for (ibno = fs->lfs_cleansz + fs->lfs_segtabsz;
26455592Sbostic 		     --ibno >= fs->lfs_cleansz; ) {
26555592Sbostic 			if (bread(fs->lfs_ivnode, ibno, fs->lfs_bsize,
26655592Sbostic 			    NOCRED, &bp))
26755592Sbostic 
26855592Sbostic 				panic("lfs: ifile read");
26955592Sbostic 			segusep = (SEGUSE *)bp->b_un.b_addr;
27055592Sbostic 			for (i = fs->lfs_sepb; i--; segusep++)
27155592Sbostic 				segusep->su_flags &= ~SEGUSE_ACTIVE;
27255592Sbostic 
27355940Sbostic 			error = VOP_BWRITE(bp);
27455592Sbostic 		}
27555592Sbostic 
27654264Sbostic 	if (do_ckp || fs->lfs_doifile) {
277*56086Sbostic redo:
27854264Sbostic 		vp = fs->lfs_ivnode;
27954264Sbostic 		while (vget(vp));
28052328Sbostic 		ip = VTOI(vp);
28155592Sbostic 		if (vp->v_dirtyblkhd != NULL)
28255592Sbostic 			lfs_writefile(fs, sp, vp);
28355592Sbostic 		(void)lfs_writeinode(fs, sp, ip);
28452077Sbostic 		vput(vp);
285*56086Sbostic 		if (lfs_writeseg(fs, sp) && do_ckp) {
286*56086Sbostic 			lfs_initseg(fs, sp);
287*56086Sbostic 			goto redo;
288*56086Sbostic 		}
28954264Sbostic 	} else
29054264Sbostic 		(void) lfs_writeseg(fs, sp);
29151342Sbostic 
29251215Sbostic 	/*
29351860Sbostic 	 * If the I/O count is non-zero, sleep until it reaches zero.  At the
29451860Sbostic 	 * moment, the user's process hangs around so we can sleep.
29551215Sbostic 	 */
29654264Sbostic 	fs->lfs_writer = 0;
29754264Sbostic 	fs->lfs_doifile = 0;
29854264Sbostic 	wakeup(&fs->lfs_dirops);
29954264Sbostic 
30055551Sbostic 	s = splbio();
30155551Sbostic 	--fs->lfs_iocount;
30251860Sbostic 	if (do_ckp) {
30352688Sbostic 		if (fs->lfs_iocount && (error =
30452995Sbostic 		    tsleep(&fs->lfs_iocount, PRIBIO + 1, "lfs sync", 0))) {
30552995Sbostic 			free(sp->bpp, M_SEGMENT);
30652995Sbostic 			free(sp, M_SEGMENT);
30751915Sbostic 			return (error);
30852995Sbostic 		}
30951860Sbostic 		splx(s);
31055940Sbostic 		fs->lfs_nactive = 0;
31151860Sbostic 		lfs_writesuper(fs, sp);
31252688Sbostic 	} else
31352688Sbostic 		splx(s);
31451215Sbostic 
31554690Sbostic 	lfs_segunlock(fs);
31654690Sbostic 
31751927Sbostic 	free(sp->bpp, M_SEGMENT);
31851927Sbostic 	free(sp, M_SEGMENT);
31951215Sbostic 
32051860Sbostic 	return (0);
32151188Sbostic }
32251188Sbostic 
32351860Sbostic /*
32451860Sbostic  * Write the dirty blocks associated with a vnode.
32551860Sbostic  */
32652077Sbostic void
32751860Sbostic lfs_writefile(fs, sp, vp)
32851499Sbostic 	struct lfs *fs;
32952085Sbostic 	struct segment *sp;
33052085Sbostic 	struct vnode *vp;
33151188Sbostic {
33251860Sbostic 	struct buf *bp;
33352085Sbostic 	struct finfo *fip;
33451860Sbostic 	IFILE *ifp;
33551188Sbostic 
33652085Sbostic 	if (sp->seg_bytes_left < fs->lfs_bsize ||
33752085Sbostic 	    sp->sum_bytes_left < sizeof(struct finfo)) {
33854264Sbostic 		(void) lfs_writeseg(fs, sp);
33952085Sbostic 		lfs_initseg(fs, sp);
34052085Sbostic 	}
34152085Sbostic 	sp->sum_bytes_left -= sizeof(struct finfo) - sizeof(daddr_t);
34251215Sbostic 
34352085Sbostic 	fip = sp->fip;
34452085Sbostic 	fip->fi_nblocks = 0;
34552085Sbostic 	fip->fi_ino = VTOI(vp)->i_number;
34652085Sbostic 	LFS_IENTRY(ifp, fs, fip->fi_ino, bp);
34752085Sbostic 	fip->fi_version = ifp->if_version;
34852085Sbostic 	brelse(bp);
34951188Sbostic 
35052085Sbostic 	/*
35152085Sbostic 	 * It may not be necessary to write the meta-data blocks at this point,
35252085Sbostic 	 * as the roll-forward recovery code should be able to reconstruct the
35352085Sbostic 	 * list.
35452085Sbostic 	 */
35552085Sbostic 	lfs_gather(fs, sp, vp, lfs_match_data);
35652085Sbostic 	lfs_gather(fs, sp, vp, lfs_match_indir);
35752085Sbostic 	lfs_gather(fs, sp, vp, lfs_match_dindir);
35851860Sbostic #ifdef TRIPLE
35952085Sbostic 	lfs_gather(fs, sp, vp, lfs_match_tindir);
36051860Sbostic #endif
36151342Sbostic 
36252085Sbostic 	fip = sp->fip;
36351860Sbostic #ifdef META
36452085Sbostic 	printf("lfs_writefile: adding %d blocks\n", fip->fi_nblocks);
36551860Sbostic #endif
36652085Sbostic 	if (fip->fi_nblocks != 0) {
36752085Sbostic 		++((SEGSUM *)(sp->segsum))->ss_nfinfo;
36852085Sbostic 		sp->fip =
36952085Sbostic 		    (struct finfo *)((caddr_t)fip + sizeof(struct finfo) +
37052085Sbostic 		    sizeof(daddr_t) * (fip->fi_nblocks - 1));
37155940Sbostic 		sp->start_lbp = &sp->fip->fi_blocks[0];
37252682Sstaelin 	} else
37352682Sstaelin 		sp->sum_bytes_left += sizeof(struct finfo) - sizeof(daddr_t);
37451215Sbostic }
37551215Sbostic 
37654264Sbostic int
37751915Sbostic lfs_writeinode(fs, sp, ip)
37851915Sbostic 	struct lfs *fs;
37952085Sbostic 	struct segment *sp;
38052085Sbostic 	struct inode *ip;
38151915Sbostic {
38252085Sbostic 	struct buf *bp, *ibp;
38352077Sbostic 	IFILE *ifp;
38452682Sstaelin 	SEGUSE *sup;
38552682Sstaelin 	daddr_t daddr;
38652077Sbostic 	ino_t ino;
38755940Sbostic 	int error, ndx;
38854264Sbostic 	int redo_ifile = 0;
38951915Sbostic 
39055940Sbostic 	if (!(ip->i_flag & (IMOD | IACC | IUPD | ICHG)))
39155940Sbostic 		return;
39255940Sbostic 
39351915Sbostic 	/* Allocate a new inode block if necessary. */
39451915Sbostic 	if (sp->ibp == NULL) {
39551915Sbostic 		/* Allocate a new segment if necessary. */
39651915Sbostic 		if (sp->seg_bytes_left < fs->lfs_bsize ||
39751915Sbostic 		    sp->sum_bytes_left < sizeof(daddr_t)) {
39854264Sbostic 			(void) lfs_writeseg(fs, sp);
39951915Sbostic 			lfs_initseg(fs, sp);
40051915Sbostic 		}
40151915Sbostic 
40251915Sbostic 		/* Get next inode block. */
40352682Sstaelin 		daddr = fs->lfs_offset;
40451915Sbostic 		fs->lfs_offset += fsbtodb(fs, 1);
40551915Sbostic 		sp->ibp = *sp->cbpp++ =
40656056Sbostic 		    lfs_newbuf(VTOI(fs->lfs_ivnode)->i_devvp, daddr,
40756056Sbostic 		    fs->lfs_bsize);
40855940Sbostic 		++sp->start_bpp;
40955940Sbostic 		fs->lfs_avail -= fsbtodb(fs, 1);
41052688Sbostic 		/* Set remaining space counters. */
41151915Sbostic 		sp->seg_bytes_left -= fs->lfs_bsize;
41251915Sbostic 		sp->sum_bytes_left -= sizeof(daddr_t);
41352077Sbostic 		ndx = LFS_SUMMARY_SIZE / sizeof(daddr_t) -
41451915Sbostic 		    sp->ninodes / INOPB(fs) - 1;
41552682Sstaelin 		((daddr_t *)(sp->segsum))[ndx] = daddr;
41651915Sbostic 	}
41751915Sbostic 
41852085Sbostic 	/* Update the inode times and copy the inode onto the inode page. */
41956056Sbostic 	if (ip->i_flag & IMOD)
42056056Sbostic 		--fs->lfs_uinodes;
42152077Sbostic 	ITIMES(ip, &time, &time);
42255940Sbostic 	ip->i_flag &= ~(IMOD | IACC | IUPD | ICHG);
42351915Sbostic 	bp = sp->ibp;
42452085Sbostic 	bp->b_un.b_dino[sp->ninodes % INOPB(fs)] = ip->i_din;
42551915Sbostic 	/* Increment inode count in segment summary block. */
42651915Sbostic 	++((SEGSUM *)(sp->segsum))->ss_ninos;
42751915Sbostic 
42851915Sbostic 	/* If this page is full, set flag to allocate a new page. */
42951915Sbostic 	if (++sp->ninodes % INOPB(fs) == 0)
43051915Sbostic 		sp->ibp = NULL;
43151915Sbostic 
43251915Sbostic 	/*
43352077Sbostic 	 * If updating the ifile, update the super-block.  Update the disk
43452077Sbostic 	 * address and access times for this inode in the ifile.
43551915Sbostic 	 */
43652077Sbostic 	ino = ip->i_number;
43755696Sbostic 	if (ino == LFS_IFILE_INUM) {
43855696Sbostic 		daddr = fs->lfs_idaddr;
43951915Sbostic 		fs->lfs_idaddr = bp->b_blkno;
44055696Sbostic 	} else {
44155696Sbostic 		LFS_IENTRY(ifp, fs, ino, ibp);
44255696Sbostic 		daddr = ifp->if_daddr;
44355696Sbostic 		ifp->if_daddr = bp->b_blkno;
44455940Sbostic 		error = VOP_BWRITE(ibp);
44555696Sbostic 	}
44652077Sbostic 
44754264Sbostic 	/*
44854264Sbostic 	 * No need to update segment usage if there was no former inode address
44954264Sbostic 	 * or if the last inode address is in the current partial segment.
45054264Sbostic 	 */
45154264Sbostic 	if (daddr != LFS_UNUSED_DADDR &&
45255803Sbostic 	    !(daddr >= fs->lfs_lastpseg && daddr <= bp->b_blkno)) {
45352682Sstaelin 		LFS_SEGENTRY(sup, fs, datosn(fs, daddr), bp);
45452682Sstaelin #ifdef DIAGNOSTIC
45554264Sbostic 		if (sup->su_nbytes < sizeof(struct dinode)) {
45652819Sbostic 			/* XXX -- Change to a panic. */
45752819Sbostic 			printf("lfs: negative bytes (segment %d)\n",
45852682Sstaelin 			    datosn(fs, daddr));
45954264Sbostic 			panic("negative bytes");
46054264Sbostic 		}
46152682Sstaelin #endif
46252682Sstaelin 		sup->su_nbytes -= sizeof(struct dinode);
46356069Sbostic 		redo_ifile =
46456069Sbostic 		    (ino == LFS_IFILE_INUM && !(bp->b_flags & B_GATHERED));
46555940Sbostic 		error = VOP_BWRITE(bp);
46652682Sstaelin 	}
46755551Sbostic 	return (redo_ifile);
46851915Sbostic }
46951915Sbostic 
47055940Sbostic int
47155940Sbostic lfs_gatherblock(sp, bp, sptr)
47255940Sbostic 	struct segment *sp;
47355940Sbostic 	struct buf *bp;
47455940Sbostic 	int *sptr;
47555940Sbostic {
47655940Sbostic 	struct lfs *fs;
47755940Sbostic 	int version;
47855940Sbostic 
47955940Sbostic 	/*
48055940Sbostic 	 * If full, finish this segment.  We may be doing I/O, so
48155940Sbostic 	 * release and reacquire the splbio().
48255940Sbostic 	 */
48356027Sbostic #ifdef DIAGNOSTIC
48456027Sbostic 	if (sp->vp == NULL)
48556027Sbostic 		panic ("lfs_gatherblock: Null vp in segment");
48656027Sbostic #endif
48755940Sbostic 	fs = sp->fs;
48855940Sbostic 	if (sp->sum_bytes_left < sizeof(daddr_t) ||
48955940Sbostic 	    sp->seg_bytes_left < fs->lfs_bsize) {
49055940Sbostic 		if (sptr)
49155940Sbostic 			splx(*sptr);
49256027Sbostic 		lfs_updatemeta(sp);
49355940Sbostic 
49455940Sbostic 		/* Add the current file to the segment summary. */
49555940Sbostic 		++((SEGSUM *)(sp->segsum))->ss_nfinfo;
49655940Sbostic 
49755940Sbostic 		version = sp->fip->fi_version;
49855940Sbostic 		(void) lfs_writeseg(fs, sp);
49955940Sbostic 		lfs_initseg(fs, sp);
50055940Sbostic 
50155940Sbostic 		sp->fip->fi_version = version;
50256027Sbostic 		sp->fip->fi_ino = VTOI(sp->vp)->i_number;
50355940Sbostic 
50455940Sbostic 		sp->sum_bytes_left -=
50555940Sbostic 		    sizeof(struct finfo) - sizeof(daddr_t);
50655940Sbostic 
50755940Sbostic 		if (sptr)
50855940Sbostic 			*sptr = splbio();
50955940Sbostic 		return(1);
51055940Sbostic 	}
51155940Sbostic 
51255940Sbostic 	/* Insert into the buffer list, update the FINFO block. */
51356056Sbostic if (bp->b_vp == sp->fs->lfs_ivnode &&
51456056Sbostic ((bp->b_lblkno == 0 && (bp->b_un.b_daddr[0] > 26 || bp->b_un.b_daddr[1] > 26)) ||
51556056Sbostic (bp->b_lblkno > 2)))
51656056Sbostic 	printf ("Bad ifile block\n");
51755940Sbostic 	bp->b_flags |= B_GATHERED;
51855940Sbostic 	*sp->cbpp++ = bp;
51955940Sbostic 	sp->fip->fi_blocks[sp->fip->fi_nblocks++] = bp->b_lblkno;
52055940Sbostic 
52155940Sbostic 	sp->sum_bytes_left -= sizeof(daddr_t);
52255940Sbostic 	sp->seg_bytes_left -= bp->b_bufsize;
52355940Sbostic 	return(0);
52455940Sbostic }
52555940Sbostic 
52652077Sbostic void
52751215Sbostic lfs_gather(fs, sp, vp, match)
52851499Sbostic 	struct lfs *fs;
52952085Sbostic 	struct segment *sp;
53052085Sbostic 	struct vnode *vp;
53152085Sbostic 	int (*match) __P((struct lfs *, struct buf *));
53251215Sbostic {
53355940Sbostic 	struct buf *bp;
53451342Sbostic 	int s;
53551215Sbostic 
53656027Sbostic 	sp->vp = vp;
53755940Sbostic 	s = splbio();
53855940Sbostic loop:	for (bp = vp->v_dirtyblkhd; bp; bp = bp->b_blockf) {
53954264Sbostic 		if (bp->b_flags & B_BUSY || !match(fs, bp) ||
54054264Sbostic 		    bp->b_flags & B_GATHERED)
54151215Sbostic 			continue;
54251342Sbostic #ifdef DIAGNOSTIC
54351860Sbostic 		if (!(bp->b_flags & B_DELWRI))
54451915Sbostic 			panic("lfs_gather: bp not B_DELWRI");
54551860Sbostic 		if (!(bp->b_flags & B_LOCKED))
54651915Sbostic 			panic("lfs_gather: bp not B_LOCKED");
54751342Sbostic #endif
54855940Sbostic 		if (lfs_gatherblock(sp, bp, &s))
54953145Sstaelin 			goto loop;
55051188Sbostic 	}
55151215Sbostic 	splx(s);
55256027Sbostic 	lfs_updatemeta(sp);
55356027Sbostic 	sp->vp = NULL;
55451188Sbostic }
55551188Sbostic 
55655940Sbostic 
55751342Sbostic /*
55851342Sbostic  * Update the metadata that points to the blocks listed in the FINFO
55951188Sbostic  * array.
56051188Sbostic  */
56152077Sbostic void
56256027Sbostic lfs_updatemeta(sp)
56352085Sbostic 	struct segment *sp;
56451188Sbostic {
56551915Sbostic 	SEGUSE *sup;
56652085Sbostic 	struct buf *bp;
56755940Sbostic 	struct lfs *fs;
56856027Sbostic 	struct vnode *vp;
56951860Sbostic 	INDIR a[NIADDR], *ap;
57052085Sbostic 	struct inode *ip;
57151915Sbostic 	daddr_t daddr, lbn, off;
57255940Sbostic 	int db_per_fsb, error, i, nblocks, num;
57351188Sbostic 
57456027Sbostic 	vp = sp->vp;
57555940Sbostic 	nblocks = &sp->fip->fi_blocks[sp->fip->fi_nblocks] - sp->start_lbp;
57656027Sbostic 	if (vp == NULL || nblocks == 0)
57751215Sbostic 		return;
57851215Sbostic 
57951915Sbostic 	/* Sort the blocks. */
58055940Sbostic 	if (!(sp->seg_flags & SEGM_CLEAN))
58155940Sbostic 		lfs_shellsort(sp->start_bpp, sp->start_lbp, nblocks);
58251215Sbostic 
58351915Sbostic 	/*
58451915Sbostic 	 * Assign disk addresses, and update references to the logical
58551915Sbostic 	 * block and the segment usage information.
58651915Sbostic 	 */
58755940Sbostic 	fs = sp->fs;
58851860Sbostic 	db_per_fsb = fsbtodb(fs, 1);
58955940Sbostic 	for (i = nblocks; i--; ++sp->start_bpp) {
59055940Sbostic 		lbn = *sp->start_lbp++;
59155940Sbostic 		(*sp->start_bpp)->b_blkno = off = fs->lfs_offset;
59251860Sbostic 		fs->lfs_offset += db_per_fsb;
59351215Sbostic 
59451860Sbostic 		if (error = lfs_bmaparray(vp, lbn, &daddr, a, &num))
59552085Sbostic 			panic("lfs_updatemeta: lfs_bmaparray %d", error);
59651860Sbostic 		ip = VTOI(vp);
59751860Sbostic 		switch (num) {
59851860Sbostic 		case 0:
59951915Sbostic 			ip->i_db[lbn] = off;
60051860Sbostic 			break;
60151860Sbostic 		case 1:
60251915Sbostic 			ip->i_ib[a[0].in_off] = off;
60351860Sbostic 			break;
60451860Sbostic 		default:
60551860Sbostic 			ap = &a[num - 1];
60651860Sbostic 			if (bread(vp, ap->in_lbn, fs->lfs_bsize, NOCRED, &bp))
60751860Sbostic 				panic("lfs_updatemeta: bread bno %d",
60851860Sbostic 				    ap->in_lbn);
60955458Sbostic 			/*
61055458Sbostic 			 * Bread may create a new indirect block which needs
61155458Sbostic 			 * to get counted for the inode.
61255458Sbostic 			 */
61355592Sbostic 			if (bp->b_blkno == -1 && !(bp->b_flags & B_CACHE)) {
61455940Sbostic printf ("Updatemeta allocating indirect block: shouldn't happen\n");
61555458Sbostic 				ip->i_blocks += btodb(fs->lfs_bsize);
61655592Sbostic 				fs->lfs_bfree -= btodb(fs->lfs_bsize);
61755592Sbostic 			}
61851915Sbostic 			bp->b_un.b_daddr[ap->in_off] = off;
61953530Sheideman 			VOP_BWRITE(bp);
62051188Sbostic 		}
62151915Sbostic 
62251915Sbostic 		/* Update segment usage information. */
62351915Sbostic 		if (daddr != UNASSIGNED) {
62451915Sbostic 			LFS_SEGENTRY(sup, fs, datosn(fs, daddr), bp);
62551915Sbostic #ifdef DIAGNOSTIC
62654264Sbostic 			if (sup->su_nbytes < fs->lfs_bsize) {
62752819Sbostic 				/* XXX -- Change to a panic. */
62852819Sbostic 				printf("lfs: negative bytes (segment %d)\n",
62951915Sbostic 				    datosn(fs, daddr));
63054264Sbostic 				panic ("Negative Bytes");
63154264Sbostic 			}
63251915Sbostic #endif
63351915Sbostic 			sup->su_nbytes -= fs->lfs_bsize;
63455940Sbostic 			error = VOP_BWRITE(bp);
63551915Sbostic 		}
63651188Sbostic 	}
63751188Sbostic }
63851188Sbostic 
63951915Sbostic /*
64051915Sbostic  * Start a new segment.
64151915Sbostic  */
64252077Sbostic void
64351915Sbostic lfs_initseg(fs, sp)
64451499Sbostic 	struct lfs *fs;
64552085Sbostic 	struct segment *sp;
64651188Sbostic {
64751915Sbostic 	SEGUSE *sup;
64851915Sbostic 	SEGSUM *ssp;
64951915Sbostic 	struct buf *bp;
65051915Sbostic 	daddr_t lbn, *lbnp;
65151215Sbostic 
65251915Sbostic 	/* Advance to the next segment. */
65351927Sbostic 	if (!LFS_PARTIAL_FITS(fs)) {
65452682Sstaelin 		/* Wake up any cleaning procs waiting on this file system. */
65552688Sbostic 		wakeup(&fs->lfs_nextseg);
65652688Sbostic 		wakeup(&lfs_allclean_wakeup);
65752682Sstaelin 
65851927Sbostic 		lfs_newseg(fs);
65951927Sbostic 		fs->lfs_offset = fs->lfs_curseg;
66051915Sbostic 		sp->seg_number = datosn(fs, fs->lfs_curseg);
66151915Sbostic 		sp->seg_bytes_left = fs->lfs_dbpseg * DEV_BSIZE;
66251915Sbostic 
66351915Sbostic 		/*
66451927Sbostic 		 * If the segment contains a superblock, update the offset
66551927Sbostic 		 * and summary address to skip over it.
66651915Sbostic 		 */
66752077Sbostic 		LFS_SEGENTRY(sup, fs, sp->seg_number, bp);
66851927Sbostic 		if (sup->su_flags & SEGUSE_SUPERBLOCK) {
66951915Sbostic 			fs->lfs_offset += LFS_SBPAD / DEV_BSIZE;
67051915Sbostic 			sp->seg_bytes_left -= LFS_SBPAD;
67151215Sbostic 		}
67252085Sbostic 		brelse(bp);
67351915Sbostic 	} else {
67451915Sbostic 		sp->seg_number = datosn(fs, fs->lfs_curseg);
67551915Sbostic 		sp->seg_bytes_left = (fs->lfs_dbpseg -
67651915Sbostic 		    (fs->lfs_offset - fs->lfs_curseg)) * DEV_BSIZE;
67751915Sbostic 	}
67854264Sbostic 	fs->lfs_lastpseg = fs->lfs_offset;
67951342Sbostic 
68055940Sbostic 	sp->fs = fs;
68151915Sbostic 	sp->ibp = NULL;
68251915Sbostic 	sp->ninodes = 0;
68351342Sbostic 
68451915Sbostic 	/* Get a new buffer for SEGSUM and enter it into the buffer list. */
68551915Sbostic 	sp->cbpp = sp->bpp;
68656056Sbostic 	*sp->cbpp = lfs_newbuf(VTOI(fs->lfs_ivnode)->i_devvp, fs->lfs_offset,
68756056Sbostic 	     LFS_SUMMARY_SIZE);
68851915Sbostic 	sp->segsum = (*sp->cbpp)->b_un.b_addr;
68955940Sbostic 	sp->start_bpp = ++sp->cbpp;
69051915Sbostic 	fs->lfs_offset += LFS_SUMMARY_SIZE / DEV_BSIZE;
69151342Sbostic 
69251915Sbostic 	/* Set point to SEGSUM, initialize it. */
69351915Sbostic 	ssp = sp->segsum;
69451915Sbostic 	ssp->ss_next = fs->lfs_nextseg;
69551915Sbostic 	ssp->ss_nfinfo = ssp->ss_ninos = 0;
69651342Sbostic 
69751915Sbostic 	/* Set pointer to first FINFO, initialize it. */
69852085Sbostic 	sp->fip = (struct finfo *)(sp->segsum + sizeof(SEGSUM));
69951915Sbostic 	sp->fip->fi_nblocks = 0;
70055940Sbostic 	sp->start_lbp = &sp->fip->fi_blocks[0];
70151342Sbostic 
70251915Sbostic 	sp->seg_bytes_left -= LFS_SUMMARY_SIZE;
70351915Sbostic 	sp->sum_bytes_left = LFS_SUMMARY_SIZE - sizeof(SEGSUM);
70451915Sbostic }
70551342Sbostic 
70651915Sbostic /*
70751915Sbostic  * Return the next segment to write.
70851915Sbostic  */
70952077Sbostic void
71051915Sbostic lfs_newseg(fs)
71151915Sbostic 	struct lfs *fs;
71251915Sbostic {
71351927Sbostic 	CLEANERINFO *cip;
71451915Sbostic 	SEGUSE *sup;
71551915Sbostic 	struct buf *bp;
71655940Sbostic 	int curseg, error, isdirty, sn;
71751915Sbostic 
71855592Sbostic         LFS_SEGENTRY(sup, fs, datosn(fs, fs->lfs_nextseg), bp);
71955592Sbostic         sup->su_flags |= SEGUSE_DIRTY;
72056056Sbostic 	sup->su_nbytes = 0;
72156056Sbostic 	sup->su_nsums = 0;
72256056Sbostic 	sup->su_ninos = 0;
72355940Sbostic         (void) VOP_BWRITE(bp);
72451927Sbostic 
72551927Sbostic 	LFS_CLEANERINFO(cip, fs, bp);
72651927Sbostic 	--cip->clean;
72751927Sbostic 	++cip->dirty;
72855940Sbostic 	(void) VOP_BWRITE(bp);
72951927Sbostic 
73051927Sbostic 	fs->lfs_lastseg = fs->lfs_curseg;
73151927Sbostic 	fs->lfs_curseg = fs->lfs_nextseg;
73251927Sbostic 	for (sn = curseg = datosn(fs, fs->lfs_curseg);;) {
73351915Sbostic 		sn = (sn + 1) % fs->lfs_nseg;
73451927Sbostic 		if (sn == curseg)
73551915Sbostic 			panic("lfs_nextseg: no clean segments");
73651915Sbostic 		LFS_SEGENTRY(sup, fs, sn, bp);
73751915Sbostic 		isdirty = sup->su_flags & SEGUSE_DIRTY;
73852085Sbostic 		brelse(bp);
73951915Sbostic 		if (!isdirty)
74051915Sbostic 			break;
74151915Sbostic 	}
74255592Sbostic 
74355940Sbostic 	++fs->lfs_nactive;
74451927Sbostic 	fs->lfs_nextseg = sntoda(fs, sn);
74551188Sbostic }
74651188Sbostic 
74754264Sbostic int
74851188Sbostic lfs_writeseg(fs, sp)
74951499Sbostic 	struct lfs *fs;
75052085Sbostic 	struct segment *sp;
75151188Sbostic {
75255940Sbostic 	extern int locked_queue_count;
75352688Sbostic 	struct buf **bpp, *bp, *cbp;
75451188Sbostic 	SEGUSE *sup;
75552085Sbostic 	SEGSUM *ssp;
75651860Sbostic 	dev_t i_dev;
75754264Sbostic 	size_t size;
75851860Sbostic 	u_long *datap, *dp;
75955940Sbostic 	int ch_per_blk, do_again, error, i, nblocks, num, s;
76054264Sbostic 	int (*strategy)__P((struct vop_strategy_args *));
76154690Sbostic 	struct vop_strategy_args vop_strategy_a;
76255592Sbostic 	u_short ninos;
76352688Sbostic 	char *p;
76451188Sbostic 
76555940Sbostic 	/*
76655940Sbostic 	 * If there are no buffers other than the segment summary to write
76755940Sbostic 	 * and it is not a checkpoint, don't do anything.  On a checkpoint,
76855940Sbostic 	 * even if there aren't any buffers, you need to write the superblock.
76955940Sbostic 	 */
77055940Sbostic 	if ((nblocks = sp->cbpp - sp->bpp) == 1 && !(sp->seg_flags & SEGM_CKP))
77155551Sbostic 		return (0);
77252085Sbostic 
77351188Sbostic 	/*
77452085Sbostic 	 * Compute checksum across data and then across summary; the first
77552085Sbostic 	 * block (the summary block) is skipped.  Set the create time here
77652085Sbostic 	 * so that it's guaranteed to be later than the inode mod times.
77751860Sbostic 	 *
77851860Sbostic 	 * XXX
77951860Sbostic 	 * Fix this to do it inline, instead of malloc/copy.
78051188Sbostic 	 */
78151860Sbostic 	datap = dp = malloc(nblocks * sizeof(u_long), M_SEGMENT, M_WAITOK);
78251915Sbostic 	for (bpp = sp->bpp, i = nblocks - 1; i--;)
78351915Sbostic 		*dp++ = (*++bpp)->b_un.b_words[0];
78452085Sbostic 	ssp = (SEGSUM *)sp->segsum;
78552103Sbostic 	ssp->ss_create = time.tv_sec;
78655803Sbostic 	ssp->ss_datasum = cksum(datap, (nblocks - 1) * sizeof(u_long));
78752085Sbostic 	ssp->ss_sumsum =
78852085Sbostic 	    cksum(&ssp->ss_datasum, LFS_SUMMARY_SIZE - sizeof(ssp->ss_sumsum));
78951927Sbostic 	free(datap, M_SEGMENT);
79054264Sbostic 	/* Update the segment usage information. */
79154264Sbostic 	LFS_SEGENTRY(sup, fs, sp->seg_number, bp);
79255592Sbostic 	ninos = (ssp->ss_ninos + INOPB(fs) - 1) / INOPB(fs);
79355592Sbostic 	sup->su_nbytes += nblocks - 1 - ninos << fs->lfs_bshift;
79454264Sbostic 	sup->su_nbytes += ssp->ss_ninos * sizeof(struct dinode);
79555803Sbostic 	sup->su_nbytes += LFS_SUMMARY_SIZE;
79654264Sbostic 	sup->su_lastmod = time.tv_sec;
79755592Sbostic 	sup->su_flags |= SEGUSE_ACTIVE;
79855592Sbostic 	sup->su_ninos += ninos;
79955592Sbostic 	++sup->su_nsums;
80056069Sbostic 	do_again = !(bp->b_flags & B_GATHERED);
80155940Sbostic 	(void)VOP_BWRITE(bp);
80255592Sbostic 	fs->lfs_bfree -= (fsbtodb(fs, ninos) + LFS_SUMMARY_SIZE / DEV_BSIZE);
80354264Sbostic 
80451860Sbostic 	i_dev = VTOI(fs->lfs_ivnode)->i_dev;
80553574Sheideman 	strategy = VTOI(fs->lfs_ivnode)->i_devvp->v_op[VOFFSET(vop_strategy)];
80651301Sbostic 
80752688Sbostic 	/*
80852688Sbostic 	 * When we simply write the blocks we lose a rotation for every block
80952688Sbostic 	 * written.  To avoid this problem, we allocate memory in chunks, copy
81052688Sbostic 	 * the buffers into the chunk and write the chunk.  56K was chosen as
81152688Sbostic 	 * some driver/controllers can't handle unsigned 16 bit transfers.
81252688Sbostic 	 * When the data is copied to the chunk, turn off the the B_LOCKED bit
81352688Sbostic 	 * and brelse the buffer (which will move them to the LRU list).  Add
81452688Sbostic 	 * the B_CALL flag to the buffer header so we can count I/O's for the
81552688Sbostic 	 * checkpoints and so we can release the allocated memory.
81652688Sbostic 	 *
81752688Sbostic 	 * XXX
81852688Sbostic 	 * This should be removed if the new virtual memory system allows us to
81952688Sbostic 	 * easily make the buffers contiguous in kernel memory and if that's
82052688Sbostic 	 * fast enough.
82152688Sbostic 	 */
82252688Sbostic #define	LFS_CHUNKSIZE	(56 * 1024)
82352688Sbostic 	ch_per_blk = LFS_CHUNKSIZE / fs->lfs_bsize;
82452688Sbostic 	for (bpp = sp->bpp, i = nblocks; i;) {
82552688Sbostic 		num = ch_per_blk;
82652688Sbostic 		if (num > i)
82752688Sbostic 			num = i;
82852688Sbostic 		i -= num;
82952688Sbostic 		size = num * fs->lfs_bsize;
83052688Sbostic 
83156056Sbostic 		cbp = lfs_newbuf(VTOI(fs->lfs_ivnode)->i_devvp,
83256056Sbostic 		    (*bpp)->b_blkno, size);
83352688Sbostic 		cbp->b_dev = i_dev;
83455940Sbostic 		cbp->b_flags |= B_ASYNC | B_BUSY;
83552688Sbostic 
83652688Sbostic 		s = splbio();
83752688Sbostic 		++fs->lfs_iocount;
83852688Sbostic 		for (p = cbp->b_un.b_addr; num--;) {
83952688Sbostic 			bp = *bpp++;
84055940Sbostic 			/*
84155940Sbostic 			 * Fake buffers from the cleaner are marked as B_INVAL.
84255940Sbostic 			 * We need to copy the data from user space rather than
84355940Sbostic 			 * from the buffer indicated.
84455940Sbostic 			 * XXX == what do I do on an error?
84555940Sbostic 			 */
84655940Sbostic 			if (bp->b_flags & B_INVAL) {
84755940Sbostic 				if (copyin(bp->b_saveaddr, p, bp->b_bcount))
84855940Sbostic 					panic("lfs_writeseg: copyin failed");
84955940Sbostic 			} else
85055940Sbostic 				bcopy(bp->b_un.b_addr, p, bp->b_bcount);
85152688Sbostic 			p += bp->b_bcount;
85255940Sbostic 			if (bp->b_flags & B_LOCKED)
85355940Sbostic 				--locked_queue_count;
85455940Sbostic 			bp->b_flags &= ~(B_ERROR | B_READ | B_DELWRI |
85554264Sbostic 			     B_LOCKED | B_GATHERED);
85655940Sbostic 			if (bp->b_flags & B_CALL) {
85755940Sbostic 				/* if B_CALL, it was created with newbuf */
85855940Sbostic 				brelvp(bp);
85955940Sbostic 				free(bp, M_SEGMENT);
86055940Sbostic 			} else {
86152688Sbostic 				bremfree(bp);
86252688Sbostic 				reassignbuf(bp, bp->b_vp);
86355940Sbostic 				brelse(bp);
86452688Sbostic 			}
86551860Sbostic 		}
86656069Sbostic 		++cbp->b_vp->v_numoutput;
86752688Sbostic 		splx(s);
86852688Sbostic 		cbp->b_bcount = p - cbp->b_un.b_addr;
86956056Sbostic 		/*
87056056Sbostic 		 * XXXX This is a gross and disgusting hack.  Since these
87156056Sbostic 		 * buffers are physically addressed, they hang off the
87256056Sbostic 		 * device vnode (devvp).  As a result, they have no way
87356056Sbostic 		 * of getting to the LFS superblock or lfs structure to
87456056Sbostic 		 * keep track of the number of I/O's pending.  So, I am
87556056Sbostic 		 * going to stuff the fs into the saveaddr field of
87656056Sbostic 		 * the buffer (yuk).
87756056Sbostic 		 */
87856056Sbostic 		cbp->b_saveaddr = (caddr_t)fs;
87953574Sheideman 		vop_strategy_a.a_desc = VDESC(vop_strategy);
88053574Sheideman 		vop_strategy_a.a_bp = cbp;
88153574Sheideman 		(strategy)(&vop_strategy_a);
88251860Sbostic 	}
88355551Sbostic 	return (do_again);
88451188Sbostic }
88551188Sbostic 
88652077Sbostic void
88751860Sbostic lfs_writesuper(fs, sp)
88851499Sbostic 	struct lfs *fs;
88952085Sbostic 	struct segment *sp;
89051301Sbostic {
89152085Sbostic 	struct buf *bp;
89251860Sbostic 	dev_t i_dev;
89353574Sheideman 	int (*strategy) __P((struct vop_strategy_args *));
89456069Sbostic 	int s;
89554690Sbostic 	struct vop_strategy_args vop_strategy_a;
89651301Sbostic 
89751860Sbostic 	i_dev = VTOI(fs->lfs_ivnode)->i_dev;
89853574Sheideman 	strategy = VTOI(fs->lfs_ivnode)->i_devvp->v_op[VOFFSET(vop_strategy)];
89951356Sbostic 
90051342Sbostic 	/* Checksum the superblock and copy it into a buffer. */
90151499Sbostic 	fs->lfs_cksum = cksum(fs, sizeof(struct lfs) - sizeof(fs->lfs_cksum));
90256056Sbostic 	bp = lfs_newbuf(VTOI(fs->lfs_ivnode)->i_devvp, fs->lfs_sboffs[0],
90356056Sbostic 	    LFS_SBPAD);
90451860Sbostic 	*bp->b_un.b_lfs = *fs;
90551215Sbostic 
90651356Sbostic 	/* Write the first superblock (wait). */
90751860Sbostic 	bp->b_dev = i_dev;
90851915Sbostic 	bp->b_flags |= B_BUSY;
90955940Sbostic 	bp->b_flags &= ~(B_DONE | B_CALL | B_ERROR | B_READ | B_DELWRI);
91053574Sheideman 	vop_strategy_a.a_desc = VDESC(vop_strategy);
91153574Sheideman 	vop_strategy_a.a_bp = bp;
91256069Sbostic 	s = splbio();
91356069Sbostic 	bp->b_vp->v_numoutput += 2;
91456069Sbostic 	splx(s);
91553574Sheideman 	(strategy)(&vop_strategy_a);
91651215Sbostic 	biowait(bp);
91751342Sbostic 
91851356Sbostic 	/* Write the second superblock (don't wait). */
91951215Sbostic 	bp->b_blkno = bp->b_lblkno = fs->lfs_sboffs[1];
92055940Sbostic 	bp->b_flags |= B_CALL | B_ASYNC | B_BUSY;
92151860Sbostic 	bp->b_flags &= ~(B_DONE | B_ERROR | B_READ | B_DELWRI);
92255940Sbostic 	bp->b_iodone = lfs_supercallback;
92353574Sheideman 	(strategy)(&vop_strategy_a);
92451215Sbostic }
92551215Sbostic 
92651342Sbostic /*
92751342Sbostic  * Logical block number match routines used when traversing the dirty block
92851342Sbostic  * chain.
92951342Sbostic  */
93052077Sbostic int
93152077Sbostic lfs_match_data(fs, bp)
93251860Sbostic 	struct lfs *fs;
93352085Sbostic 	struct buf *bp;
93451215Sbostic {
93551342Sbostic 	return (bp->b_lblkno >= 0);
93651215Sbostic }
93751215Sbostic 
93852077Sbostic int
93952077Sbostic lfs_match_indir(fs, bp)
94051860Sbostic 	struct lfs *fs;
94152085Sbostic 	struct buf *bp;
94251215Sbostic {
94351860Sbostic 	int lbn;
94451860Sbostic 
94551860Sbostic 	lbn = bp->b_lblkno;
94651860Sbostic 	return (lbn < 0 && (-lbn - NDADDR) % NINDIR(fs) == 0);
94751215Sbostic }
94851215Sbostic 
94952077Sbostic int
95052077Sbostic lfs_match_dindir(fs, bp)
95151860Sbostic 	struct lfs *fs;
95252085Sbostic 	struct buf *bp;
95351215Sbostic {
95451860Sbostic 	int lbn;
95551860Sbostic 
95651860Sbostic 	lbn = bp->b_lblkno;
95751860Sbostic 	return (lbn < 0 && (-lbn - NDADDR) % NINDIR(fs) == 1);
95851215Sbostic }
95951215Sbostic 
96052077Sbostic int
96152077Sbostic lfs_match_tindir(fs, bp)
96251499Sbostic 	struct lfs *fs;
96352085Sbostic 	struct buf *bp;
96451342Sbostic {
96551860Sbostic 	int lbn;
96651342Sbostic 
96751860Sbostic 	lbn = bp->b_lblkno;
96851860Sbostic 	return (lbn < 0 && (-lbn - NDADDR) % NINDIR(fs) == 2);
96951860Sbostic }
97051342Sbostic 
97151860Sbostic /*
97251860Sbostic  * Allocate a new buffer header.
97351860Sbostic  */
97452085Sbostic struct buf *
97555940Sbostic lfs_newbuf(vp, daddr, size)
97655940Sbostic 	struct vnode *vp;
97751860Sbostic 	daddr_t daddr;
97851860Sbostic 	size_t size;
97951860Sbostic {
98052085Sbostic 	struct buf *bp;
98155940Sbostic 	size_t nbytes;
98251342Sbostic 
98355940Sbostic 	nbytes = roundup(size, DEV_BSIZE);
98455940Sbostic 	bp = malloc(sizeof(struct buf) + nbytes, M_SEGMENT, M_WAITOK);
98556069Sbostic 	bzero(bp, sizeof(struct buf) + nbytes);
98655940Sbostic 	bgetvp(vp, bp);
98755940Sbostic 	bp->b_un.b_addr = (caddr_t)(bp + 1);
98855940Sbostic 	bp->b_bufsize = size;
98955940Sbostic 	bp->b_bcount = size;
99051860Sbostic 	bp->b_lblkno = daddr;
99151860Sbostic 	bp->b_blkno = daddr;
99251860Sbostic 	bp->b_error = 0;
99351860Sbostic 	bp->b_resid = 0;
99455940Sbostic 	bp->b_iodone = lfs_callback;
99556027Sbostic 	bp->b_flags |= B_BUSY | B_CALL | B_NOCACHE;
99651860Sbostic 	return (bp);
99751860Sbostic }
99851342Sbostic 
99953347Sbostic void
100051860Sbostic lfs_callback(bp)
100152085Sbostic 	struct buf *bp;
100251860Sbostic {
100351860Sbostic 	struct lfs *fs;
100451342Sbostic 
100556056Sbostic 	fs = (struct lfs *)bp->b_saveaddr;
100651860Sbostic #ifdef DIAGNOSTIC
100751860Sbostic 	if (fs->lfs_iocount == 0)
100851860Sbostic 		panic("lfs_callback: zero iocount\n");
100951860Sbostic #endif
101051860Sbostic 	if (--fs->lfs_iocount == 0)
101152688Sbostic 		wakeup(&fs->lfs_iocount);
101251915Sbostic 
101355940Sbostic 	brelvp(bp);
101455940Sbostic 	free(bp, M_SEGMENT);
101551860Sbostic }
101651342Sbostic 
101755940Sbostic void
101855940Sbostic lfs_supercallback(bp)
101955940Sbostic 	struct buf *bp;
102055940Sbostic {
102155940Sbostic 	brelvp(bp);
102255940Sbostic 	free(bp, M_SEGMENT);
102355940Sbostic }
102455940Sbostic 
102551215Sbostic /*
102651188Sbostic  * Shellsort (diminishing increment sort) from Data Structures and
102751188Sbostic  * Algorithms, Aho, Hopcraft and Ullman, 1983 Edition, page 290;
102851188Sbostic  * see also Knuth Vol. 3, page 84.  The increments are selected from
102951188Sbostic  * formula (8), page 95.  Roughly O(N^3/2).
103051188Sbostic  */
103151188Sbostic /*
103251188Sbostic  * This is our own private copy of shellsort because we want to sort
103351188Sbostic  * two parallel arrays (the array of buffer pointers and the array of
103451188Sbostic  * logical block numbers) simultaneously.  Note that we cast the array
103551188Sbostic  * of logical block numbers to a unsigned in this routine so that the
103651188Sbostic  * negative block numbers (meta data blocks) sort AFTER the data blocks.
103751188Sbostic  */
103852077Sbostic void
103952077Sbostic lfs_shellsort(bp_array, lb_array, nmemb)
104052085Sbostic 	struct buf **bp_array;
104151215Sbostic 	daddr_t *lb_array;
104251188Sbostic 	register int nmemb;
104351188Sbostic {
104451188Sbostic 	static int __rsshell_increments[] = { 4, 1, 0 };
104551188Sbostic 	register int incr, *incrp, t1, t2;
104652085Sbostic 	struct buf *bp_temp;
104751188Sbostic 	u_long lb_temp;
104851188Sbostic 
104951188Sbostic 	for (incrp = __rsshell_increments; incr = *incrp++;)
105051188Sbostic 		for (t1 = incr; t1 < nmemb; ++t1)
105151188Sbostic 			for (t2 = t1 - incr; t2 >= 0;)
105251188Sbostic 				if (lb_array[t2] > lb_array[t2 + incr]) {
105351188Sbostic 					lb_temp = lb_array[t2];
105451188Sbostic 					lb_array[t2] = lb_array[t2 + incr];
105551188Sbostic 					lb_array[t2 + incr] = lb_temp;
105651188Sbostic 					bp_temp = bp_array[t2];
105751188Sbostic 					bp_array[t2] = bp_array[t2 + incr];
105851188Sbostic 					bp_array[t2 + incr] = bp_temp;
105951188Sbostic 					t2 -= incr;
106051188Sbostic 				} else
106151188Sbostic 					break;
106251188Sbostic }
106355940Sbostic 
1064