2009-07-02 20:04:15

by Vivek Goyal

Subject: [RFC] IO scheduler based IO controller V6

Hi All,

Here is the V6 of the IO controller patches generated on top of 2.6.31-rc1.

Previous versions of the patches was posted here.

(V1) http://lkml.org/lkml/2009/3/11/486
(V2) http://lkml.org/lkml/2009/5/5/275
(V3) http://lkml.org/lkml/2009/5/26/472
(V4) http://lkml.org/lkml/2009/6/8/580
(V5) http://lkml.org/lkml/2009/6/19/279

This patchset is still work in progress but I want to keep on getting the
snapshot of my tree out at regular intervals to get the feedback hence V6.

Changes from V5
===============
- Broke down two of the biggest patches in to smaller patches. Now core of
bfq scheduler patches are separate patch and it should make review a bit
easier. I will try to break the patches down even more.

- Broke out bfq core scheduler changes from flat fair queuing code.
- Created separate patch for in class preemtion logic.
- Created separate patch to for core bfq hierarchical scheduler
changes.
- Created a separate patch for cgroup related bits.

- Introduced a new patch to wait for requests to complete from previous
queue before next queue is scheduled. It helps in achieving better
accounting of disk time used by writes and hence better isolation between
reads and buffered writes. This helps achieve fairness between sync queues
and buffered writes.

- Merged gui's patch for optimization during io group deletion.

- Merged gui's per device rule interface patch resulting from Paul Menage's
feedback.

- Merged gui's patch to read group data under rcu lock instead of taking
spin lock.

- Took care of some of the balbir's review comments on V5.

- Got rid of additional user defined data tyepes. "bfq_timestamp_t",
bfq_weight_t and bfq_service_t.
- Changed data type of "weight" to unsigned int.
- replaced *_extract() function names with *_remove().
- Renamed some of the bfq_* functions to io_* in comments.

- Misc code cleanups

- Moved io_get_io_group() and other common changes from patch
"implement per group bdi congestion interface" to upper patches.
- Made lots of functions static.
- Got rid of some forward declarations.
- Replaced rq_ioq() with req_ioq() and moved it to blkdev.h
- Some comment cleanups.
- Got rid of elv_ioq_set_slice_end()
- Got rid of redundant declaration of io_disconnect_groups().
- Got rid of io_group_ioq()

Limitations
===========

- This IO controller provides the bandwidth control at the IO scheduler
level (leaf node in stacked hiearchy of logical devices). So there can
be cases (depending on configuration) where application does not see
proportional BW division at higher logical level device.

LWN has written an article about the issue here.

http://lwn.net/Articles/332839/

How to solve the issue of fairness at higher level logical devices
==================================================================
Couple of suggestions have come forward.

- Implement IO control at IO scheduler layer and then with the help of
some daemon, adjust the weight on underlying devices dynamiclly, depending
on what kind of BW gurantees are to be achieved at higher level logical
block devices.

- Also implement a higher level IO controller along with IO scheduler
based controller and let user choose one depending on his needs.

A higher level controller does not know about the assumptions/policies
of unerldying IO scheduler, hence it has the potential to break down
the IO scheduler's policy with-in cgroup. A lower level controller
can work with IO scheduler much more closely and efficiently.

Other active IO controller developments
=======================================

IO throttling
-------------

This is a max bandwidth controller and not the proportional one. Secondly
it is a second level controller which can break the IO scheduler's
policy/assumtions with-in cgroup.

dm-ioband
---------

This is a proportional bandwidth controller implemented as device mapper
driver. It is also a second level controller which can break the
IO scheduler's policy/assumptions with-in cgroup.

TODO
====
- Lots of code cleanups, testing, bug fixing, optimizations, benchmarking
etc...

- Improve time keeping so that sub jiffy queue expiry time can be accounted
for.

- Work on a better interface (possibly cgroup based) for configuring per
group request descriptor limits.

- Debug and fix some of the areas like page cache where higher weight cgroup
async writes are stuck behind lower weight cgroup async writes.

Testing
=======

I have been able to do some testing as follows. All my testing is with ext3
file system with a SATA drive which supports queue depth of 31.

Test1 (Fairness for synchronous reads)
======================================
- Two dd in two cgroups with cgrop weights 1000 and 500. Ran two "dd" in those
cgroups (With CFQ scheduler and /sys/block/<device>/queue/fairness = 1)

Higher weight dd finishes first and at that point of time my script takes
care of reading cgroup files io.disk_time and io.disk_sectors for both the
groups and display the results.

dd if=/mnt/$BLOCKDEV/zerofile1 of=/dev/null &
dd if=/mnt/$BLOCKDEV/zerofile2 of=/dev/null &

234179072 bytes (234 MB) copied, 3.9065 s, 59.9 MB/s
234179072 bytes (234 MB) copied, 5.19232 s, 45.1 MB/s

group1 time=8 16 2471 group1 sectors=8 16 457840
group2 time=8 16 1220 group2 sectors=8 16 225736

First two fields in time and sectors statistics represent major and minor
number of the device. Third field represents disk time in milliseconds and
number of sectors transferred respectively.

This patchset tries to provide fairness in terms of disk time received. group1
got almost double of group2 disk time (At the time of first dd finish). These
time and sectors statistics can be read using io.disk_time and io.disk_sector
files in cgroup. More about it in documentation file.

Test2 (Reader Vs Buffered Writes)
================================
Buffered writes can be problematic and can overwhelm readers, especially with
noop and deadline. IO controller can provide isolation between readers and
buffered (async) writers.

First I ran the test without io controller to see the severity of the issue.
Ran a hostile writer and then after 10 seconds started a reader and then
monitored the completion time of reader. Reader reads a 256 MB file. Tested
this with noop scheduler.

sample script
------------
sync
echo 3 > /proc/sys/vm/drop_caches
time dd if=/dev/zero of=/mnt/sdb/reader-writer-zerofile bs=4K count=2097152
conv=fdatasync &
sleep 10
time dd if=/mnt/sdb/256M-file of=/dev/null &

Results
-------
8589934592 bytes (8.6 GB) copied, 106.045 s, 81.0 MB/s (Writer)
268435456 bytes (268 MB) copied, 96.5237 s, 2.8 MB/s (Reader)

Now it was time to test io controller whether it can provide isolation between
readers and writers with noop. I created two cgroups of weight 1000 each and
put reader in group1 and writer in group 2 and ran the test again. Upon
comletion of reader, my scripts read io.dis_time and io.disk_group cgroup
files to get an estimate how much disk time each group got and how many
sectors each group did IO for.

For more accurate accounting of disk time for buffered writes with queuing
hardware I had to set /sys/block/<disk>/queue/iosched/fairness to "2".

sample script
-------------
echo $$ > /cgroup/bfqio/test2/tasks
dd if=/dev/zero of=/mnt/$BLOCKDEV/testzerofile bs=4K count=2097152 &
sleep 10
echo noop > /sys/block/$BLOCKDEV/queue/scheduler
echo 2 > /sys/block/$BLOCKDEV/queue/iosched/fairness
echo $$ > /cgroup/bfqio/test1/tasks
dd if=/mnt/$BLOCKDEV/256M-file of=/dev/null &
wait $!
# Some code for reading cgroup files upon completion of reader.
-------------------------

Results
=======
268435456 bytes (268 MB) copied, 6.65819 s, 40.3 MB/s (Reader)

group1 time=8 16 3063 group1 sectors=8 16 524808
group2 time=8 16 3071 group2 sectors=8 16 441752

Note, reader finishes now much lesser time and both group1 and group2
got almost 3 seconds of disk time. Hence io-controller provides isolation
from buffered writes.

Test3 (AIO)
===========

AIO reads
-----------
Set up two fio, AIO read jobs in two cgroup with weight 1000 and 500
respectively. I am using cfq scheduler. Following are some lines from my test
script.

---------------------------------------------------------------
echo 1000 > /cgroup/bfqio/test1/io.weight
echo 500 > /cgroup/bfqio/test2/io.weight

fio_args="--ioengine=libaio --rw=read --size=512M --direct=1"
echo 1 > /sys/block/$BLOCKDEV/queue/iosched/fairness

echo $$ > /cgroup/bfqio/test1/tasks
fio $fio_args --name=test1 --directory=/mnt/$BLOCKDEV/fio1/
--output=/mnt/$BLOCKDEV/fio1/test1.log
--exec_postrun="../read-and-display-group-stats.sh $maj_dev $minor_dev" &

echo $$ > /cgroup/bfqio/test2/tasks
fio $fio_args --name=test2 --directory=/mnt/$BLOCKDEV/fio2/
--output=/mnt/$BLOCKDEV/fio2/test2.log &
----------------------------------------------------------------

test1 and test2 are two groups with weight 1000 and 500 respectively.
"read-and-display-group-stats.sh" is one small script which reads the
test1 and test2 cgroup files to determine how much disk time each group
got till first fio job finished.

Results
------
test1 statistics: time=8 16 22403 sectors=8 16 1049640
test2 statistics: time=8 16 11400 sectors=8 16 552864

Above shows that by the time first fio (higher weight), finished, group
test1 got 22403 ms of disk time and group test2 got 11400 ms of disk time.
similarly the statistics for number of sectors transferred are also shown.

Note that disk time given to group test1 is almost double of group2 disk
time.

AIO writes
----------
Set up two fio, AIO direct write jobs in two cgroup with weight 1000 and 500
respectively. I am using cfq scheduler. Following are some lines from my test
script.

------------------------------------------------
echo 1000 > /cgroup/bfqio/test1/io.weight
echo 500 > /cgroup/bfqio/test2/io.weight
fio_args="--ioengine=libaio --rw=write --size=512M --direct=1"

echo 1 > /sys/block/$BLOCKDEV/queue/iosched/fairness

echo $$ > /cgroup/bfqio/test1/tasks
fio $fio_args --name=test1 --directory=/mnt/$BLOCKDEV/fio1/
--output=/mnt/$BLOCKDEV/fio1/test1.log
--exec_postrun="../read-and-display-group-stats.sh $maj_dev $minor_dev" &

echo $$ > /cgroup/bfqio/test2/tasks
fio $fio_args --name=test2 --directory=/mnt/$BLOCKDEV/fio2/
--output=/mnt/$BLOCKDEV/fio2/test2.log &
-------------------------------------------------

test1 and test2 are two groups with weight 1000 and 500 respectively.
"read-and-display-group-stats.sh" is one small script which reads the
test1 and test2 cgroup files to determine how much disk time each group
got till first fio job finished.

Following are the results.

test1 statistics: time=8 16 29085 sectors=8 16 1049656
test2 statistics: time=8 16 14652 sectors=8 16 516728

Above shows that by the time first fio (higher weight), finished, group
test1 got 28085 ms of disk time and group test2 got 14652 ms of disk time.
similarly the statistics for number of sectors transferred are also shown.

Note that disk time given to group test1 is almost double of group2 disk
time.

Test4 (Writes with O_SYNC)
==========================
Created two groups with weight 1000 and 500 and launched two fio jobs doing
sync writes.

sample script
---------------------------
fio_args="--size=256m --rw=write --numjobs=1 --group_reporting --sync=1"

echo $$ > /cgroup/bfqio/test1/tasks
time fio $fio_args --name=test1 --directory=/mnt/$BLOCKDEV/fio1/
--output=/mnt/$BLOCKDEV/fio1/test1.log > /dev/null &

echo $$ > /cgroup/bfqio/test2/tasks
time fio $fio_args --name=test2 --directory=/mnt/$BLOCKDEV/fio2/
--output=/mnt/$BLOCKDEV/fio2/test2.log > /dev/null &

# some code to read group data upon completion of first fio job
----------------------------

Results
-------
group1 time=8 16 15194 group1 sectors=8 16 524864
group2 time=8 16 7689 group2 sectors=8 16 258920

Note, group 1 got almost double of group2 time as per the weight settings.

Test5 (Fairness for async writes, Buffered Write Vs Buffered Write)
===================================================================
Fairness for async writes is tricky and biggest reason is that async writes
are cached in higher layers (page cahe) as well as possibly in file system
layer also (btrfs, xfs etc), and are dispatched to lower layers not necessarily
in proportional manner.

For example, consider two dd threads reading /dev/zero as input file and doing
writes of huge files. Very soon we will cross vm_dirty_ratio and dd thread will
be forced to write out some pages to disk before more pages can be dirtied. But
not necessarily dirty pages of same thread are picked. It can very well pick
the inode of lesser priority dd thread and do some writeout. So effectively
higher weight dd is doing writeouts of lower weight dd pages and we don't see
service differentation.

IOW, the core problem with async write fairness is that higher weight thread
does not throw enought IO traffic at IO controller to keep the queue
continuously backlogged. In my testing, there are many .2 to .8 second
intervals where higher weight queue is empty and in that duration lower weight
queue get lots of job done giving the impression that there was no service
differentiation.

In summary, from IO controller point of view async writes support is there.
Because page cache has not been designed in such a manner that higher
prio/weight writer can do more write out as compared to lower prio/weight
writer, gettting service differentiation is hard and it is visible in some
cases and not visible in some cases.

Do we really care that much for fairness among two writer cgroups? One can
choose to do direct writes or sync writes if fairness for writes really
matters for him.

Following is the only case where it is hard to ensure fairness between cgroups.

- Buffered writes Vs Buffered Writes.

So to test async writes I created two partitions on a disk and created ext3
file systems on both the partitions. Also created two cgroups and generated
lots of write traffic in two cgroups (50 fio threads) and watched the disk
time statistics in respective cgroups at the interval of 2 seconds. Thanks to
ryo tsuruta for the test case.

*****************************************************************
sync
echo 3 > /proc/sys/vm/drop_caches

fio_args="--size=64m --rw=write --numjobs=50 --group_reporting"

echo $$ > /cgroup/bfqio/test1/tasks
fio $fio_args --name=test1 --directory=/mnt/sdd1/fio/ --output=/mnt/sdd1/fio/test1.log &

echo $$ > /cgroup/bfqio/test2/tasks
fio $fio_args --name=test2 --directory=/mnt/sdd2/fio/ --output=/mnt/sdd2/fio/test2.log &
***********************************************************************

And watched the disk time and sector statistics for the both the cgroups
every 2 seconds using a script. How is snippet from output.

test1 statistics: time=8 48 1315 sectors=8 48 55776 dq=8 48 1
test2 statistics: time=8 48 633 sectors=8 48 14720 dq=8 48 2

test1 statistics: time=8 48 5586 sectors=8 48 339064 dq=8 48 2
test2 statistics: time=8 48 2985 sectors=8 48 146656 dq=8 48 3

test1 statistics: time=8 48 9935 sectors=8 48 628728 dq=8 48 3
test2 statistics: time=8 48 5265 sectors=8 48 278688 dq=8 48 4

test1 statistics: time=8 48 14156 sectors=8 48 932488 dq=8 48 6
test2 statistics: time=8 48 7646 sectors=8 48 412704 dq=8 48 7

test1 statistics: time=8 48 18141 sectors=8 48 1231488 dq=8 48 10
test2 statistics: time=8 48 9820 sectors=8 48 548400 dq=8 48 8

test1 statistics: time=8 48 21953 sectors=8 48 1485632 dq=8 48 13
test2 statistics: time=8 48 12394 sectors=8 48 698288 dq=8 48 10

test1 statistics: time=8 48 25167 sectors=8 48 1705264 dq=8 48 13
test2 statistics: time=8 48 14042 sectors=8 48 817808 dq=8 48 10

First two fields in time and sectors statistics represent major and minor
number of the device. Third field represents disk time in milliseconds and
number of sectors transferred respectively.

So disk time consumed by group1 is almost double of group2 in this case.

Thanks
Vivek

2009-07-02 20:03:17

by Vivek Goyal

Subject: [PATCH 25/25] io-controller: experimental debug patch for async queue wait before expiry

o A debug patch which does wait for next IO from async queue once it
becomes empty.

o For async writes, traffic seen by IO scheduler is not in proportion to
the weight of the cgroup task/page belongs to. So if there are two processes
doing heavy writeouts in two cgroups with weights 1000 and 500 respectively,
then IO scheduler does not see more traffic/IO from higher weight cgroup
even if IO scheduler tries to give it higher disk time. Effectively, the
async queue belonging to higher weight cgroup becomes empty, and gets out
of contention for disk and lower weight cgroup gets to use disk giving
an impression in user space that higher weight cgroup did not get higher
time to disk.

o This is more of a problem at page cache level where a higher weight
process might be writing out the pages of lower weight process etc and
should be fixed there.

o While we fix those issues, introducing this debug patch which allows one
to idle on async queue (tunable via /sys/blolc/<disk>/queue/async_slice_idle) so that once a higher weight queue becomes empty, instead of expiring it
we try to wait for next request to come from that queue hence giving it
higher disk time. A higher value of async_slice_idle, around 300ms, helps
me get some right numbers for my setup. Note: higher disk time would not
necessarily translate in more IO done as higher weight group is not pushing
enough IO to io scheduler. It is just a debugging aid to prove correctness
of IO controller by providing higher disk times to higher weight cgroup.

Signed-off-by: Vivek Goyal <[email protected]>
---
block/cfq-iosched.c | 1 +
block/elevator-fq.c | 39 ++++++++++++++++++++++++++++++++++++---
block/elevator-fq.h | 5 +++++
3 files changed, 42 insertions(+), 3 deletions(-)

diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index a40a2fa..fbe56a9 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -2093,6 +2093,7 @@ static struct elv_fs_entry cfq_attrs[] = {
ELV_ATTR(slice_sync),
ELV_ATTR(slice_async),
ELV_ATTR(fairness),
+ ELV_ATTR(async_slice_idle),
__ATTR_NULL
};

diff --git a/block/elevator-fq.c b/block/elevator-fq.c
index 5b3f068..7c83d1e 100644
--- a/block/elevator-fq.c
+++ b/block/elevator-fq.c
@@ -24,6 +24,7 @@ const int elv_slice_sync = HZ / 10;
int elv_slice_async = HZ / 25;
const int elv_slice_async_rq = 2;
int elv_slice_idle = HZ / 125;
+int elv_async_slice_idle = 0;
static struct kmem_cache *elv_ioq_pool;

/* Maximum Window length for updating average disk rate */
@@ -2819,6 +2820,8 @@ SHOW_FUNCTION(elv_slice_async_show, efqd->elv_slice[0], 1);
EXPORT_SYMBOL(elv_slice_async_show);
SHOW_FUNCTION(elv_fairness_show, efqd->fairness, 0);
EXPORT_SYMBOL(elv_fairness_show);
+SHOW_FUNCTION(elv_async_slice_idle_show, efqd->elv_async_slice_idle, 1);
+EXPORT_SYMBOL(elv_async_slice_idle_show);
#undef SHOW_FUNCTION

#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
@@ -2845,6 +2848,8 @@ STORE_FUNCTION(elv_slice_async_store, &efqd->elv_slice[0], 1, UINT_MAX, 1);
EXPORT_SYMBOL(elv_slice_async_store);
STORE_FUNCTION(elv_fairness_store, &efqd->fairness, 0, 2, 0);
EXPORT_SYMBOL(elv_fairness_store);
+STORE_FUNCTION(elv_async_slice_idle_store, &efqd->elv_async_slice_idle, 0, UINT_MAX, 1);
+EXPORT_SYMBOL(elv_async_slice_idle_store);
#undef STORE_FUNCTION

