crc32: optimize inner loop

Taking a pointer reference to each row in the crc table matrix, one can
reduce the inner loop with a few insn's

Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se>
Cc: Bob Pearson <rpearson@systemfabricworks.com>
Cc: Frank Zago <fzago@systemfabricworks.com>
Cc: Eric Dumazet <eric.dumazet@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
crc32: miscellaneous cleanups

Misc cleanup of lib/crc32.c and related files.

- remove unnecessary header files.

- straighten out some convoluted ifdef's

- rewrite some references to 2 dimensional arrays as 1 dimensional
  arrays to make them correct.  I.e.  replace tab[i] with tab[0][i].

- a few trivial whitespace changes

- fix 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.

[djwong@us.ibm.com: Minor changelog tweaks]
Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
crc32: remove two instances of trailing whitespaces

This patchset (re)uses Bob Pearson's crc32 slice-by-8 code to stamp out
a software crc32c implementation.  It removes the crc32c implementation
in crypto/ in favor of using the stamped-out one in lib/.  There is also
a change to Kconfig so that the kernel builder can pick an
implementation best suited for the hardware.

The motivation for this patchset is that I am working on adding full
metadata checksumming to ext4.  As far as performance impact of adding
checksumming goes, I see nearly no change with a standard mail server
ffsb simulation.  On a test that involves only file creation and
deletion and extent tree writes, I see a drop of about 50 pcercent with
the current kernel crc32c implementation; this improves to a drop of
about 20 percent with the enclosed crc32c code.

When metadata is usually a small fraction of total IO, this new
implementation doesn't help much because metadata is usually a small
fraction of total IO.  However, when we are doing IO that is almost all
metadata (such as rm -rf'ing a tree), then this patch speeds up the
operation substantially.

Incidentally, given that iscsi, sctp, and btrfs also use crc32c, this
patchset should improve their speed as well.  I have not yet quantified
that, however.  This latest submission combines Bob's patches from late
August 2011 with mine so that they can be one coherent patch set.
Please excuse my inability to combine some of the patches; I've been
advised to leave Bob's patches alone and build atop them instead.  :/

Since the last posting, I've also collected some crc32c test results on
a bunch of different x86/powerpc/sparc platforms.  The results can be
viewed here: http://goo.gl/sgt3i ; the "crc32-kern-le" and "crc32c"
columns describe the performance of the kernel's current crc32 and
crc32c software implementations.  The "crc32c-by8-le" column shows
crc32c performance with this patchset applied.  I expect crc32
performance to be roughly the same.

The two _boost columns at the right side of the spreadsheet shows how much
faster the new implementation is over the old one.  As you can see, crc32
rises substantially, and crc32c experiences a huge increase.

This patch:

- remove trailing whitespace from lib/crc32.c
- remove trailing whitespace from lib/crc32defs.h

[djwong@us.ibm.com: changelog tweaks]
Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
crc32: move long comment about crc32 fundamentals to Documentation/

Move 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.

[djwong@us.ibm.com: minor changelog tweaks]
[akpm@linux-foundation.org: fix typo, per George]
Signed-off-by: George Spelvin <linux@horizon.com>
Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
crc32: simplify unit test code

Replace 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.

[djwong@us.ibm.com: Minor changelog tweaks]
Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
crc32: fix mixing of endian-specific types

crc32.c 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.

[djwong@us.ibm.com: Minor changelog tweaks]
Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
crc32: make CRC_*_BITS definition correspond to actual bit counts

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.

[djwong@us.ibm.com: Minor changelog tweaks]
Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
crc32: add slice-by-8 algorithm to existing code

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.

[djwong@us.ibm.com: Minor changelog tweaks]
Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
crc32: optimize loop counter 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.

[djwong@us.ibm.com: Minor changelog tweaks]
Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
crc32: add note about this patchset to crc32.c

Add a comment at the top of crc32.c

[djwong@us.ibm.com: Minor changelog tweaks]
Signed-off-by: Bob Pearson <rpearson@systemfabricworks.com>
Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
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>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: Bob Pearson <rpearson@systemfabricworks.com>
Cc: Randy Dunlap <rdunlap@xenotime.net>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
crc32: add self-test code for crc32c

Add self-test code for crc32c.

Signed-off-by: Darrick J. Wong <djwong@us.ibm.com>
Cc: Bob Pearson <rpearson@systemfabricworks.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
PM: OPP: Add opp_find_volt_floor/ceil functions

Add functions to find OPP by voltage value
in the same way as it is made for frequency.

Change-Id: Ic7250258de82ca02d4ee27cfa53bafc7de87685f
Signed-off-by: Taras Kondratiuk <taras@ti.com>
OMAP3+: PM: DVFS: Scale dependent domains to existing OPP

Currently dependent domain is scaled to:
 - dependent voltage that is got from voltage dependency table.
 - frequency that is got from OPP found for dependent voltage.

OPP for dependent voltage is found by _volt_to_opp() function
which looks for OPP with equal or _greater_ voltage.
So if there is no OPP with exact voltage (or this OPP is disabled),
then frequency from OPP with higher voltage will be used.

As a result device will run at not supported combination of frequency and voltage.
This may lead to instabilities.

This patch scales dependent domain to a correct voltage-frequency tuple,
by using both frequency and voltage from the matched OPP.

Change-Id: Ieb14be32ce2f6f2971ca0530dd077bb445a7e2f7
Signed-off-by: Taras Kondratiuk <taras@ti.com>
OMAP3+: PM: DVFS: add qos requirement to prevent interruptions

DVFS transitions are not meant to be interrupted as the interruptions
can cause severe mismatch in configuration sequences involved in DVFS.

We currently have omap_dvfs_lock check made in omap4_enter_sleep
function, however, considering cpuidle path:
a) omap4_enter_sleep is called by cpuidle's omap4_enter_idle_primary
   after the following steps:
   i) set the log state and set power domain state
   ii) WAIT FOR power domain state to transition!!!
  then we call omap4_enter_sleep
