stack.c 11 KB

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