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