tests/kernel/t_extent.c

   1 /* $NetBSD$ */
   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$");
  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, 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, u_long 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: %#lx, got: %#lx", 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 }