linux-kernel - Re: [PATCH] SLAB : use a multiply instead of a divide in obj_to

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <200612041918.29682.dada1@cosmosbay.com>
Date:	Mon, 4 Dec 2006 19:18:29 +0100
From:	Eric Dumazet <dada1@...mosbay.com>
To:	Christoph Lameter <clameter@....com>
Cc:	Andrew Morton <akpm@...l.org>, David Miller <davem@...emloft.net>,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH] SLAB : use a multiply instead of a divide in obj_to_index()

On Monday 04 December 2006 17:55, Christoph Lameter wrote:
> Could you generalize the reciprocal thingy so that the division
> can be used from other parts of the kernel as well? It would be useful to
> separately get some cycle counts on a regular division compared with your
> division. If that shows benefit then we may think about using it in the
> kernel. I am a bit surprised that this is still an issue on modern cpus.

OK I added a new include file, I am not sure it is the best way...

Well, AFAIK this particular divide is the only one that hurts performance on 
my machines.

Do you have in mind another spot in kernel where we could use this reciprocal 
divide as well ?

Yes divide complexity is still an issue with modern CPUS : 
elapsed time for 10^9 loops on Pentium M 1.6 Ghz
24 s for the version using divides
3.8 s for the version using multiplies

[PATCH] SLAB : use a multiply instead of a divide in obj_to_index()

When some objects are allocated by one CPU but freed by another CPU we can 
consume lot of cycles doing divides in obj_to_index().

(Typical load on a dual processor machine where network interrupts are handled 
by one particular CPU (allocating skbufs), and the other CPU is running the 
application (consuming and freeing skbufs))

Here on one production server (dual-core AMD Opteron 285), I noticed this 
divide took 1.20 % of CPU_CLK_UNHALTED events in kernel. But Opteron are 
quite modern cpus and the divide is much more expensive on oldest 
architectures :

On a 200 MHz sparcv9 machine, the division takes 64 cycles instead of 1 cycle 
for a multiply.

Doing some math, we can use a reciprocal multiplication instead of a divide.

If we want to compute V = (A / B)  (A and B being u32 quantities)
we can instead use :

V = ((u64)A * RECIPROCAL(B)) >> 32 ;

where RECIPROCAL(B) is precalculated to ((1LL << 32) + (B - 1)) / B

Note :

I wrote pure C code for clarity. gcc output for i386 is not optimal but 
acceptable :

mull   0x14(%ebx)
mov    %edx,%eax // part of the >> 32
xor     %edx,%edx // useless 
mov    %eax,(%esp) // could be avoided
mov    %edx,0x4(%esp) // useless
mov    (%esp),%ebx

Signed-off-by: Eric Dumazet <dada1@...mosbay.com>

View attachment "slab_avoid_divides.patch" of type "text/plain" (3014 bytes)