[PATCH] ppc64: improved VSID allocation algorithm

[PATCH] ppc64: improved VSID allocation algorithm

This patch has been tested both on SLB and segment table machines.  This
new approach is far from the final word in VSID/context allocation, but
it's a noticeable improvement on the old method.

Replace the VSID allocation algorithm.  The new algorithm first generates a
36-bit "proto-VSID" (with 0xfffffffff reserved).  For kernel addresses this
is equal to the ESID (address >> 28), for user addresses it is:

	(context << 15) | (esid & 0x7fff)

These are distinguishable from kernel proto-VSIDs because the top bit is
clear.  Proto-VSIDs with the top two bits equal to 0b10 are reserved for
now.

The proto-VSIDs are then scrambled into real VSIDs with the multiplicative
hash:

	VSID = (proto-VSID * VSID_MULTIPLIER) % VSID_MODULUS
	where	VSID_MULTIPLIER = 268435399 = 0xFFFFFC7
		VSID_MODULUS = 2^36-1 = 0xFFFFFFFFF

This scramble is 1:1, because VSID_MULTIPLIER and VSID_MODULUS are co-prime
since VSID_MULTIPLIER is prime (the largest 28-bit prime, in fact).

This scheme has a number of advantages over the old one:

- We now have VSIDs for every kernel address (i.e.  everything above
  0xC000000000000000), except the very top segment.  That simplifies a
  number of things.

- We allow for 15 significant bits of ESID for user addresses with 20
  bits of context.  i.e.  8T (43 bits) of address space for up to 1M
  contexts, significantly more than the old method (although we will need
  changes in the hash path and context allocation to take advantage of
  this).

- Because we use a real multiplicative hash function, we have better and
  more robust hash scattering with this VSID algorithm (at least based on
  some initial results).

Because the MODULUS is 2^n-1 we can use a trick to compute it efficiently
without a divide or extra multiply.  This makes the new algorithm barely
slower than the old one.

Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>