]>
git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/sparse_array.c
2 * Copyright 2019-2021 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.
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
11 #include <openssl/crypto.h>
12 #include <openssl/bn.h>
13 #include "crypto/sparse_array.h"
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.
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.
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
31 * The library builder is also permitted to define other sizes in the closed
32 * interval [2, sizeof(ossl_uintmax_t) * 8].
34 #ifndef OPENSSL_SA_BLOCK_BITS
35 # ifdef OPENSSL_SMALL_FOOTPRINT
36 # define OPENSSL_SA_BLOCK_BITS 4
38 # define OPENSSL_SA_BLOCK_BITS 12
40 #elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > (BN_BITS2 - 1)
41 # error OPENSSL_SA_BLOCK_BITS is out of range
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.
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)
56 struct sparse_array_st
{
63 OPENSSL_SA
*ossl_sa_new(void)
65 OPENSSL_SA
*res
= OPENSSL_zalloc(sizeof(*res
));
70 static void sa_doall(const OPENSSL_SA
*sa
, void (*node
)(void **),
71 void (*leaf
)(ossl_uintmax_t
, void *, void *), void *arg
)
73 int i
[SA_BLOCK_MAX_LEVELS
];
74 void *nodes
[SA_BLOCK_MAX_LEVELS
];
75 ossl_uintmax_t idx
= 0;
82 void ** const p
= nodes
[l
];
84 if (n
>= SA_BLOCK_MAX
) {
85 if (p
!= NULL
&& node
!= NULL
)
88 idx
>>= OPENSSL_SA_BLOCK_BITS
;
91 if (p
!= NULL
&& p
[n
] != NULL
) {
92 idx
= (idx
& ~SA_BLOCK_MASK
) | n
;
93 if (l
< sa
->levels
- 1) {
96 idx
<<= OPENSSL_SA_BLOCK_BITS
;
97 } else if (leaf
!= NULL
) {
98 (*leaf
)(idx
, p
[n
], arg
);
105 static void sa_free_node(void **p
)
110 static void sa_free_leaf(ossl_uintmax_t n
, void *p
, void *arg
)
115 void ossl_sa_free(OPENSSL_SA
*sa
)
117 sa_doall(sa
, &sa_free_node
, NULL
, NULL
);
121 void ossl_sa_free_leaves(OPENSSL_SA
*sa
)
123 sa_doall(sa
, &sa_free_node
, &sa_free_leaf
, NULL
);
127 /* Wrap this in a structure to avoid compiler warnings */
128 struct trampoline_st
{
129 void (*func
)(ossl_uintmax_t
, void *);
132 static void trampoline(ossl_uintmax_t n
, void *l
, void *arg
)
134 ((const struct trampoline_st
*)arg
)->func(n
, l
);
137 void ossl_sa_doall(const OPENSSL_SA
*sa
, void (*leaf
)(ossl_uintmax_t
, void *))
139 struct trampoline_st tramp
;
143 sa_doall(sa
, NULL
, &trampoline
, &tramp
);
146 void ossl_sa_doall_arg(const OPENSSL_SA
*sa
,
147 void (*leaf
)(ossl_uintmax_t
, void *, void *),
151 sa_doall(sa
, NULL
, leaf
, arg
);
154 size_t ossl_sa_num(const OPENSSL_SA
*sa
)
156 return sa
== NULL
? 0 : sa
->nelem
;
159 void *ossl_sa_get(const OPENSSL_SA
*sa
, ossl_uintmax_t n
)
164 if (sa
== NULL
|| sa
->nelem
== 0)
169 for (level
= sa
->levels
- 1; p
!= NULL
&& level
> 0; level
--)
170 p
= (void **)p
[(n
>> (OPENSSL_SA_BLOCK_BITS
* level
))
172 r
= p
== NULL
? NULL
: p
[n
& SA_BLOCK_MASK
];
177 static ossl_inline
void **alloc_node(void)
179 return OPENSSL_zalloc(SA_BLOCK_MAX
* sizeof(void *));
182 int ossl_sa_set(OPENSSL_SA
*sa
, ossl_uintmax_t posn
, void *val
)
185 ossl_uintmax_t n
= posn
;
191 for (level
= 1; level
< SA_BLOCK_MAX_LEVELS
; level
++)
192 if ((n
>>= OPENSSL_SA_BLOCK_BITS
) == 0)
195 for (;sa
->levels
< level
; sa
->levels
++) {
206 for (level
= sa
->levels
- 1; level
> 0; level
--) {
207 i
= (posn
>> (OPENSSL_SA_BLOCK_BITS
* level
)) & SA_BLOCK_MASK
;
208 if (p
[i
] == NULL
&& (p
[i
] = alloc_node()) == NULL
)
212 p
+= posn
& SA_BLOCK_MASK
;
213 if (val
== NULL
&& *p
!= NULL
)
215 else if (val
!= NULL
&& *p
== NULL
)