From: Jan Kara <jack@suse.cz>
To: Davidlohr Bueso <dave@stgolabs.net>
Cc: akpm@linux-foundation.org, mingo@kernel.org,
peterz@infradead.org, jack@suse.cz,
torvalds@linux-foundation.org, kirill.shutemov@linux.intel.com,
hch@infradead.org, ldufour@linux.vnet.ibm.com, mhocko@suse.com,
mgorman@techsingularity.net, linux-kernel@vger.kernel.org,
axboe@fb.com, linux-block@vger.kernel.org,
Davidlohr Bueso <dbueso@suse.de>
Subject: Re: [PATCH 10/17] block/cfq: replace cfq_rb_root leftmost caching
Date: Wed, 19 Jul 2017 09:46:10 +0200 [thread overview]
Message-ID: <20170719074610.GB12546@quack2.suse.cz> (raw)
In-Reply-To: <20170719014603.19029-11-dave@stgolabs.net>
On Tue 18-07-17 18:45:56, Davidlohr Bueso wrote:
> ... with the generic rbtree flavor instead. No changes
> in semantics whatsoever.
>
> Cc: axboe@fb.com
> Cc: linux-block@vger.kernel.org
> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
Looks good to me. You can add:
Reviewed-by: Jan Kara <jack@suse.cz>
Honza
> ---
> block/cfq-iosched.c | 70 +++++++++++++++--------------------------------------
> 1 file changed, 20 insertions(+), 50 deletions(-)
>
> diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
> index 3d5c28945719..92c31683a2bb 100644
> --- a/block/cfq-iosched.c
> +++ b/block/cfq-iosched.c
> @@ -93,13 +93,12 @@ struct cfq_ttime {
> * move this into the elevator for the rq sorting as well.
> */
> struct cfq_rb_root {
> - struct rb_root rb;
> - struct rb_node *left;
> + struct rb_root_cached rb;
> unsigned count;
> u64 min_vdisktime;
> struct cfq_ttime ttime;
> };
> -#define CFQ_RB_ROOT (struct cfq_rb_root) { .rb = RB_ROOT, \
> +#define CFQ_RB_ROOT (struct cfq_rb_root) { .rb = RB_ROOT_CACHED, \
> .ttime = {.last_end_request = ktime_get_ns(),},}
>
> /*
> @@ -984,10 +983,9 @@ static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
>
> static void update_min_vdisktime(struct cfq_rb_root *st)
> {
> - struct cfq_group *cfqg;
> + if (!RB_EMPTY_ROOT(&st->rb.rb_root)) {
> + struct cfq_group *cfqg = rb_entry_cfqg(st->rb.rb_leftmost);
>
> - if (st->left) {
> - cfqg = rb_entry_cfqg(st->left);
> st->min_vdisktime = max_vdisktime(st->min_vdisktime,
> cfqg->vdisktime);
> }
> @@ -1169,46 +1167,25 @@ cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2,
> }
> }
>
> -/*
> - * The below is leftmost cache rbtree addon
> - */
> static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
> {
> /* Service tree is empty */
> if (!root->count)
> return NULL;
>
> - if (!root->left)
> - root->left = rb_first(&root->rb);
> -
> - if (root->left)
> - return rb_entry(root->left, struct cfq_queue, rb_node);
> -
> - return NULL;
> + return rb_entry(rb_first_cached(&root->rb), struct cfq_queue, rb_node);
> }
>
> static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
> {
> - if (!root->left)
> - root->left = rb_first(&root->rb);
> -
> - if (root->left)
> - return rb_entry_cfqg(root->left);
> -
> - return NULL;
> + return rb_entry_cfqg(rb_first_cached(&root->rb));
> }
>
> -static void rb_erase_init(struct rb_node *n, struct rb_root *root)
> +static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
> {
> - rb_erase(n, root);
> + rb_erase_cached(n, &root->rb);
> RB_CLEAR_NODE(n);
> -}
>
> -static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
> -{
> - if (root->left == n)
> - root->left = NULL;
> - rb_erase_init(n, &root->rb);
> --root->count;
> }
>
> @@ -1258,11 +1235,11 @@ cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
> static void
> __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
> {
> - struct rb_node **node = &st->rb.rb_node;
> + struct rb_node **node = &st->rb.rb_root.rb_node;
> struct rb_node *parent = NULL;
> struct cfq_group *__cfqg;
> s64 key = cfqg_key(st, cfqg);
> - int left = 1;
> + bool leftmost = true;
>
> while (*node != NULL) {
> parent = *node;
> @@ -1272,15 +1249,12 @@ __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
> node = &parent->rb_left;
> else {
> node = &parent->rb_right;
> - left = 0;
> + leftmost = false;
> }
> }
>
> - if (left)
> - st->left = &cfqg->rb_node;
> -
> rb_link_node(&cfqg->rb_node, parent, node);
> - rb_insert_color(&cfqg->rb_node, &st->rb);
> + rb_insert_color_cached(&cfqg->rb_node, &st->rb, leftmost);
> }
>
> /*
> @@ -1381,7 +1355,7 @@ cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
> * so that groups get lesser vtime based on their weights, so that
> * if group does not loose all if it was not continuously backlogged.
> */
> - n = rb_last(&st->rb);
> + n = rb_last(&st->rb.rb_root);
> if (n) {
> __cfqg = rb_entry_cfqg(n);
> cfqg->vdisktime = __cfqg->vdisktime +
> @@ -2223,14 +2197,14 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
> struct cfq_queue *__cfqq;
> u64 rb_key;
> struct cfq_rb_root *st;
> - int left;
> + bool leftmost = true;
> int new_cfqq = 1;
> u64 now = ktime_get_ns();
>
> st = st_for(cfqq->cfqg, cfqq_class(cfqq), cfqq_type(cfqq));
> if (cfq_class_idle(cfqq)) {
> rb_key = CFQ_IDLE_DELAY;
> - parent = rb_last(&st->rb);
> + parent = rb_last(&st->rb.rb_root);
> if (parent && parent != &cfqq->rb_node) {
> __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
> rb_key += __cfqq->rb_key;
> @@ -2264,10 +2238,9 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
> cfqq->service_tree = NULL;
> }
>
> - left = 1;
> parent = NULL;
> cfqq->service_tree = st;
> - p = &st->rb.rb_node;
> + p = &st->rb.rb_root.rb_node;
> while (*p) {
> parent = *p;
> __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
> @@ -2279,16 +2252,13 @@ static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
> p = &parent->rb_left;
> else {
> p = &parent->rb_right;
> - left = 0;
> + leftmost = false;
> }
> }
>
> - if (left)
> - st->left = &cfqq->rb_node;
> -
> cfqq->rb_key = rb_key;
> rb_link_node(&cfqq->rb_node, parent, p);
> - rb_insert_color(&cfqq->rb_node, &st->rb);
> + rb_insert_color_cached(&cfqq->rb_node, &st->rb, leftmost);
> st->count++;
> if (add_front || !new_cfqq)
> return;
> @@ -2735,7 +2705,7 @@ static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
> /* There is nothing to dispatch */
> if (!st)
> return NULL;
> - if (RB_EMPTY_ROOT(&st->rb))
> + if (RB_EMPTY_ROOT(&st->rb.rb_root))
> return NULL;
> return cfq_rb_first(st);
> }
> @@ -3221,7 +3191,7 @@ static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
> struct cfq_rb_root *st = &cfqd->grp_service_tree;
> struct cfq_group *cfqg;
>
> - if (RB_EMPTY_ROOT(&st->rb))
> + if (RB_EMPTY_ROOT(&st->rb.rb_root))
> return NULL;
> cfqg = cfq_rb_first_group(st);
> update_min_vdisktime(st);
> --
> 2.12.0
>
--
Jan Kara <jack@suse.com>
SUSE Labs, CR
next prev parent reply other threads:[~2017-07-19 7:46 UTC|newest]
Thread overview: 27+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-07-19 1:45 [PATCH -next v4 00/17] rbtree: cache leftmost node internally Davidlohr Bueso
2017-07-19 1:45 ` [PATCH 01/17] " Davidlohr Bueso
2017-07-19 1:45 ` [PATCH 02/17] rbtree: optimize root-check during rebalancing loop Davidlohr Bueso
2017-07-19 1:45 ` [PATCH 03/17] rbtree: add some additional comments for rebalancing cases Davidlohr Bueso
2017-07-19 1:45 ` [PATCH 04/17] lib/rbtree_test.c: make input module parameters Davidlohr Bueso
2017-07-19 1:45 ` [PATCH 05/17] lib/rbtree_test.c: add (inorder) traversal test Davidlohr Bueso
2017-07-19 1:45 ` [PATCH 06/17] lib/rbtree_test.c: support rb_root_cached Davidlohr Bueso
2017-07-19 1:45 ` [PATCH 07/17] sched/fair: replace cfs_rq->rb_leftmost Davidlohr Bueso
2017-07-19 1:45 ` [PATCH 08/17] sched/deadline: replace earliest dl and rq leftmost caching Davidlohr Bueso
2017-07-19 1:45 ` [PATCH 09/17] locking/rtmutex: replace top-waiter and pi_waiters " Davidlohr Bueso
2017-07-19 1:45 ` [PATCH 10/17] block/cfq: replace cfq_rb_root " Davidlohr Bueso
2017-07-19 7:46 ` Jan Kara [this message]
2017-07-19 1:45 ` [PATCH 11/17] lib/interval_tree: fast overlap detection Davidlohr Bueso
2017-07-22 17:52 ` Doug Ledford
2017-08-01 17:16 ` Michael S. Tsirkin
2017-07-19 1:45 ` [PATCH 12/17] lib/interval-tree: correct comment wrt generic flavor Davidlohr Bueso
2017-07-19 1:45 ` [PATCH 13/17] procfs: use faster rb_first_cached() Davidlohr Bueso
2017-07-19 1:46 ` [PATCH 14/17] fs/epoll: " Davidlohr Bueso
2017-07-19 1:46 ` [PATCH 15/17] fs/ext4: use cached rbtrees Davidlohr Bueso
2017-07-19 7:40 ` Jan Kara
2017-07-19 22:50 ` Davidlohr Bueso
2017-07-19 1:46 ` [PATCH 16/17] mem/memcg: cache rightmost node Davidlohr Bueso
2017-07-19 7:50 ` Michal Hocko
2017-07-26 21:09 ` Andrew Morton
2017-07-27 7:06 ` Michal Hocko
2017-07-19 1:46 ` [PATCH 17/17] block/cfq: cache rightmost rb_node Davidlohr Bueso
2017-07-19 7:59 ` Jan Kara
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=20170719074610.GB12546@quack2.suse.cz \
--to=jack@suse.cz \
--cc=akpm@linux-foundation.org \
--cc=axboe@fb.com \
--cc=dave@stgolabs.net \
--cc=dbueso@suse.de \
--cc=hch@infradead.org \
--cc=kirill.shutemov@linux.intel.com \
--cc=ldufour@linux.vnet.ibm.com \
--cc=linux-block@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mgorman@techsingularity.net \
--cc=mhocko@suse.com \
--cc=mingo@kernel.org \
--cc=peterz@infradead.org \
--cc=torvalds@linux-foundation.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
all inboxes | Powered by JetHome®