[PATCH 0/7] [RFC] iosched: make a difference between read/readahead requests

[PATCH 0/7] [RFC] iosched: make a difference between read/readahead requests

[Fengguang Wu]

Hi Jens,

This patchset does two jobs:
	1) do io schedule differently on READ/READA requests.
		- to help improve I/O latency and throughput
	2) do notification/action on READA => READ events
		- to make the elevators better informed
		- to prevent the priority inversion problem
		- also brings some CPU overheads*
(*) I'm not able to provide numbers at the moment.
    Our server is not up for testing these days. But sure will for the next time.


The patches come in two groups:

1) explicitly schedule READA requests
Note: currently only the deadline elevator is touched.

[PATCH 1/7] iosched: introduce WRITEA                                                  
[PATCH 2/7] iosched: introduce parameter deadline.reada_expire                         
[PATCH 3/7] iosched: introduce deadline_add_drq_fifo()                                 
[PATCH 4/7] iosched: submit READA requests on possible readahead code path             

2) notify/act on pending reads
Naming issue: how about pending_read/need_page/... for kick_page?

[PATCH 5/7] iosched: introduce elv_kick_page()                                         
[PATCH 6/7] iosched: run elv_kick_page() on sync read                                  
[PATCH 7/7] iosched: introduce deadline_kick_page()                                    

Most overheads should be in functions deadline_kick_page() and
deadline_add_drq_fifo(). I'll explore the details later.

Any comments are welcome, thanks.

Fengguang Wu
--
Dept. Automation                University of Science and Technology of China

[PATCH 1/7] iosched: introduce WRITEA

[Fengguang Wu]

