[1/5] util/hash_table: Don't hash the deleted and freed keys

Submitted by Tomeu Vizoso on Aug. 5, 2019, 3:18 p.m.

Details

Message ID 20190805151836.12293-1-tomeu.vizoso@collabora.com
State New
Headers show
Series "Series without cover letter" ( rev: 1 ) in Mesa

Not browsing as part of any series.

Commit Message

Tomeu Vizoso Aug. 5, 2019, 3:18 p.m.
Some hash functions (eg. key_u64_hash) will attempt to dereference the
key, causing an invalid access when passed DELETED_KEY_VALUE (0x1) or
FREED_KEY_VALUE (0x0).

The entry.hash field isn't needed by the delete_function, so just stop
populating it.

Signed-off-by: Tomeu Vizoso <tomeu.vizoso@collabora.com>
Cc: Samuel Pitoiset <samuel.pitoiset@gmail.com>
Cc: Nicolai Hähnle <nicolai.haehnle@amd.com>
---
 src/util/hash_table.c | 2 --
 1 file changed, 2 deletions(-)

Patch hide | download patch | download mbox

diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index f58575de558f..e691f8baa9c1 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -667,7 +667,6 @@  _mesa_hash_table_u64_clear(struct hash_table_u64 *ht,
          struct hash_entry entry;
 
          /* Create a fake entry for the delete function. */
-         entry.hash = table->key_hash_function(table->deleted_key);
          entry.key = table->deleted_key;
          entry.data = ht->deleted_key_data;
 
@@ -682,7 +681,6 @@  _mesa_hash_table_u64_clear(struct hash_table_u64 *ht,
          struct hash_entry entry;
 
          /* Create a fake entry for the delete function. */
-         entry.hash = table->key_hash_function(uint_key(FREED_KEY_VALUE));
          entry.key = uint_key(FREED_KEY_VALUE);
          entry.data = ht->freed_key_data;
 

Comments

On Mon, Aug 05, 2019 at 05:18:32PM +0200, Tomeu Vizoso wrote:
> Some hash functions (eg. key_u64_hash) will attempt to dereference the
> key, causing an invalid access when passed DELETED_KEY_VALUE (0x1) or
> FREED_KEY_VALUE (0x0).
> 
> The entry.hash field isn't needed by the delete_function, so just stop
> populating it.

delete_function is a callback, so it is up to the caller whether it
makes use it or not.  We also would have to add a comment somewhere
about this exception.

Seems to me this is a bug of not calling hash correctly when
`sizeof(void *) != 8`.  To fix we should do like in
hash_table_u64_search() and create a temporary local struct
hash_key_u64 in that case.


	Caio
What's the implication of this for Panfrost? (I.e. which patch/es in the
series are pending on this change)

On Mon, Aug 05, 2019 at 05:18:32PM +0200, Tomeu Vizoso wrote:
> Some hash functions (eg. key_u64_hash) will attempt to dereference the
> key, causing an invalid access when passed DELETED_KEY_VALUE (0x1) or
> FREED_KEY_VALUE (0x0).
> 
> The entry.hash field isn't needed by the delete_function, so just stop
> populating it.
> 
> Signed-off-by: Tomeu Vizoso <tomeu.vizoso@collabora.com>
> Cc: Samuel Pitoiset <samuel.pitoiset@gmail.com>
> Cc: Nicolai Hähnle <nicolai.haehnle@amd.com>
> ---
>  src/util/hash_table.c | 2 --
>  1 file changed, 2 deletions(-)
> 
> diff --git a/src/util/hash_table.c b/src/util/hash_table.c
> index f58575de558f..e691f8baa9c1 100644
> --- a/src/util/hash_table.c
> +++ b/src/util/hash_table.c
> @@ -667,7 +667,6 @@ _mesa_hash_table_u64_clear(struct hash_table_u64 *ht,
>           struct hash_entry entry;
>  
>           /* Create a fake entry for the delete function. */
> -         entry.hash = table->key_hash_function(table->deleted_key);
>           entry.key = table->deleted_key;
>           entry.data = ht->deleted_key_data;
>  
> @@ -682,7 +681,6 @@ _mesa_hash_table_u64_clear(struct hash_table_u64 *ht,
>           struct hash_entry entry;
>  
>           /* Create a fake entry for the delete function. */
> -         entry.hash = table->key_hash_function(uint_key(FREED_KEY_VALUE));
>           entry.key = uint_key(FREED_KEY_VALUE);
>           entry.data = ht->freed_key_data;
>  
> -- 
> 2.20.1
To be clear, Panfrost relies on stuffing (bogus) magic numbers into u64
keys and u64 values. Is this going to break on us? That is, when you
mention this is a bug, who's buggy here? (Panfrost or hash_table_u64 or
both?)

On Mon, Aug 05, 2019 at 09:10:00AM -0700, Caio Marcelo de Oliveira Filho wrote:
> On Mon, Aug 05, 2019 at 05:18:32PM +0200, Tomeu Vizoso wrote:
> > Some hash functions (eg. key_u64_hash) will attempt to dereference the
> > key, causing an invalid access when passed DELETED_KEY_VALUE (0x1) or
> > FREED_KEY_VALUE (0x0).
> > 
> > The entry.hash field isn't needed by the delete_function, so just stop
> > populating it.
> 
> delete_function is a callback, so it is up to the caller whether it
> makes use it or not.  We also would have to add a comment somewhere
> about this exception.
> 
> Seems to me this is a bug of not calling hash correctly when
> `sizeof(void *) != 8`.  To fix we should do like in
> hash_table_u64_search() and create a temporary local struct
> hash_key_u64 in that case.
> 
> 
> 	Caio
On Mon, Aug 05, 2019 at 10:02:43AM -0700, Alyssa Rosenzweig wrote:
> To be clear, Panfrost relies on stuffing (bogus) magic numbers into u64
> keys and u64 values. Is this going to break on us? That is, when you
> mention this is a bug, who's buggy here? (Panfrost or hash_table_u64 or
> both?)

There's a bug in _mesa_hash_table_u64_clear(), it assumes it can use
the u64 directly as key, but that's not always the case.  For
`sizeof(void *) != 8` we stuff the u64 key into a struct.  Note we use
different hash functions in those cases.

The fix in the original patch "also works", but would make a special
case like "when delete_function callback is called, there are cases
where the hash in hash_entry is invalid".  The right fix is just doing
in _clear() something similar than what hash_table_u64_search() do.

When using the u64 hash table, you can use the entire u64 value space
-- there shouldn't be "bad" or "bogus" keys from the caller
perspective.  So I think Panfrost should be fine.


	Caio




> On Mon, Aug 05, 2019 at 09:10:00AM -0700, Caio Marcelo de Oliveira Filho wrote:
> > On Mon, Aug 05, 2019 at 05:18:32PM +0200, Tomeu Vizoso wrote:
> > > Some hash functions (eg. key_u64_hash) will attempt to dereference the
> > > key, causing an invalid access when passed DELETED_KEY_VALUE (0x1) or
> > > FREED_KEY_VALUE (0x0).
> > > 
> > > The entry.hash field isn't needed by the delete_function, so just stop
> > > populating it.
> > 
> > delete_function is a callback, so it is up to the caller whether it
> > makes use it or not.  We also would have to add a comment somewhere
> > about this exception.
> > 
> > Seems to me this is a bug of not calling hash correctly when
> > `sizeof(void *) != 8`.  To fix we should do like in
> > hash_table_u64_search() and create a temporary local struct
> > hash_key_u64 in that case.
> > 
> > 
> > 	Caio
On Mon, 5 Aug 2019 at 19:01, Alyssa Rosenzweig <alyssa@rosenzweig.io> wrote:
>
> What's the implication of this for Panfrost? (I.e. which patch/es in the
> series are pending on this change)

