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