[-- Attachment #1: iosched-reada-redef.patch --]
[-- Type: text/plain, Size: 911 bytes --]

Introduce WRITEA as 3, and redefine SWRITE as 5.

I'm not sure if WRITEA will ever be used, though it would be better to
redefine SWRITE to avoid possible conflict with BIO_RW_AHEAD.

Signed-off-by: Wu Fengguang <wfg@mail.ustc.edu.cn>
---


--- linux-2.6.17-rc6-mm2.orig/include/linux/fs.h
+++ linux-2.6.17-rc6-mm2/include/linux/fs.h
@@ -74,8 +74,9 @@ extern int dir_notify_enable;
 #define READ 0
 #define WRITE 1
 #define READA 2		/* read-ahead  - don't block if no resources */
-#define SWRITE 3	/* for ll_rw_block() - wait for buffer lock */
+#define WRITEA 3	/* write-ahead - don't block if no resources */
 #define SPECIAL 4	/* For non-blockdevice requests in request queue */
+#define SWRITE 5	/* for ll_rw_block() - wait for buffer lock */
 #define READ_SYNC	(READ | (1 << BIO_RW_SYNC))
 #define WRITE_SYNC	(WRITE | (1 << BIO_RW_SYNC))
 #define WRITE_BARRIER	((1 << BIO_RW) | (1 << BIO_RW_BARRIER))

--

[PATCH 4/7] iosched: submit READA requests on possible readahead code path

[Fengguang Wu]

[-- Attachment #1: iosched-submit-reada-on-possible-readahead-path.patch --]
[-- Type: text/plain, Size: 2119 bytes --]

Change the request type from READ to READA in possible readahead code paths.

- call mpage_bio_submit(READA) in mpage_readpages()
- call submit_bio(READA) in swap_readpage()

Signed-off-by: Wu Fengguang <wfg@mail.ustc.edu.cn>
---


 fs/mpage.c |   12 ++++++------
 1 files changed, 6 insertions(+), 6 deletions(-)

--- linux-2.6.17-mm1.orig/fs/mpage.c
+++ linux-2.6.17-mm1/fs/mpage.c
@@ -302,7 +302,7 @@ do_mpage_readpage(struct bio *bio, struc
 	 * This page will go to BIO.  Do we need to send this BIO off first?
 	 */
 	if (bio && (*last_block_in_bio != blocks[0] - 1))
-		bio = mpage_bio_submit(READ, bio);
+		bio = mpage_bio_submit(READA, bio);
 
 alloc_new:
 	if (bio == NULL) {
@@ -315,12 +315,12 @@ alloc_new:
 
 	length = first_hole << blkbits;
 	if (bio_add_page(bio, page, length, 0) < length) {
-		bio = mpage_bio_submit(READ, bio);
+		bio = mpage_bio_submit(READA, bio);
 		goto alloc_new;
 	}
 
 	if (buffer_boundary(map_bh) || (first_hole != blocks_per_page))
-		bio = mpage_bio_submit(READ, bio);
+		bio = mpage_bio_submit(READA, bio);
 	else
 		*last_block_in_bio = blocks[blocks_per_page - 1];
 out:
@@ -328,7 +328,7 @@ out:
 
 confused:
 	if (bio)
-		bio = mpage_bio_submit(READ, bio);
+		bio = mpage_bio_submit(READA, bio);
 	if (!PageUptodate(page))
 	        block_read_full_page(page, get_block);
 	else
@@ -418,7 +418,7 @@ mpage_readpages(struct address_space *ma
 	pagevec_lru_add(&lru_pvec);
 	BUG_ON(!list_empty(pages));
 	if (bio)
-		mpage_bio_submit(READ, bio);
+		mpage_bio_submit(READA, bio);
 	return 0;
 }
 EXPORT_SYMBOL(mpage_readpages);
@@ -437,7 +437,7 @@ int mpage_readpage(struct page *page, ge
 	bio = do_mpage_readpage(bio, page, 1, &last_block_in_bio,
 			&map_bh, &first_logical_block, get_block);
 	if (bio)
-		mpage_bio_submit(READ, bio);
+		mpage_bio_submit(READA, bio);
 	return 0;
 }
 EXPORT_SYMBOL(mpage_readpage);
--- linux-2.6.17-mm1.orig/mm/page_io.c
+++ linux-2.6.17-mm1/mm/page_io.c
@@ -124,7 +124,7 @@ int swap_readpage(struct file *file, str
 		goto out;
 	}
 	inc_page_state(pswpin);
-	submit_bio(READ, bio);
+	submit_bio(READA, bio);
 out:
 	return ret;
 }

--

[PATCH 5/7] iosched: introduce elv_kick_page()

[Fengguang Wu]

[-- Attachment #1: iosched-kick-page-elevator.patch --]
[-- Type: text/plain, Size: 2416 bytes --]

Introduce elv_kick_page() to turn a possibly READA request into READ.
The underlying elevator_kick_page_fn() should also reschedule the request
if necessary.

Signed-off-by: Wu Fengguang <wfg@mail.ustc.edu.cn>
---


 block/ll_rw_blk.c        |    8 ++++++++
 fs/buffer.c              |    5 +++--
 include/linux/elevator.h |    2 ++
 3 files changed, 13 insertions(+), 2 deletions(-)

--- linux-2.6.17-rc5-mm3.orig/include/linux/elevator.h
+++ linux-2.6.17-rc5-mm3/include/linux/elevator.h
@@ -20,6 +20,7 @@ typedef int (elevator_set_req_fn) (reque
 typedef void (elevator_put_req_fn) (request_queue_t *, struct request *);
 typedef void (elevator_activate_req_fn) (request_queue_t *, struct request *);
 typedef void (elevator_deactivate_req_fn) (request_queue_t *, struct request *);
+typedef int (elevator_kick_page_fn) (request_queue_t *, struct page *);
 
 typedef int (elevator_init_fn) (request_queue_t *, elevator_t *);
 typedef void (elevator_exit_fn) (elevator_t *);
@@ -34,6 +35,7 @@ struct elevator_ops
 	elevator_add_req_fn *elevator_add_req_fn;
 	elevator_activate_req_fn *elevator_activate_req_fn;
 	elevator_deactivate_req_fn *elevator_deactivate_req_fn;
+	elevator_kick_page_fn *elevator_kick_page_fn;
 
 	elevator_queue_empty_fn *elevator_queue_empty_fn;
 	elevator_completed_req_fn *elevator_completed_req_fn;
@@ -91,6 +93,7 @@ extern void elv_dispatch_sort(request_qu
 extern void elv_add_request(request_queue_t *, struct request *, int, int);
 extern void __elv_add_request(request_queue_t *, struct request *, int, int);
 extern void elv_insert(request_queue_t *, struct request *, int);
+extern void elv_kick_page(request_queue_t *, struct page *);
 extern int elv_merge(request_queue_t *, struct request **, struct bio *);
 extern void elv_merge_requests(request_queue_t *, struct request *,
 			       struct request *);
--- linux-2.6.17-rc5-mm3.orig/block/elevator.c
+++ linux-2.6.17-rc5-mm3/block/elevator.c
@@ -468,6 +468,16 @@ void elv_add_request(request_queue_t *q,
 	spin_unlock_irqrestore(q->queue_lock, flags);
 }
 
+void elv_kick_page(request_queue_t *q, struct page *page)
+{
+	if (page && q->elevator && q->elevator->ops->elevator_kick_page_fn) {
+		spin_lock_irq(q->queue_lock);
+		q->elevator->ops->elevator_kick_page_fn(q, page);
+		spin_unlock_irq(q->queue_lock);
+	}
+
+}
+
 static inline struct request *__elv_next_request(request_queue_t *q)
 {
 	struct request *rq;

--

[PATCH 7/7] iosched: introduce deadline_kick_page()

[Fengguang Wu]

[-- Attachment #1: iosched-kick-page-deadline.patch --]
[-- Type: text/plain, Size: 1891 bytes --]

Introduce deadline_kick_page() to
	- find the request containing the page
	- remove its BIO_RW_AHEAD flag
	- reschedule if it was of type READA

Signed-off-by: Wu Fengguang <wfg@mail.ustc.edu.cn>
---


 block/deadline-iosched.c |   45 +++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 43 insertions(+), 2 deletions(-)

--- linux-2.6.17-rc6-mm2.orig/block/deadline-iosched.c
+++ linux-2.6.17-rc6-mm2/block/deadline-iosched.c
@@ -317,6 +317,44 @@ deadline_add_request(struct request_queu
 }
 
 /*
+ * We have a pending read on @page,
+ * find the corresponding request of type READA,
+ * promote it to READ, and reschedule it.
+ */
+static int
+deadline_kick_page(struct request_queue *q, struct page *page)
+{
+	struct deadline_data *dd = q->elevator->elevator_data;
+	struct deadline_rq *drq;
+	struct request *rq;
+	struct list_head *pos;
+	struct bio_vec *bvec;
+	struct bio *bio;
+	int i;
+
+	list_for_each(pos, &dd->fifo_list[READ]) {
+		drq = list_entry_fifo(pos);
+		rq = drq->request;
+		if (rq->flags & (1 << BIO_RW_AHEAD)) {
+			rq_for_each_bio(bio, rq) {
+				bio_for_each_segment(bvec, bio, i) {
+					if (page == bvec->bv_page)
+						goto found;
+				}
+			}
+		}
+	}
+
+	return -1;
+
+found:
+	rq->flags &= ~(1 << BIO_RW_AHEAD);
+	list_del(&drq->fifo);
+	deadline_add_drq_fifo(dd, rq);
+	return 0;
+}
+
+/*
  * remove rq from rbtree, fifo, and hash
  */
 static void deadline_remove_request(request_queue_t *q, struct request *rq)
@@ -794,6 +832,7 @@ static struct elevator_type iosched_dead
 		.elevator_merge_req_fn =	deadline_merged_requests,
 		.elevator_dispatch_fn =		deadline_dispatch_requests,
 		.elevator_add_req_fn =		deadline_add_request,
+		.elevator_kick_page_fn =	deadline_kick_page,
 		.elevator_queue_empty_fn =	deadline_queue_empty,
 		.elevator_former_req_fn =	deadline_former_request,
 		.elevator_latter_req_fn =	deadline_latter_request,

--

Re: [PATCH 7/7] iosched: introduce deadline_kick_page()

[Jens Axboe]

On Sat, Jun 24 2006, Fengguang Wu wrote:
> Introduce deadline_kick_page() to
> 	- find the request containing the page
> 	- remove its BIO_RW_AHEAD flag
> 	- reschedule if it was of type READA
> 
> Signed-off-by: Wu Fengguang <wfg@mail.ustc.edu.cn>
> ---
> 
> 
>  block/deadline-iosched.c |   45 +++++++++++++++++++++++++++++++++++++++++++--
>  1 files changed, 43 insertions(+), 2 deletions(-)
> 
> --- linux-2.6.17-rc6-mm2.orig/block/deadline-iosched.c
> +++ linux-2.6.17-rc6-mm2/block/deadline-iosched.c
> @@ -317,6 +317,44 @@ deadline_add_request(struct request_queu
>  }
>  
>  /*
> + * We have a pending read on @page,
> + * find the corresponding request of type READA,
> + * promote it to READ, and reschedule it.
> + */
> +static int
> +deadline_kick_page(struct request_queue *q, struct page *page)
> +{
> +	struct deadline_data *dd = q->elevator->elevator_data;
> +	struct deadline_rq *drq;
> +	struct request *rq;
> +	struct list_head *pos;
> +	struct bio_vec *bvec;
> +	struct bio *bio;
> +	int i;
> +
> +	list_for_each(pos, &dd->fifo_list[READ]) {
> +		drq = list_entry_fifo(pos);
> +		rq = drq->request;
> +		if (rq->flags & (1 << BIO_RW_AHEAD)) {
> +			rq_for_each_bio(bio, rq) {
> +				bio_for_each_segment(bvec, bio, i) {
> +					if (page == bvec->bv_page)
> +						goto found;
> +				}
> +			}
> +		}
> +	}

Uh that's horrible!

Before we go into further details, I'd like to see some numbers on where
this makes a difference.

-- 
Jens Axboe

Re: [PATCH 7/7] iosched: introduce deadline_kick_page()

[Fengguang Wu]

On Sat, Jun 24, 2006 at 01:01:04PM +0200, Jens Axboe wrote:
> >  /*
> > + * We have a pending read on @page,
> > + * find the corresponding request of type READA,
> > + * promote it to READ, and reschedule it.
> > + */
> > +static int
> > +deadline_kick_page(struct request_queue *q, struct page *page)
> > +{
> > +	struct deadline_data *dd = q->elevator->elevator_data;
> > +	struct deadline_rq *drq;
> > +	struct request *rq;
> > +	struct list_head *pos;
> > +	struct bio_vec *bvec;
> > +	struct bio *bio;
> > +	int i;
> > +
> > +	list_for_each(pos, &dd->fifo_list[READ]) {
> > +		drq = list_entry_fifo(pos);
> > +		rq = drq->request;
> > +		if (rq->flags & (1 << BIO_RW_AHEAD)) {
> > +			rq_for_each_bio(bio, rq) {
> > +				bio_for_each_segment(bvec, bio, i) {
> > +					if (page == bvec->bv_page)
> > +						goto found;
> > +				}
> > +			}
> > +		}
> > +	}
> 
> Uh that's horrible!
> 
> Before we go into further details, I'd like to see some numbers on where
> this makes a difference.

Sorry, it is.  It brings non-trivial overhead.

This is the oprofile outputs:

reading small files:
 1245 c01edae4 9         0.1404  deadline_dispatch_requests
 1253 c01ed4d6 9         0.1404  deadline_queue_empty
 1338 c01ed3d5 8         0.1248  deadline_kick_page
 1619 c01ed350 6         0.0936  deadline_add_drq_fifo
 1707 c01eda62 5         0.0780  deadline_add_request
 1712 c01ed2e5 5         0.0780  deadline_set_request
 1867 c01ed871 4         0.0624  deadline_remove_request
 2242 c01ed9b9 2         0.0312  deadline_add_drq_rb
 2244 c01edc1e 2         0.0312  deadline_merge
 2246 c01ed923 2         0.0312  deadline_move_request
 2249 c01ed232 2         0.0312  deadline_put_request

reading a big file:
 1330 c01ed3d5 89        0.2926  deadline_kick_page
 2528 c01edae4 16        0.0526  deadline_dispatch_requests
 3036 c01ed9b9 8         0.0263  deadline_add_drq_rb
 3163 c01ed4d6 7         0.0230  deadline_queue_empty
 3394 c01edc1e 5         0.0164  deadline_merge
 3399 c01ed923 5         0.0164  deadline_move_request
 3403 c01ed2e5 5         0.0164  deadline_set_request
 3707 c01eda62 3         0.0099  deadline_add_request
 3711 c01ed871 3         0.0099  deadline_remove_request
 3917 c01ede3c 2         0.0066  deadline_merged_request
 3920 c01ed232 2         0.0066  deadline_put_request
 4214 c01ed350 1         0.0033  deadline_add_drq_fifo

The overhead of deadline_kick_page() becomes large when the request is
large (256 pages). But I guess there's way to optimize it:
- most requests will be consisted of a set of continuous pages, i.e. a
  range comparison will be sufficient.
- for a system with lots of queued requests(>100), maybe the gain can
  well pay for the overheads?

btw, some mails for this patchset did not return to me, perhaps my
mail system was broken after a previous crash... Sorry, I'll resend
them soon.

Thanks,
Wu

Re: [PATCH 7/7] iosched: introduce deadline_kick_page()

[Jens Axboe]

On Sun, Jun 25 2006, Fengguang Wu wrote:
> On Sat, Jun 24, 2006 at 01:01:04PM +0200, Jens Axboe wrote:
> > >  /*
> > > + * We have a pending read on @page,
> > > + * find the corresponding request of type READA,
> > > + * promote it to READ, and reschedule it.
> > > + */
> > > +static int
> > > +deadline_kick_page(struct request_queue *q, struct page *page)
> > > +{
> > > +	struct deadline_data *dd = q->elevator->elevator_data;
> > > +	struct deadline_rq *drq;
> > > +	struct request *rq;
> > > +	struct list_head *pos;
> > > +	struct bio_vec *bvec;
> > > +	struct bio *bio;
> > > +	int i;
> > > +
> > > +	list_for_each(pos, &dd->fifo_list[READ]) {
> > > +		drq = list_entry_fifo(pos);
> > > +		rq = drq->request;
> > > +		if (rq->flags & (1 << BIO_RW_AHEAD)) {
> > > +			rq_for_each_bio(bio, rq) {
> > > +				bio_for_each_segment(bvec, bio, i) {
> > > +					if (page == bvec->bv_page)
> > > +						goto found;
> > > +				}
> > > +			}
> > > +		}
> > > +	}
> > 
> > Uh that's horrible!
> > 
> > Before we go into further details, I'd like to see some numbers on where
> > this makes a difference.
> 
> Sorry, it is.  It brings non-trivial overhead.

Sorry for the late reply, apparently spamassassin thought this was
spam...

> This is the oprofile outputs:
> 
> reading small files:
>  1245 c01edae4 9         0.1404  deadline_dispatch_requests
>  1253 c01ed4d6 9         0.1404  deadline_queue_empty
>  1338 c01ed3d5 8         0.1248  deadline_kick_page
>  1619 c01ed350 6         0.0936  deadline_add_drq_fifo
>  1707 c01eda62 5         0.0780  deadline_add_request
>  1712 c01ed2e5 5         0.0780  deadline_set_request
>  1867 c01ed871 4         0.0624  deadline_remove_request
>  2242 c01ed9b9 2         0.0312  deadline_add_drq_rb
>  2244 c01edc1e 2         0.0312  deadline_merge
>  2246 c01ed923 2         0.0312  deadline_move_request
>  2249 c01ed232 2         0.0312  deadline_put_request
> 
> reading a big file:
>  1330 c01ed3d5 89        0.2926  deadline_kick_page
>  2528 c01edae4 16        0.0526  deadline_dispatch_requests
>  3036 c01ed9b9 8         0.0263  deadline_add_drq_rb
>  3163 c01ed4d6 7         0.0230  deadline_queue_empty
>  3394 c01edc1e 5         0.0164  deadline_merge
>  3399 c01ed923 5         0.0164  deadline_move_request
>  3403 c01ed2e5 5         0.0164  deadline_set_request
>  3707 c01eda62 3         0.0099  deadline_add_request
>  3711 c01ed871 3         0.0099  deadline_remove_request
>  3917 c01ede3c 2         0.0066  deadline_merged_request
>  3920 c01ed232 2         0.0066  deadline_put_request
>  4214 c01ed350 1         0.0033  deadline_add_drq_fifo
> 
> The overhead of deadline_kick_page() becomes large when the request is
> large (256 pages). But I guess there's way to optimize it:
> - most requests will be consisted of a set of continuous pages, i.e. a
>   range comparison will be sufficient.
> - for a system with lots of queued requests(>100), maybe the gain can
>   well pay for the overheads?

Sorry, there's just no way that something like that is acceptable for
inclusion. I don't care much about the overhead numbers (I can see from
the code that it sucks :-), I wanted to see some numbers on what
scenarios this helps performance and by how much.

-- 
Jens Axboe

Re: [PATCH 7/7] iosched: introduce deadline_kick_page()

[Fengguang Wu]

Jens,

On Wed, Jun 28, 2006 at 01:27:32PM +0200, Jens Axboe wrote:
> > The overhead of deadline_kick_page() becomes large when the request is
> > large (256 pages). But I guess there's way to optimize it:
> > - most requests will be consisted of a set of continuous pages, i.e. a
> >   range comparison will be sufficient.
> > - for a system with lots of queued requests(>100), maybe the gain can
> >   well pay for the overheads?
> 
> Sorry, there's just no way that something like that is acceptable for
> inclusion. I don't care much about the overhead numbers (I can see from
> the code that it sucks :-), I wanted to see some numbers on what
> scenarios this helps performance and by how much.

Ok, thanks. I hope that I'll be able to bring with some performance
numbers the next time :-)

Regards,
Wu

[PATCH 4/7] iosched: submit READA requests on possible readahead code path

[Fengguang Wu]

[-- Attachment #1: iosched-submit-reada-on-possible-readahead-path.patch --]
[-- Type: text/plain, Size: 2119 bytes --]

Change the request type from READ to READA in possible readahead code paths.

- call mpage_bio_submit(READA) in mpage_readpages()
- call submit_bio(READA) in swap_readpage()

Signed-off-by: Wu Fengguang <wfg@mail.ustc.edu.cn>
---


 fs/mpage.c |   12 ++++++------
 1 files changed, 6 insertions(+), 6 deletions(-)

--- linux-2.6.17-mm1.orig/fs/mpage.c
+++ linux-2.6.17-mm1/fs/mpage.c
@@ -302,7 +302,7 @@ do_mpage_readpage(struct bio *bio, struc
 	 * This page will go to BIO.  Do we need to send this BIO off first?
 	 */
 	if (bio && (*last_block_in_bio != blocks[0] - 1))
-		bio = mpage_bio_submit(READ, bio);
+		bio = mpage_bio_submit(READA, bio);
 
 alloc_new:
 	if (bio == NULL) {
@@ -315,12 +315,12 @@ alloc_new:
 
 	length = first_hole << blkbits;
 	if (bio_add_page(bio, page, length, 0) < length) {
-		bio = mpage_bio_submit(READ, bio);
+		bio = mpage_bio_submit(READA, bio);
 		goto alloc_new;
 	}
 
 	if (buffer_boundary(map_bh) || (first_hole != blocks_per_page))
-		bio = mpage_bio_submit(READ, bio);
+		bio = mpage_bio_submit(READA, bio);
 	else
 		*last_block_in_bio = blocks[blocks_per_page - 1];
 out:
@@ -328,7 +328,7 @@ out:
 
 confused:
 	if (bio)
-		bio = mpage_bio_submit(READ, bio);
+		bio = mpage_bio_submit(READA, bio);
 	if (!PageUptodate(page))
 	        block_read_full_page(page, get_block);
 	else
@@ -418,7 +418,7 @@ mpage_readpages(struct address_space *ma
 	pagevec_lru_add(&lru_pvec);
 	BUG_ON(!list_empty(pages));
 	if (bio)
-		mpage_bio_submit(READ, bio);
+		mpage_bio_submit(READA, bio);
 	return 0;
 }
 EXPORT_SYMBOL(mpage_readpages);
@@ -437,7 +437,7 @@ int mpage_readpage(struct page *page, ge
 	bio = do_mpage_readpage(bio, page, 1, &last_block_in_bio,
 			&map_bh, &first_logical_block, get_block);
 	if (bio)
-		mpage_bio_submit(READ, bio);
+		mpage_bio_submit(READA, bio);
 	return 0;
 }
 EXPORT_SYMBOL(mpage_readpage);
--- linux-2.6.17-mm1.orig/mm/page_io.c
+++ linux-2.6.17-mm1/mm/page_io.c
@@ -124,7 +124,7 @@ int swap_readpage(struct file *file, str
 		goto out;
 	}
 	inc_page_state(pswpin);
-	submit_bio(READ, bio);
+	submit_bio(READA, bio);
 out:
 	return ret;
 }

--