/*
* linux/drivers/block/deadline-iosched.c
*
* Deadline i/o scheduler.
*
* Copyright (C) 2002 Jens Axboe <axboe@suse.de>
*/
#include <linux/kernel.h>
#include <linux/fs.h>
#include <linux/blkdev.h>
#include <linux/elevator.h>
#include <linux/bio.h>
#include <linux/config.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/init.h>
#include <linux/compiler.h>
#include <linux/hash.h>
#include <linux/rbtree.h>
/*
* See Documentation/block/deadline-iosched.txt
*/
static int read_expire = HZ / 2; /* max time before a read is submitted. */
static int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */
static int writes_starved = 2; /* max times reads can starve a write */
static 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 list_entry_hash(ptr) list_entry((ptr), struct deadline_rq, hash)
#define ON_HASH(drq) (drq)->on_hash
struct deadline_data {
/*
* run time data
*/
/*
* requests (deadline_rq s) are present on both sort_list and fifo_list
*/
struct rb_root sort_list[2];
struct list_head fifo_list[2];
/*
* next in sort order. read, write or both are NULL
*/
struct deadline_rq *next_drq[2];
struct list_head *dispatch; /* driver dispatch queue */
struct list_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 */
/*
* settings that change how the i/o scheduler behaves
*/
int fifo_expire[2];
int fifo_batch;
int writes_starved;
int front_merges;
mempool_t *drq_pool;
};
/*
* 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;
/*
* request hash, key is the ending offset (for back merge lookup)
*/
struct list_head hash;
char on_hash;
/*
* 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)
/*
* the back merge hash support functions
*/
static inline void __deadline_del_drq_hash(struct deadline_rq *drq)
{
drq->on_hash = 0;
list_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 void
deadline_remove_merge_hints(request_queue_t *q, struct deadline_rq *drq)
{
deadline_del_drq_hash(drq);
if (q->last_merge == drq->request)
q->last_merge = NULL;
}
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));
drq->on_hash = 1;
list_add(&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 list_head *head = &dd->hash[DL_HASH_FN(rq_hash_key(rq))];
if (ON_HASH(drq) && drq->hash.prev != head) {
list_del(&drq->hash);
list_add(&drq->hash, head);
}
}
static struct request *
deadline_find_drq_hash(struct deadline_data *dd, sector_t offset)
{
struct list_head *hash_list = &dd->hash[DL_HASH_FN(offset)];
struct list_head *entry, *next = hash_list->next;
while ((entry = next) != hash_list) {
struct deadline_rq *drq = list_entry_hash(entry);
struct request *__rq = drq->request;
next = entry->next;
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_NONE (2)
#define RB_EMPTY(root) ((root)->rb_node == NULL)
#define ON_RB(node) ((node)->rb_color != RB_NONE)
#define RB_CLEAR(node) ((node)->rb_color = RB_NONE)
#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