-/*
- * Copyright (c) 1982, 1986 Regents of the University of California.
- * All rights reserved. The Berkeley software License Agreement
- * specifies the terms and conditions for redistribution.
+/*-
+ * Copyright (c) 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * %sccs.include.redist.c%
*
- * @(#)vfs_cluster.c 7.3 (Berkeley) %G%
+ * @(#)vfs_cluster.c 8.10 (Berkeley) %G%
*/
-#include "../machine/pte.h"
-
-#include "param.h"
-#include "systm.h"
-#include "dir.h"
-#include "user.h"
-#include "buf.h"
-#include "conf.h"
-#include "proc.h"
-#include "seg.h"
-#include "vm.h"
-#include "trace.h"
+#include <sys/param.h>
+#include <sys/proc.h>
+#include <sys/buf.h>
+#include <sys/vnode.h>
+#include <sys/mount.h>
+#include <sys/trace.h>
+#include <sys/malloc.h>
+#include <sys/resourcevar.h>
+#include <libkern/libkern.h>
+#include <ufs/ufs/quota.h>
+#include <ufs/ufs/inode.h>
/*
- * Read in (if necessary) the block and return a buffer pointer.
+ * Local declarations
*/
-struct buf *
-#ifdef SECSIZE
-bread(dev, blkno, size, secsize)
-#else SECSIZE
-bread(dev, blkno, size)
-#endif SECSIZE
- dev_t dev;
- daddr_t blkno;
- int size;
-#ifdef SECSIZE
- long secsize;
-#endif SECSIZE
-{
- register struct buf *bp;
-
- if (size == 0)
- panic("bread: size 0");
-#ifdef SECSIZE
- bp = getblk(dev, blkno, size, secsize);
-#else SECSIZE
- bp = getblk(dev, blkno, size);
-#endif SECSIZE
- if (bp->b_flags&(B_DONE|B_DELWRI)) {
- trace(TR_BREADHIT, pack(dev, size), blkno);
- return (bp);
- }
- bp->b_flags |= B_READ;
- if (bp->b_bcount > bp->b_bufsize)
- panic("bread");
- (*bdevsw[major(dev)].d_strategy)(bp);
- trace(TR_BREADMISS, pack(dev, size), blkno);
- u.u_ru.ru_inblock++; /* pay for read */
- biowait(bp);
- return (bp);
-}
+struct buf *cluster_newbuf __P((struct vnode *, struct buf *, long, daddr_t,
+ daddr_t, long, int));
+struct buf *cluster_rbuild __P((struct vnode *, u_quad_t, struct buf *,
+ daddr_t, daddr_t, long, int, long));
+void cluster_wbuild __P((struct vnode *, struct buf *, long,
+ daddr_t, int, daddr_t));
+struct cluster_save *cluster_collectbufs __P((struct vnode *, struct buf *));
+
+#ifdef DIAGNOSTIC
+/*
+ * Set to 1 if reads of block zero should cause readahead to be done.
+ * Set to 0 treats a read of block zero as a non-sequential read.
+ *
+ * Setting to one assumes that most reads of block zero of files are due to
+ * sequential passes over the files (e.g. cat, sum) where additional blocks
+ * will soon be needed. Setting to zero assumes that the majority are
+ * surgical strikes to get particular info (e.g. size, file) where readahead
+ * blocks will not be used and, in fact, push out other potentially useful
+ * blocks from the cache. The former seems intuitive, but some quick tests
+ * showed that the latter performed better from a system-wide point of view.
+ */
+int doclusterraz = 0;
+#define ISSEQREAD(vp, blk) \
+ (((blk) != 0 || doclusterraz) && \
+ ((blk) == (vp)->v_lastr + 1 || (blk) == (vp)->v_lastr))
+#else
+#define ISSEQREAD(vp, blk) \
+ ((blk) != 0 && ((blk) == (vp)->v_lastr + 1 || (blk) == (vp)->v_lastr))
+#endif
/*
- * Read in the block, like bread, but also start I/O on the
- * read-ahead block (which is not allocated to the caller)
+ * This replaces bread. If this is a bread at the beginning of a file and
+ * lastr is 0, we assume this is the first read and we'll read up to two
+ * blocks if they are sequential. After that, we'll do regular read ahead
+ * in clustered chunks.
+ *
+ * There are 4 or 5 cases depending on how you count:
+ * Desired block is in the cache:
+ * 1 Not sequential access (0 I/Os).
+ * 2 Access is sequential, do read-ahead (1 ASYNC).
+ * Desired block is not in cache:
+ * 3 Not sequential access (1 SYNC).
+ * 4 Sequential access, next block is contiguous (1 SYNC).
+ * 5 Sequential access, next block is not contiguous (1 SYNC, 1 ASYNC)
+ *
+ * There are potentially two buffers that require I/O.
+ * bp is the block requested.
+ * rbp is the read-ahead block.
+ * If either is NULL, then you don't have to do the I/O.
*/
-struct buf *
-#ifdef SECSIZE
-breada(dev, blkno, size, secsize, rablkno, rabsize)
-#else SECSIZE
-breada(dev, blkno, size, rablkno, rabsize)
-#endif SECSIZE
- dev_t dev;
- daddr_t blkno; int size;
-#ifdef SECSIZE
- long secsize;
-#endif SECSIZE
- daddr_t rablkno; int rabsize;
+cluster_read(vp, filesize, lblkno, size, cred, bpp)
+ struct vnode *vp;
+ u_quad_t filesize;
+ daddr_t lblkno;
+ long size;
+ struct ucred *cred;
+ struct buf **bpp;
{
- register struct buf *bp, *rabp;
+ struct buf *bp, *rbp;
+ daddr_t blkno, ioblkno;
+ long flags;
+ int error, num_ra, alreadyincore;
- bp = NULL;
- /*
- * If the block isn't in core, then allocate
- * a buffer and initiate i/o (getblk checks
- * for a cache hit).
- */
- if (!incore(dev, blkno)) {
-#ifdef SECSIZE
- bp = getblk(dev, blkno, size, secsize);
-#else SECSIZE
- bp = getblk(dev, blkno, size);
-#endif SECSIZE
- if ((bp->b_flags&(B_DONE|B_DELWRI)) == 0) {
- bp->b_flags |= B_READ;
- if (bp->b_bcount > bp->b_bufsize)
- panic("breada");
- (*bdevsw[major(dev)].d_strategy)(bp);
- trace(TR_BREADMISS, pack(dev, size), blkno);
- u.u_ru.ru_inblock++; /* pay for read */
- } else
- trace(TR_BREADHIT, pack(dev, size), blkno);
+#ifdef DIAGNOSTIC
+ if (size == 0)
+ panic("cluster_read: size = 0");
+#endif
+
+ error = 0;
+ flags = B_READ;
+ *bpp = bp = getblk(vp, lblkno, size, 0, 0);
+ if (bp->b_flags & B_CACHE) {
+ /*
+ * Desired block is in cache; do any readahead ASYNC.
+ * Case 1, 2.
+ */
+ trace(TR_BREADHIT, pack(vp, size), lblkno);
+ flags |= B_ASYNC;
+ ioblkno = lblkno + (vp->v_ralen ? vp->v_ralen : 1);
+ alreadyincore = incore(vp, ioblkno) != NULL;
+ bp = NULL;
+ } else {
+ /* Block wasn't in cache, case 3, 4, 5. */
+ trace(TR_BREADMISS, pack(vp, size), lblkno);
+ bp->b_flags |= B_READ;
+ ioblkno = lblkno;
+ alreadyincore = 0;
+ curproc->p_stats->p_ru.ru_inblock++; /* XXX */
}
-
/*
- * If there's a read-ahead block, start i/o
- * on it also (as above).
+ * XXX
+ * Replace 1 with a window size based on some permutation of
+ * maxcontig and rot_delay. This will let you figure out how
+ * many blocks you should read-ahead (case 2, 4, 5).
+ *
+ * If the access isn't sequential, reset the window to 1.
+ * Note that a read to the same block is considered sequential.
+ * This catches the case where the file is being read sequentially,
+ * but at smaller than the filesystem block size.
*/
- if (rablkno && !incore(dev, rablkno)) {
-#ifdef SECSIZE
- rabp = getblk(dev, rablkno, rabsize, secsize);
-#else SECSIZE
- rabp = getblk(dev, rablkno, rabsize);
-#endif SECSIZE
- if (rabp->b_flags & (B_DONE|B_DELWRI)) {
- brelse(rabp);
- trace(TR_BREADHITRA, pack(dev, rabsize), blkno);
+ rbp = NULL;
+ if (!ISSEQREAD(vp, lblkno)) {
+ vp->v_ralen = 0;
+ vp->v_maxra = lblkno;
+ } else if ((ioblkno + 1) * size <= filesize && !alreadyincore &&
+ !(error = VOP_BMAP(vp, ioblkno, NULL, &blkno, &num_ra)) &&
+ blkno != -1) {
+ /*
+ * Reading sequentially, and the next block is not in the
+ * cache. We are going to try reading ahead.
+ */
+ if (num_ra) {
+ /*
+ * If our desired readahead block had been read
+ * in a previous readahead but is no longer in
+ * core, then we may be reading ahead too far
+ * or are not using our readahead very rapidly.
+ * In this case we scale back the window.
+ */
+ if (!alreadyincore && ioblkno <= vp->v_maxra)
+ vp->v_ralen = max(vp->v_ralen >> 1, 1);
+ /*
+ * There are more sequential blocks than our current
+ * window allows, scale up. Ideally we want to get
+ * in sync with the filesystem maxcontig value.
+ */
+ else if (num_ra > vp->v_ralen && lblkno != vp->v_lastr)
+ vp->v_ralen = vp->v_ralen ?
+ min(num_ra, vp->v_ralen << 1) : 1;
+
+ if (num_ra > vp->v_ralen)
+ num_ra = vp->v_ralen;
+ }
+
+ if (num_ra) /* case 2, 4 */
+ rbp = cluster_rbuild(vp, filesize,
+ bp, ioblkno, blkno, size, num_ra, flags);
+ else if (ioblkno == lblkno) {
+ bp->b_blkno = blkno;
+ /* Case 5: check how many blocks to read ahead */
+ ++ioblkno;
+ if ((ioblkno + 1) * size > filesize ||
+ incore(vp, ioblkno) || (error = VOP_BMAP(vp,
+ ioblkno, NULL, &blkno, &num_ra)) || blkno == -1)
+ goto skip_readahead;
+ /*
+ * Adjust readahead as above.
+ * Don't check alreadyincore, we know it is 0 from
+ * the previous conditional.
+ */
+ if (num_ra) {
+ if (ioblkno <= vp->v_maxra)
+ vp->v_ralen = max(vp->v_ralen >> 1, 1);
+ else if (num_ra > vp->v_ralen &&
+ lblkno != vp->v_lastr)
+ vp->v_ralen = vp->v_ralen ?
+ min(num_ra,vp->v_ralen<<1) : 1;
+ if (num_ra > vp->v_ralen)
+ num_ra = vp->v_ralen;
+ }
+ flags |= B_ASYNC;
+ if (num_ra)
+ rbp = cluster_rbuild(vp, filesize,
+ NULL, ioblkno, blkno, size, num_ra, flags);
+ else {
+ rbp = getblk(vp, ioblkno, size, 0, 0);
+ rbp->b_flags |= flags;
+ rbp->b_blkno = blkno;
+ }
} else {
- rabp->b_flags |= B_READ|B_ASYNC;
- if (rabp->b_bcount > rabp->b_bufsize)
- panic("breadrabp");
- (*bdevsw[major(dev)].d_strategy)(rabp);
- trace(TR_BREADMISSRA, pack(dev, rabsize), rablock);
- u.u_ru.ru_inblock++; /* pay in advance */
+ /* case 2; read ahead single block */
+ rbp = getblk(vp, ioblkno, size, 0, 0);
+ rbp->b_flags |= flags;
+ rbp->b_blkno = blkno;
+ }
+
+ if (rbp == bp) /* case 4 */
+ rbp = NULL;
+ else if (rbp) { /* case 2, 5 */
+ trace(TR_BREADMISSRA,
+ pack(vp, (num_ra + 1) * size), ioblkno);
+ curproc->p_stats->p_ru.ru_inblock++; /* XXX */
}
}
+ /* XXX Kirk, do we need to make sure the bp has creds? */
+skip_readahead:
+ if (bp)
+ if (bp->b_flags & (B_DONE | B_DELWRI))
+ panic("cluster_read: DONE bp");
+ else
+ error = VOP_STRATEGY(bp);
+
+ if (rbp)
+ if (error || rbp->b_flags & (B_DONE | B_DELWRI)) {
+ rbp->b_flags &= ~(B_ASYNC | B_READ);
+ brelse(rbp);
+ } else
+ (void) VOP_STRATEGY(rbp);
+
/*
- * If block was in core, let bread get it.
- * If block wasn't in core, then the read was started
- * above, and just wait for it.
+ * Recalculate our maximum readahead
*/
- if (bp == NULL)
-#ifdef SECSIZE
- return (bread(dev, blkno, size, secsize));
-#else SECSIZE
- return (bread(dev, blkno, size));
-#endif SECSIZE
- biowait(bp);
- return (bp);
+ if (rbp == NULL)
+ rbp = bp;
+ if (rbp)
+ vp->v_maxra = rbp->b_lblkno + (rbp->b_bufsize / size) - 1;
+
+ if (bp)
+ return(biowait(bp));
+ return(error);
}
/*
- * Write the buffer, waiting for completion.
- * Then release the buffer.
+ * If blocks are contiguous on disk, use this to provide clustered
+ * read ahead. We will read as many blocks as possible sequentially
+ * and then parcel them up into logical blocks in the buffer hash table.
*/
-bwrite(bp)
- register struct buf *bp;
+struct buf *
+cluster_rbuild(vp, filesize, bp, lbn, blkno, size, run, flags)
+ struct vnode *vp;
+ u_quad_t filesize;
+ struct buf *bp;
+ daddr_t lbn;
+ daddr_t blkno;
+ long size;
+ int run;
+ long flags;
{
- register flag;
+ struct cluster_save *b_save;
+ struct buf *tbp;
+ daddr_t bn;
+ int i, inc;
+
+#ifdef DIAGNOSTIC
+ if (size != vp->v_mount->mnt_stat.f_iosize)
+ panic("cluster_rbuild: size %d != filesize %d\n",
+ size, vp->v_mount->mnt_stat.f_iosize);
+#endif
+ if (size * (lbn + run + 1) > filesize)
+ --run;
+ if (run == 0) {
+ if (!bp) {
+ bp = getblk(vp, lbn, size, 0, 0);
+ bp->b_blkno = blkno;
+ bp->b_flags |= flags;
+ }
+ return(bp);
+ }
- flag = bp->b_flags;
- bp->b_flags &= ~(B_READ | B_DONE | B_ERROR | B_DELWRI);
- if ((flag&B_DELWRI) == 0)
- u.u_ru.ru_oublock++; /* noone paid yet */
- trace(TR_BWRITE, pack(bp->b_dev, bp->b_bcount), bp->b_blkno);
- if (bp->b_bcount > bp->b_bufsize)
- panic("bwrite");
- (*bdevsw[major(bp->b_dev)].d_strategy)(bp);
+ bp = cluster_newbuf(vp, bp, flags, blkno, lbn, size, run + 1);
+ if (bp->b_flags & (B_DONE | B_DELWRI))
+ return (bp);
+ b_save = malloc(sizeof(struct buf *) * run + sizeof(struct cluster_save),
+ M_SEGMENT, M_WAITOK);
+ b_save->bs_bufsize = b_save->bs_bcount = size;
+ b_save->bs_nchildren = 0;
+ b_save->bs_children = (struct buf **)(b_save + 1);
+ b_save->bs_saveaddr = bp->b_saveaddr;
+ bp->b_saveaddr = (caddr_t) b_save;
+
+ inc = btodb(size);
+ for (bn = blkno + inc, i = 1; i <= run; ++i, bn += inc) {
+ /*
+ * A component of the cluster is already in core,
+ * terminate the cluster early.
+ */
+ if (incore(vp, lbn + i))
+ break;
+ tbp = getblk(vp, lbn + i, 0, 0, 0);
+ /*
+ * getblk may return some memory in the buffer if there were
+ * no empty buffers to shed it to. If there is currently
+ * memory in the buffer, we move it down size bytes to make
+ * room for the valid pages that cluster_callback will insert.
+ * We do this now so we don't have to do it at interrupt time
+ * in the callback routine.
+ */
+ if (tbp->b_bufsize != 0) {
+ caddr_t bdata = (char *)tbp->b_data;
+
+ /*
+ * No room in the buffer to add another page,
+ * terminate the cluster early.
+ */
+ if (tbp->b_bufsize + size > MAXBSIZE) {
+#ifdef DIAGNOSTIC
+ if (tbp->b_bufsize != MAXBSIZE)
+ panic("cluster_rbuild: too much memory");
+#endif
+ brelse(tbp);
+ break;
+ }
+ if (tbp->b_bufsize > size) {
+ /*
+ * XXX if the source and destination regions
+ * overlap we have to copy backward to avoid
+ * clobbering any valid pages (i.e. pagemove
+ * implementations typically can't handle
+ * overlap).
+ */
+ bdata += tbp->b_bufsize;
+ while (bdata > (char *)tbp->b_data) {
+ bdata -= CLBYTES;
+ pagemove(bdata, bdata + size, CLBYTES);
+ }
+ } else
+ pagemove(bdata, bdata + size, tbp->b_bufsize);
+ }
+ tbp->b_blkno = bn;
+ {
+ daddr_t temp;
+ VOP_BMAP(tbp->b_vp, tbp->b_lblkno, NULL, &temp, NULL);
+ if (temp != bn) {
+ printf("Block: %d Assigned address: %x Bmap address: %x\n",
+ tbp->b_lblkno, tbp->b_blkno, temp);
+ panic("cluster_rbuild: wrong disk address");
+ }
+ }
+ tbp->b_flags |= flags | B_READ | B_ASYNC;
+ ++b_save->bs_nchildren;
+ b_save->bs_children[i - 1] = tbp;
+ }
/*
- * If the write was synchronous, then await i/o completion.
- * If the write was "delayed", then we put the buffer on
- * the q of blocks awaiting i/o completion status.
+ * The cluster may have been terminated early, adjust the cluster
+ * buffer size accordingly. If no cluster could be formed,
+ * deallocate the cluster save info.
*/
- if ((flag&B_ASYNC) == 0) {
- biowait(bp);
- brelse(bp);
- } else if (flag & B_DELWRI)
- bp->b_flags |= B_AGE;
+ if (i <= run) {
+ if (i == 1) {
+ bp->b_saveaddr = b_save->bs_saveaddr;
+ bp->b_flags &= ~B_CALL;
+ bp->b_iodone = NULL;
+ free(b_save, M_SEGMENT);
+ }
+ allocbuf(bp, size * i);
+ }
+ return(bp);
}
/*
- * Release the buffer, marking it so that if it is grabbed
- * for another purpose it will be written out before being
- * given up (e.g. when writing a partial block where it is
- * assumed that another write for the same block will soon follow).
- * This can't be done for magtape, since writes must be done
- * in the same order as requested.
+ * Either get a new buffer or grow the existing one.
*/
-bdwrite(bp)
- register struct buf *bp;
+struct buf *
+cluster_newbuf(vp, bp, flags, blkno, lblkno, size, run)
+ struct vnode *vp;
+ struct buf *bp;
+ long flags;
+ daddr_t blkno;
+ daddr_t lblkno;
+ long size;
+ int run;
{
-
- if ((bp->b_flags&B_DELWRI) == 0)
- u.u_ru.ru_oublock++; /* noone paid yet */
- if (bdevsw[major(bp->b_dev)].d_flags & B_TAPE)
- bawrite(bp);
- else {
- bp->b_flags |= B_DELWRI | B_DONE;
- brelse(bp);
+ if (!bp) {
+ bp = getblk(vp, lblkno, size, 0, 0);
+ if (bp->b_flags & (B_DONE | B_DELWRI)) {
+ bp->b_blkno = blkno;
+ return(bp);
+ }
}
+ allocbuf(bp, run * size);
+ bp->b_blkno = blkno;
+ bp->b_iodone = cluster_callback;
+ bp->b_flags |= flags | B_CALL;
+ return(bp);
}
/*
- * Release the buffer, start I/O on it, but don't wait for completion.
+ * Cleanup after a clustered read or write.
+ * This is complicated by the fact that any of the buffers might have
+ * extra memory (if there were no empty buffer headers at allocbuf time)
+ * that we will need to shift around.
*/
-bawrite(bp)
- register struct buf *bp;
+void
+cluster_callback(bp)
+ struct buf *bp;
{
+ struct cluster_save *b_save;
+ struct buf **bpp, *tbp;
+ long bsize;
+ caddr_t cp;
+ int error = 0;
- bp->b_flags |= B_ASYNC;
- bwrite(bp);
-}
+ /*
+ * Must propogate errors to all the components.
+ */
+ if (bp->b_flags & B_ERROR)
+ error = bp->b_error;
-/*
- * Release the buffer, with no I/O implied.
- */
-brelse(bp)
- register struct buf *bp;
-{
- register struct buf *flist;
- register s;
+ daddr_t daddr;
+ b_save = (struct cluster_save *)(bp->b_saveaddr);
+ bp->b_saveaddr = b_save->bs_saveaddr;
- trace(TR_BRELSE, pack(bp->b_dev, bp->b_bufsize), bp->b_blkno);
+ bsize = b_save->bs_bufsize;
+ cp = (char *)bp->b_data + bsize;
/*
- * If someone's waiting for the buffer, or
- * is waiting for a buffer wake 'em up.
+ * Move memory from the large cluster buffer into the component
+ * buffers and mark IO as done on these.
*/
- if (bp->b_flags&B_WANTED)
- wakeup((caddr_t)bp);
- if (bfreelist[0].b_flags&B_WANTED) {
- bfreelist[0].b_flags &= ~B_WANTED;
- wakeup((caddr_t)bfreelist);
+ for (bpp = b_save->bs_children; b_save->bs_nchildren--; ++bpp) {
+ tbp = *bpp;
+ pagemove(cp, tbp->b_data, bsize);
+ tbp->b_bufsize += bsize;
+ tbp->b_bcount = bsize;
+ if (error) {
+ tbp->b_flags |= B_ERROR;
+ tbp->b_error = error;
+ }
+ biodone(tbp);
+ bp->b_bufsize -= bsize;
+ cp += bsize;
}
- if (bp->b_flags&B_ERROR)
- if (bp->b_flags & B_LOCKED)
- bp->b_flags &= ~B_ERROR; /* try again later */
- else
- bp->b_dev = NODEV; /* no assoc */
-
/*
- * Stick the buffer back on a free list.
+ * If there was excess memory in the cluster buffer,
+ * slide it up adjacent to the remaining valid data.
*/
- s = splbio();
- if (bp->b_bufsize <= 0) {
- /* block has no buffer ... put at front of unused buffer list */
- flist = &bfreelist[BQ_EMPTY];
- binsheadfree(bp, flist);
- } else if (bp->b_flags & (B_ERROR|B_INVAL)) {
- /* block has no info ... put at front of most free list */
- flist = &bfreelist[BQ_AGE];
- binsheadfree(bp, flist);
- } else {
- if (bp->b_flags & B_LOCKED)
- flist = &bfreelist[BQ_LOCKED];
- else if (bp->b_flags & B_AGE)
- flist = &bfreelist[BQ_AGE];
- else
- flist = &bfreelist[BQ_LRU];
- binstailfree(bp, flist);
+ if (bp->b_bufsize != bsize) {
+ if (bp->b_bufsize < bsize)
+ panic("cluster_callback: too little memory");
+ pagemove(cp, (char *)bp->b_data + bsize, bp->b_bufsize - bsize);
+ }
+ bp->b_bcount = bsize;
+ bp->b_iodone = NULL;
+ free(b_save, M_SEGMENT);
+ if (bp->b_flags & B_ASYNC)
+ brelse(bp);
+ else {
+ bp->b_flags &= ~B_WANTED;
+ wakeup((caddr_t)bp);
}
- bp->b_flags &= ~(B_WANTED|B_BUSY|B_ASYNC|B_AGE);
- splx(s);
-}
-
-/*
- * See if the block is associated with some buffer
- * (mainly to avoid getting hung up on a wait in breada)
- */
-incore(dev, blkno)
- dev_t dev;
- daddr_t blkno;
-{
- register struct buf *bp;
- register struct buf *dp;
-
- dp = BUFHASH(dev, blkno);
- for (bp = dp->b_forw; bp != dp; bp = bp->b_forw)
- if (bp->b_blkno == blkno && bp->b_dev == dev &&
- (bp->b_flags & B_INVAL) == 0)
- return (1);
- return (0);
-}
-
-struct buf *
-#ifdef SECSIZE
-baddr(dev, blkno, size, secsize)
-#else SECSIZE
-baddr(dev, blkno, size)
-#endif SECSIZE
- dev_t dev;
- daddr_t blkno;
- int size;
-#ifdef SECSIZE
- long secsize;
-#endif SECSIZE
-{
-
- if (incore(dev, blkno))
-#ifdef SECSIZE
- return (bread(dev, blkno, size, secsize));
-#else SECSIZE
- return (bread(dev, blkno, size));
-#endif SECSIZE
- return (0);
}
/*
- * Assign a buffer for the given block. If the appropriate
- * block is already associated, return it; otherwise search
- * for the oldest non-busy buffer and reassign it.
+ * Do clustered write for FFS.
*
- * If we find the buffer, but it is dirty (marked DELWRI) and
- * its size is changing, we must write it out first. When the
- * buffer is shrinking, the write is done by brealloc to avoid
- * losing the unwritten data. When the buffer is growing, the
- * write is done by getblk, so that bread will not read stale
- * disk data over the modified data in the buffer.
- *
- * We use splx here because this routine may be called
- * on the interrupt stack during a dump, and we don't
- * want to lower the ipl back to 0.
+ * Three cases:
+ * 1. Write is not sequential (write asynchronously)
+ * Write is sequential:
+ * 2. beginning of cluster - begin cluster
+ * 3. middle of a cluster - add to cluster
+ * 4. end of a cluster - asynchronously write cluster
*/
-struct buf *
-#ifdef SECSIZE
-getblk(dev, blkno, size, secsize)
-#else SECSIZE
-getblk(dev, blkno, size)
-#endif SECSIZE
- dev_t dev;
- daddr_t blkno;
- int size;
-#ifdef SECSIZE
- long secsize;
-#endif SECSIZE
+void
+cluster_write(bp, filesize)
+ struct buf *bp;
+ u_quad_t filesize;
{
- register struct buf *bp, *dp;
- int s;
-
- if (size > MAXBSIZE)
- panic("getblk: size too big");
- /*
- * To prevent overflow of 32-bit ints when converting block
- * numbers to byte offsets, blknos > 2^32 / DEV_BSIZE are set
- * to the maximum number that can be converted to a byte offset
- * without overflow. This is historic code; what bug it fixed,
- * or whether it is still a reasonable thing to do is open to
- * dispute. mkm 9/85
- */
- if ((unsigned)blkno >= 1 << (sizeof(int)*NBBY-DEV_BSHIFT))
- blkno = 1 << ((sizeof(int)*NBBY-DEV_BSHIFT) + 1);
- /*
- * Search the cache for the block. If we hit, but
- * the buffer is in use for i/o, then we wait until
- * the i/o has completed.
- */
- dp = BUFHASH(dev, blkno);
-loop:
- for (bp = dp->b_forw; bp != dp; bp = bp->b_forw) {
- if (bp->b_blkno != blkno || bp->b_dev != dev ||
- bp->b_flags&B_INVAL)
- continue;
- s = splbio();
- if (bp->b_flags&B_BUSY) {
- bp->b_flags |= B_WANTED;
- sleep((caddr_t)bp, PRIBIO+1);
- splx(s);
- goto loop;
- }
- splx(s);
- notavail(bp);
- if (bp->b_bcount != size) {
- if (bp->b_bcount < size && (bp->b_flags&B_DELWRI)) {
- bp->b_flags &= ~B_ASYNC;
- bwrite(bp);
- goto loop;
+ struct vnode *vp;
+ daddr_t lbn;
+ int maxclen, cursize;
+
+ vp = bp->b_vp;
+ lbn = bp->b_lblkno;
+
+ /* Initialize vnode to beginning of file. */
+ if (lbn == 0)
+ vp->v_lasta = vp->v_clen = vp->v_cstart = vp->v_lastw = 0;
+
+ if (vp->v_clen == 0 || lbn != vp->v_lastw + 1 ||
+ (bp->b_blkno != vp->v_lasta + btodb(bp->b_bcount))) {
+ maxclen = MAXBSIZE / vp->v_mount->mnt_stat.f_iosize - 1;
+ if (vp->v_clen != 0) {
+ /*
+ * Next block is not sequential.
+ *
+ * If we are not writing at end of file, the process
+ * seeked to another point in the file since its
+ * last write, or we have reached our maximum
+ * cluster size, then push the previous cluster.
+ * Otherwise try reallocating to make it sequential.
+ */
+ cursize = vp->v_lastw - vp->v_cstart + 1;
+ if ((lbn + 1) * bp->b_bcount != filesize ||
+ lbn != vp->v_lastw + 1 || vp->v_clen <= cursize) {
+ cluster_wbuild(vp, NULL, bp->b_bcount,
+ vp->v_cstart, cursize, lbn);
+ } else {
+ struct buf **bpp, **endbp;
+ struct cluster_save *buflist;
+
+ buflist = cluster_collectbufs(vp, bp);
+ endbp = &buflist->bs_children
+ [buflist->bs_nchildren - 1];
+ if (VOP_REALLOCBLKS(vp, buflist)) {
+ /*
+ * Failed, push the previous cluster.
+ */
+ for (bpp = buflist->bs_children;
+ bpp < endbp; bpp++)
+ brelse(*bpp);
+ free(buflist, M_SEGMENT);
+ cluster_wbuild(vp, NULL, bp->b_bcount,
+ vp->v_cstart, cursize, lbn);
+ } else {
+ /*
+ * Succeeded, keep building cluster.
+ */
+ for (bpp = buflist->bs_children;
+ bpp <= endbp; bpp++)
+ bdwrite(*bpp);
+ free(buflist, M_SEGMENT);
+ vp->v_lastw = lbn;
+ vp->v_lasta = bp->b_blkno;
+ return;
+ }
}
- if (brealloc(bp, size) == 0)
- goto loop;
}
- if (bp->b_bcount != size && brealloc(bp, size) == 0)
- goto loop;
- bp->b_flags |= B_CACHE;
- return (bp);
- }
- if (major(dev) >= nblkdev)
- panic("blkdev");
- bp = getnewbuf();
- bfree(bp);
- bremhash(bp);
- binshash(bp, dp);
- bp->b_dev = dev;
-#ifdef SECSIZE
- bp->b_blksize = secsize;
-#endif SECSIZE
- bp->b_blkno = blkno;
- bp->b_error = 0;
- if (brealloc(bp, size) == 0)
- goto loop;
- return (bp);
+ /*
+ * Consider beginning a cluster.
+ * If at end of file, make cluster as large as possible,
+ * otherwise find size of existing cluster.
+ */
+ if ((lbn + 1) * bp->b_bcount != filesize &&
+ (VOP_BMAP(vp, lbn, NULL, &bp->b_blkno, &maxclen) ||
+ bp->b_blkno == -1)) {
+ bawrite(bp);
+ vp->v_clen = 0;
+ vp->v_lasta = bp->b_blkno;
+ vp->v_cstart = lbn + 1;
+ vp->v_lastw = lbn;
+ return;
+ }
+ vp->v_clen = maxclen;
+ if (maxclen == 0) { /* I/O not contiguous */
+ vp->v_cstart = lbn + 1;
+ bawrite(bp);
+ } else { /* Wait for rest of cluster */
+ vp->v_cstart = lbn;
+ bdwrite(bp);
+ }
+ } else if (lbn == vp->v_cstart + vp->v_clen) {
+ /*
+ * At end of cluster, write it out.
+ */
+ cluster_wbuild(vp, bp, bp->b_bcount, vp->v_cstart,
+ vp->v_clen + 1, lbn);
+ vp->v_clen = 0;
+ vp->v_cstart = lbn + 1;
+ } else
+ /*
+ * In the middle of a cluster, so just delay the
+ * I/O for now.
+ */
+ bdwrite(bp);
+ vp->v_lastw = lbn;
+ vp->v_lasta = bp->b_blkno;
}
-/*
- * get an empty block,
- * not assigned to any particular device
- */
-struct buf *
-geteblk(size)
- int size;
-{
- register struct buf *bp, *flist;
-
- if (size > MAXBSIZE)
- panic("geteblk: size too big");
-loop:
- bp = getnewbuf();
- bp->b_flags |= B_INVAL;
- bfree(bp);
- bremhash(bp);
- flist = &bfreelist[BQ_AGE];
- binshash(bp, flist);
- bp->b_dev = (dev_t)NODEV;
-#ifdef SECSIZE
- bp->b_blksize = DEV_BSIZE;
-#endif SECSIZE
- bp->b_error = 0;
- if (brealloc(bp, size) == 0)
- goto loop;
- return (bp);
-}
/*
- * Allocate space associated with a buffer.
- * If can't get space, buffer is released
+ * This is an awful lot like cluster_rbuild...wish they could be combined.
+ * The last lbn argument is the current block on which I/O is being
+ * performed. Check to see that it doesn't fall in the middle of
+ * the current block (if last_bp == NULL).
*/
-brealloc(bp, size)
- register struct buf *bp;
- int size;
+void
+cluster_wbuild(vp, last_bp, size, start_lbn, len, lbn)
+ struct vnode *vp;
+ struct buf *last_bp;
+ long size;
+ daddr_t start_lbn;
+ int len;
+ daddr_t lbn;
{
- daddr_t start, last;
- register struct buf *ep;
- struct buf *dp;
- int s;
+ struct cluster_save *b_save;
+ struct buf *bp, *tbp;
+ caddr_t cp;
+ int i, s;
+
+#ifdef DIAGNOSTIC
+ if (size != vp->v_mount->mnt_stat.f_iosize)
+ panic("cluster_wbuild: size %d != filesize %d\n",
+ size, vp->v_mount->mnt_stat.f_iosize);
+#endif
+redo:
+ while ((!incore(vp, start_lbn) || start_lbn == lbn) && len) {
+ ++start_lbn;
+ --len;
+ }
- /*
- * First need to make sure that all overlapping previous I/O
- * is dispatched with.
- */
- if (size == bp->b_bcount)
- return (1);
- if (size < bp->b_bcount) {
- if (bp->b_flags & B_DELWRI) {
- bwrite(bp);
- return (0);
+ /* Get more memory for current buffer */
+ if (len <= 1) {
+ if (last_bp) {
+ bawrite(last_bp);
+ } else if (len) {
+ bp = getblk(vp, start_lbn, size, 0, 0);
+ bawrite(bp);
}
- if (bp->b_flags & B_LOCKED)
- panic("brealloc");
- return (allocbuf(bp, size));
+ return;
+ }
+
+ bp = getblk(vp, start_lbn, size, 0, 0);
+ if (!(bp->b_flags & B_DELWRI)) {
+ ++start_lbn;
+ --len;
+ brelse(bp);
+ goto redo;
}
- bp->b_flags &= ~B_DONE;
- if (bp->b_dev == NODEV)
- return (allocbuf(bp, size));
- trace(TR_BREALLOC, pack(bp->b_dev, size), bp->b_blkno);
/*
- * Search cache for any buffers that overlap the one that we
- * are trying to allocate. Overlapping buffers must be marked
- * invalid, after being written out if they are dirty. (indicated
- * by B_DELWRI) A disk block must be mapped by at most one buffer
- * at any point in time. Care must be taken to avoid deadlocking
- * when two buffer are trying to get the same set of disk blocks.
+ * Extra memory in the buffer, punt on this buffer.
+ * XXX we could handle this in most cases, but we would have to
+ * push the extra memory down to after our max possible cluster
+ * size and then potentially pull it back up if the cluster was
+ * terminated prematurely--too much hassle.
*/
- start = bp->b_blkno;
-#ifdef SECSIZE
- last = start + size/bp->b_blksize - 1;
-#else SECSIZE
- last = start + btodb(size) - 1;
-#endif SECSIZE
- dp = BUFHASH(bp->b_dev, bp->b_blkno);
-loop:
- for (ep = dp->b_forw; ep != dp; ep = ep->b_forw) {
- if (ep == bp || ep->b_dev != bp->b_dev || (ep->b_flags&B_INVAL))
- continue;
- /* look for overlap */
- if (ep->b_bcount == 0 || ep->b_blkno > last ||
-#ifdef SECSIZE
- ep->b_blkno + ep->b_bcount/ep->b_blksize <= start)
-#else SECSIZE
- ep->b_blkno + btodb(ep->b_bcount) <= start)
-#endif SECSIZE
- continue;
- s = splbio();
- if (ep->b_flags&B_BUSY) {
- ep->b_flags |= B_WANTED;
- sleep((caddr_t)ep, PRIBIO+1);
- splx(s);
- goto loop;
- }
- splx(s);
- notavail(ep);
- if (ep->b_flags & B_DELWRI) {
- bwrite(ep);
- goto loop;
- }
- ep->b_flags |= B_INVAL;
- brelse(ep);
+ if (bp->b_bcount != bp->b_bufsize) {
+ ++start_lbn;
+ --len;
+ bawrite(bp);
+ goto redo;
}
- return (allocbuf(bp, size));
-}
-/*
- * Find a buffer which is available for use.
- * Select something from a free list.
- * Preference is to AGE list, then LRU list.
- */
-struct buf *
-getnewbuf()
-{
- register struct buf *bp, *dp;
- int s;
-
-loop:
- s = splbio();
- for (dp = &bfreelist[BQ_AGE]; dp > bfreelist; dp--)
- if (dp->av_forw != dp)
+ --len;
+ b_save = malloc(sizeof(struct buf *) * len + sizeof(struct cluster_save),
+ M_SEGMENT, M_WAITOK);
+ b_save->bs_bcount = bp->b_bcount;
+ b_save->bs_bufsize = bp->b_bufsize;
+ b_save->bs_nchildren = 0;
+ b_save->bs_children = (struct buf **)(b_save + 1);
+ b_save->bs_saveaddr = bp->b_saveaddr;
+ bp->b_saveaddr = (caddr_t) b_save;
+
+ bp->b_flags |= B_CALL;
+ bp->b_iodone = cluster_callback;
+ cp = (char *)bp->b_data + size;
+ for (++start_lbn, i = 0; i < len; ++i, ++start_lbn) {
+ /*
+ * Block is not in core or the non-sequential block
+ * ending our cluster was part of the cluster (in which
+ * case we don't want to write it twice).
+ */
+ if (!incore(vp, start_lbn) ||
+ last_bp == NULL && start_lbn == lbn)
break;
- if (dp == bfreelist) { /* no free blocks */
- dp->b_flags |= B_WANTED;
- sleep((caddr_t)dp, PRIBIO+1);
- splx(s);
- goto loop;
- }
- splx(s);
- bp = dp->av_forw;
- notavail(bp);
- if (bp->b_flags & B_DELWRI) {
- bp->b_flags |= B_ASYNC;
- bwrite(bp);
- goto loop;
- }
- trace(TR_BRELSE, pack(bp->b_dev, bp->b_bufsize), bp->b_blkno);
- bp->b_flags = B_BUSY;
- return (bp);
-}
-/*
- * Wait for I/O completion on the buffer; return errors
- * to the user.
- */
-biowait(bp)
- register struct buf *bp;
-{
- int s;
-
- s = splbio();
- while ((bp->b_flags&B_DONE)==0)
- sleep((caddr_t)bp, PRIBIO);
- splx(s);
- if (u.u_error == 0) /* XXX */
- u.u_error = geterror(bp);
-}
+ /*
+ * Get the desired block buffer (unless it is the final
+ * sequential block whose buffer was passed in explictly
+ * as last_bp).
+ */
+ if (last_bp == NULL || start_lbn != lbn) {
+ tbp = getblk(vp, start_lbn, size, 0, 0);
+ if (!(tbp->b_flags & B_DELWRI)) {
+ brelse(tbp);
+ break;
+ }
+ } else
+ tbp = last_bp;
-/*
- * Mark I/O complete on a buffer.
- * If someone should be called, e.g. the pageout
- * daemon, do so. Otherwise, wake up anyone
- * waiting for it.
- */
-biodone(bp)
- register struct buf *bp;
-{
+ ++b_save->bs_nchildren;
- if (bp->b_flags & B_DONE)
- panic("dup biodone");
- bp->b_flags |= B_DONE;
- if (bp->b_flags & B_CALL) {
- bp->b_flags &= ~B_CALL;
- (*bp->b_iodone)(bp);
- return;
- }
- if (bp->b_flags&B_ASYNC)
- brelse(bp);
- else {
- bp->b_flags &= ~B_WANTED;
- wakeup((caddr_t)bp);
- }
-}
+ /* Move memory from children to parent */
+ if (tbp->b_blkno != (bp->b_blkno + btodb(bp->b_bufsize))) {
+ printf("Clustered Block: %d addr %x bufsize: %d\n",
+ bp->b_lblkno, bp->b_blkno, bp->b_bufsize);
+ printf("Child Block: %d addr: %x\n", tbp->b_lblkno,
+ tbp->b_blkno);
+ panic("Clustered write to wrong blocks");
+ }
-/*
- * Insure that no part of a specified block is in an incore buffer.
-#ifdef SECSIZE
- * "size" is given in device blocks (the units of b_blkno).
-#endif SECSIZE
-#ifdef SECSIZE
- * "size" is given in device blocks (the units of b_blkno).
-#endif SECSIZE
- */
-blkflush(dev, blkno, size)
- dev_t dev;
- daddr_t blkno;
-#ifdef SECSIZE
- int size;
-#else SECSIZE
- long size;
-#endif SECSIZE
-{
- register struct buf *ep;
- struct buf *dp;
- daddr_t start, last;
- int s;
-
- start = blkno;
-#ifdef SECSIZE
- last = start + size - 1;
-#else SECSIZE
- last = start + btodb(size) - 1;
-#endif SECSIZE
- dp = BUFHASH(dev, blkno);
-loop:
- for (ep = dp->b_forw; ep != dp; ep = ep->b_forw) {
- if (ep->b_dev != dev || (ep->b_flags&B_INVAL))
- continue;
- /* look for overlap */
- if (ep->b_bcount == 0 || ep->b_blkno > last ||
-#ifdef SECSIZE
- ep->b_blkno + ep->b_bcount / ep->b_blksize <= start)
-#else SECSIZE
- ep->b_blkno + btodb(ep->b_bcount) <= start)
-#endif SECSIZE
- continue;
+ pagemove(tbp->b_data, cp, size);
+ bp->b_bcount += size;
+ bp->b_bufsize += size;
+
+ tbp->b_bufsize -= size;
+ tbp->b_flags &= ~(B_READ | B_DONE | B_ERROR | B_DELWRI);
+ tbp->b_flags |= (B_ASYNC | B_AGE);
s = splbio();
- if (ep->b_flags&B_BUSY) {
- ep->b_flags |= B_WANTED;
- sleep((caddr_t)ep, PRIBIO+1);
- splx(s);
- goto loop;
- }
- if (ep->b_flags & B_DELWRI) {
- splx(s);
- notavail(ep);
- bwrite(ep);
- goto loop;
- }
+ reassignbuf(tbp, tbp->b_vp); /* put on clean list */
+ ++tbp->b_vp->v_numoutput;
splx(s);
- }
-}
+ b_save->bs_children[i] = tbp;
-/*
- * Make sure all write-behind blocks
- * on dev (or NODEV for all)
- * are flushed out.
- * (from umount and update)
- */
-bflush(dev)
- dev_t dev;
-{
- register struct buf *bp;
- register struct buf *flist;
- int s;
-
-loop:
- s = splbio();
- for (flist = bfreelist; flist < &bfreelist[BQ_EMPTY]; flist++)
- for (bp = flist->av_forw; bp != flist; bp = bp->av_forw) {
- if ((bp->b_flags & B_DELWRI) == 0)
- continue;
- if (dev == NODEV || dev == bp->b_dev) {
- bp->b_flags |= B_ASYNC;
- notavail(bp);
- bwrite(bp);
- splx(s);
- goto loop;
- }
+ cp += size;
}
- splx(s);
-}
-
-/*
- * Pick up the device's error number and pass it to the user;
- * if there is an error but the number is 0 set a generalized code.
- */
-geterror(bp)
- register struct buf *bp;
-{
- int error = 0;
- if (bp->b_flags&B_ERROR)
- if ((error = bp->b_error)==0)
- return (EIO);
- return (error);
+ if (i == 0) {
+ /* None to cluster */
+ bp->b_saveaddr = b_save->bs_saveaddr;
+ bp->b_flags &= ~B_CALL;
+ bp->b_iodone = NULL;
+ free(b_save, M_SEGMENT);
+ }
+ bawrite(bp);
+ if (i < len) {
+ len -= i + 1;
+ start_lbn += 1;
+ goto redo;
+ }
}
/*
- * Invalidate in core blocks belonging to closed or umounted filesystem
- *
- * This is not nicely done at all - the buffer ought to be removed from the
- * hash chains & have its dev/blkno fields clobbered, but unfortunately we
- * can't do that here, as it is quite possible that the block is still
- * being used for i/o. Eventually, all disc drivers should be forced to
- * have a close routine, which ought ensure that the queue is empty, then
- * properly flush the queues. Until that happy day, this suffices for
- * correctness. ... kre
+ * Collect together all the buffers in a cluster.
+ * Plus add one additional buffer.
*/
-binval(dev)
- dev_t dev;
+struct cluster_save *
+cluster_collectbufs(vp, last_bp)
+ struct vnode *vp;
+ struct buf *last_bp;
{
- register struct buf *bp;
- register struct bufhd *hp;
-#define dp ((struct buf *)hp)
-
- for (hp = bufhash; hp < &bufhash[BUFHSZ]; hp++)
- for (bp = dp->b_forw; bp != dp; bp = bp->b_forw)
- if (bp->b_dev == dev)
- bp->b_flags |= B_INVAL;
+ struct cluster_save *buflist;
+ daddr_t lbn;
+ int i, len;
+
+ len = vp->v_lastw - vp->v_cstart + 1;
+ buflist = malloc(sizeof(struct buf *) * (len + 1) + sizeof(*buflist),
+ M_SEGMENT, M_WAITOK);
+ buflist->bs_nchildren = 0;
+ buflist->bs_children = (struct buf **)(buflist + 1);
+ for (lbn = vp->v_cstart, i = 0; i < len; lbn++, i++)
+ (void)bread(vp, lbn, last_bp->b_bcount, NOCRED,
+ &buflist->bs_children[i]);
+ buflist->bs_children[i] = last_bp;
+ buflist->bs_nchildren = i + 1;
+ return (buflist);
}