From 419e6c3c68413bd6dbb6872340b2ae0d69a0fd60 Mon Sep 17 00:00:00 2001 From: Narayan Kamath Date: Fri, 28 Aug 2015 12:59:48 +0100 Subject: libutils: Fix integer overflows in VectorImpl. Use external/safe-iop to check for overflows on arithmetic operations. Also remove an unnecessary copy of Vector/SharedBuffer from codeflinger and use the copy from libutils instead. Note that some of the unit tests are somewhat useless due to test-runner limitations : gtest's ability to filter on abort message doesn't work when combined with messages formatted by android's logging system. bug: 22953624 (cherry picked from commit c609c31fb56ae434caa2d0153cd0a2f74a715071) Change-Id: I61644633db6b54fa230683615de9724f7fabf6fb --- libutils/Android.mk | 3 ++ libutils/VectorImpl.cpp | 82 ++++++++++++++++++++++++++++++------------ libutils/tests/Vector_test.cpp | 77 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 139 insertions(+), 23 deletions(-) (limited to 'libutils') diff --git a/libutils/Android.mk b/libutils/Android.mk index 4127b99..035846b 100644 --- a/libutils/Android.mk +++ b/libutils/Android.mk @@ -71,6 +71,7 @@ LOCAL_MODULE:= libutils LOCAL_STATIC_LIBRARIES := liblog LOCAL_CFLAGS += $(host_commonCflags) LOCAL_MULTILIB := both +LOCAL_C_INCLUDES += external/safe-iop/include include $(BUILD_HOST_STATIC_LIBRARY) @@ -105,6 +106,7 @@ LOCAL_SHARED_LIBRARIES := \ include external/stlport/libstlport.mk LOCAL_MODULE:= libutils +LOCAL_C_INCLUDES += external/safe-iop/include include $(BUILD_STATIC_LIBRARY) # For the device, shared @@ -118,6 +120,7 @@ LOCAL_SHARED_LIBRARIES := \ libdl \ liblog LOCAL_CFLAGS := -Werror +LOCAL_C_INCLUDES += external/safe-iop/include include external/stlport/libstlport.mk diff --git a/libutils/VectorImpl.cpp b/libutils/VectorImpl.cpp index 30ca663..de65a6c 100644 --- a/libutils/VectorImpl.cpp +++ b/libutils/VectorImpl.cpp @@ -21,6 +21,7 @@ #include #include +#include #include #include @@ -85,14 +86,19 @@ VectorImpl& VectorImpl::operator = (const VectorImpl& rhs) void* VectorImpl::editArrayImpl() { if (mStorage) { - SharedBuffer* sb = SharedBuffer::bufferFromData(mStorage)->attemptEdit(); - if (sb == 0) { - sb = SharedBuffer::alloc(capacity() * mItemSize); - if (sb) { - _do_copy(sb->data(), mStorage, mCount); - release_storage(); - mStorage = sb->data(); - } + const SharedBuffer* sb = SharedBuffer::bufferFromData(mStorage); + SharedBuffer* editable = sb->attemptEdit(); + if (editable == 0) { + // If we're here, we're not the only owner of the buffer. + // We must make a copy of it. + editable = SharedBuffer::alloc(sb->size()); + // Fail instead of returning a pointer to storage that's not + // editable. Otherwise we'd be editing the contents of a buffer + // for which we're not the only owner, which is undefined behaviour. + LOG_ALWAYS_FATAL_IF(editable == NULL); + _do_copy(editable->data(), mStorage, mCount); + release_storage(); + mStorage = editable->data(); } } return mStorage; @@ -325,13 +331,15 @@ const void* VectorImpl::itemLocation(size_t index) const ssize_t VectorImpl::setCapacity(size_t new_capacity) { - size_t current_capacity = capacity(); - ssize_t amount = new_capacity - size(); - if (amount <= 0) { - // we can't reduce the capacity - return current_capacity; - } - SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); + // The capacity must always be greater than or equal to the size + // of this vector. + if (new_capacity <= size()) { + return capacity(); + } + + size_t new_allocation_size = 0; + LOG_ALWAYS_FATAL_IF(!safe_mul(&new_allocation_size, new_capacity, mItemSize)); + SharedBuffer* sb = SharedBuffer::alloc(new_allocation_size); if (sb) { void* array = sb->data(); _do_copy(array, mStorage, size()); @@ -373,9 +381,28 @@ void* VectorImpl::_grow(size_t where, size_t amount) "[%p] _grow: where=%d, amount=%d, count=%d", this, (int)where, (int)amount, (int)mCount); // caller already checked - const size_t new_size = mCount + amount; + size_t new_size; + LOG_ALWAYS_FATAL_IF(!safe_add(&new_size, mCount, amount), "new_size overflow"); + if (capacity() < new_size) { - const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2); + // NOTE: This implementation used to resize vectors as per ((3*x + 1) / 2) + // (sigh..). Also note, the " + 1" was necessary to handle the special case + // where x == 1, where the resized_capacity will be equal to the old + // capacity without the +1. The old calculation wouldn't work properly + // if x was zero. + // + // This approximates the old calculation, using (x + (x/2) + 1) instead. + size_t new_capacity = 0; + LOG_ALWAYS_FATAL_IF(!safe_add(&new_capacity, new_size, (new_size / 2)), + "new_capacity overflow"); + LOG_ALWAYS_FATAL_IF(!safe_add(&new_capacity, new_capacity, static_cast(1u)), + "new_capacity overflow"); + new_capacity = max(kMinVectorCapacity, new_capacity); + + size_t new_alloc_size = 0; + LOG_ALWAYS_FATAL_IF(!safe_mul(&new_alloc_size, new_capacity, mItemSize), + "new_alloc_size overflow"); + // ALOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity); if ((mStorage) && (mCount==where) && @@ -383,14 +410,14 @@ void* VectorImpl::_grow(size_t where, size_t amount) (mFlags & HAS_TRIVIAL_DTOR)) { const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage); - SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize); + SharedBuffer* sb = cur_sb->editResize(new_alloc_size); if (sb) { mStorage = sb->data(); } else { return NULL; } } else { - SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); + SharedBuffer* sb = SharedBuffer::alloc(new_alloc_size); if (sb) { void* array = sb->data(); if (where != 0) { @@ -432,10 +459,19 @@ void VectorImpl::_shrink(size_t where, size_t amount) "[%p] _shrink: where=%d, amount=%d, count=%d", this, (int)where, (int)amount, (int)mCount); // caller already checked - const size_t new_size = mCount - amount; - if (new_size*3 < capacity()) { - const size_t new_capacity = max(kMinVectorCapacity, new_size*2); -// ALOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity); + size_t new_size; + LOG_ALWAYS_FATAL_IF(!safe_sub(&new_size, mCount, amount)); + + if (new_size < (capacity() / 2)) { + // NOTE: (new_size * 2) is safe because capacity didn't overflow and + // new_size < (capacity / 2)). + const size_t new_capacity = max(kMinVectorCapacity, new_size * 2); + + // NOTE: (new_capacity * mItemSize), (where * mItemSize) and + // ((where + amount) * mItemSize) beyond this point are safe because + // we are always reducing the capacity of the underlying SharedBuffer. + // In other words, (old_capacity * mItemSize) did not overflow, and + // where < (where + amount) < new_capacity < old_capacity. if ((where == new_size) && (mFlags & HAS_TRIVIAL_COPY) && (mFlags & HAS_TRIVIAL_DTOR)) diff --git a/libutils/tests/Vector_test.cpp b/libutils/tests/Vector_test.cpp index d29c054..8013187 100644 --- a/libutils/tests/Vector_test.cpp +++ b/libutils/tests/Vector_test.cpp @@ -16,6 +16,8 @@ #define LOG_TAG "Vector_test" +#define __STDC_LIMIT_MACROS +#include #include #include #include @@ -71,5 +73,80 @@ TEST_F(VectorTest, CopyOnWrite_CopyAndAddElements) { EXPECT_EQ(other[3], 5); } +// TODO: gtest isn't capable of parsing Abort messages formatted by +// Android (fails differently on host and target), so we always need to +// use an empty error message for death tests. +TEST_F(VectorTest, SetCapacity_Overflow) { + Vector vector; + EXPECT_DEATH(vector.setCapacity(SIZE_MAX / sizeof(int) + 1), ""); +} + +TEST_F(VectorTest, SetCapacity_ShrinkBelowSize) { + Vector vector; + vector.add(1); + vector.add(2); + vector.add(3); + vector.add(4); + + vector.setCapacity(8); + ASSERT_EQ(8U, vector.capacity()); + vector.setCapacity(2); + ASSERT_EQ(8U, vector.capacity()); +} + +// NOTE: All of the tests below are useless because of the "TODO" above. +// We have no way of knowing *why* the process crashed. Given that we're +// inserting a NULL array, we'll fail with a SIGSEGV eventually. We need +// the ability to make assertions on the abort message to make sure we're +// failing for the right reasons. +TEST_F(VectorTest, _grow_OverflowSize) { + Vector vector; + vector.add(1); + + // Checks that the size calculation (not the capacity calculation) doesn't + // overflow : the size here will be (1 + SIZE_MAX). + // + // EXPECT_DEATH(vector.insertArrayAt(NULL, 0, SIZE_MAX), "new_size_overflow"); + EXPECT_DEATH(vector.insertArrayAt(NULL, 0, SIZE_MAX), ""); +} + +TEST_F(VectorTest, _grow_OverflowCapacityDoubling) { + Vector vector; + + // This should fail because the calculated capacity will overflow even though + // the size of the vector doesn't. + // + // EXPECT_DEATH(vector.insertArrayAt(NULL, 0, (SIZE_MAX - 1)), "new_capacity_overflow"); + EXPECT_DEATH(vector.insertArrayAt(NULL, 0, (SIZE_MAX - 1)), ""); +} + +TEST_F(VectorTest, _grow_OverflowBufferAlloc) { + Vector vector; + // This should fail because the capacity * sizeof(int) overflows, even + // though the capacity itself doesn't. + // + // EXPECT_DEATH(vector.insertArrayAt(NULL, 0, (SIZE_MAX / 2)), "new_alloc_size overflow"); + EXPECT_DEATH(vector.insertArrayAt(NULL, 0, (SIZE_MAX / 2)), ""); +} + +TEST_F(VectorTest, editArray_Shared) { + Vector vector1; + vector1.add(1); + vector1.add(2); + vector1.add(3); + vector1.add(4); + + Vector vector2 = vector1; + ASSERT_EQ(vector1.array(), vector2.array()); + // We must make a copy here, since we're not the exclusive owners + // of this array. + ASSERT_NE(vector1.editArray(), vector2.editArray()); + + // Vector doesn't implement operator ==. + ASSERT_EQ(vector1.size(), vector2.size()); + for (size_t i = 0; i < vector1.size(); ++i) { + EXPECT_EQ(vector1[i], vector2[i]); + } +} } // namespace android -- cgit v1.1