On Tue, Sep 27, 2016 at 12:18:13PM -0400, Sean Paul wrote: > On Tue, Sep 27, 2016 at 2:36 AM, David Herrmann <dh.herrmann@xxxxxxxxx> wrote: > > Hi Chris > > > > On Mon, Sep 26, 2016 at 10:44 PM, Chris Wilson <chris@xxxxxxxxxxxxxxxxxx> wrote: > >> 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@xxxxxxxxxxxxxxxxxx> > >> Cc: Sean Paul <seanpaul@xxxxxxxxxxxx> > >> Cc: David Herrmann <dh.herrmann@xxxxxxxxx> > >> --- > >> drivers/gpu/drm/drm_prime.c | 85 +++++++++++++++++++++++++++++++++++++++------ > >> include/drm/drmP.h | 5 +-- > >> 2 files changed, 77 insertions(+), 13 deletions(-) > > > > Thanks for doing the benchmark and rewriting it with rb-trees. I think > > the lack of error-handling is a big plus here. Anyway, this is: > > > > Reviewed-by: David Herrmann <dh.herrmann@xxxxxxxxx> > > > Agreed, it's also nice be able to keep the WARN_ON in > drm_prime_destroy_file_private > > Reviewed-by: Sean Paul <seanpaul@xxxxxxxxxxxx> Applied to drm-misc, thanks. -Daniel > > > > > Your tree-traversals are a bit inconsistent in how you order your > > iterator against the element to lookup in your conditions, but.. meh. > > A big WARN_ON on conflicts might not hurt either. But looks all good. > > > > Thanks > > David > > > >> diff --git a/drivers/gpu/drm/drm_prime.c b/drivers/gpu/drm/drm_prime.c > >> index 780589b420a4..57201d68cf61 100644 > >> --- a/drivers/gpu/drm/drm_prime.c > >> +++ b/drivers/gpu/drm/drm_prime.c > >> @@ -28,6 +28,7 @@ > >> > >> #include <linux/export.h> > >> #include <linux/dma-buf.h> > >> +#include <linux/rbtree.h> > >> #include <drm/drmP.h> > >> #include <drm/drm_gem.h> > >> > >> @@ -61,9 +62,11 @@ > >> */ > >> > >> struct drm_prime_member { > >> - struct list_head entry; > >> struct dma_buf *dma_buf; > >> uint32_t handle; > >> + > >> + struct rb_node dmabuf_rb; > >> + struct rb_node handle_rb; > >> }; > >> > >> struct drm_prime_attachment { > >> @@ -75,6 +78,7 @@ static int drm_prime_add_buf_handle(struct drm_prime_file_private *prime_fpriv, > >> struct dma_buf *dma_buf, uint32_t handle) > >> { > >> struct drm_prime_member *member; > >> + struct rb_node **p, *rb; > >> > >> member = kmalloc(sizeof(*member), GFP_KERNEL); > >> if (!member) > >> @@ -83,18 +87,56 @@ static int drm_prime_add_buf_handle(struct drm_prime_file_private *prime_fpriv, > >> get_dma_buf(dma_buf); > >> member->dma_buf = dma_buf; > >> member->handle = handle; > >> - list_add(&member->entry, &prime_fpriv->head); > >> + > >> + rb = NULL; > >> + p = &prime_fpriv->dmabufs.rb_node; > >> + while (*p) { > >> + struct drm_prime_member *pos; > >> + > >> + rb = *p; > >> + pos = rb_entry(rb, struct drm_prime_member, dmabuf_rb); > >> + if (dma_buf > pos->dma_buf) > >> + p = &rb->rb_right; > >> + else > >> + p = &rb->rb_left; > >> + } > >> + rb_link_node(&member->dmabuf_rb, rb, p); > >> + rb_insert_color(&member->dmabuf_rb, &prime_fpriv->dmabufs); > >> + > >> + rb = NULL; > >> + p = &prime_fpriv->handles.rb_node; > >> + while (*p) { > >> + struct drm_prime_member *pos; > >> + > >> + rb = *p; > >> + pos = rb_entry(rb, struct drm_prime_member, handle_rb); > >> + if (handle > pos->handle) > >> + p = &rb->rb_right; > >> + else > >> + p = &rb->rb_left; > >> + } > >> + rb_link_node(&member->handle_rb, rb, p); > >> + rb_insert_color(&member->handle_rb, &prime_fpriv->handles); > >> + > >> return 0; > >> } > >> > >> static struct dma_buf *drm_prime_lookup_buf_by_handle(struct drm_prime_file_private *prime_fpriv, > >> uint32_t handle) > >> { > >> - struct drm_prime_member *member; > >> + struct rb_node *rb; > >> + > >> + rb = prime_fpriv->handles.rb_node; > >> + while (rb) { > >> + struct drm_prime_member *member; > >> > >> - list_for_each_entry(member, &prime_fpriv->head, entry) { > >> + member = rb_entry(rb, struct drm_prime_member, handle_rb); > >> if (member->handle == handle) > >> return member->dma_buf; > >> + else if (member->handle < handle) > >> + rb = rb->rb_right; > >> + else > >> + rb = rb->rb_left; > >> } > >> > >> return NULL; > >> @@ -104,14 +146,23 @@ static int drm_prime_lookup_buf_handle(struct drm_prime_file_private *prime_fpri > >> struct dma_buf *dma_buf, > >> uint32_t *handle) > >> { > >> - struct drm_prime_member *member; > >> + struct rb_node *rb; > >> + > >> + rb = prime_fpriv->dmabufs.rb_node; > >> + while (rb) { > >> + struct drm_prime_member *member; > >> > >> - list_for_each_entry(member, &prime_fpriv->head, entry) { > >> + member = rb_entry(rb, struct drm_prime_member, dmabuf_rb); > >> if (member->dma_buf == dma_buf) { > >> *handle = member->handle; > >> return 0; > >> + } else if (member->dma_buf < dma_buf) { > >> + rb = rb->rb_right; > >> + } else { > >> + rb = rb->rb_left; > >> } > >> } > >> + > >> return -ENOENT; > >> } > >> > >> @@ -166,13 +217,24 @@ static void drm_gem_map_detach(struct dma_buf *dma_buf, > >> void drm_prime_remove_buf_handle_locked(struct drm_prime_file_private *prime_fpriv, > >> struct dma_buf *dma_buf) > >> { > >> - struct drm_prime_member *member, *safe; > >> + struct rb_node *rb; > >> > >> - list_for_each_entry_safe(member, safe, &prime_fpriv->head, entry) { > >> + rb = prime_fpriv->dmabufs.rb_node; > >> + while (rb) { > >> + struct drm_prime_member *member; > >> + > >> + member = rb_entry(rb, struct drm_prime_member, dmabuf_rb); > >> if (member->dma_buf == dma_buf) { > >> + rb_erase(&member->handle_rb, &prime_fpriv->handles); > >> + rb_erase(&member->dmabuf_rb, &prime_fpriv->dmabufs); > >> + > >> dma_buf_put(dma_buf); > >> - list_del(&member->entry); > >> kfree(member); > >> + return; > >> + } else if (member->dma_buf < dma_buf) { > >> + rb = rb->rb_right; > >> + } else { > >> + rb = rb->rb_left; > >> } > >> } > >> } > >> @@ -759,12 +821,13 @@ EXPORT_SYMBOL(drm_prime_gem_destroy); > >> > >> void drm_prime_init_file_private(struct drm_prime_file_private *prime_fpriv) > >> { > >> - INIT_LIST_HEAD(&prime_fpriv->head); > >> mutex_init(&prime_fpriv->lock); > >> + prime_fpriv->dmabufs = RB_ROOT; > >> + prime_fpriv->handles = RB_ROOT; > >> } > >> > >> void drm_prime_destroy_file_private(struct drm_prime_file_private *prime_fpriv) > >> { > >> /* by now drm_gem_release should've made sure the list is empty */ > >> - WARN_ON(!list_empty(&prime_fpriv->head)); > >> + WARN_ON(!RB_EMPTY_ROOT(&prime_fpriv->dmabufs)); > >> } > >> 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 */ > >> -- > >> 2.9.3 > >> > _______________________________________________ > dri-devel mailing list > dri-devel@xxxxxxxxxxxxxxxxxxxxx > https://lists.freedesktop.org/mailman/listinfo/dri-devel -- Daniel Vetter Software Engineer, Intel Corporation http://blog.ffwll.ch _______________________________________________ dri-devel mailing list dri-devel@xxxxxxxxxxxxxxxxxxxxx https://lists.freedesktop.org/mailman/listinfo/dri-devel
