Add AlignedVector and use it for vector<MEMORY_BASIC_INFORMATION64>

Add AlignedVector and use it for vector<MEMORY_BASIC_INFORMATION64>

MEMORY_BASIC_INFORMATION64 specifies an alignment of 16, but the
standard allocator used by containers doesn't honor this. Although 16
is the default alignment size used on Windows for x86_64, it's not for
32-bit x86. clang assumed that the alignment of the structure was as
declared, and used an SSE load sequence that required this alignment.

AlignedAllocator is a replacement for std::allocator that allows the
alignment to be specified. AlignedVector is an std::vector<> that uses
AlignedAllocator instead of std::allocator.

BUG=chromium:564691
R=scottmg@chromium.org

Committed: https://chromium.googlesource.com/crashpad/crashpad/+/f55d18ade6877134e87515d9e2fc332dd40dea19

[Mark Mentovai, 2015-12-04 18:11:14]

mark@chromium.org changed reviewers:
+ scottmg@chromium.org

[scottmg, 2015-12-04 18:18:21]

According to the docs, the alignment declartion only applies to stack and static
allocations, so I'm not sure there's anything really wrong with the current
code.

[Nico, 2015-12-04 18:20:09]

thakis@chromium.org changed reviewers:
+ thakis@chromium.org

[Nico, 2015-12-04 18:20:10]

Yeah, I kind of feel that clang needs to become more conservative here. rnk,
thoughts?

[scottmg, 2015-12-04 18:21:51]

(Also, if this is the only one we think we need to do this for, we could just as
well declare our own nonaligned MBI64, as there's no use for the alignment
anyway.)

[Nico, 2015-12-04 18:24:20]

On 2015/12/04 18:21:51, scottmg wrote:
> (Also, if this is the only one we think we need to do this for, we could just
as
> well declare our own nonaligned MBI64, as there's no use for the alignment
> anyway.)

