/src/openssl/crypto/sparse_array.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Copyright 2019-2024 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 | 285k | # 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 | 168k | #define SA_BLOCK_MAX (1 << OPENSSL_SA_BLOCK_BITS) |
46 | 135k | #define SA_BLOCK_MASK (SA_BLOCK_MAX - 1) |
47 | 4.01k | #define SA_BLOCK_MAX_LEVELS (((int)sizeof(ossl_uintmax_t) * 8 \ |
48 | 4.01k | + OPENSSL_SA_BLOCK_BITS - 1) \ |
49 | 4.01k | / 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 | 16 | { |
60 | 16 | OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res)); |
61 | | |
62 | 16 | return res; |
63 | 16 | } |
64 | | |
65 | | static void sa_doall(const OPENSSL_SA *sa, void (*node)(void **), |
66 | | void (*leaf)(ossl_uintmax_t, void *, void *), void *arg) |
67 | 32 | { |
68 | 32 | int i[SA_BLOCK_MAX_LEVELS]; |
69 | 32 | void *nodes[SA_BLOCK_MAX_LEVELS]; |
70 | 32 | ossl_uintmax_t idx = 0; |
71 | 32 | int l = 0; |
72 | | |
73 | 32 | i[0] = 0; |
74 | 32 | nodes[0] = sa->nodes; |
75 | 33.2k | while (l >= 0) { |
76 | 33.1k | const int n = i[l]; |
77 | 33.1k | void ** const p = nodes[l]; |
78 | | |
79 | 33.1k | if (n >= SA_BLOCK_MAX) { |
80 | 1.95k | if (p != NULL && node != NULL) |
81 | 962 | (*node)(p); |
82 | 1.95k | l--; |
83 | 1.95k | idx >>= OPENSSL_SA_BLOCK_BITS; |
84 | 31.2k | } else { |
85 | 31.2k | i[l] = n + 1; |
86 | 31.2k | if (p != NULL && p[n] != NULL) { |
87 | 2.42k | idx = (idx & ~SA_BLOCK_MASK) | n; |
88 | 2.42k | if (l < sa->levels - 1) { |
89 | 1.92k | i[++l] = 0; |
90 | 1.92k | nodes[l] = p[n]; |
91 | 1.92k | idx <<= OPENSSL_SA_BLOCK_BITS; |
92 | 1.92k | } else if (leaf != NULL) { |
93 | 508 | (*leaf)(idx, p[n], arg); |
94 | 508 | } |
95 | 2.42k | } |
96 | 31.2k | } |
97 | 33.1k | } |
98 | 32 | } |
99 | | |
100 | | static void sa_free_node(void **p) |
101 | 962 | { |
102 | 962 | OPENSSL_free(p); |
103 | 962 | } |
104 | | |
105 | | static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg) |
106 | 0 | { |
107 | 0 | OPENSSL_free(p); |
108 | 0 | } |
109 | | |
110 | | void ossl_sa_free(OPENSSL_SA *sa) |
111 | 16 | { |
112 | 16 | if (sa != NULL) { |
113 | 16 | sa_doall(sa, &sa_free_node, NULL, NULL); |
114 | 16 | OPENSSL_free(sa); |
115 | 16 | } |
116 | 16 | } |
117 | | |
118 | | void ossl_sa_free_leaves(OPENSSL_SA *sa) |
119 | 0 | { |
120 | 0 | sa_doall(sa, &sa_free_node, &sa_free_leaf, NULL); |
121 | 0 | OPENSSL_free(sa); |
122 | 0 | } |
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 | 0 | { |
131 | 0 | ((const struct trampoline_st *)arg)->func(n, l); |
132 | 0 | } |
133 | | |
134 | | void ossl_sa_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t, void *)) |
135 | 0 | { |
136 | 0 | struct trampoline_st tramp; |
137 | |
|
138 | 0 | tramp.func = leaf; |
139 | 0 | if (sa != NULL) |
140 | 0 | sa_doall(sa, NULL, &trampoline, &tramp); |
141 | 0 | } |
142 | | |
143 | | void ossl_sa_doall_arg(const OPENSSL_SA *sa, |
144 | | void (*leaf)(ossl_uintmax_t, void *, void *), |
145 | | void *arg) |
146 | 16 | { |
147 | 16 | if (sa != NULL) |
148 | 16 | sa_doall(sa, NULL, leaf, arg); |
149 | 16 | } |
150 | | |
151 | | size_t ossl_sa_num(const OPENSSL_SA *sa) |
152 | 0 | { |
153 | 0 | return sa == NULL ? 0 : sa->nelem; |
154 | 0 | } |
155 | | |
156 | | void *ossl_sa_get(const OPENSSL_SA *sa, ossl_uintmax_t n) |
157 | 34.5k | { |
158 | 34.5k | int level; |
159 | 34.5k | void **p, *r = NULL; |
160 | | |
161 | 34.5k | if (sa == NULL || sa->nelem == 0) |
162 | 6 | return NULL; |
163 | | |
164 | 34.5k | if (n <= sa->top) { |
165 | 34.0k | p = sa->nodes; |
166 | 132k | for (level = sa->levels - 1; p != NULL && level > 0; level--) |
167 | 98.4k | p = (void **)p[(n >> (OPENSSL_SA_BLOCK_BITS * level)) |
168 | 98.4k | & SA_BLOCK_MASK]; |
169 | 34.0k | r = p == NULL ? NULL : p[n & SA_BLOCK_MASK]; |
170 | 34.0k | } |
171 | 34.5k | return r; |
172 | 34.5k | } |
173 | | |
174 | | static ossl_inline void **alloc_node(void) |
175 | 962 | { |
176 | 962 | return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *)); |
177 | 962 | } |
178 | | |
179 | | int ossl_sa_set(OPENSSL_SA *sa, ossl_uintmax_t posn, void *val) |
180 | 1.01k | { |
181 | 1.01k | int i, level = 1; |
182 | 1.01k | ossl_uintmax_t n = posn; |
183 | 1.01k | void **p; |
184 | | |
185 | 1.01k | if (sa == NULL) |
186 | 0 | return 0; |
187 | | |
188 | 4.01k | for (level = 1; level < SA_BLOCK_MAX_LEVELS; level++) |
189 | 4.01k | if ((n >>= OPENSSL_SA_BLOCK_BITS) == 0) |
190 | 1.01k | break; |
191 | | |
192 | 1.02k | for (;sa->levels < level; sa->levels++) { |
193 | 8 | p = alloc_node(); |
194 | 8 | if (p == NULL) |
195 | 0 | return 0; |
196 | 8 | p[0] = sa->nodes; |
197 | 8 | sa->nodes = p; |
198 | 8 | } |
199 | 1.01k | if (sa->top < posn) |
200 | 264 | sa->top = posn; |
201 | | |
202 | 1.01k | p = sa->nodes; |
203 | 4.06k | for (level = sa->levels - 1; level > 0; level--) { |
204 | 3.04k | i = (posn >> (OPENSSL_SA_BLOCK_BITS * level)) & SA_BLOCK_MASK; |
205 | 3.04k | if (p[i] == NULL && (p[i] = alloc_node()) == NULL) |
206 | 0 | return 0; |
207 | 3.04k | p = p[i]; |
208 | 3.04k | } |
209 | 1.01k | p += posn & SA_BLOCK_MASK; |
210 | 1.01k | if (val == NULL && *p != NULL) |
211 | 508 | sa->nelem--; |
212 | 508 | else if (val != NULL && *p == NULL) |
213 | 508 | sa->nelem++; |
214 | 1.01k | *p = val; |
215 | 1.01k | return 1; |
216 | 1.01k | } |