Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/sbin/fsck_lfs Be more efficient with the hash tables for the...
details: https://anonhg.NetBSD.org/src/rev/7e35c00cac16
branches: trunk
changeset: 580133:7e35c00cac16
user: perseant <perseant%NetBSD.org@localhost>
date: Mon Apr 11 23:19:24 2005 +0000
description:
Be more efficient with the hash tables for the buffer and vnode caches.
Note that roll-forward can add more inodes to the filesystem; don't overflow
the tables but reallocate them.
diffstat:
sbin/fsck_lfs/bufcache.c | 81 ++++++++++++++++++++++++++++++++++++++++-------
sbin/fsck_lfs/bufcache.h | 6 ++-
sbin/fsck_lfs/fsck.h | 3 +-
sbin/fsck_lfs/lfs.c | 11 ++++--
sbin/fsck_lfs/pass0.c | 9 ++++-
sbin/fsck_lfs/pass2.c | 5 ++-
sbin/fsck_lfs/pass5.c | 4 +-
sbin/fsck_lfs/pass6.c | 17 +++++----
sbin/fsck_lfs/setup.c | 34 +++++++++++++++++--
sbin/fsck_lfs/vnode.c | 20 ++++++++--
sbin/fsck_lfs/vnode.h | 6 ++-
11 files changed, 155 insertions(+), 41 deletions(-)
diffs (truncated from 531 to 300 lines):
diff -r c1a61156f72d -r 7e35c00cac16 sbin/fsck_lfs/bufcache.c
--- a/sbin/fsck_lfs/bufcache.c Mon Apr 11 22:42:47 2005 +0000
+++ b/sbin/fsck_lfs/bufcache.c Mon Apr 11 23:19:24 2005 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: bufcache.c,v 1.5 2005/04/06 02:38:17 perseant Exp $ */
+/* $NetBSD: bufcache.c,v 1.6 2005/04/11 23:19:24 perseant Exp $ */
/*-
* Copyright (c) 2003 The NetBSD Foundation, Inc.
* All rights reserved.
@@ -63,15 +63,17 @@
TAILQ_HEAD(bqueues, ubuf) bufqueues[BQUEUES];
-#define HASH_MAX 101
+struct bufhash_struct *bufhash;
-struct bufhash_struct bufhash[HASH_MAX];
+#define HASH_MAX 1024
+int hashmax = HASH_MAX;
+int hashmask = (HASH_MAX - 1);
int maxbufs = BUF_CACHE_SIZE;
int nbufs = 0;
int cachehits = 0;
int cachemisses = 0;
-int hashmax = 0;
+int max_depth = 0;
off_t locked_queue_bytes = 0;
int locked_queue_count = 0;
@@ -79,30 +81,76 @@
static int
vl_hash(struct uvnode * vp, daddr_t lbn)
{
- return (int)((unsigned long) vp + lbn) % HASH_MAX;
+ return (int)((unsigned long) vp + lbn) & hashmask;
}
/* Initialize buffer cache */
void
-bufinit(void)
+bufinit(int max)
{
int i;
+ if (max) {
+ for (hashmax = 1; hashmax < max; hashmax <<= 1)
+ ;
+ hashmask = hashmax - 1;
+ }
+
for (i = 0; i < BQUEUES; i++) {
TAILQ_INIT(&bufqueues[i]);
}
- for (i = 0; i < HASH_MAX; i++)
+ bufhash = (struct bufhash_struct *)malloc(hashmax * sizeof(*bufhash));
+ for (i = 0; i < hashmax; i++)
LIST_INIT(&bufhash[i]);
}
+/* Widen the hash table. */
+void bufrehash(int max)
+{
+ int i, newhashmax, newhashmask;
+ struct ubuf *bp, *nbp;
+ struct bufhash_struct *np;
+
+ if (max < 0 || max < hashmax)
+ return;
+
+ /* Round up to a power of two */
+ for (newhashmax = 1; newhashmax < max; newhashmax <<= 1)
+ ;
+ newhashmask = newhashmax - 1;
+
+ /* Allocate new empty hash table */
+ np = (struct bufhash_struct *)malloc(newhashmax * sizeof(*bufhash));
+ for (i = 0; i < newhashmax; i++)
+ LIST_INIT(&np[i]);
+
+ /* Now reassign all existing buffers to their new hash chains. */
+ for (i = 0; i < hashmax; i++) {
+ bp = LIST_FIRST(&bufhash[i]);
+ while(bp) {
+ nbp = LIST_NEXT(bp, b_hash);
+ LIST_REMOVE(bp, b_hash);
+ bp->b_hashval = vl_hash(bp->b_vp, bp->b_lblkno);
+ LIST_INSERT_HEAD(&np[bp->b_hashval], bp, b_hash);
+ bp = nbp;
+ }
+ }
+
+ /* Switch over and clean up */
+ free(bufhash);
+ bufhash = np;
+ hashmax = newhashmax;
+ hashmask = newhashmask;
+}
+
/* Print statistics of buffer cache usage */
void
bufstats(void)
{
- printf("buffer cache: %d hits %d misses (%2.2f%%); hash depth %d\n",
+ printf("buffer cache: %d hits %d misses (%2.2f%%); hash width %d, depth %d\n",
cachehits, cachemisses,
(cachehits * 100.0) / (cachehits + cachemisses),
- hashmax);
+ hashmax, max_depth);
}
/*
@@ -159,8 +207,9 @@
/* XXX use a real hash instead. */
depth = 0;
LIST_FOREACH(bp, &bufhash[hash], b_hash) {
- if (++depth > hashmax)
- hashmax = depth;
+ if (++depth > max_depth)
+ max_depth = depth;
+ assert(depth <= nbufs);
if (bp->b_vp == vp && bp->b_lblkno == lbn) {
return bp;
}
@@ -223,6 +272,7 @@
if (bp->b_flags & B_DELWRI)
VOP_STRATEGY(bp);
buf_destroy(bp);
+ break;
}
#ifdef DEBUG
else {
@@ -244,7 +294,8 @@
bp->b_vp = vp;
bp->b_blkno = bp->b_lblkno = lbn;
bp->b_bcount = size;
- LIST_INSERT_HEAD(&bufhash[vl_hash(vp, lbn)], bp, b_hash);
+ bp->b_hashval = vl_hash(vp, lbn);
+ LIST_INSERT_HEAD(&bufhash[bp->b_hashval], bp, b_hash);
LIST_INSERT_HEAD(&vp->v_cleanblkhd, bp, b_vnbufs);
bp->b_flags = B_BUSY;
@@ -287,6 +338,12 @@
TAILQ_INSERT_TAIL(&bufqueues[BQ_LRU], bp, b_freelist);
}
--bp->b_vp->v_usecount;
+
+ /* Move to the front of the hash chain */
+ if (LIST_FIRST(&bufhash[bp->b_hashval]) != bp) {
+ LIST_REMOVE(bp, b_hash);
+ LIST_INSERT_HEAD(&bufhash[bp->b_hashval], bp, b_hash);
+ }
}
/* Read the given block from disk, return it B_BUSY. */
diff -r c1a61156f72d -r 7e35c00cac16 sbin/fsck_lfs/bufcache.h
--- a/sbin/fsck_lfs/bufcache.h Mon Apr 11 22:42:47 2005 +0000
+++ b/sbin/fsck_lfs/bufcache.h Mon Apr 11 23:19:24 2005 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: bufcache.h,v 1.3 2005/02/26 05:45:54 perseant Exp $ */
+/* $NetBSD: bufcache.h,v 1.4 2005/04/11 23:19:24 perseant Exp $ */
/*-
* Copyright (c) 1999, 2000 The NetBSD Foundation, Inc.
@@ -89,6 +89,7 @@
daddr_t b_lblkno; /* Logical block number. */
daddr_t b_blkno; /* Underlying physical block number */
struct uvnode *b_vp; /* File vnode. */
+ int b_hashval; /* Hash value */
};
#define b_bufsize b_bcount
@@ -109,7 +110,8 @@
LIST_HEAD(bufhash_struct, ubuf);
-void bufinit(void);
+void bufinit(int);
+void bufrehash(int);
void bufstats(void);
void buf_destroy(struct ubuf *);
void bremfree(struct ubuf *);
diff -r c1a61156f72d -r 7e35c00cac16 sbin/fsck_lfs/fsck.h
--- a/sbin/fsck_lfs/fsck.h Mon Apr 11 22:42:47 2005 +0000
+++ b/sbin/fsck_lfs/fsck.h Mon Apr 11 23:19:24 2005 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: fsck.h,v 1.13 2004/07/18 20:51:30 yamt Exp $ */
+/* $NetBSD: fsck.h,v 1.14 2005/04/11 23:19:24 perseant Exp $ */
/*-
* Copyright (c) 1997 The NetBSD Foundation, Inc.
@@ -213,5 +213,6 @@
struct inoinfo *getinoinfo(ino_t);
daddr_t lfs_ino_daddr(ino_t);
void clearinode(ino_t);
+void reset_maxino(ino_t);
#include "fsck_vars.h"
diff -r c1a61156f72d -r 7e35c00cac16 sbin/fsck_lfs/lfs.c
--- a/sbin/fsck_lfs/lfs.c Mon Apr 11 22:42:47 2005 +0000
+++ b/sbin/fsck_lfs/lfs.c Mon Apr 11 23:19:24 2005 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: lfs.c,v 1.9 2005/03/25 20:16:37 perseant Exp $ */
+/* $NetBSD: lfs.c,v 1.10 2005/04/11 23:19:24 perseant Exp $ */
/*-
* Copyright (c) 2003 The NetBSD Foundation, Inc.
* All rights reserved.
@@ -104,7 +104,7 @@
extern void pwarn(const char *, ...);
extern struct uvnodelst vnodelist;
-extern struct uvnodelst getvnodelist;
+extern struct uvnodelst getvnodelist[VNODE_HASH_MAX];
extern int nvnodes;
int fsdirty = 0;
@@ -341,7 +341,7 @@
struct inode *ip;
struct ufs1_dinode *dip;
struct ubuf *bp;
- int i;
+ int i, hash;
vp = (struct uvnode *) malloc(sizeof(*vp));
memset(vp, 0, sizeof(*vp));
@@ -406,7 +406,8 @@
ip->i_lfs_fragsize[i] = blksize(fs, ip, i);
++nvnodes;
- LIST_INSERT_HEAD(&getvnodelist, vp, v_getvnodes);
+ hash = ((int)fs + ino) & (VNODE_HASH_MAX - 1);
+ LIST_INSERT_HEAD(&getvnodelist[hash], vp, v_getvnodes);
LIST_INSERT_HEAD(&vnodelist, vp, v_mntvnodes);
return vp;
@@ -548,6 +549,8 @@
if (idaddr == 0)
idaddr = fs->lfs_idaddr;
+ else
+ fs->lfs_idaddr = idaddr;
/* NB: If dummy_read!=0, idaddr==0 here so we get a fake inode. */
fs->lfs_ivnode = lfs_raw_vget(fs,
(dummy_read ? LFS_IFILE_INUM : fs->lfs_ifile), devvp->v_fd,
diff -r c1a61156f72d -r 7e35c00cac16 sbin/fsck_lfs/pass0.c
--- a/sbin/fsck_lfs/pass0.c Mon Apr 11 22:42:47 2005 +0000
+++ b/sbin/fsck_lfs/pass0.c Mon Apr 11 23:19:24 2005 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: pass0.c,v 1.19 2005/03/25 20:14:43 perseant Exp $ */
+/* $NetBSD: pass0.c,v 1.20 2005/04/11 23:19:24 perseant Exp $ */
/*-
* Copyright (c) 1999, 2000, 2001, 2002, 2003 The NetBSD Foundation, Inc.
@@ -89,6 +89,7 @@
#include "fsutil.h"
extern int fake_cleanseg;
+int extend_ifile(void);
/*
* Pass 0. Check the LFS partial segments for valid checksums, correcting
@@ -266,6 +267,12 @@
else
brelse(bp);
+ if (fs->lfs_freehd == 0) {
+ pwarn("%sree list head is 0x0\n", preen ? "f" : "F");
+ if (preen || reply("FIX"))
+ extend_ifile();
+ }
+
/*
* Check the distance between sequential free list entries.
* An ideally ordered free list will have the sum of these
diff -r c1a61156f72d -r 7e35c00cac16 sbin/fsck_lfs/pass2.c
--- a/sbin/fsck_lfs/pass2.c Mon Apr 11 22:42:47 2005 +0000
+++ b/sbin/fsck_lfs/pass2.c Mon Apr 11 23:19:24 2005 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: pass2.c,v 1.12 2005/02/06 06:13:47 perry Exp $ */
+/* $NetBSD: pass2.c,v 1.13 2005/04/11 23:19:24 perseant Exp $ */
/*
* Copyright (c) 1980, 1986, 1993
@@ -410,6 +410,9 @@
if (dirp->d_type != typemap[dirp->d_ino]) {
fileerror(idesc->id_number, dirp->d_ino,
"BAD TYPE VALUE");
+ if (debug)
+ pwarn("dir has %d, typemap has %d\n",
+ dirp->d_type, typemap[dirp->d_ino]);
dirp->d_type = typemap[dirp->d_ino];
if (reply("FIX") == 1)
ret |= ALTERED;
diff -r c1a61156f72d -r 7e35c00cac16 sbin/fsck_lfs/pass5.c
--- a/sbin/fsck_lfs/pass5.c Mon Apr 11 22:42:47 2005 +0000
+++ b/sbin/fsck_lfs/pass5.c Mon Apr 11 23:19:24 2005 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: pass5.c,v 1.14 2005/01/19 19:41:59 xtraeme Exp $ */
+/* $NetBSD: pass5.c,v 1.15 2005/04/11 23:19:24 perseant Exp $ */
Home |
Main Index |
Thread Index |
Old Index