Integrated IO controller for buffered+direct writes

Disclaimer: this code has a lot of rough edges and assumes a simple storage. It's mainly to serve as a proof of concept and focuses on getting the basic control algorithm out. It's generally working for pure/mixed buffered/direct writes, except that it still assumes the direct writes, if there are any, are aggressive ones. The exploration stops here since I see no obvious way for this scheme to support hierarchical cgroups.

Test results can be found in

https://github.com/fengguang/io-controller-tests/blob/master/log/

The key ideas and comments can be found in two functions in the patch:
- cfq_scale_slice()
- blkcg_update_dirty_ratelimit()
The other changes are mainly supporting bits.

It adapts the existing interfaces
- blkio.throttle.write_bps_device
- blkio.weight
from the semantics "for direct IO" to "for direct+buffered IO" (it now handles write IO only, but should be trivial to cover reads). It tries to do 1:1 split of direct:buffered writes inside the cgroup which essentially implements intra-cgroup proportional weights.

---
 block/blk-cgroup.c                    |   19 ++-
 block/blk-throttle.c                  |    2 +-
 block/cfq-iosched.c                   |   42 ++++-
 block/cfq.h                           |    2 +-
 fs/direct-io.c                        |    9 +
 include/linux/backing-dev.h           |   13 ++
 {block => include/linux}/blk-cgroup.h |   76 +++++++-
 include/trace/events/writeback.h      |   88 ++++++++-
 mm/backing-dev.c                      |    2 +
 mm/filemap.c                          |    1 +
 mm/page-writeback.c                   |  369 +++++++++++++++++++++++++++++++--
 11 files changed, 588 insertions(+), 35 deletions(-)
 rename {block => include/linux}/blk-cgroup.h (87%)

index 126c341..56cb330 100644
@@ -17,7 +17,7 @@
 #include <linux/err.h>
 #include <linux/blkdev.h>
 #include <linux/slab.h>
-#include "blk-cgroup.h"
+#include <linux/blk-cgroup.h>
 #include <linux/genhd.h>
 
 #define MAX_KEY_LEN 100

@@ -25,7 +25,11 @@
 static DEFINE_SPINLOCK(blkio_list_lock);
 static LIST_HEAD(blkio_list);
 
-struct blkio_cgroup blkio_root_cgroup = { .weight = 2*BLKIO_WEIGHT_DEFAULT };
+struct blkio_cgroup blkio_root_cgroup =
+{
+	.weight = 2*BLKIO_WEIGHT_DEFAULT,
+	.dio_weight = 2*BLKIO_WEIGHT_DEFAULT,
+};
 EXPORT_SYMBOL_GPL(blkio_root_cgroup);
 
 /* for encoding cft->private value on file */

@@ -1302,6 +1306,7 @@ static int blkio_weight_write(struct blkio_cgroup *blkcg, u64 val)
 	spin_lock(&blkio_list_lock);
 	spin_lock_irq(&blkcg->lock);
 	blkcg->weight = (unsigned int)val;
+	blkcg->dio_weight = (unsigned int)val;
 
 	hlist_for_each_entry(blkg, n, &blkcg->blkg_list, blkcg_node) {
 		pn = blkio_policy_search_node(blkcg, blkg->dev,

@@ -1564,6 +1569,8 @@ static void blkiocg_destroy(struct cgroup *cgroup)
 
 	free_css_id(&blkio_subsys, &blkcg->css);
 	rcu_read_unlock();
+	percpu_counter_destroy(&blkcg->nr_dirtied);
+	percpu_counter_destroy(&blkcg->nr_direct_write);
 	if (blkcg != &blkio_root_cgroup)
 		kfree(blkcg);
 }

@@ -1583,11 +1590,19 @@ static struct cgroup_subsys_state *blkiocg_create(struct cgroup *cgroup)
 		return ERR_PTR(-ENOMEM);
 
 	blkcg->weight = BLKIO_WEIGHT_DEFAULT;
+	blkcg->dio_weight = BLKIO_WEIGHT_DEFAULT;
+	blkcg->dirty_ratelimit = (100 << (20 - PAGE_SHIFT));
+	blkcg->balanced_dirty_ratelimit = (100 << (20 - PAGE_SHIFT));
+	blkcg->recent_dirtied_error = 1 << BLKCG_DIRTY_ERROR_SHIFT;
 done:
 	spin_lock_init(&blkcg->lock);
 	INIT_HLIST_HEAD(&blkcg->blkg_list);
 
 	INIT_LIST_HEAD(&blkcg->policy_list);
+
+	percpu_counter_init(&blkcg->nr_dirtied, 0);
+	percpu_counter_init(&blkcg->nr_direct_write, 0);
+
 	return &blkcg->css;
 }
 

