!standard 13.11(16)                                           08-10-16  AI05-0116-1/01
!class binding interpretation 08-10-16
!status work item 08-10-16
!status received 08-07-29
!priority Medium
!difficulty Medium
!qualifier Omission
!subject The value of Alignment for a class-wide object

!summary

T'Class'Alignment of a class-wide type must
be no greater than the 'Alignment of any type covered by T'Class.

The value passed to the Alignment parameter of Deallocate for an instance
of Unchecked_Deallocation is the same as that passed to the corresponding
Allocate call. This may require dynamic determination of this is for
an access-to-classwide type.

!question

Must T'Alignment be maximal for all tagged types (by default)?
("Maximally aligned" = largest natural alignment on the machine, i.e. max chosen by
default for any type.)

13.11(16) requires "new" to pass D'Alignment to Allocate, where D is the designated
subtype, and 13.11.2(9/2) requires this same value to be passed to Deallocate.

But consider:

    type T1 is tagged
        record
            Comp1 : Integer;
        end record;

    type T2 is new T1 with
        record
            Comp2 : Long_Float;
        end record;

Now suppose Integer'Alignment = T1'Alignment = 4, and Long_Float'Alignment =
T2'Alignment = 8. Also assume that T1'Class'Alignment = T2'Class'Alignment = 8.

    type T3 is new T1 with
        record
            Comp3 : Integer;
        end record;

    type Ref_T1 is access all T1'Class;
    procedure Free is new Unchecked_Deallocation (T1'Class, Ref_T1);
    type Ref_T3 is access all T3;
    for Ref_T3'Storage_Pool use Ref_T1'Storage_Pool;

Suppose T3'Alignment = 4.

    X : Ref_T3 := new T3; -- pass Alignment => T3'Alignment (4) to Allocate

    Y : Ref_T1 := Ref_T1(X);
    Free (Y); -- pass Alignment => T1'Class'Alignment (8) to Deallocate?!

We're not supposed to calculate Y.all'Alignment at run time (which would require a
dispatching call, or similar).  But the allocator won't necessarily work properly
if a different Alignment value is passed to Allocate and Deallocate.

So I deduce that T1'Alignment and T3'Alignment must be 8 on this machine.
In other words, all type extensions must have the same alignment
as their parent (whether or not there's an Alignment clause on the extension), and
all root tagged types must be maximally aligned by default.

What is the intent?

!recommendation

(See Summary.)

!wording

Modify 13.11(16):

An allocator of type T allocates storage from T's storage pool. If the storage
pool is a user-defined object, then the storage is allocated by calling Allocate,
passing T'Storage_Pool as the Pool parameter. The Size_In_Storage_Elements
parameter indicates the number of storage elements to be allocated, and is
no more than D'Max_Size_In_Storage_Elements, where D is the designated subtype.
The Alignment parameter is D'Alignment{ if D is a specific type, and S'Alignment
where S is the type determined by the subtype_indication or qualified_expression
of the allocator otherwise}. The result returned in the Storage_Address
parameter is used by the allocator as the address of the allocated storage,
which is a contiguous block of memory of Size_In_Storage_Elements storage
elements. Any exception propagated by Allocate is propagated by the allocator. 

!discussion

We surely don't want to require that all tagged types have maximal alignment. That
would be really bad as it would prevent implementations from supporting large
alignments (such as page alignments). Surely, we wouldn't want to require that
all tagged objects are allocated on a page boundary!

It is clear that it is OK if an object is *more* aligned than its 'Alignment
indicates, but not if it is *less* aligned. Hence, if you have a formal
parameter of a class-wide type, and an actual parameter of a type covered by
the class-wide type, then the 'Alignment of the formal parameter should be no
greater than the 'Alignment of the actual parameter. I think we would also agree
that the 'Alignment of an object must be no less than the 'Alignment of its
(specific) type. This then implies that the 'Alignment of a class-wide type must
be no greater than the 'Alignment of any type it covers.

That means that T1'Class'Alignment in the example in the question must be 4, and
thus there is no problem with this example.

However, we're not out of the woods. If T3'Alignment had been 8, then the problem
reappears.

    X : Ref_T3 := new T3; -- pass Alignment => T3'Alignment (8) to Allocate

    Y : Ref_T1 := Ref_T1(X);
    Free (Y); -- pass Alignment => T1'Class'Alignment (4) to
              --         Deallocate?! (No, it should pass 8.)

A careful reading of 13.11.2(9/2) shows that this interpretation is also wrong.
13.11.2(9/2) says nothing about the designated type of the access type; it says
that the value of Alignment is the "Size_In_Storage_Elements and Alignment are
the same values passed to the corresponding Allocate call." That means that
the values passed to Deallocate are determined by the object being deallocated,
not the type in question. For access types with classwide designated types,
this implies some sort of lookup; since that is already required for the Size
being deallocated, there is no new implementation issue with doing that. So,
in this example, 8 should be passed to Deallocate.

However, we're *still* not out of the woods. Consider the much simpler
example:

    X : Ref_T1 := new T2; -- pass Alignment => T1'Class'Alignment (4) to Allocate
    Free (Y); -- pass Alignment => T2'Alignment (8) to Deallocate?!

But this is clearly wrong: we surely don't want to allocate an object with an
alignment of 8 at an alignment of 4. The problem is that the wording of 13.11(16)
says to use the alignment of the designated type; but for a classwide type,
the alignment of the object can be greater than that. Thus we reword 13.11(16)
to use the alignment of the allocated object if the designated subtype is classwide.

Note that an implementation will not want to allow the specification of
alignments for all subtypes (not just tagged ones), because that would require using
similar techinques for all subtypes, and thus would add runtime overhead in order
to determine the proper alignment to pass to Deallocate. The language does not
require such overhead because it does not allow such specification of alignments.

--!corrigendum 13.11(16)


!ACATS Test

B-Tests for examples like these should be constructed.

!appendix

From: Robert A. Duff
Sent: Monday, July 28, 2008  9:07 AM

Must T'Alignment be maximal for all tagged types (by default)?
("Maximally aligned" = largest natural alignment on the machine, i.e. max chosen by
default for any type.)

13.11(16) requires "new" to pass D'Alignment to Allocate, where D is the designated
subtype, and 13.11.2(9/2) requires this same value to be passed to Deallocate.

But AARM-13.3(21.d) says:

                         Language Design Principles

    21.d  By default, the Alignment of a subtype should reflect the "
          natural" alignment for objects of the subtype on the machine. The
          Alignment, whether specified or default, should be known at compile
          time, even though Addresses are generally not known at compile time.
          (The generated code should never need to check at run time the
          number of zero bits at the end of an address to determine an
          alignment).

And AARM-13.3(39.h) says:

    39.h  A type extension can have a stricter Alignment than its parent. This
          can happen, for example, if the Alignment of the parent is 4, but
          the extension contains a component with Alignment 8. The Alignment
          of a class-wide type or object will have to be the maximum possible
          Alignment of any extension.

I don't understand how this can work.  Example:

    type T1 is tagged
        record
            Comp1 : Integer;
        end record;

    type T2 is new T1 with
        record
            Comp2 : Long_Float;
        end record;

Now suppose Integer'Alignment = T1'Alignment = 4, and Long_Float'Alignment =
T2'Alignment = 8. So T1'Class'Alignment = T2'Class'Alignment = 8.

    type T3 is new T1 with
        record
            Comp3 : Integer;
        end record;

    type Ref_T1 is access all T1'Class;
    procedure Free is new Unchecked_Deallocation (T1'Class, Ref_T1);
    type Ref_T3 is access all T3;
    for Ref_T3'Storage_Pool use Ref_T1'Storage_Pool;

Suppose T3'Alignment = 4.

    X : Ref_T3 := new T3; -- pass Alignment => T3'Alignment (i.e. 4) to Allocate

    Y : Ref_T1 := Ref_T1(X);
    Free (Y); -- pass Alignment => T1'Class'Alignment (i.e. 8) to Deallocate?!

We're not supposed to calculate Y.all'Alignment at run time (which would require a
dispatching call, or similar).  But the allocator won't necessarily work properly
if a different Alignment value is passed to Allocate and Deallocate.

So I deduce that T1'Alignment and T3'Alignment must be 8 on this machine, contradicting
AARM-13.3(39.h).  In other words, all type extensions must have the same alignment
as their parent (whether or not there's an Alignment clause on the extension), and
all root tagged types must be maximally aligned by default.

What's the intended run-time model?

****************************************************************

From: Tucker Taft
Sent: Monday, July 28, 2008  10:33 AM

It sounds like tagged objects allocated from a storage pool that might also be
used for access-to-classwide types must be maximally aligned.  But I don't see any
need to over-align stack-allocated tagged objects or components that are of a
tagged type, since neither of these can be passed to Unchecked_Deallocation.

This does imply that 13.11(16) and 13.11.2(9/2) should be changed to require
maximal alignment being passed to Allocate and Deallocate for tagged types if
there is a possibility that a related access-to-class-wide types is using the
same storage pool.

****************************************************************

From: Tucker Taft
Sent: Monday, July 28, 2008  2:25 PM

On further thought:  I think we should break any promise that the alignments match
between Allocate and Deallocate.  A bigger question is what is 'Alignment of T'Class,
if T'Alignment is not the max?  My belief is that T'Class'Alignment should be equal
to T'Alignment, but that any object creation of an object whose tag identifies
T2 must be aligned at T2'Alignment.  In other words, T'Class'Alignment represents
the *minimum* alignment of any type it covers.

****************************************************************

From: Robert A. Duff
Sent: Monday, July 28, 2008  5:57 PM

Hmm.  This seems like a rather different model than what's in the [A]ARM.

Here's some background.  GNAT accepts things like this:

    type Page is array (0..2**12-1) of Character;
    for Page'Alignment use 2**12;
    type Page_Ref is access all Page;

Which is not required by the Minimal Level of Support.

When you do "new" returning Page_Ref (no user-defined storage pools in sight),
it calls malloc (which aligns on something like 8- or 16-byte boundaries) with a
much bigger size, and returns a pointer to a 2**12-aligned place within that.
And it secretly stores the malloc result at a negative offset from that, so when
you Unch_Dealloc, it can retrieve that and pass it to free.

It does the above if and only if the alignment is stricter than what malloc chooses.
So GNAT gets in trouble if the Alignment passed to Allocate is different from the
Alignment passed to Deallocate.  There's a bug, where it does the above shenanigans
on "new", but not on Unch_Dealloc.  So this is an example of a pool that requires
both Alignments to match, so I don't much like the idea of taking away that promise.
What if user-defined pools depend on that promise?

GNAT also currently accepts things like:

    type T1 is tagged...
    type T2 is new T1 with
        record
            Whatever : Page;
        end record;

and:

    type T3 is new T1 with ...;
    for T3'Alignment use 2**12;

both of which need to be illegal in my opinion. These cause the above-mentioned bug.

****************************************************************

From: Randy Brukardt
Sent: Monday, July 28, 2008  7:40 PM

> On further thought:  I think we should break any promise that the 
> alignments match between Allocate and Deallocate.

That seems like a horrible idea.

The original reason that Deallocate has a Size parameter was that I complained that
pools did not necessarily have that information, but that they may depend on it.
(The original Ada9x design did not have such a parameter.) The default pool in
Janus/Ada works that way.

The Alignment parameter got added at the same time, for no important reason other
than consistency. I don't see any need for it (the information is necessarily
encoded in the address). But as Bob's example shows, give a programmer a tool
and they will find some clever way to use it. As such, it is way too late to
eliminate guarentees that have been in the language for more than a decade.

As to the underlying problem, I don't see any useful meaning for T'Class'Alignment.
The alignment of an access-to-classwide object is that of the specific type (just
as with the size) and yes that means it has to be stored somewhere (probably in
the tag). That doesn't seem like a huge deal to me. (You can never allocate a true
classwide object, only specific ones, so the reverse probably ought to be true for
deallocation as well.)

Note that this is similar to 'Size: T'Class'Size doesn't mean anything by itself,
only Obj'Size does (where Obj is an object of a classwide type).
Generally, we want 'Alignment to work the same way.

The fact that this is (sort-of) dynamic doesn't surprise me: pretty much everything
about a classwide object is determined dynamically.

Also note that we've made a guarentee that Obj'Alignment is always static, but that
doesn't need to apply to types in order to get the benefit. More specifically, it
doesn't need to apply to class-wide types (the only requirement being that the minimum
alignment be known for the purposes of parameter passing). So I think we need to
qualify the staticness "design rule" to exclude T'Class'Alignment. The alternative of
disallowing the use of T'Alignment on virtually all tagged types is insane (since the
majority of tagged types are derived from Controlled and Limited_Controlled, and most
of the rest from interfaces, it could never be specified for any concrete tagged type
 - why even bother defining it in that case?)

****************************************************************

From: Tucker Taft
Sent: Monday, July 28, 2008  7:45 PM

>> On further thought:  I think we should break any promise that the 
>> alignments match between Allocate and Deallocate.  A bigger question 
>> is what is 'Alignment of T'Class, if T'Alignment is not the max?  My 
>> belief is that T'Class'Alignment should be equal to T'Alignment, but 
>> that any object creation of an object whose tag identifies
>> T2 must be aligned at T2'Alignment.  In other words, 
>> T'Class'Alignment represents the *minimum* alignment of any type it 
>> covers.
> 
> Hmm.  This seems like a rather different model than what's in the [A]ARM.

I don't think any of us thought through the implications of
access-to-class-wide types, when combined with the possibility of access
type conversion and unchecked deallocation.  So I don't think we should
try to "divine" the AARM intent for this case from the existing words. 
Instead we should figure out a model that is efficient, safe, and flexible,
and doesn't arbitrarily limit other things programmers can do just because
of the possibility of access type conversion in conjunction with unchecked
deallocation.

If we presume that we don't want to force all tagged objects to worst-case
alignment, nor that we want to preclude overgenerous alignments on tagged
types, then we need to deal with the fact that an access-to-class wide value
can be the target of conversions from access types with different values of
'Alignment for their designated subtypes.  We also have to deal with situations
where the actual parameter and the formal parameter have different 'Alignment
values.

It seems clear that it is OK if an object is *more* aligned than its 'Alignment
indicates, but not if it is *less* aligned. Hence, if you have a formal
parameter of a class-wide type, and an actual parameter of a type covered by
the class-wide type, then the 'Alignment of the formal parameter should be no
greater than the 'Alignment of the actual parameter. I think we would also agree
that the 'Alignment of an object must be no less than the 'Alignment of its
(specific) type. This then implies that the 'Alignment of a class-wide type must
be no greater than the 'Alignment of any type it covers.

Now when it comes to allocation as opposed to parameter passing, the concerns are
somewhat reversed.  We want to be sure that the allocation is at least as aligned
as the specific type of the object created.

Perhaps the simplest answer is to say that the 'Alignment passed to Allocate and
Deallocate are always based on the "specific" type of the object involved if the
access type involved is access-to-classwide.  This means that given an object of
a classwide type we may need to "dispatch" to determine its specific-type's
alignment.  But we do that already for 'Size, so that doesn't seem so bad.  When
allocating we will often know its specific type statically, so this would generally
only come up on Unchecked_Deallocation, which seems like a small price to pay.

****************************************************************

From: Tucker Taft
Sent: Monday, July 28, 2008  8:25 PM

You might not have seen my "third" thought, but it jibes very closely with yours.
That is, make the Alignment parameter value be based on the specific type of the
object involved.

By the way, why don't we officially adopt the term the "specific type of an object"
as a solution to the problem we were wrestling with a few weeks ago about the
meaning of "type" of an object in dynamic semantics, when its declared type is
class-wide?  That is, "specific type of an object" is the type determined by its tag,
while the "declared type of an object" is the type determined by its declaration.
 We should use one or the other in dynamic semantic rules.  We shouldn't just say
"type" except in static semantics and legality rules.  And even in static semantics,
we might talk about the "specific type of an object" created by an allocator.

****************************************************************

From: Robert Dewar
Sent: Friday, August 1, 2008  6:37 PM

> On further thought:  I think we should break any promise that the 
> alignments match between Allocate and Deallocate.

That sounds like a huge incompatible change to me!

****************************************************************

From: Tucker Taft
Sent: Saturday, August 2, 2008  3:58 AM

Not to worry.  This "further thought" was quickly overruled by still further
thought.  I think Randy and I both came to the conclusion that the 'Alignment
associated with a class-wide allocation or deallocation should be determined
by the 'Alignment of the specific tagged type involved.  And that is the same
on both allocation and deallocation, so the same value will be passed in.

****************************************************************