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

Change-Id: I46b1ae8ca1f3a010be13aca36a091e76a97a7b70

4 files changed, 145 insertions, 23 deletions

diff --git a/libutils/Android.mk b/libutils/Android.mk
index d1ed99758..23a5c598f 100644
--- a/libutils/Android.mk
+++ b/libutils/Android.mk
@@ -62,6 +62,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)
 
 
@@ -92,6 +93,7 @@ LOCAL_SHARED_LIBRARIES := \
         libdl
 
 LOCAL_MODULE:= libutils
+LOCAL_C_INCLUDES += external/safe-iop/include
 include $(BUILD_STATIC_LIBRARY)
 
 # For the device, shared
@@ -105,6 +107,7 @@ LOCAL_SHARED_LIBRARIES := \
         libdl \
         liblog
 LOCAL_CFLAGS := -Werror
+LOCAL_C_INCLUDES += external/safe-iop/include
 
 include $(BUILD_SHARED_LIBRARY)
 
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 @@
 #include <stdio.h>
 
 #include <cutils/log.h>
+#include <safe_iop.h>
 
 #include <utils/Errors.h>
 #include <utils/SharedBuffer.h>
@@ -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<size_t>(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/Android.mk b/libutils/tests/Android.mk
index 7cfad89ca..d4a45fd72 100644
--- a/libutils/tests/Android.mk
+++ b/libutils/tests/Android.mk
@@ -38,3 +38,11 @@ LOCAL_SHARED_LIBRARIES := \
     libutils \
 
 include $(BUILD_NATIVE_TEST)
+
+include $(CLEAR_VARS)
+
+LOCAL_MODULE := libutils_tests_host
+LOCAL_SRC_FILES := Vector_test.cpp
+LOCAL_STATIC_LIBRARIES := libutils liblog
+
+include $(BUILD_HOST_NATIVE_TEST)
diff --git a/libutils/tests/Vector_test.cpp b/libutils/tests/Vector_test.cpp
index d29c05445..09914bd40 100644
--- a/libutils/tests/Vector_test.cpp
+++ b/libutils/tests/Vector_test.cpp
@@ -71,5 +71,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<int> vector;
+  EXPECT_DEATH(vector.setCapacity(SIZE_MAX / sizeof(int) + 1), "");
+}
+
+TEST_F(VectorTest, SetCapacity_ShrinkBelowSize) {
+  Vector<int> vector;
+  vector.add(1);
+  vector.add(2);
+  vector.add(3);
+  vector.add(4);
+
+  vector.setCapacity(8);
+  ASSERT_EQ(8, vector.capacity());
+  vector.setCapacity(2);
+  ASSERT_EQ(8, 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<int> 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<int> 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<int> 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<int> vector1;
+  vector1.add(1);
+  vector1.add(2);
+  vector1.add(3);
+  vector1.add(4);
+
+  Vector<int> 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