From: Pauli Date: Thu, 17 Aug 2017 00:10:07 +0000 (+1000) Subject: Add a reserve call to the stack data structure. X-Git-Tag: OpenSSL_1_1_1-pre1~617 X-Git-Url: https://git.openssl.org/?p=openssl.git;a=commitdiff_plain;h=1b3e2bbf64b96f636277ca29b31ba152c1831e74 Add a reserve call to the stack data structure. This allows the caller to guarantee that there is sufficient space for a number of insertions without reallocation. The expansion ratio when reallocating the array is reduced to 1.5 rather than 2. Change bounds testing to use a single size rather than both INT_MAX and SIZE_MAX. This simplifies some of the tests. Switch the stack pointers to data from char * to void * Reviewed-by: Andy Polyakov (Merged from https://github.com/openssl/openssl/pull/4386) --- diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c index 43ddf30ac1..e71da73fb5 100644 --- a/crypto/stack/stack.c +++ b/crypto/stack/stack.c @@ -1,5 +1,5 @@ /* - * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. + * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved. * * Licensed under the OpenSSL license (the "License"). You may not use * this file except in compliance with the License. You can obtain a copy @@ -12,20 +12,25 @@ #include "internal/numbers.h" #include #include +#include +#include /* For ossl_inline */ + +/* + * The initial number of nodes in the array. + */ +static const int min_nodes = 4; +static const int max_nodes = SIZE_MAX / sizeof(void *) < INT_MAX + ? (int)(SIZE_MAX / sizeof(void *)) + : INT_MAX; struct stack_st { int num; - const char **data; + const void **data; int sorted; - size_t num_alloc; + int num_alloc; OPENSSL_sk_compfunc comp; }; -#undef MIN_NODES -#define MIN_NODES 4 - -#include - OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc c) { OPENSSL_sk_compfunc old = sk->comp; @@ -52,7 +57,7 @@ OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk) if ((ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc)) == NULL) goto err; - memcpy(ret->data, sk->data, sizeof(char *) * sk->num); + memcpy(ret->data, sk->data, sizeof(void *) * sk->num); return ret; err: OPENSSL_sk_free(ret); @@ -75,7 +80,7 @@ OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk, /* direct structure assignment */ *ret = *sk; - ret->num_alloc = sk->num > MIN_NODES ? (size_t)sk->num : MIN_NODES; + 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) { OPENSSL_free(ret); @@ -107,10 +112,10 @@ OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c) if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) goto err; - if ((ret->data = OPENSSL_zalloc(sizeof(*ret->data) * MIN_NODES)) == NULL) + if ((ret->data = OPENSSL_zalloc(sizeof(*ret->data) * min_nodes)) == NULL) goto err; ret->comp = c; - ret->num_alloc = MIN_NODES; + ret->num_alloc = min_nodes; return (ret); err: @@ -118,32 +123,88 @@ OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c) return (NULL); } -int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc) +/* + * Calculate the array growth based on the target size. + * + * The growth faction 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. + * 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. + */ +static ossl_inline int compute_growth(int target, int current) { - if (st == NULL || st->num < 0 || st->num == INT_MAX) { - return 0; + const int limit = (max_nodes / 3) * 2 + (max_nodes % 3 ? 1 : 0); + + while (current < target) { + /* Check to see if we're at the hard limit */ + if (current >= max_nodes) + return 0; + + /* Expand the size by a factor of 3/2 if it is within range */ + current = current < limit ? current + current / 2 : max_nodes; } + return current; +} - if (st->num_alloc <= (size_t)(st->num + 1)) { - size_t doub_num_alloc = st->num_alloc * 2; - const char **tmpdata; +static int sk_reserve(OPENSSL_STACK *st, int n, int exact) +{ + const void **tmpdata; + int num_alloc; - /* Overflow checks */ - if (doub_num_alloc < st->num_alloc) - return 0; + /* Check to see the reservation isn't exceeding the hard limit */ + if (n > max_nodes - st->num) + return 0; - /* Avoid overflow due to multiplication by sizeof(char *) */ - if (doub_num_alloc > SIZE_MAX / sizeof(char *)) - return 0; + /* Figure out the new size */ + num_alloc = st->num + n; + if (num_alloc < min_nodes) + num_alloc = min_nodes; - tmpdata = OPENSSL_realloc((char *)st->data, - sizeof(char *) * doub_num_alloc); - if (tmpdata == NULL) + if (!exact) { + if (num_alloc <= st->num_alloc) + return 1; + num_alloc = compute_growth(num_alloc, st->num_alloc); + if (num_alloc == 0) return 0; - - st->data = tmpdata; - st->num_alloc = doub_num_alloc; + } else if (num_alloc == st->num_alloc) { + return 1; } + + tmpdata = OPENSSL_realloc((void *)st->data, sizeof(void *) * num_alloc); + if (tmpdata == NULL) + return 0; + + st->data = tmpdata; + st->num_alloc = num_alloc; + return 1; +} + +int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n) +{ + if (st == NULL || st->num < 0) + return 0; + + if (n < 0) + return 1; + return sk_reserve(st, n, 1); +} + +int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc) +{ + if (st == NULL || st->num < 0 || st->num == max_nodes) + return 0; + + if (!sk_reserve(st, 1, 0)) + return 0; + if ((loc >= st->num) || (loc < 0)) { st->data[st->num] = data; } else { @@ -168,7 +229,7 @@ void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p) void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc) { - const char *ret; + const void *ret; if (st == NULL || loc < 0 || loc >= st->num) return NULL; @@ -203,7 +264,7 @@ static int internal_find(OPENSSL_STACK *st, const void *data, ret_val_options); if (r == NULL) return (-1); - return (int)((const char **)r - st->data); + return (int)((const void **)r - st->data); } int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data) @@ -299,7 +360,7 @@ 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(char *), st->comp); + qsort(st->data, st->num, sizeof(void *), st->comp); st->sorted = 1; } } diff --git a/doc/man3/DEFINE_STACK_OF.pod b/doc/man3/DEFINE_STACK_OF.pod index 82989fad08..a9fc769f2b 100644 --- a/doc/man3/DEFINE_STACK_OF.pod +++ b/doc/man3/DEFINE_STACK_OF.pod @@ -5,17 +5,18 @@ DEFINE_STACK_OF, DEFINE_STACK_OF_CONST, DEFINE_SPECIAL_STACK_OF, DEFINE_SPECIAL_STACK_OF_CONST, OPENSSL_sk_deep_copy, OPENSSL_sk_delete, OPENSSL_sk_delete_ptr, -OPENSSL_sk_dup, OPENSSL_sk_find, OPENSSL_sk_find_ex, OPENSSL_sk_free, -OPENSSL_sk_insert, OPENSSL_sk_is_sorted, OPENSSL_sk_new, OPENSSL_sk_new_null, -OPENSSL_sk_num, OPENSSL_sk_pop, OPENSSL_sk_pop_free, OPENSSL_sk_push, -OPENSSL_sk_set, OPENSSL_sk_set_cmp_func, OPENSSL_sk_shift, OPENSSL_sk_sort, +OPENSSL_sk_dup, OPENSSL_sk_find, OPENSSL_sk_find_ex, +OPENSSL_sk_free, OPENSSL_sk_insert, OPENSSL_sk_is_sorted, +OPENSSL_sk_new, OPENSSL_sk_new_null, OPENSSL_sk_num, OPENSSL_sk_pop, +OPENSSL_sk_pop_free, OPENSSL_sk_push, OPENSSL_sk_reserve, OPENSSL_sk_set, +OPENSSL_sk_set_cmp_func, OPENSSL_sk_shift, OPENSSL_sk_sort, OPENSSL_sk_unshift, OPENSSL_sk_value, OPENSSL_sk_zero, -sk_TYPE_num, sk_TYPE_value, sk_TYPE_new, sk_TYPE_new_null, sk_TYPE_free, -sk_TYPE_zero, sk_TYPE_delete, sk_TYPE_delete_ptr, sk_TYPE_push, -sk_TYPE_unshift, sk_TYPE_pop, sk_TYPE_shift, sk_TYPE_pop_free, -sk_TYPE_insert, sk_TYPE_set, sk_TYPE_find, sk_TYPE_find_ex, sk_TYPE_sort, -sk_TYPE_is_sorted, sk_TYPE_dup, sk_TYPE_deep_copy, sk_TYPE_set_cmp_func - -stack container +sk_TYPE_num, sk_TYPE_value, sk_TYPE_new, sk_TYPE_new_null, +sk_TYPE_reserve, sk_TYPE_free, sk_TYPE_zero, sk_TYPE_delete, +sk_TYPE_delete_ptr, sk_TYPE_push, sk_TYPE_unshift, sk_TYPE_pop, +sk_TYPE_shift, sk_TYPE_pop_free, sk_TYPE_insert, sk_TYPE_set, +sk_TYPE_find, sk_TYPE_find_ex, sk_TYPE_sort, sk_TYPE_is_sorted, +sk_TYPE_dup, sk_TYPE_deep_copy, sk_TYPE_set_cmp_func - stack container =head1 SYNOPSIS @@ -37,6 +38,7 @@ stack container TYPE *sk_TYPE_value(const STACK_OF(TYPE) *sk, int idx); STACK_OF(TYPE) *sk_TYPE_new(sk_TYPE_compfunc compare); STACK_OF(TYPE) *sk_TYPE_new_null(void); + int sk_TYPE_reserve(STACK_OF(TYPE) *sk, size_t n); void sk_TYPE_free(const STACK_OF(TYPE) *sk); void sk_TYPE_zero(const STACK_OF(TYPE) *sk); TYPE *sk_TYPE_delete(STACK_OF(TYPE) *sk, int i); @@ -100,6 +102,12 @@ If B is B then no comparison function is used. sk_TYPE_new_null() allocates a new empty stack with no comparison function. +sk_TYPE_reserve() allocates additional memory in the B structure +such that the next B calls to sk_TYPE_insert(), sk_TYPE_push() +or sk_TYPE_unshift() will not fail or cause memory to be allocated +or reallocated. If B is zero, any excess space allocated in the +B structure is freed. On error B is unchanged. + sk_TYPE_set_cmp_func() sets the comparison function of B to B. The previous comparison function is returned or B if there was no previous comparison function. @@ -201,6 +209,9 @@ index is out of range. sk_TYPE_new() and sk_TYPE_new_null() return an empty stack or B if an error occurs. +sk_TYPE_reserve() returns B<1> on successful allocation of the required memory +or B<0> on error. + sk_TYPE_set_cmp_func() returns the old comparison function or B if there was no old comparison function. @@ -232,7 +243,7 @@ and was not a public API. =head1 COPYRIGHT -Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved. +Copyright 2000-2017 The OpenSSL Project Authors. All Rights Reserved. Licensed under the OpenSSL license (the "License"). You may not use this file except in compliance with the License. You can obtain a copy diff --git a/include/openssl/safestack.h b/include/openssl/safestack.h index 9fe733c24e..4241c4ff3b 100644 --- a/include/openssl/safestack.h +++ b/include/openssl/safestack.h @@ -1,5 +1,5 @@ /* - * Copyright 1999-2016 The OpenSSL Project Authors. All Rights Reserved. + * Copyright 1999-2017 The OpenSSL Project Authors. All Rights Reserved. * * Licensed under the OpenSSL license (the "License"). You may not use * this file except in compliance with the License. You can obtain a copy @@ -40,6 +40,10 @@ extern "C" { { \ return (STACK_OF(t1) *)OPENSSL_sk_new_null(); \ } \ + static ossl_inline int sk_##t1##_reserve(STACK_OF(t1) *sk, int n) \ + { \ + return OPENSSL_sk_reserve((OPENSSL_STACK *)sk, n); \ + } \ static ossl_inline void sk_##t1##_free(STACK_OF(t1) *sk) \ { \ OPENSSL_sk_free((OPENSSL_STACK *)sk); \ diff --git a/include/openssl/stack.h b/include/openssl/stack.h index 23ad3b89f9..aee763c196 100644 --- a/include/openssl/stack.h +++ b/include/openssl/stack.h @@ -1,5 +1,5 @@ /* - * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. + * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved. * * Licensed under the OpenSSL license (the "License"). You may not use * this file except in compliance with the License. You can obtain a copy @@ -27,9 +27,12 @@ void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data); OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc cmp); OPENSSL_STACK *OPENSSL_sk_new_null(void); +int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n); void OPENSSL_sk_free(OPENSSL_STACK *); void OPENSSL_sk_pop_free(OPENSSL_STACK *st, void (*func) (void *)); -OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *, OPENSSL_sk_copyfunc c, OPENSSL_sk_freefunc f); +OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *, + OPENSSL_sk_copyfunc c, + OPENSSL_sk_freefunc f); int OPENSSL_sk_insert(OPENSSL_STACK *sk, const void *data, int where); void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc); void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p); @@ -40,7 +43,8 @@ int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data); void *OPENSSL_sk_shift(OPENSSL_STACK *st); void *OPENSSL_sk_pop(OPENSSL_STACK *st); void OPENSSL_sk_zero(OPENSSL_STACK *st); -OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc cmp); +OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, + OPENSSL_sk_compfunc cmp); OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *st); void OPENSSL_sk_sort(OPENSSL_STACK *st); int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st); diff --git a/test/sanitytest.c b/test/sanitytest.c index 743c03b2d9..c1c51a2b9a 100644 --- a/test/sanitytest.c +++ b/test/sanitytest.c @@ -75,6 +75,16 @@ static int test_sanity_unsigned_convertion(void) return 1; } +static int test_sanity_range(void) +{ + /* This isn't possible to check using the framework functions */ + if (SIZE_MAX < INT_MAX) { + TEST_error("int must not be wider than size_t"); + return 0; + } + return 1; +} + int setup_tests(void) { ADD_TEST(test_sanity_null_zero); @@ -82,6 +92,7 @@ int setup_tests(void) ADD_TEST(test_sanity_twos_complement); ADD_TEST(test_sanity_sign); ADD_TEST(test_sanity_unsigned_convertion); + ADD_TEST(test_sanity_range); return 1; } diff --git a/test/stack_test.c b/test/stack_test.c index c0ec46a6bd..680f68d60e 100644 --- a/test/stack_test.c +++ b/test/stack_test.c @@ -50,7 +50,7 @@ static int int_compare(const int *const *a, const int *const *b) return 0; } -static int test_int_stack(void) +static int test_int_stack(int reserve) { static int v[] = { 1, 2, -4, 16, 999, 1, -173, 1, 9 }; static int notpresent = -1; @@ -84,6 +84,10 @@ static int test_int_stack(void) int i; int testresult = 0; + if (!TEST_ptr(s) + || (reserve > 0 && !TEST_true(sk_sint_reserve(s, 5 * reserve)))) + goto end; + /* Check push and num */ for (i = 0; i < n; i++) { if (!TEST_int_eq(sk_sint_num(s), i)) { @@ -167,7 +171,7 @@ static int uchar_compare(const unsigned char *const *a, return **a - (signed int)**b; } -static int test_uchar_stack(void) +static int test_uchar_stack(int reserve) { static const unsigned char v[] = { 1, 3, 7, 5, 255, 0 }; const int n = OSSL_NELEM(v); @@ -175,6 +179,10 @@ static int test_uchar_stack(void) int i; int testresult = 0; + if (!TEST_ptr(s) + || (reserve > 0 && !TEST_true(sk_uchar_reserve(s, 5 * reserve)))) + goto end; + /* unshift and num */ for (i = 0; i < n; i++) { if (!TEST_int_eq(sk_uchar_num(s), i)) { @@ -364,8 +372,8 @@ end: int setup_tests(void) { - ADD_TEST(test_int_stack); - ADD_TEST(test_uchar_stack); + ADD_ALL_TESTS(test_int_stack, 4); + ADD_ALL_TESTS(test_uchar_stack, 4); ADD_TEST(test_SS_stack); ADD_TEST(test_SU_stack); return 1; diff --git a/util/libcrypto.num b/util/libcrypto.num index 363059be4c..48e97ff135 100644 --- a/util/libcrypto.num +++ b/util/libcrypto.num @@ -4397,3 +4397,4 @@ EVP_PKEY_check 4340 1_1_1 EXIST::FUNCTION: EVP_PKEY_meth_set_check 4341 1_1_1 EXIST::FUNCTION: EVP_PKEY_meth_get_check 4342 1_1_1 EXIST::FUNCTION: EVP_PKEY_meth_remove 4343 1_1_1 EXIST::FUNCTION: +OPENSSL_sk_reserve 4344 1_1_1 EXIST::FUNCTION: