Skip to contentSkip to conversation

intel_iommu: refine iotlb hash calculation

PATCH Superseded Jason Wang 4 participants 9 messages Apr 10, 2023 – Apr 13, 2023

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Jason Wang

author
#0 lore raw

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

Fixes Coverity CID 1508100
Fixes 1b2b12376c8 ("intel-iommu: PASID support")
---
 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
index a62896759c..d394976e9b 100644
@@ -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
index f090e61e11..2e61eec2f5 100644
@@ -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
Reviewed-by on v1 1/1
#1 lore raw
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_SHIFT is 30 but PASID is 20 bits which will waste some bits

So this patch fixes them by

Quoted 8 lines

- 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

Fixes Coverity CID 1508100
Fixes 1b2b12376c8 ("intel-iommu: PASID support")

thanks
-- PMM

#2 lore raw
In reply to Jason Wang
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_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

Fixes Coverity CID 1508100
Fixes 1b2b12376c8 ("intel-iommu: PASID support")
---
 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
index a62896759c..d394976e9b 100644
@@ -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
index f090e61e11..2e61eec2f5 100644

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
#3 lore raw
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       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.

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

#4 lore raw
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       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.

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_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 ?

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
author
#5 lore raw
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       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.

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_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 ?

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 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.

I think so.

Thanks

Quoted 6 lines

Thanks,

--
Peter Xu

#6 lore raw
In reply to Peter Maydell
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       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.

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_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

Signature · 2 lines
Alex Bennée
Virtualisation Tech Lead @ Linaro
#7 lore raw
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;
}

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

#8 lore raw
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