You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucy.apache.org by nw...@apache.org on 2015/07/14 16:05:56 UTC
[6/6] lucy-clownfish git commit: More rework of Vector oversizing
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 <we...@aevum.de>
Authored: Tue Jul 14 15:17:27 2015 +0200
Committer: Nick Wellnhofer <we...@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;
}