I am working on a project to make arch_get_unmapped_area(_topdown) scale
for processes with large numbers of VMAs, as well as unify the various
architecture specific variations into one common set of code that does
it all.
While trying to unify the page colouring code, I have run into a number
of bugs in both the ARM/MIPS implementation, and the x86-64 implementation.
Since one of the objects of my project is to get rid of the architecture
specific copies of code, it seems more practical to document the bugs in
the current code, rather than fix them first and then replace the code
later...
What I am asking for is a quick review of my analysis below, pointing
out my mistakes and getting a general feeling whether my proposed merger
of the various page colouring functions into one function that does it
all is something you would be ok with.
ARM & MIPS seem to share essentially the same page colouring code, with
these two bugs:
COLOUR_ALIGN_DOWN can use the pgoff % shm_align_mask either positively
or negatively, depending on the address initially found by
get_unmapped_area
static inline unsigned long COLOUR_ALIGN_DOWN(unsigned long addr,
unsigned long pgoff)
{
unsigned long base = addr & ~shm_align_mask;
unsigned long off = (pgoff << PAGE_SHIFT) & shm_align_mask;
if (base + off <= addr)
return base + off;
return base - off;
}
The fix would be to return an address that is a whole shm_align_mask
lower: (((base - shm_align_mask) & ~shm_align_mask) + off
The second bug relates to MAP_FIXED mappings of files. In the
MAP_FIXED conditional, arch_get_unmapped_area(_topdown) checks
whether the mapping is colour aligned, but only for MAP_SHARED
mappings.
/*
* We do not accept a shared mapping if it would violate
* cache aliasing constraints.
*/
if ((flags & MAP_SHARED) &&
((addr - (pgoff << PAGE_SHIFT)) & shm_align_mask))
return -EINVAL;
This fails to take into account that the same file might be mapped
MAP_SHARED from some programs, and MAP_PRIVATE from another. The
fix could be a simple as always enforcing colour alignment when we
are mmapping a file (filp is non-zero).
The page colouring code on x86-64, align_addr in sys_x86_64.c is
slightly more amusing.
For one, there are separate kernel boot arguments to control whether
32 and 64 bit processes need to have their addresses aligned for
page colouring.
Do we really need that?
Would it be a problem if I discarded that code, in order to get
to one common cache colouring implementation?
Secondly, MAP_FIXED never checks for page colouring alignment.
I assume the cache aliasing on AMD Bulldozer is merely a performance
issue, and we can simply ignore page colouring for MAP_FIXED?
That will be easy to get right in an architecture-independent
implementation.
A third issue is this:
if (!(current->flags & PF_RANDOMIZE))
return addr;
Do we really want to skip page colouring merely because the
application does not have PF_RANDOMIZE set? What is this
conditional supposed to do?
When an app calls mmap with address 0, what breaks by giving
it a properly page coloured address, instead of the first
suitable address we find?
The last issue with the page colouring for x86-64 is that it
does not take pgoff into account. In other words, if one
process maps a file starting at offset 0, and another one maps
the file starting at offset 1, both mappings start at the same
page colour and the mappings do not align right. This is easy
to fix, by making that aspect of the code similar to the ARM
and MIPS code.
--
All Rights Reversed
On Wed, Jun 13, 2012 at 03:29:36PM -0400, Rik van Riel wrote:
> ARM & MIPS seem to share essentially the same page colouring code, with
> these two bugs:
>
> COLOUR_ALIGN_DOWN can use the pgoff % shm_align_mask either positively
> or negatively, depending on the address initially found by
> get_unmapped_area
>
> static inline unsigned long COLOUR_ALIGN_DOWN(unsigned long addr,
> unsigned long pgoff)
> {
> unsigned long base = addr & ~shm_align_mask;
> unsigned long off = (pgoff << PAGE_SHIFT) & shm_align_mask;
>
> if (base + off <= addr)
> return base + off;
>
> return base - off;
> }
>
> The fix would be to return an address that is a whole shm_align_mask
> lower: (((base - shm_align_mask) & ~shm_align_mask) + off
'addr' in this case is already adjusted by callers of COLOUR_ALIGN_DOWN(), so
this shouldn't be an issue, unless I'm missing something?
> The second bug relates to MAP_FIXED mappings of files. In the
> MAP_FIXED conditional, arch_get_unmapped_area(_topdown) checks
> whether the mapping is colour aligned, but only for MAP_SHARED
> mappings.
>
> /*
> * We do not accept a shared mapping if it would violate
> * cache aliasing constraints.
> */
> if ((flags & MAP_SHARED) &&
> ((addr - (pgoff << PAGE_SHIFT)) & shm_align_mask))
> return -EINVAL;
>
These observations hold true for other architectures, too. I modelled the
SH implementation off of both MIPS and sparc, where these same patterns
exist. I would be surprised if there are any architectures that do
colouring in a different way.
The logic is such that in the MAP_FIXED case we can't align addr on to some
other boundary, and so anything that violates the aliasing constraints fails.
This is a departure from POSIX, and does occasionally lead to people sending in
patches to "correct" the behaviour for the LTP mmap01 testcase which does
iterative MAP_FIXED|MAP_SHARED PAGE_SIZE apart.
> This fails to take into account that the same file might be mapped
> MAP_SHARED from some programs, and MAP_PRIVATE from another. The
> fix could be a simple as always enforcing colour alignment when we
> are mmapping a file (filp is non-zero).
>
If that combination is possible then defaulting to colour alignment seems
reasonable. Whether that combination is reasonable or not is another matter.
On Wed, Jun 13, 2012 at 03:29:36PM -0400, Rik van Riel wrote:
> The page colouring code on x86-64, align_addr in sys_x86_64.c is
> slightly more amusing.
This was done with the reviewers' fun level in mind from the very start.
:-)
> For one, there are separate kernel boot arguments to control whether
> 32 and 64 bit processes need to have their addresses aligned for
> page colouring.
>
> Do we really need that?
Yes.
Mind you, this is only enabled on AMD F15h - all other x86 simply can't
tweak it without code change.
> Would it be a problem if I discarded that code, in order to get to one
> common cache colouring implementation?
Sorry, but, we'd like to keep it in.
> Secondly, MAP_FIXED never checks for page colouring alignment. I
> assume the cache aliasing on AMD Bulldozer is merely a performance
> issue, and we can simply ignore page colouring for MAP_FIXED?
Right, AFAICR, MAP_FIXED is not generally used for shared libs (correct
me if I'm wrong here, my memory is very fuzzy about it) and since we see
the perf issue with shared libs, this was fine.
> That will be easy to get right in an architecture-independent
> implementation.
>
>
> A third issue is this:
>
> if (!(current->flags & PF_RANDOMIZE))
> return addr;
>
> Do we really want to skip page colouring merely because the
> application does not have PF_RANDOMIZE set? What is this
> conditional supposed to do?
Linus said that without this we are probably breaking old userspace
which can't stomach ASLR so we had to respect such userspace which
clears that flag.
> When an app calls mmap with address 0, what breaks by giving it a
> properly page coloured address, instead of the first suitable address
> we find?
Look at dfb09f9b7ab03fd367740e541a5caf830ed56726.
We need bits slice [12:14] in the virtual address to be the same
across all processes mapping the same physical memory otherwise, the
cross-invalidations happen.
Thanks.
--
Regards/Gruss,
Boris.
Advanced Micro Devices GmbH
Einsteinring 24, 85609 Dornach
GM: Alberto Bozzo
Reg: Dornach, Landkreis Muenchen
HRB Nr. 43632 WEEE Registernr: 129 19551
On 06/14/2012 04:42 AM, Paul Mundt wrote:
> On Wed, Jun 13, 2012 at 03:29:36PM -0400, Rik van Riel wrote:
>> ARM& MIPS seem to share essentially the same page colouring code, with
>> these two bugs:
>>
>> COLOUR_ALIGN_DOWN can use the pgoff % shm_align_mask either positively
>> or negatively, depending on the address initially found by
>> get_unmapped_area
>>
>> static inline unsigned long COLOUR_ALIGN_DOWN(unsigned long addr,
>> unsigned long pgoff)
>> {
>> unsigned long base = addr& ~shm_align_mask;
>> unsigned long off = (pgoff<< PAGE_SHIFT)& shm_align_mask;
>>
>> if (base + off<= addr)
>> return base + off;
>>
>> return base - off;
>> }
>>
>> The fix would be to return an address that is a whole shm_align_mask
>> lower: (((base - shm_align_mask)& ~shm_align_mask) + off
>
> 'addr' in this case is already adjusted by callers of COLOUR_ALIGN_DOWN(), so
> this shouldn't be an issue, unless I'm missing something?
The problem is flipping the sign of "off".
Say you have 8 possible page colours, and the file is
being mapped at pgoff 1.
Depending on addr, you can either end up with the mmap
starting at colour 7, or at colour 1. If you have multiple
programs mapping the file, you could have one mapping starting
at colour 7, one at colour 1...
>> This fails to take into account that the same file might be mapped
>> MAP_SHARED from some programs, and MAP_PRIVATE from another. The
>> fix could be a simple as always enforcing colour alignment when we
>> are mmapping a file (filp is non-zero).
>>
> If that combination is possible then defaulting to colour alignment seems
> reasonable. Whether that combination is reasonable or not is another matter.
The combination is definitely possible. I do not know if
it is reasonable, but it seems like an easy fix to also
enforce colouring for MAP_PRIVATE file mappings.
--
All rights reversed
On 06/14/2012 06:36 AM, Borislav Petkov wrote:
> On Wed, Jun 13, 2012 at 03:29:36PM -0400, Rik van Riel wrote:
>> For one, there are separate kernel boot arguments to control whether
>> 32 and 64 bit processes need to have their addresses aligned for
>> page colouring.
>>
>> Do we really need that?
>
> Yes.
What do we need it for?
I can see wanting a big knob to disable page colouring
globally for both 32 and 64 bit processes, but why do
we need to control it separately?
I am not too keen on x86 keeping a slightly changed
private copy of arch_align_addr :)
> Mind you, this is only enabled on AMD F15h - all other x86 simply can't
> tweak it without code change.
>
>> Would it be a problem if I discarded that code, in order to get to one
>> common cache colouring implementation?
>
> Sorry, but, we'd like to keep it in.
What is it used for?
>> Secondly, MAP_FIXED never checks for page colouring alignment. I
>> assume the cache aliasing on AMD Bulldozer is merely a performance
>> issue, and we can simply ignore page colouring for MAP_FIXED?
>
> Right, AFAICR, MAP_FIXED is not generally used for shared libs (correct
> me if I'm wrong here, my memory is very fuzzy about it) and since we see
> the perf issue with shared libs, this was fine.
Try stracing /bin/mount one of these days. A whole bunch
of libraries are mapped with MAP_FIXED :)
However, I expect that on x86 many applications expect
MAP_FIXED to just work, and enforcing that would be
more trouble than it's worth.
>> That will be easy to get right in an architecture-independent
>> implementation.
>>
>>
>> A third issue is this:
>>
>> if (!(current->flags& PF_RANDOMIZE))
>> return addr;
>>
>> Do we really want to skip page colouring merely because the
>> application does not have PF_RANDOMIZE set? What is this
>> conditional supposed to do?
>
> Linus said that without this we are probably breaking old userspace
> which can't stomach ASLR so we had to respect such userspace which
> clears that flag.
I wonder if that is true, since those userspace programs
probably run fine on ARM, MIPS and other architectures...
--
All rights reversed
On Thu, Jun 14, 2012 at 08:57:50AM -0400, Rik van Riel wrote:
> On 06/14/2012 06:36 AM, Borislav Petkov wrote:
> >On Wed, Jun 13, 2012 at 03:29:36PM -0400, Rik van Riel wrote:
>
> >>For one, there are separate kernel boot arguments to control whether
> >>32 and 64 bit processes need to have their addresses aligned for
> >>page colouring.
> >>
> >>Do we really need that?
> >
> >Yes.
>
> What do we need it for?
>
> I can see wanting a big knob to disable page colouring
> globally for both 32 and 64 bit processes, but why do
> we need to control it separately?
Right, so for 32-bit we have 8 bits for ASLR and with our workaround, if
enabled on 32-bit, the randomness goes down to 5 bits. Thus, we wanted
to have it flexible and so the user can choose between randomization and
performance, depending on what he cares about.
> I am not too keen on x86 keeping a slightly changed private copy of
> arch_align_addr :)
x86 is special, you know that, right? :-)
> >Mind you, this is only enabled on AMD F15h - all other x86 simply can't
> >tweak it without code change.
> >
> >>Would it be a problem if I discarded that code, in order to get to one
> >>common cache colouring implementation?
> >
> >Sorry, but, we'd like to keep it in.
>
> What is it used for?
>From <Documentation/kernel-parameters.txt>:
align_va_addr= [X86-64]
Align virtual addresses by clearing slice [14:12] when
allocating a VMA at process creation time. This option
gives you up to 3% performance improvement on AMD F15h
machines (where it is enabled by default) for a
CPU-intensive style benchmark, and it can vary highly in
a microbenchmark depending on workload and compiler.
32: only for 32-bit processes
64: only for 64-bit processes
on: enable for both 32- and 64-bit processes
off: disable for both 32- and 64-bit processes
> >>Secondly, MAP_FIXED never checks for page colouring alignment. I
> >>assume the cache aliasing on AMD Bulldozer is merely a performance
> >>issue, and we can simply ignore page colouring for MAP_FIXED?
> >
> >Right, AFAICR, MAP_FIXED is not generally used for shared libs (correct
> >me if I'm wrong here, my memory is very fuzzy about it) and since we see
> >the perf issue with shared libs, this was fine.
>
> Try stracing /bin/mount one of these days. A whole bunch
> of libraries are mapped with MAP_FIXED :)
>
> However, I expect that on x86 many applications expect
> MAP_FIXED to just work, and enforcing that would be
> more trouble than it's worth.
Right, but if MAP_FIXED mappings succeed, then all processes sharing
that mapping will have it at the same virtual address, correct? And
if so, then we don't have the aliasing issue either so MAP_FIXED is a
don't-care from that perspective.
> >>That will be easy to get right in an architecture-independent
> >>implementation.
> >>
> >>
> >>A third issue is this:
> >>
> >> if (!(current->flags& PF_RANDOMIZE))
> >> return addr;
> >>
> >>Do we really want to skip page colouring merely because the
> >>application does not have PF_RANDOMIZE set? What is this
> >>conditional supposed to do?
> >
> >Linus said that without this we are probably breaking old userspace
> >which can't stomach ASLR so we had to respect such userspace which
> >clears that flag.
>
> I wonder if that is true, since those userspace programs
> probably run fine on ARM, MIPS and other architectures...
Well, I'm too young to know that :) Reportedly, those were some obscure
old binaries and we added the PF_RANDOMIZE check out of caution, so as
to not break them, if at all.
--
Regards/Gruss,
Boris.
Advanced Micro Devices GmbH
Einsteinring 24, 85609 Dornach
GM: Alberto Bozzo
Reg: Dornach, Landkreis Muenchen
HRB Nr. 43632 WEEE Registernr: 129 19551
On Wed, Jun 13, 2012 at 03:29:36PM -0400, Rik van Riel wrote:
> COLOUR_ALIGN_DOWN can use the pgoff % shm_align_mask either positively
> or negatively, depending on the address initially found by
> get_unmapped_area
>
> static inline unsigned long COLOUR_ALIGN_DOWN(unsigned long addr,
> unsigned long pgoff)
> {
> unsigned long base = addr & ~shm_align_mask;
> unsigned long off = (pgoff << PAGE_SHIFT) & shm_align_mask;
>
> if (base + off <= addr)
> return base + off;
>
> return base - off;
> }
Yes, that is bollocks code, introduced by this commit:
commit 7dbaa466780a754154531b44c2086f6618cee3a8
Author: Rob Herring <[email protected]>
Date: Tue Nov 22 04:01:07 2011 +0100
ARM: 7169/1: topdown mmap support
Similar to other architectures, this adds topdown mmap support in user
process address space allocation policy. This allows mmap sizes greater
than 2GB. This support is largely copied from MIPS and the generic
implementations.
The address space randomization is moved into arch_pick_mmap_layout.
Tested on V-Express with ubuntu and a mmap test from here:
https://bugs.launchpad.net/bugs/861296
Unfortunately, the test platform doesn't have aliasing data caches...
> The fix would be to return an address that is a whole shm_align_mask
> lower: (((base - shm_align_mask) & ~shm_align_mask) + off
Yes, agreed.
> The second bug relates to MAP_FIXED mappings of files. In the
> MAP_FIXED conditional, arch_get_unmapped_area(_topdown) checks
> whether the mapping is colour aligned, but only for MAP_SHARED
> mappings.
>
> /*
> * We do not accept a shared mapping if it would violate
> * cache aliasing constraints.
> */
> if ((flags & MAP_SHARED) &&
> ((addr - (pgoff << PAGE_SHIFT)) & shm_align_mask))
> return -EINVAL;
>
> This fails to take into account that the same file might be mapped
> MAP_SHARED from some programs, and MAP_PRIVATE from another. The
> fix could be a simple as always enforcing colour alignment when we
> are mmapping a file (filp is non-zero).
This brings up the question: should a MAP_PRIVATE mapping see updates
to the backing file made via a shared mapping and/or writing the file
directly? After all, a r/w MAP_PRIVATE mapping which has been CoW'd
won't see the updates.
So I'd argue that a file mapped MAP_SHARED must be mapped according to
the colour rules, but a MAP_PRIVATE is free not to be so.
> Secondly, MAP_FIXED never checks for page colouring alignment.
> I assume the cache aliasing on AMD Bulldozer is merely a performance
> issue, and we can simply ignore page colouring for MAP_FIXED?
> That will be easy to get right in an architecture-independent
> implementation.
There's a whole bunch of issues with MAP_FIXED, specifically address
space overflow has been discussed previously, and resulted in this patch:
[PATCH 0/6] get rid of extra check for TASK_SIZE in get_unmapped_area
That came from a patch adding a TASK_SIZE check to each and every gua
implementation, which I raised as silly as we had a common place it could
go. I'm not sure what's happened with that patch set, or where it's at.
On 06/14/2012 09:20 AM, Russell King - ARM Linux wrote:
> On Wed, Jun 13, 2012 at 03:29:36PM -0400, Rik van Riel wrote:
>> COLOUR_ALIGN_DOWN can use the pgoff % shm_align_mask either positively
>> or negatively, depending on the address initially found by
>> get_unmapped_area
>>
>> static inline unsigned long COLOUR_ALIGN_DOWN(unsigned long addr,
>> unsigned long pgoff)
>> {
>> unsigned long base = addr& ~shm_align_mask;
>> unsigned long off = (pgoff<< PAGE_SHIFT)& shm_align_mask;
>>
>> if (base + off<= addr)
>> return base + off;
>>
>> return base - off;
>> }
>
> Yes, that is bollocks code, introduced by this commit:
>
> commit 7dbaa466780a754154531b44c2086f6618cee3a8
> Author: Rob Herring<[email protected]>
> Date: Tue Nov 22 04:01:07 2011 +0100
It's not just ARM that has this bug. It appears to
be cut'n'pasted from other architectures (MIPS? SPARC?).
>> The fix would be to return an address that is a whole shm_align_mask
>> lower: (((base - shm_align_mask)& ~shm_align_mask) + off
>
> Yes, agreed.
I will make sure the arch-independent colouring
code does that.
> This brings up the question: should a MAP_PRIVATE mapping see updates
> to the backing file made via a shared mapping and/or writing the file
> directly? After all, a r/w MAP_PRIVATE mapping which has been CoW'd
> won't see the updates.
>
> So I'd argue that a file mapped MAP_SHARED must be mapped according to
> the colour rules, but a MAP_PRIVATE is free not to be so.
OK, fair enough.
>> Secondly, MAP_FIXED never checks for page colouring alignment.
>> I assume the cache aliasing on AMD Bulldozer is merely a performance
>> issue, and we can simply ignore page colouring for MAP_FIXED?
>> That will be easy to get right in an architecture-independent
>> implementation.
>
> There's a whole bunch of issues with MAP_FIXED, specifically address
> space overflow has been discussed previously, and resulted in this patch:
>
> [PATCH 0/6] get rid of extra check for TASK_SIZE in get_unmapped_area
Turns out, get_unmapped_area_prot (the function
that calls arch_get_unmapped_area) checks for
these overflows, so we should be fine.
On Thu, Jun 14, 2012 at 03:20:07PM +0200, Borislav Petkov wrote:
> > However, I expect that on x86 many applications expect
> > MAP_FIXED to just work, and enforcing that would be
> > more trouble than it's worth.
>
> Right, but if MAP_FIXED mappings succeed, then all processes sharing
> that mapping will have it at the same virtual address, correct? And
> if so, then we don't have the aliasing issue either so MAP_FIXED is a
> don't-care from that perspective.
Once upon a time every real program carried its own malloc around. I'm
sure many of these malloc implementations rely on MAP_FIXED.
These days the big user of MAP_FIXED is glibc's dynamic loader. It
doesn't use MAP_FIXED for the first segment, only for all subsequent
segments and the addresses are chosen such this will succeed. ld(1)
has the necessary knowledge about alignment.
Problem: If you raise the alignment for mappings you want to make damn
sure that any non-broken executable ever created uses sufficient alignment
or bad things may happen.
MIPS used to use a very large alignment in ld linker scripts allowing
for up to 1MB page size. Then somebody clueless who shall smoulder in
hell reduced it to a very small value, something like 4k or 16k. When
we went for bigger page size (MIPS allows 64K page size) all binaries
created with the broken linker had to be rebuilt.
So you probably want to do a little dumpster diving in very old binutils
before doing anything that raises alignment of file mappings.
> > >Linus said that without this we are probably breaking old userspace
> > >which can't stomach ASLR so we had to respect such userspace which
> > >clears that flag.
> >
> > I wonder if that is true, since those userspace programs
> > probably run fine on ARM, MIPS and other architectures...
>
> Well, I'm too young to know that :) Reportedly, those were some obscure
> old binaries and we added the PF_RANDOMIZE check out of caution, so as
> to not break them, if at all.
See above - ld linker scripts are a big part of why things are working :)
I'm however not aware of any breakage caused by PF_RANDOMIZE.
Ralf
On 06/14/2012 05:57 AM, Rik van Riel wrote:
>
> However, I expect that on x86 many applications expect
> MAP_FIXED to just work, and enforcing that would be
> more trouble than it's worth.
>
MAP_FIXED, is well, fixed. It means that performance be screwed, if we
can fulfill the request we MUST do so.
-hpa
On 06/14/2012 04:58 PM, H. Peter Anvin wrote:
> On 06/14/2012 05:57 AM, Rik van Riel wrote:
>>
>> However, I expect that on x86 many applications expect
>> MAP_FIXED to just work, and enforcing that would be
>> more trouble than it's worth.
>>
>
> MAP_FIXED, is well, fixed. It means that performance be screwed, if we
> can fulfill the request we MUST do so.
My codebase now has a separate arch_align_addr function
for x86, which is surprisingly similar to the generic
one :)
On 06/14/2012 02:03 PM, Rik van Riel wrote:
> On 06/14/2012 04:58 PM, H. Peter Anvin wrote:
>> On 06/14/2012 05:57 AM, Rik van Riel wrote:
>>>
>>> However, I expect that on x86 many applications expect
>>> MAP_FIXED to just work, and enforcing that would be
>>> more trouble than it's worth.
>>>
>>
>> MAP_FIXED, is well, fixed. It means that performance be screwed, if we
>> can fulfill the request we MUST do so.
>
> My codebase now has a separate arch_align_addr function
> for x86, which is surprisingly similar to the generic
> one :)
I am much more skeptical to disabling page coloring in the !PF_RANDOMIZE
case when no address hint is proposed. I would like to at least try
running without it, perhaps with a chicken bit in a sysctl.
-hpa
On 06/14/2012 05:13 PM, H. Peter Anvin wrote:
> I am much more skeptical to disabling page coloring in the !PF_RANDOMIZE
> case when no address hint is proposed. I would like to at least try
> running without it, perhaps with a chicken bit in a sysctl.
Agreed, it is hard to imagine a program that passes
address 0 to mmap, yet breaks when it gets a coloured
page address back...
I'll leave that bit of code untouched for now, we can
play with it later.