Configure: disable new trace api by default
[openssl.git] / 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 <openssl/bn.h>
13 #include "internal/sparse_array.h"
14
15 /*
16  * How many bits are used to index each level in the tree structre?
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
32  * interval [2, sizeof(ossl_uintmax_t) * 8].
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
40 #elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > (BN_BITS2 - 1)
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;
47  *    a bit mask to quickly extract an index and
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)
52 #define SA_BLOCK_MAX_LEVELS     (((int)sizeof(ossl_uintmax_t) * 8 \
53                                   + OPENSSL_SA_BLOCK_BITS - 1) \
54                                  / OPENSSL_SA_BLOCK_BITS)
55
56 struct sparse_array_st {
57     int levels;
58     ossl_uintmax_t top;
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 **),
71                      void (*leaf)(ossl_uintmax_t, void *, void *), void *arg)
72 {
73     int i[SA_BLOCK_MAX_LEVELS];
74     void *nodes[SA_BLOCK_MAX_LEVELS];
75     ossl_uintmax_t idx = 0;
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--;
88             idx >>= OPENSSL_SA_BLOCK_BITS;
89         } else {
90             i[l] = n + 1;
91             if (p != NULL && p[n] != NULL) {
92                 idx = (idx & ~SA_BLOCK_MASK) | n;
93                 if (l < sa->levels - 1) {
94                     i[++l] = 0;
95                     nodes[l] = p[n];
96                     idx <<= OPENSSL_SA_BLOCK_BITS;
97                 } else if (leaf != NULL) {
98                     (*leaf)(idx, p[n], arg);
99                 }
100             }
101         }
102     }
103 }
104
105 static void sa_free_node(void **p)
106 {
107     OPENSSL_free(p);
108 }
109
110 static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg)
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 {
129     void (*func)(ossl_uintmax_t, void *);
130 };
131
132 static void trampoline(ossl_uintmax_t n, void *l, void *arg)
133 {
134     ((const struct trampoline_st *)arg)->func(n, l);
135 }
136
137 void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t,
138                                                          void *))
139 {
140     struct trampoline_st tramp;
141
142     tramp.func = leaf;
143     if (sa != NULL)
144         sa_doall(sa, NULL, &trampoline, &tramp);
145 }
146
147 void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa,
148                           void (*leaf)(ossl_uintmax_t, void *, void *),
149                           void *arg)
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
160 void *OPENSSL_SA_get(const OPENSSL_SA *sa, ossl_uintmax_t n)
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
183 int OPENSSL_SA_set(OPENSSL_SA *sa, ossl_uintmax_t posn, void *val)
184 {
185     int i, level = 1;
186     ossl_uintmax_t n = posn;
187     void **p;
188
189     if (sa == NULL)
190         return 0;
191
192     for (level = 1; level < SA_BLOCK_MAX_LEVELS; level++)
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 }