Add dynamic writeback feature from 3.1
arm: Allow CPU-supported unaligned accesses

Conflicts:

	arch/arm/kernel/head-nommu.S
	arch/arm/kernel/head.S

Conflicts:
	arch/arm/kernel/head.S
patch: add SLQB memory allocator by Nick Piggin
crc32: move to documentation

Moved a long comment from lib/crc32.c to Documentation/crc32.txt where it will more likely get read.
- Edited the resulting document to add an explanation of the slicing-by-n algorithm.

Signed-off-by: George Spelvin <linux@horizon.com>
Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>

Conflicts:
	lib/crc32.c
crc32: replace self test

Replaced the unit test provided in crc32.c, which doesn't have a makefile and doesn't
compile with current headers, with a simpler self test
routine that also gives a measure of performance and runs
at module init time. The self test option can be enabled
through a configuration option CONFIG_CRC32_SELFTEST.

The test stresses the pre and post loops and is thus not very
realistic since actual uses will likely have addresses and lengths
that are at least 4 byte aligned. However, the main loop is long
enough so that the performance is dominated by that loop.

The expected values for crc32_le and crc32_be were generated
with the original version of crc32.c using CRC_BITS_LE = 8 and
CRC_BITS_BE = 8. These values were then used to check all the
values of the BITS parameters in both the original and new versions.

The performance results show some variability from run to run
in spite of attempts to both warm the cache and reduce the amount
of OS noise by limiting interrutps during the test. To get comparable
results and to analyse options wrt performance the best time
reported over a small sample of runs has been taken.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: add pointer to tab

Replace 2D array references by pointer references in loops.
This change has no effect on X86 code but improves PPC performance.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: misc cleanup

Misc cleanup of lib/crc32.c and related files
- removed unnecessary header files.
- straightened out some convoluted ifdef's
- rewrote some references to 2 dimensional arrays as 1 dimensional arrays
to make them correct. I.e. replaced tab[i] with tab[0][i].
- a few trivial whitespace changes
- fixed a warning in gen_crc32tables.c caused by a mismatch in the
type of the pointer passed to output table. Since the table is
only used at kernel compile time, it is simpler to make the table
big enough to hold the largest column size used. One cannot make the
column size smaller in output_table because it has to be used by
both the le and be tables and they can have different column sizes.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: fix check endian warnings

in its original version freely mixed u32, __le32 and __be32 types which
caused warnings from sparse with __CHECK_ENDIAN__. This
patch fixes these by forcing the types to u32.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: add real 8 bit

crc32.c provides a choice of one of several algorithms for computing
the LSB and LSB versions of the CRC32 checksum based on the parameters
CRC_LE_BITS and CRC_BE_BITS. In the original version the
values 1, 2, 4 and 8 respectively selected versions of the
alrogithm that computed the crc 1, 2, 4 and 32 bits as a
time. This patch series adds a new version that computes
the CRC 64 bits at a time. To make things easier to
understand the parameter has been reinterpreted to actually
stand for the number of bits processed in each step of the
algorithm so that the old value 8 has been replaced with
the value 32. This also allows us to add in a widely used
crc algorithm that computes the crc 8 bits at a time called
the Sarwate algorithm.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>

Conflicts:
	lib/crc32defs.h
crc32: add slicing by 8

add slicing-by-8 algorithm to the existing slicing-by-4 algorithm.
This consists of:
- extend largest BITS size from 32 to 64
- extend tables from tab[4][256] to up to tab[8][256]
- Add code for inner loop.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
modified by faux123
crc32: optimize loops for x86

Add two changes that improve the performance of x86 systems
1. replace main loop with incrementing counter
this change improves the performance of the selftest
by about 5-6% on Nehalem CPUs. The apparent
reason is that the compiler can use the loop index
to perform an indexed memory access. This is
reported to make the performance of PowerPC CPUs
to get worse.

2. replace the rem_len loop with incrementing counter
this change improves the performance of the selftest,
which has more than the usual number of occurances,
by about 1-2% on x86 CPUs. In actual work loads
the length is most often a multiple of 4 bytes and
this code does not get executed as often if at all.
Again this change is reported to make the performance
of PowerPC get worse.

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: final

Some final changes
- added a comment at the top of crc32.c

Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
crc32: Bolt on crc32c

Reuse the existing crc32 code to stamp out a crc32c implementation

Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
crc32: Add self-test code for crc32c

Add self-test code for crc32c.

Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
crypto: crc32c should use library implementation

Since lib/crc32.c now provides crc32c, remove the software
implementation here and call the library function instead.

Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
crc32: Select an algorithm via kconfig

