Home | History | Annotate | Line # | Download | only in fsck_lfs
bufcache.c revision 1.4 
      1 /* $NetBSD: bufcache.c,v 1.4 2005/03/19 00:43:17 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 int locked_queue_count = 0;
     77 
     78 /* Simple buffer hash function */
     79 static int
     80 vl_hash(struct uvnode * vp, daddr_t lbn)
     81 {
     82 	return (int)((unsigned long) vp + lbn) % HASH_MAX;
     83 }
     84 
     85 /* Initialize buffer cache */
     86 void
     87 bufinit(void)
     88 {
     89 	int i;
     90 
     91 	for (i = 0; i < BQUEUES; i++) {
     92 		TAILQ_INIT(&bufqueues[i]);
     93 	}
     94 	for (i = 0; i < HASH_MAX; i++)
     95 		LIST_INIT(&bufhash[i]);
     96 }
     97 
     98 /* Print statistics of buffer cache usage */
     99 void
    100 bufstats(void)
    101 {
    102 	printf("buffer cache: %d hits %d misses (%2.2f%%); hash depth %d\n",
    103 	    cachehits, cachemisses,
    104 	    (cachehits * 100.0) / (cachehits + cachemisses),
    105 	    hashmax);
    106 }
    107 
    108 /*
    109  * Remove a buffer from the cache.
    110  * Caller must remove the buffer from its free list.
    111  */
    112 void
    113 buf_destroy(struct ubuf * bp)
    114 {
    115 	bp->b_flags |= B_NEEDCOMMIT;
    116 	LIST_REMOVE(bp, b_vnbufs);
    117 	LIST_REMOVE(bp, b_hash);
    118 	free(bp->b_data);
    119 	free(bp);
    120 	--nbufs;
    121 }
    122 
    123 /* Remove a buffer from its free list. */
    124 void
    125 bremfree(struct ubuf * bp)
    126 {
    127 	struct bqueues *dp = NULL;
    128 
    129 	/*
    130 	 * We only calculate the head of the freelist when removing
    131 	 * the last element of the list as that is the only time that
    132 	 * it is needed (e.g. to reset the tail pointer).
    133 	 *
    134 	 * NB: This makes an assumption about how tailq's are implemented.
    135 	 */
    136 	if (bp->b_flags & B_LOCKED) {
    137 		locked_queue_bytes -= bp->b_bcount;
    138 		--locked_queue_count;
    139 	}
    140 	if (TAILQ_NEXT(bp, b_freelist) == NULL) {
    141 		for (dp = bufqueues; dp < &bufqueues[BQUEUES]; dp++)
    142 			if (dp->tqh_last == &bp->b_freelist.tqe_next)
    143 				break;
    144 		if (dp == &bufqueues[BQUEUES])
    145 			errx(1, "bremfree: lost tail");
    146 	}
    147 	++bp->b_vp->v_usecount;
    148 	TAILQ_REMOVE(dp, bp, b_freelist);
    149 }
    150 
    151 /* Return a buffer if it is in the cache, otherwise return NULL. */
    152 struct ubuf *
    153 incore(struct uvnode * vp, int lbn)
    154 {
    155 	struct ubuf *bp;
    156 	int hash, depth;
    157 
    158 	hash = vl_hash(vp, lbn);
    159 	/* XXX use a real hash instead. */
    160 	depth = 0;
    161 	LIST_FOREACH(bp, &bufhash[hash], b_hash) {
    162 		if (++depth > hashmax)
    163 			hashmax = depth;
    164 		if (bp->b_vp == vp && bp->b_lblkno == lbn) {
    165 			return bp;
    166 		}
    167 	}
    168 	return NULL;
    169 }
    170 
    171 /*
    172  * Return a buffer of the given size, lbn and uvnode.
    173  * If none is in core, make a new one.
    174  */
    175 struct ubuf *
    176 getblk(struct uvnode * vp, daddr_t lbn, int size)
    177 {
    178 	struct ubuf *bp;
    179 #ifdef DEBUG
    180 	static int warned;
    181 #endif
    182 
    183 	/*
    184 	 * First check the buffer cache lists.
    185 	 */
    186 	if ((bp = incore(vp, lbn)) != NULL) {
    187 		assert(!(bp->b_flags & B_NEEDCOMMIT));
    188 		assert(!(bp->b_flags & B_BUSY));
    189 		assert(bp->b_bcount == size);
    190 		bp->b_flags |= B_BUSY;
    191 		bremfree(bp);
    192 		return bp;
    193 	}
    194 	/*
    195 	 * Not on the list.
    196 	 * Get a new block of the appropriate size and use that.
    197 	 * If not enough space, free blocks from the AGE and LRU lists
    198 	 * to make room.
    199 	 */
    200 	while (nbufs >= maxbufs + locked_queue_count) {
    201 		bp = TAILQ_FIRST(&bufqueues[BQ_AGE]);
    202 		if (bp)
    203 			TAILQ_REMOVE(&bufqueues[BQ_AGE], bp, b_freelist);
    204 		if (bp == NULL) {
    205 			bp = TAILQ_FIRST(&bufqueues[BQ_LRU]);
    206 			if (bp)
    207 				TAILQ_REMOVE(&bufqueues[BQ_LRU], bp,
    208 				    b_freelist);
    209 		}
    210 		if (bp) {
    211 			if (bp->b_flags & B_DELWRI)
    212 				VOP_STRATEGY(bp);
    213 			buf_destroy(bp);
    214 		}
    215 #ifdef DEBUG
    216 		else {
    217 			if (!warned) {
    218 				warnx("allocating more than %d buffers",
    219 					maxbufs);
    220 				++warned;
    221 			}
    222 			break;
    223 		}
    224 #endif
    225 	}
    226 	++nbufs;
    227 	bp = (struct ubuf *) malloc(sizeof(*bp));
    228 	memset(bp, 0, sizeof(*bp));
    229 	bp->b_data = malloc(size);
    230 	memset(bp->b_data, 0, size);
    231 
    232 	bp->b_vp = vp;
    233 	bp->b_blkno = bp->b_lblkno = lbn;
    234 	bp->b_bcount = size;
    235 	LIST_INSERT_HEAD(&bufhash[vl_hash(vp, lbn)], bp, b_hash);
    236 	LIST_INSERT_HEAD(&vp->v_cleanblkhd, bp, b_vnbufs);
    237 	bp->b_flags = B_BUSY;
    238 
    239 	return bp;
    240 }
    241 
    242 /* Write a buffer to disk according to its strategy routine. */
    243 void
    244 bwrite(struct ubuf * bp)
    245 {
    246 	bp->b_flags &= ~(B_READ | B_DONE | B_DELWRI | B_LOCKED);
    247 	VOP_STRATEGY(bp);
    248 	bp->b_flags |= B_DONE;
    249 	reassignbuf(bp, bp->b_vp);
    250 	brelse(bp);
    251 }
    252 
    253 /* Put a buffer back on its free list, clear B_BUSY. */
    254 void
    255 brelse(struct ubuf * bp)
    256 {
    257 	int age;
    258 
    259 	assert(!(bp->b_flags & B_NEEDCOMMIT));
    260 	assert(bp->b_flags & B_BUSY);
    261 
    262 	age = bp->b_flags & B_AGE;
    263 	bp->b_flags &= ~(B_BUSY | B_AGE);
    264 	if (bp->b_flags & B_INVAL) {
    265 		buf_destroy(bp);
    266 		return;
    267 	}
    268 	if (bp->b_flags & B_LOCKED) {
    269 		locked_queue_bytes += bp->b_bcount;
    270 		++locked_queue_count;
    271 		TAILQ_INSERT_TAIL(&bufqueues[BQ_LOCKED], bp, b_freelist);
    272 	} else if (age) {
    273 		TAILQ_INSERT_TAIL(&bufqueues[BQ_AGE], bp, b_freelist);
    274 	} else {
    275 		TAILQ_INSERT_TAIL(&bufqueues[BQ_LRU], bp, b_freelist);
    276 	}
    277 	--bp->b_vp->v_usecount;
    278 }
    279 
    280 /* Read the given block from disk, return it B_BUSY. */
    281 int
    282 bread(struct uvnode * vp, daddr_t lbn, int size, struct ucred * unused,
    283     struct ubuf ** bpp)
    284 {
    285 	struct ubuf *bp;
    286 	daddr_t daddr;
    287 	int error, count;
    288 
    289 	bp = getblk(vp, lbn, size);
    290 	*bpp = bp;
    291 	if (bp->b_flags & (B_DELWRI | B_DONE)) {
    292 		++cachehits;
    293 		return 0;
    294 	}
    295 	++cachemisses;
    296 
    297 	/*
    298 	 * Not found.  Need to find that block's location on disk,
    299 	 * and load it in.
    300 	 */
    301 	daddr = -1;
    302 	error = VOP_BMAP(vp, lbn, &daddr);
    303 	bp->b_blkno = daddr;
    304 	if (daddr >= 0) {
    305 		count = pread(vp->v_fd, bp->b_data, bp->b_bcount,
    306 				dbtob((off_t) daddr));
    307 		if (count == bp->b_bcount) {
    308 			bp->b_flags |= B_DONE;
    309 			return 0;
    310 		}
    311 		return -1;
    312 	}
    313 	memset(bp->b_data, 0, bp->b_bcount);
    314 	return 0;
    315 }
    316 
    317 /* Move a buffer between dirty and clean block lists. */
    318 void
    319 reassignbuf(struct ubuf * bp, struct uvnode * vp)
    320 {
    321 	LIST_REMOVE(bp, b_vnbufs);
    322 	if (bp->b_flags & B_DELWRI) {
    323 		LIST_INSERT_HEAD(&vp->v_dirtyblkhd, bp, b_vnbufs);
    324 	} else {
    325 		LIST_INSERT_HEAD(&vp->v_cleanblkhd, bp, b_vnbufs);
    326 	}
    327 }
    328 
    329 #ifdef DEBUG
    330 void
    331 dump_free_lists(void)
    332 {
    333 	struct ubuf *bp;
    334 	int i;
    335 
    336 	for (i = 0; i <= BQ_LOCKED; i++) {
    337 		printf("==> free list %d:\n", i);
    338 		TAILQ_FOREACH(bp, &bufqueues[i], b_freelist) {
    339 			printf("vp %p lbn %" PRId64 " flags %lx\n",
    340 				bp->b_vp, bp->b_lblkno, bp->b_flags);
    341 		}
    342 	}
    343 }
    344 #endif
    345