diff options
author | Pauli <pauli@openssl.org> | 2021-11-10 15:40:00 +1000 |
---|---|---|
committer | Pauli <pauli@openssl.org> | 2021-11-12 19:49:46 +1000 |
commit | 8347bfa04fc62dcf684b8a43905709fa18f6a3b1 (patch) | |
tree | ea2001761fca6a1dbd26c9d6c37f9aa535d8952c /crypto/stack | |
parent | bc4efcb0d0740467f1b8b536677a2886c2445c80 (diff) |
stack: increase the reallocation ratio
This change increases the reallocation ratio from 1.5 to 1.6.
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/16930)
Diffstat (limited to 'crypto/stack')
-rw-r--r-- | crypto/stack/stack.c | 30 |
1 files changed, 18 insertions, 12 deletions
diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c index 3d8e4746cf..c06af85e33 100644 --- a/crypto/stack/stack.c +++ b/crypto/stack/stack.c @@ -10,10 +10,13 @@ #include <stdio.h> #include "internal/cryptlib.h" #include "internal/numbers.h" +#include "internal/safe_math.h" #include <openssl/stack.h> #include <errno.h> #include <openssl/e_os2.h> /* For ossl_inline */ +OSSL_SAFE_MATH_SIGNED(int, int) + /* * The initial number of nodes in the array. */ @@ -138,32 +141,35 @@ OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c) /* * Calculate the array growth based on the target size. * - * The growth fraction is a rational number and is defined by a numerator + * The growth factor 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 simplicity of calculation and overflow checking. - * Another option 8/5 = 1.6 allows for slightly faster growth, although safe - * computation is more difficult. + * Considering only the Fibonacci ratios less than the golden ratio, the + * number of steps from the minimum allocation to integer overflow is: + * factor decimal growths + * 3/2 1.5 51 + * 8/5 1.6 45 + * 21/13 1.615... 44 * - * 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. + * All larger factors have the same number of growths. * - * Do not call it with |current| lower than 2, or it will infinitely loop. + * 3/2 and 8/5 have nice power of two shifts, so seem like a good choice. */ static ossl_inline int compute_growth(int target, int current) { - const int limit = (max_nodes / 3) * 2 + (max_nodes % 3 ? 1 : 0); + int err = 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; + current = safe_muldiv_int(current, 8, 5, &err); + if (err) + return 0; + if (current > max_nodes) + current = max_nodes; } return current; } |