617156 - Avert the Api Version Number Apocalypse

Status: RESOLVED FIXED

(Tamarin Graveyard :: Virtual Machine, defect)

Description

[Steven Johnson]

Stan Switzer comments in an external forum:

Current plans anticipate versioning AIR and the Player in every minor release. The present implementation uses a 31-bit mask for each (versioned) definition to indicate which versions a definition is present in. Some 14 bits are already in use, and each new release will require at least one bit and perhaps two, depending on whether Flash and AIR can share a version number. Sharing version numbers (which will require some tooling changes) will buy time, but we will still run out of version bits uncomfortably soon.


One way to look at product version relations is as an partial ordering of versions where v1 < v2 if every API defined in v1 is defined in v2.
e.g.:

FP_9_0 < FP_10_0 < FP_10_0_32 < FP_10_1 < FP_SYS
AIR_1_0 < AIR_1_5 < AIR_1_5_1 < AIR_1_5_2 < AIR_2_0 < AIR_SYS
FP_9_0 < AIR_1_0
FP_10_0 < AIR_1_5
FP_10_0_32 < AIR_1_5_2
FP_10_1 < AIR_2_0
FP_SYS < AIR_SYS
Which is simply a standard, compact notation to represent the partial orderings illustrated in the first table and first figure in API Versioning Solutions

(It is understood that x < y and y < z implies x < z. FP_SYS and AIR_SYS are notional "last versions" for the Flash and AIR products.)

Since versions are a partial ordering, it is possible to (topologically) sort the versions so that if v1 < v2 then ord(v1) < ord(v2). E.g.:

0 - FP_9_0
1 - AIR_1_0
2 - FP_10_0
3 - AIR_1_5
4 - AIR_1_5_1
5 - FP_10_0_32
6 - AIR_1_5_2
7 - FP_10_1
8 - AIR_2_0
9 - FP_SYS
10 - AIR_SYS

The wrinkle in this system is that while, as a matter of policy, every FP API becomes an AIR API in the corresponding release, most AIR APIs never become Flash APIs but some APIs are introduced in an AIR version and then (perhaps much) later in a Flash version. So, every versioned API is marked with the version(s) in which it was introduced.

[API(AIR_1_0), API(FP_10_0_32)] (say)
Every unversioned API is implicitly [API(FP_9_0)]

Now at runtime, any particular runtime is realizing one product or another. The set of APIs that are a part of Flash are those where

for some v, API(v) and v < FP_SYS    (< means precedes, not integer less-than)
the APIs that are a part of AIR are

for some v, API(v) and v < AIR_SYS
A compact and efficient way to represent versioned definitions at runtime is to record with each definition the "v" with the smallest ordinal for the product in question. This is the earliest version-of-introduction for that product (“ver(defn)”).

At runtime it is a simple matter to determine whether a reference should match a definition: When binding a versioned API definition, match if

ver(defn) <= ver(referencing pool) (simple integer comparison).
This preserves all existing versioning behaviors and allows us to comfortably represent billions of versions. It trades away the (as yet unused and AFIK unneeded) ability of a single VM instance to resolve API versions for different products

Comment 1

[Steven Johnson]

Attachment: Prototype patch

Here's a prototype that follows Stan's suggestion and passes regression in avmshell; the key to making this work is that the versions are segregated into "series" and only the versions from the current series are entered into lookup tables. (If a non-in-our-series version is requested, we promote it to the most compatible one that is.) We also bookend the versions with "ALLVERSIONS" and "VM_INTERNAL", both of which are considered in all series.

Still todo:
-- have to build & test in Flash/AIR

-- documentation (api-versions.xml format, general scheme, etc)

