From: Jens Axboe <axboe@suse.de>
To: linux-kernel@vger.kernel.org
Cc: Jens Axboe <axboe@suse.de>
Subject: [PATCH] 5/15 cfq-iosched: migrate to using the elevator rb functions
Date: Thu, 13 Jul 2006 14:46:28 +0200 [thread overview]
Message-ID: <1152794798563-git-send-email-axboe@suse.de> (raw)
In-Reply-To: <11527947982769-git-send-email-axboe@suse.de>
This removes the rbtree handling from CFQ.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/cfq-iosched.c | 164 +++++++++++++--------------------------------------
1 files changed, 41 insertions(+), 123 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 6fd8af1..75efc82 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -46,12 +46,6 @@ #define list_entry_fifo(ptr) list_entry(
#define RQ_DATA(rq) (rq)->elevator_private
-/*
- * rb-tree defines
- */
-#define rb_entry_crq(node) rb_entry((node), struct cfq_rq, rb_node)
-#define rq_rb_key(rq) (rq)->sector
-
static kmem_cache_t *crq_pool;
static kmem_cache_t *cfq_pool;
static kmem_cache_t *cfq_ioc_pool;
@@ -185,8 +179,6 @@ struct cfq_queue {
};
struct cfq_rq {
- struct rb_node rb_node;
- sector_t rb_key;
struct request *request;
struct cfq_queue *cfq_queue;
@@ -376,33 +368,27 @@ #define CFQ_RQ2_WRAP 0x02 /* request 2 w
*/
static struct cfq_rq *
cfq_find_next_crq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
- struct cfq_rq *last)
+ struct cfq_rq *last_crq)
{
- struct cfq_rq *crq_next = NULL, *crq_prev = NULL;
- struct rb_node *rbnext, *rbprev;
-
- if (!(rbnext = rb_next(&last->rb_node))) {
- rbnext = rb_first(&cfqq->sort_list);
- if (rbnext == &last->rb_node)
- rbnext = NULL;
- }
+ struct request *last = last_crq->request;
+ struct rb_node *rbnext = rb_next(&last->rb_node);
+ struct rb_node *rbprev = rb_prev(&last->rb_node);
+ struct cfq_rq *next = NULL, *prev = NULL;
- rbprev = rb_prev(&last->rb_node);
+ BUG_ON(RB_EMPTY_NODE(&last->rb_node));
if (rbprev)
- crq_prev = rb_entry_crq(rbprev);
- if (rbnext)
- crq_next = rb_entry_crq(rbnext);
-
- return cfq_choose_req(cfqd, crq_next, crq_prev);
-}
+ prev = RQ_DATA(rb_entry_rq(rbprev));
-static void cfq_update_next_crq(struct cfq_rq *crq)
-{
- struct cfq_queue *cfqq = crq->cfq_queue;
+ if (rbnext)
+ next = RQ_DATA(rb_entry_rq(rbnext));
+ else {
+ rbnext = rb_first(&cfqq->sort_list);
+ if (rbnext && rbnext != &last->rb_node)
+ next = RQ_DATA(rb_entry_rq(rbnext));
+ }
- if (cfqq->next_crq == crq)
- cfqq->next_crq = cfq_find_next_crq(cfqq->cfqd, cfqq, crq);
+ return cfq_choose_req(cfqd, next, prev);
}
static void cfq_resort_rr_list(struct cfq_queue *cfqq, int preempted)
@@ -497,71 +483,34 @@ static inline void cfq_del_crq_rb(struct
BUG_ON(!cfqq->queued[sync]);
cfqq->queued[sync]--;
- cfq_update_next_crq(crq);
-
- rb_erase(&crq->rb_node, &cfqq->sort_list);
+ elv_rb_del(&cfqq->sort_list, crq->request);
if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
cfq_del_cfqq_rr(cfqd, cfqq);
}
-static struct cfq_rq *
-__cfq_add_crq_rb(struct cfq_rq *crq)
-{
- struct rb_node **p = &crq->cfq_queue->sort_list.rb_node;
- struct rb_node *parent = NULL;
- struct cfq_rq *__crq;
-
- while (*p) {
- parent = *p;
- __crq = rb_entry_crq(parent);
-
- if (crq->rb_key < __crq->rb_key)
- p = &(*p)->rb_left;
- else if (crq->rb_key > __crq->rb_key)
- p = &(*p)->rb_right;
- else
- return __crq;
- }
-
- rb_link_node(&crq->rb_node, parent, p);
- return NULL;
-}
-
static void cfq_add_crq_rb(struct cfq_rq *crq)
{
struct cfq_queue *cfqq = crq->cfq_queue;
struct cfq_data *cfqd = cfqq->cfqd;
struct request *rq = crq->request;
- struct cfq_rq *__alias;
+ struct request *__alias;
- crq->rb_key = rq_rb_key(rq);
cfqq->queued[cfq_crq_is_sync(crq)]++;
/*
* looks a little odd, but the first insert might return an alias.
* if that happens, put the alias on the dispatch list
*/
- while ((__alias = __cfq_add_crq_rb(crq)) != NULL)
- cfq_dispatch_insert(cfqd->queue, __alias);
-
- rb_insert_color(&crq->rb_node, &cfqq->sort_list);
-
- if (!cfq_cfqq_on_rr(cfqq))
- cfq_add_cfqq_rr(cfqd, cfqq);
-
- /*
- * check if this request is a better next-serve candidate
- */
- cfqq->next_crq = cfq_choose_req(cfqd, cfqq->next_crq, crq);
+ while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
+ cfq_dispatch_insert(cfqd->queue, RQ_DATA(__alias));
}
static inline void
cfq_reposition_crq_rb(struct cfq_queue *cfqq, struct cfq_rq *crq)
{
- rb_erase(&crq->rb_node, &cfqq->sort_list);
+ elv_rb_del(&cfqq->sort_list, crq->request);
cfqq->queued[cfq_crq_is_sync(crq)]--;
-
cfq_add_crq_rb(crq);
}
@@ -570,28 +519,13 @@ cfq_find_rq_fmerge(struct cfq_data *cfqd
{
struct task_struct *tsk = current;
pid_t key = cfq_queue_pid(tsk, bio_data_dir(bio));
+ sector_t sector = bio->bi_sector + bio_sectors(bio);
struct cfq_queue *cfqq;
- struct rb_node *n;
- sector_t sector;
cfqq = cfq_find_cfq_hash(cfqd, key, tsk->ioprio);
- if (!cfqq)
- goto out;
-
- sector = bio->bi_sector + bio_sectors(bio);
- n = cfqq->sort_list.rb_node;
- while (n) {
- struct cfq_rq *crq = rb_entry_crq(n);
-
- if (sector < crq->rb_key)
- n = n->rb_left;
- else if (sector > crq->rb_key)
- n = n->rb_right;
- else
- return crq->request;
- }
+ if (cfqq)
+ return elv_rb_find(&cfqq->sort_list, sector);
-out:
return NULL;
}
@@ -622,6 +556,10 @@ static void cfq_deactivate_request(reque
static void cfq_remove_request(struct request *rq)
{
struct cfq_rq *crq = RQ_DATA(rq);
+ struct cfq_queue *cfqq = crq->cfq_queue;
+
+ if (cfqq->next_crq == crq)
+ cfqq->next_crq = cfq_find_next_crq(cfqq->cfqd, cfqq, crq);
list_del_init(&rq->queuelist);
cfq_del_crq_rb(crq);
@@ -642,14 +580,14 @@ cfq_merge(request_queue_t *q, struct req
return ELEVATOR_NO_MERGE;
}
-static void cfq_merged_request(request_queue_t *q, struct request *req)
+static void cfq_merged_request(request_queue_t *q, struct request *req,
+ int type)
{
struct cfq_rq *crq = RQ_DATA(req);
- if (rq_rb_key(req) != crq->rb_key) {
+ if (type == ELEVATOR_FRONT_MERGE) {
struct cfq_queue *cfqq = crq->cfq_queue;
- cfq_update_next_crq(crq);
cfq_reposition_crq_rb(cfqq, crq);
}
}
@@ -658,8 +596,6 @@ static void
cfq_merged_requests(request_queue_t *q, struct request *rq,
struct request *next)
{
- cfq_merged_request(q, rq);
-
/*
* reposition in fifo if next is older than rq
*/
@@ -881,7 +817,6 @@ static void cfq_dispatch_insert(request_
struct cfq_queue *cfqq = crq->cfq_queue;
struct request *rq;
- cfqq->next_crq = cfq_find_next_crq(cfqd, cfqq, crq);
cfq_remove_request(crq->request);
cfqq->on_dispatch[cfq_crq_is_sync(crq)]++;
elv_dispatch_sort(q, crq->request);
@@ -1700,6 +1635,12 @@ cfq_crq_enqueued(struct cfq_data *cfqd,
struct cfq_io_context *cic = crq->io_context;
/*
+ * check if this request is a better next-serve candidate
+ */
+ cfqq->next_crq = cfq_choose_req(cfqd, cfqq->next_crq, crq);
+ BUG_ON(!cfqq->next_crq);
+
+ /*
* we never wait for an async request and we don't allow preemption
* of an async request. so just return early
*/
@@ -1756,6 +1697,9 @@ static void cfq_insert_request(request_q
cfq_add_crq_rb(crq);
+ if (!cfq_cfqq_on_rr(cfqq))
+ cfq_add_cfqq_rr(cfqd, cfqq);
+
list_add_tail(&rq->queuelist, &cfqq->fifo);
cfq_crq_enqueued(cfqd, cfqq, crq);
@@ -1803,30 +1747,6 @@ static void cfq_completed_request(reques
}
}
-static struct request *
-cfq_former_request(request_queue_t *q, struct request *rq)
-{
- struct cfq_rq *crq = RQ_DATA(rq);
- struct rb_node *rbprev = rb_prev(&crq->rb_node);
-
- if (rbprev)
- return rb_entry_crq(rbprev)->request;
-
- return NULL;
-}
-
-static struct request *
-cfq_latter_request(request_queue_t *q, struct request *rq)
-{
- struct cfq_rq *crq = RQ_DATA(rq);
- struct rb_node *rbnext = rb_next(&crq->rb_node);
-
- if (rbnext)
- return rb_entry_crq(rbnext)->request;
-
- return NULL;
-}
-
/*
* we temporarily boost lower priority queues if they are holding fs exclusive
* resources. they are boosted to normal prio (CLASS_BE/4)
@@ -1982,8 +1902,6 @@ cfq_set_request(request_queue_t *q, stru
crq = mempool_alloc(cfqd->crq_pool, gfp_mask);
if (crq) {
- RB_CLEAR_NODE(&crq->rb_node);
- crq->rb_key = 0;
crq->request = rq;
crq->cfq_queue = cfqq;
crq->io_context = cic;
@@ -2345,8 +2263,8 @@ static struct elevator_type iosched_cfq
.elevator_deactivate_req_fn = cfq_deactivate_request,
.elevator_queue_empty_fn = cfq_queue_empty,
.elevator_completed_req_fn = cfq_completed_request,
- .elevator_former_req_fn = cfq_former_request,
- .elevator_latter_req_fn = cfq_latter_request,
+ .elevator_former_req_fn = elv_rb_former_request,
+ .elevator_latter_req_fn = elv_rb_latter_request,
.elevator_set_req_fn = cfq_set_request,
.elevator_put_req_fn = cfq_put_request,
.elevator_may_queue_fn = cfq_may_queue,
--
1.4.1.ged0e0
next prev parent reply other threads:[~2006-07-13 12:44 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
2006-07-13 12:46 ` [PATCH] 1/15 elevator: move the backmerging logic into the elevator core Jens Axboe
2006-07-13 12:46 ` [PATCH] 2/15 rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev Jens Axboe
2006-07-13 12:46 ` [PATCH] 3/15 elevator: abstract out the rbtree sort handling Jens Axboe
2006-07-13 12:46 ` [PATCH] 4/15 as-iosched: migrate to using the elevator rb functions Jens Axboe
2006-07-13 12:46 ` Jens Axboe [this message]
2006-07-13 12:46 ` [PATCH] 6/15 deadline-iosched: " Jens Axboe
2006-07-13 12:46 ` [PATCH] 7/15 elevator: introduce a way to reuse rq for internal FIFO handling Jens Axboe
2006-07-13 12:46 ` [PATCH] 8/15 cfq-iosched: convert to using the FIFO elevator defines Jens Axboe
2006-07-13 12:46 ` [PATCH] 9/15 as-iosched: reuse rq for fifo Jens Axboe
2006-07-13 12:46 ` [PATCH] 10/15 as-iosched: remove arq->is_sync member Jens Axboe
2006-07-13 12:46 ` [PATCH] 11/15 deadline-iosched: remove elevator private drq request type Jens Axboe
2006-07-13 12:46 ` [PATCH] 12/15 cfq-iosched: remove the crq flag functions/variable Jens Axboe
2006-07-13 12:46 ` [PATCH] 13/15 Add one more pointer to struct request for IO scheduler usage Jens Axboe
2006-07-13 12:46 ` [PATCH] 14/15 cfq-iosched: kill crq Jens Axboe
2006-07-13 12:46 ` [PATCH] 15/15 as-iosched: kill arq Jens Axboe
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=1152794798563-git-send-email-axboe@suse.de \
--to=axboe@suse.de \
--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: 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.