xref: /freebsd/contrib/netbsd-tests/kernel/t_extent.c (revision 39ee7a7a6bdd1557b1c3532abf60d139798ac88b)
1 /* $NetBSD: t_extent.c,v 1.4 2012/01/27 18:53:10 para Exp $ */
2 
3 /*-
4  * Copyright (c) 2008 The NetBSD Foundation, Inc.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
17  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
18  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
20  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26  * POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 #include <sys/cdefs.h>
30 __COPYRIGHT("@(#) Copyright (c) 2008\
31  The NetBSD Foundation, inc. All rights reserved.");
32 __RCSID("$NetBSD: t_extent.c,v 1.4 2012/01/27 18:53:10 para Exp $");
33 
34 #include <sys/types.h>
35 #include <sys/queue.h>
36 #include <sys/extent.h>
37 
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <string.h>
41 
42 #include <atf-c.h>
43 
44 #include "../h_macros.h"
45 
46 static int ret;
47 static struct extent *ex;
48 
49 #define h_create(name, start, end, flags) \
50 	ATF_REQUIRE((ex = extent_create(name, \
51 	    start, end, 0, 0, flags)) != NULL);
52 
53 #define h_alloc_region(start, size) \
54 	ATF_REQUIRE_EQ_MSG(ret = extent_alloc_region(ex, \
55 	    start, size, 0), 0, "%s", strerror(ret));
56 
57 #define h_free(start, size) \
58 	ATF_REQUIRE_EQ_MSG(ret = extent_free(ex, \
59 	    start, size, 0), 0, "%s", strerror(ret));
60 
61 static void
62 h_alloc_subregion(u_long substart, u_long subend, u_long size,
63     u_long alignment, u_long boundary, int expret, u_long expres)
64 {
65 	u_long result;
66 
67 #define FAIL(fmt, ...) \
68 	atf_tc_fail("extent_alloc_subregion1(ex, %#lx, %#lx, %#lx, %#lx, 0, " \
69 	    "%#lx, 0, &result): " fmt, substart, subend, size, alignment, \
70 	    boundary, ##__VA_ARGS__)
71 
72 	ret = extent_alloc_subregion1(ex, substart, subend, size,
73 	    alignment, 0, boundary, 0, &result);
74 
75 	if (ret != expret)
76 		FAIL("%s", strerror(errno));
77 
78 	if (expret == 0 && result != expres)
79 		FAIL("result should be: %#lx, got: %#lx", expres, result);
80 #undef FAIL
81 }
82 
83 static void
84 h_require(const char *name, u_long start,
85 	u_long end, int flags, const char *exp)
86 {
87 	char buf[4096];
88 	struct extent_region *rp;
89 	int n = 0;
90 
91 	ATF_REQUIRE_STREQ_MSG(ex->ex_name, name,
92 	    "expected: \"%s\", got: \"%s\"", name, ex->ex_name);
93 	ATF_REQUIRE_EQ_MSG(ex->ex_start, start,
94 	    "expected: %#lx, got: %#lx", start, ex->ex_start);
95 	ATF_REQUIRE_EQ_MSG(ex->ex_end, end,
96 	    "expected: %#lx, got: %#lx", end, ex->ex_end);
97 	ATF_REQUIRE_EQ_MSG(ex->ex_flags, flags,
98 	    "expected: %#x, got: %#x", flags, ex->ex_flags);
99 
100 	(void)memset(buf, 0, sizeof(buf));
101 	LIST_FOREACH(rp, &ex->ex_regions, er_link)
102 		n += snprintf(buf + n, sizeof(buf) - n,
103 		    "0x%lx - 0x%lx\n", rp->er_start, rp->er_end);
104 
105 	if (strcmp(buf, exp) == 0)
106 		return;
107 
108 	printf("Incorrect extent map\n");
109 	printf("Expected:\n%s\n", exp);
110 	printf("Got:\n%s\n", buf);
111 	atf_tc_fail("incorrect extent map");
112 }
113 
114 ATF_TC(coalesce);
115 ATF_TC_HEAD(coalesce, tc)
116 {
117 	atf_tc_set_md_var(tc, "descr", "Checks coalescing of regions");
118 }
119 ATF_TC_BODY(coalesce, tc)
120 {
121 	h_create("test1", 0, 0x4f, 0);
122 
123 	h_alloc_region(0x00, 0x10);
124 	h_alloc_region(0x20, 0x10);
125 	h_alloc_region(0x40, 0x10);
126 	h_alloc_region(0x10, 0x10);
127 	h_alloc_subregion(0, 0x4f, 0x10, EX_NOALIGN, EX_NOBOUNDARY, 0, 0x30);
128 
129 	h_require("test1", 0x00, 0x4f, 0x00,
130 	    "0x0 - 0x4f\n");
131 
132 	extent_destroy(ex);
133 }
134 
135 ATF_TC(subregion1);
136 ATF_TC_HEAD(subregion1, tc)
137 {
138 	atf_tc_set_md_var(tc, "descr",
139 	    "Checks that subregions work (PR kern/7539)");
140 }
141 ATF_TC_BODY(subregion1, tc)
142 {
143 	h_create("test2", 0, 0x2f, EX_NOCOALESCE);
144 
145 	h_alloc_region(0x00, 0x10);
146 	h_alloc_subregion(0x20, 0x30, 0x10, EX_NOALIGN, EX_NOBOUNDARY, 0, 0x20);
147 
148 	h_require("test2", 0x00, 0x2f, 0x2,
149 	    "0x0 - 0xf\n"
150 	    "0x20 - 0x2f\n");
151 
152 	extent_destroy(ex);
153 }
154 
155 ATF_TC(subregion2);
156 ATF_TC_HEAD(subregion2, tc)
157 {
158 	atf_tc_set_md_var(tc, "descr",
159 	    "Checks that subregion allocations don't overlap with existing "
160 	    "ones (fixed in 1.25)");
161 }
162 ATF_TC_BODY(subregion2, tc)
163 {
164 	h_create("test3", 0, 0x3f, EX_NOCOALESCE);
165 
166 	h_alloc_region(0x00, 0x20);
167 	h_alloc_region(0x30, 0x10);
168 	h_alloc_subregion(0x10, 0x3f, 0x10,
169 	    EX_NOALIGN, EX_NOBOUNDARY, 0, 0x20);
170 
171 	h_require("test3", 0x00, 0x3f, 0x2,
172 	    "0x0 - 0x1f\n"
173 	    "0x20 - 0x2f\n"
174 	    "0x30 - 0x3f\n");
175 
176 	extent_destroy(ex);
177 }
178 
179 ATF_TC(bound1);
180 ATF_TC_HEAD(bound1, tc)
181 {
182 	atf_tc_set_md_var(tc, "descr",
183 	    "Checks for overflow in boundary check, before an allocated region "
184 	    "(fixed in 1.32)");
185 }
186 ATF_TC_BODY(bound1, tc)
187 {
188 	h_create("test4", 0xf0000000, 0xffffffff, 0);
189 
190 	h_alloc_region(0xf1000000, 0x1);
191 	h_alloc_subregion(0xf0000000, 0xffffffff, 0x1,
192 	    EX_NOALIGN, 0x20000000, 0, 0xf0000000);
193 
194 	h_require("test4", 0xf0000000, 0xffffffff, 0x0,
195 	    "0xf0000000 - 0xf0000000\n"
196 	    "0xf1000000 - 0xf1000000\n");
197 
198 	extent_destroy(ex);
199 }
200 
201 ATF_TC(bound2);
202 ATF_TC_HEAD(bound2, tc)
203 {
204 	atf_tc_set_md_var(tc, "descr",
205 	    "Checks for overflow in boundary checks, before the subregion end "
206 	    "(fixed in 1.32)");
207 }
208 ATF_TC_BODY(bound2, tc)
209 {
210 	h_create("test5", 0xf0000000, 0xffffffff, 0);
211 
212 	h_alloc_subregion(0xf0000000, 0xffffffff, 0x1,
213 	    EX_NOALIGN, 0x20000000, 0, 0xf0000000);
214 
215 	h_require("test5", 0xf0000000, 0xffffffff, 0x0,
216 	    "0xf0000000 - 0xf0000000\n");
217 
218 	extent_destroy(ex);
219 }
220 
221 ATF_TC(bound3);
222 ATF_TC_HEAD(bound3, tc)
223 {
224 	atf_tc_set_md_var(tc, "descr",
225 	    "Checks allocation beyond last boundary line: last two "
226 	    "allocations should succeed without boundary \"fixups\"");
227 }
228 ATF_TC_BODY(bound3, tc)
229 {
230 	h_create("test6", 0, 11, 0);
231 
232 	h_alloc_subregion(0, 11, 8, EX_NOALIGN, 8, 0, 0);
233 	h_alloc_subregion(0, 11, 2, EX_NOALIGN, 8, 0, 0x8);
234 	h_alloc_subregion(0, 11, 2, EX_NOALIGN, 8, 0, 0xa);
235 
236 	h_require("test6", 0x0, 0xb, 0x0, "0x0 - 0xb\n");
237 
238 	extent_destroy(ex);
239 }
240 
241 ATF_TC(bound4);
242 ATF_TC_HEAD(bound4, tc)
243 {
244 	atf_tc_set_md_var(tc, "descr",
245 	    "Checks allocation beyond last boundary line: last allocation "
246 	    "should be bumped to the next boundary and exactly fit the "
247 	    "remaining space");
248 }
249 ATF_TC_BODY(bound4, tc)
250 {
251 	h_create("test7", 0, 11, 0);
252 
253 	h_alloc_subregion(0, 11, 7, EX_NOALIGN, 8, 0, 0);
254 	h_alloc_subregion(0, 11, 4, EX_NOALIGN, 8, 0, 8);
255 
256 	h_require("test7", 0x0, 0xb, 0x0,
257 	    "0x0 - 0x6\n"
258 	    "0x8 - 0xb\n");
259 
260 	extent_destroy(ex);
261 }
262 
263 ATF_TC(subregion3);
264 ATF_TC_HEAD(subregion3, tc)
265 {
266 	atf_tc_set_md_var(tc, "descr",
267 	    "Checks that we don't allocate a region pasts the end of "
268 	    "subregion (i.e., the second alloc_subregion should fail). "
269 	    "subr_extent.c prior to rev. 1.43 allocated region starting "
270 	    "from 0x10");
271 }
272 ATF_TC_BODY(subregion3, tc)
273 {
274 	h_create("test8", 0, 0x4f, EX_NOCOALESCE);
275 
276 	h_alloc_region(0x30, 0x10);
277 	h_alloc_subregion(0, 0xf, 0x10, EX_NOALIGN, EX_NOBOUNDARY, 0, 0);
278 	h_alloc_subregion(0, 0xf, 0x10, EX_NOALIGN, EX_NOBOUNDARY, EAGAIN, 0);
279 
280 	h_require("test8", 0x0, 0x4f, 0x2,
281 	    "0x0 - 0xf\n"
282 	    "0x30 - 0x3f\n");
283 
284 	extent_destroy(ex);
285 }
286 
287 ATF_TC(bound5);
288 ATF_TC_HEAD(bound5, tc)
289 {
290 	atf_tc_set_md_var(tc, "descr",
291 	    "When allocating a region with a boundary constraint, checks "
292 	    "proper detection of overflaps once the candidate region has "
293 	    "been aligned. subr_extent.c prior 1.45 could corrupt the extent "
294 	    "map in this situation");
295 }
296 ATF_TC_BODY(bound5, tc)
297 {
298 	h_create("test9", 0, 0x4f, 0);
299 
300 	h_alloc_subregion(0, 0x10, 4, EX_NOALIGN, 0, 0, 0);
301 	h_alloc_subregion(0xd, 0x20, 2, EX_NOALIGN, 0, 0, 0xd);
302 	h_alloc_subregion(0, 0x4f, 8, EX_NOALIGN, 8, 0, 0x10);
303 
304 	h_require("test9", 0x0, 0x4f, 0x0,
305 	    "0x0 - 0x3\n"
306 	    "0xd - 0xe\n"
307 	    "0x10 - 0x17\n");
308 
309 	extent_destroy(ex);
310 }
311 
312 ATF_TC(free);
313 ATF_TC_HEAD(free, tc)
314 {
315 	atf_tc_set_md_var(tc, "descr", "Checks extent_free()");
316 }
317 ATF_TC_BODY(free, tc)
318 {
319 	h_create("test10", 0xc0002000, 0xffffe000, EX_BOUNDZERO);
320 
321 	h_alloc_subregion(0xc0002000, 0xffffe000, 0x2000,
322 	    0x10000, 0x10000, 0, 0xc0010000);
323 	h_alloc_subregion(0xc0002000, 0xffffe000, 0x2000,
324 	    0x10000, 0x10000, 0, 0xc0020000);
325 
326 	h_require("test10", 0xc0002000, 0xffffe000, 0x0,
327 	    "0xc0010000 - 0xc0011fff\n"
328 	    "0xc0020000 - 0xc0021fff\n");
329 
330 	h_free(0xc0020000, 0x2000);
331 	h_require("test10", 0xc0002000, 0xffffe000, 0x0,
332 	    "0xc0010000 - 0xc0011fff\n");
333 
334 	h_alloc_subregion(0xc0002000, 0xffffe000, 0x10000,
335 	    0x10000, 0x10000, 0, 0xc0022000);
336 
337 	h_require("test10", 0xc0002000, 0xffffe000, 0x0,
338 	    "0xc0010000 - 0xc0011fff\n"
339 	    "0xc0022000 - 0xc0031fff\n");
340 
341 	extent_destroy(ex);
342 }
343 
344 ATF_TC(subregion4);
345 ATF_TC_HEAD(subregion4, tc)
346 {
347 	atf_tc_set_md_var(tc, "descr",
348 	    "Checks for off-by-one bug which would cause a region at the end "
349 	    "of the extent to be allocated multiple times (fixed in 1.51)");
350 }
351 ATF_TC_BODY(subregion4, tc)
352 {
353 	h_create("test11", 0x10, 0x20, EX_NOCOALESCE);
354 
355 	h_alloc_subregion(0x10, 0x13, 0x4, EX_NOALIGN, EX_NOBOUNDARY, 0, 0x10);
356 	h_alloc_subregion(0x1e, 0x1f, 0x2, EX_NOALIGN, EX_NOBOUNDARY, 0, 0x1e);
357 	h_alloc_subregion(0x20, 0x20, 0x1, EX_NOALIGN, EX_NOBOUNDARY, 0, 0x20);
358 	h_alloc_subregion(0x20, 0x20, 0x1, EX_NOALIGN, EX_NOBOUNDARY, EAGAIN, 0);
359 	h_alloc_subregion(0x10, 0x20, 0x1, EX_NOALIGN, EX_NOBOUNDARY, 0, 0x14);
360 
361 	h_require("test11", 0x10, 0x20, 0x2,
362 	    "0x10 - 0x13\n"
363 	    "0x14 - 0x14\n"
364 	    "0x1e - 0x1f\n"
365 	    "0x20 - 0x20\n");
366 
367 	extent_destroy(ex);
368 }
369 
370 ATF_TP_ADD_TCS(tp)
371 {
372 	ATF_TP_ADD_TC(tp, coalesce);
373 	ATF_TP_ADD_TC(tp, subregion1);
374 	ATF_TP_ADD_TC(tp, subregion2);
375 	ATF_TP_ADD_TC(tp, bound1);
376 	ATF_TP_ADD_TC(tp, bound2);
377 	ATF_TP_ADD_TC(tp, bound3);
378 	ATF_TP_ADD_TC(tp, bound4);
379 	ATF_TP_ADD_TC(tp, subregion3);
380 	ATF_TP_ADD_TC(tp, bound5);
381 	ATF_TP_ADD_TC(tp, free);
382 	ATF_TP_ADD_TC(tp, subregion4);
383 
384 	return atf_no_error();
385 }
386