-- With a tooling change to ASC.jar we could eliminate the versioned-uris list entirely; for that to happen we would need ASC.jar to mark all namespaces in builtin code as "versioned" (in ALLVERSIONS) and we can then treat all URIs uniformly. (While we're at it we might as well change the marking to start at 0xE000 instead of the now-unimportant 0xE000+660...)

-- It would simplify the world if we generated api-versions.h/.cpp/.as every build (rather than checking them in); this might be simpler to do in the current build setup if apivergen.as was written in Python. Given the now-simpler format for api-versions.xml it may not need to be XML anyway...

Comment 2

[Jeff Dyer]

Comment on attachment 498365 [details] [diff] [review]
Prototype patch

Looks fine. The only thing that jumped out at me is your use of 'sub' and 'super' in the .xml file. I think of a 'sub' as an extension of a 'super', but you seem to be using the opposite meaning. Not a show stopper by any means, especially since your comment in the code makes it clear.

Jd

Comment 3

[Steven Johnson]

style q: VM_INTERNAL is a suboptimal name, as it will be used by Flash/AIR as well (to mark AS3 calls that shouldn't be visible to any non-builtin code). Suggestions? plain "INTERNAL" seems lame.

Comment 4

[Steven Johnson]

Likewise, VM_ALLVERSIONS might want a better name: if a name is *defined* with this version then it exists in all versions, but if a name is *queried* using this version, it only matches if that's where it is defined. (To do a query-against-any-version you must use VM_INTERNAL, perversely enough.)

On that note, the implementation of getAnyPublicNamespace() in this patch is wrong (should use VM_INTERNAL); I think I'll rename it getUniversalPublicNamespace().

Comment 5

[Steven Johnson]

Attachment: Patch v2

Rebased to tip, cleaned up and fixed some minor Flash/AIR integration issues

Comment 6

[Steven Johnson]

Existing patch is actually subtly broken for private namespaces (it allows different private namespaces to match each other in some cases), fix coming soon.

Comment 7

[Steven Johnson]

So, the problem with private namespaces with this patch is that we used to check for Namespace matches by code like

     (ns1 == ns2 || ((ns1->m_api & ns2->m_api) && (ns1->m_uriAndType == ns2->m_uriAndType)))

This worked because the right-hand side is correct for all non-private Namespaces (ie, they have the same uri-and-type and compatible api bits), and the left-hand side is correct for all private namespaces (which should match only if the NS pointer itself matches; the URI for private namespace is ignored for lookup purposes). The critical part that I hadn't realized is that this only works because private namespaces have api bits of zero ("unversioned"), thus the RHS of this expression formerly was always false for private namespaces.

In the new scheme, though, all namespaces are treated as "versioned", so this test translate into something like

    (ns1 == ns2 || ((ns1->m_uriAndType == ns2->m_uriAndType) && (ns1->m_apiVersion <= ns2->m_apiVersion)))

The gotcha is that some authoring tools (notably FlashAuthoring) emit all private namespaces with empty uris (which is legal), so the RHS can be inappropriately true for private namespaces. 

I can think of a few ways to solve this...

-- require that the URI for a private NS is always a unique pointer. Pro: would allow us to eliminate the LHS entirely (nice win in a hot loop). Con: URI is currently required/assumed to be interned, so we'd either have to soften this (allowing it to be a non-interned string for private ns) or generate a lot of arbitrarily unique interned strings for private ns (yuck)... both of which smell like a recipe for subtle bugs down the road. (It seems likely that any code that is relying on the URI of a private NS being meaningful is dubious, so this may be workable with care.)

-- Expand the test to explicitly check for type being nonprivate on RHS, eg

    (ns1 == ns2 || (ns1->getType() != NS_Private && (ns1->m_uriAndType == ns2->m_uriAndType) && (ns1->m_apiVersion <= ns2->m_apiVersion)))

Pro: works. Con: we have to add more instructions to a hot loop. Crowder's Law applies here, but it would be nice to avoid this if possible.

-- Optimized variant on the above: since we can assume that all Namespace in MNHT are interned (see note below), and that only NS_Public namespaces are versioned, and NS_Public == 0:

    (ns1 == ns2 || ((ns1->m_uriAndType == (ns2->m_uriAndType ^ 7)) && (ns1->m_apiVersion <= ns2->m_apiVersion)))

(Basically a trick to get RHS=false for all nonpublic NS).

Pro: works, one less test in a hot loop. Cons: hacky, requires assumptions we'll have to check for.

(Side note: prior to API versioning, MNHT did a simple ns pointer compare in all cases, thus implicitly assuming that all NS's in an MNHT were interned, but there's no mechanism to check/enforce this. Would be nice to have a debug-only isInterned() method on Namespace to check this.)

Opinions welcomed.

Comment 8

[Steven Johnson]

Attachment: Patch, v3 (reviewable)

Final version of the patch, cleaning up a few corner cases I had missed. Integrated info FRR and Flash/AIR pass tests cleanly, so this is ready for a real review; main thing lacking is a loooong comment somewhere describing how the scheme works in more detail.

Comment 9

[Jeff Dyer]

Comment on attachment 503334 [details] [diff] [review]
Patch, v3 (reviewable)

Looking at the diff between the current patch and the last patch, I don't see anything suspicious. +r base largely on the fact that stejohns says that it passes the ATS.

Comment 10

[Steven Johnson]

Attachment: Patch with docs

Additive to previous; adds documentation to apivergen.as about theory of operation. Also removes a blatantly wrong comment from api-versions.xml.

Comment 11

[Jeff Dyer]

Comment on attachment 503611 [details] [diff] [review]
Patch with docs

Nice write-up!

Comment 12

[Steven Johnson]

TR 5850:a09d8e95e2d2

Comment 13

[Dan Schaffer]

Running any brightspot swfs with -Dverifyonly triggers an assertion starting in TR 5850.

Assertion failed: "((isVersionedURI(uri)))" ("/Users/build/buildbot/tamarin-redux/mac-intel-10_5/repo/core/AvmCore.cpp":4809)
Trace/BPT trap

note: I logged a separate bug https://bugzilla.mozilla.org/show_bug.cgi?id=631541