Coverage Report

Created: 2024-11-21 07:03

/src/openssl/crypto/stack/stack.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved.
3
 *
4
 * Licensed under the Apache License 2.0 (the "License").  You may not use
5
 * this file except in compliance with the License.  You can obtain a copy
6
 * in the file LICENSE in the source distribution or at
7
 * https://www.openssl.org/source/license.html
8
 */
9
10
#include <stdio.h>
11
#include "internal/cryptlib.h"
12
#include "internal/numbers.h"
13
#include "internal/safe_math.h"
14
#include <openssl/stack.h>
15
#include <errno.h>
16
#include <openssl/e_os2.h>      /* For ossl_inline */
17
18
OSSL_SAFE_MATH_SIGNED(int, int)
19
20
/*
21
 * The initial number of nodes in the array.
22
 */
23
static const int min_nodes = 4;
24
static const int max_nodes = SIZE_MAX / sizeof(void *) < INT_MAX
25
    ? (int)(SIZE_MAX / sizeof(void *)) : INT_MAX;
26
27
struct stack_st {
28
    int num;
29
    const void **data;
30
    int sorted;
31
    int num_alloc;
32
    OPENSSL_sk_compfunc comp;
33
};
34
35
OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk,
36
                                            OPENSSL_sk_compfunc c)
37
0
{
38
0
    OPENSSL_sk_compfunc old = sk->comp;
39
40
0
    if (sk->comp != c)
41
0
        sk->sorted = 0;
42
0
    sk->comp = c;
43
44
0
    return old;
45
0
}
46
47
OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
48
6.83k
{
49
6.83k
    OPENSSL_STACK *ret;
50
51
6.83k
    if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
52
0
        goto err;
53
54
6.83k
    if (sk == NULL) {
55
4
        ret->num = 0;
56
4
        ret->sorted = 0;
57
4
        ret->comp = NULL;
58
6.82k
    } else {
59
        /* direct structure assignment */
60
6.82k
        *ret = *sk;
61
6.82k
    }
62
63
6.83k
    if (sk == NULL || sk->num == 0) {
64
        /* postpone |ret->data| allocation */
65
4
        ret->data = NULL;
66
4
        ret->num_alloc = 0;
67
4
        return ret;
68
4
    }
69
70
    /* duplicate |sk->data| content */
71
6.82k
    ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc);
72
6.82k
    if (ret->data == NULL)
73
0
        goto err;
74
6.82k
    memcpy(ret->data, sk->data, sizeof(void *) * sk->num);
75
6.82k
    return ret;
76
77
0
 err:
78
0
    OPENSSL_sk_free(ret);
79
0
    return NULL;
80
6.82k
}
81
82
OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,
83
                                    OPENSSL_sk_copyfunc copy_func,
84
                                    OPENSSL_sk_freefunc free_func)
85
2
{
86
2
    OPENSSL_STACK *ret;
87
2
    int i;
88
89
2
    if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
90
0
        goto err;
91
92
2
    if (sk == NULL) {
93
2
        ret->num = 0;
94
2
        ret->sorted = 0;
95
2
        ret->comp = NULL;
96
2
    } else {
97
        /* direct structure assignment */
98
0
        *ret = *sk;
99
0
    }
100
101
2
    if (sk == NULL || sk->num == 0) {
102
        /* postpone |ret| data allocation */
103
2
        ret->data = NULL;
104
2
        ret->num_alloc = 0;
105
2
        return ret;
106
2
    }
107
108
0
    ret->num_alloc = sk->num > min_nodes ? sk->num : min_nodes;
109
0
    ret->data = OPENSSL_zalloc(sizeof(*ret->data) * ret->num_alloc);
110
0
    if (ret->data == NULL)
111
0
        goto err;
112
113
0
    for (i = 0; i < ret->num; ++i) {
114
0
        if (sk->data[i] == NULL)
115
0
            continue;
116
0
        if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
117
0
            while (--i >= 0)
118
0
                if (ret->data[i] != NULL)
119
0
                    free_func((void *)ret->data[i]);
120
0
            goto err;
121
0
        }
122
0
    }
