ia64/xen-unstable

view xen/include/xen/hash.h @ 19800:78962f85c562

IOMMU: Add two generic functions to vendor neutral interface

Add 2 generic functions into the vendor neutral iommu interface, The
reason is that from changeset 19732, there is only one global flag
"iommu_enabled" that controls iommu enablement for both vtd and amd
systems, so we need different code paths for vtd and amd iommu systems
if this flag has been turned on. Also, the early checking of
"iommu_enabled" in iommu_setup() is removed to prevent iommu
functionalities from been disabled on amd systems.

Signed-off-by: Wei Wang <wei.wang2@amd.com>
author Keir Fraser <keir.fraser@citrix.com>
date Fri Jun 19 08:41:50 2009 +0100 (2009-06-19)
parents f210a633571c
children
line source
1 #ifndef _XEN_HASH_H
2 #define _XEN_HASH_H
3 /* Fast hashing routine for a long.
4 (C) 2002 William Lee Irwin III, IBM */
6 /*
7 * Knuth recommends primes in approximately golden ratio to the maximum
8 * integer representable by a machine word for multiplicative hashing.
9 * Chuck Lever verified the effectiveness of this technique:
10 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
11 *
12 * These primes are chosen to be bit-sparse, that is operations on
13 * them can use shifts and additions instead of multiplications for
14 * machines where multiplications are slow.
15 */
16 #if BITS_PER_LONG == 32
17 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
18 #define GOLDEN_RATIO_PRIME 0x9e370001UL
19 #elif BITS_PER_LONG == 64
20 /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
21 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
22 #else
23 #error Define GOLDEN_RATIO_PRIME for your wordsize.
24 #endif
26 static inline unsigned long hash_long(unsigned long val, unsigned int bits)
27 {
28 unsigned long hash = val;
30 #if BITS_PER_LONG == 64
31 /* Sigh, gcc can't optimise this alone like it does for 32 bits. */
32 unsigned long n = hash;
33 n <<= 18;
34 hash -= n;
35 n <<= 33;
36 hash -= n;
37 n <<= 3;
38 hash += n;
39 n <<= 3;
40 hash -= n;
41 n <<= 4;
42 hash += n;
43 n <<= 2;
44 hash += n;
45 #else
46 /* On some cpus multiply is faster, on others gcc will do shifts */
47 hash *= GOLDEN_RATIO_PRIME;
48 #endif
50 /* High bits are more random, so use them. */
51 return hash >> (BITS_PER_LONG - bits);
52 }
54 static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
55 {
56 return hash_long((unsigned long)ptr, bits);
57 }
58 #endif /* _XEN_HASH_H */