proposal: runtime: add AlignedN types that can be used to increase alignment

[ianlancetaylor]

The sync/atomic packages have this in the docs in the "Bugs" section: "On both ARM and x86-32, it is the caller's responsibility to arrange for 64-bit alignment of 64-bit words accessed atomically. The first word in a global variable or in an allocated struct or slice can be relied upon to be 64-bit aligned." This makes it difficult to use atomic operations in types that may not necessarily be at the beginning of an allocated struct or slice. For example, sync.WaitGroup does this:

	// 64-bit value: high 32 bits are counter, low 32 bits are waiter count.
	// 64-bit atomic operations require 64-bit alignment, but 32-bit
	// compilers do not ensure it. So we allocate 12 bytes and then use
	// the aligned 8 bytes in them as state.
	state1 [12]byte

and this:

func (wg *WaitGroup) state() *uint64 {
	if uintptr(unsafe.Pointer(&wg.state1))%8 == 0 {
		return (*uint64)(unsafe.Pointer(&wg.state1))
	} else {
		return (*uint64)(unsafe.Pointer(&wg.state1[4]))
	}
}

Further, on x86 there are vector instructions that require alignment to 16 bytes, and there are even some instructions (e.g., vmovaps with VEC.256), that require 32 byte alignment. While those instructions are not currently generated by the gc compiler, one can easily imagine using them in assembler code, which will require the values to be appropriately aligned.

To permit programmers to force the desired alignment, I propose that we add new types to the runtime package: runtime.Aligned2, runtime.Aligned4, runtime.Aligned8, runtime.Aligned16, runtime.Aligned32, runtime.Aligned64, runtime.Aligned128. (We could also use bit values, giving us runtime.Aligned16 through runtime.Aligned1024, if that seems clearer.)

These types will be identical to the type struct{} except that they will have a the alignment implied by the name. This will make it possible to write a struct as

type vector struct {
    vals [16]byte
    _ runtime.Aligned16
}

and ensure that instances of this struct will always be aligned to a 16 byte boundary.

It will be possible to change sync.Waitgroup to be

type WaitGroup struct {
    noCopy noCopy
    _ runtime.Aligned8
    state uint64
    sema uint32
}

simplifying the code.

Although this functionality will not be used widely, it does provide a facility that we need today without requiring awkward workarounds. The drawback is the addition of a new concept to the runtime, though I think it is fairly clear to those people who need to use it.

Another complexity is that we will have to decide whether the size of a value is always a multiple of the alignment of the value. Currently that is the case. It would not be the case for the runtime.AlignedN values. Should it be the case for any struct that contains a field with one of those types? If the size of a value is not always a multiple of the alignment, we will have to modify the memory allocator to support that concept. I don't think that will be particularly difficult, but I haven't really looked.

[josharian]

A few minor comments:

• If we do this, we should probably do go/types: add GCSizes #17586 too. It's not cmd/vet that relies on go/types for information about what cmd/compile will do alignment-wise. Another example is wasted.
• Your struct vector above will have a byte of padding at the end to avoid GC problems. You probably want the struct{} field as the first field. And we'll want to carefully document that recommendation. I mention this only because if you missed this detail, others definitely will.
• This could also be done with a //go: annotation on the type. We already have other //go: annotations on types. Don't panic. I'm not suggesting we do this. (Even the mere mention of annotations tends to raise banshee-level howling.) But it does raise the general question about when and why to use magic embedded types vs annotations vs perhaps some other general mechanism that doesn't exist yet.

[ianlancetaylor]

It's true that that we do have go:nointerface and go:notinheap annotations on types, but neither is documented and the latter is clearly only for the runtime. I suppose my general reaction to support //go: annotations on types can be summed up as https://www.youtube.com/watch?v=hulm_T_xnwY .

[cespare]

@ianlancetaylor when you wrote

(We could also use runtime.Aligned16, etc., if that seems clearer.)

I don't see how this differs from the previous sentence.

[ianlancetaylor]

@cespare I meant to imply using bit values rather than byte values. Updated original comment to clarify. Those names would mean that the AlignedN names would correspond to intN names.

[rsc]

I agree we should fix this problem. I am less certain about how to fix it. Perhaps to start we should just align 64-bit integers to 64-bit addresses on 32-bit platforms. It's called out in sync/atomic because it's basically a bug on our side, one that we've just not fixed.

