Coverage Report

Created: 2024-07-27 06:35

/src/openssl/ssl/priority_queue.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2022-2023 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 <openssl/crypto.h>
11
#include <openssl/err.h>
12
#include <assert.h>
13
#include "internal/priority_queue.h"
14
#include "internal/safe_math.h"
15
#include "internal/numbers.h"
16
17
OSSL_SAFE_MATH_UNSIGNED(size_t, size_t)
18
19
/*
20
 * Fundamental operations:
21
 *                        Binary Heap   Fibonacci Heap
22
 *  Get smallest            O(1)          O(1)
23
 *  Delete any              O(log n)      O(log n) average but worst O(n)
24
 *  Insert                  O(log n)      O(1)
25
 *
26
 * Not supported:
27
 *  Merge two structures    O(log n)      O(1)
28
 *  Decrease key            O(log n)      O(1)
29
 *  Increase key            O(log n)      ?
30
 *
31
 * The Fibonacci heap is quite a bit more complicated to implement and has
32
 * larger overhead in practice.  We favour the binary heap here.  A multi-way
33
 * (ternary or quaternary) heap might elicit a performance advantage via better
34
 * cache access patterns.
35
 */
36
37
struct pq_heap_st {
38
    void *data;     /* User supplied data pointer */
39
    size_t index;   /* Constant index in elements[] */
40
};
41
42
struct pq_elem_st {
43
    size_t posn;    /* Current index in heap[] or link in free list */
44
#ifndef NDEBUG
45
    int used;       /* Debug flag indicating that this is in use */
46
#endif
47
};
48
49
struct ossl_pqueue_st {
50
    struct pq_heap_st *heap;
51
    struct pq_elem_st *elements;
52
    int (*compare)(const void *, const void *);
53
    size_t htop;        /* Highest used heap element */
54
    size_t hmax;        /* Allocated heap & element space */
55
    size_t freelist;    /* Index into elements[], start of free element list */
56
};
57
58
/*
59
 * The initial and maximum number of elements in the heap.
60
 */
61
static const size_t min_nodes = 8;
62
static const size_t max_nodes =
63
        SIZE_MAX / (sizeof(struct pq_heap_st) > sizeof(struct pq_elem_st)
64
                    ? sizeof(struct pq_heap_st) : sizeof(struct pq_elem_st));
65
66
#ifndef NDEBUG
67
/* Some basic sanity checking of the data structure */
68
# define ASSERT_USED(pq, idx)                                               \
69
40.9M
    assert(pq->elements[pq->heap[idx].index].used);                         \
70
40.4M
    assert(pq->elements[pq->heap[idx].index].posn == idx)
71
# define ASSERT_ELEM_USED(pq, elem)                                         \
72
576k
    assert(pq->elements[elem].used)
73
#else
74
# define ASSERT_USED(pq, idx)
75
# define ASSERT_ELEM_USED(pq, elem)
76
#endif
77
78
/*
79
 * Calculate the array growth based on the target size.
80
 *
81
 * The growth factor is a rational number and is defined by a numerator
82
 * and a denominator.  According to Andrew Koenig in his paper "Why Are
83
 * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
84
 * than the golden ratio (1.618...).
85
 *
86
 * We use an expansion factor of 8 / 5 = 1.6
87
 */
88
static ossl_inline size_t compute_pqueue_growth(size_t target, size_t current)
89
6.60k
{
90
6.60k
    int err = 0;
91
92
13.2k
    while (current < target) {
93
6.60k
        if (current >= max_nodes)
94
0
            return 0;
95
96
6.60k
        current = safe_muldiv_size_t(current, 8, 5, &err);
97
6.60k
        if (err)
98
0
            return 0;
99
6.60k
        if (current >= max_nodes)
100
0
            current = max_nodes;
101
6.60k
    }
102
6.60k
    return current;
103
6.60k
}
104
105
static ossl_inline void pqueue_swap_elem(OSSL_PQUEUE *pq, size_t i, size_t j)
106
8.20M
{
107
8.20M
    struct pq_heap_st *h = pq->heap, t_h;
108
8.20M
    struct pq_elem_st *e = pq->elements;
109
110
8.20M
    ASSERT_USED(pq, i);
111
16.4M
    ASSERT_USED(pq, j);
112
113
8.20M
    t_h = h[i];
114
8.20M
    h[i] = h[j];
115
8.20M
    h[j] = t_h;
116
117
8.20M
    e[h[i].index].posn = i;
118
8.20M
    e[h[j].index].posn = j;
119
8.20M
}
120
121
static ossl_inline void pqueue_move_elem(OSSL_PQUEUE *pq, size_t from, size_t to)
122
1.07M
{
123
1.07M
    struct pq_heap_st *h = pq->heap;
124
1.07M
    struct pq_elem_st *e = pq->elements;
125
126
1.07M
    ASSERT_USED(pq, from);
127
128
1.07M
    h[to] = h[from];
129
1.07M
    e[h[to].index].posn = to;
130
1.07M
}
131
132
/*
133
 * Force the specified element to the front of the heap.  This breaks
134
 * the heap partial ordering pre-condition.
135
 */