index f2ddb94..f004ccc 100644
@@ -9,7 +9,7 @@
 #include <linux/blkdev.h>
 #include <linux/bio.h>
 #include <linux/blktrace_api.h>
-#include "blk-cgroup.h"
+#include <linux/blk-cgroup.h>
 #include "blk.h"
 
 /* Max dispatch from a group in 1 round */

index 2a15592..e322f33 100644
@@ -1,6 +1,6 @@
 #ifndef _CFQ_H
 #define _CFQ_H
-#include "blk-cgroup.h"
+#include <linux/blk-cgroup.h>
 
 #ifdef CONFIG_CFQ_GROUP_IOSCHED
 static inline void cfq_blkiocg_update_io_add_stats(struct blkio_group *blkg,

index f4aadd1..e85e4da 100644
@@ -37,6 +37,7 @@
 #include <linux/uio.h>
 #include <linux/atomic.h>
 #include <linux/prefetch.h>
+#include <linux/blk-cgroup.h>
 
 /*
  * How many user pages to map in one call to get_user_pages().  This determines

@@ -766,10 +767,18 @@ submit_page_section(struct dio *dio, struct dio_submit *sdio, struct page *page,
 	int ret = 0;
 
 	if (dio->rw & WRITE) {
+#ifdef CONFIG_BLK_DEV_THROTTLING
+		struct blkio_cgroup *blkcg = task_blkio_cgroup(current);
+		if (blkcg)
+			__percpu_counter_add(&blkcg->nr_direct_write, len,
+					     BDI_STAT_BATCH);
+#endif
 		/*
 		 * Read accounting is performed in submit_bio()
 		 */
 		task_io_account_write(len);
+		add_bdi_stat(dio->inode->i_mapping->backing_dev_info,
+			     BDI_DIRECT_WRITE, len);
 	}
 
 	/*

index b1038bd..55bb537 100644
@@ -42,6 +42,7 @@ enum bdi_stat_item {
 	BDI_WRITEBACK,
 	BDI_DIRTIED,
 	BDI_WRITTEN,
+	BDI_DIRECT_WRITE,
 	NR_BDI_STAT_ITEMS
 };
 

@@ -79,6 +80,8 @@ struct backing_dev_info {
 	unsigned long written_stamp;	/* pages written at bw_time_stamp */
 	unsigned long write_bandwidth;	/* the estimated write bandwidth */
 	unsigned long avg_write_bandwidth; /* further smoothed write bw */
