hw/i386/intel_iommu.c | 8 ++++---- hw/i386/intel_iommu_internal.h | 6 +++--- 2 files changed, 7 insertions(+), 7 deletions(-)
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")
Signed-off-by: Jason Wang <jasowang@redhat.com>
---
hw/i386/intel_iommu.c | 8 ++++----
hw/i386/intel_iommu_internal.h | 6 +++---
2 files changed, 7 insertions(+), 7 deletions(-)
diff --git a/hw/i386/intel_iommu.c b/hw/i386/intel_iommu.c
index a62896759c..d394976e9b 100644
--- a/hw/i386/intel_iommu.c
+++ b/hw/i386/intel_iommu.c
@@ -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)
diff --git a/hw/i386/intel_iommu_internal.h b/hw/i386/intel_iommu_internal.h
index f090e61e11..2e61eec2f5 100644
--- a/hw/i386/intel_iommu_internal.h
+++ b/hw/i386/intel_iommu_internal.h
@@ -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 */
--
2.25.1On Mon, Apr 10, 2023 at 11:32:08AM +0800, Jason Wang wrote:
> 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")
> Signed-off-by: Jason Wang <jasowang@redhat.com>
> ---
> hw/i386/intel_iommu.c | 8 ++++----
> hw/i386/intel_iommu_internal.h | 6 +++---
> 2 files changed, 7 insertions(+), 7 deletions(-)
>
> diff --git a/hw/i386/intel_iommu.c b/hw/i386/intel_iommu.c
> index a62896759c..d394976e9b 100644
> --- a/hw/i386/intel_iommu.c
> +++ b/hw/i386/intel_iommu.c
> @@ -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)
> diff --git a/hw/i386/intel_iommu_internal.h b/hw/i386/intel_iommu_internal.h
> index f090e61e11..2e61eec2f5 100644
> --- a/hw/i386/intel_iommu_internal.h
> +++ b/hw/i386/intel_iommu_internal.h
> @@ -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,
> #define VTD_IOTLB_MAX_SIZE 1024 /* Max size of the hash table */
>
> /* IOTLB_REG */
> --
> 2.25.1
>
--
Peter Xu
On Tue, 11 Apr 2023 at 15:14, Peter Xu <peterx@redhat.com> wrote:
>
> On Mon, Apr 10, 2023 at 11:32:08AM +0800, Jason Wang wrote:
> > @@ -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;
> > }
> > /* 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.
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
Peter Maydell <peter.maydell@linaro.org> writes:
> On Tue, 11 Apr 2023 at 15:14, Peter Xu <peterx@redhat.com> wrote:
>>
>> On Mon, Apr 10, 2023 at 11:32:08AM +0800, Jason Wang wrote:
>> > @@ -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;
>> > }
>
>> > /* 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.
>
> 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.
> 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
--
Alex Bennée
Virtualisation Tech Lead @ Linaro
On Wed, 12 Apr 2023 at 09:40, Alex Bennée <alex.bennee@linaro.org> wrote:
> Peter Maydell <peter.maydell@linaro.org> writes:
> > 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
Peter Maydell <peter.maydell@linaro.org> writes:
> On Wed, 12 Apr 2023 at 09:40, Alex Bennée <alex.bennee@linaro.org> wrote:
>> Peter Maydell <peter.maydell@linaro.org> writes:
>> > 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.
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.
--
Alex Bennée
Virtualisation Tech Lead @ Linaro
On Tue, Apr 11, 2023 at 03:30:08PM +0100, Peter Maydell wrote:
> On Tue, 11 Apr 2023 at 15:14, Peter Xu <peterx@redhat.com> wrote:
> >
> > On Mon, Apr 10, 2023 at 11:32:08AM +0800, Jason Wang wrote:
> > > @@ -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;
> > > }
>
> > > /* 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.
>
> 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 ?
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,
--
Peter Xu
On Tue, Apr 11, 2023 at 10:44 PM Peter Xu <peterx@redhat.com> wrote:
>
> On Tue, Apr 11, 2023 at 03:30:08PM +0100, Peter Maydell wrote:
> > On Tue, 11 Apr 2023 at 15:14, Peter Xu <peterx@redhat.com> wrote:
> > >
> > > On Mon, Apr 10, 2023 at 11:32:08AM +0800, Jason Wang wrote:
> > > > @@ -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;
> > > > }
> >
> > > > /* 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.
> >
> > 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.
> > 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.
I think so.
Thanks
>
> Thanks,
>
> --
> Peter Xu
>
On Mon, 10 Apr 2023 at 04:32, Jason Wang <jasowang@redhat.com> wrote:
>
> 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")
> Signed-off-by: Jason Wang <jasowang@redhat.com>
Reviewed-by: Peter Maydell <peter.maydell@linaro.org>
thanks
-- PMM
© 2016 - 2024 Red Hat, Inc.