aboutsummaryrefslogtreecommitdiffstats
path: root/src/mesa/main/hash.c
Commit message (Collapse)AuthorAgeFilesLines
* replace malloc macros in imports.h with u_memory.h versionsDylan Baker2020-04-211-0/+1
| | | | | | | Reviewed-by: Marek Olšák <[email protected]> Reviewed-by: Kristian H. Kristensen <[email protected]> Reviewed-by: Matt Turner <[email protected]> Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/3024>
* util: use C99 declaration in the for-loop hash_table_foreach() macroEric Engestrom2018-10-251-3/+0
| | | | | Signed-off-by: Eric Engestrom <[email protected]> Reviewed-by: Timothy Arceri <[email protected]>
* mesa: include mtypes.h lessMarek Olšák2018-04-121-0/+1
| | | | | | | | | | - remove mtypes.h from most header files - add main/menums.h for often used definitions - remove main/core.h v2: fix radv build Reviewed-by: Brian Paul <[email protected]>
* mesa: move some hash declarations to hash.hSamuel Pitoiset2017-06-141-56/+0
| | | | | | | These will be used by the bindless hash tables to initialize the default deleted key value. Signed-off-by: Samuel Pitoiset <[email protected]>
* main: Move hashLockMutex/hashUnlockMutex to header and inlineThomas Helland2017-05-221-43/+0
| | | | Reviewed-by: Timothy Arceri <[email protected]>
* main: Use _mesa_HashLock/UnlockMutex consistentlyThomas Helland2017-05-221-13/+10
| | | | | | | | | This is shorter and easier on the eyes. At the same time this also ensures that we are always asserting that the table pointer is not NULL. Currently that was not done for all situations. Reviewed-by: Samuel Pitoiset <[email protected]> Reviewed-by: Timothy Arceri <[email protected]>
* mesa: replace _mesa_problem() with assert() in hash tableTimothy Arceri2017-05-161-6/+4
| | | | | | | There should be no way the OpenGL test suites don't hit the assert() should we do something to cause this code path to be taken. Reviewed-by: Samuel Pitoiset <[email protected]>
* mesa: create locked version of HashWalkTimothy Arceri2017-04-251-8/+26
| | | | Reviewed-by: Nicolai Hähnle <[email protected]>
* mesa: use pre_hashed version of search for the mesa hash tableTimothy Arceri2017-04-121-2/+6
| | | | | | | The key is just an unsigned int so there is never any real hashing done. Reviewed-by: Eric Anholt <[email protected]>
* Fix races during _mesa_HashWalk().Steinar H. Gunderson2016-11-121-11/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | There is currently no protection against walking a hash (using _mesa_HashWalk()) and modifying it at the same time, for instance by inserting or deleting elements. This leads to segfaults in multithreaded code if e.g. someone calls glTexImage2D (which may have to walk the list of FBOs) while another thread is calling glDeleteFramebuffers on another thread with the two contexts sharing lists. The reason for this is that _mesa_HashWalk() doesn't actually take the mutex that normally protects the hash; it takes an entirely different mutex. Thus, walks are only protected against other walks, and there is also no outer lock taking this. There is an old comment saying that this is to fix problems with deadlock if the callback needs to take a mutex; we solve this by changing the mutex to be recursive. A demonstration Helgrind hit from a real application: ==13412== Possible data race during write of size 8 at 0x3498C6A8 by thread #1 ==13412== Locks held: 2, at addresses 0x1AF09530 0x2B3DF400 ==13412== at 0x1F040C99: _mesa_hash_table_remove (hash_table.c:395) ==13412== by 0x1EE98174: _mesa_HashRemove_unlocked (hash.c:350) ==13412== by 0x1EE98174: _mesa_HashRemove (hash.c:365) ==13412== by 0x1EE2372D: _mesa_DeleteFramebuffers (fbobject.c:2669) ==13412== by 0x6105AA4: movit::ResourcePool::cleanup_unlinked_fbos(void*) (resource_pool.cpp:473) ==13412== by 0x610615B: movit::ResourcePool::release_fbo(unsigned int) (resource_pool.cpp:442) [...] ==13412== This conflicts with a previous read of size 8 by thread #20 ==13412== Locks held: 2, at addresses 0x1AF09558 0x1AF73318 ==13412== at 0x1F040CD9: _mesa_hash_table_next_entry (hash_table.c:415) ==13412== by 0x1EE982A8: _mesa_HashWalk (hash.c:426) ==13412== by 0x1EED6DFD: _mesa_update_fbo_texture.part.33 (teximage.c:2683) ==13412== by 0x1EED9410: _mesa_update_fbo_texture (teximage.c:3043) ==13412== by 0x1EED9410: teximage (teximage.c:3073) ==13412== by 0x1EEDA28F: _mesa_TexImage2D (teximage.c:3105) ==13412== by 0x166A68: operator() (mixer.cpp:454) There are many more interactions than just these two possible. Cc: 11.2 12.0 13.0 <[email protected]> Signed-off-by: Steinar H. Gunderson <[email protected]> Reviewed-by: Timothy Arceri <[email protected]>
* mesa: Replace uses of Shared->Mutex with hash-table mutexesMatt Turner2016-05-201-4/+0
| | | | | | | | | | | | | | | We were locking the Shared->Mutex and then using calling functions like _mesa_HashInsert that do additional per-hash-table locking internally. Instead just lock each hash-table's mutex and use functions like _mesa_HashInsertLocked and the new _mesa_HashRemoveLocked. In order to do this, we need to remove the locking from _mesa_HashFindFreeKeyBlock since it will always be called with the per-hash-table lock taken. Reviewed-by: Timothy Arceri <[email protected]> Reviewed-by: Brian Paul <[email protected]>
* hash: Add _mesa_HashRemoveLocked() function.Matt Turner2016-05-201-4/+15
| | | | | Reviewed-by: Timothy Arceri <[email protected]> Reviewed-by: Brian Paul <[email protected]>
* util/hash_table: add _mesa_hash_table_num_entriesNicolai Hähnle2016-02-031-3/+1
| | | | Reviewed-by: Marek Olšák <[email protected]>
* mesa/main: Remove _mesa_HashClone()Juha-Pekka Heikkila2015-06-111-28/+0
| | | | | | | | I didn't find this being used anywhere. Signed-off-by: Juha-Pekka Heikkila <[email protected]> Reviewed-by: Timothy Arceri <[email protected]> Reviewed-by: Anuj Phogat <[email protected]>
* mesa: Use assert() instead of ASSERT wrapper.Matt Turner2015-02-231-5/+5
| | | | Acked-by: Eric Anholt <[email protected]>
* hash_table: Rename insert_with_hash to insert_pre_hashedJason Ekstrand2015-01-151-1/+1
| | | | | | | We already have search_pre_hashed. This makes the APIs match better. Reviewed-by: Matt Turner <[email protected]> Reviewed-by: Eric Anholt <[email protected]>
* util/hash_table: Rework the API to know about hashingJason Ekstrand2014-12-141-5/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | 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 <[email protected]> Signed-off-by: Eric Anholt <[email protected]> Reviewed-by: Eric Anholt <[email protected]>
* util: Move the open-addressing linear-probing hash_table to src/util.Kenneth Graunke2014-08-041-1/+1
| | | | | | | | | | | | | | | | | 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 6991c2922f5 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 <[email protected]> v2 (Jason Ekstrand): Pick up another hash_table use and patch up scons Signed-off-by: Jason Ekstrand <[email protected]> Reviewed-by: Marek Olšák <[email protected]>
* mesa: add missing null check in _mesa_NewHashTable()Juha-Pekka Heikkila2014-05-301-0/+10
| | | | | Signed-off-by: Juha-Pekka Heikkila <[email protected]> Reviewed-by: Ian Romanick <[email protected]>
* mesa: Add functions for doing unlocked hash table lookupsFredrik Höglund2014-05-021-9/+80
| | | | | | | | | | | | This patch adds functions for locking/unlocking the mutex, along with _mesa_HashLookupLocked() and _mesa_HashInsertLocked() that do lookups and insertions without locking the mutex. These functions will be used by the ARB_multi_bind entry points to avoid locking/unlocking the mutex for each binding point. Reviewed-by: Brian Paul <[email protected]> Reviewed-by: Ian Romanick <[email protected]>
* mesa: remove empty glthread.h fileBrian Paul2014-03-031-1/+0
| | | | Reviewed-by: José Fonseca <[email protected]>
* mesa: switch to c11 mutex functionsBrian Paul2014-03-031-22/+22
| | | | Reviewed-by: José Fonseca <[email protected]>
* mesa: Add a clone function to mesa hashTimothy Arceri2013-09-041-0/+28
| | | | | | | | V2: const qualify table parameter Signed-off-by: Timothy Arceri <[email protected]> Reviewed-by: Brian Paul <[email protected]>
* mesa: remove outdated version lines in commentsRico Schüller2013-06-051-1/+0
| | | | Signed-off-by: Brian Paul <[email protected]>
* mesa: Restore 78-column wrapping of license text in C-style comments.Kenneth Graunke2013-04-231-3/+4
| | | | | | | | | | | | | | The previous commit introduced extra words, breaking the formatting. This text transformation was done automatically via the following shell command: $ git grep 'THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY' | sed 's/:.*$//' | xargs -I {} sh -c 'vim -e -s {} < vimscript where 'vimscript' is a file containing: /THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY/;/\*\// !fmt -w 78 -p ' * ' :wq Reviewed-by: Brian Paul <[email protected]>
* mesa: Add "OR COPYRIGHT HOLDERS" to license text disclaiming liability.Kenneth Graunke2013-04-231-1/+1
| | | | | | | | | | | | | | | This brings the license text in line with the MIT License as published on the Open Source Initiative website: http://opensource.org/licenses/mit-license.php Generated automatically be the following shell command: $ git grep 'THE AUTHORS BE LIABLE' | sed 's/:.*$//g' | xargs -I '{}' \ sed -i 's/THE AUTHORS/THE AUTHORS OR COPYRIGHT HOLDERS/' {} This introduces some wrapping issues, to be fixed in the next commit. Reviewed-by: Brian Paul <[email protected]>
* mesa: Change "BRIAN PAUL" to "THE AUTHORS" in license text.Kenneth Graunke2013-04-231-1/+1
| | | | | | | | | | | | | | | | Generated automatically be the following shell command: $ git grep 'BRIAN PAUL BE LIABLE' | sed 's/:.*$//g' | xargs -I '{}' \ sed -i 's/BRIAN PAUL/THE AUTHORS/' {} The intention here is to protect all authors, not just Brian Paul. I believe that was already the sensible interpretation, but spelling it out is probably better. More practically, it also prevents people from accidentally copy & pasting the license into a new file which says Brian is not liable when he isn't even one of the authors. Reviewed-by: Brian Paul <[email protected]>
* mesa: NULL check the pointer before trying to dereference itIan Romanick2013-04-121-2/+2
| | | | | | | | | | | | | | | | | | | Duh. Fixes issues identified by Klocwork analysis: Pointer 'table' returned from call to function 'calloc' at line 115 may be NULL and will be dereferenced at line 117. and Suspicious dereference of pointer 'table' before NULL check at line 119. NOTE: This is a candidate for the stable branches. Signed-off-by: Ian Romanick <[email protected]> Reviewed-by: Kenneth Graunke <[email protected]>
* mesa: Convert the hash table for GL object ids to the open-addressing hash.Eric Anholt2012-11-121-258/+113
| | | | | | | | | | | | | | | | | | | | | | | | | | The previous 1023-entry chaining hash table never resized, so it was very inefficient when there were many objects live. While one could have an even more efficient implementation than this (keep an array for genned names with packed IDs, or take advantage of the fact that key == hash or key == *(uint32_t *)data to store less data), this is fairly fast, and I want a nice replacement hash table for other parts of Mesa, too. It improves Minecraft performance 12.3% +/- 1.4% (n=9), dropping hash lookups from 8% of the profile to 0.5%. I also tested cairo-gl, which should be a pessimal workload for this hash table: around 247000 FBOs created and destroyed, only around 65 live at any time, and few lookups of them between creation and destruction. No statistically significant performance difference at n=76 (mean 20.3/20.4 seconds, sd 2.8/3.2 seconds). If I remove the >20 seconds outliers that appear to be due to thermal throttling, there's possibly a .97% +/- 0.31% performance win (n=61/59). The choice of cutoff for outliers feels a lot like cooking the data, but I've gone through this process 3 times for minor iterations of the code with the same conclusion each time. Reviewed-by: Brian Paul <[email protected]> Acked-by: Chad Versace <[email protected]> Acked-by: Kenneth Graunke <[email protected]> (v1)
* mesa: add _mesa_HashNumEntries() functionBrian Paul2012-01-111-0/+20
| | | | | Useful when debugging to find the number of texture objects, shader programs, etc.
* mesa: s/INLINE/inline/Brian Paul2011-10-011-1/+1
| | | | | | | INLINE is still seen in some files (some generated files, etc) but this is a good start. Acked-by: Kenneth Graunke <[email protected]>
* Drop GLcontext typedef and use struct gl_context insteadKristian Høgsberg2010-10-131-2/+2
|
* mesa: move/update hash function commentsBrian Paul2010-03-271-6/+11
| | | | (cherry picked from commit 535742d75f0096b22d1b8ff203ae561167af18f7)
* mesa: fix deadlock in _mesa_HashFindFreeKeyBlock()Brian Paul2010-03-271-6/+13
| | | | | Fixes fd.o bug 27340. (cherry picked from commit 8fe3b3f66ae57a1a6eca7f6dcb0455e14ad92075)
* Replace _mesa_malloc, _mesa_calloc and _mesa_free with plain libc versionsKristian Høgsberg2010-02-191-4/+4
|
* mesa: Lock mutex around _mesa_HashLookup linked list chase.Brian Paul2010-02-161-2/+5
| | | | | | | | | Remove const qualifier from _mesa_HashLookup() table parameter to avoid LOCK/UNLOCK warnings in the function body. Signed-off-by: Brian Paul <[email protected]> (cherry picked from commit 3094adb3caeb90124359db2356df3bf8ee94800a)
* mesa: Test for failed malloc in _mesa_HashInsert.Brian Paul2010-02-161-4/+6
| | | | | | Signed-off-by: Brian Paul <[email protected]> (cherry picked from commit 7c7247ddbf6e3f7f93e44c1cb52490044f1a2215)
* mesa: fix potential recursive locking deadlock in _mesa_HashWalk()Brian Paul2009-04-091-4/+14
| | | | If the walk callback called _mesa_HashRemove() we'd deadlock.
* mesa: Fix typo.José Fonseca2009-03-061-1/+1
| | | | Windows threads block if one over-unlocks them.
* Be more consistant with paths in #includes. Eventually, eliminate a bunch ↵Brian2007-07-041-1/+1
| | | | of -I flags.
* disable a new mem leak check until we're sure it's validBrian Paul2006-07-031-0/+2
|
* clean-upsBrian Paul2006-06-301-23/+26
|
* Added _mesa_HashDeleteAll() to delete all entries in a hash table with aBrian Paul2006-06-301-10/+74
| | | | | callback function. Added _mesa_HashWalk() to walk over all entries in a hash table with callback.
* don't compile debug code (bug 4242: rand undefined)Brian Paul2005-08-251-1/+5
|
* set table size to 1023 and use new HASH_FUNC() macroBrian Paul2005-04-101-5/+8
|
* Bug #2945: Fix math error that left half the hash buckets empty.Adam Jackson2005-04-091-1/+1
|
* Added _mesa_HashNextEntry() function to allow walking over all entriesBrian Paul2005-01-241-37/+121
| | | | | | in a hash table. Added _mesa_test_hash_functions() for unit testing. Updated comments, etc.
* Merge Jose's documentation and core Mesa changes from embedded branchKeith Whitwell2003-07-171-28/+65
|
* Removed all RCS / CVS tags (Id, Header, Date, etc.) from everything.Ian Romanick2003-06-051-1/+0
|
* Add mechanism to destroy mutexes. Important on OS's where mutex initializationKeith Whitwell2002-12-121-1/+2
| | | | allocates memory (like FreeBSD).
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-29 11:36:23 +0000