Patch "dma-buf/sw-sync: Use an rbtree to sort fences in the timeline" has been added to the 4.9-stable tree

[<gregkh@linuxfoundation.org>]

This is a note to let you know that I've just added the patch titled

    dma-buf/sw-sync: Use an rbtree to sort fences in the timeline

to the 4.9-stable tree which can be found at:
    http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary

The filename of the patch is:
     dma-buf-sw-sync-use-an-rbtree-to-sort-fences-in-the-timeline.patch
and it can be found in the queue-4.9 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree,
please let <stable@vger.kernel.org> know about it.


>From f1e8c67123cf171e2b0357e885e426328b241d7d Mon Sep 17 00:00:00 2001
From: Chris Wilson <chris@chris-wilson.co.uk>
Date: Thu, 29 Jun 2017 22:12:53 +0100
Subject: dma-buf/sw-sync: Use an rbtree to sort fences in the timeline

From: Chris Wilson <chris@chris-wilson.co.uk>

commit f1e8c67123cf171e2b0357e885e426328b241d7d upstream.

Reduce the list iteration when incrementing the timeline by storing the
fences in increasing order.

v2: Prevent spinlock recursion on free during create
v3: Fixup rebase conflict inside comments that escaped the compiler.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Sumit Semwal <sumit.semwal@linaro.org>
Cc: Sean Paul <seanpaul@chromium.org>
Cc: Gustavo Padovan <gustavo@padovan.org>
Reviewed-by: Sean Paul <seanpaul@chromium.org>
Signed-off-by: Gustavo Padovan <gustavo.padovan@collabora.com>
Link: http://patchwork.freedesktop.org/patch/msgid/20170629211253.22766-1-chris@chris-wilson.co.uk
[s/dma_fence/fence/g - gregkh]
Cc: Jisheng Zhang <Jisheng.Zhang@synaptics.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>

---
 drivers/dma-buf/sw_sync.c    |   49 +++++++++++++++++++++++++++++++++++++------
 drivers/dma-buf/sync_debug.h |    5 ++++
 2 files changed, 48 insertions(+), 6 deletions(-)

--- a/drivers/dma-buf/sw_sync.c
+++ b/drivers/dma-buf/sw_sync.c
@@ -96,6 +96,7 @@ struct sync_timeline *sync_timeline_crea
 	obj->context = fence_context_alloc(1);
 	strlcpy(obj->name, name, sizeof(obj->name));
 
+	obj->pt_tree = RB_ROOT;
 	INIT_LIST_HEAD(&obj->pt_list);
 	spin_lock_init(&obj->lock);
 
@@ -142,9 +143,13 @@ static void sync_timeline_signal(struct
 
 	obj->value += inc;
 
-	list_for_each_entry_safe(pt, next, &obj->pt_list, link)
-		if (fence_is_signaled_locked(&pt->base))
-			list_del_init(&pt->link);
+	list_for_each_entry_safe(pt, next, &obj->pt_list, link) {
+		if (!fence_is_signaled_locked(&pt->base))
+			break;
+
+		list_del_init(&pt->link);
+		rb_erase(&pt->node, &obj->pt_tree);
+	}
 
 	spin_unlock_irq(&obj->lock);
 }
