[PATCH 0/8] readahead updates

[PATCH 0/8] readahead updates

[Fengguang Wu]

Andrew,

Here are more updates for adaptive readahead.

It's not likely to have more big changes, so the next plan is to convert some
accounting items to the statistics infrastructure by Martin Peschke.
[Martin: Sorry for the long delay.]

I'm also playing with the current readahead code, trying to make it more clean
and reliable. I guess it would also be a long journey. It may be better to
wait and confirm if the adaptive readahead works in the wild, before touching
the stock readahead.

Regards,
Fengguang Wu
---

--- broken-out/series	2007-01-12 13:19:44.000000000 +0800
+++ patches/series	2007-01-27 14:53:27.000000000 +0800
@@ -1089,9 +1089,13 @@
 readahead-sysctl-parameters-set-readahead_hit_rate=1.patch
 readahead-min-max-sizes.patch
 readahead-min-max-sizes-remove-get_readahead_bounds.patch
+readahead-min-max-sizes-increase-VM_MIN_READAHEAD-to-32KB.patch
 readahead-state-based-method-aging-accounting.patch
 readahead-state-based-method-routines.patch
+readahead-state-based-method-routines-explicitly-embed-class_new-class_old-inside-flags.patch
 readahead-state-based-method.patch
+readahead-state-based-method-prevent-tiny-size.patch
+readahead-state-based-method-move-readahead_ratio-out-of-compute_thrashing_threshold.patch
 readahead-context-based-method.patch
 readahead-context-based-method-locking-fix.patch
 readahead-context-based-method-locking-fix-2.patch
@@ -1100,14 +1104,18 @@
 readahead-initial-method-guiding-sizes.patch
 readahead-initial-method-thrashing-guard-size.patch
 readahead-initial-method-user-recommended-size.patch
+readahead-initial-method-user-recommended-size-rename-to-read_ahead_initial_kb.patch
 readahead-initial-method.patch
 readahead-backward-prefetching-method.patch
 readahead-thrashing-recovery-method.patch
+readahead-thrashing-recovery-method-fix.patch
 readahead-call-scheme.patch
 readahead-call-scheme-ifdef-fix.patch
 readahead-call-scheme-build-fix.patch
 readahead-call-scheme-remove-get_readahead_bounds.patch
+readahead-call-scheme-fix-thrashed-unaligned-read.patch
 readahead-laptop-mode.patch
+readahead-laptop-mode-fix.patch
 readahead-loop-case.patch
 readahead-nfsd-case.patch
 readahead-nfsd-case-fix.patch

[PATCH 1/8] readahead: min/max sizes: increase VM_MIN_READAHEAD to 32KB

[Fengguang Wu]