Allow the kernel builder to choose a crc32* algorithm for the kernel.

Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
crc32: expose __crc32c_le to fix compilation error for crc32c
Tune deadline for flash devices
make default readahead size a kernel parameter
From: Nikanth Karthikesan <knikanth@suse.de>

Add new kernel parameter "readahead", which would be used instead of the
value of VM_MAX_READAHEAD. If the parameter is not specified, the default
of 128kb would be used.

CC: Ankit Jain <radical@gmail.com>
CC: Dave Chinner <david@fromorbit.com>
CC: Christian Ehrhardt <ehrhardt@linux.vnet.ibm.com>
Signed-off-by: Nikanth Karthikesan <knikanth@suse.de>
Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>
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 $rasize > /sys/block/$BDEV/queue/read_ahead_kb
		time dd if=/dev/$BDEV 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)

	rasize	1st run		2nd run
	----------------------------------
	  4k	123 MB/s	122 MB/s
	 16k  	153 MB/s	153 MB/s
	 32k	161 MB/s	162 MB/s
	 64k	167 MB/s	168 MB/s
	128k	197 MB/s	197 MB/s
	256k	217 MB/s	217 MB/s
	512k	238 MB/s	234 MB/s
	  1M	251 MB/s	248 MB/s
	  2M	259 MB/s	257 MB/s
==>	  4M	269 MB/s	264 MB/s
	  8M	266 MB/s	266 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

	  4k	29.6 MB/s	29.6 MB/s	29.6 MB/s
	 16k	52.1 MB/s	52.1 MB/s	52.1 MB/s
	 32k	61.5 MB/s	61.5 MB/s	61.5 MB/s
	 64k	67.2 MB/s	67.2 MB/s	67.1 MB/s
	128k	71.4 MB/s	71.3 MB/s	71.4 MB/s
	256k	73.4 MB/s	73.4 MB/s	73.3 MB/s
==>	512k	74.6 MB/s	74.6 MB/s	74.6 MB/s
	  1M	74.7 MB/s	74.6 MB/s	74.7 MB/s
	  2M	76.1 MB/s	74.6 MB/s	74.6 MB/s

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

	  4k	7.9 MB/s 	7.9 MB/s 	7.9 MB/s
	 16k	17.9 MB/s	17.9 MB/s	17.9 MB/s
	 32k	24.5 MB/s	24.5 MB/s	24.5 MB/s
	 64k	28.7 MB/s	28.7 MB/s	28.7 MB/s
	128k	28.8 MB/s	28.9 MB/s	28.9 MB/s
==>	256k	30.5 MB/s	30.5 MB/s	30.5 MB/s
	512k	30.9 MB/s	31.0 MB/s	30.9 MB/s
	  1M	31.0 MB/s	30.9 MB/s	30.9 MB/s
	  2M	30.9 MB/s	30.9 MB/s	30.9 MB/s

USB stick 4G SanDisk  Cruzer idVendor=0781, idProduct=5151

	  4k	6.4 MB/s 	6.4 MB/s 	6.4 MB/s
	 16k	13.4 MB/s	13.4 MB/s	13.2 MB/s
	 32k	17.8 MB/s	17.9 MB/s	17.8 MB/s
	 64k	21.3 MB/s	21.3 MB/s	21.2 MB/s
	128k	21.4 MB/s	21.4 MB/s	21.4 MB/s
==>	256k	23.3 MB/s	23.2 MB/s	23.2 MB/s
	512k	23.3 MB/s	23.8 MB/s	23.4 MB/s
	  1M	23.8 MB/s	23.4 MB/s	23.3 MB/s
	  2M	23.4 MB/s	23.2 MB/s	23.4 MB/s

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

	  4k	6.7 MB/s 	6.9 MB/s 	6.7 MB/s
	 16k	11.7 MB/s	11.7 MB/s	11.7 MB/s
	 32k	12.4 MB/s	12.4 MB/s	12.4 MB/s
   	 64k	13.4 MB/s	13.4 MB/s	13.4 MB/s
	128k	13.4 MB/s	13.4 MB/s	13.4 MB/s
==>	256k	13.6 MB/s	13.6 MB/s	13.6 MB/s
	512k	13.7 MB/s	13.7 MB/s	13.7 MB/s
	  1M	13.7 MB/s	13.7 MB/s	13.7 MB/s
	  2M	13.7 MB/s	13.7 MB/s	13.7 MB/s

64 MB, USB full speed (collected by Clemens Ladisch)
Bus 003 Device 003: ID 08ec:0011 M-Systems Flash Disk Pioneers DiskOnKey

	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: Vivek Goyal <vgoyal@redhat.com>
Tested-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>