void elv_schedule_dispatch(struct request_queue *q)
@@ -3018,7 +3023,7 @@ int elv_init_ioq(struct elevator_queue *eq, struct io_queue *ioq,
ioq->pid = current->pid;

ioq->sched_queue = sched_queue;
- if (is_sync && !elv_ioq_class_idle(ioq))
+ if (!elv_ioq_class_idle(ioq) && (is_sync || efqd->fairness))
elv_mark_ioq_idle_window(ioq);
bfq_init_entity(&ioq->entity, iog);
ioq->entity.budget = elv_prio_to_slice(efqd, ioq);
@@ -3699,7 +3704,12 @@ static void elv_ioq_arm_slice_timer(struct request_queue *q, int wait_for_busy)
/*
* idle is disabled, either manually or by past process history
*/
- if (!efqd->elv_slice_idle || !elv_ioq_idle_window(ioq))
+ if ((elv_ioq_sync(ioq) && !efqd->elv_slice_idle) ||
+ !elv_ioq_idle_window(ioq))
+ return;
+
+ /* If this is async queue and async_slice_idle is disabled, return */
+ if (!elv_ioq_sync(ioq) && !efqd->elv_async_slice_idle)
return;

/*
@@ -3708,7 +3718,10 @@ static void elv_ioq_arm_slice_timer(struct request_queue *q, int wait_for_busy)
*/
if (wait_for_busy) {
elv_mark_ioq_wait_busy(ioq);
- sl = efqd->elv_slice_idle;
+ if (elv_ioq_sync(ioq))
+ sl = efqd->elv_slice_idle;
+ else
+ sl = efqd->elv_async_slice_idle;
mod_timer(&efqd->idle_slice_timer, jiffies + sl);
elv_log_ioq(efqd, ioq, "arm idle: %lu wait busy=1", sl);
return;
@@ -3882,6 +3895,18 @@ void *elv_fq_select_ioq(struct request_queue *q, int force)
goto keep_queue;
}

+ /*
+ * If this is an async queue which has time slice left but not
+ * requests. Wait busy is also not on (may be because when last
+ * request completed, ioq was not empty). Wait for the request
+ * completion. May be completion will turn wait busy on.
+ */
+ if (efqd->fairness && efqd->elv_async_slice_idle && !elv_ioq_sync(ioq)
+ && elv_ioq_nr_dispatched(ioq)) {
+ ioq = NULL;
+ goto keep_queue;
+ }
+
slice_expired = 0;
expire:
if (efqd->fairness >= 2 && !force && ioq && ioq->dispatched
@@ -4076,6 +4101,13 @@ void elv_ioq_completed_request(struct request_queue *q, struct request *rq)
goto done;
}

+ /* For async queue try to do wait busy */
+ if (efqd->fairness && !elv_ioq_sync(ioq) && !ioq->nr_queued
+ && (elv_iog_nr_active(iog) <= 1)) {
+ elv_ioq_arm_slice_timer(q, 1);
+ goto done;
+ }
+
/*
* If there are no requests waiting in this queue, and
* there are other queues ready to issue requests, AND
@@ -4215,6 +4247,7 @@ int elv_init_fq_data(struct request_queue *q, struct elevator_queue *e)
efqd->elv_slice[0] = elv_slice_async;
efqd->elv_slice[1] = elv_slice_sync;
efqd->elv_slice_idle = elv_slice_idle;
+ efqd->elv_async_slice_idle = elv_async_slice_idle;
efqd->hw_tag = 1;

/* For the time being keep fairness enabled by default */
diff --git a/block/elevator-fq.h b/block/elevator-fq.h
index 19ac8ca..f089a55 100644
--- a/block/elevator-fq.h
+++ b/block/elevator-fq.h
@@ -362,6 +362,8 @@ struct elv_fq_data {
* users of this functionality.
*/
unsigned int elv_slice_idle;
+ /* idle slice for async queue */
+ unsigned int elv_async_slice_idle;
struct timer_list idle_slice_timer;
struct work_struct unplug_work;

@@ -647,6 +649,9 @@ extern ssize_t elv_slice_async_store(struct elevator_queue *q, const char *name,
extern ssize_t elv_fairness_show(struct elevator_queue *q, char *name);
extern ssize_t elv_fairness_store(struct elevator_queue *q, const char *name,
size_t count);
+extern ssize_t elv_async_slice_idle_show(struct elevator_queue *q, char *name);
+extern ssize_t elv_async_slice_idle_store(struct elevator_queue *q,
+ const char *name, size_t count);

/* Functions used by elevator.c */
extern int elv_init_fq_data(struct request_queue *q, struct elevator_queue *e);
--
1.6.0.6

2009-07-02 20:03:31

by Vivek Goyal

Subject: [PATCH 07/25] io-controller: core bfq scheduler changes for hierarchical setup

o Some of the core bfq scheduler changes for hiearchical groups.

Signed-off-by: Fabio Checconi <[email protected]>
Signed-off-by: Paolo Valente <[email protected]>
Signed-off-by: Nauman Rafique <[email protected]>
Signed-off-by: Vivek Goyal <[email protected]>
---
block/elevator-fq.c | 169 ++++++++++++++++++++++++++++++++++++++++++++++-----
block/elevator-fq.h | 4 +
init/Kconfig | 8 +++
3 files changed, 165 insertions(+), 16 deletions(-)

diff --git a/block/elevator-fq.c b/block/elevator-fq.c
index 67c02b9..0acfa2c 100644
--- a/block/elevator-fq.c
+++ b/block/elevator-fq.c
@@ -42,6 +42,69 @@ static int elv_rate_sampling_window = HZ / 10;
*/
#define WFQ_SERVICE_SHIFT 22

+#ifdef CONFIG_GROUP_IOSCHED
+#define for_each_entity(entity) \
+ for (; entity != NULL; entity = entity->parent)
+
+#define for_each_entity_safe(entity, parent) \
+ for (; entity && ({ parent = entity->parent; 1; }); entity = parent)
+
+
+static struct io_entity *bfq_lookup_next_entity(struct io_sched_data *sd,
+ int extract);
+
+static int bfq_update_next_active(struct io_sched_data *sd)
+{
+ struct io_group *iog;
+ struct io_entity *entity, *next_active;
+
+ if (sd->active_entity != NULL)
+ /* will update/requeue at the end of service */
+ return 0;
+
+ /*
+ * NOTE: this can be improved in may ways, such as returning
+ * 1 (and thus propagating upwards the update) only when the
+ * budget changes, or caching the bfqq that will be scheduled
+ * next from this subtree. By now we worry more about
+ * correctness than about performance...
+ */
+ next_active = bfq_lookup_next_entity(sd, 0);
+ sd->next_active = next_active;
+
+ if (next_active != NULL) {
+ iog = container_of(sd, struct io_group, sched_data);
+ entity = iog->my_entity;
+ if (entity != NULL)
+ entity->budget = next_active->budget;
+ }
+
+ return 1;
+}
+
+static inline void bfq_check_next_active(struct io_sched_data *sd,
+ struct io_entity *entity)
+{
+ BUG_ON(sd->next_active != entity);
+}
+#else /* GROUP_IOSCHED */
+#define for_each_entity(entity) \
+ for (; entity != NULL; entity = NULL)
+
+#define for_each_entity_safe(entity, parent) \
+ for (parent = NULL; entity != NULL; entity = parent)
+
+static inline int bfq_update_next_active(struct io_sched_data *sd)
+{
+ return 0;
+}
+
+static inline void bfq_check_next_active(struct io_sched_data *sd,
+ struct io_entity *entity)
+{
+}
+#endif /* GROUP_IOSCHED */
+
static inline int elv_prio_slice(struct elv_fq_data *efqd, int sync,
unsigned short prio)
{
@@ -587,8 +650,10 @@ static struct io_entity *bfq_lookup_next_entity(struct io_sched_data *sd,
entity = __bfq_lookup_next_entity(st);
if (entity != NULL) {
if (extract) {
+ bfq_check_next_active(sd, entity);
bfq_active_remove(st, entity);
sd->active_entity = entity;
+ sd->next_active = NULL;
}
break;
}
@@ -661,11 +726,8 @@ static void __bfq_activate_entity(struct io_entity *entity, int add_front)
if (add_front) {
struct io_entity *next_entity;

- /*
- * Determine the entity which will be dispatched next
- * Use sd->next_active once hierarchical patch is applied
- */
- next_entity = bfq_lookup_next_entity(sd, 0);
+ /* Determine the entity which will be dispatched next */
+ next_entity = sd->next_active;

if (next_entity && next_entity != entity) {
struct io_service_tree *new_st;
@@ -697,7 +759,21 @@ static void __bfq_activate_entity(struct io_entity *entity, int add_front)
*/
static void bfq_activate_entity(struct io_entity *entity, int add_front)
{
- __bfq_activate_entity(entity, add_front);
+ struct io_sched_data *sd;
+
+ for_each_entity(entity) {
+ __bfq_activate_entity(entity, add_front);
+
+ add_front = 0;
+ sd = entity->sched_data;
+ if (!bfq_update_next_active(sd))
+ /*
+ * No need to propagate the activation to the
+ * upper entities, as they will be updated when
+ * the active entity is rescheduled.
+ */
+ break;
+ }
}

/**
@@ -732,6 +808,8 @@ static int __bfq_deactivate_entity(struct io_entity *entity, int requeue)
bfq_idle_remove(st, entity);
else if (entity->tree != NULL)
BUG();
+ if (was_active || sd->next_active == entity)
+ ret = bfq_update_next_active(sd);

if (!requeue || !bfq_gt(entity->finish, st->vtime))
bfq_forget_entity(st, entity);
@@ -739,6 +817,7 @@ static int __bfq_deactivate_entity(struct io_entity *entity, int requeue)
bfq_idle_insert(st, entity);

BUG_ON(sd->active_entity == entity);
+ BUG_ON(sd->next_active == entity);

return ret;
}
@@ -750,18 +829,62 @@ static int __bfq_deactivate_entity(struct io_entity *entity, int requeue)
*/
static void bfq_deactivate_entity(struct io_entity *entity, int requeue)
{
- __bfq_deactivate_entity(entity, requeue);
+ struct io_sched_data *sd;
+ struct io_entity *parent;
+
+ for_each_entity_safe(entity, parent) {
+ sd = entity->sched_data;
+
+ if (!__bfq_deactivate_entity(entity, requeue))
+ /*
+ * The parent entity is still backlogged, and
+ * we don't need to update it as it is still
+ * under service.
+ */
+ break;
+
+ if (sd->next_active != NULL) {
+ /*
+ * The parent entity is still backlogged and
+ * the budgets on the path towards the root
+ * need to be updated.
+ */
+ goto update;
+ }
+
+ /*
+ * If we reach there the parent is no more backlogged and
+ * we want to propagate the dequeue upwards.
+ *
+ */
+
+ requeue = 1;
+ }
+
+ return;
+
+update:
+ entity = parent;
+ for_each_entity(entity) {
+ __bfq_activate_entity(entity, 0);
+
+ sd = entity->sched_data;
+ if (!bfq_update_next_active(sd))
+ break;
+ }
}

static void entity_served(struct io_entity *entity, unsigned long served)
{
struct io_service_tree *st;

- st = io_entity_service_tree(entity);
- entity->service += served;
- BUG_ON(st->wsum == 0);
- st->vtime += bfq_delta(served, st->wsum);
- bfq_forget_idle(st);
+ for_each_entity(entity) {
+ st = io_entity_service_tree(entity);
+ entity->service += served;
+ BUG_ON(st->wsum == 0);
+ st->vtime += bfq_delta(served, st->wsum);
+ bfq_forget_idle(st);
+ }
}

/**
@@ -1154,11 +1277,25 @@ static struct io_queue *elv_get_next_ioq(struct request_queue *q, int extract)
return NULL;

sd = &efqd->root_group->sched_data;
- entity = bfq_lookup_next_entity(sd, 1);

- BUG_ON(!entity);
- if (extract)
- entity->service = 0;
+ for (; sd != NULL; sd = entity->my_sched_data) {
+ entity = bfq_lookup_next_entity(sd, 1);
+ /*
+ * entity can be null despite the fact that there are busy
+ * queues. if all the busy queues are under a group which is
+ * currently under service.
+ * So if we are just looking for next ioq while something is
+ * being served, null entity is not an error.
+ */
+ BUG_ON(!entity && extract);
+
+ if (extract)
+ entity->service = 0;
+
+ if (!entity)
+ return NULL;
+ }
+
ioq = io_entity_to_ioq(entity);

return ioq;
diff --git a/block/elevator-fq.h b/block/elevator-fq.h
index 4b69239..57207c4 100644
--- a/block/elevator-fq.h
+++ b/block/elevator-fq.h
@@ -72,6 +72,7 @@ struct io_service_tree {
*/
struct io_sched_data {
struct io_entity *active_entity;
+ struct io_entity *next_active;
struct io_service_tree service_tree[IO_IOPRIO_CLASSES];
};

@@ -181,7 +182,10 @@ struct io_queue {
};

struct io_group {
+ struct io_entity entity;
struct io_sched_data sched_data;
+ struct io_entity *my_entity;
+
/*
* async queue for each priority case for RT and BE class.
* Used only for cfq.
diff --git a/init/Kconfig b/init/Kconfig
index 1ce05a4..a380f46 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -612,6 +612,14 @@ config CGROUP_MEM_RES_CTLR_SWAP
Now, memory usage of swap_cgroup is 2 bytes per entry. If swap page
size is 4096bytes, 512k per 1Gbytes of swap.

+config GROUP_IOSCHED
+ bool "Group IO Scheduler"
+ depends on CGROUPS && ELV_FAIR_QUEUING
+ default n
+ ---help---
+ This feature lets IO scheduler recognize task groups and control
+ disk bandwidth allocation to such task groups.
+
endif # CGROUPS

config MM_OWNER
--
1.6.0.6

2009-07-02 20:03:50

by Vivek Goyal

Subject: [PATCH 04/25] io-controller: Common flat fair queuing code in elevaotor layer

This is common fair queuing code in elevator layer. This is controlled by
config option CONFIG_ELV_FAIR_QUEUING. This patch initially only introduces
flat fair queuing support where there is only one group, "root group" and all
the tasks belong to root group.

This elevator layer changes are backward compatible. That means any ioscheduler
using old interfaces will continue to work.

This code is essentially the CFQ code for fair queuing. The primary difference
is that flat rounding robin algorithm of CFQ has been replaced with BFQ (WF2Q+).

Signed-off-by: Nauman Rafique <[email protected]>
Signed-off-by: Fabio Checconi <[email protected]>
Signed-off-by: Paolo Valente <[email protected]>
Signed-off-by: Aristeu Rozanski <[email protected]>
Signed-off-by: Gui Jianfeng <[email protected]>
Signed-off-by: Vivek Goyal <[email protected]>
---
block/Kconfig.iosched | 13 +
block/Makefile | 1 +
block/blk.h | 4 +
block/elevator-fq.c | 1254 +++++++++++++++++++++++++++++++++++++++++++++-
block/elevator-fq.h | 304 +++++++++++
block/elevator.c | 42 ++-
include/linux/blkdev.h | 14 +
include/linux/elevator.h | 51 ++
8 files changed, 1667 insertions(+), 16 deletions(-)

diff --git a/block/Kconfig.iosched b/block/Kconfig.iosched
index 7e803fc..3398134 100644
--- a/block/Kconfig.iosched
+++ b/block/Kconfig.iosched
@@ -2,6 +2,19 @@ if BLOCK

menu "IO Schedulers"

+config ELV_FAIR_QUEUING
+ bool "Elevator Fair Queuing Support"
+ default n
+ ---help---
+ Traditionally only cfq had notion of multiple queues and it did
+ fair queuing at its own. With the cgroups and need of controlling
+ IO, now even the simple io schedulers like noop, deadline, as will
+ have one queue per cgroup and will need hierarchical fair queuing.
+ Instead of every io scheduler implementing its own fair queuing
+ logic, this option enables fair queuing in elevator layer so that
+ other ioschedulers can make use of it.
+ If unsure, say N.
+
config IOSCHED_NOOP
bool
default y
diff --git a/block/Makefile b/block/Makefile
index e9fa4dd..94bfc6e 100644
--- a/block/Makefile
+++ b/block/Makefile
@@ -15,3 +15,4 @@ obj-$(CONFIG_IOSCHED_CFQ) += cfq-iosched.o

obj-$(CONFIG_BLOCK_COMPAT) += compat_ioctl.o
obj-$(CONFIG_BLK_DEV_INTEGRITY) += blk-integrity.o
+obj-$(CONFIG_ELV_FAIR_QUEUING) += elevator-fq.o
diff --git a/block/blk.h b/block/blk.h
index 3fae6ad..99c3819 100644
--- a/block/blk.h
+++ b/block/blk.h
@@ -71,6 +71,8 @@ static inline void elv_activate_rq(struct request_queue *q, struct request *rq)
{
struct elevator_queue *e = q->elevator;

+ elv_fq_activate_rq(q, rq);
+
if (e->ops->elevator_activate_req_fn)
e->ops->elevator_activate_req_fn(q, rq);
}
@@ -79,6 +81,8 @@ static inline void elv_deactivate_rq(struct request_queue *q, struct request *rq
{
struct elevator_queue *e = q->elevator;

+ elv_fq_deactivate_rq(q, rq);
+
if (e->ops->elevator_deactivate_req_fn)
e->ops->elevator_deactivate_req_fn(q, rq);
}
diff --git a/block/elevator-fq.c b/block/elevator-fq.c
index 7ee4321..6f23d7e 100644
--- a/block/elevator-fq.c
+++ b/block/elevator-fq.c
@@ -14,6 +14,17 @@

#include <linux/blkdev.h>
#include "elevator-fq.h"
+#include <linux/blktrace_api.h>
+
+/* Values taken from cfq */
+const int elv_slice_sync = HZ / 10;
+int elv_slice_async = HZ / 25;
+const int elv_slice_async_rq = 2;
+int elv_slice_idle = HZ / 125;
+static struct kmem_cache *elv_ioq_pool;
+
+#define ELV_SLICE_SCALE (5)
+#define ELV_HW_QUEUE_MIN (5)

#define IO_SERVICE_TREE_INIT ((struct io_service_tree) \
{ RB_ROOT, RB_ROOT, NULL, NULL, 0, 0 })
@@ -28,6 +39,22 @@
*/
#define WFQ_SERVICE_SHIFT 22

+static inline int elv_prio_slice(struct elv_fq_data *efqd, int sync,
+ unsigned short prio)
+{
+ const int base_slice = efqd->elv_slice[sync];
+
+ WARN_ON(prio >= IOPRIO_BE_NR);
+
+ return base_slice + (base_slice/ELV_SLICE_SCALE * (4 - prio));
+}
+
+static inline int
+elv_prio_to_slice(struct elv_fq_data *efqd, struct io_queue *ioq)
+{
+ return elv_prio_slice(efqd, elv_ioq_sync(ioq), ioq->entity.ioprio);
+}
+
/**
* bfq_gt - compare two timestamps.
* @a: first ts.
@@ -423,11 +450,6 @@ __bfq_entity_update_prio(struct io_service_tree *old_st,
*/
if (ioq) {
struct elv_fq_data *efqd = ioq->efqd;
- /*
- * elv_prio_to_slice() is defined in later patches
- * where a slice length is calculated from the
- * ioprio of the queue.
- */
entity->budget = elv_prio_to_slice(efqd, ioq);
}

@@ -750,3 +772,1225 @@ static void io_flush_idle_tree(struct io_service_tree *st)
for (; entity != NULL; entity = st->first_idle)
__bfq_deactivate_entity(entity, 0);
}
+
+/* Elevator fair queuing function */
+static inline struct io_queue *elv_active_ioq(struct elevator_queue *e)
+{
+ return e->efqd.active_queue;
+}
+
+void *elv_active_sched_queue(struct elevator_queue *e)
+{
+ return ioq_sched_queue(elv_active_ioq(e));
+}
+EXPORT_SYMBOL(elv_active_sched_queue);
+
+int elv_nr_busy_ioq(struct elevator_queue *e)
+{
+ return e->efqd.busy_queues;
+}
+EXPORT_SYMBOL(elv_nr_busy_ioq);
+
+int elv_hw_tag(struct elevator_queue *e)
+{
+ return e->efqd.hw_tag;
+}
+EXPORT_SYMBOL(elv_hw_tag);
+
+/* Helper functions for operating on elevator idle slice timer */
+int elv_mod_idle_slice_timer(struct elevator_queue *eq, unsigned long expires)
+{
+ struct elv_fq_data *efqd = &eq->efqd;
+
+ return mod_timer(&efqd->idle_slice_timer, expires);
+}
+EXPORT_SYMBOL(elv_mod_idle_slice_timer);
+
+int elv_del_idle_slice_timer(struct elevator_queue *eq)
+{
+ struct elv_fq_data *efqd = &eq->efqd;
+
+ return del_timer(&efqd->idle_slice_timer);
+}
+EXPORT_SYMBOL(elv_del_idle_slice_timer);
+
+unsigned int elv_get_slice_idle(struct elevator_queue *eq)
+{
+ return eq->efqd.elv_slice_idle;
+}
+EXPORT_SYMBOL(elv_get_slice_idle);
+
+static void elv_ioq_served(struct io_queue *ioq, unsigned long served)
+{
+ entity_served(&ioq->entity, served);
+}
+
+/* Tells whether ioq is queued in root group or not */
+static inline int is_root_group_ioq(struct request_queue *q,
+ struct io_queue *ioq)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+
+ return (ioq->entity.sched_data == &efqd->root_group->sched_data);
+}
+
+/*
+ * sysfs parts below -->
+ */
+static ssize_t
+elv_var_show(unsigned int var, char *page)
+{
+ return sprintf(page, "%d\n", var);
+}
+
+static ssize_t
+elv_var_store(unsigned int *var, const char *page, size_t count)
+{
+ char *p = (char *) page;
+
+ *var = simple_strtoul(p, &p, 10);
+ return count;
+}
+
+#define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
+ssize_t __FUNC(struct elevator_queue *e, char *page) \
+{ \
+ struct elv_fq_data *efqd = &e->efqd; \
+ unsigned int __data = __VAR; \
+ if (__CONV) \
+ __data = jiffies_to_msecs(__data); \
+ return elv_var_show(__data, (page)); \
+}
+SHOW_FUNCTION(elv_slice_idle_show, efqd->elv_slice_idle, 1);
+EXPORT_SYMBOL(elv_slice_idle_show);
+SHOW_FUNCTION(elv_slice_sync_show, efqd->elv_slice[1], 1);
+EXPORT_SYMBOL(elv_slice_sync_show);
+SHOW_FUNCTION(elv_slice_async_show, efqd->elv_slice[0], 1);
+EXPORT_SYMBOL(elv_slice_async_show);
+#undef SHOW_FUNCTION
+
+#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
+ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count)\
+{ \
+ struct elv_fq_data *efqd = &e->efqd; \
+ unsigned int __data; \
+ int ret = elv_var_store(&__data, (page), count); \
+ if (__data < (MIN)) \
+ __data = (MIN); \
+ else if (__data > (MAX)) \
+ __data = (MAX); \
+ if (__CONV) \
+ *(__PTR) = msecs_to_jiffies(__data); \
+ else \
+ *(__PTR) = __data; \
+ return ret; \
+}
+STORE_FUNCTION(elv_slice_idle_store, &efqd->elv_slice_idle, 0, UINT_MAX, 1);
+EXPORT_SYMBOL(elv_slice_idle_store);
+STORE_FUNCTION(elv_slice_sync_store, &efqd->elv_slice[1], 1, UINT_MAX, 1);
+EXPORT_SYMBOL(elv_slice_sync_store);
+STORE_FUNCTION(elv_slice_async_store, &efqd->elv_slice[0], 1, UINT_MAX, 1);
+EXPORT_SYMBOL(elv_slice_async_store);
+#undef STORE_FUNCTION
+
+void elv_schedule_dispatch(struct request_queue *q)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+
+ if (elv_nr_busy_ioq(q->elevator)) {
+ elv_log(efqd, "schedule dispatch");
+ kblockd_schedule_work(efqd->queue, &efqd->unplug_work);
+ }
+}
+EXPORT_SYMBOL(elv_schedule_dispatch);
+
+static void elv_kick_queue(struct work_struct *work)
+{
+ struct elv_fq_data *efqd =
+ container_of(work, struct elv_fq_data, unplug_work);
+ struct request_queue *q = efqd->queue;
+
+ spin_lock_irq(q->queue_lock);
+ __blk_run_queue(q);
+ spin_unlock_irq(q->queue_lock);
+}
+
+static void elv_shutdown_timer_wq(struct elevator_queue *e)
+{
+ del_timer_sync(&e->efqd.idle_slice_timer);
+ cancel_work_sync(&e->efqd.unplug_work);
+}
+
+static void elv_ioq_set_prio_slice(struct request_queue *q,
+ struct io_queue *ioq)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+
+ ioq->slice_end = jiffies + ioq->entity.budget;
+ elv_log_ioq(efqd, ioq, "set_slice=%lu", ioq->entity.budget);
+}
+
+static void elv_ioq_update_io_thinktime(struct io_queue *ioq)
+{
+ struct elv_fq_data *efqd = ioq->efqd;
+ unsigned long elapsed = jiffies - ioq->last_end_request;
+ unsigned long ttime = min(elapsed, 2UL * efqd->elv_slice_idle);
+
+ ioq->ttime_samples = (7*ioq->ttime_samples + 256) / 8;
+ ioq->ttime_total = (7*ioq->ttime_total + 256*ttime) / 8;
+ ioq->ttime_mean = (ioq->ttime_total + 128) / ioq->ttime_samples;
+}
+
+/*
+ * Disable idle window if the process thinks too long.
+ * This idle flag can also be updated by io scheduler.
+ */
+static void elv_ioq_update_idle_window(struct elevator_queue *eq,
+ struct io_queue *ioq, struct request *rq)
+{
+ int old_idle, enable_idle;
+ struct elv_fq_data *efqd = ioq->efqd;
+
+ /*
+ * Don't idle for async or idle io prio class
+ */
+ if (!elv_ioq_sync(ioq) || elv_ioq_class_idle(ioq))
+ return;
+
+ enable_idle = old_idle = elv_ioq_idle_window(ioq);
+
+ if (!efqd->elv_slice_idle)
+ enable_idle = 0;
+ else if (ioq_sample_valid(ioq->ttime_samples)) {
+ if (ioq->ttime_mean > efqd->elv_slice_idle)
+ enable_idle = 0;
+ else
+ enable_idle = 1;
+ }
+
+ /*
+ * From think time perspective idle should be enabled. Check with
+ * io scheduler if it wants to disable idling based on additional
+ * considrations like seek pattern.
+ */
+ if (enable_idle) {
+ if (eq->ops->elevator_update_idle_window_fn)
+ enable_idle = eq->ops->elevator_update_idle_window_fn(
+ eq, ioq->sched_queue, rq);
+ if (!enable_idle)
+ elv_log_ioq(efqd, ioq, "iosched disabled idle");
+ }
+
+ if (old_idle != enable_idle) {
+ elv_log_ioq(efqd, ioq, "idle=%d", enable_idle);
+ if (enable_idle)
+ elv_mark_ioq_idle_window(ioq);
+ else
+ elv_clear_ioq_idle_window(ioq);
+ }
+}
+
+struct io_queue *elv_alloc_ioq(struct request_queue *q, gfp_t gfp_mask)
+{
+ struct io_queue *ioq = NULL;
+
+ ioq = kmem_cache_alloc_node(elv_ioq_pool, gfp_mask, q->node);
+ return ioq;
+}
+EXPORT_SYMBOL(elv_alloc_ioq);
+
+void elv_free_ioq(struct io_queue *ioq)
+{
+ kmem_cache_free(elv_ioq_pool, ioq);
+}
+EXPORT_SYMBOL(elv_free_ioq);
+
+int elv_init_ioq(struct elevator_queue *eq, struct io_queue *ioq,
+ struct io_group *iog, void *sched_queue, int ioprio_class,
+ int ioprio, int is_sync)
+{
+ struct elv_fq_data *efqd = &eq->efqd;
+
+ RB_CLEAR_NODE(&ioq->entity.rb_node);
+ atomic_set(&ioq->ref, 0);
+ ioq->efqd = efqd;
+ elv_ioq_set_ioprio_class(ioq, ioprio_class);
+ elv_ioq_set_ioprio(ioq, ioprio);
+ ioq->pid = current->pid;
+ ioq->sched_queue = sched_queue;
+ if (is_sync && !elv_ioq_class_idle(ioq))
+ elv_mark_ioq_idle_window(ioq);
+ bfq_init_entity(&ioq->entity, iog);
+ ioq->entity.budget = elv_prio_to_slice(efqd, ioq);
+ if (is_sync)
+ ioq->last_end_request = jiffies;
+
+ return 0;
+}
+EXPORT_SYMBOL(elv_init_ioq);
+
+void elv_put_ioq(struct io_queue *ioq)
+{
+ struct elv_fq_data *efqd = ioq->efqd;
+ struct elevator_queue *e = container_of(efqd, struct elevator_queue,
+ efqd);
+
+ BUG_ON(atomic_read(&ioq->ref) <= 0);
+ if (!atomic_dec_and_test(&ioq->ref))
+ return;
+ BUG_ON(ioq->nr_queued);
+ BUG_ON(ioq->entity.tree != NULL);
+ BUG_ON(elv_ioq_busy(ioq));
+ BUG_ON(efqd->active_queue == ioq);
+
+ /* Can be called by outgoing elevator. Don't use q */
+ BUG_ON(!e->ops->elevator_free_sched_queue_fn);
+
+ e->ops->elevator_free_sched_queue_fn(e, ioq->sched_queue);
+ elv_log_ioq(efqd, ioq, "put_queue");
+ elv_free_ioq(ioq);
+}
+EXPORT_SYMBOL(elv_put_ioq);
+
+void elv_release_ioq(struct elevator_queue *e, struct io_queue **ioq_ptr)
+{
+ struct io_queue *ioq = *ioq_ptr;
+
+ if (ioq != NULL) {
+ /* Drop the reference taken by the io group */
+ elv_put_ioq(ioq);
+ *ioq_ptr = NULL;
+ }
+}
+
+/*
+ * Normally next io queue to be served is selected from the service tree.
+ * This function allows one to choose a specific io queue to run next
+ * out of order. This is primarily to accomodate the close_cooperator
+ * feature of cfq.
+ *
+ * Currently it is done only for root level as to begin with supporting
+ * close cooperator feature only for root group to make sure default
+ * cfq behavior in flat hierarchy is not changed.
+ */
+static void elv_set_next_ioq(struct request_queue *q, struct io_queue *ioq)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+ struct io_entity *entity = &ioq->entity;
+ struct io_sched_data *sd = &efqd->root_group->sched_data;
+ struct io_service_tree *st = io_entity_service_tree(entity);
+
+ BUG_ON(efqd->active_queue != NULL || sd->active_entity != NULL);
+ BUG_ON(!efqd->busy_queues);
+ BUG_ON(sd != entity->sched_data);
+ BUG_ON(!st);
+
+ bfq_update_vtime(st);
+ bfq_active_remove(st, entity);
+ sd->active_entity = entity;
+ entity->service = 0;
+ elv_log_ioq(efqd, ioq, "set_next_ioq");
+}
+
+/* Get next queue for service. */
+static struct io_queue *elv_get_next_ioq(struct request_queue *q, int extract)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+ struct io_entity *entity = NULL;
+ struct io_queue *ioq = NULL;
+ struct io_sched_data *sd;
+
+ /*
+ * We should not call lookup when an entity is active, as doing
+ * lookup can result in an erroneous vtime jump.
+ */
+ BUG_ON(efqd->active_queue != NULL);
+
+ if (!efqd->busy_queues)
+ return NULL;
+
+ sd = &efqd->root_group->sched_data;
+ entity = bfq_lookup_next_entity(sd, 1);
+
+ BUG_ON(!entity);
+ if (extract)
+ entity->service = 0;
+ ioq = io_entity_to_ioq(entity);
+
+ return ioq;
+}
+
+/*
+ * coop (cooperating queue) tells that io scheduler selected a queue for us
+ * and we did not select the next queue based on fairness.
+ */
+static void __elv_set_active_ioq(struct elv_fq_data *efqd, struct io_queue *ioq,
+ int coop)
+{
+ struct request_queue *q = efqd->queue;
+
+ if (ioq) {
+ elv_log_ioq(efqd, ioq, "set_active, busy=%d",
+ efqd->busy_queues);
+ ioq->slice_end = 0;
+
+ elv_clear_ioq_wait_request(ioq);
+ elv_clear_ioq_must_dispatch(ioq);
+ elv_mark_ioq_slice_new(ioq);
+
+ del_timer(&efqd->idle_slice_timer);
+ }
+
+ efqd->active_queue = ioq;
+
+ /* Let iosched know if it wants to take some action */
+ if (ioq) {
+ if (q->elevator->ops->elevator_active_ioq_set_fn)
+ q->elevator->ops->elevator_active_ioq_set_fn(q,
+ ioq->sched_queue, coop);
+ }
+}
+
+/* Get and set a new active queue for service. */
+static struct io_queue *elv_set_active_ioq(struct request_queue *q,
+ struct io_queue *ioq)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+ int coop = 0;
+
+ if (!ioq)
+ ioq = elv_get_next_ioq(q, 1);
+ else {
+ elv_set_next_ioq(q, ioq);
+ /*
+ * io scheduler selected the next queue for us. Pass this
+ * this info back to io scheudler. cfq currently uses it
+ * to reset coop flag on the queue.
+ */
+ coop = 1;
+ }
+ __elv_set_active_ioq(efqd, ioq, coop);
+ return ioq;
+}
+
+static void elv_reset_active_ioq(struct elv_fq_data *efqd)
+{
+ struct request_queue *q = efqd->queue;
+ struct io_queue *ioq = elv_active_ioq(efqd->queue->elevator);
+
+ if (q->elevator->ops->elevator_active_ioq_reset_fn)
+ q->elevator->ops->elevator_active_ioq_reset_fn(q,
+ ioq->sched_queue);
+ efqd->active_queue = NULL;
+ del_timer(&efqd->idle_slice_timer);
+}
+
+static void elv_activate_ioq(struct io_queue *ioq, int add_front)
+{
+ bfq_activate_entity(&ioq->entity, add_front);
+}
+
+static void elv_deactivate_ioq(struct elv_fq_data *efqd, struct io_queue *ioq,
+ int requeue)
+{
+ bfq_deactivate_entity(&ioq->entity, requeue);
+}
+
+/* Called when an inactive queue receives a new request. */
+static void elv_add_ioq_busy(struct elv_fq_data *efqd, struct io_queue *ioq)
+{
+ BUG_ON(elv_ioq_busy(ioq));
+ BUG_ON(ioq == efqd->active_queue);
+ elv_log_ioq(efqd, ioq, "add to busy");
+ elv_activate_ioq(ioq, 0);
+ elv_mark_ioq_busy(ioq);
+ efqd->busy_queues++;
+ if (elv_ioq_class_rt(ioq)) {
+ struct io_group *iog = ioq_to_io_group(ioq);
+ iog->busy_rt_queues++;
+ }
+}
+
+static void elv_del_ioq_busy(struct elevator_queue *e, struct io_queue *ioq,
+ int requeue)
+{
+ struct elv_fq_data *efqd = &e->efqd;
+
+ BUG_ON(!elv_ioq_busy(ioq));
+ BUG_ON(ioq->nr_queued);
+ elv_log_ioq(efqd, ioq, "del from busy");
+ elv_clear_ioq_busy(ioq);
+ BUG_ON(efqd->busy_queues == 0);
+ efqd->busy_queues--;
+ if (elv_ioq_class_rt(ioq)) {
+ struct io_group *iog = ioq_to_io_group(ioq);
+ iog->busy_rt_queues--;
+ }
+
+ elv_deactivate_ioq(efqd, ioq, requeue);
+}
+
+/*
+ * Do the accounting. Determine how much service (in terms of time slices)
+ * current queue used and adjust the start, finish time of queue and vtime
+ * of the tree accordingly.
+ *
+ * Determining the service used in terms of time is tricky in certain
+ * situations. Especially when underlying device supports command queuing
+ * and requests from multiple queues can be there at same time, then it
+ * is not clear which queue consumed how much of disk time.
+ *
+ * To mitigate this problem, cfq starts the time slice of the queue only
+ * after first request from the queue has completed. This does not work
+ * very well if we expire the queue before we wait for first and more
+ * request to finish from the queue. For seeky queues, we will expire the
+ * queue after dispatching few requests without waiting and start dispatching
+ * from next queue.
+ *
+ * Not sure how to determine the time consumed by queue in such scenarios.
+ * Currently as a crude approximation, we are charging 25% of time slice
+ * for such cases. A better mechanism is needed for accurate accounting.
+ */
+void __elv_ioq_slice_expired(struct request_queue *q, struct io_queue *ioq)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+ struct io_entity *entity = &ioq->entity;
+ long slice_unused = 0, slice_used = 0, slice_overshoot = 0;
+
+ assert_spin_locked(q->queue_lock);
+ elv_log_ioq(efqd, ioq, "slice expired");
+
+ if (elv_ioq_wait_request(ioq))
+ del_timer(&efqd->idle_slice_timer);
+
+ elv_clear_ioq_wait_request(ioq);
+
+ /*
+ * if ioq->slice_end = 0, that means a queue was expired before first
+ * reuqest from the queue got completed. Of course we are not planning
+ * to idle on the queue otherwise we would not have expired it.
+ *
+ * Charge for the 25% slice in such cases. This is not the best thing
+ * to do but at the same time not very sure what's the next best
+ * thing to do.
+ *
+ * This arises from that fact that we don't have the notion of
+ * one queue being operational at one time. io scheduler can dispatch
+ * requests from multiple queues in one dispatch round. Ideally for
+ * more accurate accounting of exact disk time used by disk, one
+ * should dispatch requests from only one queue and wait for all
+ * the requests to finish. But this will reduce throughput.
+ */
+ if (!ioq->slice_end)
+ slice_used = entity->budget/4;
+ else {
+ if (time_after(ioq->slice_end, jiffies)) {
+ slice_unused = ioq->slice_end - jiffies;
+ if (slice_unused == entity->budget) {
+ /*
+ * queue got expired immediately after
+ * completing first request. Charge 25% of
+ * slice.
+ */
+ slice_used = entity->budget/4;
+ } else
+ slice_used = entity->budget - slice_unused;
+ } else {
+ slice_overshoot = jiffies - ioq->slice_end;
+ slice_used = entity->budget + slice_overshoot;
+ }
+ }
+
+ elv_log_ioq(efqd, ioq, "sl_end=%lx, jiffies=%lx", ioq->slice_end,
+ jiffies);
+ elv_log_ioq(efqd, ioq, "sl_used=%ld, budget=%ld overshoot=%ld",
+ slice_used, entity->budget, slice_overshoot);
+ elv_ioq_served(ioq, slice_used);
+
+ BUG_ON(ioq != efqd->active_queue);
+ elv_reset_active_ioq(efqd);
+
+ if (!ioq->nr_queued)
+ elv_del_ioq_busy(q->elevator, ioq, 1);
+ else
+ elv_activate_ioq(ioq, 0);
+}
+EXPORT_SYMBOL(__elv_ioq_slice_expired);
+
+/*
+ * Expire the ioq.
+ */
+void elv_ioq_slice_expired(struct request_queue *q)
+{
+ struct io_queue *ioq = elv_active_ioq(q->elevator);
+
+ if (ioq)
+ __elv_ioq_slice_expired(q, ioq);
+}
+
+/*
+ * Check if new_cfqq should preempt the currently active queue. Return 0 for
+ * no or if we aren't sure, a 1 will cause a preemption attempt.
+ */
+static int elv_should_preempt(struct request_queue *q, struct io_queue *new_ioq,
+ struct request *rq)
+{
+ struct io_queue *ioq;
+ struct elevator_queue *eq = q->elevator;
+ struct io_entity *entity, *new_entity;
+
+ ioq = elv_active_ioq(eq);
+
+ if (!ioq)
+ return 0;
+
+ entity = &ioq->entity;
+ new_entity = &new_ioq->entity;
+
+ /*
+ * Allow an RT request to pre-empt an ongoing non-RT cfqq timeslice.
+ */
+
+ if (new_entity->ioprio_class == IOPRIO_CLASS_RT
+ && entity->ioprio_class != IOPRIO_CLASS_RT)
+ return 1;
+ /*
+ * Allow an BE request to pre-empt an ongoing IDLE clas timeslice.
+ */
+
+ if (new_entity->ioprio_class == IOPRIO_CLASS_BE
+ && entity->ioprio_class == IOPRIO_CLASS_IDLE)
+ return 1;
+
+ /*
+ * Check with io scheduler if it has additional criterion based on
+ * which it wants to preempt existing queue.
+ */
+ if (eq->ops->elevator_should_preempt_fn)
+ return eq->ops->elevator_should_preempt_fn(q,
+ ioq_sched_queue(new_ioq), rq);
+
+ return 0;
+}
+
+static void elv_preempt_queue(struct request_queue *q, struct io_queue *ioq)
+{
+ elv_log_ioq(&q->elevator->efqd, ioq, "preempt");
+ elv_ioq_slice_expired(q);
+
+ /*
+ * Put the new queue at the front of the of the current list,
+ * so we know that it will be selected next.
+ */
+
+ elv_activate_ioq(ioq, 1);
+ ioq->slice_end = 0;
+ elv_mark_ioq_slice_new(ioq);
+}
+
+void elv_ioq_request_add(struct request_queue *q, struct request *rq)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+ struct io_queue *ioq = rq->ioq;
+
+ if (!elv_iosched_fair_queuing_enabled(q->elevator))
+ return;
+
+ BUG_ON(!efqd);
+ BUG_ON(!ioq);
+ efqd->rq_queued++;
+ ioq->nr_queued++;
+
+ if (!elv_ioq_busy(ioq))
+ elv_add_ioq_busy(efqd, ioq);
+
+ elv_ioq_update_io_thinktime(ioq);
+ elv_ioq_update_idle_window(q->elevator, ioq, rq);
+
+ if (ioq == elv_active_ioq(q->elevator)) {
+ /*
+ * Remember that we saw a request from this process, but
+ * don't start queuing just yet. Otherwise we risk seeing lots
+ * of tiny requests, because we disrupt the normal plugging
+ * and merging. If the request is already larger than a single
+ * page, let it rip immediately. For that case we assume that
+ * merging is already done. Ditto for a busy system that
+ * has other work pending, don't risk delaying until the
+ * idle timer unplug to continue working.
+ */
+ if (elv_ioq_wait_request(ioq)) {
+ if (blk_rq_bytes(rq) > PAGE_CACHE_SIZE ||
+ efqd->busy_queues > 1) {
+ del_timer(&efqd->idle_slice_timer);
+ __blk_run_queue(q);
+ }
+ elv_mark_ioq_must_dispatch(ioq);
+ }
+ } else if (elv_should_preempt(q, ioq, rq)) {
+ /*
+ * not the active queue - expire current slice if it is
+ * idle and has expired it's mean thinktime or this new queue
+ * has some old slice time left and is of higher priority or
+ * this new queue is RT and the current one is BE
+ */
+ elv_preempt_queue(q, ioq);
+ __blk_run_queue(q);
+ }
+}
+
+static void elv_idle_slice_timer(unsigned long data)
+{
+ struct elv_fq_data *efqd = (struct elv_fq_data *)data;
+ struct io_queue *ioq;
+ unsigned long flags;
+ struct request_queue *q = efqd->queue;
+
+ elv_log(efqd, "idle timer fired");
+
+ spin_lock_irqsave(q->queue_lock, flags);
+
+ ioq = efqd->active_queue;
+
+ if (ioq) {
+
+ /*
+ * We saw a request before the queue expired, let it through
+ */
+ if (elv_ioq_must_dispatch(ioq))
+ goto out_kick;
+
+ /*
+ * expired
+ */
+ if (elv_ioq_slice_used(ioq))
+ goto expire;
+
+ /*
+ * only expire and reinvoke request handler, if there are
+ * other queues with pending requests
+ */
+ if (!elv_nr_busy_ioq(q->elevator))
+ goto out_cont;
+
+ /*
+ * not expired and it has a request pending, let it dispatch
+ */
+ if (ioq->nr_queued)
+ goto out_kick;
+ }
+expire:
+ elv_ioq_slice_expired(q);
+out_kick:
+ elv_schedule_dispatch(q);
+out_cont:
+ spin_unlock_irqrestore(q->queue_lock, flags);
+}
+
+static void elv_ioq_arm_slice_timer(struct request_queue *q)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+ struct io_queue *ioq = elv_active_ioq(q->elevator);
+ unsigned long sl;
+
+ BUG_ON(!ioq);
+
+ /*
+ * SSD device without seek penalty, disable idling. But only do so
+ * for devices that support queuing, otherwise we still have a problem
+ * with sync vs async workloads.
+ */
+ if (blk_queue_nonrot(q) && efqd->hw_tag)
+ return;
+
+ /*
+ * still requests with the driver, don't idle
+ */
+ if (efqd->rq_in_driver)
+ return;
+
+ /*
+ * idle is disabled, either manually or by past process history
+ */
+ if (!efqd->elv_slice_idle || !elv_ioq_idle_window(ioq))
+ return;
+
+ /*
+ * may be iosched got its own idling logic. In that case io
+ * schduler will take care of arming the timer, if need be.
+ */
+ if (q->elevator->ops->elevator_arm_slice_timer_fn) {
+ q->elevator->ops->elevator_arm_slice_timer_fn(q,
+ ioq->sched_queue);
+ } else {
+ elv_mark_ioq_wait_request(ioq);
+ sl = efqd->elv_slice_idle;
+ mod_timer(&efqd->idle_slice_timer, jiffies + sl);
+ elv_log_ioq(efqd, ioq, "arm idle: %lu", sl);
+ }
+}
+
+/*
+ * If io scheduler has functionality of keeping track of close cooperator, check
+ * with it if it has got a closely co-operating queue.
+ */
+static inline struct io_queue *elv_close_cooperator(struct request_queue *q,
+ struct io_queue *ioq, int probe)
+{
+ struct elevator_queue *e = q->elevator;
+ struct io_queue *new_ioq = NULL;
+
+ /*
+ * Currently this feature is supported only for flat hierarchy or
+ * root group queues so that default cfq behavior is not changed.
+ */
+ if (!is_root_group_ioq(q, ioq))
+ return NULL;
+
+ if (q->elevator->ops->elevator_close_cooperator_fn)
+ new_ioq = e->ops->elevator_close_cooperator_fn(q,
+ ioq->sched_queue, probe);
+
+ /* Only select co-operating queue if it belongs to root group */
+ if (new_ioq && !is_root_group_ioq(q, new_ioq))
+ return NULL;
+
+ return new_ioq;
+}
+
+/* Common layer function to select the next queue to dispatch from */
+void *elv_fq_select_ioq(struct request_queue *q, int force)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+ struct io_queue *new_ioq = NULL, *ioq = elv_active_ioq(q->elevator);
+ struct io_group *iog;
+
+ if (!elv_nr_busy_ioq(q->elevator))
+ return NULL;
+
+ if (ioq == NULL)
+ goto new_queue;
+
+ /*
+ * Force dispatch. Continue to dispatch from current queue as long
+ * as it has requests.
+ */
+ if (unlikely(force)) {
+ if (ioq->nr_queued)
+ goto keep_queue;
+ else
+ goto expire;
+ }
+
+ /*
+ * The active queue has run out of time, expire it and select new.
+ */
+ if (elv_ioq_slice_used(ioq) && !elv_ioq_must_dispatch(ioq))
+ goto expire;
+
+ /*
+ * If we have a RT cfqq waiting, then we pre-empt the current non-rt
+ * cfqq.
+ */
+ iog = ioq_to_io_group(ioq);
+
+ if (!elv_ioq_class_rt(ioq) && iog->busy_rt_queues) {
+ /*
+ * We simulate this as cfqq timed out so that it gets to bank
+ * the remaining of its time slice.
+ */
+ elv_log_ioq(efqd, ioq, "preempt");
+ goto expire;
+ }
+
+ /*
+ * The active queue has requests and isn't expired, allow it to
+ * dispatch.
+ */
+
+ if (ioq->nr_queued)
+ goto keep_queue;
+
+ /*
+ * If another queue has a request waiting within our mean seek
+ * distance, let it run. The expire code will check for close
+ * cooperators and put the close queue at the front of the service
+ * tree.
+ */
+ new_ioq = elv_close_cooperator(q, ioq, 0);
+ if (new_ioq)
+ goto expire;
+
+ /*
+ * No requests pending. If the active queue still has requests in
+ * flight or is idling for a new request, allow either of these
+ * conditions to happen (or time out) before selecting a new queue.
+ */
+
+ if (timer_pending(&efqd->idle_slice_timer) ||
+ (elv_ioq_nr_dispatched(ioq) && elv_ioq_idle_window(ioq))) {
+ ioq = NULL;
+ goto keep_queue;
+ }
+
+expire:
+ elv_ioq_slice_expired(q);
+new_queue:
+ ioq = elv_set_active_ioq(q, new_ioq);
+keep_queue:
+ return ioq;
+}
+
+/* A request got removed from io_queue. Do the accounting */
+void elv_ioq_request_removed(struct elevator_queue *e, struct request *rq)
+{
+ struct io_queue *ioq;
+ struct elv_fq_data *efqd;
+
+ if (!elv_iosched_fair_queuing_enabled(e))
+ return;
+
+ ioq = rq->ioq;
+ BUG_ON(!ioq);
+ ioq->nr_queued--;
+
+ efqd = ioq->efqd;
+ BUG_ON(!efqd);
+ efqd->rq_queued--;
+
+ if (elv_ioq_busy(ioq) && (elv_active_ioq(e) != ioq) && !ioq->nr_queued)
+ elv_del_ioq_busy(e, ioq, 1);
+}
+
+/* A request got dispatched. Do the accounting. */
+void elv_fq_dispatched_request(struct elevator_queue *e, struct request *rq)
+{
+ struct io_queue *ioq = rq->ioq;
+
+ if (!elv_iosched_fair_queuing_enabled(e))
+ return;
+
+ BUG_ON(!ioq);
+ elv_ioq_request_dispatched(ioq);
+ elv_ioq_request_removed(e, rq);
+ elv_clear_ioq_must_dispatch(ioq);
+}
+
+void elv_fq_activate_rq(struct request_queue *q, struct request *rq)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+
+ if (!elv_iosched_fair_queuing_enabled(q->elevator))
+ return;
+
+ efqd->rq_in_driver++;
+ elv_log_ioq(efqd, rq->ioq, "activate rq, drv=%d",
+ efqd->rq_in_driver);
+}
+
+void elv_fq_deactivate_rq(struct request_queue *q, struct request *rq)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+
+ if (!elv_iosched_fair_queuing_enabled(q->elevator))
+ return;
+
+ WARN_ON(!efqd->rq_in_driver);
+ efqd->rq_in_driver--;
+ elv_log_ioq(efqd, rq->ioq, "deactivate rq, drv=%d",
+ efqd->rq_in_driver);
+}
+
+/*
+ * Update hw_tag based on peak queue depth over 50 samples under
+ * sufficient load.
+ */
+static void elv_update_hw_tag(struct elv_fq_data *efqd)
+{
+ if (efqd->rq_in_driver > efqd->rq_in_driver_peak)
+ efqd->rq_in_driver_peak = efqd->rq_in_driver;
+
+ if (efqd->rq_queued <= ELV_HW_QUEUE_MIN &&
+ efqd->rq_in_driver <= ELV_HW_QUEUE_MIN)
+ return;
+
+ if (efqd->hw_tag_samples++ < 50)
+ return;
+
+ if (efqd->rq_in_driver_peak >= ELV_HW_QUEUE_MIN)
+ efqd->hw_tag = 1;
+ else
+ efqd->hw_tag = 0;
+
+ efqd->hw_tag_samples = 0;
+ efqd->rq_in_driver_peak = 0;
+}
+
+/* A request got completed from io_queue. Do the accounting. */
+void elv_ioq_completed_request(struct request_queue *q, struct request *rq)
+{
+ const int sync = rq_is_sync(rq);
+ struct io_queue *ioq;
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+
+ if (!elv_iosched_fair_queuing_enabled(q->elevator))
+ return;
+
+ ioq = rq->ioq;
+
+ elv_log_ioq(efqd, ioq, "complete");
+
+ elv_update_hw_tag(efqd);
+
+ WARN_ON(!efqd->rq_in_driver);
+ WARN_ON(!ioq->dispatched);
+ efqd->rq_in_driver--;
+ ioq->dispatched--;
+
+ if (sync)
+ ioq->last_end_request = jiffies;
+
+ /*
+ * If this is the active queue, check if it needs to be expired,
+ * or if we want to idle in case it has no pending requests.
+ */
+
+ if (elv_active_ioq(q->elevator) == ioq) {
+ if (elv_ioq_slice_new(ioq)) {
+ elv_ioq_set_prio_slice(q, ioq);
+ elv_clear_ioq_slice_new(ioq);
+ }
+ /*
+ * If there are no requests waiting in this queue, and
+ * there are other queues ready to issue requests, AND
+ * those other queues are issuing requests within our
+ * mean seek distance, give them a chance to run instead
+ * of idling.
+ */
+ if (elv_ioq_slice_used(ioq) || elv_ioq_class_idle(ioq))
+ elv_ioq_slice_expired(q);
+ else if (!ioq->nr_queued && !elv_close_cooperator(q, ioq, 1)
+ && sync && !rq_noidle(rq))
+ elv_ioq_arm_slice_timer(q);
+ }
+
+ if (!efqd->rq_in_driver)
+ elv_schedule_dispatch(q);
+}
+
+struct io_group *io_get_io_group(struct request_queue *q)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+
+ /* In flat mode, there is only root group */
+ return efqd->root_group;
+}
+EXPORT_SYMBOL(io_get_io_group);
+
+void *io_group_async_queue_prio(struct io_group *iog, int ioprio_class,
+ int ioprio)
+{
+ struct io_queue *ioq = NULL;
+
+ switch (ioprio_class) {
+ case IOPRIO_CLASS_RT:
+ ioq = iog->async_queue[0][ioprio];
+ break;
+ case IOPRIO_CLASS_BE:
+ ioq = iog->async_queue[1][ioprio];
+ break;
+ case IOPRIO_CLASS_IDLE:
+ ioq = iog->async_idle_queue;
+ break;
+ default:
+ BUG();
+ }
+
+ if (ioq)
+ return ioq->sched_queue;
+ return NULL;
+}
+EXPORT_SYMBOL(io_group_async_queue_prio);
+
+void io_group_set_async_queue(struct io_group *iog, int ioprio_class,
+ int ioprio, struct io_queue *ioq)
+{
+ switch (ioprio_class) {
+ case IOPRIO_CLASS_RT:
+ iog->async_queue[0][ioprio] = ioq;
+ break;
+ case IOPRIO_CLASS_BE:
+ iog->async_queue[1][ioprio] = ioq;
+ break;
+ case IOPRIO_CLASS_IDLE:
+ iog->async_idle_queue = ioq;
+ break;
+ default:
+ BUG();
+ }
+
+ /*
+ * Take the group reference and pin the queue. Group exit will
+ * clean it up
+ */
+ elv_get_ioq(ioq);
+}
+EXPORT_SYMBOL(io_group_set_async_queue);
+
+/*
+ * Release all the io group references to its async queues.
+ */
+static void
+io_put_io_group_queues(struct elevator_queue *e, struct io_group *iog)
+{
+ int i, j;
+
+ for (i = 0; i < 2; i++)
+ for (j = 0; j < IOPRIO_BE_NR; j++)
+ elv_release_ioq(e, &iog->async_queue[i][j]);
+
+ /* Free up async idle queue */
+ elv_release_ioq(e, &iog->async_idle_queue);
+}
+
+static struct io_group *io_alloc_root_group(struct request_queue *q,
+ struct elevator_queue *e, void *key)
+{
+ struct io_group *iog;
+ int i;
+
+ iog = kmalloc_node(sizeof(*iog), GFP_KERNEL | __GFP_ZERO, q->node);
+ if (iog == NULL)
+ return NULL;
+
+ for (i = 0; i < IO_IOPRIO_CLASSES; i++)
+ iog->sched_data.service_tree[i] = IO_SERVICE_TREE_INIT;
+
+ return iog;
+}
+
+static void io_free_root_group(struct elevator_queue *e)
+{
+ struct io_group *iog = e->efqd.root_group;
+ struct io_service_tree *st;
+ int i;
+
+ for (i = 0; i < IO_IOPRIO_CLASSES; i++) {
+ st = iog->sched_data.service_tree + i;
+ io_flush_idle_tree(st);
+ }
+
+ io_put_io_group_queues(e, iog);
+ kfree(iog);
+}
+
+static void elv_slab_kill(void)
+{
+ /*
+ * Caller already ensured that pending RCU callbacks are completed,
+ * so we should have no busy allocations at this point.
+ */
+ if (elv_ioq_pool)
+ kmem_cache_destroy(elv_ioq_pool);
+}
+
+static int __init elv_slab_setup(void)
+{
+ elv_ioq_pool = KMEM_CACHE(io_queue, 0);
+ if (!elv_ioq_pool)
+ goto fail;
+
+ return 0;
+fail:
+ elv_slab_kill();
+ return -ENOMEM;
+}
+
+/* Initialize fair queueing data associated with elevator */
+int elv_init_fq_data(struct request_queue *q, struct elevator_queue *e)
+{
+ struct io_group *iog;
+ struct elv_fq_data *efqd = &e->efqd;
+
+ if (!elv_iosched_fair_queuing_enabled(e))
+ return 0;
+
+ iog = io_alloc_root_group(q, e, efqd);
+ if (iog == NULL)
+ return 1;
+
+ efqd->root_group = iog;
+ efqd->queue = q;
+
+ init_timer(&efqd->idle_slice_timer);
+ efqd->idle_slice_timer.function = elv_idle_slice_timer;
+ efqd->idle_slice_timer.data = (unsigned long) efqd;
+
+ INIT_WORK(&efqd->unplug_work, elv_kick_queue);
+
+ efqd->elv_slice[0] = elv_slice_async;
+ efqd->elv_slice[1] = elv_slice_sync;
+ efqd->elv_slice_idle = elv_slice_idle;
+ efqd->hw_tag = 1;
+
+ return 0;
+}
+
+/*
+ * elv_exit_fq_data is called before we call elevator_exit_fn. Before
+ * we ask elevator to cleanup its queues, we do the cleanup here so
+ * that all the group and idle tree references to ioq are dropped. Later
+ * during elevator cleanup, ioc reference will be dropped which will lead
+ * to removal of ioscheduler queue as well as associated ioq object.
+ */
+void elv_exit_fq_data(struct elevator_queue *e)
+{
+ struct elv_fq_data *efqd = &e->efqd;
+
+ if (!elv_iosched_fair_queuing_enabled(e))
+ return;
+
+ elv_shutdown_timer_wq(e);
+
+ BUG_ON(timer_pending(&efqd->idle_slice_timer));
+ io_free_root_group(e);
+}
+
+/*
+ * This is called after the io scheduler has cleaned up its data structres.
+ * I don't think that this function is required. Right now just keeping it
+ * because cfq cleans up timer and work queue again after freeing up
+ * io contexts. To me io scheduler has already been drained out, and all
+ * the active queue have already been expired so time and work queue should
+ * not been activated during cleanup process.
+ *
+ * Keeping it here for the time being. Will get rid of it later.
+ */
+void elv_exit_fq_data_post(struct elevator_queue *e)
+{
+ struct elv_fq_data *efqd = &e->efqd;
+
+ if (!elv_iosched_fair_queuing_enabled(e))
+ return;
+
+ elv_shutdown_timer_wq(e);
+ BUG_ON(timer_pending(&efqd->idle_slice_timer));
+}
+
+
+static int __init elv_fq_init(void)
+{
+ if (elv_slab_setup())
+ return -ENOMEM;
+
+ /* could be 0 on HZ < 1000 setups */
+
+ if (!elv_slice_async)
+ elv_slice_async = 1;
+
+ if (!elv_slice_idle)
+ elv_slice_idle = 1;
+
+ return 0;
+}
+
+module_init(elv_fq_init);
diff --git a/block/elevator-fq.h b/block/elevator-fq.h
index 4554d7f..a7cbc0f 100644
--- a/block/elevator-fq.h
+++ b/block/elevator-fq.h
@@ -22,6 +22,10 @@
struct io_entity;
struct io_queue;