The solution proposed here essentially assumes the compiler will not reorder fields, at least not if these tags are present. I don't think we've fully closed the door on that (#10014). In that issue (two years ago), I argued that it is important for the programmer to have control over locality, so wholesale reordering of fields is not great (for example, sort by size and then lay out would give optimal packing but I think be too invasive).

At the same time, I am getting tired of looking for uint32-sized or bool-sized holes when adding fields to existing structs, and even more I am getting tired of being forced to choose between "understandable struct definition" and "small-in-memory struct definition". I do wonder if the compiler should be able by default to sift individual small fields up into gaps that would otherwise go unfilled, but not otherwise reorder the definitions. This is getting off-topic for this issue, except that any such scheme would need an override annotation for cgo and so that might give a mechanism for expressing alignment as well; of course any reordering would need to keep alignment in mind. I don't have any good ideas.

Also not every variable that needs alignment is a field in a struct. I'm not sure what to do about that either. Code might declare 'var x [16]byte' and want to pass it to something that requires 16-byte alignment, for example. Maybe that's getting too far ahead of ourselves, but it's worth keeping in mind.

I had hoped that alignment would be a property of a type, not a specific declaration. Are there cases where that's not tenable?

[mdempsky]

runtime.AlignedCache (which could just alias an appropriate AlignedN type) would help address #19025.

[ianlancetaylor]

I did not mean to imply that this approach meant that the compiler could not reorder fields. The language spec does not state that the alignment of one field in a struct implies anything at all about the alignment of subsequent fields in the struct. I envision any uses of this as being of the form

type Vec struct {
    _ runtime.Aligned16
    b [16]byte
}

Here we know that any instance of Vec is aligned to a 16-byte boundary.

I agree that alignment should be a property of a type, and I believe that that satisfies all alignment needs in Go. The question is how you specify that alignment, and whether it can be done without using a magic comment. This proposal is one approach: in effect, you can only specify the alignment of struct types, and you do so by adding a field of type runtime.AlignedN.

For comparison, in C (with GCC extensions) you specify alignment of a type by writing

typedef T ... __attribute__((aligned(n)));

You can also specify alignment of a specific variable in the same way. Or, you can implement alignment for a specific memory allocation by using memalign or posix_memalign (since C's memory allocator does not understand types, it is generally necessary to use these functions when allocating memory for an aligned type).

Clearly for Go it would be nicer to be able to declare the alignment of any type, rather than this proposal which in effect only permits you to declare the alignment of a struct. If we can figure out a way to do that, we should. But I'd really rather not do it via a magic comment.

[minux]

For sync/atomic, the biggest problem is usually not the alignment of the whole structure (because we have at least 8 byte alignment on struct larger than 8 byte), but ensuring that the next uint64 will be aligned correctly within the struct. A nice solution is to just increase alignment of 64-bit types on 32-bit architectures. For vectors, I think once we figure out how to use SIMD intrinsics, we will have types of 128-bit, 256-bit and 512-bit alignment.

[ianlancetaylor]

For sync/atomic, the biggest problem is usually not the alignment of the
whole structure (because we have at least 8 byte alignment on struct larger
than 8 byte), but ensuring that the next uint64 will be aligned correctly
within the struct.

Yes, understood. With this proposal you write "the next uint64" as a field of type alignedUint64, a struct defined as

type alignedUint64 struct {
    _ runtime.Aligned8
    v uint64
}

Vectors and sync/atomic are not the only uses of aligned types, so I think a more general solution would be a good idea if we can find one.

[cespare]

Here's a slight variation on the original proposal:

• Add runtime.Align2, ... runtime.Align128. (Note: "align", not "aligned")
• These are just like struct{}, except that if a runtime.AlignN, is used as a struct field, it specifies the alignment of the following field (in declared order).
• If a runtime.AlignN is declared as the last struct field, it specifies the alignment of the entire struct.

This gets to @minux's point about aligning particular struct fields. You could even use multiple AlignNs to align multiple fields in a single struct.

(AlignN is more like a magic comment than AlignedN is, but at least it isn't a comment.)

[rsc]

@ianlancetaylor Thanks for the clarification. I was slightly confused by the fact that in your original post 'struct vector' (really should be 'type vector struct') puts the alignment after the field, not before.

[minux]

On Feb 13, 2017 7:46 PM, "Caleb Spare" ***@***.***> wrote: Here's a slight variation on the original proposal: - Add runtime.Align2, ... runtime.Align128. (Note: "align", not "aligned") - These are just like struct{}, except that if a runtime.AlignN, is used as a struct field, it specifies the alignment of the *following* field (in declared order). - If a runtime.AlignN is declared as the last struct field, it specifies the alignment of the entire struct.

I think any AlignN will set the alignment for the whole structure. The logic is this: In order to ensure N byte alignment for a particular field, we must first ensure at least N byte alignment for the whole structure and then make sure the field has N byte aligned offset within the structure. I understand this proposal diverges from existing C convention, but I think it's more intuitive to the programmer. And we can also add a magical AlignCacheLine type to force at least cache line alignment in order to reduce false sharing (i think this is better than #19025). In order to not make the types too magical from the language specification's perspective, I suggest that we make them like this: type alignedbyte byte // the only magical and unexported type, only allowed as underlying type of an array, the resulting array has the alignment as the size of the array type aligned16 [16]alignedbyte // a 16-byte aligned type which takes 16-byte of space. type Align16 [0]aligned16 // zero size, can be embedded into other structs to force alignment of the next field (and also the whole structure) This takes advantage of recently clarified spec #18950, regarding alignment of [0]T.

[josharian]

If a runtime.AlignN is declared as the last struct field, it specifies the alignment of the entire struct.

Zero-sized final fields cause cmd/compile to insert a padding byte at the end. I imagine that is unacceptable in many of the cases for which increasing alignment is important.