ssl/priority_queue.c

   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  */
  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         return pq->heap[--pq->htop].data;
 269     if (n > 0)
 270         pqueue_force_bottom(pq, n);
 271     return ossl_pqueue_pop(pq);
 272 }
 273
 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
 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         return 0;
 310     pq->heap = h;
 311
 312     e = OPENSSL_realloc(pq->elements, new_max * sizeof(*pq->elements));
 313     if (e == NULL)
 314         return 0;
 315     pq->elements = e;
 316
 317     pq->hmax = new_max;
 318     pqueue_add_freelist(pq, cur_max);
 319     return 1;
 320 }
 321
 322 OSSL_PQUEUE *ossl_pqueue_new(int (*compare)(const void *, const void *))
 323 {
 324     OSSL_PQUEUE *pq;
 325
 326     if (compare == NULL)
 327         return NULL;
 328
 329     pq = OPENSSL_malloc(sizeof(*pq));
 330     if (pq == NULL)
 331         return NULL;
 332     pq->compare = compare;
 333     pq->hmax = min_nodes;
 334     pq->htop = 0;
 335     pq->freelist = 0;
 336     pq->heap = OPENSSL_malloc(sizeof(*pq->heap) * min_nodes);
 337     pq->elements = OPENSSL_malloc(sizeof(*pq->elements) * min_nodes);
 338     if (pq->heap == NULL || pq->elements == NULL) {
 339         ossl_pqueue_free(pq);
 340         return NULL;
 341     }
 342     pqueue_add_freelist(pq, 0);
 343     return pq;
 344 }
 345
 346 void ossl_pqueue_free(OSSL_PQUEUE *pq)
 347 {
 348     if (pq != NULL) {
 349         OPENSSL_free(pq->heap);
 350         OPENSSL_free(pq->elements);
 351         OPENSSL_free(pq);
 352     }
 353 }
 354
 355 void ossl_pqueue_pop_free(OSSL_PQUEUE *pq, void (*freefunc)(void *))
 356 {
 357     size_t i;
 358
 359     if (pq != NULL) {
 360         for (i = 0; i < pq->htop; i++)
 361             (*freefunc)(pq->heap[i].data);
 362         ossl_pqueue_free(pq);
 363     }
 364 }
 365
 366 size_t ossl_pqueue_num(const OSSL_PQUEUE *pq)
 367 {
 368     return pq != NULL ? pq->htop : 0;
 369 }