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