From: Uladzislau Rezki <urezki@gmail.com>
To: Joel Fernandes <joel@joelfernandes.org>
Cc: Uladzislau Rezki <urezki@gmail.com>,
linux-kernel@vger.kernel.org, kernel-team@android.com,
kernel-team@lge.com, Byungchul Park <byungchul.park@lge.com>,
Davidlohr Bueso <dave@stgolabs.net>,
Josh Triplett <josh@joshtriplett.org>,
Lai Jiangshan <jiangshanlai@gmail.com>,
Mathieu Desnoyers <mathieu.desnoyers@efficios.com>,
max.byungchul.park@gmail.com,
"Paul E. McKenney" <paulmck@linux.ibm.com>,
Rao Shoaib <rao.shoaib@oracle.com>,
rcu@vger.kernel.org, Steven Rostedt <rostedt@goodmis.org>
Subject: Re: [PATCH v4 1/2] rcu/tree: Add basic support for kfree_rcu() batching
Date: Tue, 8 Oct 2019 18:23:06 +0200 [thread overview]
Message-ID: <20191008162306.GA5901@pc636> (raw)
In-Reply-To: <20191004172038.GG253167@google.com>
On Fri, Oct 04, 2019 at 01:20:38PM -0400, Joel Fernandes wrote:
> On Tue, Oct 01, 2019 at 01:27:02PM +0200, Uladzislau Rezki wrote:
> [snip]
> > > > I have just a small question related to workloads and performance evaluation.
> > > > Are you aware of any specific workloads which benefit from it for example
> > > > mobile area, etc? I am asking because i think about backporting of it and
> > > > reuse it on our kernel.
> > >
> > > I am not aware of a mobile usecase that benefits but there are server
> > > workloads that make system more stable in the face of a kfree_rcu() flood.
> > >
> > OK, i got it. I wanted to test it finding out how it could effect mobile
> > workloads.
> >
> > >
> > > For the KVA allocator work, I see it is quite similar to the way binder
> > > allocates blocks. See function: binder_alloc_new_buf_locked(). Is there are
> > > any chance to reuse any code? For one thing, binder also has an rbtree for
> > > allocated blocks for fast lookup of allocated blocks. Does the KVA allocator
> > > not have the need for that?
> > >
> > Well, there is a difference. Actually the free blocks are not sorted by
> > the its size like in binder layer, if understand the code correctly.
> >
> > Instead, i keep them(free blocks) sorted(by start address) in ascending
> > order + maintain the augment value(biggest free size in left or right sub-tree)
> > for each node, that allows to navigate toward the lowest address and the block
> > that definitely suits. So as a result our allocations become sequential
> > what is important.
>
> Right, I realized this after sending the email that binder and kva sort
> differently though they both try to use free sizes during the allocation.
>
> Would you have any papers, which survey various rb-tree based allocator
> algorithms and their tradeoffs? I am interested in studying these more
> especially in relation to the binder driver. Would also be nice to make
> contributions to papers surveying both these allocators to describe the state
> of the art.
>
So far i have not had any paper with different kind of comparison. But
that is interested for sure, especially to analyze the model for example
based on B-Tree, so when we can fully utilize a cache performance.
Because regular binary trees are just pointer chasing.
As for binder driver and its allocator, is it O(lognN) complexity? Is
there any bottleneck in its implementation?
Thanks!
--
Vlad Rezki
next prev parent reply other threads:[~2019-10-08 16:23 UTC|newest]
Thread overview: 30+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-08-14 16:04 [PATCH v4 1/2] rcu/tree: Add basic support for kfree_rcu() batching Joel Fernandes (Google)
2019-08-14 16:04 ` [PATCH v4 2/2] rcuperf: Add kfree_rcu() performance Tests Joel Fernandes (Google)
2019-08-14 22:58 ` Paul E. McKenney
2019-08-19 19:33 ` Joel Fernandes
2019-08-19 22:23 ` Paul E. McKenney
2019-08-19 23:51 ` Joel Fernandes
2019-08-20 2:50 ` Paul E. McKenney
2019-08-21 0:27 ` Joel Fernandes
2019-08-21 0:31 ` Joel Fernandes
2019-08-21 0:44 ` Paul E. McKenney
2019-08-21 0:51 ` Joel Fernandes
2019-08-16 16:43 ` [PATCH v4 1/2] rcu/tree: Add basic support for kfree_rcu() batching Paul E. McKenney
2019-08-16 17:44 ` Joel Fernandes
2019-08-16 19:16 ` Paul E. McKenney
2019-08-17 1:32 ` Joel Fernandes
2019-08-17 3:56 ` Paul E. McKenney
2019-08-17 4:30 ` Joel Fernandes
2019-08-17 5:20 ` Paul E. McKenney
2019-08-17 5:53 ` Joel Fernandes
2019-08-17 21:45 ` Paul E. McKenney
2019-09-18 9:58 ` Uladzislau Rezki
2019-09-30 20:16 ` Joel Fernandes
2019-10-01 11:27 ` Uladzislau Rezki
2019-10-04 17:20 ` Joel Fernandes
2019-10-08 16:23 ` Uladzislau Rezki [this message]
2019-12-10 9:53 ` Uladzislau Rezki
2019-12-11 23:46 ` Paul E. McKenney
2019-12-16 12:06 ` Uladzislau Rezki
2019-12-12 5:27 ` Joel Fernandes
2019-12-16 12:46 ` Uladzislau Rezki
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=20191008162306.GA5901@pc636 \
--to=urezki@gmail.com \
--cc=byungchul.park@lge.com \
--cc=dave@stgolabs.net \
--cc=jiangshanlai@gmail.com \
--cc=joel@joelfernandes.org \
--cc=josh@joshtriplett.org \
--cc=kernel-team@android.com \
--cc=kernel-team@lge.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mathieu.desnoyers@efficios.com \
--cc=max.byungchul.park@gmail.com \
--cc=paulmck@linux.ibm.com \
--cc=rao.shoaib@oracle.com \
--cc=rcu@vger.kernel.org \
--cc=rostedt@goodmis.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).