t_extent.c revision 314817
1/* $NetBSD: t_extent.c,v 1.5 2017/01/13 21:30:41 christos 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.5 2017/01/13 21:30:41 christos 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 46static int ret; 47static 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 61static void 62h_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 83static void 84h_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 114ATF_TC(coalesce); 115ATF_TC_HEAD(coalesce, tc) 116{ 117 atf_tc_set_md_var(tc, "descr", "Checks coalescing of regions"); 118} 119ATF_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 135ATF_TC(subregion1); 136ATF_TC_HEAD(subregion1, tc) 137{ 138 atf_tc_set_md_var(tc, "descr", 139 "Checks that subregions work (PR kern/7539)"); 140} 141ATF_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 155ATF_TC(subregion2); 156ATF_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} 162ATF_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 179ATF_TC(bound1); 180ATF_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} 186ATF_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 201ATF_TC(bound2); 202ATF_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} 208ATF_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 221ATF_TC(bound3); 222ATF_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} 228ATF_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 241ATF_TC(bound4); 242ATF_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} 249ATF_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 263ATF_TC(subregion3); 264ATF_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} 272ATF_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 287ATF_TC(bound5); 288ATF_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} 296ATF_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 312ATF_TC(free); 313ATF_TC_HEAD(free, tc) 314{ 315 atf_tc_set_md_var(tc, "descr", "Checks extent_free()"); 316} 317ATF_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 344ATF_TC(subregion4); 345ATF_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} 351ATF_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 370ATF_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