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 the 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 } 217