readahead stats/tracing, backwards prefetching and more

This looks reasonable: smaller device tend to be slower (USB sticks as well as micro/mobile/old hard disks).

Given that the non-rotational attribute is not always reported, we can take disk size as a max readahead size hint. This patch uses a formula that generates the following concrete limits:

Quoted 3 lines · Wu Fengguang

This looks reasonable: smaller device tend to be slower (USB sticks as well as micro/mobile/old hard disks).

Quoted 3 lines

Given that the non-rotational attribute is not always reported, we can take disk size as a max readahead size hint. This patch uses a formula that generates the following concrete limits:

Given that you mentioned the rotational flag and device size in this mail, as well as benchmarking with an intel SSD - did you measure how useful large read ahead sizes still are with highend Flash device that have extremly high read IOP rates?

Quoted 3 lines · Wu Fengguang

Given that the non-rotational attribute is not always reported, we can take disk size as a max readahead size hint. This patch uses a formula that generates the following concrete limits:

Given that you mentioned the rotational flag and device size in this mail, as well as benchmarking with an intel SSD - did you measure how useful large read ahead sizes still are with highend Flash device that have extremly high read IOP rates?

Linus reports a _really_ small & slow (505kB, 15kB/s) USB device, on which blkid runs unpleasantly slow. He manages to optimize the blkid reads down to 1kB+16kB, but still kernel read-ahead turns it into 48kB.

lseek 0, read 1024 => readahead 4 pages (start of file)
lseek 1536, read 16384 => readahead 8 pages (page contiguous)

The readahead heuristics involved here are reasonable ones in general. So it's good to fix blkid with fadvise(RANDOM), as Linus already did.

For the kernel part, Linus suggests:
So maybe we could be less aggressive about read-ahead when the size of the device is small? Turning a 16kB read into a 64kB one is a big deal, when it's about 15% of the whole device!

This looks reasonable: smaller device tend to be slower (USB sticks as well as micro/mobile/old hard disks).

Given that the non-rotational attribute is not always reported, we can take disk size as a max readahead size hint. This patch uses a formula that generates the following concrete limits:

        disk size    readahead size
     (scale by 4)      (scale by 2)
               1M                8k
               4M               16k
              16M               32k
              64M               64k
             256M              128k
        --------------------------- (*)
               1G              256k
               4G              512k
              16G             1024k
              64G             2048k
             256G             4096k

(*) Since the default readahead size is 128k, this limit only takes effect for devices whose size is less than 256M.

Linus reports a _really_ small & slow (505kB, 15kB/s) USB device, on which blkid runs unpleasantly slow. He manages to optimize the blkid reads down to 1kB+16kB, but still kernel read-ahead turns it into 48kB.

lseek 0, read 1024 => readahead 4 pages (start of file)

lseek 1536, read 16384 => readahead 8 pages (page contiguous)

The readahead heuristics involved here are reasonable ones in general. So it's good to fix blkid with fadvise(RANDOM), as Linus already did.

For the kernel part, Linus suggests:
So maybe we could be less aggressive about read-ahead when the size of the device is small? Turning a 16kB read into a 64kB one is a big deal, when it's about 15% of the whole device!

This looks reasonable: smaller device tend to be slower (USB sticks as well as micro/mobile/old hard disks).

block/genhd.c +7 -0

@@ -623,6 +623,26 @@ void add_disk(struct gendisk *disk)
 	WARN_ON(retval);
 
 	disk_add_events(disk);
+
+	/*
+	 * Limit default readahead size for small devices.
+	 *        disk size    readahead size
+	 *               1M                8k
+	 *               4M               16k
+	 *              16M               32k

In a better world, userspace would run a work-out-what-readahead-size-to-use script each time a distro is installed and when new storage devices are added/detected. Userspace would then remember that readahead size for subsequent bootups.

In the real world, we shovel guaranteed-to-be-wrong guesswork into the kernel and everyone just uses the results. Sigh.

Quoted 4 lines · On Mon, 21 Nov 2011 17:18:20 +0800 Wu Fengguang <[email protected]> wrote:

Linus reports a _really_ small & slow (505kB, 15kB/s) USB device, on which blkid runs unpleasantly slow. He manages to optimize the blkid reads down to 1kB+16kB, but still kernel read-ahead turns it into 48kB.

Quoted 1 line

lseek 0, read 1024 => readahead 4 pages (start of file)

I'm disturbed that the code did a 4 page (16kbyte?) readahead after an lseek. Given the high probability that the next read will occur after a second lseek, that's a mistake.

Was an lseek to offset 0 special-cased?

Quoted 10 lines

lseek 1536, read 16384 => readahead 8 pages (page contiguous)

The readahead heuristics involved here are reasonable ones in general. So it's good to fix blkid with fadvise(RANDOM), as Linus already did.

For the kernel part, Linus suggests:
So maybe we could be less aggressive about read-ahead when the size of the device is small? Turning a 16kB read into a 64kB one is a big deal, when it's about 15% of the whole device!

Quoted 2 lines

This looks reasonable: smaller device tend to be slower (USB sticks as well as micro/mobile/old hard disks).

Spose so. Obviously there are other characteristics which should be considered when choosing a readaahead size, but one of them can be disk size and that's what this change does.

In a better world, userspace would run a work-out-what-readahead-size-to-use script each time a distro is installed and when new storage devices are added/detected. Userspace would then remember that readahead size for subsequent bootups.

In the real world, we shovel guaranteed-to-be-wrong guesswork into the kernel and everyone just uses the results. Sigh.

Quoted 19 lines

block/genhd.c +13 -0

@@ -623,6 +623,26 @@ void add_disk(struct gendisk *disk)
 	WARN_ON(retval);
 
 	disk_add_events(disk);
+
+	/*
+	 * Limit default readahead size for small devices.
+	 *        disk size    readahead size
+	 *               1M                8k
+	 *               4M               16k
+	 *              16M               32k
+	 *              64M               64k
+	 *             256M              128k
+	 *               1G              256k
+	 *               4G              512k
+	 *              16G             1024k
+	 *              64G             2048k

block/genhd.c void add_disk(struct gendisk *disk) · line 642

Quoted 4 lines

block/genhd.c +4 -0

+	 *             256G             4096k
+	 */
+	if (get_capacity(disk)) {
+		unsigned long size = get_capacity(disk) >> 9;

get_capacity() returns sector_t. This expression will overflow with a 2T disk. I'm not sure if we successfully support 2T disks on 32-bit machines, but changes like this will guarantee that we don't :)