136
static ossl_inline void pqueue_force_bottom(OSSL_PQUEUE *pq, size_t n)
137
0
{
138
0
    ASSERT_USED(pq, n);
139
0
    while (n > 0) {
140
0
        const size_t p = (n - 1) / 2;
141
142
0
        ASSERT_USED(pq, p);
143
0
        pqueue_swap_elem(pq, n, p);
144
0
        n = p;
145
0
    }
146
0
}
147
148
/*
149
 * Move an element down to its correct position to restore the partial
150
 * order pre-condition.
151
 */
152
static ossl_inline void pqueue_move_down(OSSL_PQUEUE *pq, size_t n)
153
1.14M
{
154
1.14M
    struct pq_heap_st *h = pq->heap;
155
156
1.14M
    ASSERT_USED(pq, n);
157
1.83M
    while (n > 0) {
158
1.76M
        const size_t p = (n - 1) / 2;
159
160
1.76M
        ASSERT_USED(pq, p);
161
1.76M
        if (pq->compare(h[n].data, h[p].data) >= 0)
162
1.07M
            break;
163
686k
        pqueue_swap_elem(pq, n, p);
164
686k
        n = p;
165
686k
    }
166
1.14M
}
167
168
/*
169
 * Move an element up to its correct position to restore the partial
170
 * order pre-condition.
171
 */