Patch 2 needs this, otherwise we SIGSEGV on context destruction if
blend shaders are used. And patch 3 depends on patch 5, otherwise the
GPU would try to execute a shader in a memory region marked as not
executable.

Will be sending a v2 with Caio's suggestion.

Cheers,

Tomeu




> On Mon, Aug 05, 2019 at 05:18:32PM +0200, Tomeu Vizoso wrote:
> > Some hash functions (eg. key_u64_hash) will attempt to dereference the
> > key, causing an invalid access when passed DELETED_KEY_VALUE (0x1) or
> > FREED_KEY_VALUE (0x0).
> >
> > The entry.hash field isn't needed by the delete_function, so just stop
> > populating it.
> >
> > Signed-off-by: Tomeu Vizoso <tomeu.vizoso@collabora.com>
> > Cc: Samuel Pitoiset <samuel.pitoiset@gmail.com>
> > Cc: Nicolai Hähnle <nicolai.haehnle@amd.com>
> > ---
> >  src/util/hash_table.c | 2 --
> >  1 file changed, 2 deletions(-)
> >
> > diff --git a/src/util/hash_table.c b/src/util/hash_table.c
> > index f58575de558f..e691f8baa9c1 100644
> > --- a/src/util/hash_table.c
> > +++ b/src/util/hash_table.c
> > @@ -667,7 +667,6 @@ _mesa_hash_table_u64_clear(struct hash_table_u64 *ht,
> >           struct hash_entry entry;
> >
> >           /* Create a fake entry for the delete function. */
> > -         entry.hash = table->key_hash_function(table->deleted_key);
> >           entry.key = table->deleted_key;
> >           entry.data = ht->deleted_key_data;
> >
> > @@ -682,7 +681,6 @@ _mesa_hash_table_u64_clear(struct hash_table_u64 *ht,
> >           struct hash_entry entry;
> >
> >           /* Create a fake entry for the delete function. */
> > -         entry.hash = table->key_hash_function(uint_key(FREED_KEY_VALUE));
> >           entry.key = uint_key(FREED_KEY_VALUE);
> >           entry.data = ht->freed_key_data;
> >
> > --
> > 2.20.1
> _______________________________________________
> mesa-dev mailing list
> mesa-dev@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev