summaryrefslogtreecommitdiff
path: root/include/drm
diff options
context:
space:
mode:
authorChris Wilson <chris@chris-wilson.co.uk>2016-09-26 23:44:14 +0300
committerDaniel Vetter <daniel.vetter@ffwll.ch>2016-10-04 09:23:07 +0300
commit077675c1e8a193a6355d4a7c8c7bf63be310b472 (patch)
tree1126f18b7accec717e1fc6d4862fa344a6d0a1b5 /include/drm
parent188af070d4d20474cba4d42b4eaf728ba116f418 (diff)
downloadlinux-077675c1e8a193a6355d4a7c8c7bf63be310b472.tar.xz
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
Diffstat (limited to 'include/drm')
-rw-r--r--include/drm/drmP.h5
1 files changed, 3 insertions, 2 deletions
diff --git a/include/drm/drmP.h b/include/drm/drmP.h
index c53dc90942e0..289207f12adb 100644
--- a/include/drm/drmP.h
+++ b/include/drm/drmP.h
@@ -51,6 +51,7 @@
#include <linux/platform_device.h>
#include <linux/poll.h>
#include <linux/ratelimit.h>
+#include <linux/rbtree.h>
#include <linux/sched.h>
#include <linux/slab.h>
#include <linux/types.h>
@@ -371,10 +372,10 @@ struct drm_pending_event {
we deliver the event, for tracing only */
};
-/* initial implementaton using a linked list - todo hashtab */
struct drm_prime_file_private {
- struct list_head head;
struct mutex lock;
+ struct rb_root dmabufs;
+ struct rb_root handles;
};
/** File private data */