* [PATCH] drm: Convert prime dma-buf <-> handle to rhashtable
@ 2016-09-22 14:43 Chris Wilson
2016-09-22 15:49 ` ✗ Fi.CI.BAT: warning for " Patchwork
` (3 more replies)
0 siblings, 4 replies; 8+ messages in thread
From: Chris Wilson @ 2016-09-22 14:43 UTC (permalink / raw)
To: dri-devel; +Cc: intel-gfx
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!).
Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=94631
Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
---
drivers/gpu/drm/drm_prime.c | 94 +++++++++++++++++++++++++++++++++++----------
include/drm/drmP.h | 5 ++-
2 files changed, 77 insertions(+), 22 deletions(-)
diff --git a/drivers/gpu/drm/drm_prime.c b/drivers/gpu/drm/drm_prime.c
index 780589b420a4..ad077def660d 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/rhashtable.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 rhash_head dma_buf_rht;
+ struct rhash_head handle_rht;
};
struct drm_prime_attachment {
@@ -71,10 +74,31 @@ struct drm_prime_attachment {
enum dma_data_direction dir;
};
+static const struct rhashtable_params dma_buf_params = {
+ .head_offset = offsetof(struct drm_prime_member, dma_buf_rht),
+ .key_len = sizeof(struct dma_buf *),
+ .key_offset = offsetof(struct drm_prime_member, dma_buf),
+ .hashfn = jhash,
+ .nulls_base = 1u << RHT_BASE_SHIFT,
+ .automatic_shrinking = true,
+ .nelem_hint = 2,
+};
+
+static const struct rhashtable_params handle_params = {
+ .head_offset = offsetof(struct drm_prime_member, handle_rht),
+ .key_len = sizeof(uint32_t),
+ .key_offset = offsetof(struct drm_prime_member, handle),
+ .hashfn = jhash,
+ .nulls_base = 1u << RHT_BASE_SHIFT,
+ .automatic_shrinking = true,
+ .nelem_hint = 2,
+};
+
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;
+ int err;
member = kmalloc(sizeof(*member), GFP_KERNEL);
if (!member)
@@ -83,8 +107,28 @@ 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);
+
+ err = rhashtable_insert_fast(&prime_fpriv->dma_bufs,
+ &member->dma_buf_rht,
+ dma_buf_params);
+ if (err)
+ goto err_dma_buf;
+
+ err = rhashtable_insert_fast(&prime_fpriv->handles,
+ &member->handle_rht,
+ handle_params);
+ if (err)
+ goto err_dma_rht;
+
return 0;
+
+err_dma_rht:
+ rhashtable_remove_fast(&prime_fpriv->dma_bufs,
+ &member->dma_buf_rht,
+ dma_buf_params);
+err_dma_buf:
+ dma_buf_put(dma_buf);
+ return err;
}
static struct dma_buf *drm_prime_lookup_buf_by_handle(struct drm_prime_file_private *prime_fpriv,
@@ -92,10 +136,10 @@ static struct dma_buf *drm_prime_lookup_buf_by_handle(struct drm_prime_file_priv
{
struct drm_prime_member *member;
- list_for_each_entry(member, &prime_fpriv->head, entry) {
- if (member->handle == handle)
- return member->dma_buf;
- }
+ member = rhashtable_lookup_fast(&prime_fpriv->handles,
+ &handle, handle_params);
+ if (member)
+ return member->dma_buf;
return NULL;
}
@@ -106,12 +150,13 @@ static int drm_prime_lookup_buf_handle(struct drm_prime_file_private *prime_fpri
{
struct drm_prime_member *member;
- list_for_each_entry(member, &prime_fpriv->head, entry) {
- if (member->dma_buf == dma_buf) {
- *handle = member->handle;
- return 0;
- }
+ member = rhashtable_lookup_fast(&prime_fpriv->dma_bufs,
+ &dma_buf, dma_buf_params);
+ if (member) {
+ *handle = member->handle;
+ return 0;
}
+
return -ENOENT;
}
@@ -166,14 +211,21 @@ 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 drm_prime_member *member;
- list_for_each_entry_safe(member, safe, &prime_fpriv->head, entry) {
- if (member->dma_buf == dma_buf) {
- dma_buf_put(dma_buf);
- list_del(&member->entry);
- kfree(member);
- }
+ member = rhashtable_lookup_fast(&prime_fpriv->dma_bufs,
+ &dma_buf, dma_buf_params);
+ if (member) {
+ rhashtable_remove_fast(&prime_fpriv->dma_bufs,
+ &member->dma_buf_rht,
+ dma_buf_params);
+
+ rhashtable_remove_fast(&prime_fpriv->handles,
+ &member->handle_rht,
+ handle_params);
+
+ dma_buf_put(dma_buf);
+ kfree(member);
}
}
@@ -759,12 +811,14 @@ 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);
+ rhashtable_init(&prime_fpriv->dma_bufs, &dma_buf_params);
+ rhashtable_init(&prime_fpriv->handles, &handle_params);
}
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));
+ rhashtable_destroy(&prime_fpriv->dma_bufs);
+ rhashtable_destroy(&prime_fpriv->handles);
}
diff --git a/include/drm/drmP.h b/include/drm/drmP.h
index c53dc90942e0..6966fb030d0f 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/rhashtable.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 rhashtable dma_bufs;
+ struct rhashtable handles;
};
/** File private data */
--
2.9.3
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply related [flat|nested] 8+ messages in thread* ✗ Fi.CI.BAT: warning for drm: Convert prime dma-buf <-> handle to rhashtable
2016-09-22 14:43 [PATCH] drm: Convert prime dma-buf <-> handle to rhashtable Chris Wilson
@ 2016-09-22 15:49 ` Patchwork
2016-09-23 10:27 ` [PATCH] " Sean Paul
` (2 subsequent siblings)
3 siblings, 0 replies; 8+ messages in thread
From: Patchwork @ 2016-09-22 15:49 UTC (permalink / raw)
To: Chris Wilson; +Cc: intel-gfx
== Series Details ==
Series: drm: Convert prime dma-buf <-> handle to rhashtable
URL : https://patchwork.freedesktop.org/series/12787/
State : warning
== Summary ==
Series 12787v1 drm: Convert prime dma-buf <-> handle to rhashtable
https://patchwork.freedesktop.org/api/1.0/series/12787/revisions/1/mbox/
Test kms_pipe_crc_basic:
Subgroup hang-read-crc-pipe-b:
dmesg-warn -> PASS (fi-hsw-4770k)
Subgroup nonblocking-crc-pipe-b:
pass -> DMESG-WARN (fi-skl-6770hq)
fi-bdw-5557u total:244 pass:222 dwarn:0 dfail:0 fail:7 skip:15
fi-bsw-n3050 total:244 pass:191 dwarn:0 dfail:0 fail:23 skip:30
fi-byt-n2820 total:244 pass:190 dwarn:0 dfail:0 fail:19 skip:35
fi-hsw-4770k total:244 pass:215 dwarn:0 dfail:0 fail:7 skip:22
fi-hsw-4770r total:244 pass:215 dwarn:0 dfail:0 fail:7 skip:22
fi-ilk-650 total:244 pass:176 dwarn:0 dfail:0 fail:8 skip:60
fi-ivb-3520m total:244 pass:212 dwarn:0 dfail:0 fail:7 skip:25
fi-ivb-3770 total:244 pass:207 dwarn:0 dfail:0 fail:0 skip:37
fi-skl-6260u total:244 pass:223 dwarn:0 dfail:0 fail:7 skip:14
fi-skl-6700hq total:244 pass:213 dwarn:1 dfail:0 fail:8 skip:22
fi-skl-6700k total:244 pass:212 dwarn:1 dfail:0 fail:7 skip:24
fi-skl-6770hq total:244 pass:220 dwarn:2 dfail:0 fail:8 skip:14
fi-snb-2520m total:244 pass:202 dwarn:0 dfail:0 fail:6 skip:36
fi-snb-2600 total:244 pass:200 dwarn:0 dfail:0 fail:6 skip:38
Results at /archive/results/CI_IGT_test/Patchwork_2569/
405fa9d85079a608a4f0da0e6136822c005e1c4b drm-intel-nightly: 2016y-09m-22d-12h-10m-28s UTC integration manifest
4e76cda drm: Convert prime dma-buf <-> handle to rhashtable
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [PATCH] drm: Convert prime dma-buf <-> handle to rhashtable
2016-09-22 14:43 [PATCH] drm: Convert prime dma-buf <-> handle to rhashtable Chris Wilson
2016-09-22 15:49 ` ✗ Fi.CI.BAT: warning for " Patchwork
@ 2016-09-23 10:27 ` Sean Paul
2016-09-26 20:44 ` [PATCH] drm: Convert prime dma-buf <-> handle to rbtree Chris Wilson
2016-09-26 21:23 ` ✗ Fi.CI.BAT: warning for drm: Convert prime dma-buf <-> handle to rhashtable (rev2) Patchwork
3 siblings, 0 replies; 8+ messages in thread
From: Sean Paul @ 2016-09-23 10:27 UTC (permalink / raw)
To: Chris Wilson; +Cc: Intel Graphics Development, dri-devel
On Thu, Sep 22, 2016 at 7:43 AM, 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!).
>
> Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=94631
> Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Looks like a nice improvement
Reviewed-by: Sean Paul <seanpaul@chromium.org>
> ---
> drivers/gpu/drm/drm_prime.c | 94 +++++++++++++++++++++++++++++++++++----------
> include/drm/drmP.h | 5 ++-
> 2 files changed, 77 insertions(+), 22 deletions(-)
>
> diff --git a/drivers/gpu/drm/drm_prime.c b/drivers/gpu/drm/drm_prime.c
> index 780589b420a4..ad077def660d 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/rhashtable.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 rhash_head dma_buf_rht;
> + struct rhash_head handle_rht;
> };
>
> struct drm_prime_attachment {
> @@ -71,10 +74,31 @@ struct drm_prime_attachment {
> enum dma_data_direction dir;
> };
>
> +static const struct rhashtable_params dma_buf_params = {
> + .head_offset = offsetof(struct drm_prime_member, dma_buf_rht),
> + .key_len = sizeof(struct dma_buf *),
> + .key_offset = offsetof(struct drm_prime_member, dma_buf),
> + .hashfn = jhash,
> + .nulls_base = 1u << RHT_BASE_SHIFT,
> + .automatic_shrinking = true,
> + .nelem_hint = 2,
> +};
> +
> +static const struct rhashtable_params handle_params = {
> + .head_offset = offsetof(struct drm_prime_member, handle_rht),
> + .key_len = sizeof(uint32_t),
> + .key_offset = offsetof(struct drm_prime_member, handle),
> + .hashfn = jhash,
> + .nulls_base = 1u << RHT_BASE_SHIFT,
> + .automatic_shrinking = true,
> + .nelem_hint = 2,
> +};
> +
> 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;
> + int err;
>
> member = kmalloc(sizeof(*member), GFP_KERNEL);
> if (!member)
> @@ -83,8 +107,28 @@ 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);
> +
> + err = rhashtable_insert_fast(&prime_fpriv->dma_bufs,
> + &member->dma_buf_rht,
> + dma_buf_params);
> + if (err)
> + goto err_dma_buf;
> +
> + err = rhashtable_insert_fast(&prime_fpriv->handles,
> + &member->handle_rht,
> + handle_params);
> + if (err)
> + goto err_dma_rht;
> +
> return 0;
> +
> +err_dma_rht:
> + rhashtable_remove_fast(&prime_fpriv->dma_bufs,
> + &member->dma_buf_rht,
> + dma_buf_params);
> +err_dma_buf:
> + dma_buf_put(dma_buf);
> + return err;
> }
>
> static struct dma_buf *drm_prime_lookup_buf_by_handle(struct drm_prime_file_private *prime_fpriv,
> @@ -92,10 +136,10 @@ static struct dma_buf *drm_prime_lookup_buf_by_handle(struct drm_prime_file_priv
> {
> struct drm_prime_member *member;
>
> - list_for_each_entry(member, &prime_fpriv->head, entry) {
> - if (member->handle == handle)
> - return member->dma_buf;
> - }
> + member = rhashtable_lookup_fast(&prime_fpriv->handles,
> + &handle, handle_params);
> + if (member)
> + return member->dma_buf;
>
> return NULL;
> }
> @@ -106,12 +150,13 @@ static int drm_prime_lookup_buf_handle(struct drm_prime_file_private *prime_fpri
> {
> struct drm_prime_member *member;
>
> - list_for_each_entry(member, &prime_fpriv->head, entry) {
> - if (member->dma_buf == dma_buf) {
> - *handle = member->handle;
> - return 0;
> - }
> + member = rhashtable_lookup_fast(&prime_fpriv->dma_bufs,
> + &dma_buf, dma_buf_params);
> + if (member) {
> + *handle = member->handle;
> + return 0;
> }
> +
> return -ENOENT;
> }
>
> @@ -166,14 +211,21 @@ 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 drm_prime_member *member;
>
> - list_for_each_entry_safe(member, safe, &prime_fpriv->head, entry) {
> - if (member->dma_buf == dma_buf) {
> - dma_buf_put(dma_buf);
> - list_del(&member->entry);
> - kfree(member);
> - }
> + member = rhashtable_lookup_fast(&prime_fpriv->dma_bufs,
> + &dma_buf, dma_buf_params);
> + if (member) {
> + rhashtable_remove_fast(&prime_fpriv->dma_bufs,
> + &member->dma_buf_rht,
> + dma_buf_params);
> +
> + rhashtable_remove_fast(&prime_fpriv->handles,
> + &member->handle_rht,
> + handle_params);
> +
> + dma_buf_put(dma_buf);
> + kfree(member);
> }
> }
>
> @@ -759,12 +811,14 @@ 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);
> + rhashtable_init(&prime_fpriv->dma_bufs, &dma_buf_params);
> + rhashtable_init(&prime_fpriv->handles, &handle_params);
> }
>
> 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));
> + rhashtable_destroy(&prime_fpriv->dma_bufs);
> + rhashtable_destroy(&prime_fpriv->handles);
> }
> diff --git a/include/drm/drmP.h b/include/drm/drmP.h
> index c53dc90942e0..6966fb030d0f 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/rhashtable.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 rhashtable dma_bufs;
> + struct rhashtable handles;
> };
>
> /** File private data */
> --
> 2.9.3
>
> _______________________________________________
> Intel-gfx mailing list
> Intel-gfx@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/intel-gfx
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx
^ permalink raw reply [flat|nested] 8+ messages in thread* [PATCH] drm: Convert prime dma-buf <-> handle to rbtree
2016-09-22 14:43 [PATCH] drm: Convert prime dma-buf <-> handle to rhashtable Chris Wilson
2016-09-22 15:49 ` ✗ Fi.CI.BAT: warning for " Patchwork
2016-09-23 10:27 ` [PATCH] " Sean Paul
@ 2016-09-26 20:44 ` Chris Wilson
2016-09-27 6:36 ` David Herrmann
2016-09-26 21:23 ` ✗ Fi.CI.BAT: warning for drm: Convert prime dma-buf <-> handle to rhashtable (rev2) Patchwork
3 siblings, 1 reply; 8+ messages in thread
From: Chris Wilson @ 2016-09-26 20:44 UTC (permalink / raw)
To: dri-devel; +Cc: intel-gfx
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(-)
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@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply related [flat|nested] 8+ messages in thread* Re: [PATCH] drm: Convert prime dma-buf <-> handle to rbtree
2016-09-26 20:44 ` [PATCH] drm: Convert prime dma-buf <-> handle to rbtree Chris Wilson
@ 2016-09-27 6:36 ` David Herrmann
2016-09-27 16:18 ` Sean Paul
0 siblings, 1 reply; 8+ messages in thread
From: David Herrmann @ 2016-09-27 6:36 UTC (permalink / raw)
To: Chris Wilson; +Cc: Intel Graphics Development, dri-devel
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>
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@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [PATCH] drm: Convert prime dma-buf <-> handle to rbtree
2016-09-27 6:36 ` David Herrmann
@ 2016-09-27 16:18 ` Sean Paul
2016-09-29 9:21 ` Daniel Vetter
0 siblings, 1 reply; 8+ messages in thread
From: Sean Paul @ 2016-09-27 16:18 UTC (permalink / raw)
To: David Herrmann; +Cc: Intel Graphics Development, dri-devel
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
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [PATCH] drm: Convert prime dma-buf <-> handle to rbtree
2016-09-27 16:18 ` Sean Paul
@ 2016-09-29 9:21 ` Daniel Vetter
0 siblings, 0 replies; 8+ messages in thread
From: Daniel Vetter @ 2016-09-29 9:21 UTC (permalink / raw)
To: Sean Paul; +Cc: Intel Graphics Development, dri-devel
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@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>
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@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/dri-devel
--
Daniel Vetter
Software Engineer, Intel Corporation
http://blog.ffwll.ch
_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/dri-devel
^ permalink raw reply [flat|nested] 8+ messages in thread
* ✗ Fi.CI.BAT: warning for drm: Convert prime dma-buf <-> handle to rhashtable (rev2)
2016-09-22 14:43 [PATCH] drm: Convert prime dma-buf <-> handle to rhashtable Chris Wilson
` (2 preceding siblings ...)
2016-09-26 20:44 ` [PATCH] drm: Convert prime dma-buf <-> handle to rbtree Chris Wilson
@ 2016-09-26 21:23 ` Patchwork
3 siblings, 0 replies; 8+ messages in thread
From: Patchwork @ 2016-09-26 21:23 UTC (permalink / raw)
To: Chris Wilson; +Cc: intel-gfx
== Series Details ==
Series: drm: Convert prime dma-buf <-> handle to rhashtable (rev2)
URL : https://patchwork.freedesktop.org/series/12787/
State : warning
== Summary ==
Series 12787v2 drm: Convert prime dma-buf <-> handle to rhashtable
https://patchwork.freedesktop.org/api/1.0/series/12787/revisions/2/mbox/
Test gem_exec_gttfill:
Subgroup basic:
pass -> SKIP (fi-snb-2600)
pass -> SKIP (fi-byt-n2820)
pass -> SKIP (fi-snb-2520m)
pass -> SKIP (fi-ivb-3770)
pass -> SKIP (fi-ivb-3520m)
Test kms_psr_sink_crc:
Subgroup psr_basic:
dmesg-warn -> PASS (fi-skl-6700hq)
fi-bdw-5557u total:244 pass:229 dwarn:0 dfail:0 fail:0 skip:15
fi-bsw-n3050 total:244 pass:202 dwarn:0 dfail:0 fail:0 skip:42
fi-byt-n2820 total:244 pass:207 dwarn:0 dfail:0 fail:1 skip:36
fi-hsw-4770 total:244 pass:222 dwarn:0 dfail:0 fail:0 skip:22
fi-hsw-4770r total:244 pass:222 dwarn:0 dfail:0 fail:0 skip:22
fi-ilk-650 total:244 pass:182 dwarn:0 dfail:0 fail:2 skip:60
fi-ivb-3520m total:244 pass:218 dwarn:0 dfail:0 fail:0 skip:26
fi-ivb-3770 total:244 pass:206 dwarn:0 dfail:0 fail:0 skip:38
fi-skl-6260u total:244 pass:230 dwarn:0 dfail:0 fail:0 skip:14
fi-skl-6700hq total:244 pass:222 dwarn:0 dfail:0 fail:0 skip:22
fi-skl-6700k total:244 pass:219 dwarn:1 dfail:0 fail:0 skip:24
fi-skl-6770hq total:244 pass:228 dwarn:1 dfail:0 fail:1 skip:14
fi-snb-2520m total:244 pass:207 dwarn:0 dfail:0 fail:0 skip:37
fi-snb-2600 total:244 pass:206 dwarn:0 dfail:0 fail:0 skip:38
Results at /archive/results/CI_IGT_test/Patchwork_2579/
aab15c274da587bcab19376d2caa9d6626440335 drm-intel-nightly: 2016y-09m-26d-12h-11m-33s UTC integration manifest
74e4f9b drm: Convert prime dma-buf <-> handle to rbtree
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2016-09-29 9:21 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-09-22 14:43 [PATCH] drm: Convert prime dma-buf <-> handle to rhashtable Chris Wilson
2016-09-22 15:49 ` ✗ Fi.CI.BAT: warning for " Patchwork
2016-09-23 10:27 ` [PATCH] " Sean Paul
2016-09-26 20:44 ` [PATCH] drm: Convert prime dma-buf <-> handle to rbtree Chris Wilson
2016-09-27 6:36 ` David Herrmann
2016-09-27 16:18 ` Sean Paul
2016-09-29 9:21 ` Daniel Vetter
2016-09-26 21:23 ` ✗ Fi.CI.BAT: warning for drm: Convert prime dma-buf <-> handle to rhashtable (rev2) Patchwork
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.