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