From: Jens Axboe <axboe@suse.de>
To: linux-kernel@vger.kernel.org
Cc: Jens Axboe <axboe@suse.de>
Subject: [PATCH] 6/15 deadline-iosched: migrate to using the elevator rb functions
Date: Thu, 13 Jul 2006 14:46:29 +0200 [thread overview]
Message-ID: <11527947983756-git-send-email-axboe@suse.de> (raw)
In-Reply-To: <11527947982769-git-send-email-axboe@suse.de>
This removes the rbtree handling from deadline.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/deadline-iosched.c | 170 +++++++++-------------------------------------
1 files changed, 34 insertions(+), 136 deletions(-)
diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index b66e820..8300ba1 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -57,12 +57,6 @@ struct deadline_data {
* pre-request data.
*/
struct deadline_rq {
- /*
- * rbtree index, key is the starting offset
- */
- struct rb_node rb_node;
- sector_t rb_key;
-
struct request *request;
/*
@@ -78,108 +72,38 @@ static kmem_cache_t *drq_pool;
#define RQ_DATA(rq) ((struct deadline_rq *) (rq)->elevator_private)
-/*
- * rb tree support functions
- */
-#define rb_entry_drq(node) rb_entry((node), struct deadline_rq, rb_node)
-#define DRQ_RB_ROOT(dd, drq) (&(dd)->sort_list[rq_data_dir((drq)->request)])
-#define rq_rb_key(rq) (rq)->sector
-
-static struct deadline_rq *
-__deadline_add_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
-{
- struct rb_node **p = &DRQ_RB_ROOT(dd, drq)->rb_node;
- struct rb_node *parent = NULL;
- struct deadline_rq *__drq;
-
- while (*p) {
- parent = *p;
- __drq = rb_entry_drq(parent);
-
- if (drq->rb_key < __drq->rb_key)
- p = &(*p)->rb_left;
- else if (drq->rb_key > __drq->rb_key)
- p = &(*p)->rb_right;
- else
- return __drq;
- }
-
- rb_link_node(&drq->rb_node, parent, p);
- return NULL;
-}
+#define RQ_RB_ROOT(dd, rq) (&(dd)->sort_list[rq_data_dir((rq))])
+#define DRQ_RB_ROOT(dd, drq) RQ_RB_ROOT((drq)->request)
static void
-deadline_add_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
+deadline_add_drq_rb(struct deadline_data *dd, struct request *rq)
{
- struct deadline_rq *__alias;
-
- drq->rb_key = rq_rb_key(drq->request);
+ struct rb_root *root = RQ_RB_ROOT(dd, rq);
+ struct request *__alias;
retry:
- __alias = __deadline_add_drq_rb(dd, drq);
- if (!__alias) {
- rb_insert_color(&drq->rb_node, DRQ_RB_ROOT(dd, drq));
- return;
+ __alias = elv_rb_add(root, rq);
+ if (unlikely(__alias)) {
+ deadline_move_request(dd, RQ_DATA(__alias));
+ goto retry;
}
-
- deadline_move_request(dd, __alias);
- goto retry;
}
static inline void
deadline_del_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
{
- const int data_dir = rq_data_dir(drq->request);
+ struct request *rq = drq->request;
+ const int data_dir = rq_data_dir(rq);
if (dd->next_drq[data_dir] == drq) {
- struct rb_node *rbnext = rb_next(&drq->rb_node);
+ struct rb_node *rbnext = rb_next(&rq->rb_node);
dd->next_drq[data_dir] = NULL;
if (rbnext)
- dd->next_drq[data_dir] = rb_entry_drq(rbnext);
- }
-
- BUG_ON(!RB_EMPTY_NODE(&drq->rb_node));
- rb_erase(&drq->rb_node, DRQ_RB_ROOT(dd, drq));
- RB_CLEAR_NODE(&drq->rb_node);
-}
-
-static struct request *
-deadline_find_drq_rb(struct deadline_data *dd, sector_t sector, int data_dir)
-{
- struct rb_node *n = dd->sort_list[data_dir].rb_node;
- struct deadline_rq *drq;
-
- while (n) {
- drq = rb_entry_drq(n);
-
- if (sector < drq->rb_key)
- n = n->rb_left;
- else if (sector > drq->rb_key)
- n = n->rb_right;
- else
- return drq->request;
+ dd->next_drq[data_dir] = RQ_DATA(rb_entry_rq(rbnext));
}
- return NULL;
-}
-
-/*
- * deadline_find_first_drq finds the first (lowest sector numbered) request
- * for the specified data_dir. Used to sweep back to the start of the disk
- * (1-way elevator) after we process the last (highest sector) request.
- */
-static struct deadline_rq *
-deadline_find_first_drq(struct deadline_data *dd, int data_dir)
-{
- struct rb_node *n = dd->sort_list[data_dir].rb_node;
-
- for (;;) {
- if (n->rb_left == NULL)
- return rb_entry_drq(n);
-
- n = n->rb_left;
- }
+ elv_rb_del(RQ_RB_ROOT(dd, rq), rq);
}
/*
@@ -192,7 +116,7 @@ deadline_add_request(struct request_queu
struct deadline_rq *drq = RQ_DATA(rq);
const int data_dir = rq_data_dir(drq->request);
- deadline_add_drq_rb(dd, drq);
+ deadline_add_drq_rb(dd, rq);
/*
* set expire time (only used for reads) and add to fifo list
@@ -224,11 +148,11 @@ deadline_merge(request_queue_t *q, struc
* check for front merge
*/
if (dd->front_merges) {
- sector_t rb_key = bio->bi_sector + bio_sectors(bio);
+ sector_t sector = bio->bi_sector + bio_sectors(bio);
- __rq = deadline_find_drq_rb(dd, rb_key, bio_data_dir(bio));
+ __rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);
if (__rq) {
- BUG_ON(rb_key != rq_rb_key(__rq));
+ BUG_ON(sector != __rq->sector);
if (elv_rq_merge_ok(__rq, bio)) {
ret = ELEVATOR_FRONT_MERGE;
@@ -243,17 +167,17 @@ out:
return ret;
}
-static void deadline_merged_request(request_queue_t *q, struct request *req)
+static void deadline_merged_request(request_queue_t *q, struct request *req,
+ int type)
{
struct deadline_data *dd = q->elevator->elevator_data;
- struct deadline_rq *drq = RQ_DATA(req);
/*
* if the merge was a front merge, we need to reposition request
*/
- if (rq_rb_key(req) != drq->rb_key) {
- deadline_del_drq_rb(dd, drq);
- deadline_add_drq_rb(dd, drq);
+ if (type == ELEVATOR_FRONT_MERGE) {
+ elv_rb_del(RQ_RB_ROOT(dd, req), req);
+ deadline_add_drq_rb(dd, req);
}
}
@@ -261,18 +185,12 @@ static void
deadline_merged_requests(request_queue_t *q, struct request *req,
struct request *next)
{
- struct deadline_data *dd = q->elevator->elevator_data;
struct deadline_rq *drq = RQ_DATA(req);
struct deadline_rq *dnext = RQ_DATA(next);
BUG_ON(!drq);
BUG_ON(!dnext);
- if (rq_rb_key(req) != drq->rb_key) {
- deadline_del_drq_rb(dd, drq);
- deadline_add_drq_rb(dd, drq);
- }
-
/*
* if dnext expires before drq, assign its expire time to drq
* and move into dnext position (dnext will be deleted) in fifo
@@ -308,14 +226,15 @@ deadline_move_to_dispatch(struct deadlin
static void
deadline_move_request(struct deadline_data *dd, struct deadline_rq *drq)
{
- const int data_dir = rq_data_dir(drq->request);
- struct rb_node *rbnext = rb_next(&drq->rb_node);
+ struct request *rq = drq->request;
+ const int data_dir = rq_data_dir(rq);
+ struct rb_node *rbnext = rb_next(&rq->rb_node);
dd->next_drq[READ] = NULL;
dd->next_drq[WRITE] = NULL;
if (rbnext)
- dd->next_drq[data_dir] = rb_entry_drq(rbnext);
+ dd->next_drq[data_dir] = RQ_DATA(rb_entry_rq(rbnext));
dd->last_sector = drq->request->sector + drq->request->nr_sectors;
@@ -426,13 +345,17 @@ dispatch_find_request:
*/
drq = dd->next_drq[data_dir];
} else {
+ struct rb_node *n;
+
/*
* The last req was the other direction or we have run out of
* higher-sectored requests. Go back to the lowest sectored
* request (1 way elevator) and start a new batch.
*/
dd->batching = 0;
- drq = deadline_find_first_drq(dd, data_dir);
+ n = rb_first(&dd->sort_list[data_dir]);
+ if (n)
+ drq = RQ_DATA(rb_entry_rq(n));
}
dispatch_request:
@@ -453,30 +376,6 @@ static int deadline_queue_empty(request_
&& list_empty(&dd->fifo_list[READ]);
}
-static struct request *
-deadline_former_request(request_queue_t *q, struct request *rq)
-{
- struct deadline_rq *drq = RQ_DATA(rq);
- struct rb_node *rbprev = rb_prev(&drq->rb_node);
-
- if (rbprev)
- return rb_entry_drq(rbprev)->request;
-
- return NULL;
-}
-
-static struct request *
-deadline_latter_request(request_queue_t *q, struct request *rq)
-{
- struct deadline_rq *drq = RQ_DATA(rq);
- struct rb_node *rbnext = rb_next(&drq->rb_node);
-
- if (rbnext)
- return rb_entry_drq(rbnext)->request;
-
- return NULL;
-}
-
static void deadline_exit_queue(elevator_t *e)
{
struct deadline_data *dd = e->elevator_data;
@@ -542,7 +441,6 @@ deadline_set_request(request_queue_t *q,
drq = mempool_alloc(dd->drq_pool, gfp_mask);
if (drq) {
memset(drq, 0, sizeof(*drq));
- RB_CLEAR_NODE(&drq->rb_node);
drq->request = rq;
INIT_LIST_HEAD(&drq->fifo);
@@ -633,8 +531,8 @@ static struct elevator_type iosched_dead
.elevator_dispatch_fn = deadline_dispatch_requests,
.elevator_add_req_fn = deadline_add_request,
.elevator_queue_empty_fn = deadline_queue_empty,
- .elevator_former_req_fn = deadline_former_request,
- .elevator_latter_req_fn = deadline_latter_request,
+ .elevator_former_req_fn = elv_rb_former_request,
+ .elevator_latter_req_fn = elv_rb_latter_request,
.elevator_set_req_fn = deadline_set_request,
.elevator_put_req_fn = deadline_put_request,
.elevator_init_fn = deadline_init_queue,
--
1.4.1.ged0e0
next prev parent reply other threads:[~2006-07-13 12:48 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 ` [PATCH] 5/15 cfq-iosched: " Jens Axboe
2006-07-13 12:46 ` Jens Axboe [this message]
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=11527947983756-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.