[PATCH 3/3] Replace hash-of-lists (cmd_hash_list) with a list (cmd_list)

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



It doesn't appear hashing the commands on an it_nexus is a benefit.
Both it_nexus_destroy and abort_task_set iterate across all lists
in the hash, which is equivalent to iterating through the list. Insertion
and removal from the list remains O(1).

Signed-off-by: Andy Grover <agrover@xxxxxxxxxx>
---
 usr/hash.h   |   58 ----------------------------------------------------------
 usr/target.c |   35 ++++++++++++++---------------------
 usr/target.h |    7 +------
 3 files changed, 15 insertions(+), 85 deletions(-)
 delete mode 100644 usr/hash.h

diff --git a/usr/hash.h b/usr/hash.h
deleted file mode 100644
index cf42d8a..0000000
--- a/usr/hash.h
+++ /dev/null
@@ -1,58 +0,0 @@
-#ifndef _LINUX_HASH_H
-#define _LINUX_HASH_H
-/* Fast hashing routine for a long.
-   (C) 2002 William Lee Irwin III, IBM */
-
-/*
- * Knuth recommends primes in approximately golden ratio to the maximum
- * integer representable by a machine word for multiplicative hashing.
- * Chuck Lever verified the effectiveness of this technique:
- * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
- *
- * These primes are chosen to be bit-sparse, that is operations on
- * them can use shifts and additions instead of multiplications for
- * machines where multiplications are slow.
- */
-#if BITS_PER_LONG == 32
-/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
-#define GOLDEN_RATIO_PRIME 0x9e370001UL
-#elif BITS_PER_LONG == 64
-/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
-#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
-#else
-#error Define GOLDEN_RATIO_PRIME for your wordsize.
-#endif
-
-static inline unsigned long hash_long(unsigned long val, unsigned int bits)
-{
-	unsigned long hash = val;
-
-#if BITS_PER_LONG == 64
-	/*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
-	unsigned long n = hash;
-	n <<= 18;
-	hash -= n;
-	n <<= 33;
-	hash -= n;
-	n <<= 3;
-	hash += n;
-	n <<= 3;
-	hash -= n;
-	n <<= 4;
-	hash += n;
-	n <<= 2;
-	hash += n;
-#else
-	/* On some cpus multiply is faster, on others gcc will do shifts */
-	hash *= GOLDEN_RATIO_PRIME;
-#endif
-
-	/* High bits are more random, so use them. */
-	return hash >> (BITS_PER_LONG - bits);
-}
-
-static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
-{
-	return hash_long((unsigned long)ptr, bits);
-}
-#endif /* _LINUX_HASH_H */
diff --git a/usr/target.c b/usr/target.c
index 3651767..5a8dfa6 100644
--- a/usr/target.c
+++ b/usr/target.c
@@ -263,7 +263,7 @@ void ua_sense_add_it_nexus(uint64_t itn_id, struct scsi_lu *lu,
 
 int it_nexus_create(int tid, uint64_t itn_id, int host_no, char *info)
 {
-	int i, ret;
+	int ret;
 	struct target *target;
 	struct it_nexus *itn;
 	struct scsi_lu *lu;
@@ -308,8 +308,7 @@ int it_nexus_create(int tid, uint64_t itn_id, int host_no, char *info)
 			 &itn->it_nexus_lu_info_list);
 	}
 
-	for (i = 0; i < ARRAY_SIZE(itn->cmd_hash_list); i++)
-		INIT_LIST_HEAD(&itn->cmd_hash_list[i]);
+	INIT_LIST_HEAD(&itn->cmd_list);
 
 	list_add_tail(&itn->nexus_siblings, &target->it_nexus_list);
 
@@ -321,7 +320,6 @@ out:
 
 int it_nexus_destroy(int tid, uint64_t itn_id)
 {
-	int i;
 	struct it_nexus *itn;
 	struct scsi_lu *lu;
 
@@ -331,9 +329,8 @@ int it_nexus_destroy(int tid, uint64_t itn_id)
 	if (!itn)
 		return -ENOENT;
 
-	for (i = 0; i < ARRAY_SIZE(itn->cmd_hash_list); i++)
-		if (!list_empty(&itn->cmd_hash_list[i]))
-			return -EBUSY;
+	if (!list_empty(&itn->cmd_list))
+		return -EBUSY;
 
 	list_for_each_entry(lu, &itn->nexus_target->device_list, device_siblings)
 		device_release(tid, itn_id, lu->lun, 0);
@@ -357,8 +354,7 @@ static struct scsi_lu *device_lookup(struct target *target, uint64_t lun)
 
 static void cmd_hlist_insert(struct it_nexus *itn, struct scsi_cmd *cmd)
 {
-	struct list_head *list = &itn->cmd_hash_list[hashfn(cmd->tag)];
-	list_add(&cmd->c_hlist, list);
+	list_add(&cmd->c_hlist, &itn->cmd_list);
 }
 
 static void cmd_hlist_remove(struct scsi_cmd *cmd)
@@ -1109,22 +1105,19 @@ static int abort_task_set(struct mgmt_req *mreq, struct target* target,
 {
 	struct scsi_cmd *cmd, *tmp;
 	struct it_nexus *itn;
-	int i, err, count = 0;
+	int err, count = 0;
 
 	eprintf("found %" PRIx64 " %d\n", tag, all);
 
 	list_for_each_entry(itn, &target->it_nexus_list, nexus_siblings) {
-		for (i = 0; i < ARRAY_SIZE(itn->cmd_hash_list); i++) {
-			struct list_head *list = &itn->cmd_hash_list[i];
-			list_for_each_entry_safe(cmd, tmp, list, c_hlist) {
-				if ((all && itn->itn_id == itn_id) ||
-				    (cmd->tag == tag && itn->itn_id == itn_id) ||
-				    (lun && !memcmp(cmd->lun, lun, sizeof(cmd->lun)))) {
-					err = abort_cmd(target, mreq, cmd);
-					if (err)
-						mreq->busy++;
-					count++;
-				}
+		list_for_each_entry_safe(cmd, tmp, &itn->cmd_list, c_hlist) {
+			if ((all && itn->itn_id == itn_id) ||
+			    (cmd->tag == tag && itn->itn_id == itn_id) ||
+			    (lun && !memcmp(cmd->lun, lun, sizeof(cmd->lun)))) {
+				err = abort_cmd(target, mreq, cmd);
+				if (err)
+					mreq->busy++;
+				count++;
 			}
 		}
 	}
diff --git a/usr/target.h b/usr/target.h
index f1e51f3..ba03f3c 100644
--- a/usr/target.h
+++ b/usr/target.h
@@ -2,11 +2,6 @@
 #define __TARGET_H__
 
 #include <limits.h>
-#define BITS_PER_LONG (ULONG_MAX == 0xFFFFFFFFUL ? 32 : 64)
-#include "hash.h"
-
-#define	HASH_ORDER	4
-#define	hashfn(val)	hash_long((unsigned long) (val), HASH_ORDER)
 
 struct acl_entry {
 	char *address;
@@ -52,7 +47,7 @@ struct it_nexus {
 	uint64_t itn_id;
 	long ctime;
 
-	struct list_head cmd_hash_list[1 << HASH_ORDER];
+	struct list_head cmd_list;
 
 	struct target *nexus_target;
 
-- 
1.7.1

--
To unsubscribe from this list: send the line "unsubscribe stgt" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html


[Index of Archives]     [Linux SCSI]     [Linux RAID]     [Linux Clusters]     [Linux USB Devel]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]

  Powered by Linux