cfq: request-deadline policy
Subsystems (2)
RFC PATCH 1/2 cfq: request-deadline policy
CFQ is designed for sharing disk bandwidth proportionally between queues and groups and for reordering requests to reduce disks seek time. Currently it cannot gurantee or estimate latency for individual requests, even if latencies are low for almost all requests, some of them can stuck inside scheduler for a long time. The fair policy is good as long as someone luckless begins to die due to a timeout.
This patch implements fifo requests dispatching with deadline policy: now cfq obliged to dispatch request if it stuck in the queue for more than deadline.
This way now cfq can try to ensure the expected latency of requests execution. It is like a safety valve, it should not work all time, but it should keep latency in sane range when the scheduler is unable to effectively handle flow of requests, especially in cases when the "noop" or "deadline" shows better performance.
deadline can be tuned via /sys/block/<device>/queue/iosched/deadline_{sync,async} it by default 2000ms for sync and 4000ms for async requests, use 0 to disable it.
--- block/cfq-iosched.c | 93 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 93 insertions(+), 0 deletions(-)
block/cfq-iosched.c +93 -0
@@ -22,6 +22,7 @@/* max queue in one round of service */ static const int cfq_quantum =8 ;static const int cfq_fifo_expire[2 ] = {HZ /4 ,HZ /8 }; +static const int cfq_deadline[2 ] = {HZ *4 ,HZ *2 };/* maximum backwards seek, in KiB */ static const int cfq_back_max =16 *1024 ;/* penalty of a backwards seek */
@@ -120,6 +121,11 @@ struct cfq_queue {/* fifo list of requests in sort_list */ struct list_head fifo; +/* cached rq_fifo_time() for first rq in fifo */ +unsigned long fifo_key; +/* cfqd->fifo_tree member */ +struct rb_node fifo_node; +/* time when queue got scheduled in to dispatch first request. */ unsigned long dispatch_start;unsigned int allocated_slice;
@@ -238,6 +244,11 @@ struct cfq_data {*/ struct rb_root prio_trees[CFQ_PRIO_LISTS ]; +/* queues sorted by cfqq->fifo_key */ +struct rb_root fifo_tree[2 ]; +/* leftmost queue in fifo_tree */ +struct cfq_queue *fifo_first[2 ]; +unsigned int busy_queues;unsigned int busy_sync_queues;
@@ -280,6 +291,7 @@ struct cfq_data {*/ unsigned int cfq_quantum;unsigned int cfq_fifo_expire[2 ]; +unsigned int cfq_deadline[2 ];unsigned int cfq_back_penalty;unsigned int cfq_back_max;unsigned int cfq_slice[2 ];
@@ -1416,6 +1428,46 @@ static void cfq_prio_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq) cfqq->p_root =NULL ; } +static void cfq_resort_fifo_tree (struct cfq_data *cfqd,struct cfq_queue *cfqq) +{ +struct rb_node **p, *parent; +struct cfq_queue *__cfqq; +int sync =cfq_cfqq_sync (cfqq); +int new_first =1 ; + +if (!RB_EMPTY_NODE (&cfqq->fifo_node)) { +if (cfqq == cfqd->fifo_first[sync]) { + parent =rb_next (&cfqq->fifo_node); + __cfqq = rb_entry(parent, struct cfq_queue, fifo_node); + cfqd->fifo_first[sync] = parent ? __cfqq :NULL ; + } +rb_erase_init (&cfqq->fifo_node, &cfqd->fifo_tree[sync]); + } + +if (list_empty (&cfqq->fifo) || !cfqd->cfq_deadline[sync] || +cfq_class_idle (cfqq)) +return ; + + cfqq->fifo_key =rq_fifo_time (rq_entry_fifo (cfqq->fifo.next)); + + parent =NULL ; + p = &cfqd->fifo_tree[sync].rb_node; +while (*p) { + parent = *p; + __cfqq = rb_entry(parent, struct cfq_queue, fifo_node); +if (time_before_eq (__cfqq->fifo_key, cfqq->fifo_key)) { + p = &(*p)->rb_right; + new_first =0 ; + }else + p = &(*p)->rb_left; + } +rb_link_node (&cfqq->fifo_node, parent, p); +rb_insert_color (&cfqq->fifo_node, &cfqd->fifo_tree[sync]); + +if (new_first) + cfqd->fifo_first[sync] = cfqq; +} +/* * Update cfqq's position in the service tree. */
@@ -1444,6 +1496,7 @@ static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq) cfqd->busy_sync_queues++;cfq_resort_rr_list (cfqd, cfqq); +cfq_resort_fifo_tree (cfqd, cfqq); }/*
@@ -1588,11 +1641,16 @@ static void cfq_deactivate_request(struct request_queue *q, struct request *rq)static void cfq_remove_request (struct request *rq) {struct cfq_queue *cfqq =RQ_CFQQ (rq); +int fifo_first = rq->queuelist.prev == &cfqq->fifo;if (cfqq->next_rq == rq) cfqq->next_rq =cfq_find_next_rq (cfqq->cfqd, cfqq, rq);list_del_init (&rq->queuelist); + +if (fifo_first && !RB_EMPTY_NODE (&cfqq->fifo_node)) +cfq_resort_fifo_tree (cfqq->cfqd, cfqq); +cfq_del_rq_rb (rq); cfqq->cfqd->rq_queued--;
@@ -2573,6 +2631,27 @@ static bool cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq)return true; } +static bool cfq_dispatch_deadline (struct cfq_data *cfqd,int sync) +{ +struct cfq_queue *cfqq = cfqd->fifo_first[sync]; +unsigned int deadline = cfqd->cfq_deadline[sync]; + +if (!cfqq || !deadline) +return false; + +if (time_before (jiffies, cfqq->fifo_key + deadline)) +return false; + +cfq_log_cfqq (cfqd, cfqq,"dispatch deadline" ); +cfq_dispatch_insert (cfqd->queue,rq_entry_fifo (cfqq->fifo.next)); + +/* remove empty queue from service tree and expire its slices */ +if (RB_EMPTY_ROOT (&cfqq->sort_list)) +__cfq_slice_expired (cfqd, cfqq,0 ); + +return true; +} +/* * Find the cfqq that we need to service and move a request from that to the * dispatch list
@@ -2588,6 +2667,9 @@ static int cfq_dispatch_requests(struct request_queue *q, int force)if (unlikely (force))return cfq_forced_dispatch (cfqd); +if (cfq_dispatch_deadline (cfqd,1 ) ||cfq_dispatch_deadline (cfqd,0 )) +return 1 ; + cfqq =cfq_select_queue (cfqd);if (!cfqq)return 0 ;
@@ -2924,6 +3006,7 @@ static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq, {RB_CLEAR_NODE (&cfqq->rb_node);RB_CLEAR_NODE (&cfqq->p_node); +RB_CLEAR_NODE (&cfqq->fifo_node);INIT_LIST_HEAD (&cfqq->fifo); cfqq->ref =0 ;
@@ -4033,6 +4116,8 @@ static void *cfq_init_queue(struct request_queue *q)for (i =0 ; i <CFQ_PRIO_LISTS ; i++) cfqd->prio_trees[i] =RB_ROOT ; + cfqd->fifo_tree[0 ] = cfqd->fifo_tree[1 ] =RB_ROOT ; +/* * Our fallback cfqq if cfq_find_alloc_queue() runs into OOM issues. * Grab a permanent reference to it, so that the normal code flow
@@ -4055,6 +4140,8 @@ static void *cfq_init_queue(struct request_queue *q) cfqd->cfq_quantum = cfq_quantum; cfqd->cfq_fifo_expire[0 ] = cfq_fifo_expire[0 ]; cfqd->cfq_fifo_expire[1 ] = cfq_fifo_expire[1 ]; + cfqd->cfq_deadline[0 ] = cfq_deadline[0 ]; + cfqd->cfq_deadline[1 ] = cfq_deadline[1 ]; cfqd->cfq_back_max = cfq_back_max; cfqd->cfq_back_penalty = cfq_back_penalty; cfqd->cfq_slice[0 ] = cfq_slice_async;
@@ -4130,6 +4217,8 @@ static ssize_t __FUNC(struct elevator_queue *e, char *page) \SHOW_FUNCTION (cfq_quantum_show, cfqd->cfq_quantum,0 );SHOW_FUNCTION (cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1 ],1 );SHOW_FUNCTION (cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0 ],1 ); +SHOW_FUNCTION (cfq_deadline_sync_show, cfqd->cfq_deadline[1 ],1 ); +SHOW_FUNCTION (cfq_deadline_async_show, cfqd->cfq_deadline[0 ],1 );SHOW_FUNCTION (cfq_back_seek_max_show, cfqd->cfq_back_max,0 );SHOW_FUNCTION (cfq_back_seek_penalty_show, cfqd->cfq_back_penalty,0 );SHOW_FUNCTION (cfq_slice_idle_show, cfqd->cfq_slice_idle,1 );
@@ -4161,6 +4250,8 @@ STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1, UINT_MAX, 1);STORE_FUNCTION (cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0 ],1 ,UINT_MAX ,1 ); +STORE_FUNCTION (cfq_deadline_sync_store, &cfqd->cfq_deadline[1 ],0 ,UINT_MAX ,1 ); +STORE_FUNCTION (cfq_deadline_async_store, &cfqd->cfq_deadline[0 ],0 ,UINT_MAX ,1 );STORE_FUNCTION (cfq_back_seek_max_store, &cfqd->cfq_back_max,0 ,UINT_MAX ,0 );STORE_FUNCTION (cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty,1 ,UINT_MAX ,0 );
@@ -4180,6 +4271,8 @@ static struct elv_fs_entry cfq_attrs[] = {CFQ_ATTR (quantum),CFQ_ATTR (fifo_expire_sync),CFQ_ATTR (fifo_expire_async), +CFQ_ATTR (deadline_sync), +CFQ_ATTR (deadline_async),CFQ_ATTR (back_seek_max),CFQ_ATTR (back_seek_penalty), CFQ_ATTR(slice_sync),
RFC PATCH 2/2 blkio-cgroup: add max wait time statistics
This patch adds blk-cgroup attribute blkio.io_wait_max to show maximum time spent waiting in scheduler queue.
--- block/blk-cgroup.c | 27 ++++++++++++++++++++++++++- block/blk-cgroup.h | 3 +++ 2 files changed, 29 insertions(+), 1 deletions(-)
block/blk-cgroup.c +26 -1
@@ -197,6 +197,19 @@ static void blkio_add_stat(uint64_t *stat, uint64_t add, bool direction, stat[BLKIO_STAT_ASYNC ] += add; } +static void blkio_max_stat (uint64_t *stat,uint64_t cur,bool direction, +bool sync) +{ +if (direction) + stat[BLKIO_STAT_WRITE ] =max (stat[BLKIO_STAT_WRITE ], cur); +else + stat[BLKIO_STAT_READ ] =max (stat[BLKIO_STAT_READ ], cur); +if (sync) + stat[BLKIO_STAT_SYNC ] =max (stat[BLKIO_STAT_SYNC ], cur); +else + stat[BLKIO_STAT_ASYNC ] =max (stat[BLKIO_STAT_ASYNC ], cur); +} +/* * Decrements the appropriate stat variable if non-zero depending on the * request type. Panics on value being zero.
@@ -432,9 +445,12 @@ void blkiocg_update_completion_stats(struct blkio_group *blkg,if (time_after64 (now, io_start_time))blkio_add_stat (stats->stat_arr[BLKIO_STAT_SERVICE_TIME ], now - io_start_time, direction, sync); -if (time_after64 (io_start_time, start_time)) +if (time_after64 (io_start_time, start_time)) {blkio_add_stat (stats->stat_arr[BLKIO_STAT_WAIT_TIME ], io_start_time - start_time, direction, sync); +blkio_max_stat (stats->stat_arr[BLKIO_STAT_WAIT_MAX ], + io_start_time - start_time, direction, sync); + }spin_unlock_irqrestore (&blkg->stats_lock, flags); }EXPORT_SYMBOL_GPL (blkiocg_update_completion_stats);
@@ -1252,6 +1268,9 @@ static int blkiocg_file_read_map(struct cgroup *cgrp, struct cftype *cft,case BLKIO_PROP_io_wait_time:return blkio_read_blkg_stats (blkcg, cft, cb,BLKIO_STAT_WAIT_TIME ,1 ,0 ); +case BLKIO_PROP_io_wait_max: +return blkio_read_blkg_stats (blkcg, cft, cb, +BLKIO_STAT_WAIT_MAX ,0 ,0 );case BLKIO_PROP_io_merged:return blkio_read_blkg_stats (blkcg, cft, cb,BLKIO_STAT_CPU_MERGED ,1 ,1 );
@@ -1423,6 +1442,12 @@ struct cftype blkio_files[] = { .read_map = blkiocg_file_read_map, }, { + .name = "io_wait_max", + .private = BLKIOFILE_PRIVATE(BLKIO_POLICY_PROP, + BLKIO_PROP_io_wait_max), + .read_map = blkiocg_file_read_map, + }, + { .name = "io_merged", .private = BLKIOFILE_PRIVATE(BLKIO_POLICY_PROP, BLKIO_PROP_io_merged),
block/blk-cgroup.h +3 -0
@@ -39,6 +39,8 @@ enum stat_type {BLKIO_STAT_SERVICE_TIME =0 ,/* Total time spent waiting in scheduler queue in ns */ BLKIO_STAT_WAIT_TIME , +/* Maximum time spent waiting in scheduler queue in ns */ +BLKIO_STAT_WAIT_MAX ,/* Number of IOs queued up */ BLKIO_STAT_QUEUED,/* All the single valued stats go below this */
@@ -92,6 +94,7 @@ enum blkcg_file_name_prop { BLKIO_PROP_unaccounted_time, BLKIO_PROP_io_service_time, BLKIO_PROP_io_wait_time, + BLKIO_PROP_io_wait_max, BLKIO_PROP_io_merged, BLKIO_PROP_io_queued, BLKIO_PROP_avg_queue_size,
2011/7/4 Konstantin Khlebnikov <[email protected]>:
Quoted 9 lines
CFQ is designed for sharing disk bandwidth proportionally between queues and groups and for reordering requests to reduce disks seek time. Currently it cannot gurantee or estimate latency for individual requests, even if latencies are low for almost all requests, some of them can stuck inside scheduler for a long time. The fair policy is good as long as someone luckless begins to die due to a timeout.
This patch implements fifo requests dispatching with deadline policy: now cfq obliged to dispatch request if it stuck in the queue for more than deadline.
Quoted 7 lines
This way now cfq can try to ensure the expected latency of requests execution. It is like a safety valve, it should not work all time, but it should keep latency in sane range when the scheduler is unable to effectively handle flow of requests, especially in cases when the "noop" or "deadline" shows better performance.
deadline can be tuned via /sys/block/<device>/queue/iosched/deadline_{sync,async} it by default 2000ms for sync and 4000ms for async requests, use 0 to disable it.
I'm afraid this takes too far away. It completed breaks fairness of CFQ. The sync/async and priority of queues lose meaning. Even deadline is meaningful of some kind, maybe we should add a policy in preempt. If a queue has very old requests, don't preempt such queue. But we should be careful to tune how long slice the queue can take so fairness isn't broken.
Thanks,
Shaohua
Quoted 9 lines · Konstantin Khlebnikov
CFQ is designed for sharing disk bandwidth proportionally between queues and groups and for reordering requests to reduce disks seek time. Currently it cannot gurantee or estimate latency for individual requests, even if latencies are low for almost all requests, some of them can stuck inside scheduler for a long time. The fair policy is good as long as someone luckless begins to die due to a timeout.
This patch implements fifo requests dispatching with deadline policy: now cfq obliged to dispatch request if it stuck in the queue for more than deadline.
Quoted 7 lines
This way now cfq can try to ensure the expected latency of requests execution. It is like a safety valve, it should not work all time, but it should keep latency in sane range when the scheduler is unable to effectively handle flow of requests, especially in cases when the "noop" or "deadline" shows better performance.
deadline can be tuned via /sys/block/<device>/queue/iosched/deadline_{sync,async} it by default 2000ms for sync and 4000ms for async requests, use 0 to disable it.
What's the workload where you are running into issues with existing policy?
We have low_latency=1 by default and which tries to schedule every queue once in 300ms atleast. And with-in queue we already have the notion of looking at fifo and dispatch the expired request first.
So to me sync queue scheduling shold be pretty good. Async queues can get starved though. With-in sync queue, if some requests have expired, it is probably because of the fact that disk is slow and we are throwing too much IO at it. So if we start always dispatching expired requests first, then the notion of fairness is out of the window.
Why not use deadline scheduler for your case?
Thanks
Vivek
Quoted 15 lines · Vivek Goyal
Quoted 14 lines · Konstantin Khlebnikov
CFQ is designed for sharing disk bandwidth proportionally between queues and groups and for reordering requests to reduce disks seek time. Currently it cannot gurantee or estimate latency for individual requests, even if latencies are low for almost all requests, some of them can stuck inside scheduler for a long time. The fair policy is good as long as someone luckless begins to die due to a timeout.
This patch implements fifo requests dispatching with deadline policy: now cfq obliged to dispatch request if it stuck in the queue for more than deadline.
This way now cfq can try to ensure the expected latency of requests execution. It is like a safety valve, it should not work all time, but it should keep latency in sane range when the scheduler is unable to effectively handle flow of requests, especially in cases when the "noop" or "deadline" shows better performance.
Quoted 5 lines
Quoted 2 lines
deadline can be tuned via /sys/block/<device>/queue/iosched/deadline_{sync,async} it by default 2000ms for sync and 4000ms for async requests, use 0 to disable it.
What's the workload where you are running into issues with existing policy?
This is huge internal test workload,
there >100 containers with mail/http/ftp and something more.
Quoted 4 lines
We have low_latency=1 by default and which tries to schedule every queue once in 300ms atleast. And with-in queue we already have the notion of looking at fifo and dispatch the expired request first.
Without this patch some requests stuck in the scheduler for more than 30 seconds, and it looks like it is no limit.
With this patch max-wait-time (from the second patch) shows 7 seconds for this workload, so of course queue is over-congested, but it continues to work predictably.
Quoted 9 lines
So to me sync queue scheduling shold be pretty good. Async queues can get starved though. With-in sync queue, if some requests have expired, it is probably because of the fact that disk is slow and we are throwing too much IO at it. So if we start always dispatching expired requests first, then the notion of fairness is out of the window.
Why not use deadline scheduler for your case?
Because the scheduler must be universal, load can be arbitrary and constantly changing, we also can not modify each machine separately.
Quoted 3 lines
Thanks
Vivek
Quoted 26 lines · Konstantin Khlebnikov
Quoted 15 lines · Vivek Goyal
Quoted 14 lines · Konstantin Khlebnikov
CFQ is designed for sharing disk bandwidth proportionally between queues and groups and for reordering requests to reduce disks seek time. Currently it cannot gurantee or estimate latency for individual requests, even if latencies are low for almost all requests, some of them can stuck inside scheduler for a long time. The fair policy is good as long as someone luckless begins to die due to a timeout.
This patch implements fifo requests dispatching with deadline policy: now cfq obliged to dispatch request if it stuck in the queue for more than deadline.
This way now cfq can try to ensure the expected latency of requests execution. It is like a safety valve, it should not work all time, but it should keep latency in sane range when the scheduler is unable to effectively handle flow of requests, especially in cases when the "noop" or "deadline" shows better performance.
Quoted 5 lines
Quoted 2 lines
deadline can be tuned via /sys/block/<device>/queue/iosched/deadline_{sync,async} it by default 2000ms for sync and 4000ms for async requests, use 0 to disable it.
What's the workload where you are running into issues with existing policy?
This is huge internal test workload,
there >100 containers with mail/http/ftp and something more.Quoted 1 line
Quoted 6 lines
Quoted 3 lines
We have low_latency=1 by default and which tries to schedule every queue once in 300ms atleast. And with-in queue we already have the notion of looking at fifo and dispatch the expired request first.
Without this patch some requests stuck in the scheduler for more than 30 seconds, and it looks like it is no limit.
Have you done any analysis why requets are stuck for more than 30 seconds. May be running blktrace will help.
Is it async requests which are stuck or sync requests?
We have seen that async requests can be stuck for a long time in CFQ in an attempt to give sync requests priority. I will be surprised if it is sync request stuck for 30 seconds.
I think first we need to run traces and analyze why request is stuck for long time. With 300ms soft latency target, we dynamically reduce the slice of every queue with 16ms minimum. So without cgroups, one shall have to have close to 2 million procesess to create 32second delay in servicing a cfq queue. I don't think you have that many processes doing IO.
So running some traces and diving little deeper to figure out what's happening will help. If you are quoting these numbers for async request or for a sync request which is dependent on some async request, then I can belive those.
Quoted 12 lines
With this patch max-wait-time (from the second patch) shows 7 seconds for this workload, so of course queue is over-congested, but it continues to work predictably.
Quoted 8 lines
So to me sync queue scheduling shold be pretty good. Async queues can get starved though. With-in sync queue, if some requests have expired, it is probably because of the fact that disk is slow and we are throwing too much IO at it. So if we start always dispatching expired requests first, then the notion of fairness is out of the window.
Quoted 4 lines
Quoted 1 line
Why not use deadline scheduler for your case?
Because the scheduler must be universal, load can be arbitrary and constantly changing, we also can not modify each machine separately.
That's fine. But every scheduler has some property and one needs to use a scheduler which suits their workoload/storage.
Anyway, before we figure out how to fix the problem, we need to figure out what's the problem and what is being delayed and where does the delay come from.
Thanks
Vivek
Quoted 2 lines · Konstantin Khlebnikov
This patch implements fifo requests dispatching with deadline policy: now cfq obliged to dispatch request if it stuck in the queue for more than deadline.
Have you considered BFQ (http://lkml.org/lkml/2008/11/11/148) which is WF2Q+ variant?