summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to 'libutils/VectorImpl.cpp')
-rw-r--r--libutils/VectorImpl.cpp82
1 files changed, 59 insertions, 23 deletions
diff --git a/libutils/VectorImpl.cpp b/libutils/VectorImpl.cpp
index 2ac158b9f..e8d40ed20 100644
--- a/libutils/VectorImpl.cpp
+++ b/libutils/VectorImpl.cpp
@@ -21,6 +21,7 @@
21#include <stdio.h> 21#include <stdio.h>
22 22
23#include <cutils/log.h> 23#include <cutils/log.h>
24#include <safe_iop.h>
24 25
25#include <utils/Errors.h> 26#include <utils/Errors.h>
26#include <utils/VectorImpl.h> 27#include <utils/VectorImpl.h>
@@ -86,14 +87,19 @@ VectorImpl& VectorImpl::operator = (const VectorImpl& rhs)
86void* VectorImpl::editArrayImpl() 87void* VectorImpl::editArrayImpl()
87{ 88{
88 if (mStorage) { 89 if (mStorage) {
89 SharedBuffer* sb = SharedBuffer::bufferFromData(mStorage)->attemptEdit(); 90 const SharedBuffer* sb = SharedBuffer::bufferFromData(mStorage);
90 if (sb == 0) { 91 SharedBuffer* editable = sb->attemptEdit();
91 sb = SharedBuffer::alloc(capacity() * mItemSize); 92 if (editable == 0) {
92 if (sb) { 93 // If we're here, we're not the only owner of the buffer.
93 _do_copy(sb->data(), mStorage, mCount); 94 // We must make a copy of it.
94 release_storage(); 95 editable = SharedBuffer::alloc(sb->size());
95 mStorage = sb->data(); 96 // Fail instead of returning a pointer to storage that's not
96 } 97 // editable. Otherwise we'd be editing the contents of a buffer
98 // for which we're not the only owner, which is undefined behaviour.
99 LOG_ALWAYS_FATAL_IF(editable == NULL);
100 _do_copy(editable->data(), mStorage, mCount);
101 release_storage();
102 mStorage = editable->data();
97 } 103 }
98 } 104 }
99 return mStorage; 105 return mStorage;
@@ -329,13 +335,15 @@ const void* VectorImpl::itemLocation(size_t index) const
329 335
330ssize_t VectorImpl::setCapacity(size_t new_capacity) 336ssize_t VectorImpl::setCapacity(size_t new_capacity)
331{ 337{
332 size_t current_capacity = capacity(); 338 // The capacity must always be greater than or equal to the size
333 ssize_t amount = new_capacity - size(); 339 // of this vector.
334 if (amount <= 0) { 340 if (new_capacity <= size()) {
335 // we can't reduce the capacity 341 return capacity();
336 return current_capacity; 342 }
337 } 343
338 SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 344 size_t new_allocation_size = 0;
345 LOG_ALWAYS_FATAL_IF(!safe_mul(&new_allocation_size, new_capacity, mItemSize));
346 SharedBuffer* sb = SharedBuffer::alloc(new_allocation_size);
339 if (sb) { 347 if (sb) {
340 void* array = sb->data(); 348 void* array = sb->data();
341 _do_copy(array, mStorage, size()); 349 _do_copy(array, mStorage, size());
@@ -377,9 +385,28 @@ void* VectorImpl::_grow(size_t where, size_t amount)
377 "[%p] _grow: where=%d, amount=%d, count=%d", 385 "[%p] _grow: where=%d, amount=%d, count=%d",
378 this, (int)where, (int)amount, (int)mCount); // caller already checked 386 this, (int)where, (int)amount, (int)mCount); // caller already checked
379 387
380 const size_t new_size = mCount + amount; 388 size_t new_size;
389 LOG_ALWAYS_FATAL_IF(!safe_add(&new_size, mCount, amount), "new_size overflow");
390
381 if (capacity() < new_size) { 391 if (capacity() < new_size) {
382 const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2); 392 // NOTE: This implementation used to resize vectors as per ((3*x + 1) / 2)
393 // (sigh..). Also note, the " + 1" was necessary to handle the special case
394 // where x == 1, where the resized_capacity will be equal to the old
395 // capacity without the +1. The old calculation wouldn't work properly
396 // if x was zero.
397 //
398 // This approximates the old calculation, using (x + (x/2) + 1) instead.
399 size_t new_capacity = 0;
400 LOG_ALWAYS_FATAL_IF(!safe_add(&new_capacity, new_size, (new_size / 2)),
401 "new_capacity overflow");
402 LOG_ALWAYS_FATAL_IF(!safe_add(&new_capacity, new_capacity, static_cast<size_t>(1u)),
403 "new_capacity overflow");
404 new_capacity = max(kMinVectorCapacity, new_capacity);
405
406 size_t new_alloc_size = 0;
407 LOG_ALWAYS_FATAL_IF(!safe_mul(&new_alloc_size, new_capacity, mItemSize),
408 "new_alloc_size overflow");
409
383// ALOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity); 410// ALOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity);
384 if ((mStorage) && 411 if ((mStorage) &&
385 (mCount==where) && 412 (mCount==where) &&
@@ -387,14 +414,14 @@ void* VectorImpl::_grow(size_t where, size_t amount)
387 (mFlags & HAS_TRIVIAL_DTOR)) 414 (mFlags & HAS_TRIVIAL_DTOR))
388 { 415 {
389 const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage); 416 const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage);
390 SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize); 417 SharedBuffer* sb = cur_sb->editResize(new_alloc_size);
391 if (sb) { 418 if (sb) {
392 mStorage = sb->data(); 419 mStorage = sb->data();
393 } else { 420 } else {
394 return NULL; 421 return NULL;
395 } 422 }
396 } else { 423 } else {
397 SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 424 SharedBuffer* sb = SharedBuffer::alloc(new_alloc_size);
398 if (sb) { 425 if (sb) {
399 void* array = sb->data(); 426 void* array = sb->data();
400 if (where != 0) { 427 if (where != 0) {
@@ -436,10 +463,19 @@ void VectorImpl::_shrink(size_t where, size_t amount)
436 "[%p] _shrink: where=%d, amount=%d, count=%d", 463 "[%p] _shrink: where=%d, amount=%d, count=%d",
437 this, (int)where, (int)amount, (int)mCount); // caller already checked 464 this, (int)where, (int)amount, (int)mCount); // caller already checked
438 465
439 const size_t new_size = mCount - amount; 466 size_t new_size;
440 if (new_size*3 < capacity()) { 467 LOG_ALWAYS_FATAL_IF(!safe_sub(&new_size, mCount, amount));
441 const size_t new_capacity = max(kMinVectorCapacity, new_size*2); 468
442// ALOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity); 469 if (new_size < (capacity() / 2)) {
470 // NOTE: (new_size * 2) is safe because capacity didn't overflow and
471 // new_size < (capacity / 2)).
472 const size_t new_capacity = max(kMinVectorCapacity, new_size * 2);
473
474 // NOTE: (new_capacity * mItemSize), (where * mItemSize) and
475 // ((where + amount) * mItemSize) beyond this point are safe because
476 // we are always reducing the capacity of the underlying SharedBuffer.
477 // In other words, (old_capacity * mItemSize) did not overflow, and
478 // where < (where + amount) < new_capacity < old_capacity.
443 if ((where == new_size) && 479 if ((where == new_size) &&
444 (mFlags & HAS_TRIVIAL_COPY) && 480 (mFlags & HAS_TRIVIAL_COPY) &&
445 (mFlags & HAS_TRIVIAL_DTOR)) 481 (mFlags & HAS_TRIVIAL_DTOR))