blob: 209e269fa3e7ba4986fdeed06ae5737fea9909dd [file] [log] [blame]
/*
* ROW (Read Over Write) I/O scheduler.
*
* Copyright (c) 2012-2014, The Linux Foundation. All rights reserved.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 and
* only version 2 as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*/
/* See Documentation/block/row-iosched.txt */
#include <linux/kernel.h>
#include <linux/fs.h>
#include <linux/blkdev.h>
#include <linux/elevator.h>
#include <linux/bio.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/init.h>
#include <linux/compiler.h>
#include <linux/blktrace_api.h>
#include <linux/hrtimer.h>
/*
* enum row_queue_prio - Priorities of the ROW queues
*
* This enum defines the priorities (and the number of queues)
* the requests will be distributed to. The higher priority -
* the bigger is the "bus time" (or the dispatch quantum) given
* to that queue.
* ROWQ_PRIO_HIGH_READ - is the higher priority queue.
*
*/
enum row_queue_prio {
ROWQ_PRIO_HIGH_READ = 0,
ROWQ_PRIO_HIGH_SWRITE,
ROWQ_PRIO_REG_READ,
ROWQ_PRIO_REG_SWRITE,
ROWQ_PRIO_REG_WRITE,
ROWQ_PRIO_LOW_READ,
ROWQ_PRIO_LOW_SWRITE,
ROWQ_MAX_PRIO,
};
/*
* The following indexes define the distribution of ROW queues according to
* priorities. Each index defines the first queue in that priority group.
*/
#define ROWQ_HIGH_PRIO_IDX ROWQ_PRIO_HIGH_READ
#define ROWQ_REG_PRIO_IDX ROWQ_PRIO_REG_READ
#define ROWQ_LOW_PRIO_IDX ROWQ_PRIO_LOW_READ
/**
* struct row_queue_params - ROW queue parameters
* @idling_enabled: Flag indicating whether idling is enable on
* the queue
* @quantum: Number of requests to be dispatched from this queue
* in a dispatch cycle
* @is_urgent: Flags indicating whether the queue can notify on
* urgent requests
*
*/
struct row_queue_params {
bool idling_enabled;
int quantum;
bool is_urgent;
};
/*
* This array holds the default values of the different configurables
* for each ROW queue. Each row of the array holds the following values:
* {idling_enabled, quantum, is_urgent}
* Each row corresponds to a queue with the same index (according to
* enum row_queue_prio)
* Note: The quantums are valid inside their priority type. For example:
* For every 10 high priority read requests, 1 high priority sync
* write will be dispatched.
* For every 100 regular read requests 1 regular write request will
* be dispatched.
*/
static const struct row_queue_params row_queues_def[] = {
/* idling_enabled, quantum, is_urgent */
{true, 10, true}, /* ROWQ_PRIO_HIGH_READ */
{false, 1, false}, /* ROWQ_PRIO_HIGH_SWRITE */
{true, 100, true}, /* ROWQ_PRIO_REG_READ */
{false, 1, false}, /* ROWQ_PRIO_REG_SWRITE */
{false, 1, false}, /* ROWQ_PRIO_REG_WRITE */
{false, 1, false}, /* ROWQ_PRIO_LOW_READ */
{false, 1, false} /* ROWQ_PRIO_LOW_SWRITE */
};
/* Default values for idling on read queues (in msec) */
#define ROW_IDLE_TIME_MSEC 5
#define ROW_READ_FREQ_MSEC 5
/**
* struct rowq_idling_data - parameters for idling on the queue
* @last_insert_time: time the last request was inserted
* to the queue
* @begin_idling: flag indicating wether we should idle
*
*/
struct rowq_idling_data {
ktime_t last_insert_time;
bool begin_idling;
};
/**
* struct row_queue - requests grouping structure
* @rdata: parent row_data structure
* @fifo: fifo of requests
* @prio: queue priority (enum row_queue_prio)
* @nr_dispatched: number of requests already dispatched in
* the current dispatch cycle
* @nr_req: number of requests in queue
* @dispatch quantum: number of requests this queue may
* dispatch in a dispatch cycle
* @idle_data: data for idling on queues
*
*/
struct row_queue {
struct row_data *rdata;
struct list_head fifo;
enum row_queue_prio prio;
unsigned int nr_dispatched;
unsigned int nr_req;
int disp_quantum;
/* used only for READ queues */
struct rowq_idling_data idle_data;
};
/**
* struct idling_data - data for idling on empty rqueue
* @idle_time_ms: idling duration (msec)
* @freq_ms: min time between two requests that
* triger idling (msec)
* @hr_timer: idling timer
* @idle_work: the work to be scheduled when idling timer expires
* @idling_queue_idx: index of the queues we're idling on
*
*/
struct idling_data {
s64 idle_time_ms;
s64 freq_ms;
struct hrtimer hr_timer;
struct work_struct idle_work;
enum row_queue_prio idling_queue_idx;
};
/**
* struct starvation_data - data for starvation management
* @starvation_limit: number of times this priority class
* can tolerate being starved
* @starvation_counter: number of requests from higher
* priority classes that were dispatched while this
* priority request were pending
*
*/
struct starvation_data {
int starvation_limit;
int starvation_counter;
};
/**
* struct row_queue - Per block device rqueue structure
* @dispatch_queue: dispatch rqueue
* @row_queues: array of priority request queues
* @rd_idle_data: data for idling after READ request
* @nr_reqs: nr_reqs[0] holds the number of all READ requests in
* scheduler, nr_reqs[1] holds the number of all WRITE
* requests in scheduler
* @urgent_in_flight: flag indicating that there is an urgent
* request that was dispatched to driver and is yet to
* complete.
* @pending_urgent_rq: pointer to the pending urgent request
* @last_served_ioprio_class: I/O priority class that was last dispatched from
* @reg_prio_starvation: starvation data for REGULAR priority queues
* @low_prio_starvation: starvation data for LOW priority queues
* @cycle_flags: used for marking unserved queueus
*
*/
struct row_data {
struct request_queue *dispatch_queue;
struct row_queue row_queues[ROWQ_MAX_PRIO];
struct idling_data rd_idle_data;
unsigned int nr_reqs[2];
bool urgent_in_flight;
struct request *pending_urgent_rq;
int last_served_ioprio_class;
#define ROW_REG_STARVATION_TOLLERANCE 5000
struct starvation_data reg_prio_starvation;
#define ROW_LOW_STARVATION_TOLLERANCE 10000
struct starvation_data low_prio_starvation;
unsigned int cycle_flags;
};
#define RQ_ROWQ(rq) ((struct row_queue *) ((rq)->elv.priv[0]))
#define row_log(q, fmt, args...) \
blk_add_trace_msg(q, "%s():" fmt , __func__, ##args)
#define row_log_rowq(rdata, rowq_id, fmt, args...) \
blk_add_trace_msg(rdata->dispatch_queue, "rowq%d " fmt, \
rowq_id, ##args)
static inline void row_mark_rowq_unserved(struct row_data *rd,
enum row_queue_prio qnum)
{
rd->cycle_flags |= (1 << qnum);
}
static inline void row_clear_rowq_unserved(struct row_data *rd,
enum row_queue_prio qnum)
{
rd->cycle_flags &= ~(1 << qnum);
}
static inline int row_rowq_unserved(struct row_data *rd,
enum row_queue_prio qnum)
{
return rd->cycle_flags & (1 << qnum);
}
static inline void __maybe_unused row_dump_queues_stat(struct row_data *rd)
{
int i;
row_log(rd->dispatch_queue, " Queues status:");
for (i = 0; i < ROWQ_MAX_PRIO; i++)
row_log(rd->dispatch_queue,
"queue%d: dispatched= %d, nr_req=%d", i,
rd->row_queues[i].nr_dispatched,
rd->row_queues[i].nr_req);
}
/******************** Static helper functions ***********************/
static void kick_queue(struct work_struct *work)
{
struct idling_data *read_data =
container_of(work, struct idling_data, idle_work);
struct row_data *rd =
container_of(read_data, struct row_data, rd_idle_data);
blk_run_queue(rd->dispatch_queue);
}
static enum hrtimer_restart row_idle_hrtimer_fn(struct hrtimer *hr_timer)
{
struct idling_data *read_data =
container_of(hr_timer, struct idling_data, hr_timer);
struct row_data *rd =
container_of(read_data, struct row_data, rd_idle_data);
row_log_rowq(rd, rd->rd_idle_data.idling_queue_idx,
"Performing delayed work");
/* Mark idling process as done */
rd->row_queues[rd->rd_idle_data.idling_queue_idx].
idle_data.begin_idling = false;
rd->rd_idle_data.idling_queue_idx = ROWQ_MAX_PRIO;
if (!rd->nr_reqs[READ] && !rd->nr_reqs[WRITE])
row_log(rd->dispatch_queue, "No requests in scheduler");
else
kblockd_schedule_work(rd->dispatch_queue,
&read_data->idle_work);
return HRTIMER_NORESTART;
}
/*
* row_regular_req_pending() - Check if there are REGULAR priority requests
* Pending in scheduler
* @rd: pointer to struct row_data
*
* Returns True if there are REGULAR priority requests in scheduler queues.
* False, otherwise.
*/
static inline bool row_regular_req_pending(struct row_data *rd)
{
int i;
for (i = ROWQ_REG_PRIO_IDX; i < ROWQ_LOW_PRIO_IDX; i++)
if (!list_empty(&rd->row_queues[i].fifo))
return true;
return false;
}
/*
* row_low_req_pending() - Check if there are LOW priority requests
* Pending in scheduler
* @rd: pointer to struct row_data
*
* Returns True if there are LOW priority requests in scheduler queues.
* False, otherwise.
*/
static inline bool row_low_req_pending(struct row_data *rd)
{
int i;
for (i = ROWQ_LOW_PRIO_IDX; i < ROWQ_MAX_PRIO; i++)
if (!list_empty(&rd->row_queues[i].fifo))
return true;
return false;
}
/******************* Elevator callback functions *********************/
/*
* row_add_request() - Add request to the scheduler
* @q: requests queue
* @rq: request to add
*
*/
static void row_add_request(struct request_queue *q,
struct request *rq)
{
struct row_data *rd = (struct row_data *)q->elevator->elevator_data;
struct row_queue *rqueue = RQ_ROWQ(rq);
s64 diff_ms;
bool queue_was_empty = list_empty(&rqueue->fifo);
list_add_tail(&rq->queuelist, &rqueue->fifo);
rd->nr_reqs[rq_data_dir(rq)]++;
rqueue->nr_req++;
rq_set_fifo_time(rq, jiffies); /* for statistics*/
if (rq->cmd_flags & REQ_URGENT) {
WARN_ON(1);
blk_dump_rq_flags(rq, "");
rq->cmd_flags &= ~REQ_URGENT;
}
if (row_queues_def[rqueue->prio].idling_enabled) {
if (rd->rd_idle_data.idling_queue_idx == rqueue->prio &&
hrtimer_active(&rd->rd_idle_data.hr_timer)) {
if (hrtimer_try_to_cancel(
&rd->rd_idle_data.hr_timer) >= 0) {
row_log_rowq(rd, rqueue->prio,
"Canceled delayed work on %d",
rd->rd_idle_data.idling_queue_idx);
rd->rd_idle_data.idling_queue_idx =
ROWQ_MAX_PRIO;
}
}
diff_ms = ktime_to_ms(ktime_sub(ktime_get(),
rqueue->idle_data.last_insert_time));
if (unlikely(diff_ms < 0)) {
pr_err("%s(): time delta error: diff_ms < 0",
__func__);
rqueue->idle_data.begin_idling = false;
return;
}
if (diff_ms < rd->rd_idle_data.freq_ms) {
rqueue->idle_data.begin_idling = true;
row_log_rowq(rd, rqueue->prio, "Enable idling");
} else {
rqueue->idle_data.begin_idling = false;
row_log_rowq(rd, rqueue->prio, "Disable idling (%ldms)",
(long)diff_ms);
}
rqueue->idle_data.last_insert_time = ktime_get();
}
if (row_queues_def[rqueue->prio].is_urgent &&
!rd->pending_urgent_rq && !rd->urgent_in_flight) {
/* Handle High Priority queues */
if (rqueue->prio < ROWQ_REG_PRIO_IDX &&
rd->last_served_ioprio_class != IOPRIO_CLASS_RT &&
queue_was_empty) {
row_log_rowq(rd, rqueue->prio,
"added (high prio) urgent request");
rq->cmd_flags |= REQ_URGENT;
rd->pending_urgent_rq = rq;
} else if (row_rowq_unserved(rd, rqueue->prio)) {
/* Handle Regular priotity queues */
row_log_rowq(rd, rqueue->prio,
"added urgent request (total on queue=%d)",
rqueue->nr_req);
rq->cmd_flags |= REQ_URGENT;
rd->pending_urgent_rq = rq;
}
} else
row_log_rowq(rd, rqueue->prio,
"added request (total on queue=%d)", rqueue->nr_req);
}
/**
* row_reinsert_req() - Reinsert request back to the scheduler
* @q: requests queue
* @rq: request to add
*
* Reinsert the given request back to the queue it was
* dispatched from as if it was never dispatched.
*
* Returns 0 on success, error code otherwise
*/
static int row_reinsert_req(struct request_queue *q,
struct request *rq)
{
struct row_data *rd = q->elevator->elevator_data;
struct row_queue *rqueue = RQ_ROWQ(rq);
if (!rqueue || rqueue->prio >= ROWQ_MAX_PRIO)
return -EIO;
list_add(&rq->queuelist, &rqueue->fifo);
rd->nr_reqs[rq_data_dir(rq)]++;
rqueue->nr_req++;
row_log_rowq(rd, rqueue->prio,
"%s request reinserted (total on queue=%d)",
(rq_data_dir(rq) == READ ? "READ" : "write"), rqueue->nr_req);
if (rq->cmd_flags & REQ_URGENT) {
/*
* It's not compliant with the design to re-insert
* urgent requests. We want to be able to track this
* down.
*/
WARN_ON(1);
if (!rd->urgent_in_flight) {
pr_err("%s(): no urgent in flight", __func__);
} else {
rd->urgent_in_flight = false;
pr_err("%s(): reinserting URGENT %s req",
__func__,
(rq_data_dir(rq) == READ ? "READ" : "WRITE"));
if (rd->pending_urgent_rq) {
pr_err("%s(): urgent rq is pending",
__func__);
rd->pending_urgent_rq->cmd_flags &= ~REQ_URGENT;
}
rd->pending_urgent_rq = rq;
}
}
return 0;
}
static void row_completed_req(struct request_queue *q, struct request *rq)
{
struct row_data *rd = q->elevator->elevator_data;
if (rq->cmd_flags & REQ_URGENT) {
if (!rd->urgent_in_flight) {
WARN_ON(1);
pr_err("%s(): URGENT req but urgent_in_flight = F",
__func__);
}
rd->urgent_in_flight = false;
rq->cmd_flags &= ~REQ_URGENT;
}
row_log(q, "completed %s %s req.",
(rq->cmd_flags & REQ_URGENT ? "URGENT" : "regular"),
(rq_data_dir(rq) == READ ? "READ" : "WRITE"));
}
/**
* row_urgent_pending() - Return TRUE if there is an urgent
* request on scheduler
* @q: requests queue
*/
static bool row_urgent_pending(struct request_queue *q)
{
struct row_data *rd = q->elevator->elevator_data;
if (rd->urgent_in_flight) {
row_log(rd->dispatch_queue, "%d urgent requests in flight",
rd->urgent_in_flight);
return false;
}
if (rd->pending_urgent_rq) {
row_log(rd->dispatch_queue, "Urgent request pending");
return true;
}
row_log(rd->dispatch_queue, "no urgent request pending/in flight");
return false;
}
/**
* row_remove_request() - Remove given request from scheduler
* @q: requests queue
* @rq: request to remove
*
*/
static void row_remove_request(struct row_data *rd,
struct request *rq)
{
struct row_queue *rqueue = RQ_ROWQ(rq);
list_del_init(&(rq)->queuelist);
if (rd->pending_urgent_rq == rq)
rd->pending_urgent_rq = NULL;
else
BUG_ON(rq->cmd_flags & REQ_URGENT);
rqueue->nr_req--;
rd->nr_reqs[rq_data_dir(rq)]--;
}
/*
* row_dispatch_insert() - move request to dispatch queue
* @rd: pointer to struct row_data
* @rq: the request to dispatch
*
* This function moves the given request to the dispatch queue
*
*/
static void row_dispatch_insert(struct row_data *rd, struct request *rq)
{
struct row_queue *rqueue = RQ_ROWQ(rq);
row_remove_request(rd, rq);
elv_dispatch_sort(rd->dispatch_queue, rq);
if (rq->cmd_flags & REQ_URGENT) {
WARN_ON(rd->urgent_in_flight);
rd->urgent_in_flight = true;
}
rqueue->nr_dispatched++;
row_clear_rowq_unserved(rd, rqueue->prio);
row_log_rowq(rd, rqueue->prio,
" Dispatched request %p nr_disp = %d", rq,
rqueue->nr_dispatched);
if (rqueue->prio < ROWQ_REG_PRIO_IDX) {
rd->last_served_ioprio_class = IOPRIO_CLASS_RT;
if (row_regular_req_pending(rd))
rd->reg_prio_starvation.starvation_counter++;
if (row_low_req_pending(rd))
rd->low_prio_starvation.starvation_counter++;
} else if (rqueue->prio < ROWQ_LOW_PRIO_IDX) {
rd->last_served_ioprio_class = IOPRIO_CLASS_BE;
rd->reg_prio_starvation.starvation_counter = 0;
if (row_low_req_pending(rd))
rd->low_prio_starvation.starvation_counter++;
} else {
rd->last_served_ioprio_class = IOPRIO_CLASS_IDLE;
rd->low_prio_starvation.starvation_counter = 0;
}
}
/*
* row_get_ioprio_class_to_serve() - Return the next I/O priority
* class to dispatch requests from
* @rd: pointer to struct row_data
* @force: flag indicating if forced dispatch
*
* This function returns the next I/O priority class to serve
* {IOPRIO_CLASS_NONE, IOPRIO_CLASS_RT, IOPRIO_CLASS_BE, IOPRIO_CLASS_IDLE}.
* If there are no more requests in scheduler or if we're idling on some queue
* IOPRIO_CLASS_NONE will be returned.
* If idling is scheduled on a lower priority queue than the one that needs
* to be served, it will be canceled.
*
*/
static int row_get_ioprio_class_to_serve(struct row_data *rd, int force)
{
int i;
int ret = IOPRIO_CLASS_NONE;
if (!rd->nr_reqs[READ] && !rd->nr_reqs[WRITE]) {
row_log(rd->dispatch_queue, "No more requests in scheduler");
goto check_idling;
}
/* First, go over the high priority queues */
for (i = 0; i < ROWQ_REG_PRIO_IDX; i++) {
if (!list_empty(&rd->row_queues[i].fifo)) {
if (hrtimer_active(&rd->rd_idle_data.hr_timer)) {
if (hrtimer_try_to_cancel(
&rd->rd_idle_data.hr_timer) >= 0) {
row_log(rd->dispatch_queue,
"Canceling delayed work on %d. RT pending",
rd->rd_idle_data.idling_queue_idx);
rd->rd_idle_data.idling_queue_idx =
ROWQ_MAX_PRIO;
}
}
if (row_regular_req_pending(rd) &&
(rd->reg_prio_starvation.starvation_counter >=
rd->reg_prio_starvation.starvation_limit))
ret = IOPRIO_CLASS_BE;
else if (row_low_req_pending(rd) &&
(rd->low_prio_starvation.starvation_counter >=
rd->low_prio_starvation.starvation_limit))
ret = IOPRIO_CLASS_IDLE;
else
ret = IOPRIO_CLASS_RT;
goto done;
}
}
/*
* At the moment idling is implemented only for READ queues.
* If enabled on WRITE, this needs updating
*/
if (hrtimer_active(&rd->rd_idle_data.hr_timer)) {
row_log(rd->dispatch_queue, "Delayed work pending. Exiting");
goto done;
}
check_idling:
/* Check for (high priority) idling and enable if needed */
for (i = 0; i < ROWQ_REG_PRIO_IDX && !force; i++) {
if (rd->row_queues[i].idle_data.begin_idling &&
row_queues_def[i].idling_enabled)
goto initiate_idling;
}
/* Regular priority queues */
for (i = ROWQ_REG_PRIO_IDX; i < ROWQ_LOW_PRIO_IDX; i++) {
if (list_empty(&rd->row_queues[i].fifo)) {
/* We can idle only if this is not a forced dispatch */
if (rd->row_queues[i].idle_data.begin_idling &&
!force && row_queues_def[i].idling_enabled)
goto initiate_idling;
} else {
if (row_low_req_pending(rd) &&
(rd->low_prio_starvation.starvation_counter >=
rd->low_prio_starvation.starvation_limit))
ret = IOPRIO_CLASS_IDLE;
else
ret = IOPRIO_CLASS_BE;
goto done;
}
}
if (rd->nr_reqs[READ] || rd->nr_reqs[WRITE])
ret = IOPRIO_CLASS_IDLE;
goto done;
initiate_idling:
hrtimer_start(&rd->rd_idle_data.hr_timer,
ktime_set(0, rd->rd_idle_data.idle_time_ms * NSEC_PER_MSEC),
HRTIMER_MODE_REL);
rd->rd_idle_data.idling_queue_idx = i;
row_log_rowq(rd, i, "Scheduled delayed work on %d. exiting", i);
done:
return ret;
}
static void row_restart_cycle(struct row_data *rd,
int start_idx, int end_idx)
{
int i;
row_dump_queues_stat(rd);
for (i = start_idx; i < end_idx; i++) {
if (rd->row_queues[i].nr_dispatched <
rd->row_queues[i].disp_quantum)
row_mark_rowq_unserved(rd, i);
rd->row_queues[i].nr_dispatched = 0;
}
row_log(rd->dispatch_queue, "Restarting cycle for class @ %d-%d",
start_idx, end_idx);
}
/*
* row_get_next_queue() - selects the next queue to dispatch from
* @q: requests queue
* @rd: pointer to struct row_data
* @start_idx/end_idx: indexes in the row_queues array to select a queue
* from.
*
* Return index of the queues to dispatch from. Error code if fails.
*
*/
static int row_get_next_queue(struct request_queue *q, struct row_data *rd,
int start_idx, int end_idx)
{
int i = start_idx;
bool restart = true;
int ret = -EIO;
do {
if (list_empty(&rd->row_queues[i].fifo) ||
rd->row_queues[i].nr_dispatched >=
rd->row_queues[i].disp_quantum) {
i++;
if (i == end_idx && restart) {
/* Restart cycle for this priority class */
row_restart_cycle(rd, start_idx, end_idx);
i = start_idx;
restart = false;
}
} else {
ret = i;
break;
}
} while (i < end_idx);
return ret;
}
/*
* row_dispatch_requests() - selects the next request to dispatch
* @q: requests queue
* @force: flag indicating if forced dispatch
*
* Return 0 if no requests were moved to the dispatch queue.
* 1 otherwise
*
*/
static int row_dispatch_requests(struct request_queue *q, int force)
{
struct row_data *rd = (struct row_data *)q->elevator->elevator_data;
int ret = 0, currq, ioprio_class_to_serve, start_idx, end_idx;
if (force && hrtimer_active(&rd->rd_idle_data.hr_timer)) {
if (hrtimer_try_to_cancel(&rd->rd_idle_data.hr_timer) >= 0) {
row_log(rd->dispatch_queue,
"Canceled delayed work on %d - forced dispatch",
rd->rd_idle_data.idling_queue_idx);
rd->rd_idle_data.idling_queue_idx = ROWQ_MAX_PRIO;
}
}
if (rd->pending_urgent_rq) {
row_log(rd->dispatch_queue, "dispatching urgent request");
row_dispatch_insert(rd, rd->pending_urgent_rq);
ret = 1;
goto done;
}
ioprio_class_to_serve = row_get_ioprio_class_to_serve(rd, force);
row_log(rd->dispatch_queue, "Dispatching from %d priority class",
ioprio_class_to_serve);
switch (ioprio_class_to_serve) {
case IOPRIO_CLASS_NONE:
rd->last_served_ioprio_class = IOPRIO_CLASS_NONE;
goto done;
case IOPRIO_CLASS_RT:
start_idx = ROWQ_HIGH_PRIO_IDX;
end_idx = ROWQ_REG_PRIO_IDX;
break;
case IOPRIO_CLASS_BE:
start_idx = ROWQ_REG_PRIO_IDX;
end_idx = ROWQ_LOW_PRIO_IDX;
break;
case IOPRIO_CLASS_IDLE:
start_idx = ROWQ_LOW_PRIO_IDX;
end_idx = ROWQ_MAX_PRIO;
break;
default:
pr_err("%s(): Invalid I/O priority class", __func__);
goto done;
}
currq = row_get_next_queue(q, rd, start_idx, end_idx);
/* Dispatch */
if (currq >= 0) {
row_dispatch_insert(rd,
rq_entry_fifo(rd->row_queues[currq].fifo.next));
ret = 1;
}
done:
return ret;
}
/*
* row_init_queue() - Init scheduler data structures
* @q: requests queue
*
* Return pointer to struct row_data to be saved in elevator for
* this dispatch queue
*
*/
static int row_init_queue(struct request_queue *q, struct elevator_type *e)
{
struct row_data *rdata;
struct elevator_queue *eq;
int i;
eq = elevator_alloc(q, e);
if (!eq)
return -ENOMEM;
rdata = kmalloc_node(sizeof(*rdata),
GFP_KERNEL | __GFP_ZERO, q->node);
if (!rdata) {
kobject_put(&eq->kobj);
return -ENOMEM;
}
eq->elevator_data = rdata;
memset(rdata, 0, sizeof(*rdata));
for (i = 0; i < ROWQ_MAX_PRIO; i++) {
INIT_LIST_HEAD(&rdata->row_queues[i].fifo);
rdata->row_queues[i].disp_quantum = row_queues_def[i].quantum;
rdata->row_queues[i].rdata = rdata;
rdata->row_queues[i].prio = i;
rdata->row_queues[i].idle_data.begin_idling = false;
rdata->row_queues[i].idle_data.last_insert_time =
ktime_set(0, 0);
}
rdata->reg_prio_starvation.starvation_limit =
ROW_REG_STARVATION_TOLLERANCE;
rdata->low_prio_starvation.starvation_limit =
ROW_LOW_STARVATION_TOLLERANCE;
/*
* Currently idling is enabled only for READ queues. If we want to
* enable it for write queues also, note that idling frequency will
* be the same in both cases
*/
rdata->rd_idle_data.idle_time_ms = ROW_IDLE_TIME_MSEC;
rdata->rd_idle_data.freq_ms = ROW_READ_FREQ_MSEC;
hrtimer_init(&rdata->rd_idle_data.hr_timer,
CLOCK_MONOTONIC, HRTIMER_MODE_REL);
rdata->rd_idle_data.hr_timer.function = &row_idle_hrtimer_fn;
INIT_WORK(&rdata->rd_idle_data.idle_work, kick_queue);
rdata->last_served_ioprio_class = IOPRIO_CLASS_NONE;
rdata->rd_idle_data.idling_queue_idx = ROWQ_MAX_PRIO;
rdata->dispatch_queue = q;
spin_lock_irq(q->queue_lock);
q->elevator = eq;
spin_unlock_irq(q->queue_lock);
return 0;
}
/*
* row_exit_queue() - called on unloading the RAW scheduler
* @e: poiner to struct elevator_queue
*
*/
static void row_exit_queue(struct elevator_queue *e)
{
struct row_data *rd = (struct row_data *)e->elevator_data;
int i;
for (i = 0; i < ROWQ_MAX_PRIO; i++)
BUG_ON(!list_empty(&rd->row_queues[i].fifo));
if (hrtimer_cancel(&rd->rd_idle_data.hr_timer))
pr_err("%s(): idle timer was active!", __func__);
rd->rd_idle_data.idling_queue_idx = ROWQ_MAX_PRIO;
kfree(rd);
}
/*
* row_merged_requests() - Called when 2 requests are merged
* @q: requests queue
* @rq: request the two requests were merged into
* @next: request that was merged
*/
static void row_merged_requests(struct request_queue *q, struct request *rq,
struct request *next)
{
struct row_queue *rqueue = RQ_ROWQ(next);
list_del_init(&next->queuelist);
rqueue->nr_req--;
if (rqueue->rdata->pending_urgent_rq == next) {
pr_err("\n\nROW_WARNING: merging pending urgent!");
rqueue->rdata->pending_urgent_rq = rq;
rq->cmd_flags |= REQ_URGENT;
WARN_ON(!(next->cmd_flags & REQ_URGENT));
next->cmd_flags &= ~REQ_URGENT;
}
rqueue->rdata->nr_reqs[rq_data_dir(rq)]--;
}
/*
* row_get_queue_prio() - Get queue priority for a given request
*
* This is a helping function which purpose is to determine what
* ROW queue the given request should be added to (and
* dispatched from later on)
*
*/
static enum row_queue_prio row_get_queue_prio(struct request *rq,
struct row_data *rd)
{
const int data_dir = rq_data_dir(rq);
const bool is_sync = rq_is_sync(rq);
enum row_queue_prio q_type = ROWQ_MAX_PRIO;
int ioprio_class = IOPRIO_PRIO_CLASS(rq->elv.icq->ioc->ioprio);
switch (ioprio_class) {
case IOPRIO_CLASS_RT:
if (data_dir == READ)
q_type = ROWQ_PRIO_HIGH_READ;
else if (is_sync)
q_type = ROWQ_PRIO_HIGH_SWRITE;
else {
pr_err("%s:%s(): got a simple write from RT_CLASS. How???",
rq->rq_disk->disk_name, __func__);
q_type = ROWQ_PRIO_REG_WRITE;
}
break;
case IOPRIO_CLASS_IDLE:
if (data_dir == READ)
q_type = ROWQ_PRIO_LOW_READ;
else if (is_sync)
q_type = ROWQ_PRIO_LOW_SWRITE;
else {
pr_err("%s:%s(): got a simple write from IDLE_CLASS. How???",
rq->rq_disk->disk_name, __func__);
q_type = ROWQ_PRIO_REG_WRITE;
}
break;
case IOPRIO_CLASS_NONE:
case IOPRIO_CLASS_BE:
default:
if (data_dir == READ)
q_type = ROWQ_PRIO_REG_READ;
else if (is_sync)
q_type = ROWQ_PRIO_REG_SWRITE;
else
q_type = ROWQ_PRIO_REG_WRITE;
break;
}
return q_type;
}
/*
* row_set_request() - Set ROW data structures associated with this request.
* @q: requests queue
* @rq: pointer to the request
* @gfp_mask: ignored
*
*/
static int
row_set_request(struct request_queue *q, struct request *rq, struct bio *bio,
gfp_t gfp_mask)
{
struct row_data *rd = (struct row_data *)q->elevator->elevator_data;
unsigned long flags;
spin_lock_irqsave(q->queue_lock, flags);
rq->elv.priv[0] =
(void *)(&rd->row_queues[row_get_queue_prio(rq, rd)]);
spin_unlock_irqrestore(q->queue_lock, flags);
return 0;
}
/********** Helping sysfs functions/defenitions for ROW attributes ******/
static ssize_t row_var_show(int var, char *page)
{
return snprintf(page, 100, "%d\n", var);
}
static ssize_t row_var_store(int *var, const char *page, size_t count)
{
int err;
err = kstrtoul(page, 10, (unsigned long *)var);
return count;
}
#define SHOW_FUNCTION(__FUNC, __VAR) \
static ssize_t __FUNC(struct elevator_queue *e, char *page) \
{ \
struct row_data *rowd = e->elevator_data; \
int __data = __VAR; \
return row_var_show(__data, (page)); \
}
SHOW_FUNCTION(row_hp_read_quantum_show,
rowd->row_queues[ROWQ_PRIO_HIGH_READ].disp_quantum);
SHOW_FUNCTION(row_rp_read_quantum_show,
rowd->row_queues[ROWQ_PRIO_REG_READ].disp_quantum);
SHOW_FUNCTION(row_hp_swrite_quantum_show,
rowd->row_queues[ROWQ_PRIO_HIGH_SWRITE].disp_quantum);
SHOW_FUNCTION(row_rp_swrite_quantum_show,
rowd->row_queues[ROWQ_PRIO_REG_SWRITE].disp_quantum);
SHOW_FUNCTION(row_rp_write_quantum_show,
rowd->row_queues[ROWQ_PRIO_REG_WRITE].disp_quantum);
SHOW_FUNCTION(row_lp_read_quantum_show,
rowd->row_queues[ROWQ_PRIO_LOW_READ].disp_quantum);
SHOW_FUNCTION(row_lp_swrite_quantum_show,
rowd->row_queues[ROWQ_PRIO_LOW_SWRITE].disp_quantum);
SHOW_FUNCTION(row_rd_idle_data_show, rowd->rd_idle_data.idle_time_ms);
SHOW_FUNCTION(row_rd_idle_data_freq_show, rowd->rd_idle_data.freq_ms);
SHOW_FUNCTION(row_reg_starv_limit_show,
rowd->reg_prio_starvation.starvation_limit);
SHOW_FUNCTION(row_low_starv_limit_show,
rowd->low_prio_starvation.starvation_limit);
#undef SHOW_FUNCTION
#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX) \
static ssize_t __FUNC(struct elevator_queue *e, \
const char *page, size_t count) \
{ \
struct row_data *rowd = e->elevator_data; \
int __data; \
int ret = row_var_store(&__data, (page), count); \
if (__data < (MIN)) \
__data = (MIN); \
else if (__data > (MAX)) \
__data = (MAX); \
*(__PTR) = __data; \
return ret; \
}
STORE_FUNCTION(row_hp_read_quantum_store,
&rowd->row_queues[ROWQ_PRIO_HIGH_READ].disp_quantum, 1, INT_MAX);
STORE_FUNCTION(row_rp_read_quantum_store,
&rowd->row_queues[ROWQ_PRIO_REG_READ].disp_quantum,
1, INT_MAX);
STORE_FUNCTION(row_hp_swrite_quantum_store,
&rowd->row_queues[ROWQ_PRIO_HIGH_SWRITE].disp_quantum,
1, INT_MAX);
STORE_FUNCTION(row_rp_swrite_quantum_store,
&rowd->row_queues[ROWQ_PRIO_REG_SWRITE].disp_quantum,
1, INT_MAX);
STORE_FUNCTION(row_rp_write_quantum_store,
&rowd->row_queues[ROWQ_PRIO_REG_WRITE].disp_quantum,
1, INT_MAX);
STORE_FUNCTION(row_lp_read_quantum_store,
&rowd->row_queues[ROWQ_PRIO_LOW_READ].disp_quantum,
1, INT_MAX);
STORE_FUNCTION(row_lp_swrite_quantum_store,
&rowd->row_queues[ROWQ_PRIO_LOW_SWRITE].disp_quantum,
1, INT_MAX);
STORE_FUNCTION(row_rd_idle_data_store, &rowd->rd_idle_data.idle_time_ms,
1, INT_MAX);
STORE_FUNCTION(row_rd_idle_data_freq_store, &rowd->rd_idle_data.freq_ms,
1, INT_MAX);
STORE_FUNCTION(row_reg_starv_limit_store,
&rowd->reg_prio_starvation.starvation_limit,
1, INT_MAX);
STORE_FUNCTION(row_low_starv_limit_store,
&rowd->low_prio_starvation.starvation_limit,
1, INT_MAX);
#undef STORE_FUNCTION
#define ROW_ATTR(name) \
__ATTR(name, S_IRUGO|S_IWUSR, row_##name##_show, \
row_##name##_store)
static struct elv_fs_entry row_attrs[] = {
ROW_ATTR(hp_read_quantum),
ROW_ATTR(rp_read_quantum),
ROW_ATTR(hp_swrite_quantum),
ROW_ATTR(rp_swrite_quantum),
ROW_ATTR(rp_write_quantum),
ROW_ATTR(lp_read_quantum),
ROW_ATTR(lp_swrite_quantum),
ROW_ATTR(rd_idle_data),
ROW_ATTR(rd_idle_data_freq),
ROW_ATTR(reg_starv_limit),
ROW_ATTR(low_starv_limit),
__ATTR_NULL
};
static struct elevator_type iosched_row = {
.ops = {
.elevator_merge_req_fn = row_merged_requests,
.elevator_dispatch_fn = row_dispatch_requests,
.elevator_add_req_fn = row_add_request,
.elevator_reinsert_req_fn = row_reinsert_req,
.elevator_is_urgent_fn = row_urgent_pending,
.elevator_completed_req_fn = row_completed_req,
.elevator_former_req_fn = elv_rb_former_request,
.elevator_latter_req_fn = elv_rb_latter_request,
.elevator_set_req_fn = row_set_request,
.elevator_init_fn = row_init_queue,
.elevator_exit_fn = row_exit_queue,
},
.icq_size = sizeof(struct io_cq),
.icq_align = __alignof__(struct io_cq),
.elevator_attrs = row_attrs,
.elevator_name = "row",
.elevator_owner = THIS_MODULE,
};
static int __init row_init(void)
{
elv_register(&iosched_row);
return 0;
}
static void __exit row_exit(void)
{
elv_unregister(&iosched_row);
}
module_init(row_init);
module_exit(row_exit);
MODULE_LICENSE("GPLv2");
MODULE_DESCRIPTION("Read Over Write IO scheduler");