[patch] UFS inode hash chain conversion to SLIST

[Joe Talbott]

The attached patch is my attempt to convert the i_next field in struct
inode to an SLIST.  I'm not sure if I handled the initialization
correctly or if I handled the ilast part of ufs_ihashins() correctly.
It seems to me that a STAILQ may be a better choice since it seems
like all insertions are done on the tail of the list (queue).
Comments are welcome.

Thanks,
Joe
Index: sys/vfs/ufs/inode.h
===================================================================
RCS file: /home/dcvs/src/sys/vfs/ufs/inode.h,v
retrieving revision 1.12
diff -u -r1.12 inode.h
--- sys/vfs/ufs/inode.h	10 Sep 2006 01:26:41 -0000	1.12
+++ sys/vfs/ufs/inode.h	13 Jun 2007 00:29:28 -0000
@@ -81,7 +81,7 @@
  * active, and is put back when the file is no longer being used.
  */
 struct inode {
-	struct inode	*i_next;/* Hash chain */
+	SLIST_ENTRY(inode) i_next;/* Hash Chain */
 	struct	vnode  *i_vnode;/* Vnode associated with this inode. */
 	struct	vnode  *i_devvp;/* Vnode for block I/O. */
 	uint32_t i_flag;	/* flags, see below */
Index: sys/vfs/ufs/ufs_ihash.c
===================================================================
RCS file: /home/dcvs/src/sys/vfs/ufs/ufs_ihash.c,v
retrieving revision 1.20
diff -u -r1.20 ufs_ihash.c
--- sys/vfs/ufs/ufs_ihash.c	14 Oct 2006 16:26:40 -0000	1.20
+++ sys/vfs/ufs/ufs_ihash.c	13 Jun 2007 00:30:01 -0000
@@ -51,7 +51,10 @@
 /*
  * Structures associated with inode cacheing.
  */
-static struct inode **ihashtbl;
+
+SLIST_HEAD(ihashhead, inode) head = SLIST_HEAD_INITIALIZER(head);
+
+static struct ihashhead **ihashtbl;
 static u_long	ihash;		/* size of hash table - 1 */
 static struct lwkt_token ufs_ihash_token;
 
@@ -63,10 +66,20 @@
 void
 ufs_ihashinit(void)
 {
+	u_long i;
+	struct ihashhead *ihh;
+
 	ihash = 16;
 	while (ihash < desiredvnodes)
 		ihash <<= 1;
 	ihashtbl = kmalloc(sizeof(void *) * ihash, M_UFSIHASH, M_WAITOK|M_ZERO);
+	for (i = 0; i < ihash; i++)
+	{
+		ihh = kmalloc(sizeof(head),
+			      M_UFSIHASH, M_WAITOK|M_ZERO);
+		*(ihashtbl + i) = ihh;
+		SLIST_INIT(*(ihashtbl + i));
+	}
 	--ihash;
 	lwkt_token_init(&ufs_ihash_token);
 }
@@ -90,11 +103,13 @@
 struct vnode *
 ufs_ihashlookup(cdev_t dev, ino_t inum)
 {
+	struct ihashhead **ipp;
 	struct inode *ip;
 	lwkt_tokref ilock;
 
 	lwkt_gettoken(&ilock, &ufs_ihash_token);
-	for (ip = *INOHASH(dev, inum); ip; ip = ip->i_next) {
+	ipp = INOHASH(dev, inum);
+	SLIST_FOREACH(ip, *ipp, i_next) {
 		if (inum == ip->i_number && dev == ip->i_dev)
 			break;
 	}
@@ -117,12 +132,14 @@
 ufs_ihashget(cdev_t dev, ino_t inum)
 {
 	lwkt_tokref ilock;
+	struct ihashhead **ipp;
 	struct inode *ip;
 	struct vnode *vp;
 
 	lwkt_gettoken(&ilock, &ufs_ihash_token);
 loop:
-	for (ip = *INOHASH(dev, inum); ip; ip = ip->i_next) {
+	ipp = INOHASH(dev, inum);
+	SLIST_FOREACH(ip, *ipp, i_next) {
 		if (inum != ip->i_number || dev != ip->i_dev)
 			continue;
 		vp = ITOV(ip);
@@ -132,7 +149,8 @@
 		 * We must check to see if the inode has been ripped
 		 * out from under us after blocking.
 		 */
-		for (ip = *INOHASH(dev, inum); ip; ip = ip->i_next) {
+		ipp = INOHASH(dev, inum);
+		SLIST_FOREACH(ip, *ipp, i_next) {
 			if (inum == ip->i_number && dev == ip->i_dev)
 				break;
 		}
@@ -156,10 +174,12 @@
 ufs_ihashcheck(cdev_t dev, ino_t inum)
 {
 	lwkt_tokref ilock;
+	struct ihashhead **ipp;
 	struct inode *ip;
 
 	lwkt_gettoken(&ilock, &ufs_ihash_token);
-	for (ip = *INOHASH(dev, inum); ip; ip = ip->i_next) {
+	ipp = INOHASH(dev, inum);
+	SLIST_FOREACH(ip, *ipp, i_next) {
 		if (inum == ip->i_number && dev == ip->i_dev)
 			break;
 	}
@@ -173,22 +193,27 @@
 int
 ufs_ihashins(struct inode *ip)
 {
-	struct inode **ipp;
+	struct ihashhead **ipp;
 	struct inode *iq;
 	lwkt_tokref ilock;
+	struct inode *ilast;
 
 	KKASSERT((ip->i_flag & IN_HASHED) == 0);
 	lwkt_gettoken(&ilock, &ufs_ihash_token);
 	ipp = INOHASH(ip->i_dev, ip->i_number);
-	while ((iq = *ipp) != NULL) {
+	SLIST_FOREACH(iq, *ipp, i_next) {
 		if (ip->i_dev == iq->i_dev && ip->i_number == iq->i_number) {
 			lwkt_reltoken(&ilock);
 			return(EBUSY);
 		}
-		ipp = &iq->i_next;
+		if (SLIST_NEXT(iq, i_next) == NULL)
+			ilast = iq;
 	}
-	ip->i_next = NULL;
-	*ipp = ip;
+	if (SLIST_EMPTY(*ipp))
+		SLIST_INSERT_HEAD(*ipp, ip, i_next);
+	else
+		SLIST_INSERT_AFTER(ilast, ip, i_next);
+
 	ip->i_flag |= IN_HASHED;
 	lwkt_reltoken(&ilock);
 	return(0);
@@ -201,21 +226,20 @@
 ufs_ihashrem(struct inode *ip)
 {
 	lwkt_tokref ilock;
-	struct inode **ipp;
+	struct ihashhead **ipp;
 	struct inode *iq;
 
 	lwkt_gettoken(&ilock, &ufs_ihash_token);
 	if (ip->i_flag & IN_HASHED) {
 		ipp = INOHASH(ip->i_dev, ip->i_number);
-		while ((iq = *ipp) != NULL) {
+		SLIST_FOREACH(iq, *ipp, i_next)
+		{
 			if (ip == iq)
 				break;
-			ipp = &iq->i_next;
-		}
+		} 
 		KKASSERT(ip == iq);
-		*ipp = ip->i_next;
-		ip->i_next = NULL;
-		ip->i_flag &= ~IN_HASHED;
+		SLIST_REMOVE(*ipp, iq, inode, i_next);
+		iq->i_flag &= ~IN_HASHED;
 	}
 	lwkt_reltoken(&ilock);
 }