stack: increase the reallocation ratio
This change increases the reallocation ratio from 1.5 to 1.6.
#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;
}