+#ifdef CONFIG_ELV_FAIR_QUEUING
+#define ELV_ATTR(name) \
+ __ATTR(name, S_IRUGO|S_IWUSR, elv_##name##_show, elv_##name##_store)
+
/**
* struct io_service_tree - per ioprio_class service tree.
* @active: tree for active entities (i.e., those backlogged).
@@ -149,15 +153,125 @@ struct io_entity {
struct io_queue {
struct io_entity entity;
atomic_t ref;
+ unsigned int flags;

/* Pointer to generic elevator fair queuing data structure */
struct elv_fq_data *efqd;
+ pid_t pid;
+
+ /* Number of requests queued on this io queue */
+ unsigned long nr_queued;
+
+ /* Requests dispatched from this queue */
+ int dispatched;
+
+ /* Keep a track of think time of processes in this queue */
+ unsigned long last_end_request;
+ unsigned long ttime_total;
+ unsigned long ttime_samples;
+ unsigned long ttime_mean;
+
+ unsigned long slice_end;
+
+ /* Pointer to io scheduler's queue */
+ void *sched_queue;
};

struct io_group {
struct io_sched_data sched_data;
+ /*
+ * async queue for each priority case for RT and BE class.
+ * Used only for cfq.
+ */
+
+ struct io_queue *async_queue[2][IOPRIO_BE_NR];
+ struct io_queue *async_idle_queue;
+
+ /*
+ * Used to track any pending rt requests so we can pre-empt current
+ * non-RT cfqq in service when this value is non-zero.
+ */
+ unsigned int busy_rt_queues;
+};
+
+struct elv_fq_data {
+ struct io_group *root_group;
+
+ struct request_queue *queue;
+ unsigned int busy_queues;
+
+ /* Number of requests queued */
+ int rq_queued;
+
+ /* Pointer to the ioscheduler queue being served */
+ void *active_queue;
+
+ /*
+ * queue-depth detection
+ */
+ int rq_in_driver;
+ int hw_tag;
+ int hw_tag_samples;
+ int rq_in_driver_peak;
+
+ /*
+ * elevator fair queuing layer has the capability to provide idling
+ * for ensuring fairness for processes doing dependent reads.
+ * This might be needed to ensure fairness among two processes doing
+ * synchronous reads in two different cgroups. noop and deadline don't
+ * have any notion of anticipation/idling. As of now, these are the
+ * users of this functionality.
+ */
+ unsigned int elv_slice_idle;
+ struct timer_list idle_slice_timer;
+ struct work_struct unplug_work;
+
+ /* Base slice length for sync and async queues */
+ unsigned int elv_slice[2];
};

