Re: [patch] nfsd optimizations for test10

Re: [patch] nfsd optimizations for test10

[Ying Chen/Almaden/IBM]

 1/ Do you have any stats showing what sort of speedup this gives -
    I'm curious.


I don't have the exact timing stats to show the improvements, but I do have
some stats that I gathered when running SPEC SFS.
Basically with the default racache scheme which only keeps 80 entries in
the table (if I remember the # right), since SPEC SFS works on a lot of
files, I can see that shortly after the SPEC SFS test gets started, the
table is filled up, and nfsd_get_raparam() will never insert any other ra
values to the table, i.e., the racache hit ratio is always 0 for the SPEC
SFS runs, and yet each time when it's called, it scans the entire table
once, i.e., 80 table entries. On the other hand, when hash table is used,
on average, the old files can be removes and new entries can be added
dynamically, so the hit ratio improves and even if there isn't a hit, the
hash chain search is far more better than a table scan. On average, at most
a few list walk will suffice.


 2/ Was there a particular reason that you didn't use the
      include/linux/list.h
    list structures for the hash and lru chains?  If not, I suggest
    that doing so would be a good idea.  It should make the code
    clearer and more in-keeping with other code in the kernel.

No there isn't. Oh, well, maybe there is... I used nfscache.c as the base
when I built racache, which didn't use list.h.
Having said that, I just did not try hard to make the kernel more
consistant.

 3/ It is easiest for (many of) us if you just include the patch
    in-line in your email messages rather than as an attachment.   You
    can then be sure that EVERY mail reader can display it
    effectively, and Linus has said a number of times that he doesn't
    like attachments.
 3a/ If you or your mailer insists on using attachments, please make
    sure that the mime-type of the attachment is correct - text/plain,
    not applications/x-unknown.  Again, that makes it a lot easier to
    read your patch.

No problem with this. I will do that for the future patches.

 4/ I doubt that this is significant enough to go in before 2.4.0-final
now,
    but it probably has a reasonable chance of getting in shortly
    afterwards.

I really hope that this can go into 2.4, since the changes are really
straight-forward and I've been testing and running this under a wide range
of situations for a couple months in my own patched kernels. I probably
should have sent it a bit earlier. Oh, well.


NeilBrown
knfsd maintainer.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/



-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: [patch] nfsd optimizations for test10

[Neil Brown]

On Friday November 10, ying@almaden.ibm.com wrote:
> Hi,
> 
> I made some optimizations on racache in nfsd in test10. The idea is to
> replace with existing fixed length table for readahead cache in NFSD with a
> hash table.
> The old racache is essentially ineffective in dealing with large # of
> files, and yet eats CPU cycles in scanning the table (even though the table
> is small),
> the hash table-based is much more effective and fast. I have generated the
> patch for test10 and tested it.
> 
> (See attached file: nfshdiff)(See attached file: nfsdiff)
> 
> 
> Ying

Thanks for this.
A couple of questions and comments:

 1/ Do you have any stats showing what sort of speedup this gives -
    I'm curious.

 2/ Was there a particular reason that you didn't use the
      include/linux/list.h
    list structures for the hash and lru chains?  If not, I suggest
    that doing so would be a good idea.  It should make the code
    clearer and more in-keeping with other code in the kernel.

 3/ It is easiest for (many of) us if you just include the patch
    in-line in your email messages rather than as an attachment.   You
    can then be sure that EVERY mail reader can display it
    effectively, and Linus has said a number of times that he doesn't
    like attachments.
 3a/ If you or your mailer insists on using attachments, please make
    sure that the mime-type of the attachment is correct - text/plain,
    not applications/x-unknown.  Again, that makes it a lot easier to
    read your patch.

 4/ I doubt that this is significant enough to go in before 2.4.0-final now,
    but it probably has a reasonable chance of getting in shortly
    afterwards.

NeilBrown
knfsd maintainer.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

[patch] nfsd optimizations for test10

[Ying Chen/Almaden/IBM]

[-- Attachment #1: Type: text/plain, Size: 493 bytes --]

Hi,

I made some optimizations on racache in nfsd in test10. The idea is to
replace with existing fixed length table for readahead cache in NFSD with a
hash table.
The old racache is essentially ineffective in dealing with large # of
files, and yet eats CPU cycles in scanning the table (even though the table
is small),
the hash table-based is much more effective and fast. I have generated the
patch for test10 and tested it.

(See attached file: nfshdiff)(See attached file: nfsdiff)


Ying

[-- Attachment #2: nfshdiff --]
[-- Type: application/octet-stream, Size: 2210 bytes --]

diff -ruN nfsd.orig/nfsd.h nfsd.opt/nfsd.h
--- nfsd.orig/nfsd.h	Fri Nov 10 15:27:37 2000
+++ nfsd.opt/nfsd.h	Fri Nov 10 16:03:43 2000
@@ -76,7 +76,7 @@
 
 /* nfsd/vfs.c */
 int		fh_lock_parent(struct svc_fh *, struct dentry *);
-int		nfsd_racache_init(int);
+int		nfsd_racache_init(void);
 void		nfsd_racache_shutdown(void);
 int		nfsd_lookup(struct svc_rqst *, struct svc_fh *,
 				const char *, int, struct svc_fh *);
diff -ruN nfsd.orig/racache.h nfsd.opt/racache.h
--- nfsd.orig/racache.h	Fri Nov 10 16:10:23 2000
+++ nfsd.opt/racache.h	Fri Nov 10 15:50:49 2000
@@ -0,0 +1,43 @@
+/*
+ * include/linux/nfsd/racache.h
+ *
+ * Read ahead racache. 
+ */
+
+#ifndef NFSRACACHE_H
+#define NFSRACACHE_H
+
+#ifdef __KERNEL__
+#include <linux/sched.h>
+
+/*
+ * This is a cache of readahead params that help us choose the proper
+ * readahead strategy. Initially, we set all readahead parameters to 0
+ * and let the VFS handle things.
+ * If you increase the number of cached files very much, you'll need to
+ * add a hash table here.
+ */
+/*
+ * Representation of an racache entry. The first two members *must*
+ * be hash_next and hash_prev.
+ */
+struct raparms {
+	struct raparms		*p_hash_next;
+	struct raparms		*p_hash_prev;
+	struct raparms		*p_lru_next;
+	struct raparms		*p_lru_prev;
+	ino_t			p_ino;
+	dev_t			p_dev;
+	unsigned long		p_reada,
+				p_ramax,
+				p_raend,
+				p_ralen,
+				p_rawin;
+};
+
+int nfsd_racache_init(void);
+void	nfsd_racache_shutdown(void);
+struct raparms *nfsd_get_raparms(dev_t , ino_t );
+
+#endif /* __KERNEL__ */
+#endif /* NFSRACACHE_H */
diff -ruN nfsd.orig/stats.h nfsd.opt/stats.h
--- nfsd.orig/stats.h	Tue Jul 18 23:04:06 2000
+++ nfsd.opt/stats.h	Fri Nov 10 15:51:52 2000
@@ -25,8 +25,8 @@
 					 * of available threads were in use */
 	unsigned int	th_fullcnt;	/* number of times last free thread was used */
 	unsigned int	ra_size;	/* size of ra cache */
-	unsigned int	ra_depth[11];	/* number of times ra entry was found that deep
-					 * in the cache (10percentiles). [10] = not found */
+	unsigned int	ra_hits;	/* ra cache hits */
+	unsigned int	ra_misses;	/* ra cache misses */
 };
 
 /* thread usage wraps very million seconds (approx one fortnight) */

[-- Attachment #3: nfsdiff --]
[-- Type: application/octet-stream, Size: 11428 bytes --]

diff -ruN nfsd.orig/Makefile nfsd.opt/Makefile
--- nfsd.orig/Makefile	Wed Dec  8 15:17:55 1999
+++ nfsd.opt/Makefile	Fri Nov 10 17:10:56 2000
@@ -9,7 +9,7 @@
 
 O_TARGET := nfsd.o
 O_OBJS   := nfssvc.o nfsctl.o nfsproc.o nfsfh.o vfs.o \
-	    export.o auth.o lockd.o nfscache.o nfsxdr.o \
+	    export.o auth.o lockd.o nfscache.o nfsracache.o nfsxdr.o \
 	    stats.o
 ifdef CONFIG_NFSD_V3
   O_OBJS += nfs3proc.o nfs3xdr.o
diff -ruN nfsd.orig/nfsracache.c nfsd.opt/nfsracache.c
--- nfsd.orig/nfsracache.c	Wed Dec 31 16:00:00 1969
+++ nfsd.opt/nfsracache.c	Fri Nov 10 17:00:53 2000
@@ -0,0 +1,233 @@
+/*
+ * linux/fs/nfsd/nfsracache.c
+ *
+ * NFSD racache. 
+ */
+
+#include <linux/kernel.h>
+#include <linux/sched.h>
+#include <linux/malloc.h>
+#include <linux/string.h>
+
+#include <linux/sunrpc/svc.h>
+#include <linux/nfsd/nfsd.h>
+#include <linux/nfsd/racache.h>
+
+#define CACHESIZE		2048
+#define HASHSIZE		512
+#define REQHASH(ino, dev)	((((ino) >> 24) ^ (ino) ^ (dev)) & (HASHSIZE-1))
+
+spinlock_t racache_lock = SPIN_LOCK_UNLOCKED;
+
+/*
+ * The position of the pointers are important. Don't change it without knowing what
+ * you are doing. 
+ */
+struct racache_head {
+	struct raparms *	next;
+	struct raparms *	prev;
+};
+
+static struct raparms *		raparm_cache = NULL;
+static struct racache_head *	hash_list;
+
+static struct raparms *	lru_head = NULL;
+static struct raparms *	lru_tail = NULL;
+static struct raparms *	free_head;
+static struct raparms *	free_tail;
+
+int
+nfsd_racache_init(void)
+{
+	struct raparms	*rp;
+	struct racache_head	*rahead;
+	size_t			i;
+	unsigned long		order;
+
+	lru_head = NULL;
+	lru_tail = NULL;
+	i = CACHESIZE * sizeof (struct raparms);
+	for (order = 0; (PAGE_SIZE << order) < i; order++)
+		;
+	raparm_cache = (struct raparms *)
+		__get_free_pages(GFP_KERNEL, order);
+	if (!raparm_cache) {
+		printk (KERN_ERR "nfsd: cannot allocate %Zd bytes for racache\n", i);
+		return -1;
+	}
+	memset(raparm_cache, 0, i);
+
+	i = HASHSIZE * sizeof (struct racache_head);
+	hash_list = kmalloc (i, GFP_KERNEL);
+	if (!hash_list) {
+		free_pages ((unsigned long)raparm_cache, order);
+		raparm_cache = NULL;
+		printk (KERN_ERR "nfsd: cannot allocate %Zd bytes for hash list in racache\n", i);
+		return -1;
+	}
+
+	spin_lock(&racache_lock); 
+	for (i = 0, rahead = hash_list; i < HASHSIZE; i++, rahead++)
+		rahead->next = rahead->prev = (struct raparms *) rahead;
+
+	for (i = 0, rp = raparm_cache; i < CACHESIZE; i++, rp++) {
+		rp->p_hash_next = rp->p_hash_prev = rp;
+		rp->p_lru_next = rp + 1;
+		rp->p_lru_prev = rp - 1;
+	}
+	free_head = raparm_cache;
+	free_tail = raparm_cache + CACHESIZE - 1;
+	free_head->p_lru_prev = NULL;
+	free_tail->p_lru_next = NULL;
+	spin_unlock(&racache_lock); 
+
+	nfsdstats.ra_size = CACHESIZE;
+	return 0;
+}
+
+void
+nfsd_racache_shutdown(void)
+{
+	size_t			i;
+	unsigned long		order;
+
+	i = CACHESIZE * sizeof (struct raparms);
+	for (order = 0; (PAGE_SIZE << order) < i; order++)
+		;
+	spin_lock(&racache_lock); 
+	free_pages ((unsigned long)raparm_cache, order);
+	raparm_cache = NULL;
+	kfree (hash_list);
+	hash_list = NULL;
+	spin_unlock(&racache_lock); 
+}
+
+/*
+ * Move cache entry from LRU list to front of LRU list
+ */
+static void
+lru_put_front(struct raparms *rp)
+{
+	struct raparms	*prev = rp->p_lru_prev,
+				*next = rp->p_lru_next;
+
+	if (prev)
+		prev->p_lru_next = next;
+	else
+		return;
+	if (next)
+		next->p_lru_prev = prev;
+	else
+		lru_tail = prev;
+
+	rp->p_lru_next = lru_head;
+	rp->p_lru_prev = NULL;
+	lru_head->p_lru_prev = rp;
+	lru_head = rp;
+}
+
+/*
+ * Move cache entry from the free list to front of LRU list
+ */
+static void
+lru_insert_front(struct raparms *rp)
+{
+	rp->p_lru_prev = NULL;
+	rp->p_lru_next = lru_head;
+	if (lru_head)
+		lru_head->p_lru_prev = rp;
+	lru_head = rp;
+	if (!lru_tail)
+		lru_tail = rp;
+}
+
+/*
+ * Move cache entry from the free list to front of LRU list
+ * Meanwhile, remove it from the hash list also.
+ */
+static struct raparms *lru_remove_item(struct raparms *item)
+{
+	struct raparms	*rp;
+	struct raparms	*prev; 
+	struct raparms	*next; 
+
+	rp = item->p_lru_prev;
+	if (item != lru_head) {
+		rp->p_lru_next = item->p_lru_next;
+		if (rp->p_lru_next) 
+			rp->p_lru_next->p_lru_prev = rp;
+	} else {
+		lru_head = item->p_lru_next;
+		if (lru_head) 
+			lru_head->p_lru_prev = NULL;
+	}
+	item->p_lru_prev = NULL;
+	item->p_lru_next = NULL;
+	if (item == lru_tail)
+		lru_tail = rp;
+	prev = item->p_hash_prev,
+	next = item->p_hash_next;
+	prev->p_hash_next = next;
+	next->p_hash_prev = prev;
+	item->p_hash_next = NULL;
+	item->p_hash_prev = NULL;
+
+	return item;
+}
+
+
+static inline struct raparms	*
+nfsd_racache_insert(ino_t ino, dev_t dev)
+{
+	struct raparms	*ra = NULL;
+	struct racache_head *rap;
+
+	if (!free_head) {
+		/* Replace with LRU. */
+		if (lru_tail) 
+			ra = lru_remove_item(lru_tail);
+	} else {
+		ra = free_head;
+		free_head = free_head->p_lru_next; 
+	}
+	memset(ra, 0, sizeof(*ra));
+	ra->p_dev = dev;
+	ra->p_ino = ino;
+	rap = (struct racache_head *) &hash_list[REQHASH(ino, dev)];
+	ra->p_hash_next = rap->next;
+	ra->p_hash_prev = (struct raparms *) rap;
+	rap->next->p_hash_prev = ra;
+	rap->next = ra;
+
+	lru_insert_front(ra);
+	return ra;
+}
+
+/*
+ * Try to find an entry matching the current call in the cache. When none
+ * is found, we grab the oldest unlocked entry off the LRU list.
+ * Note that no operation within the loop may sleep.
+ */
+struct raparms *
+nfsd_get_raparms(dev_t dev, ino_t ino)
+{
+	struct raparms	*rahead;
+	struct raparms	*ra = NULL;
+
+	spin_lock(&racache_lock);
+
+	ra = rahead = (struct raparms *) &hash_list[REQHASH(ino, dev)];
+	while ((ra = ra->p_hash_next) != rahead) {
+	     	if ((ra->p_ino == ino) && (ra->p_dev == dev)) { 
+			lru_put_front(ra);
+			nfsdstats.ra_hits++;
+			goto found;
+		}
+	}
+	/* Did not find one. Get a new item and insert it into the hash table. */
+	ra = nfsd_racache_insert(ino, dev);
+	nfsdstats.ra_misses++;
+found:
+	spin_unlock(&racache_lock);
+	return ra;
+}
diff -ruN nfsd.orig/nfssvc.c nfsd.opt/nfssvc.c
--- nfsd.orig/nfssvc.c	Sun Oct  1 20:35:16 2000
+++ nfsd.opt/nfssvc.c	Fri Nov 10 17:03:09 2000
@@ -43,7 +43,7 @@
 static void			nfsd(struct svc_rqst *rqstp);
 struct timeval			nfssvc_boot;
 static struct svc_serv 		*nfsd_serv;
-static int			nfsd_busy;
+static atomic_t			nfsd_busy;
 static unsigned long		nfsd_last_call;
 
 struct nfsd_list {
@@ -72,7 +72,7 @@
 		nrservs = NFSD_MAXSERVS;
 	
 	/* Readahead param cache - will no-op if it already exists */
-	error =	nfsd_racache_init(2*nrservs);
+	error =	nfsd_racache_init();
 	if (error<0)
 		goto out;
 	if (!nfsd_serv) {
@@ -185,8 +185,8 @@
 		    ;
 		if (err < 0)
 			break;
-		update_thread_usage(nfsd_busy);
-		nfsd_busy++;
+		update_thread_usage(atomic_read(&nfsd_busy));
+		atomic_inc(&nfsd_busy);
 
 		/* Lock the export hash tables for reading. */
 		exp_readlock();
@@ -205,8 +205,8 @@
 
 		/* Unlock export hash tables */
 		exp_unlock();
-		update_thread_usage(nfsd_busy);
-		nfsd_busy--;
+		update_thread_usage(atomic_read(&nfsd_busy));
+		atomic_dec(&nfsd_busy);
 	}
 
 	if (err != -EINTR) {
diff -ruN nfsd.orig/stats.c nfsd.opt/stats.c
--- nfsd.orig/stats.c	Tue Jul 18 23:04:06 2000
+++ nfsd.opt/stats.c	Fri Nov 10 17:04:52 2000
@@ -15,9 +15,8 @@
  *	th <threads> <fullcnt> <10%-20%> <20%-30%> ... <90%-100%> <100%> 
  *			time (seconds) when nfsd thread usage above thresholds
  *			and number of times that all threads were in use
- *	ra cache-size  <10%  <20%  <30% ... <100% not-found
- *			number of times that read-ahead entry was found that deep in
- *			the cache.
+ *	ra cache-size  <racache-size> <hits> <misses> 
+			racache size, hits, and misses
  *	plus generic RPC stats (see net/sunrpc/stats.c)
  *
  * Copyright (C) 1995, 1996, 1997 Olaf Kirch <okir@monad.swb.de>
@@ -65,11 +64,8 @@
 	}
 
 	/* newline and ra-cache */
-	len += sprintf(buffer+len, "\nra %u", nfsdstats.ra_size);
-	for (i=0; i<11; i++)
-		len += sprintf(buffer+len, " %u", nfsdstats.ra_depth[i]);
-	len += sprintf(buffer+len, "\n");
-	
+	len += sprintf(buffer+len, "\nra %u %u %u\n", nfsdstats.ra_size, 
+			nfsdstats.ra_hits, nfsdstats.ra_misses);
 
 	/* Assume we haven't hit EOF yet. Will be set by svc_proc_read. */
 	*eof = 0;
diff -ruN nfsd.orig/vfs.c nfsd.opt/vfs.c
--- nfsd.orig/vfs.c	Mon Oct 16 12:58:51 2000
+++ nfsd.opt/vfs.c	Fri Nov 10 17:09:23 2000
@@ -36,6 +36,7 @@
 
 #include <linux/sunrpc/svc.h>
 #include <linux/nfsd/nfsd.h>
+#include <linux/nfsd/racache.h>
 #ifdef CONFIG_NFSD_V3
 #include <linux/nfs3.h>
 #include <linux/nfsd/xdr3.h>
@@ -56,28 +57,6 @@
 #define IS_ISMNDLK(i)	(S_ISREG((i)->i_mode) && MANDATORY_LOCK(i))
 
 /*
- * This is a cache of readahead params that help us choose the proper
- * readahead strategy. Initially, we set all readahead parameters to 0
- * and let the VFS handle things.
- * If you increase the number of cached files very much, you'll need to
- * add a hash table here.
- */
-struct raparms {
-	struct raparms		*p_next;
-	unsigned int		p_count;
-	ino_t			p_ino;
-	dev_t			p_dev;
-	unsigned long		p_reada,
-				p_ramax,
-				p_raend,
-				p_ralen,
-				p_rawin;
-};
-
-static struct raparms *		raparml;
-static struct raparms *		raparm_cache;
-
-/*
  * Look up one component of a pathname.
  * N.B. After this call _both_ fhp and resfh need an fh_put
  *
@@ -540,42 +519,6 @@
 }
 
 /*
- * Obtain the readahead parameters for the file
- * specified by (dev, ino).
- */
-static inline struct raparms *
-nfsd_get_raparms(dev_t dev, ino_t ino)
-{
-	struct raparms	*ra, **rap, **frap = NULL;
-	int depth = 0;
-	
-	for (rap = &raparm_cache; (ra = *rap); rap = &ra->p_next) {
-		if (ra->p_ino == ino && ra->p_dev == dev)
-			goto found;
-		depth++;
-		if (ra->p_count == 0)
-			frap = rap;
-	}
-	depth = nfsdstats.ra_size*11/10;
-	if (!frap)
-		return NULL;
-	rap = frap;
-	ra = *frap;
-	memset(ra, 0, sizeof(*ra));
-	ra->p_dev = dev;
-	ra->p_ino = ino;
-found:
-	if (rap != &raparm_cache) {
-		*rap = ra->p_next;
-		ra->p_next   = raparm_cache;
-		raparm_cache = ra;
-	}
-	ra->p_count++;
-	nfsdstats.ra_depth[depth*10/nfsdstats.ra_size]++;
-	return ra;
-}
-
-/*
  * Read data from a file. count must contain the requested read count
  * on entry. On return, *count contains the number of bytes actually read.
  * N.B. After this call fhp needs an fh_put
@@ -626,7 +569,6 @@
 		ra->p_raend = file.f_raend;
 		ra->p_ralen = file.f_ralen;
 		ra->p_rawin = file.f_rawin;
-		ra->p_count -= 1;
 	}
 
 	if (err >= 0) {
@@ -1546,42 +1488,4 @@
 		err = permission(inode, MAY_EXEC);
 
 	return err? nfserrno(err) : 0;
-}
-
-void
-nfsd_racache_shutdown(void)
-{
-	if (!raparm_cache)
-		return;
-	dprintk("nfsd: freeing readahead buffers.\n");
-	kfree(raparml);
-	raparm_cache = raparml = NULL;
-}
-/*
- * Initialize readahead param cache
- */
-int
-nfsd_racache_init(int cache_size)
-{
-	int	i;
-
-	if (raparm_cache)
-		return 0;
-	raparml = kmalloc(sizeof(struct raparms) * cache_size, GFP_KERNEL);
-
-	if (raparml != NULL) {
-		dprintk("nfsd: allocating %d readahead buffers.\n",
-			cache_size);
-		memset(raparml, 0, sizeof(struct raparms) * cache_size);
-		for (i = 0; i < cache_size - 1; i++) {
-			raparml[i].p_next = raparml + i + 1;
-		}
-		raparm_cache = raparml;
-	} else {
-		printk(KERN_WARNING
-		       "nfsd: Could not allocate memory read-ahead cache.\n");
-		return -ENOMEM;
-	}
-	nfsdstats.ra_size = cache_size;
-	return 0;
 }