Commit Graph

44 Commits

Author SHA1 Message Date
Jesse Natalie ffd4157b1c util/hash_table: Clear special 0/1 entries for u64 hash table too
Fixes: e532a47f ("util/hash_table: do not leak u64 struct key")
Reviewed-by: Emma Anholt <emma@anholt.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/13390>
2021-11-02 11:02:18 -07:00
Marek Olšák a4e0b02f85 mesa: skip strlen when hashing strings for ProgramResourceHash
Reviewed-by: Timothy Arceri <tarceri@itsqueeze.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/13507>
2021-10-29 07:19:20 -04:00
Mike Blumenkrantz c449a8a2c1 util/hash_table: _mesa_hash_table_create_u32_keys()
Reviewed-by: Erik Faye-Lund <erik.faye-lund@collabora.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/10673>
2021-05-07 13:14:08 +00:00
Juan A. Suarez Romero e532a47f76 util/hash_table: do not leak u64 struct key
For non 64bit devices the key stored in hash_table_u64 is wrapped in
hash_key_u64 structure, which is never free.

This commit fixes this issue by just removing the user-defined
`delete_function` parameter in hash_table_u64_{destroy,clear} (which
nobody is using) and using instead a delete function to free this
structure.

Fixes: 608257cf82 ("i965: Fix INTEL_DEBUG=bat")
Reviewed-by: Ian Romanick <ian.d.romanick@intel.com>
Signed-off-by: Juan A. Suarez Romero <jasuarez@igalia.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/10480>
2021-04-29 12:58:23 +02:00
Mike Blumenkrantz 31e546a762 util/hash_table: add macro for destructively iterating entries
a common usage for hash tables is for tracking exactly one instance of a pointer
for a given period of time, after which the table's entries are purged and it
is reused

this macro enables the purge phase of such usage to reset the table to a
pristine state, avoiding future rehashing due to ballooning of deleted entries

Reviewed-by: Adam Jackson <ajax@redhat.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/8498>
2021-04-07 22:57:27 +00:00
Mike Blumenkrantz 41042f7fa2 util/hash_table: optimize rehash for empty table and no-func clears
if the table is filled with deleted entries, we don't need to rzalloc+free an identical
block of memory for the table, we can just memset the existing one

the same applies to table clears without a function passed in that the table
doesn't need to be iterated and can just be memset

Reviewed-by: Eric Anholt <eric@anholt.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/8450>
2021-01-14 13:51:35 +00:00
Pierre-Eric Pelloux-Prayer ba67843dbd util/hash_table: add _mesa_hash_data_with_seed function
Reviewed-by: Marek Olšák <marek.olsak@amd.com>
Reviewed-by: Ian Romanick <ian.d.romanick@intel.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/7078>
2020-12-08 10:10:47 +01:00
Eric Anholt 4618ca82c3 util/hash_table: Clean up the _mesa_hash_table_clear() implementation.
Use the entry_is_present() helper to clarify what's going on with
deletion, and then we can remove the special continue for NULL since we're
just writing NULL anyway (which the CPU cache will elide for us).

Reviewed-by: Jason Ekstrand <jason@jlekstrand.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/7244>
2020-11-10 22:18:31 +00:00
Eric Anholt 9c5422c7dd util/hash_table: Handle NULL ht in _mesa_hash_table_clear().
This is the one useful bit of _mesa_set_clear() that wasn't in
_mesa_hash_table_clear().

Reviewed-by: Jason Ekstrand <jason@jlekstrand.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/7244>
2020-11-10 22:18:31 +00:00
Mike Blumenkrantz 0b96b7bf10 util/hash_table: add function for reserving size in a hash table
rehashing a populated hash table is very expensive, so for the case where
the maximum/likely table size is already known, this function allows for
pre-sizing the table to avoid ever needing a rehash

Acked-by: Pierre-Eric Pelloux-Prayer <pierre-eric.pelloux-prayer@amd.com>
Reviewed-by: Eric Anholt <eric@anholt.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/7037>
2020-10-08 18:21:48 +00:00
Dmitriy Nester 387176829b util/hash_table: replace fnv1a hash function with xxhash
xxhash is faster than fnv1a in almost all circumstances, so we're
switching to it globally.

Signed-off-by: Dmytro Nester <dmytro.nester@globallogic.com>
Reviewed-by: Eric Anholt <eric@anholt.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4020>
2020-05-25 19:41:09 +00:00
Dylan Baker b85775900d replace malloc macros in imports.h with u_memory.h versions
Reviewed-by: Marek Olšák <marek.olsak@amd.com>
Reviewed-by: Kristian H. Kristensen <hoegsberg@google.com>
Reviewed-by: Matt Turner <mattst88@gmail.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/3024>
2020-04-21 11:09:03 -07:00
Marek Olšák 76f79db3f5 util: stop including files from mesa/main
Reviewed-by: Timothy Arceri <tarceri@itsqueeze.com
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4324>
2020-03-27 21:00:09 +00:00
Kristian H. Kristensen f1dc4c9554 Mark a few static inline helpers with ASSERTED
Quiet warnings in release builds where these look unused.

