Re: [PATCH for 8.1] intel_iommu: refine iotlb hash calculation

[Jason Wang]

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
>