[-- Attachment #1: readahead-min-max-sizes-increase-VM_MIN_READAHEAD-to-32KB.patch --]
[-- Type: text/plain, Size: 1004 bytes --]

Use a minimal readahead size of 32KB instead of 16KB for the adaptive readahead.

The potential benefit(disk utilization in worst case doubles) is large, while
the potential panelty is small(wastes up to 32MB when thrashed/missed 1000 times).

This minimal value is only applied for sequential streams.

Signed-off-by: Fengguang Wu <wfg@mail.ustc.edu.cn>
---
 include/linux/mm.h |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

--- linux-2.6.20-rc4-mm1.orig/include/linux/mm.h
+++ linux-2.6.20-rc4-mm1/include/linux/mm.h
@@ -1069,10 +1069,11 @@ int write_one_page(struct page *page, in
 /* readahead.c */
 #ifdef CONFIG_ADAPTIVE_READAHEAD
 #define VM_MAX_READAHEAD	1024	/* kbytes */
+#define VM_MIN_READAHEAD	32	/* kbytes (includes current page) */
 #else
 #define VM_MAX_READAHEAD	128	/* kbytes */
-#endif
 #define VM_MIN_READAHEAD	16	/* kbytes (includes current page) */
+#endif
 #define VM_MAX_CACHE_HIT    	256	/* max pages in a row in cache before
 					 * turning readahead off */
 

--

[PATCH 2/8] readahead: state based method routines: explicitly embed class_new/class_old inside flags

[Fengguang Wu]

[-- Attachment #1: readahead-state-based-method-routines-explicitly-embed-class_new-class_old-inside-flags.patch --]
[-- Type: text/plain, Size: 2155 bytes --]

The new/old ra class were implicitly stored in low bits of file_ra_state.flags.
Now make the data structure obvious, and remove the coding tricks.

Signed-off-by: Fengguang Wu <wfg@mail.ustc.edu.cn>
---
 include/linux/fs.h |    9 ++++++++-
 mm/readahead.c     |   18 ++++--------------
 2 files changed, 12 insertions(+), 15 deletions(-)

--- linux-2.6.20-rc4-mm1.orig/include/linux/fs.h
+++ linux-2.6.20-rc4-mm1/include/linux/fs.h
@@ -738,7 +738,14 @@ struct file_ra_state {
 	unsigned long mmap_hit;		/* Cache hit stat for mmap accesses */
 	unsigned long mmap_miss;	/* Cache miss stat for mmap accesses */
 
-	unsigned long flags;	/* RA_FLAG_xxx | ra_class_old | ra_class_new */
+	union {
+		unsigned long	flags;	/* RA_FLAG_xxx | class_old | class_new */
+		struct {
+			u8	class_new;
+			u8	class_old;
+		};
+	};
+
 	unsigned long prev_page;	/* Cache last read() position */
 	unsigned long ra_pages;		/* Maximum readahead window */
 };
--- linux-2.6.20-rc4-mm1.orig/mm/readahead.c
+++ linux-2.6.20-rc4-mm1/mm/readahead.c
@@ -48,8 +48,6 @@ int readahead_hit_rate = 1;
 /*
  * Detailed classification of read-ahead behaviors.
  */
-#define RA_CLASS_SHIFT 4
-#define RA_CLASS_MASK  ((1 << RA_CLASS_SHIFT) - 1)
 enum ra_class {
 	RA_CLASS_ALL,
 	RA_CLASS_INITIAL,
@@ -795,12 +793,12 @@ out:
 
 static enum ra_class ra_class_new(struct file_ra_state *ra)
 {
-	return ra->flags & RA_CLASS_MASK;
+	return ra->class_new;
 }
 
 static inline enum ra_class ra_class_old(struct file_ra_state *ra)
 {
-	return (ra->flags >> RA_CLASS_SHIFT) & RA_CLASS_MASK;
+	return ra->class_old;
 }
 
 static unsigned long ra_readahead_size(struct file_ra_state *ra)
@@ -832,16 +830,8 @@ static int ra_has_index(struct file_ra_s
  */
 static void ra_set_class(struct file_ra_state *ra, enum ra_class ra_class)
 {
-	unsigned long flags_mask;
-	unsigned long flags;
-	unsigned long old_ra_class;
-
-	flags_mask = ~(RA_CLASS_MASK | (RA_CLASS_MASK << RA_CLASS_SHIFT));
-	flags = ra->flags & flags_mask;
-
-	old_ra_class = ra_class_new(ra) << RA_CLASS_SHIFT;
-
-	ra->flags = flags | old_ra_class | ra_class;
+	ra->class_old = ra->class_new;
+	ra->class_new = ra_class;
 }
 
 /*

--

[PATCH 3/8] readahead: state based method: prevent tiny size

[Fengguang Wu]

[-- Attachment #1: readahead-state-based-method-prevent-tiny-size.patch --]
[-- Type: text/plain, Size: 1581 bytes --]

- cancel look-ahead if readahead size is small compared to the look-ahead size,
  to avoid too small I/O size, and not to add more memory/io pressure on the
  possibly loaded system.
- prevent issuing tiny readahead size, by applying a minimal limit

Signed-off-by: Fengguang Wu <wfg@mail.ustc.edu.cn>
---
 mm/readahead.c |   21 ++++++++++++++++-----
 1 file changed, 16 insertions(+), 5 deletions(-)

--- linux-2.6.20-rc4-mm1.orig/mm/readahead.c
+++ linux-2.6.20-rc4-mm1/mm/readahead.c
@@ -932,17 +932,21 @@ static int adjust_rala(unsigned long ra_
 			unsigned long *ra_size, unsigned long *la_size)
 {
 	/*
-	 * Substract the old look-ahead to get real safe size for the next
-	 * read-ahead request.
+	 * Cancel asynchrous read-ahead,
+	 * if there is a major upsurge of load, or fall of this stream's speed.
 	 */
-	if (*ra_size > *la_size)
-		*ra_size -= *la_size;
-	else {
+	if (*ra_size <= *la_size * 2) {
 		ra_account(NULL, RA_EVENT_READAHEAD_SHRINK, *ra_size);
 		return 0;
 	}
 
 	/*
+	 * Substract the old look-ahead to get real safe size for the next
+	 * read-ahead request.
+	 */
+	*ra_size -= *la_size;
+
+	/*
 	 * Set new la_size according to the (still large) ra_size.
 	 */
 	*la_size = *ra_size / LOOKAHEAD_RATIO;
@@ -956,6 +960,13 @@ static void limit_rala(unsigned long ra_
 	unsigned long stream_shift;
 
 	/*
+	 * Protect against too small I/O sizes,
+	 * by mapping [0, 4*min] to [min, 4*min].
+	 */
+	if (*ra_size < 4 * MIN_RA_PAGES)
+		*ra_size = MIN_RA_PAGES + *ra_size * 3 / 4;
+
+	/*
 	 * Apply basic upper limits.
 	 */
 	if (*ra_size > ra_max)

--

[PATCH 4/8] readahead: state based method: move readahead_ratio out of compute_thrashing_threshold()

[Fengguang Wu]

[-- Attachment #1: readahead-state-based-method-move-readahead_ratio-out-of-compute_thrashing_threshold.patch --]
[-- Type: text/plain, Size: 957 bytes --]

Make compute_thrashing_threshold() a pure computing routine,
by moving the readahead_ratio policy out of it.

Signed-off-by: Fengguang Wu <wfg@mail.ustc.edu.cn>
---
 mm/readahead.c |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

--- linux-2.6.20-rc4-mm1.orig/mm/readahead.c
+++ linux-2.6.20-rc4-mm1/mm/readahead.c
@@ -1025,7 +1025,7 @@ static unsigned long compute_thrashing_t
 	stream_shift = ra_invoke_interval(ra);
 
 	/* future safe space */
-	ll = (uint64_t) stream_shift * (global_size >> 9) * readahead_ratio * 5;
+	ll = (uint64_t) stream_shift * global_size;
 	do_div(ll, global_shift);
 	ra_size = ll;
 
@@ -1063,6 +1063,7 @@ state_based_readahead(struct address_spa
 	la_old = la_size = ra->readahead_index - offset;
 	ra_old = ra_readahead_size(ra);
 	ra_size = compute_thrashing_threshold(ra, &remain_space);
+	ra_size = ra_size * readahead_ratio / 100;
 
 	if (page && remain_space <= la_size) {
 		rescue_pages(page, la_size);

--

[PATCH 5/8] readahead: initial method: user recommended size: rename to read_ahead_initial_kb

[Fengguang Wu]

[-- Attachment #1: readahead-initial-method-user-recommended-size-rename-to-read_ahead_initial_kb.patch --]
[-- Type: text/plain, Size: 695 bytes --]

Rename the sysfs parameter initial_ra_kb to read_ahead_initial_kb,
which hopefully is a more consistent and user friendly name.

Signed-off-by: Fengguang Wu <wfg@mail.ustc.edu.cn>
---
 block/ll_rw_blk.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

--- linux-2.6.20-rc4-mm1.orig/block/ll_rw_blk.c
+++ linux-2.6.20-rc4-mm1/block/ll_rw_blk.c
@@ -3992,7 +3992,7 @@ static struct queue_sysfs_entry queue_ra
 };
 
 static struct queue_sysfs_entry queue_initial_ra_entry = {
-	.attr = {.name = "initial_ra_kb", .mode = S_IRUGO | S_IWUSR },
+	.attr = {.name = "read_ahead_initial_kb", .mode = S_IRUGO | S_IWUSR },
 	.show = queue_initial_ra_show,
 	.store = queue_initial_ra_store,
 };

--

[PATCH 6/8] readahead: thrashing recovery method fix

[Fengguang Wu]

[-- Attachment #1: readahead-thrashing-recovery-method-fix.patch --]
[-- Type: text/plain, Size: 1951 bytes --]

- keep lookahead_index if the current chunk is lost, so that when we
  revisted this stream, the state based method see a consistent state.
- correct the thrashing-threshold computation
- discount read-ahead size more, to free more memory to the system on pressure
- disable look-ahead when thrashed, just to be safe

Signed-off-by: Fengguang Wu <wfg@mail.ustc.edu.cn>
---
 mm/readahead.c |   28 +++++++++++++---------------
 1 file changed, 13 insertions(+), 15 deletions(-)

--- linux-2.6.20-rc4-mm1.orig/mm/readahead.c
+++ linux-2.6.20-rc4-mm1/mm/readahead.c
@@ -1524,28 +1524,26 @@ thrashing_recovery_readahead(struct addr
 						ra->readahead_index - offset);
 #endif
 
-	/*
-	 * Some thrashing occur in (ra_index, la_index], in which case the
-	 * old read-ahead chunk is lost soon after the new one is allocated.
-	 * Ensure that we recover all needed pages in the old chunk.
-	 */
-	if (offset < ra->ra_index)
-		ra_size = ra->ra_index - offset;
-	else {
+	if (offset < ra->ra_index) {
+		/*
+		 * Thrashed when we are in [la_index, ra_index), i.e.
+		 * the old chunk is lost soon after the new one is allocated.
+		 * Ensure that we recover all needed pages in the old chunk.
+		 * And futher keep the lookahead_index untouched.
+		 */
+		ra_size = ra->lookahead_index - offset;
+	} else {
 		/* After thrashing, we know the exact thrashing-threshold. */
-		ra_size = offset - ra->ra_index;
+		ra_size = offset - ra->la_index;
 		update_ra_thrash_bytes(mapping->backing_dev_info, ra_size);
 
-		/* And we'd better be a bit conservative. */
-		ra_size = ra_size * 3 / 4;
+		/* And be cooperative: the system may be hunting for memory. */
+		ra_size = MIN_RA_PAGES + ra_size / 2;
 	}
 
-	if (ra_size > ra_max)
-		ra_size = ra_max;
-
 	ra_set_class(ra, RA_CLASS_THRASHING);
 	ra_set_index(ra, offset, offset);
-	ra_set_size(ra, ra_size, ra_size / LOOKAHEAD_RATIO);
+	ra_set_size(ra, ra_size, 0);
 
 	return ra_submit(ra, mapping, filp);
 }

--

[PATCH 7/8] readahead: call scheme: fix thrashed unaligned read

[Fengguang Wu]

[-- Attachment #1: readahead-call-scheme-fix-thrashed-unaligned-read.patch --]
[-- Type: text/plain, Size: 780 bytes --]

When doing unaligned/subpages sequential reads, and thrashing happened,
it is possible that (offset == prev_page),
besides the normal  (offset == prev_page + 1).

We do not have such problem for the state based method.

Signed-off-by: Fengguang Wu <wfg@mail.ustc.edu.cn>
---
 mm/readahead.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

--- linux-2.6.20-rc4-mm1.orig/mm/readahead.c
+++ linux-2.6.20-rc4-mm1/mm/readahead.c
@@ -1618,7 +1618,7 @@ page_cache_readahead_adaptive(struct add
 	/*
 	 * Recover from possible thrashing.
 	 */
-	if (!page && offset == ra->prev_page + 1 && ra_has_index(ra, offset))
+	if (!page && offset - ra->prev_page <= 1 && ra_has_index(ra, offset))
 		return thrashing_recovery_readahead(mapping, filp, ra,
 								offset, ra_max);
 

--

[PATCH 8/8] readahead: laptop mode fix

[Fengguang Wu]

[-- Attachment #1: readahead-laptop-mode-fix.patch --]
[-- Type: text/plain, Size: 2151 bytes --]

1) make LAPTOP_POLL_INTERVAL independent of page size

2) defer readahead to the _last_ minute

There's no luck for the kernel to know the right time of
waking up the disk in order to hide the spin up latency.

So we make the rule simple:
- The kernel ensures _longest_ spin down time;
- The media player caches enough data to hide the spin up delay.

That means, if one enabled laptop mode, and want to watch movies
without pauses, he should setup proper media player cache as well.

Signed-off-by: Fengguang Wu <wfg@mail.ustc.edu.cn>
---
 mm/readahead.c |   22 ++++++++--------------
 1 file changed, 8 insertions(+), 14 deletions(-)

--- linux-2.6.20-rc4-mm1.orig/mm/readahead.c
+++ linux-2.6.20-rc4-mm1/mm/readahead.c
@@ -37,7 +37,7 @@
 #define INITIAL_RA_PAGES  DIV_ROUND_UP(64*1024, PAGE_CACHE_SIZE)
 
 /* In laptop mode, poll delayed look-ahead on every ## pages read. */
-#define LAPTOP_POLL_INTERVAL 16
+#define LAPTOP_POLL_INTERVAL	DIV_ROUND_UP(64*1024, PAGE_CACHE_SIZE)
 
 /* Set look-ahead size to 1/# of the thrashing-threshold. */
 #define LOOKAHEAD_RATIO 8
@@ -788,28 +788,22 @@ out:
 
 /*
  * Set a new look-ahead mark at @next.
- * Return 0 if the new mark is successfully set.
  */
-static int renew_lookahead(struct address_space *mapping,
+static void defer_lookahead(struct address_space *mapping,
 				struct file_ra_state *ra,
 				pgoff_t offset, pgoff_t next)
 {
 	struct page *page;
 
-	if (offset == ra->lookahead_index &&
-	      next >= ra->readahead_index)
-		return 1;
-
-	if (!(page = find_get_page(mapping, next)))
-		return 1;
+	page = find_get_page(mapping, next);
+	if (!page)
+		return;
 
 	SetPageReadahead(page);
 	page_cache_release(page);
 
 	if (ra->lookahead_index == offset)
 	    ra->lookahead_index = next;
-
-	return 0;
 }
 
 /*
@@ -1617,9 +1611,9 @@ page_cache_readahead_adaptive(struct add
 		 * Defer read-ahead to save energy.
 		 */
 		if (unlikely(laptop_mode && laptop_spinned_down())) {
-			if (!renew_lookahead(mapping, ra, offset,
-						offset + LAPTOP_POLL_INTERVAL))
-				return 0;
+			defer_lookahead(mapping, ra, offset,
+						offset + LAPTOP_POLL_INTERVAL);
+			return 0;
 		}
 	}
 

--

Re: [PATCH 0/8] readahead updates

[martin]

On Sat, 2007-01-27 at 16:02 +0800, Fengguang Wu wrote:
> Andrew,
> 
> Here are more updates for adaptive readahead.
> 
> It's not likely to have more big changes, so the next plan is to convert some
> accounting items to the statistics infrastructure by Martin Peschke.
> [Martin: Sorry for the long delay.]

Do you mean the ra_account() items?

Thanks,
Martin

Re: [PATCH 2/8] readahead: state based method routines: explicitly embed class_new/class_old inside flags

[Bodo Eggert]

Fengguang Wu <wfg@mail.ustc.edu.cn> wrote:

> The new/old ra class were implicitly stored in low bits of
> file_ra_state.flags. Now make the data structure obvious, and remove the
> coding tricks.

> +++ linux-2.6.20-rc4-mm1/include/linux/fs.h

> -     unsigned long flags;    /* RA_FLAG_xxx | ra_class_old | ra_class_new */
> +     union {
> +             unsigned long   flags;  /* RA_FLAG_xxx | class_old | class_new */
> +             struct {
> +                     u8      class_new;
> +                     u8      class_old;

This doesn't work on big endiam machines, does it?

IMO you should use a bitfield instead.
-- 
Your e-mail has been returned due to insufficient voltage. 

Friß, Spammer: aegzcH4Js@luevh-7.7eggert.dyndns.org
 ptulV7@C.7eggert.dyndns.org vkIfyB@SEcltba.7eggert.dyndns.org

Re: [PATCH 2/8] readahead: state based method routines: explicitly embed class_new/class_old inside flags

[Randy Dunlap]

On Sat, 27 Jan 2007 13:01:08 +0100 Bodo Eggert wrote:

> Fengguang Wu <wfg@mail.ustc.edu.cn> wrote:
> 
> > The new/old ra class were implicitly stored in low bits of
> > file_ra_state.flags. Now make the data structure obvious, and remove the
> > coding tricks.
> 
> > +++ linux-2.6.20-rc4-mm1/include/linux/fs.h
> 
> > -     unsigned long flags;    /* RA_FLAG_xxx | ra_class_old | ra_class_new */
> > +     union {
> > +             unsigned long   flags;  /* RA_FLAG_xxx | class_old | class_new */
> > +             struct {
> > +                     u8      class_new;
> > +                     u8      class_old;
> 
> This doesn't work on big endiam machines, does it?
> 
> IMO you should use a bitfield instead.

Or "use bit masks instead" since

"The order of allocation of bit-fields within a unit (high-order to
low-order or low-order to high-order) is implementation-defined."

---
~Randy