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 = 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 */ 88 static ossl_inline size_t 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 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 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 */ 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 */ 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 */ 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 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 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 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 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 pq->elements[elem].posn = pq->freelist; 269 pq->freelist = elem; 270 #ifndef NDEBUG 271 pq->elements[elem].used = 0; 272 #endif 273 return pq->heap[--pq->htop].data; 274 } 275 if (n > 0) 276 pqueue_force_bottom(pq, n); 277 return ossl_pqueue_pop(pq); 278 } 279 280 static void pqueue_add_freelist(OSSL_PQUEUE *pq, size_t from) 281 { 282 struct pq_elem_st *e = pq->elements; 283 size_t i; 284 285 #ifndef NDEBUG 286 for (i = from; i < pq->hmax; i++) 287 e[i].used = 0; 288 #endif 289 e[from].posn = pq->freelist; 290 for (i = from + 1; i < pq->hmax; i++) 291 e[i].posn = i - 1; 292 pq->freelist = pq->hmax - 1; 293 } 294 295 int ossl_pqueue_reserve(OSSL_PQUEUE *pq, size_t n) 296 { 297 size_t new_max, cur_max; 298 struct pq_heap_st *h; 299 struct pq_elem_st *e; 300 301 if (pq == NULL) 302 return 0; 303 cur_max = pq->hmax; 304 if (pq->htop + n < cur_max) 305 return 1; 306 307 new_max = compute_pqueue_growth(n + cur_max, cur_max); 308 if (new_max == 0) { 309 ERR_raise(ERR_LIB_SSL, ERR_R_INTERNAL_ERROR); 310 return 0; 311 } 312 313 h = OPENSSL_realloc(pq->heap, new_max * sizeof(*pq->heap)); 314 if (h == NULL) 315 return 0; 316 pq->heap = h; 317 318 e = OPENSSL_realloc(pq->elements, new_max * sizeof(*pq->elements)); 319 if (e == NULL) 320 return 0; 321 pq->elements = e; 322 323 pq->hmax = new_max; 324 pqueue_add_freelist(pq, cur_max); 325 return 1; 326 } 327 328 OSSL_PQUEUE *ossl_pqueue_new(int (*compare)(const void *, const void *)) 329 { 330 OSSL_PQUEUE *pq; 331 332 if (compare == NULL) 333 return NULL; 334 335 pq = OPENSSL_malloc(sizeof(*pq)); 336 if (pq == NULL) 337 return NULL; 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 return NULL; 347 } 348 pqueue_add_freelist(pq, 0); 349 return pq; 350 } 351 352 void ossl_pqueue_free(OSSL_PQUEUE *pq) 353 { 354 if (pq != NULL) { 355 OPENSSL_free(pq->heap); 356 OPENSSL_free(pq->elements); 357 OPENSSL_free(pq); 358 } 359 } 360 361 void ossl_pqueue_pop_free(OSSL_PQUEUE *pq, void (*freefunc)(void *)) 362 { 363 size_t i; 364 365 if (pq != NULL) { 366 for (i = 0; i < pq->htop; i++) 367 (*freefunc)(pq->heap[i].data); 368 ossl_pqueue_free(pq); 369 } 370 } 371 372 size_t ossl_pqueue_num(const OSSL_PQUEUE *pq) 373 { 374 return pq != NULL ? pq->htop : 0; 375 } 376