172
static ossl_inline void pqueue_move_up(OSSL_PQUEUE *pq, size_t n)
173
1.07M
{
174
1.07M
    struct pq_heap_st *h = pq->heap;
175
1.07M
    size_t p = n * 2 + 1;
176
177
1.07M
    ASSERT_USED(pq, n);
178
1.07M
    if (pq->htop > p + 1) {
179
1.06M
        ASSERT_USED(pq, p);
180
2.13M
        ASSERT_USED(pq, p + 1);
181
1.06M
        if (pq->compare(h[p].data, h[p + 1].data) > 0)
182
263k
            p++;
183
1.06M
    }
184
8.59M
    while (pq->htop > p && pq->compare(h[p].data, h[n].data) < 0) {
185
7.51M
        ASSERT_USED(pq, p);
186
7.51M
        pqueue_swap_elem(pq, n, p);
187
7.51M
        n = p;
188
7.51M
        p = n * 2 + 1;
189
7.51M
        if (pq->htop > p + 1) {
190
7.04M
            ASSERT_USED(pq, p + 1);
191
7.04M
            if (pq->compare(h[p].data, h[p + 1].data) > 0)
192
3.31M
                p++;
193
7.04M
        }
194
7.51M
    }
195
1.07M
}
196
197
int ossl_pqueue_push(OSSL_PQUEUE *pq, void *data, size_t *elem)
198
1.14M
{
199
1.14M
    size_t n, m;
200
201
1.14M
    if (!ossl_pqueue_reserve(pq, 1))
202
0
        return 0;
203
204
1.14M
    n = pq->htop++;
205
1.14M
    m = pq->freelist;
206
1.14M
    pq->freelist = pq->elements[m].posn;
207
208
1.14M
    pq->heap[n].data = data;
209
1.14M
    pq->heap[n].index = m;
210
211
1.14M
    pq->elements[m].posn = n;
212
1.14M
#ifndef NDEBUG
213
1.14M
    pq->elements[m].used = 1;
214
1.14M
#endif
215
1.14M
    pqueue_move_down(pq, n);
216
1.14M
    if (elem != NULL)
217
1.14M
        *elem = m;
218
1.14M
    return 1;
219
1.14M
}
220
221
void *ossl_pqueue_peek(const OSSL_PQUEUE *pq)
222
2.20M
{
223
2.20M
    if (pq->htop > 0) {
224
585k
        ASSERT_USED(pq, 0);
225
585k
        return pq->heap->data;
226
585k
    }
227
1.62M
    return NULL;
228
2.20M
}
229
230
void *ossl_pqueue_pop(OSSL_PQUEUE *pq)
231
1.65M
{
232
1.65M
    void *res;
233
1.65M
    size_t elem;
234
235
1.65M
    if (pq == NULL || pq->htop == 0)
236
569k
        return NULL;
237
238
2.16M
    ASSERT_USED(pq, 0);
239
1.08M
    res = pq->heap->data;
240
1.08M
    elem = pq->heap->index;
241
242
1.08M
    if (--pq->htop != 0) {
243
1.07M
        pqueue_move_elem(pq, pq->htop, 0);
244
1.07M
        pqueue_move_up(pq, 0);
245
1.07M
    }
246
247
1.08M
    pq->elements[elem].posn = pq->freelist;
248
1.08M
    pq->freelist = elem;
249
1.08M
#ifndef NDEBUG
250
1.08M
    pq->elements[elem].used = 0;
251
1.08M
#endif
252
1.08M
    return res;
253
2.16M
}
254
255
void *ossl_pqueue_remove(OSSL_PQUEUE *pq, size_t elem)
256
576k
{
257
576k
    size_t n;
258
259
576k
    if (pq == NULL || elem >= pq->hmax || pq->htop == 0)
260
0
        return 0;
261
262
576k
    ASSERT_ELEM_USED(pq, elem);
263
576k
    n = pq->elements[elem].posn;
264
265
576k
    ASSERT_USED(pq, n);
266
267
576k
    if (n == pq->htop - 1) {
268
62.9k
        pq->elements[elem].posn = pq->freelist;
269
62.9k
        pq->freelist = elem;
270
62.9k
#ifndef NDEBUG
271
62.9k
        pq->elements[elem].used = 0;
272
62.9k
#endif
273
62.9k
        return pq->heap[--pq->htop].data;
274
62.9k
    }
275
513k
    if (n > 0)
276
0
        pqueue_force_bottom(pq, n);
277
513k
    return ossl_pqueue_pop(pq);
278
576k
}
279
280
static void pqueue_add_freelist(OSSL_PQUEUE *pq, size_t from)
281
576k
{
282
576k
    struct pq_elem_st *e = pq->elements;
283
576k
    size_t i;
284
285
576k
#ifndef NDEBUG
286
6.25M
    for (i = from; i < pq->hmax; i++)
287
5.67M
        e[i].used = 0;
288
576k
#endif
289
576k
    e[from].posn = pq->freelist;
290
5.67M
    for (i = from + 1; i < pq->hmax; i++)
291
5.10M
        e[i].posn = i - 1;
292
576k
    pq->freelist = pq->hmax - 1;
293
576k
}
294
295
int ossl_pqueue_reserve(OSSL_PQUEUE *pq, size_t n)
296
1.14M
{
297
1.14M
    size_t new_max, cur_max;
298
1.14M
    struct pq_heap_st *h;
299
1.14M
    struct pq_elem_st *e;
300
301
1.14M
    if (pq == NULL)
302
0
        return 0;
303
1.14M
    cur_max = pq->hmax;
304
1.14M
    if (pq->htop + n < cur_max)
305
1.13M
        return 1;
306
307
6.60k
    new_max = compute_pqueue_growth(n + cur_max, cur_max);
308
6.60k
    if (new_max == 0) {
309
0
        ERR_raise(ERR_LIB_SSL, ERR_R_INTERNAL_ERROR);
310
0
        return 0;
311
0
    }
312
313
6.60k
    h = OPENSSL_realloc(pq->heap, new_max * sizeof(*pq->heap));
314
6.60k
    if (h == NULL)
315
0
        return 0;
316
6.60k
    pq->heap = h;
317
318
6.60k
    e = OPENSSL_realloc(pq->elements, new_max * sizeof(*pq->elements));
319
6.60k
    if (e == NULL)
320
0
        return 0;
321
6.60k
    pq->elements = e;
322
323
6.60k
    pq->hmax = new_max;
324
6.60k
    pqueue_add_freelist(pq, cur_max);
325
6.60k
    return 1;
326
6.60k
}
327
328
OSSL_PQUEUE *ossl_pqueue_new(int (*compare)(const void *, const void *))
329
569k
{
330
569k
    OSSL_PQUEUE *pq;
331
332
569k
    if (compare == NULL)
333
0
        return NULL;
334
335
569k
    pq = OPENSSL_malloc(sizeof(*pq));
336
569k
    if (pq == NULL)
337
0
        return NULL;
338
569k
    pq->compare = compare;
339
569k
    pq->hmax = min_nodes;
340
569k
    pq->htop = 0;
341
569k
    pq->freelist = 0;
342
569k
    pq->heap = OPENSSL_malloc(sizeof(*pq->heap) * min_nodes);
343
569k
    pq->elements = OPENSSL_malloc(sizeof(*pq->elements) * min_nodes);
344
569k
    if (pq->heap == NULL || pq->elements == NULL) {
345
0
        ossl_pqueue_free(pq);
346
0
        return NULL;
347
0
    }
348
569k
    pqueue_add_freelist(pq, 0);
349
569k
    return pq;
350
569k
}
351
352
void ossl_pqueue_free(OSSL_PQUEUE *pq)
353
569k
{
354
569k
    if (pq != NULL) {
355
569k
        OPENSSL_free(pq->heap);
356
569k
        OPENSSL_free(pq->elements);
357
569k
        OPENSSL_free(pq);
358
569k
    }
359
569k
}
360
361
void ossl_pqueue_pop_free(OSSL_PQUEUE *pq, void (*freefunc)(void *))
362
0
{
363
0
    size_t i;
364
365
0
    if (pq != NULL) {
366
0
        for (i = 0; i < pq->htop; i++)
367
0
            (*freefunc)(pq->heap[i].data);
368
0
        ossl_pqueue_free(pq);
369
0
    }
370
0
}
371
372
size_t ossl_pqueue_num(const OSSL_PQUEUE *pq)
373
1.43M
{
374
1.43M
    return pq != NULL ? pq->htop : 0;
375
1.43M
}