1 files changed, 269 insertions, 240 deletions

diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c
index fa50083e22b3..975515db5972 100644
--- a/crypto/stack/stack.c
+++ b/crypto/stack/stack.c
@@ -1,86 +1,39 @@
-/* crypto/stack/stack.c */
-/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
- * All rights reserved.
+/*
+ * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
  *
- * This package is an SSL implementation written
- * by Eric Young (eay@cryptsoft.com).
- * The implementation was written so as to conform with Netscapes SSL.
- *
- * This library is free for commercial and non-commercial use as long as
- * the following conditions are aheared to.  The following conditions
- * apply to all code found in this distribution, be it the RC4, RSA,
- * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
- * included with this distribution is covered by the same copyright terms
- * except that the holder is Tim Hudson (tjh@cryptsoft.com).
- *
- * Copyright remains Eric Young's, and as such any Copyright notices in
- * the code are not to be removed.
- * If this package is used in a product, Eric Young should be given attribution
- * as the author of the parts of the library used.
- * This can be in the form of a textual message at program startup or
- * in documentation (online or textual) provided with the package.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *    "This product includes cryptographic software written by
- *     Eric Young (eay@cryptsoft.com)"
- *    The word 'cryptographic' can be left out if the rouines from the library
- *    being used are not cryptographic related :-).
- * 4. If you include any Windows specific code (or a derivative thereof) from
- *    the apps directory (application code) you must include an acknowledgement:
- *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
- *
- * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- * The licence and distribution terms for any publically available version or
- * derivative of this code cannot be changed.  i.e. this code cannot simply be
- * copied and put under another distribution licence
- * [including the GNU Public Licence.]
+ * Licensed under the OpenSSL license (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
  */
 
-/*-
- * Code for stacks
- * Author - Eric Young v 1.0
- * 1.2 eay 12-Mar-97 -  Modified sk_find so that it _DOES_ return the
- *                      lowest index for the searched item.
- *
- * 1.1 eay - Take from netdb and added to SSLeay
- *
- * 1.0 eay - First version 29/07/92
- */
 #include <stdio.h>
-#include "cryptlib.h"
+#include "internal/cryptlib.h"
+#include "internal/numbers.h"
 #include <openssl/stack.h>
 #include <openssl/objects.h>
-
-#undef MIN_NODES
-#define MIN_NODES       4
-
-const char STACK_version[] = "Stack" OPENSSL_VERSION_PTEXT;
-
 #include <errno.h>
+#include <openssl/e_os2.h>      /* For ossl_inline */
 
-int (*sk_set_cmp_func(_STACK *sk, int (*c) (const void *, const void *)))
- (const void *, const void *) {
-    int (*old) (const void *, const void *) = sk->comp;
+/*
+ * 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 void **data;
+    int sorted;
+    int num_alloc;
+    OPENSSL_sk_compfunc comp;
+};
+
+OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc c)
+{
+    OPENSSL_sk_compfunc old = sk->comp;
 
     if (sk->comp != c)
         sk->sorted = 0;
@@ -89,51 +42,62 @@ int (*sk_set_cmp_func(_STACK *sk, int (*c) (const void *, const void *)))
     return old;
 }
 
-_STACK *sk_dup(_STACK *sk)
+OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
 {
-    _STACK *ret;
-    char **s;
+    OPENSSL_STACK *ret;
 
-    if ((ret = sk_new(sk->comp)) == NULL)
-        goto err;
-    s = (char **)OPENSSL_realloc((char *)ret->data,
-                                 (unsigned int)sizeof(char *) *
-                                 sk->num_alloc);
-    if (s == NULL)
+    if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
+        CRYPTOerr(CRYPTO_F_OPENSSL_SK_DUP, ERR_R_MALLOC_FAILURE);
+        return NULL;
+    }
+
+    /* 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;
-    ret->data = s;
-
-    ret->num = sk->num;
-    memcpy(ret->data, sk->data, sizeof(char *) * sk->num);
-    ret->sorted = sk->sorted;
-    ret->num_alloc = sk->num_alloc;
-    ret->comp = sk->comp;
-    return (ret);
+    memcpy(ret->data, sk->data, sizeof(void *) * sk->num);
+    return ret;
  err:
-    if (ret)
-        sk_free(ret);
-    return (NULL);
+    OPENSSL_sk_free(ret);
+    return NULL;
 }
 
-_STACK *sk_deep_copy(_STACK *sk, void *(*copy_func) (void *),
-                     void (*free_func) (void *))
+OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,
+                             OPENSSL_sk_copyfunc copy_func,
+                             OPENSSL_sk_freefunc free_func)
 {
-    _STACK *ret;
+    OPENSSL_STACK *ret;
     int i;
 
-    if ((ret = OPENSSL_malloc(sizeof(_STACK))) == NULL)
+    if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
+        CRYPTOerr(CRYPTO_F_OPENSSL_SK_DEEP_COPY, ERR_R_MALLOC_FAILURE);
+        return NULL;
+    }
+
+    /* direct structure assignment */
+    *ret = *sk;
+
+    if (sk->num == 0) {
+        /* postpone |ret| data allocation */
+        ret->data = NULL;
+        ret->num_alloc = 0;
         return ret;
-    ret->comp = sk->comp;
-    ret->sorted = sk->sorted;
-    ret->num = sk->num;
-    ret->num_alloc = sk->num > MIN_NODES ? sk->num : MIN_NODES;
-    ret->data = OPENSSL_malloc(sizeof(char *) * ret->num_alloc);
+    }
+
+    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);
         return NULL;
     }
