intel_iommu: refine iotlb hash calculation
PATCH v2 1/1 intel_iommu: refine iotlb hash calculation
Commit 1b2b12376c8 ("intel-iommu: PASID support") takes PASID into account when calculating iotlb hash like:
static guint vtd_iotlb_hash(gconstpointer v)
{
const struct vtd_iotlb_key *key = v;
return key->gfn | ((key->sid) << VTD_IOTLB_SID_SHIFT) |
(key->level) << VTD_IOTLB_LVL_SHIFT |
(key->pasid) << VTD_IOTLB_PASID_SHIFT;
}This turns out to be problematic since:
- the shift will lose bits if not converting to uint64_t
- level should be off by one in order to fit into 2 bits
- VTD_IOTLB_PASID_SHIFT is 30 but PASID is 20 bits which will waste some bits
- the hash result is uint64_t so we will lose bits when converting to guint
So this patch fixes them by
- converting the keys into uint64_t before doing the shift
- off level by one to make it fit into two bits
- change the sid, lvl and pasid shift to 26, 42 and 44 in order to take the full width of uint64_t
- perform an XOR to the top 32bit with the bottom 32bit for the final result to fit guint
---
Changes since V1:
- perform XOR to avoid losing bits when converting to gint
--- hw/i386/intel_iommu.c | 9 +++++---- hw/i386/intel_iommu_internal.h | 6 +++--- 2 files changed, 8 insertions(+), 7 deletions(-)
hw/i386/intel_iommu.c +5 -4
@@ -64,8 +64,8 @@ struct vtd_as_key {struct vtd_iotlb_key {uint64_t gfn;uint32_t pasid; -uint32_t level;uint16_t sid; +uint8_t level; };static void vtd_address_space_refresh_all (IntelIOMMUState *s);
@@ -221,10 +221,11 @@ static gboolean vtd_iotlb_equal(gconstpointer v1, gconstpointer v2)static guint vtd_iotlb_hash (gconstpointer v) {const struct vtd_iotlb_key *key = v; +uint64_t hash64 = key->gfn | ((uint64_t )(key->sid) <<VTD_IOTLB_SID_SHIFT ) | + (uint64_t )(key->level -1 ) <<VTD_IOTLB_LVL_SHIFT | + (uint64_t )(key->pasid) <<VTD_IOTLB_PASID_SHIFT ; -return key->gfn | ((key->sid) <<VTD_IOTLB_SID_SHIFT ) | - (key->level) <<VTD_IOTLB_LVL_SHIFT | - (key->pasid) <<VTD_IOTLB_PASID_SHIFT ; +return (guint)((hash64 >>32 ) ^ (hash64 &0xffffffffU )); }static gboolean vtd_as_equal (gconstpointer v1,gconstpointer v2)
hw/i386/intel_iommu_internal.h +3 -3
@@ -114,9 +114,9 @@ VTD_INTERRUPT_ADDR_FIRST + 1)/* The shift of source_id in the key of IOTLB hash table */ -#define VTD_IOTLB_SID_SHIFT 20 -#define VTD_IOTLB_LVL_SHIFT 28 -#define VTD_IOTLB_PASID_SHIFT 30 +#define VTD_IOTLB_SID_SHIFT 26 +#define VTD_IOTLB_LVL_SHIFT 42 +#define VTD_IOTLB_PASID_SHIFT 44#define VTD_IOTLB_MAX_SIZE 1024/* Max size of the hash table */ /* IOTLB_REG */
Signature · 1 line
2.25.1
Quoted 57 lines · Jason Wang
Commit
1b2b12376c8("intel-iommu: PASID support") takes PASID into account when calculating iotlb hash like:static guint
vtd_iotlb_hash(gconstpointer v){ const struct vtd_iotlb_key *key = v; return key->gfn | ((key->sid) << VTD_IOTLB_SID_SHIFT) | (key->level) << VTD_IOTLB_LVL_SHIFT | (key->pasid) << VTD_IOTLB_PASID_SHIFT; }This turns out to be problematic since:
- the shift will lose bits if not converting to
uint64_t
- level should be off by one in order to fit into 2 bits
-VTD_IOTLB_PASID_SHIFTis 30 but PASID is 20 bits which will waste some bits
- the hash result isuint64_tso we will lose bits when converting to guintSo this patch fixes them by
- converting the keys into
uint64_tbefore doing the shift
- off level by one to make it fit into two bits
- change the sid, lvl and pasid shift to 26, 42 and 44 in order to take the full width ofuint64_t
- perform an XOR to the top 32bit with the bottom 32bit for the final result to fit guintFixes Coverity CID 1508100Fixes 1b2b12376c8 ("intel-iommu: PASID support")Signed-off-by Jason Wang <[email protected]>---
Changes since V1:
- perform XOR to avoid losing bits when converting to gint--- hw/i386/intel_iommu.c | 9 +++++---- hw/i386/intel_iommu_internal.h | 6 +++--- 2 files changed, 8 insertions(+), 7 deletions(-)hw/i386/intel_iommu.c +1
-1@@ -64,8 +64,8 @@ struct vtd_as_key {struct vtd_iotlb_key {uint64_t gfn;uint32_t pasid; -uint32_t level;uint16_t sid; +uint8_t level; };static void vtd_address_space_refresh_all (IntelIOMMUState *s);@@ -221,10 +221,11 @@ static gboolean vtd_iotlb_equal(gconstpointer v1, gconstpointer v2)static guint vtd_iotlb_hash (gconstpointer v)
hw/i386/intel_iommu.c static gboolean vtd_iotlb_equal(gconstpointer v1, gconstpointer v2) · line 228
Quoted 10 lines
hw/i386/intel_iommu.c +4
-3{const struct vtd_iotlb_key *key = v; +uint64_t hash64 = key->gfn | ((uint64_t )(key->sid) <<VTD_IOTLB_SID_SHIFT ) | + (uint64_t )(key->level -1 ) <<VTD_IOTLB_LVL_SHIFT | + (uint64_t )(key->pasid) <<VTD_IOTLB_PASID_SHIFT ; -return key->gfn | ((key->sid) <<VTD_IOTLB_SID_SHIFT ) | - (key->level) <<VTD_IOTLB_LVL_SHIFT | - (key->pasid) <<VTD_IOTLB_PASID_SHIFT ; +return (guint)((hash64 >>32 ) ^ (hash64 &0xffffffffU ));
Have you measured the distribution this hash gives you? Otherwise consider using the qemu_xxhash() functions to return a well distributed 32 bit hash value.
Signature · 2 lines
Alex Bennée Virtualisation Tech Lead @ Linaro
Quoted 67 lines · Alex Bennée
Quoted 63 lines · Jason Wang
Commit
1b2b12376c8("intel-iommu: PASID support") takes PASID into account when calculating iotlb hash like:static guint
vtd_iotlb_hash(gconstpointer v){ const struct vtd_iotlb_key *key = v; return key->gfn | ((key->sid) << VTD_IOTLB_SID_SHIFT) | (key->level) << VTD_IOTLB_LVL_SHIFT | (key->pasid) << VTD_IOTLB_PASID_SHIFT; }This turns out to be problematic since:
- the shift will lose bits if not converting to
uint64_t
- level should be off by one in order to fit into 2 bits
-VTD_IOTLB_PASID_SHIFTis 30 but PASID is 20 bits which will waste some bits
- the hash result isuint64_tso we will lose bits when converting to guintSo this patch fixes them by
- converting the keys into
uint64_tbefore doing the shift
- off level by one to make it fit into two bits
- change the sid, lvl and pasid shift to 26, 42 and 44 in order to take the full width ofuint64_t
- perform an XOR to the top 32bit with the bottom 32bit for the final result to fit guintFixes Coverity CID 1508100Fixes 1b2b12376c8 ("intel-iommu: PASID support")Signed-off-by Jason Wang <[email protected]>---
Changes since V1:
- perform XOR to avoid losing bits when converting to gint--- hw/i386/intel_iommu.c | 9 +++++---- hw/i386/intel_iommu_internal.h | 6 +++--- 2 files changed, 8 insertions(+), 7 deletions(-)hw/i386/intel_iommu.c +4
-1@@ -64,8 +64,8 @@ struct vtd_as_key {struct vtd_iotlb_key {uint64_t gfn;uint32_t pasid; -uint32_t level;uint16_t sid; +uint8_t level; };static void vtd_address_space_refresh_all (IntelIOMMUState *s);@@ -221,10 +221,11 @@ static gboolean vtd_iotlb_equal(gconstpointer v1, gconstpointer v2)static guint vtd_iotlb_hash (gconstpointer v) {const struct vtd_iotlb_key *key = v; +uint64_t hash64 = key->gfn | ((uint64_t )(key->sid) <<VTD_IOTLB_SID_SHIFT ) | + (uint64_t )(key->level -1 ) <<VTD_IOTLB_LVL_SHIFT | + (uint64_t )(key->pasid) <<VTD_IOTLB_PASID_SHIFT ;
Quoted 8 lines
hw/i386/intel_iommu.c static gboolean vtd_iotlb_equal(gconstpointer v1, gconstpointer v2) · line 228
Quoted 4 lines
hw/i386/intel_iommu.c +1
-3-return key->gfn | ((key->sid) <<VTD_IOTLB_SID_SHIFT ) | - (key->level) <<VTD_IOTLB_LVL_SHIFT | - (key->pasid) <<VTD_IOTLB_PASID_SHIFT ; +return (guint)((hash64 >>32 ) ^ (hash64 &0xffffffffU ));Have you measured the distribution this hash gives you? Otherwise consider using the
qemu_xxhash()functions to return a well distributed 32 bit hash value.
It depends on a lot of factors and so it won't be even because the individuals keys are not evenly distributed:
- gfn depends on guest DMA subsystems
- level depends on when huge pages are used
- pasid depends on whether PASID is being used
I'm ok to switch to use qemu_xxhash() if everyone agree. Or if as Peter said, if it has been dealt with glibc, maybe it's not worth to bother.
Thanks
Quoted 5 lines
--
Alex Bennée
Virtualisation Tech Lead @ Linaro
Quoted 80 lines · Jason Wang
Quoted 67 lines · Alex Bennée
Quoted 63 lines · Jason Wang
Commit
1b2b12376c8("intel-iommu: PASID support") takes PASID into account when calculating iotlb hash like:static guint
vtd_iotlb_hash(gconstpointer v){ const struct vtd_iotlb_key *key = v; return key->gfn | ((key->sid) << VTD_IOTLB_SID_SHIFT) | (key->level) << VTD_IOTLB_LVL_SHIFT | (key->pasid) << VTD_IOTLB_PASID_SHIFT; }This turns out to be problematic since:
- the shift will lose bits if not converting to
uint64_t
- level should be off by one in order to fit into 2 bits
-VTD_IOTLB_PASID_SHIFTis 30 but PASID is 20 bits which will waste some bits
- the hash result isuint64_tso we will lose bits when converting to guintSo this patch fixes them by
- converting the keys into
uint64_tbefore doing the shift
- off level by one to make it fit into two bits
- change the sid, lvl and pasid shift to 26, 42 and 44 in order to take the full width ofuint64_t
- perform an XOR to the top 32bit with the bottom 32bit for the final result to fit guintFixes Coverity CID 1508100Fixes 1b2b12376c8 ("intel-iommu: PASID support")Signed-off-by Jason Wang <[email protected]>---
Changes since V1:
- perform XOR to avoid losing bits when converting to gint--- hw/i386/intel_iommu.c | 9 +++++---- hw/i386/intel_iommu_internal.h | 6 +++--- 2 files changed, 8 insertions(+), 7 deletions(-)hw/i386/intel_iommu.c +4
-1@@ -64,8 +64,8 @@ struct vtd_as_key {struct vtd_iotlb_key {uint64_t gfn;uint32_t pasid; -uint32_t level;uint16_t sid; +uint8_t level; };static void vtd_address_space_refresh_all (IntelIOMMUState *s);@@ -221,10 +221,11 @@ static gboolean vtd_iotlb_equal(gconstpointer v1, gconstpointer v2)static guint vtd_iotlb_hash (gconstpointer v) {const struct vtd_iotlb_key *key = v; +uint64_t hash64 = key->gfn | ((uint64_t )(key->sid) <<VTD_IOTLB_SID_SHIFT ) | + (uint64_t )(key->level -1 ) <<VTD_IOTLB_LVL_SHIFT | + (uint64_t )(key->pasid) <<VTD_IOTLB_PASID_SHIFT ;Quoted 8 lines
hw/i386/intel_iommu.c static gboolean vtd_iotlb_equal(gconstpointer v1, gconstpointer v2) · line 228
Quoted 4 lines
hw/i386/intel_iommu.c +1
-3-return key->gfn | ((key->sid) <<VTD_IOTLB_SID_SHIFT ) | - (key->level) <<VTD_IOTLB_LVL_SHIFT | - (key->pasid) <<VTD_IOTLB_PASID_SHIFT ; +return (guint)((hash64 >>32 ) ^ (hash64 &0xffffffffU ));Have you measured the distribution this hash gives you? Otherwise consider using the
qemu_xxhash()functions to return a well distributed 32 bit hash value.It depends on a lot of factors and so it won't be even because the individuals keys are not evenly distributed:
Quoted 7 lines
- gfn depends on guest DMA subsystems
- level depends on when huge pages are used
- pasid depends on whether PASID is being usedI'm ok to switch to use
qemu_xxhash()if everyone agree. Or if as Peter said, if it has been dealt with glibc, maybe it's not worth to bother.
Yeah I missed that glibs default hash functions where pretty basic. I think you can ignore my suggestion.
Quoted 8 lines
Thanks
Quoted 5 lines
--
Alex Bennée
Virtualisation Tech Lead @ Linaro
Signature · 2 lines
Alex Bennée Virtualisation Tech Lead @ Linaro
Quoted 30 lines · Jason Wang
Commit
1b2b12376c8("intel-iommu: PASID support") takes PASID into account when calculating iotlb hash like:static guint
vtd_iotlb_hash(gconstpointer v){ const struct vtd_iotlb_key *key = v; return key->gfn | ((key->sid) << VTD_IOTLB_SID_SHIFT) | (key->level) << VTD_IOTLB_LVL_SHIFT | (key->pasid) << VTD_IOTLB_PASID_SHIFT; }This turns out to be problematic since:
- the shift will lose bits if not converting to
uint64_t
- level should be off by one in order to fit into 2 bits
-VTD_IOTLB_PASID_SHIFTis 30 but PASID is 20 bits which will waste some bits
- the hash result isuint64_tso we will lose bits when converting to guintSo this patch fixes them by
- converting the keys into
uint64_tbefore doing the shift
- off level by one to make it fit into two bits
- change the sid, lvl and pasid shift to 26, 42 and 44 in order to take the full width ofuint64_t
- perform an XOR to the top 32bit with the bottom 32bit for the final result to fit guint
Quoted 3 lines
Fixes Coverity CID 1508100Fixes 1b2b12376c8 ("intel-iommu: PASID support")Signed-off-by Jason Wang <[email protected]>
Signature · 1 line
Peter Xu