From: Chris Wilson <chris@chris-wilson.co.uk> To: akpm@linux-foundation.org Cc: linux-kernel@vger.kernel.org, dri-devel@lists.freedesktop.org, intel-gfx@lists.freedesktop.org, "Chris Wilson" <chris@chris-wilson.co.uk>, "Davidlohr Bueso" <dbueso@suse.de>, "Jérôme Glisse" <jglisse@redhat.com>, "Joonas Lahtinen" <joonas.lahtinen@linux.intel.com>, "Daniel Vetter" <daniel.vetter@ffwll.ch> Subject: [PATCH] lib/rbtree,drm/mm: Add rbtree_replace_node_cached() Date: Wed, 22 Nov 2017 10:07:29 +0000 [thread overview] Message-ID: <20171122100729.3742-1-chris@chris-wilson.co.uk> (raw) In-Reply-To: <20171109212435.9265-1-chris@chris-wilson.co.uk> Add a variant of rbtree_replace_node() that maintains the leftmost cache of struct rbtree_root_cached when replacing nodes within the rbtree. As drm_mm is the only rb_replace_node() being used on an interval tree, the mistake looks fairly self-contained. Furthermore the only user of drm_mm_replace_node() is its testsuite... Fixes: f808c13fd373 ("lib/interval_tree: fast overlap detection") Testcase: igt/drm_mm/replace Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk> Cc: Davidlohr Bueso <dbueso@suse.de> Cc: Jérôme Glisse <jglisse@redhat.com> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com> Cc: Daniel Vetter <daniel.vetter@ffwll.ch> Link: https://patchwork.freedesktop.org/patch/msgid/20171109212435.9265-1-chris@chris-wilson.co.uk Acked-by: Davidlohr Bueso <dbueso@suse.de> Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com> --- drivers/gpu/drm/drm_mm.c | 8 +++++--- include/linux/rbtree.h | 2 ++ lib/rbtree.c | 10 ++++++++++ 3 files changed, 17 insertions(+), 3 deletions(-) diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 61a1c8ea74bc..c3c79ee6119e 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -575,21 +575,23 @@ EXPORT_SYMBOL(drm_mm_remove_node); */ void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new) { + struct drm_mm *mm = old->mm; + DRM_MM_BUG_ON(!old->allocated); *new = *old; list_replace(&old->node_list, &new->node_list); - rb_replace_node(&old->rb, &new->rb, &old->mm->interval_tree.rb_root); + rb_replace_node_cached(&old->rb, &new->rb, &mm->interval_tree); if (drm_mm_hole_follows(old)) { list_replace(&old->hole_stack, &new->hole_stack); rb_replace_node(&old->rb_hole_size, &new->rb_hole_size, - &old->mm->holes_size); + &mm->holes_size); rb_replace_node(&old->rb_hole_addr, &new->rb_hole_addr, - &old->mm->holes_addr); + &mm->holes_addr); } old->allocated = false; diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index d574361943ea..fcbeed4053ef 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -99,6 +99,8 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root); extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, struct rb_root *root); +extern void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new, + struct rb_root_cached *root); static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link) diff --git a/lib/rbtree.c b/lib/rbtree.c index ba4a9d165f1b..d3ff682fd4b8 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -603,6 +603,16 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, } EXPORT_SYMBOL(rb_replace_node); +void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new, + struct rb_root_cached *root) +{ + rb_replace_node(victim, new, &root->rb_root); + + if (root->rb_leftmost == victim) + root->rb_leftmost = new; +} +EXPORT_SYMBOL(rb_replace_node_cached); + void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { -- 2.15.0
WARNING: multiple messages have this Message-ID (diff)
From: Chris Wilson <chris@chris-wilson.co.uk> To: akpm@linux-foundation.org Cc: "Davidlohr Bueso" <dbueso@suse.de>, "Daniel Vetter" <daniel.vetter@ffwll.ch>, intel-gfx@lists.freedesktop.org, "Joonas Lahtinen" <joonas.lahtinen@linux.intel.com>, linux-kernel@vger.kernel.org, dri-devel@lists.freedesktop.org, "Jérôme Glisse" <jglisse@redhat.com> Subject: [PATCH] lib/rbtree,drm/mm: Add rbtree_replace_node_cached() Date: Wed, 22 Nov 2017 10:07:29 +0000 [thread overview] Message-ID: <20171122100729.3742-1-chris@chris-wilson.co.uk> (raw) In-Reply-To: <20171109212435.9265-1-chris@chris-wilson.co.uk> Add a variant of rbtree_replace_node() that maintains the leftmost cache of struct rbtree_root_cached when replacing nodes within the rbtree. As drm_mm is the only rb_replace_node() being used on an interval tree, the mistake looks fairly self-contained. Furthermore the only user of drm_mm_replace_node() is its testsuite... Fixes: f808c13fd373 ("lib/interval_tree: fast overlap detection") Testcase: igt/drm_mm/replace Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk> Cc: Davidlohr Bueso <dbueso@suse.de> Cc: Jérôme Glisse <jglisse@redhat.com> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com> Cc: Daniel Vetter <daniel.vetter@ffwll.ch> Link: https://patchwork.freedesktop.org/patch/msgid/20171109212435.9265-1-chris@chris-wilson.co.uk Acked-by: Davidlohr Bueso <dbueso@suse.de> Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com> --- drivers/gpu/drm/drm_mm.c | 8 +++++--- include/linux/rbtree.h | 2 ++ lib/rbtree.c | 10 ++++++++++ 3 files changed, 17 insertions(+), 3 deletions(-) diff --git a/drivers/gpu/drm/drm_mm.c b/drivers/gpu/drm/drm_mm.c index 61a1c8ea74bc..c3c79ee6119e 100644 --- a/drivers/gpu/drm/drm_mm.c +++ b/drivers/gpu/drm/drm_mm.c @@ -575,21 +575,23 @@ EXPORT_SYMBOL(drm_mm_remove_node); */ void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new) { + struct drm_mm *mm = old->mm; + DRM_MM_BUG_ON(!old->allocated); *new = *old; list_replace(&old->node_list, &new->node_list); - rb_replace_node(&old->rb, &new->rb, &old->mm->interval_tree.rb_root); + rb_replace_node_cached(&old->rb, &new->rb, &mm->interval_tree); if (drm_mm_hole_follows(old)) { list_replace(&old->hole_stack, &new->hole_stack); rb_replace_node(&old->rb_hole_size, &new->rb_hole_size, - &old->mm->holes_size); + &mm->holes_size); rb_replace_node(&old->rb_hole_addr, &new->rb_hole_addr, - &old->mm->holes_addr); + &mm->holes_addr); } old->allocated = false; diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index d574361943ea..fcbeed4053ef 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -99,6 +99,8 @@ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root); extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, struct rb_root *root); +extern void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new, + struct rb_root_cached *root); static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link) diff --git a/lib/rbtree.c b/lib/rbtree.c index ba4a9d165f1b..d3ff682fd4b8 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -603,6 +603,16 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, } EXPORT_SYMBOL(rb_replace_node); +void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new, + struct rb_root_cached *root) +{ + rb_replace_node(victim, new, &root->rb_root); + + if (root->rb_leftmost == victim) + root->rb_leftmost = new; +} +EXPORT_SYMBOL(rb_replace_node_cached); + void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { -- 2.15.0 _______________________________________________ dri-devel mailing list dri-devel@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/dri-devel
next prev parent reply other threads:[~2017-11-22 10:09 UTC|newest] Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top 2017-11-09 21:24 [PATCH 1/2] lib/rbtree,drm/mm: Add rbtree_replace_node_cached() Chris Wilson 2017-11-09 21:24 ` [PATCH 2/2] drm/selftests/mm: Add callsite indicator to common asserts Chris Wilson 2017-11-21 8:07 ` Joonas Lahtinen 2017-11-09 21:46 ` ✗ Fi.CI.BAT: warning for series starting with [1/2] lib/rbtree, drm/mm: Add rbtree_replace_node_cached() Patchwork 2017-11-10 14:26 ` [PATCH 1/2] " Davidlohr Bueso 2017-11-21 8:49 ` [PATCH 1/2] lib/rbtree,drm/mm: " Joonas Lahtinen 2017-11-22 10:07 ` Chris Wilson [this message] 2017-11-22 10:07 ` [PATCH] " Chris Wilson 2017-11-22 10:32 ` ✓ Fi.CI.BAT: success for series starting with lib/rbtree, drm/mm: Add rbtree_replace_node_cached() (rev2) Patchwork 2017-11-22 11:53 ` ✓ Fi.CI.IGT: " Patchwork
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=20171122100729.3742-1-chris@chris-wilson.co.uk \ --to=chris@chris-wilson.co.uk \ --cc=akpm@linux-foundation.org \ --cc=daniel.vetter@ffwll.ch \ --cc=dbueso@suse.de \ --cc=dri-devel@lists.freedesktop.org \ --cc=intel-gfx@lists.freedesktop.org \ --cc=jglisse@redhat.com \ --cc=joonas.lahtinen@linux.intel.com \ --cc=linux-kernel@vger.kernel.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: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
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.