block/genhd.c void add_disk(struct gendisk *disk) · line 643

Quoted 1 line

block/genhd.c +1 -0

+		size = 1UL << (ilog2(size) / 2);

I think there's a rounddown_pow_of_two() hiding in that expression?

block/genhd.c void add_disk(struct gendisk *disk) · line 644

Quoted 1 line

block/genhd.c +1 -0

+		bdi->ra_pages = min(bdi->ra_pages, size);

I don't have a clue why that min() is in there. It needs a comment, please.

From: Nikanth Karthikesan <[email protected]>

Add new kernel parameter "readahead=", which allows user to override the static VM_MAX_READAHEAD=128kb.

Quoted 4 lines · Wu Fengguang

From: Nikanth Karthikesan <[email protected]>

Add new kernel parameter "readahead=", which allows user to override the static VM_MAX_READAHEAD=128kb.

Is a boot-time paramter really such a good idea? I would at least

make it a sysctl so that it's run-time controllable, including beeing able to set it from initscripts.

Quoted 7 lines · Christoph Hellwig

Quoted 4 lines · Wu Fengguang

From: Nikanth Karthikesan <[email protected]>

Add new kernel parameter "readahead=", which allows user to override the static VM_MAX_READAHEAD=128kb.

Is a boot-time paramter really such a good idea? I would at least

It's most convenient to set at boot time, because the default size will be used to initialize all the block devices.

Quoted 2 lines

make it a sysctl so that it's run-time controllable, including beeing able to set it from initscripts.

Once boot up, it's more natural to set the size one by one, for example

        blockdev --setra 1024 /dev/sda2

or
echo 512 > /sys/block/sda/queue/read_ahead_kb

And you still have the chance to modify the global default, but the change will only be inherited by newly created devices thereafter:

echo 512 > /sys/devices/virtual/bdi/default/read_ahead_kb

The above command is very suitable for use in initscripts. However there are no natural way to do sysctl as there is no such a global value.

Quoted 25 lines · Wu Fengguang

Quoted 7 lines · Christoph Hellwig

Quoted 4 lines · Wu Fengguang

From: Nikanth Karthikesan <[email protected]>

Add new kernel parameter "readahead=", which allows user to override the static VM_MAX_READAHEAD=128kb.

Is a boot-time paramter really such a good idea? I would at least

It's most convenient to set at boot time, because the default size will be used to initialize all the block devices.

Quoted 2 lines

make it a sysctl so that it's run-time controllable, including beeing able to set it from initscripts.

Once boot up, it's more natural to set the size one by one, for example

        blockdev --setra 1024 /dev/sda2

or
echo 512 > /sys/block/sda/queue/read_ahead_kb

And you still have the chance to modify the global default, but the change will only be inherited by newly created devices thereafter:

Quoted 5 lines

echo 512 > /sys/devices/virtual/bdi/default/read_ahead_kb

The above command is very suitable for use in initscripts. However there are no natural way to do sysctl as there is no such a global value.

Well, you can always have an udev rule to set read_ahead_kb to whatever
you want. In some respect that looks like a nicer solution to me...

Quoted 26 lines · Jan Kara

Quoted 25 lines · Wu Fengguang

Quoted 7 lines · Christoph Hellwig

Quoted 4 lines · Wu Fengguang

From: Nikanth Karthikesan <[email protected]>

Add new kernel parameter "readahead=", which allows user to override the static VM_MAX_READAHEAD=128kb.

Is a boot-time paramter really such a good idea? I would at least

It's most convenient to set at boot time, because the default size will be used to initialize all the block devices.

Quoted 2 lines

make it a sysctl so that it's run-time controllable, including beeing able to set it from initscripts.

Once boot up, it's more natural to set the size one by one, for example

        blockdev --setra 1024 /dev/sda2

or
echo 512 > /sys/block/sda/queue/read_ahead_kb

And you still have the chance to modify the global default, but the change will only be inherited by newly created devices thereafter:

Quoted 7 lines

Quoted 5 lines

echo 512 > /sys/devices/virtual/bdi/default/read_ahead_kb

The above command is very suitable for use in initscripts. However there are no natural way to do sysctl as there is no such a global value.

Well, you can always have an udev rule to set read_ahead_kb to whatever
you want. In some respect that looks like a nicer solution to me...

And one that has already been in use for exactly this purpose for years. Indeed, it's far more flexible because you can give different types of devices different default readahead settings quite easily, and it you can set different defaults for just about any tunable parameter (e.g. readahead, ctq depth, max IO sizes, etc) in the same way.

Hence I don't think we should treat default readahead any differently from any other configurable storage parameter - we've already got places to change the per-device defaults to something sensible at boot/discovery time....

Quoted 6 lines · Dave Chinner

Quoted 5 lines · Jan Kara

Quoted 4 lines · Wu Fengguang

Quoted 3 lines · Christoph Hellwig

Quoted 2 lines · Wu Fengguang

From: Nikanth Karthikesan<[email protected]>

Quoted 7 lines

And one that has already been in use for exactly this purpose for years. Indeed, it's far more flexible because you can give different types of devices different default readahead settings quite easily, and it you can set different defaults for just about any tunable parameter (e.g. readahead, ctq depth, max IO sizes, etc) in the same way.

I'm interested in this usage, too. Would you share some of your rules?

Quoted 7 lines · Wu Fengguang

Quoted 6 lines · Dave Chinner

Quoted 5 lines · Jan Kara

Quoted 4 lines · Wu Fengguang

Quoted 3 lines · Christoph Hellwig

Quoted 2 lines · Wu Fengguang

