Revision: 3614
Author: [email protected]
Date: Fri Jan 15 05:10:50 2010
Log: Merge r3560, r3562 and r3568 from bleeding_edge to 1.3 branch to fix
potential integer overflows.
Review URL: http://codereview.chromium.org/551045
http://code.google.com/p/v8/source/detail?r=3614
Modified:
/branches/1.3/src/heap.cc
/branches/1.3/src/objects.cc
/branches/1.3/src/objects.h
/branches/1.3/src/runtime.cc
/branches/1.3/src/utils.cc
/branches/1.3/src/version.cc
=======================================
--- /branches/1.3/src/heap.cc Wed Jan 6 23:49:31 2010
+++ /branches/1.3/src/heap.cc Fri Jan 15 05:10:50 2010
@@ -1990,6 +1990,9 @@
Object* Heap::AllocateByteArray(int length, PretenureFlag pretenure) {
+ if (length < 0 || length > ByteArray::kMaxLength) {
+ return Failure::OutOfMemoryException();
+ }
if (pretenure == NOT_TENURED) {
return AllocateByteArray(length);
}
@@ -2008,6 +2011,9 @@
Object* Heap::AllocateByteArray(int length) {
+ if (length < 0 || length > ByteArray::kMaxLength) {
+ return Failure::OutOfMemoryException();
+ }
int size = ByteArray::SizeFor(length);
AllocationSpace space =
size > MaxObjectSizeInPagedSpace() ? LO_SPACE : NEW_SPACE;
@@ -2666,12 +2672,16 @@
Object* Heap::AllocateInternalSymbol(unibrow::CharacterStream* buffer,
int chars,
uint32_t length_field) {
+ ASSERT(chars >= 0);
// Ensure the chars matches the number of characters in the buffer.
ASSERT(static_cast<unsigned>(chars) == buffer->Length());
// Determine whether the string is ascii.
bool is_ascii = true;
- while (buffer->has_more() && is_ascii) {
- if (buffer->GetNext() > unibrow::Utf8::kMaxOneByteChar) is_ascii =
false;
+ while (buffer->has_more()) {
+ if (buffer->GetNext() > unibrow::Utf8::kMaxOneByteChar) {
+ is_ascii = false;
+ break;
+ }
}
buffer->Rewind();
@@ -2680,6 +2690,9 @@
Map* map;
if (is_ascii) {
+ if (chars > SeqAsciiString::kMaxLength) {
+ return Failure::OutOfMemoryException();
+ }
if (chars <= String::kMaxShortSize) {
map = short_ascii_symbol_map();
} else if (chars <= String::kMaxMediumSize) {
@@ -2689,6 +2702,9 @@
}
size = SeqAsciiString::SizeFor(chars);
} else {
+ if (chars > SeqTwoByteString::kMaxLength) {
+ return Failure::OutOfMemoryException();
+ }
if (chars <= String::kMaxShortSize) {
map = short_symbol_map();
} else if (chars <= String::kMaxMediumSize) {
@@ -2721,13 +2737,17 @@
Object* Heap::AllocateRawAsciiString(int length, PretenureFlag pretenure) {
+ if (length < 0 || length > SeqAsciiString::kMaxLength) {
+ return Failure::OutOfMemoryException();
+ }
+ int size = SeqAsciiString::SizeFor(length);
+ ASSERT(size <= SeqAsciiString::kMaxSize);
+
AllocationSpace space = (pretenure == TENURED) ? OLD_DATA_SPACE :
NEW_SPACE;
// New space can't cope with forced allocation.
if (always_allocate()) space = OLD_DATA_SPACE;
- int size = SeqAsciiString::SizeFor(length);
-
Object* result = Failure::OutOfMemoryException();
if (space == NEW_SPACE) {
result = size <= kMaxObjectSizeInNewSpace
@@ -2758,13 +2778,17 @@
Object* Heap::AllocateRawTwoByteString(int length, PretenureFlag
pretenure) {
+ if (length < 0 || length > SeqTwoByteString::kMaxLength) {
+ return Failure::OutOfMemoryException();
+ }
+ int size = SeqTwoByteString::SizeFor(length);
+ ASSERT(size <= SeqTwoByteString::kMaxSize);
+
AllocationSpace space = (pretenure == TENURED) ? OLD_DATA_SPACE :
NEW_SPACE;
// New space can't cope with forced allocation.
if (always_allocate()) space = OLD_DATA_SPACE;
- int size = SeqTwoByteString::SizeFor(length);
-
Object* result = Failure::OutOfMemoryException();
if (space == NEW_SPACE) {
result = size <= kMaxObjectSizeInNewSpace
@@ -2806,6 +2830,9 @@
Object* Heap::AllocateRawFixedArray(int length) {
+ if (length < 0 || length > FixedArray::kMaxLength) {
+ return Failure::OutOfMemoryException();
+ }
// Use the general function if we're forced to always allocate.
if (always_allocate()) return AllocateFixedArray(length, TENURED);
// Allocate the raw data for a fixed array.
@@ -2857,7 +2884,11 @@
Object* Heap::AllocateFixedArray(int length, PretenureFlag pretenure) {
+ ASSERT(length >= 0);
ASSERT(empty_fixed_array()->IsFixedArray());
+ if (length < 0 || length > FixedArray::kMaxLength) {
+ return Failure::OutOfMemoryException();
+ }
if (length == 0) return empty_fixed_array();
// New space can't cope with forced allocation.
=======================================
--- /branches/1.3/src/objects.cc Thu Jan 7 00:01:27 2010
+++ /branches/1.3/src/objects.cc Fri Jan 15 05:10:50 2010
@@ -6931,10 +6931,14 @@
template<typename Shape, typename Key>
-Object* HashTable<Shape, Key>::Allocate(
- int at_least_space_for) {
+Object* HashTable<Shape, Key>::Allocate(int at_least_space_for) {
int capacity = RoundUpToPowerOf2(at_least_space_for);
- if (capacity < 4) capacity = 4; // Guarantee min capacity.
+ if (capacity < 4) {
+ capacity = 4; // Guarantee min capacity.
+ } else if (capacity > HashTable::kMaxCapacity) {
+ return Failure::OutOfMemoryException();
+ }
+
Object* obj = Heap::AllocateHashTable(EntryToIndex(capacity));
if (!obj->IsFailure()) {
HashTable::cast(obj)->SetNumberOfElements(0);
=======================================
--- /branches/1.3/src/objects.h Thu Jan 7 00:01:27 2010
+++ /branches/1.3/src/objects.h Fri Jan 15 05:10:50 2010
@@ -1757,6 +1757,10 @@
#endif
Object* SlowReverseLookup(Object* value);
+ // Maximal number of elements (numbered 0 .. kMaxElementCount - 1).
+ // Also maximal value of JSArray's length property.
+ static const uint32_t kMaxElementCount = 0xffffffffu;
+
static const uint32_t kMaxGap = 1024;
static const int kMaxFastElementsLength = 5000;
static const int kInitialMaxFastElementArray = 100000;
@@ -1883,8 +1887,14 @@
// Casting.
static inline FixedArray* cast(Object* obj);
- // Align data at kPointerSize, even if Array.kHeaderSize isn't aligned.
- static const int kHeaderSize = POINTER_SIZE_ALIGN(Array::kHeaderSize);
+ static const int kHeaderSize = Array::kAlignedSize;
+
+ // Maximal allowed size, in bytes, of a single FixedArray.
+ // Prevents overflowing size computations, as well as extreme memory
+ // consumption.
+ static const int kMaxSize = 512 * MB;
+ // Maximally allowed length of a FixedArray.
+ static const int kMaxLength = (kMaxSize - kHeaderSize) / kPointerSize;
// Dispatched behavior.
int FixedArraySize() { return SizeFor(length()); }
@@ -2194,6 +2204,12 @@
// Constant used for denoting a absent entry.
static const int kNotFound = -1;
+ // Maximal capacity of HashTable. Based on maximal length of underlying
+ // FixedArray. Staying below kMaxCapacity also ensures that EntryToIndex
+ // cannot overflow.
+ static const int kMaxCapacity =
+ (FixedArray::kMaxLength - kElementsStartOffset) / kEntrySize;
+
// Find entry for key otherwise return -1.
int FindEntry(Key key);
@@ -2224,6 +2240,7 @@
// use bit-wise AND with a mask, so the capacity must be positive
// and non-zero.
ASSERT(capacity > 0);
+ ASSERT(capacity <= kMaxCapacity);
fast_set(this, kCapacityIndex, Smi::FromInt(capacity));
}
@@ -2562,6 +2579,11 @@
static const int kHeaderSize = Array::kHeaderSize;
static const int kAlignedSize = Array::kAlignedSize;
+ // Maximal memory consumption for a single ByteArray.
+ static const int kMaxSize = 512 * MB;
+ // Maximal length of a single ByteArray.
+ static const int kMaxLength = kMaxSize - kHeaderSize;
+
private:
DISALLOW_IMPLICIT_CONSTRUCTORS(ByteArray);
};
@@ -4267,6 +4289,12 @@
static const int kHeaderSize = String::kSize;
static const int kAlignedSize = POINTER_SIZE_ALIGN(kHeaderSize);
+ // Maximal memory usage for a single sequential ASCII string.
+ static const int kMaxSize = 512 * MB;
+ // Maximal length of a single sequential ASCII string.
+ // Q.v. String::kMaxLength which is the maximal size of concatenated
strings.
+ static const int kMaxLength = (kMaxSize - kHeaderSize);
+
// Support for StringInputBuffer.
inline void SeqAsciiStringReadBlockIntoBuffer(ReadBlockBuffer* buffer,
unsigned* offset,
@@ -4313,6 +4341,12 @@
static const int kHeaderSize = String::kSize;
static const int kAlignedSize = POINTER_SIZE_ALIGN(kHeaderSize);
+ // Maximal memory usage for a single sequential two-byte string.
+ static const int kMaxSize = 512 * MB;
+ // Maximal length of a single sequential two-byte string.
+ // Q.v. String::kMaxLength which is the maximal size of concatenated
strings.
+ static const int kMaxLength = (kMaxSize - kHeaderSize) /
sizeof(uint16_t);
+
// Support for StringInputBuffer.
inline void SeqTwoByteStringReadBlockIntoBuffer(ReadBlockBuffer* buffer,
unsigned* offset_ptr,
=======================================
--- /branches/1.3/src/runtime.cc Thu Jan 7 00:01:27 2010
+++ /branches/1.3/src/runtime.cc Fri Jan 15 05:10:50 2010
@@ -1406,7 +1406,7 @@
void IncrementCharacterCount(int by) {
- if (character_count_ > Smi::kMaxValue - by) {
+ if (character_count_ > String::kMaxLength - by) {
V8::FatalProcessOutOfMemory("String.replace result too large.");
}
character_count_ += by;
@@ -3252,6 +3252,7 @@
escaped_length += 3;
}
// We don't allow strings that are longer than a maximal length.
+ ASSERT(String::kMaxLength < 0x7fffffff - 6); // Cannot overflow.
if (escaped_length > String::kMaxLength) {
Top::context()->mark_out_of_memory();
return Failure::OutOfMemoryException();
@@ -3813,6 +3814,7 @@
bool ascii = special->IsAsciiRepresentation();
int position = 0;
+ int increment = 0;
for (int i = 0; i < array_length; i++) {
Object* elt = fixed_array->get(i);
if (elt->IsSmi()) {
@@ -3822,21 +3824,22 @@
if (pos + len > special_length) {
return Top::Throw(Heap::illegal_argument_symbol());
}
- position += len;
+ increment = len;
} else if (elt->IsString()) {
String* element = String::cast(elt);
int element_length = element->length();
- position += element_length;
+ increment = element_length;
if (ascii && !element->IsAsciiRepresentation()) {
ascii = false;
}
} else {
return Top::Throw(Heap::illegal_argument_symbol());
}
- if (position > String::kMaxLength) {
+ if (increment > String::kMaxLength - position) {
Top::context()->mark_out_of_memory();
return Failure::OutOfMemoryException();
}
+ position += increment;
}
int length = position;
@@ -5232,11 +5235,11 @@
uint32_t index_limit,
bool fast_elements) :
storage_(storage), index_limit_(index_limit),
- fast_elements_(fast_elements), index_offset_(0) { }
+ index_offset_(0), fast_elements_(fast_elements) { }
void visit(uint32_t i, Handle<Object> elm) {
- uint32_t index = i + index_offset_;
- if (index >= index_limit_) return;
+ if (i >= index_limit_ - index_offset_) return;
+ uint32_t index = index_offset_ + i;
if (fast_elements_) {
ASSERT(index < static_cast<uint32_t>(storage_->length()));
@@ -5252,16 +5255,23 @@
}
void increase_index_offset(uint32_t delta) {
- index_offset_ += delta;
+ if (index_limit_ - index_offset_ < delta) {
+ index_offset_ = index_limit_;
+ } else {
+ index_offset_ += delta;
+ }
}
Handle<FixedArray> storage() { return storage_; }
private:
Handle<FixedArray> storage_;
+ // Limit on the accepted indices. Elements with indices larger than the
+ // limit are ignored by the visitor.
uint32_t index_limit_;
- bool fast_elements_;
+ // Index after last seen index. Always less than or equal to
index_limit_.
uint32_t index_offset_;
+ bool fast_elements_;
};
@@ -5433,6 +5443,11 @@
*
* If a ArrayConcatVisitor object is given, the visitor is called with
* parameters, element's index + visitor_index_offset and the element.
+ *
+ * The returned number of elements is an upper bound on the actual number
+ * of elements added. If the same element occurs in more than one object
+ * in the array's prototype chain, it will be counted more than once, but
+ * will only occur once in the result.
*/
static uint32_t IterateArrayAndPrototypeElements(Handle<JSArray> array,
ArrayConcatVisitor*
visitor) {
@@ -5455,8 +5470,14 @@
uint32_t nof_elements = 0;
for (int i = objects.length() - 1; i >= 0; i--) {
Handle<JSObject> obj = objects[i];
- nof_elements +=
+ uint32_t encountered_elements =
IterateElements(Handle<JSObject>::cast(obj), range, visitor);
+
+ if (encountered_elements > JSObject::kMaxElementCount - nof_elements) {
+ nof_elements = JSObject::kMaxElementCount;
+ } else {
+ nof_elements += encountered_elements;
+ }
}
return nof_elements;
@@ -5473,10 +5494,12 @@
* elements. If an argument is not an Array object, the function
* visits the object as if it is an one-element array.
*
- * If the result array index overflows 32-bit integer, the rounded
+ * If the result array index overflows 32-bit unsigned integer, the rounded
* non-negative number is used as new length. For example, if one
* array length is 2^32 - 1, second array length is 1, the
* concatenated array length is 0.
+ * TODO(lrn) Change length behavior to ECMAScript 5 specification (length
+ * is one more than the last array index to get a value assigned).
*/
static uint32_t IterateArguments(Handle<JSArray> arguments,
ArrayConcatVisitor* visitor) {
@@ -5492,16 +5515,23 @@
IterateArrayAndPrototypeElements(array, visitor);
// Total elements of array and its prototype chain can be more than
// the array length, but ArrayConcat can only concatenate at most
- // the array length number of elements.
- visited_elements += (nof_elements > len) ? len : nof_elements;
+ // the array length number of elements. We use the length as an
estimate
+ // for the actual number of elements added.
+ uint32_t added_elements = (nof_elements > len) ? len : nof_elements;
+ if (JSArray::kMaxElementCount - visited_elements < added_elements) {
+ visited_elements = JSArray::kMaxElementCount;
+ } else {
+ visited_elements += added_elements;
+ }
if (visitor) visitor->increase_index_offset(len);
-
} else {
if (visitor) {
visitor->visit(0, obj);
visitor->increase_index_offset(1);
}
- visited_elements++;
+ if (visited_elements < JSArray::kMaxElementCount) {
+ visited_elements++;
+ }
}
}
return visited_elements;
@@ -5511,6 +5541,8 @@
/**
* Array::concat implementation.
* See ECMAScript 262, 15.4.4.4.
+ * TODO(lrn): Fix non-compliance for very large concatenations and update
to
+ * following the ECMAScript 5 specification.
*/
static Object* Runtime_ArrayConcat(Arguments args) {
ASSERT(args.length() == 1);
@@ -5527,12 +5559,18 @@
{ AssertNoAllocation nogc;
for (uint32_t i = 0; i < num_of_args; i++) {
Object* obj = arguments->GetElement(i);
+ uint32_t length_estimate;
if (obj->IsJSArray()) {
- result_length +=
+ length_estimate =
static_cast<uint32_t>(JSArray::cast(obj)->length()->Number());
} else {
- result_length++;
- }
+ length_estimate = 1;
+ }
+ if (JSObject::kMaxElementCount - result_length < length_estimate) {
+ result_length = JSObject::kMaxElementCount;
+ break;
+ }
+ result_length += length_estimate;
}
}
=======================================
--- /branches/1.3/src/utils.cc Wed Oct 7 02:00:33 2009
+++ /branches/1.3/src/utils.cc Fri Jan 15 05:10:50 2010
@@ -40,6 +40,7 @@
// Implementation is from "Hacker's Delight" by Henry S. Warren, Jr.,
// figure 3-3, page 48, where the function is called clp2.
uint32_t RoundUpToPowerOf2(uint32_t x) {
+ ASSERT(x <= 0x80000000u);
x = x - 1;
x = x | (x >> 1);
x = x | (x >> 2);
=======================================
--- /branches/1.3/src/version.cc Thu Jan 7 00:01:27 2010
+++ /branches/1.3/src/version.cc Fri Jan 15 05:10:50 2010
@@ -35,7 +35,7 @@
#define MAJOR_VERSION 1
#define MINOR_VERSION 3
#define BUILD_NUMBER 18
-#define PATCH_LEVEL 19
+#define PATCH_LEVEL 20
#define CANDIDATE_VERSION false
// Define SONAME to have the SCons build the put a specific SONAME into the
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
