intel_iommu: refine iotlb hash calculation
PATCH 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
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 if possible
--- hw/i386/intel_iommu.c | 8 ++++---- hw/i386/intel_iommu_internal.h | 6 +++--- 2 files changed, 7 insertions(+), 7 deletions(-)
hw/i386/intel_iommu.c +4 -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);
@@ -222,9 +222,9 @@ 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 ; +return 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 ; }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 22 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 bitsSo this patch fixes them by
Quoted 8 lines
- 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_tif possibleFixes Coverity CID 1508100Fixes 1b2b12376c8 ("intel-iommu: PASID support")Signed-off-by Jason Wang <[email protected]>
thanks
-- PMM
Quoted 66 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 bitsSo 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_tif possibleFixes Coverity CID 1508100Fixes 1b2b12376c8 ("intel-iommu: PASID support")Signed-off-by Jason Wang <[email protected]>--- hw/i386/intel_iommu.c | 8 ++++---- hw/i386/intel_iommu_internal.h | 6 +++--- 2 files changed, 7 insertions(+), 7 deletions(-)hw/i386/intel_iommu.c +4
-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);@@ -222,9 +222,9 @@ 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 ; +return 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 ; }static gboolean vtd_as_equal (gconstpointer v1,gconstpointer v2)hw/i386/intel_iommu_internal.h +0
-0
hw/i386/intel_iommu_internal.h line 119
Quoted 9 lines
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
This is for the hash function only, IIUC it means anything over sizeof(guint) will be ignored and not contributing anything to the hash value being generated due to the uint64->guint conversion.
IOW, I think "level" and "pasid" will just be ignored.
If the whole point of hash function here is to try provide the best distribution of hash value generated for keys... perhaps we can cut some of the fields, but still we should fit all things into 32bits?
My wild guess is coverity complains mostly because of the shift overflow, so that'll be addressed too if we explicit cut things off with uint64_t.
Thanks,
Quoted 6 lines
hw/i386/intel_iommu_internal.h +0
-0#define VTD_IOTLB_MAX_SIZE 1024/* Max size of the hash table */ /* IOTLB_REG */ Signature · 1 line
2.25.1
Signature · 1 line
Peter Xu
Quoted 26 lines · Peter Xu
Quoted 9 lines · Jason Wang
hw/i386/intel_iommu.c +2
-3@@ -222,9 +222,9 @@ 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 ; +return key->gfn | ((uint64_t )(key->sid) <<VTD_IOTLB_SID_SHIFT ) | + (uint64_t)(key->level - 1) << VTD_IOTLB_LVL_SHIFT |hw/i386/intel_iommu.c static guint vtd_iotlb_hash(gconstpointer v)
Quoted 10 lines
hw/i386/intel_iommu.c +4
-3+ (uint64_t )(key->pasid) <<VTD_IOTLB_PASID_SHIFT ; }/* 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 44This is for the hash function only, IIUC it means anything over sizeof(guint) will be ignored and not contributing anything to the hash value being generated due to the
uint64->guintconversion.
Quoted 1 line
IOW, I think "level" and "pasid" will just be ignored.
Whoops, hadn't noticed that guint type... (glib's g_int64_hash()'s approach to this is to XOR the top 32 bits with the bottom 32 bits to produce the 32-bit hash value.)
Also, does anybody know what the requirements are on consistency between the hash_func and the key_equal_func for a GHashTable ? Is the hash_func supposed to return the same hash for every key that compares equal under key_equal_func ?
thanks
-- PMM
Quoted 34 lines · Peter Maydell
Quoted 26 lines · Peter Xu
Quoted 9 lines · Jason Wang
hw/i386/intel_iommu.c +2
-3@@ -222,9 +222,9 @@ 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 ; +return key->gfn | ((uint64_t )(key->sid) <<VTD_IOTLB_SID_SHIFT ) | + (uint64_t)(key->level - 1) << VTD_IOTLB_LVL_SHIFT |hw/i386/intel_iommu.c static guint vtd_iotlb_hash(gconstpointer v)
Quoted 10 lines
hw/i386/intel_iommu.c +4
-3+ (uint64_t )(key->pasid) <<VTD_IOTLB_PASID_SHIFT ; }/* 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 44This is for the hash function only, IIUC it means anything over sizeof(guint) will be ignored and not contributing anything to the hash value being generated due to the
uint64->guintconversion.Quoted 1 line
IOW, I think "level" and "pasid" will just be ignored.
Whoops, hadn't noticed that guint type... (glib's g_int64_hash()'s approach to this is to XOR the top 32 bits with the bottom 32 bits to produce the 32-bit hash value.)
Quoted 4 lines
Also, does anybody know what the requirements are on consistency between the
hash_funcand thekey_equal_funcfor a GHashTable ? Is thehash_funcsupposed to return the same hash for every key that compares equal underkey_equal_func?
I quickly checked up a local (but old) glib code (v2.71.0), and it seems this is the major place where key_equal_func() is used (also see the comment above the comparison):
g_hash_table_lookup_node()
{
...
/* We first check if our full hash values
* are equal so we can avoid calling the full-blown
* key equality function in most cases.
*/
if (node_hash == hash_value)
{
gpointer node_key = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys);
if (hash_table->key_equal_func)
{
if (hash_table->key_equal_func (node_key, key))
return node_index;
}
else if (node_key == key)
{
return node_index;
}
}...
}
I would guess hash_func() is only the fast version but if key_equal_func() is provided it'll be the final / most accurate way to tell whether two nodes are the same.
I assume from that POV the hash function should return the same value if key_equal_func() tells they're the same node.
Thanks,
Signature · 1 line
Peter Xu
Quoted 29 lines · Peter Xu
Quoted 27 lines · Peter Maydell
Quoted 26 lines · Peter Xu
Quoted 9 lines · Jason Wang
hw/i386/intel_iommu.c +2
-3@@ -222,9 +222,9 @@ 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 ; +return key->gfn | ((uint64_t )(key->sid) <<VTD_IOTLB_SID_SHIFT ) | + (uint64_t)(key->level - 1) << VTD_IOTLB_LVL_SHIFT |hw/i386/intel_iommu.c static guint vtd_iotlb_hash(gconstpointer v)
Quoted 10 lines
hw/i386/intel_iommu.c +4
-3+ (uint64_t )(key->pasid) <<VTD_IOTLB_PASID_SHIFT ; }/* 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 44This is for the hash function only, IIUC it means anything over sizeof(guint) will be ignored and not contributing anything to the hash value being generated due to the
uint64->guintconversion.
Quoted 7 lines
Quoted 7 lines
Quoted 1 line
IOW, I think "level" and "pasid" will just be ignored.
Whoops, hadn't noticed that guint type... (glib's g_int64_hash()'s approach to this is to XOR the top 32 bits with the bottom 32 bits to produce the 32-bit hash value.)
I will do this in next version.
Quoted 33 lines
Quoted 4 lines
Also, does anybody know what the requirements are on consistency between the
hash_funcand thekey_equal_funcfor a GHashTable ? Is thehash_funcsupposed to return the same hash for every key that compares equal underkey_equal_func?I quickly checked up a local (but old) glib code (v2.71.0), and it seems this is the major place where
key_equal_func()is used (also see the comment above the comparison):
g_hash_table_lookup_node()
{
.../* We first check if our full hash values * are equal so we can avoid calling the full-blown * key equality function in most cases. */ if (node_hash == hash_value) { gpointer node_key = g_hash_table_fetch_key_or_value (hash_table->keys, node_index, hash_table->have_big_keys); if (hash_table->key_equal_func) { if (hash_table->key_equal_func (node_key, key)) return node_index; } else if (node_key == key) { return node_index; } }...
}
Quoted 6 lines
I would guess
hash_func()is only the fast version but ifkey_equal_func()is provided it'll be the final / most accurate way to tell whether two nodes are the same.I assume from that POV the hash function should return the same value if
key_equal_func()tells they're the same node.
I think so.
Thanks
Quoted 6 lines
Thanks,
--
Peter Xu
Quoted 27 lines · Peter Maydell
Quoted 26 lines · Peter Xu
Quoted 9 lines · Jason Wang
hw/i386/intel_iommu.c +2
-3@@ -222,9 +222,9 @@ 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 ; +return key->gfn | ((uint64_t )(key->sid) <<VTD_IOTLB_SID_SHIFT ) | + (uint64_t)(key->level - 1) << VTD_IOTLB_LVL_SHIFT |hw/i386/intel_iommu.c static guint vtd_iotlb_hash(gconstpointer v)
Quoted 10 lines
hw/i386/intel_iommu.c +4
-3+ (uint64_t )(key->pasid) <<VTD_IOTLB_PASID_SHIFT ; }/* 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 44This is for the hash function only, IIUC it means anything over sizeof(guint) will be ignored and not contributing anything to the hash value being generated due to the
uint64->guintconversion.
Quoted 6 lines
Quoted 1 line
IOW, I think "level" and "pasid" will just be ignored.
Whoops, hadn't noticed that guint type... (glib's g_int64_hash()'s approach to this is to XOR the top 32 bits with the bottom 32 bits to produce the 32-bit hash value.)
This is less of a hash and more just concatting a bunch of fields. BTW if the glib built-in hash isn't suitable we also have the qemu_xxhash() functions which claim a good distribution of values and we use in a number of places throughout the code.
Quoted 7 lines
Also, does anybody know what the requirements are on consistency between the
hash_funcand thekey_equal_funcfor a GHashTable ? Is thehash_funcsupposed to return the same hash for every key that compares equal underkey_equal_func?thanks
-- PMM
Signature · 2 lines
Alex Bennée Virtualisation Tech Lead @ Linaro
Quoted 10 lines · Alex Bennée
Quoted 4 lines · Peter Maydell
Whoops, hadn't noticed that guint type... (glib's g_int64_hash()'s approach to this is to XOR the top 32 bits with the bottom 32 bits to produce the 32-bit hash value.)
This is less of a hash and more just concatting a bunch of fields. BTW if the glib built-in hash isn't suitable we also have the
qemu_xxhash()functions which claim a good distribution of values and we use in a number of places throughout the code.
Is that really necessary? If glib doesn't do anything complex for "my keys are just integers" I don't see that we need to do anything complex for "my keys are a handful of integers". glib does do a bit on its end to counteract suboptimal hash functions:
https://github.com/GNOME/glib/blob/main/glib/ghash.c#L429
static inline guintg_hash_table_hash_to_index (GHashTable *hash_table, guint hash) {
/* Multiply the hash by a small prime before applying the modulo. This
* prevents the table from becoming densely packed, even with a poor hash
* function. A densely packed table would have poor performance on
* workloads with many failed lookups or a high degree of churn. */
return (hash * 11) % hash_table->mod;
}
I figure if glib thought that users of hash tables should be doing more complex stuff then they would (a) provide helpers for that and (b) call it out in the docs. They don't do either.
thanks
-- PMM
Quoted 29 lines · Peter Maydell
Quoted 10 lines · Alex Bennée
Quoted 4 lines · Peter Maydell
Whoops, hadn't noticed that guint type... (glib's g_int64_hash()'s approach to this is to XOR the top 32 bits with the bottom 32 bits to produce the 32-bit hash value.)
This is less of a hash and more just concatting a bunch of fields. BTW if the glib built-in hash isn't suitable we also have the
qemu_xxhash()functions which claim a good distribution of values and we use in a number of places throughout the code.Is that really necessary? If glib doesn't do anything complex for "my keys are just integers" I don't see that we need to do anything complex for "my keys are a handful of integers". glib does do a bit on its end to counteract suboptimal hash functions:
https://github.com/GNOME/glib/blob/main/glib/ghash.c#L429
static inline guint
g_hash_table_hash_to_index(GHashTable*hash_table, guint hash) {
/* Multiply the hash by a small prime before applying the modulo. This
* prevents the table from becoming densely packed, even with a poor hash
* function. A densely packed table would have poor performance on
* workloads with many failed lookups or a high degree of churn. */
return (hash * 11) %hash_table->mod;
}
Quoted 3 lines
I figure if glib thought that users of hash tables should be doing more complex stuff then they would (a) provide helpers for that and (b) call it out in the docs. They don't do either.
Ahh I didn't realise glib was adding extra steps (although I guess it makes sense if it is resizing its tables) or that their default hash functions where so basic.
The original primary user of the qemu_xxhash functions is QHT which has to manage its own tables so relies more on having a well distributed hash function.
Signature · 2 lines
Alex Bennée Virtualisation Tech Lead @ Linaro