Branch data Line data Source code
1 : : /*
2 : : * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
3 : : *
4 : : * Licensed under the Apache License, Version 2.0 (the "License").
5 : : * You may not use this file except in compliance with the License.
6 : : * A copy of the License is located at
7 : : *
8 : : * http://aws.amazon.com/apache2.0
9 : : *
10 : : * or in the "license" file accompanying this file. This file is distributed
11 : : * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
12 : : * express or implied. See the License for the specific language governing
13 : : * permissions and limitations under the License.
14 : : */
15 : :
16 : : #include "utils/s2n_array.h"
17 : :
18 : : #include <sys/param.h>
19 : :
20 : : #include "utils/s2n_blob.h"
21 : : #include "utils/s2n_mem.h"
22 : : #include "utils/s2n_safety.h"
23 : :
24 : : S2N_RESULT s2n_array_validate(const struct s2n_array *array)
25 : 7890346 : {
26 : 7890346 : uint32_t mem_size = 0;
27 [ + + ][ + - ]: 7890346 : RESULT_ENSURE_REF(array);
28 [ - + ]: 7890344 : RESULT_GUARD(s2n_blob_validate(&array->mem));
29 [ # # ][ - + ]: 7890344 : RESULT_ENSURE_NE(array->element_size, 0);
30 [ - + ]: 7890344 : RESULT_GUARD_POSIX(s2n_mul_overflow(array->len, array->element_size, &mem_size));
31 [ - + ][ # # ]: 7890344 : RESULT_ENSURE_GTE(array->mem.size, mem_size);
32 [ # # ][ + - ]: 7890344 : RESULT_ENSURE(S2N_IMPLIES(array->mem.size, array->mem.growable), S2N_ERR_SAFETY);
[ + + ]
33 : 7890344 : return S2N_RESULT_OK;
34 : 7890344 : }
35 : :
36 : : static S2N_RESULT s2n_array_enlarge(struct s2n_array *array, uint32_t capacity)
37 : 6969672 : {
38 [ - + ][ # # ]: 6969672 : RESULT_ENSURE_REF(array);
39 : :
40 : : /* Acquire the memory */
41 : 6969672 : uint32_t mem_needed = 0;
42 [ + + ]: 6969672 : RESULT_GUARD_POSIX(s2n_mul_overflow(array->element_size, capacity, &mem_needed));
43 [ - + ]: 6969671 : RESULT_GUARD_POSIX(s2n_realloc(&array->mem, mem_needed));
44 : :
45 : : /* Zero the extened part */
46 : 6969671 : uint32_t array_elements_size = 0;
47 [ - + ]: 6969671 : RESULT_GUARD_POSIX(s2n_mul_overflow(array->element_size, array->len, &array_elements_size));
48 [ - + ][ # # ]: 6969671 : RESULT_CHECKED_MEMSET(array->mem.data + array_elements_size, 0, array->mem.size - array_elements_size);
[ + + ]
49 [ - + ][ + - ]: 6969671 : RESULT_POSTCONDITION(s2n_array_validate(array));
50 : 6969671 : return S2N_RESULT_OK;
51 : 6969671 : }
52 : :
53 : : struct s2n_array *s2n_array_new(uint32_t element_size)
54 : 1454 : {
55 : 1454 : struct s2n_array *array = s2n_array_new_with_capacity(element_size, S2N_INITIAL_ARRAY_SIZE);
56 [ + + ][ + - ]: 1454 : PTR_ENSURE_REF(array);
57 : :
58 : 1453 : return array;
59 : 1454 : }
60 : :
61 : : struct s2n_array *s2n_array_new_with_capacity(uint32_t element_size, uint32_t capacity)
62 : 1616 : {
63 : 1616 : DEFER_CLEANUP(struct s2n_blob mem = { 0 }, s2n_free);
64 [ - + ]: 1616 : PTR_GUARD_POSIX(s2n_alloc(&mem, sizeof(struct s2n_array)));
65 : :
66 : 1616 : DEFER_CLEANUP(struct s2n_array *array = (void *) mem.data, s2n_array_free_p);
67 : 1616 : ZERO_TO_DISABLE_DEFER_CLEANUP(mem);
68 : :
69 [ + + ]: 1616 : PTR_GUARD_RESULT(s2n_array_init_with_capacity(array, element_size, capacity));
70 : :
71 : 1615 : struct s2n_array *array_ret = array;
72 : 1615 : ZERO_TO_DISABLE_DEFER_CLEANUP(array);
73 : :
74 : 1615 : return array_ret;
75 : 1616 : }
76 : :
77 : : S2N_RESULT s2n_array_init(struct s2n_array *array, uint32_t element_size)
78 : 6966658 : {
79 [ - + ][ # # ]: 6966658 : RESULT_ENSURE_REF(array);
80 : :
81 [ - + ]: 6966658 : RESULT_GUARD(s2n_array_init_with_capacity(array, element_size, 0));
82 : :
83 : 6966658 : return S2N_RESULT_OK;
84 : 6966658 : }
85 : :
86 : : S2N_RESULT s2n_array_init_with_capacity(struct s2n_array *array, uint32_t element_size, uint32_t capacity)
87 : 6968274 : {
88 [ - + ][ # # ]: 6968274 : RESULT_ENSURE_REF(array);
89 : :
90 : 6968274 : *array = (struct s2n_array){ .element_size = element_size };
91 : :
92 [ + + ]: 6968274 : RESULT_GUARD(s2n_array_enlarge(array, capacity));
93 : :
94 : 6968273 : return S2N_RESULT_OK;
95 : 6968274 : }
96 : :
97 : : S2N_RESULT s2n_array_pushback(struct s2n_array *array, void **element)
98 : 2936 : {
99 [ + + ][ + + ]: 2936 : RESULT_PRECONDITION(s2n_array_validate(array));
100 [ - + ][ # # ]: 2935 : RESULT_ENSURE_REF(element);
101 : 2935 : return s2n_array_insert(array, array->len, element);
102 : 2935 : }
103 : :
104 : : S2N_RESULT s2n_array_get(struct s2n_array *array, uint32_t idx, void **element)
105 : 899415 : {
106 [ + + ][ + + ]: 899415 : RESULT_PRECONDITION(s2n_array_validate(array));
107 [ - + ][ # # ]: 899414 : RESULT_ENSURE_REF(element);
108 [ + - ][ + + ]: 899414 : RESULT_ENSURE(idx < array->len, S2N_ERR_ARRAY_INDEX_OOB);
109 : 893150 : *element = array->mem.data + (array->element_size * idx);
110 : 893150 : return S2N_RESULT_OK;
111 : 899414 : }
112 : :
113 : : S2N_RESULT s2n_array_insert_and_copy(struct s2n_array *array, uint32_t idx, void *element)
114 : 1467 : {
115 : 1467 : void *insert_location = NULL;
116 [ - + ]: 1467 : RESULT_GUARD(s2n_array_insert(array, idx, &insert_location));
117 [ # # ][ - + ]: 1467 : RESULT_CHECKED_MEMCPY(insert_location, element, array->element_size);
[ + - ]
118 : 1467 : return S2N_RESULT_OK;
119 : 1467 : }
120 : :
121 : : S2N_RESULT s2n_array_insert(struct s2n_array *array, uint32_t idx, void **element)
122 : 4403 : {
123 [ - + ][ + - ]: 4403 : RESULT_PRECONDITION(s2n_array_validate(array));
124 [ - + ][ # # ]: 4403 : RESULT_ENSURE_REF(element);
125 : : /* index == len is ok since we're about to add one element */
126 [ - + ][ # # ]: 4403 : RESULT_ENSURE(idx <= array->len, S2N_ERR_ARRAY_INDEX_OOB);
127 : :
128 : : /* We are about to add one more element to the array. Add capacity if necessary */
129 : 4403 : uint32_t current_capacity = 0;
130 [ - + ]: 4403 : RESULT_GUARD(s2n_array_capacity(array, ¤t_capacity));
131 : :
132 [ + + ]: 4403 : if (array->len >= current_capacity) {
133 : : /* Enlarge the array */
134 : 1398 : uint32_t new_capacity = 0;
135 [ - + ]: 1398 : RESULT_GUARD_POSIX(s2n_mul_overflow(current_capacity, 2, &new_capacity));
136 : 1398 : new_capacity = MAX(new_capacity, S2N_INITIAL_ARRAY_SIZE);
137 [ - + ]: 1398 : RESULT_GUARD(s2n_array_enlarge(array, new_capacity));
138 : 1398 : }
139 : :
140 : : /* If we are adding at an existing index, slide everything down. */
141 [ + + ]: 4403 : if (idx < array->len) {
142 : 1 : uint32_t size = 0;
143 [ - + ]: 1 : RESULT_GUARD_POSIX(s2n_mul_overflow(array->len - idx, array->element_size, &size));
144 : 1 : memmove(array->mem.data + array->element_size * (idx + 1),
145 : 1 : array->mem.data + array->element_size * idx,
146 : 1 : size);
147 : 1 : }
148 : :
149 : 4403 : *element = array->mem.data + array->element_size * idx;
150 : 4403 : array->len++;
151 : :
152 [ - + ][ + - ]: 4403 : RESULT_POSTCONDITION(s2n_array_validate(array));
153 : 4403 : return S2N_RESULT_OK;
154 : 4403 : }
155 : :
156 : : S2N_RESULT s2n_array_remove(struct s2n_array *array, uint32_t idx)
157 : 5 : {
158 [ - + ][ + - ]: 5 : RESULT_PRECONDITION(s2n_array_validate(array));
159 [ - + ][ # # ]: 5 : RESULT_ENSURE(idx < array->len, S2N_ERR_ARRAY_INDEX_OOB);
160 : :
161 : : /* If the removed element is the last one, no need to move anything.
162 : : * Otherwise, shift everything down */
163 [ + + ]: 5 : if (idx != array->len - 1) {
164 : 2 : uint32_t size = 0;
165 [ - + ]: 2 : RESULT_GUARD_POSIX(s2n_mul_overflow(array->len - idx - 1, array->element_size, &size));
166 : 2 : memmove(array->mem.data + array->element_size * idx,
167 : 2 : array->mem.data + array->element_size * (idx + 1),
168 : 2 : size);
169 : 2 : }
170 : 5 : array->len--;
171 : :
172 : : /* After shifting, zero the last element */
173 [ # # ][ - + ]: 5 : RESULT_CHECKED_MEMSET(array->mem.data + array->element_size * array->len,
[ + - ]
174 : 5 : 0,
175 : 5 : array->element_size);
176 : :
177 [ - + ][ + - ]: 5 : RESULT_POSTCONDITION(s2n_array_validate(array));
178 : 5 : return S2N_RESULT_OK;
179 : 5 : }
180 : :
181 : : S2N_RESULT s2n_array_num_elements(struct s2n_array *array, uint32_t *len)
182 : 4794 : {
183 [ - + ][ + - ]: 4794 : RESULT_PRECONDITION(s2n_array_validate(array));
184 [ - + ][ # # ]: 4794 : RESULT_ENSURE_MUT(len);
185 : :
186 : 4794 : *len = array->len;
187 : :
188 : 4794 : return S2N_RESULT_OK;
189 : 4794 : }
190 : :
191 : : S2N_RESULT s2n_array_capacity(struct s2n_array *array, uint32_t *capacity)
192 : 4714 : {
193 [ - + ][ + - ]: 4714 : RESULT_PRECONDITION(s2n_array_validate(array));
194 [ - + ][ # # ]: 4714 : RESULT_ENSURE_MUT(capacity);
195 : :
196 : 4714 : *capacity = array->mem.size / array->element_size;
197 : :
198 : 4714 : return S2N_RESULT_OK;
199 : 4714 : }
200 : :
201 : : S2N_CLEANUP_RESULT s2n_array_free_p(struct s2n_array **parray)
202 : 4698 : {
203 [ - + ][ # # ]: 4698 : RESULT_ENSURE_REF(parray);
204 : :
205 : 4698 : struct s2n_array *array = *parray;
206 [ + + ]: 4698 : if (array == NULL) {
207 : 3082 : return S2N_RESULT_OK;
208 : 3082 : }
209 : :
210 : : /* Free the elements */
211 [ - + ]: 1616 : RESULT_GUARD_POSIX(s2n_free(&array->mem));
212 : :
213 : : /* And finally the array */
214 [ - + ]: 1616 : RESULT_GUARD_POSIX(s2n_free_object((uint8_t **) parray, sizeof(struct s2n_array)));
215 : :
216 : 1616 : return S2N_RESULT_OK;
217 : 1616 : }
218 : :
219 : : S2N_RESULT s2n_array_free(struct s2n_array *array)
220 : 1470 : {
221 [ + - ][ + + ]: 1470 : RESULT_ENSURE_REF(array);
222 : 1469 : return s2n_array_free_p(&array);
223 : 1470 : }
|
