external_mesa3d/src/mesa/main/hash.c, branch replicant-6.0

Fix races during _mesa_HashWalk().

2016-11-24T16:34:39+00:00

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 
Signed-off-by: Steinar H. Gunderson 
Reviewed-by: Timothy Arceri 
(cherry picked from commit 2e2562cabbe9a1d3fb997ccaccc20ba31b2006c3)

mesa: Replace uses of Shared->Mutex with hash-table mutexes

2016-05-20T17:05:09+00:00

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 
Reviewed-by: Brian Paul

hash: Add _mesa_HashRemoveLocked() function.

2016-05-20T17:05:09+00:00

Reviewed-by: Timothy Arceri 
Reviewed-by: Brian Paul

util/hash_table: add _mesa_hash_table_num_entries

2016-02-03T13:03:35+00:00

Reviewed-by: Marek Olšák

mesa/main: Remove _mesa_HashClone()

2015-06-11T10:17:11+00:00

I didn't find this being used anywhere.

Signed-off-by: Juha-Pekka Heikkila 
Reviewed-by: Timothy Arceri 
Reviewed-by: Anuj Phogat

mesa: Use assert() instead of ASSERT wrapper.

2015-02-23T18:49:47+00:00

Acked-by: Eric Anholt

hash_table: Rename insert_with_hash to insert_pre_hashed

2015-01-15T21:21:27+00:00

We already have search_pre_hashed.  This makes the APIs match better.

Reviewed-by: Matt Turner 
Reviewed-by: Eric Anholt

util/hash_table: Rework the API to know about hashing

2014-12-15T03:32:53+00:00

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 
Signed-off-by: Eric Anholt 
Reviewed-by: Eric Anholt

util: Move the open-addressing linear-probing hash_table to src/util.

2014-08-04T18:07:05+00:00

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 

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

Signed-off-by: Jason Ekstrand 
Reviewed-by: Marek Olšák

mesa: add missing null check in _mesa_NewHashTable()

2014-05-30T04:20:53+00:00

Signed-off-by: Juha-Pekka Heikkila 
Reviewed-by: Ian Romanick