b) Now in omap4_enter_idle_secondary,
  GIC disabled, and we directly hit omap4_enter_lowpwer and goes down

We DONOT want this to take place when DVFS frequency configuration,
voltage programming and smartreflex AVS operations take place.

So request for QoS for the period of transition and release once operation
is done as it is less intrusive and takes care of CPU0 or CPU1 activity
to low power states as well.

Change-Id: I7731a3262bf88dd78e279a8c8306850e077865a5
Reported-by: Vinay Chaurasia <vinaych@ti.com>
Signed-off-by: Nishanth Menon <nm@ti.com>
OMAP3+: PM: DVFS: fix making wrong scale direction decision

In most cases with SmartReflex AVS class 3 and Class 1.5 calibration,
the SR adjusted voltage(Vsr) is usually lower than Vnom, However,
at times, the Vsr for a higher OPP may even be lower than a couple of
lower OPPs. For example, on a specific sample silicon on OMAP4430:
MPU OPP    Vsr                Vnom
OPP50      0.862249970436096  1.025
OPP100     1.03509700298309   1.2
OPPTurbo   1.09257805347443   1.325
OPPNitro   1.18703103065491   1.388
OPPNitroSB 1.29427194595337   1.398

Consider in the above case where we transition from OPPTurbo to OPP100
We are attempting to transition from 1.325V to 1.09V, if we pickup voltage
while SmartReflex AVS convergence is taking place, we might pickup 1.21V
which in effect is a scale down decision flag for DVFS. however,
since SR was active, it could make a jump of upto 8steps (100mV) lowering
the voltage to 1.1V after s/w sampled the voltage, which in reality
should have made SR to do a scale up operation.

This wrong scale direction can result in either dependent domain scale
combination to be performed wrongly OR even scale with lower voltage
for a given transition frequency resulting in device instability.

Fix the same by sampling the voltage only after stopping SmartReflex AVS
convergence.

Change-Id: I119a22b7060f30d123c4fe3bcabfadb6d7d71419
Signed-off-by: Nishanth Menon <nm@ti.com>

Conflicts:

	arch/arm/mach-omap2/dvfs.c
OMAP3+: PM: DVFS: decide to scale dependent domains based on nominal voltage

Current DVFS scale decision assumes voltage dependency - hence the scale
decision is implemented based on voltage transition decision. This is
wrong as the dependency between domains is at OPP tuple level, so
no matter what the voltage level is, if we transition from a lower
frequency to a higher frequency, we should scale dependent domain
ahead of transitioning voltage/frequency for the current domain,
and viceversa when switching to lower OPP.

With Smartreflex AVS Class3 or Smartreflex AVS Class1.5, consider
the following Scenario:
The current OPP might be in
Vnom (Vn) - if SR is disabled OR if SR has not yet made the first
   adjustment
