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