1 /*
2 * Copyright 2022-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 <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 = SIZE_MAX / (sizeof(struct pq_heap_st) > sizeof(struct pq_elem_st) ? sizeof(struct pq_heap_st) : sizeof(struct pq_elem_st));
63
64 #ifndef NDEBUG
65 /* Some basic sanity checking of the data structure */
66 #define ASSERT_USED(pq, idx) \
67 assert(pq->elements[pq->heap[idx].index].used); \
68 assert(pq->elements[pq->heap[idx].index].posn == idx)
69 #define ASSERT_ELEM_USED(pq, elem) \
70 assert(pq->elements[elem].used)
71 #else
72 #define ASSERT_USED(pq, idx)
73 #define ASSERT_ELEM_USED(pq, elem)
74 #endif
75
76 /*
77 * Calculate the array growth based on the target size.
78 *
79 * The growth factor is a rational number and is defined by a numerator
80 * and a denominator. According to Andrew Koenig in his paper "Why Are
81 * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
82 * than the golden ratio (1.618...).
83 *
84 * We use an expansion factor of 8 / 5 = 1.6
85 */
compute_pqueue_growth(size_t target,size_t current)86 static ossl_inline size_t compute_pqueue_growth(size_t target, size_t current)
87 {
88 int err = 0;
89
90 while (current < target) {
91 if (current >= max_nodes)
92 return 0;
93
94 current = safe_muldiv_size_t(current, 8, 5, &err);
95 if (err)
96 return 0;
97 if (current >= max_nodes)
98 current = max_nodes;
99 }
100 return current;
101 }
102
pqueue_swap_elem(OSSL_PQUEUE * pq,size_t i,size_t j)103 static ossl_inline void pqueue_swap_elem(OSSL_PQUEUE *pq, size_t i, size_t j)
104 {
105 struct pq_heap_st *h = pq->heap, t_h;
106 struct pq_elem_st *e = pq->elements;
107
108 ASSERT_USED(pq, i);
109 ASSERT_USED(pq, j);
110
111 t_h = h[i];
112 h[i] = h[j];
113 h[j] = t_h;
114
115 e[h[i].index].posn = i;
116 e[h[j].index].posn = j;
117 }
118
pqueue_move_elem(OSSL_PQUEUE * pq,size_t from,size_t to)119 static ossl_inline void pqueue_move_elem(OSSL_PQUEUE *pq, size_t from, size_t to)
120 {
121 struct pq_heap_st *h = pq->heap;
122 struct pq_elem_st *e = pq->elements;
123
124 ASSERT_USED(pq, from);
125
126 h[to] = h[from];
127 e[h[to].index].posn = to;
128 }
129
130 /*
131 * Force the specified element to the front of the heap. This breaks
132 * the heap partial ordering pre-condition.
133 */
pqueue_force_bottom(OSSL_PQUEUE * pq,size_t n)134 static ossl_inline void pqueue_force_bottom(OSSL_PQUEUE *pq, size_t n)
135 {
136 ASSERT_USED(pq, n);
137 while (n > 0) {
138 const size_t p = (n - 1) / 2;
139
140 ASSERT_USED(pq, p);
141 pqueue_swap_elem(pq, n, p);
142 n = p;
143 }
144 }
145
146 /*
147 * Move an element down to its correct position to restore the partial
148 * order pre-condition.
149 */
pqueue_move_down(OSSL_PQUEUE * pq,size_t n)150 static ossl_inline void pqueue_move_down(OSSL_PQUEUE *pq, size_t n)
151 {
152 struct pq_heap_st *h = pq->heap;
153
154 ASSERT_USED(pq, n);
155 while (n > 0) {
156 const size_t p = (n - 1) / 2;
157
158 ASSERT_USED(pq, p);
159 if (pq->compare(h[n].data, h[p].data) >= 0)
160 break;
161 pqueue_swap_elem(pq, n, p);
162 n = p;
163 }
164 }
165
166 /*
167 * Move an element up to its correct position to restore the partial
168 * order pre-condition.
169 */
pqueue_move_up(OSSL_PQUEUE * pq,size_t n)170 static ossl_inline void pqueue_move_up(OSSL_PQUEUE *pq, size_t n)
171 {
172 struct pq_heap_st *h = pq->heap;
173 size_t p = n * 2 + 1;
174
175 ASSERT_USED(pq, n);
176 if (pq->htop > p + 1) {
177 ASSERT_USED(pq, p);
178 ASSERT_USED(pq, p + 1);
179 if (pq->compare(h[p].data, h[p + 1].data) > 0)
180 p++;
181 }
182 while (pq->htop > p && pq->compare(h[p].data, h[n].data) < 0) {
183 ASSERT_USED(pq, p);
184 pqueue_swap_elem(pq, n, p);
185 n = p;
186 p = n * 2 + 1;
187 if (pq->htop > p + 1) {
188 ASSERT_USED(pq, p + 1);
189 if (pq->compare(h[p].data, h[p + 1].data) > 0)
190 p++;
191 }
192 }
193 }
194
ossl_pqueue_push(OSSL_PQUEUE * pq,void * data,size_t * elem)195 int ossl_pqueue_push(OSSL_PQUEUE *pq, void *data, size_t *elem)
196 {
197 size_t n, m;
198
199 if (!ossl_pqueue_reserve(pq, 1))
200 return 0;
201
202 n = pq->htop++;
203 m = pq->freelist;
204 pq->freelist = pq->elements[m].posn;
205
206 pq->heap[n].data = data;
207 pq->heap[n].index = m;
208
209 pq->elements[m].posn = n;
210 #ifndef NDEBUG
211 pq->elements[m].used = 1;
212 #endif
213 pqueue_move_down(pq, n);
214 if (elem != NULL)
215 *elem = m;
216 return 1;
217 }
218
ossl_pqueue_peek(const OSSL_PQUEUE * pq)219 void *ossl_pqueue_peek(const OSSL_PQUEUE *pq)
220 {
221 if (pq->htop > 0) {
222 ASSERT_USED(pq, 0);
223 return pq->heap->data;
224 }
225 return NULL;
226 }
227
ossl_pqueue_pop(OSSL_PQUEUE * pq)228 void *ossl_pqueue_pop(OSSL_PQUEUE *pq)
229 {
230 void *res;
231 size_t elem;
232
233 if (pq == NULL || pq->htop == 0)
234 return NULL;
235
236 ASSERT_USED(pq, 0);
237 res = pq->heap->data;
238 elem = pq->heap->index;
239
240 if (--pq->htop != 0) {
241 pqueue_move_elem(pq, pq->htop, 0);
242 pqueue_move_up(pq, 0);
243 }
244
245 pq->elements[elem].posn = pq->freelist;
246 pq->freelist = elem;
247 #ifndef NDEBUG
248 pq->elements[elem].used = 0;
249 #endif
250 return res;
251 }
252
ossl_pqueue_remove(OSSL_PQUEUE * pq,size_t elem)253 void *ossl_pqueue_remove(OSSL_PQUEUE *pq, size_t elem)
254 {
255 size_t n;
256
257 if (pq == NULL || elem >= pq->hmax || pq->htop == 0)
258 return 0;
259
260 ASSERT_ELEM_USED(pq, elem);
261 n = pq->elements[elem].posn;
262
263 ASSERT_USED(pq, n);
264
265 if (n == pq->htop - 1) {
266 pq->elements[elem].posn = pq->freelist;
267 pq->freelist = elem;
268 #ifndef NDEBUG
269 pq->elements[elem].used = 0;
270 #endif
271 return pq->heap[--pq->htop].data;
272 }
273 if (n > 0)
274 pqueue_force_bottom(pq, n);
275 return ossl_pqueue_pop(pq);
276 }
277
pqueue_add_freelist(OSSL_PQUEUE * pq,size_t from)278 static void pqueue_add_freelist(OSSL_PQUEUE *pq, size_t from)
279 {
280 struct pq_elem_st *e = pq->elements;
281 size_t i;
282
283 #ifndef NDEBUG
284 for (i = from; i < pq->hmax; i++)
285 e[i].used = 0;
286 #endif
287 e[from].posn = pq->freelist;
288 for (i = from + 1; i < pq->hmax; i++)
289 e[i].posn = i - 1;
290 pq->freelist = pq->hmax - 1;
291 }
292
ossl_pqueue_reserve(OSSL_PQUEUE * pq,size_t n)293 int ossl_pqueue_reserve(OSSL_PQUEUE *pq, size_t n)
294 {
295 size_t new_max, cur_max;
296 struct pq_heap_st *h;
297 struct pq_elem_st *e;
298
299 if (pq == NULL)
300 return 0;
301 cur_max = pq->hmax;
302 if (pq->htop + n < cur_max)
303 return 1;
304
305 new_max = compute_pqueue_growth(n + cur_max, cur_max);
306 if (new_max == 0) {
307 ERR_raise(ERR_LIB_SSL, ERR_R_INTERNAL_ERROR);
308 return 0;
309 }
310
311 h = OPENSSL_realloc(pq->heap, new_max * sizeof(*pq->heap));
312 if (h == NULL)
313 return 0;
314 pq->heap = h;
315
316 e = OPENSSL_realloc(pq->elements, new_max * sizeof(*pq->elements));
317 if (e == NULL)
318 return 0;
319 pq->elements = e;
320
321 pq->hmax = new_max;
322 pqueue_add_freelist(pq, cur_max);
323 return 1;
324 }
325
ossl_pqueue_new(int (* compare)(const void *,const void *))326 OSSL_PQUEUE *ossl_pqueue_new(int (*compare)(const void *, const void *))
327 {
328 OSSL_PQUEUE *pq;
329
330 if (compare == NULL)
331 return NULL;
332
333 pq = OPENSSL_malloc(sizeof(*pq));
334 if (pq == NULL)
335 return NULL;
336 pq->compare = compare;
337 pq->hmax = min_nodes;
338 pq->htop = 0;
339 pq->freelist = 0;
340 pq->heap = OPENSSL_malloc(sizeof(*pq->heap) * min_nodes);
341 pq->elements = OPENSSL_malloc(sizeof(*pq->elements) * min_nodes);
342 if (pq->heap == NULL || pq->elements == NULL) {
343 ossl_pqueue_free(pq);
344 return NULL;
345 }
346 pqueue_add_freelist(pq, 0);
347 return pq;
348 }
349
ossl_pqueue_free(OSSL_PQUEUE * pq)350 void ossl_pqueue_free(OSSL_PQUEUE *pq)
351 {
352 if (pq != NULL) {
353 OPENSSL_free(pq->heap);
354 OPENSSL_free(pq->elements);
355 OPENSSL_free(pq);
356 }
357 }
358
ossl_pqueue_pop_free(OSSL_PQUEUE * pq,void (* freefunc)(void *))359 void ossl_pqueue_pop_free(OSSL_PQUEUE *pq, void (*freefunc)(void *))
360 {
361 size_t i;
362
363 if (pq != NULL) {
364 for (i = 0; i < pq->htop; i++)
365 (*freefunc)(pq->heap[i].data);
366 ossl_pqueue_free(pq);
367 }
368 }
369
ossl_pqueue_num(const OSSL_PQUEUE * pq)370 size_t ossl_pqueue_num(const OSSL_PQUEUE *pq)
371 {
372 return pq != NULL ? pq->htop : 0;
373 }
374