!standard 3.10.2(22) 12-11-30 AI12-0016-1/01 !class binding interpretation 11-12-30 !status work item 11-11-13 !status received 11-07-28 !priority Medium !difficulty Hard !subject Implementation model of dynamic accessibility checking !summary **TBD. !question The AARM provides a suggested implementation model for dynamic accessibility checking in the Implmentation Note beginning with AARM 3.10.2(22.u). However, this model alone is not enough to correctly implement Ada 2005, and Ada 2012 makes this even less true. Is the intent that the "small integer" model of dynamic accessibility is no longer enough? (Yes.) If so, the AARM notes should be updated to provide a realistic model. !recommendation ** TBD. !wording ** TBD. !discussion Problems with the the "small integer" model for representing accessibility levels and performing run-time accessibility checking have been identified (see mail message of July 28, 2011, previously filed in this AI). This is a description of a more general implementation approach which addresses these problems without introducing unacceptable costs in space, time, or complexity. This is only intended to demonstrate that at least one viable implementation model exists and to make this available to language implementors as an option. It is not intended to introduce any language changes, but rather to offer one way of meeting the requirements that are already implicit in the language definition. It may be that language changes in this area are needed. "Master-based" accessibility checking (see the accept_statement example and the discussion of incomparable accessibility levels in AI05-0024) may require wording changes to address scenarios involving incomparable accessibility levels (i.e., unequal levels, neither of which is "deeper" than the other). For example, the check associated with an access type conversion is defined by "For an access-to-object type, a check is made that the accessibility level of the operand type is not deeper than that of the target type, ...". If it is somehow possible that the two accessibility levels mentioned above might be incomparable then we would want the run-time check to fail in this case; with the current wording, the check would pass. Such RM wording changes are outside the scope of this discussion, except that it is intended that the implementation model described herein would be compatible with such changes. We describe the proposal in the "software present tense", as a fait accompli. The accessibility level of a master is represented at run-time by a pointer to an object whose lifetime is that of the master. For example, if the master is an execution of a subprogram body, then the object would be declared (implicitly, by the compiler) within the subprogram. For the following example procedure P1 (X : access Integer) is ... ; procedure P2 is Local : aliased Integer; begin P1 (Local'Access); the implicit parameter passed to P1 to describe X's accessibility level might be implemented by something like procedure P2 is P2_Level : aliased constant Level_Object := ... ; Local : aliased Integer; begin P1 (..., P2_Level'Unchecked_Access); So what does this type Level_Object look like? Given two accessibility levels A and B, the fundamental operation that must be supported is answering the question "might an entity whose accessibility level is A outlive one whose level is B?". Fortunately, it is not necessary to support this query for an arbitrary pair of accessibility levels; an implementation can take advantage of knowledge about the domain of this query. A query at some point in the execution of a program can only involve levels that are directly visible or somehow indirectly reachable at that point. To illustrate this point, let's first consider an implementation which would suffice to implement Ada 95 (but not, as it turns out, Ada 2005 or Ada 2012). Note that the small integer model also suffices for implementing Ada 95, so this initial implementation is really only useful as an expository stepping stone towards a more expressive implementation which does support Ada 2005 and Ada 2012. The Ada-95-only implementation: For each master whose level needs to be represented at run-time (e.g., because a reference to a local variable is passed as an actual parameter where the corresponding formal is of an anonymous access type, as in procedure P2 in the example above), a local aliased constant of type Level_Object_95 is declared. The type is declared as type Level_Object_95; type Level_95 is access constant Level_Object_95; type Level_Object_95 is record Static_Link : Level_95; end record; A single constant of type Level_Object_95 is declared at library level: Library_Level_Object_95 : aliased constant Level_Object_95 := (Static_Link => null); Library_Level_95 : constant Level_95 := Library_Level_Object_95'Access; All other objects of type Level_Object_95 are aliased constants declared in more nested scopes and containing pointers to the level object for the corresponding elaboration of the nearest (statically) enclosing scope which has a level object. This corresponds roughly to the "static link" mechanism traditionally used for implementing up-level references. To determine whether level A is deeper than level B, one traverses links starting at A until either B or null is encountered (the former indicating A is deeper than B, the latter indicating otherwise; a level is, by definition, not deeper than itself so the A = B case must also be handled correctly). The following example (which involves an anonymous access-to-subprogram type, not an Ada 95 feature) demonstrates that this approach, at least as described so far, doesn't handle some Ada 2012 constructs: procedure Accessibility_Test is procedure Call_Proc (Proc : not null access procedure (X, Y : access Integer); X, Y : access Integer) is Local : aliased Integer; begin if X = null then Proc.all (Local'Access, Y); else Proc.all (X, Local'Access); end if; end; procedure P1 is procedure P2 (X, Y : access Integer) is type Ref is access all Integer; for Ref'Storage_Size use 0; Ptr : Ref; procedure P3 (X, Y : access Integer) is begin Ptr := Ref (X); -- OK (1) begin Ptr := Ref (Y); -- raises Program_Error (2) exception when Program_Error => null; end; pragma Assert (Ptr /= Y); end; begin Call_Proc (P3'Access, X, null); end; begin Call_Proc (P2'Access, null, null); end; begin P1; end; Let's look at how this model breaks down in the case of this example. When P3 is called, the call stack is P3 Call_Proc P2 Call_Proc P1 Accessibility_Test The two accessibility levels passed into P3 correspond to the two calls to Call_Proc. One of these two levels is longer lived than the level of the call to P2 (which is also the level of Ref, the target type of the access type conversions) and one of them is shorter-lived, but this essential distinction is lost. The first access type conversion should succeed and the second should fail, but there is insufficient information to make this distinction. So now we take the view that the "static link" is just one example (albeit, the most important one) of a level whose lifetime is known to be longer than that of a given level for which we are declaring the level object. In the case of a subprogram which has an anonymous access-to-object parameter, for example, the level of the parameter (which is passed in) is also known to have this property. For a class-wide parameter, the level of the underlying specific type of the parameter is another such "known to outlive me" level. For a build-in-place function or a function with an anonymous access result type, the level determined at the point of call is another. The point is that a set of such "predecessor" levels can be determined by combining the static-link with other levels extracted (extraction details TBD) from the parameters. The idea is that at the time of a subprogram call, the only existing levels that the callee will need to refer to are those that are reachable via an uplevel reference to an enclosing scope combined with those that are somehow passed in as parameters (this includes things like the accessibility level of the underlying specific type of a tagged parameter, not just simple cases like anonymous access-to-object typed parameters; note that for most implementations this particular example probably means that the descriptor for specific tagged type will contain the pointer value representing its accessibility level). This suggests something like type Level_Object; type Level is access constant Level_Object with Storage_Size => 0; type Level_Vector is array (Positive range <>) of Level; type Level_Object (Predecessor_Count : Natural) is record Predecessors : Level_Vector (1 .. Predecessor_Count); end record; Library_Level_Object : aliased constant Level_Object := (Predecessor_Count => 0); Library_Level : constant Level := Library_Level_Object'Access; In our example above, the two level objects declared locally to the two invocations of Call_Proc would now capture the needed distinction by incorporating the levels of their parameters. See the "gory details" section below for a detailed explanation of how this is accomplished. It would also be instructive (I imagine) to look at the examples given in the initial AI discussion (in particular, procedures Ada05_Example and Access_Result_Test) which illustrate cases that the small integer model cannot handle and to work through how these cases work with the proposed model (Note: I have not actually had time to do this yet, but that doesn't stop me from recommending this action to others). This raises performance questions. To decide whether level A is at least as long-lived as level B, we need to traverse B's known predecessors, just as before, but now this involves traversing a DAG instead of a linked list. Can this be done cheaply enough? One answer to that is to store the "static link" in the first element of the Predecessors array and to optimize for the case where the Ada-95-style representation described above would have sufficed to determine that the check would pass. We certainly don't care about performance in the case where the check will fail; it might be that we also don't care very much about performance in the corner cases where this richer data structure (i.e., multiple predecessors) is needed to get the right answer. Is it worthwhile to try to avoid adding redundant predecessors to a Level_Vector? Consider the case of a subprogram which takes an access parameter when the parameter happens to be null (or a pointer to an object declared at library level). If redundant predecessors are always filtered out, then we are talking about traversing a tree instead of a DAG. We still have the important optimization that no level object is declared for a master that doesn't need one. In particular, wrappers don't declare level objects. The details of how we extract predecessor information from a routine's parameters when building a level object have been glossed over here. Some thought is needed here (e.g., are there cases where a parameter of a specific tagged type requires extracting the accessibility level of the underlying type of the actual and incorporating that into the predecessor set of the callee?). Note, however, that the rest of the model is not particularly sensitive to these details. ==== Gory details (as promised above): When P3 is called, the call stack is P3 Call_Proc - second call P2 Call_Proc - first call P1 Accessibility_Test The only masters in this example (besides the library_level master) are subprogram body executions, so there are at most 7 accessibility level objects to worry about. In fact, the procedures Accessibility_Test, P1, and P3 do not require level objects, so there are only 4. When P1 calls Call_Proc, it has to pass in two accessibility levels for the parameters X and Y. Because it is passing in "null" values, it passes in the library level. Inside this (i.e., the first) call to Call_Proc, Call_Proc builds its local level object. Let's ignore the access-to-subprogram parameter for now and also assume that we are not going to perform any filtering at this point to weed out predecessors which contribute no new information. So the object declaration might be implemented as something like Level : aliased constant Level_Object := (Predecessor_Count => 3, Predecessors => (Library_Level, X'Accessibility_Level, Y'Accessibility_Level)); In this case, X'Accessibility_Level and Y'Accessibility_Level both yield Library_Level, so we get three copies of the same dependency. To recap: Call_Proc_Call_1.Level_Object = (3, (1..3 => Library_Level)) Call Proc then calls P2, passing in Call_Proc_Call_1.Level_Object'Access as the accessibility level for X and passing along Library_Level as the accessibility level for Y. P2, upon being called, builds its local level object in much the same way that Call_Proc did, ending up with P2.Level_Object = (3, (Library_Level, Call_Proc_Call_1.Level_Object'Access, Library_Level)); P2 then calls Call_Proc, passing along Call_Proc_Call_1.Level_Object'Access as the accessibility level for X and passing in Library_Level as the level for Y. Call_Proc, upon being called again, builds its local level object, ending up with Call_Proc_Call_2.Level_Object = (3, (Library_Level, Call_Proc_Call_1.Level_Object'Access, Library_Level)); Call Proc then calls P3, passing along Call_Proc_Call_1.Level_Object'Access as the accessibility level for X and passing in Call_Proc_Call_2.Level_Object'Access as the accessibility level for Y. P3 now performs two accessibility checks. For the first access type conversion, it compares the accessibility level for X (which is Call_Proc_Call_1.Level_Object'Access) to that of the access type Ref (which is P2.Level_Object'Access) so see if X is sufficiently long-lived. The answer is yes, because X's level is a predecessor of Ref's, and the check passes as desired. For the second access type conversion, the accessibility level of Y is used in place of X's. The accessibility level of Y is Call_Proc_Call_2.Level_Object'Access, which is nowhere to be found in a predecessor traversal starting from Ref's level. Thus, the check fails as desired. !ACATS test ** TBD. !appendix From: Steve Baird Sent: Thursday, July 28, 2011 12:25 PM The AARM provides a suggested implementation model for dynamic accessibility checking in the Implmentation Note beginning with AARM 3.10.2(22.u). It appears that Ada05 introduced some constructs which require modifying this implementation model. Further modifications appear to be needed in order to implement Ada2012. At the very least, it appears that the AARM's description of the intended implementation model needs to be updated; the ARG may decide that other actions are needed if it is determined that the language as currently defined is too difficult/expensive to implement. First, a review of the currently suggested implementation model, unchanged since Ada95. =========== Begin recap =========== Terminology: For purposes of this discussion, I'll use the term "scope" or "dynamic scope" to indicate a particular elaboration of a lifetime-bounding constuct such as a subprogram body or a block statement. In this discussion (which is not about static semantics), a package does not introduce a new scope. One dynamic scope is "enclosed" or "statically enclosed" by another if locals of the enclsoing scope are directly accessible (via uplevel referencing) from within the inner scope. To emphasize, this is not a relationship between static entities such as subprogram bodies. If a subprogram is statically declared within another, there exists (at runtime) exactly one invocation of the outsr subprogram which "statically encloses" a given invocation of the inner subprogram. "Library level" is also considered to be a scope. The library-level scope statically encloses all other scopes. Associated with a parameter of an anonymous access type is a Natural-valued implicitly-generated implementation-level parameter. If the given callable construct is nested within N enclosing dynamic scopes (for example, N would be zero for a subprogram declared at library level), this parameter (call it P) is intepreted by the callee as follows: 0 ..N - the accessibility level of the designated object is that of the Pth statically enclosing scope (zero indicates library-level). N+1 .. Integer'Last - None of the above. The accessibility level of the designated object corresponds to some scope which does not statically enclose the scope of the callee. The accessibility level of the designated object is treated in this case as if it matched that of the locals of the callee. This approach relies on two assumptions: - a caller is able to easily pass in these values; and - these values provide anough information for the callee to easily perform any required dynamic accessibility checks. We shall see (below) that changes introduced in Ada05 violate the first assumption and changes introduced in Ada2012 violate the second. Values greater than N+1 are allowed and treated as being equivalent in every way to a value of N+1. This is needed in order to implement calls through an access to subprogram value where the called subprogram is declared in a less nested scope than the access-to-subprogram type, as in procedure Global (X : access Integer) is ... end P1; procedure Foo is procedure Bar is Local_Var : aliased Integer; type Local_Ref is access procedure (X : access Integer); Ptr : Ref := Global'Access; ... begin Ptr.all (X => Local_Var'Access); Because Ptr might designate a subprogram declared inside of Foo, a level of 2 must be passed in even though procedure Global will treat all values greater than 0 identically. Note that care must be taken in implementing the rule that a value greater than N+1 must be treated tha same as N+1 when calling a nested subprogram, as in procedure Global (X1 : access Integer) is type Ref is access all Integer; Ptr : Ref; procedure Local (X2 : access Integer) is begin Ptr := Ref (X2); -- should pass runtime check end Local; begin Local (X2 => X1); If Global is passed the value 2 and simply passes it along to Local without modification, the accessibilty check associated with the type conversion inside Local may incorrectly raise Program_Error. One way (albeit perhaps not the most efficient way) to handle this is for a callee to "normalize" any access levels that it is passed by "min"-ing them with the (statically known) accessibility level of the callee's locals. In the above example, this would cause Global to pass Local a value of 1 instead of 2 and all is well. Wrappers for access-to-subprogram callees would be another approach (although this seems like it would be overkill in most situations). Normalization of the actual parameter at the point of a call which needs it might be a practical solution. ========= End recap ========= Ada05 introduced nested extensions (AI95-00344) and anonymous access to subprogram types (AI95-00254; thanks to Tucker for pointing out this aspect of the problem). Either of these introduces the possibility of a call where there is inadequate statically-known information about the enclosing scope of the callee. In Ada95, the scope of the callee was always known (even for a dispatching call) except in the case of a call through an access to subprogram value. In that case, the scope of the access-to-subprogram type declaration could be used instead and all was well. Consider the case of an Ada05 dispatching call or call through a value of an anonymous access-to-subprogram type, where the callee takes a parameter of an anonymous access type, as in: procedure Outer is X : aliased Integer; procedure Inner (Ref : access procedure (Xx : aliased Integer)) is begin Ref.all (Xx => X'Access); The crux of the problem is that the caller knows what scope X is declared in, but doesn't know which Integer value would represent that scope to the callee. If the callee is declared somewhere within the same invocation of Foo which statically encloses the invocation of Bar, then the value 1 should be passed in. Otherwise, the value Integer'Last would be a good choice. For the sake of specificity, consider the following example: procedure Ada05_Example is package Root_Pkg is type Root is abstract tagged null record; procedure Prim_Op (Xxx : Root; Yyy : access Integer) is abstract; end Root_Pkg; procedure Proc (Root_Ref : access Root_Pkg.Root'Class) Is type Int_Ref is access all Integer; Int_Ptr : Int_Ref; Int_Var : aliased Integer; package Ext_Pkg is type Ext is new Root_Pkg.Root with null record; procedure Prim_Op (Xxx : Ext; Yyy : access Integer); end Ext_Pkg; package body Ext_Pkg is procedure Prim_Op (Xxx : Ext; Yyy : access Integer) is begin Int_Ptr := Int_Ref (Yyy); end Prim_Op; end Ext_Pkg; Ext_Var : aliased Ext_Pkg.Ext; Refs : constant array (Boolean) of access Root_Pkg.Root'Class := (Ext_Var'Access, Root_Ref); begin if Root_Ref = null then Proc (Ext_Var'Access); -- If Int_Ptr is not null at this point, -- then it is a dangling reference to an -- elaboration of Int_Var which no longer exists -- as a result of else for Exception_Expected in Boolean loop declare Test_Failed_1, Test_Failed_2 : exception; begin Root_Pkg.Prim_Op (Refs (Exception_Expected).all, Int_Var'Access); if Exception_Expected thepn raise Test_Failed_1; end if; exception when Program_Error => if not Exception_Expected then raise Test_Failed_2; end if; end; end loop; end if; end Proc; begin Proc (null); end Ada05_Example; While analyzing this example, Tucker wrote (in private communication) the following description of its execution: The basic point is that there are three levels here, the level of Root_Pkg, the level of the outer call on Proc, and the level of the recursive call on Proc. The recursive call is passed an Ext_Var object from the outer call. Inside the recursive call, it calls the Prim_Op operation on this outer Ext_Var object, passing it a local Int_Var'Access. That Prim_Op operation stores Int_Var'Access into its (outer) Int_Ptr and returns. The conversion to Int_Ref is supposed to catch this. But at the point of call, it thinks it is calling a Root_Pkg-level operation, when in fact it is calling something much more deeply nested. I added something like We call Prim_Op in a loop which is executed twice. The first time, we need to pass in the value 2. Ext_Var is declared in the "right" elaboration of Proc's decl list (i.e., the one which elaborated the Prim_Op which is being called). The second time we need to pass in a value of 3 or more because (ultimately) we are passing in a reference to a declaration of Ext_Var declared in a "wrong" elaboration of Proc. Tucker also pointed out that anonymous access-to-subprogram parameter types can be used to demonstrate the same problem, as in package body Pkg is procedure Plum(P : access procedure(X : access T)) is type T_Ref is access all T; T_Ptr : T_Ref; T_Var : aliased T; procedure Nested(X : access T) is begin T_Ptr := T_Ref(X); -- Checks level of X against T_Ref end Nested; begin if P = null then Plum(Nested'Access); else P.all(T_Var'Access); end if; end Plum; begin Plum(null); end Pkg; Consider a case (such as the Outer/Inner example above) where the caller knows what scope he wants to represent to the callee, but doesn't know what Integer value to use to represent it. A "none of the above" value (e.g., Integer'Last) should be used if and only if the the scope that is to be represented will not statically enclose the scope of the callee (once the callee is called). If the caller had some mechanism for determining whether the callee's set of enclosing scopes includes the "dynamic scope" mentioned above, then the caller could conditionally pass in Integer'Last as appropriate and all would be well. Such a mechanism could certainly be invented, but it might be quite "heavy", perhaps involving distributed overhead. One would like to extract the static link of the callee (before the call) and then traverse static links, looking for the scope in question; then pass in Integer'Last if and only if the scope is not found. Given FE/BE boundaries, IL and VM interfaces, and optimizations such as inlining, subprogram hoisting, and static link elimination, this kind of static link manipulation may turn out to be unimplementable, or at least impractical. FE-generated data structures of some sort may be required. On the other hand, perhaps some such mechanism is also needed for master-based (as opposed to static accessibility level based) accessibility checks. See AI05-0024, particularly the example involving an accept statement. Another approach would be to have the caller pass in both an Integer value (needed for cheap comparisons) and some indication (conceptually, something like a frame pointer) of the scope that Integer value is intended to represent; the callee could then compare that second value with the scope the Integer value represents to the callee and substitute Integer'Last if the two values don't match. In any case, the current AARM description makes no mention of this implementation issue. On to Ada2012. The second assumption mentioned above that this whole implementation model rests upon is that there is no need to distinguish between two distinct members of the set of scopes that are represented by a "none of the above" value passed in as part of some call. Ada2012 (AI05-0234) changed the semantics anonymous access function result types which return an allocator so that the accessibility level of the allocated object is "determined by the point of call". Consider an Ada2012 function which 1) has an anonymous access result type whose designated type has an access Integer discriminant; and 2) takes an "access Integer" parameter; and 3) returns an allocator as follows: new Discriminated (Discrim => Access_Param); Consider further the case where the two accessibility values that are passed in (one for the access parameter, one for the function result type level "determined by the point of call") are both Integer'Last or some other "none of the above" value. There isn't enough info here to determine whether the allocator should succeed. We need to know about the relationship between the two "none of the above" scopes, and we don't. To be specific, consider the following example: procedure Access_Result_Test is procedure Assert (Condition : Boolean) is Test_Failed : exception; begin if not Condition then raise Test_Failed; end if; end Assert; subtype Designated is Integer; type Discriminated (D1, D2 : access Designated) is null record; function Make (Arg1, Arg2 : access Designated; Flag : Boolean := False) return access Discriminated is Local1, Local2 : aliased Designated := 123; type Named is access all Discriminated; Named_Var : Named; begin if Arg1 /= null and Arg2 /= null then return new Discriminated (D1 => Arg1, D2 => Arg2); -- -- evaluation of this allocator includes, among -- other things, accessibility checks for the -- two discriminant values, elsif Arg1 /= null then return Make (Arg1, Local2'Access); elsif Flag then Named_Var := Named (Make (Local1'Access, Local2'Access)); -- should not raise P_E else Named_Var := Named (Make (Local1'Access, null)); -- allocator should raise P_E end if; Named_Var.D2.all := 456; -- D2 must not be dangling here Assert (Local1 + Local2 = 579); return null; end Make; begin for Flag in Boolean loop begin Assert ((Make (null, null, Flag) = null) and then Flag); exception when Program_Error => Assert (not Flag); end; end loop; end Access_Result_Test; Similar examples can be constructed which do not involve allocators or anonymous access function results. Consider: function Make (X : access Integer) return Discriminated is begin return Discriminated'(Discrim => X, ...); An accessibility check is required in order to ensure that X does not designate something whose accessibility level is more deeply nested than the level determined by the point of call. AI05-0234's "determined by the point of call" rule seems to be at the heart of this issue. All of the examples given in this entire discussion seem very contrived. Perhaps a legality rule could be found which would disallow the cases which introduce these problems without rejecting cases that come up in practice. This may be worth pursuing. Even if we wanted to classify these cases as erroneous (which I think would be a bad idea), we would still need a precise definition of what it is that is being defined to be erroneous. Thoughts? **************************************************************** From: Randy Brukardt Sent: Thursday, July 28, 2011 1:15 PM (1) Your mind sure is twisted. :-) (2) Accessibility checks for objects aren't worth the headaches. I've only once written code where 'Access could even be used, otherwise I've always had to turn them off by using 'Unchecked_Access and do my own management. So what's the point? The static checks catch low-hanging fruit, so they're probably worth the effort, but the dynamic checks have huge overhead (getting huge-er!) and provide a "tripping hazard" (as Bob puts it) as much as any help. If you really want to prevent dangling pointers, don't use access types, use a container (or some type where the language provides the support for you, like dynamic arrays or mutable records). (3) A Legality Rule like "no returns of types with access discriminants", or "no declaration of access discriminants", or "no declaration of access parameters" probably would help. ;-) But barring that, I don't quite see how you could craft a static rule to deal with things that are fundamentally dynamic (access parameters, returns of access discriminants, etc.) At best, you could reject anything where the scope is unknown at the call site, but I would be very surprised if that didn't scoop up a lot of cases that are perfectly fine. Especially as we would have to assume the worst about T'Class (that it has access discriminants), so such a rule would apply to any function returning T'Class. I think you'd end up rejecting almost all calls that had an access parameter and returned T'Class -- that's not going to fly. (I've got a lot of those in the Claw Builder. :-) (4) The "simple" implementation model always looked too good to be true, and the requirement to do the minimum already showed that it was going to not work in the long run. The question I have is whether it is possible to implement any other implementation that works. On a mono-processor or shared memory machine, you could use the stack frame addresses as an indication of the scope (although compares that are not for equality are problematical, as there are multiple task stacks, and they have to be in *some* order in memory, such that "<" might succeed even though there is a problem [when multiple tasks are involved]). If tasks are mapped to different processors with some unshared memory, the problem is harder -- but in that case, one couldn't really create 'Access to unshared memory, so there probably isn't much point in worrying about that. So I would suggest thinking hard about an implementation model of passing pointers to stack frames as an accessibility indication rather than integers. (On most machines, that will not change the size passed as parameters anyway.) Why does that not work? (It wouldn't surprise me if it didn't, but I'd like to know why.) **************************************************************** From: Bob Duff Sent: Thursday, July 28, 2011 1:22 PM > At the very least, it appears that the AARM's description of the > intended implementation model needs to be updated; the ARG may decide > that other actions are needed if it is determined that the language as > currently defined is too difficult/expensive to implement. This is an excellent write-up. For the first time (given this write-up, plus our private conversations), I feel like I actually understand what's going on! (It won't last -- I'm going to save your email for future reference.) I vote for "too difficult/expensive to implement". Maybe we can come up with some compile-time rules that prevent the problems. But that may be impossible; the reason we don't know what level to pass will be the same reason we don't know that it should be illegal (without forbidding useful stuff). Or maybe Post-Compilation rules? Maybe making the run-time checks more conservative would work. These are all convoluted examples, so maybe we could say "if we don't know what level to pass, raise an exception, or in some sense assume the worst". As a last resort, maybe we should make some things erroneous. That should be easier to define, because we can depend on global information not available to the compiler. I can rationalize that by saying: Most access values are used to build heap-allocated data structures, so most dangling pointers are caused by premature Unchecked_Deallocation. The accessibility checks are no help there. And quite often, when you have pointers to stack-allocated things, you need to use 'Unchecked_Access; again, accessibility checks are no help. So why get excited if the accessibility checks are not 100% bullet-proof? -- it's already the case that they only prevent SOME dangling pointers. Needs more thought -- I don't have any concrete suggestions right now. **************************************************************** From: Bob Duff Sent: Thursday, July 28, 2011 1:42 PM > (1) Your mind sure is twisted. :-) ;-) > (2) Accessibility checks for objects aren't worth the headaches. I've > only once written code where 'Access could even be used, otherwise > I've always had to turn them off by using 'Unchecked_Access and do my own management. The GNAT sources contain 305 occurrences of 'Unchecked_Access, and 2409 occurrences of 'Access, so "only once" is not a universal experience. But I tend to agree with your point that making the run-time accessibility checks bullet proof is not worth a huge implementation effort. > (3) A Legality Rule like "no returns of types with access > discriminants", Note that our new syntactic sugar for containers depends heavily on this feature! >...or > "no declaration of access discriminants", or "no declaration of access >parameters" probably would help. ;-) OK, I see the smiley. How about "you can't initialize an access discriminant from an access parameter"? And "you can't return an anonymous access result that comes from an access parameter"? >...But barring that, I don't quite see how you could craft a static >rule to deal with things that are fundamentally dynamic (access >parameters, returns of access discriminants, etc.) At best, you could >reject anything where the scope is unknown at the call site, but I >would be very surprised if that didn't scoop up a lot of cases that are >perfectly fine. Especially as we would have to assume the worst about >T'Class (that it has access discriminants), so such a rule would apply >to any function returning T'Class. For the same reason, whatever overhead is involved, applies to any function returning T'Class (hence is distributed overhead). > So I would suggest thinking hard about an implementation model of > passing pointers to stack frames as an accessibility indication rather > than integers. (On most machines, that will not change the size passed > as parameters anyway.) Why does that not work? (It wouldn't surprise > me if it didn't, but I'd like to know why.) I'm not sure, but it sounds like an implementation earthquake, because in GNAT (and I suppose most compilers), only the front end knows about accessibility levels, and only the back end knows about static links / frame pointers. On the other hand, I suppose you can get at your own frame-pointer-like thing by simply taking 'Address of the first local object (and concoct a zero-sized one if there are none). **************************************************************** From: Gary Dismukes Sent: Thursday, July 28, 2011 2:03 PM > > So I would suggest thinking hard about an implementation model of > > passing pointers to stack frames as an accessibility indication > > rather than integers. (On most machines, that will not change the > > size passed as parameters anyway.) Why does that not work? (It > > wouldn't surprise me if it didn't, but I'd like to know why.) > > I'm not sure, but it sounds like an implementation earthquake, because > in GNAT (and I suppose most compilers), only the front end knows about > accessibility levels, and only the back end knows about static links / > frame pointers. Right, I don't think we want to go down that path. > On the other hand, I suppose you can get at your own > frame-pointer-like thing by simply taking 'Address of the first local > object (and concoct a zero-sized one if there are none). That occurred to me as well, but I believe that won't work on VM-based implementations such as for JVM (not sure about .NET). **************************************************************** From: Steve Baird Sent: Thursday, July 28, 2011 2:03 PM > This is an excellent write-up. For the first time (given this > write-up, plus our private conversations), I feel like I actually > understand what's going on! (It won't last -- I'm going to save your > email for future reference.) Thanks. As you know, it took me a good while before I understood things well enough to produce this write-up. Thanks to you, Gary, and Tuck for helping me get to that point. > Maybe making the run-time checks more conservative would work. These > are all convoluted examples, so maybe we could say "if we don't know > what level to pass, raise an exception, or in some sense assume the > worst". That would help with the Ada2012 problem. In implementation terms, a runtime accessibility check would be defined to fail if it involves the comparison of two "none of the above" values. > As a last resort, maybe we should make some things erroneous. > That should be easier to define, because we can depend on global > information not available to the compiler. > I can rationalize that by saying: Most access values are used to > build heap-allocated data structures, so most dangling pointers are > caused by premature Unchecked_Deallocation. The accessibility checks > are no help there. And quite often, when you have pointers to > stack-allocated things, you need to use 'Unchecked_Access; again, > accessibility checks are no help. So why get excited if the > accessibility checks are not 100% bullet-proof? -- it's already the > case that they only prevent SOME dangling pointers. When people use Unchecked_Deallocation or Unchecked_Access, they know that avoiding dangling pointers is their own responsibility. The constructs we are talking about seem different to me. I understand the argument that defining the problems away by declaring them to be erroneous is ok because nobody in their right mind does anything close to the sort of stuff that is in these examples, but this seems like a slippery slope to me. **************************************************************** From: Randy Brukardt Sent: Thursday, July 28, 2011 2:58 PM ... > > (3) A Legality Rule like "no returns of types with access > > discriminants", > > Note that our new syntactic sugar for containers depends heavily on > this feature! > > >...or > > "no declaration of access discriminants", or "no declaration of > >access parameters" probably would help. ;-) > > OK, I see the smiley. > > How about "you can't initialize an access discriminant from an access > parameter"? And "you can't return an anonymous access result that > comes from an access parameter"? I suspect that people using our new syntactic sugar would do exactly that, if they don't want to use an aliased parameter. At least aliased parameters don't have the different level problem (they are assumed to be the same as the return), but I have to wonder if we wouldn't find a similar problem with them. And, of course, I've dubious that that is enough. > >...But barring that, I don't quite see how you could craft a static > >rule to deal with things that are fundamentally dynamic (access > >parameters, returns of access discriminants, etc.) At best, you could > >reject anything where the scope is unknown at the call site, but I > >would be very surprised if that didn't scoop up a lot of cases that > >are perfectly fine. Especially as we would have to assume the worst > >about T'Class (that it has access discriminants), so such a rule > >would apply to any function returning T'Class. > > For the same reason, whatever overhead is involved, applies to any > function returning T'Class (hence is distributed overhead). Right, but we already know that (from AI-51 and AI-234 - in particular, reread the Implementation Note 3.10.2(10.d.2-7/3)). There is nothing new about that. Indeed, that's Tucker's bait-and-switch: when we complained about the overhead of dynamic checks during the design of Ada 2005, he came up with a static model. We then agreed to allow these features into Ada 2005 (they would have never made it in otherwise). A few years later, Steve points out problems with the static model, and Tucker announces that we have to use a dynamic model with all of the overhead that we would never have agreed to for Ada 2005. Nice. [Note: I don't think Tucker did this on purpose and don't mean to imply that he did, but the effect was instead of killing the nasty coextension idea immediately and completely, we now have a permanent morass with distributed overhead to boot.] > > So I would suggest thinking hard about an implementation model of > > passing pointers to stack frames as an accessibility indication > > rather than integers. (On most machines, that will not change the > > size passed as parameters anyway.) Why does that not work? (It > > wouldn't surprise me if it didn't, but I'd like to know why.) > > I'm not sure, but it sounds like an implementation earthquake, because > in GNAT (and I suppose most compilers), only the front end knows about > accessibility levels, and only the back end knows about static links / > frame pointers. There is no interaction between dynamic and static accessibility levels in this model (you would *never* check a static level against a dynamic level, you would always check two dynamic levels or two static levels), so I don't know why that would matter. I do understand that it would take substantial implementation effort (it requires redoing all of the existing dynamic checks at a minimum), but if that would detect *all* of the errors properly *and* still be reasonably implementable, then I think the language should adopt that as the intended implementation model. But I agree that this is a big IF. I wanted to focus thought on whether that IF is true (especially the first part, because it if doesn't detect all of the errors, it couldn't be worth it). But I do think we want to avoid erroneousness if we can. It's clear to me that the "integer level" model is dead, and has never been all that alive (it was a hack at best). So I wanted to look at alternatives; if there is a practical implementation (given a clean slate) that does detects all of the errors and not too much, then we have a very different trade-off than if no such implementation exists. So I think we need to find an implementation that would detect all of the problems and not too much (forget everything that compilers actually are doing for the moment), so we have a clear idea of how much overhead that implementation causes. Only then can we make an informed decision on whether erroneousness or bizarre restrictions are worthwhile. I surely can't do it now. (And there is no rush - this is not going into Ada 2012 in any case.) > On the other hand, I suppose you can get at your own > frame-pointer-like thing by simply taking 'Address of the first local > object (and concoct a zero-sized one if there are none). Right. Or something similar. (And I'm not sure why you would need a dynamic level if there are no objects or access collections [which require local data structures] -- why would you be comparing it??) **************************************************************** From: Tucker Taft Sent: Thursday, July 28, 2011 4:09 PM I think Randy might be headed the right direction here. Basically forget the static accessibility approximation in code where there is any danger of this sort of nastiness, and go with a true dynamic accessibility level. My guess is that code with no access parameters/results, no nested extensions, no nested access-to-subp types need not worry about these problems. Hopefully that is most of the world. Code that has any of these troublesome features would move toward passing around dynamic accessibility levels/descriptors as an additional implicit parameter. **************************************************************** From: Randy Brukardt Sent: Thursday, July 28, 2011 7:58 PM ... > How about "you can't initialize an access discriminant from an access > parameter"? And "you can't return an anonymous access result that > comes from an access parameter"? Those wouldn't work by themselves, because you could "launder" an access parameter by storing it in a local SAOAAT. (Stealing Steve's moniker.) Recall that the accessibility of a SAOAAT is the same as the assigned value, including a passed-in parameter. You could also ban access discriminants coming from a SAOAAT, but that seems pretty severe; flow analysis of the usage of a SAOAAT surely is more complex than existing legality rules. In any case, I'd be suspicious of adopting a complex Legality Rule to ban this particular problem case, because I think it is only a matter of time before someone runs into some other combination that's also a problem. We tried that strategy with general-access-to-unconstrained, and we plugged a new hole every year until we finally gave up with Ada 2005. (Would this problem come up when a generic in out parameter is used as an access discriminant, and the instance is local?? Etc.) P.S. SAOAAT = Stand-Alone Object of an Anonymous Access Type. **************************************************************** From: Jean-Pierre Rosen Sent: Friday, July 29, 2011 6:09 AM > This is an excellent write-up. For the first time (given this > write-up, plus our private conversations), I feel like I actually > understand what's going on! (It won't last -- I'm going to save your > email for future reference.) > + 1 I'll save it, just in case I decide to start a training session "Introduction to accessibility levels - 5 days" ;-) From what I understood from the discussions, it seems to me that: 1) Making it safe is not practically doable 2) Restricting to safe cases would be too restrictive. I don't like the idea of a false feeling of safety. Wouldn't it be possible to restrict to safe cases, and have a gateway through some Unchecked gizmo to go to the (necessary) unsafe state? **************************************************************** From: Bob Duff Sent: Friday, July 29, 2011 1:28 PM > ... > > How about "you can't initialize an access discriminant from an > > access parameter"? And "you can't return an anonymous access result > > that comes from an access parameter"? > > Those wouldn't work by themselves, because you could "launder" an > access parameter by storing it in a local SAOAAT. (Stealing Steve's > moniker.) I've always been opposed to using dynamic accessibility levels for SAOOAAAATs (however many "A"s it has). > Recall that the accessibility of a SAOAAT is the same as the assigned > value, including a passed-in parameter. You could also ban access > discriminants coming from a SAOAAT, but that seems pretty severe; flow > analysis of the usage of a SAOAAT surely is more complex than existing legality rules. I don't understand. By "severe" do you mean "overly restrictive for the programmer"? I don't mind that -- I've gotten along fine for years without ever using SAOAATs, so I wouldn't mind restricting them in the discrim case. But then you say, "; flow...", and I don't see what that has to do with being "severe". > In any case, I'd be suspicious of adopting a complex Legality Rule to > ban this particular problem case, because I think it is only a matter > of time before someone runs into some other combination that's also a > problem. We tried that strategy with general-access-to-unconstrained, > and we plugged a new hole every year until we finally gave up with Ada > 2005. (Would this problem come up when a generic in out parameter is > used as an access discriminant, and the instance is local?? Etc.) You're probably right. But what can we do, other than come up with some rules and hope they're right, and fix them when we notice otherwise? **************************************************************** From: Randy Brukardt Sent: Friday, July 29, 2011 2:07 PM > You're probably right. But what can we do, other than come up with > some rules and hope they're right, and fix them when we notice > otherwise? There are clearly two other choices: (1) Do nothing - which requires implementations to do it right. So far as I can tell, this is implementable -- it would require changing what compilers currently do, but would not be incompatible or inconsistent (you'd get the same answer in simple cases). I'm rather unsure why this isn't acceptable [it seems to me that has to be done in any case to deal with the "incomparable masters" checks of 4.8 and 6.5]. New language features are going to break some eggs, and it's fairly clear that Ada 2005 broke a lot of eggs that we didn't realize at the time. (2) Drop some or all of the dynamic accessibility checks in favor of leaving the associated cases erroneous. That might require some new rules, but they'd be dynamic rules, not Legality Rules, meaning that they wouldn't have all of the generic contract complications. [And I was *only* speaking about Legality Rules in my previous comment.] I strongly prefer "do it right" to the other options -- and I'd like to know if there is any real problem with a purely dynamic dynamic check. (Say using stack frames.) Other than "we don't do it that way now", which is irrelevant if the alternatives are erroneousness or a permanent cascade of every more arbitrary and restrictive rules -- both of which are far worse alternatives. **************************************************************** From: Steve Baird Sent: Friday, July 29, 2011 6:51 PM > There are clearly two other choices: (1) Do nothing - which requires > implementations to do it right. So far as I can tell, this is > implementable > -- it would require changing what compilers currently do, but would > not be incompatible or inconsistent (you'd get the same answer in simple cases). > I'm rather unsure why this isn't acceptable [it seems to me that has > to be done in any case to deal with the "incomparable masters" checks > of 4.8 and 6.5]. I think this is an important point. I'm guessing that you are right that "it has to done" in order to implement the checks you mentioned, but I haven't thought about it enough. If it is true that we already need to develop some more general mechanism in order to handle these accessibility checks (this is what I was talking about in the original message when I referenced AI05-0024), then the "no RM changes - just implement it" solution might become more attractive. Details, of course, are needed (particularly about the amount, if any, of distributed overhead). > ... -- and I'd like to know > if there is any real problem with a purely ... dynamic check. (Say > using stack frames.) As I mentioned in the earlier message, there may be problems with directly accessing the frame pointer. Say the portion of the compiler which knows about the dynamic semantics of Ada generates some intermediate representation in which this sort of manipulation cannot be expressed. Or, as I mentioned earlier, consider the interactions with optimizations such as subprogram hoisting, inlining, and static link elimination. One might give up on accessing the frame pointer directly and instead have the aforementioned Ada-knowledgeable part of the compiler generate its own data structure to capture the needed information. The compiler generates a small record object in each "interesting" frame containing, say, a static nesting level and a link to the corresponding object of the nearest statically enclosing frame which has one. This is only an incomplete sketch of an approach, but this is the sort of thing I was talking about in the original message when I said "FE-generated data structures of some sort may be required". **************************************************************** From: Randy Brukardt Sent: Friday, July 29, 2011 8:18 PM Using a separate data structure automatically means "distributed overhead", of course. The stack frame approach is appealing because it doesn't have such overhead (we're already creating stack frames). OTOH, stack frames probably don't correspond exactly to dynamic masters (masters that are a subprogram call are very unlikely to have a frame of their own, and many compilers combine the frames for all blocks into one). But perhaps the data structures associated with finalization of masters could be "borrowed" for this purpose (they surely have the correct run-time nesting). There still would be distributed overhead, but it's overhead that already exists and the added overhead would probably be zero in many frames. (Janus/Ada aggressively tries to eliminate finalization data from frames; that would be somewhat less possible if it also was used for dynamic accessibility checks. Thus there still would be a bit of overhead.) **************************************************************** From: Steve Baird Sent: Friday, November 30, 2012 7:07 PM Thanks to Gary, Bob, and Tuck for much useful discussion and review on this one. [Followed by the !discussion of version /01 of this AI.] **************************************************************** From: Randy Brukardt Sent: Friday, November 30, 2012 11:20 PM > Problems with the the "small integer" model for representing > accessibility levels and performing run-time accessibility checking > have been identified (see > mail message of July 28, 2011, previously filed in this AI). At some point, these problems will have to be put into the body of the AI. An AI is intended to be readable without referring to the e-mail section (it's customary for some users to strip that off). > This is only intended to demonstrate that at least one viable > implementation model exists and to make this available to language > implementors as an option. It is not intended to introduce any > language changes, but rather to offer one way of meeting the > requirements that are already implicit in the language definition. But we at least need to rewrite the AARM notes to not suggest a model that doesn't work. Someone is going to have to take that short stick. ... > We describe the proposal in the "software present tense", as a fait > accompli. I presume this means you haven't actually implemented this to see if it works. :-) ... > Let's look at how this model breaks down in the case of this example. > When P3 is called, the call stack is > P3 > Call_Proc > P2 > Call_Proc > P1 > Accessibility_Test > > The two accessibility levels passed into P3 correspond to the two > calls to Call_Proc. One of these two levels is longer lived than the > level of the call to P2 (which is also the level of Ref, the target > type of the access type conversions) and one of them is shorter-lived, > but this essential distinction is lost. The first access type > conversion should succeed and the second should fail, but there is > insufficient information to make this distinction. I admit, I lost you completely at this point. I don't have time to work this example through on a whiteboard (which might be the only way to understand it -- but I would have expected the two parameters to point at different frames (frame objects) if they have a different lifetime. How could it be otherwise here? Perhaps this has something to do with the "normalization" step of the small-integer model, which never made sense to me, either. (I know it's been explained to me, but it is so nonsensical that it doesn't stick. (Of course, I can't seem to understand how one could make static links work, either [and despite repeated attempts to explain it to me], so I'm the wrong person to understand such a discussion. Plus I always think about these problems mentally using displays, which might give different results in some of these examples, so I might be missing the problem because there isn't one...) Anyway, I read the rest of this, but I don't understand the problem very well so I can't give any reasonable thoughts on the answer. **************************************************************** From: Randy Brukardt Sent: Saturday, December 1, 2012 12:14 AM ... > I admit, I lost you completely at this point. I don't have time to > work this example through on a whiteboard (which might be the only way > to understand it -- but I would have expected the two parameters to > point at different frames (frame objects) if they have a different > lifetime. How could it be otherwise here? Having been unable to stop thinking about this (instead of doing critical work for the upcoming meeting ;-), I think the problem is that you are trying to solve the problem the wrong way. Specifically, dynamic masters are nested dynamically, and their static links are pretty much irrelevant. If you try to treat this like the static checks (or the small integer model, for that matter), you are working harder than necessary. So I think your Level_Objects are much too complex (and expensive to create). I believe that there is a simple solution and usually very efficient solution that piggybacks on the finalization chain mechanism. (Of course, if your compiler just spent $$$$ and time to get rid of that, you're going to be out of luck, but in any case we're trying to find a simple reference implementation, and the RM reference implementation for finalization uses a chain.) The basic idea is to ensure that the first object in every master is the special Level_Object that you described in your paper, and it is linked to the innermost enclosing *dynamically* enclosing master of this frame. (This is dirt cheap in Janus/Ada because such an object already exists, all I have to do is add the pointer into it.) And how do you find that pointer to the enclosing master's level object? The thumb points to it (or immediately before it, I forget) when you enter the scope. The finalization setup already has all of the needed information. (This lets us skip levels for which no level object or finalization is needed; nothing bad will happen.) The check is essentially the same as you suggest (run the chain looking for the frame). Note that if one is willing to have a bit more fixed overhead, and the single stack of a task is contiguous, one can stick the current task id into the Level_Object. In that case, preceding the check with: if A.Task_Id = B.Task_Id then if A.Link > B.Link then -- Error. -- else OK. end if; else -- Run chain as before. end if; Makes the check dirt cheap unless the levels are from two different task's stacks. (Which should be very rare!) [Although simply special-casing library-level probably is enough to make the checks cheap enough, since the vast majority of types are declared at library-level.] I'm pretty sure this ought to work for your example (the levels belong to different stack frames for the two parameters, and surely cannot be the same in this case). Whether it works in all cases is something to think about some other day. Now, moving on to critical work... **************************************************************** From: Bob Duff Sent: Saturday, December 1, 2012 8:34 AM >...Specifically, dynamic masters are > nested dynamically, and their static links are pretty much irrelevant. I think any method that involves chasing dynamic links will be too inefficient in some cases. (If my name were Randy, I'd use words like "non-starter". ;-)) Imagine a recursive procedure that takes an access parameter. You could easily get thousands of stack frames, and if you have an accessibility check for each call, it's quadratic in the recursion depth. Static chains, on the other hand, are (approximately) never longer than 3. We do indeed need a whiteboard or equivalent to understand this stuff. I understood it briefly during the meeting with Steve and Tuck, but that was while staring at a picture Steve had drawn. > if A.Task_Id = B.Task_Id then That's an interesting idea. > Now, moving on to critical work... With 2020 still 7 years away, I wouldn't consider anything critical, but yeah, OK, get back to work. ;-) **************************************************************** From: Randy Brukardt Sent: Saturday, December 1, 2012 2:27 PM > >...Specifically, dynamic masters are > > nested dynamically, and their static links are pretty much irrelevant. > > I think any method that involves chasing dynamic links will be too > inefficient in some cases. (If my name were Randy, I'd use words like > "non-starter". ;-)) > > Imagine a recursive procedure that takes an access parameter. > You could easily get thousands of stack frames, and if you have an > accessibility check for each call, it's quadratic in the recursion > depth. Only if your check is stupid. :-) The only time the check needs to chase anything is if the objects are not library level and are possibly incomparable (come from different tasks). I think it would be extremely difficult to create an example like that which was quadratic (I'm sure it would be possible, but surely would be pathological). Besides that, I personally don't care if it take 6 months to execute a check on a anonymous access parameter. These checks are rare in any case (most such parameters are just dereferenced which don't require any checks), and they are (as one B. Duff said) a "tripping hazard" in any case -- I'd hope that the users saw the error of their ways and used "in out" or "aliased in out" or a named access instead (none of which require complex dynamic checks). > Static chains, on the other hand, are (approximately) never longer > than 3. True enough. But if you have as much overhead as in Steve's description to *create* those data structures (recall that they're dynamically sized, which in Janus/Ada would mean heap allocation!) -- and for the vast majority of anonymous access parameters they'll never be used at all (I've only used anonymous access to get "in out reference" parameters on functions, not necessary in Ada 2012 and in any case, these never generated any checks). So that overhead is completely wasted. Piggybacking on a mechanism that already exists (in Janus/Ada at least) has less overhead, and the objects are statically sized. > We do indeed need a whiteboard or equivalent to understand this stuff. > I understood it briefly during the meeting with Steve and Tuck, but > that was while staring at a picture Steve had drawn. > > > if A.Task_Id = B.Task_Id then > > That's an interesting idea. It's the only reason that I agreed to "incomparable levels" in the first place -- the check is cheap in all cases except when the levels appear incomparable. Probably I should repeat the entire check algorithm again (it's in the e-mail of the AI for "incomparable levels"). When checking that "A shall not be deeper than B, else Program_Error is raised", we ought to do the following: if A.Level = Library_Level then return; -- OK elsif B.Level = Library_Level then raise Program_Error; -- The case where both levels are library-level is included in the first branch. elsif A.Task_ID = B.Task_Id then -- The levels belong to the same task (this includes both the same level). -- We assume that the stack for a single task is contiguous. if A.Level'Address > B.Level'Address then -- The direction ("<" or ">") depends on which way your stacks -- grow in memory. raise Program_Error; else return; -- OK. end if; else -- Two different tasks (can't be the same level). -- A has to be on B's chain. Temp := B.Level.Link; while Temp /= null loop if Temp = A then return; -- OK. else Temp := Temp.Link; end if; end loop; -- If we get here, we didn't find A on B's chain. raise Program_Error; end if; This is ordered in the order of likelihood, so the most common cases are checked first and use the least instructions to check. Note that the "two different tasks" case is quite rare, and probably will fail most of the time. So it's hard to get worried about how expensive it is. Besides, these dynamic checks themselves are quite rare in real code. Usually, rare * rare = don't care! > > Now, moving on to critical work... > > With 2020 still 7 years away, I wouldn't consider anything critical, > but yeah, OK, get back to work. ;-) Sorry, you misunderstood. While Ada 2012 does have a couple of critical bugs that need fixing yesterday, that's not what I meant. I meant "work critical to my continued employment in this position". Specifically: (1) People are coming from all over the world for this ARG meeting (I realize you just have to take the T or something, but that's not the case for most of us). They won't be happy if the agenda is mostly empty because I didn't get the work done. (2) I have a HILT panel on Thursday (please come, BTW), and I'll look pretty clueless if I don't have anything to say. That's why I'm here right now, rather than relaxing and watching football. **************************************************************** From: Tucker Taft Sent: Saturday, December 1, 2012 8:11 PM >> Static chains, on the other hand, are (approximately) never longer >> than 3. > > True enough. But if you have as much overhead as in Steve's > description to > *create* those data structures (recall that they're dynamically sized, > which in Janus/Ada would mean heap allocation!) ... There is no need for dynamically-sized structures. Steve might have described them that way, but in our discussions, these were linked stack-based structures, each node of which was of fixed size. When we discussed it, we had two kinds of (singly-linked) lists of frame ids: one kind of list represented a particular named access type (which is the target of a conversion or an allocator), and consisted of one link per static nesting level enclosing the declaration of the access type; the other kind of list represented a set of levels for a particular run-time tag or access parameter, where the set starts out as a single level, but which grows when an access parameter is passed to a more nested subprogram, by linking into the set the frame-id for the outer subprogram which received the original access parameter. This corresponds exactly to the situation where the small-number approach requires a possible fixup. The check is to verify that at least one of the members of the set appears in the list representing the target access type. If we treat the two lists as representing sets of frame ids, then it is a check to see if the two sets overlap at all. In any case, a white board would definitely be helpful to explain this. I think the overhead is pretty low overall. **************************************************************** From: Jean-Pierre Rosen Sent: Sunday, December 2, 2012 4:47 PM > With 2020 still 7 years away, I wouldn't consider anything critical, > but yeah, OK, get back to work. ;-) And then, ASIS raises its ugly head... **************************************************************** From: Steve Baird Sent: Monday, December 3, 2012 11:34 AM > There is no need for dynamically-sized structures. Steve might have > described them that way, but in our discussions, these were linked > stack-based structures, each node of which was of fixed size. Even in my description, there is no *need* for dynamic-sized structures (although such structures are an implementation option). Suppose we have a subprogram for which we need to declare an accessibility level object. The idea is that the number of predecessors stored in that object is known statically - one for the "static link" and then a known additional number (usually zero or one) for each parameter. Consider, however, a routine with a bunch of anonymous-access-to-object typed parameters. The straightforward approach would include a predecessor for each one. If it turns out at runtime that many of the parameters for some particular execution of the subprogram body have the same accessibility level (e.g., they designate library-level objects), then this would result in storing repeated (and therefore redundant) predecessors. This is ok but one could imagine an implementation trying to detect at least some cases like this and reduce the number of predecessors by eliminating redundant ones. In that case, I agree, we do end up with a dynamically constrained object, but even then we have a reasonable statically-known upper bound on the size of the object (i.e., the size we would have used in the unoptimized scheme) which could be used to avoid dynamic storage allocation. **************************************************************** From: Randy Brukardt Sent: Monday, December 3, 2012 4:32 PM ... > This is ok but one could imagine an implementation trying to detect at > least some cases like this and reduce the number of predecessors by > eliminating redundant ones. In that case, I agree, we do end up with a > dynamically constrained object, but even then we have a reasonable > statically-known upper bound on the size of the object (i.e., the size > we would have used in the unoptimized scheme) which could be used to > avoid dynamic storage allocation. I think you're missing the big picture here. This implementation is amazingly complex, and the number of people who understand it can be counted on one hand (something I highly doubt is going to change significantly no matter how many whiteboard presentations are given). Tucker says that "This corresponds exactly to the situation where the small-number approach requires a possible fixup." -- which I can believe -- but the number of people who understand why that fixup is necessary can be counted on two hands (and I'm being generous). I know that our compiler uses that fixup in some situations, but I have no real idea why or whether it is implemented right -- it just passes the tests that we have. (I certainly shouldn't be counted on either of these hands at the moment.) I proposed a simpler implementation that: (A) Piggybacks on the existing *reference* implementation of finalization; (B) Directly corresponds to the rules being checked; (C) As the same or better per-master overhead in the default implementation (only one word per master is needed); (D) Has the same overhead in passing "Level_Objects", and allows the most masters (that don't need a Level_Object) to skip having them. The only downside is that the checks might be expensive in some *unusual* cases. I point out: (1) Those cases are quite unusual (they need both recursive routines and dynamic checks in the same subprograms); (2) Ada 2012 tries hard to eliminate dynamic checks. A significant reason for the inclusion of "in out" parameters on functions was to get rid of the dynamic checks associated with the workaround. Similarly, the motivating reason for including "aliased" parameters is that these are guaranteed to work with the return object of a function (as any needed checks are made at the call site) -- there should be no dynamic checks involved with those either. So, in new code, the presence of dynamic checks pretty much indicate a design error -- it's hard to worry about the performance of things that shouldn't occur. (3) So we're mostly left with the performance of legacy code, and for that, there is a clear solution if adding a small amount of additional overhead in the Level_Object is acceptable (and task stacks are contiguous, which they usually are), in which case the only time the check could become expensive is when the levels belong to different tasks and neither is library level. And then to actually become expensive, recursion would also need to be involved (you'd need hundreds of nested masters before the performance could become at all noticeable). That ought to be rare enough to be ignorable (I would really doubt that anyone would be complaining about the performance of something so rarely encountered). It's valuable to work out an alternative implementation for those not using finalization chains and thumbs (which I suppose includes GNAT), but I really doubt that we should talk about that implementation in the AARM notes, simply because it is so complex and frankly, bizarre. And this AI is primarily about a reference implementation for the AARM; what GNAT chooses to do is essentially irrelevant for the AARM. **************************************************************** From: Tucker Taft Sent: Monday, December 3, 2012 8:27 PM > ... It's valuable to work out an alternative implementation for those > not using finalization chains and thumbs (which I suppose includes > GNAT), but I really doubt that we should talk about that > implementation in the AARM notes, simply because it is so complex and > frankly, bizarre. And this AI is primarily about a reference > implementation for the AARM; what GNAT chooses to do is essentially irrelevant for the AARM. GNAT is relevant since it tends to be the first "real" implementation of the language features. But in any case, I think we should probably leave most of the details out of the AARM, and put them in separate design notes, or perhaps in AIs. We can describe both alternatives at a high level, and give a reference to the AI or wherever we decide to put the details. **************************************************************** From: Randy Brukardt Sent: Monday, December 3, 2012 9:02 PM ... > GNAT is relevant since it tends to be the first "real" > implementation of the language features. Well, sure, but we all know that real compilers have all kinds of gunk to deal with that we surely don't want to be discussing in terms of a reference implementation. > But in any case, I think we should probably leave most of the details > out of the AARM, and put them in separate design notes, or perhaps in > AIs. > We can describe both alternatives at a high level, and give a > reference to the AI or wherever we decide to put the details. I agree that we don't want a lot of details. Preferably, we'd have a level of detail roughly the same as we have for implementing finalization, and then a suggestion to read AI12-0016-1 for more details and alternative implementations. ****************************************************************