(that's what we did for http://crbug.com/540897)

[Reid Kleckner, 2015-12-04 19:16:20]

On 2015/12/04 18:20:10, Nico wrote:
> Yeah, I kind of feel that clang needs to become more conservative here. rnk,
> thoughts?

I have a vague memory that Apple had to make clang more conservative on Darwin
in similar situations, but I can't reproduce it. Clang actually carefully tracks
where it got its alignment information from: either from the pointer type, or
from an actual stack or global variable. If we decide this is the right way to
go, we can cap our alignment assumptions from pointer types to be the alignment
provided by the system allocator, which is usually '2 * sizeof(void*)'.

Anyway, I emailed John about it. He's the one that would've done this and would
care about this change.

We should probably do something in crashpad in the meantime, though. This CL
works, or you could clone the MBI64 struct and not align it. If we decide to get
more conservative, we can rip out the workaround.

[Reid Kleckner, 2015-12-04 19:41:12]

On 2015/12/04 19:16:20, Reid Kleckner wrote:
> Anyway, I emailed John about it. He's the one that would've done this and
would
> care about this change.

John got back to me, the option I was thinking of is -fmax-type-align. The issue
is that explicit alignment attributes override it, and __declspec(align(#)) is
an explicit alignment attribute just like __attribute__((aligned(#))).

In other words, I think this is working as intended in Clang.

We could be less aggressive about vectorization and alignment when we are
pretending to be MSVC, but that doesn't seem like the best thing for users in
the long run.

MSDN even recommends that you don't use malloc/new/std::allocator with
__declspec(align(#))), and instead use _aligned_malloc or your own stuff.

[Nico, 2015-12-04 19:47:11]

On 2015/12/04 19:41:12, Reid Kleckner wrote:
> On 2015/12/04 19:16:20, Reid Kleckner wrote:
> > Anyway, I emailed John about it. He's the one that would've done this and
> would
> > care about this change.
> 
> John got back to me, the option I was thinking of is -fmax-type-align. The
issue
> is that explicit alignment attributes override it, and __declspec(align(#)) is
> an explicit alignment attribute just like __attribute__((aligned(#))).
> 
> In other words, I think this is working as intended in Clang.
> 
> We could be less aggressive about vectorization and alignment when we are
> pretending to be MSVC, but that doesn't seem like the best thing for users in
> the long run.
> 
> MSDN even recommends that you don't use malloc/new/std::allocator with
> __declspec(align(#))), and instead use _aligned_malloc or your own stuff.

MSDN says "The compiler does not guarantee or attempt to preserve the alignment
attribute of data during a copy or data transform operation. For example, memcpy
can copy a struct declared with __declspec(align(#)) to any location. Note that
ordinary allocators—for example, malloc, C++ operator new, and the Win32
allocators—return memory that is usually not sufficiently aligned for
__declspec(align(#)) structures or arrays of structures. [...] This type now has
a 32-byte alignment attribute. This means that all static and automatic
instances start on a 32-byte boundary."

This suggests that cl thinks it's not valid to assume that a random pointer to a
struct with a declspec(align) annotation is aligned.

Given that we ran into this twice in the last two months, I think it's probably
a good idea to be less aggressive with alignment assumptions here :-/

[Mark Mentovai, 2015-12-04 19:48:11]

mark@chromium.org changed reviewers:
- thakis@chromium.org

[Mark Mentovai, 2015-12-04 19:48:11]

I would think that if the standard supports what MSVC does (substituting
alignas() for __declspec(align()) as needed, since we’re not on VS2015 yet, but
someone said that it’s the same in VS2015), Clang ought to follow suit when
pretending to be cl. If not, then we should probably fix it in Crashpad, whether
or not Clang does anything.

But I don’t have time to check the standard right now.

[scottmg, 2015-12-04 19:58:51]

I think clang is in the wrong, and this seems like kind of a lot of code for
what it's fixing. But codewise, lgtm, and it'll be good to green the bots.

https://codereview.chromium.org/1498133002/diff/1/util/stdlib/aligned_allocat...
File util/stdlib/aligned_allocator.cc (right):

https://codereview.chromium.org/1498133002/diff/1/util/stdlib/aligned_allocat...
util/stdlib/aligned_allocator.cc:25: #include <xutility>
_Xbad_alloc is only there in VS2012+ I think, but I guess we won't worry about
that. :)

https://codereview.chromium.org/1498133002/diff/1/util/stdlib/aligned_allocat...
File util/stdlib/aligned_allocator.h (right):

https://codereview.chromium.org/1498133002/diff/1/util/stdlib/aligned_allocat...
util/stdlib/aligned_allocator.h:1: // Copyright 2015 The Crashpad Authors. All
rights reserved.
I'm surprised we don't have this in base. I guess all the gpu stuff does their
alignment manually or in angle.

[Mark Mentovai, 2015-12-04 20:01:39]

I won’t check this in until clang definitely says they’re not fixing it because
they think they’re right. It seems like there isn’t agreement on that side of
the table yet.

[Reid Kleckner, 2015-12-07 19:34:22]

On 2015/12/04 20:01:39, Mark Mentovai wrote:
> I won’t check this in until clang definitely says they’re not fixing it
because
> they think they’re right. It seems like there isn’t agreement on that side of
> the table yet.

I'd rather not make Clang's behavior different across platforms without more
evidence to show that this is a widespread compatibility issue. It's come up
twice, which is a few times, but not that many in the grand scheme of things.

It's also not clear that MSVC won't perform similar optimizations if you add
more floating point to it to try to make it vectorize.

So, let's change crashpad.

[scottmg, 2015-12-07 20:42:23]

On 2015/12/07 19:34:22, Reid Kleckner wrote:
> On 2015/12/04 20:01:39, Mark Mentovai wrote:
> > I won’t check this in until clang definitely says they’re not fixing it
> because
> > they think they’re right. It seems like there isn’t agreement on that side
of
> > the table yet.
> 
> I'd rather not make Clang's behavior different across platforms without more
> evidence to show that this is a widespread compatibility issue. It's come up
> twice, which is a few times, but not that many in the grand scheme of things.
> 
> It's also not clear that MSVC won't perform similar optimizations if you add
> more floating point to it to try to make it vectorize.

I suspect it'd come up a lot more if VC ever did that, and we'd have an
AlignedVector in Chromium by now.

> 
> So, let's change crashpad.

[Mark Mentovai, 2015-12-07 22:05:38]

I had a chance to look into this a little more.

I don’t think that MSVC is actually wrong here, even though it sucks for things
with stringent alignment requirements like SSE memory operands, and the ability
to use those freely during optimization.

The easy reference: http://en.cppreference.com/w/cpp/language/object#Alignment

> […] the largest fundamental alignment of any type is the alignment of
> std::max_align_t. If a type's alignment is made stricter (larger) than
> std::max_align_t using alignas, it is known as a type with extended
> alignment requirement. A type whose alignment is extended or a class
> type whose non-static data member has extended alignment is an over
> aligned type. It is implementation-defined if new-expression,
> std::allocator::allocate, and std::get_temporary_buffer support over
> aligned types. […]

The authoritative reference:

C++11 18.2 [support.types] ¶8:
> The type max_align_t is a POD type whose alignment requirement is at
> least as great as that of every scalar type, and whose alignment
> requirement is supported in every context.

C++11 3.11 [basic.align] ¶3:
> An extended alignment is represented by an alignment greater than
> alignof(std::max_align_t). It is implementation-defined whether any
> extended alignments are supported and the contexts in which they are
> supported (7.6.2). A type having an extended alignment requirement is
> an over-aligned type.

C++11 5.3.4 [expr.new] (regarding “new”) ¶1:
> It is implementation-defined whether over-aligned types are supported
> (3.11).

C++11 17.6.3.5 [allocator.requirements] (regarding allocators generally) ¶6:
> If the alignment associated with a specific over-aligned type is not
> supported by an allocator, instantiation of the allocator for that
> type may fail. The allocator also may silently ignore the requested
> alignment.

C++11 20.6.9.1 [allocator.members] ¶5 (regarding std::allocator::allocate):
> Returns: A pointer to the initial element of an array of storage of
> size n * sizeof(T), aligned appropriately for objects of type T. It is
> implementation-defined whether over-aligned types are supported
> (3.11).

C++11 3.9.2 [basic.compound] ¶3 :
> [Note: Pointers to over-aligned types (3.11) have no special
> representation, but their range of valid values is restricted by the
> extended alignment requirement. This International Standard specifies
> only two ways of obtaining such a pointer: taking the address of a
> valid object with an over-aligned type, and using one of the runtime
> pointer alignment functions. An implementation may provide other means
> of obtaining a valid pointer value for an over-aligned type. — end
> note ]

[hans, 2015-12-07 22:36:43]

On 2015/12/07 20:42:23, scottmg wrote:
> On 2015/12/07 19:34:22, Reid Kleckner wrote:
> > On 2015/12/04 20:01:39, Mark Mentovai wrote:
> > > I won’t check this in until clang definitely says they’re not fixing it
> > because
> > > they think they’re right. It seems like there isn’t agreement on that side
> of
> > > the table yet.
> > 
> > I'd rather not make Clang's behavior different across platforms without more
> > evidence to show that this is a widespread compatibility issue. It's come up
> > twice, which is a few times, but not that many in the grand scheme of
things.
> > 
> > It's also not clear that MSVC won't perform similar optimizations if you add
> > more floating point to it to try to make it vectorize.
> 
> I suspect it'd come up a lot more if VC ever did that, and we'd have an
> AlignedVector in Chromium by now.

I tried to coax MSVC into making some assumptions about alignment:

  #define N 16
  struct __declspec(align(32)) S {
    float x[N * 2];
  };
  void f(S *s) {
    for (int i = 0; i < N; i++)
      s->x[i] *= s->x[i + N]; 
  }

GCC will use "movaps" here (which requires alignment), but MSVC does not. It
does if 's' is on the stack, though.

Nico poked me to re-read the text he quoted in #10, in particular "This means
that all static and automatic
instances start on a 32-byte boundary." I suppose that might be how they track
it, i.e. they only make assumptions about the alignment if it's on the stack or
static, not just because the type has declspec align.

While we figure out how to fix this in Clang, would it make sense to work around
it in Crashpad anyway? As Mark said in crbug.com/564691#25, having unaligned
objects that express a desire to be aligned seems a little iffy.

[Mark Mentovai, 2015-12-08 00:48:48]

hans wrote:
> On 2015/12/07 20:42:23, scottmg wrote:
> > On 2015/12/07 19:34:22, Reid Kleckner wrote:
> > > On 2015/12/04 20:01:39, Mark Mentovai wrote:
> > > > I won’t check this in until clang definitely says they’re not fixing it
> > > because
> > > > they think they’re right. It seems like there isn’t agreement on that
side
> > of
> > > > the table yet.
> > > 
> > > I'd rather not make Clang's behavior different across platforms without
more
> > > evidence to show that this is a widespread compatibility issue. It's come
up
> > > twice, which is a few times, but not that many in the grand scheme of
> things.
> > > 
> > > It's also not clear that MSVC won't perform similar optimizations if you
add
> > > more floating point to it to try to make it vectorize.
> > 
> > I suspect it'd come up a lot more if VC ever did that, and we'd have an
> > AlignedVector in Chromium by now.
> 
> I tried to coax MSVC into making some assumptions about alignment:
> 
>   #define N 16
>   struct __declspec(align(32)) S {
>     float x[N * 2];
>   };
>   void f(S *s) {
>     for (int i = 0; i < N; i++)
>       s->x[i] *= s->x[i + N]; 
>   }
> 
> GCC will use "movaps" here (which requires alignment), but MSVC does not. It
> does if 's' is on the stack, though.
> 
> Nico poked me to re-read the text he quoted in #10, in particular "This means
> that all static and automatic
> instances start on a 32-byte boundary." I suppose that might be how they track
> it, i.e. they only make assumptions about the alignment if it's on the stack
or
> static, not just because the type has declspec align.
> 
> While we figure out how to fix this in Clang, would it make sense to work
around
> it in Crashpad anyway? As Mark said in crbug.com/564691#25, having unaligned
> objects that express a desire to be aligned seems a little iffy.

Something to keep in mind for clang is that you don’t necessarily need to be so
pessimistic on x86_64, where the ABI and allocators should provide 16-byte
alignment.

I couldn’t reproduce this bug at all on x86_64, only on 32-bit x86.

[Nico, 2015-12-08 18:27:50]

thakis@chromium.org changed reviewers:
+ thakis@chromium.org

[Nico, 2015-12-08 18:27:51]

hans, rnk, and I just discussed what we want to do in clang-cl and we agreed:

* declspec(align) should only assume alignment for things it allocated itself
(autos, statics), like cl does
* __attribute___((__align__)) will keep the current semantics (these being
different is unfortunate, but that's already the case and we're not really
making the world worse)

Making this change will take a while though (1-2 months maybe?), so we'd
appreciate if this patch could land in the meantime.

[Mark Mentovai, 2015-12-08 19:14:18]

Is there a clang bug that we can point this to, so that our future selves will
know when it's no longer necessary?

[Mark Mentovai, 2015-12-08 20:13:06]

mark@chromium.org changed reviewers:
- thakis@chromium.org

[Mark Mentovai, 2015-12-08 20:13:06]

Updated with commentary for checkin. Scott, one more look?

[scottmg, 2015-12-08 20:19:55]

lgtm

https://codereview.chromium.org/1498133002/diff/20001/util/stdlib/aligned_all...
File util/stdlib/aligned_allocator.h (right):

https://codereview.chromium.org/1498133002/diff/20001/util/stdlib/aligned_all...
util/stdlib/aligned_allocator.h:30: #define NOEXCEPT _NOEXCEPT
Since this is in a header, and it's not #ifndef NOEXCEPT, maybe using
CRASHPAD_NOEXCEPT would be safer lest someone else use the same name somewhere.

[Mark Mentovai, 2015-12-08 20:38:05]

https://codereview.chromium.org/1498133002/diff/20001/util/stdlib/aligned_all...
File util/stdlib/aligned_allocator.h (right):

https://codereview.chromium.org/1498133002/diff/20001/util/stdlib/aligned_all...
util/stdlib/aligned_allocator.h:30: #define NOEXCEPT _NOEXCEPT
scottmg wrote:
> Since this is in a header, and it's not #ifndef NOEXCEPT, maybe using
> CRASHPAD_NOEXCEPT would be safer lest someone else use the same name
somewhere.

Good call, done.

[Mark Mentovai, 2015-12-08 20:38:23]

Description was changed from

==========
Add AlignedVector and use it for vector<MEMORY_BASIC_INFORMATION64>

MEMORY_BASIC_INFORMATION64 specifies an alignment of 16, but the
standard allocator used by containers doesn't honor this. Although 16
is the default alignment size used on Windows for x86_64, it's not for
32-bit x86. clang assumed that the alignment of the structure was as
declared, and used an SSE load sequence that required this alignment.

AlignedAllocator is a replacement for std::allocator that allows the
alignment to be specified. AlignedVector is an std::vector<> that uses
AlignedAllocator instead of std::allocator.

BUG=chromium:564691
==========

to

==========
Add AlignedVector and use it for vector<MEMORY_BASIC_INFORMATION64>

MEMORY_BASIC_INFORMATION64 specifies an alignment of 16, but the
standard allocator used by containers doesn't honor this. Although 16
is the default alignment size used on Windows for x86_64, it's not for
32-bit x86. clang assumed that the alignment of the structure was as
declared, and used an SSE load sequence that required this alignment.

AlignedAllocator is a replacement for std::allocator that allows the
alignment to be specified. AlignedVector is an std::vector<> that uses
AlignedAllocator instead of std::allocator.

BUG=chromium:564691
R=scottmg@chromium.org

Committed:
https://chromium.googlesource.com/crashpad/crashpad/+/f55d18ade6877134e87515d...
==========

[Mark Mentovai, 2015-12-08 20:38:24]

Committed patchset #3 (id:40001) manually as
f55d18ade6877134e87515d9e2fc332dd40dea19 (presubmit successful).