From 8e8e507ed720ca0acbeb15e238bf99519a9e7aab Mon Sep 17 00:00:00 2001 From: FdaSilvaYY Date: Thu, 28 Sep 2017 22:03:26 +0200 Subject: [PATCH] Postpone allocation of STACK internal storage ... until a first push(), insert() or an explicit call to OPENSSL_sk_reserve Factorise STACK item deletion code Reviewed-by: Andy Polyakov Reviewed-by: Paul Dale Reviewed-by: Richard Levitte (Merged from https://github.com/openssl/openssl/pull/4379) --- crypto/stack/stack.c | 96 +++++++++++++++++++++++++++++--------------- 1 file changed, 63 insertions(+), 33 deletions(-) diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c index e71da73fb5..5c9d48726e 100644 --- a/crypto/stack/stack.c +++ b/crypto/stack/stack.c @@ -55,6 +55,13 @@ OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk) /* direct structure assignment */ *ret = *sk; + if (sk->num == 0) { + /* postpone |ret->data| allocation */ + ret->data = NULL; + ret->num_alloc = 0; + return ret; + } + /* duplicate |sk->data| content */ if ((ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc)) == NULL) goto err; memcpy(ret->data, sk->data, sizeof(void *) * sk->num); @@ -80,6 +87,13 @@ OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk, /* direct structure assignment */ *ret = *sk; + if (sk->num == 0) { + /* postpone |ret| data allocation */ + ret->data = NULL; + ret->num_alloc = 0; + return ret; + } + ret->num_alloc = sk->num > min_nodes ? sk->num : min_nodes; ret->data = OPENSSL_zalloc(sizeof(*ret->data) * ret->num_alloc); if (ret->data == NULL) { @@ -103,41 +117,35 @@ OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk, OPENSSL_STACK *OPENSSL_sk_new_null(void) { - return OPENSSL_sk_new((OPENSSL_sk_compfunc)NULL); + return OPENSSL_zalloc(sizeof(OPENSSL_STACK)); } OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c) { - OPENSSL_STACK *ret; - - if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) - goto err; - if ((ret->data = OPENSSL_zalloc(sizeof(*ret->data) * min_nodes)) == NULL) - goto err; - ret->comp = c; - ret->num_alloc = min_nodes; - return (ret); + OPENSSL_STACK *ret = OPENSSL_sk_new_null(); - err: - OPENSSL_free(ret); - return (NULL); + if (ret != NULL) + ret->comp = c; + return ret; } /* * Calculate the array growth based on the target size. * - * The growth faction is a rational number and is defined by a numerator + * The growth fraction is a rational number and is defined by a numerator * and a denominator. According to Andrew Koenig in his paper "Why Are * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less * than the golden ratio (1.618...). * - * We use 3/2 = 1.5 for simplicty of calculation and overflow checking. + * We use 3/2 = 1.5 for simplicity of calculation and overflow checking. * Another option 8/5 = 1.6 allows for slightly faster growth, although safe * computation is more difficult. * * The limit to avoid overflow is spot on. The modulo three correction term * ensures that the limit is the largest number than can be expanded by the * growth factor without exceeding the hard limit. + * + * Do not call it with |current| lower than 2, or it will infinitely loop. */ static ossl_inline int compute_growth(int target, int current) { @@ -154,6 +162,7 @@ static ossl_inline int compute_growth(int target, int current) return current; } +/* internal STACK storage allocation */ static int sk_reserve(OPENSSL_STACK *st, int n, int exact) { const void **tmpdata; @@ -168,6 +177,19 @@ static int sk_reserve(OPENSSL_STACK *st, int n, int exact) if (num_alloc < min_nodes) num_alloc = min_nodes; + /* If |st->data| allocation was postponed */ + if (st->data == NULL) { + /* + * At this point, |st->num_alloc| and |st->num| are 0; + * so |num_alloc| value is |n| or |min_nodes| if greater than |n|. + */ + st->data = OPENSSL_zalloc(sizeof(void *) * num_alloc); + if (st->data == NULL) + return 0; + st->num_alloc = num_alloc; + return 1; + } + if (!exact) { if (num_alloc <= st->num_alloc) return 1; @@ -217,29 +239,34 @@ int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc) return st->num; } +static ossl_inline void *internal_delete(OPENSSL_STACK *st, int loc) +{ + const void *ret = st->data[loc]; + + if (loc != st->num - 1) + memmove(&st->data[loc], &st->data[loc + 1], + sizeof(st->data[0]) * (st->num - loc - 1)); + st->num--; + + return (void *)ret; +} + void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p) { int i; for (i = 0; i < st->num; i++) if (st->data[i] == p) - return OPENSSL_sk_delete(st, i); + return internal_delete(st, i); return NULL; } void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc) { - const void *ret; - if (st == NULL || loc < 0 || loc >= st->num) return NULL; - ret = st->data[loc]; - if (loc != st->num - 1) - memmove(&st->data[loc], &st->data[loc + 1], - sizeof(st->data[0]) * (st->num - loc - 1)); - st->num--; - return (void *)ret; + return internal_delete(st, loc); } static int internal_find(OPENSSL_STACK *st, const void *data, @@ -248,7 +275,7 @@ static int internal_find(OPENSSL_STACK *st, const void *data, const void *r; int i; - if (st == NULL) + if (st == NULL || st->num == 0) return -1; if (st->comp == NULL) { @@ -279,7 +306,9 @@ int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data) int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data) { - return (OPENSSL_sk_insert(st, data, st->num)); + if (st == NULL) + return -1; + return OPENSSL_sk_insert(st, data, st->num); } int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data) @@ -290,19 +319,19 @@ int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data) void *OPENSSL_sk_shift(OPENSSL_STACK *st) { if (st == NULL) - return (NULL); + return NULL; if (st->num <= 0) - return (NULL); - return (OPENSSL_sk_delete(st, 0)); + return NULL; + return internal_delete(st, 0); } void *OPENSSL_sk_pop(OPENSSL_STACK *st) { if (st == NULL) - return (NULL); + return NULL; if (st->num <= 0) - return (NULL); - return (OPENSSL_sk_delete(st, st->num - 1)); + return NULL; + return internal_delete(st, st->num - 1); } void OPENSSL_sk_zero(OPENSSL_STACK *st) @@ -360,7 +389,8 @@ void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data) void OPENSSL_sk_sort(OPENSSL_STACK *st) { if (st && !st->sorted && st->comp != NULL) { - qsort(st->data, st->num, sizeof(void *), st->comp); + if (st->data != NULL) + qsort(st->data, st->num, sizeof(void *), st->comp); st->sorted = 1; } } -- 2.34.1