From: Nikanth Karthikesan<[email protected]>

[...]

Quoted 8 lines

Quoted 7 lines

And one that has already been in use for exactly this purpose for years. Indeed, it's far more flexible because you can give different types of devices different default readahead settings quite easily, and it you can set different defaults for just about any tunable parameter (e.g. readahead, ctq depth, max IO sizes, etc) in the same way.

Quoted 2 lines

I'm interested in this usage, too. Would you share some of your rules?

FYI - This is an example of a rules Suse delivers in SLES @ s390 for a while now. With little modifications it could be used for all Dave mentioned above.

cat /etc/udev/rules.d/60-readahead.rules
#

# Rules to set an increased default max readahead size for s390 disk devices

# This file should be installed in /etc/udev/rules.d

#

SUBSYSTEM!="block", GOTO="ra_end"

ACTION!="add", GOTO="ra_end"

# on device add set initial readahead to 512 (instead of in kernel 128) 

KERNEL=="sd*[!0-9]", ATTR{queue/read_ahead_kb}="512"

KERNEL=="dasd*[!0-9]", ATTR{queue/read_ahead_kb}="512"

LABEL="ra_end"

Signature · 2 lines

Grüsse / regards, Christian Ehrhardt
IBM Linux Technology Center, System z Linux Performance

Quoted 19 lines

cat /etc/udev/rules.d/60-readahead.rules
#

# Rules to set an increased default max readahead size for s390 disk devices

# This file should be installed in /etc/udev/rules.d

#

SUBSYSTEM!="block", GOTO="ra_end"

ACTION!="add", GOTO="ra_end"

Quoted 5 lines

# on device add set initial readahead to 512 (instead of in kernel 128) 

KERNEL=="sd*[!0-9]", ATTR{queue/read_ahead_kb}="512"

KERNEL=="dasd*[!0-9]", ATTR{queue/read_ahead_kb}="512"

So SLES (@s390 and maybe more) is already shipping with 512kb readahead size? Good to know this!

From: Nikanth Karthikesan <[email protected]>

Add new kernel parameter "readahead=", which allows user to override the static VM_MAX_READAHEAD=128kb.

CC Ankit Jain <[email protected]>

CC Dave Chinner <[email protected]>

CC Christian Ehrhardt <[email protected]>

Acked-by Rik van Riel <[email protected]>

Signed-off-by Nikanth Karthikesan <[email protected]>

Signed-off-by Wu Fengguang <[email protected]>

---
 Documentation/kernel-parameters.txt |    6 ++++++
 block/blk-core.c                    |    3 +--
 fs/fuse/inode.c                     |    2 +-
 mm/readahead.c                      |   19 +++++++++++++++++++
 4 files changed, 27 insertions(+), 3 deletions(-)

Documentation/kernel-parameters.txt bytes respectively. Such letter suffixes · line 2251

Quoted 4 lines

Documentation/kernel-parameters.txt +4 -0

+	readahead=nn[KM]
+			Default max readahead size for block devices.
+
+			This default max readahead size may be overrode

s/overrode/overridden/ ?

plain text document attachment (readahead-flags.patch) Introduce a readahead flags field and embed the existing mmap_miss in it (mainly to save space).

It will be possible to lose the flags in race conditions, however the impact should be limited. For the race to happen, there must be two threads sharing the same file descriptor to be in page fault or readahead at the same time.

Note that it has always been racy for "page faults" at the same time.

And if ever the race happen, we'll lose one mmap_miss++ or mmap_miss--. Which may change some concrete readahead behavior, but won't really impact overall I/O performance.

CC Andi Kleen <[email protected]>

CC Steven Whitehouse <[email protected]>

Acked-by Rik van Riel <[email protected]>

Signed-off-by Wu Fengguang <[email protected]>

---
 include/linux/fs.h |   31 ++++++++++++++++++++++++++++++-
 mm/filemap.c       |    9 ++-------
 2 files changed, 32 insertions(+), 8 deletions(-)

include/linux/fs.h +30 -1

@@ -945,10 +945,39 @@ struct file_ra_state {
 					   there are only # of pages ahead */
 
 	unsigned int ra_pages;		/* Maximum readahead window */
-	unsigned int mmap_miss;		/* Cache miss stat for mmap accesses */
+	unsigned int ra_flags;
 	loff_t prev_pos;		/* Cache last read() position */
 };
 
+/* ra_flags bits */
+#define	READAHEAD_MMAP_MISS	0x000003ff /* cache misses for mmap access */
+
+/*
+ * Don't do ra_flags++ directly to avoid possible overflow:
+ * the ra fields can be accessed concurrently in a racy way.
+ */
+static inline unsigned int ra_mmap_miss_inc(struct file_ra_state *ra)
+{
+	unsigned int miss = ra->ra_flags & READAHEAD_MMAP_MISS;
+
+	/* the upper bound avoids banging the cache line unnecessarily */
+	if (miss < READAHEAD_MMAP_MISS) {
+		miss++;
+		ra->ra_flags = miss | (ra->ra_flags & ~READAHEAD_MMAP_MISS);
+	}
+	return miss;
+}
+
+static inline void ra_mmap_miss_dec(struct file_ra_state *ra)
+{
+	unsigned int miss = ra->ra_flags & READAHEAD_MMAP_MISS;
+
+	if (miss) {
+		miss--;
+		ra->ra_flags = miss | (ra->ra_flags & ~READAHEAD_MMAP_MISS);
+	}
+}
+
 /*
  * Check if @index falls in the readahead windows.
  */

mm/filemap.c +1 -5

@@ -1597,15 +1597,11 @@ static void do_sync_mmap_readahead(struc
 		return;
 	}
 
-	/* Avoid banging the cache line if not needed */
-	if (ra->mmap_miss < MMAP_LOTSAMISS * 10)
-		ra->mmap_miss++;
-
 	/*
 	 * Do we miss much more than hit in this file? If so,
 	 * stop bothering with read-ahead. It will only hurt.
 	 */