-    for (i = 0; i < ret->num_alloc; i++)
-        ret->data[i] = NULL;
 
     for (i = 0; i < ret->num; ++i) {
         if (sk->data[i] == NULL)
@@ -141,182 +105,259 @@ _STACK *sk_deep_copy(_STACK *sk, void *(*copy_func) (void *),
         if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
             while (--i >= 0)
                 if (ret->data[i] != NULL)
-                    free_func(ret->data[i]);
-            sk_free(ret);
+                    free_func((void *)ret->data[i]);
+            OPENSSL_sk_free(ret);
             return NULL;
         }
     }
     return ret;
 }
 
-_STACK *sk_new_null(void)
+OPENSSL_STACK *OPENSSL_sk_new_null(void)
 {
-    return sk_new((int (*)(const void *, const void *))0);
+    return OPENSSL_sk_new_reserve(NULL, 0);
 }
 
-_STACK *sk_new(int (*c) (const void *, const void *))
+OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
 {
-    _STACK *ret;
-    int i;
+    return OPENSSL_sk_new_reserve(c, 0);
+}
 
-    if ((ret = OPENSSL_malloc(sizeof(_STACK))) == NULL)
-        goto err;
-    if ((ret->data = OPENSSL_malloc(sizeof(char *) * MIN_NODES)) == NULL)
-        goto err;
-    for (i = 0; i < MIN_NODES; i++)
-        ret->data[i] = NULL;
-    ret->comp = c;
-    ret->num_alloc = MIN_NODES;
-    ret->num = 0;
-    ret->sorted = 0;
-    return (ret);
- err:
-    if (ret)
-        OPENSSL_free(ret);
-    return (NULL);
+/*
+ * Calculate the array growth based on the target size.
+ *
+ * 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 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)
+{
+    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;
 }
 
-int sk_insert(_STACK *st, void *data, int loc)
+/* internal STACK storage allocation */
+static int sk_reserve(OPENSSL_STACK *st, int n, int exact)
 {
-    char **s;
+    const void **tmpdata;
+    int num_alloc;
 
-    if (st == NULL)
+    /* Check to see the reservation isn't exceeding the hard limit */
+    if (n > max_nodes - st->num)
         return 0;
-    if (st->num_alloc <= st->num + 1) {
-        s = OPENSSL_realloc((char *)st->data,
-                            (unsigned int)sizeof(char *) * st->num_alloc * 2);
-        if (s == NULL)
-            return (0);
-        st->data = s;
-        st->num_alloc *= 2;
+
+    /* Figure out the new size */
+    num_alloc = st->num + n;
+    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|.
+         */
+        if ((st->data = OPENSSL_zalloc(sizeof(void *) * num_alloc)) == NULL) {
+            CRYPTOerr(CRYPTO_F_SK_RESERVE, ERR_R_MALLOC_FAILURE);
+            return 0;
+        }
+        st->num_alloc = num_alloc;
+        return 1;
+    }
+
+    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;
+    } else if (num_alloc == st->num_alloc) {
+        return 1;
     }
