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