ssl/priority_queue.c

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