[stgt] [PATCH 3/3] Replace hash-of-lists (cmd_hash_list) with a list (cmd_list)
Andy Grover
agrover at redhat.com
Tue Sep 27 21:21:32 CEST 2011
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 at redhat.com>
---
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 at vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
More information about the stgt
mailing list