crypto/stack/stack.c

   1 /*
   2  * Copyright 1995-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 <stdio.h>
  11 #include "internal/cryptlib.h"
  12 #include "internal/numbers.h"
  13 #include "internal/safe_math.h"
  14 #include <openssl/stack.h>
  15 #include <errno.h>
  16 #include <openssl/e_os2.h>      /* For ossl_inline */
  17
  18 OSSL_SAFE_MATH_SIGNED(int, int)
  19
  20 /*
  21  * The initial number of nodes in the array.
  22  */
  23 static const int min_nodes = 4;
  24 static const int max_nodes = SIZE_MAX / sizeof(void *) < INT_MAX
  25     ? (int)(SIZE_MAX / sizeof(void *)) : INT_MAX;
  26
  27 struct stack_st {
  28     int num;
  29     const void **data;
  30     int sorted;
  31     int num_alloc;
  32     OPENSSL_sk_compfunc comp;
  33     OPENSSL_sk_freefunc_thunk free_thunk;
  34 };
  35
  36 OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk,
  37                                             OPENSSL_sk_compfunc c)
  38 {
  39     OPENSSL_sk_compfunc old = sk->comp;
  40
  41     if (sk->comp != c)
  42         sk->sorted = 0;
  43     sk->comp = c;
  44
  45     return old;
  46 }
  47
  48 OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
  49 {
  50     OPENSSL_STACK *ret;
  51
  52     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
  53         goto err;
  54
  55     if (sk == NULL) {
  56         ret->num = 0;
  57         ret->sorted = 0;
  58         ret->comp = NULL;
  59     } else {
  60         /* direct structure assignment */
  61         *ret = *sk;
  62     }
  63
  64     if (sk == NULL || sk->num == 0) {
  65         /* postpone |ret->data| allocation */
  66         ret->data = NULL;
  67         ret->num_alloc = 0;
  68         return ret;
  69     }
  70
  71     /* duplicate |sk->data| content */
  72     ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc);
  73     if (ret->data == NULL)
  74         goto err;
  75     memcpy(ret->data, sk->data, sizeof(void *) * sk->num);
  76     return ret;
  77
  78  err:
  79     OPENSSL_sk_free(ret);
  80     return NULL;
  81 }
  82
  83 OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,
  84                                     OPENSSL_sk_copyfunc copy_func,
  85                                     OPENSSL_sk_freefunc free_func)
  86 {
  87     OPENSSL_STACK *ret;
  88     int i;
  89
  90     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
  91         goto err;
  92
  93     if (sk == NULL) {
  94         ret->num = 0;
  95         ret->sorted = 0;
  96         ret->comp = NULL;
  97     } else {
  98         /* direct structure assignment */
  99         *ret = *sk;
 100     }
 101
 102     if (sk == NULL || sk->num == 0) {
 103         /* postpone |ret| data allocation */
 104         ret->data = NULL;
 105         ret->num_alloc = 0;
 106         return ret;
 107     }
 108
 109     ret->num_alloc = sk->num > min_nodes ? sk->num : min_nodes;
 110     ret->data = OPENSSL_zalloc(sizeof(*ret->data) * ret->num_alloc);
 111     if (ret->data == NULL)
 112         goto err;
 113
 114     for (i = 0; i < ret->num; ++i) {
 115         if (sk->data[i] == NULL)
 116             continue;
 117         if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {
 118             while (--i >= 0)
 119                 if (ret->data[i] != NULL)
 120                     free_func((void *)ret->data[i]);
 121             goto err;
 122         }
 123     }
 124     return ret;
 125
 126  err:
 127     OPENSSL_sk_free(ret);
 128     return NULL;
 129 }
 130
 131 OPENSSL_STACK *OPENSSL_sk_new_null(void)
 132 {
 133     return OPENSSL_sk_new_reserve(NULL, 0);
 134 }
 135
 136 OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
 137 {
 138     return OPENSSL_sk_new_reserve(c, 0);
 139 }
 140
 141 /*
 142  * Calculate the array growth based on the target size.
 143  *
 144  * The growth factor is a rational number and is defined by a numerator
 145  * and a denominator.  According to Andrew Koenig in his paper "Why Are
 146  * Vectors Efficient?" from JOOP 11(5) 1998, this factor should be less
 147  * than the golden ratio (1.618...).
 148  *
 149  * Considering only the Fibonacci ratios less than the golden ratio, the
 150  * number of steps from the minimum allocation to integer overflow is:
 151  *      factor  decimal    growths
 152  *       3/2     1.5          51
 153  *       8/5     1.6          45
 154  *      21/13    1.615...     44
 155  *
 156  * All larger factors have the same number of growths.
 157  *
 158  * 3/2 and 8/5 have nice power of two shifts, so seem like a good choice.
 159  */
 160 static ossl_inline int compute_growth(int target, int current)
 161 {
 162     int err = 0;
 163
 164     while (current < target) {
 165         if (current >= max_nodes)
 166             return 0;
 167
 168         current = safe_muldiv_int(current, 8, 5, &err);
 169         if (err != 0)
 170             return 0;
 171         if (current >= max_nodes)
 172             current = max_nodes;
 173     }
 174     return current;
 175 }
 176
 177 /* internal STACK storage allocation */
 178 static int sk_reserve(OPENSSL_STACK *st, int n, int exact)
 179 {
 180     const void **tmpdata;
 181     int num_alloc;
 182
 183     /* Check to see the reservation isn't exceeding the hard limit */
 184     if (n > max_nodes - st->num) {
 185         ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
 186         return 0;
 187     }
 188
 189     /* Figure out the new size */
 190     num_alloc = st->num + n;
 191     if (num_alloc < min_nodes)
 192         num_alloc = min_nodes;
 193
 194     /* If |st->data| allocation was postponed */
 195     if (st->data == NULL) {
 196         /*
 197          * At this point, |st->num_alloc| and |st->num| are 0;
 198          * so |num_alloc| value is |n| or |min_nodes| if greater than |n|.
 199          */
 200         if ((st->data = OPENSSL_zalloc(sizeof(void *) * num_alloc)) == NULL)
 201             return 0;
 202         st->num_alloc = num_alloc;
 203         return 1;
 204     }
 205
 206     if (!exact) {
 207         if (num_alloc <= st->num_alloc)
 208             return 1;
 209         num_alloc = compute_growth(num_alloc, st->num_alloc);
 210         if (num_alloc == 0) {
 211             ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
 212             return 0;
 213         }
 214     } else if (num_alloc == st->num_alloc) {
 215         return 1;
 216     }
 217
 218     tmpdata = OPENSSL_realloc((void *)st->data, sizeof(void *) * num_alloc);
 219     if (tmpdata == NULL)
 220         return 0;
 221
 222     st->data = tmpdata;
 223     st->num_alloc = num_alloc;
 224     return 1;
 225 }
 226
 227 OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n)
 228 {
 229     OPENSSL_STACK *st = OPENSSL_zalloc(sizeof(OPENSSL_STACK));
 230
 231     if (st == NULL)
 232         return NULL;
 233
 234     st->comp = c;
 235
 236     if (n <= 0)
 237         return st;
 238
 239     if (!sk_reserve(st, n, 1)) {
 240         OPENSSL_sk_free(st);
 241         return NULL;
 242     }
 243
 244     return st;
 245 }
 246
 247 int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n)
 248 {
 249     if (st == NULL) {
 250         ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
 251         return 0;
 252     }
 253
 254     if (n < 0)
 255         return 1;
 256     return sk_reserve(st, n, 1);
 257 }
 258
 259 OPENSSL_STACK *OPENSSL_sk_set_thunks(OPENSSL_STACK *st, OPENSSL_sk_freefunc_thunk f_thunk)
 260 {
 261     if (st != NULL)
 262         st->free_thunk = f_thunk;
 263
 264     return st;
 265 }
 266
 267 int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc)
 268 {
 269     if (st == NULL) {
 270         ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
 271         return 0;
 272     }
 273     if (st->num == max_nodes) {
 274         ERR_raise(ERR_LIB_CRYPTO, CRYPTO_R_TOO_MANY_RECORDS);
 275         return 0;
 276     }
 277
 278     if (!sk_reserve(st, 1, 0))
 279         return 0;
 280
 281     if ((loc >= st->num) || (loc < 0)) {
 282         st->data[st->num] = data;
 283     } else {
 284         memmove(&st->data[loc + 1], &st->data[loc],
 285                 sizeof(st->data[0]) * (st->num - loc));
 286         st->data[loc] = data;
 287     }
 288     st->num++;
 289     st->sorted = 0;
 290     return st->num;
 291 }
 292
 293 static ossl_inline void *internal_delete(OPENSSL_STACK *st, int loc)
 294 {
 295     const void *ret = st->data[loc];
 296
 297     if (loc != st->num - 1)
 298         memmove(&st->data[loc], &st->data[loc + 1],
 299                 sizeof(st->data[0]) * (st->num - loc - 1));
 300     st->num--;
 301
 302     return (void *)ret;
 303 }
 304
 305 void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p)
 306 {
 307     int i;
 308
 309     if (st == NULL)
 310         return NULL;
 311
 312     for (i = 0; i < st->num; i++)
 313         if (st->data[i] == p)
 314             return internal_delete(st, i);
 315     return NULL;
 316 }
 317
 318 void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
 319 {
 320     if (st == NULL || loc < 0 || loc >= st->num)
 321         return NULL;
 322
 323     return internal_delete(st, loc);
 324 }
 325
 326 static int internal_find(OPENSSL_STACK *st, const void *data,
 327                          int ret_val_options, int *pnum_matched)
 328 {
 329     const void *r;
 330     int i, count = 0;
 331     int *pnum = pnum_matched;
 332
 333     if (st == NULL || st->num == 0)
 334         return -1;
 335
 336     if (pnum == NULL)
 337         pnum = &count;
 338
 339     if (st->comp == NULL) {
 340         for (i = 0; i < st->num; i++)
 341             if (st->data[i] == data) {
 342                 *pnum = 1;
 343                 return i;
 344             }
 345         *pnum = 0;
 346         return -1;
 347     }
 348
 349     if (data == NULL)
 350         return -1;
 351
 352     if (!st->sorted) {
 353         int res = -1;
 354
 355         for (i = 0; i < st->num; i++)
 356             if (st->comp(&data, st->data + i) == 0) {
 357                 if (res == -1)
 358                     res = i;
 359                 ++*pnum;
 360                 /* Check if only one result is wanted and exit if so */
 361                 if (pnum_matched == NULL)
 362                     return i;
 363             }
 364         if (res == -1)
 365             *pnum = 0;
 366         return res;
 367     }
 368
 369     if (pnum_matched != NULL)
 370         ret_val_options |= OSSL_BSEARCH_FIRST_VALUE_ON_MATCH;
 371     r = ossl_bsearch(&data, st->data, st->num, sizeof(void *), st->comp,
 372                      ret_val_options);
 373
 374     if (pnum_matched != NULL) {
 375         *pnum = 0;
 376         if (r != NULL) {
 377             const void **p = (const void **)r;
 378
 379             while (p < st->data + st->num) {
 380                 if (st->comp(&data, p) != 0)
 381                     break;
 382                 ++*pnum;
 383                 ++p;
 384             }
 385         }
 386     }
 387
 388     return r == NULL ? -1 : (int)((const void **)r - st->data);
 389 }
 390
 391 int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
 392 {
 393     return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, NULL);
 394 }
 395
 396 int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
 397 {
 398     return internal_find(st, data, OSSL_BSEARCH_VALUE_ON_NOMATCH, NULL);
 399 }
 400
 401 int OPENSSL_sk_find_all(OPENSSL_STACK *st, const void *data, int *pnum)
 402 {
 403     return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, pnum);
 404 }
 405
 406 int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data)
 407 {
 408     if (st == NULL)
 409         return 0;
 410     return OPENSSL_sk_insert(st, data, st->num);
 411 }
 412
 413 int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data)
 414 {
 415     return OPENSSL_sk_insert(st, data, 0);
 416 }
 417
 418 void *OPENSSL_sk_shift(OPENSSL_STACK *st)
 419 {
 420     if (st == NULL || st->num == 0)
 421         return NULL;
 422     return internal_delete(st, 0);
 423 }
 424
 425 void *OPENSSL_sk_pop(OPENSSL_STACK *st)
 426 {
 427     if (st == NULL || st->num == 0)
 428         return NULL;
 429     return internal_delete(st, st->num - 1);
 430 }
 431
 432 void OPENSSL_sk_zero(OPENSSL_STACK *st)
 433 {
 434     if (st == NULL || st->num == 0)
 435         return;
 436     memset(st->data, 0, sizeof(*st->data) * st->num);
 437     st->num = 0;
 438 }
 439
 440 void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
 441 {
 442     int i;
 443
 444     if (st == NULL)
 445         return;
 446
 447     for (i = 0; i < st->num; i++) {
 448         if (st->data[i] != NULL) {
 449             if (st->free_thunk != NULL)
 450                 st->free_thunk(func, (void *)st->data[i]);
 451             else
 452                 func((void *)st->data[i]);
 453         }
 454     }
 455     OPENSSL_sk_free(st);
 456 }
 457
 458 void OPENSSL_sk_free(OPENSSL_STACK *st)
 459 {
 460     if (st == NULL)
 461         return;
 462     OPENSSL_free(st->data);
 463     OPENSSL_free(st);
 464 }
 465
 466 int OPENSSL_sk_num(const OPENSSL_STACK *st)
 467 {
 468     return st == NULL ? -1 : st->num;
 469 }
 470
 471 void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
 472 {
 473     if (st == NULL || i < 0 || i >= st->num)
 474         return NULL;
 475     return (void *)st->data[i];
 476 }
 477
 478 void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data)
 479 {
 480     if (st == NULL) {
 481         ERR_raise(ERR_LIB_CRYPTO, ERR_R_PASSED_NULL_PARAMETER);
 482         return NULL;
 483     }
 484     if (i < 0 || i >= st->num) {
 485         ERR_raise_data(ERR_LIB_CRYPTO, ERR_R_PASSED_INVALID_ARGUMENT,
 486                        "i=%d", i);
 487         return NULL;
 488     }
 489     st->data[i] = data;
 490     st->sorted = 0;
 491     return (void *)st->data[i];
 492 }
 493
 494 void OPENSSL_sk_sort(OPENSSL_STACK *st)
 495 {
 496     if (st != NULL && !st->sorted && st->comp != NULL) {
 497         if (st->num > 1)
 498             qsort(st->data, st->num, sizeof(void *), st->comp);
 499         st->sorted = 1; /* empty or single-element stack is considered sorted */
 500     }
 501 }
 502
 503 int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
 504 {
 505     return st == NULL ? 1 : st->sorted;
 506 }