Vcurrent(Vc) - which can either be:
	Vsr_intermdiate(Vi) - if SR was interrupted in the middle
		of convergence
	Vsr(Vs) - if SR has completed adjustment.

For all purposes Current OPP's Vn > Vc.
However, when we consider the new OPP we are entering (assume for
SR1.5, new OPP is not a calibrated opp in this discussion):
Going down, we have the following cases:
Case a) current_Vn > current_Vc > new_Vn
Case b) current_Vn > new_Vn > current_Vc
Going up, we could have:
Case c) new_Vn > current_Vn > current_Vc
OR we might even have a scenario
case d) current_Vn > (current_Vc == new_Vn)

Today's code compares current_Vc against new_Vn, and makes a decision
when to scale dependent domain. This will work find in case (a) and
case (c).

However, in case (b), we scale dependent domain at the wrong time,
in case of case (d), we dont even attempt to scale dependent domains!!

This is wrong. since the comparable factor which closely represents
the order of OPP is Vnom, the right thing to check for scaling dependent
domains is Vnom. Hence use it instead.

Change-Id: I93868743301e115fab8e33ff14317b07b81ef5d8
Signed-off-by: Nishanth Menon <nm@ti.com>
OMAP3+: voltage: omap_voltage_get_voltdata searches only for Vnom

Operational voltage comparisons are wrong in this search since we can
end up with scenarios such as the following:
OPP1 Volt_nominal == OPP2 Volt_calibrated
if the search for Volt_calibrated of OPP2 is done, if OPP1 appears
earlier in the array, this will result in returning the OPP1's
volt_data pointer which is wrong. In such a double match, there is no
real "correct selection" possible.

The current users of this function omap_voltage_get_voltdata are
dvfs.c and pm.c (setting up boot voltage) - both these use Vnom
for search, so it is safe to remove the check for operational voltage
and search for a match only for Vnom.

Change-Id: Ic8455cbd5a00dcc30e4989aa9db9b18c9da9741c
Signed-off-by: Nishanth Menon <nm@ti.com>
Signed-off-by: Grygorii Strashko <grygorii.strashko@ti.com>
OMAP3+: LDO: ensure that right ABB type is selected

since target_volt converted by omap_voltage_get_voltdata to get to
abb type for the OPP voltage level, we can have a scenario as follows:
OPP100 Vnom=1.2V, Vcalib = 0V(not calibrated) ABB type - bypass
OPPNitro Vnom=1.375, Vcalib = 1.2V ABB type = FBB
in this case, voltdm_scale will first gets the operational_voltage
of oppNitro and recieves 1.2V, sends it down to abb_prescale function
which in turn converts it back into vdata using
omap_voltage_get_voltdata
however, omap_voltage_get_voltdata walks through the volt_data array
and finds the first match of OPP100 where Vnom = 1.2V and returns
the volt_data pointer for OPP100, this causes ABB logic to think
that it is attempting to go to an OPP with bypass, which in effect
crashes the device once frequency is set to OPPNitro, but ABB is in
bypass mode.

To solve this, we should pass the exact volt_data pointer down to
the abb prescale and postscale handlers so that this back and forth
conversion error does not take place.

Change-Id: I49099caba069798d7bd8888c614fd5e2e27fab6f
Signed-off-by: Nishanth Menon <nm@ti.com>
Signed-off-by: Grygorii Strashko <grygorii.strashko@ti.com>
OMAP3+: ABB: make the pre and post scale decision based off Vnom

Currently the ABB LDO prescale and post scale configurations are
done based off voltdm_scale. However when Vsr(SR adjusted voltage)
of the current OPP is the same as Vnom(nominal voltage) of the new
OPP, this results in voltdm_scale not being called.

This has a side-effect of prescale and postscale of ABB not being
invoked either. In case where the new OPP requires FBB, this will
result in device failure.

The right procedure is to move the prescale and postscale notifier
out of the voltage scale API, instead have it on top of dvfs path
and depend on nominal voltage scaling direction to give a proper
trigger on need basis.

NOTE: ABB prescale is skipped in pm.c initial configuration to
take care of various types of bad and correct bootloader
configuration.

Change-Id: Ie953f515ab6182d6fa9be85d0ea83228db63d969
Signed-off-by: Nishanth Menon <nm@ti.com>