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 
ossl_sa_new(void)58 OPENSSL_SA *ossl_sa_new(void)
59 {
60     OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res));
61 
62     return res;
63 }
64 
sa_doall(const OPENSSL_SA * sa,void (* node)(void **),void (* leaf)(ossl_uintmax_t,void *,void *),void * arg)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 
sa_free_node(void ** p)100 static void sa_free_node(void **p)
101 {
102     OPENSSL_free(p);
103 }
104 
sa_free_leaf(ossl_uintmax_t n,void * p,void * arg)105 static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg)
106 {
107     OPENSSL_free(p);
108 }
109 
ossl_sa_free(OPENSSL_SA * sa)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 
ossl_sa_free_leaves(OPENSSL_SA * sa)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 
trampoline(ossl_uintmax_t n,void * l,void * arg)129 static void trampoline(ossl_uintmax_t n, void *l, void *arg)
130 {
131     ((const struct trampoline_st *)arg)->func(n, l);
132 }
133 
ossl_sa_doall(const OPENSSL_SA * sa,void (* leaf)(ossl_uintmax_t,void *))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 
ossl_sa_doall_arg(const OPENSSL_SA * sa,void (* leaf)(ossl_uintmax_t,void *,void *),void * arg)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 
ossl_sa_num(const OPENSSL_SA * sa)151 size_t ossl_sa_num(const OPENSSL_SA *sa)
152 {
153     return sa == NULL ? 0 : sa->nelem;
154 }
155 
ossl_sa_get(const OPENSSL_SA * sa,ossl_uintmax_t n)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 
alloc_node(void)174 static ossl_inline void **alloc_node(void)
175 {
176     return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *));
177 }
178 
ossl_sa_set(OPENSSL_SA * sa,ossl_uintmax_t posn,void * val)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