Coverage Report

Created: 2025-06-13 06:56

/src/openssl/crypto/sparse_array.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2019-2024 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 there 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
288
# 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
272
#define SA_BLOCK_MAX            (1 << OPENSSL_SA_BLOCK_BITS)
46
0
#define SA_BLOCK_MASK           (SA_BLOCK_MAX - 1)
47
0
#define SA_BLOCK_MAX_LEVELS     (((int)sizeof(ossl_uintmax_t) * 8 \
48
0
                                  + OPENSSL_SA_BLOCK_BITS - 1) \
49
0
                                 / 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
58
OPENSSL_SA *ossl_sa_new(void)
59
8
{
60
8
    OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res));
61
62
8
    return res;
63
8
}
64
65
static void sa_doall(const OPENSSL_SA *sa, void (*node)(void **),
66
                     void (*leaf)(ossl_uintmax_t, void *, void *), void *arg)
67
16
{
68
16
    int i[SA_BLOCK_MAX_LEVELS];
69
16
    void *nodes[SA_BLOCK_MAX_LEVELS];
70
16
    ossl_uintmax_t idx = 0;
71
16
    int l = 0;
72
73
16
    i[0] = 0;
74
16
    nodes[0] = sa->nodes;
75
288
    while (l >= 0) {
76
272
        const int n = i[l];
77
272
        void ** const p = nodes[l];
78
79
272
        if (n >= SA_BLOCK_MAX) {
80
16
            if (p != NULL && node != NULL)
81
0
                (*node)(p);
82
16
            l--;
83
16
            idx >>= OPENSSL_SA_BLOCK_BITS;
84
256
        } else {
85
256
            i[l] = n + 1;
86
256
            if (p != NULL && p[n] != NULL) {
87
0
                idx = (idx & ~SA_BLOCK_MASK) | n;
88
0
                if (l < sa->levels - 1) {
89
0
                    i[++l] = 0;
90
0
                    nodes[l] = p[n];
91
0
                    idx <<= OPENSSL_SA_BLOCK_BITS;
92
0
                } else if (leaf != NULL) {
93
0
                    (*leaf)(idx, p[n], arg);
94
0
                }
95
0
            }
96
256
        }
97
272
    }
98
16
}
99
100
static void sa_free_node(void **p)
101
0
{
102
0
    OPENSSL_free(p);
103
0
}
104
105
static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg)
106
0
{
107
0
    OPENSSL_free(p);
108
0
}
109
110
void ossl_sa_free(OPENSSL_SA *sa)
111
8
{
112
8
    if (sa != NULL) {
113
8
        sa_doall(sa, &sa_free_node, NULL, NULL);
114
8
        OPENSSL_free(sa);
115
8
    }
116
8
}
117
118
void ossl_sa_free_leaves(OPENSSL_SA *sa)
119
0
{
120
0
    sa_doall(sa, &sa_free_node, &sa_free_leaf, NULL);
121
0
    OPENSSL_free(sa);
122
0
}
123
124
/* Wrap this in a structure to avoid compiler warnings */
125
struct trampoline_st {
126
    void (*func)(ossl_uintmax_t, void *);
127
};
128
129
static void trampoline(ossl_uintmax_t n, void *l, void *arg)
130
0
{
131
0
    ((const struct trampoline_st *)arg)->func(n, l);
132
0
}
133
134
void ossl_sa_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t, void *))
135
0
{
136
0
    struct trampoline_st tramp;
137
138
0
    tramp.func = leaf;
139
0
    if (sa != NULL)
140
0
        sa_doall(sa, NULL, &trampoline, &tramp);
141
0
}
142
143
void ossl_sa_doall_arg(const OPENSSL_SA *sa,
144
                          void (*leaf)(ossl_uintmax_t, void *, void *),
145
                          void *arg)
146
8
{
147
8
    if (sa != NULL)
148
8
        sa_doall(sa, NULL, leaf, arg);
149
8
}
150
151
size_t ossl_sa_num(const OPENSSL_SA *sa)
152
0
{
153
0
    return sa == NULL ? 0 : sa->nelem;
154
0
}
155
156
void *ossl_sa_get(const OPENSSL_SA *sa, ossl_uintmax_t n)
157
0
{
158
0
    int level;
159
0
    void **p, *r = NULL;
160
161
0
    if (sa == NULL || sa->nelem == 0)
162
0
        return NULL;
163
164
0
    if (n <= sa->top) {
165
0
        p = sa->nodes;
166
0
        for (level = sa->levels - 1; p != NULL && level > 0; level--)
167
0
            p = (void **)p[(n >> (OPENSSL_SA_BLOCK_BITS * level))
168
0
                           & SA_BLOCK_MASK];
169
0
        r = p == NULL ? NULL : p[n & SA_BLOCK_MASK];
170
0
    }
171
0
    return r;
172
0
}
173
174
static ossl_inline void **alloc_node(void)
175
0
{
176
0
    return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *));
177
0
}
178
179
int ossl_sa_set(OPENSSL_SA *sa, ossl_uintmax_t posn, void *val)
180
0
{
181
0
    int i, level = 1;
182
0
    ossl_uintmax_t n = posn;
183
0
    void **p;
184
185
0
    if (sa == NULL)
186
0
        return 0;
187
188
0
    for (level = 1; level < SA_BLOCK_MAX_LEVELS; level++)
189
0
        if ((n >>= OPENSSL_SA_BLOCK_BITS) == 0)
190
0
            break;
191
192
0
    for (;sa->levels < level; sa->levels++) {
193
0
        p = alloc_node();
194
0
        if (p == NULL)
195
0
            return 0;
196
0
        p[0] = sa->nodes;
197
0
        sa->nodes = p;
198
0
    }
199
0
    if (sa->top < posn)
200
0
        sa->top = posn;
201
202
0
    p = sa->nodes;
203
0
    for (level = sa->levels - 1; level > 0; level--) {
204
0
        i = (posn >> (OPENSSL_SA_BLOCK_BITS * level)) & SA_BLOCK_MASK;
205
0
        if (p[i] == NULL && (p[i] = alloc_node()) == NULL)
206
0
            return 0;
207
0
        p = p[i];
208
0
    }
209
0
    p += posn & SA_BLOCK_MASK;
210
0
    if (val == NULL && *p != NULL)
211
0
        sa->nelem--;
212
0
    else if (val != NULL && *p == NULL)
213
0
        sa->nelem++;
214
0
    *p = val;
215
0
    return 1;
216
0
}