Commit Graph

6 Commits

Author SHA1 Message Date
Lionel Landwerlin cdc4377591 util/sparse_free_list: manipulate node pointers using atomic primitives
Probably doesn't fix anything but those should be accessed in an
atomic way just like the head pointer.

Signed-off-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>
Fixes: e4f01eca3b ("util: Add a free list structure for use with util_sparse_array")
Reviewed-by: Jason Ekstrand <jason@jlekstrand.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4613>
2020-04-18 12:18:03 +00:00
D Scott Phillips dc3a17997b util/sparse_array: don't stomp head's counter on pop operations
By temporarily storing the new_head by a uint32_t, we wipe out the
counter section of the head pointer.

Fixes: e4f01eca ("util: Add a free list structure for use with util_sparse_array")
Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>
Reviewed-by: Rafael Antognolli <rafael.antognolli@intel.com>
Reviewed-by: Jason Ekstrand <jason@jlekstrand.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4612>
2020-04-17 18:41:40 +00:00
Jason Ekstrand aee004a7c8 util/sparse_array: Stash the node level in the node pointer
This reworks the data structure a bit and, in my view, simplifies it.
Instead of each node having a header which has the node level in it, we
use the bottom 6 bits of the pointer for that.  This requires us to
allocate with the os_malloc/free_aligned helpers (which call into
posix_memalign on Linux) but cache-line aligning our allocations is
actually probably a good thing given that we're doing atomics on them.

The primary advantages to doing this is that it changes the number of
memory accesses per tree level from 2 to 1 when walking the tree because
we no longer have to look at node->level.

Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>
Tested-by: Marge Bot <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4228>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4228>
2020-03-20 15:31:10 -05:00
Jason Ekstrand 9fcd8bdbfc util/sparse_array: Add a node_size_log2 temporary
We use this value several times.  It's probably best to encourage the
compiler to only read it once.  I have no proof that this actually makes
any performance improvement whatsoever.

Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4228>
2020-03-20 15:26:07 -05:00
Jason Ekstrand e4f01eca3b util: Add a free list structure for use with util_sparse_array
Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>
2019-10-31 13:46:09 +00:00
Jason Ekstrand 09ec6917c1 util: Add a util_sparse_array data structure
Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>
2019-10-31 13:46:08 +00:00