From: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
To: linux-kernel@vger.kernel.org
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
stable@vger.kernel.org, Chris Wilson <chris@chris-wilson.co.uk>,
Sumit Semwal <sumit.semwal@linaro.org>,
Sean Paul <seanpaul@chromium.org>,
Gustavo Padovan <gustavo@padovan.org>,
Gustavo Padovan <gustavo.padovan@collabora.com>,
Jisheng Zhang <Jisheng.Zhang@synaptics.com>
Subject: [PATCH 4.9 094/109] dma-buf/sw-sync: Use an rbtree to sort fences in the timeline
Date: Thu, 7 Dec 2017 13:57:18 +0100 [thread overview]
Message-ID: <20171207125645.458257410@linuxfoundation.org> (raw)
In-Reply-To: <20171207125634.631485452@linuxfoundation.org>
4.9-stable review patch. If anyone has any objections, please let me know.
------------------
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
next prev parent reply other threads:[~2017-12-07 12:57 UTC|newest]
Thread overview: 120+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-12-07 12:55 [PATCH 4.9 000/109] 4.9.68-stable review Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 001/109] bcache: only permit to recovery read error when cache device is clean Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 002/109] bcache: recover data from backing when data " Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 003/109] drm/fsl-dcu: avoid disabling pixel clock twice on suspend Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 004/109] drm/fsl-dcu: enable IRQ before drm_atomic_helper_resume() Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 006/109] mm, oom_reaper: gather each vma to prevent leaking TLB entry Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 007/109] uas: Always apply US_FL_NO_ATA_1X quirk to Seagate devices Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 008/109] usb: quirks: Add no-lpm quirk for KY-688 USB 3.1 Type-C Hub Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 009/109] serial: 8250_pci: Add Amazon PCI serial device ID Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 010/109] s390/runtime instrumentation: simplify task exit handling Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 011/109] USB: serial: option: add Quectel BG96 id Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 012/109] ima: fix hash algorithm initialization Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 013/109] s390/pci: do not require AIS facility Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 014/109] selftests/x86/ldt_get: Add a few additional tests for limits Greg Kroah-Hartman
2017-12-07 12:55 ` [PATCH 4.9 015/109] staging: greybus: loopback: Fix iteration count on async path Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 016/109] m68k: fix ColdFire node shift size calculation Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 017/109] serial: 8250_fintek: Fix rs485 disablement on invalid ioctl() Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 018/109] staging: rtl8188eu: avoid a null dereference on pmlmepriv Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 019/109] spi: sh-msiof: Fix DMA transfer size check Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 020/109] spi: spi-axi: fix potential use-after-free after deregistration Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 021/109] mmc: sdhci-msm: fix issue with power irq Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 022/109] usb: dwc2: Fix UDC state tracking Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 023/109] usb: dwc2: Error out of dwc2_hsotg_ep_disable() if were in host mode Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 024/109] usb: phy: tahvo: fix error handling in tahvo_usb_probe() Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 025/109] serial: 8250: Preserve DLD[7:4] for PORT_XR17V35X Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 026/109] x86/entry: Use SYSCALL_DEFINE() macros for sys_modify_ldt() Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 027/109] EDAC, sb_edac: Fix missing break in switch Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 028/109] sysrq : fix Show Regs call trace on ARM Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 029/109] usbip: tools: Install all headers needed for libusbip development Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 030/109] perf test attr: Fix ignored test case result Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 031/109] kprobes/x86: Disable preemption in ftrace-based jprobes Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 034/109] dax: Avoid page invalidation races and unnecessary radix tree traversals Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 035/109] net/mlx4_en: Fix type mismatch for 32-bit systems Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 036/109] l2tp: take remote address into account in l2tp_ip and l2tp_ip6 socket lookups Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 037/109] dmaengine: stm32-dma: Set correct args number for DMA request from DT Greg Kroah-Hartman
2017-12-07 13:03 ` Ludovic BARRE
2017-12-07 13:14 ` Pierre Yves MORDRET
2017-12-07 13:50 ` Greg Kroah-Hartman
2017-12-07 14:04 ` Pierre Yves MORDRET
2017-12-07 15:40 ` alexander.levin
2017-12-07 16:49 ` Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 038/109] dmaengine: stm32-dma: Fix null pointer dereference in stm32_dma_tx_status Greg Kroah-Hartman
2017-12-07 13:04 ` Ludovic BARRE
2017-12-07 13:18 ` Ludovic BARRE
2017-12-07 13:26 ` Pierre Yves MORDRET
2017-12-07 13:41 ` Pierre Yves MORDRET
2017-12-07 14:00 ` Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 039/109] usb: gadget: f_fs: Fix ExtCompat descriptor validation Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 040/109] libcxgb: fix error check for ip6_route_output() Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 041/109] net: systemport: Utilize skb_put_padto() Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 042/109] net: systemport: Pad packet before inserting TSB Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 043/109] ARM: OMAP2+: Fix WL1283 Bluetooth Baud Rate Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 044/109] ARM: OMAP1: DMA: Correct the number of logical channels Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 045/109] vti6: fix device register to report IFLA_INFO_KIND Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 046/109] be2net: fix accesses to unicast list Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 047/109] be2net: fix unicast list filling Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 048/109] net/appletalk: Fix kernel memory disclosure Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 049/109] libfs: Modify mount_pseudo_xattr to be clear it is not a userspace mount Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 050/109] net: qrtr: Mark buf as little endian Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 051/109] mm: fix remote numa hits statistics Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 052/109] mac80211: calculate min channel width correctly Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 053/109] ravb: Remove Rx overflow log messages Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 054/109] nfs: Dont take a reference on fl->fl_file for LOCK operation Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 055/109] drm/exynos/decon5433: update shadow registers iff there are active windows Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 056/109] drm/exynos/decon5433: set STANDALONE_UPDATE_F also if planes are disabled Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 057/109] KVM: arm/arm64: Fix occasional warning from the timer work function Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 058/109] mac80211: prevent skb/txq mismatch Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 059/109] NFSv4: Fix client recovery when server reboots multiple times Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 060/109] perf/x86/intel: Account interrupts for PEBS errors Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 061/109] powerpc/mm: Fix memory hotplug BUG() on radix Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 062/109] qla2xxx: Fix wrong IOCB type assumption Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 064/109] drm/exynos/decon5433: set STANDALONE_UPDATE_F on output enablement Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 065/109] net: sctp: fix array overrun read on sctp_timer_tbl Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 066/109] x86/fpu: Set the xcomp_bv when we fake up a XSAVES area Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 068/109] mac80211: dont try to sleep in rate_control_rate_init() Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 069/109] RDMA/qedr: Return success when not changing QP state Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 070/109] RDMA/qedr: Fix RDMA CM loopback Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 071/109] tipc: fix nametbl_lock soft lockup at module exit Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 072/109] tipc: fix cleanup at module unload Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 073/109] dmaengine: pl330: fix double lock Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 074/109] tcp: correct memory barrier usage in tcp_check_space() Greg Kroah-Hartman
2017-12-07 12:56 ` [PATCH 4.9 075/109] i2c: i2c-cadence: Initialize configuration before probing devices Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 076/109] nvmet: cancel fatal error and flush async work before free controller Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 077/109] gtp: clear DF bit on GTP packet tx Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 078/109] gtp: fix cross netns recv on gtp socket Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 079/109] net: phy: micrel: KSZ8795 do not set SUPPORTED_[Asym_]Pause Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 081/109] be2net: fix initial MAC setting Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 082/109] vfio/spapr: Fix missing mutex unlock when creating a window Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 083/109] mm: avoid returning VM_FAULT_RETRY from ->page_mkwrite handlers Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 084/109] xen-netfront: Improve error handling during initialization Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 085/109] [media] cec: initiator should be the same as the destination for, poll Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 086/109] xen-netback: vif counters from int/long to u64 Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 087/109] net: fec: fix multicast filtering hardware setup Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 088/109] dma-buf/dma-fence: Extract __dma_fence_is_later() Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 089/109] dma-buf/sw-sync: Fix the is-signaled test to handle u32 wraparound Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 090/109] dma-buf/sw-sync: Prevent user overflow on timeline advance Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 091/109] dma-buf/sw-sync: Reduce irqsave/irqrestore from known context Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 092/109] dma-buf/sw-sync: sync_pt is private and of fixed size Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 093/109] dma-buf/sw-sync: Fix locking around sync_timeline lists Greg Kroah-Hartman
2017-12-07 12:57 ` Greg Kroah-Hartman [this message]
2017-12-07 12:57 ` [PATCH 4.9 095/109] dma-buf/sw_sync: move timeline_fence_ops around Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 096/109] dma-buf/sw_sync: clean up list before signaling the fence Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 097/109] dma-fence: Clear fence->status during dma_fence_init() Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 098/109] dma-fence: Wrap querying the fence->status Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 099/109] dma-fence: Introduce drm_fence_set_error() helper Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 100/109] dma-buf/sw_sync: force signal all unsignaled fences on dying timeline Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 101/109] dma-buf/sync_file: hold reference to fence when creating sync_file Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 102/109] dma-buf: Update kerneldoc for sync_file_create Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 103/109] usb: hub: Cycle HUB power when initialization fails Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 104/109] usb: xhci: fix panic in xhci_free_virt_devices_depth_first Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 105/109] USB: core: Add type-specific length check of BOS descriptors Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 106/109] USB: Increase usbfs transfer limit Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 107/109] USB: devio: Prevent integer overflow in proc_do_submiturb() Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 108/109] USB: usbfs: Filter flags passed in from user space Greg Kroah-Hartman
2017-12-07 12:57 ` [PATCH 4.9 109/109] usb: host: fix incorrect updating of offset Greg Kroah-Hartman
2017-12-07 20:55 ` [PATCH 4.9 000/109] 4.9.68-stable review Guenter Roeck
2017-12-08 0:07 ` Shuah Khan
2017-12-08 5:35 ` Naresh Kamboju
2017-12-08 13:58 ` Greg Kroah-Hartman
2017-12-08 14:04 ` Milosz Wasilewski
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20171207125645.458257410@linuxfoundation.org \
--to=gregkh@linuxfoundation.org \
--cc=Jisheng.Zhang@synaptics.com \
--cc=chris@chris-wilson.co.uk \
--cc=gustavo.padovan@collabora.com \
--cc=gustavo@padovan.org \
--cc=linux-kernel@vger.kernel.org \
--cc=seanpaul@chromium.org \
--cc=stable@vger.kernel.org \
--cc=sumit.semwal@linaro.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).