/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 | } |