-    if ((loc >= (int)st->num) || (loc < 0))
+
+    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;
+}
+
+OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n)
+{
+    OPENSSL_STACK *st = OPENSSL_zalloc(sizeof(OPENSSL_STACK));
+
+    if (st == NULL)
+        return NULL;
+
+    st->comp = c;
+
+    if (n <= 0)
+        return st;
+
+    if (!sk_reserve(st, n, 1)) {
+        OPENSSL_sk_free(st);
+        return NULL;
+    }
+
+    return st;
+}
+
+int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n)
+{
+    if (st == NULL)
+        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 == max_nodes)
+        return 0;
+
+    if (!sk_reserve(st, 1, 0))
+        return 0;
+
+    if ((loc >= st->num) || (loc < 0)) {
         st->data[st->num] = data;
-    else {
-        int i;
-        char **f, **t;
-
-        f = st->data;
-        t = &(st->data[1]);
-        for (i = st->num; i >= loc; i--)
-            t[i] = f[i];
-
-#ifdef undef                    /* no memmove on sunos :-( */
-        memmove(&(st->data[loc + 1]),
-                &(st->data[loc]), sizeof(char *) * (st->num - loc));
-#endif
+    } else {
+        memmove(&st->data[loc + 1], &st->data[loc],
+                sizeof(st->data[0]) * (st->num - loc));
         st->data[loc] = data;
     }
     st->num++;
     st->sorted = 0;
-    return (st->num);
+    return st->num;
 }
 
-void *sk_delete_ptr(_STACK *st, void *p)
+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 (sk_delete(st, i));
-    return (NULL);
+            return internal_delete(st, i);
+    return NULL;
 }
 
-void *sk_delete(_STACK *st, int loc)
+void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
 {
-    char *ret;
-    int i, j;
-
-    if (!st || (loc < 0) || (loc >= st->num))
+    if (st == NULL || loc < 0 || loc >= st->num)
         return NULL;
 
-    ret = st->data[loc];
-    if (loc != st->num - 1) {
-        j = st->num - 1;
-        for (i = loc; i < j; i++)
-            st->data[i] = st->data[i + 1];
-        /*
-         * In theory memcpy is not safe for this memcpy( &(st->data[loc]),
-         * &(st->data[loc+1]), sizeof(char *)*(st->num-loc-1));
-         */
-    }
-    st->num--;
-    return (ret);
+    return internal_delete(st, loc);
 }
 
-static int internal_find(_STACK *st, void *data, int ret_val_options)
+static int internal_find(OPENSSL_STACK *st, const void *data,
+                         int ret_val_options)
 {
-    const void *const *r;
+    const void *r;
     int i;
 
-    if (st == NULL)
+    if (st == NULL || st->num == 0)
         return -1;
 
     if (st->comp == NULL) {
         for (i = 0; i < st->num; i++)
             if (st->data[i] == data)
-                return (i);
-        return (-1);
+                return i;
+        return -1;
+    }
+
+    if (!st->sorted) {
+        if (st->num > 1)
+            qsort(st->data, st->num, sizeof(void *), st->comp);
+        st->sorted = 1; /* empty or single-element stack is considered sorted */
     }
-    sk_sort(st);
     if (data == NULL)
-        return (-1);
+        return -1;
     r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,
                         ret_val_options);
-    if (r == NULL)
-        return (-1);
-    return (int)((char **)r - st->data);
+
+    return r == NULL ? -1 : (int)((const void **)r - st->data);
 }
 
-int sk_find(_STACK *st, void *data)
+int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
 {
     return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
 }
 
-int sk_find_ex(_STACK *st, void *data)
+int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
 {
     return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
 }
 
-int sk_push(_STACK *st, void *data)
+int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data)
 {
-    return (sk_insert(st, data, st->num));
+    if (st == NULL)
+        return -1;
+    return OPENSSL_sk_insert(st, data, st->num);
 }
 