123
0
    return ret;
124
125
0
 err:
126
0
    OPENSSL_sk_free(ret);
127
0
    return NULL;
128
0
}
129
130
OPENSSL_STACK *OPENSSL_sk_new_null(void)
131
2.42k
{
132
2.42k
    return OPENSSL_sk_new_reserve(NULL, 0);
133
2.42k
}
134
135
OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
136
284
{
137
284
    return OPENSSL_sk_new_reserve(c, 0);
138
284
}
139
140
/*
141
 * Calculate the array growth based on the target size.
142
 *
143
 * The growth factor is a rational number and is defined by a numerator
144
 * and a denominator.  According to Andrew Koenig in his paper "Why Are
145
 * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
146
 * than the golden ratio (1.618...).
147
 *
148
 * Considering only the Fibonacci ratios less than the golden ratio, the
149
 * number of steps from the minimum allocation to integer overflow is:
150
 *      factor  decimal    growths
151
 *       3/2     1.5          51
152
 *       8/5     1.6          45
153
 *      21/13    1.615...     44
154
 *
155
 * All larger factors have the same number of growths.
156
 *
157
 * 3/2 and 8/5 have nice power of two shifts, so seem like a good choice.
158
 */
159
static ossl_inline int compute_growth(int target, int current)
160
36
{
161
36
    int err = 0;
162
163
72
    while (current < target) {
164
36
        if (current >= max_nodes)
165
0
            return 0;
166
167
36
        current = safe_muldiv_int(current, 8, 5, &err);
168
36
        if (err != 0)
169
0
            return 0;
170
36
        if (current >= max_nodes)
171
0
            current = max_nodes;
172
36
    }
173
36
    return current;
174
36
}
175
176
/* internal STACK storage allocation */
177
static int sk_reserve(OPENSSL_STACK *st, int n, int exact)
178
2.15k
{
179
2.15k
    const void **tmpdata;
180
2.15k
    int num_alloc;
181
182
    /* Check to see the reservation isn't exceeding the hard limit */
183
2.15k
    if (n > max_nodes - st->num) {
184
0
        ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
185
0
        return 0;
186
0
    }
187
188
    /* Figure out the new size */
189
2.15k
    num_alloc = st->num + n;
190
2.15k
    if (num_alloc < min_nodes)
191
1.54k
        num_alloc = min_nodes;
192
193
    /* If |st->data| allocation was postponed */
194
2.15k
    if (st->data == NULL) {
195
        /*
196
         * At this point, |st->num_alloc| and |st->num| are 0;
197
         * so |num_alloc| value is |n| or |min_nodes| if greater than |n|.
198
         */
199
1.02k
        if ((st->data = OPENSSL_zalloc(sizeof(void *) * num_alloc)) == NULL)
200
0
            return 0;
201
1.02k
        st->num_alloc = num_alloc;
202
1.02k
        return 1;
203
1.02k
    }
204
205
1.12k
    if (!exact) {
206
1.12k
        if (num_alloc <= st->num_alloc)
207
1.09k
            return 1;
208
36
        num_alloc = compute_growth(num_alloc, st->num_alloc);
209
36
        if (num_alloc == 0) {
210
0
            ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
211
0
            return 0;
212
0
        }
213
36
    } else if (num_alloc == st->num_alloc) {
214
0
        return 1;
215
0
    }
216
217
36
    tmpdata = OPENSSL_realloc((void *)st->data, sizeof(void *) * num_alloc);
218
36
    if (tmpdata == NULL)
219
0
        return 0;
220
221
36
    st->data = tmpdata;
222
36
    st->num_alloc = num_alloc;
223
36
    return 1;
224
36
}
225
226
OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n)
227
1.31k
{
228
1.31k
    OPENSSL_STACK *st = OPENSSL_zalloc(sizeof(OPENSSL_STACK));
229
230
1.31k
    if (st == NULL)
231
0
        return NULL;
232
233
1.31k
    st->comp = c;
234
235
1.31k
    if (n <= 0)
236
1.31k
        return st;
237
238
0
    if (!sk_reserve(st, n, 1)) {
239
0
        OPENSSL_sk_free(st);
240
0
        return NULL;
241
0
    }
242
243
0
    return st;
244
0
}
245
246
int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n)
247
0
{
248
0
    if (st == NULL) {
249
0
        ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
250
0
        return 0;
251
0
    }
252
253
0
    if (n < 0)
254
0
        return 1;
255
0
    return sk_reserve(st, n, 1);
256
0
}
257
258
int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc)
259
2.15k
{
260
2.15k
    if (st == NULL) {
261
0
        ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
262
0
        return 0;
263
0
    }
264
2.15k
    if (st->num == max_nodes) {
265
0
        ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
266
0
        return 0;
267
0
    }
268
269
2.15k
    if (!sk_reserve(st, 1, 0))
270
0
        return 0;
271
272
2.15k
    if ((loc >= st->num) || (loc < 0)) {
273
2.15k
        st->data[st->num] = data;
274
2.15k
    } else {
275
0
        memmove(&st->data[loc + 1], &st->data[loc],
276
0
                sizeof(st->data[0]) * (st->num - loc));
277
0
        st->data[loc] = data;
278
0
    }
279
2.15k
    st->num++;
280
2.15k
    st->sorted = 0;
281
2.15k
    return st->num;
282
2.15k
}
283
284
static ossl_inline void *internal_delete(OPENSSL_STACK *st, int loc)
285
4
{
286
4
    const void *ret = st->data[loc];
287
288
4
    if (loc != st->num - 1)
289
0
        memmove(&st->data[loc], &st->data[loc + 1],
290
0
                sizeof(st->data[0]) * (st->num - loc - 1));
291
4
    st->num--;
292
293
4
    return (void *)ret;
294
4
}
295
296
void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p)
297
0
{
298
0
    int i;
299
300
0
    if (st == NULL)
301
0
        return NULL;
302
303
0
    for (i = 0; i < st->num; i++)
304
0
        if (st->data[i] == p)
305
0
            return internal_delete(st, i);
306
0
    return NULL;
307
0
}
308
309
void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
310
4
{
311
4
    if (st == NULL || loc < 0 || loc >= st->num)
312
0
        return NULL;
313
314
4
    return internal_delete(st, loc);
315
4
}
316
317
static int internal_find(OPENSSL_STACK *st, const void *data,
318
                         int ret_val_options, int *pnum_matched)
