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 "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 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
56struct sparse_array_st {
57 int levels;
58 ossl_uintmax_t top;
59 size_t nelem;
60 void **nodes;
61};
62
63OPENSSL_SA *OPENSSL_SA_new(void)
64{
65 OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res));
66
67 return res;
68}
69
70static 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
105static void sa_free_node(void **p)
106{
107 OPENSSL_free(p);
108}
109
110static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg)
111{
112 OPENSSL_free(p);
113}
114
115void OPENSSL_SA_free(OPENSSL_SA *sa)
116{
117 sa_doall(sa, &sa_free_node, NULL, NULL);
118 OPENSSL_free(sa);
119}
120
121void 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 */
128struct trampoline_st {
129 void (*func)(ossl_uintmax_t, void *);
130};
131
132static void trampoline(ossl_uintmax_t n, void *l, void *arg)
133{
134 ((const struct trampoline_st *)arg)->func(n, l);
135}
136
137void 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
147void 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
155size_t OPENSSL_SA_num(const OPENSSL_SA *sa)
156{
157 return sa == NULL ? 0 : sa->nelem;
158}
159
160void *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
178static ossl_inline void **alloc_node(void)
179{
180 return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *));
181}
182
183int 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}
221