543247 - Attempting to create huge strings causes OOM shutdown rather than out-of-memory exception

Status: RESOLVED WONTFIX

(Tamarin Graveyard :: Virtual Machine, defect)

Description

[Steven Johnson]

Running code like

		public function LoopStringConcatCrash(){
			var str:String = "a"
			var i:int = 1000;
			while(i--) 
				str += str;
		}

will eventually trigger an OOM shutdown of the entire VM. This seems awfully heavy-handed, since this situation could be detected and dealt with via throwing kOutOfMemoryError instead.

Comment 1

[Steven Johnson]

In theory, this could be dealt with pretty simply by adding a "pleaseConcatStrings" variant, and using it from op_add and the jit and interpreter... the only gotcha is that it appears to require either adding an extra parameter all the way down the call stack (yuck) or code duplication (yuck). Opinions welcomed.

Comment 2

[Lars T Hansen]

FOL if you ask me.  We don't provide any other memory management on the AS3 level, and I don't quite see why an out-of-memory exception should be provided.  I mean, what can you be expected to do?  You don't have any working memory to operate in.

Comment 3

[Lars T Hansen]

It now strikes me that you were talking about throwing this exception on the C++ level, bypassing(?) ActionScript exception handling.  Could you provide more detail?

Comment 4

[Steven Johnson]

