1 /*
2 * Copyright (c) 2015-2016 Los Alamos National Security, LLC. All
3 * rights reserved.
4 * Copyright (c) 2015-2016 Cray Inc. All rights reserved.
5 *
6 * This software is available to you under a choice of one of two
7 * licenses. You may choose to be licensed under the terms of the GNU
8 * General Public License (GPL) Version 2, available from the file
9 * COPYING in the main directory of this source tree, or the
10 * BSD license below:
11 *
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
14 * conditions are met:
15 *
16 * - Redistributions of source code must retain the above
17 * copyright notice, this list of conditions and the following
18 * disclaimer.
19 *
20 * - Redistributions in binary form must reproduce the above
21 * copyright notice, this list of conditions and the following
22 * disclaimer in the documentation and/or other materials
23 * provided with the distribution.
24 *
25 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
26 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
27 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
28 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
29 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
30 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
31 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
32 * SOFTWARE.
33 */
34
35 #include "gnix_buddy_allocator.h"
36 #include <criterion/criterion.h>
37 #include "gnix_rdma_headers.h"
38 #include <time.h>
39
40 #define LEN (1024 * 1024) /* buddy_handle->len */
41 #define MAX_LEN (LEN / 2) /* buddy_handle->max */
42 #define MIN_LEN MIN_BLOCK_SIZE
43
44 long *buf = NULL; /* buddy_handle->base */
45 gnix_buddy_alloc_handle_t *buddy_handle;
46
47 struct ptrs_t {
48 void *ptr; /* ptrs alloc'd by buddy_alloc */
49 uint32_t size; /* size of the ptr */
50 } *ptrs;
51
buddy_allocator_setup(void)52 void buddy_allocator_setup(void)
53 {
54 int ret;
55
56 ptrs = calloc(LEN / MIN_LEN, sizeof(struct ptrs_t));
57 cr_assert(ptrs, "buddy_allocator_setup");
58
59 buf = calloc(LEN, sizeof(long));
60 cr_assert(buf, "buddy_allocator_setup");
61
62 ret = _gnix_buddy_allocator_create(buf, LEN, MAX_LEN, &buddy_handle);
63 cr_assert(!ret, "_gnix_buddy_allocator_create");
64 }
65
buddy_allocator_teardown(void)66 void buddy_allocator_teardown(void)
67 {
68 int ret;
69
70 ret = _gnix_buddy_allocator_destroy(buddy_handle);
71 cr_assert(!ret, "_gnix_buddy_allocator_destroy");
72
73 free(ptrs);
74 free(buf);
75 }
76
77 /* Test invalid parameters for setup */
buddy_allocator_setup_error(void)78 void buddy_allocator_setup_error(void)
79 {
80 int ret;
81
82 ret = _gnix_buddy_allocator_create(NULL, LEN, MAX_LEN, &buddy_handle);
83 cr_assert_eq(ret, -FI_EINVAL);
84
85 ret = _gnix_buddy_allocator_create(buf, 0, MAX_LEN, &buddy_handle);
86 cr_assert_eq(ret, -FI_EINVAL);
87
88 ret = _gnix_buddy_allocator_create(buf, LEN, LEN + 1, &buddy_handle);
89 cr_assert_eq(ret, -FI_EINVAL);
90
91 ret = _gnix_buddy_allocator_create(buf, LEN, 0, &buddy_handle);
92 cr_assert_eq(ret, -FI_EINVAL);
93
94 ret = _gnix_buddy_allocator_create(buf, LEN, MAX_LEN, NULL);
95 cr_assert_eq(ret, -FI_EINVAL);
96 }
97
98 /* Test invalid parameters for teardown */
buddy_allocator_teardown_error(void)99 void buddy_allocator_teardown_error(void)
100 {
101 int ret;
102
103 ret = _gnix_buddy_allocator_destroy(NULL);
104 cr_assert_eq(ret, -FI_EINVAL);
105 }
106
107 /* Sequential alloc */
do_alloc(uint32_t len)108 void do_alloc(uint32_t len)
109 {
110 uint32_t i = 0, ret;
111
112 /* Allocate all the memory and write to each block */
113 for (; i < LEN / len; i++) {
114 ptrs[i].size = len;
115 ret = _gnix_buddy_alloc(buddy_handle, &ptrs[i].ptr, len);
116 cr_assert(!ret, "_gnix_buddy_alloc");
117 memset(ptrs[i].ptr, 0, len);
118 }
119
120 /* Ensure that all free lists are empty */
121 for (i = 0; i < buddy_handle->nlists; i++) {
122 ret = dlist_empty(buddy_handle->lists + i);
123 cr_assert_eq(ret, 1);
124 }
125 }
126
127 /* Sequential free */
do_free(uint32_t len)128 void do_free(uint32_t len)
129 {
130 int i = 0, ret;
131
132 /* Free all allocated blocks */
133 for (i = 0; i < LEN / len; i++) {
134 ret = _gnix_buddy_free(buddy_handle, ptrs[i].ptr, ptrs[i].size);
135 cr_assert(!ret, "_gnix_buddy_free");
136 }
137
138 /* Ensure that every free list except the last is empty */
139 for (i = 0; i < buddy_handle->nlists - 1; i++) {
140 ret = dlist_empty(buddy_handle->lists + i);
141 cr_assert_eq(ret, 1);
142 }
143 ret = dlist_empty(buddy_handle->lists + i);
144 cr_assert_eq(ret, 0);
145 }
146
147 TestSuite(buddy_allocator, .init = buddy_allocator_setup,
148 .fini = buddy_allocator_teardown, .disabled = false);
149
150 /* Sequential alloc and frees */
Test(buddy_allocator,sequential_alloc_free)151 Test(buddy_allocator, sequential_alloc_free)
152 {
153 uint32_t i = MIN_LEN;
154
155 for (i = MIN_LEN; i <= MAX_LEN; i *= 2) {
156 do_alloc(i);
157 do_free(i);
158 }
159 }
160
161 /* Pseudo random allocs and frees */
Test(buddy_allocator,random_alloc_free)162 Test(buddy_allocator, random_alloc_free)
163 {
164 int i = 0, j = 0, ret;
165
166 srand((unsigned) time(NULL));
167
168 for (j = MIN_LEN; j <= MAX_LEN; j *= 2) {
169 do {
170 ret = rand() % 100;
171
172 if (ret <= 49) {
173 /* ~50% chance to alloc min size blocks*/
174 ptrs[i].size = MIN_BLOCK_SIZE;
175 } else if (ret >= 50 &&
176 ret <= 87) {
177 /* ~37% chance to alloc blocks of size
178 * [MIN_BLOCK_SIZE * 2, MAX_BLOCK_SIZE / 2]
179 */
180 ptrs[i].size = OFFSET(MIN_BLOCK_SIZE,
181 (rand() %
182 (buddy_handle->nlists -
183 1)) + 1);
184 } else {
185 /* ~13% chance to alloc max size blocks */
186 ptrs[i].size = buddy_handle->max;
187 }
188
189 ret = _gnix_buddy_alloc(buddy_handle, &ptrs[i].ptr,
190 ptrs[i].size);
191 cr_assert_neq(ret, -FI_EINVAL);
192
193 i++;
194 } while (ret != -FI_ENOMEM);
195
196 /* Free all allocated blocks */
197 for (i -= 2; i >= 0; i--) {
198 ret = _gnix_buddy_free(buddy_handle, ptrs[i].ptr,
199 ptrs[i].size);
200 cr_assert(!ret, "_gnix_buddy_free");
201 }
202
203 /* Ensure that every free list except the last is empty */
204 for (i = 0; i < buddy_handle->nlists - 1; i++) {
205 ret = dlist_empty(buddy_handle->lists + i);
206 cr_assert_eq(ret, 1);
207 }
208 ret = dlist_empty(buddy_handle->lists + i);
209 cr_assert_eq(ret, 0);
210
211 i = 0;
212 }
213 }
214
Test(buddy_allocator,alloc_free_error)215 Test(buddy_allocator, alloc_free_error)
216 {
217 int ret;
218 void *tmp;
219
220 do_alloc(MIN_LEN);
221
222 /* Request one additional block */
223 ret = _gnix_buddy_alloc(buddy_handle, &tmp, MIN_LEN);
224 cr_assert_eq(ret, -FI_ENOMEM);
225
226 do_free(MIN_LEN);
227 }
228
229 /* Test invalid buddy alloc and free parameters */
Test(buddy_allocator,parameter_error)230 Test(buddy_allocator, parameter_error)
231 {
232 int ret;
233
234 buddy_allocator_setup_error();
235 buddy_allocator_teardown_error();
236
237 /* BEGIN: Alloc, invalid parameters */
238 ret = _gnix_buddy_alloc(NULL, ptrs->ptr, MAX_LEN);
239 cr_assert_eq(ret, -FI_EINVAL);
240
241 ret = _gnix_buddy_alloc(buddy_handle, ptrs->ptr, MAX_LEN + 1);
242 cr_assert_eq(ret, -FI_EINVAL);
243
244 ret = _gnix_buddy_alloc(buddy_handle, ptrs->ptr, 0);
245 cr_assert_eq(ret, -FI_EINVAL);
246
247 ret = _gnix_buddy_alloc(buddy_handle, NULL, MAX_LEN);
248 cr_assert_eq(ret, -FI_EINVAL);
249 /* END: Alloc, invalid parameters */
250
251 /* BEGIN: Free, invalid parameters */
252 ret = _gnix_buddy_free(NULL, ptrs->ptr, MAX_LEN);
253 cr_assert_eq(ret, -FI_EINVAL);
254
255 ret = _gnix_buddy_free(buddy_handle, NULL, MAX_LEN);
256 cr_assert_eq(ret, -FI_EINVAL);
257
258 ret = _gnix_buddy_free(buddy_handle, buf - 1, MAX_LEN);
259 cr_assert_eq(ret, -FI_EINVAL);
260
261 ret = _gnix_buddy_free(buddy_handle, buf + LEN, MAX_LEN);
262 cr_assert_eq(ret, -FI_EINVAL);
263
264 ret = _gnix_buddy_free(buddy_handle, buf, MAX_LEN + 1);
265 cr_assert_eq(ret, -FI_EINVAL);
266
267 ret = _gnix_buddy_free(buddy_handle, buf - 1, 0);
268 cr_assert_eq(ret, -FI_EINVAL);
269 /* END: Free, invalid parameters */
270 }
271