+/* Logging facilities. */
+#define elv_log_ioq(efqd, ioq, fmt, args...) \
+ blk_add_trace_msg((efqd)->queue, "elv%d%c " fmt, (ioq)->pid, \
+ elv_ioq_sync(ioq) ? 'S' : 'A', ##args)
+
+#define elv_log(efqd, fmt, args...) \
+ blk_add_trace_msg((efqd)->queue, "elv " fmt, ##args)
+
+#define ioq_sample_valid(samples) ((samples) > 80)
+
+/* Some shared queue flag manipulation functions among elevators */
+
+enum elv_queue_state_flags {
+ ELV_QUEUE_FLAG_busy = 0, /* has requests or is under service */
+ ELV_QUEUE_FLAG_sync, /* synchronous queue */
+ ELV_QUEUE_FLAG_idle_window, /* elevator slice idling enabled */
+ ELV_QUEUE_FLAG_wait_request, /* waiting for a request */
+ ELV_QUEUE_FLAG_must_dispatch, /* must be allowed a dispatch */
+ ELV_QUEUE_FLAG_slice_new, /* no requests dispatched in slice */
+};
+
+#define ELV_IO_QUEUE_FLAG_FNS(name) \
+static inline void elv_mark_ioq_##name(struct io_queue *ioq) \
+{ \
+ (ioq)->flags |= (1 << ELV_QUEUE_FLAG_##name); \
+} \
+static inline void elv_clear_ioq_##name(struct io_queue *ioq) \
+{ \
+ (ioq)->flags &= ~(1 << ELV_QUEUE_FLAG_##name); \
+} \
+static inline int elv_ioq_##name(struct io_queue *ioq) \
+{ \
+ return ((ioq)->flags & (1 << ELV_QUEUE_FLAG_##name)) != 0; \
+}
+
+ELV_IO_QUEUE_FLAG_FNS(busy)
+ELV_IO_QUEUE_FLAG_FNS(sync)
+ELV_IO_QUEUE_FLAG_FNS(wait_request)
+ELV_IO_QUEUE_FLAG_FNS(must_dispatch)
+ELV_IO_QUEUE_FLAG_FNS(idle_window)
+ELV_IO_QUEUE_FLAG_FNS(slice_new)
+
static inline struct io_service_tree *
io_entity_service_tree(struct io_entity *entity)
{
@@ -169,4 +283,194 @@ io_entity_service_tree(struct io_entity *entity)

return sched_data->service_tree + idx;
}
+
+/* A request got dispatched from the io_queue. Do the accounting. */
+static inline void elv_ioq_request_dispatched(struct io_queue *ioq)
+{
+ ioq->dispatched++;
+}
+
+static inline int elv_ioq_slice_used(struct io_queue *ioq)
+{
+ if (elv_ioq_slice_new(ioq))
+ return 0;
+ if (time_before(jiffies, ioq->slice_end))
+ return 0;
+
+ return 1;
+}
+
+/* How many request are currently dispatched from the queue */
+static inline int elv_ioq_nr_dispatched(struct io_queue *ioq)
+{
+ return ioq->dispatched;
+}
+
+/* How many request are currently queued in the queue */
+static inline int elv_ioq_nr_queued(struct io_queue *ioq)
+{
+ return ioq->nr_queued;
+}
+
+static inline void elv_get_ioq(struct io_queue *ioq)
+{
+ atomic_inc(&ioq->ref);
+}
+
+static inline int elv_ioq_class_idle(struct io_queue *ioq)
+{
+ return ioq->entity.ioprio_class == IOPRIO_CLASS_IDLE;
+}
+
+static inline int elv_ioq_class_rt(struct io_queue *ioq)
+{
+ return ioq->entity.ioprio_class == IOPRIO_CLASS_RT;
+}
+
+static inline int elv_ioq_ioprio_class(struct io_queue *ioq)
+{
+ return ioq->entity.new_ioprio_class;
+}
+
+static inline int elv_ioq_ioprio(struct io_queue *ioq)
+{
+ return ioq->entity.new_ioprio;
+}
+
+static inline void elv_ioq_set_ioprio_class(struct io_queue *ioq,
+ int ioprio_class)
+{
+ ioq->entity.new_ioprio_class = ioprio_class;
+ ioq->entity.ioprio_changed = 1;
+}
+
+/**
+ * bfq_ioprio_to_weight - calc a weight from an ioprio.
+ * @ioprio: the ioprio value to convert.
+ */
+static inline unsigned int bfq_ioprio_to_weight(int ioprio)
+{
+ WARN_ON(ioprio < 0 || ioprio >= IOPRIO_BE_NR);
+ return IOPRIO_BE_NR - ioprio;
+}
+
+static inline void elv_ioq_set_ioprio(struct io_queue *ioq, int ioprio)
+{
+ ioq->entity.new_ioprio = ioprio;
+ ioq->entity.new_weight = bfq_ioprio_to_weight(ioprio);
+ ioq->entity.ioprio_changed = 1;
+}
+
+static inline void *ioq_sched_queue(struct io_queue *ioq)
+{
+ if (ioq)
+ return ioq->sched_queue;
+ return NULL;
+}
+
+static inline struct io_group *ioq_to_io_group(struct io_queue *ioq)
+{
+ return container_of(ioq->entity.sched_data, struct io_group,
+ sched_data);
+}
+
+extern ssize_t elv_slice_idle_show(struct elevator_queue *q, char *name);
+extern ssize_t elv_slice_idle_store(struct elevator_queue *q, const char *name,
+ size_t count);
+extern ssize_t elv_slice_sync_show(struct elevator_queue *q, char *name);
+extern ssize_t elv_slice_sync_store(struct elevator_queue *q, const char *name,
+ size_t count);
+extern ssize_t elv_slice_async_show(struct elevator_queue *q, char *name);
+extern ssize_t elv_slice_async_store(struct elevator_queue *q, const char *name,
+ size_t count);
+
+/* Functions used by elevator.c */
+extern int elv_init_fq_data(struct request_queue *q, struct elevator_queue *e);
+extern void elv_exit_fq_data(struct elevator_queue *e);
+extern void elv_exit_fq_data_post(struct elevator_queue *e);
+
+extern void elv_ioq_request_add(struct request_queue *q, struct request *rq);
+extern void elv_ioq_request_removed(struct elevator_queue *e,
+ struct request *rq);
+extern void elv_fq_dispatched_request(struct elevator_queue *e,
+ struct request *rq);
+
+extern void elv_fq_activate_rq(struct request_queue *q, struct request *rq);
+extern void elv_fq_deactivate_rq(struct request_queue *q, struct request *rq);
+
+extern void elv_ioq_completed_request(struct request_queue *q,
+ struct request *rq);
+
+extern void *elv_fq_select_ioq(struct request_queue *q, int force);
+
+/* Functions used by io schedulers */
+extern void elv_put_ioq(struct io_queue *ioq);
+extern void __elv_ioq_slice_expired(struct request_queue *q,
+ struct io_queue *ioq);
+extern int elv_init_ioq(struct elevator_queue *eq, struct io_queue *ioq,
+ struct io_group *iog, void *sched_queue, int ioprio_class,
+ int ioprio, int is_sync);
+extern void elv_schedule_dispatch(struct request_queue *q);
+extern int elv_hw_tag(struct elevator_queue *e);
+extern void *elv_active_sched_queue(struct elevator_queue *e);
+extern int elv_mod_idle_slice_timer(struct elevator_queue *eq,
+ unsigned long expires);
+extern int elv_del_idle_slice_timer(struct elevator_queue *eq);
+extern unsigned int elv_get_slice_idle(struct elevator_queue *eq);
+extern void *io_group_async_queue_prio(struct io_group *iog, int ioprio_class,
+ int ioprio);
+extern void io_group_set_async_queue(struct io_group *iog, int ioprio_class,
+ int ioprio, struct io_queue *ioq);
+extern struct io_group *io_get_io_group(struct request_queue *q);
+extern int elv_nr_busy_ioq(struct elevator_queue *e);
+extern struct io_queue *elv_alloc_ioq(struct request_queue *q, gfp_t gfp_mask);
+extern void elv_free_ioq(struct io_queue *ioq);
+
+#else /* CONFIG_ELV_FAIR_QUEUING */
+
+static inline int elv_init_fq_data(struct request_queue *q,
+ struct elevator_queue *e)
+{
+ return 0;
+}
+
+static inline void elv_exit_fq_data(struct elevator_queue *e) {}
+static inline void elv_exit_fq_data_post(struct elevator_queue *e) {}
+
+static inline void elv_fq_activate_rq(struct request_queue *q,
+ struct request *rq)
+{
+}
+
+static inline void elv_fq_deactivate_rq(struct request_queue *q,
+ struct request *rq)
+{
+}
+
+static inline void elv_fq_dispatched_request(struct elevator_queue *e,
+ struct request *rq)
+{
+}
+
+static inline void elv_ioq_request_removed(struct elevator_queue *e,
+ struct request *rq)
+{
+}
+
+static inline void elv_ioq_request_add(struct request_queue *q,
+ struct request *rq)
+{
+}
+
+static inline void elv_ioq_completed_request(struct request_queue *q,
+ struct request *rq)
+{
+}
+
+static inline void *ioq_sched_queue(struct io_queue *ioq) { return NULL; }
+static inline void *elv_fq_select_ioq(struct request_queue *q, int force)
+{
+ return NULL;
+}
+#endif /* CONFIG_ELV_FAIR_QUEUING */
#endif /* _BFQ_SCHED_H */
diff --git a/block/elevator.c b/block/elevator.c
index ca86192..357f529 100644
--- a/block/elevator.c
+++ b/block/elevator.c
@@ -226,6 +226,9 @@ static struct elevator_queue *elevator_alloc(struct request_queue *q,
for (i = 0; i < ELV_HASH_ENTRIES; i++)
INIT_HLIST_HEAD(&eq->hash[i]);

+ if (elv_init_fq_data(q, eq))
+ goto err;
+
return eq;
err:
kfree(eq);
@@ -296,9 +299,11 @@ EXPORT_SYMBOL(elevator_init);
void elevator_exit(struct elevator_queue *e)
{
mutex_lock(&e->sysfs_lock);
+ elv_exit_fq_data(e);
if (e->ops->elevator_exit_fn)
e->ops->elevator_exit_fn(e);
e->ops = NULL;
+ elv_exit_fq_data_post(e);
mutex_unlock(&e->sysfs_lock);

kobject_put(&e->kobj);
@@ -425,6 +430,7 @@ void elv_dispatch_sort(struct request_queue *q, struct request *rq)
elv_rqhash_del(q, rq);

q->nr_sorted--;
+ elv_fq_dispatched_request(q->elevator, rq);

boundary = q->end_sector;
stop_flags = REQ_SOFTBARRIER | REQ_HARDBARRIER | REQ_STARTED;
@@ -465,6 +471,7 @@ void elv_dispatch_add_tail(struct request_queue *q, struct request *rq)
elv_rqhash_del(q, rq);

q->nr_sorted--;
+ elv_fq_dispatched_request(q->elevator, rq);

q->end_sector = rq_end_sector(rq);
q->boundary_rq = rq;
@@ -532,6 +539,7 @@ void elv_merge_requests(struct request_queue *q, struct request *rq,
elv_rqhash_del(q, next);

q->nr_sorted--;
+ elv_ioq_request_removed(e, next);
q->last_merge = rq;
}

@@ -638,12 +646,8 @@ void elv_insert(struct request_queue *q, struct request *rq, int where)
q->last_merge = rq;
}

- /*
- * Some ioscheds (cfq) run q->request_fn directly, so
- * rq cannot be accessed after calling
- * elevator_add_req_fn.
- */
q->elevator->ops->elevator_add_req_fn(q, rq);
+ elv_ioq_request_add(q, rq);
break;

case ELEVATOR_INSERT_REQUEUE:
@@ -742,13 +746,12 @@ EXPORT_SYMBOL(elv_add_request);

int elv_queue_empty(struct request_queue *q)
{
- struct elevator_queue *e = q->elevator;
-
if (!list_empty(&q->queue_head))
return 0;

- if (e->ops->elevator_queue_empty_fn)
- return e->ops->elevator_queue_empty_fn(q);
+ /* Hopefully nr_sorted works and no need to call queue_empty_fn */
+ if (q->nr_sorted)
+ return 0;

return 1;
}
@@ -828,8 +831,11 @@ void elv_completed_request(struct request_queue *q, struct request *rq)
*/
if (blk_account_rq(rq)) {
q->in_flight[rq_is_sync(rq)]--;
- if (blk_sorted_rq(rq) && e->ops->elevator_completed_req_fn)
- e->ops->elevator_completed_req_fn(q, rq);
+ if (blk_sorted_rq(rq)) {
+ if (e->ops->elevator_completed_req_fn)
+ e->ops->elevator_completed_req_fn(q, rq);
+ elv_ioq_completed_request(q, rq);
+ }
}

/*
@@ -1125,3 +1131,17 @@ struct request *elv_rb_latter_request(struct request_queue *q,
return NULL;
}
EXPORT_SYMBOL(elv_rb_latter_request);
+
+/* Get the io scheduler queue pointer. For cfq, it is stored in rq->ioq*/
+void *elv_get_sched_queue(struct request_queue *q, struct request *rq)
+{
+ return ioq_sched_queue(req_ioq(rq));
+}
+EXPORT_SYMBOL(elv_get_sched_queue);
+
+/* Select an ioscheduler queue to dispatch request from. */
+void *elv_select_sched_queue(struct request_queue *q, int force)
+{
+ return ioq_sched_queue(elv_fq_select_ioq(q, force));
+}
+EXPORT_SYMBOL(elv_select_sched_queue);
diff --git a/include/linux/blkdev.h b/include/linux/blkdev.h
index 8963d91..551e17d 100644
--- a/include/linux/blkdev.h
+++ b/include/linux/blkdev.h
@@ -234,6 +234,11 @@ struct request {

/* for bidi */
struct request *next_rq;
+
+#ifdef CONFIG_ELV_FAIR_QUEUING
+ /* io queue request belongs to */
+ struct io_queue *ioq;
+#endif
};

static inline unsigned short req_get_ioprio(struct request *req)
@@ -241,6 +246,15 @@ static inline unsigned short req_get_ioprio(struct request *req)
return req->ioprio;
}

+static inline struct io_queue *req_ioq(struct request *req)
+{
+#ifdef CONFIG_ELV_FAIR_QUEUING
+ return req->ioq;
+#else
+ return NULL;
+#endif
+}
+
/*
* State information carried for REQ_TYPE_PM_SUSPEND and REQ_TYPE_PM_RESUME
* requests. Some step values could eventually be made generic.
diff --git a/include/linux/elevator.h b/include/linux/elevator.h
index 1cb3372..81f1ed8 100644
--- a/include/linux/elevator.h
+++ b/include/linux/elevator.h
@@ -2,6 +2,7 @@
#define _LINUX_ELEVATOR_H

#include <linux/percpu.h>
+#include "../../block/elevator-fq.h"

#ifdef CONFIG_BLOCK

@@ -29,6 +30,18 @@ typedef void (elevator_deactivate_req_fn) (struct request_queue *, struct reques

typedef void *(elevator_init_fn) (struct request_queue *);
typedef void (elevator_exit_fn) (struct elevator_queue *);
+#ifdef CONFIG_ELV_FAIR_QUEUING
+typedef void (elevator_free_sched_queue_fn) (struct elevator_queue*, void *);
+typedef void (elevator_active_ioq_set_fn) (struct request_queue*, void *, int);
+typedef void (elevator_active_ioq_reset_fn) (struct request_queue *, void*);
+typedef void (elevator_arm_slice_timer_fn) (struct request_queue*, void*);
+typedef int (elevator_should_preempt_fn) (struct request_queue*, void*,
+ struct request*);
+typedef int (elevator_update_idle_window_fn) (struct elevator_queue*, void*,
+ struct request*);
+typedef struct io_queue* (elevator_close_cooperator_fn) (struct request_queue*,
+ void*, int probe);
+#endif

struct elevator_ops
{
@@ -56,6 +69,17 @@ struct elevator_ops
elevator_init_fn *elevator_init_fn;
elevator_exit_fn *elevator_exit_fn;
void (*trim)(struct io_context *);
+
+#ifdef CONFIG_ELV_FAIR_QUEUING
+ elevator_free_sched_queue_fn *elevator_free_sched_queue_fn;
+ elevator_active_ioq_set_fn *elevator_active_ioq_set_fn;
+ elevator_active_ioq_reset_fn *elevator_active_ioq_reset_fn;
+
+ elevator_arm_slice_timer_fn *elevator_arm_slice_timer_fn;
+ elevator_should_preempt_fn *elevator_should_preempt_fn;
+ elevator_update_idle_window_fn *elevator_update_idle_window_fn;
+ elevator_close_cooperator_fn *elevator_close_cooperator_fn;
+#endif
};

#define ELV_NAME_MAX (16)
@@ -76,6 +100,9 @@ struct elevator_type
struct elv_fs_entry *elevator_attrs;
char elevator_name[ELV_NAME_MAX];
struct module *elevator_owner;
+#ifdef CONFIG_ELV_FAIR_QUEUING
+ int elevator_features;
+#endif
};

/*
@@ -89,6 +116,10 @@ struct elevator_queue
struct elevator_type *elevator_type;
struct mutex sysfs_lock;
struct hlist_head *hash;
+#ifdef CONFIG_ELV_FAIR_QUEUING
+ /* fair queuing data */
+ struct elv_fq_data efqd;
+#endif
};

/*
@@ -207,5 +238,25 @@ enum {
__val; \
})

+/* iosched can let elevator know their feature set/capability */
+#ifdef CONFIG_ELV_FAIR_QUEUING
+
+/* iosched wants to use fair queuing logic of elevator layer */
+#define ELV_IOSCHED_NEED_FQ 1
+
+static inline int elv_iosched_fair_queuing_enabled(struct elevator_queue *e)
+{
+ return (e->elevator_type->elevator_features) & ELV_IOSCHED_NEED_FQ;
+}
+
+#else /* ELV_IOSCHED_FAIR_QUEUING */
+
+static inline int elv_iosched_fair_queuing_enabled(struct elevator_queue *e)
+{
+ return 0;
+}
+#endif /* ELV_IOSCHED_FAIR_QUEUING */
+extern void *elv_get_sched_queue(struct request_queue *q, struct request *rq);
+extern void *elv_select_sched_queue(struct request_queue *q, int force);
#endif /* CONFIG_BLOCK */
#endif
--
1.6.0.6

2009-07-02 20:04:43

by Vivek Goyal

Subject: [PATCH 05/25] io-controller: Charge for time slice based on average disk rate

o There are situations where a queue gets expired very soon and it looks
as if time slice used by that queue is zero. For example, If an async
queue dispatches a bunch of requests and queue is expired before first
request completes. Another example is where a queue is expired as soon
as first request completes and queue has no more requests (sync queues
on SSD).

o Currently we just charge 25% of slice length in such cases. This patch tries
to improve on that approximation by keeping a track of average disk rate
and charging for time by nr_sectors/disk_rate.

o This is still experimental, not very sure if it gives measurable improvement
or not. May be a better scheme is to use something more granular than jiffies
for time keeping for io queues.

Signed-off-by: Vivek Goyal <[email protected]>
---
block/elevator-fq.c | 97 +++++++++++++++++++++++++++++++++++++++++++++++----
block/elevator-fq.h | 11 ++++++
2 files changed, 101 insertions(+), 7 deletions(-)

diff --git a/block/elevator-fq.c b/block/elevator-fq.c
index 6f23d7e..67c02b9 100644
--- a/block/elevator-fq.c
+++ b/block/elevator-fq.c
@@ -23,6 +23,9 @@ const int elv_slice_async_rq = 2;
int elv_slice_idle = HZ / 125;
static struct kmem_cache *elv_ioq_pool;

+/* Maximum Window length for updating average disk rate */
+static int elv_rate_sampling_window = HZ / 10;
+
#define ELV_SLICE_SCALE (5)
#define ELV_HW_QUEUE_MIN (5)

@@ -941,6 +944,47 @@ static void elv_ioq_update_io_thinktime(struct io_queue *ioq)
ioq->ttime_mean = (ioq->ttime_total + 128) / ioq->ttime_samples;
}

+static void elv_update_io_rate(struct elv_fq_data *efqd, struct request *rq)
+{
+ long elapsed = jiffies - efqd->rate_sampling_start;
+ unsigned long total;
+
+ /* sampling window is off */
+ if (!efqd->rate_sampling_start)
+ return;
+
+ efqd->rate_sectors_current += blk_rq_sectors(rq);
+
+ if (efqd->rq_in_driver && (elapsed < elv_rate_sampling_window))
+ return;
+
+ efqd->rate_sectors = (7*efqd->rate_sectors +
+ 256*efqd->rate_sectors_current) / 8;
+
+ if (!elapsed) {
+ /*
+ * updating rate before a jiffy could complete. Could be a
+ * problem with fast queuing/non-queuing hardware. Should we
+ * look at higher resolution time source?
+ *
+ * In case of non-queuing hardware we will probably not try to
+ * dispatch from multiple queues and will be able to account
+ * for disk time used and will not need this approximation
+ * anyway?
+ */
+ elapsed = 1;
+ }
+
+ efqd->rate_time = (7*efqd->rate_time + 256*elapsed) / 8;
+ total = efqd->rate_sectors + (efqd->rate_time/2);
+ efqd->mean_rate = total/efqd->rate_time;
+
+ elv_log(efqd, "mean_rate=%d, t=%d s=%d", efqd->mean_rate,
+ elapsed, efqd->rate_sectors_current);
+ efqd->rate_sampling_start = 0;
+ efqd->rate_sectors_current = 0;
+}
+
/*
* Disable idle window if the process thinks too long.
* This idle flag can also be updated by io scheduler.
@@ -1231,6 +1275,34 @@ static void elv_del_ioq_busy(struct elevator_queue *e, struct io_queue *ioq,
}

/*
+ * Calculate the effective disk time used by the queue based on how many
+ * sectors queue has dispatched and what is the average disk rate
+ * Returns disk time in ms.
+ */
+static inline unsigned long elv_disk_time_used(struct request_queue *q,
+ struct io_queue *ioq)
+{
+ struct elv_fq_data *efqd = &q->elevator->efqd;
+ struct io_entity *entity = &ioq->entity;
+ unsigned long jiffies_used = 0;
+
+ if (!efqd->mean_rate)
+ return entity->budget/4;
+
+ /* Charge the queue based on average disk rate */
+ jiffies_used = ioq->nr_sectors/efqd->mean_rate;
+
+ if (!jiffies_used)
+ jiffies_used = 1;
+
+ elv_log_ioq(efqd, ioq, "disk time=%ldms sect=%lu rate=%ld",
+ jiffies_to_msecs(jiffies_used),
+ ioq->nr_sectors, efqd->mean_rate);
+
+ return jiffies_used;
+}
+
+/*
* Do the accounting. Determine how much service (in terms of time slices)
* current queue used and adjust the start, finish time of queue and vtime
* of the tree accordingly.
@@ -1248,8 +1320,10 @@ static void elv_del_ioq_busy(struct elevator_queue *e, struct io_queue *ioq,
* from next queue.
*
* Not sure how to determine the time consumed by queue in such scenarios.
- * Currently as a crude approximation, we are charging 25% of time slice
- * for such cases. A better mechanism is needed for accurate accounting.
+ * Currently as a crude approximation, try to keep track of average disk rate
+ * and charge the queue based on number of sectors transferred. If suffcient
+ * disk rate data is not available then we are charging 25% of time slice
+ * for such cases. A better mechanism, is needed for accurate accounting.
*/
void __elv_ioq_slice_expired(struct request_queue *q, struct io_queue *ioq)
{
@@ -1270,9 +1344,9 @@ void __elv_ioq_slice_expired(struct request_queue *q, struct io_queue *ioq)
* reuqest from the queue got completed. Of course we are not planning
* to idle on the queue otherwise we would not have expired it.
*
- * Charge for the 25% slice in such cases. This is not the best thing
- * to do but at the same time not very sure what's the next best
- * thing to do.
+ * Charge the queue based on average disk rate or the 25% slice if
+ * mean rate is 0. This is not the best thing to do but at the same
+ * time not very sure what's the next best thing to do.
*
* This arises from that fact that we don't have the notion of
* one queue being operational at one time. io scheduler can dispatch
@@ -1282,7 +1356,7 @@ void __elv_ioq_slice_expired(struct request_queue *q, struct io_queue *ioq)
* the requests to finish. But this will reduce throughput.
*/
if (!ioq->slice_end)
- slice_used = entity->budget/4;
+ slice_used = elv_disk_time_used(q, ioq);
else {
if (time_after(ioq->slice_end, jiffies)) {
slice_unused = ioq->slice_end - jiffies;
@@ -1292,7 +1366,7 @@ void __elv_ioq_slice_expired(struct request_queue *q, struct io_queue *ioq)
* completing first request. Charge 25% of
* slice.
*/
- slice_used = entity->budget/4;
+ slice_used = elv_disk_time_used(q, ioq);
} else
slice_used = entity->budget - slice_unused;
} else {
@@ -1310,6 +1384,8 @@ void __elv_ioq_slice_expired(struct request_queue *q, struct io_queue *ioq)
BUG_ON(ioq != efqd->active_queue);
elv_reset_active_ioq(efqd);

+ /* Queue is being expired. Reset number of secotrs dispatched */
+ ioq->nr_sectors = 0;
if (!ioq->nr_queued)
elv_del_ioq_busy(q->elevator, ioq, 1);
else
@@ -1671,6 +1747,7 @@ void elv_fq_dispatched_request(struct elevator_queue *e, struct request *rq)

BUG_ON(!ioq);
elv_ioq_request_dispatched(ioq);
+ ioq->nr_sectors += blk_rq_sectors(rq);
elv_ioq_request_removed(e, rq);
elv_clear_ioq_must_dispatch(ioq);
}
@@ -1683,6 +1760,10 @@ void elv_fq_activate_rq(struct request_queue *q, struct request *rq)
return;

efqd->rq_in_driver++;
+
+ if (!efqd->rate_sampling_start)
+ efqd->rate_sampling_start = jiffies;
+
elv_log_ioq(efqd, rq->ioq, "activate rq, drv=%d",
efqd->rq_in_driver);
}
@@ -1746,6 +1827,8 @@ void elv_ioq_completed_request(struct request_queue *q, struct request *rq)
efqd->rq_in_driver--;
ioq->dispatched--;

+ elv_update_io_rate(efqd, rq);
+
if (sync)
ioq->last_end_request = jiffies;

diff --git a/block/elevator-fq.h b/block/elevator-fq.h
index a7cbc0f..4b69239 100644
--- a/block/elevator-fq.h
+++ b/block/elevator-fq.h
@@ -165,6 +165,9 @@ struct io_queue {
/* Requests dispatched from this queue */
int dispatched;

+ /* Number of sectors dispatched in current dispatch round */
+ unsigned long nr_sectors;
+
/* Keep a track of think time of processes in this queue */
unsigned long last_end_request;
unsigned long ttime_total;
@@ -228,6 +231,14 @@ struct elv_fq_data {

/* Base slice length for sync and async queues */
unsigned int elv_slice[2];
+
+ /* Fields for keeping track of average disk rate */
+ unsigned long rate_sectors; /* number of sectors finished */
+ unsigned long rate_time; /* jiffies elapsed */
+ unsigned long mean_rate; /* sectors per jiffy */
+ unsigned long long rate_sampling_start; /*sampling window start jifies*/
+ /* number of sectors finished io during current sampling window */
+ unsigned long rate_sectors_current;
};

/* Logging facilities. */
--
1.6.0.6

2009-07-02 20:04:29

by Vivek Goyal

Subject: [PATCH 01/25] io-controller: Documentation

o Documentation for io-controller.

Signed-off-by: Vivek Goyal <[email protected]>
---
Documentation/block/00-INDEX | 2 +
Documentation/block/io-controller.txt | 378 +++++++++++++++++++++++++++++++++
2 files changed, 380 insertions(+), 0 deletions(-)
create mode 100644 Documentation/block/io-controller.txt

diff --git a/Documentation/block/00-INDEX b/Documentation/block/00-INDEX
index 961a051..dc8bf95 100644
--- a/Documentation/block/00-INDEX
+++ b/Documentation/block/00-INDEX
@@ -10,6 +10,8 @@ capability.txt
- Generic Block Device Capability (/sys/block/<disk>/capability)
deadline-iosched.txt
- Deadline IO scheduler tunables
+io-controller.txt
+ - IO controller for provding hierarchical IO scheduling
ioprio.txt
- Block io priorities (in CFQ scheduler)
request.txt
diff --git a/Documentation/block/io-controller.txt b/Documentation/block/io-controller.txt
new file mode 100644
index 0000000..b2a96b3
--- /dev/null
+++ b/Documentation/block/io-controller.txt
@@ -0,0 +1,378 @@
+ IO Controller
+ =============
+
+Overview
+========
+
+This patchset implements a proportional weight IO controller. That is one
+can create cgroups and assign prio/weights to those cgroups and task group
+will get access to disk proportionate to the weight of the group.
+
+These patches modify elevator layer and individual IO schedulers to do
+IO control hence this io controller works only on block devices which use
+one of the standard io schedulers can not be used with any xyz logical block
+device.
+
+The assumption/thought behind modifying IO scheduler is that resource control
+is needed only on leaf nodes where the actual contention for resources is
+present and not on intertermediate logical block devices.
+
+Consider following hypothetical scenario. Lets say there are three physical
+disks, namely sda, sdb and sdc. Two logical volumes (lv0 and lv1) have been
+created on top of these. Some part of sdb is in lv0 and some part is in lv1.
+
+ lv0 lv1
+ / \ / \
+ sda sdb sdc
+
+Also consider following cgroup hierarchy
+
+ root
+ / \
+ A B
+ / \ / \
+ T1 T2 T3 T4
+
+A and B are two cgroups and T1, T2, T3 and T4 are tasks with-in those cgroups.
+Assuming T1, T2, T3 and T4 are doing IO on lv0 and lv1. These tasks should
+get their fair share of bandwidth on disks sda, sdb and sdc. There is no
+IO control on intermediate logical block nodes (lv0, lv1).
+
+So if tasks T1 and T2 are doing IO on lv0 and T3 and T4 are doing IO on lv1
+only, there will not be any contetion for resources between group A and B if
+IO is going to sda or sdc. But if actual IO gets translated to disk sdb, then
+IO scheduler associated with the sdb will distribute disk bandwidth to
+group A and B proportionate to their weight.
+
+CFQ already has the notion of fairness and it provides differential disk
+access based on priority and class of the task. Just that it is flat and
+with cgroup stuff, it needs to be made hierarchical to achive a good
+hierarchical control on IO.
+
+Rest of the IO schedulers (noop, deadline and AS) don't have any notion
+of fairness among various threads. They maintain only one queue where all
+the IO gets queued (internally this queue is split in read and write queue
+for deadline and AS). With this patchset, now we maintain one queue per
+cgropu per device and then try to do fair queuing among those queues.
+
+One of the concerns raised with modifying IO schedulers was that we don't
+want to replicate the code in all the IO schedulers. These patches share
+the fair queuing code which has been moved to a common layer (elevator
+layer). Hence we don't end up replicating code across IO schedulers. Following
+diagram depicts the concept.
+
+ --------------------------------
+ | Elevator Layer + Fair Queuing |
+ --------------------------------
+ | | | |
+ NOOP DEADLINE AS CFQ
+
+Design
+======
+This patchset primarily uses BFQ (Budget Fair Queuing) code to provide
+fairness among different IO queues. Fabio and Paolo implemented BFQ which uses
+B-WF2Q+ algorithm for fair queuing.
+
+Why BFQ?
+
+- Not sure if weighted round robin logic of CFQ can be easily extended for
+ hierarchical mode. One of the things is that we can not keep dividing
+ the time slice of parent group among childrens. Deeper we go in hierarchy
+ time slice will get smaller.
+
+ One of the ways to implement hierarchical support could be to keep track
+ of virtual time and service provided to queue/group and select a queue/group
+ for service based on any of the various available algoriths.
+
+ BFQ already had support for hierarchical scheduling, taking those patches
+ was easier.
+
+- BFQ was designed to provide tighter bounds/delay w.r.t service provided
+ to a queue. Delay/Jitter with BFQ is O(1).
+
+ Note: BFQ originally used amount of IO done (number of sectors) as notion
+ of service provided. IOW, it tried to provide fairness in terms of
+ actual IO done and not in terms of actual time disk access was
+ given to a queue.
+
+ This patcheset modified BFQ to provide fairness in time domain because
+ that's what CFQ does. So idea was try not to deviate too much from
+ the CFQ behavior initially.
+
+ Providing fairness in time domain makes accounting trciky because
+ due to command queueing, at one time there might be multiple requests
+ from different queues and there is no easy way to find out how much
+ disk time actually was consumed by the requests of a particular
+ queue. More about this in comments in source code.
+
+We have taken BFQ code as starting point for providing fairness among groups
+because it already contained lots of features which we required to implement
+hierarhical IO scheduling. With this patch set, I am not trying to ensure O(1)
+delay here as my goal is to provide fairness among groups. Most likely that
+will mean that latencies are not worse than what cfq currently provides (if
+not improved ones). Once fairness is ensured, one can look into more in
+ensuring O(1) latencies.
+
+From data structure point of view, one can think of a tree per device, where
+io groups and io queues are hanging and are being scheduled using B-WF2Q+
+algorithm. io_queue, is end queue where requests are actually stored and
+dispatched from (like cfqq).
+
+These io queues are primarily created by and managed by end io schedulers
+depending on its semantics. For example, noop, deadline and AS ioschedulers
+keep one io queues per cgroup and cfqq keeps one io queue per io_context in
+a cgroup (apart from async queues).
+
+A request is mapped to an io group by elevator layer and which io queue it
+is mapped to with in group depends on ioscheduler. Currently "current" task
+is used to determine the cgroup (hence io group) of the request. Down the
+line we need to make use of bio-cgroup patches to map delayed writes to
+right group.
+
+Going back to old behavior
+==========================
+In new scheme of things essentially we are creating hierarchical fair
+queuing logic in elevator layer and chaning IO schedulers to make use of
+that logic so that end IO schedulers start supporting hierarchical scheduling.
+
+Elevator layer continues to support the old interfaces. So even if fair queuing
+is enabled at elevator layer, one can have both new hierchical scheduler as
+well as old non-hierarchical scheduler operating.
+
+Also noop, deadline and AS have option of enabling hierarchical scheduling.
+If it is selected, fair queuing is done in hierarchical manner. If hierarchical
+scheduling is disabled, noop, deadline and AS should retain their existing
+behavior.
+
+CFQ is the only exception where one can not disable fair queuing as it is
+needed for provding fairness among various threads even in non-hierarchical
+mode.
+
+Various user visible config options
+===================================
+CONFIG_IOSCHED_NOOP_HIER
+ - Enables hierchical fair queuing in noop. Not selecting this option
+ leads to old behavior of noop.
+
+CONFIG_IOSCHED_DEADLINE_HIER
+ - Enables hierchical fair queuing in deadline. Not selecting this
+ option leads to old behavior of deadline.
+
+CONFIG_IOSCHED_AS_HIER
+ - Enables hierchical fair queuing in AS. Not selecting this option
+ leads to old behavior of AS.
+
+CONFIG_IOSCHED_CFQ_HIER
+ - Enables hierarchical fair queuing in CFQ. Not selecting this option
+ still does fair queuing among various queus but it is flat and not
+ hierarchical.
+
+CGROUP_BLKIO
+ - This option enables blkio-cgroup controller for IO tracking
+ purposes. That means, by this controller one can attribute a write
+ to the original cgroup and not assume that it belongs to submitting
+ thread.
+
+CONFIG_TRACK_ASYNC_CONTEXT
+ - Currently CFQ attributes the writes to the submitting thread and
+ caches the async queue pointer in the io context of the process.
+ If this option is set, it tells cfq and elevator fair queuing logic
+ that for async writes make use of IO tracking patches and attribute
+ writes to original cgroup and not to write submitting thread.
+
+CONFIG_DEBUG_GROUP_IOSCHED
+ - Throws extra debug messages in blktrace output helpful in doing
+ doing debugging in hierarchical setup.
+
+ - Also allows for export of extra debug statistics like group queue
+ and dequeue statistics on device through cgroup interface.
+
+Config options selected automatically
+=====================================
+These config options are not user visible and are selected/deselected
+automatically based on IO scheduler configurations.
+
+CONFIG_ELV_FAIR_QUEUING
+ - Enables/Disables the fair queuing logic at elevator layer.
+
+CONFIG_GROUP_IOSCHED
+ - Enables/Disables hierarchical queuing and associated cgroup bits.
+
+HOWTO
+=====
+So far I have done very simple testing of running two dd threads in two
+different cgroups. Here is what you can do.
+
+- Enable hierarchical scheduling in io scheuduler of your choice (say cfq).
+ CONFIG_IOSCHED_CFQ_HIER=y
+
+- Enable IO tracking for async writes.
+ CONFIG_TRACK_ASYNC_CONTEXT=y
+
+ (This will automatically select CGROUP_BLKIO)
+
+- Compile and boot into kernel and mount IO controller and blkio io tracking
+ controller.
+
+ mount -t cgroup -o io,blkio none /cgroup
+
+- Create two cgroups
+ mkdir -p /cgroup/test1/ /cgroup/test2
+
+- Set weights of group test1 and test2
+ echo 1000 > /cgroup/test1/io.weight
+ echo 500 > /cgroup/test2/io.weight
+
+- Set "fairness" parameter to 1 at the disk you are testing.
+
+ echo 1 > /sys/block/<disk>/queue/iosched/fairness
+
+- Create two same size files (say 512MB each) on same disk (file1, file2) and
+ launch two dd threads in different cgroup to read those files. Make sure
+ right io scheduler is being used for the block device where files are
+ present (the one you compiled in hierarchical mode).
+
+ sync
+ echo 3 > /proc/sys/vm/drop_caches
+
+ dd if=/mnt/sdb/zerofile1 of=/dev/null &
+ echo $! > /cgroup/test1/tasks
+ cat /cgroup/test1/tasks
+
+ dd if=/mnt/sdb/zerofile2 of=/dev/null &
+ echo $! > /cgroup/test2/tasks
+ cat /cgroup/test2/tasks
+
+- At macro level, first dd should finish first. To get more precise data, keep
+ on looking at (with the help of script), at io.disk_time and io.disk_sectors
+ files of both test1 and test2 groups. This will tell how much disk time
+ (in milli seconds), each group got and how many secotors each group
+ dispatched to the disk. We provide fairness in terms of disk time, so
+ ideally io.disk_time of cgroups should be in proportion to the weight.
+ (It is hard to achieve though :-)).
+
+Regarding "fairness" parameter
+==============================
+IO controller has introduced a "fairness" tunable for every io scheduler.
+Currently this tunable can assume values 0, 1 and 2.
+
+There are places where io schedulers are geared towards throughput. Sometimes
+fairness and throughput don't go together. This tunable helps choose fairness
+over throughput depending on the need.
+
+0 --> We should achive existing io scheduler behavior. Some of the special
+ fairness hooks are disabled.
+
+1 --> Helps in achieving the better fairness for sync queues.
+
+2 --> If buffered writes come into play, use this. For example, One cgroup
+ doing sync reads and other cgroup doing buffered writes, use "2" to
+ provide better fairness/isolation between two cgroups.
+
+Details of cgroup files
+=======================
+- io.ioprio_class
+ - Specifies class of the cgroup (RT, BE, IDLE). This is default io
+ class of the group on all the devices until and unless overridden by
+ per device rule. (See io.policy).
+
+ 1 = RT; 2 = BE, 3 = IDLE
+
+- io.weight
+ - Specifies per cgroup weight. This is default weight of the group
+ on all the devices until and unless overridden by per device rule.
+ (See io.policy).
+
+- io.disk_time
+ - disk time allocated to cgroup per device in milliseconds. First
+ two fields specify the major and minor number of the device and
+ third field specifies the disk time allocated to group in
+ milliseconds.
+
+- io.disk_sectors
+ - number of sectors transferred to/from disk by the group. First
+ two fields specify the major and minor number of the device and
+ third field specifies the number of sectors transferred by the
+ group to/from the device.
+
+- io.disk_queue
+ - Debugging aid only enabled if CONFIG_DEBUG_GROUP_IOSCHED=y. This
+ gives the statistics about how many a times a group was queued
+ on service tree of the device. First two fields specify the major
+ and minor number of the device and third field specifies the number
+ of times a group was queued on a particular device.
+
+- io.disk_queue
+ - Debugging aid only enabled if CONFIG_DEBUG_GROUP_IOSCHED=y. This
+ gives the statistics about how many a times a group was de-queued
+ or removed from the service tree of the device. This basically gives
+ and idea if we can generate enough IO to create continuously
+ backlogged groups. First two fields specify the major and minor
+ number of the device and third field specifies the number
+ of times a group was de-queued on a particular device.
+
+- io.policy
+ - One can specify per cgroup per device rules using this interface.
+ These rules override the default value of group weight and class as
+ specified by io.weight and io.ioprio_class.
+
+ Following is the format.
+
+ #echo dev_maj:dev_minor weight ioprio_class > /patch/to/cgroup/io.policy
+
+ weight=0 means removing a policy.
+
+ Examples:
+
+ Configure weight=300 ioprio_class=2 on /dev/hdb (8:16) in this cgroup
+ # echo 8:16 300 2 > io.policy
+ # cat io.policy
+ dev weight class
+ 8:16 300 2
+
+ Configure weight=500 ioprio_class=1 on /dev/hda (8:0) in this cgroup
+ # echo 8:0 500 1 > io.policy
+ # cat io.policy
+ dev weight class
+ 8:0 500 1
+ 8:16 300 2
+
+ Remove the policy for /dev/hda in this cgroup
+ # echo 8:0 0 1 > io.policy
+ # cat io.policy
+ dev weight class
+ 8:16 300 2
+
+About configuring request desriptors
+====================================
+Traditionally there are 128 request desriptors allocated per request queue
+where io scheduler is operating (/sys/block/<disk>/queue/nr_requests). If these
+request descriptors are exhausted, processes will put to sleep and woken
+up once request descriptors are available.
+
+With io controller and cgroup stuff, one can not afford to allocate requests
+from single pool as one group might allocate lots of requests and then tasks
+from other groups might be put to sleep and this other group might be a
+higher weight group. Hence to make sure that a group always can get the
+request descriptors it is entitled to, one needs to make request descriptor
+limit per group on every queue.
+
+A new parameter /sys/block/<disk>/queue/nr_group_requests has been introduced
+and this parameter controlls the maximum number of requests per group.
+nr_requests still continues to control total number of request descriptors
+on the queue.
+
+Ideally one should set nr_requests to be following.
+
+nr_requests = number_of_cgroups * nr_group_requests
+
+This will make sure that at any point of time nr_group_requests number of
+request descriptors will be available for any of the cgroups.
+
+Currently default nr_requests=512 and nr_group_requests=128. This will make
+sure that apart from root group one can create 3 more group without running
+into any issues. If one decides to create more cgorus, nr_requests and
+nr_group_requests should be adjusted accordingly.
+
+Probably a better way to assign limit to group request descriptors is through
+sysfs interface. This is a future TODO item.
--
1.6.0.6

2009-07-02 20:04:55

by Vivek Goyal

Subject: [PATCH 14/25] io-controller: Separate out queue and data

o So far noop, deadline and AS had one common structure called *_data which
contained both the queue information where requests are queued and also
common data used for scheduling. This patch breaks down this common
structure in two parts, *_queue and *_data. This is along the lines of
cfq where all the reuquests are queued in queue and common data and tunables
are part of data.

o It does not change the functionality but this re-organization helps once
noop, deadline and AS are changed to use hierarchical fair queuing.

o looks like queue_empty function is not required and we can check for
q->nr_sorted in elevator layer to see if ioscheduler queues are empty or
not.

Signed-off-by: Nauman Rafique <[email protected]>
Signed-off-by: Gui Jianfeng <[email protected]>
Signed-off-by: Vivek Goyal <[email protected]>
---
block/as-iosched.c | 208 ++++++++++++++++++++++++++--------------------
block/deadline-iosched.c | 117 ++++++++++++++++----------
block/elevator.c | 111 +++++++++++++++++++++----
block/noop-iosched.c | 59 ++++++-------
include/linux/elevator.h | 8 ++-
5 files changed, 319 insertions(+), 184 deletions(-)

diff --git a/block/as-iosched.c b/block/as-iosched.c
index 7a12cf6..cafc734 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -76,13 +76,7 @@ enum anticipation_status {
* or timed out */
};

-struct as_data {
- /*
- * run time data
- */
-
- struct request_queue *q; /* the "owner" queue */
-
+struct as_queue {
/*
* requests (as_rq s) are present on both sort_list and fifo_list
*/
@@ -90,6 +84,14 @@ struct as_data {
struct list_head fifo_list[2];

struct request *next_rq[2]; /* next in sort order */
+ unsigned long last_check_fifo[2];
+ 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? */
+};
+
+struct as_data {
+ struct request_queue *q; /* the "owner" queue */
sector_t last_sector[2]; /* last SYNC & ASYNC sectors */

unsigned long exit_prob; /* probability a task will exit while
@@ -103,21 +105,17 @@ struct as_data {
sector_t new_seek_mean;

unsigned long current_batch_expires;
- unsigned long last_check_fifo[2];
int changed_batch; /* 1: waiting for old batch to end */
int new_batch; /* 1: waiting on first read complete */
- int batch_data_dir; /* current batch SYNC / ASYNC */
- 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? */

enum anticipation_status antic_status;
unsigned long antic_start; /* jiffies: when it started */
struct timer_list antic_timer; /* anticipatory scheduling timer */
- struct work_struct antic_work; /* Deferred unplugging */
+ struct work_struct antic_work; /* Deferred unplugging */
struct io_context *io_context; /* Identify the expected process */
int ioc_finished; /* IO associated with io_context is finished */
int nr_dispatched;
+ int batch_data_dir; /* current batch SYNC / ASYNC */

/*
* settings that change how the i/o scheduler behaves
@@ -258,13 +256,14 @@ static void as_put_io_context(struct request *rq)
/*
* rb tree support functions
*/
-#define RQ_RB_ROOT(ad, rq) (&(ad)->sort_list[rq_is_sync((rq))])
+#define RQ_RB_ROOT(asq, rq) (&(asq)->sort_list[rq_is_sync((rq))])

static void as_add_rq_rb(struct as_data *ad, struct request *rq)
{
struct request *alias;
+ struct as_queue *asq = elv_get_sched_queue(ad->q, rq);

- while ((unlikely(alias = elv_rb_add(RQ_RB_ROOT(ad, rq), rq)))) {
+ while ((unlikely(alias = elv_rb_add(RQ_RB_ROOT(asq, rq), rq)))) {
as_move_to_dispatch(ad, alias);
as_antic_stop(ad);
}
@@ -272,7 +271,9 @@ static void as_add_rq_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);
+ struct as_queue *asq = elv_get_sched_queue(ad->q, rq);
+
+ elv_rb_del(RQ_RB_ROOT(asq, rq), rq);
}

/*
@@ -366,7 +367,7 @@ as_choose_req(struct as_data *ad, struct request *rq1, struct request *rq2)
* what request to process next. Anticipation works on top of this.
*/
static struct request *
-as_find_next_rq(struct as_data *ad, struct request *last)
+as_find_next_rq(struct as_data *ad, struct as_queue *asq, struct request *last)
{
struct rb_node *rbnext = rb_next(&last->rb_node);
struct rb_node *rbprev = rb_prev(&last->rb_node);
@@ -382,7 +383,7 @@ as_find_next_rq(struct as_data *ad, struct request *last)
else {
const int data_dir = rq_is_sync(last);

- rbnext = rb_first(&ad->sort_list[data_dir]);
+ rbnext = rb_first(&asq->sort_list[data_dir]);
if (rbnext && rbnext != &last->rb_node)
next = rb_entry_rq(rbnext);
}
@@ -789,9 +790,10 @@ static int as_can_anticipate(struct as_data *ad, struct request *rq)
static void as_update_rq(struct as_data *ad, struct request *rq)
{
const int data_dir = rq_is_sync(rq);
+ struct as_queue *asq = elv_get_sched_queue(ad->q, rq);

/* keep the next_rq cache up to date */
- ad->next_rq[data_dir] = as_choose_req(ad, rq, ad->next_rq[data_dir]);
+ asq->next_rq[data_dir] = as_choose_req(ad, rq, asq->next_rq[data_dir]);

/*
* have we been anticipating this request?
@@ -812,25 +814,26 @@ static void update_write_batch(struct as_data *ad)
{
unsigned long batch = ad->batch_expire[BLK_RW_ASYNC];
long write_time;
+ struct as_queue *asq = elv_get_sched_queue(ad->q, NULL);

write_time = (jiffies - ad->current_batch_expires) + batch;
if (write_time < 0)
write_time = 0;

- if (write_time > batch && !ad->write_batch_idled) {
+ if (write_time > batch && !asq->write_batch_idled) {
if (write_time > batch * 3)
- ad->write_batch_count /= 2;
+ asq->write_batch_count /= 2;
else
- ad->write_batch_count--;
- } else if (write_time < batch && ad->current_write_count == 0) {
+ asq->write_batch_count--;
+ } else if (write_time < batch && asq->current_write_count == 0) {
if (batch > write_time * 3)
- ad->write_batch_count *= 2;
+ asq->write_batch_count *= 2;
else
- ad->write_batch_count++;
+ asq->write_batch_count++;
}

- if (ad->write_batch_count < 1)
- ad->write_batch_count = 1;
+ if (asq->write_batch_count < 1)
+ asq->write_batch_count = 1;
}

/*
@@ -901,6 +904,7 @@ static void as_remove_queued_request(struct request_queue *q,
const int data_dir = rq_is_sync(rq);
struct as_data *ad = q->elevator->elevator_data;
struct io_context *ioc;
+ struct as_queue *asq = elv_get_sched_queue(q, rq);

WARN_ON(RQ_STATE(rq) != AS_RQ_QUEUED);

@@ -914,8 +918,8 @@ static void as_remove_queued_request(struct request_queue *q,
* Update the "next_rq" cache if we are about to remove its
* entry
*/
- if (ad->next_rq[data_dir] == rq)
- ad->next_rq[data_dir] = as_find_next_rq(ad, rq);
+ if (asq->next_rq[data_dir] == rq)
+ asq->next_rq[data_dir] = as_find_next_rq(ad, asq, rq);

rq_fifo_clear(rq);
as_del_rq_rb(ad, rq);
@@ -929,23 +933,23 @@ static void as_remove_queued_request(struct request_queue *q,
*
* See as_antic_expired comment.
*/
-static int as_fifo_expired(struct as_data *ad, int adir)
+static int as_fifo_expired(struct as_data *ad, struct as_queue *asq, int adir)
{
struct request *rq;
long delta_jif;

- delta_jif = jiffies - ad->last_check_fifo[adir];
+ delta_jif = jiffies - asq->last_check_fifo[adir];
if (unlikely(delta_jif < 0))
delta_jif = -delta_jif;
if (delta_jif < ad->fifo_expire[adir])
return 0;

- ad->last_check_fifo[adir] = jiffies;
+ asq->last_check_fifo[adir] = jiffies;

- if (list_empty(&ad->fifo_list[adir]))
+ if (list_empty(&asq->fifo_list[adir]))
return 0;

- rq = rq_entry_fifo(ad->fifo_list[adir].next);
+ rq = rq_entry_fifo(asq->fifo_list[adir].next);

return time_after(jiffies, rq_fifo_time(rq));
}
@@ -954,7 +958,7 @@ static int as_fifo_expired(struct as_data *ad, int adir)
* as_batch_expired returns true if the current batch has expired. A batch
* is a set of reads or a set of writes.
*/
-static inline int as_batch_expired(struct as_data *ad)
+static inline int as_batch_expired(struct as_data *ad, struct as_queue *asq)
{
if (ad->changed_batch || ad->new_batch)
return 0;
@@ -964,7 +968,7 @@ static inline int as_batch_expired(struct as_data *ad)
return time_after(jiffies, ad->current_batch_expires);

return time_after(jiffies, ad->current_batch_expires)
- || ad->current_write_count == 0;
+ || asq->current_write_count == 0;
}

/*
@@ -973,6 +977,7 @@ static inline int as_batch_expired(struct as_data *ad)
static void as_move_to_dispatch(struct as_data *ad, struct request *rq)
{
const int data_dir = rq_is_sync(rq);
+ struct as_queue *asq = elv_get_sched_queue(ad->q, rq);

BUG_ON(RB_EMPTY_NODE(&rq->rb_node));

@@ -995,12 +1000,12 @@ static void as_move_to_dispatch(struct as_data *ad, struct request *rq)
ad->io_context = NULL;
}

- if (ad->current_write_count != 0)
- ad->current_write_count--;
+ if (asq->current_write_count != 0)
+ asq->current_write_count--;
}
ad->ioc_finished = 0;

- ad->next_rq[data_dir] = as_find_next_rq(ad, rq);
+ asq->next_rq[data_dir] = as_find_next_rq(ad, asq, rq);

/*
* take it off the sort and fifo list, add to dispatch queue
@@ -1024,9 +1029,16 @@ static void as_move_to_dispatch(struct as_data *ad, struct request *rq)
static int as_dispatch_request(struct request_queue *q, int force)
{
struct as_data *ad = q->elevator->elevator_data;
- const int reads = !list_empty(&ad->fifo_list[BLK_RW_SYNC]);
- const int writes = !list_empty(&ad->fifo_list[BLK_RW_ASYNC]);
struct request *rq;
+ struct as_queue *asq = elv_select_sched_queue(q, force);
+ int reads, writes;
+
+ if (!asq)
+ return 0;
+
+ reads = !list_empty(&asq->fifo_list[BLK_RW_SYNC]);
+ writes = !list_empty(&asq->fifo_list[BLK_RW_ASYNC]);
+

if (unlikely(force)) {
/*
@@ -1042,25 +1054,25 @@ static int as_dispatch_request(struct request_queue *q, int force)
ad->changed_batch = 0;
ad->new_batch = 0;

- while (ad->next_rq[BLK_RW_SYNC]) {
- as_move_to_dispatch(ad, ad->next_rq[BLK_RW_SYNC]);
+ while (asq->next_rq[BLK_RW_SYNC]) {
+ as_move_to_dispatch(ad, asq->next_rq[BLK_RW_SYNC]);
dispatched++;
}
- ad->last_check_fifo[BLK_RW_SYNC] = jiffies;
+ asq->last_check_fifo[BLK_RW_SYNC] = jiffies;

- while (ad->next_rq[BLK_RW_ASYNC]) {
- as_move_to_dispatch(ad, ad->next_rq[BLK_RW_ASYNC]);
+ while (asq->next_rq[BLK_RW_ASYNC]) {
+ as_move_to_dispatch(ad, asq->next_rq[BLK_RW_ASYNC]);
dispatched++;
}
- ad->last_check_fifo[BLK_RW_ASYNC] = jiffies;
+ asq->last_check_fifo[BLK_RW_ASYNC] = jiffies;

return dispatched;
}

/* Signal that the write batch was uncontended, so we can't time it */
if (ad->batch_data_dir == BLK_RW_ASYNC && !reads) {
- if (ad->current_write_count == 0 || !writes)
- ad->write_batch_idled = 1;
+ if (asq->current_write_count == 0 || !writes)
+ asq->write_batch_idled = 1;
}

if (!(reads || writes)
@@ -1069,14 +1081,14 @@ static int as_dispatch_request(struct request_queue *q, int force)
|| ad->changed_batch)
return 0;

- if (!(reads && writes && as_batch_expired(ad))) {
+ if (!(reads && writes && as_batch_expired(ad, asq))) {
/*
* batch is still running or no reads or no writes
*/
- rq = ad->next_rq[ad->batch_data_dir];
+ rq = asq->next_rq[ad->batch_data_dir];

if (ad->batch_data_dir == BLK_RW_SYNC && ad->antic_expire) {
- if (as_fifo_expired(ad, BLK_RW_SYNC))
+ if (as_fifo_expired(ad, asq, BLK_RW_SYNC))
goto fifo_expired;

if (as_can_anticipate(ad, rq)) {
@@ -1100,7 +1112,7 @@ static int as_dispatch_request(struct request_queue *q, int force)
*/

if (reads) {
- BUG_ON(RB_EMPTY_ROOT(&ad->sort_list[BLK_RW_SYNC]));
+ BUG_ON(RB_EMPTY_ROOT(&asq->sort_list[BLK_RW_SYNC]));

if (writes && ad->batch_data_dir == BLK_RW_SYNC)
/*
@@ -1113,8 +1125,8 @@ static int as_dispatch_request(struct request_queue *q, int force)
ad->changed_batch = 1;
}
ad->batch_data_dir = BLK_RW_SYNC;
- rq = rq_entry_fifo(ad->fifo_list[BLK_RW_SYNC].next);
- ad->last_check_fifo[ad->batch_data_dir] = jiffies;
+ rq = rq_entry_fifo(asq->fifo_list[BLK_RW_SYNC].next);
+ asq->last_check_fifo[ad->batch_data_dir] = jiffies;
goto dispatch_request;
}

@@ -1124,7 +1136,7 @@ static int as_dispatch_request(struct request_queue *q, int force)

if (writes) {
dispatch_writes:
- BUG_ON(RB_EMPTY_ROOT(&ad->sort_list[BLK_RW_ASYNC]));
+ BUG_ON(RB_EMPTY_ROOT(&asq->sort_list[BLK_RW_ASYNC]));

if (ad->batch_data_dir == BLK_RW_SYNC) {
ad->changed_batch = 1;
@@ -1137,10 +1149,10 @@ dispatch_writes:
ad->new_batch = 0;
}
ad->batch_data_dir = BLK_RW_ASYNC;
- ad->current_write_count = ad->write_batch_count;
- ad->write_batch_idled = 0;
- rq = rq_entry_fifo(ad->fifo_list[BLK_RW_ASYNC].next);
- ad->last_check_fifo[BLK_RW_ASYNC] = jiffies;
+ asq->current_write_count = asq->write_batch_count;
+ asq->write_batch_idled = 0;
+ rq = rq_entry_fifo(asq->fifo_list[BLK_RW_ASYNC].next);
+ asq->last_check_fifo[BLK_RW_ASYNC] = jiffies;
goto dispatch_request;
}

@@ -1152,9 +1164,9 @@ dispatch_request:
* If a request has expired, service it.
*/

- if (as_fifo_expired(ad, ad->batch_data_dir)) {
+ if (as_fifo_expired(ad, asq, ad->batch_data_dir)) {
fifo_expired:
- rq = rq_entry_fifo(ad->fifo_list[ad->batch_data_dir].next);
+ rq = rq_entry_fifo(asq->fifo_list[ad->batch_data_dir].next);
}

if (ad->changed_batch) {
@@ -1187,6 +1199,7 @@ static void as_add_request(struct request_queue *q, struct request *rq)
{
struct as_data *ad = q->elevator->elevator_data;
int data_dir;
+ struct as_queue *asq = elv_get_sched_queue(q, rq);

RQ_SET_STATE(rq, AS_RQ_NEW);

@@ -1205,7 +1218,7 @@ static void as_add_request(struct request_queue *q, struct request *rq)
* set expire time and add to fifo list
*/
rq_set_fifo_time(rq, jiffies + ad->fifo_expire[data_dir]);
- list_add_tail(&rq->queuelist, &ad->fifo_list[data_dir]);
+ list_add_tail(&rq->queuelist, &asq->fifo_list[data_dir]);

as_update_rq(ad, rq); /* keep state machine up to date */
RQ_SET_STATE(rq, AS_RQ_QUEUED);
@@ -1227,31 +1240,20 @@ static void as_deactivate_request(struct request_queue *q, struct request *rq)
atomic_inc(&RQ_IOC(rq)->aic->nr_dispatched);
}

-/*
- * as_queue_empty tells us if there are requests left in the device. It may
- * not be the case that a driver can get the next request even if the queue
- * is not empty - it is used in the block layer to check for plugging and
- * merging opportunities
- */
-static int as_queue_empty(struct request_queue *q)
-{
- struct as_data *ad = q->elevator->elevator_data;
-
- return list_empty(&ad->fifo_list[BLK_RW_ASYNC])
- && list_empty(&ad->fifo_list[BLK_RW_SYNC]);
-}
-
static int
as_merge(struct request_queue *q, struct request **req, struct bio *bio)
{
- struct as_data *ad = q->elevator->elevator_data;
sector_t rb_key = bio->bi_sector + bio_sectors(bio);
struct request *__rq;
+ struct as_queue *asq = elv_get_sched_queue_current(q);
+
+ if (!asq)
+ return ELEVATOR_NO_MERGE;

/*
* check for front merge
*/
- __rq = elv_rb_find(&ad->sort_list[bio_data_dir(bio)], rb_key);
+ __rq = elv_rb_find(&asq->sort_list[bio_data_dir(bio)], rb_key);
if (__rq && elv_rq_merge_ok(__rq, bio)) {
*req = __rq;
return ELEVATOR_FRONT_MERGE;
@@ -1334,6 +1336,41 @@ static int as_may_queue(struct request_queue *q, int rw)
return ret;
}

+/* Called with queue lock held */
+static void *as_alloc_as_queue(struct request_queue *q,
+ struct elevator_queue *eq, gfp_t gfp_mask)
+{
+ struct as_queue *asq;
+ struct as_data *ad = eq->elevator_data;
+
+ asq = kmalloc_node(sizeof(*asq), gfp_mask | __GFP_ZERO, q->node);
+ if (asq == NULL)
+ goto out;
+
+ INIT_LIST_HEAD(&asq->fifo_list[BLK_RW_SYNC]);
+ INIT_LIST_HEAD(&asq->fifo_list[BLK_RW_ASYNC]);
+ asq->sort_list[BLK_RW_SYNC] = RB_ROOT;
+ asq->sort_list[BLK_RW_ASYNC] = RB_ROOT;
+ if (ad)
+ asq->write_batch_count = ad->batch_expire[BLK_RW_ASYNC] / 10;
+ else
+ asq->write_batch_count = default_write_batch_expire / 10;
+
+ if (asq->write_batch_count < 2)
+ asq->write_batch_count = 2;
+out:
+ return asq;
+}
+
+static void as_free_as_queue(struct elevator_queue *e, void *sched_queue)
+{
+ struct as_queue *asq = sched_queue;
+
+ BUG_ON(!list_empty(&asq->fifo_list[BLK_RW_SYNC]));
+ BUG_ON(!list_empty(&asq->fifo_list[BLK_RW_ASYNC]));
+ kfree(asq);
+}
+
static void as_exit_queue(struct elevator_queue *e)
{
struct as_data *ad = e->elevator_data;
@@ -1341,9 +1378,6 @@ static void as_exit_queue(struct elevator_queue *e)
del_timer_sync(&ad->antic_timer);
cancel_work_sync(&ad->antic_work);

- BUG_ON(!list_empty(&ad->fifo_list[BLK_RW_SYNC]));
- BUG_ON(!list_empty(&ad->fifo_list[BLK_RW_ASYNC]));
-
put_io_context(ad->io_context);
kfree(ad);
}
@@ -1367,10 +1401,6 @@ static void *as_init_queue(struct request_queue *q)
init_timer(&ad->antic_timer);
INIT_WORK(&ad->antic_work, as_work_handler);

- INIT_LIST_HEAD(&ad->fifo_list[BLK_RW_SYNC]);
- INIT_LIST_HEAD(&ad->fifo_list[BLK_RW_ASYNC]);
- ad->sort_list[BLK_RW_SYNC] = RB_ROOT;
- ad->sort_list[BLK_RW_ASYNC] = RB_ROOT;
ad->fifo_expire[BLK_RW_SYNC] = default_read_expire;
ad->fifo_expire[BLK_RW_ASYNC] = default_write_expire;
ad->antic_expire = default_antic_expire;
@@ -1378,9 +1408,6 @@ static void *as_init_queue(struct request_queue *q)
ad->batch_expire[BLK_RW_ASYNC] = default_write_batch_expire;

ad->current_batch_expires = jiffies + ad->batch_expire[BLK_RW_SYNC];
- ad->write_batch_count = ad->batch_expire[BLK_RW_ASYNC] / 10;
- if (ad->write_batch_count < 2)
- ad->write_batch_count = 2;

return ad;
}
@@ -1478,7 +1505,6 @@ static struct elevator_type iosched_as = {
.elevator_add_req_fn = as_add_request,
.elevator_activate_req_fn = as_activate_request,
.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 = elv_rb_former_request,
.elevator_latter_req_fn = elv_rb_latter_request,
@@ -1486,6 +1512,8 @@ static struct elevator_type iosched_as = {
.elevator_init_fn = as_init_queue,
.elevator_exit_fn = as_exit_queue,
.trim = as_trim,
+ .elevator_alloc_sched_queue_fn = as_alloc_as_queue,
+ .elevator_free_sched_queue_fn = as_free_as_queue,
},

.elevator_attrs = as_attrs,
diff --git a/block/deadline-iosched.c b/block/deadline-iosched.c
index b547cbc..5bd5257 100644
--- a/block/deadline-iosched.c
+++ b/block/deadline-iosched.c
@@ -23,25 +23,23 @@ static const int writes_starved = 2; /* max times reads can starve a write */
static const int fifo_batch = 16; /* # of sequential requests treated as one
by the above parameters. For throughput. */

-struct deadline_data {
- /*
- * run time data
- */
-
+struct deadline_queue {
/*
* requests (deadline_rq s) are present on both sort_list and fifo_list
*/
- struct rb_root sort_list[2];
+ struct rb_root sort_list[2];
struct list_head fifo_list[2];
-
/*
* next in sort order. read, write or both are NULL
*/
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 */
+};

+struct deadline_data {
+ struct request_queue *q;
+ sector_t last_sector; /* head position */
/*
* settings that change how the i/o scheduler behaves
*/
@@ -56,7 +54,9 @@ static void deadline_move_request(struct deadline_data *, struct request *);
static inline struct rb_root *
deadline_rb_root(struct deadline_data *dd, struct request *rq)
{
- return &dd->sort_list[rq_data_dir(rq)];
+ struct deadline_queue *dq = elv_get_sched_queue(dd->q, rq);
+
+ return &dq->sort_list[rq_data_dir(rq)];
}

/*
@@ -87,9 +87,10 @@ static inline void
deadline_del_rq_rb(struct deadline_data *dd, struct request *rq)
{
const int data_dir = rq_data_dir(rq);
+ struct deadline_queue *dq = elv_get_sched_queue(dd->q, rq);

- if (dd->next_rq[data_dir] == rq)
- dd->next_rq[data_dir] = deadline_latter_request(rq);
+ if (dq->next_rq[data_dir] == rq)
+ dq->next_rq[data_dir] = deadline_latter_request(rq);

elv_rb_del(deadline_rb_root(dd, rq), rq);
}
@@ -102,6 +103,7 @@ deadline_add_request(struct request_queue *q, struct request *rq)
{
struct deadline_data *dd = q->elevator->elevator_data;
const int data_dir = rq_data_dir(rq);
+ struct deadline_queue *dq = elv_get_sched_queue(q, rq);

deadline_add_rq_rb(dd, rq);

@@ -109,7 +111,7 @@ deadline_add_request(struct request_queue *q, struct request *rq)
* set expire time and add to fifo list
*/
rq_set_fifo_time(rq, jiffies + dd->fifo_expire[data_dir]);
- list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);
+ list_add_tail(&rq->queuelist, &dq->fifo_list[data_dir]);
}

/*
@@ -129,6 +131,11 @@ deadline_merge(struct request_queue *q, struct request **req, struct bio *bio)
struct deadline_data *dd = q->elevator->elevator_data;
struct request *__rq;
int ret;
+ struct deadline_queue *dq;
+
+ dq = elv_get_sched_queue_current(q);
+ if (!dq)
+ return ELEVATOR_NO_MERGE;

/*
* check for front merge
@@ -136,7 +143,7 @@ deadline_merge(struct request_queue *q, struct request **req, struct bio *bio)
if (dd->front_merges) {
sector_t sector = bio->bi_sector + bio_sectors(bio);

- __rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);
+ __rq = elv_rb_find(&dq->sort_list[bio_data_dir(bio)], sector);
if (__rq) {
BUG_ON(sector != blk_rq_pos(__rq));

@@ -207,10 +214,11 @@ static void
deadline_move_request(struct deadline_data *dd, struct request *rq)
{
const int data_dir = rq_data_dir(rq);
+ struct deadline_queue *dq = elv_get_sched_queue(dd->q, rq);

- dd->next_rq[READ] = NULL;
- dd->next_rq[WRITE] = NULL;
- dd->next_rq[data_dir] = deadline_latter_request(rq);
+ dq->next_rq[READ] = NULL;
+ dq->next_rq[WRITE] = NULL;
+ dq->next_rq[data_dir] = deadline_latter_request(rq);

dd->last_sector = rq_end_sector(rq);

@@ -225,9 +233,9 @@ deadline_move_request(struct deadline_data *dd, struct request *rq)
* deadline_check_fifo returns 0 if there are no expired requests 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)
+static inline int deadline_check_fifo(struct deadline_queue *dq, int ddir)
{
- struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next);
+ struct request *rq = rq_entry_fifo(dq->fifo_list[ddir].next);

/*
* rq is expired!
@@ -245,20 +253,26 @@ static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
static int deadline_dispatch_requests(struct request_queue *q, int force)
{
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_queue *dq = elv_select_sched_queue(q, force);
+ int reads, writes;
struct request *rq;
int data_dir;

+ if (!dq)
+ return 0;
+
+ reads = !list_empty(&dq->fifo_list[READ]);
+ writes = !list_empty(&dq->fifo_list[WRITE]);
+
/*
* batches are currently reads XOR writes
*/
- if (dd->next_rq[WRITE])
- rq = dd->next_rq[WRITE];
+ if (dq->next_rq[WRITE])
+ rq = dq->next_rq[WRITE];
else
- rq = dd->next_rq[READ];
+ rq = dq->next_rq[READ];

- if (rq && dd->batching < dd->fifo_batch)
+ if (rq && dq->batching < dd->fifo_batch)
/* we have a next request are still entitled to batch */
goto dispatch_request;

@@ -268,9 +282,9 @@ static int deadline_dispatch_requests(struct request_queue *q, int force)
*/

if (reads) {
- BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ]));
+ BUG_ON(RB_EMPTY_ROOT(&dq->sort_list[READ]));

- if (writes && (dd->starved++ >= dd->writes_starved))
+ if (writes && (dq->starved++ >= dd->writes_starved))
goto dispatch_writes;

data_dir = READ;
@@ -284,9 +298,9 @@ static int deadline_dispatch_requests(struct request_queue *q, int force)

if (writes) {
dispatch_writes:
- BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
+ BUG_ON(RB_EMPTY_ROOT(&dq->sort_list[WRITE]));

- dd->starved = 0;
+ dq->starved = 0;

data_dir = WRITE;

@@ -299,48 +313,62 @@ dispatch_find_request:
/*
* we are not running a batch, find best request for selected data_dir
*/
- if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) {
+ if (deadline_check_fifo(dq, data_dir) || !dq->next_rq[data_dir]) {
/*
* A deadline has expired, the last request was in the other
* direction, or we have run out of higher-sectored requests.
* Start again from the request with the earliest expiry time.
*/
- rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
+ rq = rq_entry_fifo(dq->fifo_list[data_dir].next);
} else {
/*
* The last req was the same dir and we have a next request in
* sort order. No expired requests so continue on from here.
*/
- rq = dd->next_rq[data_dir];
+ rq = dq->next_rq[data_dir];
}

- dd->batching = 0;
+ dq->batching = 0;

dispatch_request:
/*
* rq is the selected appropriate request.
*/
- dd->batching++;
+ dq->batching++;
deadline_move_request(dd, rq);

return 1;
}

-static int deadline_queue_empty(struct request_queue *q)
+static void *deadline_alloc_deadline_queue(struct request_queue *q,
+ struct elevator_queue *eq, gfp_t gfp_mask)
{
- struct deadline_data *dd = q->elevator->elevator_data;
+ struct deadline_queue *dq;

- return list_empty(&dd->fifo_list[WRITE])
- && list_empty(&dd->fifo_list[READ]);
+ dq = kmalloc_node(sizeof(*dq), gfp_mask | __GFP_ZERO, q->node);
+ if (dq == NULL)
+ goto out;
+
+ INIT_LIST_HEAD(&dq->fifo_list[READ]);
+ INIT_LIST_HEAD(&dq->fifo_list[WRITE]);
+ dq->sort_list[READ] = RB_ROOT;
+ dq->sort_list[WRITE] = RB_ROOT;
+out:
+ return dq;
+}
+
+static void deadline_free_deadline_queue(struct elevator_queue *e,
+ void *sched_queue)
+{
+ struct deadline_queue *dq = sched_queue;
+
+ kfree(dq);
}

static void deadline_exit_queue(struct elevator_queue *e)
{
struct deadline_data *dd = e->elevator_data;

- BUG_ON(!list_empty(&dd->fifo_list[READ]));
- BUG_ON(!list_empty(&dd->fifo_list[WRITE]));
-
kfree(dd);
}

@@ -355,10 +383,7 @@ static void *deadline_init_queue(struct request_queue *q)
if (!dd)
return NULL;

- INIT_LIST_HEAD(&dd->fifo_list[READ]);
- INIT_LIST_HEAD(&dd->fifo_list[WRITE]);
- dd->sort_list[READ] = RB_ROOT;
- dd->sort_list[WRITE] = RB_ROOT;
+ dd->q = q;
dd->fifo_expire[READ] = read_expire;
dd->fifo_expire[WRITE] = write_expire;
dd->writes_starved = writes_starved;
@@ -445,13 +470,13 @@ static struct elevator_type iosched_deadline = {
.elevator_merge_req_fn = deadline_merged_requests,
.elevator_dispatch_fn = deadline_dispatch_requests,
.elevator_add_req_fn = deadline_add_request,
- .elevator_queue_empty_fn = deadline_queue_empty,
.elevator_former_req_fn = elv_rb_former_request,
.elevator_latter_req_fn = elv_rb_latter_request,
.elevator_init_fn = deadline_init_queue,
.elevator_exit_fn = deadline_exit_queue,
+ .elevator_alloc_sched_queue_fn = deadline_alloc_deadline_queue,
+ .elevator_free_sched_queue_fn = deadline_free_deadline_queue,
},
-
.elevator_attrs = deadline_attrs,
.elevator_name = "deadline",
.elevator_owner = THIS_MODULE,
diff --git a/block/elevator.c b/block/elevator.c
index a6ef1f1..76cfc3a 100644
--- a/block/elevator.c
+++ b/block/elevator.c
@@ -175,17 +175,54 @@ static struct elevator_type *elevator_get(const char *name)
return e;
}

-static void *elevator_init_queue(struct request_queue *q,
- struct elevator_queue *eq)
+static void *elevator_init_data(struct request_queue *q,
+ struct elevator_queue *eq)
{
- return eq->ops->elevator_init_fn(q);
+ void *data = NULL;
+
+ if (eq->ops->elevator_init_fn) {
+ data = eq->ops->elevator_init_fn(q);
+ if (data)
+ return data;
+ else
+ return ERR_PTR(-ENOMEM);
+ }
+
+ /* IO scheduler does not instanciate data (noop), it is not an error */
+ return NULL;
+}
+
+static void elevator_free_sched_queue(struct elevator_queue *eq,
+ void *sched_queue)
+{
+ /* Not all io schedulers (cfq) strore sched_queue */
+ if (!sched_queue)
+ return;
+ eq->ops->elevator_free_sched_queue_fn(eq, sched_queue);
+}
+
+static void *elevator_alloc_sched_queue(struct request_queue *q,
+ struct elevator_queue *eq)
+{
+ void *sched_queue = NULL;
+
+ if (eq->ops->elevator_alloc_sched_queue_fn) {
+ sched_queue = eq->ops->elevator_alloc_sched_queue_fn(q, eq,
+ GFP_KERNEL);
+ if (!sched_queue)
+ return ERR_PTR(-ENOMEM);
+
+ }
+
+ return sched_queue;
}

static void elevator_attach(struct request_queue *q, struct elevator_queue *eq,
- void *data)
+ void *data, void *sched_queue)
{
q->elevator = eq;
eq->elevator_data = data;
+ eq->sched_queue = sched_queue;
}

static char chosen_elevator[16];
@@ -255,7 +292,7 @@ int elevator_init(struct request_queue *q, char *name)
struct elevator_type *e = NULL;
struct elevator_queue *eq;
int ret = 0;
- void *data;
+ void *data = NULL, *sched_queue = NULL;

INIT_LIST_HEAD(&q->queue_head);
q->last_merge = NULL;
@@ -289,13 +326,21 @@ int elevator_init(struct request_queue *q, char *name)
if (!eq)
return -ENOMEM;

- data = elevator_init_queue(q, eq);
- if (!data) {
+ data = elevator_init_data(q, eq);
+
+ if (IS_ERR(data)) {
+ kobject_put(&eq->kobj);
+ return -ENOMEM;
+ }
+
+ sched_queue = elevator_alloc_sched_queue(q, eq);
+
+ if (IS_ERR(sched_queue)) {
kobject_put(&eq->kobj);
return -ENOMEM;
}

- elevator_attach(q, eq, data);
+ elevator_attach(q, eq, data, sched_queue);
return ret;
}
EXPORT_SYMBOL(elevator_init);
@@ -303,6 +348,7 @@ EXPORT_SYMBOL(elevator_init);
void elevator_exit(struct elevator_queue *e)
{
mutex_lock(&e->sysfs_lock);
+ elevator_free_sched_queue(e, e->sched_queue);
elv_exit_fq_data(e);
if (e->ops->elevator_exit_fn)
e->ops->elevator_exit_fn(e);
@@ -992,7 +1038,7 @@ EXPORT_SYMBOL_GPL(elv_unregister);
static int elevator_switch(struct request_queue *q, struct elevator_type *new_e)
{
struct elevator_queue *old_elevator, *e;
- void *data;
+ void *data = NULL, *sched_queue = NULL;

/*
* Allocate new elevator
@@ -1001,10 +1047,18 @@ static int elevator_switch(struct request_queue *q, struct elevator_type *new_e)
if (!e)
return 0;

- data = elevator_init_queue(q, e);
- if (!data) {
+ data = elevator_init_data(q, e);
+
+ if (IS_ERR(data)) {
kobject_put(&e->kobj);
- return 0;
+ return -ENOMEM;
+ }
+
+ sched_queue = elevator_alloc_sched_queue(q, e);
+
+ if (IS_ERR(sched_queue)) {
+ kobject_put(&e->kobj);
+ return -ENOMEM;
}

/*
@@ -1021,7 +1075,7 @@ static int elevator_switch(struct request_queue *q, struct elevator_type *new_e)
/*
* attach and start new elevator
*/
- elevator_attach(q, e, data);
+ elevator_attach(q, e, data, sched_queue);

spin_unlock_irq(q->queue_lock);

@@ -1136,16 +1190,43 @@ struct request *elv_rb_latter_request(struct request_queue *q,
}
EXPORT_SYMBOL(elv_rb_latter_request);

-/* Get the io scheduler queue pointer. For cfq, it is stored in rq->ioq*/
+/* Get the io scheduler queue pointer. */
void *elv_get_sched_queue(struct request_queue *q, struct request *rq)
{
- return ioq_sched_queue(req_ioq(rq));
+ /*
+ * io scheduler is not using fair queuing. Return sched_queue
+ * pointer stored in elevator_queue. It will be null if io
+ * scheduler never stored anything there to begin with (cfq)
+ */
+ if (!elv_iosched_fair_queuing_enabled(q->elevator))
+ return q->elevator->sched_queue;
+
+ /*
+ * IO schedueler is using fair queuing infrasture. If io scheduler
+ * has passed a non null rq, retrieve sched_queue pointer from
+ * there. */
+ if (rq)
+ return ioq_sched_queue(req_ioq(rq));
+
+ return NULL;
}
EXPORT_SYMBOL(elv_get_sched_queue);

/* Select an ioscheduler queue to dispatch request from. */
void *elv_select_sched_queue(struct request_queue *q, int force)
{
+ if (!elv_iosched_fair_queuing_enabled(q->elevator))
+ return q->elevator->sched_queue;
+
return ioq_sched_queue(elv_fq_select_ioq(q, force));
}
EXPORT_SYMBOL(elv_select_sched_queue);
+
+/*
+ * Get the io scheduler queue pointer for current task.
+ */
+void *elv_get_sched_queue_current(struct request_queue *q)
+{
+ return q->elevator->sched_queue;
+}
+EXPORT_SYMBOL(elv_get_sched_queue_current);
diff --git a/block/noop-iosched.c b/block/noop-iosched.c
index 3a0d369..d587832 100644
--- a/block/noop-iosched.c
+++ b/block/noop-iosched.c
@@ -7,7 +7,7 @@
#include <linux/module.h>
#include <linux/init.h>

-struct noop_data {
+struct noop_queue {
struct list_head queue;
};

@@ -19,11 +19,14 @@ static void noop_merged_requests(struct request_queue *q, struct request *rq,

static int noop_dispatch(struct request_queue *q, int force)
{
- struct noop_data *nd = q->elevator->elevator_data;
+ struct noop_queue *nq = elv_select_sched_queue(q, force);

- if (!list_empty(&nd->queue)) {
+ if (!nq)
+ return 0;
+
+ if (!list_empty(&nq->queue)) {
struct request *rq;
- rq = list_entry(nd->queue.next, struct request, queuelist);
+ rq = list_entry(nq->queue.next, struct request, queuelist);
list_del_init(&rq->queuelist);
elv_dispatch_sort(q, rq);
return 1;
@@ -33,24 +36,17 @@ static int noop_dispatch(struct request_queue *q, int force)

static void noop_add_request(struct request_queue *q, struct request *rq)
{
- struct noop_data *nd = q->elevator->elevator_data;
+ struct noop_queue *nq = elv_get_sched_queue(q, rq);

- list_add_tail(&rq->queuelist, &nd->queue);
-}
-
-static int noop_queue_empty(struct request_queue *q)
-{
- struct noop_data *nd = q->elevator->elevator_data;
-
- return list_empty(&nd->queue);
+ list_add_tail(&rq->queuelist, &nq->queue);
}

static struct request *
noop_former_request(struct request_queue *q, struct request *rq)
{
- struct noop_data *nd = q->elevator->elevator_data;
+ struct noop_queue *nq = elv_get_sched_queue(q, rq);

- if (rq->queuelist.prev == &nd->queue)
+ if (rq->queuelist.prev == &nq->queue)
return NULL;
return list_entry(rq->queuelist.prev, struct request, queuelist);
}
@@ -58,30 +54,32 @@ noop_former_request(struct request_queue *q, struct request *rq)
static struct request *
noop_latter_request(struct request_queue *q, struct request *rq)
{
- struct noop_data *nd = q->elevator->elevator_data;
+ struct noop_queue *nq = elv_get_sched_queue(q, rq);

- if (rq->queuelist.next == &nd->queue)
+ if (rq->queuelist.next == &nq->queue)
return NULL;
return list_entry(rq->queuelist.next, struct request, queuelist);
}

-static void *noop_init_queue(struct request_queue *q)
+static void *noop_alloc_noop_queue(struct request_queue *q,
+ struct elevator_queue *eq, gfp_t gfp_mask)
{
- struct noop_data *nd;
+ struct noop_queue *nq;

- nd = kmalloc_node(sizeof(*nd), GFP_KERNEL, q->node);
- if (!nd)
- return NULL;
- INIT_LIST_HEAD(&nd->queue);
- return nd;
+ nq = kmalloc_node(sizeof(*nq), gfp_mask | __GFP_ZERO, q->node);
+ if (nq == NULL)
+ goto out;
+
+ INIT_LIST_HEAD(&nq->queue);
+out:
+ return nq;
}

-static void noop_exit_queue(struct elevator_queue *e)
+static void noop_free_noop_queue(struct elevator_queue *e, void *sched_queue)
{
- struct noop_data *nd = e->elevator_data;
+ struct noop_queue *nq = sched_queue;

- BUG_ON(!list_empty(&nd->queue));
- kfree(nd);
+ kfree(nq);
}

static struct elevator_type elevator_noop = {
@@ -89,11 +87,10 @@ static struct elevator_type elevator_noop = {
.elevator_merge_req_fn = noop_merged_requests,
.elevator_dispatch_fn = noop_dispatch,
.elevator_add_req_fn = noop_add_request,
- .elevator_queue_empty_fn = noop_queue_empty,
.elevator_former_req_fn = noop_former_request,
.elevator_latter_req_fn = noop_latter_request,
- .elevator_init_fn = noop_init_queue,
- .elevator_exit_fn = noop_exit_queue,
+ .elevator_alloc_sched_queue_fn = noop_alloc_noop_queue,
+ .elevator_free_sched_queue_fn = noop_free_noop_queue,
},
.elevator_name = "noop",
.elevator_owner = THIS_MODULE,
diff --git a/include/linux/elevator.h b/include/linux/elevator.h
index 81f1ed8..e7048b9 100644
--- a/include/linux/elevator.h
+++ b/include/linux/elevator.h
@@ -30,8 +30,9 @@ typedef void (elevator_deactivate_req_fn) (struct request_queue *, struct reques

typedef void *(elevator_init_fn) (struct request_queue *);
typedef void (elevator_exit_fn) (struct elevator_queue *);
-#ifdef CONFIG_ELV_FAIR_QUEUING
+typedef void* (elevator_alloc_sched_queue_fn) (struct request_queue *q, struct elevator_queue *eq, gfp_t);
typedef void (elevator_free_sched_queue_fn) (struct elevator_queue*, void *);
+#ifdef CONFIG_ELV_FAIR_QUEUING
typedef void (elevator_active_ioq_set_fn) (struct request_queue*, void *, int);
typedef void (elevator_active_ioq_reset_fn) (struct request_queue *, void*);
typedef void (elevator_arm_slice_timer_fn) (struct request_queue*, void*);
@@ -70,8 +71,9 @@ struct elevator_ops
elevator_exit_fn *elevator_exit_fn;
void (*trim)(struct io_context *);

-#ifdef CONFIG_ELV_FAIR_QUEUING
+ elevator_alloc_sched_queue_fn *elevator_alloc_sched_queue_fn;
elevator_free_sched_queue_fn *elevator_free_sched_queue_fn;
+#ifdef CONFIG_ELV_FAIR_QUEUING
elevator_active_ioq_set_fn *elevator_active_ioq_set_fn;
elevator_active_ioq_reset_fn *elevator_active_ioq_reset_fn;

@@ -112,6 +114,7 @@ struct elevator_queue
{
struct elevator_ops *ops;
void *elevator_data;
+ void *sched_queue;
struct kobject kobj;
struct elevator_type *elevator_type;
struct mutex sysfs_lock;
@@ -258,5 +261,6 @@ static inline int elv_iosched_fair_queuing_enabled(struct elevator_queue *e)
#endif /* ELV_IOSCHED_FAIR_QUEUING */
extern void *elv_get_sched_queue(struct request_queue *q, struct request *rq);
extern void *elv_select_sched_queue(struct request_queue *q, int force);
+extern void *elv_get_sched_queue_current(struct request_queue *q);
#endif /* CONFIG_BLOCK */
#endif
--
1.6.0.6

2009-07-02 20:05:13

by Vivek Goyal

Subject: [PATCH 23/25] io-controller: Support per cgroup per device weights and io class

This patch enables per-cgroup per-device weight and ioprio_class handling.
A new cgroup interface "policy" is introduced. You can make use of this
file to configure weight and ioprio_class for each device in a given cgroup.
The original "weight" and "ioprio_class" files are still available. If you
don't do special configuration for a particular device, "weight" and
"ioprio_class" are used as default values in this device.

You can use the following format to play with the new interface.
#echo dev_major:dev_minor weight ioprio_class > /patch/to/cgroup/policy
weight=0 means removing the policy for device.

Examples:
Configure weight=300 ioprio_class=2 on /dev/hdb (8:16) in this cgroup
# echo "8:16 300 2" > io.policy
# cat io.policy
dev weight class
8:16 300 2

Configure weight=500 ioprio_class=1 on /dev/hda (8:0) in this cgroup
# echo "8:0 500 1" > io.policy
# cat io.policy
dev weight class
8:0 500 1
8:16 300 2

Remove the policy for /dev/hda in this cgroup
# echo 8:0 0 1 > io.policy
# cat io.policy
dev weight class
8:16 300 2

Changelog (v1 -> v2)
- Rename some structures
- Use spin_lock_irqsave() and spin_lock_irqrestore() version to prevent
from enabling the interrupts unconditionally.
- Fix policy setup bug when switching to another io scheduler.
- If a policy is available for a specific device, don't update weight and
io class when writing "weight" and "iprio_class".
- Fix a bug when parsing policy string.

Signed-off-by: Gui Jianfeng <[email protected]>
Signed-off-by: Vivek Goyal <[email protected]>
---
block/elevator-fq.c | 266 ++++++++++++++++++++++++++++++++++++++++++++++++++-
block/elevator-fq.h | 10 ++
2 files changed, 272 insertions(+), 4 deletions(-)

diff --git a/block/elevator-fq.c b/block/elevator-fq.c
index 2a2b68d..31b066d 100644
--- a/block/elevator-fq.c
+++ b/block/elevator-fq.c
@@ -17,6 +17,7 @@
#include <linux/blktrace_api.h>
#include <linux/seq_file.h>
#include <linux/biotrack.h>
+#include <linux/genhd.h>

/* Values taken from cfq */
const int elv_slice_sync = HZ / 10;
@@ -1053,12 +1054,31 @@ static void bfq_init_entity(struct io_entity *entity, struct io_group *iog)
entity->sched_data = &iog->sched_data;
}

-static void io_group_init_entity(struct io_cgroup *iocg, struct io_group *iog)
+static struct io_policy_node *policy_search_node(const struct io_cgroup *iocg,
+ dev_t dev);
+
+static void io_group_init_entity(struct io_cgroup *iocg, struct io_group *iog,
+ dev_t dev)
{
struct io_entity *entity = &iog->entity;
+ struct io_policy_node *pn;
+ unsigned long flags;
+
+ spin_lock_irqsave(&iocg->lock, flags);
+ pn = policy_search_node(iocg, dev);
+ if (pn) {
+ entity->weight = pn->weight;
+ entity->new_weight = pn->weight;
+ entity->ioprio_class = pn->ioprio_class;
+ entity->new_ioprio_class = pn->ioprio_class;
+ } else {
+ entity->weight = iocg->weight;
+ entity->new_weight = iocg->weight;
+ entity->ioprio_class = iocg->ioprio_class;
+ entity->new_ioprio_class = iocg->ioprio_class;
+ }
+ spin_unlock_irqrestore(&iocg->lock, flags);

- entity->weight = entity->new_weight = iocg->weight;
- entity->ioprio_class = entity->new_ioprio_class = iocg->ioprio_class;
entity->ioprio_changed = 1;
entity->my_sched_data = &iog->sched_data;
}
@@ -1174,6 +1194,227 @@ io_cgroup_lookup_group(struct io_cgroup *iocg, void *key)
return NULL;
}

+static int io_cgroup_policy_read(struct cgroup *cgrp, struct cftype *cft,
+ struct seq_file *m)
+{
+ struct io_cgroup *iocg;
+ struct io_policy_node *pn;
+
+ iocg = cgroup_to_io_cgroup(cgrp);
+
+ if (list_empty(&iocg->policy_list))
+ goto out;
+
+ seq_printf(m, "dev\tweight\tclass\n");
+
+ spin_lock_irq(&iocg->lock);
+ list_for_each_entry(pn, &iocg->policy_list, node) {
+ seq_printf(m, "%u:%u\t%u\t%hu\n", MAJOR(pn->dev),
+ MINOR(pn->dev), pn->weight, pn->ioprio_class);
+ }
+ spin_unlock_irq(&iocg->lock);
+out:
+ return 0;
+}
+
+static inline void policy_insert_node(struct io_cgroup *iocg,
+ struct io_policy_node *pn)
+{
+ list_add(&pn->node, &iocg->policy_list);
+}
+
+/* Must be called with iocg->lock held */
+static inline void policy_delete_node(struct io_policy_node *pn)
+{
+ list_del(&pn->node);
+}
+
+/* Must be called with iocg->lock held */
+static struct io_policy_node *policy_search_node(const struct io_cgroup *iocg,
+ dev_t dev)
+{
+ struct io_policy_node *pn;
+
+ if (list_empty(&iocg->policy_list))
+ return NULL;
+
+ list_for_each_entry(pn, &iocg->policy_list, node) {
+ if (pn->dev == dev)
+ return pn;
+ }
+
+ return NULL;
+}
+
+static int check_dev_num(dev_t dev)
+{
+ int part = 0;
+ struct gendisk *disk;
+
+ disk = get_gendisk(dev, &part);
+ if (!disk || part)
+ return -ENODEV;
+
+ return 0;
+}
+
+static int policy_parse_and_set(char *buf, struct io_policy_node *newpn)
+{
+ char *s[4], *p, *major_s = NULL, *minor_s = NULL;
+ int ret;
+ unsigned long major, minor, temp;
+ int i = 0;
+ dev_t dev;
+
+ memset(s, 0, sizeof(s));
+ while ((p = strsep(&buf, " ")) != NULL) {
+ if (!*p)
+ continue;
+ s[i++] = p;
+
+ /* Prevent from inputing too many things */
+ if (i == 4)
+ break;
+ }
+
+ if (i != 3)
+ return -EINVAL;
+
+ p = strsep(&s[0], ":");
+ if (p != NULL)
+ major_s = p;
+ else
+ return -EINVAL;
+
+ minor_s = s[0];
+ if (!minor_s)
+ return -EINVAL;
+
+ ret = strict_strtoul(major_s, 10, &major);
+ if (ret)
+ return -EINVAL;
+
+ ret = strict_strtoul(minor_s, 10, &minor);
+ if (ret)
+ return -EINVAL;
+
+ dev = MKDEV(major, minor);
+
+ ret = check_dev_num(dev);
+ if (ret)
+ return ret;
+
+ newpn->dev = dev;
+
+ if (s[1] == NULL)
+ return -EINVAL;
+
+ ret = strict_strtoul(s[1], 10, &temp);
+ if (ret || temp > WEIGHT_MAX)
+ return -EINVAL;
+
+ newpn->weight = temp;
+
+ if (s[2] == NULL)
+ return -EINVAL;
+
+ ret = strict_strtoul(s[2], 10, &temp);
+ if (ret || temp < IOPRIO_CLASS_RT || temp > IOPRIO_CLASS_IDLE)
+ return -EINVAL;
+ newpn->ioprio_class = temp;
+
+ return 0;
+}
+
+static int io_cgroup_policy_write(struct cgroup *cgrp, struct cftype *cft,
+ const char *buffer)
+{
+ struct io_cgroup *iocg;
+ struct io_policy_node *newpn, *pn;
+ char *buf;
+ int ret = 0;
+ int keep_newpn = 0;
+ struct hlist_node *n;
+ struct io_group *iog;
+
+ buf = kstrdup(buffer, GFP_KERNEL);
+ if (!buf)
+ return -ENOMEM;
+
+ newpn = kzalloc(sizeof(*newpn), GFP_KERNEL);
+ if (!newpn) {
+ ret = -ENOMEM;
+ goto free_buf;
+ }
+
+ ret = policy_parse_and_set(buf, newpn);
+ if (ret)
+ goto free_newpn;
+
+ if (!cgroup_lock_live_group(cgrp)) {
+ ret = -ENODEV;
+ goto free_newpn;
+ }
+
+ iocg = cgroup_to_io_cgroup(cgrp);
+ spin_lock_irq(&iocg->lock);
+
+ pn = policy_search_node(iocg, newpn->dev);
+ if (!pn) {
+ if (newpn->weight != 0) {
+ policy_insert_node(iocg, newpn);
+ keep_newpn = 1;
+ }
+ goto update_io_group;
+ }
+
+ if (newpn->weight == 0) {
+ /* weight == 0 means deleteing a policy */
+ policy_delete_node(pn);
+ goto update_io_group;
+ }
+
+ pn->weight = newpn->weight;
+ pn->ioprio_class = newpn->ioprio_class;
+
+update_io_group:
+ hlist_for_each_entry(iog, n, &iocg->group_data, group_node) {
+ if (iog->dev == newpn->dev) {
+ if (newpn->weight) {
+ iog->entity.new_weight = newpn->weight;
+ iog->entity.new_ioprio_class =
+ newpn->ioprio_class;
+ /*
+ * iog weight and ioprio_class updating
+ * actually happens if ioprio_changed is set.
+ * So ensure ioprio_changed is not set until
+ * new weight and new ioprio_class are updated.
+ */
+ smp_wmb();
+ iog->entity.ioprio_changed = 1;
+ } else {
+ iog->entity.new_weight = iocg->weight;
+ iog->entity.new_ioprio_class =
+ iocg->ioprio_class;
+
+ /* The same as above */
+ smp_wmb();
+ iog->entity.ioprio_changed = 1;
+ }
+ }
+ }
+ spin_unlock_irq(&iocg->lock);
+
+ cgroup_unlock();
+
+free_newpn:
+ if (!keep_newpn)
+ kfree(newpn);
+free_buf:
+ kfree(buf);
+ return ret;
+}
+
#define SHOW_FUNCTION(__VAR) \
static u64 io_cgroup_##__VAR##_read(struct cgroup *cgroup, \
struct cftype *cftype) \
@@ -1206,6 +1447,7 @@ static int io_cgroup_##__VAR##_write(struct cgroup *cgroup, \
struct io_cgroup *iocg; \
struct io_group *iog; \
struct hlist_node *n; \
+ struct io_policy_node *pn; \
\
if (val < (__MIN) || val > (__MAX)) \
return -EINVAL; \
@@ -1218,6 +1460,9 @@ static int io_cgroup_##__VAR##_write(struct cgroup *cgroup, \
spin_lock_irq(&iocg->lock); \
iocg->__VAR = (unsigned long)val; \
hlist_for_each_entry(iog, n, &iocg->group_data, group_node) { \
+ pn = policy_search_node(iocg, iog->dev); \
+ if (pn) \
+ continue; \
iog->entity.new_##__VAR = (unsigned long)val; \
smp_wmb(); \
iog->entity.ioprio_changed = 1; \
@@ -1295,6 +1540,12 @@ static int io_cgroup_disk_sectors_read(struct cgroup *cgroup,

struct cftype bfqio_files[] = {
{
+ .name = "policy",
+ .read_seq_string = io_cgroup_policy_read,
+ .write_string = io_cgroup_policy_write,
+ .max_write_len = 256,
+ },
+ {
.name = "weight",
.read_u64 = io_cgroup_weight_read,
.write_u64 = io_cgroup_weight_write,
@@ -1336,6 +1587,7 @@ static struct cgroup_subsys_state *iocg_create(struct cgroup_subsys *subsys,
INIT_HLIST_HEAD(&iocg->group_data);
iocg->weight = IO_DEFAULT_GRP_WEIGHT;
iocg->ioprio_class = IO_DEFAULT_GRP_CLASS;
+ INIT_LIST_HEAD(&iocg->policy_list);

return &iocg->css;
}
@@ -1438,7 +1690,7 @@ io_group_chain_alloc(struct request_queue *q, void *key, struct cgroup *cgroup)
sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
iog->dev = MKDEV(major, minor);

- io_group_init_entity(iocg, iog);
+ io_group_init_entity(iocg, iog, iog->dev);
iog->my_entity = &iog->entity;

atomic_set(&iog->ref, 0);
@@ -1904,6 +2156,7 @@ static void iocg_destroy(struct cgroup_subsys *subsys, struct cgroup *cgroup)
struct io_group *iog;
struct elv_fq_data *efqd;
unsigned long uninitialized_var(flags);
+ struct io_policy_node *pn, *pntmp;

/*
* io groups are linked in two lists. One list is maintained
@@ -1943,6 +2196,11 @@ remove_entry:
goto remove_entry;

done:
+ list_for_each_entry_safe(pn, pntmp, &iocg->policy_list, node) {
+ policy_delete_node(pn);
+ kfree(pn);
+ }
+
free_css_id(&io_subsys, &iocg->css);
rcu_read_unlock();
BUG_ON(!hlist_empty(&iocg->group_data));
diff --git a/block/elevator-fq.h b/block/elevator-fq.h
index 214fb61..58c650b 100644
--- a/block/elevator-fq.h
+++ b/block/elevator-fq.h
@@ -267,6 +267,13 @@ struct io_group {
struct request_list rl;
};

+struct io_policy_node {
+ struct list_head node;
+ dev_t dev;
+ unsigned int weight;
+ unsigned short ioprio_class;
+};
+
/**
* struct io_cgroup - io cgroup data structure.
* @css: subsystem state for io in the containing cgroup.
@@ -284,6 +291,9 @@ struct io_cgroup {
unsigned int weight;
unsigned short ioprio_class;

+ /* list of io_policy_node */
+ struct list_head policy_list;
+
spinlock_t lock;
struct hlist_head group_data;
};
--
1.6.0.6

2009-07-02 20:06:26

by Vivek Goyal

Subject: [PATCH 16/25] io-controller: noop changes for hierarchical fair queuing

This patch changes noop to use queue scheduling code from elevator layer.
One can go back to old noop by deselecting CONFIG_IOSCHED_NOOP_HIER.

Signed-off-by: Nauman Rafique <[email protected]>
Signed-off-by: Vivek Goyal <[email protected]>
---
block/Kconfig.iosched | 11 +++++++++++
block/noop-iosched.c | 13 +++++++++++++
2 files changed, 24 insertions(+), 0 deletions(-)

diff --git a/block/Kconfig.iosched b/block/Kconfig.iosched
index a91a807..9da6657 100644
--- a/block/Kconfig.iosched
+++ b/block/Kconfig.iosched
@@ -25,6 +25,17 @@ config IOSCHED_NOOP
that do their own scheduling and require only minimal assistance from
the kernel.

+config IOSCHED_NOOP_HIER
+ bool "Noop Hierarchical Scheduling support"
+ depends on IOSCHED_NOOP && CGROUPS
+ select ELV_FAIR_QUEUING
+ select GROUP_IOSCHED
+ default n
+ ---help---
+ Enable hierarhical scheduling in noop. In this mode noop keeps
+ one IO queue per cgroup instead of a global queue. Elevator
+ fair queuing logic ensures fairness among various queues.
+
config IOSCHED_AS
tristate "Anticipatory I/O scheduler"
default y
diff --git a/block/noop-iosched.c b/block/noop-iosched.c
index 731dbf2..97ea41b 100644
--- a/block/noop-iosched.c
+++ b/block/noop-iosched.c
@@ -82,6 +82,15 @@ static void noop_free_noop_queue(struct elevator_queue *e, void *sched_queue)
kfree(nq);
}

+#ifdef CONFIG_IOSCHED_NOOP_HIER
+static struct elv_fs_entry noop_attrs[] = {
+ ELV_ATTR(fairness),
+ ELV_ATTR(slice_idle),
+ ELV_ATTR(slice_sync),
+ __ATTR_NULL
+};
+#endif
+
static struct elevator_type elevator_noop = {
.ops = {
.elevator_merge_req_fn = noop_merged_requests,
@@ -92,6 +101,10 @@ static struct elevator_type elevator_noop = {
.elevator_alloc_sched_queue_fn = noop_alloc_noop_queue,
.elevator_free_sched_queue_fn = noop_free_noop_queue,
},
+#ifdef CONFIG_IOSCHED_NOOP_HIER
+ .elevator_features = ELV_IOSCHED_NEED_FQ | ELV_IOSCHED_SINGLE_IOQ,
+ .elevator_attrs = noop_attrs,
+#endif
.elevator_name = "noop",
.elevator_owner = THIS_MODULE,
};
--
1.6.0.6

2009-07-02 20:05:51

by Vivek Goyal

Subject: [PATCH 22/25] io-controller: Per io group bdi congestion interface

o So far there used to be only one pair or queue of request descriptors
(one for sync and one for async) per device and number of requests allocated
used to decide whether associated bdi is congested or not.

Now with per io group request descriptor infrastructure, there is a pair
of request descriptor queue per io group per device. So it might happen
that overall request queue is not congested but a particular io group
bio belongs to is congested.

Or, it could be otherwise that group is not congested but overall queue
is congested. This can happen if user has not properly set the request
descriptors limits for queue and groups.
(q->nr_requests < nr_groups * q->nr_group_requests)

Hence there is a need for new interface which can query deivce congestion
status per group. This group is determined by the "struct page" IO will be
done for. If page is null, then group is determined from the current task
context.

o This patch introduces new set of function bdi_*_congested_group(), which
take "struct page" as addition argument. These functions will call the
block layer and in trun elevator to find out if the io group the page will
go into is congested or not.

o Currently I have introduced the core functions and migrated most of the users.
But there might be still some left. This is an ongoing TODO item.

o There are some io_get_io_group() related changes which should be pushed into
higher patches. Still testing this patch. Will push these changes up in next
posting.

Signed-off-by: Vivek Goyal <[email protected]>
---
block/blk-core.c | 21 ++++++++++++++
block/elevator-fq.c | 58 ++++++++++++++++++++++++++++++++++++++++
block/elevator-fq.h | 6 ++++
drivers/md/dm-table.c | 11 +++++---
drivers/md/dm.c | 7 +++--
drivers/md/dm.h | 3 +-
drivers/md/linear.c | 7 +++-
drivers/md/multipath.c | 7 +++-
drivers/md/raid0.c | 6 +++-
drivers/md/raid1.c | 9 ++++--
drivers/md/raid10.c | 6 +++-
drivers/md/raid5.c | 2 +-
fs/afs/write.c | 8 +++++-
fs/btrfs/disk-io.c | 6 +++-
fs/btrfs/extent_io.c | 12 ++++++++
fs/btrfs/volumes.c | 8 ++++-
fs/cifs/file.c | 11 +++++++
fs/ext2/ialloc.c | 2 +-
fs/gfs2/aops.c | 12 ++++++++
fs/nilfs2/segbuf.c | 3 +-
fs/xfs/linux-2.6/xfs_aops.c | 2 +-
fs/xfs/linux-2.6/xfs_buf.c | 2 +-
include/linux/backing-dev.h | 61 ++++++++++++++++++++++++++++++++++++++++-
include/linux/blkdev.h | 5 +++
mm/backing-dev.c | 62 +++++++++++++++++++++++++++++++++++++++++++
mm/page-writeback.c | 11 +++++++
mm/readahead.c | 2 +-
27 files changed, 318 insertions(+), 32 deletions(-)

diff --git a/block/blk-core.c b/block/blk-core.c
index 2035c20..79fe6a9 100644
--- a/block/blk-core.c
+++ b/block/blk-core.c
@@ -90,6 +90,27 @@ void blk_queue_congestion_threshold(struct request_queue *q)
q->nr_congestion_off = nr;
}

+#ifdef CONFIG_GROUP_IOSCHED
+int blk_queue_io_group_congested(struct backing_dev_info *bdi, int bdi_bits,
+ struct page *page)
+{
+ int ret = 0;
+ struct request_queue *q = bdi->unplug_io_data;
+
+ if (!q && !q->elevator)
+ return bdi_congested(bdi, bdi_bits);
+
+ /* Do we need to hold queue lock? */
+ if (bdi_bits & (1 << BDI_sync_congested))
+ ret |= elv_io_group_congested(q, page, 1);
+
+ if (bdi_bits & (1 << BDI_async_congested))
+ ret |= elv_io_group_congested(q, page, 0);
+
+ return ret;
+}
+#endif
+
/**
* blk_get_backing_dev_info - get the address of a queue's backing_dev_info
* @bdev: device
diff --git a/block/elevator-fq.c b/block/elevator-fq.c
index c4a2b1e..2a2b68d 100644
--- a/block/elevator-fq.c
+++ b/block/elevator-fq.c
@@ -1102,6 +1102,58 @@ struct request_list *io_group_get_request_list(struct request_queue *q,
return &iog->rl;
}

+/* Set io group congestion on and off thresholds */
+void elv_io_group_congestion_threshold(struct request_queue *q,
+ struct io_group *iog)
+{
+ int nr;
+
+ nr = q->nr_group_requests - (q->nr_group_requests / 8) + 1;
+ if (nr > q->nr_group_requests)
+ nr = q->nr_group_requests;
+ iog->nr_congestion_on = nr;
+
+ nr = q->nr_group_requests - (q->nr_group_requests / 8)
+ - (q->nr_group_requests / 16) - 1;
+ if (nr < 1)
+ nr = 1;
+ iog->nr_congestion_off = nr;
+}
+
+static inline int elv_is_iog_congested(struct request_queue *q,
+ struct io_group *iog, int sync)
+{
+ if (iog->rl.count[sync] >= iog->nr_congestion_on)
+ return 1;
+ return 0;
+}
+
+/* Determine if io group page maps to is congested or not */
+int elv_io_group_congested(struct request_queue *q, struct page *page, int sync)
+{
+ struct io_group *iog;
+ int ret = 0;
+
+ rcu_read_lock();
+
+ iog = io_get_io_group(q, page, 0);
+
+ if (!iog) {
+ /*
+ * Either cgroup got deleted or this is first request in the
+ * group and associated io group object has not been created
+ * yet. Map it to root group.
+ *
+ * TODO: Fix the case of group not created yet.
+ */
+ iog = q->elevator->efqd.root_group;
+ }
+
+ ret = elv_is_iog_congested(q, iog, sync);
+ rcu_read_unlock();
+ return ret;
+}
+
/*
* Search the io_group for efqd into the hash table (by now only a list)
* of bgrp. Must be called under rcu_read_lock().
@@ -1401,6 +1453,7 @@ io_group_chain_alloc(struct request_queue *q, void *key, struct cgroup *cgroup)
elv_get_iog(iog);

blk_init_request_list(&iog->rl);
+ elv_io_group_congestion_threshold(q, iog);

if (leaf == NULL) {
leaf = iog;
@@ -1680,6 +1733,7 @@ static struct io_group *io_alloc_root_group(struct request_queue *q,
iog->sched_data.service_tree[i] = IO_SERVICE_TREE_INIT;

blk_init_request_list(&iog->rl);
+ elv_io_group_congestion_threshold(q, iog);

iocg = &io_root_cgroup;
spin_lock_irq(&iocg->lock);
@@ -1688,6 +1742,10 @@ static struct io_group *io_alloc_root_group(struct request_queue *q,
iog->iocg_id = css_id(&iocg->css);
spin_unlock_irq(&iocg->lock);

+#ifdef CONFIG_DEBUG_GROUP_IOSCHED
+ io_group_path(iog, iog->path, sizeof(iog->path));
+#endif
+
return iog;
}

diff --git a/block/elevator-fq.h b/block/elevator-fq.h
index 74a7393..214fb61 100644
--- a/block/elevator-fq.h
+++ b/block/elevator-fq.h
@@ -259,6 +259,10 @@ struct io_group {
/* Single ioq per group, used for noop, deadline, anticipatory */
struct io_queue *ioq;

+ /* io group congestion on and off threshold for request descriptors */
+ unsigned int nr_congestion_on;
+ unsigned int nr_congestion_off;
+
/* request list associated with the group */
struct request_list rl;
};
@@ -531,6 +535,8 @@ extern struct io_queue *elv_lookup_ioq_bio(struct request_queue *q,
struct bio *bio);
extern struct request_list *io_group_get_request_list(struct request_queue *q,
struct bio *bio);
+extern int elv_io_group_congested(struct request_queue *q, struct page *page,
+ int sync);

/* Sets the single ioq associated with the io group. (noop, deadline, AS) */
static inline void io_group_set_ioq(struct io_group *iog, struct io_queue *ioq)
diff --git a/drivers/md/dm-table.c b/drivers/md/dm-table.c
index 4899ebe..e3fd6d8 100644
--- a/drivers/md/dm-table.c
+++ b/drivers/md/dm-table.c
@@ -1175,7 +1175,8 @@ int dm_table_resume_targets(struct dm_table *t)
return 0;
}

-int dm_table_any_congested(struct dm_table *t, int bdi_bits)
+int dm_table_any_congested(struct dm_table *t, int bdi_bits, struct page *page,
+ int group)
{
struct dm_dev_internal *dd;
struct list_head *devices = dm_table_get_devices(t);
@@ -1185,9 +1186,11 @@ int dm_table_any_congested(struct dm_table *t, int bdi_bits)
struct request_queue *q = bdev_get_queue(dd->dm_dev.bdev);
char b[BDEVNAME_SIZE];

- if (likely(q))
- r |= bdi_congested(&q->backing_dev_info, bdi_bits);
- else
+ if (likely(q)) {
+ struct backing_dev_info *bdi = &q->backing_dev_info;
+ r |= group ? bdi_congested_group(bdi, bdi_bits, page)
+ : bdi_congested(bdi, bdi_bits);
+ } else
DMWARN_LIMIT("%s: any_congested: nonexistent device %s",
dm_device_name(t->md),
bdevname(dd->dm_dev.bdev, b));
diff --git a/drivers/md/dm.c b/drivers/md/dm.c
index 3c6d4ee..320ef4c 100644
--- a/drivers/md/dm.c
+++ b/drivers/md/dm.c
@@ -1608,7 +1608,8 @@ static void dm_unplug_all(struct request_queue *q)
}
}

-static int dm_any_congested(void *congested_data, int bdi_bits)
+static int dm_any_congested(void *congested_data, int bdi_bits,
+ struct page *page, int group)
{
int r = bdi_bits;
struct mapped_device *md = congested_data;
@@ -1625,8 +1626,8 @@ static int dm_any_congested(void *congested_data, int bdi_bits)
r = md->queue->backing_dev_info.state &
bdi_bits;
else
- r = dm_table_any_congested(map, bdi_bits);
-
+ r = dm_table_any_congested(map, bdi_bits, page,
+ group);
dm_table_put(map);
}
}
diff --git a/drivers/md/dm.h b/drivers/md/dm.h
index 23278ae..9c4c5a5 100644
--- a/drivers/md/dm.h
+++ b/drivers/md/dm.h
@@ -57,7 +57,8 @@ struct list_head *dm_table_get_devices(struct dm_table *t);
void dm_table_presuspend_targets(struct dm_table *t);
void dm_table_postsuspend_targets(struct dm_table *t);
int dm_table_resume_targets(struct dm_table *t);
-int dm_table_any_congested(struct dm_table *t, int bdi_bits);
+int dm_table_any_congested(struct dm_table *t, int bdi_bits, struct page *page,
+ int group);
int dm_table_any_busy_target(struct dm_table *t);
int dm_table_set_type(struct dm_table *t);
unsigned dm_table_get_type(struct dm_table *t);
diff --git a/drivers/md/linear.c b/drivers/md/linear.c
index 15c8b7b..f227075 100644
--- a/drivers/md/linear.c
+++ b/drivers/md/linear.c
@@ -102,7 +102,7 @@ static void linear_unplug(struct request_queue *q)
rcu_read_unlock();
}

-static int linear_congested(void *data, int bits)
+static int linear_congested(void *data, int bits, struct page *page, int group)
{
mddev_t *mddev = data;
linear_conf_t *conf;
@@ -113,7 +113,10 @@ static int linear_congested(void *data, int bits)

for (i = 0; i < mddev->raid_disks && !ret ; i++) {
struct request_queue *q = bdev_get_queue(conf->disks[i].rdev->bdev);
- ret |= bdi_congested(&q->backing_dev_info, bits);
+ struct backing_dev_info *bdi = &q->backing_dev_info;
+
+ ret |= group ? bdi_congested_group(bdi, bits, page) :
+ bdi_congested(bdi, bits);
}

rcu_read_unlock();
diff --git a/drivers/md/multipath.c b/drivers/md/multipath.c
index cbe368f..87bb1dd 100644
--- a/drivers/md/multipath.c
+++ b/drivers/md/multipath.c
@@ -192,7 +192,8 @@ static void multipath_status (struct seq_file *seq, mddev_t *mddev)
seq_printf (seq, "]");
}

-static int multipath_congested(void *data, int bits)
+static int multipath_congested(void *data, int bits, struct page *page,
+ int group)
{
mddev_t *mddev = data;
multipath_conf_t *conf = mddev->private;
@@ -203,8 +204,10 @@ static int multipath_congested(void *data, int bits)
mdk_rdev_t *rdev = rcu_dereference(conf->multipaths[i].rdev);
if (rdev && !test_bit(Faulty, &rdev->flags)) {
struct request_queue *q = bdev_get_queue(rdev->bdev);
+ struct backing_dev_info *bdi = &q->backing_dev_info;

- ret |= bdi_congested(&q->backing_dev_info, bits);
+ ret |= group ? bdi_congested_group(bdi, bits, page)
+ : bdi_congested(bdi, bits);
/* Just like multipath_map, we just check the
* first available device
*/
diff --git a/drivers/md/raid0.c b/drivers/md/raid0.c
index ab4a489..f7813e7 100644
--- a/drivers/md/raid0.c
+++ b/drivers/md/raid0.c
@@ -37,7 +37,7 @@ static void raid0_unplug(struct request_queue *q)
}
}

-static int raid0_congested(void *data, int bits)
+static int raid0_congested(void *data, int bits, struct page *page, int group)
{
mddev_t *mddev = data;
raid0_conf_t *conf = mddev->private;
@@ -46,8 +46,10 @@ static int raid0_congested(void *data, int bits)

for (i = 0; i < mddev->raid_disks && !ret ; i++) {
struct request_queue *q = bdev_get_queue(devlist[i]->bdev);
+ struct backing_dev_info *bdi = &q->backing_dev_info;

- ret |= bdi_congested(&q->backing_dev_info, bits);
+ ret |= group ? bdi_congested_group(bdi, bits, page)
+ : bdi_congested(bdi, bits);
}
return ret;
}
diff --git a/drivers/md/raid1.c b/drivers/md/raid1.c
index 89939a7..6132848 100644
--- a/drivers/md/raid1.c
+++ b/drivers/md/raid1.c
@@ -570,7 +570,7 @@ static void raid1_unplug(struct request_queue *q)
md_wakeup_thread(mddev->thread);
}

-static int raid1_congested(void *data, int bits)
+static int raid1_congested(void *data, int bits, struct page *page, int group)
{
mddev_t *mddev = data;
conf_t *conf = mddev->private;
@@ -581,14 +581,17 @@ static int raid1_congested(void *data, int bits)
mdk_rdev_t *rdev = rcu_dereference(conf->mirrors[i].rdev);
if (rdev && !test_bit(Faulty, &rdev->flags)) {
struct request_queue *q = bdev_get_queue(rdev->bdev);
+ struct backing_dev_info *bdi = &q->backing_dev_info;

/* Note the '|| 1' - when read_balance prefers
* non-congested targets, it can be removed
*/
if ((bits & (1<<BDI_async_congested)) || 1)
- ret |= bdi_congested(&q->backing_dev_info, bits);
+ ret |= group ? bdi_congested_group(bdi, bits,
+ page) : bdi_congested(bdi, bits);
else
- ret &= bdi_congested(&q->backing_dev_info, bits);
+ ret &= group ? bdi_congested_group(bdi, bits,
+ page) : bdi_congested(bdi, bits);
}
}
rcu_read_unlock();
diff --git a/drivers/md/raid10.c b/drivers/md/raid10.c
index ae12cea..3d9c6b0 100644
--- a/drivers/md/raid10.c
+++ b/drivers/md/raid10.c
@@ -625,7 +625,7 @@ static void raid10_unplug(struct request_queue *q)
md_wakeup_thread(mddev->thread);
}

-static int raid10_congested(void *data, int bits)
+static int raid10_congested(void *data, int bits, struct page *page, int group)
{
mddev_t *mddev = data;
conf_t *conf = mddev->private;
@@ -636,8 +636,10 @@ static int raid10_congested(void *data, int bits)
mdk_rdev_t *rdev = rcu_dereference(conf->mirrors[i].rdev);
if (rdev && !test_bit(Faulty, &rdev->flags)) {
struct request_queue *q = bdev_get_queue(rdev->bdev);
+ struct backing_dev_info *bdi = &q->backing_dev_info;

- ret |= bdi_congested(&q->backing_dev_info, bits);
+ ret |= group ? bdi_congested_group(bdi, bits, page)
+ : bdi_congested(bdi, bits);
}
}
rcu_read_unlock();
diff --git a/drivers/md/raid5.c b/drivers/md/raid5.c
index f9f991e..16e4d1a 100644
--- a/drivers/md/raid5.c
+++ b/drivers/md/raid5.c
@@ -3323,7 +3323,7 @@ static void raid5_unplug_device(struct request_queue *q)
unplug_slaves(mddev);
}

-static int raid5_congested(void *data, int bits)
+static int raid5_congested(void *data, int bits, struct page *page, int group)
{
mddev_t *mddev = data;
raid5_conf_t *conf = mddev->private;
diff --git a/fs/afs/write.c b/fs/afs/write.c
index c2e7a7f..aa8b359 100644
--- a/fs/afs/write.c
+++ b/fs/afs/write.c
@@ -455,7 +455,7 @@ int afs_writepage(struct page *page, struct writeback_control *wbc)
}

wbc->nr_to_write -= ret;
- if (wbc->nonblocking && bdi_write_congested(bdi))
+ if (wbc->nonblocking && bdi_or_group_write_congested(bdi, page))
wbc->encountered_congestion = 1;

_leave(" = 0");
@@ -491,6 +491,12 @@ static int afs_writepages_region(struct address_space *mapping,
return 0;
}

+ if (wbc->nonblocking && bdi_write_congested_group(bdi, page)) {
+ wbc->encountered_congestion = 1;
+ page_cache_release(page);
+ break;
+ }
+
/* at this point we hold neither mapping->tree_lock nor lock on
* the page itself: the page may be truncated or invalidated
* (changing page->mapping to NULL), or even swizzled back from
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index d28d29c..cd7cf6c 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -1249,7 +1249,8 @@ struct btrfs_root *btrfs_read_fs_root(struct btrfs_fs_info *fs_info,
return root;
}

-static int btrfs_congested_fn(void *congested_data, int bdi_bits)
+static int btrfs_congested_fn(void *congested_data, int bdi_bits,
+ struct page *page, int group)
{
struct btrfs_fs_info *info = (struct btrfs_fs_info *)congested_data;
int ret = 0;
@@ -1260,7 +1261,8 @@ static int btrfs_congested_fn(void *congested_data, int bdi_bits)
if (!device->bdev)
continue;
bdi = blk_get_backing_dev_info(device->bdev);
- if (bdi && bdi_congested(bdi, bdi_bits)) {
+ if (bdi && (group ? bdi_congested_group(bdi, bdi_bits, page) :
+ bdi_congested(bdi, bdi_bits))) {
ret = 1;
break;
}
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 6826018..fd7d53f 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -2368,6 +2368,18 @@ retry:
unsigned i;

scanned = 1;
+
+ /*
+ * If the io group page will go into is congested, bail out.
+ */
+ if (wbc->nonblocking
+ && bdi_write_congested_group(bdi, pvec.pages[0])) {
+ wbc->encountered_congestion = 1;
+ done = 1;
+ pagevec_release(&pvec);
+ break;
+ }
+
for (i = 0; i < nr_pages; i++) {
struct page *page = pvec.pages[i];

diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c
index 3ab80e9..7ab5dea 100644
--- a/fs/btrfs/volumes.c
+++ b/fs/btrfs/volumes.c
@@ -165,6 +165,7 @@ static noinline int run_scheduled_bios(struct btrfs_device *device)
unsigned long limit;
unsigned long last_waited = 0;
int force_reg = 0;
+ struct page *page;

bdi = blk_get_backing_dev_info(device->bdev);
fs_info = device->dev_root->fs_info;
@@ -276,8 +277,11 @@ loop_lock:
* is now congested. Back off and let other work structs
* run instead
*/
- if (pending && bdi_write_congested(bdi) && batch_run > 32 &&
- fs_info->fs_devices->open_devices > 1) {
+ if (pending)
+ page = bio_iovec_idx(pending, 0)->bv_page;
+
+ if (pending && bdi_or_group_write_congested(bdi, page) &&
+ num_run > 32 && fs_info->fs_devices->open_devices > 1) {
struct io_context *ioc;

ioc = current->io_context;
diff --git a/fs/cifs/file.c b/fs/cifs/file.c
index 0686684..365ca1b 100644
--- a/fs/cifs/file.c
+++ b/fs/cifs/file.c
@@ -1466,6 +1466,17 @@ retry:
n_iov = 0;
bytes_to_write = 0;

+ /*
+ * If the io group page will go into is congested, bail out.
+ */
+ if (wbc->nonblocking &&
+ bdi_write_congested_group(bdi, pvec.pages[0])) {
+ wbc->encountered_congestion = 1;
+ done = 1;
+ pagevec_release(&pvec);
+ break;
+ }
+
for (i = 0; i < nr_pages; i++) {
page = pvec.pages[i];
/*
diff --git a/fs/ext2/ialloc.c b/fs/ext2/ialloc.c
index 15387c9..090a961 100644
--- a/fs/ext2/ialloc.c
+++ b/fs/ext2/ialloc.c
@@ -179,7 +179,7 @@ static void ext2_preread_inode(struct inode *inode)
struct backing_dev_info *bdi;

bdi = inode->i_mapping->backing_dev_info;
- if (bdi_read_congested(bdi))
+ if (bdi_or_group_read_congested(bdi, NULL))
return;
if (bdi_write_congested(bdi))
return;
diff --git a/fs/gfs2/aops.c b/fs/gfs2/aops.c
index 03ebb43..5b9c93b 100644
--- a/fs/gfs2/aops.c
+++ b/fs/gfs2/aops.c
@@ -371,6 +371,18 @@ retry:
PAGECACHE_TAG_DIRTY,
min(end - index, (pgoff_t)PAGEVEC_SIZE-1) + 1))) {
scanned = 1;
+
+ /*
+ * If io group page belongs to is congested. bail out.
+ */
+ if (wbc->nonblocking
+ && bdi_write_congested_group(bdi, pvec.pages[0])) {
+ wbc->encountered_congestion = 1;
+ done = 1;
+ pagevec_release(&pvec);
+ break;
+ }
+
ret = gfs2_write_jdata_pagevec(mapping, wbc, &pvec, nr_pages, end);
if (ret)
done = 1;
diff --git a/fs/nilfs2/segbuf.c b/fs/nilfs2/segbuf.c
index 9e3fe17..aa29612 100644
--- a/fs/nilfs2/segbuf.c
+++ b/fs/nilfs2/segbuf.c
@@ -266,8 +266,9 @@ static int nilfs_submit_seg_bio(struct nilfs_write_info *wi, int mode)
{
struct bio *bio = wi->bio;
int err;
+ struct page *page = bio_iovec_idx(bio, 0)->bv_page;

- if (wi->nbio > 0 && bdi_write_congested(wi->bdi)) {
+ if (wi->nbio > 0 && bdi_or_group_write_congested(wi->bdi, page)) {
wait_for_completion(&wi->bio_event);
wi->nbio--;
if (unlikely(atomic_read(&wi->err))) {
diff --git a/fs/xfs/linux-2.6/xfs_aops.c b/fs/xfs/linux-2.6/xfs_aops.c
index 7ec89fc..2a515ab 100644
--- a/fs/xfs/linux-2.6/xfs_aops.c
+++ b/fs/xfs/linux-2.6/xfs_aops.c
@@ -891,7 +891,7 @@ xfs_convert_page(

bdi = inode->i_mapping->backing_dev_info;
wbc->nr_to_write--;
- if (bdi_write_congested(bdi)) {
+ if (bdi_or_group_write_congested(bdi, page)) {
wbc->encountered_congestion = 1;
done = 1;
} else if (wbc->nr_to_write <= 0) {
diff --git a/fs/xfs/linux-2.6/xfs_buf.c b/fs/xfs/linux-2.6/xfs_buf.c
index 1418b91..e95c97e 100644
--- a/fs/xfs/linux-2.6/xfs_buf.c
+++ b/fs/xfs/linux-2.6/xfs_buf.c
@@ -714,7 +714,7 @@ xfs_buf_readahead(
struct backing_dev_info *bdi;

bdi = target->bt_mapping->backing_dev_info;
- if (bdi_read_congested(bdi))
+ if (bdi_or_group_read_congested(bdi, NULL))
return;

flags |= (XBF_TRYLOCK|XBF_ASYNC|XBF_READ_AHEAD);
diff --git a/include/linux/backing-dev.h b/include/linux/backing-dev.h
index 0ec2c59..f06fdbf 100644
--- a/include/linux/backing-dev.h
+++ b/include/linux/backing-dev.h
@@ -29,7 +29,7 @@ enum bdi_state {
BDI_unused, /* Available bits start here */
};

-typedef int (congested_fn)(void *, int);
+typedef int (congested_fn)(void *, int, struct page *, int);

enum bdi_stat_item {
BDI_RECLAIMABLE,
@@ -209,7 +209,7 @@ int writeback_in_progress(struct backing_dev_info *bdi);
static inline int bdi_congested(struct backing_dev_info *bdi, int bdi_bits)
{
if (bdi->congested_fn)
- return bdi->congested_fn(bdi->congested_data, bdi_bits);
+ return bdi->congested_fn(bdi->congested_data, bdi_bits, NULL, 0);
return (bdi->state & bdi_bits);
}

@@ -229,6 +229,63 @@ static inline int bdi_rw_congested(struct backing_dev_info *bdi)
(1 << BDI_async_congested));
}

+#ifdef CONFIG_GROUP_IOSCHED
+extern int bdi_congested_group(struct backing_dev_info *bdi, int bdi_bits,
+ struct page *page);
+
+extern int bdi_read_congested_group(struct backing_dev_info *bdi,
+ struct page *page);
+
+extern int bdi_or_group_read_congested(struct backing_dev_info *bdi,
+ struct page *page);
+
+extern int bdi_write_congested_group(struct backing_dev_info *bdi,
+ struct page *page);
+
+extern int bdi_or_group_write_congested(struct backing_dev_info *bdi,
+ struct page *page);
+
+extern int bdi_rw_congested_group(struct backing_dev_info *bdi,
+ struct page *page);
+#else /* CONFIG_GROUP_IOSCHED */
+static inline int bdi_congested_group(struct backing_dev_info *bdi,
+ int bdi_bits, struct page *page)
+{
+ return bdi_congested(bdi, bdi_bits);
+}
+
+static inline int bdi_read_congested_group(struct backing_dev_info *bdi,
+ struct page *page)
+{
+ return bdi_read_congested(bdi);
+}
+
+static inline int bdi_or_group_read_congested(struct backing_dev_info *bdi,
+ struct page *page)
+{
+ return bdi_read_congested(bdi);
+}
+
+static inline int bdi_write_congested_group(struct backing_dev_info *bdi,
+ struct page *page)
+{
+ return bdi_write_congested(bdi);
+}
+
+static inline int bdi_or_group_write_congested(struct backing_dev_info *bdi,
+ struct page *page)
+{
+ return bdi_write_congested(bdi);
+}
+
+static inline int bdi_rw_congested_group(struct backing_dev_info *bdi,
+ struct page *page)
+{
+ return bdi_rw_congested(bdi);
+}
+
+#endif /* CONFIG_GROUP_IOSCHED */
+
void clear_bdi_congested(struct backing_dev_info *bdi, int rw);
void set_bdi_congested(struct backing_dev_info *bdi, int rw);
long congestion_wait(int rw, long timeout);
diff --git a/include/linux/blkdev.h b/include/linux/blkdev.h
index 655440c..e8565b1 100644
--- a/include/linux/blkdev.h
+++ b/include/linux/blkdev.h
@@ -897,6 +897,11 @@ static inline void blk_set_queue_congested(struct request_queue *q, int rw)
set_bdi_congested(&q->backing_dev_info, rw);
}

+#ifdef CONFIG_GROUP_IOSCHED
+extern int blk_queue_io_group_congested(struct backing_dev_info *bdi,
+ int bdi_bits, struct page *page);
+#endif
+
extern void blk_start_queue(struct request_queue *q);
extern void blk_stop_queue(struct request_queue *q);
extern void blk_sync_queue(struct request_queue *q);
diff --git a/mm/backing-dev.c b/mm/backing-dev.c
index 493b468..cef038d 100644
--- a/mm/backing-dev.c
+++ b/mm/backing-dev.c
@@ -7,6 +7,7 @@
#include <linux/module.h>
#include <linux/writeback.h>
#include <linux/device.h>
+#include "../block/elevator-fq.h"

void default_unplug_io_fn(struct backing_dev_info *bdi, struct page *page)
{
@@ -328,3 +329,64 @@ long congestion_wait(int rw, long timeout)
}
EXPORT_SYMBOL(congestion_wait);

+/*
+ * With group IO scheduling, there are request descriptors per io group per
+ * queue. So generic notion of whether queue is congested or not is not
+ * very accurate. Queue might not be congested but the io group in which
+ * request will go might actually be congested.
+ *
+ * Hence to get the correct idea about congestion level, one should query
+ * the io group congestion status on the queue. Pass in the page information
+ * which can be used to determine the io group of the page and congestion
+ * status can be determined accordingly.
+ *
+ * If page info is not passed, io group is determined from the current task
+ * context.
+ */
+#ifdef CONFIG_GROUP_IOSCHED
+int bdi_congested_group(struct backing_dev_info *bdi, int bdi_bits,
+ struct page *page)
+{
+ if (bdi->congested_fn)
+ return bdi->congested_fn(bdi->congested_data, bdi_bits, page, 1);
+
+ return blk_queue_io_group_congested(bdi, bdi_bits, page);
+}
+EXPORT_SYMBOL(bdi_congested_group);
+
+int bdi_read_congested_group(struct backing_dev_info *bdi, struct page *page)
+{
+ return bdi_congested_group(bdi, 1 << BDI_sync_congested, page);
+}
+EXPORT_SYMBOL(bdi_read_congested_group);
+
+/* Checks if either bdi or associated group is read congested */
+int bdi_or_group_read_congested(struct backing_dev_info *bdi,
+ struct page *page)
+{
+ return bdi_read_congested(bdi) || bdi_read_congested_group(bdi, page);
+}
+EXPORT_SYMBOL(bdi_or_group_read_congested);
+
+int bdi_write_congested_group(struct backing_dev_info *bdi, struct page *page)
+{
+ return bdi_congested_group(bdi, 1 << BDI_async_congested, page);
+}
+EXPORT_SYMBOL(bdi_write_congested_group);
+
+/* Checks if either bdi or associated group is write congested */
+int bdi_or_group_write_congested(struct backing_dev_info *bdi,
+ struct page *page)
+{
+ return bdi_write_congested(bdi) || bdi_write_congested_group(bdi, page);
+}
+EXPORT_SYMBOL(bdi_or_group_write_congested);
+
+int bdi_rw_congested_group(struct backing_dev_info *bdi, struct page *page)
+{
+ return bdi_congested_group(bdi, (1 << BDI_sync_congested) |
+ (1 << BDI_async_congested), page);
+}
+EXPORT_SYMBOL(bdi_rw_congested_group);
+
+#endif /* CONFIG_GROUP_IOSCHED */
diff --git a/mm/page-writeback.c b/mm/page-writeback.c
index 31d3675..5ad9453 100644
--- a/mm/page-writeback.c
+++ b/mm/page-writeback.c
@@ -982,6 +982,17 @@ retry:
if (nr_pages == 0)
break;

+ /*
+ * If the io group page will go into is congested, bail out.
+ */
+ if (wbc->nonblocking
+ && bdi_write_congested_group(bdi, pvec.pages[0])) {
+ wbc->encountered_congestion = 1;
+ done = 1;
+ pagevec_release(&pvec);
+ break;
+ }
+
for (i = 0; i < nr_pages; i++) {
struct page *page = pvec.pages[i];

diff --git a/mm/readahead.c b/mm/readahead.c
index aa1aa23..22e0639 100644
--- a/mm/readahead.c
+++ b/mm/readahead.c
@@ -542,7 +542,7 @@ page_cache_async_readahead(struct address_space *mapping,
/*
* Defer asynchronous read-ahead on IO congestion.
*/
- if (bdi_read_congested(mapping->backing_dev_info))
+ if (bdi_or_group_read_congested(mapping->backing_dev_info, NULL))
return;

/* do read-ahead */
--
1.6.0.6

2009-07-02 20:06:10

by Vivek Goyal

Subject: [PATCH 10/25] io-controller: cfq changes to use hierarchical fair queuing code in elevaotor layer

Make cfq hierarhical.

Signed-off-by: Nauman Rafique <[email protected]>
Signed-off-by: Fabio Checconi <[email protected]>
Signed-off-by: Paolo Valente <[email protected]>
Signed-off-by: Aristeu Rozanski <[email protected]>
Signed-off-by: Vivek Goyal <[email protected]>
---
block/Kconfig.iosched | 8 ++++++
block/cfq-iosched.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++-
init/Kconfig | 2 +-
3 files changed, 69 insertions(+), 3 deletions(-)

diff --git a/block/Kconfig.iosched b/block/Kconfig.iosched
index dd5224d..a91a807 100644
--- a/block/Kconfig.iosched
+++ b/block/Kconfig.iosched
@@ -54,6 +54,14 @@ config IOSCHED_CFQ
working environment, suitable for desktop systems.
This is the default I/O scheduler.

+config IOSCHED_CFQ_HIER
+ bool "CFQ Hierarchical Scheduling support"
+ depends on IOSCHED_CFQ && CGROUPS
+ select GROUP_IOSCHED
+ default n
+ ---help---
+ Enable hierarhical scheduling in cfq.
+
choice
prompt "Default I/O scheduler"
default DEFAULT_CFQ
diff --git a/block/cfq-iosched.c b/block/cfq-iosched.c
index 6ddc882..02b5cd5 100644
--- a/block/cfq-iosched.c
+++ b/block/cfq-iosched.c
@@ -1222,6 +1222,60 @@ static void cfq_ioc_set_ioprio(struct io_context *ioc)
ioc->ioprio_changed = 0;
}

+#ifdef CONFIG_IOSCHED_CFQ_HIER
+static void changed_cgroup(struct io_context *ioc, struct cfq_io_context *cic)
+{
+ struct cfq_queue *async_cfqq = cic_to_cfqq(cic, 0);
+ struct cfq_queue *sync_cfqq = cic_to_cfqq(cic, 1);
+ struct cfq_data *cfqd = cic->key;
+ struct io_group *iog, *__iog;
+ unsigned long flags;
+ struct request_queue *q;
+
+ if (unlikely(!cfqd))
+ return;
+
+ q = cfqd->queue;
+
+ spin_lock_irqsave(q->queue_lock, flags);
+
+ iog = io_get_io_group(q, 0);
+
+ if (async_cfqq != NULL) {
+ __iog = cfqq_to_io_group(async_cfqq);
+ if (iog != __iog) {
+ /* cgroup changed, drop the reference to async queue */
+ cic_set_cfqq(cic, NULL, 0);
+ cfq_put_queue(async_cfqq);
+ }
+ }
+
+ if (sync_cfqq != NULL) {
+ __iog = cfqq_to_io_group(sync_cfqq);
+
+ /*
+ * Drop reference to sync queue. A new sync queue will
+ * be assigned in new group upon arrival of a fresh request.
+ * If old queue has got requests, those reuests will be
+ * dispatched over a period of time and queue will be freed
+ * automatically.
+ */
+ if (iog != __iog) {
+ cic_set_cfqq(cic, NULL, 1);
+ cfq_put_queue(sync_cfqq);
+ }
+ }
+
+ spin_unlock_irqrestore(q->queue_lock, flags);
+}
+
+static void cfq_ioc_set_cgroup(struct io_context *ioc)
+{
+ call_for_each_cic(ioc, changed_cgroup);
+ ioc->cgroup_changed = 0;
+}
+#endif /* CONFIG_IOSCHED_CFQ_HIER */
+
static struct cfq_queue *
cfq_find_alloc_queue(struct cfq_data *cfqd, int is_sync,
struct io_context *ioc, gfp_t gfp_mask)
@@ -1232,7 +1286,7 @@ cfq_find_alloc_queue(struct cfq_data *cfqd, int is_sync,
struct io_queue *ioq = NULL, *new_ioq = NULL;
struct io_group *iog = NULL;
retry:
- iog = io_get_io_group(q);
+ iog = io_get_io_group(q, 1);

cic = cfq_cic_lookup(cfqd, ioc);
/* cic always exists here */
@@ -1334,7 +1388,7 @@ cfq_get_queue(struct cfq_data *cfqd, int is_sync, struct io_context *ioc,
const int ioprio_class = task_ioprio_class(ioc);
struct cfq_queue *async_cfqq = NULL;
struct cfq_queue *cfqq = NULL;
- struct io_group *iog = io_get_io_group(cfqd->queue);
+ struct io_group *iog = io_get_io_group(cfqd->queue, 1);

if (!is_sync) {
async_cfqq = io_group_async_queue_prio(iog, ioprio_class,
@@ -1493,6 +1547,10 @@ out:
smp_read_barrier_depends();
if (unlikely(ioc->ioprio_changed))
cfq_ioc_set_ioprio(ioc);
+#ifdef CONFIG_IOSCHED_CFQ_HIER
+ if (unlikely(ioc->cgroup_changed))
+ cfq_ioc_set_cgroup(ioc);
+#endif
return cic;
err_free:
cfq_cic_free(cic);
diff --git a/init/Kconfig b/init/Kconfig
index a380f46..eaa44db 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -613,7 +613,7 @@ config CGROUP_MEM_RES_CTLR_SWAP
size is 4096bytes, 512k per 1Gbytes of swap.

config GROUP_IOSCHED
- bool "Group IO Scheduler"
+ bool
depends on CGROUPS && ELV_FAIR_QUEUING
default n
---help---
--
1.6.0.6

2009-07-02 20:06:39

by Vivek Goyal

Subject: [PATCH 21/25] io-controller: Per cgroup request descriptor support

o Currently a request queue has got fixed number of request descriptors for
sync and async requests. Once the request descriptors are consumed, new
processes are put to sleep and they effectively become serialized. Because
sync and async queues are separate, async requests don't impact sync ones
but if one is looking for fairness between async requests, that is not
achievable if request queue descriptors become bottleneck.

o Make request descriptor's per io group so that if there is lots of IO
going on in one cgroup, it does not impact the IO of other group.

o This is just one relatively simple way of doing things. This patch will
probably change after the feedback. Folks have raised concerns that in
hierchical setup, child's request descriptors should be capped by parent's
request descriptors. May be we need to have per cgroup per device files
in cgroups where one can specify the upper limit of request descriptors
and whenever a cgroup is created one needs to assign request descritor
limit making sure total sum of child's request descriptor is not more than
of parent.

I guess something like memory controller. Anyway, that would be the next
step. For the time being, we have implemented something simpler as follows.

o This patch implements the per cgroup request descriptors. request pool per
queue is still common but every group will have its own wait list and its
own count of request descriptors allocated to that group for sync and async
queues. So effectively request_list becomes per io group property and not a
global request queue feature.

o Currently one can define q->nr_requests to limit request descriptors
allocated for the queue. Now there is another tunable q->nr_group_requests
which controls the requests descriptr limit per group. q->nr_requests
supercedes q->nr_group_requests to make sure if there are lots of groups
present, we don't end up allocating too many request descriptors on the
queue.

Signed-off-by: Nauman Rafique <[email protected]>
Signed-off-by: Vivek Goyal <[email protected]>
---
block/blk-core.c | 305 +++++++++++++++++++++++++++++++++++++----------
block/blk-settings.c | 1 +
block/blk-sysfs.c | 58 +++++++--
block/elevator-fq.c | 14 +++
block/elevator-fq.h | 5 +
block/elevator.c | 7 +-
include/linux/blkdev.h | 87 +++++++++++++-
7 files changed, 395 insertions(+), 82 deletions(-)

diff --git a/block/blk-core.c b/block/blk-core.c
index 6d8b4dd..2035c20 100644
--- a/block/blk-core.c
+++ b/block/blk-core.c
@@ -460,20 +460,30 @@ void blk_cleanup_queue(struct request_queue *q)
}
EXPORT_SYMBOL(blk_cleanup_queue);

-static int blk_init_free_list(struct request_queue *q)
+void blk_init_request_list(struct request_list *rl)
{
- struct request_list *rl = &q->rq;

rl->count[BLK_RW_SYNC] = rl->count[BLK_RW_ASYNC] = 0;
- rl->starved[BLK_RW_SYNC] = rl->starved[BLK_RW_ASYNC] = 0;
- rl->elvpriv = 0;
init_waitqueue_head(&rl->wait[BLK_RW_SYNC]);
init_waitqueue_head(&rl->wait[BLK_RW_ASYNC]);
+}

- rl->rq_pool = mempool_create_node(BLKDEV_MIN_RQ, mempool_alloc_slab,
- mempool_free_slab, request_cachep, q->node);
+static int blk_init_free_list(struct request_queue *q)
+{
+ /*
+ * Initialize the queue request list in case there are non-hiearchical
+ * io schedulers not making use of fair queuing infrastructure.
+ *
+ * For ioschedulers making use of fair queuing infrastructure, request
+ * list is inside the associated group and when that group is
+ * instanciated, it takes care of initializing the request list also.
+ */
+ blk_init_request_list(&q->rq);
+ q->rq_data.rq_pool = mempool_create_node(BLKDEV_MIN_RQ,
+ mempool_alloc_slab, mempool_free_slab,
+ request_cachep, q->node);

- if (!rl->rq_pool)
+ if (!q->rq_data.rq_pool)
return -ENOMEM;

return 0;
@@ -575,6 +585,9 @@ blk_init_queue_node(request_fn_proc *rfn, spinlock_t *lock, int node_id)
return NULL;
}

+ /* init starved waiter wait queue */
+ init_waitqueue_head(&q->rq_data.starved_wait);
+
/*
* if caller didn't supply a lock, they get per-queue locking with
* our embedded lock
@@ -624,14 +637,14 @@ static inline void blk_free_request(struct request_queue *q, struct request *rq)
{
if (rq->cmd_flags & REQ_ELVPRIV)
elv_put_request(q, rq);
- mempool_free(rq, q->rq.rq_pool);
+ mempool_free(rq, q->rq_data.rq_pool);
}

static struct request *
blk_alloc_request(struct request_queue *q, struct bio *bio, int flags, int priv,
gfp_t gfp_mask)
{
- struct request *rq = mempool_alloc(q->rq.rq_pool, gfp_mask);
+ struct request *rq = mempool_alloc(q->rq_data.rq_pool, gfp_mask);

if (!rq)
return NULL;
@@ -642,7 +655,7 @@ blk_alloc_request(struct request_queue *q, struct bio *bio, int flags, int priv,

if (priv) {
if (unlikely(elv_set_request(q, rq, bio, gfp_mask))) {
- mempool_free(rq, q->rq.rq_pool);
+ mempool_free(rq, q->rq_data.rq_pool);
return NULL;
}
rq->cmd_flags |= REQ_ELVPRIV;
@@ -685,18 +698,18 @@ static void ioc_set_batching(struct request_queue *q, struct io_context *ioc)
ioc->last_waited = jiffies;
}

-static void __freed_request(struct request_queue *q, int sync)
+static void __freed_request(struct request_queue *q, int sync,
+ struct request_list *rl)
{
- struct request_list *rl = &q->rq;
-
- if (rl->count[sync] < queue_congestion_off_threshold(q))
+ if (q->rq_data.count[sync] < queue_congestion_off_threshold(q))
blk_clear_queue_congested(q, sync);

- if (rl->count[sync] + 1 <= q->nr_requests) {
+ if (q->rq_data.count[sync] + 1 <= q->nr_requests)
+ blk_clear_queue_full(q, sync);
+
+ if (rl->count[sync] + 1 <= q->nr_group_requests) {
if (waitqueue_active(&rl->wait[sync]))
wake_up(&rl->wait[sync]);
-
- blk_clear_queue_full(q, sync);
}
}

@@ -704,63 +717,133 @@ static void __freed_request(struct request_queue *q, int sync)
* A request has just been released. Account for it, update the full and
* congestion status, wake up any waiters. Called under q->queue_lock.
*/
-static void freed_request(struct request_queue *q, int sync, int priv)
-{
- struct request_list *rl = &q->rq;
+static void freed_request(struct request_queue *q, int sync, int priv,
+ struct request_list *rl)
+{
+ /* There is a window during request allocation where request is
+ * mapped to one group but by the time a queue for the group is
+ * allocated, it is possible that original cgroup/io group has been
+ * deleted and now io queue is allocated in a different group (root)
+ * altogether.
+ *
+ * One solution to the problem is that rq should take io group
+ * reference. But it looks too much to do that to solve this issue.
+ * The only side affect to the hard to hit issue seems to be that
+ * we will try to decrement the rl->count for a request list which
+ * did not allocate that request. Chcek for rl->count going less than
+ * zero and do not decrement it if that's the case.
+ */
+
+ if (priv && rl->count[sync] > 0)
+ rl->count[sync]--;
+
+ BUG_ON(!q->rq_data.count[sync]);
+ q->rq_data.count[sync]--;

- rl->count[sync]--;
if (priv)
- rl->elvpriv--;
+ q->rq_data.elvpriv--;

- __freed_request(q, sync);
+ __freed_request(q, sync, rl);

if (unlikely(rl->starved[sync ^ 1]))
- __freed_request(q, sync ^ 1);
+ __freed_request(q, sync ^ 1, rl);
+
+ /* Wake up the starved process on global list, if any */
+ if (unlikely(q->rq_data.starved)) {
+ if (waitqueue_active(&q->rq_data.starved_wait))
+ wake_up(&q->rq_data.starved_wait);
+ q->rq_data.starved--;
+ }
+}
+
+/*
+ * Returns whether one can sleep on this request list or not. There are
+ * cases (elevator switch) where request list might not have allocated
+ * any request descriptor but we deny request allocation due to gloabl
+ * limits. In that case one should sleep on global list as on this request
+ * list no wakeup will take place.
+ *
+ * Also sets the request list starved flag if there are no requests pending
+ * in the direction of rq.
+ *
+ * Return 1 --> sleep on request list, 0 --> sleep on global list
+ */
+static int can_sleep_on_request_list(struct request_list *rl, int is_sync)
+{
+ if (unlikely(rl->count[is_sync] == 0)) {
+ /*
+ * If there is a request pending in other direction
+ * in same io group, then set the starved flag of
+ * the group request list. Otherwise, we need to
+ * make this process sleep in global starved list
+ * to make sure it will not sleep indefinitely.
+ */
+ if (rl->count[is_sync ^ 1] != 0) {
+ rl->starved[is_sync] = 1;
+ return 1;
+ } else
+ return 0;
+ }
+
+ return 1;
}

/*
* Get a free request, queue_lock must be held.
- * Returns NULL on failure, with queue_lock held.
+ * Returns NULL on failure, with queue_lock held. Also sets the "reason" field
+ * in case of failure. This reason field helps caller decide to whether sleep
+ * on per group list or global per queue list.
+ * reason = 0 sleep on per group list
+ * reason = 1 sleep on global list
+ *
* Returns !NULL on success, with queue_lock *not held*.
*/
static struct request *get_request(struct request_queue *q, int rw_flags,
- struct bio *bio, gfp_t gfp_mask)
+ struct bio *bio, gfp_t gfp_mask,
+ struct request_list *rl, int *reason)
{
struct request *rq = NULL;
- struct request_list *rl = &q->rq;
struct io_context *ioc = NULL;
const bool is_sync = rw_is_sync(rw_flags) != 0;
int may_queue, priv;
+ int sleep_on_global = 0;

may_queue = elv_may_queue(q, rw_flags);
if (may_queue == ELV_MQUEUE_NO)
goto rq_starved;

- if (rl->count[is_sync]+1 >= queue_congestion_on_threshold(q)) {
- if (rl->count[is_sync]+1 >= q->nr_requests) {
- ioc = current_io_context(GFP_ATOMIC, q->node);
- /*
- * The queue will fill after this allocation, so set
- * it as full, and mark this process as "batching".
- * This process will be allowed to complete a batch of
- * requests, others will be blocked.
- */
- if (!blk_queue_full(q, is_sync)) {
- ioc_set_batching(q, ioc);
- blk_set_queue_full(q, is_sync);
- } else {
- if (may_queue != ELV_MQUEUE_MUST
- && !ioc_batching(q, ioc)) {
- /*
- * The queue is full and the allocating
- * process is not a "batcher", and not
- * exempted by the IO scheduler
- */
- goto out;
- }
+ if (q->rq_data.count[is_sync]+1 >= queue_congestion_on_threshold(q))
+ blk_set_queue_congested(q, is_sync);
+
+ /*
+ * Looks like there is no user of queue full now.
+ * Keeping it for time being.
+ */
+ if (q->rq_data.count[is_sync]+1 >= q->nr_requests)
+ blk_set_queue_full(q, is_sync);
+
+ if (rl->count[is_sync]+1 >= q->nr_group_requests) {
+ ioc = current_io_context(GFP_ATOMIC, q->node);
+ /*
+ * The queue request descriptor group will fill after this
+ * allocation, so set
+ * it as full, and mark this process as "batching".
+ * This process will be allowed to complete a batch of
+ * requests, others will be blocked.
+ */
+ if (rl->count[is_sync] <= q->nr_group_requests)
+ ioc_set_batching(q, ioc);
+ else {
+ if (may_queue != ELV_MQUEUE_MUST
+ && !ioc_batching(q, ioc)) {
+ /*
+ * The queue is full and the allocating
+ * process is not a "batcher", and not
+ * exempted by the IO scheduler
+ */
+ goto out;
}
}
- blk_set_queue_congested(q, is_sync);
}

/*
@@ -768,21 +851,60 @@ static struct request *get_request(struct request_queue *q, int rw_flags,
* limit of requests, otherwise we could have thousands of requests
* allocated with any setting of ->nr_requests
*/
- if (rl->count[is_sync] >= (3 * q->nr_requests / 2))
+
+ if (q->rq_data.count[is_sync] >= (3 * q->nr_requests / 2)) {
+ /*
+ * Queue is too full for allocation. On which request queue
+ * the task should sleep? Generally it should sleep on its
+ * request list but if elevator switch is happening, in that
+ * window, request descriptors are allocated from global
+ * pool and are not accounted against any particular request
+ * list as group is going away.
+ *
+ * So it might happen that request list does not have any
+ * requests allocated at all and if process sleeps on per
+ * group request list, it will not be woken up. In such case,
+ * make it sleep on global starved list.
+ */
+ if (test_bit(QUEUE_FLAG_ELVSWITCH, &q->queue_flags)
+ || !can_sleep_on_request_list(rl, is_sync))
+ sleep_on_global = 1;
+ goto out;
+ }
+
+ /*
+ * Allocation of request is allowed from queue perspective. Now check
+ * from per group request list
+ */
+
+ if (rl->count[is_sync] >= (3 * q->nr_group_requests / 2))
goto out;

- rl->count[is_sync]++;
rl->starved[is_sync] = 0;

+ q->rq_data.count[is_sync]++;
+
priv = !test_bit(QUEUE_FLAG_ELVSWITCH, &q->queue_flags);
- if (priv)
- rl->elvpriv++;
+ if (priv) {
+ q->rq_data.elvpriv++;
+ /*
+ * Account the request to request list only if request is
+ * going to elevator. During elevator switch, there will
+ * be small window where group is going away and new group
+ * will not be allocated till elevator switch is complete.
+ * So till then instead of slowing down the application,
+ * we will continue to allocate request from total common
+ * pool instead of per group limit
+ */
+ rl->count[is_sync]++;
+ }

if (blk_queue_io_stat(q))
rw_flags |= REQ_IO_STAT;
spin_unlock_irq(q->queue_lock);

rq = blk_alloc_request(q, bio, rw_flags, priv, gfp_mask);
+
if (unlikely(!rq)) {
/*
* Allocation failed presumably due to memory. Undo anything
@@ -792,7 +914,7 @@ static struct request *get_request(struct request_queue *q, int rw_flags,
* wait queue, but this is pretty rare.
*/
spin_lock_irq(q->queue_lock);
- freed_request(q, is_sync, priv);
+ freed_request(q, is_sync, priv, rl);

/*
* in the very unlikely event that allocation failed and no
@@ -802,9 +924,8 @@ static struct request *get_request(struct request_queue *q, int rw_flags,
* rq mempool into READ and WRITE
*/
rq_starved:
- if (unlikely(rl->count[is_sync] == 0))
- rl->starved[is_sync] = 1;
-
+ if (!can_sleep_on_request_list(rl, is_sync))
+ sleep_on_global = 1;
goto out;
}

@@ -819,6 +940,8 @@ rq_starved:

trace_block_getrq(q, bio, rw_flags & 1);
out:
+ if (reason && sleep_on_global)
+ *reason = 1;
return rq;
}

@@ -832,16 +955,44 @@ static struct request *get_request_wait(struct request_queue *q, int rw_flags,
struct bio *bio)
{
const bool is_sync = rw_is_sync(rw_flags) != 0;
+ int sleep_on_global = 0;
struct request *rq;
+ struct request_list *rl = blk_get_request_list(q, bio);
+ struct io_group *iog = NULL;

- rq = get_request(q, rw_flags, bio, GFP_NOIO);
+ rq = get_request(q, rw_flags, bio, GFP_NOIO, rl, &sleep_on_global);
while (!rq) {
DEFINE_WAIT(wait);
struct io_context *ioc;
- struct request_list *rl = &q->rq;

- prepare_to_wait_exclusive(&rl->wait[is_sync], &wait,
- TASK_UNINTERRUPTIBLE);
+ if (sleep_on_global) {
+ /*
+ * Task failed allocation and needs to wait and
+ * try again. There are no requests pending from
+ * the io group hence need to sleep on global
+ * wait queue. Most likely the allocation failed
+ * because of memory issues.
+ */
+
+ q->rq_data.starved++;
+ prepare_to_wait_exclusive(&q->rq_data.starved_wait,
+ &wait, TASK_UNINTERRUPTIBLE);
+ } else {
+ /*
+ * We are about to sleep on a request list and we
+ * drop queue lock. After waking up, we will do
+ * finish_wait() on request list and in the mean
+ * time group might be gone. Take a reference to
+ * the group now.
+ */
+ prepare_to_wait_exclusive(&rl->wait[is_sync], &wait,
+ TASK_UNINTERRUPTIBLE);
+#ifdef CONFIG_GROUP_IOSCHED
+ iog = rl_iog(rl);
+ if (iog)
+ elv_get_iog(iog);
+#endif
+ }

trace_block_sleeprq(q, bio, rw_flags & 1);

@@ -859,9 +1010,30 @@ static struct request *get_request_wait(struct request_queue *q, int rw_flags,
ioc_set_batching(q, ioc);

spin_lock_irq(q->queue_lock);
- finish_wait(&rl->wait[is_sync], &wait);

- rq = get_request(q, rw_flags, bio, GFP_NOIO);
+ if (sleep_on_global) {
+ finish_wait(&q->rq_data.starved_wait, &wait);
+ sleep_on_global = 0;
+ } else {
+ finish_wait(&rl->wait[is_sync], &wait);
+#ifdef CONFIG_GROUP_IOSCHED
+ /*
+ * We had taken a reference to the rl/iog.
+ * Put that now
+ */
+ iog = rl_iog(rl);
+ if (iog)
+ elv_put_iog(iog);
+#endif
+ }
+
+ /*
+ * After the sleep check the rl again in case cgrop bio
+ * belonged to is gone and it is mapped to root group now
+ */
+ rl = blk_get_request_list(q, bio);
+ rq = get_request(q, rw_flags, bio, GFP_NOIO, rl,
+ &sleep_on_global);
};

return rq;
@@ -870,14 +1042,16 @@ static struct request *get_request_wait(struct request_queue *q, int rw_flags,
struct request *blk_get_request(struct request_queue *q, int rw, gfp_t gfp_mask)
{
struct request *rq;
+ struct request_list *rl;

BUG_ON(rw != READ && rw != WRITE);

spin_lock_irq(q->queue_lock);
+ rl = blk_get_request_list(q, NULL);
if (gfp_mask & __GFP_WAIT) {
rq = get_request_wait(q, rw, NULL);
} else {
- rq = get_request(q, rw, NULL, gfp_mask);
+ rq = get_request(q, rw, NULL, gfp_mask, rl, NULL);
if (!rq)
spin_unlock_irq(q->queue_lock);
}
@@ -1094,12 +1268,13 @@ void __blk_put_request(struct request_queue *q, struct request *req)
if (req->cmd_flags & REQ_ALLOCED) {
int is_sync = rq_is_sync(req) != 0;
int priv = req->cmd_flags & REQ_ELVPRIV;
+ struct request_list *rl = rq_rl(q, req);

BUG_ON(!list_empty(&req->queuelist));
BUG_ON(!hlist_unhashed(&req->hash));

blk_free_request(q, req);
- freed_request(q, is_sync, priv);
+ freed_request(q, is_sync, priv, rl);
}
}
EXPORT_SYMBOL_GPL(__blk_put_request);
diff --git a/block/blk-settings.c b/block/blk-settings.c
index bd582a7..78b8aec 100644
--- a/block/blk-settings.c
+++ b/block/blk-settings.c
@@ -148,6 +148,7 @@ void blk_queue_make_request(struct request_queue *q, make_request_fn *mfn)
* set defaults
*/
q->nr_requests = BLKDEV_MAX_RQ;
+ q->nr_group_requests = BLKDEV_MAX_GROUP_RQ;

q->make_request_fn = mfn;
blk_queue_dma_alignment(q, 511);
diff --git a/block/blk-sysfs.c b/block/blk-sysfs.c
index b1cd040..577ed42 100644
--- a/block/blk-sysfs.c
+++ b/block/blk-sysfs.c
@@ -38,42 +38,66 @@ static ssize_t queue_requests_show(struct request_queue *q, char *page)
static ssize_t
queue_requests_store(struct request_queue *q, const char *page, size_t count)
{
- struct request_list *rl = &q->rq;
+ struct request_list *rl;
unsigned long nr;
int ret = queue_var_store(&nr, page, count);
if (nr < BLKDEV_MIN_RQ)
nr = BLKDEV_MIN_RQ;

spin_lock_irq(q->queue_lock);
+ rl = blk_get_request_list(q, NULL);
q->nr_requests = nr;
blk_queue_congestion_threshold(q);

- if (rl->count[BLK_RW_SYNC] >= queue_congestion_on_threshold(q))
+ if (q->rq_data.count[BLK_RW_SYNC] >= queue_congestion_on_threshold(q))
blk_set_queue_congested(q, BLK_RW_SYNC);
- else if (rl->count[BLK_RW_SYNC] < queue_congestion_off_threshold(q))
+ else if (q->rq_data.count[BLK_RW_SYNC] <
+ queue_congestion_off_threshold(q))
blk_clear_queue_congested(q, BLK_RW_SYNC);

- if (rl->count[BLK_RW_ASYNC] >= queue_congestion_on_threshold(q))
+ if (q->rq_data.count[BLK_RW_ASYNC] >= queue_congestion_on_threshold(q))
blk_set_queue_congested(q, BLK_RW_ASYNC);
- else if (rl->count[BLK_RW_ASYNC] < queue_congestion_off_threshold(q))
+ else if (q->rq_data.count[BLK_RW_ASYNC] <
+ queue_congestion_off_threshold(q))
blk_clear_queue_congested(q, BLK_RW_ASYNC);

- if (rl->count[BLK_RW_SYNC] >= q->nr_requests) {
+ if (q->rq_data.count[BLK_RW_SYNC] >= q->nr_requests) {
blk_set_queue_full(q, BLK_RW_SYNC);
- } else if (rl->count[BLK_RW_SYNC]+1 <= q->nr_requests) {
+ } else if (q->rq_data.count[BLK_RW_SYNC]+1 <= q->nr_requests) {
blk_clear_queue_full(q, BLK_RW_SYNC);
wake_up(&rl->wait[BLK_RW_SYNC]);
}

- if (rl->count[BLK_RW_ASYNC] >= q->nr_requests) {
+ if (q->rq_data.count[BLK_RW_ASYNC] >= q->nr_requests) {
blk_set_queue_full(q, BLK_RW_ASYNC);
- } else if (rl->count[BLK_RW_ASYNC]+1 <= q->nr_requests) {
+ } else if (q->rq_data.count[BLK_RW_ASYNC]+1 <= q->nr_requests) {
blk_clear_queue_full(q, BLK_RW_ASYNC);
wake_up(&rl->wait[BLK_RW_ASYNC]);
}
spin_unlock_irq(q->queue_lock);
return ret;
}
+#ifdef CONFIG_GROUP_IOSCHED
+static ssize_t queue_group_requests_show(struct request_queue *q, char *page)
+{
+ return queue_var_show(q->nr_group_requests, (page));
+}
+
+static ssize_t
+queue_group_requests_store(struct request_queue *q, const char *page,
+ size_t count)
+{
+ unsigned long nr;
+ int ret = queue_var_store(&nr, page, count);
+ if (nr < BLKDEV_MIN_RQ)
+ nr = BLKDEV_MIN_RQ;
+
+ spin_lock_irq(q->queue_lock);
+ q->nr_group_requests = nr;
+ spin_unlock_irq(q->queue_lock);
+ return ret;
+}
+#endif

static ssize_t queue_ra_show(struct request_queue *q, char *page)
{
@@ -239,6 +263,14 @@ static struct queue_sysfs_entry queue_requests_entry = {
.store = queue_requests_store,
};

+#ifdef CONFIG_GROUP_IOSCHED
+static struct queue_sysfs_entry queue_group_requests_entry = {
+ .attr = {.name = "nr_group_requests", .mode = S_IRUGO | S_IWUSR },
+ .show = queue_group_requests_show,
+ .store = queue_group_requests_store,
+};
+#endif
+
static struct queue_sysfs_entry queue_ra_entry = {
.attr = {.name = "read_ahead_kb", .mode = S_IRUGO | S_IWUSR },
.show = queue_ra_show,
@@ -313,6 +345,9 @@ static struct queue_sysfs_entry queue_iostats_entry = {

static struct attribute *default_attrs[] = {
&queue_requests_entry.attr,
+#ifdef CONFIG_GROUP_IOSCHED
+ &queue_group_requests_entry.attr,
+#endif
&queue_ra_entry.attr,
&queue_max_hw_sectors_entry.attr,
&queue_max_sectors_entry.attr,
@@ -392,12 +427,11 @@ static void blk_release_queue(struct kobject *kobj)
{
struct request_queue *q =
container_of(kobj, struct request_queue, kobj);
- struct request_list *rl = &q->rq;

blk_sync_queue(q);

- if (rl->rq_pool)
- mempool_destroy(rl->rq_pool);
+ if (q->rq_data.rq_pool)
+ mempool_destroy(q->rq_data.rq_pool);

if (q->queue_tags)
__blk_queue_free_tags(q);
diff --git a/block/elevator-fq.c b/block/elevator-fq.c
index 899972c..c4a2b1e 100644
--- a/block/elevator-fq.c
+++ b/block/elevator-fq.c
@@ -1092,6 +1092,16 @@ static struct io_cgroup *cgroup_to_io_cgroup(struct cgroup *cgroup)
struct io_cgroup, css);
}

+struct request_list *io_group_get_request_list(struct request_queue *q,
+ struct bio *bio)
+{
+ struct io_group *iog;
+
+ iog = io_get_io_group_bio(q, bio, 1);
+ BUG_ON(!iog);
+ return &iog->rl;
+}
+
/*
* Search the io_group for efqd into the hash table (by now only a list)
* of bgrp. Must be called under rcu_read_lock().
@@ -1390,6 +1400,8 @@ io_group_chain_alloc(struct request_queue *q, void *key, struct cgroup *cgroup)
*/
elv_get_iog(iog);

+ blk_init_request_list(&iog->rl);
+
if (leaf == NULL) {
leaf = iog;
prev = leaf;
@@ -1667,6 +1679,8 @@ static struct io_group *io_alloc_root_group(struct request_queue *q,
for (i = 0; i < IO_IOPRIO_CLASSES; i++)
iog->sched_data.service_tree[i] = IO_SERVICE_TREE_INIT;

+ blk_init_request_list(&iog->rl);
+
iocg = &io_root_cgroup;
spin_lock_irq(&iocg->lock);
rcu_assign_pointer(iog->key, key);
diff --git a/block/elevator-fq.h b/block/elevator-fq.h
index bb43444..74a7393 100644
--- a/block/elevator-fq.h
+++ b/block/elevator-fq.h
@@ -258,6 +258,9 @@ struct io_group {

/* Single ioq per group, used for noop, deadline, anticipatory */
struct io_queue *ioq;
+
+ /* request list associated with the group */
+ struct request_list rl;
};

/**
@@ -526,6 +529,8 @@ extern void elv_fq_unset_request_ioq(struct request_queue *q,
struct request *rq);
extern struct io_queue *elv_lookup_ioq_bio(struct request_queue *q,
struct bio *bio);
+extern struct request_list *io_group_get_request_list(struct request_queue *q,
+ struct bio *bio);

/* Sets the single ioq associated with the io group. (noop, deadline, AS) */
static inline void io_group_set_ioq(struct io_group *iog, struct io_queue *ioq)
diff --git a/block/elevator.c b/block/elevator.c
index 68d5a80..38a118b 100644
--- a/block/elevator.c
+++ b/block/elevator.c
@@ -646,7 +646,7 @@ void elv_quiesce_start(struct request_queue *q)
* make sure we don't have any requests in flight
*/
elv_drain_elevator(q);
- while (q->rq.elvpriv) {
+ while (q->rq_data.elvpriv) {
__blk_run_queue(q);
spin_unlock_irq(q->queue_lock);
msleep(10);
@@ -745,8 +745,9 @@ void elv_insert(struct request_queue *q, struct request *rq, int where)
}

if (unplug_it && blk_queue_plugged(q)) {
- int nrq = q->rq.count[BLK_RW_SYNC] + q->rq.count[BLK_RW_ASYNC]
- - queue_in_flight(q);
+ int nrq = q->rq_data.count[BLK_RW_SYNC] +
+ q->rq_data.count[BLK_RW_ASYNC] -
+ queue_in_flight(q);

if (nrq >= q->unplug_thresh)
__generic_unplug_device(q);
diff --git a/include/linux/blkdev.h b/include/linux/blkdev.h
index 551e17d..655440c 100644
--- a/include/linux/blkdev.h
+++ b/include/linux/blkdev.h
@@ -32,21 +32,51 @@ struct request;
struct sg_io_hdr;

#define BLKDEV_MIN_RQ 4
+
+#ifdef CONFIG_GROUP_IOSCHED
+#define BLKDEV_MAX_RQ 512 /* Default maximum for queue */
+#define BLKDEV_MAX_GROUP_RQ 128 /* Default maximum per group*/
+#else
#define BLKDEV_MAX_RQ 128 /* Default maximum */
+/*
+ * This is eqivalent to case of only one group present (root group). Let
+ * it consume all the request descriptors available on the queue .
+ */
+#define BLKDEV_MAX_GROUP_RQ BLKDEV_MAX_RQ /* Default maximum */
+#endif

struct request;
typedef void (rq_end_io_fn)(struct request *, int);

struct request_list {
/*
- * count[], starved[], and wait[] are indexed by
+ * count[], starved and wait[] are indexed by
* BLK_RW_SYNC/BLK_RW_ASYNC
*/
int count[2];
int starved[2];
+ wait_queue_head_t wait[2];
+};
+
+/*
+ * This data structures keeps track of mempool of requests for the queue
+ * and some overall statistics.
+ */
+struct request_data {
+ /*
+ * Per queue request descriptor count. This is in addition to per
+ * cgroup count
+ */
+ int count[2];
int elvpriv;
mempool_t *rq_pool;
- wait_queue_head_t wait[2];
+ int starved;
+ /*
+ * Global list for starved tasks. A task will be queued here if
+ * it could not allocate request descriptor and the associated
+ * group request list does not have any requests pending.
+ */
+ wait_queue_head_t starved_wait;
};

/*
@@ -355,6 +385,9 @@ struct request_queue
*/
struct request_list rq;

+ /* Contains request pool and other data like starved data */
+ struct request_data rq_data;
+
request_fn_proc *request_fn;
make_request_fn *make_request_fn;
prep_rq_fn *prep_rq_fn;
@@ -416,6 +449,8 @@ struct request_queue
* queue settings
*/
unsigned long nr_requests; /* Max # of requests */
+ /* Max # of per io group requests */
+ unsigned long nr_group_requests;
unsigned int nr_congestion_on;
unsigned int nr_congestion_off;
unsigned int nr_batching;
@@ -795,6 +830,54 @@ extern int scsi_cmd_ioctl(struct request_queue *, struct gendisk *, fmode_t,
extern int sg_scsi_ioctl(struct request_queue *, struct gendisk *, fmode_t,
struct scsi_ioctl_command __user *);

+extern void blk_init_request_list(struct request_list *rl);
+
+static inline struct request_list *blk_get_request_list(struct request_queue *q,
+ struct bio *bio)
+{
+#ifdef CONFIG_GROUP_IOSCHED
+ if (!elv_iosched_fair_queuing_enabled(q->elevator))
+ return &q->rq;
+
+ return io_group_get_request_list(q, bio);
+#else
+ return &q->rq;
+#endif
+}
+
+static inline struct request_list *rq_rl(struct request_queue *q,
+ struct request *rq)
+{
+#ifdef CONFIG_GROUP_IOSCHED
+ struct io_group *iog;
+ int priv = rq->cmd_flags & REQ_ELVPRIV;
+
+ if (!elv_iosched_fair_queuing_enabled(q->elevator))
+ return &q->rq;
+
+ BUG_ON(priv && !rq->ioq);
+
+ if (priv)
+ iog = ioq_to_io_group(rq->ioq);
+ else
+ iog = q->elevator->efqd.root_group;
+
+ BUG_ON(!iog);
+ return &iog->rl;
+#else
+ return &q->rq;
+#endif
+}
+
+static inline struct io_group *rl_iog(struct request_list *rl)
+{
+#ifdef CONFIG_GROUP_IOSCHED
+ return container_of(rl, struct io_group, rl);
+#else
+ return NULL;
+#endif
+}
+
/*
* A queue has just exitted congestion. Note this in the global counter of
* congested queues, and wake up anyone who was waiting for requests to be
--
1.6.0.6

2009-07-02 20:05:34

by Vivek Goyal

Subject: [PATCH 03/25] io-controller: bfq support of in-class preemption

o Generally preemption is associated with cross class where if an request
from RT class is pending it will preempt the ongoing BE or IDLE class
request.

o CFQ also does in-class preemtions like a sync request queue preempting the
async request queue. In that case it looks like preempting queue gains
share and it is not fair.

o Implement the similar functionality in bfq so that we can retain the
existing CFQ behavior.

o This patch creates a bypass path so that a queue can be put at the
front of the service tree (add_front, similar to CFQ), so that it will
be selected next to run. That's a different thing that in the process
this queue gains share.

Signed-off-by: Vivek Goyal <[email protected]>
---
block/elevator-fq.c | 43 +++++++++++++++++++++++++++++++++++++++----
1 files changed, 39 insertions(+), 4 deletions(-)

diff --git a/block/elevator-fq.c b/block/elevator-fq.c
index a58efdc..7ee4321 100644
--- a/block/elevator-fq.c
+++ b/block/elevator-fq.c
@@ -582,7 +582,7 @@ static struct io_entity *bfq_lookup_next_entity(struct io_sched_data *sd,
* service received if @entity is active) of the queue to calculate its
* timestamps.
*/
-static void __bfq_activate_entity(struct io_entity *entity)
+static void __bfq_activate_entity(struct io_entity *entity, int add_front)
{
struct io_sched_data *sd = entity->sched_data;
struct io_service_tree *st = io_entity_service_tree(entity);
@@ -627,7 +627,42 @@ static void __bfq_activate_entity(struct io_entity *entity)
}

st = __bfq_entity_update_prio(st, entity);
- bfq_calc_finish(entity, entity->budget);
+ /*
+ * This is to emulate cfq like functionality where preemption can
+ * happen with-in same class, like sync queue preempting async queue
+ * May be this is not a very good idea from fairness point of view
+ * as preempting queue gains share. Keeping it for now.
+ */
+ if (add_front) {
+ struct io_entity *next_entity;
+
+ /*
+ * Determine the entity which will be dispatched next
+ * Use sd->next_active once hierarchical patch is applied
+ */
+ next_entity = bfq_lookup_next_entity(sd, 0);
+
+ if (next_entity && next_entity != entity) {
+ struct io_service_tree *new_st;
+ u64 delta;
+
+ new_st = io_entity_service_tree(next_entity);
+
+ /*
+ * At this point, both entities should belong to
+ * same service tree as cross service tree preemption
+ * is automatically taken care by algorithm
+ */
+ BUG_ON(new_st != st);
+ entity->finish = next_entity->finish - 1;
+ delta = bfq_delta(entity->budget, entity->weight);
+ entity->start = entity->finish - delta;
+ if (bfq_gt(entity->start, st->vtime))
+ entity->start = st->vtime;
+ }
+ } else {
+ bfq_calc_finish(entity, entity->budget);
+ }
bfq_active_insert(st, entity);
}

@@ -635,9 +670,9 @@ static void __bfq_activate_entity(struct io_entity *entity)
* bfq_activate_entity - activate an entity.
* @entity: the entity to activate.
*/
-static void bfq_activate_entity(struct io_entity *entity)
+static void bfq_activate_entity(struct io_entity *entity, int add_front)
{
- __bfq_activate_entity(entity);
+ __bfq_activate_entity(entity, add_front);
}

/**
--
1.6.0.6

2009-07-02 20:06:53

by Vivek Goyal

Subject: [PATCH 18/25] io-controller: anticipatory changes for hierarchical fair queuing

This patch changes anticipatory scheduler to use queue scheduling code from
elevator layer. One can go back to old as by deselecting
CONFIG_IOSCHED_AS_HIER. Even with CONFIG_IOSCHED_AS_HIER=y, with-out any
other cgroup created, AS behavior should remain the same as old.

o AS is a single queue ioschduler, that means there is one AS queue per group.

o common layer code select the queue to dispatch from based on fairness, and
then AS code selects the request with-in group.

o AS runs reads and writes batches with-in group. So common layer runs timed
group queues and with-in group time, AS runs timed batches of reads and
writes.

o Note: Previously AS write batch length was adjusted synamically whenever
a W->R batch data direction took place and when first request from the
read batch completed.

Now write batch updation takes place when last request from the write
batch has finished during W->R transition.

o AS runs its own anticipation logic to anticipate on reads. common layer also
does the anticipation on the group if think time of the group is with-in
slice_idle.

o Introduced few debugging messages in AS.

Signed-off-by: Nauman Rafique <[email protected]>
Signed-off-by: Vivek Goyal <[email protected]>
---
block/Kconfig.iosched | 12 ++
block/as-iosched.c | 280 +++++++++++++++++++++++++++++++++++++++++++++-
block/elevator-fq.c | 93 +++++++++++++--
block/elevator-fq.h | 3 +
include/linux/elevator.h | 2 +
5 files changed, 372 insertions(+), 18 deletions(-)

diff --git a/block/Kconfig.iosched b/block/Kconfig.iosched
index 3a9e7d7..77fc786 100644
--- a/block/Kconfig.iosched
+++ b/block/Kconfig.iosched
@@ -45,6 +45,18 @@ config IOSCHED_AS
deadline I/O scheduler, it can also be slower in some cases
especially some database loads.

+config IOSCHED_AS_HIER
+ bool "Anticipatory Hierarchical Scheduling support"
+ depends on IOSCHED_AS && CGROUPS
+ select ELV_FAIR_QUEUING
+ select GROUP_IOSCHED
+ default n
+ ---help---
+ Enable hierarhical scheduling in anticipatory. In this mode
+ anticipatory keeps one IO queue per cgroup instead of a global
+ queue. Elevator fair queuing logic ensures fairness among various
+ queues.
+
config IOSCHED_DEADLINE
tristate "Deadline I/O scheduler"
default y
diff --git a/block/as-iosched.c b/block/as-iosched.c
index e3514eb..18a61bb 100644
--- a/block/as-iosched.c
+++ b/block/as-iosched.c
@@ -16,6 +16,7 @@
#include <linux/compiler.h>
#include <linux/rbtree.h>
#include <linux/interrupt.h>
+#include <linux/blktrace_api.h>

/*
* See Documentation/block/as-iosched.txt
@@ -84,10 +85,24 @@ struct as_queue {
struct list_head fifo_list[2];

struct request *next_rq[2]; /* next in sort order */
+
+ /*
+ * If an as_queue is switched while a batch is running, then we
+ * store the time left before current batch will expire
+ */
+ long current_batch_time_left;
+
+ /*
+ * batch data dir when queue was scheduled out. This will be used
+ * to setup ad->batch_data_dir when queue is scheduled in.
+ */
+ int saved_batch_data_dir;
+
unsigned long last_check_fifo[2];
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? */
+ int nr_queued[2];
};

struct as_data {
@@ -123,6 +138,9 @@ struct as_data {
unsigned long fifo_expire[2];
unsigned long batch_expire[2];
unsigned long antic_expire;
+
+ /* elevator requested a queue switch. */
+ int switch_queue;
};

/*
@@ -144,12 +162,174 @@ enum arq_state {
#define RQ_STATE(rq) ((enum arq_state)(rq)->elevator_private2)
#define RQ_SET_STATE(rq, state) ((rq)->elevator_private2 = (void *) state)

+#define as_log(ad, fmt, args...) \
+ blk_add_trace_msg((ad)->q, "as " fmt, ##args)
+
static DEFINE_PER_CPU(unsigned long, ioc_count);
static struct completion *ioc_gone;
static DEFINE_SPINLOCK(ioc_gone_lock);

static void as_move_to_dispatch(struct as_data *ad, struct request *rq);
static void as_antic_stop(struct as_data *ad);
+static inline int as_batch_expired(struct as_data *ad, struct as_queue *asq);
+
+#ifdef CONFIG_IOSCHED_AS_HIER
+static void as_save_batch_context(struct as_data *ad, struct as_queue *asq)
+{
+ /* Save batch data dir */
+ asq->saved_batch_data_dir = ad->batch_data_dir;
+
+ if (ad->changed_batch) {
+ /*
+ * In case of force expire, we come here. Batch changeover
+ * has been signalled but we are waiting for all the
+ * request to finish from previous batch and then start
+ * the new batch. Can't wait now. Mark that full batch time
+ * needs to be allocated when this queue is scheduled again.
+ */
+ asq->current_batch_time_left =
+ ad->batch_expire[ad->batch_data_dir];
+ ad->changed_batch = 0;
+ goto out;
+ }
+
+ if (ad->new_batch) {
+ /*
+ * We should come here only when new_batch has been set
+ * but no read request has been issued or if it is a forced
+ * expiry.
+ *
+ * In both the cases, new batch has not started yet so
+ * allocate full batch length for next scheduling opportunity.
+ * We don't do write batch size adjustment in hierarchical
+ * AS so that should not be an issue.
+ */
+ asq->current_batch_time_left =
+ ad->batch_expire[ad->batch_data_dir];
+ ad->new_batch = 0;
+ goto out;
+ }
+
+ /* Save how much time is left before current batch expires */
+ if (as_batch_expired(ad, asq))
+ asq->current_batch_time_left = 0;
+ else {
+ asq->current_batch_time_left = ad->current_batch_expires
+ - jiffies;
+ BUG_ON((asq->current_batch_time_left) < 0);
+ }
+
+ if (ad->io_context) {
+ put_io_context(ad->io_context);
+ ad->io_context = NULL;
+ }
+
+out:
+ as_log(ad, "save batch: dir=%c time_left=%d changed_batch=%d"
+ " new_batch=%d, antic_status=%d",
+ ad->batch_data_dir ? 'R' : 'W',
+ asq->current_batch_time_left,
+ ad->changed_batch, ad->new_batch, ad->antic_status);
+ return;
+}
+
+/*
+ * FIXME: In original AS, read batch's time account started only after when
+ * first request had completed (if last batch was a write batch). But here
+ * we might be rescheduling a read batch right away irrespective of the fact
+ * of disk cache state.
+ */
+static void as_restore_batch_context(struct as_data *ad, struct as_queue *asq)
+{
+ /* Adjust the batch expire time */
+ if (asq->current_batch_time_left)
+ ad->current_batch_expires = jiffies +
+ asq->current_batch_time_left;
+ /* restore asq batch_data_dir info */
+ ad->batch_data_dir = asq->saved_batch_data_dir;
+ as_log(ad, "restore batch: dir=%c time=%d reads_q=%d writes_q=%d"
+ " ad->antic_status=%d",
+ ad->batch_data_dir ? 'R' : 'W',
+ asq->current_batch_time_left,
+ asq->nr_queued[1], asq->nr_queued[0],
+ ad->antic_status);
+}
+
+/* ioq has been set. */
+static void as_active_ioq_set(struct request_queue *q, void *sched_queue,
+ int coop)
+{
+ struct as_queue *asq = sched_queue;
+ struct as_data *ad = q->elevator->elevator_data;
+
+ as_restore_batch_context(ad, asq);
+}
+
+/*
+ * This is a notification from common layer that it wishes to expire this
+ * io queue. AS decides whether queue can be expired, if yes, it also
+ * saves the batch context.
+ */
+static int as_expire_ioq(struct request_queue *q, void *sched_queue,
+ int slice_expired, int force)
+{
+ struct as_data *ad = q->elevator->elevator_data;
+ int status = ad->antic_status;
+ struct as_queue *asq = sched_queue;
+
+ as_log(ad, "as_expire_ioq slice_expired=%d, force=%d", slice_expired,
+ force);
+
+ /* Forced expiry. We don't have a choice */
+ if (force) {
+ as_antic_stop(ad);
+ /*
+ * antic_stop() sets antic_status to FINISHED which signifies
+ * that either we timed out or we found a close request but
+ * that's not the case here. Start from scratch.
+ */
+ ad->antic_status = ANTIC_OFF;
+ as_save_batch_context(ad, asq);
+ ad->switch_queue = 0;
+ return 1;
+ }
+
+ /*
+ * We are waiting for requests to finish from last
+ * batch. Don't expire the queue now
+ */
+ if (ad->changed_batch)
+ goto keep_queue;
+
+ /*
+ * Wait for all requests from existing batch to finish before we
+ * switch the queue. New queue might change the batch direction
+ * and this is to be consistent with AS philosophy of not dispatching
+ * new requests to underlying drive till requests from requests
+ * from previous batch are completed.
+ */
+ if (ad->nr_dispatched)
+ goto keep_queue;
+
+ /*
+ * If AS anticipation is ON, wait for it to finish.
+ */
+ BUG_ON(status == ANTIC_WAIT_REQ);
+
+ if (status == ANTIC_WAIT_NEXT)
+ goto keep_queue;
+
+ /* We are good to expire the queue. Save batch context */
+ as_save_batch_context(ad, asq);
+ ad->switch_queue = 0;
+ return 1;
+
+keep_queue:
+ /* Mark that elevator requested for queue switch whenever possible */
+ ad->switch_queue = 1;
+ return 0;
+}
+#endif

/*
* IO Context helper functions
@@ -429,6 +609,7 @@ static void as_antic_waitnext(struct as_data *ad)
mod_timer(&ad->antic_timer, timeout);

ad->antic_status = ANTIC_WAIT_NEXT;
+ as_log(ad, "antic_waitnext set");
}

/*
@@ -442,8 +623,10 @@ static void as_antic_waitreq(struct as_data *ad)
if (ad->antic_status == ANTIC_OFF) {
if (!ad->io_context || ad->ioc_finished)
as_antic_waitnext(ad);
- else
+ else {
ad->antic_status = ANTIC_WAIT_REQ;
+ as_log(ad, "antic_waitreq set");
+ }
}
}

@@ -455,6 +638,8 @@ static void as_antic_stop(struct as_data *ad)
{
int status = ad->antic_status;

+ as_log(ad, "as_antic_stop antic_status=%d", ad->antic_status);
+
if (status == ANTIC_WAIT_REQ || status == ANTIC_WAIT_NEXT) {
if (status == ANTIC_WAIT_NEXT)
del_timer(&ad->antic_timer);
@@ -474,6 +659,7 @@ static void as_antic_timeout(unsigned long data)
unsigned long flags;

spin_lock_irqsave(q->queue_lock, flags);
+ as_log(ad, "as_antic_timeout");
if (ad->antic_status == ANTIC_WAIT_REQ
|| ad->antic_status == ANTIC_WAIT_NEXT) {
struct as_io_context *aic;
@@ -652,6 +838,21 @@ static int as_can_break_anticipation(struct as_data *ad, struct request *rq)
struct io_context *ioc;
struct as_io_context *aic;

+#ifdef CONFIG_IOSCHED_AS_HIER
+ /*
+ * If the active asq and rq's asq are not same, then one can not
+ * break the anticipation. This primarily becomes useful when a
+ * request is added to a queue which is not being served currently.
+ */
+ if (rq) {
+ struct as_queue *asq = elv_get_sched_queue(ad->q, rq);
+ struct as_queue *curr_asq =
+ elv_active_sched_queue(ad->q->elevator);
+
+ if (asq != curr_asq)
+ return 0;
+ }
+#endif
ioc = ad->io_context;
BUG_ON(!ioc);
spin_lock(&ioc->lock);
@@ -810,16 +1011,20 @@ static void as_update_rq(struct as_data *ad, struct request *rq)
/*
* Gathers timings and resizes the write batch automatically
*/
-static void update_write_batch(struct as_data *ad)
+static void update_write_batch(struct as_data *ad, struct request *rq)
{
unsigned long batch = ad->batch_expire[BLK_RW_ASYNC];
long write_time;
- struct as_queue *asq = elv_get_sched_queue(ad->q, NULL);
+ struct as_queue *asq = elv_get_sched_queue(ad->q, rq);

write_time = (jiffies - ad->current_batch_expires) + batch;
if (write_time < 0)
write_time = 0;

+ as_log(ad, "upd write: write_time=%d batch=%d write_batch_idled=%d"
+ " current_write_count=%d", write_time, batch,
+ asq->write_batch_idled, asq->current_write_count);
+
if (write_time > batch && !asq->write_batch_idled) {
if (write_time > batch * 3)
asq->write_batch_count /= 2;
@@ -834,6 +1039,8 @@ static void update_write_batch(struct as_data *ad)

if (asq->write_batch_count < 1)
asq->write_batch_count = 1;
+
+ as_log(ad, "upd write count=%d", asq->write_batch_count);
}

/*
@@ -843,6 +1050,7 @@ static void update_write_batch(struct as_data *ad)
static void as_completed_request(struct request_queue *q, struct request *rq)
{
struct as_data *ad = q->elevator->elevator_data;
+ struct as_queue *asq = elv_get_sched_queue(q, rq);

WARN_ON(!list_empty(&rq->queuelist));

@@ -851,7 +1059,24 @@ static void as_completed_request(struct request_queue *q, struct request *rq)
goto out;
}

+ as_log(ad, "complete: reads_q=%d writes_q=%d changed_batch=%d"
+ " new_batch=%d switch_queue=%d, dir=%c",
+ asq->nr_queued[1], asq->nr_queued[0], ad->changed_batch,
+ ad->new_batch, ad->switch_queue,
+ ad->batch_data_dir ? 'R' : 'W');
+
if (ad->changed_batch && ad->nr_dispatched == 1) {
+ /*
+ * If this was write batch finishing, adjust the write batch
+ * length.
+ *
+ * Note, write batch length is being calculated upon completion
+ * of last write request finished and not completion of first
+ * read request finished in the next batch.
+ */
+ if (ad->batch_data_dir == BLK_RW_SYNC)
+ update_write_batch(ad, rq);
+
ad->current_batch_expires = jiffies +
ad->batch_expire[ad->batch_data_dir];
kblockd_schedule_work(q, &ad->antic_work);
@@ -869,7 +1094,6 @@ static void as_completed_request(struct request_queue *q, struct request *rq)
* and writeback caches
*/
if (ad->new_batch && ad->batch_data_dir == rq_is_sync(rq)) {
- update_write_batch(ad);
ad->current_batch_expires = jiffies +
ad->batch_expire[BLK_RW_SYNC];
ad->new_batch = 0;
@@ -888,6 +1112,13 @@ static void as_completed_request(struct request_queue *q, struct request *rq)
}

as_put_io_context(rq);
+
+ /*
+ * If elevator requested a queue switch, kick the queue in the
+ * hope that this is right time for switch.
+ */
+ if (ad->switch_queue)
+ kblockd_schedule_work(q, &ad->antic_work);
out:
RQ_SET_STATE(rq, AS_RQ_POSTSCHED);
}
@@ -908,6 +1139,9 @@ static void as_remove_queued_request(struct request_queue *q,

WARN_ON(RQ_STATE(rq) != AS_RQ_QUEUED);

+ BUG_ON(asq->nr_queued[data_dir] <= 0);
+ asq->nr_queued[data_dir]--;
+
ioc = RQ_IOC(rq);
if (ioc && ioc->aic) {
BUG_ON(!atomic_read(&ioc->aic->nr_queued));
@@ -1019,6 +1253,8 @@ static void as_move_to_dispatch(struct as_data *ad, struct request *rq)
if (RQ_IOC(rq) && RQ_IOC(rq)->aic)
atomic_inc(&RQ_IOC(rq)->aic->nr_dispatched);
ad->nr_dispatched++;
+ as_log(ad, "dispatch req dir=%c nr_dispatched = %d",
+ data_dir ? 'R' : 'W', ad->nr_dispatched);
}

/*
@@ -1066,6 +1302,7 @@ static int as_dispatch_request(struct request_queue *q, int force)
}
asq->last_check_fifo[BLK_RW_ASYNC] = jiffies;

+ as_log(ad, "forced dispatch");
return dispatched;
}

@@ -1078,8 +1315,14 @@ static int as_dispatch_request(struct request_queue *q, int force)
if (!(reads || writes)
|| ad->antic_status == ANTIC_WAIT_REQ
|| ad->antic_status == ANTIC_WAIT_NEXT
- || ad->changed_batch)
+ || ad->changed_batch) {
+ as_log(ad, "no dispatch. read_q=%d, writes_q=%d"
+ " ad->antic_status=%d, changed_batch=%d,"
+ " switch_queue=%d new_batch=%d", asq->nr_queued[1],
+ asq->nr_queued[0], ad->antic_status, ad->changed_batch,
+ ad->switch_queue, ad->new_batch);
return 0;
+ }

if (!(reads && writes && as_batch_expired(ad, asq))) {
/*
@@ -1092,6 +1335,7 @@ static int as_dispatch_request(struct request_queue *q, int force)
goto fifo_expired;

if (as_can_anticipate(ad, rq)) {
+ as_log(ad, "can_anticipate = 1");
as_antic_waitreq(ad);
return 0;
}
@@ -1111,6 +1355,8 @@ static int as_dispatch_request(struct request_queue *q, int force)
* data direction (read / write)
*/

+ as_log(ad, "select a fresh batch and request");
+
if (reads) {
BUG_ON(RB_EMPTY_ROOT(&asq->sort_list[BLK_RW_SYNC]));

@@ -1125,6 +1371,7 @@ static int as_dispatch_request(struct request_queue *q, int force)
ad->changed_batch = 1;
}
ad->batch_data_dir = BLK_RW_SYNC;
+ as_log(ad, "new batch dir is sync");
rq = rq_entry_fifo(asq->fifo_list[BLK_RW_SYNC].next);
asq->last_check_fifo[ad->batch_data_dir] = jiffies;
goto dispatch_request;
@@ -1149,6 +1396,7 @@ dispatch_writes:
ad->new_batch = 0;
}
ad->batch_data_dir = BLK_RW_ASYNC;
+ as_log(ad, "new batch dir is async");
asq->current_write_count = asq->write_batch_count;
asq->write_batch_idled = 0;
rq = rq_entry_fifo(asq->fifo_list[BLK_RW_ASYNC].next);
@@ -1184,6 +1432,9 @@ fifo_expired:
ad->changed_batch = 0;
}

+ if (ad->switch_queue)
+ return 0;
+
/*
* rq is the selected appropriate request.
*/
@@ -1207,6 +1458,11 @@ static void as_add_request(struct request_queue *q, struct request *rq)

rq->elevator_private = as_get_io_context(q->node);

+ asq->nr_queued[data_dir]++;
+ as_log(ad, "add a %c request read_q=%d write_q=%d",
+ data_dir ? 'R' : 'W', asq->nr_queued[1],
+ asq->nr_queued[0]);
+
if (RQ_IOC(rq)) {
as_update_iohist(ad, RQ_IOC(rq)->aic, rq);
atomic_inc(&RQ_IOC(rq)->aic->nr_queued);
@@ -1408,6 +1664,7 @@ static void *as_init_queue(struct request_queue *q)
ad->batch_expire[BLK_RW_ASYNC] = default_write_batch_expire;

ad->current_batch_expires = jiffies + ad->batch_expire[BLK_RW_SYNC];
+ ad->switch_queue = 0;

return ad;
}
@@ -1493,6 +1750,11 @@ static struct elv_fs_entry as_attrs[] = {
AS_ATTR(antic_expire),
AS_ATTR(read_batch_expire),
AS_ATTR(write_batch_expire),
+#ifdef CONFIG_IOSCHED_AS_HIER
+ ELV_ATTR(fairness),
+ ELV_ATTR(slice_idle),
+ ELV_ATTR(slice_sync),
+#endif
__ATTR_NULL
};

@@ -1514,8 +1776,14 @@ static struct elevator_type iosched_as = {
.trim = as_trim,
.elevator_alloc_sched_queue_fn = as_alloc_as_queue,
.elevator_free_sched_queue_fn = as_free_as_queue,
+#ifdef CONFIG_IOSCHED_AS_HIER
+ .elevator_expire_ioq_fn = as_expire_ioq,
+ .elevator_active_ioq_set_fn = as_active_ioq_set,
},
-
+ .elevator_features = ELV_IOSCHED_NEED_FQ | ELV_IOSCHED_SINGLE_IOQ,
+#else
+ },
+#endif
.elevator_attrs = as_attrs,
.elevator_name = "anticipatory",
.elevator_owner = THIS_MODULE,
diff --git a/block/elevator-fq.c b/block/elevator-fq.c
index 25fdac6..c1d04b1 100644
--- a/block/elevator-fq.c
+++ b/block/elevator-fq.c
@@ -2523,6 +2523,7 @@ static void __elv_set_active_ioq(struct elv_fq_data *efqd, struct io_queue *ioq,
elv_clear_ioq_must_dispatch(ioq);
elv_clear_ioq_wait_busy_done(ioq);
elv_mark_ioq_slice_new(ioq);
+ elv_clear_ioq_must_expire(ioq);

del_timer(&efqd->idle_slice_timer);
}
@@ -2646,6 +2647,49 @@ static inline unsigned long elv_disk_time_used(struct request_queue *q,
}

/*
+ * Call iosched to let that elevator wants to expire the queue. This gives
+ * iosched like AS to say no (if it is in the middle of batch changeover or
+ * it is anticipating). it also allows iosched to do some house keeping
+ *
+ * force--> it is force dispatch and iosched must clean up its state. This
+ * is useful when elevator wants to drain iosched and wants to
+ * expire currnent active queue.
+ *
+ * slice_expired--> if 1, ioq slice expired hence elevator fair queuing logic
+ * wants to switch the queue. iosched should allow that until
+ * and unless necessary. Currently AS can deny the switch if
+ * in the middle of batch switch.
+ *
+ * if 0, time slice is still remaining. It is up to the iosched
+ * whether it wants to wait on this queue or just want to
+ * expire it and move on to next queue.
+ *
+ */
+static int elv_iosched_expire_ioq(struct request_queue *q, int slice_expired,
+ int force)
+{
+ struct elevator_queue *e = q->elevator;
+ struct io_queue *ioq = elv_active_ioq(q->elevator);
+ int ret = 1;
+
+ if (e->ops->elevator_expire_ioq_fn) {
+ ret = e->ops->elevator_expire_ioq_fn(q, ioq->sched_queue,
+ slice_expired, force);
+ /*
+ * AS denied expiration of queue right now. Mark that elevator
+ * layer has requested ioscheduler (as) to expire this queue.
+ * Now as will try to expire this queue as soon as it can.
+ * Now don't try to dispatch from this queue even if we get
+ * a new request and if time slice is left. Do expire it once.
+ */
+ if (!ret)
+ elv_mark_ioq_must_expire(ioq);
+ }
+
+ return ret;
+}
+
+/*
* Do the accounting. Determine how much service (in terms of time slices)
* current queue used and adjust the start, finish time of queue and vtime
* of the tree accordingly.
@@ -2683,6 +2727,7 @@ void __elv_ioq_slice_expired(struct request_queue *q, struct io_queue *ioq)
elv_clear_ioq_wait_request(ioq);
elv_clear_ioq_wait_busy(ioq);
elv_clear_ioq_wait_busy_done(ioq);
+ elv_clear_ioq_must_expire(ioq);

/*
* if ioq->slice_end = 0, that means a queue was expired before first
@@ -2821,16 +2866,18 @@ static int elv_should_preempt(struct request_queue *q, struct io_queue *new_ioq,
static void elv_preempt_queue(struct request_queue *q, struct io_queue *ioq)
{
elv_log_ioq(&q->elevator->efqd, ioq, "preempt");
- elv_ioq_slice_expired(q);
+ if (elv_iosched_expire_ioq(q, 0, 1)) {
+ elv_ioq_slice_expired(q);

- /*
- * Put the new queue at the front of the of the current list,
- * so we know that it will be selected next.
- */
+ /*
+ * Put the new queue at the front of the of the current list,
+ * so we know that it will be selected next.
+ */

- elv_activate_ioq(ioq, 1);
- ioq->slice_end = 0;
- elv_mark_ioq_slice_new(ioq);
+ elv_activate_ioq(ioq, 1);
+ ioq->slice_end = 0;
+ elv_mark_ioq_slice_new(ioq);
+ }
}

void elv_ioq_request_add(struct request_queue *q, struct request *rq)
@@ -3035,6 +3082,8 @@ void *elv_fq_select_ioq(struct request_queue *q, int force)
struct elv_fq_data *efqd = &q->elevator->efqd;
struct io_queue *new_ioq = NULL, *ioq = elv_active_ioq(q->elevator);
struct io_group *iog;
+ struct elevator_type *e = q->elevator->elevator_type;
+ int slice_expired = 1;

if (!elv_nr_busy_ioq(q->elevator))
return NULL;
@@ -3053,6 +3102,10 @@ void *elv_fq_select_ioq(struct request_queue *q, int force)
goto expire;
}

+ /* This queue has been marked for expiry. Try to expire it */
+ if (elv_ioq_must_expire(ioq))
+ goto expire;
+
/*
* If there is only root group present, don't expire the queue for
* single queue ioschedulers (noop, deadline, AS). It is unnecessary
@@ -3142,8 +3195,10 @@ void *elv_fq_select_ioq(struct request_queue *q, int force)
goto keep_queue;
}

+ slice_expired = 0;
expire:
- if (efqd->fairness >= 2 && !force && ioq && ioq->dispatched) {
+ if (efqd->fairness >= 2 && !force && ioq && ioq->dispatched
+ && strcmp(e->elevator_name, "anticipatory")) {
/*
* If there are request dispatched from this queue, don't
* dispatch requests from new queue till all the requests from
@@ -3154,6 +3209,11 @@ expire:
*
* Set ioq = NULL so that no more requests are dispatched from
* this queue.
+ *
+ * Note: Anticipatory already has the behavior where queue
+ * switch is not allowed until requests from previous queue
+ * have finished. Hence we don't have to get into this loop
+ * in case of AS.
*/
elv_log_ioq(efqd, ioq, "select: wait for requests to finish"
" disp=%lu", ioq->dispatched);
@@ -3161,7 +3221,14 @@ expire:
goto keep_queue;
}

- elv_ioq_slice_expired(q);
+ if (elv_iosched_expire_ioq(q, slice_expired, force))
+ elv_ioq_slice_expired(q);
+ else
+ /*
+ * Not making ioq = NULL, as AS can deny queue expiration and
+ * continue to dispatch from same queue
+ */
+ goto keep_queue;
new_queue:
ioq = elv_set_active_ioq(q, new_ioq);
keep_queue:
@@ -3298,7 +3365,8 @@ void elv_ioq_completed_request(struct request_queue *q, struct request *rq)
}

if (elv_ioq_class_idle(ioq)) {
- elv_ioq_slice_expired(q);
+ if (elv_iosched_expire_ioq(q, 1, 0))
+ elv_ioq_slice_expired(q);
goto done;
}

@@ -3343,7 +3411,8 @@ void elv_ioq_completed_request(struct request_queue *q, struct request *rq)
goto done;

/* Expire the queue */
- elv_ioq_slice_expired(q);
+ if (elv_iosched_expire_ioq(q, 1, 0))
+ elv_ioq_slice_expired(q);
}
} else if (!ioq->nr_queued && !elv_close_cooperator(q, ioq, 1)
&& sync && (!rq_noidle(rq) || efqd->fairness))
diff --git a/block/elevator-fq.h b/block/elevator-fq.h
index baa6cee..c117d40 100644
--- a/block/elevator-fq.h
+++ b/block/elevator-fq.h
@@ -371,6 +371,8 @@ enum elv_queue_state_flags {
ELV_QUEUE_FLAG_slice_new, /* no requests dispatched in slice */
ELV_QUEUE_FLAG_wait_busy, /* wait for this queue to get busy */
ELV_QUEUE_FLAG_wait_busy_done, /* Have already waited on this queue*/
+ ELV_QUEUE_FLAG_must_expire, /* Expire this queue even if it has
+ * request and time slice left */
};

#define ELV_IO_QUEUE_FLAG_FNS(name) \
@@ -395,6 +397,7 @@ ELV_IO_QUEUE_FLAG_FNS(idle_window)
ELV_IO_QUEUE_FLAG_FNS(slice_new)
ELV_IO_QUEUE_FLAG_FNS(wait_busy)
ELV_IO_QUEUE_FLAG_FNS(wait_busy_done)
+ELV_IO_QUEUE_FLAG_FNS(must_expire)

static inline struct io_service_tree *
io_entity_service_tree(struct io_entity *entity)
diff --git a/include/linux/elevator.h b/include/linux/elevator.h
index 6d2c8db..dda7951 100644
--- a/include/linux/elevator.h
+++ b/include/linux/elevator.h
@@ -42,6 +42,7 @@ typedef int (elevator_update_idle_window_fn) (struct elevator_queue*, void*,
struct request*);
typedef struct io_queue* (elevator_close_cooperator_fn) (struct request_queue*,
void*, int probe);
+typedef int (elevator_expire_ioq_fn) (struct request_queue*, void *, int, int);
#endif

struct elevator_ops
@@ -81,6 +82,7 @@ struct elevator_ops
elevator_should_preempt_fn *elevator_should_preempt_fn;
elevator_update_idle_window_fn *elevator_update_idle_window_fn;
elevator_close_cooperator_fn *elevator_close_cooperator_fn;
+ elevator_expire_ioq_fn *elevator_expire_ioq_fn;
#endif
};

--
1.6.0.6