* [PATCH] 1/15 elevator: move the backmerging logic into the elevator core
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
@ 2006-07-13 12:46 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 2/15 rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev Jens Axboe
` (13 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
Right now, every IO scheduler implements its own backmerging (except for
noop, which does no merging). That results in duplicated code for
essentially the same operation, which is never a good thing. This patch
moves the backmerging out of the io schedulers and into the elevator
core. We save 1.6kb of text and as a bonus get backmerging for noop as
well. Win-win!
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/as-iosched.c | 139 +------------------------------------------
block/cfq-iosched.c | 86 +--------------------------
block/deadline-iosched.c | 128 +---------------------------------------
block/elevator.c | 147 +++++++++++++++++++++++++++++++++++++++++-----
block/ll_rw_blk.c | 2 +
include/linux/blkdev.h | 17 +----
include/linux/elevator.h | 2 +
7 files changed, 146 insertions(+), 375 deletions(-)
diff --git a/block/as-iosched.c b/block/as-iosched.c
index 5da56d4..1c44ce3 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -14,7 +14,6 @@ #include <linux/module.h>
#include <linux/slab.h>
#include <linux/init.h>
#include <linux/compiler.h>
-#include <linux/hash.h>
#include <linux/rbtree.h>
#include <linux/interrupt.h>
@@ -95,7 +94,6 @@ struct as_data {
struct as_rq *next_arq[2]; /* next in sort order */
sector_t last_sector[2]; /* last REQ_SYNC & REQ_ASYNC sectors */
- struct hlist_head *hash; /* request hash */
unsigned long exit_prob; /* probability a task will exit while
being waited on */
@@ -162,11 +160,6 @@ struct as_rq {
struct io_context *io_context; /* The submitting task */
/*
- * request hash, key is the ending offset (for back merge lookup)
- */
- struct hlist_node hash;
-
- /*
* expire fifo
*/
struct list_head fifo;
@@ -273,77 +266,6 @@ static void as_put_io_context(struct as_
}
/*
- * the back merge hash support functions
- */
-static const int as_hash_shift = 6;
-#define AS_HASH_BLOCK(sec) ((sec) >> 3)
-#define AS_HASH_FN(sec) (hash_long(AS_HASH_BLOCK((sec)), as_hash_shift))
-#define AS_HASH_ENTRIES (1 << as_hash_shift)
-#define rq_hash_key(rq) ((rq)->sector + (rq)->nr_sectors)
-
-static inline void __as_del_arq_hash(struct as_rq *arq)
-{
- hlist_del_init(&arq->hash);
-}
-
-static inline void as_del_arq_hash(struct as_rq *arq)
-{
- if (!hlist_unhashed(&arq->hash))
- __as_del_arq_hash(arq);
-}
-
-static void as_add_arq_hash(struct as_data *ad, struct as_rq *arq)
-{
- struct request *rq = arq->request;
-
- BUG_ON(!hlist_unhashed(&arq->hash));
-
- hlist_add_head(&arq->hash, &ad->hash[AS_HASH_FN(rq_hash_key(rq))]);
-}
-
-/*
- * move hot entry to front of chain
- */
-static inline void as_hot_arq_hash(struct as_data *ad, struct as_rq *arq)
-{
- struct request *rq = arq->request;
- struct hlist_head *head = &ad->hash[AS_HASH_FN(rq_hash_key(rq))];
-
- if (hlist_unhashed(&arq->hash)) {
- WARN_ON(1);
- return;
- }
-
- if (&arq->hash != head->first) {
- hlist_del(&arq->hash);
- hlist_add_head(&arq->hash, head);
- }
-}
-
-static struct request *as_find_arq_hash(struct as_data *ad, sector_t offset)
-{
- struct hlist_head *hash_list = &ad->hash[AS_HASH_FN(offset)];
- struct hlist_node *entry, *next;
- struct as_rq *arq;
-
- hlist_for_each_entry_safe(arq, entry, next, hash_list, hash) {
- struct request *__rq = arq->request;
-
- BUG_ON(hlist_unhashed(&arq->hash));
-
- if (!rq_mergeable(__rq)) {
- as_del_arq_hash(arq);
- continue;
- }
-
- if (rq_hash_key(__rq) == offset)
- return __rq;
- }
-
- return NULL;
-}
-
-/*
* rb tree support functions
*/
#define rb_entry_arq(node) rb_entry((node), struct as_rq, rb_node)
@@ -1060,7 +982,6 @@ static void as_remove_queued_request(req
ad->next_arq[data_dir] = as_find_next_arq(ad, arq);
list_del_init(&arq->fifo);
- as_del_arq_hash(arq);
as_del_arq_rb(ad, arq);
}
@@ -1349,8 +1270,6 @@ static void as_add_request(request_queue
}
as_add_arq_rb(ad, arq);
- if (rq_mergeable(arq->request))
- as_add_arq_hash(ad, arq);
/*
* set expire time (only used for reads) and add to fifo list
@@ -1428,42 +1347,17 @@ as_merge(request_queue_t *q, struct requ
struct as_data *ad = q->elevator->elevator_data;
sector_t rb_key = bio->bi_sector + bio_sectors(bio);
struct request *__rq;
- int ret;
-
- /*
- * see if the merge hash can satisfy a back merge
- */
- __rq = as_find_arq_hash(ad, bio->bi_sector);
- if (__rq) {
- BUG_ON(__rq->sector + __rq->nr_sectors != bio->bi_sector);
-
- if (elv_rq_merge_ok(__rq, bio)) {
- ret = ELEVATOR_BACK_MERGE;
- goto out;
- }
- }
/*
* check for front merge
*/
__rq = as_find_arq_rb(ad, rb_key, bio_data_dir(bio));
- if (__rq) {
- BUG_ON(rb_key != rq_rb_key(__rq));
-
- if (elv_rq_merge_ok(__rq, bio)) {
- ret = ELEVATOR_FRONT_MERGE;
- goto out;
- }
+ if (__rq && elv_rq_merge_ok(__rq, bio)) {
+ *req = __rq;
+ return ELEVATOR_FRONT_MERGE;
}
return ELEVATOR_NO_MERGE;
-out:
- if (ret) {
- if (rq_mergeable(__rq))
- as_hot_arq_hash(ad, RQ_DATA(__rq));
- }
- *req = __rq;
- return ret;
}
static void as_merged_request(request_queue_t *q, struct request *req)
@@ -1472,12 +1366,6 @@ static void as_merged_request(request_qu
struct as_rq *arq = RQ_DATA(req);
/*
- * hash always needs to be repositioned, key is end sector
- */
- as_del_arq_hash(arq);
- as_add_arq_hash(ad, arq);
-
- /*
* if the merge was a front merge, we need to reposition request
*/
if (rq_rb_key(req) != arq->rb_key) {
@@ -1501,13 +1389,6 @@ static void as_merged_requests(request_q
BUG_ON(!arq);
BUG_ON(!anext);
- /*
- * reposition arq (this is the merged request) in hash, and in rbtree
- * in case of a front merge
- */
- as_del_arq_hash(arq);
- as_add_arq_hash(ad, arq);
-
if (rq_rb_key(req) != arq->rb_key) {
as_del_arq_rb(ad, arq);
as_add_arq_rb(ad, arq);
@@ -1591,7 +1472,6 @@ static int as_set_request(request_queue_
arq->request = rq;
arq->state = AS_RQ_PRESCHED;
arq->io_context = NULL;
- INIT_HLIST_NODE(&arq->hash);
INIT_LIST_HEAD(&arq->fifo);
rq->elevator_private = arq;
return 0;
@@ -1628,7 +1508,6 @@ static void as_exit_queue(elevator_t *e)
mempool_destroy(ad->arq_pool);
put_io_context(ad->io_context);
- kfree(ad->hash);
kfree(ad);
}
@@ -1639,7 +1518,6 @@ static void as_exit_queue(elevator_t *e)
static void *as_init_queue(request_queue_t *q, elevator_t *e)
{
struct as_data *ad;
- int i;
if (!arq_pool)
return NULL;
@@ -1651,17 +1529,9 @@ static void *as_init_queue(request_queue
ad->q = q; /* Identify what queue the data belongs to */
- ad->hash = kmalloc_node(sizeof(struct hlist_head)*AS_HASH_ENTRIES,
- GFP_KERNEL, q->node);
- if (!ad->hash) {
- kfree(ad);
- return NULL;
- }
-
ad->arq_pool = mempool_create_node(BLKDEV_MIN_RQ, mempool_alloc_slab,
mempool_free_slab, arq_pool, q->node);
if (!ad->arq_pool) {
- kfree(ad->hash);
kfree(ad);
return NULL;
}
@@ -1672,9 +1542,6 @@ static void *as_init_queue(request_queue
init_timer(&ad->antic_timer);
INIT_WORK(&ad->antic_work, as_work_handler, q);
- for (i = 0; i < AS_HASH_ENTRIES; i++)
- INIT_HLIST_HEAD(&ad->hash[i]);
-
INIT_LIST_HEAD(&ad->fifo_list[REQ_SYNC]);
INIT_LIST_HEAD(&ad->fifo_list[REQ_ASYNC]);
ad->sort_list[REQ_SYNC] = RB_ROOT;
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 102ebc2..6fd8af1 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -41,16 +41,6 @@ #define CFQ_QHASH_SHIFT 6
#define CFQ_QHASH_ENTRIES (1 << CFQ_QHASH_SHIFT)
#define list_entry_qhash(entry) hlist_entry((entry), struct cfq_queue, cfq_hash)
-/*
- * for the hash of crq inside the cfqq
- */
-#define CFQ_MHASH_SHIFT 6
-#define CFQ_MHASH_BLOCK(sec) ((sec) >> 3)
-#define CFQ_MHASH_ENTRIES (1 << CFQ_MHASH_SHIFT)
-#define CFQ_MHASH_FN(sec) hash_long(CFQ_MHASH_BLOCK(sec), CFQ_MHASH_SHIFT)
-#define rq_hash_key(rq) ((rq)->sector + (rq)->nr_sectors)
-#define list_entry_hash(ptr) hlist_entry((ptr), struct cfq_rq, hash)
-
#define list_entry_cfqq(ptr) list_entry((ptr), struct cfq_queue, cfq_list)
#define list_entry_fifo(ptr) list_entry((ptr), struct request, queuelist)
@@ -112,11 +102,6 @@ struct cfq_data {
*/
struct hlist_head *cfq_hash;
- /*
- * global crq hash for all queues
- */
- struct hlist_head *crq_hash;
-
mempool_t *crq_pool;
int rq_in_driver;
@@ -203,7 +188,6 @@ struct cfq_rq {
struct rb_node rb_node;
sector_t rb_key;
struct request *request;
- struct hlist_node hash;
struct cfq_queue *cfq_queue;
struct cfq_io_context *io_context;
@@ -272,42 +256,6 @@ static void cfq_dispatch_insert(request_
static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, unsigned int key, struct task_struct *tsk, gfp_t gfp_mask);
/*
- * lots of deadline iosched dupes, can be abstracted later...
- */
-static inline void cfq_del_crq_hash(struct cfq_rq *crq)
-{
- hlist_del_init(&crq->hash);
-}
-
-static inline void cfq_add_crq_hash(struct cfq_data *cfqd, struct cfq_rq *crq)
-{
- const int hash_idx = CFQ_MHASH_FN(rq_hash_key(crq->request));
-
- hlist_add_head(&crq->hash, &cfqd->crq_hash[hash_idx]);
-}
-
-static struct request *cfq_find_rq_hash(struct cfq_data *cfqd, sector_t offset)
-{
- struct hlist_head *hash_list = &cfqd->crq_hash[CFQ_MHASH_FN(offset)];
- struct hlist_node *entry, *next;
-
- hlist_for_each_safe(entry, next, hash_list) {
- struct cfq_rq *crq = list_entry_hash(entry);
- struct request *__rq = crq->request;
-
- if (!rq_mergeable(__rq)) {
- cfq_del_crq_hash(crq);
- continue;
- }
-
- if (rq_hash_key(__rq) == offset)
- return __rq;
- }
-
- return NULL;
-}
-
-/*
* scheduler run of queue, if there are requests pending and no one in the
* driver that will restart queueing
*/
@@ -677,7 +625,6 @@ static void cfq_remove_request(struct re
list_del_init(&rq->queuelist);
cfq_del_crq_rb(crq);
- cfq_del_crq_hash(crq);
}
static int
@@ -685,34 +632,20 @@ cfq_merge(request_queue_t *q, struct req
{
struct cfq_data *cfqd = q->elevator->elevator_data;
struct request *__rq;
- int ret;
-
- __rq = cfq_find_rq_hash(cfqd, bio->bi_sector);
- if (__rq && elv_rq_merge_ok(__rq, bio)) {
- ret = ELEVATOR_BACK_MERGE;
- goto out;
- }
__rq = cfq_find_rq_fmerge(cfqd, bio);
if (__rq && elv_rq_merge_ok(__rq, bio)) {
- ret = ELEVATOR_FRONT_MERGE;
- goto out;
+ *req = __rq;
+ return ELEVATOR_FRONT_MERGE;
}
return ELEVATOR_NO_MERGE;
-out:
- *req = __rq;
- return ret;
}
static void cfq_merged_request(request_queue_t *q, struct request *req)
{
- struct cfq_data *cfqd = q->elevator->elevator_data;
struct cfq_rq *crq = RQ_DATA(req);
- cfq_del_crq_hash(crq);
- cfq_add_crq_hash(cfqd, crq);
-
if (rq_rb_key(req) != crq->rb_key) {
struct cfq_queue *cfqq = crq->cfq_queue;
@@ -1825,9 +1758,6 @@ static void cfq_insert_request(request_q
list_add_tail(&rq->queuelist, &cfqq->fifo);
- if (rq_mergeable(rq))
- cfq_add_crq_hash(cfqd, crq);
-
cfq_crq_enqueued(cfqd, cfqq, crq);
}
@@ -2055,7 +1985,6 @@ cfq_set_request(request_queue_t *q, stru
RB_CLEAR_NODE(&crq->rb_node);
crq->rb_key = 0;
crq->request = rq;
- INIT_HLIST_NODE(&crq->hash);
crq->cfq_queue = cfqq;
crq->io_context = cic;
@@ -2221,7 +2150,6 @@ static void cfq_exit_queue(elevator_t *e
cfq_shutdown_timer_wq(cfqd);
mempool_destroy(cfqd->crq_pool);
- kfree(cfqd->crq_hash);
kfree(cfqd->cfq_hash);
kfree(cfqd);
}
@@ -2246,20 +2174,14 @@ static void *cfq_init_queue(request_queu
INIT_LIST_HEAD(&cfqd->empty_list);
INIT_LIST_HEAD(&cfqd->cic_list);
- cfqd->crq_hash = kmalloc(sizeof(struct hlist_head) * CFQ_MHASH_ENTRIES, GFP_KERNEL);
- if (!cfqd->crq_hash)
- goto out_crqhash;
-
cfqd->cfq_hash = kmalloc(sizeof(struct hlist_head) * CFQ_QHASH_ENTRIES, GFP_KERNEL);
if (!cfqd->cfq_hash)
- goto out_cfqhash;
+ goto out_crqhash;
cfqd->crq_pool = mempool_create_slab_pool(BLKDEV_MIN_RQ, crq_pool);
if (!cfqd->crq_pool)
goto out_crqpool;
- for (i = 0; i < CFQ_MHASH_ENTRIES; i++)
- INIT_HLIST_HEAD(&cfqd->crq_hash[i]);
for (i = 0; i < CFQ_QHASH_ENTRIES; i++)
INIT_HLIST_HEAD(&cfqd->cfq_hash[i]);
@@ -2289,8 +2211,6 @@ static void *cfq_init_queue(request_queu
return cfqd;
out_crqpool:
kfree(cfqd->cfq_hash);
-out_cfqhash:
- kfree(cfqd->crq_hash);
out_crqhash:
kfree(cfqd);
return NULL;
diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index c7ca9f0..b66e820 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -12,7 +12,6 @@ #include <linux/module.h>
#include <linux/slab.h>
#include <linux/init.h>
#include <linux/compiler.h>
-#include <linux/hash.h>
#include <linux/rbtree.h>
/*
@@ -24,13 +23,6 @@ static const int writes_starved = 2;
static const int fifo_batch = 16; /* # of sequential requests treated as one
by the above parameters. For throughput. */
-static const int deadline_hash_shift = 5;
-#define DL_HASH_BLOCK(sec) ((sec) >> 3)
-#define DL_HASH_FN(sec) (hash_long(DL_HASH_BLOCK((sec)), deadline_hash_shift))
-#define DL_HASH_ENTRIES (1 << deadline_hash_shift)
-#define rq_hash_key(rq) ((rq)->sector + (rq)->nr_sectors)
-#define ON_HASH(drq) (!hlist_unhashed(&(drq)->hash))
-
struct deadline_data {
/*
* run time data
@@ -46,7 +38,6 @@ struct deadline_data {
* next in sort order. read, write or both are NULL
*/
struct deadline_rq *next_drq[2];
- struct hlist_head *hash; /* request hash */
unsigned int batching; /* number of sequential requests made */
sector_t last_sector; /* head position */
unsigned int starved; /* times reads have starved writes */
@@ -75,11 +66,6 @@ struct deadline_rq {
struct request *request;
/*
- * request hash, key is the ending offset (for back merge lookup)
- */
- struct hlist_node hash;
-
- /*
* expire fifo
*/
struct list_head fifo;
@@ -93,69 +79,6 @@ static kmem_cache_t *drq_pool;
#define RQ_DATA(rq) ((struct deadline_rq *) (rq)->elevator_private)
/*
- * the back merge hash support functions
- */
-static inline void __deadline_del_drq_hash(struct deadline_rq *drq)
-{
- hlist_del_init(&drq->hash);
-}
-
-static inline void deadline_del_drq_hash(struct deadline_rq *drq)
-{
- if (ON_HASH(drq))
- __deadline_del_drq_hash(drq);
-}
-
-static inline void
-deadline_add_drq_hash(struct deadline_data *dd, struct deadline_rq *drq)
-{
- struct request *rq = drq->request;
-
- BUG_ON(ON_HASH(drq));
-
- hlist_add_head(&drq->hash, &dd->hash[DL_HASH_FN(rq_hash_key(rq))]);
-}
-
-/*
- * move hot entry to front of chain
- */
-static inline void
-deadline_hot_drq_hash(struct deadline_data *dd, struct deadline_rq *drq)
-{
- struct request *rq = drq->request;
- struct hlist_head *head = &dd->hash[DL_HASH_FN(rq_hash_key(rq))];
-
- if (ON_HASH(drq) && &drq->hash != head->first) {
- hlist_del(&drq->hash);
- hlist_add_head(&drq->hash, head);
- }
-}
-
-static struct request *
-deadline_find_drq_hash(struct deadline_data *dd, sector_t offset)
-{
- struct hlist_head *hash_list = &dd->hash[DL_HASH_FN(offset)];
- struct hlist_node *entry, *next;
- struct deadline_rq *drq;
-
- hlist_for_each_entry_safe(drq, entry, next, hash_list, hash) {
- struct request *__rq = drq->request;
-
- BUG_ON(!ON_HASH(drq));
-
- if (!rq_mergeable(__rq)) {
- __deadline_del_drq_hash(drq);
- continue;
- }
-
- if (rq_hash_key(__rq) == offset)
- return __rq;
- }
-
- return NULL;
-}
-
-/*
* rb tree support functions
*/
#define rb_entry_drq(node) rb_entry((node), struct deadline_rq, rb_node)
@@ -267,22 +190,19 @@ deadline_add_request(struct request_queu
{
struct deadline_data *dd = q->elevator->elevator_data;
struct deadline_rq *drq = RQ_DATA(rq);
-
const int data_dir = rq_data_dir(drq->request);
deadline_add_drq_rb(dd, drq);
+
/*
* set expire time (only used for reads) and add to fifo list
*/
drq->expires = jiffies + dd->fifo_expire[data_dir];
list_add_tail(&drq->fifo, &dd->fifo_list[data_dir]);
-
- if (rq_mergeable(rq))
- deadline_add_drq_hash(dd, drq);
}
/*
- * remove rq from rbtree, fifo, and hash
+ * remove rq from rbtree and fifo.
*/
static void deadline_remove_request(request_queue_t *q, struct request *rq)
{
@@ -291,7 +211,6 @@ static void deadline_remove_request(requ
list_del_init(&drq->fifo);
deadline_del_drq_rb(dd, drq);
- deadline_del_drq_hash(drq);
}
static int
@@ -302,19 +221,6 @@ deadline_merge(request_queue_t *q, struc
int ret;
/*
- * see if the merge hash can satisfy a back merge
- */
- __rq = deadline_find_drq_hash(dd, bio->bi_sector);
- if (__rq) {
- BUG_ON(__rq->sector + __rq->nr_sectors != bio->bi_sector);
-
- if (elv_rq_merge_ok(__rq, bio)) {
- ret = ELEVATOR_BACK_MERGE;
- goto out;
- }
- }
-
- /*
* check for front merge
*/
if (dd->front_merges) {
@@ -333,8 +239,6 @@ deadline_merge(request_queue_t *q, struc
return ELEVATOR_NO_MERGE;
out:
- if (ret)
- deadline_hot_drq_hash(dd, RQ_DATA(__rq));
*req = __rq;
return ret;
}
@@ -345,12 +249,6 @@ static void deadline_merged_request(requ
struct deadline_rq *drq = RQ_DATA(req);
/*
- * hash always needs to be repositioned, key is end sector
- */
- deadline_del_drq_hash(drq);
- deadline_add_drq_hash(dd, drq);
-
- /*
* if the merge was a front merge, we need to reposition request
*/
if (rq_rb_key(req) != drq->rb_key) {
@@ -370,13 +268,6 @@ deadline_merged_requests(request_queue_t
BUG_ON(!drq);
BUG_ON(!dnext);
- /*
- * reposition drq (this is the merged request) in hash, and in rbtree
- * in case of a front merge
- */
- deadline_del_drq_hash(drq);
- deadline_add_drq_hash(dd, drq);
-
if (rq_rb_key(req) != drq->rb_key) {
deadline_del_drq_rb(dd, drq);
deadline_add_drq_rb(dd, drq);
@@ -594,7 +485,6 @@ static void deadline_exit_queue(elevator
BUG_ON(!list_empty(&dd->fifo_list[WRITE]));
mempool_destroy(dd->drq_pool);
- kfree(dd->hash);
kfree(dd);
}
@@ -605,7 +495,6 @@ static void deadline_exit_queue(elevator
static void *deadline_init_queue(request_queue_t *q, elevator_t *e)
{
struct deadline_data *dd;
- int i;
if (!drq_pool)
return NULL;
@@ -615,24 +504,13 @@ static void *deadline_init_queue(request
return NULL;
memset(dd, 0, sizeof(*dd));
- dd->hash = kmalloc_node(sizeof(struct hlist_head)*DL_HASH_ENTRIES,
- GFP_KERNEL, q->node);
- if (!dd->hash) {
- kfree(dd);
- return NULL;
- }
-
dd->drq_pool = mempool_create_node(BLKDEV_MIN_RQ, mempool_alloc_slab,
mempool_free_slab, drq_pool, q->node);
if (!dd->drq_pool) {
- kfree(dd->hash);
kfree(dd);
return NULL;
}
- for (i = 0; i < DL_HASH_ENTRIES; i++)
- INIT_HLIST_HEAD(&dd->hash[i]);
-
INIT_LIST_HEAD(&dd->fifo_list[READ]);
INIT_LIST_HEAD(&dd->fifo_list[WRITE]);
dd->sort_list[READ] = RB_ROOT;
@@ -667,8 +545,6 @@ deadline_set_request(request_queue_t *q,
RB_CLEAR_NODE(&drq->rb_node);
drq->request = rq;
- INIT_HLIST_NODE(&drq->hash);
-
INIT_LIST_HEAD(&drq->fifo);
rq->elevator_private = drq;
diff --git a/block/elevator.c b/block/elevator.c
index bc7baee..3e40530 100644
--- a/block/elevator.c
+++ b/block/elevator.c
@@ -33,6 +33,7 @@ #include <linux/init.h>
#include <linux/compiler.h>
#include <linux/delay.h>
#include <linux/blktrace_api.h>
+#include <linux/hash.h>
#include <asm/uaccess.h>
@@ -40,6 +41,16 @@ static DEFINE_SPINLOCK(elv_list_lock);
static LIST_HEAD(elv_list);
/*
+ * Merge hash stuff.
+ */
+static const int elv_hash_shift = 6;
+#define ELV_HASH_BLOCK(sec) ((sec) >> 3)
+#define ELV_HASH_FN(sec) (hash_long(ELV_HASH_BLOCK((sec)), elv_hash_shift))
+#define ELV_HASH_ENTRIES (1 << elv_hash_shift)
+#define rq_hash_key(rq) ((rq)->sector + (rq)->nr_sectors)
+#define ELV_ON_HASH(rq) (!hlist_unhashed(&(rq)->hash))
+
+/*
* can we safely merge with this request?
*/
inline int elv_rq_merge_ok(struct request *rq, struct bio *bio)
@@ -153,25 +164,41 @@ static struct kobj_type elv_ktype;
static elevator_t *elevator_alloc(struct elevator_type *e)
{
- elevator_t *eq = kmalloc(sizeof(elevator_t), GFP_KERNEL);
- if (eq) {
- memset(eq, 0, sizeof(*eq));
- eq->ops = &e->ops;
- eq->elevator_type = e;
- kobject_init(&eq->kobj);
- snprintf(eq->kobj.name, KOBJ_NAME_LEN, "%s", "iosched");
- eq->kobj.ktype = &elv_ktype;
- mutex_init(&eq->sysfs_lock);
- } else {
- elevator_put(e);
- }
+ elevator_t *eq;
+ int i;
+
+ eq = kmalloc(sizeof(elevator_t), GFP_KERNEL);
+ if (unlikely(!eq))
+ goto err;
+
+ memset(eq, 0, sizeof(*eq));
+ eq->ops = &e->ops;
+ eq->elevator_type = e;
+ kobject_init(&eq->kobj);
+ snprintf(eq->kobj.name, KOBJ_NAME_LEN, "%s", "iosched");
+ eq->kobj.ktype = &elv_ktype;
+ mutex_init(&eq->sysfs_lock);
+
+ eq->hash = kmalloc(sizeof(struct hlist_head) * ELV_HASH_ENTRIES, GFP_KERNEL);
+ if (!eq->hash)
+ goto err;
+
+ for (i = 0; i < ELV_HASH_ENTRIES; i++)
+ INIT_HLIST_HEAD(&eq->hash[i]);
+
return eq;
+err:
+ kfree(eq);
+ elevator_put(e);
+ return NULL;
}
static void elevator_release(struct kobject *kobj)
{
elevator_t *e = container_of(kobj, elevator_t, kobj);
+
elevator_put(e->elevator_type);
+ kfree(e->hash);
kfree(e);
}
@@ -223,6 +250,53 @@ void elevator_exit(elevator_t *e)
kobject_put(&e->kobj);
}
+static inline void __elv_rqhash_del(struct request *rq)
+{
+ hlist_del_init(&rq->hash);
+}
+
+static void elv_rqhash_del(request_queue_t *q, struct request *rq)
+{
+ if (ELV_ON_HASH(rq))
+ __elv_rqhash_del(rq);
+}
+
+static void elv_rqhash_add(request_queue_t *q, struct request *rq)
+{
+ elevator_t *e = q->elevator;
+
+ BUG_ON(ELV_ON_HASH(rq));
+ hlist_add_head(&rq->hash, &e->hash[ELV_HASH_FN(rq_hash_key(rq))]);
+}
+
+static void elv_rqhash_reposition(request_queue_t *q, struct request *rq)
+{
+ __elv_rqhash_del(rq);
+ elv_rqhash_add(q, rq);
+}
+
+static struct request *elv_rqhash_find(request_queue_t *q, sector_t offset)
+{
+ elevator_t *e = q->elevator;
+ struct hlist_head *hash_list = &e->hash[ELV_HASH_FN(offset)];
+ struct hlist_node *entry, *next;
+ struct request *rq;
+
+ hlist_for_each_entry_safe(rq, entry, next, hash_list, hash) {
+ BUG_ON(!ELV_ON_HASH(rq));
+
+ if (unlikely(!rq_mergeable(rq))) {
+ __elv_rqhash_del(rq);
+ continue;
+ }
+
+ if (rq_hash_key(rq) == offset)
+ return rq;
+ }
+
+ return NULL;
+}
+
/*
* Insert rq into dispatch queue of q. Queue lock must be held on
* entry. If sort != 0, rq is sort-inserted; otherwise, rq will be
@@ -235,6 +309,9 @@ void elv_dispatch_sort(request_queue_t *
if (q->last_merge == rq)
q->last_merge = NULL;
+
+ elv_rqhash_del(q, rq);
+
q->nr_sorted--;
boundary = q->end_sector;
@@ -258,11 +335,32 @@ void elv_dispatch_sort(request_queue_t *
list_add(&rq->queuelist, entry);
}
+/*
+ * This should be in elevator.h, but that requires pulling in rq and q
+ */
+void elv_dispatch_add_tail(struct request_queue *q, struct request *rq)
+{
+ if (q->last_merge == rq)
+ q->last_merge = NULL;
+
+ elv_rqhash_del(q, rq);
+
+ q->nr_sorted--;
+
+ q->end_sector = rq_end_sector(rq);
+ q->boundary_rq = rq;
+ list_add_tail(&rq->queuelist, &q->queue_head);
+}
+
int elv_merge(request_queue_t *q, struct request **req, struct bio *bio)
{
elevator_t *e = q->elevator;
+ struct request *__rq;
int ret;
+ /*
+ * First try one-hit cache.
+ */
if (q->last_merge) {
ret = elv_try_merge(q->last_merge, bio);
if (ret != ELEVATOR_NO_MERGE) {
@@ -271,6 +369,15 @@ int elv_merge(request_queue_t *q, struct
}
}
+ /*
+ * See if our hash lookup can find a potential backmerge.
+ */
+ __rq = elv_rqhash_find(q, bio->bi_sector);
+ if (__rq && elv_rq_merge_ok(__rq, bio)) {
+ *req = __rq;
+ return ELEVATOR_BACK_MERGE;
+ }
+
if (e->ops->elevator_merge_fn)
return e->ops->elevator_merge_fn(q, req, bio);
@@ -284,6 +391,8 @@ void elv_merged_request(request_queue_t
if (e->ops->elevator_merged_fn)
e->ops->elevator_merged_fn(q, rq);
+ elv_rqhash_reposition(q, rq);
+
q->last_merge = rq;
}
@@ -294,8 +403,11 @@ void elv_merge_requests(request_queue_t
if (e->ops->elevator_merge_req_fn)
e->ops->elevator_merge_req_fn(q, rq, next);
- q->nr_sorted--;
+ elv_rqhash_reposition(q, rq);
+ elv_rqhash_del(q, next);
+
+ q->nr_sorted--;
q->last_merge = rq;
}
@@ -371,8 +483,12 @@ void elv_insert(request_queue_t *q, stru
BUG_ON(!blk_fs_request(rq));
rq->flags |= REQ_SORTED;
q->nr_sorted++;
- if (q->last_merge == NULL && rq_mergeable(rq))
- q->last_merge = rq;
+ if (rq_mergeable(rq)) {
+ elv_rqhash_add(q, rq);
+ if (!q->last_merge)
+ q->last_merge = rq;
+ }
+
/*
* Some ioscheds (cfq) run q->request_fn directly, so
* rq cannot be accessed after calling
@@ -557,6 +673,7 @@ struct request *elv_next_request(request
void elv_dequeue_request(request_queue_t *q, struct request *rq)
{
BUG_ON(list_empty(&rq->queuelist));
+ BUG_ON(ELV_ON_HASH(rq));
list_del_init(&rq->queuelist);
diff --git a/block/ll_rw_blk.c b/block/ll_rw_blk.c
index 61d6b3c..84c7b1c 100644
--- a/block/ll_rw_blk.c
+++ b/block/ll_rw_blk.c
@@ -281,6 +281,7 @@ static inline void rq_init(request_queue
{
INIT_LIST_HEAD(&rq->queuelist);
INIT_LIST_HEAD(&rq->donelist);
+ INIT_HLIST_NODE(&rq->hash);
rq->errors = 0;
rq->rq_status = RQ_ACTIVE;
@@ -2665,6 +2666,7 @@ void __blk_put_request(request_queue_t *
int priv = req->flags & REQ_ELVPRIV;
BUG_ON(!list_empty(&req->queuelist));
+ BUG_ON(!hlist_unhashed(&req->hash));
blk_free_request(q, req);
freed_request(q, rw, priv);
diff --git a/include/linux/blkdev.h b/include/linux/blkdev.h
index aafe827..9b23cbe 100644
--- a/include/linux/blkdev.h
+++ b/include/linux/blkdev.h
@@ -148,6 +148,8 @@ struct request {
struct bio *bio;
struct bio *biotail;
+ struct hlist_node hash; /* merge hash */
+
void *elevator_private;
void *completion_data;
@@ -679,21 +681,6 @@ static inline void blkdev_dequeue_reques
}
/*
- * This should be in elevator.h, but that requires pulling in rq and q
- */
-static inline void elv_dispatch_add_tail(struct request_queue *q,
- struct request *rq)
-{
- if (q->last_merge == rq)
- q->last_merge = NULL;
- q->nr_sorted--;
-
- q->end_sector = rq_end_sector(rq);
- q->boundary_rq = rq;
- list_add_tail(&rq->queuelist, &q->queue_head);
-}
-
-/*
* Access functions for manipulating queue properties
*/
extern request_queue_t *blk_init_queue_node(request_fn_proc *rfn,
diff --git a/include/linux/elevator.h b/include/linux/elevator.h
index 1713ace..2c270e9 100644
--- a/include/linux/elevator.h
+++ b/include/linux/elevator.h
@@ -82,12 +82,14 @@ struct elevator_queue
struct kobject kobj;
struct elevator_type *elevator_type;
struct mutex sysfs_lock;
+ struct hlist_head *hash;
};
/*
* block elevator interface
*/
extern void elv_dispatch_sort(request_queue_t *, struct request *);
+extern void elv_dispatch_add_tail(request_queue_t *, struct request *);
extern void elv_add_request(request_queue_t *, struct request *, int, int);
extern void __elv_add_request(request_queue_t *, struct request *, int, int);
extern void elv_insert(request_queue_t *, struct request *, int);
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 2/15 rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev
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 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 3/15 elevator: abstract out the rbtree sort handling Jens Axboe
` (12 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
The conditions got reserved. Also make rb_next() and rb_prev() check
for the empty condition.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/as-iosched.c | 4 ++--
include/linux/rbtree.h | 2 +-
lib/rbtree.c | 6 ++++++
3 files changed, 9 insertions(+), 3 deletions(-)
diff --git a/block/as-iosched.c b/block/as-iosched.c
index 1c44ce3..d677029 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -336,7 +336,7 @@ static void as_add_arq_rb(struct as_data
static inline void as_del_arq_rb(struct as_data *ad, struct as_rq *arq)
{
- if (!RB_EMPTY_NODE(&arq->rb_node)) {
+ if (RB_EMPTY_NODE(&arq->rb_node)) {
WARN_ON(1);
return;
}
@@ -1039,7 +1039,7 @@ static void as_move_to_dispatch(struct a
struct request *rq = arq->request;
const int data_dir = arq->is_sync;
- BUG_ON(!RB_EMPTY_NODE(&arq->rb_node));
+ BUG_ON(RB_EMPTY_NODE(&arq->rb_node));
as_antic_stop(ad);
ad->antic_status = ANTIC_OFF;
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 8d5382e..344bc34 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -133,7 +133,7 @@ #define RB_ROOT (struct rb_root) { NULL,
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
-#define RB_EMPTY_NODE(node) (rb_parent(node) != node)
+#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
extern void rb_insert_color(struct rb_node *, struct rb_root *);
diff --git a/lib/rbtree.c b/lib/rbtree.c
index 1e55ba1..48499c2 100644
--- a/lib/rbtree.c
+++ b/lib/rbtree.c
@@ -322,6 +322,9 @@ struct rb_node *rb_next(struct rb_node *
{
struct rb_node *parent;
+ if (rb_parent(node) == node)
+ return NULL;
+
/* If we have a right-hand child, go down and then left as far
as we can. */
if (node->rb_right) {
@@ -348,6 +351,9 @@ struct rb_node *rb_prev(struct rb_node *
{
struct rb_node *parent;
+ if (rb_parent(node) == node)
+ return NULL;
+
/* If we have a left-hand child, go down and then right as far
as we can. */
if (node->rb_left) {
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 3/15 elevator: abstract out the rbtree sort handling
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 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 4/15 as-iosched: migrate to using the elevator rb functions Jens Axboe
` (11 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
The rbtree sort/lookup/reposition logic is mostly duplicated in
cfq/deadline/as, so move it to the elevator core. The io schedulers
still provide the actual rb root, as we don't want to impose any sort
of specific handling on the schedulers.
Introduce the helpers and rb_node in struct request to help migrate the
IO schedulers.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/elevator.c | 123 +++++++++++++++++++++++++++++++++++++++++-----
block/ll_rw_blk.c | 7 +--
include/linux/blkdev.h | 1
include/linux/elevator.h | 18 ++++++-
4 files changed, 130 insertions(+), 19 deletions(-)
diff --git a/block/elevator.c b/block/elevator.c
index 3e40530..9cd2805 100644
--- a/block/elevator.c
+++ b/block/elevator.c
@@ -239,6 +239,8 @@ int elevator_init(request_queue_t *q, ch
return ret;
}
+EXPORT_SYMBOL(elevator_init);
+
void elevator_exit(elevator_t *e)
{
mutex_lock(&e->sysfs_lock);
@@ -250,6 +252,8 @@ void elevator_exit(elevator_t *e)
kobject_put(&e->kobj);
}
+EXPORT_SYMBOL(elevator_exit);
+
static inline void __elv_rqhash_del(struct request *rq)
{
hlist_del_init(&rq->hash);
@@ -298,9 +302,68 @@ static struct request *elv_rqhash_find(r
}
/*
+ * RB-tree support functions for inserting/lookup/removal of requests
+ * in a sorted RB tree.
+ */
+struct request *elv_rb_add(struct rb_root *root, struct request *rq)
+{
+ struct rb_node **p = &root->rb_node;
+ struct rb_node *parent = NULL;
+ struct request *__rq;
+
+ while (*p) {
+ parent = *p;
+ __rq = rb_entry(parent, struct request, rb_node);
+
+ if (rq->sector < __rq->sector)
+ p = &(*p)->rb_left;
+ else if (rq->sector > __rq->sector)
+ p = &(*p)->rb_right;
+ else
+ return __rq;
+ }
+
+ rb_link_node(&rq->rb_node, parent, p);
+ rb_insert_color(&rq->rb_node, root);
+ return NULL;
+}
+
+EXPORT_SYMBOL(elv_rb_add);
+
+void elv_rb_del(struct rb_root *root, struct request *rq)
+{
+ BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
+ rb_erase(&rq->rb_node, root);
+ RB_CLEAR_NODE(&rq->rb_node);
+}
+
+EXPORT_SYMBOL(elv_rb_del);
+
+struct request *elv_rb_find(struct rb_root *root, sector_t sector)
+{
+ struct rb_node *n = root->rb_node;
+ struct request *rq;
+
+ while (n) {
+ rq = rb_entry(n, struct request, rb_node);
+
+ if (sector < rq->sector)
+ n = n->rb_left;
+ else if (sector > rq->sector)
+ n = n->rb_right;
+ else
+ return rq;
+ }
+
+ return NULL;
+}
+
+EXPORT_SYMBOL(elv_rb_find);
+
+/*
* Insert rq into dispatch queue of q. Queue lock must be held on
- * entry. If sort != 0, rq is sort-inserted; otherwise, rq will be
- * appended to the dispatch queue. To be used by specific elevators.
+ * entry. rq is sort insted into the dispatch queue. To be used by
+ * specific elevators.
*/
void elv_dispatch_sort(request_queue_t *q, struct request *rq)
{
@@ -335,8 +398,12 @@ void elv_dispatch_sort(request_queue_t *
list_add(&rq->queuelist, entry);
}
+EXPORT_SYMBOL(elv_dispatch_sort);
+
/*
- * This should be in elevator.h, but that requires pulling in rq and q
+ * Insert rq into dispatch queue of q. Queue lock must be held on
+ * entry. rq is added to the back of the dispatch queue. To be used by
+ * specific elevators.
*/
void elv_dispatch_add_tail(struct request_queue *q, struct request *rq)
{
@@ -352,6 +419,8 @@ void elv_dispatch_add_tail(struct reques
list_add_tail(&rq->queuelist, &q->queue_head);
}
+EXPORT_SYMBOL(elv_dispatch_add_tail);
+
int elv_merge(request_queue_t *q, struct request **req, struct bio *bio)
{
elevator_t *e = q->elevator;
@@ -384,14 +453,15 @@ int elv_merge(request_queue_t *q, struct
return ELEVATOR_NO_MERGE;
}
-void elv_merged_request(request_queue_t *q, struct request *rq)
+void elv_merged_request(request_queue_t *q, struct request *rq, int type)
{
elevator_t *e = q->elevator;
if (e->ops->elevator_merged_fn)
- e->ops->elevator_merged_fn(q, rq);
+ e->ops->elevator_merged_fn(q, rq, type);
- elv_rqhash_reposition(q, rq);
+ if (type == ELEVATOR_BACK_MERGE)
+ elv_rqhash_reposition(q, rq);
q->last_merge = rq;
}
@@ -577,6 +647,8 @@ void __elv_add_request(request_queue_t *
elv_insert(q, rq, where);
}
+EXPORT_SYMBOL(__elv_add_request);
+
void elv_add_request(request_queue_t *q, struct request *rq, int where,
int plug)
{
@@ -587,6 +659,8 @@ void elv_add_request(request_queue_t *q,
spin_unlock_irqrestore(q->queue_lock, flags);
}
+EXPORT_SYMBOL(elv_add_request);
+
static inline struct request *__elv_next_request(request_queue_t *q)
{
struct request *rq;
@@ -670,6 +744,8 @@ struct request *elv_next_request(request
return rq;
}
+EXPORT_SYMBOL(elv_next_request);
+
void elv_dequeue_request(request_queue_t *q, struct request *rq)
{
BUG_ON(list_empty(&rq->queuelist));
@@ -686,6 +762,8 @@ void elv_dequeue_request(request_queue_t
q->in_flight++;
}
+EXPORT_SYMBOL(elv_dequeue_request);
+
int elv_queue_empty(request_queue_t *q)
{
elevator_t *e = q->elevator;
@@ -699,6 +777,8 @@ int elv_queue_empty(request_queue_t *q)
return 1;
}
+EXPORT_SYMBOL(elv_queue_empty);
+
struct request *elv_latter_request(request_queue_t *q, struct request *rq)
{
elevator_t *e = q->elevator;
@@ -1024,11 +1104,26 @@ ssize_t elv_iosched_show(request_queue_t
return len;
}
-EXPORT_SYMBOL(elv_dispatch_sort);
-EXPORT_SYMBOL(elv_add_request);
-EXPORT_SYMBOL(__elv_add_request);
-EXPORT_SYMBOL(elv_next_request);
-EXPORT_SYMBOL(elv_dequeue_request);
-EXPORT_SYMBOL(elv_queue_empty);
-EXPORT_SYMBOL(elevator_exit);
-EXPORT_SYMBOL(elevator_init);
+struct request *elv_rb_former_request(request_queue_t *q, struct request *rq)
+{
+ struct rb_node *rbprev = rb_prev(&rq->rb_node);
+
+ if (rbprev)
+ return rb_entry_rq(rbprev);
+
+ return NULL;
+}
+
+EXPORT_SYMBOL(elv_rb_former_request);
+
+struct request *elv_rb_latter_request(request_queue_t *q, struct request *rq)
+{
+ struct rb_node *rbnext = rb_next(&rq->rb_node);
+
+ if (rbnext)
+ return rb_entry_rq(rbnext);
+
+ return NULL;
+}
+
+EXPORT_SYMBOL(elv_rb_latter_request);
diff --git a/block/ll_rw_blk.c b/block/ll_rw_blk.c
index 84c7b1c..08c1615 100644
--- a/block/ll_rw_blk.c
+++ b/block/ll_rw_blk.c
@@ -281,11 +281,12 @@ static inline void rq_init(request_queue
{
INIT_LIST_HEAD(&rq->queuelist);
INIT_LIST_HEAD(&rq->donelist);
- INIT_HLIST_NODE(&rq->hash);
rq->errors = 0;
rq->rq_status = RQ_ACTIVE;
rq->bio = rq->biotail = NULL;
+ INIT_HLIST_NODE(&rq->hash);
+ RB_CLEAR_NODE(&rq->rb_node);
rq->ioprio = 0;
rq->buffer = NULL;
rq->ref_count = 1;
@@ -2896,7 +2897,7 @@ static int __make_request(request_queue_
req->ioprio = ioprio_best(req->ioprio, prio);
drive_stat_acct(req, nr_sectors, 0);
if (!attempt_back_merge(q, req))
- elv_merged_request(q, req);
+ elv_merged_request(q, req, el_ret);
goto out;
case ELEVATOR_FRONT_MERGE:
@@ -2923,7 +2924,7 @@ static int __make_request(request_queue_
req->ioprio = ioprio_best(req->ioprio, prio);
drive_stat_acct(req, nr_sectors, 0);
if (!attempt_front_merge(q, req))
- elv_merged_request(q, req);
+ elv_merged_request(q, req, el_ret);
goto out;
/* ELV_NO_MERGE: elevator says don't/can't merge. */
diff --git a/include/linux/blkdev.h b/include/linux/blkdev.h
index 9b23cbe..e296719 100644
--- a/include/linux/blkdev.h
+++ b/include/linux/blkdev.h
@@ -149,6 +149,7 @@ struct request {
struct bio *biotail;
struct hlist_node hash; /* merge hash */
+ struct rb_node rb_node; /* sort/lookup */
void *elevator_private;
void *completion_data;
diff --git a/include/linux/elevator.h b/include/linux/elevator.h
index 2c270e9..95b2a04 100644
--- a/include/linux/elevator.h
+++ b/include/linux/elevator.h
@@ -6,7 +6,7 @@ typedef int (elevator_merge_fn) (request
typedef void (elevator_merge_req_fn) (request_queue_t *, struct request *, struct request *);
-typedef void (elevator_merged_fn) (request_queue_t *, struct request *);
+typedef void (elevator_merged_fn) (request_queue_t *, struct request *, int);
typedef int (elevator_dispatch_fn) (request_queue_t *, int);
@@ -96,7 +96,7 @@ extern void elv_insert(request_queue_t *
extern int elv_merge(request_queue_t *, struct request **, struct bio *);
extern void elv_merge_requests(request_queue_t *, struct request *,
struct request *);
-extern void elv_merged_request(request_queue_t *, struct request *);
+extern void elv_merged_request(request_queue_t *, struct request *, int);
extern void elv_dequeue_request(request_queue_t *, struct request *);
extern void elv_requeue_request(request_queue_t *, struct request *);
extern int elv_queue_empty(request_queue_t *);
@@ -127,6 +127,19 @@ extern void elevator_exit(elevator_t *);
extern int elv_rq_merge_ok(struct request *, struct bio *);
/*
+ * Helper functions.
+ */
+extern struct request *elv_rb_former_request(request_queue_t *, struct request *);
+extern struct request *elv_rb_latter_request(request_queue_t *, struct request *);
+
+/*
+ * rb support functions.
+ */
+extern struct request *elv_rb_add(struct rb_root *, struct request *);
+extern void elv_rb_del(struct rb_root *, struct request *);
+extern struct request *elv_rb_find(struct rb_root *, sector_t);
+
+/*
* Return values from elevator merger
*/
#define ELEVATOR_NO_MERGE 0
@@ -151,5 +164,6 @@ enum {
};
#define rq_end_sector(rq) ((rq)->sector + (rq)->nr_sectors)
+#define rb_entry_rq(node) rb_entry((node), struct request, rb_node)
#endif
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 4/15 as-iosched: migrate to using the elevator rb functions
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (2 preceding siblings ...)
2006-07-13 12:46 ` [PATCH] 3/15 elevator: abstract out the rbtree sort handling Jens Axboe
@ 2006-07-13 12:46 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 5/15 cfq-iosched: " Jens Axboe
` (10 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
This removes the rbtree handling from AS.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/as-iosched.c | 182 ++++++++--------------------------------------------
1 files changed, 29 insertions(+), 153 deletions(-)
diff --git a/block/as-iosched.c b/block/as-iosched.c
index d677029..413a944 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -149,12 +149,6 @@ enum arq_state {
};
struct as_rq {
- /*
- * rbtree index, key is the starting offset
- */
- struct rb_node rb_node;
- sector_t rb_key;
-
struct request *request;
struct io_context *io_context; /* The submitting task */
@@ -268,101 +262,22 @@ static void as_put_io_context(struct as_
/*
* rb tree support functions
*/
-#define rb_entry_arq(node) rb_entry((node), struct as_rq, rb_node)
#define ARQ_RB_ROOT(ad, arq) (&(ad)->sort_list[(arq)->is_sync])
-#define rq_rb_key(rq) (rq)->sector
-/*
- * as_find_first_arq 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 as_rq *as_find_first_arq(struct as_data *ad, int data_dir)
+static void as_add_arq_rb(struct as_data *ad, struct request *rq)
{
- struct rb_node *n = ad->sort_list[data_dir].rb_node;
-
- if (n == NULL)
- return NULL;
-
- for (;;) {
- if (n->rb_left == NULL)
- return rb_entry_arq(n);
-
- n = n->rb_left;
- }
-}
-
-/*
- * Add the request to the rb tree if it is unique. If there is an alias (an
- * existing request against the same sector), which can happen when using
- * direct IO, then return the alias.
- */
-static struct as_rq *__as_add_arq_rb(struct as_data *ad, struct as_rq *arq)
-{
- struct rb_node **p = &ARQ_RB_ROOT(ad, arq)->rb_node;
- struct rb_node *parent = NULL;
- struct as_rq *__arq;
- struct request *rq = arq->request;
-
- arq->rb_key = rq_rb_key(rq);
-
- while (*p) {
- parent = *p;
- __arq = rb_entry_arq(parent);
-
- if (arq->rb_key < __arq->rb_key)
- p = &(*p)->rb_left;
- else if (arq->rb_key > __arq->rb_key)
- p = &(*p)->rb_right;
- else
- return __arq;
- }
-
- rb_link_node(&arq->rb_node, parent, p);
- rb_insert_color(&arq->rb_node, ARQ_RB_ROOT(ad, arq));
-
- return NULL;
-}
-
-static void as_add_arq_rb(struct as_data *ad, struct as_rq *arq)
-{
- struct as_rq *alias;
+ struct as_rq *arq = RQ_DATA(rq);
+ struct request *alias;
- while ((unlikely(alias = __as_add_arq_rb(ad, arq)))) {
- as_move_to_dispatch(ad, alias);
+ while ((unlikely(alias = elv_rb_add(ARQ_RB_ROOT(ad, arq), rq)))) {
+ as_move_to_dispatch(ad, RQ_DATA(alias));
as_antic_stop(ad);
}
}
-static inline void as_del_arq_rb(struct as_data *ad, struct as_rq *arq)
+static inline void as_del_arq_rb(struct as_data *ad, struct request *rq)
{
- if (RB_EMPTY_NODE(&arq->rb_node)) {
- WARN_ON(1);
- return;
- }
-
- rb_erase(&arq->rb_node, ARQ_RB_ROOT(ad, arq));
- RB_CLEAR_NODE(&arq->rb_node);
-}
-
-static struct request *
-as_find_arq_rb(struct as_data *ad, sector_t sector, int data_dir)
-{
- struct rb_node *n = ad->sort_list[data_dir].rb_node;
- struct as_rq *arq;
-
- while (n) {
- arq = rb_entry_arq(n);
-
- if (sector < arq->rb_key)
- n = n->rb_left;
- else if (sector > arq->rb_key)
- n = n->rb_right;
- else
- return arq->request;
- }
-
- return NULL;
+ elv_rb_del(ARQ_RB_ROOT(ad, RQ_DATA(rq)), rq);
}
/*
@@ -455,32 +370,29 @@ as_choose_req(struct as_data *ad, struct
* this with as_choose_req form the basis for how the scheduler chooses
* what request to process next. Anticipation works on top of this.
*/
-static struct as_rq *as_find_next_arq(struct as_data *ad, struct as_rq *last)
+static struct as_rq *as_find_next_arq(struct as_data *ad, struct as_rq *arq)
{
- const int data_dir = last->is_sync;
- struct as_rq *ret;
+ struct request *last = arq->request;
struct rb_node *rbnext = rb_next(&last->rb_node);
struct rb_node *rbprev = rb_prev(&last->rb_node);
- struct as_rq *arq_next, *arq_prev;
+ struct as_rq *next = NULL, *prev = NULL;
- BUG_ON(!RB_EMPTY_NODE(&last->rb_node));
+ BUG_ON(RB_EMPTY_NODE(&last->rb_node));
if (rbprev)
- arq_prev = rb_entry_arq(rbprev);
- else
- arq_prev = NULL;
+ prev = RQ_DATA(rb_entry_rq(rbprev));
if (rbnext)
- arq_next = rb_entry_arq(rbnext);
+ next = RQ_DATA(rb_entry_rq(rbnext));
else {
- arq_next = as_find_first_arq(ad, data_dir);
- if (arq_next == last)
- arq_next = NULL;
- }
+ const int data_dir = arq->is_sync;
- ret = as_choose_req(ad, arq_next, arq_prev);
+ rbnext = rb_first(&ad->sort_list[data_dir]);
+ if (rbnext && rbnext != &last->rb_node)
+ next = RQ_DATA(rb_entry_rq(rbnext));
+ }
- return ret;
+ return as_choose_req(ad, next, prev);
}
/*
@@ -982,7 +894,7 @@ static void as_remove_queued_request(req
ad->next_arq[data_dir] = as_find_next_arq(ad, arq);
list_del_init(&arq->fifo);
- as_del_arq_rb(ad, arq);
+ as_del_arq_rb(ad, rq);
}
/*
@@ -1039,7 +951,7 @@ static void as_move_to_dispatch(struct a
struct request *rq = arq->request;
const int data_dir = arq->is_sync;
- BUG_ON(RB_EMPTY_NODE(&arq->rb_node));
+ BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
as_antic_stop(ad);
ad->antic_status = ANTIC_OFF;
@@ -1064,8 +976,6 @@ static void as_move_to_dispatch(struct a
}
ad->ioc_finished = 0;
- ad->next_arq[data_dir] = as_find_next_arq(ad, arq);
-
/*
* take it off the sort and fifo list, add to dispatch queue
*/
@@ -1269,7 +1179,7 @@ static void as_add_request(request_queue
atomic_inc(&arq->io_context->aic->nr_queued);
}
- as_add_arq_rb(ad, arq);
+ as_add_arq_rb(ad, rq);
/*
* set expire time (only used for reads) and add to fifo list
@@ -1315,32 +1225,6 @@ static int as_queue_empty(request_queue_
&& list_empty(&ad->fifo_list[REQ_SYNC]);
}
-static struct request *as_former_request(request_queue_t *q,
- struct request *rq)
-{
- struct as_rq *arq = RQ_DATA(rq);
- struct rb_node *rbprev = rb_prev(&arq->rb_node);
- struct request *ret = NULL;
-
- if (rbprev)
- ret = rb_entry_arq(rbprev)->request;
-
- return ret;
-}
-
-static struct request *as_latter_request(request_queue_t *q,
- struct request *rq)
-{
- struct as_rq *arq = RQ_DATA(rq);
- struct rb_node *rbnext = rb_next(&arq->rb_node);
- struct request *ret = NULL;
-
- if (rbnext)
- ret = rb_entry_arq(rbnext)->request;
-
- return ret;
-}
-
static int
as_merge(request_queue_t *q, struct request **req, struct bio *bio)
{
@@ -1351,7 +1235,7 @@ as_merge(request_queue_t *q, struct requ
/*
* check for front merge
*/
- __rq = as_find_arq_rb(ad, rb_key, bio_data_dir(bio));
+ __rq = elv_rb_find(&ad->sort_list[bio_data_dir(bio)], rb_key);
if (__rq && elv_rq_merge_ok(__rq, bio)) {
*req = __rq;
return ELEVATOR_FRONT_MERGE;
@@ -1360,17 +1244,16 @@ as_merge(request_queue_t *q, struct requ
return ELEVATOR_NO_MERGE;
}
-static void as_merged_request(request_queue_t *q, struct request *req)
+static void as_merged_request(request_queue_t *q, struct request *req, int type)
{
struct as_data *ad = q->elevator->elevator_data;
- struct as_rq *arq = RQ_DATA(req);
/*
* if the merge was a front merge, we need to reposition request
*/
- if (rq_rb_key(req) != arq->rb_key) {
- as_del_arq_rb(ad, arq);
- as_add_arq_rb(ad, arq);
+ if (type == ELEVATOR_FRONT_MERGE) {
+ as_del_arq_rb(ad, req);
+ as_add_arq_rb(ad, req);
/*
* Note! At this stage of this and the next function, our next
* request may not be optimal - eg the request may have "grown"
@@ -1382,18 +1265,12 @@ static void as_merged_request(request_qu
static void as_merged_requests(request_queue_t *q, struct request *req,
struct request *next)
{
- struct as_data *ad = q->elevator->elevator_data;
struct as_rq *arq = RQ_DATA(req);
struct as_rq *anext = RQ_DATA(next);
BUG_ON(!arq);
BUG_ON(!anext);
- if (rq_rb_key(req) != arq->rb_key) {
- as_del_arq_rb(ad, arq);
- as_add_arq_rb(ad, arq);
- }
-
/*
* if anext expires before arq, assign its expire time to arq
* and move into anext position (anext will be deleted) in fifo
@@ -1468,7 +1345,6 @@ static int as_set_request(request_queue_
if (arq) {
memset(arq, 0, sizeof(*arq));
- RB_CLEAR_NODE(&arq->rb_node);
arq->request = rq;
arq->state = AS_RQ_PRESCHED;
arq->io_context = NULL;
@@ -1654,8 +1530,8 @@ static struct elevator_type iosched_as =
.elevator_deactivate_req_fn = as_deactivate_request,
.elevator_queue_empty_fn = as_queue_empty,
.elevator_completed_req_fn = as_completed_request,
- .elevator_former_req_fn = as_former_request,
- .elevator_latter_req_fn = as_latter_request,
+ .elevator_former_req_fn = elv_rb_former_request,
+ .elevator_latter_req_fn = elv_rb_latter_request,
.elevator_set_req_fn = as_set_request,
.elevator_put_req_fn = as_put_request,
.elevator_may_queue_fn = as_may_queue,
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 5/15 cfq-iosched: migrate to using the elevator rb functions
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (3 preceding siblings ...)
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
2006-07-13 12:46 ` [PATCH] 6/15 deadline-iosched: " Jens Axboe
` (9 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
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
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 6/15 deadline-iosched: migrate to using the elevator rb functions
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (4 preceding siblings ...)
2006-07-13 12:46 ` [PATCH] 5/15 cfq-iosched: " Jens Axboe
@ 2006-07-13 12:46 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 7/15 elevator: introduce a way to reuse rq for internal FIFO handling Jens Axboe
` (8 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
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
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 7/15 elevator: introduce a way to reuse rq for internal FIFO handling
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (5 preceding siblings ...)
2006-07-13 12:46 ` [PATCH] 6/15 deadline-iosched: " Jens Axboe
@ 2006-07-13 12:46 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 8/15 cfq-iosched: convert to using the FIFO elevator defines Jens Axboe
` (7 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
The io schedulers can use this instead of having to allocate space for
it themselves.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
include/linux/elevator.h | 12 ++++++++++++
1 files changed, 12 insertions(+), 0 deletions(-)
diff --git a/include/linux/elevator.h b/include/linux/elevator.h
index 95b2a04..0e7b1a7 100644
--- a/include/linux/elevator.h
+++ b/include/linux/elevator.h
@@ -166,4 +166,16 @@ enum {
#define rq_end_sector(rq) ((rq)->sector + (rq)->nr_sectors)
#define rb_entry_rq(node) rb_entry((node), struct request, rb_node)
+/*
+ * Hack to reuse the donelist list_head as the fifo time holder while
+ * the request is in the io scheduler. Saves an unsigned long in rq.
+ */
+#define rq_fifo_time(rq) ((unsigned long) (rq)->donelist.next)
+#define rq_set_fifo_time(rq,exp) ((rq)->donelist.next = (void *) (exp))
+#define rq_entry_fifo(ptr) list_entry((ptr), struct request, queuelist)
+#define rq_fifo_clear(rq) do { \
+ list_del_init(&(rq)->queuelist); \
+ INIT_LIST_HEAD(&(rq)->donelist); \
+ } while (0)
+
#endif
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 8/15 cfq-iosched: convert to using the FIFO elevator defines
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (6 preceding siblings ...)
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 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 9/15 as-iosched: reuse rq for fifo Jens Axboe
` (6 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/cfq-iosched.c | 3 +--
1 files changed, 1 insertions(+), 2 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 75efc82..3770c27 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -42,7 +42,6 @@ #define CFQ_QHASH_ENTRIES (1 << CFQ_QHAS
#define list_entry_qhash(entry) hlist_entry((entry), struct cfq_queue, cfq_hash)
#define list_entry_cfqq(ptr) list_entry((ptr), struct cfq_queue, cfq_list)
-#define list_entry_fifo(ptr) list_entry((ptr), struct request, queuelist)
#define RQ_DATA(rq) (rq)->elevator_private
@@ -840,7 +839,7 @@ static inline struct cfq_rq *cfq_check_f
if (!list_empty(&cfqq->fifo)) {
int fifo = cfq_cfqq_class_sync(cfqq);
- crq = RQ_DATA(list_entry_fifo(cfqq->fifo.next));
+ crq = RQ_DATA(rq_entry_fifo(cfqq->fifo.next));
rq = crq->request;
if (time_after(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo])) {
cfq_mark_cfqq_fifo_expire(cfqq);
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 9/15 as-iosched: reuse rq for fifo
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (7 preceding siblings ...)
2006-07-13 12:46 ` [PATCH] 8/15 cfq-iosched: convert to using the FIFO elevator defines Jens Axboe
@ 2006-07-13 12:46 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 10/15 as-iosched: remove arq->is_sync member Jens Axboe
` (5 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
Saves some space in arq.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/as-iosched.c | 34 ++++++++++++----------------------
1 files changed, 12 insertions(+), 22 deletions(-)
diff --git a/block/as-iosched.c b/block/as-iosched.c
index 413a944..13d8d91 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -131,8 +131,6 @@ struct as_data {
unsigned long antic_expire;
};
-#define list_entry_fifo(ptr) list_entry((ptr), struct as_rq, fifo)
-
/*
* per-request data.
*/
@@ -153,12 +151,6 @@ struct as_rq {
struct io_context *io_context; /* The submitting task */
- /*
- * expire fifo
- */
- struct list_head fifo;
- unsigned long expires;
-
unsigned int is_sync;
enum arq_state state;
};
@@ -893,7 +885,7 @@ static void as_remove_queued_request(req
if (ad->next_arq[data_dir] == arq)
ad->next_arq[data_dir] = as_find_next_arq(ad, arq);
- list_del_init(&arq->fifo);
+ rq_fifo_clear(rq);
as_del_arq_rb(ad, rq);
}
@@ -907,7 +899,7 @@ static void as_remove_queued_request(req
*/
static int as_fifo_expired(struct as_data *ad, int adir)
{
- struct as_rq *arq;
+ struct request *rq;
long delta_jif;
delta_jif = jiffies - ad->last_check_fifo[adir];
@@ -921,9 +913,9 @@ static int as_fifo_expired(struct as_dat
if (list_empty(&ad->fifo_list[adir]))
return 0;
- arq = list_entry_fifo(ad->fifo_list[adir].next);
+ rq = rq_entry_fifo(ad->fifo_list[adir].next);
- return time_after(jiffies, arq->expires);
+ return time_after(jiffies, rq_fifo_time(rq));
}
/*
@@ -1087,7 +1079,7 @@ static int as_dispatch_request(request_q
ad->changed_batch = 1;
}
ad->batch_data_dir = REQ_SYNC;
- arq = list_entry_fifo(ad->fifo_list[ad->batch_data_dir].next);
+ arq = RQ_DATA(rq_entry_fifo(ad->fifo_list[REQ_SYNC].next));
ad->last_check_fifo[ad->batch_data_dir] = jiffies;
goto dispatch_request;
}
@@ -1127,8 +1119,7 @@ dispatch_request:
if (as_fifo_expired(ad, ad->batch_data_dir)) {
fifo_expired:
- arq = list_entry_fifo(ad->fifo_list[ad->batch_data_dir].next);
- BUG_ON(arq == NULL);
+ arq = RQ_DATA(rq_entry_fifo(ad->fifo_list[ad->batch_data_dir].next));
}
if (ad->changed_batch) {
@@ -1184,8 +1175,8 @@ static void as_add_request(request_queue
/*
* set expire time (only used for reads) and add to fifo list
*/
- arq->expires = jiffies + ad->fifo_expire[data_dir];
- list_add_tail(&arq->fifo, &ad->fifo_list[data_dir]);
+ rq_set_fifo_time(rq, jiffies + ad->fifo_expire[data_dir]);
+ list_add_tail(&rq->queuelist, &ad->fifo_list[data_dir]);
as_update_arq(ad, arq); /* keep state machine up to date */
arq->state = AS_RQ_QUEUED;
@@ -1275,10 +1266,10 @@ static void as_merged_requests(request_q
* if anext expires before arq, assign its expire time to arq
* and move into anext position (anext will be deleted) in fifo
*/
- if (!list_empty(&arq->fifo) && !list_empty(&anext->fifo)) {
- if (time_before(anext->expires, arq->expires)) {
- list_move(&arq->fifo, &anext->fifo);
- arq->expires = anext->expires;
+ if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
+ if (time_before(rq_fifo_time(next), rq_fifo_time(req))) {
+ list_move(&req->queuelist, &next->queuelist);
+ rq_set_fifo_time(req, rq_fifo_time(next));
/*
* Don't copy here but swap, because when anext is
* removed below, it must contain the unused context
@@ -1348,7 +1339,6 @@ static int as_set_request(request_queue_
arq->request = rq;
arq->state = AS_RQ_PRESCHED;
arq->io_context = NULL;
- INIT_LIST_HEAD(&arq->fifo);
rq->elevator_private = arq;
return 0;
}
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 10/15 as-iosched: remove arq->is_sync member
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (8 preceding siblings ...)
2006-07-13 12:46 ` [PATCH] 9/15 as-iosched: reuse rq for fifo Jens Axboe
@ 2006-07-13 12:46 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 11/15 deadline-iosched: remove elevator private drq request type Jens Axboe
` (4 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
We can track this in struct request.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/as-iosched.c | 36 ++++++++++++++----------------------
include/linux/blkdev.h | 5 +++++
2 files changed, 19 insertions(+), 22 deletions(-)
diff --git a/block/as-iosched.c b/block/as-iosched.c
index 13d8d91..3fbb56d 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -151,7 +151,6 @@ struct as_rq {
struct io_context *io_context; /* The submitting task */
- unsigned int is_sync;
enum arq_state state;
};
@@ -241,7 +240,7 @@ static void as_put_io_context(struct as_
aic = arq->io_context->aic;
- if (arq->is_sync == REQ_SYNC && aic) {
+ if (rq_is_sync(arq->request) && aic) {
spin_lock(&aic->lock);
set_bit(AS_TASK_IORUNNING, &aic->state);
aic->last_end_request = jiffies;
@@ -254,14 +253,13 @@ static void as_put_io_context(struct as_
/*
* rb tree support functions
*/
-#define ARQ_RB_ROOT(ad, arq) (&(ad)->sort_list[(arq)->is_sync])
+#define RQ_RB_ROOT(ad, rq) (&(ad)->sort_list[rq_is_sync((rq))])
static void as_add_arq_rb(struct as_data *ad, struct request *rq)
{
- struct as_rq *arq = RQ_DATA(rq);
struct request *alias;
- while ((unlikely(alias = elv_rb_add(ARQ_RB_ROOT(ad, arq), rq)))) {
+ while ((unlikely(alias = elv_rb_add(RQ_RB_ROOT(ad, rq), rq)))) {
as_move_to_dispatch(ad, RQ_DATA(alias));
as_antic_stop(ad);
}
@@ -269,7 +267,7 @@ static void as_add_arq_rb(struct as_data
static inline void as_del_arq_rb(struct as_data *ad, struct request *rq)
{
- elv_rb_del(ARQ_RB_ROOT(ad, RQ_DATA(rq)), rq);
+ elv_rb_del(RQ_RB_ROOT(ad, rq), rq);
}
/*
@@ -300,13 +298,13 @@ as_choose_req(struct as_data *ad, struct
if (arq2 == NULL)
return arq1;
- data_dir = arq1->is_sync;
+ data_dir = rq_is_sync(arq1->request);
last = ad->last_sector[data_dir];
s1 = arq1->request->sector;
s2 = arq2->request->sector;
- BUG_ON(data_dir != arq2->is_sync);
+ BUG_ON(data_dir != rq_is_sync(arq2->request));
/*
* Strict one way elevator _except_ in the case where we allow
@@ -377,7 +375,7 @@ static struct as_rq *as_find_next_arq(st
if (rbnext)
next = RQ_DATA(rb_entry_rq(rbnext));
else {
- const int data_dir = arq->is_sync;
+ const int data_dir = rq_is_sync(last);
rbnext = rb_first(&ad->sort_list[data_dir]);
if (rbnext && rbnext != &last->rb_node)
@@ -538,8 +536,7 @@ static void as_update_seekdist(struct as
static void as_update_iohist(struct as_data *ad, struct as_io_context *aic,
struct request *rq)
{
- struct as_rq *arq = RQ_DATA(rq);
- int data_dir = arq->is_sync;
+ int data_dir = rq_is_sync(rq);
unsigned long thinktime = 0;
sector_t seek_dist;
@@ -674,7 +671,7 @@ static int as_can_break_anticipation(str
return 1;
}
- if (arq && arq->is_sync == REQ_SYNC && as_close_req(ad, aic, arq)) {
+ if (arq && rq_is_sync(arq->request) && as_close_req(ad, aic, arq)) {
/*
* Found a close request that is not one of ours.
*
@@ -758,7 +755,7 @@ static int as_can_anticipate(struct as_d
*/
static void as_update_arq(struct as_data *ad, struct as_rq *arq)
{
- const int data_dir = arq->is_sync;
+ const int data_dir = rq_is_sync(arq->request);
/* keep the next_arq cache up to date */
ad->next_arq[data_dir] = as_choose_req(ad, arq, ad->next_arq[data_dir]);
@@ -835,7 +832,7 @@ static void as_completed_request(request
* actually serviced. This should help devices with big TCQ windows
* and writeback caches
*/
- if (ad->new_batch && ad->batch_data_dir == arq->is_sync) {
+ if (ad->new_batch && ad->batch_data_dir == rq_is_sync(rq)) {
update_write_batch(ad);
ad->current_batch_expires = jiffies +
ad->batch_expire[REQ_SYNC];
@@ -868,7 +865,7 @@ out:
static void as_remove_queued_request(request_queue_t *q, struct request *rq)
{
struct as_rq *arq = RQ_DATA(rq);
- const int data_dir = arq->is_sync;
+ const int data_dir = rq_is_sync(rq);
struct as_data *ad = q->elevator->elevator_data;
WARN_ON(arq->state != AS_RQ_QUEUED);
@@ -941,7 +938,7 @@ static inline int as_batch_expired(struc
static void as_move_to_dispatch(struct as_data *ad, struct as_rq *arq)
{
struct request *rq = arq->request;
- const int data_dir = arq->is_sync;
+ const int data_dir = rq_is_sync(rq);
BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
@@ -1156,12 +1153,7 @@ static void as_add_request(request_queue
arq->state = AS_RQ_NEW;
- if (rq_data_dir(arq->request) == READ
- || (arq->request->flags & REQ_RW_SYNC))
- arq->is_sync = 1;
- else
- arq->is_sync = 0;
- data_dir = arq->is_sync;
+ data_dir = rq_is_sync(rq);
arq->io_context = as_get_io_context();
diff --git a/include/linux/blkdev.h b/include/linux/blkdev.h
index e296719..78808a0 100644
--- a/include/linux/blkdev.h
+++ b/include/linux/blkdev.h
@@ -513,6 +513,11 @@ #define list_entry_rq(ptr) list_entry((p
#define rq_data_dir(rq) ((rq)->flags & 1)
+/*
+ * We regard a request as sync, if it's a READ or a SYNC write.
+ */
+#define rq_is_sync(rq) (rq_data_dir((rq)) == READ || (rq)->flags & REQ_RW_SYNC)
+
static inline int blk_queue_full(struct request_queue *q, int rw)
{
if (rw == READ)
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 11/15 deadline-iosched: remove elevator private drq request type
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (9 preceding siblings ...)
2006-07-13 12:46 ` [PATCH] 10/15 as-iosched: remove arq->is_sync member Jens Axboe
@ 2006-07-13 12:46 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 12/15 cfq-iosched: remove the crq flag functions/variable Jens Axboe
` (3 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
A big win, we now save an allocation/free on each request! With the
previous rb/hash abstractions, we can just reuse queuelist/donelist
for the FIFO data and be done with it.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/deadline-iosched.c | 194 ++++++++++++----------------------------------
1 files changed, 52 insertions(+), 142 deletions(-)
diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index 8300ba1..3b3b441 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -37,7 +37,7 @@ struct deadline_data {
/*
* next in sort order. read, write or both are NULL
*/
- struct deadline_rq *next_drq[2];
+ struct request *next_rq[2];
unsigned int batching; /* number of sequential requests made */
sector_t last_sector; /* head position */
unsigned int starved; /* times reads have starved writes */
@@ -49,34 +49,14 @@ struct deadline_data {
int fifo_batch;
int writes_starved;
int front_merges;
-
- mempool_t *drq_pool;
};
-/*
- * pre-request data.
- */
-struct deadline_rq {
- struct request *request;
-
- /*
- * expire fifo
- */
- struct list_head fifo;
- unsigned long expires;
-};
-
-static void deadline_move_request(struct deadline_data *dd, struct deadline_rq *drq);
-
-static kmem_cache_t *drq_pool;
-
-#define RQ_DATA(rq) ((struct deadline_rq *) (rq)->elevator_private)
+static void deadline_move_request(struct deadline_data *, struct request *);
#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 request *rq)
+deadline_add_rq_rb(struct deadline_data *dd, struct request *rq)
{
struct rb_root *root = RQ_RB_ROOT(dd, rq);
struct request *__alias;
@@ -84,45 +64,43 @@ deadline_add_drq_rb(struct deadline_data
retry:
__alias = elv_rb_add(root, rq);
if (unlikely(__alias)) {
- deadline_move_request(dd, RQ_DATA(__alias));
+ deadline_move_request(dd, __alias);
goto retry;
}
}
static inline void
-deadline_del_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
+deadline_del_rq_rb(struct deadline_data *dd, struct request *rq)
{
- struct request *rq = drq->request;
const int data_dir = rq_data_dir(rq);
- if (dd->next_drq[data_dir] == drq) {
+ if (dd->next_rq[data_dir] == rq) {
struct rb_node *rbnext = rb_next(&rq->rb_node);
- dd->next_drq[data_dir] = NULL;
+ dd->next_rq[data_dir] = NULL;
if (rbnext)
- dd->next_drq[data_dir] = RQ_DATA(rb_entry_rq(rbnext));
+ dd->next_rq[data_dir] = rb_entry_rq(rbnext);
}
elv_rb_del(RQ_RB_ROOT(dd, rq), rq);
}
/*
- * add drq to rbtree and fifo
+ * add rq to rbtree and fifo
*/
static void
deadline_add_request(struct request_queue *q, struct request *rq)
{
struct deadline_data *dd = q->elevator->elevator_data;
- struct deadline_rq *drq = RQ_DATA(rq);
- const int data_dir = rq_data_dir(drq->request);
+ const int data_dir = rq_data_dir(rq);
- deadline_add_drq_rb(dd, rq);
+ deadline_add_rq_rb(dd, rq);
/*
* set expire time (only used for reads) and add to fifo list
*/
- drq->expires = jiffies + dd->fifo_expire[data_dir];
- list_add_tail(&drq->fifo, &dd->fifo_list[data_dir]);
+ rq_set_fifo_time(rq, jiffies + dd->fifo_expire[data_dir]);
+ list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);
}
/*
@@ -130,11 +108,10 @@ deadline_add_request(struct request_queu
*/
static void deadline_remove_request(request_queue_t *q, struct request *rq)
{
- struct deadline_rq *drq = RQ_DATA(rq);
struct deadline_data *dd = q->elevator->elevator_data;
- list_del_init(&drq->fifo);
- deadline_del_drq_rb(dd, drq);
+ rq_fifo_clear(rq);
+ deadline_del_rq_rb(dd, rq);
}
static int
@@ -177,7 +154,7 @@ static void deadline_merged_request(requ
*/
if (type == ELEVATOR_FRONT_MERGE) {
elv_rb_del(RQ_RB_ROOT(dd, req), req);
- deadline_add_drq_rb(dd, req);
+ deadline_add_rq_rb(dd, req);
}
}
@@ -185,20 +162,14 @@ static void
deadline_merged_requests(request_queue_t *q, struct request *req,
struct request *next)
{
- struct deadline_rq *drq = RQ_DATA(req);
- struct deadline_rq *dnext = RQ_DATA(next);
-
- BUG_ON(!drq);
- BUG_ON(!dnext);
-
/*
- * if dnext expires before drq, assign its expire time to drq
- * and move into dnext position (dnext will be deleted) in fifo
+ * if next expires before rq, assign its expire time to rq
+ * and move into next position (next will be deleted) in fifo
*/
- if (!list_empty(&drq->fifo) && !list_empty(&dnext->fifo)) {
- if (time_before(dnext->expires, drq->expires)) {
- list_move(&drq->fifo, &dnext->fifo);
- drq->expires = dnext->expires;
+ if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
+ if (time_before(rq_fifo_time(next), rq_fifo_time(req))) {
+ list_move(&req->queuelist, &next->queuelist);
+ rq_set_fifo_time(req, rq_fifo_time(next));
}
}
@@ -212,53 +183,50 @@ deadline_merged_requests(request_queue_t
* move request from sort list to dispatch queue.
*/
static inline void
-deadline_move_to_dispatch(struct deadline_data *dd, struct deadline_rq *drq)
+deadline_move_to_dispatch(struct deadline_data *dd, struct request *rq)
{
- request_queue_t *q = drq->request->q;
+ request_queue_t *q = rq->q;
- deadline_remove_request(q, drq->request);
- elv_dispatch_add_tail(q, drq->request);
+ deadline_remove_request(q, rq);
+ elv_dispatch_add_tail(q, rq);
}
/*
* move an entry to dispatch queue
*/
static void
-deadline_move_request(struct deadline_data *dd, struct deadline_rq *drq)
+deadline_move_request(struct deadline_data *dd, struct request *rq)
{
- 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;
+ dd->next_rq[READ] = NULL;
+ dd->next_rq[WRITE] = NULL;
if (rbnext)
- dd->next_drq[data_dir] = RQ_DATA(rb_entry_rq(rbnext));
+ dd->next_rq[data_dir] = rb_entry_rq(rbnext);
- dd->last_sector = drq->request->sector + drq->request->nr_sectors;
+ dd->last_sector = rq->sector + rq->nr_sectors;
/*
* take it off the sort and fifo list, move
* to dispatch queue
*/
- deadline_move_to_dispatch(dd, drq);
+ deadline_move_to_dispatch(dd, rq);
}
-#define list_entry_fifo(ptr) list_entry((ptr), struct deadline_rq, fifo)
-
/*
* deadline_check_fifo returns 0 if there are no expired reads on the fifo,
* 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
*/
static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
{
- struct deadline_rq *drq = list_entry_fifo(dd->fifo_list[ddir].next);
+ struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next);
/*
- * drq is expired!
+ * rq is expired!
*/
- if (time_after(jiffies, drq->expires))
+ if (time_after(jiffies, rq_fifo_time(rq)))
return 1;
return 0;
@@ -273,21 +241,21 @@ static int deadline_dispatch_requests(re
struct deadline_data *dd = q->elevator->elevator_data;
const int reads = !list_empty(&dd->fifo_list[READ]);
const int writes = !list_empty(&dd->fifo_list[WRITE]);
- struct deadline_rq *drq;
+ struct request *rq;
int data_dir;
/*
* batches are currently reads XOR writes
*/
- if (dd->next_drq[WRITE])
- drq = dd->next_drq[WRITE];
+ if (dd->next_rq[WRITE])
+ rq = dd->next_rq[WRITE];
else
- drq = dd->next_drq[READ];
+ rq = dd->next_rq[READ];
- if (drq) {
+ if (rq) {
/* we have a "next request" */
- if (dd->last_sector != drq->request->sector)
+ if (dd->last_sector != rq->sector)
/* end the batch on a non sequential request */
dd->batching += dd->fifo_batch;
@@ -336,34 +304,33 @@ dispatch_find_request:
if (deadline_check_fifo(dd, data_dir)) {
/* An expired request exists - satisfy it */
dd->batching = 0;
- drq = list_entry_fifo(dd->fifo_list[data_dir].next);
+ rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
- } else if (dd->next_drq[data_dir]) {
+ } else if (dd->next_rq[data_dir]) {
/*
* The last req was the same dir and we have a next request in
* sort order. No expired requests so continue on from here.
*/
- drq = dd->next_drq[data_dir];
+ rq = dd->next_rq[data_dir];
} else {
- struct rb_node *n;
-
+ struct rb_node *node;
/*
* 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;
- n = rb_first(&dd->sort_list[data_dir]);
- if (n)
- drq = RQ_DATA(rb_entry_rq(n));
+ node = rb_first(&dd->sort_list[data_dir]);
+ if (node)
+ rq = rb_entry_rq(node);
}
dispatch_request:
/*
- * drq is the selected appropriate request.
+ * rq is the selected appropriate request.
*/
dd->batching++;
- deadline_move_request(dd, drq);
+ deadline_move_request(dd, rq);
return 1;
}
@@ -383,33 +350,21 @@ static void deadline_exit_queue(elevator
BUG_ON(!list_empty(&dd->fifo_list[READ]));
BUG_ON(!list_empty(&dd->fifo_list[WRITE]));
- mempool_destroy(dd->drq_pool);
kfree(dd);
}
/*
- * initialize elevator private data (deadline_data), and alloc a drq for
- * each request on the free lists
+ * initialize elevator private data (deadline_data).
*/
static void *deadline_init_queue(request_queue_t *q, elevator_t *e)
{
struct deadline_data *dd;
- if (!drq_pool)
- return NULL;
-
dd = kmalloc_node(sizeof(*dd), GFP_KERNEL, q->node);
if (!dd)
return NULL;
memset(dd, 0, sizeof(*dd));
- dd->drq_pool = mempool_create_node(BLKDEV_MIN_RQ, mempool_alloc_slab,
- mempool_free_slab, drq_pool, q->node);
- if (!dd->drq_pool) {
- kfree(dd);
- return NULL;
- }
-
INIT_LIST_HEAD(&dd->fifo_list[READ]);
INIT_LIST_HEAD(&dd->fifo_list[WRITE]);
dd->sort_list[READ] = RB_ROOT;
@@ -422,36 +377,6 @@ static void *deadline_init_queue(request
return dd;
}
-static void deadline_put_request(request_queue_t *q, struct request *rq)
-{
- struct deadline_data *dd = q->elevator->elevator_data;
- struct deadline_rq *drq = RQ_DATA(rq);
-
- mempool_free(drq, dd->drq_pool);
- rq->elevator_private = NULL;
-}
-
-static int
-deadline_set_request(request_queue_t *q, struct request *rq, struct bio *bio,
- gfp_t gfp_mask)
-{
- struct deadline_data *dd = q->elevator->elevator_data;
- struct deadline_rq *drq;
-
- drq = mempool_alloc(dd->drq_pool, gfp_mask);
- if (drq) {
- memset(drq, 0, sizeof(*drq));
- drq->request = rq;
-
- INIT_LIST_HEAD(&drq->fifo);
-
- rq->elevator_private = drq;
- return 0;
- }
-
- return 1;
-}
-
/*
* sysfs parts below
*/
@@ -533,8 +458,6 @@ static struct elevator_type iosched_dead
.elevator_queue_empty_fn = deadline_queue_empty,
.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,
.elevator_exit_fn = deadline_exit_queue,
},
@@ -546,24 +469,11 @@ static struct elevator_type iosched_dead
static int __init deadline_init(void)
{
- int ret;
-
- drq_pool = kmem_cache_create("deadline_drq", sizeof(struct deadline_rq),
- 0, 0, NULL, NULL);
-
- if (!drq_pool)
- return -ENOMEM;
-
- ret = elv_register(&iosched_deadline);
- if (ret)
- kmem_cache_destroy(drq_pool);
-
- return ret;
+ return elv_register(&iosched_deadline);
}
static void __exit deadline_exit(void)
{
- kmem_cache_destroy(drq_pool);
elv_unregister(&iosched_deadline);
}
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 12/15 cfq-iosched: remove the crq flag functions/variable
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (10 preceding siblings ...)
2006-07-13 12:46 ` [PATCH] 11/15 deadline-iosched: remove elevator private drq request type Jens Axboe
@ 2006-07-13 12:46 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 13/15 Add one more pointer to struct request for IO scheduler usage Jens Axboe
` (2 subsequent siblings)
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
There's just one flag currently (SYNC), and that one can be grabbed from
the request.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/cfq-iosched.c | 58 ++++++++++++++-------------------------------------
1 files changed, 16 insertions(+), 42 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 3770c27..c97e387 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -182,8 +182,6 @@ struct cfq_rq {
struct cfq_queue *cfq_queue;
struct cfq_io_context *io_context;
-
- unsigned int crq_flags;
};
enum cfqq_state_flags {
@@ -221,27 +219,6 @@ CFQ_CFQQ_FNS(idle_window);
CFQ_CFQQ_FNS(prio_changed);
#undef CFQ_CFQQ_FNS
-enum cfq_rq_state_flags {
- CFQ_CRQ_FLAG_is_sync = 0,
-};
-
-#define CFQ_CRQ_FNS(name) \
-static inline void cfq_mark_crq_##name(struct cfq_rq *crq) \
-{ \
- crq->crq_flags |= (1 << CFQ_CRQ_FLAG_##name); \
-} \
-static inline void cfq_clear_crq_##name(struct cfq_rq *crq) \
-{ \
- crq->crq_flags &= ~(1 << CFQ_CRQ_FLAG_##name); \
-} \
-static inline int cfq_crq_##name(const struct cfq_rq *crq) \
-{ \
- return (crq->crq_flags & (1 << CFQ_CRQ_FLAG_##name)) != 0; \
-}
-
-CFQ_CRQ_FNS(is_sync);
-#undef CFQ_CRQ_FNS
-
static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned int, unsigned short);
static void cfq_dispatch_insert(request_queue_t *, struct cfq_rq *);
static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, unsigned int key, struct task_struct *tsk, gfp_t gfp_mask);
@@ -290,9 +267,9 @@ #define CFQ_RQ2_WRAP 0x02 /* request 2 w
if (crq2 == NULL)
return crq1;
- if (cfq_crq_is_sync(crq1) && !cfq_crq_is_sync(crq2))
+ if (rq_is_sync(crq1->request) && !rq_is_sync(crq2->request))
return crq1;
- else if (cfq_crq_is_sync(crq2) && !cfq_crq_is_sync(crq1))
+ else if (rq_is_sync(crq2->request) && !rq_is_sync(crq1->request))
return crq2;
s1 = crq1->request->sector;
@@ -477,7 +454,7 @@ static inline void cfq_del_crq_rb(struct
{
struct cfq_queue *cfqq = crq->cfq_queue;
struct cfq_data *cfqd = cfqq->cfqd;
- const int sync = cfq_crq_is_sync(crq);
+ const int sync = rq_is_sync(crq->request);
BUG_ON(!cfqq->queued[sync]);
cfqq->queued[sync]--;
@@ -495,7 +472,7 @@ static void cfq_add_crq_rb(struct cfq_rq
struct request *rq = crq->request;
struct request *__alias;
- cfqq->queued[cfq_crq_is_sync(crq)]++;
+ cfqq->queued[rq_is_sync(rq)]++;
/*
* looks a little odd, but the first insert might return an alias.
@@ -508,8 +485,10 @@ static void cfq_add_crq_rb(struct cfq_rq
static inline void
cfq_reposition_crq_rb(struct cfq_queue *cfqq, struct cfq_rq *crq)
{
- elv_rb_del(&cfqq->sort_list, crq->request);
- cfqq->queued[cfq_crq_is_sync(crq)]--;
+ struct request *rq = crq->request;
+
+ elv_rb_del(&cfqq->sort_list, rq);
+ cfqq->queued[rq_is_sync(rq)]--;
cfq_add_crq_rb(crq);
}
@@ -814,11 +793,11 @@ static void cfq_dispatch_insert(request_
{
struct cfq_data *cfqd = q->elevator->elevator_data;
struct cfq_queue *cfqq = crq->cfq_queue;
- struct request *rq;
+ struct request *rq = crq->request;
- cfq_remove_request(crq->request);
- cfqq->on_dispatch[cfq_crq_is_sync(crq)]++;
- elv_dispatch_sort(q, crq->request);
+ cfq_remove_request(rq);
+ cfqq->on_dispatch[rq_is_sync(rq)]++;
+ elv_dispatch_sort(q, rq);
rq = list_entry(q->queue_head.prev, struct request, queuelist);
cfqd->last_sector = rq->sector + rq->nr_sectors;
@@ -1585,7 +1564,7 @@ cfq_should_preempt(struct cfq_data *cfqd
*/
if (new_cfqq->slice_left < cfqd->cfq_slice_idle)
return 0;
- if (cfq_crq_is_sync(crq) && !cfq_cfqq_sync(cfqq))
+ if (rq_is_sync(crq->request) && !cfq_cfqq_sync(cfqq))
return 1;
return 0;
@@ -1634,7 +1613,7 @@ 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
+ * 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);
@@ -1643,7 +1622,7 @@ cfq_crq_enqueued(struct cfq_data *cfqd,
* we never wait for an async request and we don't allow preemption
* of an async request. so just return early
*/
- if (!cfq_crq_is_sync(crq)) {
+ if (!rq_is_sync(crq->request)) {
/*
* sync process issued an async request, if it's waiting
* then expire it and kick rq handling.
@@ -1709,7 +1688,7 @@ static void cfq_completed_request(reques
struct cfq_rq *crq = RQ_DATA(rq);
struct cfq_queue *cfqq = crq->cfq_queue;
struct cfq_data *cfqd = cfqq->cfqd;
- const int sync = cfq_crq_is_sync(crq);
+ const int sync = rq_is_sync(rq);
unsigned long now;
now = jiffies;
@@ -1905,11 +1884,6 @@ cfq_set_request(request_queue_t *q, stru
crq->cfq_queue = cfqq;
crq->io_context = cic;
- if (is_sync)
- cfq_mark_crq_is_sync(crq);
- else
- cfq_clear_crq_is_sync(crq);
-
rq->elevator_private = crq;
return 0;
}
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 13/15 Add one more pointer to struct request for IO scheduler usage
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (11 preceding siblings ...)
2006-07-13 12:46 ` [PATCH] 12/15 cfq-iosched: remove the crq flag functions/variable Jens Axboe
@ 2006-07-13 12:46 ` 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
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
Then we have enough room in the request to get rid of the dynamic
allocations in CFQ/AS.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/ll_rw_blk.c | 2 ++
include/linux/blkdev.h | 6 ++++++
2 files changed, 8 insertions(+), 0 deletions(-)
diff --git a/block/ll_rw_blk.c b/block/ll_rw_blk.c
index 08c1615..4018254 100644
--- a/block/ll_rw_blk.c
+++ b/block/ll_rw_blk.c
@@ -451,6 +451,7 @@ static void queue_flush(request_queue_t
rq_init(q, rq);
rq->flags = REQ_HARDBARRIER;
rq->elevator_private = NULL;
+ rq->elevator_private2 = NULL;
rq->rq_disk = q->bar_rq.rq_disk;
rq->rl = NULL;
rq->end_io = end_io;
@@ -477,6 +478,7 @@ static inline struct request *start_orde
rq->flags = bio_data_dir(q->orig_bar_rq->bio);
rq->flags |= q->ordered & QUEUE_ORDERED_FUA ? REQ_FUA : 0;
rq->elevator_private = NULL;
+ rq->elevator_private2 = NULL;
rq->rl = NULL;
init_request_from_bio(rq, q->orig_bar_rq->bio);
rq->end_io = bar_end_io;
diff --git a/include/linux/blkdev.h b/include/linux/blkdev.h
index 78808a0..ba4378f 100644
--- a/include/linux/blkdev.h
+++ b/include/linux/blkdev.h
@@ -151,7 +151,13 @@ struct request {
struct hlist_node hash; /* merge hash */
struct rb_node rb_node; /* sort/lookup */
+ /*
+ * two pointers are available for the IO schedulers, if they need
+ * more they have to dynamically allocate it.
+ */
void *elevator_private;
+ void *elevator_private2;
+
void *completion_data;
int rq_status; /* should split this into a few status bits */
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 14/15 cfq-iosched: kill crq
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (12 preceding siblings ...)
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 ` Jens Axboe
2006-07-13 12:46 ` [PATCH] 15/15 as-iosched: kill arq Jens Axboe
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
Get rid of the cfq_rq request type. With the added elevator_private2, we
have enough room in struct request to get rid of any crq allocation/free
for each request.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/cfq-iosched.c | 239 ++++++++++++++++++++-------------------------------
1 files changed, 95 insertions(+), 144 deletions(-)
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index c97e387..d0e49da 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -43,9 +43,9 @@ #define list_entry_qhash(entry) hlist_en
#define list_entry_cfqq(ptr) list_entry((ptr), struct cfq_queue, cfq_list)
-#define RQ_DATA(rq) (rq)->elevator_private
+#define RQ_CIC(rq) ((struct cfq_io_context*)(rq)->elevator_private)
+#define RQ_CFQQ(rq) ((rq)->elevator_private2)
-static kmem_cache_t *crq_pool;
static kmem_cache_t *cfq_pool;
static kmem_cache_t *cfq_ioc_pool;
@@ -95,8 +95,6 @@ struct cfq_data {
*/
struct hlist_head *cfq_hash;
- mempool_t *crq_pool;
-
int rq_in_driver;
int hw_tag;
@@ -153,7 +151,7 @@ struct cfq_queue {
/* sorted list of pending requests */
struct rb_root sort_list;
/* if fifo isn't expired, next request to serve */
- struct cfq_rq *next_crq;
+ struct request *next_rq;
/* requests queued in sort_list */
int queued[2];
/* currently allocated requests */
@@ -177,13 +175,6 @@ struct cfq_queue {
unsigned int flags;
};
-struct cfq_rq {
- struct request *request;
-
- struct cfq_queue *cfq_queue;
- struct cfq_io_context *io_context;
-};
-
enum cfqq_state_flags {
CFQ_CFQQ_FLAG_on_rr = 0,
CFQ_CFQQ_FLAG_wait_request,
@@ -220,7 +211,7 @@ CFQ_CFQQ_FNS(prio_changed);
#undef CFQ_CFQQ_FNS
static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned int, unsigned short);
-static void cfq_dispatch_insert(request_queue_t *, struct cfq_rq *);
+static void cfq_dispatch_insert(request_queue_t *, struct request *);
static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, unsigned int key, struct task_struct *tsk, gfp_t gfp_mask);
/*
@@ -249,12 +240,12 @@ static inline pid_t cfq_queue_pid(struct
}
/*
- * Lifted from AS - choose which of crq1 and crq2 that is best served now.
+ * Lifted from AS - choose which of rq1 and rq2 that is best served now.
* We choose the request that is closest to the head right now. Distance
* behind the head is penalized and only allowed to a certain extent.
*/
-static struct cfq_rq *
-cfq_choose_req(struct cfq_data *cfqd, struct cfq_rq *crq1, struct cfq_rq *crq2)
+static struct request *
+cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2)
{
sector_t last, s1, s2, d1 = 0, d2 = 0;
unsigned long back_max;
@@ -262,18 +253,18 @@ #define CFQ_RQ1_WRAP 0x01 /* request 1 w
#define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */
unsigned wrap = 0; /* bit mask: requests behind the disk head? */
- if (crq1 == NULL || crq1 == crq2)
- return crq2;
- if (crq2 == NULL)
- return crq1;
+ if (rq1 == NULL || rq1 == rq2)
+ return rq2;
+ if (rq2 == NULL)
+ return rq1;
- if (rq_is_sync(crq1->request) && !rq_is_sync(crq2->request))
- return crq1;
- else if (rq_is_sync(crq2->request) && !rq_is_sync(crq1->request))
- return crq2;
+ if (rq_is_sync(rq1) && !rq_is_sync(rq2))
+ return rq1;
+ else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
+ return rq2;
- s1 = crq1->request->sector;
- s2 = crq2->request->sector;
+ s1 = rq1->sector;
+ s2 = rq2->sector;
last = cfqd->last_sector;
@@ -308,23 +299,23 @@ #define CFQ_RQ2_WRAP 0x02 /* request 2 w
* check two variables for all permutations: --> faster!
*/
switch (wrap) {
- case 0: /* common case for CFQ: crq1 and crq2 not wrapped */
+ case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
if (d1 < d2)
- return crq1;
+ return rq1;
else if (d2 < d1)
- return crq2;
+ return rq2;
else {
if (s1 >= s2)
- return crq1;
+ return rq1;
else
- return crq2;
+ return rq2;
}
case CFQ_RQ2_WRAP:
- return crq1;
+ return rq1;
case CFQ_RQ1_WRAP:
- return crq2;
- case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both crqs wrapped */
+ return rq2;
+ case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
default:
/*
* Since both rqs are wrapped,
@@ -333,35 +324,34 @@ #define CFQ_RQ2_WRAP 0x02 /* request 2 w
* since back seek takes more time than forward.
*/
if (s1 <= s2)
- return crq1;
+ return rq1;
else
- return crq2;
+ return rq2;
}
}
/*
* would be nice to take fifo expire time into account as well
*/
-static struct cfq_rq *
-cfq_find_next_crq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
- struct cfq_rq *last_crq)
+static struct request *
+cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
+ struct request *last)
{
- 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;
+ struct request *next = NULL, *prev = NULL;
BUG_ON(RB_EMPTY_NODE(&last->rb_node));
if (rbprev)
- prev = RQ_DATA(rb_entry_rq(rbprev));
+ prev = rb_entry_rq(rbprev);
if (rbnext)
- next = RQ_DATA(rb_entry_rq(rbnext));
+ next = rb_entry_rq(rbnext);
else {
rbnext = rb_first(&cfqq->sort_list);
if (rbnext && rbnext != &last->rb_node)
- next = RQ_DATA(rb_entry_rq(rbnext));
+ next = rb_entry_rq(rbnext);
}
return cfq_choose_req(cfqd, next, prev);
@@ -450,26 +440,25 @@ cfq_del_cfqq_rr(struct cfq_data *cfqd, s
/*
* rb tree support functions
*/
-static inline void cfq_del_crq_rb(struct cfq_rq *crq)
+static inline void cfq_del_rq_rb(struct request *rq)
{
- struct cfq_queue *cfqq = crq->cfq_queue;
+ struct cfq_queue *cfqq = RQ_CFQQ(rq);
struct cfq_data *cfqd = cfqq->cfqd;
- const int sync = rq_is_sync(crq->request);
+ const int sync = rq_is_sync(rq);
BUG_ON(!cfqq->queued[sync]);
cfqq->queued[sync]--;
- elv_rb_del(&cfqq->sort_list, crq->request);
+ elv_rb_del(&cfqq->sort_list, rq);
if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
cfq_del_cfqq_rr(cfqd, cfqq);
}
-static void cfq_add_crq_rb(struct cfq_rq *crq)
+static void cfq_add_rq_rb(struct request *rq)
{
- struct cfq_queue *cfqq = crq->cfq_queue;
+ struct cfq_queue *cfqq = RQ_CFQQ(rq);
struct cfq_data *cfqd = cfqq->cfqd;
- struct request *rq = crq->request;
struct request *__alias;
cfqq->queued[rq_is_sync(rq)]++;
@@ -479,17 +468,15 @@ static void cfq_add_crq_rb(struct cfq_rq
* if that happens, put the alias on the dispatch list
*/
while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
- cfq_dispatch_insert(cfqd->queue, RQ_DATA(__alias));
+ cfq_dispatch_insert(cfqd->queue, __alias);
}
static inline void
-cfq_reposition_crq_rb(struct cfq_queue *cfqq, struct cfq_rq *crq)
+cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
{
- struct request *rq = crq->request;
-
elv_rb_del(&cfqq->sort_list, rq);
cfqq->queued[rq_is_sync(rq)]--;
- cfq_add_crq_rb(crq);
+ cfq_add_rq_rb(rq);
}
static struct request *
@@ -533,14 +520,13 @@ 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;
+ struct cfq_queue *cfqq = RQ_CFQQ(rq);
- if (cfqq->next_crq == crq)
- cfqq->next_crq = cfq_find_next_crq(cfqq->cfqd, cfqq, crq);
+ if (cfqq->next_rq == rq)
+ cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
list_del_init(&rq->queuelist);
- cfq_del_crq_rb(crq);
+ cfq_del_rq_rb(rq);
}
static int
@@ -561,12 +547,10 @@ cfq_merge(request_queue_t *q, struct req
static void cfq_merged_request(request_queue_t *q, struct request *req,
int type)
{
- struct cfq_rq *crq = RQ_DATA(req);
-
if (type == ELEVATOR_FRONT_MERGE) {
- struct cfq_queue *cfqq = crq->cfq_queue;
+ struct cfq_queue *cfqq = RQ_CFQQ(req);
- cfq_reposition_crq_rb(cfqq, crq);
+ cfq_reposition_rq_rb(cfqq, req);
}
}
@@ -789,11 +773,10 @@ static int cfq_arm_slice_timer(struct cf
return 1;
}
-static void cfq_dispatch_insert(request_queue_t *q, struct cfq_rq *crq)
+static void cfq_dispatch_insert(request_queue_t *q, struct request *rq)
{
struct cfq_data *cfqd = q->elevator->elevator_data;
- struct cfq_queue *cfqq = crq->cfq_queue;
- struct request *rq = crq->request;
+ struct cfq_queue *cfqq = RQ_CFQQ(rq);
cfq_remove_request(rq);
cfqq->on_dispatch[rq_is_sync(rq)]++;
@@ -806,11 +789,10 @@ static void cfq_dispatch_insert(request_
/*
* return expired entry, or NULL to just start from scratch in rbtree
*/
-static inline struct cfq_rq *cfq_check_fifo(struct cfq_queue *cfqq)
+static inline struct request *cfq_check_fifo(struct cfq_queue *cfqq)
{
struct cfq_data *cfqd = cfqq->cfqd;
struct request *rq;
- struct cfq_rq *crq;
if (cfq_cfqq_fifo_expire(cfqq))
return NULL;
@@ -818,11 +800,10 @@ static inline struct cfq_rq *cfq_check_f
if (!list_empty(&cfqq->fifo)) {
int fifo = cfq_cfqq_class_sync(cfqq);
- crq = RQ_DATA(rq_entry_fifo(cfqq->fifo.next));
- rq = crq->request;
+ rq = rq_entry_fifo(cfqq->fifo.next);
if (time_after(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo])) {
cfq_mark_cfqq_fifo_expire(cfqq);
- return crq;
+ return rq;
}
}
@@ -909,25 +890,25 @@ __cfq_dispatch_requests(struct cfq_data
BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
do {
- struct cfq_rq *crq;
+ struct request *rq;
/*
* follow expired path, else get first next available
*/
- if ((crq = cfq_check_fifo(cfqq)) == NULL)
- crq = cfqq->next_crq;
+ if ((rq = cfq_check_fifo(cfqq)) == NULL)
+ rq = cfqq->next_rq;
/*
* finally, insert request into driver dispatch list
*/
- cfq_dispatch_insert(cfqd->queue, crq);
+ cfq_dispatch_insert(cfqd->queue, rq);
cfqd->dispatch_slice++;
dispatched++;
if (!cfqd->active_cic) {
- atomic_inc(&crq->io_context->ioc->refcount);
- cfqd->active_cic = crq->io_context;
+ atomic_inc(&RQ_CIC(rq)->ioc->refcount);
+ cfqd->active_cic = RQ_CIC(rq);
}
if (RB_EMPTY_ROOT(&cfqq->sort_list))
@@ -958,13 +939,12 @@ static int
cfq_forced_dispatch_cfqqs(struct list_head *list)
{
struct cfq_queue *cfqq, *next;
- struct cfq_rq *crq;
int dispatched;
dispatched = 0;
list_for_each_entry_safe(cfqq, next, list, cfq_list) {
- while ((crq = cfqq->next_crq)) {
- cfq_dispatch_insert(cfqq->cfqd->queue, crq);
+ while (cfqq->next_rq) {
+ cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
dispatched++;
}
BUG_ON(!list_empty(&cfqq->fifo));
@@ -1040,8 +1020,8 @@ cfq_dispatch_requests(request_queue_t *q
}
/*
- * task holds one reference to the queue, dropped when task exits. each crq
- * in-flight on this queue also holds a reference, dropped when crq is freed.
+ * task holds one reference to the queue, dropped when task exits. each rq
+ * in-flight on this queue also holds a reference, dropped when rq is freed.
*
* queue lock must be held here.
*/
@@ -1486,15 +1466,15 @@ #endif
static void
cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_io_context *cic,
- struct cfq_rq *crq)
+ struct request *rq)
{
sector_t sdist;
u64 total;
- if (cic->last_request_pos < crq->request->sector)
- sdist = crq->request->sector - cic->last_request_pos;
+ if (cic->last_request_pos < rq->sector)
+ sdist = rq->sector - cic->last_request_pos;
else
- sdist = cic->last_request_pos - crq->request->sector;
+ sdist = cic->last_request_pos - rq->sector;
/*
* Don't allow the seek distance to get too large from the
@@ -1545,7 +1525,7 @@ cfq_update_idle_window(struct cfq_data *
*/
static int
cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
- struct cfq_rq *crq)
+ struct request *rq)
{
struct cfq_queue *cfqq = cfqd->active_queue;
@@ -1564,7 +1544,7 @@ cfq_should_preempt(struct cfq_data *cfqd
*/
if (new_cfqq->slice_left < cfqd->cfq_slice_idle)
return 0;
- if (rq_is_sync(crq->request) && !cfq_cfqq_sync(cfqq))
+ if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
return 1;
return 0;
@@ -1603,26 +1583,26 @@ static void cfq_start_queueing(struct cf
}
/*
- * Called when a new fs request (crq) is added (to cfqq). Check if there's
+ * Called when a new fs request (rq) is added (to cfqq). Check if there's
* something we should do about it
*/
static void
-cfq_crq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
- struct cfq_rq *crq)
+cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
+ struct request *rq)
{
- struct cfq_io_context *cic = crq->io_context;
+ struct cfq_io_context *cic = RQ_CIC(rq);
/*
* 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);
+ cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq);
+ BUG_ON(!cfqq->next_rq);
/*
* we never wait for an async request and we don't allow preemption
* of an async request. so just return early
*/
- if (!rq_is_sync(crq->request)) {
+ if (!rq_is_sync(rq)) {
/*
* sync process issued an async request, if it's waiting
* then expire it and kick rq handling.
@@ -1636,11 +1616,11 @@ cfq_crq_enqueued(struct cfq_data *cfqd,
}
cfq_update_io_thinktime(cfqd, cic);
- cfq_update_io_seektime(cfqd, cic, crq);
+ cfq_update_io_seektime(cfqd, cic, rq);
cfq_update_idle_window(cfqd, cfqq, cic);
cic->last_queue = jiffies;
- cic->last_request_pos = crq->request->sector + crq->request->nr_sectors;
+ cic->last_request_pos = rq->sector + rq->nr_sectors;
if (cfqq == cfqd->active_queue) {
/*
@@ -1653,7 +1633,7 @@ cfq_crq_enqueued(struct cfq_data *cfqd,
del_timer(&cfqd->idle_slice_timer);
cfq_start_queueing(cfqd, cfqq);
}
- } else if (cfq_should_preempt(cfqd, cfqq, crq)) {
+ } else if (cfq_should_preempt(cfqd, cfqq, rq)) {
/*
* not the active queue - expire current slice if it is
* idle and has expired it's mean thinktime or this new queue
@@ -1668,25 +1648,23 @@ cfq_crq_enqueued(struct cfq_data *cfqd,
static void cfq_insert_request(request_queue_t *q, struct request *rq)
{
struct cfq_data *cfqd = q->elevator->elevator_data;
- struct cfq_rq *crq = RQ_DATA(rq);
- struct cfq_queue *cfqq = crq->cfq_queue;
+ struct cfq_queue *cfqq = RQ_CFQQ(rq);
cfq_init_prio_data(cfqq);
- cfq_add_crq_rb(crq);
+ cfq_add_rq_rb(rq);
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);
+ cfq_rq_enqueued(cfqd, cfqq, rq);
}
static void cfq_completed_request(request_queue_t *q, struct request *rq)
{
- struct cfq_rq *crq = RQ_DATA(rq);
- struct cfq_queue *cfqq = crq->cfq_queue;
+ struct cfq_queue *cfqq = RQ_CFQQ(rq);
struct cfq_data *cfqd = cfqq->cfqd;
const int sync = rq_is_sync(rq);
unsigned long now;
@@ -1709,7 +1687,7 @@ static void cfq_completed_request(reques
}
if (sync)
- crq->io_context->last_end_request = now;
+ RQ_CIC(rq)->last_end_request = now;
/*
* If this is the active queue, check if it needs to be expired,
@@ -1817,20 +1795,18 @@ static void cfq_check_waiters(request_qu
*/
static void cfq_put_request(request_queue_t *q, struct request *rq)
{
- struct cfq_data *cfqd = q->elevator->elevator_data;
- struct cfq_rq *crq = RQ_DATA(rq);
+ struct cfq_queue *cfqq = RQ_CFQQ(rq);
- if (crq) {
- struct cfq_queue *cfqq = crq->cfq_queue;
+ if (cfqq) {
const int rw = rq_data_dir(rq);
BUG_ON(!cfqq->allocated[rw]);
cfqq->allocated[rw]--;
- put_io_context(crq->io_context->ioc);
+ put_io_context(RQ_CIC(rq)->ioc);
- mempool_free(crq, cfqd->crq_pool);
rq->elevator_private = NULL;
+ rq->elevator_private2 = NULL;
cfq_check_waiters(q, cfqq);
cfq_put_queue(cfqq);
@@ -1850,7 +1826,6 @@ cfq_set_request(request_queue_t *q, stru
const int rw = rq_data_dir(rq);
pid_t key = cfq_queue_pid(tsk, rw);
struct cfq_queue *cfqq;
- struct cfq_rq *crq;
unsigned long flags;
int is_sync = key != CFQ_KEY_ASYNC;
@@ -1876,23 +1851,13 @@ cfq_set_request(request_queue_t *q, stru
cfq_clear_cfqq_must_alloc(cfqq);
cfqd->rq_starved = 0;
atomic_inc(&cfqq->ref);
- spin_unlock_irqrestore(q->queue_lock, flags);
- crq = mempool_alloc(cfqd->crq_pool, gfp_mask);
- if (crq) {
- crq->request = rq;
- crq->cfq_queue = cfqq;
- crq->io_context = cic;
+ spin_unlock_irqrestore(q->queue_lock, flags);
- rq->elevator_private = crq;
- return 0;
- }
+ rq->elevator_private = cic;
+ rq->elevator_private2 = cfqq;
+ return 0;
- spin_lock_irqsave(q->queue_lock, flags);
- cfqq->allocated[rw]--;
- if (!(cfqq->allocated[0] + cfqq->allocated[1]))
- cfq_mark_cfqq_must_alloc(cfqq);
- cfq_put_queue(cfqq);
queue_fail:
if (cic)
put_io_context(cic->ioc);
@@ -2040,7 +2005,6 @@ static void cfq_exit_queue(elevator_t *e
cfq_shutdown_timer_wq(cfqd);
- mempool_destroy(cfqd->crq_pool);
kfree(cfqd->cfq_hash);
kfree(cfqd);
}
@@ -2067,11 +2031,7 @@ static void *cfq_init_queue(request_queu
cfqd->cfq_hash = kmalloc(sizeof(struct hlist_head) * CFQ_QHASH_ENTRIES, GFP_KERNEL);
if (!cfqd->cfq_hash)
- goto out_crqhash;
-
- cfqd->crq_pool = mempool_create_slab_pool(BLKDEV_MIN_RQ, crq_pool);
- if (!cfqd->crq_pool)
- goto out_crqpool;
+ goto out_free;
for (i = 0; i < CFQ_QHASH_ENTRIES; i++)
INIT_HLIST_HEAD(&cfqd->cfq_hash[i]);
@@ -2100,17 +2060,13 @@ static void *cfq_init_queue(request_queu
cfqd->cfq_slice_idle = cfq_slice_idle;
return cfqd;
-out_crqpool:
- kfree(cfqd->cfq_hash);
-out_crqhash:
+out_free:
kfree(cfqd);
return NULL;
}
static void cfq_slab_kill(void)
{
- if (crq_pool)
- kmem_cache_destroy(crq_pool);
if (cfq_pool)
kmem_cache_destroy(cfq_pool);
if (cfq_ioc_pool)
@@ -2119,11 +2075,6 @@ static void cfq_slab_kill(void)
static int __init cfq_slab_setup(void)
{
- crq_pool = kmem_cache_create("crq_pool", sizeof(struct cfq_rq), 0, 0,
- NULL, NULL);
- if (!crq_pool)
- goto fail;
-
cfq_pool = kmem_cache_create("cfq_pool", sizeof(struct cfq_queue), 0, 0,
NULL, NULL);
if (!cfq_pool)
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread* [PATCH] 15/15 as-iosched: kill arq
2006-07-13 12:46 [PATCHSET] 0/15 IO scheduler improvements Jens Axboe
` (13 preceding siblings ...)
2006-07-13 12:46 ` [PATCH] 14/15 cfq-iosched: kill crq Jens Axboe
@ 2006-07-13 12:46 ` Jens Axboe
14 siblings, 0 replies; 16+ messages in thread
From: Jens Axboe @ 2006-07-13 12:46 UTC (permalink / raw)
To: linux-kernel; +Cc: Jens Axboe
Get rid of the as_rq request type. With the added elevator_private2, we
have enough room in struct request to get rid of any arq allocation/free
for each request.
Signed-off-by: Jens Axboe <axboe@suse.de>
---
block/as-iosched.c | 311 ++++++++++++++++++++--------------------------------
1 files changed, 117 insertions(+), 194 deletions(-)
diff --git a/block/as-iosched.c b/block/as-iosched.c
index 3fbb56d..5083f6a 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -92,7 +92,7 @@ struct as_data {
struct rb_root sort_list[2];
struct list_head fifo_list[2];
- struct as_rq *next_arq[2]; /* next in sort order */
+ struct request *next_rq[2]; /* next in sort order */
sector_t last_sector[2]; /* last REQ_SYNC & REQ_ASYNC sectors */
unsigned long exit_prob; /* probability a task will exit while
@@ -113,7 +113,6 @@ struct as_data {
int write_batch_count; /* max # of reqs in a write batch */
int current_write_count; /* how many requests left this batch */
int write_batch_idled; /* has the write batch gone idle? */
- mempool_t *arq_pool;
enum anticipation_status antic_status;
unsigned long antic_start; /* jiffies: when it started */
@@ -146,22 +145,14 @@ enum arq_state {
AS_RQ_POSTSCHED, /* when they shouldn't be */
};
-struct as_rq {
- struct request *request;
-
- struct io_context *io_context; /* The submitting task */
-
- enum arq_state state;
-};
-
-#define RQ_DATA(rq) ((struct as_rq *) (rq)->elevator_private)
-
-static kmem_cache_t *arq_pool;
+#define RQ_IOC(rq) ((struct io_context *) (rq)->elevator_private)
+#define RQ_STATE(rq) ((enum arq_state)(rq)->elevator_private2)
+#define RQ_SET_STATE(rq, state) ((rq)->elevator_private2 = (void *) state)
static atomic_t ioc_count = ATOMIC_INIT(0);
static struct completion *ioc_gone;
-static void as_move_to_dispatch(struct as_data *ad, struct as_rq *arq);
+static void as_move_to_dispatch(struct as_data *ad, struct request *rq);
static void as_antic_stop(struct as_data *ad);
/*
@@ -231,23 +222,23 @@ static struct io_context *as_get_io_cont
return ioc;
}
-static void as_put_io_context(struct as_rq *arq)
+static void as_put_io_context(struct request *rq)
{
struct as_io_context *aic;
- if (unlikely(!arq->io_context))
+ if (unlikely(!RQ_IOC(rq)))
return;
- aic = arq->io_context->aic;
+ aic = RQ_IOC(rq)->aic;
- if (rq_is_sync(arq->request) && aic) {
+ if (rq_is_sync(rq) && aic) {
spin_lock(&aic->lock);
set_bit(AS_TASK_IORUNNING, &aic->state);
aic->last_end_request = jiffies;
spin_unlock(&aic->lock);
}
- put_io_context(arq->io_context);
+ put_io_context(RQ_IOC(rq));
}
/*
@@ -255,17 +246,17 @@ static void as_put_io_context(struct as_
*/
#define RQ_RB_ROOT(ad, rq) (&(ad)->sort_list[rq_is_sync((rq))])
-static void as_add_arq_rb(struct as_data *ad, struct request *rq)
+static void as_add_rq_rb(struct as_data *ad, struct request *rq)
{
struct request *alias;
while ((unlikely(alias = elv_rb_add(RQ_RB_ROOT(ad, rq), rq)))) {
- as_move_to_dispatch(ad, RQ_DATA(alias));
+ as_move_to_dispatch(ad, alias);
as_antic_stop(ad);
}
}
-static inline void as_del_arq_rb(struct as_data *ad, struct request *rq)
+static inline void as_del_rq_rb(struct as_data *ad, struct request *rq)
{
elv_rb_del(RQ_RB_ROOT(ad, rq), rq);
}
@@ -285,26 +276,26 @@ #define BACK_PENALTY 2
* as_choose_req selects the preferred one of two requests of the same data_dir
* ignoring time - eg. timeouts, which is the job of as_dispatch_request
*/
-static struct as_rq *
-as_choose_req(struct as_data *ad, struct as_rq *arq1, struct as_rq *arq2)
+static struct request *
+as_choose_req(struct as_data *ad, struct request *rq1, struct request *rq2)
{
int data_dir;
sector_t last, s1, s2, d1, d2;
int r1_wrap=0, r2_wrap=0; /* requests are behind the disk head */
const sector_t maxback = MAXBACK;
- if (arq1 == NULL || arq1 == arq2)
- return arq2;
- if (arq2 == NULL)
- return arq1;
+ if (rq1 == NULL || rq1 == rq2)
+ return rq2;
+ if (rq2 == NULL)
+ return rq1;
- data_dir = rq_is_sync(arq1->request);
+ data_dir = rq_is_sync(rq1);
last = ad->last_sector[data_dir];
- s1 = arq1->request->sector;
- s2 = arq2->request->sector;
+ s1 = rq1->sector;
+ s2 = rq2->sector;
- BUG_ON(data_dir != rq_is_sync(arq2->request));
+ BUG_ON(data_dir != rq_is_sync(rq2));
/*
* Strict one way elevator _except_ in the case where we allow
@@ -331,55 +322,55 @@ as_choose_req(struct as_data *ad, struct
/* Found required data */
if (!r1_wrap && r2_wrap)
- return arq1;
+ return rq1;
else if (!r2_wrap && r1_wrap)
- return arq2;
+ return rq2;
else if (r1_wrap && r2_wrap) {
/* both behind the head */
if (s1 <= s2)
- return arq1;
+ return rq1;
else
- return arq2;
+ return rq2;
}
/* Both requests in front of the head */
if (d1 < d2)
- return arq1;
+ return rq1;
else if (d2 < d1)
- return arq2;
+ return rq2;
else {
if (s1 >= s2)
- return arq1;
+ return rq1;
else
- return arq2;
+ return rq2;
}
}
/*
- * as_find_next_arq finds the next request after @prev in elevator order.
+ * as_find_next_rq finds the next request after @prev in elevator order.
* this with as_choose_req form the basis for how the scheduler chooses
* what request to process next. Anticipation works on top of this.
*/
-static struct as_rq *as_find_next_arq(struct as_data *ad, struct as_rq *arq)
+static struct request *
+as_find_next_rq(struct as_data *ad, struct request *last)
{
- struct request *last = arq->request;
struct rb_node *rbnext = rb_next(&last->rb_node);
struct rb_node *rbprev = rb_prev(&last->rb_node);
- struct as_rq *next = NULL, *prev = NULL;
+ struct request *next = NULL, *prev = NULL;
BUG_ON(RB_EMPTY_NODE(&last->rb_node));
if (rbprev)
- prev = RQ_DATA(rb_entry_rq(rbprev));
+ prev = rb_entry_rq(rbprev);
if (rbnext)
- next = RQ_DATA(rb_entry_rq(rbnext));
+ next = rb_entry_rq(rbnext);
else {
const int data_dir = rq_is_sync(last);
rbnext = rb_first(&ad->sort_list[data_dir]);
if (rbnext && rbnext != &last->rb_node)
- next = RQ_DATA(rb_entry_rq(rbnext));
+ next = rb_entry_rq(rbnext);
}
return as_choose_req(ad, next, prev);
@@ -575,11 +566,11 @@ static void as_update_iohist(struct as_d
* previous one issued.
*/
static int as_close_req(struct as_data *ad, struct as_io_context *aic,
- struct as_rq *arq)
+ struct request *rq)
{
unsigned long delay; /* milliseconds */
sector_t last = ad->last_sector[ad->batch_data_dir];
- sector_t next = arq->request->sector;
+ sector_t next = rq->sector;
sector_t delta; /* acceptable close offset (in sectors) */
sector_t s;
@@ -636,7 +627,7 @@ static int as_close_req(struct as_data *
*
* If this task has queued some other IO, do not enter enticipation.
*/
-static int as_can_break_anticipation(struct as_data *ad, struct as_rq *arq)
+static int as_can_break_anticipation(struct as_data *ad, struct request *rq)
{
struct io_context *ioc;
struct as_io_context *aic;
@@ -644,7 +635,7 @@ static int as_can_break_anticipation(str
ioc = ad->io_context;
BUG_ON(!ioc);
- if (arq && ioc == arq->io_context) {
+ if (rq && ioc == RQ_IOC(rq)) {
/* request from same process */
return 1;
}
@@ -671,7 +662,7 @@ static int as_can_break_anticipation(str
return 1;
}
- if (arq && rq_is_sync(arq->request) && as_close_req(ad, aic, arq)) {
+ if (rq && rq_is_sync(rq) && as_close_req(ad, aic, rq)) {
/*
* Found a close request that is not one of ours.
*
@@ -687,7 +678,7 @@ static int as_can_break_anticipation(str
ad->exit_no_coop = (7*ad->exit_no_coop)/8;
}
- as_update_iohist(ad, aic, arq->request);
+ as_update_iohist(ad, aic, rq);
return 1;
}
@@ -714,10 +705,10 @@ static int as_can_break_anticipation(str
}
/*
- * as_can_anticipate indicates whether we should either run arq
+ * as_can_anticipate indicates whether we should either run rq
* or keep anticipating a better request.
*/
-static int as_can_anticipate(struct as_data *ad, struct as_rq *arq)
+static int as_can_anticipate(struct as_data *ad, struct request *rq)
{
if (!ad->io_context)
/*
@@ -731,7 +722,7 @@ static int as_can_anticipate(struct as_d
*/
return 0;
- if (as_can_break_anticipation(ad, arq))
+ if (as_can_break_anticipation(ad, rq))
/*
* This request is a good candidate. Don't keep anticipating,
* run it.
@@ -749,16 +740,16 @@ static int as_can_anticipate(struct as_d
}
/*
- * as_update_arq must be called whenever a request (arq) is added to
+ * as_update_rq must be called whenever a request (rq) is added to
* the sort_list. This function keeps caches up to date, and checks if the
* request might be one we are "anticipating"
*/
-static void as_update_arq(struct as_data *ad, struct as_rq *arq)
+static void as_update_rq(struct as_data *ad, struct request *rq)
{
- const int data_dir = rq_is_sync(arq->request);
+ const int data_dir = rq_is_sync(rq);
- /* keep the next_arq cache up to date */
- ad->next_arq[data_dir] = as_choose_req(ad, arq, ad->next_arq[data_dir]);
+ /* keep the next_rq cache up to date */
+ ad->next_rq[data_dir] = as_choose_req(ad, rq, ad->next_rq[data_dir]);
/*
* have we been anticipating this request?
@@ -767,7 +758,7 @@ static void as_update_arq(struct as_data
*/
if (ad->antic_status == ANTIC_WAIT_REQ
|| ad->antic_status == ANTIC_WAIT_NEXT) {
- if (as_can_break_anticipation(ad, arq))
+ if (as_can_break_anticipation(ad, rq))
as_antic_stop(ad);
}
}
@@ -807,12 +798,11 @@ static void update_write_batch(struct as
static void as_completed_request(request_queue_t *q, struct request *rq)
{
struct as_data *ad = q->elevator->elevator_data;
- struct as_rq *arq = RQ_DATA(rq);
WARN_ON(!list_empty(&rq->queuelist));
- if (arq->state != AS_RQ_REMOVED) {
- printk("arq->state %d\n", arq->state);
+ if (RQ_STATE(rq) != AS_RQ_REMOVED) {
+ printk("rq->state %d\n", RQ_STATE(rq));
WARN_ON(1);
goto out;
}
@@ -839,7 +829,7 @@ static void as_completed_request(request
ad->new_batch = 0;
}
- if (ad->io_context == arq->io_context && ad->io_context) {
+ if (ad->io_context == RQ_IOC(rq) && ad->io_context) {
ad->antic_start = jiffies;
ad->ioc_finished = 1;
if (ad->antic_status == ANTIC_WAIT_REQ) {
@@ -851,9 +841,9 @@ static void as_completed_request(request
}
}
- as_put_io_context(arq);
+ as_put_io_context(rq);
out:
- arq->state = AS_RQ_POSTSCHED;
+ RQ_SET_STATE(rq, AS_RQ_POSTSCHED);
}
/*
@@ -864,26 +854,27 @@ out:
*/
static void as_remove_queued_request(request_queue_t *q, struct request *rq)
{
- struct as_rq *arq = RQ_DATA(rq);
const int data_dir = rq_is_sync(rq);
struct as_data *ad = q->elevator->elevator_data;
+ struct io_context *ioc;
- WARN_ON(arq->state != AS_RQ_QUEUED);
+ WARN_ON(RQ_STATE(rq) != AS_RQ_QUEUED);
- if (arq->io_context && arq->io_context->aic) {
- BUG_ON(!atomic_read(&arq->io_context->aic->nr_queued));
- atomic_dec(&arq->io_context->aic->nr_queued);
+ ioc = RQ_IOC(rq);
+ if (ioc && ioc->aic) {
+ BUG_ON(!atomic_read(&ioc->aic->nr_queued));
+ atomic_dec(&ioc->aic->nr_queued);
}
/*
- * Update the "next_arq" cache if we are about to remove its
+ * Update the "next_rq" cache if we are about to remove its
* entry
*/
- if (ad->next_arq[data_dir] == arq)
- ad->next_arq[data_dir] = as_find_next_arq(ad, arq);
+ if (ad->next_rq[data_dir] == rq)
+ ad->next_rq[data_dir] = as_find_next_rq(ad, rq);
rq_fifo_clear(rq);
- as_del_arq_rb(ad, rq);
+ as_del_rq_rb(ad, rq);
}
/*
@@ -935,9 +926,8 @@ static inline int as_batch_expired(struc
/*
* move an entry to dispatch queue
*/
-static void as_move_to_dispatch(struct as_data *ad, struct as_rq *arq)
+static void as_move_to_dispatch(struct as_data *ad, struct request *rq)
{
- struct request *rq = arq->request;
const int data_dir = rq_is_sync(rq);
BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
@@ -947,13 +937,14 @@ static void as_move_to_dispatch(struct a
/*
* This has to be set in order to be correctly updated by
- * as_find_next_arq
+ * as_find_next_rq
*/
ad->last_sector[data_dir] = rq->sector + rq->nr_sectors;
if (data_dir == REQ_SYNC) {
+ struct io_context *ioc = RQ_IOC(rq);
/* In case we have to anticipate after this */
- copy_io_context(&ad->io_context, &arq->io_context);
+ copy_io_context(&ad->io_context, &ioc);
} else {
if (ad->io_context) {
put_io_context(ad->io_context);
@@ -969,13 +960,13 @@ static void as_move_to_dispatch(struct a
* take it off the sort and fifo list, add to dispatch queue
*/
as_remove_queued_request(ad->q, rq);
- WARN_ON(arq->state != AS_RQ_QUEUED);
+ WARN_ON(RQ_STATE(rq) != AS_RQ_QUEUED);
elv_dispatch_sort(ad->q, rq);
- arq->state = AS_RQ_DISPATCHED;
- if (arq->io_context && arq->io_context->aic)
- atomic_inc(&arq->io_context->aic->nr_dispatched);
+ RQ_SET_STATE(rq, AS_RQ_DISPATCHED);
+ if (RQ_IOC(rq) && RQ_IOC(rq)->aic)
+ atomic_inc(&RQ_IOC(rq)->aic->nr_dispatched);
ad->nr_dispatched++;
}
@@ -987,9 +978,9 @@ static void as_move_to_dispatch(struct a
static int as_dispatch_request(request_queue_t *q, int force)
{
struct as_data *ad = q->elevator->elevator_data;
- struct as_rq *arq;
const int reads = !list_empty(&ad->fifo_list[REQ_SYNC]);
const int writes = !list_empty(&ad->fifo_list[REQ_ASYNC]);
+ struct request *rq;
if (unlikely(force)) {
/*
@@ -1005,14 +996,14 @@ static int as_dispatch_request(request_q
ad->changed_batch = 0;
ad->new_batch = 0;
- while (ad->next_arq[REQ_SYNC]) {
- as_move_to_dispatch(ad, ad->next_arq[REQ_SYNC]);
+ while (ad->next_rq[REQ_SYNC]) {
+ as_move_to_dispatch(ad, ad->next_rq[REQ_SYNC]);
dispatched++;
}
ad->last_check_fifo[REQ_SYNC] = jiffies;
- while (ad->next_arq[REQ_ASYNC]) {
- as_move_to_dispatch(ad, ad->next_arq[REQ_ASYNC]);
+ while (ad->next_rq[REQ_ASYNC]) {
+ as_move_to_dispatch(ad, ad->next_rq[REQ_ASYNC]);
dispatched++;
}
ad->last_check_fifo[REQ_ASYNC] = jiffies;
@@ -1036,19 +1027,19 @@ static int as_dispatch_request(request_q
/*
* batch is still running or no reads or no writes
*/
- arq = ad->next_arq[ad->batch_data_dir];
+ rq = ad->next_rq[ad->batch_data_dir];
if (ad->batch_data_dir == REQ_SYNC && ad->antic_expire) {
if (as_fifo_expired(ad, REQ_SYNC))
goto fifo_expired;
- if (as_can_anticipate(ad, arq)) {
+ if (as_can_anticipate(ad, rq)) {
as_antic_waitreq(ad);
return 0;
}
}
- if (arq) {
+ if (rq) {
/* we have a "next request" */
if (reads && !writes)
ad->current_batch_expires =
@@ -1076,7 +1067,7 @@ static int as_dispatch_request(request_q
ad->changed_batch = 1;
}
ad->batch_data_dir = REQ_SYNC;
- arq = RQ_DATA(rq_entry_fifo(ad->fifo_list[REQ_SYNC].next));
+ rq = rq_entry_fifo(ad->fifo_list[REQ_SYNC].next);
ad->last_check_fifo[ad->batch_data_dir] = jiffies;
goto dispatch_request;
}
@@ -1102,7 +1093,7 @@ dispatch_writes:
ad->batch_data_dir = REQ_ASYNC;
ad->current_write_count = ad->write_batch_count;
ad->write_batch_idled = 0;
- arq = ad->next_arq[ad->batch_data_dir];
+ rq = ad->next_rq[ad->batch_data_dir];
goto dispatch_request;
}
@@ -1116,7 +1107,7 @@ dispatch_request:
if (as_fifo_expired(ad, ad->batch_data_dir)) {
fifo_expired:
- arq = RQ_DATA(rq_entry_fifo(ad->fifo_list[ad->batch_data_dir].next));
+ rq = rq_entry_fifo(ad->fifo_list[ad->batch_data_dir].next);
}
if (ad->changed_batch) {
@@ -1135,34 +1126,33 @@ fifo_expired:
}
/*
- * arq is the selected appropriate request.
+ * rq is the selected appropriate request.
*/
- as_move_to_dispatch(ad, arq);
+ as_move_to_dispatch(ad, rq);
return 1;
}
/*
- * add arq to rbtree and fifo
+ * add rq to rbtree and fifo
*/
static void as_add_request(request_queue_t *q, struct request *rq)
{
struct as_data *ad = q->elevator->elevator_data;
- struct as_rq *arq = RQ_DATA(rq);
int data_dir;
- arq->state = AS_RQ_NEW;
+ RQ_SET_STATE(rq, AS_RQ_NEW);
data_dir = rq_is_sync(rq);
- arq->io_context = as_get_io_context();
+ rq->elevator_private = as_get_io_context();
- if (arq->io_context) {
- as_update_iohist(ad, arq->io_context->aic, arq->request);
- atomic_inc(&arq->io_context->aic->nr_queued);
+ if (RQ_IOC(rq)) {
+ as_update_iohist(ad, RQ_IOC(rq)->aic, rq);
+ atomic_inc(&RQ_IOC(rq)->aic->nr_queued);
}
- as_add_arq_rb(ad, rq);
+ as_add_rq_rb(ad, rq);
/*
* set expire time (only used for reads) and add to fifo list
@@ -1170,28 +1160,24 @@ static void as_add_request(request_queue
rq_set_fifo_time(rq, jiffies + ad->fifo_expire[data_dir]);
list_add_tail(&rq->queuelist, &ad->fifo_list[data_dir]);
- as_update_arq(ad, arq); /* keep state machine up to date */
- arq->state = AS_RQ_QUEUED;
+ as_update_rq(ad, rq); /* keep state machine up to date */
+ RQ_SET_STATE(rq, AS_RQ_QUEUED);
}
static void as_activate_request(request_queue_t *q, struct request *rq)
{
- struct as_rq *arq = RQ_DATA(rq);
-
- WARN_ON(arq->state != AS_RQ_DISPATCHED);
- arq->state = AS_RQ_REMOVED;
- if (arq->io_context && arq->io_context->aic)
- atomic_dec(&arq->io_context->aic->nr_dispatched);
+ WARN_ON(RQ_STATE(rq) != AS_RQ_DISPATCHED);
+ RQ_SET_STATE(rq, AS_RQ_REMOVED);
+ if (RQ_IOC(rq) && RQ_IOC(rq)->aic)
+ atomic_dec(&RQ_IOC(rq)->aic->nr_dispatched);
}
static void as_deactivate_request(request_queue_t *q, struct request *rq)
{
- struct as_rq *arq = RQ_DATA(rq);
-
- WARN_ON(arq->state != AS_RQ_REMOVED);
- arq->state = AS_RQ_DISPATCHED;
- if (arq->io_context && arq->io_context->aic)
- atomic_inc(&arq->io_context->aic->nr_dispatched);
+ WARN_ON(RQ_STATE(rq) != AS_RQ_REMOVED);
+ RQ_SET_STATE(rq, AS_RQ_DISPATCHED);
+ if (RQ_IOC(rq) && RQ_IOC(rq)->aic)
+ atomic_inc(&RQ_IOC(rq)->aic->nr_dispatched);
}
/*
@@ -1235,8 +1221,8 @@ static void as_merged_request(request_qu
* if the merge was a front merge, we need to reposition request
*/
if (type == ELEVATOR_FRONT_MERGE) {
- as_del_arq_rb(ad, req);
- as_add_arq_rb(ad, req);
+ as_del_rq_rb(ad, req);
+ as_add_rq_rb(ad, req);
/*
* Note! At this stage of this and the next function, our next
* request may not be optimal - eg the request may have "grown"
@@ -1248,25 +1234,22 @@ static void as_merged_request(request_qu
static void as_merged_requests(request_queue_t *q, struct request *req,
struct request *next)
{
- struct as_rq *arq = RQ_DATA(req);
- struct as_rq *anext = RQ_DATA(next);
-
- BUG_ON(!arq);
- BUG_ON(!anext);
-
/*
- * if anext expires before arq, assign its expire time to arq
- * and move into anext position (anext will be deleted) in fifo
+ * if next expires before rq, assign its expire time to arq
+ * and move into next position (next will be deleted) in fifo
*/
if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
if (time_before(rq_fifo_time(next), rq_fifo_time(req))) {
+ struct io_context *rioc = RQ_IOC(req);
+ struct io_context *nioc = RQ_IOC(next);
+
list_move(&req->queuelist, &next->queuelist);
rq_set_fifo_time(req, rq_fifo_time(next));
/*
* Don't copy here but swap, because when anext is
* removed below, it must contain the unused context
*/
- swap_io_context(&arq->io_context, &anext->io_context);
+ swap_io_context(&rioc, &nioc);
}
}
@@ -1274,9 +1257,9 @@ static void as_merged_requests(request_q
* kill knowledge of next, this one is a goner
*/
as_remove_queued_request(q, next);
- as_put_io_context(anext);
+ as_put_io_context(next);
- anext->state = AS_RQ_MERGED;
+ RQ_SET_STATE(next, AS_RQ_MERGED);
}
/*
@@ -1299,45 +1282,6 @@ static void as_work_handler(void *data)
spin_unlock_irqrestore(q->queue_lock, flags);
}
-static void as_put_request(request_queue_t *q, struct request *rq)
-{
- struct as_data *ad = q->elevator->elevator_data;
- struct as_rq *arq = RQ_DATA(rq);
-
- if (!arq) {
- WARN_ON(1);
- return;
- }
-
- if (unlikely(arq->state != AS_RQ_POSTSCHED &&
- arq->state != AS_RQ_PRESCHED &&
- arq->state != AS_RQ_MERGED)) {
- printk("arq->state %d\n", arq->state);
- WARN_ON(1);
- }
-
- mempool_free(arq, ad->arq_pool);
- rq->elevator_private = NULL;
-}
-
-static int as_set_request(request_queue_t *q, struct request *rq,
- struct bio *bio, gfp_t gfp_mask)
-{
- struct as_data *ad = q->elevator->elevator_data;
- struct as_rq *arq = mempool_alloc(ad->arq_pool, gfp_mask);
-
- if (arq) {
- memset(arq, 0, sizeof(*arq));
- arq->request = rq;
- arq->state = AS_RQ_PRESCHED;
- arq->io_context = NULL;
- rq->elevator_private = arq;
- return 0;
- }
-
- return 1;
-}
-
static int as_may_queue(request_queue_t *q, int rw, struct bio *bio)
{
int ret = ELV_MQUEUE_MAY;
@@ -1364,22 +1308,17 @@ static void as_exit_queue(elevator_t *e)
BUG_ON(!list_empty(&ad->fifo_list[REQ_SYNC]));
BUG_ON(!list_empty(&ad->fifo_list[REQ_ASYNC]));
- mempool_destroy(ad->arq_pool);
put_io_context(ad->io_context);
kfree(ad);
}
/*
- * initialize elevator private data (as_data), and alloc a arq for
- * each request on the free lists
+ * initialize elevator private data (as_data).
*/
static void *as_init_queue(request_queue_t *q, elevator_t *e)
{
struct as_data *ad;
- if (!arq_pool)
- return NULL;
-
ad = kmalloc_node(sizeof(*ad), GFP_KERNEL, q->node);
if (!ad)
return NULL;
@@ -1387,13 +1326,6 @@ static void *as_init_queue(request_queue
ad->q = q; /* Identify what queue the data belongs to */
- ad->arq_pool = mempool_create_node(BLKDEV_MIN_RQ, mempool_alloc_slab,
- mempool_free_slab, arq_pool, q->node);
- if (!ad->arq_pool) {
- kfree(ad);
- return NULL;
- }
-
/* anticipatory scheduling helpers */
ad->antic_timer.function = as_antic_timeout;
ad->antic_timer.data = (unsigned long)q;
@@ -1514,8 +1446,6 @@ static struct elevator_type iosched_as =
.elevator_completed_req_fn = as_completed_request,
.elevator_former_req_fn = elv_rb_former_request,
.elevator_latter_req_fn = elv_rb_latter_request,
- .elevator_set_req_fn = as_set_request,
- .elevator_put_req_fn = as_put_request,
.elevator_may_queue_fn = as_may_queue,
.elevator_init_fn = as_init_queue,
.elevator_exit_fn = as_exit_queue,
@@ -1531,11 +1461,6 @@ static int __init as_init(void)
{
int ret;
- arq_pool = kmem_cache_create("as_arq", sizeof(struct as_rq),
- 0, 0, NULL, NULL);
- if (!arq_pool)
- return -ENOMEM;
-
ret = elv_register(&iosched_as);
if (!ret) {
/*
@@ -1547,7 +1472,6 @@ static int __init as_init(void)
return 0;
}
- kmem_cache_destroy(arq_pool);
return ret;
}
@@ -1561,7 +1485,6 @@ static void __exit as_exit(void)
if (atomic_read(&ioc_count))
wait_for_completion(ioc_gone);
synchronize_rcu();
- kmem_cache_destroy(arq_pool);
}
module_init(as_init);
--
1.4.1.ged0e0
^ permalink raw reply related [flat|nested] 16+ messages in thread