From: Lai Jiangshan <jiangshanlai+lkml@gmail.com>
To: Peter Zijlstra <peterz@infradead.org>
Cc: Lai Jiangshan <laijs@linux.alibaba.com>,
LKML <linux-kernel@vger.kernel.org>,
"Paul E . McKenney" <paulmck@kernel.org>,
Oleg Nesterov <oleg@redhat.com>,
Michel Lespinasse <walken@google.com>,
Andrea Arcangeli <aarcange@redhat.com>,
David Woodhouse <David.Woodhouse@intel.com>,
Rik van Riel <riel@redhat.com>,
Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Subject: Re: [PATCH 1/2] rbtree_latch: quit searching when reaching to maximum depth
Date: Fri, 15 May 2020 22:39:25 +0800 [thread overview]
Message-ID: <CAJhGHyAMOQ7Bp8kYF7urp572SguFjiLs5PmqQvTKAkwfwBrOKQ@mail.gmail.com> (raw)
In-Reply-To: <20200515130030.GV2957@hirez.programming.kicks-ass.net>
On Fri, May 15, 2020 at 9:04 PM Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Fri, May 15, 2020 at 12:47:06PM +0000, Lai Jiangshan wrote:
> > lib/rbtree.c has ensured that there is not possible to
> > inadvertently cause (temporary) loops in the tree structure
> > as seen in program order of the modifier. But loop is still
> > possible to be seen in searcher due to CPU's reordering.
> >
> > for example:
> > modifier searcher
> >
> > left rotate at parent
> > parent->rb_right is node
> > search to parent
> > parent->rb_right is node
> > +->see node->rb_left changed
> > WRITE_ONCE(parent->rb_right, tmp);-+ | node->rb_left is parennt
> > no smp_wmb(), some arch can | |
> > reorder these two writes | | loop long between
> > WRITE_ONCE(node->rb_left, parent);-+-+ parent and node
> > |
> > +--->finally see
> > parent->rb_right
> >
> > The long loop won't stop until the modifer's CPU flushes
> > its writes. Too avoid it, we should limit the searching depth.
>
> Cute, have you actually observed this? Did you have performance issues?
I can only test it on x86 by now, which implies smp_wmb() between
writes. I haven't observed any thing wrong. I'm just imaging
it on some other ARCHs.
I accidentally found this part of code when I searched for
whether there is any attempt again to use rbtree with RCU, and
whether there are the cases besides speculative page fault.
>
> > There are no more than (1<<BITS_PER_LONG)-1 nodes in the tree.
> > And the max_depth of a tree is no more than 2*lg(node_count+1),
> > which is no mare than 2*BITS_PER_LONG.
> >
> > So the serarch should stop when diving down up to
> > 2*BITS_PER_LONG depth.
>
> Arguably you can have a larger key space, but I think due to memory
> constraints this limit still isn't wrong. But I do feel you need a
> comment with that.
Sure, I will add some comments about why "2*BITS_PER_LONG" in code.
But how it could be larger key space? there are not more than
(1<<BITS_PER_LONG) bytes in the kernel dereferencable address
space, and (1<<BITS_PER_LONG)/sizeof(rb_node) must be less than
(1<<BITS_PER_LONG)-1.
next prev parent reply other threads:[~2020-05-15 14:39 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-05-15 12:47 [PATCH 1/2] rbtree_latch: quit searching when reaching to maximum depth Lai Jiangshan
2020-05-15 12:47 ` [PATCH 2/2] rbtree_latch: don't need to check seq when it found a node Lai Jiangshan
2020-05-15 13:04 ` Peter Zijlstra
2020-05-15 13:00 ` [PATCH 1/2] rbtree_latch: quit searching when reaching to maximum depth Peter Zijlstra
2020-05-15 14:39 ` Lai Jiangshan [this message]
2020-05-15 15:01 ` Peter Zijlstra
2020-05-15 15:59 ` [PATCH V2 " Lai Jiangshan
2020-05-15 15:59 ` [PATCH V2 2/2] rbtree_latch: don't need to check seq when it found a node Lai Jiangshan
2020-05-16 4:27 ` Michel Lespinasse
2020-05-16 4:52 ` Lai Jiangshan
2020-05-16 5:03 ` Michel Lespinasse
2020-05-23 0:56 ` [PATCH V2 1/2] rbtree_latch: quit searching when reaching to maximum depth Lai Jiangshan
2020-05-15 13:14 ` [PATCH " Mathieu Desnoyers
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=CAJhGHyAMOQ7Bp8kYF7urp572SguFjiLs5PmqQvTKAkwfwBrOKQ@mail.gmail.com \
--to=jiangshanlai+lkml@gmail.com \
--cc=David.Woodhouse@intel.com \
--cc=aarcange@redhat.com \
--cc=laijs@linux.alibaba.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mathieu.desnoyers@efficios.com \
--cc=oleg@redhat.com \
--cc=paulmck@kernel.org \
--cc=peterz@infradead.org \
--cc=riel@redhat.com \
--cc=walken@google.com \
/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 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.