Add sparse array data type.

This commit adds a space and time efficient sparse array data structure.
The structure's raw API is wrapped by inline functions which provide type
safety.

Reviewed-by: Richard Levitte <levitte@openssl.org>
Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/8197)

4 files changed, 448 insertions, 2 deletions

diff --git a/crypto/README.sparse_array b/crypto/README.sparse_array
new file mode 100644
index 0000000000..947c34dbbe
--- /dev/null
+++ b/crypto/README.sparse_array
@@ -0,0 +1,155 @@
+The sparse_array.c file contains an implementation of a sparse array that
+attempts to be both space and time efficient.
+
+The sparse array is represented using a tree structure.  Each node in the
+tree contains a block of pointers to either the user supplied leaf values or
+to another node.
+
+There are a number of parameters used to define the block size:
+
+    OPENSSL_SA_BLOCK_BITS   Specifies the number of bits covered by each block
+    SA_BLOCK_MAX            Specifies the number of pointers in each block
+    SA_BLOCK_MASK           Specifies a bit mask to perform modulo block size
+    SA_BLOCK_MAX_LEVELS     Indicates the maximum possible height of the tree
+
+These constants are inter-related:
+    SA_BLOCK_MAX        = 2 ^ OPENSSL_SA_BLOCK_BITS
+    SA_BLOCK_MASK       = SA_BLOCK_MAX - 1
+    SA_BLOCK_MAX_LEVELS = number of bits in size_t divided by
+                          OPENSSL_SA_BLOCK_BITS rounded up to the next multiple
+                          of OPENSSL_SA_BLOCK_BITS
+
+OPENSSL_SA_BLOCK_BITS can be defined at compile time and this overrides the
+built in setting.
+
+As a space and performance optimisation, the height of the tree is usually
+less than the maximum possible height.  Only sufficient height is allocated to
+accommodate the largest index added to the data structure.
+
+The largest index used to add a value to the array determines the tree height:
+
+        +----------------------+---------------------+
+        | Largest Added Index  |   Height of Tree    |
+        +----------------------+---------------------+
+        | SA_BLOCK_MAX     - 1 |          1          |
+        | SA_BLOCK_MAX ^ 2 - 1 |          2          |
+        | SA_BLOCK_MAX ^ 3 - 1 |          3          |
+        | ...                  |          ...        |
+        | size_t max           | SA_BLOCK_MAX_LEVELS |
+        +----------------------+---------------------+
+
+The tree height is dynamically increased as needed based on additions.
+
+An empty tree is represented by a NULL root pointer.  Inserting a value at
+index 0 results in the allocation of a top level node full of null pointers
+except for the single pointer to the user's data (N = SA_BLOCK_MAX for
+breviety):
+
+        +----+
+        |Root|
+        |Node|
+        +-+--+
+          |
+          |
+          |
+          v
+        +-+-+---+---+---+---+
+        | 0 | 1 | 2 |...|N-1|
+        |   |nil|nil|...|nil|
+        +-+-+---+---+---+---+
+          |
+          |
+          |
+          v
+        +-+--+
+        |User|
+        |Data|
+        +----+
+    Index 0
+
+
+Inserting at element 2N+1 creates a new root node and pushes down the old root
+node.  It then creates a second second level node to hold the pointer to the
+user's new data:
+
+        +----+
+        |Root|
+        |Node|
+        +-+--+
+          |
+          |
+          |
+          v
+        +-+-+---+---+---+---+
+        | 0 | 1 | 2 |...|N-1|
+        |   |nil|   |...|nil|
+        +-+-+---+-+-+---+---+
+          |       |
+          |       +------------------+
+          |                          |
+          v                          v
+        +-+-+---+---+---+---+      +-+-+---+---+---+---+
+        | 0 | 1 | 2 |...|N-1|      | 0 | 1 | 2 |...|N-1|
+        |nil|   |nil|...|nil|      |nil|   |nil|...|nil|
+        +-+-+---+---+---+---+      +---+-+-+---+---+---+
+          |                              |
+          |                              |
+          |                              |
+          v                              v
+        +-+--+                         +-+--+
+        |User|                         |User|
+        |Data|                         |Data|
+        +----+                         +----+
+    Index 0                       Index 2N+1
+
+
+The nodes themselves are allocated in a sparse manner.  Only nodes which exist
+along a path from the root of the tree to an added leaf will be allocated.
+The complexity is hidden and nodes are allocated on an as needed basis.
+Because the data is expected to be sparse this doesn't result in a large waste
+of space.
+
+Values can be removed from the sparse array by setting their index position to
+NULL.  The data structure does not attempt to reclaim nodes or reduce the
+height of the tree on removal.  For example, now setting index 0 to NULL would
+result in:
+
+        +----+
+        |Root|
+        |Node|
+        +-+--+
+          |
+          |
+          |
+          v
+        +-+-+---+---+---+---+
+        | 0 | 1 | 2 |...|N-1|
+        |   |nil|   |...|nil|
+        +-+-+---+-+-+---+---+
+          |       |
+          |       +------------------+
+          |                          |
+          v                          v
+        +-+-+---+---+---+---+      +-+-+---+---+---+---+
+        | 0 | 1 | 2 |...|N-1|      | 0 | 1 | 2 |...|N-1|
+        |nil|nil|nil|...|nil|      |nil|   |nil|...|nil|
+        +---+---+---+---+---+      +---+-+-+---+---+---+
+                                         |
+                                         |
+                                         |
+                                         v
+                                       +-+--+
+                                       |User|
+                                       |Data|
+                                       +----+
+                                  Index 2N+1
+
+
+Accesses to elements in the sparse array take O(log n) time where n is the
+largest element.  The base of the logarithm is SA_BLOCK_MAX, so for moderately
+small indices (e.g. NIDs), single level (constant time) access is achievable.
+Space usage is O(minimum(m, n log(n)) where m is the number of elements in the
+array.
+
+Note: sparse arrays only include pointers to types.  Thus, SPARSE_ARRAY_OF(char)
+can be used to store a string.
diff --git a/crypto/build.info b/crypto/build.info
index 5e879ea9b4..3b6731534b 100644
--- a/crypto/build.info
+++ b/crypto/build.info
@@ -12,8 +12,8 @@ SOURCE[../libcrypto]=\
         cryptlib.c mem.c mem_dbg.c cversion.c ex_data.c cpt_err.c \
         ebcdic.c uid.c o_time.c o_str.c o_dir.c o_fopen.c ctype.c \
         threads_pthread.c threads_win.c threads_none.c getenv.c \
-        o_init.c o_fips.c mem_sec.c init.c {- $target{cpuid_asm_src} -} \
-        {- $target{uplink_aux_src} -}
+        o_init.c o_fips.c mem_sec.c init.c sparse_array.c \
+        {- $target{cpuid_asm_src} -} {- $target{uplink_aux_src} -}
 
 DEPEND[cversion.o]=buildinf.h
 GENERATE[buildinf.h]=../util/mkbuildinf.pl "$(CC) $(LIB_CFLAGS) $(CPPFLAGS_Q)" "$(PLATFORM)"
diff --git a/crypto/include/internal/sparse_array.h b/crypto/include/internal/sparse_array.h
new file mode 100644
index 0000000000..bf0a9966af
--- /dev/null
+++ b/crypto/include/internal/sparse_array.h
@@ -0,0 +1,78 @@
+/*
+ * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the Apache License 2.0 (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
+ */
+
+#ifndef HEADER_SPARSE_ARRAY_H
+# define HEADER_SPARSE_ARRAY_H
+
+# ifdef __cplusplus
+extern "C" {
+# endif
+
+# define SPARSE_ARRAY_OF(type) struct sparse_array_st_ ## type
+
+# define DEFINE_SPARSE_ARRAY_OF(type) \
+    SPARSE_ARRAY_OF(type); \
+    static ossl_inline SPARSE_ARRAY_OF(type) * \
+        ossl_sa_##type##_new(void) \
+    { \
+        return (SPARSE_ARRAY_OF(type) *)OPENSSL_SA_new(); \
+    } \
+    static ossl_inline void ossl_sa_##type##_free(SPARSE_ARRAY_OF(type) *sa) \
+    { \
+        OPENSSL_SA_free((OPENSSL_SA *)sa); \
+    } \
+    static ossl_inline void ossl_sa_##type##_free_leaves(SPARSE_ARRAY_OF(type) *sa) \
+    { \
+        OPENSSL_SA_free_leaves((OPENSSL_SA *)sa); \
+    } \
+    static ossl_inline size_t ossl_sa_##type##_num(const SPARSE_ARRAY_OF(type) *sa) \
+    { \
+        return OPENSSL_SA_num((OPENSSL_SA *)sa); \
+    } \
+    static ossl_inline void ossl_sa_##type##_doall(const SPARSE_ARRAY_OF(type) *sa, \
+                                                   void (*leaf)(type *)) \
+    { \
+        OPENSSL_SA_doall((OPENSSL_SA *)sa, (void (*)(void *))leaf); \
+    } \
+    static ossl_inline void ossl_sa_##type##_doall_arg(const SPARSE_ARRAY_OF(type) *sa, \
+                                                       void (*leaf)(type *, \
+						                    void *),\
+                                                       void *arg) \
+    { \
+        OPENSSL_SA_doall_arg((OPENSSL_SA *)sa, (void (*)(void *, void *))leaf, \
+                             arg); \
+    } \
+    static ossl_inline type *ossl_sa_##type##_get(const SPARSE_ARRAY_OF(type) *sa, \
+                                                  size_t n) \
+    { \
+        return (type *)OPENSSL_SA_get((OPENSSL_SA *)sa, n); \
+    } \
+    static ossl_inline int ossl_sa_##type##_set(SPARSE_ARRAY_OF(type) *sa, \
+                                                size_t n, type *val) \
+    { \
+        return OPENSSL_SA_set((OPENSSL_SA *)sa, n, (void *)val); \
+    } \
+    SPARSE_ARRAY_OF(type)
+
+typedef struct sparse_array_st OPENSSL_SA;
+OPENSSL_SA *OPENSSL_SA_new(void);
+void OPENSSL_SA_free(OPENSSL_SA *sa);
+void OPENSSL_SA_free_leaves(OPENSSL_SA *sa);
+size_t OPENSSL_SA_num(const OPENSSL_SA *sa);
+void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(void *));
+void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa, void (*leaf)(void *, void *),
+                          void *);
+void *OPENSSL_SA_get(const OPENSSL_SA *sa, size_t n);
+int OPENSSL_SA_set(OPENSSL_SA *sa, size_t n, void *val);
+
+# ifdef  __cplusplus
+}
+# endif
+#endif
diff --git a/crypto/sparse_array.c b/crypto/sparse_array.c
new file mode 100644
index 0000000000..8b56b257cf
--- /dev/null
+++ b/crypto/sparse_array.c
@@ -0,0 +1,213 @@
+/*
+ * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
+ *
+ * Licensed under the Apache License 2.0 (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
+ */
+
+#include <openssl/crypto.h>
+#include "internal/sparse_array.h"
+
+/*
+ * How many bits are used to index each level in the tree structre?
+ * This setting determines the number of pointers stored in each node of the
+ * tree used to represent the sparse array.  Having more pointers reduces the
+ * depth of the tree but potentially wastes more memory.  That is, this is a
+ * direct space versus time tradeoff.
+ *
+ * The large memory model uses twelve bits which means that the are 4096
+ * pointers in each tree node.  This is more than sufficient to hold the
+ * largest defined NID (as of Feb 2019).  This means that using a NID to
+ * index a sparse array becomes a constant time single array look up.
+ *
+ * The small memory model uses four bits which means the tree nodes contain
+ * sixteen pointers.  This reduces the amount of unused space significantly
+ * at a cost in time.
+ *
+ * The library builder is also permitted to define other sizes in the closed
+ * interval [2, sizeof(size_t) * 8].
+ */
+#ifndef OPENSSL_SA_BLOCK_BITS
+# ifdef OPENSSL_SMALL_FOOTPRINT
+#  define OPENSSL_SA_BLOCK_BITS           4
+# else
+#  define OPENSSL_SA_BLOCK_BITS           12
+# endif
+#elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > BN_BITS2
+# error OPENSSL_SA_BLOCK_BITS is out of range
+#endif
+
+/*
+ * From the number of bits, work out:
+ *    the number of pointers in a tree node;
+ *    a bit mask to quickly extra an index and
+ *    the maximum depth of the tree structure.
+  */
+#define SA_BLOCK_MAX            (1 << OPENSSL_SA_BLOCK_BITS)
+#define SA_BLOCK_MASK           (SA_BLOCK_MAX - 1)
+#define SA_BLOCK_MAX_LEVELS     (((int)sizeof(size_t) * 8 \
+                                  + OPENSSL_SA_BLOCK_BITS - 1) \
+                                 / OPENSSL_SA_BLOCK_BITS)
+
+struct sparse_array_st {
+    int levels;
+    size_t top;
+    size_t nelem;
+    void **nodes;
+};
+
+OPENSSL_SA *OPENSSL_SA_new(void)
+{
+    OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res));
+
+    return res;
+}
+
+static void sa_doall(const OPENSSL_SA *sa, void (*node)(void **),
+                     void (*leaf)(void *, void *), void *arg)
+{
+    int i[SA_BLOCK_MAX_LEVELS];
+    void *nodes[SA_BLOCK_MAX_LEVELS];
+    int l = 0;
+
+    i[0] = 0;
+    nodes[0] = sa->nodes;
+    while (l >= 0) {
+        const int n = i[l];
+        void ** const p = nodes[l];
+
+        if (n >= SA_BLOCK_MAX) {
+            if (p != NULL && node != NULL)
+                (*node)(p);
+            l--;
+        } else {
+            i[l] = n + 1;
+            if (p != NULL && p[n] != NULL) {
+                if (l < sa->levels - 1) {
+                    i[++l] = 0;
+                    nodes[l] = p[n];
+                } else if (leaf != NULL) {
+                    (*leaf)(p[n], arg);
+                }
+            }
+        }
+    }
+}
+
+static void sa_free_node(void **p)
+{
+    OPENSSL_free(p);
+}
+
+static void sa_free_leaf(void *p, void *arg)
+{
+    OPENSSL_free(p);
+}
+
+void OPENSSL_SA_free(OPENSSL_SA *sa)
+{
+    sa_doall(sa, &sa_free_node, NULL, NULL);
+    OPENSSL_free(sa);
+}
+
+void OPENSSL_SA_free_leaves(OPENSSL_SA *sa)
+{
+    sa_doall(sa, &sa_free_node, &sa_free_leaf, NULL);
+    OPENSSL_free(sa);
+}
+
+/* Wrap this in a structure to avoid compiler warnings */
+struct trampoline_st {
+    void (*func)(void *);
+};
+
+static void trampoline(void *l, void *arg)
+{
+    ((const struct trampoline_st *)arg)->func(l);
+}
+
+void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(void *))
+{
+    struct trampoline_st tramp;
+
+    tramp.func = leaf;
+    if (sa != NULL)
+        sa_doall(sa, NULL, &trampoline, &tramp);
+}
+
+void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa, void (*leaf)(void *, void *),
+                          void *arg)
+{
+    if (sa != NULL)
+        sa_doall(sa, NULL, leaf, arg);
+}
+
+size_t OPENSSL_SA_num(const OPENSSL_SA *sa)
+{
+    return sa == NULL ? 0 : sa->nelem;
+}
+
+void *OPENSSL_SA_get(const OPENSSL_SA *sa, size_t n)
+{
+    int level;
+    void **p, *r = NULL;
+
+    if (sa == NULL)
+        return NULL;
+
+    if (n <= sa->top) {
+        p = sa->nodes;
+        for (level = sa->levels - 1; p != NULL && level > 0; level--)
+            p = (void **)p[(n >> (OPENSSL_SA_BLOCK_BITS * level))
+                           & SA_BLOCK_MASK];
+        r = p == NULL ? NULL : p[n & SA_BLOCK_MASK];
+    }
+    return r;
+}
+
+static ossl_inline void **alloc_node(void)
+{
+    return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *));
+}
+
+int OPENSSL_SA_set(OPENSSL_SA *sa, size_t posn, void *val)
+{
+    int i, level = 1;
+    size_t n = posn;
+    void **p;
+
+    if (sa == NULL)
+        return 0;
+
+    for (level = 1; level <= SA_BLOCK_MAX_LEVELS; level++)
+        if ((n >>= OPENSSL_SA_BLOCK_BITS) == 0)
+            break;
+
+    for (;sa->levels < level; sa->levels++) {
+        p = alloc_node();
+        if (p == NULL)
+            return 0;
+        p[0] = sa->nodes;
+        sa->nodes = p;
+    }
+    if (sa->top < posn)
+        sa->top = posn;
+
+    p = sa->nodes;
+    for (level = sa->levels - 1; level > 0; level--) {
+        i = (posn >> (OPENSSL_SA_BLOCK_BITS * level)) & SA_BLOCK_MASK;
+        if (p[i] == NULL && (p[i] = alloc_node()) == NULL)
+            return 0;
+        p = p[i];
+    }
+    p += posn & SA_BLOCK_MASK;
+    if (val == NULL && *p != NULL)
+        sa->nelem--;
+    else if (val != NULL && *p == NULL)
+        sa->nelem++;
+    *p = val;
+    return 1;
+}