sys/x86/iommu/intel_gas.c

   1 /*-
   2  * Copyright (c) 2013 The FreeBSD Foundation
   3  * All rights reserved.
   4  *
   5  * This software was developed by Konstantin Belousov <kib@FreeBSD.org>
   6  * under sponsorship from the FreeBSD Foundation.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  29
  30 #include <sys/cdefs.h>
  31 __FBSDID("$FreeBSD$");
  32
  33 #define RB_AUGMENT(entry) dmar_gas_augment_entry(entry)
  34
  35 #include <sys/param.h>
  36 #include <sys/systm.h>
  37 #include <sys/malloc.h>
  38 #include <sys/bus.h>
  39 #include <sys/interrupt.h>
  40 #include <sys/kernel.h>
  41 #include <sys/ktr.h>
  42 #include <sys/lock.h>
  43 #include <sys/proc.h>
  44 #include <sys/rwlock.h>
  45 #include <sys/memdesc.h>
  46 #include <sys/mutex.h>
  47 #include <sys/sysctl.h>
  48 #include <sys/rman.h>
  49 #include <sys/taskqueue.h>
  50 #include <sys/tree.h>
  51 #include <sys/uio.h>
  52 #include <dev/pci/pcivar.h>
  53 #include <vm/vm.h>
  54 #include <vm/vm_extern.h>
  55 #include <vm/vm_kern.h>
  56 #include <vm/vm_object.h>
  57 #include <vm/vm_page.h>
  58 #include <vm/vm_map.h>
  59 #include <vm/uma.h>
  60 #include <machine/atomic.h>
  61 #include <machine/bus.h>
  62 #include <machine/md_var.h>
  63 #include <machine/specialreg.h>
  64 #include <x86/include/busdma_impl.h>
  65 #include <x86/iommu/intel_reg.h>
  66 #include <x86/iommu/busdma_dmar.h>
  67 #include <x86/iommu/intel_dmar.h>
  68
  69 /*
  70  * Guest Address Space management.
  71  */
  72
  73 static uma_zone_t dmar_map_entry_zone;
  74
  75 static void
  76 intel_gas_init(void)
  77 {
  78
  79         dmar_map_entry_zone = uma_zcreate("DMAR_MAP_ENTRY",
  80             sizeof(struct dmar_map_entry), NULL, NULL,
  81             NULL, NULL, UMA_ALIGN_PTR, 0);
  82 }
  83 SYSINIT(intel_gas, SI_SUB_DRIVERS, SI_ORDER_FIRST, intel_gas_init, NULL);
  84
  85 struct dmar_map_entry *
  86 dmar_gas_alloc_entry(struct dmar_ctx *ctx, u_int flags)
  87 {
  88         struct dmar_map_entry *res;
  89
  90         KASSERT((flags & ~(DMAR_PGF_WAITOK)) == 0,
  91             ("unsupported flags %x", flags));
  92
  93         res = uma_zalloc(dmar_map_entry_zone, ((flags & DMAR_PGF_WAITOK) !=
  94             0 ? M_WAITOK : M_NOWAIT) | M_ZERO);
  95         if (res != NULL) {
  96                 res->ctx = ctx;
  97                 atomic_add_int(&ctx->entries_cnt, 1);
  98         }
  99         return (res);
 100 }
 101
 102 void
 103 dmar_gas_free_entry(struct dmar_ctx *ctx, struct dmar_map_entry *entry)
 104 {
 105
 106         KASSERT(ctx == entry->ctx,
 107             ("mismatched free ctx %p entry %p entry->ctx %p", ctx,
 108             entry, entry->ctx));
 109         atomic_subtract_int(&ctx->entries_cnt, 1);
 110         uma_zfree(dmar_map_entry_zone, entry);
 111 }
 112
 113 static int
 114 dmar_gas_cmp_entries(struct dmar_map_entry *a, struct dmar_map_entry *b)
 115 {
 116
 117         /* Last entry have zero size, so <= */
 118         KASSERT(a->start <= a->end, ("inverted entry %p (%jx, %jx)",
 119             a, (uintmax_t)a->start, (uintmax_t)a->end));
 120         KASSERT(b->start <= b->end, ("inverted entry %p (%jx, %jx)",
 121             b, (uintmax_t)b->start, (uintmax_t)b->end));
 122         KASSERT(a->end <= b->start || b->end <= a->start ||
 123             a->end == a->start || b->end == b->start,
 124             ("overlapping entries %p (%jx, %jx) %p (%jx, %jx)",
 125             a, (uintmax_t)a->start, (uintmax_t)a->end,
 126             b, (uintmax_t)b->start, (uintmax_t)b->end));
 127
 128         if (a->end < b->end)
 129                 return (-1);
 130         else if (b->end < a->end)
 131                 return (1);
 132         return (0);
 133 }
 134
 135 static void
 136 dmar_gas_augment_entry(struct dmar_map_entry *entry)
 137 {
 138         struct dmar_map_entry *l, *r;
 139
 140         for (; entry != NULL; entry = RB_PARENT(entry, rb_entry)) {
 141                 l = RB_LEFT(entry, rb_entry);
 142                 r = RB_RIGHT(entry, rb_entry);
 143                 if (l == NULL && r == NULL) {
 144                         entry->free_down = entry->free_after;
 145                 } else if (l == NULL && r != NULL) {
 146                         entry->free_down = MAX(entry->free_after, r->free_down);
 147                 } else if (/*l != NULL && */ r == NULL) {
 148                         entry->free_down = MAX(entry->free_after, l->free_down);
 149                 } else /* if (l != NULL && r != NULL) */ {
 150                         entry->free_down = MAX(entry->free_after, l->free_down);
 151                         entry->free_down = MAX(entry->free_down, r->free_down);
 152                 }
 153         }
 154 }
 155
 156 RB_GENERATE(dmar_gas_entries_tree, dmar_map_entry, rb_entry,
 157     dmar_gas_cmp_entries);
 158
 159 static void
 160 dmar_gas_fix_free(struct dmar_ctx *ctx, struct dmar_map_entry *entry)
 161 {
 162         struct dmar_map_entry *next;
 163
 164         next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry);
 165         entry->free_after = (next != NULL ? next->start : ctx->end) -
 166             entry->end;
 167         dmar_gas_augment_entry(entry);
 168 }
 169
 170 #ifdef INVARIANTS
 171 static void
 172 dmar_gas_check_free(struct dmar_ctx *ctx)
 173 {
 174         struct dmar_map_entry *entry, *next, *l, *r;
 175         dmar_gaddr_t v;
 176
 177         RB_FOREACH(entry, dmar_gas_entries_tree, &ctx->rb_root) {
 178                 KASSERT(ctx == entry->ctx,
 179                     ("mismatched free ctx %p entry %p entry->ctx %p", ctx,
 180                     entry, entry->ctx));
 181                 next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry);
 182                 if (next == NULL) {
 183                         MPASS(entry->free_after == ctx->end - entry->end);
 184                 } else {
 185                         MPASS(entry->free_after = next->start - entry->end);
 186                         MPASS(entry->end <= next->start);
 187                 }
 188                 l = RB_LEFT(entry, rb_entry);
 189                 r = RB_RIGHT(entry, rb_entry);
 190                 if (l == NULL && r == NULL) {
 191                         MPASS(entry->free_down == entry->free_after);
 192                 } else if (l == NULL && r != NULL) {
 193                         MPASS(entry->free_down = MAX(entry->free_after,
 194                             r->free_down));
 195                 } else if (r == NULL) {
 196                         MPASS(entry->free_down = MAX(entry->free_after,
 197                             l->free_down));
 198                 } else {
 199                         v = MAX(entry->free_after, l->free_down);
 200                         v = MAX(entry->free_down, r->free_down);
 201                         MPASS(entry->free_down == v);
 202                 }
 203         }
 204 }
 205 #endif
 206
 207 static bool
 208 dmar_gas_rb_insert(struct dmar_ctx *ctx, struct dmar_map_entry *entry)
 209 {
 210         struct dmar_map_entry *prev, *found;
 211
 212         found = RB_INSERT(dmar_gas_entries_tree, &ctx->rb_root, entry);
 213         dmar_gas_fix_free(ctx, entry);
 214         prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry);
 215         if (prev != NULL)
 216                 dmar_gas_fix_free(ctx, prev);
 217         return (found == NULL);
 218 }
 219
 220 static void
 221 dmar_gas_rb_remove(struct dmar_ctx *ctx, struct dmar_map_entry *entry)
 222 {
 223         struct dmar_map_entry *prev;
 224
 225         prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry);
 226         RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry);
 227         if (prev != NULL)
 228                 dmar_gas_fix_free(ctx, prev);
 229 }
 230
 231 void
 232 dmar_gas_init_ctx(struct dmar_ctx *ctx)
 233 {
 234         struct dmar_map_entry *begin, *end;
 235
 236         begin = dmar_gas_alloc_entry(ctx, DMAR_PGF_WAITOK);
 237         end = dmar_gas_alloc_entry(ctx, DMAR_PGF_WAITOK);
 238
 239         DMAR_CTX_LOCK(ctx);
 240         KASSERT(ctx->entries_cnt == 2, ("dirty ctx %p", ctx));
 241         KASSERT(RB_EMPTY(&ctx->rb_root), ("non-empty entries %p", ctx));
 242
 243         begin->start = 0;
 244         begin->end = DMAR_PAGE_SIZE;
 245         begin->free_after = ctx->end - begin->end;
 246         begin->flags = DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_UNMAPPED;
 247         dmar_gas_rb_insert(ctx, begin);
 248
 249         end->start = ctx->end;
 250         end->end = ctx->end;
 251         end->free_after = 0;
 252         end->flags = DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_UNMAPPED;
 253         dmar_gas_rb_insert(ctx, end);
 254
 255         ctx->first_place = begin;
 256         ctx->last_place = end;
 257         DMAR_CTX_UNLOCK(ctx);
 258 }
 259
 260 void
 261 dmar_gas_fini_ctx(struct dmar_ctx *ctx)
 262 {
 263         struct dmar_map_entry *entry, *entry1;
 264
 265         DMAR_CTX_ASSERT_LOCKED(ctx);
 266         KASSERT(ctx->entries_cnt == 2, ("ctx still in use %p", ctx));
 267
 268         entry = RB_MIN(dmar_gas_entries_tree, &ctx->rb_root);
 269         KASSERT(entry->start == 0, ("start entry start %p", ctx));
 270         KASSERT(entry->end == DMAR_PAGE_SIZE, ("start entry end %p", ctx));
 271         KASSERT(entry->flags == DMAR_MAP_ENTRY_PLACE,
 272             ("start entry flags %p", ctx));
 273         RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry);
 274         dmar_gas_free_entry(ctx, entry);
 275
 276         entry = RB_MAX(dmar_gas_entries_tree, &ctx->rb_root);
 277         KASSERT(entry->start == ctx->end, ("end entry start %p", ctx));
 278         KASSERT(entry->end == ctx->end, ("end entry end %p", ctx));
 279         KASSERT(entry->free_after == 0, ("end entry free_after%p", ctx));
 280         KASSERT(entry->flags == DMAR_MAP_ENTRY_PLACE,
 281             ("end entry flags %p", ctx));
 282         RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry);
 283         dmar_gas_free_entry(ctx, entry);
 284
 285         RB_FOREACH_SAFE(entry, dmar_gas_entries_tree, &ctx->rb_root, entry1) {
 286                 KASSERT((entry->flags & DMAR_MAP_ENTRY_RMRR) != 0,
 287                     ("non-RMRR entry left %p", ctx));
 288                 RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry);
 289                 dmar_gas_free_entry(ctx, entry);
 290         }
 291 }
 292
 293 struct dmar_gas_match_args {
 294         struct dmar_ctx *ctx;
 295         dmar_gaddr_t size;
 296         int offset;
 297         const struct bus_dma_tag_common *common;
 298         u_int gas_flags;
 299         struct dmar_map_entry *entry;
 300 };
 301
 302 static bool
 303 dmar_gas_match_one(struct dmar_gas_match_args *a, struct dmar_map_entry *prev,
 304     dmar_gaddr_t end)
 305 {
 306         dmar_gaddr_t bs, start;
 307
 308         if (a->entry->start + a->size > end)
 309                 return (false);
 310
 311         /* DMAR_PAGE_SIZE to create gap after new entry. */
 312         if (a->entry->start < prev->end + DMAR_PAGE_SIZE ||
 313             a->entry->start + a->size + a->offset + DMAR_PAGE_SIZE >
 314             prev->end + prev->free_after)
 315                 return (false);
 316
 317         /* No boundary crossing. */
 318         if (dmar_test_boundary(a->entry->start + a->offset, a->size,
 319             a->common->boundary))
 320                 return (true);
 321
 322         /*
 323          * The start + offset to start + offset + size region crosses
 324          * the boundary.  Check if there is enough space after the
 325          * next boundary after the prev->end.
 326          */
 327         bs = (a->entry->start + a->offset + a->common->boundary) &
 328             ~(a->common->boundary - 1);
 329         start = roundup2(bs, a->common->alignment);
 330         /* DMAR_PAGE_SIZE to create gap after new entry. */
 331         if (start + a->offset + a->size + DMAR_PAGE_SIZE <=
 332             prev->end + prev->free_after &&
 333             start + a->offset + a->size <= end &&
 334             dmar_test_boundary(start + a->offset, a->size,
 335             a->common->boundary)) {
 336                 a->entry->start = start;
 337                 return (true);
 338         }
 339
 340         /*
 341          * Not enough space to align at the requested boundary, or
 342          * boundary is smaller than the size, but allowed to split.
 343          * We already checked that start + size does not overlap end.
 344          *
 345          * XXXKIB. It is possible that bs is exactly at the start of
 346          * the next entry, then we do not have gap.  Ignore for now.
 347          */
 348         if ((a->gas_flags & DMAR_GM_CANSPLIT) != 0) {
 349                 a->size = bs - a->entry->start;
 350                 return (true);
 351         }
 352
 353         return (false);
 354 }
 355
 356 static void
 357 dmar_gas_match_insert(struct dmar_gas_match_args *a,
 358     struct dmar_map_entry *prev)
 359 {
 360         struct dmar_map_entry *next;
 361         bool found;
 362
 363         /*
 364          * The prev->end is always aligned on the page size, which
 365          * causes page alignment for the entry->start too.  The size
 366          * is checked to be multiple of the page size.
 367          *
 368          * The page sized gap is created between consequent
 369          * allocations to ensure that out-of-bounds accesses fault.
 370          */
 371         a->entry->end = a->entry->start + a->size;
 372
 373         next = RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, prev);
 374         KASSERT(next->start >= a->entry->end &&
 375             next->start - a->entry->start >= a->size &&
 376             prev->end <= a->entry->end,
 377             ("dmar_gas_match_insert hole failed %p prev (%jx, %jx) "
 378             "free_after %jx next (%jx, %jx) entry (%jx, %jx)", a->ctx,
 379             (uintmax_t)prev->start, (uintmax_t)prev->end,
 380             (uintmax_t)prev->free_after,
 381             (uintmax_t)next->start, (uintmax_t)next->end,
 382             (uintmax_t)a->entry->start, (uintmax_t)a->entry->end));
 383
 384         prev->free_after = a->entry->start - prev->end;
 385         a->entry->free_after = next->start - a->entry->end;
 386
 387         found = dmar_gas_rb_insert(a->ctx, a->entry);
 388         KASSERT(found, ("found dup %p start %jx size %jx",
 389             a->ctx, (uintmax_t)a->entry->start, (uintmax_t)a->size));
 390         a->entry->flags = DMAR_MAP_ENTRY_MAP;
 391
 392         KASSERT(RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root,
 393             a->entry) == prev,
 394             ("entry %p prev %p inserted prev %p", a->entry, prev,
 395             RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root, a->entry)));
 396         KASSERT(RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root,
 397             a->entry) == next,
 398             ("entry %p next %p inserted next %p", a->entry, next,
 399             RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, a->entry)));
 400 }
 401
 402 static int
 403 dmar_gas_lowermatch(struct dmar_gas_match_args *a, struct dmar_map_entry *prev)
 404 {
 405         struct dmar_map_entry *l;
 406         int ret;
 407
 408         if (prev->end < a->common->lowaddr) {
 409                 a->entry->start = roundup2(prev->end + DMAR_PAGE_SIZE,
 410                     a->common->alignment);
 411                 if (dmar_gas_match_one(a, prev, a->common->lowaddr)) {
 412                         dmar_gas_match_insert(a, prev);
 413                         return (0);
 414                 }
 415         }
 416         if (prev->free_down < a->size + a->offset + DMAR_PAGE_SIZE)
 417                 return (ENOMEM);
 418         l = RB_LEFT(prev, rb_entry);
 419         if (l != NULL) {
 420                 ret = dmar_gas_lowermatch(a, l);
 421                 if (ret == 0)
 422                         return (0);
 423         }
 424         l = RB_RIGHT(prev, rb_entry);
 425         if (l != NULL)
 426                 return (dmar_gas_lowermatch(a, l));
 427         return (ENOMEM);
 428 }
 429
 430 static int
 431 dmar_gas_uppermatch(struct dmar_gas_match_args *a)
 432 {
 433         struct dmar_map_entry *next, *prev, find_entry;
 434
 435         find_entry.start = a->common->highaddr;
 436         next = RB_NFIND(dmar_gas_entries_tree, &a->ctx->rb_root, &find_entry);
 437         if (next == NULL)
 438                 return (ENOMEM);
 439         prev = RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root, next);
 440         KASSERT(prev != NULL, ("no prev %p %jx", a->ctx,
 441             (uintmax_t)find_entry.start));
 442         for (;;) {
 443                 a->entry->start = prev->start + DMAR_PAGE_SIZE;
 444                 if (a->entry->start < a->common->highaddr)
 445                         a->entry->start = a->common->highaddr;
 446                 a->entry->start = roundup2(a->entry->start,
 447                     a->common->alignment);
 448                 if (dmar_gas_match_one(a, prev, a->ctx->end)) {
 449                         dmar_gas_match_insert(a, prev);
 450                         return (0);
 451                 }
 452
 453                 /*
 454                  * XXXKIB.  This falls back to linear iteration over
 455                  * the free space in the high region.  But high
 456                  * regions are almost unused, the code should be
 457                  * enough to cover the case, although in the
 458                  * non-optimal way.
 459                  */
 460                 prev = next;
 461                 next = RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, prev);
 462                 KASSERT(next != NULL, ("no next %p %jx", a->ctx,
 463                     (uintmax_t)find_entry.start));
 464                 if (next->end >= a->ctx->end)
 465                         return (ENOMEM);
 466         }
 467 }
 468
 469 static int
 470 dmar_gas_find_space(struct dmar_ctx *ctx,
 471     const struct bus_dma_tag_common *common, dmar_gaddr_t size,
 472     int offset, u_int flags, struct dmar_map_entry *entry)
 473 {
 474         struct dmar_gas_match_args a;
 475         int error;
 476
 477         DMAR_CTX_ASSERT_LOCKED(ctx);
 478         KASSERT(entry->flags == 0, ("dirty entry %p %p", ctx, entry));
 479         KASSERT((size & DMAR_PAGE_MASK) == 0, ("size %jx", (uintmax_t)size));
 480
 481         a.ctx = ctx;
 482         a.size = size;
 483         a.offset = offset;
 484         a.common = common;
 485         a.gas_flags = flags;
 486         a.entry = entry;
 487
 488         /* Handle lower region. */
 489         if (common->lowaddr > 0) {
 490                 error = dmar_gas_lowermatch(&a, RB_ROOT(&ctx->rb_root));
 491                 if (error == 0)
 492                         return (0);
 493                 KASSERT(error == ENOMEM,
 494                     ("error %d from dmar_gas_lowermatch", error));
 495         }
 496         /* Handle upper region. */
 497         if (common->highaddr >= ctx->end)
 498                 return (ENOMEM);
 499         error = dmar_gas_uppermatch(&a);
 500         KASSERT(error == ENOMEM,
 501             ("error %d from dmar_gas_uppermatch", error));
 502         return (error);
 503 }
 504
 505 static int
 506 dmar_gas_alloc_region(struct dmar_ctx *ctx, struct dmar_map_entry *entry,
 507     u_int flags)
 508 {
 509         struct dmar_map_entry *next, *prev;
 510         bool found;
 511
 512         DMAR_CTX_ASSERT_LOCKED(ctx);
 513
 514         if ((entry->start & DMAR_PAGE_MASK) != 0 ||
 515             (entry->end & DMAR_PAGE_MASK) != 0)
 516                 return (EINVAL);
 517         if (entry->start >= entry->end)
 518                 return (EINVAL);
 519         if (entry->end >= ctx->end)
 520                 return (EINVAL);
 521
 522         next = RB_NFIND(dmar_gas_entries_tree, &ctx->rb_root, entry);
 523         KASSERT(next != NULL, ("next must be non-null %p %jx", ctx,
 524             (uintmax_t)entry->start));
 525         prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, next);
 526         /* prev could be NULL */
 527
 528         /*
 529          * Adapt to broken BIOSes which specify overlapping RMRR
 530          * entries.
 531          *
 532          * XXXKIB: this does not handle a case when prev or next
 533          * entries are completely covered by the current one, which
 534          * extends both ways.
 535          */
 536         if (prev != NULL && prev->end > entry->start &&
 537             (prev->flags & DMAR_MAP_ENTRY_PLACE) == 0) {
 538                 if ((prev->flags & DMAR_MAP_ENTRY_RMRR) == 0)
 539                         return (EBUSY);
 540                 entry->start = prev->end;
 541         }
 542         if (next != NULL && next->start < entry->end &&
 543             (next->flags & DMAR_MAP_ENTRY_PLACE) == 0) {
 544                 if ((next->flags & DMAR_MAP_ENTRY_RMRR) == 0)
 545                         return (EBUSY);
 546                 entry->end = next->start;
 547         }
 548         if (entry->end == entry->start)
 549                 return (0);
 550
 551         if (prev != NULL && prev->end > entry->start) {
 552                 /* This assumes that prev is the placeholder entry. */
 553                 dmar_gas_rb_remove(ctx, prev);
 554                 prev = NULL;
 555         }
 556         if (next != NULL && next->start < entry->end) {
 557                 dmar_gas_rb_remove(ctx, next);
 558                 next = NULL;
 559         }
 560
 561         found = dmar_gas_rb_insert(ctx, entry);
 562         KASSERT(found, ("found RMRR dup %p start %jx end %jx",
 563             ctx, (uintmax_t)entry->start, (uintmax_t)entry->end));
 564         entry->flags = DMAR_MAP_ENTRY_RMRR;
 565
 566 #ifdef INVARIANTS
 567         struct dmar_map_entry *ip, *in;
 568         ip = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry);
 569         in = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry);
 570         KASSERT(prev == NULL || ip == prev,
 571             ("RMRR %p (%jx %jx) prev %p (%jx %jx) ins prev %p (%jx %jx)",
 572             entry, entry->start, entry->end, prev,
 573             prev == NULL ? 0 : prev->start, prev == NULL ? 0 : prev->end,
 574             ip, ip == NULL ? 0 : ip->start, ip == NULL ? 0 : ip->end));
 575         KASSERT(next == NULL || in == next,
 576             ("RMRR %p (%jx %jx) next %p (%jx %jx) ins next %p (%jx %jx)",
 577             entry, entry->start, entry->end, next,
 578             next == NULL ? 0 : next->start, next == NULL ? 0 : next->end,
 579             in, in == NULL ? 0 : in->start, in == NULL ? 0 : in->end));
 580 #endif
 581
 582         return (0);
 583 }
 584
 585 void
 586 dmar_gas_free_space(struct dmar_ctx *ctx, struct dmar_map_entry *entry)
 587 {
 588
 589         DMAR_CTX_ASSERT_LOCKED(ctx);
 590         KASSERT((entry->flags & (DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_RMRR |
 591             DMAR_MAP_ENTRY_MAP)) == DMAR_MAP_ENTRY_MAP,
 592             ("permanent entry %p %p", ctx, entry));
 593
 594         dmar_gas_rb_remove(ctx, entry);
 595         entry->flags &= ~DMAR_MAP_ENTRY_MAP;
 596 #ifdef INVARIANTS
 597         if (dmar_check_free)
 598                 dmar_gas_check_free(ctx);
 599 #endif
 600 }
 601
 602 void
 603 dmar_gas_free_region(struct dmar_ctx *ctx, struct dmar_map_entry *entry)
 604 {
 605         struct dmar_map_entry *next, *prev;
 606
 607         DMAR_CTX_ASSERT_LOCKED(ctx);
 608         KASSERT((entry->flags & (DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_RMRR |
 609             DMAR_MAP_ENTRY_MAP)) == DMAR_MAP_ENTRY_RMRR,
 610             ("non-RMRR entry %p %p", ctx, entry));
 611
 612         prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry);
 613         next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry);
 614         dmar_gas_rb_remove(ctx, entry);
 615         entry->flags &= ~DMAR_MAP_ENTRY_RMRR;
 616
 617         if (prev == NULL)
 618                 dmar_gas_rb_insert(ctx, ctx->first_place);
 619         if (next == NULL)
 620                 dmar_gas_rb_insert(ctx, ctx->last_place);
 621 }
 622
 623 int
 624 dmar_gas_map(struct dmar_ctx *ctx, const struct bus_dma_tag_common *common,
 625     dmar_gaddr_t size, int offset, u_int eflags, u_int flags, vm_page_t *ma,
 626     struct dmar_map_entry **res)
 627 {
 628         struct dmar_map_entry *entry;
 629         int error;
 630
 631         KASSERT((flags & ~(DMAR_GM_CANWAIT | DMAR_GM_CANSPLIT)) == 0,
 632             ("invalid flags 0x%x", flags));
 633
 634         entry = dmar_gas_alloc_entry(ctx, (flags & DMAR_GM_CANWAIT) != 0 ?
 635             DMAR_PGF_WAITOK : 0);
 636         if (entry == NULL)
 637                 return (ENOMEM);
 638         DMAR_CTX_LOCK(ctx);
 639         error = dmar_gas_find_space(ctx, common, size, offset, flags, entry);
 640         if (error == ENOMEM) {
 641                 DMAR_CTX_UNLOCK(ctx);
 642                 dmar_gas_free_entry(ctx, entry);
 643                 return (error);
 644         }
 645 #ifdef INVARIANTS
 646         if (dmar_check_free)
 647                 dmar_gas_check_free(ctx);
 648 #endif
 649         KASSERT(error == 0,
 650             ("unexpected error %d from dmar_gas_find_entry", error));
 651         KASSERT(entry->end < ctx->end, ("allocated GPA %jx, max GPA %jx",
 652             (uintmax_t)entry->end, (uintmax_t)ctx->end));
 653         entry->flags |= eflags;
 654         DMAR_CTX_UNLOCK(ctx);
 655
 656         error = ctx_map_buf(ctx, entry->start, entry->end - entry->start, ma,
 657             ((eflags & DMAR_MAP_ENTRY_READ) != 0 ? DMAR_PTE_R : 0) |
 658             ((eflags & DMAR_MAP_ENTRY_WRITE) != 0 ? DMAR_PTE_W : 0) |
 659             ((eflags & DMAR_MAP_ENTRY_SNOOP) != 0 ? DMAR_PTE_SNP : 0) |
 660             ((eflags & DMAR_MAP_ENTRY_TM) != 0 ? DMAR_PTE_TM : 0),
 661             (flags & DMAR_GM_CANWAIT) != 0 ? DMAR_PGF_WAITOK : 0);
 662         if (error == ENOMEM) {
 663                 dmar_ctx_unload_entry(entry, true);
 664                 return (error);
 665         }
 666         KASSERT(error == 0,
 667             ("unexpected error %d from ctx_map_buf", error));
 668
 669         *res = entry;
 670         return (0);
 671 }
 672
 673 int
 674 dmar_gas_map_region(struct dmar_ctx *ctx, struct dmar_map_entry *entry,
 675     u_int eflags, u_int flags, vm_page_t *ma)
 676 {
 677         dmar_gaddr_t start;
 678         int error;
 679
 680         KASSERT(entry->flags == 0, ("used RMRR entry %p %p %x", ctx,
 681             entry, entry->flags));
 682         KASSERT((flags & ~(DMAR_GM_CANWAIT)) == 0,
 683             ("invalid flags 0x%x", flags));
 684
 685         start = entry->start;
 686         DMAR_CTX_LOCK(ctx);
 687         error = dmar_gas_alloc_region(ctx, entry, flags);
 688         if (error != 0) {
 689                 DMAR_CTX_UNLOCK(ctx);
 690                 return (error);
 691         }
 692         entry->flags |= eflags;
 693         DMAR_CTX_UNLOCK(ctx);
 694         if (entry->end == entry->start)
 695                 return (0);
 696
 697         error = ctx_map_buf(ctx, entry->start, entry->end - entry->start,
 698             ma + OFF_TO_IDX(start - entry->start),
 699             ((eflags & DMAR_MAP_ENTRY_READ) != 0 ? DMAR_PTE_R : 0) |
 700             ((eflags & DMAR_MAP_ENTRY_WRITE) != 0 ? DMAR_PTE_W : 0) |
 701             ((eflags & DMAR_MAP_ENTRY_SNOOP) != 0 ? DMAR_PTE_SNP : 0) |
 702             ((eflags & DMAR_MAP_ENTRY_TM) != 0 ? DMAR_PTE_TM : 0),
 703             (flags & DMAR_GM_CANWAIT) != 0 ? DMAR_PGF_WAITOK : 0);
 704         if (error == ENOMEM) {
 705                 dmar_ctx_unload_entry(entry, false);
 706                 return (error);
 707         }
 708         KASSERT(error == 0,
 709             ("unexpected error %d from ctx_map_buf", error));
 710
 711         return (0);
 712 }
 713
 714 int
 715 dmar_gas_reserve_region(struct dmar_ctx *ctx, dmar_gaddr_t start,
 716     dmar_gaddr_t end)
 717 {
 718         struct dmar_map_entry *entry;
 719         int error;
 720
 721         entry = dmar_gas_alloc_entry(ctx, DMAR_PGF_WAITOK);
 722         entry->start = start;
 723         entry->end = end;
 724         DMAR_CTX_LOCK(ctx);
 725         error = dmar_gas_alloc_region(ctx, entry, DMAR_GM_CANWAIT);
 726         if (error == 0)
 727                 entry->flags |= DMAR_MAP_ENTRY_UNMAPPED;
 728         DMAR_CTX_UNLOCK(ctx);
 729         if (error != 0)
 730                 dmar_gas_free_entry(ctx, entry);
 731         return (error);
 732 }