Re: [RFC 2/3]block: FIOPS ioscheduler core

From: Zhu Yanhai
Date: Fri Jan 06 2012 - 20:06:55 EST

Next message: Yinghai Lu: "Re: [git pull] PCI fixes"
Previous message: Mark Brown: "Re: [PATCH v8 2/2] davinci: CQ93VC: remove machine specific headerfile inclusion from codec driver"
In reply to: Namjae Jeon: "Re: [RFC 2/3]block: FIOPS ioscheduler core"
Next in thread: Dave Chinner: "Re: [RFC 0/3]block: An IOPS based ioscheduler"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

2012/1/4 Shaohua Li <shaohua.li@xxxxxxxxx>:
> FIOPS (Fair IOPS) ioscheduler is IOPS based ioscheduler, so only targets
> for drive without I/O seek. It's quite similar like CFQ, but the dispatch
> decision is made according to IOPS instead of slice.
>
> The algorithm is simple. Drive has a service tree, and each task lives in
> the tree. The key into the tree is called vios (virtual I/O). Every request
> has vios, which is calculated according to its ioprio, request size and so
> on. Task's vios is the sum of vios of all requests it dispatches. FIOPS
> always selects task with minimum vios in the service tree and let the task
> dispatch request. The dispatched request's vios is then added to the task's
> vios and the task is repositioned in the sevice tree.
>
> Unlike CFQ, FIOPS doesn't have separate sync/async queues, because with I/O
> less writeback, usually a task can only dispatch either sync or async requests.
> Bias read or write request can still be done with read/write scale.
>
> One issue is if workload iodepth is lower than drive queue_depth, IOPS
> share of a task might not be strictly according to its priority, request
> size and so on. In this case, the drive is in idle actually. Solving the
> problem need make drive idle, so impact performance. I believe CFQ isn't
> completely fair between tasks in such case too.
>
> Signed-off-by: Shaohua Li <shaohua.li@xxxxxxxxx>
> ---
> Âblock/Kconfig.iosched | Â Â8
> Âblock/Makefile Â Â Â Â| Â Â1
> Âblock/blk-ioc.c Â Â Â | Â Â2
> Âblock/blk.h Â Â Â Â Â | Â Â2
> Âblock/fiops-iosched.c | Â659 ++++++++++++++++++++++++++++++++++++++++++++++++++
> Â5 files changed, 670 insertions(+), 2 deletions(-)
>
> Index: linux/block/Makefile
> ===================================================================
> --- linux.orig/block/Makefile Â 2011-12-28 09:42:18.000000000 +0800
> +++ linux/block/Makefile Â Â Â Â2011-12-28 09:42:35.000000000 +0800
> @@ -14,6 +14,7 @@ obj-$(CONFIG_BLK_DEV_THROTTLING) Â Â Â+= blk-
> Âobj-$(CONFIG_IOSCHED_NOOP) Â Â += noop-iosched.o
> Âobj-$(CONFIG_IOSCHED_DEADLINE) += deadline-iosched.o
> Âobj-$(CONFIG_IOSCHED_CFQ) Â Â Â+= cfq-iosched.o
> +obj-$(CONFIG_IOSCHED_FIOPS) Â Â+= fiops-iosched.o
>
> Âobj-$(CONFIG_BLOCK_COMPAT) Â Â += compat_ioctl.o
> Âobj-$(CONFIG_BLK_DEV_INTEGRITY) Â Â Â Â+= blk-integrity.o
> Index: linux/block/fiops-iosched.c
> ===================================================================
> --- /dev/null Â 1970-01-01 00:00:00.000000000 +0000
> +++ linux/block/fiops-iosched.c 2012-01-04 14:01:26.000000000 +0800
> @@ -0,0 +1,659 @@
> +/*
> + * IOPS based IO scheduler. Based on CFQ.
> + * ÂCopyright (C) 2003 Jens Axboe <axboe@xxxxxxxxx>
> + * ÂShaohua Li <shli@xxxxxxxxxx>
> + */
> +#include <linux/module.h>
> +#include <linux/slab.h>
> +#include <linux/blkdev.h>
> +#include <linux/elevator.h>
> +#include <linux/jiffies.h>
> +#include <linux/rbtree.h>
> +#include <linux/ioprio.h>
> +#include "blk.h"
> +
> +#define VIOS_SCALE_SHIFT 10
> +#define VIOS_SCALE (1 << VIOS_SCALE_SHIFT)
> +
> +struct fiops_rb_root {
> + Â Â Â struct rb_root rb;
> + Â Â Â struct rb_node *left;
> + Â Â Â unsigned count;
> +
> + Â Â Â u64 min_vios;
> +};
> +#define FIOPS_RB_ROOT Â(struct fiops_rb_root) { .rb = RB_ROOT}
> +
> +struct fiops_data {
> + Â Â Â struct queue_data qdata;
> +
> + Â Â Â struct fiops_rb_root service_tree;
> +
> + Â Â Â unsigned int busy_queues;
> +
> + Â Â Â struct work_struct unplug_work;
> +};
> +
> +struct fiops_ioc {
> + Â Â Â struct dev_io_context dev_ioc;
> +
> + Â Â Â unsigned int flags;
> + Â Â Â struct fiops_data *fiopsd;
> + Â Â Â struct rb_node rb_node;
> + Â Â Â u64 vios; /* key in service_tree */
> + Â Â Â struct fiops_rb_root *service_tree;
> +
> + Â Â Â struct rb_root sort_list;
> + Â Â Â struct list_head fifo;
> +
> + Â Â Â pid_t pid;
> +};
> +
> +static struct kmem_cache *fiops_ioc_pool;
> +static struct ioc_builder ioc_builder;
> +#define queue_data_to_fiopsd(ptr) container_of(ptr, struct fiops_data, qdata)
> +#define dev_ioc_to_fiops_ioc(ptr) container_of(ptr, struct fiops_ioc, dev_ioc)
> +#define ioc_service_tree(ioc) (&((ioc)->fiopsd->service_tree))
> +
> +#define RQ_CIC(rq) Â Â Â Â Â Â \
> + Â Â Â ((struct fiops_ioc *) (rq)->elevator_private[0])
> +enum ioc_state_flags {
> + Â Â Â FIOPS_IOC_FLAG_on_rr = 0, Â Â Â /* on round-robin busy list */
> +};
> +
> +#define FIOPS_IOC_FNS(name) Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +static inline void fiops_mark_ioc_##name(struct fiops_ioc *ioc) Â Â Â Â\
> +{ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â ioc->flags |= (1 << FIOPS_IOC_FLAG_##name); Â Â Â Â Â Â Â Â Â Â \
> +} Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +static inline void fiops_clear_ioc_##name(struct fiops_ioc *ioc) Â Â Â \
> +{ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â ioc->flags &= ~(1 << FIOPS_IOC_FLAG_##name); Â Â Â Â Â Â Â Â Â Â\
> +} Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> +static inline int fiops_ioc_##name(const struct fiops_ioc *ioc) Â Â Â Â\
> +{ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â\
> + Â Â Â return ((ioc)->flags & (1 << FIOPS_IOC_FLAG_##name)) != 0; Â Â Â\
> +}
> +
> +FIOPS_IOC_FNS(on_rr);
> +#undef FIOPS_IOC_FNS
> +
> +/*
> + * The below is leftmost cache rbtree addon
> + */
> +static struct fiops_ioc *fiops_rb_first(struct fiops_rb_root *root)
> +{
> + Â Â Â /* Service tree is empty */
> + Â Â Â if (!root->count)
> + Â Â Â Â Â Â Â return NULL;
> +
> + Â Â Â if (!root->left)
> + Â Â Â Â Â Â Â root->left = rb_first(&root->rb);
> +
> + Â Â Â if (root->left)
> + Â Â Â Â Â Â Â return rb_entry(root->left, struct fiops_ioc, rb_node);
> +
> + Â Â Â return NULL;
> +}
> +
> +static void rb_erase_init(struct rb_node *n, struct rb_root *root)
> +{
> + Â Â Â rb_erase(n, root);
> + Â Â Â RB_CLEAR_NODE(n);
> +}
> +
> +static void fiops_rb_erase(struct rb_node *n, struct fiops_rb_root *root)
> +{
> + Â Â Â if (root->left == n)
> + Â Â Â Â Â Â Â root->left = NULL;
> + Â Â Â rb_erase_init(n, &root->rb);
> + Â Â Â --root->count;
> +}
> +
> +static inline u64 max_vios(u64 min_vios, u64 vios)
> +{
> + Â Â Â s64 delta = (s64)(vios - min_vios);
> + Â Â Â if (delta > 0)
> + Â Â Â Â Â Â Â min_vios = vios;
> +
> + Â Â Â return min_vios;
> +}
> +
> +static void fiops_update_min_vios(struct fiops_rb_root *service_tree)
> +{
> + Â Â Â struct fiops_ioc *ioc;
> +
> + Â Â Â ioc = fiops_rb_first(service_tree);
> + Â Â Â if (!ioc)
> + Â Â Â Â Â Â Â return;
> + Â Â Â service_tree->min_vios = max_vios(service_tree->min_vios, ioc->vios);
This is tracking the max vios here, not the min one. Should be min_vios()?
> +}
> +
> +/*
> + * The fiopsd->service_trees holds all pending fiops_ioc's that have
> + * requests waiting to be processed. It is sorted in the order that
> + * we will service the queues.
> + */
> +static void fiops_service_tree_add(struct fiops_data *fiopsd,
> + Â Â Â struct fiops_ioc *ioc)
> +{
> + Â Â Â struct rb_node **p, *parent;
> + Â Â Â struct fiops_ioc *__ioc;
> + Â Â Â struct fiops_rb_root *service_tree = ioc_service_tree(ioc);
> + Â Â Â u64 vios;
> + Â Â Â int left;
> +
> + Â Â Â /* New added IOC */
> + Â Â Â if (RB_EMPTY_NODE(&ioc->rb_node))
> + Â Â Â Â Â Â Â vios = max_vios(service_tree->min_vios, ioc->vios);
> + Â Â Â else {
> + Â Â Â Â Â Â Â vios = ioc->vios;
> + Â Â Â Â Â Â Â /* ioc->service_tree might not equal to service_tree */
> + Â Â Â Â Â Â Â fiops_rb_erase(&ioc->rb_node, ioc->service_tree);
> + Â Â Â Â Â Â Â ioc->service_tree = NULL;
> + Â Â Â }
> +
> + Â Â Â left = 1;
> + Â Â Â parent = NULL;
> + Â Â Â ioc->service_tree = service_tree;
> + Â Â Â p = &service_tree->rb.rb_node;
> + Â Â Â while (*p) {
> + Â Â Â Â Â Â Â struct rb_node **n;
> +
> + Â Â Â Â Â Â Â parent = *p;
> + Â Â Â Â Â Â Â __ioc = rb_entry(parent, struct fiops_ioc, rb_node);
> +
> + Â Â Â Â Â Â Â /*
> + Â Â Â Â Â Â Â Â* sort by key, that represents service time.
> + Â Â Â Â Â Â Â Â*/
> + Â Â Â Â Â Â Â if (vios < Â__ioc->vios)
> + Â Â Â Â Â Â Â Â Â Â Â n = &(*p)->rb_left;
> + Â Â Â Â Â Â Â else {
> + Â Â Â Â Â Â Â Â Â Â Â n = &(*p)->rb_right;
> + Â Â Â Â Â Â Â Â Â Â Â left = 0;
> + Â Â Â Â Â Â Â }
> +
> + Â Â Â Â Â Â Â p = n;
> + Â Â Â }
> +
> + Â Â Â if (left)
> + Â Â Â Â Â Â Â service_tree->left = &ioc->rb_node;
> +
> + Â Â Â ioc->vios = vios;
> + Â Â Â rb_link_node(&ioc->rb_node, parent, p);
> + Â Â Â rb_insert_color(&ioc->rb_node, &service_tree->rb);
> + Â Â Â service_tree->count++;
> +
> + Â Â Â fiops_update_min_vios(service_tree);
> +}
> +
> +/*
> + * Update ioc's position in the service tree.
> + */
> +static void fiops_resort_rr_list(struct fiops_data *fiopsd,
> + Â Â Â struct fiops_ioc *ioc)
> +{
> + Â Â Â /*
> + Â Â Â Â* Resorting requires the ioc to be on the RR list already.
> + Â Â Â Â*/
> + Â Â Â if (fiops_ioc_on_rr(ioc))
> + Â Â Â Â Â Â Â fiops_service_tree_add(fiopsd, ioc);
> +}
> +
> +/*
> + * add to busy list of queues for service, trying to be fair in ordering
> + * the pending list according to last request service
> + */
> +static void fiops_add_ioc_rr(struct fiops_data *fiopsd, struct fiops_ioc *ioc)
> +{
> + Â Â Â BUG_ON(fiops_ioc_on_rr(ioc));
> + Â Â Â fiops_mark_ioc_on_rr(ioc);
> +
> + Â Â Â fiopsd->busy_queues++;
> +
> + Â Â Â fiops_resort_rr_list(fiopsd, ioc);
> +}
> +
> +/*
> + * Called when the ioc no longer has requests pending, remove it from
> + * the service tree.
> + */
> +static void fiops_del_ioc_rr(struct fiops_data *fiopsd, struct fiops_ioc *ioc)
> +{
> + Â Â Â BUG_ON(!fiops_ioc_on_rr(ioc));
> + Â Â Â fiops_clear_ioc_on_rr(ioc);
> +
> + Â Â Â if (!RB_EMPTY_NODE(&ioc->rb_node)) {
> + Â Â Â Â Â Â Â fiops_rb_erase(&ioc->rb_node, ioc->service_tree);
> + Â Â Â Â Â Â Â ioc->service_tree = NULL;
> + Â Â Â }
> +
> + Â Â Â BUG_ON(!fiopsd->busy_queues);
> + Â Â Â fiopsd->busy_queues--;
> +}
> +
> +/*
> + * rb tree support functions
> + */
> +static void fiops_del_rq_rb(struct request *rq)
> +{
> + Â Â Â struct fiops_ioc *ioc = RQ_CIC(rq);
> +
> + Â Â Â elv_rb_del(&ioc->sort_list, rq);
> +}
> +
> +static void fiops_add_rq_rb(struct request *rq)
> +{
> + Â Â Â struct fiops_ioc *ioc = RQ_CIC(rq);
> + Â Â Â struct fiops_data *fiopsd = ioc->fiopsd;
> +
> + Â Â Â elv_rb_add(&ioc->sort_list, rq);
> +
> + Â Â Â if (!fiops_ioc_on_rr(ioc))
> + Â Â Â Â Â Â Â fiops_add_ioc_rr(fiopsd, ioc);
> +}
> +
> +static void fiops_reposition_rq_rb(struct fiops_ioc *ioc, struct request *rq)
> +{
> + Â Â Â elv_rb_del(&ioc->sort_list, rq);
> + Â Â Â fiops_add_rq_rb(rq);
> +}
> +
> +static void fiops_remove_request(struct request *rq)
> +{
> + Â Â Â list_del_init(&rq->queuelist);
> + Â Â Â fiops_del_rq_rb(rq);
> +}
> +
> +static u64 fiops_scaled_vios(struct fiops_data *fiopsd,
> + Â Â Â struct fiops_ioc *ioc, struct request *rq)
> +{
> + Â Â Â return VIOS_SCALE;
> +}
> +
> +/* return vios dispatched */
> +static u64 fiops_dispatch_request(struct fiops_data *fiopsd,
> + Â Â Â struct fiops_ioc *ioc)
> +{
> + Â Â Â struct request *rq;
> + Â Â Â struct request_queue *q = fiopsd->qdata.queue;
> +
> + Â Â Â rq = rq_entry_fifo(ioc->fifo.next);
> +
> + Â Â Â fiops_remove_request(rq);
> + Â Â Â elv_dispatch_sort(q, rq);
> +
> + Â Â Â return fiops_scaled_vios(fiopsd, ioc, rq);
> +}
> +
> +static int fiops_forced_dispatch(struct fiops_data *fiopsd)
> +{
> + Â Â Â struct fiops_ioc *ioc;
> + Â Â Â int dispatched = 0;
> +
> + Â Â Â while ((ioc = fiops_rb_first(&fiopsd->service_tree)) != NULL) {
> + Â Â Â Â Â Â Â while (!list_empty(&ioc->fifo)) {
> + Â Â Â Â Â Â Â Â Â Â Â fiops_dispatch_request(fiopsd, ioc);
> + Â Â Â Â Â Â Â Â Â Â Â dispatched++;
> + Â Â Â Â Â Â Â }
> + Â Â Â Â Â Â Â if (fiops_ioc_on_rr(ioc))
> + Â Â Â Â Â Â Â Â Â Â Â fiops_del_ioc_rr(fiopsd, ioc);
> + Â Â Â }
> + Â Â Â return dispatched;
> +}
> +
> +static struct fiops_ioc *fiops_select_ioc(struct fiops_data *fiopsd)
> +{
> + Â Â Â struct fiops_ioc *ioc;
> +
> + Â Â Â if (RB_EMPTY_ROOT(&fiopsd->service_tree.rb))
> + Â Â Â Â Â Â Â return NULL;
> + Â Â Â ioc = fiops_rb_first(&fiopsd->service_tree);
> + Â Â Â return ioc;
> +}
> +
> +static void fiops_charge_vios(struct fiops_data *fiopsd,
> + Â Â Â struct fiops_ioc *ioc, u64 vios)
> +{
> + Â Â Â struct fiops_rb_root *service_tree = ioc->service_tree;
> + Â Â Â ioc->vios += vios;
> +
> + Â Â Â if (RB_EMPTY_ROOT(&ioc->sort_list))
> + Â Â Â Â Â Â Â fiops_del_ioc_rr(fiopsd, ioc);
> + Â Â Â else
> + Â Â Â Â Â Â Â fiops_resort_rr_list(fiopsd, ioc);
> +
> + Â Â Â fiops_update_min_vios(service_tree);
> +}
> +
> +static int fiops_dispatch_requests(struct request_queue *q, int force)
> +{
> + Â Â Â struct fiops_data *fiopsd = q->elevator->elevator_data;
> + Â Â Â struct fiops_ioc *ioc;
> + Â Â Â u64 vios;
> +
> + Â Â Â if (unlikely(force))
> + Â Â Â Â Â Â Â return fiops_forced_dispatch(fiopsd);
> +
> + Â Â Â ioc = fiops_select_ioc(fiopsd);
> + Â Â Â if (!ioc)
> + Â Â Â Â Â Â Â return 0;
> +
> + Â Â Â vios = fiops_dispatch_request(fiopsd, ioc);
> +
> + Â Â Â fiops_charge_vios(fiopsd, ioc, vios);
> + Â Â Â return 1;
> +}
> +
> +static void fiops_insert_request(struct request_queue *q, struct request *rq)
> +{
> + Â Â Â struct fiops_ioc *ioc = RQ_CIC(rq);
> +
> + Â Â Â rq_set_fifo_time(rq, jiffies);
> +
> + Â Â Â list_add_tail(&rq->queuelist, &ioc->fifo);
> +
> + Â Â Â fiops_add_rq_rb(rq);
> +}
> +
> +/*
> + * scheduler run of queue, if there are requests pending and no one in the
> + * driver that will restart queueing
> + */
> +static inline void fiops_schedule_dispatch(struct fiops_data *fiopsd)
> +{
> + Â Â Â if (fiopsd->busy_queues)
> + Â Â Â Â Â Â Â kblockd_schedule_work(fiopsd->qdata.queue,
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â &fiopsd->unplug_work);
> +}
> +
> +static int
> +fiops_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
> +{
> + Â Â Â struct fiops_data *fiopsd = q->elevator->elevator_data;
> + Â Â Â struct dev_io_context *dev_ioc;
> + Â Â Â struct fiops_ioc *cic;
> +
> + Â Â Â might_sleep_if(gfp_mask & __GFP_WAIT);
> +
> + Â Â Â dev_ioc = queue_data_get_io_context(&ioc_builder, &fiopsd->qdata,
> + Â Â Â Â Â Â Â gfp_mask);
> + Â Â Â if (!dev_ioc)
> + Â Â Â Â Â Â Â goto queue_fail;
> +
> + Â Â Â cic = dev_ioc_to_fiops_ioc(dev_ioc);
> +
> + Â Â Â /*
> + Â Â Â Â* we hold a reference of dev_ioc and nobody else set this request,
> + Â Â Â Â* doesn't need locking
> + Â Â Â Â*/
> + Â Â Â rq->elevator_private[0] = cic;
> +
> + Â Â Â return 0;
> +
> +queue_fail:
> + Â Â Â fiops_schedule_dispatch(fiopsd);
> + Â Â Â return 1;
> +}
> +
> +static void fiops_put_request(struct request *rq)
> +{
> + Â Â Â struct fiops_ioc *ioc = RQ_CIC(rq);
> +
> + Â Â Â if (ioc) {
> + Â Â Â Â Â Â Â rq->elevator_private[0] = NULL;
> + Â Â Â Â Â Â Â put_io_context(ioc->dev_ioc.ioc);
> + Â Â Â }
> +}
> +
> +static struct request *
> +fiops_find_rq_fmerge(struct fiops_data *fiopsd, struct bio *bio)
> +{
> + Â Â Â struct task_struct *tsk = current;
> + Â Â Â struct dev_io_context *gen_cic;
> + Â Â Â struct fiops_ioc *cic;
> +
> + Â Â Â gen_cic = queue_data_cic_lookup(&fiopsd->qdata, tsk->io_context);
> + Â Â Â if (!gen_cic)
> + Â Â Â Â Â Â Â return NULL;
> + Â Â Â cic = dev_ioc_to_fiops_ioc(gen_cic);
> +
> + Â Â Â if (cic) {
> + Â Â Â Â Â Â Â sector_t sector = bio->bi_sector + bio_sectors(bio);
> +
> + Â Â Â Â Â Â Â return elv_rb_find(&cic->sort_list, sector);
> + Â Â Â }
> +
> + Â Â Â return NULL;
> +}
> +
> +static int fiops_merge(struct request_queue *q, struct request **req,
> + Â Â Â Â Â Â Â Â Â Âstruct bio *bio)
> +{
> + Â Â Â struct fiops_data *fiopsd = q->elevator->elevator_data;
> + Â Â Â struct request *__rq;
> +
> + Â Â Â __rq = fiops_find_rq_fmerge(fiopsd, bio);
> + Â Â Â if (__rq && elv_rq_merge_ok(__rq, bio)) {
> + Â Â Â Â Â Â Â *req = __rq;
> + Â Â Â Â Â Â Â return ELEVATOR_FRONT_MERGE;
> + Â Â Â }
> +
> + Â Â Â return ELEVATOR_NO_MERGE;
> +}
> +
> +static void fiops_merged_request(struct request_queue *q, struct request *req,
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Âint type)
> +{
> + Â Â Â if (type == ELEVATOR_FRONT_MERGE) {
> + Â Â Â Â Â Â Â struct fiops_ioc *ioc = RQ_CIC(req);
> +
> + Â Â Â Â Â Â Â fiops_reposition_rq_rb(ioc, req);
> + Â Â Â }
> +}
> +
> +static void
> +fiops_merged_requests(struct request_queue *q, struct request *rq,
> + Â Â Â Â Â Â Â Â Â struct request *next)
> +{
> + Â Â Â struct fiops_ioc *ioc = RQ_CIC(rq);
> + Â Â Â struct fiops_data *fiopsd = q->elevator->elevator_data;
> + Â Â Â /*
> + Â Â Â Â* reposition in fifo if next is older than rq
> + Â Â Â Â*/
> + Â Â Â if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
> + Â Â Â Â Â time_before(rq_fifo_time(next), rq_fifo_time(rq))) {
> + Â Â Â Â Â Â Â list_move(&rq->queuelist, &next->queuelist);
> + Â Â Â Â Â Â Â rq_set_fifo_time(rq, rq_fifo_time(next));
> + Â Â Â }
> +
> + Â Â Â fiops_remove_request(next);
> +
> + Â Â Â ioc = RQ_CIC(next);
> + Â Â Â /*
> + Â Â Â Â* all requests of this task are merged to other tasks, delete it
> + Â Â Â Â* from the service tree.
> + Â Â Â Â*/
> + Â Â Â if (fiops_ioc_on_rr(ioc) && RB_EMPTY_ROOT(&ioc->sort_list))
> + Â Â Â Â Â Â Â fiops_del_ioc_rr(fiopsd, ioc);
> +}
> +
> +static int fiops_allow_merge(struct request_queue *q, struct request *rq,
> + Â Â Â Â Â Â Â Â Â Â Â Â Âstruct bio *bio)
> +{
> + Â Â Â struct fiops_data *fiopsd = q->elevator->elevator_data;
> + Â Â Â struct dev_io_context *gen_cic;
> + Â Â Â struct fiops_ioc *cic;
> +
> + Â Â Â /*
> + Â Â Â Â* Lookup the ioc that this bio will be queued with. Allow
> + Â Â Â Â* merge only if rq is queued there.
> + Â Â Â Â*/
> + Â Â Â gen_cic = queue_data_cic_lookup(&fiopsd->qdata, current->io_context);
> + Â Â Â if (!gen_cic)
> + Â Â Â Â Â Â Â return false;
> + Â Â Â cic = dev_ioc_to_fiops_ioc(gen_cic);
> +
> + Â Â Â return cic == RQ_CIC(rq);
> +}
> +
> +static void fiops_exit_queue(struct elevator_queue *e)
> +{
> + Â Â Â struct fiops_data *fiopsd = e->elevator_data;
> + Â Â Â struct request_queue *q = fiopsd->qdata.queue;
> +
> + Â Â Â cancel_work_sync(&fiopsd->unplug_work);
> +
> + Â Â Â spin_lock_irq(q->queue_lock);
> +
> + Â Â Â ioc_builder_exit_queue(&ioc_builder, &fiopsd->qdata);
> +
> + Â Â Â spin_unlock_irq(q->queue_lock);
> + Â Â Â kfree(fiopsd);
> +}
> +
> +static void fiops_kick_queue(struct work_struct *work)
> +{
> + Â Â Â struct fiops_data *fiopsd =
> + Â Â Â Â Â Â Â container_of(work, struct fiops_data, unplug_work);
> + Â Â Â struct request_queue *q = fiopsd->qdata.queue;
> +
> + Â Â Â spin_lock_irq(q->queue_lock);
> + Â Â Â __blk_run_queue(q);
> + Â Â Â spin_unlock_irq(q->queue_lock);
> +}
> +
> +static void *fiops_init_queue(struct request_queue *q)
> +{
> + Â Â Â struct fiops_data *fiopsd;
> +
> + Â Â Â fiopsd = kzalloc_node(sizeof(*fiopsd), GFP_KERNEL, q->node);
> + Â Â Â if (!fiopsd)
> + Â Â Â Â Â Â Â return NULL;
> +
> + Â Â Â if (ioc_builder_init_queue(&ioc_builder, &fiopsd->qdata, q)) {
> + Â Â Â Â Â Â Â kfree(fiopsd);
> + Â Â Â Â Â Â Â return NULL;
> + Â Â Â }
> +
> + Â Â Â fiopsd->service_tree = FIOPS_RB_ROOT;
> +
> + Â Â Â INIT_WORK(&fiopsd->unplug_work, fiops_kick_queue);
> +
> + Â Â Â return fiopsd;
> +}
> +
> +static void fiops_slab_kill(void)
> +{
> + Â Â Â /*
> + Â Â Â Â* Caller already ensured that pending RCU callbacks are completed,
> + Â Â Â Â* so we should have no busy allocations at this point.
> + Â Â Â Â*/
> + Â Â Â if (fiops_ioc_pool)
> + Â Â Â Â Â Â Â kmem_cache_destroy(fiops_ioc_pool);
> +}
> +
> +static int __init fiops_slab_setup(void)
> +{
> + Â Â Â fiops_ioc_pool = KMEM_CACHE(fiops_ioc, 0);
> + Â Â Â if (!fiops_ioc_pool)
> + Â Â Â Â Â Â Â return -ENOMEM;
> +
> + Â Â Â return 0;
> +}
> +
> +static struct dev_io_context *
> +fiops_alloc_ioc(struct ioc_builder *builder, struct queue_data *qdata,
> + Â Â Â gfp_t gfp_mask)
> +{
> + Â Â Â struct fiops_ioc *ioc = kmem_cache_alloc_node(fiops_ioc_pool,
> + Â Â Â Â Â Â Â gfp_mask, qdata->queue->node);
> + Â Â Â if (ioc)
> + Â Â Â Â Â Â Â return &ioc->dev_ioc;
> + Â Â Â return NULL;
> +}
> +
> +static void fiops_free_ioc(struct ioc_builder *builder,
> + Â Â Â struct dev_io_context *dev_ioc)
> +{
> + Â Â Â struct fiops_ioc *ioc = dev_ioc_to_fiops_ioc(dev_ioc);
> + Â Â Â kmem_cache_free(fiops_ioc_pool, ioc);
> +}
> +
> +static void fiops_init_cic(struct queue_data *qdata,
> + Â Â Â struct dev_io_context *gen_cic)
> +{
> + Â Â Â struct fiops_data *fiopsd = queue_data_to_fiopsd(qdata);
> + Â Â Â struct fiops_ioc *ioc = dev_ioc_to_fiops_ioc(gen_cic);
> +
> + Â Â Â RB_CLEAR_NODE(&ioc->rb_node);
> + Â Â Â INIT_LIST_HEAD(&ioc->fifo);
> + Â Â Â ioc->sort_list = RB_ROOT;
> +
> + Â Â Â ioc->fiopsd = fiopsd;
> +
> + Â Â Â ioc->pid = current->pid;
> +}
> +
> +static void fiops_exit_cic(struct queue_data *qdata,
> + Â Â Â struct dev_io_context *gen_cic)
> +{
> + Â Â Â struct fiops_ioc *ioc = dev_ioc_to_fiops_ioc(gen_cic);
> +
> + Â Â Â WARN_ON(fiops_ioc_on_rr(ioc));
> +}
> +
> +static struct ioc_builder ioc_builder = {
> + Â Â Â .alloc_ioc = fiops_alloc_ioc,
> + Â Â Â .free_ioc = fiops_free_ioc,
> + Â Â Â .cic_init = fiops_init_cic,
> + Â Â Â .cic_exit = fiops_exit_cic,
> +};
> +
> +static struct elevator_type iosched_fiops = {
> + Â Â Â .ops = {
> + Â Â Â Â Â Â Â .elevator_merge_fn = Â Â Â Â Â Âfiops_merge,
> + Â Â Â Â Â Â Â .elevator_merged_fn = Â Â Â Â Â fiops_merged_request,
> + Â Â Â Â Â Â Â .elevator_merge_req_fn = Â Â Â Âfiops_merged_requests,
> + Â Â Â Â Â Â Â .elevator_allow_merge_fn = Â Â Âfiops_allow_merge,
> + Â Â Â Â Â Â Â .elevator_dispatch_fn = Â Â Â Â fiops_dispatch_requests,
> + Â Â Â Â Â Â Â .elevator_add_req_fn = Â Â Â Â Âfiops_insert_request,
> + Â Â Â Â Â Â Â .elevator_former_req_fn = Â Â Â elv_rb_former_request,
> + Â Â Â Â Â Â Â .elevator_latter_req_fn = Â Â Â elv_rb_latter_request,
> + Â Â Â Â Â Â Â .elevator_set_req_fn = Â Â Â Â Âfiops_set_request,
> + Â Â Â Â Â Â Â .elevator_put_req_fn = Â Â Â Â Âfiops_put_request,
> + Â Â Â Â Â Â Â .elevator_init_fn = Â Â Â Â Â Â fiops_init_queue,
> + Â Â Â Â Â Â Â .elevator_exit_fn = Â Â Â Â Â Â fiops_exit_queue,
> + Â Â Â Â Â Â Â .trim = Â Â Â Â Â Â Â Â Â Â Â Â queue_data_free_io_context,
> + Â Â Â },
> + Â Â Â .elevator_name = Â Â Â Â"fiops",
> + Â Â Â .elevator_owner = Â Â Â THIS_MODULE,
> +};
> +
> +static int __init fiops_init(void)
> +{
> + Â Â Â if (fiops_slab_setup())
> + Â Â Â Â Â Â Â return -ENOMEM;
> + Â Â Â if (ioc_builder_init(&ioc_builder)) {
> + Â Â Â Â Â Â Â fiops_slab_kill();
> + Â Â Â Â Â Â Â return -ENOMEM;
> + Â Â Â }
> +
> + Â Â Â elv_register(&iosched_fiops);
> +
> + Â Â Â return 0;
> +}
> +
> +static void __exit fiops_exit(void)
> +{
> + Â Â Â elv_unregister(&iosched_fiops);
> + Â Â Â io_context_builder_exit(&ioc_builder);
> + Â Â Â fiops_slab_kill();
> +}
> +
> +module_init(fiops_init);
> +module_exit(fiops_exit);
> +
> +MODULE_AUTHOR("Jens Axboe, Shaohua Li <shli@xxxxxxxxxx>");
> +MODULE_LICENSE("GPL");
> +MODULE_DESCRIPTION("IOPS based IO scheduler");
> Index: linux/block/Kconfig.iosched
> ===================================================================
> --- linux.orig/block/Kconfig.iosched Â Â2011-12-28 09:42:18.000000000 +0800
> +++ linux/block/Kconfig.iosched 2012-01-04 13:58:35.000000000 +0800
> @@ -43,6 +43,14 @@ config CFQ_GROUP_IOSCHED
> Â Â Â Â---help---
> Â Â Â Â ÂEnable group IO scheduling in CFQ.
>
> +config IOSCHED_FIOPS
> + Â Â Â tristate "IOPS based I/O scheduler"
> + Â Â Â default y
> + Â Â Â ---help---
> + Â Â Â Â This is an IOPS based I/O scheduler. It will try to distribute
> + Â Â Â Â ÂIOPS equally among all processes in the system. It's mainly for
> + Â Â Â Â ÂFlash based storage.
> +
> Âchoice
> Â Â Â Âprompt "Default I/O scheduler"
> Â Â Â Âdefault DEFAULT_CFQ
> Index: linux/block/blk.h
> ===================================================================
> --- linux.orig/block/blk.h Â Â Â2011-12-28 09:42:18.000000000 +0800
> +++ linux/block/blk.h Â 2011-12-28 09:42:35.000000000 +0800
> @@ -206,7 +206,7 @@ static inline void blk_throtl_exit(struc
> Âstatic inline void blk_throtl_release(struct request_queue *q) { }
> Â#endif /* CONFIG_BLK_DEV_THROTTLING */
>
> -#if IS_ENABLED(CONFIG_IOSCHED_CFQ)
> +#if IS_ENABLED(CONFIG_IOSCHED_CFQ) || IS_ENABLED(CONFIG_IOSCHED_FIOPS)
> Âstruct queue_data;
> Âstruct ioc_builder {
> Â Â Â Âstruct dev_io_context *(*alloc_ioc)(struct ioc_builder *builder,
> Index: linux/block/blk-ioc.c
> ===================================================================
> --- linux.orig/block/blk-ioc.c Â2011-12-28 09:42:18.000000000 +0800
> +++ linux/block/blk-ioc.c Â Â Â 2011-12-28 09:42:35.000000000 +0800
> @@ -164,7 +164,7 @@ static int __init blk_ioc_init(void)
> Â}
> Âsubsys_initcall(blk_ioc_init);
>
> -#if IS_ENABLED(CONFIG_IOSCHED_CFQ)
> +#if IS_ENABLED(CONFIG_IOSCHED_CFQ) || IS_ENABLED(CONFIG_IOSCHED_FIOPS)
> Â#define CIC_DEAD_INDEX_SHIFT Â 1
>
> Âstatic inline void *queue_data_dead_key(struct queue_data *qdata)
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at Âhttp://vger.kernel.org/majordomo-info.html
> Please read the FAQ at Âhttp://www.tux.org/lkml/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Next message: Yinghai Lu: "Re: [git pull] PCI fixes"
Previous message: Mark Brown: "Re: [PATCH v8 2/2] davinci: CQ93VC: remove machine specific headerfile inclusion from codec driver"
In reply to: Namjae Jeon: "Re: [RFC 2/3]block: FIOPS ioscheduler core"
Next in thread: Dave Chinner: "Re: [RFC 0/3]block: An IOPS based ioscheduler"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]