crypto/sparse_array.c

   1 /*
   2  * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
   4  *
   5  * Licensed under the Apache License 2.0 (the "License").  You may not use
   6  * this file except in compliance with the License.  You can obtain a copy
   7  * in the file LICENSE in the source distribution or at
   8  * https://www.openssl.org/source/license.html
   9  */
  10
  11 #include <openssl/crypto.h>
  12 #include <openssl/bn.h>
  13 #include "internal/sparse_array.h"
  14
  15 /*
  16  * How many bits are used to index each level in the tree structure?
  17  * This setting determines the number of pointers stored in each node of the
  18  * tree used to represent the sparse array.  Having more pointers reduces the
  19  * depth of the tree but potentially wastes more memory.  That is, this is a
  20  * direct space versus time tradeoff.
  21  *
  22  * The large memory model uses twelve bits which means that the are 4096
  23  * pointers in each tree node.  This is more than sufficient to hold the
  24  * largest defined NID (as of Feb 2019).  This means that using a NID to
  25  * index a sparse array becomes a constant time single array look up.
  26  *
  27  * The small memory model uses four bits which means the tree nodes contain
  28  * sixteen pointers.  This reduces the amount of unused space significantly
  29  * at a cost in time.
  30  *
  31  * The library builder is also permitted to define other sizes in the closed
  32  * interval [2, sizeof(ossl_uintmax_t) * 8].
  33  */
  34 #ifndef OPENSSL_SA_BLOCK_BITS
  35 # ifdef OPENSSL_SMALL_FOOTPRINT
  36 #  define OPENSSL_SA_BLOCK_BITS           4
  37 # else
  38 #  define OPENSSL_SA_BLOCK_BITS           12
  39 # endif
  40 #elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > (BN_BITS2 - 1)
  41 # error OPENSSL_SA_BLOCK_BITS is out of range
  42 #endif
  43
  44 /*
  45  * From the number of bits, work out:
  46  *    the number of pointers in a tree node;
  47  *    a bit mask to quickly extract an index and
  48  *    the maximum depth of the tree structure.
  49   */
  50 #define SA_BLOCK_MAX            (1 << OPENSSL_SA_BLOCK_BITS)
  51 #define SA_BLOCK_MASK           (SA_BLOCK_MAX - 1)
  52 #define SA_BLOCK_MAX_LEVELS     (((int)sizeof(ossl_uintmax_t) * 8 \
  53                                   + OPENSSL_SA_BLOCK_BITS - 1) \
  54                                  / OPENSSL_SA_BLOCK_BITS)
  55
  56 struct sparse_array_st {
  57     int levels;
  58     ossl_uintmax_t top;
  59     size_t nelem;
  60     void **nodes;
  61 };
  62
  63 OPENSSL_SA *OPENSSL_SA_new(void)
  64 {
  65     OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res));
  66
  67     return res;
  68 }
  69
  70 static void sa_doall(const OPENSSL_SA *sa, void (*node)(void **),
  71                      void (*leaf)(ossl_uintmax_t, void *, void *), void *arg)
  72 {
  73     int i[SA_BLOCK_MAX_LEVELS];
  74     void *nodes[SA_BLOCK_MAX_LEVELS];
  75     ossl_uintmax_t idx = 0;
  76     int l = 0;
  77
  78     i[0] = 0;
  79     nodes[0] = sa->nodes;
  80     while (l >= 0) {
  81         const int n = i[l];
  82         void ** const p = nodes[l];
  83
  84         if (n >= SA_BLOCK_MAX) {
  85             if (p != NULL && node != NULL)
  86                 (*node)(p);
  87             l--;
  88             idx >>= OPENSSL_SA_BLOCK_BITS;
  89         } else {
  90             i[l] = n + 1;
  91             if (p != NULL && p[n] != NULL) {
  92                 idx = (idx & ~SA_BLOCK_MASK) | n;
  93                 if (l < sa->levels - 1) {
  94                     i[++l] = 0;
  95                     nodes[l] = p[n];
  96                     idx <<= OPENSSL_SA_BLOCK_BITS;
  97                 } else if (leaf != NULL) {
  98                     (*leaf)(idx, p[n], arg);
  99                 }
 100             }
 101         }
 102     }
 103 }
 104
 105 static void sa_free_node(void **p)
 106 {
 107     OPENSSL_free(p);
 108 }
 109
 110 static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg)
 111 {
 112     OPENSSL_free(p);
 113 }
 114
 115 void OPENSSL_SA_free(OPENSSL_SA *sa)
 116 {
 117     sa_doall(sa, &sa_free_node, NULL, NULL);
 118     OPENSSL_free(sa);
 119 }
 120
 121 void OPENSSL_SA_free_leaves(OPENSSL_SA *sa)
 122 {
 123     sa_doall(sa, &sa_free_node, &sa_free_leaf, NULL);
 124     OPENSSL_free(sa);
 125 }
 126
 127 /* Wrap this in a structure to avoid compiler warnings */
 128 struct trampoline_st {
 129     void (*func)(ossl_uintmax_t, void *);
 130 };
 131
 132 static void trampoline(ossl_uintmax_t n, void *l, void *arg)
 133 {
 134     ((const struct trampoline_st *)arg)->func(n, l);
 135 }
 136
 137 void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t,
 138                                                          void *))
 139 {
 140     struct trampoline_st tramp;
 141
 142     tramp.func = leaf;
 143     if (sa != NULL)
 144         sa_doall(sa, NULL, &trampoline, &tramp);
 145 }
 146
 147 void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa,
 148                           void (*leaf)(ossl_uintmax_t, void *, void *),
 149                           void *arg)
 150 {
 151     if (sa != NULL)
 152         sa_doall(sa, NULL, leaf, arg);
 153 }
 154
 155 size_t OPENSSL_SA_num(const OPENSSL_SA *sa)
 156 {
 157     return sa == NULL ? 0 : sa->nelem;
 158 }
 159
 160 void *OPENSSL_SA_get(const OPENSSL_SA *sa, ossl_uintmax_t n)
 161 {
 162     int level;
 163     void **p, *r = NULL;
 164
 165     if (sa == NULL)
 166         return NULL;
 167
 168     if (n <= sa->top) {
 169         p = sa->nodes;
 170         for (level = sa->levels - 1; p != NULL && level > 0; level--)
 171             p = (void **)p[(n >> (OPENSSL_SA_BLOCK_BITS * level))
 172                            & SA_BLOCK_MASK];
 173         r = p == NULL ? NULL : p[n & SA_BLOCK_MASK];
 174     }
 175     return r;
 176 }
 177
 178 static ossl_inline void **alloc_node(void)
 179 {
 180     return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *));
 181 }
 182
 183 int OPENSSL_SA_set(OPENSSL_SA *sa, ossl_uintmax_t posn, void *val)
 184 {
 185     int i, level = 1;
 186     ossl_uintmax_t n = posn;
 187     void **p;
 188
 189     if (sa == NULL)
 190         return 0;
 191
 192     for (level = 1; level < SA_BLOCK_MAX_LEVELS; level++)
 193         if ((n >>= OPENSSL_SA_BLOCK_BITS) == 0)
 194             break;
 195
 196     for (;sa->levels < level; sa->levels++) {
 197         p = alloc_node();
 198         if (p == NULL)
 199             return 0;
 200         p[0] = sa->nodes;
 201         sa->nodes = p;
 202     }
 203     if (sa->top < posn)
 204         sa->top = posn;
 205
 206     p = sa->nodes;
 207     for (level = sa->levels - 1; level > 0; level--) {
 208         i = (posn >> (OPENSSL_SA_BLOCK_BITS * level)) & SA_BLOCK_MASK;
 209         if (p[i] == NULL && (p[i] = alloc_node()) == NULL)
 210             return 0;
 211         p = p[i];
 212     }
 213     p += posn & SA_BLOCK_MASK;
 214     if (val == NULL && *p != NULL)
 215         sa->nelem--;
 216     else if (val != NULL && *p == NULL)
 217         sa->nelem++;
 218     *p = val;
 219     return 1;
 220 }