drm: Convert prime dma-buf <-> handle to rbtree
Currently we use a linear walk to lookup a handle and return a dma-buf,
and vice versa. A long overdue TODO task is to convert that to a
hashtable. Since the initial implementation of dma-buf/prime, we now
have resizeable hashtables we can use (and now a future task is to RCU
enable the lookup!). However, this patch opts to use an rbtree instead
to provide O(lgN) lookups (and insertion, deletion). rbtrees were chosen
over using the RCU backed resizable hashtable to firstly avoid the
reallocations (rbtrees can be embedded entirely within the parent
struct) and to favour simpler code with predictable worst case
behaviour. In simple testing, the difference between using the constant
lookup and insertion of the rhashtable and the rbtree was less than 10%
of the wall time (igt/benchmarks/prime_lookup) - both are dramatic
improvements over the existing linear lists.
v2: Favour rbtree over rhashtable
Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=94631
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Sean Paul <seanpaul@chromium.org>
Cc: David Herrmann <dh.herrmann@gmail.com>
Reviewed-by: David Herrmann <dh.herrmann@gmail.com>
Reviewed-by: Sean Paul <seanpaul@chromium.org>
Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Link: http://patchwork.freedesktop.org/patch/msgid/20160926204414.23222-1-chris@chris-wilson.co.uk
2 files changed