684211 - Injection: dense array optimization's use of all-zero-bits as "empty" in a dense range is incorrect and breaks programs

Status: RESOLVED WONTFIX

(Tamarin Graveyard :: Virtual Machine, defect, P3)

Description

[Lars T Hansen]

Test case:

  class C {
    var x = 0;
  }
  class D extends C {
    var y = x;
  }
  print((new D).y);

Avik observed that this program has recently changed meaning from printing "null" to printing "undefined".  Investigation revealed that this was injected into TR in 5713/5714:

  changeset:   5713:9c0aeb405ad3
  user:        Steven Johnson <[e-mail]>
  date:        Tue Jan 04 12:55:41 2011 -0800
  summary:     Bug 610063 - Port 'dense array' work from TT (r=lhansen)

5714 adds some compile fixes so that's the one that is testable.

Initial investigation revealed that this is not a change in property initialization semantics as first thought but a problem in the representation of dense array objects.  It goes as follows. 

We have this:

  public function print(...s)
  {
    System.trace(s)
  }

where System.trace is a native method.  That method is represented in C++ code as this:

  AvmBox
  avmplus_System_trace_thunk(AvmMethodEnv env, uint32_t argc, AvmBox* argv)
  {
    enum {
      argoff0 = 0
      , argoff1 = argoff0 + AvmThunkArgSize_AvmObject
    };
    (void)argc;
    (void)env;
    ::avmshell::SystemClass* const obj =
       (::avmshell::SystemClass*)AvmThunkUnbox_AvmReceiver(AvmObject,
                                                           argv[argoff0]);
    obj->trace(
        (ArrayObject*)AvmThunkUnbox_AvmObject(argv[argoff1])
    );
    return kAvmThunkUndefined;
  }

which is correct, as its first argument is an ArrayObject* and it passes this into the native layer by calling obj->trace().

As it representes rest arguments, the ArrayObject is dense and it has one element and that element is a null value from the property initialization, ie, it's all-bits-zero.

For practical purposes, the body of trace() in C++ code is this:

  for (int i=0, n = a->getLength(); i < n; i++)
  {
    StringIndexer s(core->string(a->getUintProperty(i)));
    ...
  }

getUintProperty() eventually ends up in ArrayObject::getUintPropertyImpl(), which says:

  if (denseIdx < m_denseArray.length())
  {
    Atom result = m_denseArray.get(denseIdx);
    if (result != atomNotFound)
      return result;
      // else, a hole in the dense area, must fall thru and 
      // search the hashtable/proto chain
  }
  Atom result = ScriptObject::getUintProperty(index);

What happens here is that the all-null-bits representation of an uninitialized field is also the representation of atomNotFound.  Hence the lookup here fails and we go into ScriptObject::getUintProperty(), where we'll eventually return undefined.  Hence the change in meaning of the program.

Comment 1

[Lars T Hansen]

Felix and I have hashed around some options on IM.  Two possibilities right now:

1) use a value like (~uintptr_t(0) ^ 7), ie 0xF...F8, which is a value tagged with kUnusedAtomTag whose payload is guaranteed not to be a valid pointer.

2) allocate a bibop page and allocate an object off of that page whose address serves as the pointer payload of a bibop-tagged "invalid atom" value; the object would be kept alive by locking it.

Neither solution is without problems.

Solution 1 is not good because it is theoretically possible that the Player stores values that look like that in our data structures.  It won't be a pointer but it could be some other payload.  So far as we can tell that's the only disadvantage with this solution, however.

Solution 2 is cleaner because we control the bibop tag, but it has higher complexity because of the storage that has to be managed, and it's not clear how it's going to behave in a shutdown situation: What dependencies are there on this value being "good" while we're shutting down?  Also, this solution requires a non-constant, so the invalid atom value has to be stored someplace and fetched whenever we need it.  It's a fairly non-local change.

I probably favor solution 1 right now, but ideally we'd vet it with the Player and AIR engineers somehow.  Simply knowing that they only ever store true pointer values would be sufficient, since our special payload would not be a valid pointer.

Comment 2

[Lars T Hansen]

I guess another possible solution is to go from dense to sparse the minute a hole is created, but I have no idea what the consequences of that are.

Comment 3

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to Lars T Hansen from comment #1)
> Felix and I have hashed around some options on IM.

Third possibility we briefly considered: 
3) Within the Array code, attempts to put Atom(0) into an ArrayObject siliently insert a tagged null object instead.

Lars noted that if we did Solution 3: "it might be appropriate to add that to the optimized vector write code proposed in bug 601817, and to its to-be-proposed Array equivalent.  However, that will transition from a value without a type to one with a type, potentially, so I'm not sure it's a good idea."

Comment 4

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: test T v2: expansion of test from description

While exploring related edge cases, I realized that our debug code in avmplusHashtable explicitly asserts that it won't ever see EMPTY (== Atom(0) == atomNotFound) as a name nor as a value:

Assertion failed: "((name != EMPTY && value != EMPTY))" ("/Users/fklockii/Dev/tamarin-redux/core/avmplusHashtable.cpp":94)

Those asserts were there before Steven put in the dense array changes, and they fire on this test case on rev 5711:93a6f1d1128f (the predecessor to dense arrays).  From what I can tell, there's no ill-effects from violating them, but I'm not certain of that yet.

Still investigating how EMPTY is actually used in the avmplusHashtable code.  It seems to me like we have been acting like the comment above atomNotFound that says atomNotFound never used [1] is true, even though Lars has pointed out to me that its not true, as illustrated by Avik's program.

[1] http://hg.mozilla.org/tamarin-redux/rev/5712#l16.12