(In reply to comment #2)
> FOL if you ask me.  

No way! This formerly caused an AS3 exception to be thrown. The new behavior kills the entirely player. This allows trivial DOS attacks for anything that can load SWF.

> I mean, what can you be expected to do?  
> You don't have any working memory to operate in.

Not so. The termination isn't because we don't have any memory, it's because we were about to ask for an unreasonable amount of memory.

(In reply to comment #3)
> It now strikes me that you were talking about throwing this exception on the
> C++ level, bypassing(?) ActionScript exception handling.  

No, I'm talking about throwing an AS3 exception. There is plenty of precedent for this (eg ObjectVectorObject::grow())

Comment 5

[Lars T Hansen]

(In reply to comment #4)
> (In reply to comment #2)
> > FOL if you ask me.  
> 
> No way! This formerly caused an AS3 exception to be thrown. The new behavior
> kills the entirely player. This allows trivial DOS attacks for anything that
> can load SWF.

OK then :-)

Comment 6

[Lars T Hansen]

BTW OOM DOS attacks are trivial anyway, and don't require large objects.  We don't, and I expect won't, throw OOM errors for other failure-to-allocate cases.  I'm only pointing out that the DOS argument is a bit spurious, what we're really protecting against is inadvertent creation of too-large strings, which I could believe is a somewhat common problem.

Should we worry about arrays and vectors in the same vein?  I expect that 

  new Vector.<int>(100000000)

will bring down the player (and browser) on most smartphones pretty much immediately.

Arrays require a little more work, since they can be sparse the memory is allocated less eagerly, but the problem is roughly the same.

Comment 7

[Lars T Hansen]

I'll own it for now, work on it when I have some spare time.  Poachable.

Comment 8

[Lars T Hansen]

Trying to grasp this, here's my current understanding:

- if certain operations originating from AS3 code or the C++ implementations
  of builtins request a too-large object then an out-of-memory exception
  should be thrown on the AS3 level

- a "too-large" request is one of:
  - a request that overflows the maximum object size or that overflows
    arithmetically during object size computation
  - a request that is valid per se but where the allocation fails
    because the object could not be allocated

- the operations that are affected are exhaustively enumerated and are as
  follows:
  - string allocation and concatenation
  - vector storage allocation
  - array storage allocation

- the implementation is best-effort, ie, it is more important that s1 + s2
  throw an error if the string is too large than that XML.toString() do it
  if the accumulated string is too large.  The main reason for this clause
  is that "originating from AS3 code" is a squishy requirement.

Open questions:

- is there a threshold for how large the requests must be before we invoke
  the exception machinery, for example, what happens with "a" + "b" if we
  can't allocate - exception or OOM shutdown?

Please correct my understanding of the problem as appropriate.

Comment 9

[Lars T Hansen]

We had an OOM junta meeting today and there are various other cases that may also have to considered:

 - ByteArray (different impl in shell and Player)
 - Dictionary
 - Bitmaps (in Player)
 - Netbuffers (in Player)
 - other unidentified avmglue (in Player)

The implementation is best-effort in another sense than noted above, namely, we should reliably detect large-allocation problems and attempt to throw out-of-memory exceptions to signal them, but if the system is in a very-low-memory state then the act of trying to allocate the exception object may itself cause OOM failures, and if that happens shutdown logic may prevent the exception from being allocated and thrown.  That would be acceptable.

Finally the junta notes that it's the documented behavior that matters most of all and that we need to scour the documentation to find all the places that promise that an exception is thrown.

Comment 10

[Lars T Hansen]

Adding to the above list:

- Object (large linear hash table)
- methods that are often implemented in C++ and that can create large
  strings or arrays, like Array.join, Array.splice, String.replace,
  String.split, WhatEver.toString - probably a longish list when all is
  said and done

Comment 11

[Lars T Hansen]

Note a related bug in the InlineHashtable code, which silently fails if it can't extend the hash table:

	void InlineHashtable::add(Atom name, Atom value)
	{
		if (isFull())
		{
			if (!grow())
				return;
		}
		put(name, value);
	}

Comment 12

[Lars T Hansen]

AS3 documentation for Flash CS4:

"The MemoryError exception is thrown when a memory allocation request fails.

On a desktop machine, memory allocation failures are rare unless an allocation request is extremely large. For example, a 32-bit Windows program can access only 2GB of address space, so a request for 10 billion bytes is impossible."

and an elaborate example on the same page to illustrate that it is thrown:

"package {
    import flash.display.Sprite;
    import flash.errors.MemoryError;
    import flash.utils.setInterval;
       
    public class MemoryErrorExample extends Sprite {
        private var crashingStr:String;
        private var intervalId:Number;
           
        public function MemoryErrorExample() {
            crashingStr = "abcdefghijklmnopqrstuvwxyz";
            intervalId = setInterval(exhaustMemory, 50);
        }
           
        public function exhaustMemory():void {            
            try {
                crashingStr += crashingStr;
            }
            catch(e:MemoryError) {
                trace(e);
            }
        }
    }
}"

Comment 13

[Lars T Hansen]

Seaching the Flash/Flex online docs, only these are explicitly documented as throwing MemoryError:

- FileReference.{cancel,load,save,upload}
- URLSteam.{cancel,load}
- URLLoader.load

- flash.globalization.NumberFormatter.{formatInt,formatNumber,formatUInt}
  methods as well as the negativeSymbol property (bizarre)

Comment 14

[Lars T Hansen]

Finally note that MemoryErrors is in flash.errors, not in the AS3 core built-ins, though the kOutOfMemoryError constant is defined by the AS3 core built-ins - it's in core/ErrorConstants.as as well as in ErrorConstants.h.

There is vestigial code in VectorClass.cpp, DataIO.cpp and ByteArrayGlue.cpp in the VM that throws this error, like this:

    toplevel()->throwError(kOutOfMemoryError);

Only in the case of DataIO.cpp will this error be thrown; VectorClass.cpp uses allocation methods that will never return NULL and the throw is commented out in the ByteArrayGlue.

One curious thing about the line above is that it will throw a plain Error object with kOutOfMemoryError, not a flash.errors.MemoryError object.  Ergo an application listening for out of memory errors may have to listen for more than MemoryError.  Presumably this is a Fact Of Life at this point, code with this behavior having shipped already? (TBD.)

Comment 15

[Lars T Hansen]

By inspection of Argo source code, these also throw MemoryError or Error with kOutOfMemoryError:

- EncryptedLocalStore::processErrorCode throws MemoryError (from AS3 code)

- ByteArray - the Flash implementation correctly uses kCanFail and throws
  MemoryError if the allocation failed, and also has one half-hearted check
  for trying to allocate a too-large object (which should be cleaned up)

- DataInput and DataOutput use kCanFail and throw MemoryError if the
  allocation fails.

- GlobalizationUtils throws an Error (not a MemoryError) with kOutOfMemoryError
  in some situations, but provides a utility function that throws a MemoryError
  properly, used by other modules...

- ImageSpriteGlue throws Error with kOutOfMemoryError in some situations

- NetParser throws MemoryError in some situations

- NumberFormatterGlue throws MemoryError in some situations

- ShaderJobGlue throws Error with kOutOfMemoryError

- CTS_Support throws Error with kOutOfMemoryError, and there's some other CTS
  code that messes around with kOutOfMemoryError, I haven't tracked the logic
  for this yet.

Comment 16

[Tommy Reilly]

(In reply to comment #12)
> and an elaborate example on the same page to illustrate that it is thrown:

Did you try this example out?  I'd be surprised if it didn't crash.

Comment 17

[Lars T Hansen]

(In reply to comment #16)
> (In reply to comment #12)
> > and an elaborate example on the same page to illustrate that it is thrown:
> 
> Did you try this example out?  I'd be surprised if it didn't crash.

Did not.  It's next on my to-do list.

Comment 18

[Lars T Hansen]

(In reply to comment #17)
> (In reply to comment #16)
> > (In reply to comment #12)
> > > and an elaborate example on the same page to illustrate that it is thrown:
> > 
> > Did you try this example out?  I'd be surprised if it didn't crash.
> 
> Did not.  It's next on my to-do list.

Official standalone release FP10.0 builds (Marlin and Squirt) crash quickly with a simple variant of the allocation loop.  Unfortunately I can't seem to run it in the debugger now that I've upgraded to OS 10.6 because of GCC incompatibilities, but I attached to it from gdb and looked at the disassembly and state, it's credibly a null pointer crash following an allocator call.  I conclude that support for reliable too-large object handling was absent from previous Player versions.

Removing INJECTION tag, but probably still need to fix some of the worst corner cases for Argo.

Comment 19

[Lars T Hansen]

Attachment: Preliminary test cases

Some simple and obvious cases - String, Vector, Array, Dictionary, Object.  Note the Dictionary and Object cases will loop forever without a fix to InlineHashtable::add.

Comment 20

[Lars T Hansen]

Attachment: Changes to InlineHashtable

Preliminary patch: require a Toplevel* to be propagated into the InlineHashtable functions.  The latter use the pointer as a flag: if it is not NULL then use it to throw an exception if the capacity of the hash table is at its limit or if the allocation of a larger table fails.

The patch requires further changes through the VM and probablhy in the player, and of course that's where all the difficulty is: at some point it becomes necessary to decide whether to pass NULL or to find a Toplevel pointer to pass.  Those changes are not part of this patch.

Asking for review just to see if the approach will fly.

Comment 21

[Steven Johnson]

Comment on attachment 425590 [details] [diff] [review]
Changes to InlineHashtable

Looks ok as-is, but we should examine the call-chain ramifications upstream (eg in Flash) before landing.

Comment 22

[Steven Johnson]

(In reply to comment #18)
> Official standalone release FP10.0 builds (Marlin and Squirt) crash quickly
> with a simple variant of the allocation loop. 

FWIW, I don't disbelieve this result, but that's contrary to what was originally reported in Watson.

Comment 23

[Lars T Hansen]

(In reply to comment #22)
> (In reply to comment #18)
> > Official standalone release FP10.0 builds (Marlin and Squirt) crash quickly
> > with a simple variant of the allocation loop. 
> 
> FWIW, I don't disbelieve this result, but that's contrary to what was
> originally reported in Watson.

There could be multiple modes here, for example, an allocation that fails because there's no memory might be different than an allocation that fails because the request is outside the largest supported object size.

Do you have the Watson bug number?

Comment 24

[Lars T Hansen]

Comment on attachment 425590 [details] [diff] [review]
Changes to InlineHashtable

Obsoleted by bug #545014.

Comment 25

[Lars T Hansen]

(In reply to comment #11)
> Note a related bug in the InlineHashtable code, which silently fails if it
> can't extend the hash table:
>
> ...

Logged as bug #545014.

Comment 26

[Lars T Hansen]

Considering all the complications and all the possible code paths, it seems to me that passing flags from the AS3 level down through various levels is not going to be workable in practice.  What we really want is a mechanism that answers the question "Can I safely throw an AS3 exception here?"  The answer should be "yes" if there's an agent that's ready to catch that exception before the throw bypasses some critical code, otherwise "no".  If the answer is "yes" then throw it - we need a Toplevel object for that - and otherwise just call GCHeap::SignalObjectTooLarge (which will abort the VM and the Player).

Given that a even putproperty() call can cause the problem it is unlikely that all entry points into the VM are protected by exception handlers at present, which is why we need the mechanism in the first place.

Just thinking out loud now, a flag (a Toplevel*) that is set to something non-NULL when an exception handler is erected and set to NULL on call-outs from the VM might do the trick.  It needs to be saved and restored properly and unwound as the exception propagates up the stack.  Maybe something built on our execution frame objects?

Comment 27

[Lars T Hansen]

AvmCore::willExceptionBeCaught is part of the answer but maybe not all of it.  What I worry about is this situation:

   <code establishes exception handler>
   <AS3 code executes>
     <AS3 calls out to C++>
       <lots of C++ host code on the stack here>
         ...
           <C++ host code calls setUintProperty>
              <setUintProperty overflows the object and must throw>

At this point there's an exception handler, but throwing to it is almost certainly not correct: the C++ host code must be unwound.  In the past we've not thrown exceptions from setUintProperty (well, it throws a ReferenceError when trying to set a read-only property, but that's not a common case) so code paths are unlikely to cope with this problem.  We'd want the call-out from AS3 to set a bit s.t. the search for exception handler stops when it gets to it, unless another handler has been established further down the stack.

Comment 28

[Lars T Hansen]

(In reply to comment #23)
> 
> There could be multiple modes here, for example, an allocation that fails
> because there's no memory might be different than an allocation that fails
> because the request is outside the largest supported object size.

Platform dependency: on Mac we crash quickly, but Windows builds stay up (Marlin).

Comment 29

[Steven Johnson]

(In reply to comment #28)
> Platform dependency: on Mac we crash quickly, but Windows builds stay up
> (Marlin).

OK, at this point I think I agree that this specific OOM issue probably should just stay as-is for now: since this formerly crashed on at least one prominent platform (Mac) that counts as "code didn't work reliably before", so working on Win was just getting lucky. OOM behavior is clearly better than crashing.

We should mark this issue down as one to potentially re-examine for the future but OOM seems good enough for now.

Comment 30

[Lars T Hansen]

(In reply to comment #28)
> (In reply to comment #23)
> > 
> > There could be multiple modes here, for example, an allocation that fails
> > because there's no memory might be different than an allocation that fails
> > because the request is outside the largest supported object size.
> 
> Platform dependency: on Mac we crash quickly, but Windows builds stay up
> (Marlin).

Even Marlin is not reliable on Windows - the error thrown (in Firefox) is a script timeout, not an out of memory error.  What happens is that the process grows to 1.1GB quickly and then stalls, I bet it gets into some sort of loop.

Comment 31

[Lars T Hansen]

Deferred by joint decision of the OOM junta, QE, and Lee.

Comment 32

[Sylvestre Ledru [:Sylvestre]]

Tamarin is a dead project now. Mass WONTFIX.

Comment 33

[Sylvestre Ledru [:Sylvestre]]

Tamarin isn't maintained anymore. WONTFIX remaining bugs.