block: limit default readahead size for small devices .
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.

The formula is determined on the following data, collected by script:

#!/bin/sh

# please make sure BDEV is not mounted or opened by others
BDEV=sdb

for rasize in 4 16 32 64 128 256 512 1024 2048 4096 8192
do
echo  > /sys/block//queue/read_ahead_kb
time dd if=/dev/ of=/dev/null bs=4k count=102400
done
The principle is, the formula shall not limit readahead size to such a
degree that will impact some device's sequential read performance.

The Intel SSD is special in that its throughput increases steadily with
larger readahead size. However it may take years for Linux to increase
its default readahead size to 2MB, so we don't take it seriously in the
formula.

SSD 80G Intel x25-M SSDSA2M080 (reported by Li Shaohua)

rasize1st run2nd run
----------------------------------
  4k123 MB/s122 MB/s
 16k  153 MB/s153 MB/s
 32k161 MB/s162 MB/s
 64k167 MB/s168 MB/s
128k197 MB/s197 MB/s
256k217 MB/s217 MB/s
512k238 MB/s234 MB/s
  1M251 MB/s248 MB/s
  2M259 MB/s257 MB/s
==>  4M269 MB/s264 MB/s
  8M266 MB/s266 MB/s
Note that ==> points to the readahead size that yields plateau throughput.

SSD 22G MARVELL SD88SA02 MP1F (reported by Jens Axboe)

rasize  1st             2nd
--------------------------------
  4k     41 MB/s         41 MB/s
 16k     85 MB/s         81 MB/s
 32k    102 MB/s        109 MB/s
 64k    125 MB/s        144 MB/s
128k    183 MB/s        185 MB/s
256k    216 MB/s        216 MB/s
512k    216 MB/s        236 MB/s
1024k   251 MB/s        252 MB/s
  2M    258 MB/s        258 MB/s
==>       4M    266 MB/s        266 MB/s
  8M    266 MB/s        266 MB/s
SSD 30G SanDisk SATA 5000

  4k29.6 MB/s29.6 MB/s29.6 MB/s
 16k52.1 MB/s52.1 MB/s52.1 MB/s
 32k61.5 MB/s61.5 MB/s61.5 MB/s
 64k67.2 MB/s67.2 MB/s67.1 MB/s
128k71.4 MB/s71.3 MB/s71.4 MB/s
256k73.4 MB/s73.4 MB/s73.3 MB/s
==>512k74.6 MB/s74.6 MB/s74.6 MB/s
  1M74.7 MB/s74.6 MB/s74.7 MB/s
  2M76.1 MB/s74.6 MB/s74.6 MB/s

USB stick 32G Teclast CoolFlash idVendor=1307, idProduct=0165

  4k7.9 MB/s 7.9 MB/s 7.9 MB/s
 16k17.9 MB/s17.9 MB/s17.9 MB/s
 32k24.5 MB/s24.5 MB/s24.5 MB/s
 64k28.7 MB/s28.7 MB/s28.7 MB/s
128k28.8 MB/s28.9 MB/s28.9 MB/s
==>256k30.5 MB/s30.5 MB/s30.5 MB/s
512k30.9 MB/s31.0 MB/s30.9 MB/s
  1M31.0 MB/s30.9 MB/s30.9 MB/s
  2M30.9 MB/s30.9 MB/s30.9 MB/s

USB stick 4G

  4k6.4 MB/s 6.4 MB/s 6.4 MB/s
 16k13.4 MB/s13.4 MB/s13.2 MB/s
 32k17.8 MB/s17.9 MB/s17.8 MB/s
 64k21.3 MB/s21.3 MB/s21.2 MB/s
128k21.4 MB/s21.4 MB/s21.4 MB/s
==>256k23.3 MB/s23.2 MB/s23.2 MB/s
512k23.3 MB/s23.8 MB/s23.4 MB/s
  1M23.8 MB/s23.4 MB/s23.3 MB/s
  2M23.4 MB/s23.2 MB/s23.4 MB/s

USB stick 2G idVendor=0204, idProduct=6025 SerialNumber: 08082005000113

  4k6.7 MB/s 6.9 MB/s 6.7 MB/s
 16k11.7 MB/s11.7 MB/s11.7 MB/s
 32k12.4 MB/s12.4 MB/s12.4 MB/s
    64k13.4 MB/s13.4 MB/s13.4 MB/s
128k13.4 MB/s13.4 MB/s13.4 MB/s
==>256k13.6 MB/s13.6 MB/s13.6 MB/s
512k13.7 MB/s13.7 MB/s13.7 MB/s
  1M13.7 MB/s13.7 MB/s13.7 MB/s
  2M13.7 MB/s13.7 MB/s13.7 MB/s

64 MB, USB full speed (collected by Clemens Ladisch)
Bus

4KB:    139.339 s, 376 kB/s
16KB:   81.0427 s, 647 kB/s
32KB:   71.8513 s, 730 kB/s
==>64KB:   67.3872 s, 778 kB/s
128KB:  67.5434 s, 776 kB/s
256KB:  65.9019 s, 796 kB/s
512KB:  66.2282 s, 792 kB/s
1024KB: 67.4632 s, 777 kB/s
2048KB: 69.9759 s, 749 kB/s

An unnamed SD card (Yakui):

         4k     195.873 s,  5.5 MB/s
         8k     123.425 s,  8.7 MB/s
         16k    86.6425 s, 12.4 MB/s
         32k    66.7519 s, 16.1 MB/s
==>      64k    58.5262 s, 18.3 MB/s
         128k   59.3847 s, 18.1 MB/s
         256k   59.3188 s, 18.1 MB/s
         512k   59.0218 s, 18.2 MB/s

CC: Li Shaohua <shaohua.li@intel.com>
CC: Clemens Ladisch <clemens@ladisch.de>
Acked-by: Jens Axboe <jens.axboe@oracle.com>
Acked-by: Rik van Riel <riel@redhat.com>
Tested-by: Viv
Tested-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>