Part-of: <https://gitlab.freedesktop.org/mesa/mesa/merge_requests/3866>
2020-02-19 18:34:33 +00:00
Anthony Pesch 1496cc92f6 util/hash_table: added hash functions for integer types
A few hash_table users roll their own integer hash functions which
call _mesa_hash_data to perform the hashing which ultimately calls
into XXH32 with a dynamic key length. When using small keys with a
constant size the hash rate can be greatly improved by inlining
XXH32 and providing it a constant key length, see:
https://fastcompression.blogspot.com/2018/03/xxhash-for-small-keys-impressive-power.html

Additionally, this patch removes calls to _mesa_key_hash_string and
makes them instead call _mesa_has_string directly, matching the new
integer hash functions.

Reviewed-by: Eric Anholt <eric@anholt.net>
Reviewed-by: Iago Toral Quiroga <itoral@igalia.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/merge_requests/3475>
2020-01-23 17:06:57 +00:00
Anthony Pesch 931388ceca util/hash_table: replace _mesa_hash_data's fnv1a hash function with xxhash
For most key sizes, xxhash outperforms fnv1a's hash rate substantially (bug
2153). In particular, the V3D driver hashes multiple ~200 byte keys as part
of the shader cache lookup which can easily eat up 10-20% of the runtime on
the Raspberry Pi. Swapping over to xxhash drops this to ~1% of the runtime.

Reviewed-by: Eric Anholt <eric@anholt.net>
Reviewed-by: Iago Toral Quiroga <itoral@igalia.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/merge_requests/3475>
2020-01-23 17:06:57 +00:00
Anthony Pesch 032f8807f7 util: move fnv1a hash implementation into its own header
Reviewed-by: Eric Anholt <eric@anholt.net>
Reviewed-by: Iago Toral Quiroga <itoral@igalia.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/merge_requests/3475>
2020-01-23 17:06:57 +00:00
Tomeu Vizoso 5804d75b9c util/hash_table: Fix hashing in clears on 32-bit
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).

When in 32-bit arch a 64-bit key value doesn't fit into a pointer, so
hash_table_u64 internally use a pointer to a struct containing the
64-bit key value.

Fix _mesa_hash_table_u64_clear() to handle the 32-bit case by creating a
temporary hash_key_u64 to pass to the hash function.

Signed-off-by: Tomeu Vizoso <tomeu.vizoso@collabora.com>
Suggested-by: Caio Marcelo de Oliveira Filho <caio.oliveira@intel.com>
Reviewed-by: Caio Marcelo de Oliveira Filho <caio.oliveira@intel.com>
Cc: Samuel Pitoiset <samuel.pitoiset@gmail.com>
Cc: Nicolai Hähnle <nicolai.haehnle@amd.com>
2019-08-08 07:42:52 +02:00
Caio Marcelo de Oliveira Filho 608257cf82 i965: Fix INTEL_DEBUG=bat
Use hash_table_u64 instead of hash_table directly, since the former
will also handle the special keys (deleted and freed) and allow use
the whole u64 space.

Fixes crash in INTEL_DEBUG=bat when using a key with value 0 -- the
current value for a freed key.

Fixes: b38dab101c "util/hash_table: Assert that keys are not reserved pointers"
Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>
Reviewed-by: Kenneth Graunke <kenneth@whitecape.org>
2019-06-12 15:57:16 -07:00
Caio Marcelo de Oliveira Filho eb41ce1b01 util/hash_table: Properly handle the NULL key in hash_table_u64
The hash_table_u64 should support any uint64_t as input.  It does
special handling for the "deleted" key, storing the data in the table
itself; do the same for the "freed" key.

Fixes: b38dab101c "util/hash_table: Assert that keys are not reserved pointers"
Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>
Reviewed-by: Kenneth Graunke <kenneth@whitecape.org>
2019-06-12 15:57:16 -07:00
Jason Ekstrand b38dab101c util/hash_table: Assert that keys are not reserved pointers
If we insert a NULL key, it will appear to succeed but will mess up
entry counting.  Similar errors can occur if someone accidentally
inserts the deleted key.  The later is highly unlikely but technically
possible so we should guard against it too.

Reviewed-by: Kenneth Graunke <kenneth@whitecape.org>
Reviewed-by: Caio Marcelo de Oliveira Filho <caio.oliveira@intel.com>
Reviewed-by: Eric Anholt <eric@anholt.net>
2019-06-06 00:27:53 +00:00
Connor Abbott 8c74772edc util/hash_table: Use fast modulo computation
While we're here, copy the size table from set.c to get rid of hard tabs
in the hash_table.c version.

