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