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