1 /*
2 * Copyright 2022 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
16 OSSL_SAFE_MATH_UNSIGNED(size_t, size_t)
17
18 /*
19 * Fundamental operations:
20 * Binary Heap Fibonacci Heap
21 * Get smallest O(1) O(1)
22 * Delete any O(log n) O(log n) average but worst O(n)
23 * Insert O(log n) O(1)
24 *
25 * Not supported:
26 * Merge two structures O(log n) O(1)
27 * Decrease key O(log n) O(1)
28 * Increase key O(log n) ?
29 *
30 * The Fibonacci heap is quite a bit more complicated to implement and has
31 * larger overhead in practice. We favour the binary heap here. A multi-way
32 * (ternary or quaternary) heap might elicit a performance advantage via better
33 * cache access patterns.
34 */
35
36 struct pq_heap_st {
37 void *data; /* User supplied data pointer */
38 size_t index; /* Constant index in elements[] */
39 };
40
41 struct pq_elem_st {
42 size_t posn; /* Current index in heap[] or link in free list */
43 #ifndef NDEBUG
44 int used; /* Debug flag indicating that this is in use */
45 #endif
46 };
47
48 struct ossl_pqueue_st
49 {
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 assert(pq->elements[pq->heap[idx].index].used); \
70 assert(pq->elements[pq->heap[idx].index].posn == idx)
71 # define ASSERT_ELEM_USED(pq, elem) \
72 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 */
compute_pqueue_growth(size_t target,size_t current)88 static ossl_inline int compute_pqueue_growth(size_t target, size_t current)
89 {
90 int err = 0;
91
92 while (current < target) {
93 if (current >= max_nodes)
94 return 0;
95
96 current = safe_muldiv_size_t(current, 8, 5, &err);
97 if (err)
98 return 0;
99 if (current >= max_nodes)
100 current = max_nodes;
101 }
102 return current;
103 }
104
pqueue_swap_elem(OSSL_PQUEUE * pq,size_t i,size_t j)105 static ossl_inline void pqueue_swap_elem(OSSL_PQUEUE *pq, size_t i, size_t j)
106 {
107 struct pq_heap_st *h = pq->heap, t_h;
108 struct pq_elem_st *e = pq->elements;
109
110 ASSERT_USED(pq, i);
111 ASSERT_USED(pq, j);
112
113 t_h = h[i];
114 h[i] = h[j];
115 h[j] = t_h;
116
117 e[h[i].index].posn = i;
118 e[h[j].index].posn = j;
119 }
120
pqueue_move_elem(OSSL_PQUEUE * pq,size_t from,size_t to)121 static ossl_inline void pqueue_move_elem(OSSL_PQUEUE *pq, size_t from, size_t to)
122 {
123 struct pq_heap_st *h = pq->heap;
124 struct pq_elem_st *e = pq->elements;
125
126 ASSERT_USED(pq, from);
127
128 h[to] = h[from];
129 e[h[to].index].posn = to;
130 }
131
132 /*
133 * Force the specified element to the front of the heap. This breaks
134 * the heap partial ordering pre-condition.
135 */
pqueue_force_bottom(OSSL_PQUEUE * pq,size_t n)136 static ossl_inline void pqueue_force_bottom(OSSL_PQUEUE *pq, size_t n)
137 {
138 ASSERT_USED(pq, n);
139 while (n > 0) {
140 const size_t p = (n - 1) / 2;
141
142 ASSERT_USED(pq, p);
143 pqueue_swap_elem(pq, n, p);
144 n = p;
145 }
146 }
147
148 /*
149 * Move an element down to its correct position to restore the partial
150 * order pre-condition.
151 */
pqueue_move_down(OSSL_PQUEUE * pq,size_t n)152 static ossl_inline void pqueue_move_down(OSSL_PQUEUE *pq, size_t n)
153 {
154 struct pq_heap_st *h = pq->heap;
155
156 ASSERT_USED(pq, n);
157 while (n > 0) {
158 const size_t p = (n - 1) / 2;
159
160 ASSERT_USED(pq, p);
161 if (pq->compare(h[n].data, h[p].data) >= 0)
162 break;
163 pqueue_swap_elem(pq, n, p);
164 n = p;
165 }
166 }
167
168 /*
169 * Move an element up to its correct position to restore the partial
170 * order pre-condition.
171 */
pqueue_move_up(OSSL_PQUEUE * pq,size_t n)172 static ossl_inline void pqueue_move_up(OSSL_PQUEUE *pq, size_t n)
173 {
174 struct pq_heap_st *h = pq->heap;
175 size_t p = n * 2 + 1;
176
177 ASSERT_USED(pq, n);
178 if (pq->htop > p + 1) {
179 ASSERT_USED(pq, p);
180 ASSERT_USED(pq, p + 1);
181 if (pq->compare(h[p].data, h[p + 1].data) > 0)
182 p++;
183 }
184 while (pq->htop > p && pq->compare(h[p].data, h[n].data) < 0) {
185 ASSERT_USED(pq, p);
186 pqueue_swap_elem(pq, n, p);
187 n = p;
188 p = n * 2 + 1;
189 if (pq->htop > p + 1) {
190 ASSERT_USED(pq, p + 1);
191 if (pq->compare(h[p].data, h[p + 1].data) > 0)
192 p++;
193 }
194 }
195 }
196
ossl_pqueue_push(OSSL_PQUEUE * pq,void * data,size_t * elem)197 int ossl_pqueue_push(OSSL_PQUEUE *pq, void *data, size_t *elem)
198 {
199 size_t n, m;
200
201 if (!ossl_pqueue_reserve(pq, 1))
202 return 0;
203
204 n = pq->htop++;
205 m = pq->freelist;
206 pq->freelist = pq->elements[m].posn;
207
208 pq->heap[n].data = data;
209 pq->heap[n].index = m;
210
211 pq->elements[m].posn = n;
212 #ifndef NDEBUG
213 pq->elements[m].used = 1;
214 #endif
215 pqueue_move_down(pq, n);
216 if (elem != NULL)
217 *elem = m;
218 return 1;
219 }
220
ossl_pqueue_peek(const OSSL_PQUEUE * pq)221 void *ossl_pqueue_peek(const OSSL_PQUEUE *pq)
222 {
223 if (pq->htop > 0) {
224 ASSERT_USED(pq, 0);
225 return pq->heap->data;
226 }
227 return NULL;
228 }
229
ossl_pqueue_pop(OSSL_PQUEUE * pq)230 void *ossl_pqueue_pop(OSSL_PQUEUE *pq)
231 {
232 void *res;
233 size_t elem;
234
235 if (pq == NULL || pq->htop == 0)
236 return NULL;
237
238 ASSERT_USED(pq, 0);
239 res = pq->heap->data;
240 elem = pq->heap->index;
241
242 if (--pq->htop != 0) {
243 pqueue_move_elem(pq, pq->htop, 0);
244 pqueue_move_up(pq, 0);
245 }
246
247 pq->elements[elem].posn = pq->freelist;
248 pq->freelist = elem;
249 #ifndef NDEBUG
250 pq->elements[elem].used = 0;
251 #endif
252 return res;
253 }
254
ossl_pqueue_remove(OSSL_PQUEUE * pq,size_t elem)255 void *ossl_pqueue_remove(OSSL_PQUEUE *pq, size_t elem)
256 {
257 size_t n;
258
259 if (pq == NULL || elem >= pq->hmax || pq->htop == 0)
260 return 0;
261
262 ASSERT_ELEM_USED(pq, elem);
263 n = pq->elements[elem].posn;
264
265 ASSERT_USED(pq, n);
266
267 if (n == pq->htop - 1)
268 return pq->heap[--pq->htop].data;
269 if (n > 0)
270 pqueue_force_bottom(pq, n);
271 return ossl_pqueue_pop(pq);
272 }
273
pqueue_add_freelist(OSSL_PQUEUE * pq,size_t from)274 static void pqueue_add_freelist(OSSL_PQUEUE *pq, size_t from)
275 {
276 struct pq_elem_st *e = pq->elements;
277 size_t i;
278
279 #ifndef NDEBUG
280 for (i = from; i < pq->hmax; i++)
281 e[i].used = 0;
282 #endif
283 e[from].posn = pq->freelist;
284 for (i = from + 1; i < pq->hmax; i++)
285 e[i].posn = i - 1;
286 pq->freelist = pq->hmax - 1;
287 }
288
ossl_pqueue_reserve(OSSL_PQUEUE * pq,size_t n)289 int ossl_pqueue_reserve(OSSL_PQUEUE *pq, size_t n)
290 {
291 size_t new_max, cur_max;
292 struct pq_heap_st *h;
293 struct pq_elem_st *e;
294
295 if (pq == NULL)
296 return 0;
297 cur_max = pq->hmax;
298 if (pq->htop + n < cur_max)
299 return 1;
300
301 new_max = compute_pqueue_growth(n + cur_max, cur_max);
302 if (new_max == 0) {
303 ERR_raise(ERR_LIB_SSL, ERR_R_INTERNAL_ERROR);
304 return 0;
305 }
306
307 h = OPENSSL_realloc(pq->heap, new_max * sizeof(*pq->heap));
308 if (h == NULL) {
309 ERR_raise(ERR_LIB_SSL, ERR_R_MALLOC_FAILURE);
310 return 0;
311 }
312 pq->heap = h;
313
314 e = OPENSSL_realloc(pq->elements, new_max * sizeof(*pq->elements));
315 if (e == NULL) {
316 ERR_raise(ERR_LIB_SSL, ERR_R_MALLOC_FAILURE);
317 return 0;
318 }
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 ERR_raise(ERR_LIB_SSL, ERR_R_MALLOC_FAILURE);
336 return NULL;
337 }
338 pq->compare = compare;
339 pq->hmax = min_nodes;
340 pq->htop = 0;
341 pq->freelist = 0;
342 pq->heap = OPENSSL_malloc(sizeof(*pq->heap) * min_nodes);
343 pq->elements = OPENSSL_malloc(sizeof(*pq->elements) * min_nodes);
344 if (pq->heap == NULL || pq->elements == NULL) {
345 ossl_pqueue_free(pq);
346 ERR_raise(ERR_LIB_SSL, ERR_R_MALLOC_FAILURE);
347 return NULL;
348 }
349 pqueue_add_freelist(pq, 0);
350 return pq;
351 }
352
ossl_pqueue_free(OSSL_PQUEUE * pq)353 void ossl_pqueue_free(OSSL_PQUEUE *pq)
354 {
355 if (pq != NULL) {
356 OPENSSL_free(pq->heap);
357 OPENSSL_free(pq->elements);
358 OPENSSL_free(pq);
359 }
360 }
361
ossl_pqueue_pop_free(OSSL_PQUEUE * pq,void (* freefunc)(void *))362 void ossl_pqueue_pop_free(OSSL_PQUEUE *pq, void (*freefunc)(void *))
363 {
364 size_t i;
365
366 if (pq != NULL) {
367 for (i = 0; i < pq->htop; i++)
368 (*freefunc)(pq->heap[i].data);
369 ossl_pqueue_free(pq);
370 }
371 }
372
ossl_pqueue_num(const OSSL_PQUEUE * pq)373 size_t ossl_pqueue_num(const OSSL_PQUEUE *pq)
374 {
375 return pq != NULL ? pq->htop : 0;
376 }
377