319
0
{
320
0
    const void *r;
321
0
    int i, count = 0;
322
0
    int *pnum = pnum_matched;
323
324
0
    if (st == NULL || st->num == 0)
325
0
        return -1;
326
327
0
    if (pnum == NULL)
328
0
        pnum = &count;
329
330
0
    if (st->comp == NULL) {
331
0
        for (i = 0; i < st->num; i++)
332
0
            if (st->data[i] == data) {
333
0
                *pnum = 1;
334
0
                return i;
335
0
            }
336
0
        *pnum = 0;
337
0
        return -1;
338
0
    }
339
340
0
    if (data == NULL)
341
0
        return -1;
342
343
0
    if (!st->sorted) {
344
0
        int res = -1;
345
346
0
        for (i = 0; i < st->num; i++)
347
0
            if (st->comp(&data, st->data + i) == 0) {
348
0
                if (res == -1)
349
0
                    res = i;
350
0
                ++*pnum;
351
                /* Check if only one result is wanted and exit if so */
352
0
                if (pnum_matched == NULL)
353
0
                    return i;
354
0
            }
355
0
        if (res == -1)
356
0
            *pnum = 0;
357
0
        return res;
358
0
    }
359
360
0
    if (pnum_matched != NULL)
361
0
        ret_val_options |= OSSL_BSEARCH_FIRST_VALUE_ON_MATCH;
362
0
    r = ossl_bsearch(&data, st->data, st->num, sizeof(void *), st->comp,
363
0
                     ret_val_options);
364
365
0
    if (pnum_matched != NULL) {
366
0
        *pnum = 0;
367
0
        if (r != NULL) {
368
0
            const void **p = (const void **)r;
369
370
0
            while (p < st->data + st->num) {
371
0
                if (st->comp(&data, p) != 0)
372
0
                    break;
373
0
                ++*pnum;
374
0
                ++p;
375
0
            }
376
0
        }
377
0
    }
378
379
0
    return r == NULL ? -1 : (int)((const void **)r - st->data);
380
0
}
381
382
int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
383
0
{
384
0
    return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, NULL);