-int sk_unshift(_STACK *st, void *data)
+int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data)
 {
-    return (sk_insert(st, data, 0));
+    return OPENSSL_sk_insert(st, data, 0);
 }
 
-void *sk_shift(_STACK *st)
+void *OPENSSL_sk_shift(OPENSSL_STACK *st)
 {
-    if (st == NULL)
-        return (NULL);
-    if (st->num <= 0)
-        return (NULL);
-    return (sk_delete(st, 0));
+    if (st == NULL || st->num == 0)
+        return NULL;
+    return internal_delete(st, 0);
 }
 
-void *sk_pop(_STACK *st)
+void *OPENSSL_sk_pop(OPENSSL_STACK *st)
 {
-    if (st == NULL)
-        return (NULL);
-    if (st->num <= 0)
-        return (NULL);
-    return (sk_delete(st, st->num - 1));
+    if (st == NULL || st->num == 0)
+        return NULL;
+    return internal_delete(st, st->num - 1);
 }
 
-void sk_zero(_STACK *st)
+void OPENSSL_sk_zero(OPENSSL_STACK *st)
 {
-    if (st == NULL)
-        return;
-    if (st->num <= 0)
+    if (st == NULL || st->num == 0)
         return;
-    memset((char *)st->data, 0, sizeof(*st->data) * st->num);
+    memset(st->data, 0, sizeof(*st->data) * st->num);
     st->num = 0;
 }
 
-void sk_pop_free(_STACK *st, void (*func) (void *))
+void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
 {
     int i;
 
@@ -324,61 +365,49 @@ void sk_pop_free(_STACK *st, void (*func) (void *))
         return;
     for (i = 0; i < st->num; i++)
         if (st->data[i] != NULL)
-            func(st->data[i]);
-    sk_free(st);
+            func((char *)st->data[i]);
+    OPENSSL_sk_free(st);
 }
 
-void sk_free(_STACK *st)
+void OPENSSL_sk_free(OPENSSL_STACK *st)
 {
     if (st == NULL)
         return;
-    if (st->data != NULL)
-        OPENSSL_free(st->data);
+    OPENSSL_free(st->data);
     OPENSSL_free(st);
 }
 
-int sk_num(const _STACK *st)
+int OPENSSL_sk_num(const OPENSSL_STACK *st)
 {
-    if (st == NULL)
-        return -1;
-    return st->num;
+    return st == NULL ? -1 : st->num;
 }
 
-void *sk_value(const _STACK *st, int i)
+void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
 {
-    if (!st || (i < 0) || (i >= st->num))
+    if (st == NULL || i < 0 || i >= st->num)
         return NULL;
-    return st->data[i];
+    return (void *)st->data[i];
 }
 
-void *sk_set(_STACK *st, int i, void *value)
+void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data)
 {
-    if (!st || (i < 0) || (i >= st->num))
+    if (st == NULL || i < 0 || i >= st->num)
         return NULL;
-    return (st->data[i] = value);
+    st->data[i] = data;
+    st->sorted = 0;
+    return (void *)st->data[i];
 }
 
-void sk_sort(_STACK *st)
+void OPENSSL_sk_sort(OPENSSL_STACK *st)
 {
-    if (st && !st->sorted && st->comp != NULL) {
-        int (*comp_func) (const void *, const void *);
-
-        /*
-         * same comment as in sk_find ... previously st->comp was declared as
-         * a (void*,void*) callback type, but this made the population of the
-         * callback pointer illogical - our callbacks compare type** with
-         * type**, so we leave the casting until absolutely necessary (ie.
-         * "now").
-         */
-        comp_func = (int (*)(const void *, const void *))(st->comp);
-        qsort(st->data, st->num, sizeof(char *), comp_func);
-        st->sorted = 1;
+    if (st != NULL && !st->sorted && st->comp != NULL) {
+        if (st->num > 1)
+            qsort(st->data, st->num, sizeof(void *), st->comp);
+        st->sorted = 1; /* empty or single-element stack is considered sorted */
     }
 }
 
-int sk_is_sorted(const _STACK *st)
+int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
 {
-    if (!st)
-        return 1;
-    return st->sorted;
+    return st == NULL ? 1 : st->sorted;
 }