Comment 5

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to Felix S Klock II from comment #4)
> From what I can tell, there's no ill-effects from violating
> them, but I'm not certain of that yet.

More precisely: it is the (value != EMPTY) conjunct in that assertion that can be easily violated via the all-bits-zero value in Avik's code, and I do not yet see any ill-effects from violating that conjunct.

(It is more plausible that violating the (name != EMPTY) conjunct could cause problems.  I have been trying to figure out if there is some way to combine Dictionary and the all-bits-zero to make that assertion fire, but I have not managed to do so yet.)

Comment 6

[Dan Smith]

Targeting for Anza.  There isn't a clearly correct, low-risk fix that we can take for Serrano.

Comment 7

[Lars T Hansen]

From comment #4 and comment #5 it seems clear that even the old value of EMPTY was incorrect, and again, that is probably so because we're using all-bits-zero as the initializer for fresh objects; that value can legitimately appear in AS3 objects without external C++ code needing to be involved.

However as comment #5 points out, this bug has been benign in the context of the hash table since we're more concerned about the name there than the value.  The dense array work changes that: the value becomes important.

Comment 8

[Lars T Hansen]

In comment #3 Felix quotes me as saying that transitioning from an "untyped" to a "typed" null value might be a bad idea.  Some experiments I've done so far fail to expose the distinction between the two null values, and indeed null is not of any specific type according to "is", so we may always have to launder null specially anyway - and it would be strange, though possible, if we treated the untagged null value differently.

I still don't like the idea of the "transitioning" fallback since we have a number of optimizations that bypass specific APIs internally; the fix has a potential for being brittle.  But as it only pertains to Array writes it may actually be practical.

Comment 9

[Lars T Hansen]

A wrinkle:

  class C {
    var x:String = null;
  }
  class D extends C {
    var y = x;
  }
  print((new D).y);

Without the annotation ":String" it prints undefined.  With the annotation it prints "null".  This means that my original explanation does not account for all the facts, something is missing.

Comment 10

[Lars T Hansen]

The special sauce that makes #9 what it is is probably that a typed field is always stored untagged, but when it is read and converted to an atom a tag is inserted based on the annotated type.  Thus y gets a string-tagged null pointer, which is not all-bits-zero.  I think that means that my original explanation stands.

Comment 11

[Felix S. Klock II [:pnkfelix, :fklock]]

(we should probably decide if we're really trying to resolve this for anza or not soonish.)

Comment 12

[Felix S. Klock II [:pnkfelix, :fklock]]

Another data point that may relate to this bug (and so I wanted to jot the note somewhere).

Consider this program, foo.as:

  var a = [];
  a[10] = 10;
  a.length = 10;
  print(a.AS3::shift());
  print(a.public::shift());

In 32-bit release -Ojit, foo.as prints:

  null
  undefined

In 32-bit release -Dinterp, foo.as prints:

  1.8148258665723936e-307
  1.8148258665723936e-307

In 32-bit DebugDebugger (both jit/interp modes), foo.as assert fails:
  Assertion failed: "((((avmplus::Atom)(uintptr_t(atom) & 7))==kDoubleType))" ("../core/AvmCore-inlines.h":453)
which is this:

REALLY_INLINE /*static*/ double AvmCore::atomToDouble(Atom atom)
{
    AvmAssert(atomKind(atom)==kDoubleType);
    return *(const double*)atomPtr(atom);
}


(the stack trace shows that in both cases the problem is arising from SystemClass::trace.)

I inspected the values when walking the stack a little; it seems like the troublesome value(s) has the kUnusedAtomTag but is otherwise carrying a payload.  My understanding is that such a value may arise from the player's [ab[use of arrays, but we should not be seeing it pop up from avmshell.

Comment 13

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to Felix S Klock II from comment #12)
> Another data point that may relate to this bug (and so I wanted to jot the
> note somewhere).

(Never mind, its an unrelated bug.)

Comment 14

[Dan Smith]

Have we converged on a recommended fix?  It seems like option 3 (within the Array code, attempts to put Atom(0) into an ArrayObject siliently insert a tagged null object instead) is the contender.

Retargeting to Brannan to give time to patch and test.  If this is considered low risk and very testable for Anza, I'll reconsider.

Comment 15

[Lars T Hansen]

(In reply to Dan Smith from comment #14)

> Have we converged on a recommended fix?  It seems like option 3 (within the
> Array code, attempts to put Atom(0) into an ArrayObject siliently insert a
> tagged null object instead) is the contender.

Attempting to talk myself around to agreeing:

It's probably an OK solution even in the face of aggressive planned optimization (eg monotyped dense arrays with inlined read/write).  It will slow down the untyped write paths a little bit but those paths are plenty slow already, and always out-of-line anyway.

Can we guarantee that stores of Atom(0) would always take the slow path under the assumption of aggressive optimization?  The cases are jitted code, interpreter C++ code, Tamarin C++ code, foreign C++ code.  C++ code will likely call setUintProperty(), fine.  The JIT will probably take the slow path because the write barrier is way too heavyweight to inline, and if the JIT does not know the type of the atom there's no sense in speculating inline in order to discover a fast path - too much bloat at too little payoff.

I think it will work.  I'm not fond of it, since we're patching a bug instead of fixing the underlying problem (dense arrays are not well defined with our current representation).  I expect I'll revisit the issue if we optimize Arrays to avoid boxing atoms stored into them.

Comment 16

[Felix S. Klock II [:pnkfelix, :fklock]]

ah what a nightmare; I guess with AS4 all these sorts of problems will go away.