-	if (ra->mmap_miss > MMAP_LOTSAMISS)
+	if (ra_mmap_miss_inc(ra) > MMAP_LOTSAMISS)
 		return;
 
 	/*

Hi,

I'm not quite sure why you copied me in to this patch, but I've had a

look at it and it seems ok to me. Some of the other patches in this series look as if they might be rather useful for the GFS2 dir readahead code though, so I'll be keeping an eye on developments in this area,

Acked-by Steven Whitehouse <[email protected]>

Quoted 85 lines

plain text document attachment (readahead-flags.patch) Introduce a readahead flags field and embed the existing mmap_miss in it (mainly to save space).

It will be possible to lose the flags in race conditions, however the impact should be limited. For the race to happen, there must be two threads sharing the same file descriptor to be in page fault or readahead at the same time.

Note that it has always been racy for "page faults" at the same time.

And if ever the race happen, we'll lose one mmap_miss++ or mmap_miss--. Which may change some concrete readahead behavior, but won't really impact overall I/O performance.

CC Andi Kleen <[email protected]>

CC Steven Whitehouse <[email protected]>

Acked-by Rik van Riel <[email protected]>

Signed-off-by Wu Fengguang <[email protected]>

---
 include/linux/fs.h |   31 ++++++++++++++++++++++++++++++-
 mm/filemap.c       |    9 ++-------
 2 files changed, 32 insertions(+), 8 deletions(-)

include/linux/fs.h +30 -1

@@ -945,10 +945,39 @@ struct file_ra_state {
 					   there are only # of pages ahead */
 
 	unsigned int ra_pages;		/* Maximum readahead window */
-	unsigned int mmap_miss;		/* Cache miss stat for mmap accesses */
+	unsigned int ra_flags;
 	loff_t prev_pos;		/* Cache last read() position */
 };
 
+/* ra_flags bits */
+#define	READAHEAD_MMAP_MISS	0x000003ff /* cache misses for mmap access */
+
+/*
+ * Don't do ra_flags++ directly to avoid possible overflow:
+ * the ra fields can be accessed concurrently in a racy way.
+ */
+static inline unsigned int ra_mmap_miss_inc(struct file_ra_state *ra)
+{
+	unsigned int miss = ra->ra_flags & READAHEAD_MMAP_MISS;
+
+	/* the upper bound avoids banging the cache line unnecessarily */
+	if (miss < READAHEAD_MMAP_MISS) {
+		miss++;
+		ra->ra_flags = miss | (ra->ra_flags & ~READAHEAD_MMAP_MISS);
+	}
+	return miss;
+}
+
+static inline void ra_mmap_miss_dec(struct file_ra_state *ra)
+{
+	unsigned int miss = ra->ra_flags & READAHEAD_MMAP_MISS;
+
+	if (miss) {
+		miss--;
+		ra->ra_flags = miss | (ra->ra_flags & ~READAHEAD_MMAP_MISS);
+	}
+}
+
 /*
  * Check if @index falls in the readahead windows.
  */

mm/filemap.c +1 -5

@@ -1597,15 +1597,11 @@ static void do_sync_mmap_readahead(struc
 		return;
 	}
 
-	/* Avoid banging the cache line if not needed */
-	if (ra->mmap_miss < MMAP_LOTSAMISS * 10)
-		ra->mmap_miss++;
-
 	/*
 	 * Do we miss much more than hit in this file? If so,
 	 * stop bothering with read-ahead. It will only hurt.
 	 */
-	if (ra->mmap_miss > MMAP_LOTSAMISS)
+	if (ra_mmap_miss_inc(ra) > MMAP_LOTSAMISS)
 		return;
 

mm/filemap.c static void do_async_mmap_readahead(stru · line 1635

Quoted 13 lines

mm/filemap.c +1 -2

 	/*

@@ -1633,8 +1629,7 @@ static void do_async_mmap_readahead(stru
 	/* If we don't want any read-ahead, don't bother */
 	if (VM_RandomReadHint(vma))
 		return;
-	if (ra->mmap_miss > 0)
-		ra->mmap_miss--;
+	ra_mmap_miss_dec(ra);
 	if (PageReadahead(page))
 		page_cache_async_readahead(mapping, ra, file,
 					   page, offset, ra->ra_pages);

Introduce a readahead flags field and embed the existing mmap_miss in it (mainly to save space).

It will be possible to lose the flags in race conditions, however the impact should be limited. For the race to happen, there must be two threads sharing the same file descriptor to be in page fault or readahead at the same time.

Note that it has always been racy for "page faults" at the same time.

And if ever the race happen, we'll lose one mmap_miss++ or mmap_miss--. Which may change some concrete readahead behavior, but won't really impact overall I/O performance.

CC Andi Kleen <[email protected]>

CC Steven Whitehouse <[email protected]>

Acked-by Rik van Riel <[email protected]>

Signed-off-by Wu Fengguang <[email protected]>

---
 include/linux/fs.h |   31 ++++++++++++++++++++++++++++++-
 mm/filemap.c       |    9 ++-------
 2 files changed, 32 insertions(+), 8 deletions(-)

include/linux/fs.h +18 -0

 	loff_t prev_pos;		/* Cache last read() position */
 };
 
+/* ra_flags bits */
+#define	READAHEAD_MMAP_MISS	0x000003ff /* cache misses for mmap access */
+
+/*
+ * Don't do ra_flags++ directly to avoid possible overflow:
+ * the ra fields can be accessed concurrently in a racy way.
+ */
+static inline unsigned int ra_mmap_miss_inc(struct file_ra_state *ra)
+{
+	unsigned int miss = ra->ra_flags & READAHEAD_MMAP_MISS;
+
+	/* the upper bound avoids banging the cache line unnecessarily */
+	if (miss < READAHEAD_MMAP_MISS) {
+		miss++;
+		ra->ra_flags = miss | (ra->ra_flags & ~READAHEAD_MMAP_MISS);
+	}
+	return miss;
+}

Quoted 2 lines · On Mon, 21 Nov 2011 17:18:22 +0800 Wu Fengguang <[email protected]> wrote:

Introduce a readahead flags field and embed the existing mmap_miss in it (mainly to save space).

What an ugly patch.

Quoted 25 lines

It will be possible to lose the flags in race conditions, however the impact should be limited. For the race to happen, there must be two threads sharing the same file descriptor to be in page fault or readahead at the same time.

Note that it has always been racy for "page faults" at the same time.

And if ever the race happen, we'll lose one mmap_miss++ or mmap_miss--. Which may change some concrete readahead behavior, but won't really impact overall I/O performance.

CC Andi Kleen <[email protected]>

CC Steven Whitehouse <[email protected]>

Acked-by Rik van Riel <[email protected]>

Signed-off-by Wu Fengguang <[email protected]>

---
 include/linux/fs.h |   31 ++++++++++++++++++++++++++++++-
 mm/filemap.c       |    9 ++-------
 2 files changed, 32 insertions(+), 8 deletions(-)

include/linux/fs.h +0 -0

@@ -945,10 +945,39 @@ struct file_ra_state {
 					   there are only # of pages ahead */
 

include/linux/fs.h struct file_ra_state { · line 948

Quoted 3 lines

include/linux/fs.h +1 -1

 	unsigned int ra_pages;		/* Maximum readahead window */
-	unsigned int mmap_miss;		/* Cache miss stat for mmap accesses */
+	unsigned int ra_flags;

And it doesn't actually save any space, unless ra_flags gets used for something else in a subsequent patch. And if it does, perhaps ra_flags

should be ulong, which is compatible with the bitops.h code. Or perhaps we should use a bitfield and let the compiler do the work.

Quoted 26 lines

include/linux/fs.h +23 -0

 	loff_t prev_pos;		/* Cache last read() position */
 };
 
+/* ra_flags bits */
+#define	READAHEAD_MMAP_MISS	0x000003ff /* cache misses for mmap access */
+
+/*
+ * Don't do ra_flags++ directly to avoid possible overflow:
+ * the ra fields can be accessed concurrently in a racy way.
+ */
+static inline unsigned int ra_mmap_miss_inc(struct file_ra_state *ra)
+{
+	unsigned int miss = ra->ra_flags & READAHEAD_MMAP_MISS;
+
+	/* the upper bound avoids banging the cache line unnecessarily */
+	if (miss < READAHEAD_MMAP_MISS) {
+		miss++;
+		ra->ra_flags = miss | (ra->ra_flags & ~READAHEAD_MMAP_MISS);
+	}
+	return miss;
+}
+
+static inline void ra_mmap_miss_dec(struct file_ra_state *ra)
+{
+	unsigned int miss = ra->ra_flags & READAHEAD_MMAP_MISS;
+

include/linux/fs.h struct file_ra_state { · line 979

Quoted 5 lines

include/linux/fs.h +5 -0

+	if (miss) {
+		miss--;
+		ra->ra_flags = miss | (ra->ra_flags & ~READAHEAD_MMAP_MISS);
+	}
+}

It's strange that ra_mmap_miss_inc() returns the new value whereas ra_mmap_miss_dec() returns void.

Quoted 2 lines

should be ulong, which is compatible with the bitops.h code. Or perhaps we should use a bitfield and let the compiler do the work.

What if we do

        u16     mmap_miss;
        u16     ra_flags;

That would get rid of this patch. I'd still like to pack the various flags as well as pattern into one single ra_flags, which makes it convenient to pass things around (as one single parameter).

Quoted 8 lines · On Wed, 23 Nov 2011 20:47:45 +0800 Wu Fengguang <[email protected]> wrote:

Quoted 2 lines

should be ulong, which is compatible with the bitops.h code. Or perhaps we should use a bitfield and let the compiler do the work.

What if we do

        u16     mmap_miss;
        u16     ra_flags;

Quoted 3 lines

That would get rid of this patch. I'd still like to pack the various flags as well as pattern into one single ra_flags, which makes it convenient to pass things around (as one single parameter).

I'm not sure that this will improve things much...

Again, how does the code look if you use a bitfield and let the compiler do the worK?

Record the readahead pattern in ra_flags and extend the ra_submit() parameters, to be used by the next readahead tracing/stats patches.

7 patterns are defined:

pattern readahead for
-----------------------------------------------------------
RA_PATTERN_INITIAL start-of-file read
RA_PATTERN_SUBSEQUENT trivial sequential read
RA_PATTERN_CONTEXT interleaved sequential read
RA_PATTERN_OVERSIZE oversize read
RA_PATTERN_MMAP_AROUND mmap fault
RA_PATTERN_FADVISE posix_fadvise()
RA_PATTERN_RANDOM random read

include/linux/fs.h +6 -0

+#define READAHEAD_PATTERN	0xf0000000
+
+/*
+ * Which policy makes decision to do the current read-ahead IO?
+ */
+enum readahead_pattern {

Quoted 5 lines · On Mon, 21 Nov 2011 17:18:23 +0800 Wu Fengguang <[email protected]> wrote:

Record the readahead pattern in ra_flags and extend the ra_submit() parameters, to be used by the next readahead tracing/stats patches.

7 patterns are defined:

Quoted 9 lines

pattern readahead for
-----------------------------------------------------------
RA_PATTERN_INITIAL start-of-file read
RA_PATTERN_SUBSEQUENT trivial sequential read
RA_PATTERN_CONTEXT interleaved sequential read
RA_PATTERN_OVERSIZE oversize read
RA_PATTERN_MMAP_AROUND mmap fault
RA_PATTERN_FADVISE posix_fadvise()
RA_PATTERN_RANDOM random read

It would be useful to spell out in full detail what an "interleaved sequential read" is, and why a read is considered "oversized", etc. The 'enum readahead_pattern' definition site would be a good place for this.

Quoted 9 lines

Note that random reads will be recorded in file_ra_state now. This won't deteriorate cache bouncing because the ra->prev_pos update in do_generic_file_read() already pollutes the data cache, and filemap_fault() will stop calling into us after MMAP_LOTSAMISS.

include/linux/fs.h +0 -0

@@ -951,6 +951,39 @@ struct file_ra_state {
 

include/linux/fs.h struct file_ra_state { · line 954

Quoted 3 lines

include/linux/fs.h +1 -0

 /* ra_flags bits */
 #define	READAHEAD_MMAP_MISS	0x000003ff /* cache misses for mmap access */
+#define	READAHEAD_MMAP		0x00010000

Why leave a gap?

And what is READAHEAD_MMAP anyway?

include/linux/fs.h struct file_ra_state { · line 956

Quoted 1 line

include/linux/fs.h +1 -0

+#define READAHEAD_PATTERN_SHIFT	28

Why 28?

Quoted 12 lines

include/linux/fs.h +12 -0

+#define READAHEAD_PATTERN	0xf0000000
+
+/*
+ * Which policy makes decision to do the current read-ahead IO?
+ */
+enum readahead_pattern {
+	RA_PATTERN_INITIAL,
+	RA_PATTERN_SUBSEQUENT,
+	RA_PATTERN_CONTEXT,
+	RA_PATTERN_MMAP_AROUND,
+	RA_PATTERN_FADVISE,
+	RA_PATTERN_OVERSIZE,

include/linux/fs.h struct file_ra_state { · line 972

Quoted 4 lines

include/linux/fs.h +4 -0

+	RA_PATTERN_RANDOM,
+	RA_PATTERN_ALL,		/* for summary stats */
+	RA_PATTERN_MAX
+};

Again, the behaviour is all undocumented. I see from the code that multiple flags can be set at the same time. So afacit a file can be marked RANDOM and SUBSEQUENT at the same time, which seems oxymoronic.

This reader wants to know what the implications of this are - how the code chooses, prioritises and acts. But this code doesn't tell me.

include/linux/fs.h struct file_ra_state { · line 976

Quoted 3 lines

include/linux/fs.h +3 -0

+static inline unsigned int ra_pattern(unsigned int ra_flags)
+{
+	unsigned int pattern = ra_flags >> READAHEAD_PATTERN_SHIFT;

OK, no masking is needed because the code silently assumes that arg `ra_flags' came out of an ra_state.ra_flags and it also silently assumes that no higher bits are used in ra_state.ra_flags.

That's a bit of a handgrenade - if someone redoes the flags enumeration, the code will explode.

include/linux/fs.h struct file_ra_state { · line 976

Quoted 2 lines

include/linux/fs.h +2 -0

+	return min_t(unsigned int, pattern, RA_PATTERN_ALL);
+}

<scratches head>

What the heck is that min_t() doing in there?

+static unsigned long ra_stats[RA_PATTERN_MAX][RA_ACCOUNT_MAX];

Quoted 1 line

+static unsigned long ra_stats[RA_PATTERN_MAX][RA_ACCOUNT_MAX];

Why not make it per cpu? That should get the overhead down, probably even enough that it can be enabled by default.

BTW I have an older framework to make it really easy to add per cpu stats counters to debugfs. Will repost, that would simplify it even more.

The accounting code will be compiled in by default (CONFIG_READAHEAD_STATS=y), and will remain inactive unless enabled explicitly with either boot option

readahead_stats=1

or through the debugfs interface

echo 1 > /debug/readahead/stats_enable

The added overheads are two readahead_stats() calls per readahead. Which is trivial costs unless there are concurrent random reads on super fast SSDs, which may lead to cache bouncing when updating the global ra_stats[][]. Considering that normal users won't need this except when debugging performance problems, it's disabled by default. So it looks reasonable to keep this debug code simple rather than trying to improve its scalability.

...

mm/readahead.c +4 -0

@@ -51,6 +62,182 @@ EXPORT_SYMBOL_GPL(file_ra_state_init);
 
 #define list_to_page(head) (list_entry((head)->prev, struct page, lru))
 
+#ifdef CONFIG_READAHEAD_STATS
+#include <linux/seq_file.h>
+#include <linux/debugfs.h>
+

mm/readahead.c +20 -0

+	RA_ACCOUNT_IOCOUNT,	/* readahead IO */
+	RA_ACCOUNT_SYNC,	/* readahead IO that is synchronous */
+	RA_ACCOUNT_MMAP,	/* readahead IO by mmap page faults */
+	/* number of readahead pages */
+	RA_ACCOUNT_SIZE,	/* readahead size */
+	RA_ACCOUNT_ASIZE,	/* readahead async size */
+	RA_ACCOUNT_ACTUAL,	/* readahead actual IO size */
+	/* end mark */
+	RA_ACCOUNT_MAX,
+};
+
 
...
 
+static void readahead_event(struct address_space *mapping,
+			    pgoff_t offset,
+			    unsigned long req_size,
+			    unsigned int ra_flags,
+			    pgoff_t start,
+			    unsigned int size,
+			    unsigned int async_size,
+			    unsigned int actual)
+{

...

I may be wrong, but I don't think the CPU cost of this code matters a lot. People will rarely turn it on and disk IO is a lot slower than CPU actions and it's waaaaaaay more important to get high-quality info about readahead than it is to squeeze out a few CPU cycles.

Quoted 3 lines · On Mon, 21 Nov 2011 17:18:24 +0800 Wu Fengguang <[email protected]> wrote:

The accounting code will be compiled in by default (CONFIG_READAHEAD_STATS=y), and will remain inactive unless enabled explicitly with either boot option

Quoted 5 lines

readahead_stats=1

or through the debugfs interface

echo 1 > /debug/readahead/stats_enable

It's unfortunate that these two things have different names.

I'd have thought that the debugfs knob was sufficient - no need for the boot option.

Quoted 7 lines

The added overheads are two readahead_stats() calls per readahead. Which is trivial costs unless there are concurrent random reads on super fast SSDs, which may lead to cache bouncing when updating the global ra_stats[][]. Considering that normal users won't need this except when debugging performance problems, it's disabled by default. So it looks reasonable to keep this debug code simple rather than trying to improve its scalability.

I may be wrong, but I don't think the CPU cost of this code matters a lot. People will rarely turn it on and disk IO is a lot slower than CPU actions and it's waaaaaaay more important to get high-quality info about readahead than it is to squeeze out a few CPU cycles.

Quoted 4 lines

mm/readahead.c +0 -0

@@ -51,6 +62,182 @@ EXPORT_SYMBOL_GPL(file_ra_state_init);
 
 #define list_to_page(head) (list_entry((head)->prev, struct page, lru))
 

Quoted 4 lines

mm/readahead.c +4 -0

+#ifdef CONFIG_READAHEAD_STATS
+#include <linux/seq_file.h>
+#include <linux/debugfs.h>
+

mm/readahead.c EXPORT_SYMBOL_GPL(file_ra_state_init); · line 78

Quoted 10 lines

mm/readahead.c +10 -0

+static u32 readahead_stats_enable __read_mostly;
+
+static int __init config_readahead_stats(char *str)
+{
+	int enable = 1;
+	get_option(&str, &enable);
+	readahead_stats_enable = enable;
+	return 0;
+}
+early_param("readahead_stats", config_readahead_stats);

Why use early_param() rather than plain old __setup()?

mm/readahead.c EXPORT_SYMBOL_GPL(file_ra_state_init); · line 84

Quoted 5 lines

mm/readahead.c +5 -0

+enum ra_account {
+	/* number of readaheads */
+	RA_ACCOUNT_COUNT,	/* readahead request */
+	RA_ACCOUNT_EOF,		/* readahead request covers EOF */
+	RA_ACCOUNT_CHIT,	/* readahead request covers some cached pages */

I don't like chit :) "cache_hit" would be better. Or just "hit".

mm/readahead.c EXPORT_SYMBOL_GPL(file_ra_state_init); · line 90

Quoted 1 line

mm/readahead.c +1 -0

+	RA_ACCOUNT_ASIZE,	/* readahead async size */

Quoted 23 lines

mm/readahead.c +20 -0

+	RA_ACCOUNT_ACTUAL,	/* readahead actual IO size */
+	/* end mark */
+	RA_ACCOUNT_MAX,
+};
+
 
...
 
+static void readahead_event(struct address_space *mapping,
+			    pgoff_t offset,
+			    unsigned long req_size,
+			    unsigned int ra_flags,
+			    pgoff_t start,
+			    unsigned int size,
+			    unsigned int async_size,
+			    unsigned int actual)
+{
+#ifdef CONFIG_READAHEAD_STATS
+	if (readahead_stats_enable) {
+		readahead_stats(mapping, offset, req_size, ra_flags,
+				start, size, async_size, actual);
+		readahead_stats(mapping, offset, req_size,
+				RA_PATTERN_ALL << READAHEAD_PATTERN_SHIFT,

mm/readahead.c EXPORT_SYMBOL_GPL(file_ra_state_init); · line 239

Quoted 4 lines

mm/readahead.c +4 -0

+				start, size, async_size, actual);
+	}
+#endif
+}

The stub should be inlined, methinks. The overhead of evaluating and preparing eight arguments is significant. I don't think the compiler is yet smart enough to save us.

Quoted 9 lines

...

Documentation/kernel-parameters.txt +0 -0

@@ -2251,6 +2251,12 @@ bytes respectively. Such letter suffixes
 			This default max readahead size may be overrode
 			in some cases, notably NFS, btrfs and software RAID.
 

Documentation/kernel-parameters.txt bytes respectively. Such letter suffixes · line 2258

Quoted 5 lines

Documentation/kernel-parameters.txt +5 -0

+	readahead_stats[=0|1]
+			Enable/disable readahead stats accounting.
+
+			It's also possible to enable/disable it after boot:
+			echo 1 > /sys/kernel/debug/readahead/stats_enable

Can the current setting be read back?

Quoted 7 lines

Quoted 7 lines

mm/readahead.c +7 -0

+{
+#ifdef CONFIG_READAHEAD_STATS
+	if (readahead_stats_enable) {
+		readahead_stats(mapping, offset, req_size, ra_flags,
+				start, size, async_size, actual);
+		readahead_stats(mapping, offset, req_size,
+				RA_PATTERN_ALL << READAHEAD_PATTERN_SHIFT,

Quoted 8 lines

mm/readahead.c EXPORT_SYMBOL_GPL(file_ra_state_init); · line 239

Quoted 4 lines

mm/readahead.c +4 -0

+				start, size, async_size, actual);
+	}
+#endif
+}

The stub should be inlined, methinks. The overhead of evaluating and preparing eight arguments is significant. I don't think the compiler is yet smart enough to save us.

The parameter list actually becomes even out of control when doing the bit fields:

(quoted diff) +4 -0

+       readahead_event(mapping, offset, req_size,
+                       ra->pattern, ra->for_mmap, ra->for_metadata,
+                       ra->start + ra->size >= eof,
+                       ra->start, ra->size, ra->async_size, actual);

So I end up passing file_ra_state around. The added cost is, I'll have to dynamically create a file_ra_state for the fadvise case, which should be acceptable since it's a cold path.

Quoted 24 lines · On Tue, 29 Nov 2011 11:23:23 +0800 Wu Fengguang <[email protected]> wrote:

Quoted 7 lines

Quoted 7 lines

(quoted diff) +7 -0

+{
+#ifdef CONFIG_READAHEAD_STATS
+	if (readahead_stats_enable) {
+		readahead_stats(mapping, offset, req_size, ra_flags,
+				start, size, async_size, actual);
+		readahead_stats(mapping, offset, req_size,
+				RA_PATTERN_ALL << READAHEAD_PATTERN_SHIFT,

Quoted 8 lines

Review

Quoted 4 lines

(quoted diff) +4 -0

+				start, size, async_size, actual);
+	}
+#endif
+}

The stub should be inlined, methinks. The overhead of evaluating and preparing eight arguments is significant. I don't think the compiler is yet smart enough to save us.

The parameter list actually becomes even out of control when doing the bit fields:

(quoted diff) +4 -0

+       readahead_event(mapping, offset, req_size,
+                       ra->pattern, ra->for_mmap, ra->for_metadata,
+                       ra->start + ra->size >= eof,
+                       ra->start, ra->size, ra->async_size, actual);

Quoted 3 lines

So I end up passing file_ra_state around. The added cost is, I'll have to dynamically create a file_ra_state for the fadvise case, which should be acceptable since it's a cold path.

That will reduce the cost of something which would have zero cost by making this function a static inline when CONFIG_READAHEAD_STATS=n.

int force_page_cache_readahead(struct address_space *mapping, struct file *filp,

mm/readahead.c +3 -0

 		pgoff_t offset, unsigned long nr_to_read)
 {
+	struct file_ra_state fadvice_ra = {
+		.pattern	= RA_PATTERN_FADVISE,
+	};
 	int ret = 0;
 
 	if (unlikely(!mapping->a_ops->readpage && !mapping->a_ops->readpages))

@@ -222,8 +397,9 @@ int force_page_cache_readahead(struct ad
 

plain text document attachment (readahead-tracer.patch) This is very useful for verifying whether the algorithms are working to our expectaions.

Example output:

# echo 1 > /debug/tracing/events/vfs/readahead/enable
# cp test-file /dev/null
# cat /debug/tracing/trace  # trimmed output
readahead-initial(dev=0:15, ino=100177, req=0+2, ra=0+4-2, async=0) = 4
readahead-subsequent(dev=0:15, ino=100177, req=2+2, ra=4+8-8, async=1) = 8
readahead-subsequent(dev=0:15, ino=100177, req=4+2, ra=12+16-16, async=1) = 16
readahead-subsequent(dev=0:15, ino=100177, req=12+2, ra=28+32-32, async=1) = 32
readahead-subsequent(dev=0:15, ino=100177, req=28+2, ra=60+60-60, async=1) = 24
readahead-subsequent(dev=0:15, ino=100177, req=60+2, ra=120+60-60, async=1) = 0

CC Ingo Molnar <[email protected]>

CC Jens Axboe <[email protected]>

CC Steven Rostedt <[email protected]>

CC Peter Zijlstra <[email protected]>

Acked-by Rik van Riel <[email protected]>

Signed-off-by Wu Fengguang <[email protected]>

Add the backwards prefetching feature. It's pretty simple if we don't support async prefetching and interleaved reads.

Quoted 2 lines · On Mon, 21 Nov 2011 17:18:26 +0800 Wu Fengguang <[email protected]> wrote:

Add the backwards prefetching feature. It's pretty simple if we don't support async prefetching and interleaved reads.

Well OK, but I wonder how many applications out there read files in reverse order. Is it common enough to bother special-casing in the kernel like this?

Some applications (eg. blkid, id3tool etc.) seek around the file to get information. For example, blkid does

	     seek to	0
	     read	1024
	     seek to	1536
	     read	16384

The start-of-file readahead heuristic is wrong for them, whose access pattern can be identified by lseek() calls.

Acked-by Rik van Riel <[email protected]>

Acked-by Linus Torvalds <[email protected]>

Signed-off-by Wu Fengguang <[email protected]>

---
 fs/read_write.c    |    4 ++++
 include/linux/fs.h |    1 +
 mm/readahead.c     |    3 +++
 3 files changed, 8 insertions(+)

mm/readahead.c +3 -0

@@ -629,6 +629,8 @@ ondemand_readahead(struct address_space 
 	 * start of file
 	 */
 	if (!offset) {
+		if ((ra->ra_flags & READAHEAD_LSEEK) && req_size < max)
+			goto random_read;
 		ra_set_pattern(ra, RA_PATTERN_INITIAL);
 		goto initial_readahead;
 	}

@@ -707,6 +709,7 @@ ondemand_readahead(struct address_space 
 	if (try_context_readahead(mapping, ra, offset, req_size, max))
 		goto readit;
 
+random_read:
 	/*
 	 * standalone, small random read
 	 */

Quoted 6 lines

fs/read_write.c +0 -0

@@ -47,6 +47,10 @@ static loff_t lseek_execute(struct file 
 		file->f_pos = offset;
 		file->f_version = 0;
 	}

fs/read_write.c static loff_t lseek_execute(struct file · line 55

Quoted 6 lines

fs/read_write.c +4 -0

+
+	if (!(file->f_ra.ra_flags & READAHEAD_LSEEK))
+		file->f_ra.ra_flags |= READAHEAD_LSEEK;
+
 	return offset;
 }

Confused. How does READAHEAD_LSEEK get cleared again?

Andrew,

I'm getting around to pick up the readahead works again :-)

This first series is mainly to add some debug facilities, to support the long missed backwards prefetching capability, and some old patches that somehow get delayed (shame me).

The next step would be to better handle the readahead thrashing situations. That would require rewriting part of the algorithms, this is why I'd like to keep the backwards prefetching simple and stupid for now.

When (almost) free of readahead thrashing, we'll be in a good position to lift the default readahead size. Which I suspect would be the single most efficient way to improve performance for the large volumes of casually maintained Linux file servers.

Quoted 8 lines · Wu Fengguang

Andrew,

I'm getting around to pick up the readahead works again :-)

This first series is mainly to add some debug facilities, to support the long missed backwards prefetching capability, and some old patches that somehow get delayed (shame me).

Quoted 8 lines

The next step would be to better handle the readahead thrashing situations. That would require rewriting part of the algorithms, this is why I'd like to keep the backwards prefetching simple and stupid for now.

When (almost) free of readahead thrashing, we'll be in a good position to lift the default readahead size. Which I suspect would be the single most efficient way to improve performance for the large volumes of casually maintained Linux file servers.

Btw, if you work actively in that area I have a todo list item I was planning to look into sooner or later: instead of embedding the ra state into the struct file allocate it dynamically. That way files that either don't use the pagecache, or aren't read from won't need have to pay the price for increasing struct file size, and if we have to we could enlarge it more easily.

Besides removing f_version in the common
struct file and also allocting f_owner separately that seem to be the easiest ways to get struct file size down.