Reviewed-by: Eric Anholt <eric@anholt.net>
Acked-by: Jason Ekstrand <jason@jlekstrand.net>
2019-05-31 19:14:35 +02:00
Connor Abbott 983b001c77 util/hash_table: Add specialized resizing add function
To keep it in sync with the set implementation.

Reviewed-by: Eric Anholt <eric@anholt.net>
Acked-by: Jason Ekstrand <jason@jlekstrand.net>
2019-05-31 19:14:22 +02:00
Connor Abbott 451211741c util/hash_table: Pull out loop-invariant computations
To keep the set and hash table in sync. Note that some of this had
already been done for hash tables, in particular pulling out the
hash % ht->size computation.

Reviewed-by: Eric Anholt <eric@anholt.net>
Acked-by: Jason Ekstrand <jason@jlekstrand.net>
2019-05-31 19:14:09 +02:00
Caio Marcelo de Oliveira Filho ee23e8b17c util: Helper to create sets and hashes with pointer keys
These combinations are common enough and deserve a shortcut.

Reviewed-by: Jason Ekstrand <jason@jlekstrand.net>
Acked-by: Eric Engestrom <eric@engestrom.ch>
2019-01-14 10:49:21 -08:00
Ian Romanick e3043e1276 util/hash_table: Add _mesa_hash_table_init function
Signed-off-by: Ian Romanick <ian.d.romanick@intel.com>
Reviewed-by: Jason Ekstrand <jason@jlekstrand.net>
2018-12-16 14:39:56 -08:00
Eric Engestrom bb84fa146f util: use C99 declaration in the for-loop hash_table_foreach() macro
Signed-off-by: Eric Engestrom <eric@engestrom.ch>
Reviewed-by: Timothy Arceri <tarceri@itsqueeze.com>
2018-10-25 12:43:18 +01:00
Caio Marcelo de Oliveira Filho 4ec8b39fcd util/hash_table: add helper to remove entry by key
And the corresponding test case.

Reviewed-by: Eric Anholt <eric@anholt.net>
2018-07-13 14:20:49 -07:00
Thomas Helland 6baaf4291b util: Implement a hash table cloning function
V2: Don't rzalloc; we are about to rewrite the whole thing (Vladislav)

Reviewed-by: Eric Anholt <eric@anholt.net>
Reviewed-by: Emil Velikov <emil.velikov@collabora.com>
2018-03-14 19:52:01 +01:00
Lionel Landwerlin a8b1715b8a util: hashtable: make hashing prototypes match
It seems nobody's using the string hashing function. If you try to
pass it directly to the hashtable creation function, you'll get
compiler warning for non matching prototypes. Let's make them match.

Signed-off-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>
Reviewed-by: Kenneth Graunke <kenneth@whitecape.org>
2017-10-30 15:18:00 +00:00
Tapani Pälli 8dba6f8cf4 util: fix warning/error on 32bit build
Add uintptr_t cast to fix 'cast to pointer from integer of different size'
warning on 32bit build (build error on Android M).

Signed-off-by: Tapani Pälli <tapani.palli@intel.com>
Reviewed-by: Michel Dänzer <michel.daenzer@amd.com>
Reviewed-by: Samuel Pitoiset <samuel.pitoiset@gmail.com>
2017-07-25 12:54:33 +03:00
Samuel Pitoiset 6649b840c3 mesa/util: add a hash table wrapper which support 64-bit keys
Needed for bindless handles which are represented using
64-bit unsigned integers. All hash table implementations should
be uniformized later on.

Signed-off-by: Samuel Pitoiset <samuel.pitoiset@gmail.com>
Reviewed-by: Nicolai Hähnle <nicolai.haehnle@amd.com>
2017-06-14 10:04:35 +02:00
Tapani Pälli 0abebec012 util: add assert that key cannot be NULL on insertion
Signed-off-by: Tapani Pälli <tapani.palli@intel.com>
Reviewed-by: Jason Ekstrand <jason@jlekstrand.net>
Reviewed-by: Eric Anholt <eric@anholt.net>
2016-08-22 07:37:55 +03:00
Nicolai Hähnle 8b11d8cfbf util/hash_table: add _mesa_hash_table_clear (v4)
v4: coding style change (Matt Turner)

Reviewed-by: Ian Romanick <ian.d.romanick@intel.com> (v3)
2016-02-03 14:03:25 +01:00
Connor Abbott 19db71807f util/hash_table: don't compare deleted entries
The equivalent of the last patch for the hash table. I'm not aware of
any issues this fixes.

v2:
- use entry_is_deleted (Timothy)