+	unsigned long direct_write_stamp;
+	unsigned long direct_write_bandwidth;
 
 	/*
 	 * The base dirty throttle rate, re-calculated on every 200ms.

@@ -144,6 +147,16 @@ static inline void __add_bdi_stat(struct backing_dev_info *bdi,
 	__percpu_counter_add(&bdi->bdi_stat[item], amount, BDI_STAT_BATCH);
 }
 
+static inline void add_bdi_stat(struct backing_dev_info *bdi,
+		enum bdi_stat_item item, s64 amount)
+{
+	unsigned long flags;
+
+	local_irq_save(flags);
+	__add_bdi_stat(bdi, item, amount);
+	local_irq_restore(flags);
+}
+
 static inline void __inc_bdi_stat(struct backing_dev_info *bdi,
 		enum bdi_stat_item item)
 {

index dd8e2aa..b623358 100644
@@ -99,6 +99,7 @@ static int bdi_debug_stats_show(struct seq_file *m, void *v)
 		   "BackgroundThresh:   %10lu kB\n"
 		   "BdiDirtied:         %10lu kB\n"
 		   "BdiWritten:         %10lu kB\n"
+		   "BdiDirectWrite:     %10lu kB\n"
 		   "BdiWriteBandwidth:  %10lu kBps\n"
 		   "b_dirty:            %10lu\n"
 		   "b_io:               %10lu\n"

@@ -112,6 +113,7 @@ static int bdi_debug_stats_show(struct seq_file *m, void *v)
 		   K(background_thresh),
 		   (unsigned long) K(bdi_stat(bdi, BDI_DIRTIED)),
 		   (unsigned long) K(bdi_stat(bdi, BDI_WRITTEN)),
+		   (unsigned long) K(bdi_stat(bdi, BDI_DIRECT_WRITE)),
 		   (unsigned long) K(bdi->write_bandwidth),
 		   nr_dirty,
 		   nr_io,

index 79c4b2b..a945b71 100644
@@ -2294,6 +2294,7 @@ generic_file_direct_write(struct kiocb *iocb, const struct iovec *iov,
 	}
 
 	written = mapping->a_ops->direct_IO(WRITE, iocb, iov, pos, *nr_segs);
+	inc_bdi_stat(mapping->backing_dev_info, BDI_DIRECT_WRITE);
 
 	/*
 	 * Finally, try again to invalidate clean pages which might have been

1.7.9.1

On Thu, Apr 19, 2012 at 01:28:11PM +0800, Fengguang Wu wrote:
[..]

Hey, if you can explain in few lines the design and what's the objective its much easier to understand then going through the patch and first trying to understand the internals of writeback.

Regarding upper limit (blkio.throttle_write_bps_device) thre are only two problems with doing it a device layer.

- We lose context information for buffered writes.
- This can be solved by per inode cgroup association.

- Or solve it by throttling writer synchronously in balance_dirty_pages(). I had done that by exporting a hook from blk-throttle so that writeback layer does not have to worry about all the details.

- Filesystems can get seriliazed.
- This needs to be solved by filesystems.

- Or again, invoke blk-throttle hook from balance_dirty_pages. It will solve the problem for buffered writes but direct writes will still have filesystem serialization issue. So it needs to be solved by filesystems anyway.

- Throttling for network file systems.
- This would be the only advantage or implementing things at higher layer so that we don't have to build special knowledge of throttling in lower layers.

So which of the above problem you are exactly solving by throttling by writes in writeback layer and why exporting a throttling hook from blk-throttle to balance_drity_pages()is not a good idea?

Thanks
Vivek

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

The main objective is to keep the current buffered IO path untouched and keep a single pool of dirty/writeback pages and single async IO queue.

The basic balance_dirty_pages() work model is to split the total writeout bandwidth equally to N dirtier tasks, where N is re-estimated on every 200ms.

        bdi->dirty_ratelimit = bdi->write_bandwidth / N
        task_ratelimit = bdi->dirty_ratelimit   # ignoring dirty position control for simplicity

To support blkcg, the new formula is

        bdi->dirty_ratelimit = bdi->write_bandwidth / N
        blkcg->dirty_ratelimit = bdi->dirty_ratelimit
        task_ratelimit = blkcg->dirty_ratelimit / M

where N is the number of cgroups, M is the number of dirtier tasks inside each cgroup.

To support proportional async and dio weights, the formula is expanded to

        bdi->dirty_ratelimit = (bdi->write_bandwidth +
                                bdi->direct_write_bandwidth) / N
        blkcg->dirty_ratelimit = bdi->dirty_ratelimit / P
        task_ratelimit = blkcg->dirty_ratelimit / M

where P=2 when there are both aggressive async/dio IOs inside that cgroup, P=1 when there are only aggressive async IOs.

balance_dirty_pages() will do dirty throttling when dirty pages enter the page cache. It also splits up blkcg->weight into dio_weight and async_weight for use by cfq.

cfq will continue to do proportional weight throttling:
- dio goes to each cgroup
- all async writeout carried out in the root cgroup

dirty time

  cgroup1                 cgroup2                 cgroup3
  +---------+---------+   +-------------------+   +-------------------+
  |  async  |   dio   |   |       async       |   |        dio        |
  +---------+---------+   +-------------------+   +-------------------+

250 250 500 500

writeout time

  root cgroup                       cgroup1       cgroup3
  +---------+-------------------+   +---------+   +-------------------+
  |  async          async       |   |   dio   |   |        dio        |
  +---------+-------------------+   +---------+   +-------------------+

750 250 500

In the above example, the async weights for cgroup1 and cgroup2 will be added up and allocated to the root cgroup, so the flusher will get half total disk time. Assume a 150MB/s disk and equal cost for async/dio IOs, the above cfq weights will yield

        bdi->write_bandwidth = 75
        blkcg1->dio_rate = 25
        blkcg2->dio_rate = 50
        bdi->direct_write_bandwidth = sum(dio_rate) = 75

balance_dirty_pages() will detect out N=3 cgroups doing active IO, and yield

        bdi->dirty_ratelimit = (bdi->write_bandwidth +
                                bdi->direct_write_bandwidth) / N
                             = 50

For cgroup1, it detects both aggressive async/dio IOs, so assigns half bandwidth to the dirtier tasks inside cgroup1:

        blkcg1->dirty_ratelimit = bdi->dirty_ratelimit / 2
                                = 25

For cgroup2, it detects only aggressive async IOs, so assign full bandwidth to the dirtier tasks inside cgroup2:

        blkcg2->dirty_ratelimit = bdi->dirty_ratelimit
                                = 50

In the end, balance_dirty_pages() will throttle dirty rates to 25+50 MB/s for cgroup1+cgroup2, and cfq will give 250+500 weights to the flusher, yielding 25+75 MB/s writeout bandwidth. So the two ends meet nicely.

Agreed.

Agreed.

Yeah here is the gap.

I'm fine with adding a blk-throttle hook in balance_drity_pages(). The current dirty throttling algorithms can work just fine with it. And this feature should serve the majority users well.

I'll remove the blkio.throttle.write_bps_device support from this patchset. It's not complete in the current form, after all.

However as a user, I do feel it much easier to specify one single per-cgroup limit rather than breaking it down to per-device limits. There is also the obvious need to do per-bdi limits on software RAID, btrfs, NFS, CIFS, fuse, etc.

So if there come such user requests where your blk-throttle runs short, I'd be glad to do an up limit IO controller in high layer :-)

The sweet thing is, the two up limit IO controllers will be able to live with each other peacefully and freely selectable by the user:

- "0:0 bw" enables high layer per-cgroup throttling
- "bdi_maj:bdi_min bw" enables high layer per-cgroup-per-bdi throttling
- "dev_maj:dev_min bw" enables block layer throttling

The implementation will be very similar to this prototype:

buffered write IO controller in balance_dirty_pages()
https://lkml.org/lkml/2012/3/28/275

It's pretty simple (in code size), yet powerful enough to distribute total bandwidth limit equally to all IO tasks, whether they are doing buffered or direct IO.

It will need to insert calls to a stripped down balance_dirty_pages() in the readahead and direct IO paths. The async IO will need some more code to delay the IO completion notifications.

Thanks,
Fengguang

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

The main objective is to keep the current buffered IO path untouched and keep a single pool of dirty/writeback pages and single async IO queue.

The basic balance_dirty_pages() work model is to split the total writeout bandwidth equally to N dirtier tasks, where N is re-estimated on every 200ms.

        bdi->dirty_ratelimit = bdi->write_bandwidth / N
        task_ratelimit = bdi->dirty_ratelimit   # ignoring dirty position control for simplicity

To support blkcg, the new formula is

        bdi->dirty_ratelimit = bdi->write_bandwidth / N
        blkcg->dirty_ratelimit = bdi->dirty_ratelimit
        task_ratelimit = blkcg->dirty_ratelimit / M

where N is the number of cgroups, M is the number of dirtier tasks inside each cgroup.

To support proportional async and dio weights, the formula is expanded to

        bdi->dirty_ratelimit = (bdi->write_bandwidth +
                                bdi->direct_write_bandwidth) / N
        blkcg->dirty_ratelimit = bdi->dirty_ratelimit / P
        task_ratelimit = blkcg->dirty_ratelimit / M

where P=2 when there are both aggressive async/dio IOs inside that cgroup, P=1 when there are only aggressive async IOs.

balance_dirty_pages() will do dirty throttling when dirty pages enter the page cache. It also splits up blkcg->weight into dio_weight and async_weight for use by cfq.

cfq will continue to do proportional weight throttling:
- dio goes to each cgroup
- all async writeout carried out in the root cgroup

dirty time

  cgroup1                 cgroup2                 cgroup3
  +---------+---------+   +-------------------+   +-------------------+
  |  async  |   dio   |   |       async       |   |        dio        |
  +---------+---------+   +-------------------+   +-------------------+

250 250 500 500

writeout time

  root cgroup                       cgroup1       cgroup3
  +---------+-------------------+   +---------+   +-------------------+
  |  async          async       |   |   dio   |   |        dio        |
  +---------+-------------------+   +---------+   +-------------------+

750 250 500

In the above example, the async weights for cgroup1 and cgroup2 will be added up and allocated to the root cgroup, so the flusher will get half total disk time. Assume a 150MB/s disk and equal cost for async/dio IOs, the above cfq weights will yield

        bdi->write_bandwidth = 75
        blkcg1->dio_rate = 25
        blkcg2->dio_rate = 50
        bdi->direct_write_bandwidth = sum(dio_rate) = 75

balance_dirty_pages() will detect out N=3 cgroups doing active IO, and yield

        bdi->dirty_ratelimit = (bdi->write_bandwidth +
                                bdi->direct_write_bandwidth) / N
                             = 50

For cgroup1, it detects both aggressive async/dio IOs, so assigns half bandwidth to the dirtier tasks inside cgroup1:

        blkcg1->dirty_ratelimit = bdi->dirty_ratelimit / 2
                                = 25

For cgroup2, it detects only aggressive async IOs, so assign full bandwidth to the dirtier tasks inside cgroup2:

        blkcg2->dirty_ratelimit = bdi->dirty_ratelimit
                                = 50

In the end, balance_dirty_pages() will throttle dirty rates to 25+50 MB/s for cgroup1+cgroup2, and cfq will give 250+500 weights to the flusher, yielding 25+75 MB/s writeout bandwidth. So the two ends meet nicely.

Agreed.

Agreed.

Yeah here is the gap.

I'm fine with adding a blk-throttle hook in balance_drity_pages(). The current dirty throttling algorithms can work just fine with it. And this feature should serve the majority users well.

I'll remove the blkio.throttle.write_bps_device support from this patchset. It's not complete in the current form, after all.

However as a user, I do feel it much easier to specify one single per-cgroup limit rather than breaking it down to per-device limits. There is also the obvious need to do per-bdi limits on software RAID, btrfs, NFS, CIFS, fuse, etc.

So if there come such user requests where your blk-throttle runs short, I'd be glad to do an up limit IO controller in high layer :-)

The sweet thing is, the two up limit IO controllers will be able to live with each other peacefully and freely selectable by the user:

- "0:0 bw" enables high layer per-cgroup throttling
- "bdi_maj:bdi_min bw" enables high layer per-cgroup-per-bdi throttling
- "dev_maj:dev_min bw" enables block layer throttling

The implementation will be very similar to this prototype:

buffered write IO controller in balance_dirty_pages()
https://lkml.org/lkml/2012/3/28/275

It's pretty simple (in code size), yet powerful enough to distribute total bandwidth limit equally to all IO tasks, whether they are doing buffered or direct IO.

It will need to insert calls to a stripped down balance_dirty_pages() in the readahead and direct IO paths. The async IO will need some more code to delay the IO completion notifications.

Thanks,
Fengguang

On Thu, Apr 19, 2012 at 01:28:11PM +0800, Fengguang Wu wrote:
[..]

Hey, if you can explain in few lines the design and what's the objective its much easier to understand then going through the patch and first trying to understand the internals of writeback.

Regarding upper limit (blkio.throttle_write_bps_device) thre are only two problems with doing it a device layer.

- We lose context information for buffered writes.
- This can be solved by per inode cgroup association.

- Or solve it by throttling writer synchronously in balance_dirty_pages(). I had done that by exporting a hook from blk-throttle so that writeback layer does not have to worry about all the details.

- Filesystems can get seriliazed.
- This needs to be solved by filesystems.

- Or again, invoke blk-throttle hook from balance_dirty_pages. It will solve the problem for buffered writes but direct writes will still have filesystem serialization issue. So it needs to be solved by filesystems anyway.

- Throttling for network file systems.
- This would be the only advantage or implementing things at higher layer so that we don't have to build special knowledge of throttling in lower layers.

So which of the above problem you are exactly solving by throttling by writes in writeback layer and why exporting a throttling hook from blk-throttle to balance_drity_pages()is not a good idea?

Thanks
Vivek