More rework of Vector oversizing Reduce number of overflow checks. Make sure that array size doesn't overflow just because of oversizing.
Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/6090c315 Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/6090c315 Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/6090c315 Branch: refs/heads/master Commit: 6090c3153a0d7680117140e25332e243021e15db Parents: c91a9e4 Author: Nick Wellnhofer <wellnho...@aevum.de> Authored: Tue Jul 14 15:17:27 2015 +0200 Committer: Nick Wellnhofer <wellnho...@aevum.de> Committed: Tue Jul 14 15:25:43 2015 +0200 ---------------------------------------------------------------------- runtime/core/Clownfish/Test/TestVector.c | 22 +++++++++---- runtime/core/Clownfish/Vector.c | 47 ++++++++++++--------------- 2 files changed, 37 insertions(+), 32 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/6090c315/runtime/core/Clownfish/Test/TestVector.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Test/TestVector.c b/runtime/core/Clownfish/Test/TestVector.c index 1a72768..7b51cb3 100644 --- a/runtime/core/Clownfish/Test/TestVector.c +++ b/runtime/core/Clownfish/Test/TestVector.c @@ -21,6 +21,8 @@ #define CFISH_USE_SHORT_NAMES #define TESTCFISH_USE_SHORT_NAMES +#define MAX_VECTOR_SIZE (SIZE_MAX / sizeof(Obj*)) + #include "Clownfish/Test/TestVector.h" #include "Clownfish/String.h" @@ -406,7 +408,7 @@ static void S_overflow_Push(void *context) { UNUSED_VAR(context); Vector *array = Vec_new(0); - array->cap = SIZE_MAX; + array->cap = MAX_VECTOR_SIZE; array->size = array->cap; Vec_Push(array, (Obj*)CFISH_TRUE); } @@ -415,9 +417,7 @@ static void S_overflow_Insert(void *context) { UNUSED_VAR(context); Vector *array = Vec_new(0); - array->cap = SIZE_MAX; - array->size = array->cap; - Vec_Insert(array, 38911, (Obj*)CFISH_TRUE); + Vec_Insert(array, SIZE_MAX, (Obj*)CFISH_TRUE); } static void @@ -427,12 +427,20 @@ S_overflow_Push_All(void *context) { array->cap = 1000000000; array->size = array->cap; Vector *other = Vec_new(0); - other->cap = SIZE_MAX - array->cap + 1; + other->cap = MAX_VECTOR_SIZE - array->cap + 1; other->size = other->cap; Vec_Push_All(array, other); } static void +S_overflow_Insert_All(void *context) { + UNUSED_VAR(context); + Vector *array = Vec_new(0); + Vector *other = Vec_new(0); + Vec_Insert_All(array, SIZE_MAX, other); +} + +static void S_overflow_Store(void *context) { UNUSED_VAR(context); Vector *array = Vec_new(0); @@ -459,6 +467,8 @@ test_exceptions(TestBatchRunner *runner) { "Insert throws on overflow"); S_test_exception(runner, S_overflow_Push_All, "Push_All throws on overflow"); + S_test_exception(runner, S_overflow_Insert_All, + "Insert_All throws on overflow"); S_test_exception(runner, S_overflow_Store, "Store throws on overflow"); } @@ -517,7 +527,7 @@ test_Grow(TestBatchRunner *runner) { void TestVector_Run_IMP(TestVector *self, TestBatchRunner *runner) { - TestBatchRunner_Plan(runner, (TestBatch*)self, 61); + TestBatchRunner_Plan(runner, (TestBatch*)self, 62); test_Equals(runner); test_Store_Fetch(runner); test_Push_Pop_Insert(runner); http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/6090c315/runtime/core/Clownfish/Vector.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Vector.c b/runtime/core/Clownfish/Vector.c index 8dbf3cc..18c09d2 100644 --- a/runtime/core/Clownfish/Vector.c +++ b/runtime/core/Clownfish/Vector.c @@ -26,18 +26,17 @@ #include "Clownfish/Util/Memory.h" #include "Clownfish/Util/SortUtils.h" +#define MAX_VECTOR_SIZE (SIZE_MAX / sizeof(Obj*)) + static CFISH_INLINE void SI_copy_and_incref(Obj **dst, Obj **src, size_t num); static CFISH_INLINE void -SI_add_grow_and_oversize(Vector *self, size_t addend1, size_t addend2); +SI_add_grow_and_oversize(Vector *self, size_t size, size_t extra); static void S_grow_and_oversize(Vector *self, size_t min_size); -static CFISH_INLINE void -SI_grow(Vector *self, size_t capacity); - static void S_overflow_error(void); @@ -110,7 +109,7 @@ Vec_Pop_IMP(Vector *self) { void Vec_Insert_IMP(Vector *self, size_t tick, Obj *elem) { size_t max_tick = tick > self->size ? tick : self->size; - SI_add_grow_and_oversize(self, max_tick, 1); + SI_add_grow_and_oversize(self, 1, max_tick); if (tick < self->size) { memmove(self->elems + tick + 1, self->elems + tick, @@ -128,7 +127,7 @@ Vec_Insert_IMP(Vector *self, size_t tick, Obj *elem) { void Vec_Insert_All_IMP(Vector *self, size_t tick, Vector *other) { size_t max_tick = tick > self->size ? tick : self->size; - SI_add_grow_and_oversize(self, max_tick, other->size); + SI_add_grow_and_oversize(self, other->size, max_tick); if (tick < self->size) { memmove(self->elems + tick + other->size, self->elems + tick, @@ -158,7 +157,7 @@ Vec_Store_IMP(Vector *self, size_t tick, Obj *elem) { DECREF(self->elems[tick]); } else { - SI_add_grow_and_oversize(self, tick, 1); + SI_add_grow_and_oversize(self, 1, tick); memset(self->elems + self->size, 0, (tick - self->size) * sizeof(Obj*)); self->size = tick + 1; @@ -169,7 +168,12 @@ Vec_Store_IMP(Vector *self, size_t tick, Obj *elem) { void Vec_Grow_IMP(Vector *self, size_t capacity) { if (capacity > self->cap) { - SI_grow(self, capacity); + if (capacity > MAX_VECTOR_SIZE) { + S_overflow_error(); + return; + } + self->elems = (Obj**)REALLOCATE(self->elems, capacity * sizeof(Obj*)); + self->cap = capacity; } } @@ -301,22 +305,24 @@ SI_copy_and_incref(Obj **dst, Obj **src, size_t num) { } } -// Ensure that the vector's capacity is at least (addend1 + addend2). +// Ensure that the vector's capacity is at least (size + extra). +// Assumes that size <= MAX_VECTOR_SIZE. // If the vector must be grown, oversize the allocation. static CFISH_INLINE void -SI_add_grow_and_oversize(Vector *self, size_t addend1, size_t addend2) { - size_t min_size = addend1 + addend2; - // Check for overflow. - if (min_size < addend1) { +SI_add_grow_and_oversize(Vector *self, size_t size, size_t extra) { + if (extra > MAX_VECTOR_SIZE - size) { S_overflow_error(); return; } + size_t min_size = size + extra; if (min_size > self->cap) { S_grow_and_oversize(self, min_size); } } +// Assumes min_size <= MAX_VECTOR_SIZE. +// __attribute__((noinline)) static void S_grow_and_oversize(Vector *self, size_t min_size) { // Oversize by 25%, but at least four elements. @@ -324,21 +330,10 @@ S_grow_and_oversize(Vector *self, size_t min_size) { if (extra < 4) { extra = 4; } size_t capacity = min_size + extra; - // Check for overflow. - if (capacity < min_size) { - S_overflow_error(); - return; + if (capacity > MAX_VECTOR_SIZE) { + capacity = MAX_VECTOR_SIZE; } - SI_grow(self, capacity); -} - -static CFISH_INLINE void -SI_grow(Vector *self, size_t capacity) { - if (capacity > SIZE_MAX / sizeof(Obj*)) { - S_overflow_error(); - return; - } self->elems = (Obj**)REALLOCATE(self->elems, capacity * sizeof(Obj*)); self->cap = capacity; }
