[RFC PATCH 1/2] ARM: kernel: build MPIDR hash function data structure

[Lorenzo Pieralisi]

On Tue, Jun 04, 2013 at 06:31:33PM +0100, Nicolas Pitre wrote:
> On Tue, 4 Jun 2013, Lorenzo Pieralisi wrote:
> 
> > On ARM SMP systems, cores are identified by their MPIDR register.
> > The MPIDR guidelines in the ARM ARM do not provide strict enforcement of
> > MPIDR layout, only recommendations that, if followed, split the MPIDR
> > on ARM 32 bit platforms in three affinity levels. In multi-cluster
> > systems like big.LITTLE, if the affinity guidelines are followed, the
> > MPIDR can not be considered an index anymore. This means that the
> > association between logical CPU in the kernel and the HW CPU identifier
> > becomes somewhat more complicated requiring methods like hashing to
> > associate a given MPIDR to a CPU logical index, in order for the look-up
> > to be carried out in an efficient and scalable way.
> > 
> > This patch provides a function in the kernel that starting from the
> > cpu_logical_map, implement collision-free hashing of MPIDR values by checking
> > all significative bits of MPIDR affinity level bitfields. The hashing
> > can then be carried out through bits shifting and ORing; the resulting
> > hash algorithm is a collision-free though not minimal hash that can be
> > executed with few assembly instructions. The mpidr is filtered through a
> > mpidr mask that is built by checking all bits that toggle in the set of
> > MPIDRs corresponding to possible CPUs. Bits that do not toggle do not carry
> > information so they do not contribute to the resulting hash.
> > 
> > Pseudo code:
> > 
> > /* check all bits that toggle, so they are required */
> > for (i = 1, mpidr_mask = 0; i < num_possible_cpus(); i++)
> > 	mpidr_mask |= (cpu_logical_map(i) ^ cpu_logical_map(0));
> > 
> > /*
> >  * Build shifts to be applied to aff0, aff1, aff2 values to hash the mpidr
> >  * fls() returns the last bit set in a word, 0 if none
> >  * ffs() returns the first bit set in a word, 0 if none
> >  */
> > fs0 = mpidr_mask[7:0] ? ffs(mpidr_mask[7:0]) - 1 : 0;
> > fs1 = mpidr_mask[15:8] ? ffs(mpidr_mask[15:8]) - 1 : 0;
> > fs2 = mpidr_mask[23:16] ? ffs(mpidr_mask[23:16]) - 1 : 0;
> > ls0 = fls(mpidr_mask[7:0]);
> > ls1 = fls(mpidr_mask[15:8]);
> > ls2 = fls(mpidr_mask[23:16]);
> > bits0 = ls0 - fs0;
> > bits1 = ls1 - fs1;
> > bits2 = ls2 - fs2;
> > aff0_shift = fs0;
> > aff1_shift = 8 + fs1 - bits0;
> > aff2_shift = 16 + fs2 - (bits0 + bits1);
> > u32 hash(u32 mpidr) {
> > 	u32 l0, l1, l2;
> > 	u32 mpidr_masked = mpidr & mpidr_mask;
> > 	l0 = mpidr_masked & 0xff;
> > 	l1 = mpidr_masked & 0xff00;
> > 	l2 = mpidr_masked & 0xff0000;
> > 	return (l0 >> aff0_shift | l1 >> aff1_shift | l2 >> aff2_shift);
> > }
> > 
> > The hashing algorithm relies on the inherent properties set in the ARM ARM
> > recommendations for the MPIDR. Exotic configurations, where for instance the
> > MPIDR values at a given affinity level have large holes, can end up requiring
> > big hash tables since the compression of values that can be achieved through
> > shifting is somewhat crippled when holes are present. Kernel warns if
> > the number of buckets of the resulting hash table exceeds the number of
> > possible CPUs by a factor of 4, which is a symptom of a very sparse HW
> > MPIDR configuration.
> > 
> > The hash algorithm is quite simple and can easily be implemented in assembly
> > code, to be used in code paths where the kernel virtual address space is
> > not set-up (ie cpu_resume) and instruction and data fetches are strongly
> > ordered so code must be compact and must carry out few data accesses.
> > 
> > Cc: Dave Martin <dave.martin at arm.com>
> > Cc: Will Deacon <will.deacon at arm.com>
> > Cc: Catalin Marinas <catalin.marinas at arm.com>
> > Cc: Russell King <linux at arm.linux.org.uk>
> > Cc: Nicolas Pitre <nicolas.pitre at linaro.org>
> > Cc: Colin Cross <ccross at android.com>
> > Cc: Santosh Shilimkar <santosh.shilimkar at ti.com>
> > Cc: Daniel Lezcano <daniel.lezcano at linaro.org>
> > Cc: Amit Kucheria <amit.kucheria at linaro.org>
> > Signed-off-by: Lorenzo Pieralisi <lorenzo.pieralisi at arm.com>
> 
> Reviewed-by: Nicolas Pitre <nico at linaro.org>

Thank you very much !
Lorenzo