Enforce length/size limits for variable size heap object in order to

Enforce length/size limits for variable size heap object in order to
avoid overflow.

For each variable size heap object, compute the maximum number of
elements and use that in the ::New functions to avoid overflow.  If a
bad length/size reaches a ::New function, that is a FATAL error -- the
problem should have been caught earlier by the dart api or by the
library code.

Add "border guards" in the dart api and in library calls which cause
new variable size heap objects to be allocated.  We check for invalid
length/size and throw explanatory error messages.
Committed: https://code.google.com/p/dart/source/detail?r=10130

[turnidge, 2012-07-16 19:05:14]

Attempt to fix security bug 1749 

http://code.google.com/p/dart/issues/detail?id=1749

in the Dart VM.

[cshapiro, 2012-07-17 22:54:30]

http://codereview.chromium.org/10782016/diff/1/lib/byte_array.cc
File lib/byte_array.cc (right):

http://codereview.chromium.org/10782016/diff/1/lib/byte_array.cc#newcode22
lib/byte_array.cc:22: arguments.Add(&index_object);
Out of the kindness of your heart, please make this error message a string with
a descriptive error message.

http://codereview.chromium.org/10782016/diff/1/lib/byte_array.cc#newcode264
lib/byte_array.cc:264: if (len < 0 || len > Int8Array::kMaxElements) {
Maybe some derivative or close cousin to the RangeCheck above (including
exception throwing).

http://codereview.chromium.org/10782016/diff/1/lib/string.cc
File lib/string.cc (right):

http://codereview.chromium.org/10782016/diff/1/lib/string.cc#newcode18
lib/string.cc:18: 
The native argument is always a built-in Array.  We should make this a fatal
instead of a throw.

http://codereview.chromium.org/10782016/diff/1/vm/object.cc
File vm/object.cc (right):

http://codereview.chromium.org/10782016/diff/1/vm/object.cc#newcode9481
vm/object.cc:9481: if (len < 0) {
This should check against a kMaxElements, preferably the same kMaxElements in
the non-external OneByteString type.

External types will be serialized as their internal counterpart in a snapshot.

http://codereview.chromium.org/10782016/diff/1/vm/object.cc#newcode9993
vm/object.cc:9993: if (len < 0) {
This needs an upper bound, use the non-external one.

http://codereview.chromium.org/10782016/diff/1/vm/object.h
File vm/object.h (right):

http://codereview.chromium.org/10782016/diff/1/vm/object.h#newcode24
vm/object.h:24: ((kIntptrMax - sizeof(Raw##type) - sizeof(RawObject)) /         
            \
Give consideration to the maximum value of a Smi.

[turnidge, 2012-07-18 18:17:04]

Ready for another look.

http://codereview.chromium.org/10782016/diff/1/lib/byte_array.cc
File lib/byte_array.cc (right):

http://codereview.chromium.org/10782016/diff/1/lib/byte_array.cc#newcode22
lib/byte_array.cc:22: arguments.Add(&index_object);
On 2012/07/17 22:54:30, cshapiro wrote:
> Out of the kindness of your heart, please make this error message a string
with
> a descriptive error message.

Done.

http://codereview.chromium.org/10782016/diff/1/lib/byte_array.cc#newcode264
lib/byte_array.cc:264: if (len < 0 || len > Int8Array::kMaxElements) {
On 2012/07/17 22:54:30, cshapiro wrote:
> Maybe some derivative or close cousin to the RangeCheck above (including
> exception throwing).

Done.

http://codereview.chromium.org/10782016/diff/1/lib/string.cc
File lib/string.cc (right):

http://codereview.chromium.org/10782016/diff/1/lib/string.cc#newcode18
lib/string.cc:18: 
On 2012/07/17 22:54:30, cshapiro wrote:
> The native argument is always a built-in Array.  We should make this a fatal
> instead of a throw.

Done.

http://codereview.chromium.org/10782016/diff/1/vm/object.cc
File vm/object.cc (right):

http://codereview.chromium.org/10782016/diff/1/vm/object.cc#newcode9481
vm/object.cc:9481: if (len < 0) {
On 2012/07/17 22:54:30, cshapiro wrote:
> This should check against a kMaxElements, preferably the same kMaxElements in
> the non-external OneByteString type.
> 
> External types will be serialized as their internal counterpart in a snapshot.

I went further than that.  I have made all strings share a common kMaxElements. 
Seems simpler.

http://codereview.chromium.org/10782016/diff/1/vm/object.cc#newcode9993
vm/object.cc:9993: if (len < 0) {
On 2012/07/17 22:54:30, cshapiro wrote:
> This needs an upper bound, use the non-external one.

Done.

http://codereview.chromium.org/10782016/diff/1/vm/object.h
File vm/object.h (right):

http://codereview.chromium.org/10782016/diff/1/vm/object.h#newcode24
vm/object.h:24: ((kIntptrMax - sizeof(Raw##type) - sizeof(RawObject)) /         
            \
On 2012/07/17 22:54:30, cshapiro wrote:
> Give consideration to the maximum value of a Smi.

This is awkward to do, since the Smi::MaxValue isn't defined yet at this point.

...

Are you sure we need to check this here?  My goal is to prevent overflow of the
intptr_t type used to compute instance sizes.  Is there any reason why I should
need to enforce the Smi max here?

[cshapiro, 2012-07-19 05:49:01]

I hope I have described my reasoning regarding considering a Smi in the
MAX_ELEMENTS macro.  I am not sure this applies to all cases, but I think it
does.  Aside from that everything LGTM.

http://codereview.chromium.org/10782016/diff/1/vm/object.h
File vm/object.h (right):

http://codereview.chromium.org/10782016/diff/1/vm/object.h#newcode24
vm/object.h:24: ((kIntptrMax - sizeof(Raw##type) - sizeof(RawObject)) /         
            \
I lost an earlier comment.  It may appear after I publish, sorry if there is any
confusion.

Maybe I am totally wrong about this but as I see it MAX_ELEMENTS will over
estimate the maximum number of elements in a collection of a given element
width.  As such, I am not entirely enthusiastic about it in its current form,
its name, or the kMaxElements name.

For example, the maximum number of elements of an Int8Array or Uint8Array is the
maximum Smi value as we do not permit a Bigint valued index.  The Smi range is
always half the intptr_t range and, as such, MAX_ELEMENTS will always
over-estimate its value to be outside the Smi range, ((0x7FFFFFFF - 8 - 4) / 1)
> 0x3fffffff  

I think it would be a little bit simpler to have max value be computed as
follows

  (Smi::kMaxValue >> 0) for  8-bit elements
  (Smi::kMaxValue >> 1) for 16-bit elements
  (Smi::kMaxValue >> 2) for 32-bit elements 
  (Smi::kMaxValue >> 3) for 64-bit elements  

The halving of the range of a Smi versus inptr_t provides enough slop to
discount header sizes entirely.  Furthemore, kMaxElements can be encoded as a
Smi without overflowing to a Bigint.

http://codereview.chromium.org/10782016/diff/12001/lib/string.cc
File lib/string.cc (right):

http://codereview.chromium.org/10782016/diff/12001/lib/string.cc#newcode26
lib/string.cc:26: // Array, which is our standard list implementation.  It
should
This is further strengthened by the size of an array header is equal to the size
of a string header.  It is possible for that correspondence to change but but
can validate here with a compile time assert.

http://codereview.chromium.org/10782016/diff/12001/vm/dart_api_impl.cc
File vm/dart_api_impl.cc (right):

http://codereview.chromium.org/10782016/diff/12001/vm/dart_api_impl.cc#newcod...
vm/dart_api_impl.cc:1601: if (length < 0 || length >
TwoByteString::kMaxElements) {
I thought you were going to add a macro or something to make all of the API
users look the same.  You may have had a reason not to do that and I might be
mistaken.

[turnidge, 2012-07-31 23:21:45]

http://codereview.chromium.org/10782016/diff/1/vm/object.h
File vm/object.h (right):

http://codereview.chromium.org/10782016/diff/1/vm/object.h#newcode24
vm/object.h:24: ((kIntptrMax - sizeof(Raw##type) - sizeof(RawObject)) /         
            \
On 2012/07/19 05:49:01, cshapiro wrote:
> I lost an earlier comment.  It may appear after I publish, sorry if there is
any
> confusion.
> 
> Maybe I am totally wrong about this but as I see it MAX_ELEMENTS will over
> estimate the maximum number of elements in a collection of a given element
> width.  As such, I am not entirely enthusiastic about it in its current form,
> its name, or the kMaxElements name.
> 
> For example, the maximum number of elements of an Int8Array or Uint8Array is
the
> maximum Smi value as we do not permit a Bigint valued index.  The Smi range is
> always half the intptr_t range and, as such, MAX_ELEMENTS will always
> over-estimate its value to be outside the Smi range, ((0x7FFFFFFF - 8 - 4) /
1)
> > 0x3fffffff  
> 
> I think it would be a little bit simpler to have max value be computed as
> follows
> 
>   (Smi::kMaxValue >> 0) for  8-bit elements
>   (Smi::kMaxValue >> 1) for 16-bit elements
>   (Smi::kMaxValue >> 2) for 32-bit elements 
>   (Smi::kMaxValue >> 3) for 64-bit elements  
> 
> The halving of the range of a Smi versus inptr_t provides enough slop to
> discount header sizes entirely.  Furthemore, kMaxElements can be encoded as a
> Smi without overflowing to a Bigint.

Done.

http://codereview.chromium.org/10782016/diff/12001/lib/string.cc
File lib/string.cc (right):

http://codereview.chromium.org/10782016/diff/12001/lib/string.cc#newcode26
lib/string.cc:26: // Array, which is our standard list implementation.  It
should
On 2012/07/19 05:49:01, cshapiro wrote:
> This is further strengthened by the size of an array header is equal to the
size
> of a string header.  It is possible for that correspondence to change but but
> can validate here with a compile time assert.

Removed.  Fixed in a forthcoming CL that changes zone->Allocate...

http://codereview.chromium.org/10782016/diff/12001/vm/dart_api_impl.cc
File vm/dart_api_impl.cc (right):

http://codereview.chromium.org/10782016/diff/12001/vm/dart_api_impl.cc#newcod...
vm/dart_api_impl.cc:1601: if (length < 0 || length >
TwoByteString::kMaxElements) {
On 2012/07/19 05:49:01, cshapiro wrote:
> I thought you were going to add a macro or something to make all of the API
> users look the same.  You may have had a reason not to do that and I might be
> mistaken.

Done.