Home | History | Annotate | Line # | Download | only in fsck_lfs
bufcache.c revision 1.3 
      1 /* $NetBSD: bufcache.c,v 1.3 2005/02/26 05:45:54 perseant Exp $ */
      2 /*-
      3  * Copyright (c) 2003 The NetBSD Foundation, Inc.
      4  * All rights reserved.
      5  *
      6  * This code is derived from software contributed to The NetBSD Foundation
      7  * by Konrad E. Schroder <perseant (at) hhhh.org>.
      8  *
      9  * Redistribution and use in source and binary forms, with or without
     10  * modification, are permitted provided that the following conditions
     11  * are met:
     12  * 1. Redistributions of source code must retain the above copyright
     13  *    notice, this list of conditions and the following disclaimer.
     14  * 2. Redistributions in binary form must reproduce the above copyright
     15  *    notice, this list of conditions and the following disclaimer in the
     16  *    documentation and/or other materials provided with the distribution.
     17  * 3. All advertising materials mentioning features or use of this software
     18  *    must display the following acknowledgement:
     19  *	This product includes software developed by the NetBSD
     20  *	Foundation, Inc. and its contributors.
     21  * 4. Neither the name of The NetBSD Foundation nor the names of its
     22  *    contributors may be used to endorse or promote products derived
     23  *    from this software without specific prior written permission.
     24  *
     25  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     26  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     27  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     28  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     29  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     30  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     31  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     32  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     33  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     35  * POSSIBILITY OF SUCH DAMAGE.
     36  */
     37 
     38 #include <sys/types.h>
     39 #include <sys/param.h>
     40 #include <sys/time.h>
     41 #include <sys/buf.h>
     42 #include <sys/queue.h>
     43 #include <sys/mount.h>
     44 
     45 #include <assert.h>
     46 #include <err.h>
     47 #include <stdio.h>
     48 #include <stdlib.h>
     49 #include <string.h>
     50 #include <unistd.h>
     51 
     52 #include "bufcache.h"
     53 #include "vnode.h"
     54 
     55 /*
     56  * Definitions for the buffer free lists.
     57  */
     58 #define	BQUEUES		3	/* number of free buffer queues */
     59 
     60 #define	BQ_LOCKED	0	/* super-blocks &c */
     61 #define	BQ_LRU		1	/* lru, useful buffers */
     62 #define	BQ_AGE		2	/* rubbish */
     63 
     64 TAILQ_HEAD(bqueues, ubuf) bufqueues[BQUEUES];
     65 
     66 #define HASH_MAX 101
     67 
     68 struct bufhash_struct bufhash[HASH_MAX];
     69 
     70 int maxbufs = BUF_CACHE_SIZE;
     71 int nbufs = 0;
     72 int cachehits = 0;
     73 int cachemisses = 0;
     74 int hashmax = 0;
     75 off_t locked_queue_bytes = 0;
     76 
     77 /* Simple buffer hash function */
     78 static int
     79 vl_hash(struct uvnode * vp, daddr_t lbn)
     80 {
     81 	return (int)((unsigned long) vp + lbn) % HASH_MAX;
     82 }
     83 
     84 /* Initialize buffer cache */
     85 void
     86 bufinit(void)
     87 {
     88 	int i;
     89 
     90 	for (i = 0; i < BQUEUES; i++) {
     91 		TAILQ_INIT(&bufqueues[i]);
     92 	}
     93 	for (i = 0; i < HASH_MAX; i++)
     94 		LIST_INIT(&bufhash[HASH_MAX]);
     95 }
     96 
     97 /* Print statistics of buffer cache usage */
     98 void
     99 bufstats(void)
    100 {
    101 	printf("buffer cache: %d hits %d misses (%2.2f%%); hash depth %d\n",
    102 	    cachehits, cachemisses,
    103 	    (cachehits * 100.0) / (cachehits + cachemisses),
    104 	    hashmax);
    105 }
    106 
    107 /*
    108  * Remove a buffer from the cache.
    109  * Caller must remove the buffer from its free list.
    110  */
    111 void
    112 buf_destroy(struct ubuf * bp)
    113 {
    114 	bp->b_flags |= B_NEEDCOMMIT;
    115 	LIST_REMOVE(bp, b_vnbufs);
    116 	LIST_REMOVE(bp, b_hash);
    117 	free(bp->b_data);
    118 	free(bp);
    119 	--nbufs;
    120 }
    121 
    122 /* Remove a buffer from its free list. */
    123 void
    124 bremfree(struct ubuf * bp)
    125 {
    126 	struct bqueues *dp = NULL;
    127 
    128 	/*
    129 	 * We only calculate the head of the freelist when removing
    130 	 * the last element of the list as that is the only time that
    131 	 * it is needed (e.g. to reset the tail pointer).
    132 	 *
    133 	 * NB: This makes an assumption about how tailq's are implemented.
    134 	 */
    135 	if (bp->b_flags & B_LOCKED) {
    136 		locked_queue_bytes -= bp->b_bcount;
    137 	}
    138 	if (TAILQ_NEXT(bp, b_freelist) == NULL) {
    139 		for (dp = bufqueues; dp < &bufqueues[BQUEUES]; dp++)
    140 			if (dp->tqh_last == &bp->b_freelist.tqe_next)
    141 				break;
    142 		if (dp == &bufqueues[BQUEUES])
    143 			errx(1, "bremfree: lost tail");
    144 	}
    145 	++bp->b_vp->v_usecount;
    146 	TAILQ_REMOVE(dp, bp, b_freelist);
    147 }
    148 
    149 /* Return a buffer if it is in the cache, otherwise return NULL. */
    150 struct ubuf *
    151 incore(struct uvnode * vp, int lbn)
    152 {
    153 	struct ubuf *bp;
    154 	int hash, depth;
    155 
    156 	hash = vl_hash(vp, lbn);
    157 	/* XXX use a real hash instead. */
    158 	depth = 0;
    159 	LIST_FOREACH(bp, &bufhash[hash], b_hash) {
    160 		if (++depth > hashmax)
    161 			hashmax = depth;
    162 		if (bp->b_vp == vp && bp->b_lblkno == lbn) {
    163 			return bp;
    164 		}
    165 	}
    166 	return NULL;
    167 }
    168 
    169 /*
    170  * Return a buffer of the given size, lbn and uvnode.
    171  * If none is in core, make a new one.
    172  */
    173 struct ubuf *
    174 getblk(struct uvnode * vp, daddr_t lbn, int size)
    175 {
    176 	struct ubuf *bp;
    177 #ifdef DEBUG
    178 	static int warned;
    179 #endif
    180 
    181 	/*
    182 	 * First check the buffer cache lists.
    183 	 */
    184 	if ((bp = incore(vp, lbn)) != NULL) {
    185 		assert(!(bp->b_flags & B_NEEDCOMMIT));
    186 		assert(!(bp->b_flags & B_BUSY));
    187 		assert(bp->b_bcount == size);
    188 		bp->b_flags |= B_BUSY;
    189 		bremfree(bp);
    190 		return bp;
    191 	}
    192 	/*
    193 	 * Not on the list.
    194 	 * Get a new block of the appropriate size and use that.
    195 	 * If not enough space, free blocks from the AGE and LRU lists
    196 	 * to make room.
    197 	 */
    198 	while (nbufs >= maxbufs) {
    199 		bp = TAILQ_FIRST(&bufqueues[BQ_AGE]);
    200 		if (bp)
    201 			TAILQ_REMOVE(&bufqueues[BQ_AGE], bp, b_freelist);
    202 		if (bp == NULL) {
    203 			bp = TAILQ_FIRST(&bufqueues[BQ_LRU]);
    204 			if (bp)
    205 				TAILQ_REMOVE(&bufqueues[BQ_LRU], bp,
    206 				    b_freelist);
    207 		}
    208 		if (bp) {
    209 			if (bp->b_flags & B_DELWRI)
    210 				VOP_STRATEGY(bp);
    211 			buf_destroy(bp);
    212 		}
    213 #ifdef DEBUG
    214 		else {
    215 			if (!warned)
    216 				warnx("allocating more than %d buffers",
    217 					maxbufs);
    218 			++warned;
    219 			break;
    220 		}
    221 #endif
    222 	}
    223 	++nbufs;
    224 	bp = (struct ubuf *) malloc(sizeof(*bp));
    225 	memset(bp, 0, sizeof(*bp));
    226 	bp->b_data = malloc(size);
    227 	memset(bp->b_data, 0, size);
    228 
    229 	bp->b_vp = vp;
    230 	bp->b_blkno = bp->b_lblkno = lbn;
    231 	bp->b_bcount = size;
    232 	LIST_INSERT_HEAD(&bufhash[vl_hash(vp, lbn)], bp, b_hash);
    233 	LIST_INSERT_HEAD(&vp->v_cleanblkhd, bp, b_vnbufs);
    234 	bp->b_flags = B_BUSY;
    235 
    236 	return bp;
    237 }
    238 
    239 /* Write a buffer to disk according to its strategy routine. */
    240 void
    241 bwrite(struct ubuf * bp)
    242 {
    243 	bp->b_flags &= ~(B_READ | B_DONE | B_DELWRI | B_LOCKED);
    244 	VOP_STRATEGY(bp);
    245 	bp->b_flags |= B_DONE;
    246 	reassignbuf(bp, bp->b_vp);
    247 	brelse(bp);
    248 }
    249 
    250 /* Put a buffer back on its free list, clear B_BUSY. */
    251 void
    252 brelse(struct ubuf * bp)
    253 {
    254 	int age;
    255 
    256 	assert(!(bp->b_flags & B_NEEDCOMMIT));
    257 	assert(bp->b_flags & B_BUSY);
    258 
    259 	age = bp->b_flags & B_AGE;
    260 	bp->b_flags &= ~(B_BUSY | B_AGE);
    261 	if (bp->b_flags & B_INVAL) {
    262 		buf_destroy(bp);
    263 		return;
    264 	}
    265 	if (bp->b_flags & B_LOCKED) {
    266 		locked_queue_bytes += bp->b_bcount;
    267 		TAILQ_INSERT_TAIL(&bufqueues[BQ_LOCKED], bp, b_freelist);
    268 	} else if (age) {
    269 		TAILQ_INSERT_TAIL(&bufqueues[BQ_AGE], bp, b_freelist);
    270 	} else {
    271 		TAILQ_INSERT_TAIL(&bufqueues[BQ_LRU], bp, b_freelist);
    272 	}
    273 	--bp->b_vp->v_usecount;
    274 }
    275 
    276 /* Read the given block from disk, return it B_BUSY. */
    277 int
    278 bread(struct uvnode * vp, daddr_t lbn, int size, struct ucred * unused,
    279     struct ubuf ** bpp)
    280 {
    281 	struct ubuf *bp;
    282 	daddr_t daddr;
    283 	int error, count;
    284 
    285 	bp = getblk(vp, lbn, size);
    286 	*bpp = bp;
    287 	if (bp->b_flags & (B_DELWRI | B_DONE)) {
    288 		++cachehits;
    289 		return 0;
    290 	}
    291 	++cachemisses;
    292 
    293 	/*
    294 	 * Not found.  Need to find that block's location on disk,
    295 	 * and load it in.
    296 	 */
    297 	daddr = -1;
    298 	error = VOP_BMAP(vp, lbn, &daddr);
    299 	bp->b_blkno = daddr;
    300 	if (daddr >= 0) {
    301 		count = pread(vp->v_fd, bp->b_data, bp->b_bcount,
    302 				dbtob((off_t) daddr));
    303 		if (count == bp->b_bcount) {
    304 			bp->b_flags |= B_DONE;
    305 			return 0;
    306 		}
    307 		return -1;
    308 	}
    309 	memset(bp->b_data, 0, bp->b_bcount);
    310 	return 0;
    311 }
    312 
    313 /* Move a buffer between dirty and clean block lists. */
    314 void
    315 reassignbuf(struct ubuf * bp, struct uvnode * vp)
    316 {
    317 	LIST_REMOVE(bp, b_vnbufs);
    318 	if (bp->b_flags & B_DELWRI) {
    319 		LIST_INSERT_HEAD(&vp->v_dirtyblkhd, bp, b_vnbufs);
    320 	} else {
    321 		LIST_INSERT_HEAD(&vp->v_cleanblkhd, bp, b_vnbufs);
    322 	}
    323 }
    324 
    325 #ifdef DEBUG
    326 void
    327 dump_free_lists(void)
    328 {
    329 	struct ubuf *bp;
    330 	int i;
    331 
    332 	for (i = 0; i <= BQ_LOCKED; i++) {
    333 		printf("==> free list %d:\n", i);
    334 		TAILQ_FOREACH(bp, &bufqueues[i], b_freelist) {
    335 			printf("vp %p lbn %" PRId64 " flags %lx\n",
    336 				bp->b_vp, bp->b_lblkno, bp->b_flags);
    337 		}
    338 	}
    339 }
    340 #endif
    341