Re: [PATCH] drm: Convert prime dma-buf <-> handle to rbtree

[Sean Paul <seanpaul@chromium.org>]

On Tue, Sep 27, 2016 at 2:36 AM, David Herrmann <dh.herrmann@gmail.com> wrote:
> Hi Chris
>
> On Mon, Sep 26, 2016 at 10:44 PM, Chris Wilson <chris@chris-wilson.co.uk> 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@chris-wilson.co.uk>
>> Cc: Sean Paul <seanpaul@chromium.org>
>> Cc: David Herrmann <dh.herrmann@gmail.com>
>> ---
>>  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@gmail.com>


Agreed, it's also nice be able to keep the WARN_ON in
drm_prime_destroy_file_private

Reviewed-by: Sean Paul <seanpaul@chromium.org>

>
> 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
>>
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx