]>
Commit | Line | Data |
---|---|---|
a40f0f64 | 1 | /* |
fecb3aae | 2 | * Copyright 2019-2022 The OpenSSL Project Authors. All Rights Reserved. |
a40f0f64 P |
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> | |
54b5fb2d | 12 | #include <openssl/bn.h> |
25f2138b | 13 | #include "crypto/sparse_array.h" |
a40f0f64 P |
14 | |
15 | /* | |
c2969ff6 | 16 | * How many bits are used to index each level in the tree structure? |
a40f0f64 P |
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 | * | |
514bd51a P |
22 | * The default is to use four bits which means that the are 16 |
23 | * pointers in each tree node. | |
a40f0f64 P |
24 | * |
25 | * The library builder is also permitted to define other sizes in the closed | |
514bd51a P |
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. | |
a40f0f64 P |
32 | */ |
33 | #ifndef OPENSSL_SA_BLOCK_BITS | |
514bd51a | 34 | # define OPENSSL_SA_BLOCK_BITS 4 |
e0ae0585 | 35 | #elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > (BN_BITS2 - 1) |
a40f0f64 P |
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; | |
e5fee28f | 42 | * a bit mask to quickly extract an index and |
a40f0f64 P |
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) | |
8ab53b19 | 47 | #define SA_BLOCK_MAX_LEVELS (((int)sizeof(ossl_uintmax_t) * 8 \ |
a40f0f64 P |
48 | + OPENSSL_SA_BLOCK_BITS - 1) \ |
49 | / OPENSSL_SA_BLOCK_BITS) | |
50 | ||
51 | struct sparse_array_st { | |
52 | int levels; | |
8ab53b19 | 53 | ossl_uintmax_t top; |
a40f0f64 P |
54 | size_t nelem; |
55 | void **nodes; | |
56 | }; | |
57 | ||
ff0266ed | 58 | OPENSSL_SA *ossl_sa_new(void) |
a40f0f64 P |
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 **), | |
8ab53b19 | 66 | void (*leaf)(ossl_uintmax_t, void *, void *), void *arg) |
a40f0f64 P |
67 | { |
68 | int i[SA_BLOCK_MAX_LEVELS]; | |
69 | void *nodes[SA_BLOCK_MAX_LEVELS]; | |
8ab53b19 | 70 | ossl_uintmax_t idx = 0; |
a40f0f64 P |
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--; | |
008b4ff9 | 83 | idx >>= OPENSSL_SA_BLOCK_BITS; |
a40f0f64 P |
84 | } else { |
85 | i[l] = n + 1; | |
86 | if (p != NULL && p[n] != NULL) { | |
008b4ff9 | 87 | idx = (idx & ~SA_BLOCK_MASK) | n; |
a40f0f64 P |
88 | if (l < sa->levels - 1) { |
89 | i[++l] = 0; | |
90 | nodes[l] = p[n]; | |
008b4ff9 | 91 | idx <<= OPENSSL_SA_BLOCK_BITS; |
a40f0f64 | 92 | } else if (leaf != NULL) { |
008b4ff9 | 93 | (*leaf)(idx, p[n], arg); |
a40f0f64 P |
94 | } |
95 | } | |
96 | } | |
97 | } | |
98 | } | |
99 | ||
100 | static void sa_free_node(void **p) | |
101 | { | |
102 | OPENSSL_free(p); | |
103 | } | |
104 | ||
8ab53b19 | 105 | static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg) |
a40f0f64 P |
106 | { |
107 | OPENSSL_free(p); | |
108 | } | |
109 | ||
ff0266ed | 110 | void ossl_sa_free(OPENSSL_SA *sa) |
a40f0f64 | 111 | { |
93429fc0 P |
112 | if (sa != NULL) { |
113 | sa_doall(sa, &sa_free_node, NULL, NULL); | |
114 | OPENSSL_free(sa); | |
115 | } | |
a40f0f64 P |
116 | } |
117 | ||
ff0266ed | 118 | void ossl_sa_free_leaves(OPENSSL_SA *sa) |
a40f0f64 P |
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 { | |
8ab53b19 | 126 | void (*func)(ossl_uintmax_t, void *); |
a40f0f64 P |
127 | }; |
128 | ||
8ab53b19 | 129 | static void trampoline(ossl_uintmax_t n, void *l, void *arg) |
a40f0f64 | 130 | { |
008b4ff9 | 131 | ((const struct trampoline_st *)arg)->func(n, l); |
a40f0f64 P |
132 | } |
133 | ||
ff0266ed | 134 | void ossl_sa_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t, void *)) |
a40f0f64 P |
135 | { |
136 | struct trampoline_st tramp; | |
137 | ||
138 | tramp.func = leaf; | |
139 | if (sa != NULL) | |
140 | sa_doall(sa, NULL, &trampoline, &tramp); | |
141 | } | |
142 | ||
ff0266ed | 143 | void ossl_sa_doall_arg(const OPENSSL_SA *sa, |
8ab53b19 P |
144 | void (*leaf)(ossl_uintmax_t, void *, void *), |
145 | void *arg) | |
a40f0f64 P |
146 | { |
147 | if (sa != NULL) | |
148 | sa_doall(sa, NULL, leaf, arg); | |
149 | } | |
150 | ||
ff0266ed | 151 | size_t ossl_sa_num(const OPENSSL_SA *sa) |
a40f0f64 P |
152 | { |
153 | return sa == NULL ? 0 : sa->nelem; | |
154 | } | |
155 | ||
ff0266ed | 156 | void *ossl_sa_get(const OPENSSL_SA *sa, ossl_uintmax_t n) |
a40f0f64 P |
157 | { |
158 | int level; | |
159 | void **p, *r = NULL; | |
160 | ||
04cb5ec0 | 161 | if (sa == NULL || sa->nelem == 0) |
a40f0f64 P |
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 | ||
ff0266ed | 179 | int ossl_sa_set(OPENSSL_SA *sa, ossl_uintmax_t posn, void *val) |
a40f0f64 P |
180 | { |
181 | int i, level = 1; | |
8ab53b19 | 182 | ossl_uintmax_t n = posn; |
a40f0f64 P |
183 | void **p; |
184 | ||
185 | if (sa == NULL) | |
186 | return 0; | |
187 | ||
1bdbdaff | 188 | for (level = 1; level < SA_BLOCK_MAX_LEVELS; level++) |
a40f0f64 P |
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 | } |