A "RecursiveConstants" attribute

[Remi Forax]

I like this approach, this is fine for me.

Rémi

----- Mail original -----
> De: "daniel smith" <daniel.smith at oracle.com>
> À: "valhalla-spec-experts" <valhalla-spec-experts at openjdk.java.net>
> Envoyé: Samedi 17 Février 2018 00:32:17
> Objet: Re: A "RecursiveConstants" attribute

>> On Jan 31, 2018, at 2:50 PM, Brian Goetz <brian.goetz at oracle.com> wrote:
>> 
>> OK, so the goal is clearly to *prohibit* cyclic constants by enforcing a depth
>> constraint on condy-in-condy nesting.  I like this goal much better, and I see
>> how the solution addresses it.
>> 
>> Still, I have to wonder whether its worth the complexity of capturing it
>> explicitly with a new (stackmap-like) attribute, which must be specified, and
>> gives us more chances for the classfile to be out of sync with itself, for the
>> goal of preventing something that can't usefully happen anyway -- as we
>> discussed previously, trying to actually resolve a cyclic constant will likely
>> result in SOE, so such classfiles are pretty much useless and therefore not
>> likely to spread very far.
> 
> This is a reasonable critique. Another critique is that the cost of tracking
> down and parsing an extra attribute will undo a lot of the performance benefit
> of having it, perhaps even causing a net slowdown.
> 
> As we've discussed the idea a little more, my inclination (raised in the meeting
> this week) is to give up on trying to add structural restrictions on constant
> pools designed to facilitate cycle detection. It seems like we can, in fact,
> detect cycles without extra guidance, and with minimal overhead in most cases.
> Some details below.
> 
> Big picture, the most attractive path forward seems to be:
> - In 11, a CONSTANT_Dynamic with a cycle is an "error", reported via SOE at
> resolution time
> - When we introduce lazy condy resolution, we move the error detection to class
> load time, with a check that we're comfortable isn't disrupting startup time
> - As other potentially-cyclical constants are introduced, we use the same load
> time checks
> - We never require extra information from the compiler, or reject classes that
> are hard to prove cycle-free
> 
> One nice thing about that last point is that we don't have to worry about
> incompatible support for "hard" classes in different releases.
> 
> I'd love to hear about some experiments with this. We're talking about
> performance impact, and all discussion to this point has been hypothetical.
> Would be good to get some concrete feedback.
> 
> —Dan
> 
> -----
> 
> Details:
> 
> We started with a rule for format checking (JVMS 4.8) that says it's illegal for
> a CONSTANT_Dynamic (or, in the future, other potentially-cyclical constants) to
> refer, via static arguments, to itself—directly or indirectly. But we quickly
> decided this sounded expensive, and we didn't want a heavy validation step to
> mess with startup time.
> 
> Hence, we explored various ways to prohibit otherwise-valid classes that would
> be hard to prove cycle-free. Something like the RecursiveConstants attributes
> seems to be the best option in that space.
> 
> However, scrutinizing the original assumption, it seems reasonable that we can
> optimize the check so that it's extremely lightweight when references are
> "backward" (to previous entries in the constant pool), and only performs more
> expensive analysis when references are "forward". Most classes should naturally
> use backward references exclusively, since entries tend to be generated
> bottom-up. (In theory. If there are counter examples produced by any mainstream
> bytecode generators, that would be good to know.)
> 
> So a dumb (worst case O(n^2)) but fast (very low constant cost) check could look
> something like:
> 
> void checkCP(int i) {
>    switch (tag(i)) {
>        case CONSTANT_Dynamic:
>            ...
>            for (int j : condyStaticArgs(i)) {
>                if (j >= i && tag(j) == CONSTANT_Dynamic) {
>                    assertUnreachable(i, j); // can't reach i from j
>                }
>            }
>            ...
>        ...
>    }
> }
> 
> It's already necessary to check that constant pool references are well-typed, so
> everything up to 'assertUnreachable' here is practically free*. The
> 'assertUnreachable' call might be somewhat expensive, but it will rarely be
> called in practice (and even then, we don't expect many structures to be
> particularly deep).
> 
> (*In the particular case of CONSTANT_Dynamic, there's an indirection through
> BootstrapMethods. If a class heavily shares BootstrapMethods entries, then
> there's a new cost here, iterating over the same static arguments multiple
> times. Some optimization could be done to speed that up. For example, if there
> are no forward references on the first pass, there will be no forward
> references on later passes, when i is a larger number.)
> 
> A good worst-case test would be a constant pool without cycles, built entirely
> out of forward references, consisting of lots of deep CONSTANT_Dynamic trees.
> Needless to say, we don't expect to encounter classes like this in the wild.
> But, if we do, the big benefit here is that, while they'll be a little slower
> to load, they'll still work.