Home | History | Annotate | Line # | Download | only in kern
vfs_bio.c revision 1.73
      1 /*	$NetBSD: vfs_bio.c,v 1.73 2000/11/27 08:39:43 chs Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 1994 Christopher G. Demetriou
      5  * Copyright (c) 1982, 1986, 1989, 1993
      6  *	The Regents of the University of California.  All rights reserved.
      7  * (c) UNIX System Laboratories, Inc.
      8  * All or some portions of this file are derived from material licensed
      9  * to the University of California by American Telephone and Telegraph
     10  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
     11  * the permission of UNIX System Laboratories, Inc.
     12  *
     13  * Redistribution and use in source and binary forms, with or without
     14  * modification, are permitted provided that the following conditions
     15  * are met:
     16  * 1. Redistributions of source code must retain the above copyright
     17  *    notice, this list of conditions and the following disclaimer.
     18  * 2. Redistributions in binary form must reproduce the above copyright
     19  *    notice, this list of conditions and the following disclaimer in the
     20  *    documentation and/or other materials provided with the distribution.
     21  * 3. All advertising materials mentioning features or use of this software
     22  *    must display the following acknowledgement:
     23  *	This product includes software developed by the University of
     24  *	California, Berkeley and its contributors.
     25  * 4. Neither the name of the University nor the names of its contributors
     26  *    may be used to endorse or promote products derived from this software
     27  *    without specific prior written permission.
     28  *
     29  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     30  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     31  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     32  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     33  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     34  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     35  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     36  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     37  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     38  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     39  * SUCH DAMAGE.
     40  *
     41  *	@(#)vfs_bio.c	8.6 (Berkeley) 1/11/94
     42  */
     43 
     44 /*
     45  * Some references:
     46  *	Bach: The Design of the UNIX Operating System (Prentice Hall, 1986)
     47  *	Leffler, et al.: The Design and Implementation of the 4.3BSD
     48  *		UNIX Operating System (Addison Welley, 1989)
     49  */
     50 
     51 #include <sys/param.h>
     52 #include <sys/systm.h>
     53 #include <sys/proc.h>
     54 #include <sys/buf.h>
     55 #include <sys/vnode.h>
     56 #include <sys/mount.h>
     57 #include <sys/trace.h>
     58 #include <sys/malloc.h>
     59 #include <sys/resourcevar.h>
     60 #include <sys/conf.h>
     61 
     62 #include <uvm/uvm.h>
     63 
     64 #include <miscfs/specfs/specdev.h>
     65 
     66 /* Macros to clear/set/test flags. */
     67 #define	SET(t, f)	(t) |= (f)
     68 #define	CLR(t, f)	(t) &= ~(f)
     69 #define	ISSET(t, f)	((t) & (f))
     70 
     71 /*
     72  * Definitions for the buffer hash lists.
     73  */
     74 #define	BUFHASH(dvp, lbn)	\
     75 	(&bufhashtbl[(((long)(dvp) >> 8) + (int)(lbn)) & bufhash])
     76 LIST_HEAD(bufhashhdr, buf) *bufhashtbl, invalhash;
     77 u_long	bufhash;
     78 struct bio_ops bioops;	/* I/O operation notification */
     79 
     80 /*
     81  * Insq/Remq for the buffer hash lists.
     82  */
     83 #define	binshash(bp, dp)	LIST_INSERT_HEAD(dp, bp, b_hash)
     84 #define	bremhash(bp)		LIST_REMOVE(bp, b_hash)
     85 
     86 /*
     87  * Definitions for the buffer free lists.
     88  */
     89 #define	BQUEUES		4		/* number of free buffer queues */
     90 
     91 #define	BQ_LOCKED	0		/* super-blocks &c */
     92 #define	BQ_LRU		1		/* lru, useful buffers */
     93 #define	BQ_AGE		2		/* rubbish */
     94 #define	BQ_EMPTY	3		/* buffer headers with no memory */
     95 
     96 TAILQ_HEAD(bqueues, buf) bufqueues[BQUEUES];
     97 int needbuffer;
     98 
     99 /*
    100  * Buffer pool for I/O buffers.
    101  */
    102 struct pool bufpool;
    103 
    104 /*
    105  * Insq/Remq for the buffer free lists.
    106  */
    107 #define	binsheadfree(bp, dp)	TAILQ_INSERT_HEAD(dp, bp, b_freelist)
    108 #define	binstailfree(bp, dp)	TAILQ_INSERT_TAIL(dp, bp, b_freelist)
    109 
    110 static __inline struct buf *bio_doread __P((struct vnode *, daddr_t, int,
    111 					    struct ucred *, int));
    112 int count_lock_queue __P((void));
    113 
    114 void
    115 bremfree(bp)
    116 	struct buf *bp;
    117 {
    118 	int s = splbio();
    119 
    120 	struct bqueues *dp = NULL;
    121 
    122 	/*
    123 	 * We only calculate the head of the freelist when removing
    124 	 * the last element of the list as that is the only time that
    125 	 * it is needed (e.g. to reset the tail pointer).
    126 	 *
    127 	 * NB: This makes an assumption about how tailq's are implemented.
    128 	 */
    129 	if (bp->b_freelist.tqe_next == NULL) {
    130 		for (dp = bufqueues; dp < &bufqueues[BQUEUES]; dp++)
    131 			if (dp->tqh_last == &bp->b_freelist.tqe_next)
    132 				break;
    133 		if (dp == &bufqueues[BQUEUES])
    134 			panic("bremfree: lost tail");
    135 	}
    136 	TAILQ_REMOVE(dp, bp, b_freelist);
    137 	splx(s);
    138 }
    139 
    140 /*
    141  * Initialize buffers and hash links for buffers.
    142  */
    143 void
    144 bufinit()
    145 {
    146 	struct buf *bp;
    147 	struct bqueues *dp;
    148 	int i;
    149 	int base, residual;
    150 
    151 	/*
    152 	 * Initialize the buffer pool.  This pool is used for buffers
    153 	 * which are strictly I/O control blocks, not buffer cache
    154 	 * buffers.
    155 	 */
    156 	pool_init(&bufpool, sizeof(struct buf), 0, 0, 0, "bufpl", 0,
    157 	    NULL, NULL, M_DEVBUF);
    158 
    159 	for (dp = bufqueues; dp < &bufqueues[BQUEUES]; dp++)
    160 		TAILQ_INIT(dp);
    161 	bufhashtbl = hashinit(nbuf, HASH_LIST, M_CACHE, M_WAITOK, &bufhash);
    162 	base = bufpages / nbuf;
    163 	residual = bufpages % nbuf;
    164 	for (i = 0; i < nbuf; i++) {
    165 		bp = &buf[i];
    166 		memset((char *)bp, 0, sizeof(*bp));
    167 		bp->b_dev = NODEV;
    168 		bp->b_vnbufs.le_next = NOLIST;
    169 		LIST_INIT(&bp->b_dep);
    170 		bp->b_data = buffers + i * MAXBSIZE;
    171 		if (i < residual)
    172 			bp->b_bufsize = (base + 1) * PAGE_SIZE;
    173 		else
    174 			bp->b_bufsize = base * PAGE_SIZE;
    175 		bp->b_flags = B_INVAL;
    176 		dp = bp->b_bufsize ? &bufqueues[BQ_AGE] : &bufqueues[BQ_EMPTY];
    177 		binsheadfree(bp, dp);
    178 		binshash(bp, &invalhash);
    179 	}
    180 }
    181 
    182 static __inline struct buf *
    183 bio_doread(vp, blkno, size, cred, async)
    184 	struct vnode *vp;
    185 	daddr_t blkno;
    186 	int size;
    187 	struct ucred *cred;
    188 	int async;
    189 {
    190 	struct buf *bp;
    191 	struct proc *p = (curproc != NULL ? curproc : &proc0);	/* XXX */
    192 
    193 	bp = getblk(vp, blkno, size, 0, 0);
    194 
    195 	/*
    196 	 * If buffer does not have data valid, start a read.
    197 	 * Note that if buffer is B_INVAL, getblk() won't return it.
    198 	 * Therefore, it's valid if it's I/O has completed or been delayed.
    199 	 */
    200 	if (!ISSET(bp->b_flags, (B_DONE | B_DELWRI))) {
    201 		/* Start I/O for the buffer. */
    202 		SET(bp->b_flags, B_READ | async);
    203 		VOP_STRATEGY(bp);
    204 
    205 		/* Pay for the read. */
    206 		p->p_stats->p_ru.ru_inblock++;
    207 	} else if (async) {
    208 		brelse(bp);
    209 	}
    210 
    211 	return (bp);
    212 }
    213 
    214 /*
    215  * Read a disk block.
    216  * This algorithm described in Bach (p.54).
    217  */
    218 int
    219 bread(vp, blkno, size, cred, bpp)
    220 	struct vnode *vp;
    221 	daddr_t blkno;
    222 	int size;
    223 	struct ucred *cred;
    224 	struct buf **bpp;
    225 {
    226 	struct buf *bp;
    227 
    228 	/* Get buffer for block. */
    229 	bp = *bpp = bio_doread(vp, blkno, size, cred, 0);
    230 
    231 	/*
    232 	 * Delayed write buffers are found in the cache and have
    233 	 * valid contents. Also, B_ERROR is not set, otherwise
    234 	 * getblk() would not have returned them.
    235 	 */
    236 	if (ISSET(bp->b_flags, B_DONE|B_DELWRI))
    237 		return (0);
    238 
    239 	/*
    240 	 * Otherwise, we had to start a read for it; wait until
    241 	 * it's valid and return the result.
    242 	 */
    243 	return (biowait(bp));
    244 }
    245 
    246 /*
    247  * Read-ahead multiple disk blocks. The first is sync, the rest async.
    248  * Trivial modification to the breada algorithm presented in Bach (p.55).
    249  */
    250 int
    251 breadn(vp, blkno, size, rablks, rasizes, nrablks, cred, bpp)
    252 	struct vnode *vp;
    253 	daddr_t blkno; int size;
    254 	daddr_t rablks[]; int rasizes[];
    255 	int nrablks;
    256 	struct ucred *cred;
    257 	struct buf **bpp;
    258 {
    259 	struct buf *bp;
    260 	int i;
    261 
    262 	bp = *bpp = bio_doread(vp, blkno, size, cred, 0);
    263 
    264 	/*
    265 	 * For each of the read-ahead blocks, start a read, if necessary.
    266 	 */
    267 	for (i = 0; i < nrablks; i++) {
    268 		/* If it's in the cache, just go on to next one. */
    269 		if (incore(vp, rablks[i]))
    270 			continue;
    271 
    272 		/* Get a buffer for the read-ahead block */
    273 		(void) bio_doread(vp, rablks[i], rasizes[i], cred, B_ASYNC);
    274 	}
    275 
    276 	/*
    277 	 * Delayed write buffers are found in the cache and have
    278 	 * valid contents. Also, B_ERROR is not set, otherwise
    279 	 * getblk() would not have returned them.
    280 	 */
    281 	if (ISSET(bp->b_flags, B_DONE|B_DELWRI))
    282 		return (0);
    283 
    284 	/*
    285 	 * Otherwise, we had to start a read for it; wait until
    286 	 * it's valid and return the result.
    287 	 */
    288 	return (biowait(bp));
    289 }
    290 
    291 /*
    292  * Read with single-block read-ahead.  Defined in Bach (p.55), but
    293  * implemented as a call to breadn().
    294  * XXX for compatibility with old file systems.
    295  */
    296 int
    297 breada(vp, blkno, size, rablkno, rabsize, cred, bpp)
    298 	struct vnode *vp;
    299 	daddr_t blkno; int size;
    300 	daddr_t rablkno; int rabsize;
    301 	struct ucred *cred;
    302 	struct buf **bpp;
    303 {
    304 
    305 	return (breadn(vp, blkno, size, &rablkno, &rabsize, 1, cred, bpp));
    306 }
    307 
    308 /*
    309  * Block write.  Described in Bach (p.56)
    310  */
    311 int
    312 bwrite(bp)
    313 	struct buf *bp;
    314 {
    315 	int rv, sync, wasdelayed, s;
    316 	struct proc *p = (curproc != NULL ? curproc : &proc0);	/* XXX */
    317 	struct vnode *vp;
    318 	struct mount *mp;
    319 
    320 	/*
    321 	 * Remember buffer type, to switch on it later.  If the write was
    322 	 * synchronous, but the file system was mounted with MNT_ASYNC,
    323 	 * convert it to a delayed write.
    324 	 * XXX note that this relies on delayed tape writes being converted
    325 	 * to async, not sync writes (which is safe, but ugly).
    326 	 */
    327 	sync = !ISSET(bp->b_flags, B_ASYNC);
    328 	if (sync && bp->b_vp && bp->b_vp->v_mount &&
    329 	    ISSET(bp->b_vp->v_mount->mnt_flag, MNT_ASYNC)) {
    330 		bdwrite(bp);
    331 		return (0);
    332 	}
    333 
    334 	/*
    335 	 * Collect statistics on synchronous and asynchronous writes.
    336 	 * Writes to block devices are charged to their associated
    337 	 * filesystem (if any).
    338 	 */
    339 	if ((vp = bp->b_vp) != NULL) {
    340 		if (vp->v_type == VBLK)
    341 			mp = vp->v_specmountpoint;
    342 		else
    343 			mp = vp->v_mount;
    344 		if (mp != NULL) {
    345 			if (sync)
    346 				mp->mnt_stat.f_syncwrites++;
    347 			else
    348 				mp->mnt_stat.f_asyncwrites++;
    349 		}
    350 	}
    351 
    352 	wasdelayed = ISSET(bp->b_flags, B_DELWRI);
    353 
    354 	s = splbio();
    355 
    356 	CLR(bp->b_flags, (B_READ | B_DONE | B_ERROR | B_DELWRI));
    357 
    358 	/*
    359 	 * Pay for the I/O operation and make sure the buf is on the correct
    360 	 * vnode queue.
    361 	 */
    362 	if (wasdelayed)
    363 		reassignbuf(bp, bp->b_vp);
    364 	else
    365 		p->p_stats->p_ru.ru_oublock++;
    366 
    367 	/* Initiate disk write.  Make sure the appropriate party is charged. */
    368 	bp->b_vp->v_numoutput++;
    369 	splx(s);
    370 
    371 	VOP_STRATEGY(bp);
    372 
    373 	if (sync) {
    374 		/* If I/O was synchronous, wait for it to complete. */
    375 		rv = biowait(bp);
    376 
    377 		/* Release the buffer. */
    378 		brelse(bp);
    379 
    380 		return (rv);
    381 	} else {
    382 		return (0);
    383 	}
    384 }
    385 
    386 int
    387 vn_bwrite(v)
    388 	void *v;
    389 {
    390 	struct vop_bwrite_args *ap = v;
    391 
    392 	return (bwrite(ap->a_bp));
    393 }
    394 
    395 /*
    396  * Delayed write.
    397  *
    398  * The buffer is marked dirty, but is not queued for I/O.
    399  * This routine should be used when the buffer is expected
    400  * to be modified again soon, typically a small write that
    401  * partially fills a buffer.
    402  *
    403  * NB: magnetic tapes cannot be delayed; they must be
    404  * written in the order that the writes are requested.
    405  *
    406  * Described in Leffler, et al. (pp. 208-213).
    407  */
    408 void
    409 bdwrite(bp)
    410 	struct buf *bp;
    411 {
    412 	struct proc *p = (curproc != NULL ? curproc : &proc0);	/* XXX */
    413 	int s;
    414 
    415 	/* If this is a tape block, write the block now. */
    416 	/* XXX NOTE: the memory filesystem usurpes major device */
    417 	/* XXX       number 255, which is a bad idea.		*/
    418 	if (bp->b_dev != NODEV &&
    419 	    major(bp->b_dev) != 255 &&	/* XXX - MFS buffers! */
    420 	    bdevsw[major(bp->b_dev)].d_type == D_TAPE) {
    421 		bawrite(bp);
    422 		return;
    423 	}
    424 
    425 	/*
    426 	 * If the block hasn't been seen before:
    427 	 *	(1) Mark it as having been seen,
    428 	 *	(2) Charge for the write,
    429 	 *	(3) Make sure it's on its vnode's correct block list.
    430 	 */
    431 	s = splbio();
    432 
    433 	if (!ISSET(bp->b_flags, B_DELWRI)) {
    434 		SET(bp->b_flags, B_DELWRI);
    435 		p->p_stats->p_ru.ru_oublock++;
    436 		reassignbuf(bp, bp->b_vp);
    437 	}
    438 
    439 	/* Otherwise, the "write" is done, so mark and release the buffer. */
    440 	CLR(bp->b_flags, B_NEEDCOMMIT|B_DONE);
    441 	splx(s);
    442 
    443 	brelse(bp);
    444 }
    445 
    446 /*
    447  * Asynchronous block write; just an asynchronous bwrite().
    448  */
    449 void
    450 bawrite(bp)
    451 	struct buf *bp;
    452 {
    453 
    454 	SET(bp->b_flags, B_ASYNC);
    455 	VOP_BWRITE(bp);
    456 }
    457 
    458 /*
    459  * Ordered block write; asynchronous, but I/O will occur in order queued.
    460  */
    461 void
    462 bowrite(bp)
    463 	struct buf *bp;
    464 {
    465 
    466 	SET(bp->b_flags, B_ASYNC | B_ORDERED);
    467 	VOP_BWRITE(bp);
    468 }
    469 
    470 /*
    471  * Same as first half of bdwrite, mark buffer dirty, but do not release it.
    472  */
    473 void
    474 bdirty(bp)
    475 	struct buf *bp;
    476 {
    477 	struct proc *p = (curproc != NULL ? curproc : &proc0);	/* XXX */
    478 	int s;
    479 
    480 	s = splbio();
    481 
    482 	CLR(bp->b_flags, B_AGE);
    483 
    484 	if (!ISSET(bp->b_flags, B_DELWRI)) {
    485 		SET(bp->b_flags, B_DELWRI);
    486 		p->p_stats->p_ru.ru_oublock++;
    487 		reassignbuf(bp, bp->b_vp);
    488 	}
    489 
    490 	splx(s);
    491 }
    492 
    493 /*
    494  * Release a buffer on to the free lists.
    495  * Described in Bach (p. 46).
    496  */
    497 void
    498 brelse(bp)
    499 	struct buf *bp;
    500 {
    501 	struct bqueues *bufq;
    502 	int s;
    503 
    504 	KASSERT(ISSET(bp->b_flags, B_BUSY));
    505 
    506 	/* Wake up any processes waiting for any buffer to become free. */
    507 	if (needbuffer) {
    508 		needbuffer = 0;
    509 		wakeup(&needbuffer);
    510 	}
    511 
    512 	/* Block disk interrupts. */
    513 	s = splbio();
    514 
    515 	/* Wake up any proceeses waiting for _this_ buffer to become free. */
    516 	if (ISSET(bp->b_flags, B_WANTED)) {
    517 		CLR(bp->b_flags, B_WANTED|B_AGE);
    518 		wakeup(bp);
    519 	}
    520 
    521 	/*
    522 	 * Determine which queue the buffer should be on, then put it there.
    523 	 */
    524 
    525 	/* If it's locked, don't report an error; try again later. */
    526 	if (ISSET(bp->b_flags, (B_LOCKED|B_ERROR)) == (B_LOCKED|B_ERROR))
    527 		CLR(bp->b_flags, B_ERROR);
    528 
    529 	/* If it's not cacheable, or an error, mark it invalid. */
    530 	if (ISSET(bp->b_flags, (B_NOCACHE|B_ERROR)))
    531 		SET(bp->b_flags, B_INVAL);
    532 
    533 	if (ISSET(bp->b_flags, B_VFLUSH)) {
    534 		/*
    535 		 * This is a delayed write buffer that was just flushed to
    536 		 * disk.  It is still on the LRU queue.  If it's become
    537 		 * invalid, then we need to move it to a different queue;
    538 		 * otherwise leave it in its current position.
    539 		 */
    540 		CLR(bp->b_flags, B_VFLUSH);
    541 		if (!ISSET(bp->b_flags, B_ERROR|B_INVAL|B_LOCKED|B_AGE))
    542 			goto already_queued;
    543 		else
    544 			bremfree(bp);
    545 	}
    546 
    547 	if ((bp->b_bufsize <= 0) || ISSET(bp->b_flags, B_INVAL)) {
    548 		/*
    549 		 * If it's invalid or empty, dissociate it from its vnode
    550 		 * and put on the head of the appropriate queue.
    551 		 */
    552 		if (LIST_FIRST(&bp->b_dep) != NULL && bioops.io_deallocate)
    553 			(*bioops.io_deallocate)(bp);
    554 		CLR(bp->b_flags, B_DONE|B_DELWRI);
    555 		if (bp->b_vp) {
    556 			reassignbuf(bp, bp->b_vp);
    557 			brelvp(bp);
    558 		}
    559 		if (bp->b_bufsize <= 0)
    560 			/* no data */
    561 			bufq = &bufqueues[BQ_EMPTY];
    562 		else
    563 			/* invalid data */
    564 			bufq = &bufqueues[BQ_AGE];
    565 		binsheadfree(bp, bufq);
    566 	} else {
    567 		/*
    568 		 * It has valid data.  Put it on the end of the appropriate
    569 		 * queue, so that it'll stick around for as long as possible.
    570 		 * If buf is AGE, but has dependencies, must put it on last
    571 		 * bufqueue to be scanned, ie LRU. This protects against the
    572 		 * livelock where BQ_AGE only has buffers with dependencies,
    573 		 * and we thus never get to the dependent buffers in BQ_LRU.
    574 		 */
    575 		if (ISSET(bp->b_flags, B_LOCKED))
    576 			/* locked in core */
    577 			bufq = &bufqueues[BQ_LOCKED];
    578 		else if (!ISSET(bp->b_flags, B_AGE))
    579 			/* valid data */
    580 			bufq = &bufqueues[BQ_LRU];
    581 		else {
    582 			/* stale but valid data */
    583 			int has_deps;
    584 
    585 			if (LIST_FIRST(&bp->b_dep) != NULL &&
    586 			    bioops.io_countdeps)
    587 				has_deps = (*bioops.io_countdeps)(bp, 0);
    588 			else
    589 				has_deps = 0;
    590 			bufq = has_deps ? &bufqueues[BQ_LRU] :
    591 			    &bufqueues[BQ_AGE];
    592 		}
    593 		binstailfree(bp, bufq);
    594 	}
    595 
    596 already_queued:
    597 	/* Unlock the buffer. */
    598 	CLR(bp->b_flags, B_AGE|B_ASYNC|B_BUSY|B_NOCACHE|B_ORDERED);
    599 	SET(bp->b_flags, B_CACHE);
    600 
    601 	/* Allow disk interrupts. */
    602 	splx(s);
    603 }
    604 
    605 /*
    606  * Determine if a block is in the cache.
    607  * Just look on what would be its hash chain.  If it's there, return
    608  * a pointer to it, unless it's marked invalid.  If it's marked invalid,
    609  * we normally don't return the buffer, unless the caller explicitly
    610  * wants us to.
    611  */
    612 struct buf *
    613 incore(vp, blkno)
    614 	struct vnode *vp;
    615 	daddr_t blkno;
    616 {
    617 	struct buf *bp;
    618 
    619 	bp = BUFHASH(vp, blkno)->lh_first;
    620 
    621 	/* Search hash chain */
    622 	for (; bp != NULL; bp = bp->b_hash.le_next) {
    623 		if (bp->b_lblkno == blkno && bp->b_vp == vp &&
    624 		    !ISSET(bp->b_flags, B_INVAL))
    625 		return (bp);
    626 	}
    627 
    628 	return (NULL);
    629 }
    630 
    631 /*
    632  * Get a block of requested size that is associated with
    633  * a given vnode and block offset. If it is found in the
    634  * block cache, mark it as having been found, make it busy
    635  * and return it. Otherwise, return an empty block of the
    636  * correct size. It is up to the caller to insure that the
    637  * cached blocks be of the correct size.
    638  */
    639 struct buf *
    640 getblk(vp, blkno, size, slpflag, slptimeo)
    641 	struct vnode *vp;
    642 	daddr_t blkno;
    643 	int size, slpflag, slptimeo;
    644 {
    645 	struct buf *bp;
    646 	int s, err;
    647 
    648 start:
    649 	bp = incore(vp, blkno);
    650 	if (bp != NULL) {
    651 		s = splbio();
    652 		if (ISSET(bp->b_flags, B_BUSY)) {
    653 			if (curproc == uvm.pagedaemon_proc) {
    654 				splx(s);
    655 				return NULL;
    656 			}
    657 			SET(bp->b_flags, B_WANTED);
    658 			err = tsleep(bp, slpflag | (PRIBIO + 1), "getblk",
    659 				     slptimeo);
    660 			splx(s);
    661 			if (err)
    662 				return (NULL);
    663 			goto start;
    664 		}
    665 #ifdef DIAGNOSTIC
    666 		if (ISSET(bp->b_flags, B_DONE|B_DELWRI) && bp->b_bcount < size)
    667 			panic("getblk: block size invariant failed");
    668 #endif
    669 		SET(bp->b_flags, B_BUSY);
    670 		bremfree(bp);
    671 		splx(s);
    672 	} else {
    673 		if ((bp = getnewbuf(slpflag, slptimeo)) == NULL)
    674 			goto start;
    675 
    676 		binshash(bp, BUFHASH(vp, blkno));
    677 		bp->b_blkno = bp->b_lblkno = bp->b_rawblkno = blkno;
    678 		s = splbio();
    679 		bgetvp(vp, bp);
    680 		splx(s);
    681 	}
    682 	allocbuf(bp, size);
    683 	return (bp);
    684 }
    685 
    686 /*
    687  * Get an empty, disassociated buffer of given size.
    688  */
    689 struct buf *
    690 geteblk(size)
    691 	int size;
    692 {
    693 	struct buf *bp;
    694 
    695 	while ((bp = getnewbuf(0, 0)) == 0)
    696 		;
    697 	SET(bp->b_flags, B_INVAL);
    698 	binshash(bp, &invalhash);
    699 	allocbuf(bp, size);
    700 	return (bp);
    701 }
    702 
    703 /*
    704  * Expand or contract the actual memory allocated to a buffer.
    705  *
    706  * If the buffer shrinks, data is lost, so it's up to the
    707  * caller to have written it out *first*; this routine will not
    708  * start a write.  If the buffer grows, it's the callers
    709  * responsibility to fill out the buffer's additional contents.
    710  */
    711 void
    712 allocbuf(bp, size)
    713 	struct buf *bp;
    714 	int size;
    715 {
    716 	struct buf *nbp;
    717 	vsize_t desired_size;
    718 	int s;
    719 
    720 	desired_size = round_page((vsize_t)size);
    721 	if (desired_size > MAXBSIZE)
    722 		panic("allocbuf: buffer larger than MAXBSIZE requested");
    723 
    724 	if (bp->b_bufsize == desired_size)
    725 		goto out;
    726 
    727 	/*
    728 	 * If the buffer is smaller than the desired size, we need to snarf
    729 	 * it from other buffers.  Get buffers (via getnewbuf()), and
    730 	 * steal their pages.
    731 	 */
    732 	while (bp->b_bufsize < desired_size) {
    733 		int amt;
    734 
    735 		/* find a buffer */
    736 		while ((nbp = getnewbuf(0, 0)) == NULL)
    737 			;
    738 
    739 		SET(nbp->b_flags, B_INVAL);
    740 		binshash(nbp, &invalhash);
    741 
    742 		/* and steal its pages, up to the amount we need */
    743 		amt = min(nbp->b_bufsize, (desired_size - bp->b_bufsize));
    744 		pagemove((nbp->b_data + nbp->b_bufsize - amt),
    745 			 bp->b_data + bp->b_bufsize, amt);
    746 		bp->b_bufsize += amt;
    747 		nbp->b_bufsize -= amt;
    748 
    749 		/* reduce transfer count if we stole some data */
    750 		if (nbp->b_bcount > nbp->b_bufsize)
    751 			nbp->b_bcount = nbp->b_bufsize;
    752 
    753 #ifdef DIAGNOSTIC
    754 		if (nbp->b_bufsize < 0)
    755 			panic("allocbuf: negative bufsize");
    756 #endif
    757 
    758 		brelse(nbp);
    759 	}
    760 
    761 	/*
    762 	 * If we want a buffer smaller than the current size,
    763 	 * shrink this buffer.  Grab a buf head from the EMPTY queue,
    764 	 * move a page onto it, and put it on front of the AGE queue.
    765 	 * If there are no free buffer headers, leave the buffer alone.
    766 	 */
    767 	if (bp->b_bufsize > desired_size) {
    768 		s = splbio();
    769 		if ((nbp = bufqueues[BQ_EMPTY].tqh_first) == NULL) {
    770 			/* No free buffer head */
    771 			splx(s);
    772 			goto out;
    773 		}
    774 		bremfree(nbp);
    775 		SET(nbp->b_flags, B_BUSY);
    776 		splx(s);
    777 
    778 		/* move the page to it and note this change */
    779 		pagemove(bp->b_data + desired_size,
    780 		    nbp->b_data, bp->b_bufsize - desired_size);
    781 		nbp->b_bufsize = bp->b_bufsize - desired_size;
    782 		bp->b_bufsize = desired_size;
    783 		nbp->b_bcount = 0;
    784 		SET(nbp->b_flags, B_INVAL);
    785 
    786 		/* release the newly-filled buffer and leave */
    787 		brelse(nbp);
    788 	}
    789 
    790 out:
    791 	bp->b_bcount = size;
    792 }
    793 
    794 /*
    795  * Find a buffer which is available for use.
    796  * Select something from a free list.
    797  * Preference is to AGE list, then LRU list.
    798  */
    799 struct buf *
    800 getnewbuf(slpflag, slptimeo)
    801 	int slpflag, slptimeo;
    802 {
    803 	struct buf *bp;
    804 	int s;
    805 
    806 start:
    807 	s = splbio();
    808 	if ((bp = bufqueues[BQ_AGE].tqh_first) != NULL ||
    809 	    (bp = bufqueues[BQ_LRU].tqh_first) != NULL) {
    810 		bremfree(bp);
    811 	} else {
    812 		/* wait for a free buffer of any kind */
    813 		needbuffer = 1;
    814 		tsleep(&needbuffer, slpflag|(PRIBIO+1), "getnewbuf", slptimeo);
    815 		splx(s);
    816 		return (NULL);
    817 	}
    818 
    819 	if (ISSET(bp->b_flags, B_VFLUSH)) {
    820 		/*
    821 		 * This is a delayed write buffer being flushed to disk.  Make
    822 		 * sure it gets aged out of the queue when it's finished, and
    823 		 * leave it off the LRU queue.
    824 		 */
    825 		CLR(bp->b_flags, B_VFLUSH);
    826 		SET(bp->b_flags, B_AGE);
    827 		splx(s);
    828 		goto start;
    829 	}
    830 
    831 	/* Buffer is no longer on free lists. */
    832 	SET(bp->b_flags, B_BUSY);
    833 
    834 	/* If buffer was a delayed write, start it, and go back to the top. */
    835 	if (ISSET(bp->b_flags, B_DELWRI)) {
    836 		splx(s);
    837 		/*
    838 		 * This buffer has gone through the LRU, so make sure it gets
    839 		 * reused ASAP.
    840 		 */
    841 		SET(bp->b_flags, B_AGE);
    842 		bawrite(bp);
    843 		goto start;
    844 	}
    845 
    846 	/* disassociate us from our vnode, if we had one... */
    847 	if (bp->b_vp)
    848 		brelvp(bp);
    849 	splx(s);
    850 
    851 	if (LIST_FIRST(&bp->b_dep) != NULL && bioops.io_deallocate)
    852 		(*bioops.io_deallocate)(bp);
    853 
    854 	/* clear out various other fields */
    855 	bp->b_flags = B_BUSY;
    856 	bp->b_dev = NODEV;
    857 	bp->b_blkno = bp->b_lblkno = bp->b_rawblkno = 0;
    858 	bp->b_iodone = 0;
    859 	bp->b_error = 0;
    860 	bp->b_resid = 0;
    861 	bp->b_bcount = 0;
    862 
    863 	bremhash(bp);
    864 	return (bp);
    865 }
    866 
    867 /*
    868  * Wait for operations on the buffer to complete.
    869  * When they do, extract and return the I/O's error value.
    870  */
    871 int
    872 biowait(bp)
    873 	struct buf *bp;
    874 {
    875 	int s;
    876 
    877 	s = splbio();
    878 	while (!ISSET(bp->b_flags, B_DONE))
    879 		tsleep(bp, PRIBIO + 1, "biowait", 0);
    880 	splx(s);
    881 
    882 	/* check for interruption of I/O (e.g. via NFS), then errors. */
    883 	if (ISSET(bp->b_flags, B_EINTR)) {
    884 		CLR(bp->b_flags, B_EINTR);
    885 		return (EINTR);
    886 	} else if (ISSET(bp->b_flags, B_ERROR))
    887 		return (bp->b_error ? bp->b_error : EIO);
    888 	else
    889 		return (0);
    890 }
    891 
    892 /*
    893  * Mark I/O complete on a buffer.
    894  *
    895  * If a callback has been requested, e.g. the pageout
    896  * daemon, do so. Otherwise, awaken waiting processes.
    897  *
    898  * [ Leffler, et al., says on p.247:
    899  *	"This routine wakes up the blocked process, frees the buffer
    900  *	for an asynchronous write, or, for a request by the pagedaemon
    901  *	process, invokes a procedure specified in the buffer structure" ]
    902  *
    903  * In real life, the pagedaemon (or other system processes) wants
    904  * to do async stuff to, and doesn't want the buffer brelse()'d.
    905  * (for swap pager, that puts swap buffers on the free lists (!!!),
    906  * for the vn device, that puts malloc'd buffers on the free lists!)
    907  */
    908 void
    909 biodone(bp)
    910 	struct buf *bp;
    911 {
    912 	int s = splbio();
    913 
    914 	if (ISSET(bp->b_flags, B_DONE))
    915 		panic("biodone already");
    916 	SET(bp->b_flags, B_DONE);		/* note that it's done */
    917 
    918 	if (LIST_FIRST(&bp->b_dep) != NULL && bioops.io_complete)
    919 		(*bioops.io_complete)(bp);
    920 
    921 	if (!ISSET(bp->b_flags, B_READ))	/* wake up reader */
    922 		vwakeup(bp);
    923 
    924 	if (ISSET(bp->b_flags, B_CALL)) {	/* if necessary, call out */
    925 		CLR(bp->b_flags, B_CALL);	/* but note callout done */
    926 		(*bp->b_iodone)(bp);
    927 	} else {
    928 		if (ISSET(bp->b_flags, B_ASYNC))	/* if async, release */
    929 			brelse(bp);
    930 		else {				/* or just wakeup the buffer */
    931 			CLR(bp->b_flags, B_WANTED);
    932 			wakeup(bp);
    933 		}
    934 	}
    935 
    936 	splx(s);
    937 }
    938 
    939 /*
    940  * Return a count of buffers on the "locked" queue.
    941  */
    942 int
    943 count_lock_queue()
    944 {
    945 	struct buf *bp;
    946 	int n = 0;
    947 
    948 	for (bp = bufqueues[BQ_LOCKED].tqh_first; bp;
    949 	    bp = bp->b_freelist.tqe_next)
    950 		n++;
    951 	return (n);
    952 }
    953 
    954 #ifdef DEBUG
    955 /*
    956  * Print out statistics on the current allocation of the buffer pool.
    957  * Can be enabled to print out on every ``sync'' by setting "syncprt"
    958  * in vfs_syscalls.c using sysctl.
    959  */
    960 void
    961 vfs_bufstats()
    962 {
    963 	int s, i, j, count;
    964 	struct buf *bp;
    965 	struct bqueues *dp;
    966 	int counts[(MAXBSIZE / PAGE_SIZE) + 1];
    967 	static char *bname[BQUEUES] = { "LOCKED", "LRU", "AGE", "EMPTY" };
    968 
    969 	for (dp = bufqueues, i = 0; dp < &bufqueues[BQUEUES]; dp++, i++) {
    970 		count = 0;
    971 		for (j = 0; j <= MAXBSIZE/PAGE_SIZE; j++)
    972 			counts[j] = 0;
    973 		s = splbio();
    974 		for (bp = dp->tqh_first; bp; bp = bp->b_freelist.tqe_next) {
    975 			counts[bp->b_bufsize/PAGE_SIZE]++;
    976 			count++;
    977 		}
    978 		splx(s);
    979 		printf("%s: total-%d", bname[i], count);
    980 		for (j = 0; j <= MAXBSIZE/PAGE_SIZE; j++)
    981 			if (counts[j] != 0)
    982 				printf(", %d-%d", j * PAGE_SIZE, counts[j]);
    983 		printf("\n");
    984 	}
    985 }
    986 #endif /* DEBUG */
    987