Reviewed-by: Timothy Arceri <timothy.arceri@collabora.com>
Signed-off-by: Connor Abbott <cwabbott0@gmail.com>
2016-02-02 14:42:40 -05:00
Jason Ekstrand c9287e797b util/hash_table: Do a full search when adding new items
Previously, the hash_table_insert function would bail early if it found a
deleted slot that it could re-use.  However, this is a problem if the key
being inserted is already in the hash table but further down the list.  If
this happens, the element ends up getting inserted in the hash table twice.
This commit makes it so that we walk over all of the possible entries for
the given key and then, if we don't find the key, place it in the available
free entry we found.

Reviewed-by: Eric Anholt <eric@anholt.net>
2015-02-07 17:01:05 -08:00
Jan Vesely 3cb10cce37 mesa: Fix some signed-unsigned comparison warnings
v2: s/unsigned int/unsigned/ in prog_optimize.c

Signed-off-by: Jan Vesely <jan.vesely@rutgers.edu>
Reviewed-by: David Heidelberg <david@ixit.cz>
Reviewed-by: Jose Fonseca <jfonseca@vmware.com>
2015-01-21 14:05:52 +00:00
Jason Ekstrand 8ed5305d28 hash_table: Rename insert_with_hash to insert_pre_hashed
We already have search_pre_hashed.  This makes the APIs match better.

Reviewed-by: Matt Turner <mattst88@gmail.com>
Reviewed-by: Eric Anholt <eric@anholt.net>
2015-01-15 13:21:27 -08:00
Jason Ekstrand a3b73ccf6d util/hash_table: Pull the details of the FNV-1a into helpers
This way the basics of the FNV-1a hash can be reused to easily create other
hashing functions.

Reviewed-by: Eric Anholt <eric@anholt.net>
2015-01-15 07:20:23 -08:00
Eric Anholt 6c3115af85 hash_table: Fix compiler warnings from the renaming.
Not sure how we both missed this.  None of the callers were using the
return value, though.
2014-12-14 20:22:07 -08:00
Jason Ekstrand 94303a0750 util/hash_table: Rework the API to know about hashing
Previously, the hash_table API required the user to do all of the hashing
of keys as it passed them in.  Since the hashing function is intrinsically
tied to the comparison function, it makes sense for the hash table to know
about it.  Also, it makes for a somewhat clumsy API as the user is
constantly calling hashing functions many of which have long names.  This
is especially bad when the standard call looks something like

_mesa_hash_table_insert(ht, _mesa_pointer_hash(key), key, data);

In the above case, there is no reason why the hash table shouldn't do the
hashing for you.  We leave the option for you to do your own hashing if
it's more efficient, but it's no longer needed.  Also, if you do do your
own hashing, the hash table will assert that your hash matches what it
expects out of the hashing function.  This should make it harder to mess up
your hashing.

v2: change to call the old entrypoint "pre_hashed" rather than
    "with_hash", like cworth's equivalent change upstream (change by
    anholt, acked-in-general by Jason).

Signed-off-by: Jason Ekstrand <jason.ekstrand@intel.com>
Signed-off-by: Eric Anholt <eric@anholt.net>
Reviewed-by: Eric Anholt <eric@anholt.net>
2014-12-14 19:32:53 -08:00
Timothy Arceri b3721cd230 util: update hash type comments
Signed-off-by: Timothy Arceri <t_arceri@yahoo.com.au>
Reviewed-by: Eric Anholt <eric@anholt.net>
2014-11-26 20:04:13 +11:00
Jason Ekstrand efa0aa8ffc util: Gather some common macros
This gathers macros that have been included across components into util so
that the include chain can be more vertical.  In particular, this makes
util stand on its own without any dependence whatsoever on the rest of
mesa.

Signed-off-by: "Jason Ekstrand" <jason.ekstrand@intel.com>
Reviewed-by: Marek Olšák <marek.olsak@amd.com>
2014-08-04 11:07:10 -07:00
Kenneth Graunke 72e55bb688 util: Move the open-addressing linear-probing hash_table to src/util.
This hash table is used in core Mesa, the GLSL compiler, and the i965
driver, which makes it a good candidate for the new src/util module.

It's much faster than program/hash_table.[ch] (see commit 6991c2922f
for data), and José's u_hash_table.c has a comment saying Gallium should
probably consider switching to a linear probing hash table at some point.
So this seems like the best candidate for a shared data structure.

Signed-off-by: Kenneth Graunke <kenneth@whitecape.org>

v2 (Jason Ekstrand): Pick up another hash_table use and patch up scons

Signed-off-by: Jason Ekstrand <jason.ekstrand@intel.com>
Reviewed-by: Marek Olšák <marek.olsak@amd.com>
2014-08-04 11:07:05 -07:00
Renamed from src/mesa/main/hash_table.c (Browse further)