@@ -174,8 +179,38 @@ static struct sync_pt *sync_pt_create(st
 	INIT_LIST_HEAD(&pt->link);
 
 	spin_lock_irq(&obj->lock);
-	if (!fence_is_signaled_locked(&pt->base))
-		list_add_tail(&pt->link, &obj->pt_list);
+	if (!fence_is_signaled_locked(&pt->base)) {
+		struct rb_node **p = &obj->pt_tree.rb_node;
+		struct rb_node *parent = NULL;
+
+		while (*p) {
+			struct sync_pt *other;
+			int cmp;
+
+			parent = *p;
+			other = rb_entry(parent, typeof(*pt), node);
+			cmp = value - other->base.seqno;
+			if (cmp > 0) {
+				p = &parent->rb_right;
+			} else if (cmp < 0) {
+				p = &parent->rb_left;
+			} else {
+				if (fence_get_rcu(&other->base)) {
+					fence_put(&pt->base);
+					pt = other;
+					goto unlock;
+				}
+				p = &parent->rb_left;
+			}
+		}
+		rb_link_node(&pt->node, parent, p);
+		rb_insert_color(&pt->node, &obj->pt_tree);
+
+		parent = rb_next(&pt->node);
+		list_add_tail(&pt->link,
+			      parent ? &rb_entry(parent, typeof(*pt), node)->link : &obj->pt_list);
+	}
+unlock:
 	spin_unlock_irq(&obj->lock);
 
 	return pt;
@@ -202,8 +237,10 @@ static void timeline_fence_release(struc
 		unsigned long flags;
 
 		spin_lock_irqsave(fence->lock, flags);
-		if (!list_empty(&pt->link))
+		if (!list_empty(&pt->link)) {
 			list_del(&pt->link);
+			rb_erase(&pt->node, &parent->pt_tree);
+		}
 		spin_unlock_irqrestore(fence->lock, flags);
 	}
 
--- a/drivers/dma-buf/sync_debug.h
+++ b/drivers/dma-buf/sync_debug.h
@@ -14,6 +14,7 @@
 #define _LINUX_SYNC_H
 
 #include <linux/list.h>
+#include <linux/rbtree.h>
 #include <linux/spinlock.h>
 #include <linux/fence.h>
 
@@ -25,6 +26,7 @@
  * @kref:		reference count on fence.
  * @name:		name of the sync_timeline. Useful for debugging
  * @lock:		lock protecting @pt_list and @value
+ * @pt_tree:		rbtree of active (unsignaled/errored) sync_pts
  * @pt_list:		list of active (unsignaled/errored) sync_pts
  * @sync_timeline_list:	membership in global sync_timeline_list
  */
@@ -36,6 +38,7 @@ struct sync_timeline {
 	u64			context;
 	int			value;
 
+	struct rb_root		pt_tree;
 	struct list_head	pt_list;
 	spinlock_t		lock;
 
@@ -51,10 +54,12 @@ static inline struct sync_timeline *fenc
  * struct sync_pt - sync_pt object
  * @base: base fence object
  * @link: link on the sync timeline's list
+ * @node: node in the sync timeline's tree
  */
 struct sync_pt {
 	struct fence base;
 	struct list_head link;
+	struct rb_node node;
 };
 
 #ifdef CONFIG_SW_SYNC


Patches currently in stable-queue which might be from chris@chris-wilson.co.uk are

queue-4.9/dma-buf-sw-sync-fix-the-is-signaled-test-to-handle-u32-wraparound.patch
queue-4.9/dma-fence-clear-fence-status-during-dma_fence_init.patch
queue-4.9/dma-buf-sw-sync-fix-locking-around-sync_timeline-lists.patch
queue-4.9/dma-fence-wrap-querying-the-fence-status.patch
queue-4.9/dma-buf-sw_sync-clean-up-list-before-signaling-the-fence.patch
queue-4.9/dma-buf-sw-sync-reduce-irqsave-irqrestore-from-known-context.patch
queue-4.9/dma-buf-sw_sync-move-timeline_fence_ops-around.patch
queue-4.9/dma-buf-sw-sync-prevent-user-overflow-on-timeline-advance.patch
queue-4.9/dma-fence-introduce-drm_fence_set_error-helper.patch
queue-4.9/dma-buf-sw_sync-force-signal-all-unsignaled-fences-on-dying-timeline.patch
queue-4.9/dma-buf-sw-sync-use-an-rbtree-to-sort-fences-in-the-timeline.patch
queue-4.9/dma-buf-sw-sync-sync_pt-is-private-and-of-fixed-size.patch
queue-4.9/dma-buf-dma-fence-extract-__dma_fence_is_later.patch