Re: linux-2.4.26 released

[William Lee Irwin III <wli@holomorphy.com>]

On Tue, Apr 20, 2004 at 04:23:12PM -0700, William Lee Irwin III wrote:
>> -		return (mps_cpu/4)*16 + (1<<(mps_cpu%4));
>> +		return (mps_cpu & ~0x3) << 2 | 1 << (mps_cpu & 0x3);

On Wed, Apr 21, 2004 at 06:53:44AM +0200, Willy Tarreau wrote:
> I think you wanted to put '<< 4' here instead of '<< 2'. Also, could you
> put (useless for some) parenthesis to group the left side and the right
> side of the bit-wise OR ? I'm always scared that someone changes it to
> an addition with good intentions and changes the operators precedence
> without noticing.

The important thing here is the bit movement.

apicid[7]:	mps_cpu[5]
apicid[6]:	mps_cpu[4]
apicid[5]:	mps_cpu[3]
apicid[4]:	mps_cpu[2]
apicid[3]:	mps_cpu[1] && mps_cpu[0]	|
apicid[2]:	mps_cpu[1] && !mps_cpu[0]	|  == 1 << mps_cpu[0:1]
apicid[1]:	!mps_cpu[1] && mps_cpu[0]	|
apicid[0]:	!mps_cpu[1] && !mps_cpu[0]	|

apicid[4:7] and mps_cpu[2:5] encode the cluster ID for use by the
clustered hierarchical DFR local APIC ID settings (which in this case
are done by the BIOS, not the OS). apicid[0:3] is an architecturally
defined cluster-local cpumask, which as it's 4 bits, only needs 2 bits
to densely encode within mps_cpu[0:1]. The mps_cpu values are basically
BIOS-defined and the mps_cpu values are computed from auxiliary tables
provided by the BIOS in combination with the serial APIC's physical
APIC ID's (which are provided as 0, 1, 2, 4; the computation in mpparse.c
                logical_apicid = (quad << 4) + 
                        (m->mpc_apicid ? m->mpc_apicid << 1 : 1);
is easily tabulated as (quad << 4) | one of 1 2 4 8. The way that the
various information is compacted into a NR_CPUS-sized array indexed by
the logical APIC ID is with the computation carrying the clustered
hierarchical logical APIC ID to the | of the cluster ID shifted right
by 2, and the __ffs() of the lower 4 bits of the logical APIC ID (the
"local" logical APIC ID) so as to match later-used mps_cpu values. It
appears, though, that the majority of the arrays indexed in this way,
e.g. bios_cpu[], have been removed (excepting raw_phys_apicid[] etc.).

So the proof of all this is:

(a) mps_cpu % 4 == mps_cpu & 0x3
	The right side of the | is equal to the right side of the +
(b) (mps_cpu & ~0x3) << 2
		== mps_cpu[3:7] << 4
		== (mps_cpu/4) << 4
		== 16*(mps_cpu/4)
	The left side of the | is equal to the left side of the +
(c) ((mps_cpu & ~0x3) << 2) & (1 << (mps_cpu & 0x3))
		== (mps_cpu[3:7] << 4) & (1 << (mps_cpu & 0x3))
		== 0
	Because shifting 1 by mps_cpu & 0x3 on the left can set no bit
	higher than 3, but the right side is shifted left by 4, which
	is out of its reach.
	So there are no carries, and the | is equivalent to the +.

The ~, <<, &, and | version clarifies the bit movement. The definitions
are in terms of bit extraction, which matches the patch more closely
than the in-tree arithmetic definition.


-- wli