| 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
| ||
|
Date: Thu, 21 May 2015 16:03:14 +0200
From: Ingo Molnar <mingo@...nel.org>
To: Denys Vlasenko <dvlasenk@...hat.com>
Cc: Linus Torvalds <torvalds@...ux-foundation.org>,
Andy Lutomirski <luto@...capital.net>,
Davidlohr Bueso <dave@...olabs.net>,
Peter Anvin <hpa@...or.com>,
Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
Tim Chen <tim.c.chen@...ux.intel.com>,
Borislav Petkov <bp@...en8.de>,
Peter Zijlstra <peterz@...radead.org>,
"Chandramouleeswaran, Aswin" <aswin@...com>,
Peter Zijlstra <a.p.zijlstra@...llo.nl>,
Brian Gerst <brgerst@...il.com>,
Paul McKenney <paulmck@...ux.vnet.ibm.com>,
Thomas Gleixner <tglx@...utronix.de>,
Jason Low <jason.low2@...com>,
"linux-tip-commits@...r.kernel.org"
<linux-tip-commits@...r.kernel.org>,
Arjan van de Ven <arjan@...radead.org>,
Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: [RFC PATCH] x86/64: Optimize the effective instruction cache
footprint of kernel functions
* Denys Vlasenko <dvlasenk@...hat.com> wrote:
> > The AMD system, with a starkly different x86 microarchitecture, is
> > showing similar characteristics:
> >
> > linux-falign-functions=_64-bytes/res-amd.txt: 108,886,550 L1-icache-load-misses ( +- 0.10% ) (100.00%)
> > linux-falign-functions=_32-bytes/res-amd.txt: 110,433,214 L1-icache-load-misses ( +- 0.15% ) (100.00%)
> > linux-falign-functions=__1-bytes/res-amd.txt: 113,623,200 L1-icache-load-misses ( +- 0.17% ) (100.00%)
> > linux-falign-functions=128-bytes/res-amd.txt: 119,100,216 L1-icache-load-misses ( +- 0.22% ) (100.00%)
> > linux-falign-functions=_16-bytes/res-amd.txt: 122,916,937 L1-icache-load-misses ( +- 0.15% ) (100.00%)
> > linux-falign-functions=__8-bytes/res-amd.txt: 123,810,566 L1-icache-load-misses ( +- 0.18% ) (100.00%)
> > linux-falign-functions=__2-bytes/res-amd.txt: 124,337,908 L1-icache-load-misses ( +- 0.71% ) (100.00%)
> > linux-falign-functions=__4-bytes/res-amd.txt: 125,221,805 L1-icache-load-misses ( +- 0.09% ) (100.00%)
> > linux-falign-functions=256-bytes/res-amd.txt: 135,761,433 L1-icache-load-misses ( +- 0.18% ) (100.00%)
> > linux-____CC_OPTIMIZE_FOR_SIZE=y/res-amd.txt: 159,918,181 L1-icache-load-misses ( +- 0.10% ) (100.00%)
> > linux-falign-functions=512-bytes/res-amd.txt: 170,307,064 L1-icache-load-misses ( +- 0.26% ) (100.00%)
> >
> > 64 bytes is a similar sweet spot. Note that the penalty at 512 bytes
> > is much steeper than on Intel systems: cache associativity is likely
> > lower on this AMD CPU.
> >
> > Interestingly the 1 byte alignment result is still pretty good on AMD
> > systems - and I used the exact same kernel image on both systems, so
> > the layout of the functions is exactly the same.
> >
> > Elapsed time is noisier, but shows a similar trend:
> >
> > linux-falign-functions=_64-bytes/res-amd.txt: 1.928409143 seconds time elapsed ( +- 2.74% )
> > linux-falign-functions=128-bytes/res-amd.txt: 1.932961745 seconds time elapsed ( +- 2.18% )
> > linux-falign-functions=__8-bytes/res-amd.txt: 1.940703051 seconds time elapsed ( +- 1.84% )
> > linux-falign-functions=__1-bytes/res-amd.txt: 1.940744001 seconds time elapsed ( +- 2.15% )
> > linux-falign-functions=_32-bytes/res-amd.txt: 1.962074787 seconds time elapsed ( +- 2.38% )
> > linux-falign-functions=_16-bytes/res-amd.txt: 2.000941789 seconds time elapsed ( +- 1.18% )
> > linux-falign-functions=__4-bytes/res-amd.txt: 2.002305627 seconds time elapsed ( +- 2.75% )
> > linux-falign-functions=256-bytes/res-amd.txt: 2.003218532 seconds time elapsed ( +- 3.16% )
> > linux-falign-functions=__2-bytes/res-amd.txt: 2.031252839 seconds time elapsed ( +- 1.77% )
> > linux-falign-functions=512-bytes/res-amd.txt: 2.080632439 seconds time elapsed ( +- 1.06% )
> > linux-____CC_OPTIMIZE_FOR_SIZE=y/res-amd.txt: 2.346644318 seconds time elapsed ( +- 2.19% )
> >
> > 64 bytes alignment is the sweet spot here as well, it's 3.7%
> > faster than the default 16 bytes alignment.
>
> In AMD, 64 bytes win too, yes, but by a *very* small margin. 8 bytes
> and 1 byte alignments have basically same timings, and both take
> what, +0.63% of time longer to run?
See my previous mail why this is a misleading conclusion: the timings
have so much stddev that they are not really comparable. But if you
look at the cachemiss you'll see the true difference:
linux-falign-functions=_64-bytes/res-amd.txt: 108,886,550 L1-icache-load-misses ( +- 0.10% ) (100.00%)
linux-falign-functions=__8-bytes/res-amd.txt: 123,810,566 L1-icache-load-misses ( +- 0.18% ) (100.00%)
linux-falign-functions=__1-bytes/res-amd.txt: 113,623,200 L1-icache-load-misses ( +- 0.17% ) (100.00%)
1 byte alignment isn't optimal on AMD either.
> > + #
> > + # Allocate a separate cacheline for every function,
> > + # for optimal instruction cache packing:
> > + #
> > + KBUILD_CFLAGS += -falign-functions=$(CONFIG_X86_FUNCTION_ALIGNMENT)
>
> How about -falign-functions=CONFIG_X86_FUNCTION_ALIGNMENT/2 + 1 instead?
>
> This avoids pathological cases where function starting just a few
> bytes after 64-bytes boundary gets aligned to the next one, wasting
> ~60 bytes.
Well, that should be pretty similar to the 32-byte aligned numbers I
already posted, right?
The 32-byte numbers are better than the default 16-byte alignment, but
64-byte alignment was even better.
A quick build shows:
text data bss dec hex filename
13534242 2579560 1634304 17748106 10ed08a linux-falign-functions=__1-bytes/vmlinux
13554530 2579560 1634304 17768394 10f1fca linux-falign-functions=__2-bytes/vmlinux
13590946 2579560 1634304 17804810 10fae0a linux-falign-functions=__4-bytes/vmlinux
13658786 2579560 1634304 17872650 110b70a linux-falign-functions=__8-bytes/vmlinux
13799602 2579560 1634304 18013466 112dd1a linux-falign-functions=_16-bytes/vmlinux
13943906 2579560 1634304 18157770 11510ca linux-falign-functions=_33-bytes/vmlinux [1]
14075330 2579560 1634304 18289194 117122a linux-falign-functions=_32-bytes/vmlinux [2]
14664898 2579560 1634304 18878762 120112a linux-falign-functions=_64-bytes/vmlinux
15980994 2579560 1634304 20194858 134262a linux-falign-functions=128-bytes/vmlinux
19038018 2591848 1634304 23264170 162fbaa linux-falign-functions=256-bytes/vmlinux
26391106 2591848 1634304 30617258 1d32eaa linux-falign-functions=512-bytes/vmlinux
Interestingly the -falign-functions=33 kernel is marginally smaller
than the -falign-functions=32 kernel, by 0.1%.
But the numbers aren't exceptional:
671,702,272 L1-icache-load-misses ( +- 0.06% ) (100.00%)
11,892,913,320 instructions ( +- 0.01% )
300,030 context-switches ( +- 0.00% )
7.349312237 seconds time elapsed ( +- 1.20% )
Compared to the others it's on rank 3:
linux-falign-functions=_64-bytes/res.txt: 647,853,942 L1-icache-load-misses ( +- 0.07% ) (100.00%)
linux-falign-functions=128-bytes/res.txt: 669,401,612 L1-icache-load-misses ( +- 0.08% ) (100.00%)
linux-falign-functions=_33-bytes/res.txt: [NEW] 671,702,272 L1-icache-load-misses ( +- 0.06% ) (100.00%)
linux-falign-functions=_32-bytes/res.txt: 685,969,043 L1-icache-load-misses ( +- 0.08% ) (100.00%)
linux-falign-functions=256-bytes/res.txt: 699,130,207 L1-icache-load-misses ( +- 0.06% ) (100.00%)
linux-falign-functions=512-bytes/res.txt: 699,130,207 L1-icache-load-misses ( +- 0.06% ) (100.00%)
linux-falign-functions=_16-bytes/res.txt: 706,080,917 L1-icache-load-misses [vanilla kernel] ( +- 0.05% ) (100.00%)
linux-falign-functions=__1-bytes/res.txt: 724,539,055 L1-icache-load-misses ( +- 0.31% ) (100.00%)
linux-falign-functions=__4-bytes/res.txt: 725,707,848 L1-icache-load-misses ( +- 0.12% ) (100.00%)
linux-falign-functions=__8-bytes/res.txt: 726,543,194 L1-icache-load-misses ( +- 0.04% ) (100.00%)
linux-falign-functions=__2-bytes/res.txt: 738,946,179 L1-icache-load-misses ( +- 0.12% ) (100.00%)
linux-____CC_OPTIMIZE_FOR_SIZE=y/res.txt: 921,910,808 L1-icache-load-misses ( +- 0.05% ) (100.00%)
So I still think the best strategy would be a variant of what I
mentioned before:
1) 'small functions': whose size is 1-63 bytes.
2) 'large functions': whose size is 64- bytes.
3) align all large functions to 64 bytes cachelines.
4) pack all small functions into remaining large function tail
holes, without them spilling over into the next cacheline
5) pack the remaining small functions with each other, tightly, as
long as they don't spill over to the next cacheline.
6) once optimization steps 1-5 are performed, for all cachelines
that contain small functions and still have a hole near the end
of the cacheline, allow functions to be aligned to 32/16/8/4/2
bytes as long as they still fit into the cacheline.
So for example lets consider this layout with tight packing:
[small-fn1][small-fn2][large-fn3...........................][small-fn4 ..... ][hole............]
[......... cacheline 1 ........][......... cacheline 2 ........][......... cacheline 3 ........]
Both 'fn3' and 'fn4' are on two cachelines.
After step 5 we'd get such a packing:
[small-fn1][small-fn2][hole....][large-fn3...........................][small-fn4 ..... ][hole..]
[......... cacheline 1 ........][......... cacheline 2 ........][......... cacheline 3 ........]
fn1, fn2 and fn4 each have their own cacheline, while large-fn3
necessarily has to spill into the next cacheline due to its size.
'fn4' is now on a single cache line.
After step 6 we'd get some extra intra-cacheline alignment by
utilizing the holes:
[small-fn1]..[small-fn2][hole..][large-fn3...........................]...[small-fn4 ..... ][hle]
[......... cacheline 1 ........][......... cacheline 2 ........][......... cacheline 3 ........]
Note how small-fn2 got moved forward by 2 bytes, to move it to an 8
bytes boundary and small-fn4 got moved forward by 3 bytes - at the
expense of the holes at the end of the cachelines.
This function alignment optimization basically minimizes the number of
cache line boundaries intersecting individual functions, so this
minimizes the I$ footprint aggressively.
This is not a trivial computation btw.: because even if we do this
only per .o object file we'd have to consider nr_fns! permutations of
all possible function ordering. We'd want to pick the ordering that
matches the above 1-6 constraints, _and_ which is as close to 'source
code ordering' as possible.
Such an optimization cannot be described via simple local alignment
rules like any variant of -falign-functions, as it requires reordering
of functions.
Thanks,
Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists