crypto/sparse_array.c

   1 /*
   2  * Copyright 2019-2022 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 "crypto/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 default is to use four bits which means that there are 16
  23  * pointers in each tree node.
  24  *
  25  * The library builder is also permitted to define other sizes in the closed
  26  * interval [2, sizeof(ossl_uintmax_t) * 8].  Space use generally scales
  27  * exponentially with the block size, although the implementation only
  28  * creates enough blocks to support the largest used index.  The depth is:
  29  *      ceil(log_2(largest index) / 2^{block size})
  30  * E.g. with a block size of 4, and a largest index of 1000, the depth
  31  * will be three.
  32  */
  33 #ifndef OPENSSL_SA_BLOCK_BITS
  34 # define OPENSSL_SA_BLOCK_BITS           4
  35 #elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > (BN_BITS2 - 1)
  36 # error OPENSSL_SA_BLOCK_BITS is out of range
  37 #endif
  38
  39 /*
  40  * From the number of bits, work out:
  41  *    the number of pointers in a tree node;
  42  *    a bit mask to quickly extract an index and
  43  *    the maximum depth of the tree structure.
  44   */
  45 #define SA_BLOCK_MAX            (1 << OPENSSL_SA_BLOCK_BITS)
  46 #define SA_BLOCK_MASK           (SA_BLOCK_MAX - 1)
  47 #define SA_BLOCK_MAX_LEVELS     (((int)sizeof(ossl_uintmax_t) * 8 \
  48                                   + OPENSSL_SA_BLOCK_BITS - 1) \
  49                                  / OPENSSL_SA_BLOCK_BITS)
  50
  51 struct sparse_array_st {
  52     int levels;
  53     ossl_uintmax_t top;
  54     size_t nelem;
  55     void **nodes;
  56 };
  57
  58 OPENSSL_SA *ossl_sa_new(void)
  59 {
  60     OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res));
  61
  62     return res;
  63 }
  64
  65 static void sa_doall(const OPENSSL_SA *sa, void (*node)(void **),
  66                      void (*leaf)(ossl_uintmax_t, void *, void *), void *arg)
  67 {
  68     int i[SA_BLOCK_MAX_LEVELS];
  69     void *nodes[SA_BLOCK_MAX_LEVELS];
  70     ossl_uintmax_t idx = 0;
  71     int l = 0;
  72
  73     i[0] = 0;
  74     nodes[0] = sa->nodes;
  75     while (l >= 0) {
  76         const int n = i[l];
  77         void ** const p = nodes[l];
  78
  79         if (n >= SA_BLOCK_MAX) {
  80             if (p != NULL && node != NULL)
  81                 (*node)(p);
  82             l--;
  83             idx >>= OPENSSL_SA_BLOCK_BITS;
  84         } else {
  85             i[l] = n + 1;
  86             if (p != NULL && p[n] != NULL) {
  87                 idx = (idx & ~SA_BLOCK_MASK) | n;
  88                 if (l < sa->levels - 1) {
  89                     i[++l] = 0;
  90                     nodes[l] = p[n];
  91                     idx <<= OPENSSL_SA_BLOCK_BITS;
  92                 } else if (leaf != NULL) {
  93                     (*leaf)(idx, p[n], arg);
  94                 }
  95             }
  96         }
  97     }
  98 }
  99
 100 static void sa_free_node(void **p)
 101 {
 102     OPENSSL_free(p);
 103 }
 104
 105 static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg)
 106 {
 107     OPENSSL_free(p);
 108 }
 109
 110 void ossl_sa_free(OPENSSL_SA *sa)
 111 {
 112     if (sa != NULL) {
 113         sa_doall(sa, &sa_free_node, NULL, NULL);
 114         OPENSSL_free(sa);
 115     }
 116 }
 117
 118 void ossl_sa_free_leaves(OPENSSL_SA *sa)
 119 {
 120     sa_doall(sa, &sa_free_node, &sa_free_leaf, NULL);
 121     OPENSSL_free(sa);
 122 }
 123
 124 /* Wrap this in a structure to avoid compiler warnings */
 125 struct trampoline_st {
 126     void (*func)(ossl_uintmax_t, void *);
 127 };
 128
 129 static void trampoline(ossl_uintmax_t n, void *l, void *arg)
 130 {
 131     ((const struct trampoline_st *)arg)->func(n, l);
 132 }
 133
 134 void ossl_sa_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t, void *))
 135 {
 136     struct trampoline_st tramp;
 137
 138     tramp.func = leaf;
 139     if (sa != NULL)
 140         sa_doall(sa, NULL, &trampoline, &tramp);
 141 }
 142
 143 void ossl_sa_doall_arg(const OPENSSL_SA *sa,
 144                           void (*leaf)(ossl_uintmax_t, void *, void *),
 145                           void *arg)
 146 {
 147     if (sa != NULL)
 148         sa_doall(sa, NULL, leaf, arg);
 149 }
 150
 151 size_t ossl_sa_num(const OPENSSL_SA *sa)
 152 {
 153     return sa == NULL ? 0 : sa->nelem;
 154 }
 155
 156 void *ossl_sa_get(const OPENSSL_SA *sa, ossl_uintmax_t n)
 157 {
 158     int level;
 159     void **p, *r = NULL;
 160
 161     if (sa == NULL || sa->nelem == 0)
 162         return NULL;
 163
 164     if (n <= sa->top) {
 165         p = sa->nodes;
 166         for (level = sa->levels - 1; p != NULL && level > 0; level--)
 167             p = (void **)p[(n >> (OPENSSL_SA_BLOCK_BITS * level))
 168                            & SA_BLOCK_MASK];
 169         r = p == NULL ? NULL : p[n & SA_BLOCK_MASK];
 170     }
 171     return r;
 172 }
 173
 174 static ossl_inline void **alloc_node(void)
 175 {
 176     return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *));
 177 }
 178
 179 int ossl_sa_set(OPENSSL_SA *sa, ossl_uintmax_t posn, void *val)
 180 {
 181     int i, level = 1;
 182     ossl_uintmax_t n = posn;
 183     void **p;
 184
 185     if (sa == NULL)
 186         return 0;
 187
 188     for (level = 1; level < SA_BLOCK_MAX_LEVELS; level++)
 189         if ((n >>= OPENSSL_SA_BLOCK_BITS) == 0)
 190             break;
 191
 192     for (;sa->levels < level; sa->levels++) {
 193         p = alloc_node();
 194         if (p == NULL)
 195             return 0;
 196         p[0] = sa->nodes;
 197         sa->nodes = p;
 198     }
 199     if (sa->top < posn)
 200         sa->top = posn;
 201
 202     p = sa->nodes;
 203     for (level = sa->levels - 1; level > 0; level--) {
 204         i = (posn >> (OPENSSL_SA_BLOCK_BITS * level)) & SA_BLOCK_MASK;
 205         if (p[i] == NULL && (p[i] = alloc_node()) == NULL)
 206             return 0;
 207         p = p[i];
 208     }
 209     p += posn & SA_BLOCK_MASK;
 210     if (val == NULL && *p != NULL)
 211         sa->nelem--;
 212     else if (val != NULL && *p == NULL)
 213         sa->nelem++;
 214     *p = val;
 215     return 1;
 216 }