385
0
}
386
387
int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
388
0
{
389
0
    return internal_find(st, data, OSSL_BSEARCH_VALUE_ON_NOMATCH, NULL);
390
0
}
391
392
int OPENSSL_sk_find_all(OPENSSL_STACK *st, const void *data, int *pnum)
393
0
{
394
0
    return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, pnum);
395
0
}
396
397
int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data)
398
2.15k
{
399
2.15k
    if (st == NULL)
400
0
        return 0;
401
2.15k
    return OPENSSL_sk_insert(st, data, st->num);
402
2.15k
}
403
404
int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data)
405
0
{
406
0
    return OPENSSL_sk_insert(st, data, 0);
407
0
}
408
409
void *OPENSSL_sk_shift(OPENSSL_STACK *st)
410
0
{
411
0
    if (st == NULL || st->num == 0)
412
0
        return NULL;
413
0
    return internal_delete(st, 0);
414
0
}
415
416
void *OPENSSL_sk_pop(OPENSSL_STACK *st)
417
0
{
418
0
    if (st == NULL || st->num == 0)
419
0
        return NULL;
420
0
    return internal_delete(st, st->num - 1);
421
0
}
422
423
void OPENSSL_sk_zero(OPENSSL_STACK *st)
424
0
{
425
0
    if (st == NULL || st->num == 0)
426
0
        return;
427
0
    memset(st->data, 0, sizeof(*st->data) * st->num);
428
0
    st->num = 0;
429
0
}
430
431
void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
432
8.15k
{
433
8.15k
    int i;
434
435
8.15k
    if (st == NULL)
436
6.84k
        return;
437
3.41k
    for (i = 0; i < st->num; i++)
438
2.11k
        if (st->data[i] != NULL)
439
2.11k
            func((char *)st->data[i]);
440
1.30k
    OPENSSL_sk_free(st);
441
1.30k
}
442
443
void OPENSSL_sk_free(OPENSSL_STACK *st)
444
18.0k
{
445
18.0k
    if (st == NULL)
446
8.47k
        return;
447
9.53k
    OPENSSL_free(st->data);
448
9.53k
    OPENSSL_free(st);
449
9.53k
}
450
451
int OPENSSL_sk_num(const OPENSSL_STACK *st)
452
30.1k
{
453
30.1k
    return st == NULL ? -1 : st->num;
454
30.1k
}
455
456
void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
457
18.2k
{
458
18.2k
    if (st == NULL || i < 0 || i >= st->num)
459
0
        return NULL;
460
18.2k
    return (void *)st->data[i];
461
18.2k
}
462
463
void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data)
464
0
{
465
0
    if (st == NULL) {
466
0
        ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
467
0
        return NULL;
468
0
    }
469
0
    if (i < 0 || i >= st->num) {
470
0
        ERR_raise_data(ERR_LIB_CRYPTO, ERR_R_PASSED_INVALID_ARGUMENT,
471
0
                       "i=%d", i);
472
0
        return NULL;
473
0
    }
474
0
    st->data[i] = data;
475
0
    st->sorted = 0;
476
0
    return (void *)st->data[i];
477
0
}
478
479
void OPENSSL_sk_sort(OPENSSL_STACK *st)
480
276
{
481
276
    if (st != NULL && !st->sorted && st->comp != NULL) {
482
276
        if (st->num > 1)
483
0
            qsort(st->data, st->num, sizeof(void *), st->comp);
484
276
        st->sorted = 1; /* empty or single-element stack is considered sorted */
485
276
    }
486
276
}
487
488
int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
489
0
{
490
0
    return st == NULL ? 1 : st->sorted;
491
0
}