1257251Skib/*- 2257251Skib * Copyright (c) 2013 The FreeBSD Foundation 3257251Skib * All rights reserved. 4257251Skib * 5257251Skib * This software was developed by Konstantin Belousov <kib@FreeBSD.org> 6257251Skib * under sponsorship from the FreeBSD Foundation. 7257251Skib * 8257251Skib * Redistribution and use in source and binary forms, with or without 9257251Skib * modification, are permitted provided that the following conditions 10257251Skib * are met: 11257251Skib * 1. Redistributions of source code must retain the above copyright 12257251Skib * notice, this list of conditions and the following disclaimer. 13257251Skib * 2. Redistributions in binary form must reproduce the above copyright 14257251Skib * notice, this list of conditions and the following disclaimer in the 15257251Skib * documentation and/or other materials provided with the distribution. 16257251Skib * 17257251Skib * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18257251Skib * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19257251Skib * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20257251Skib * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21257251Skib * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22257251Skib * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23257251Skib * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24257251Skib * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25257251Skib * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26257251Skib * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27257251Skib * SUCH DAMAGE. 28257251Skib */ 29257251Skib 30257251Skib#include <sys/cdefs.h> 31257251Skib__FBSDID("$FreeBSD: releng/10.3/sys/x86/iommu/intel_gas.c 281545 2015-04-15 06:56:51Z kib $"); 32257251Skib 33257251Skib#define RB_AUGMENT(entry) dmar_gas_augment_entry(entry) 34257251Skib 35257251Skib#include <sys/param.h> 36257251Skib#include <sys/systm.h> 37257251Skib#include <sys/malloc.h> 38257251Skib#include <sys/bus.h> 39257251Skib#include <sys/interrupt.h> 40257251Skib#include <sys/kernel.h> 41257251Skib#include <sys/ktr.h> 42257251Skib#include <sys/lock.h> 43257251Skib#include <sys/proc.h> 44257251Skib#include <sys/rwlock.h> 45257251Skib#include <sys/memdesc.h> 46257251Skib#include <sys/mutex.h> 47257251Skib#include <sys/sysctl.h> 48257251Skib#include <sys/rman.h> 49257251Skib#include <sys/taskqueue.h> 50257251Skib#include <sys/tree.h> 51257251Skib#include <sys/uio.h> 52257251Skib#include <dev/pci/pcivar.h> 53257251Skib#include <vm/vm.h> 54257251Skib#include <vm/vm_extern.h> 55257251Skib#include <vm/vm_kern.h> 56257251Skib#include <vm/vm_object.h> 57257251Skib#include <vm/vm_page.h> 58257251Skib#include <vm/vm_map.h> 59257251Skib#include <vm/uma.h> 60257251Skib#include <machine/atomic.h> 61257251Skib#include <machine/bus.h> 62257251Skib#include <machine/md_var.h> 63257251Skib#include <machine/specialreg.h> 64257251Skib#include <x86/include/busdma_impl.h> 65257251Skib#include <x86/iommu/intel_reg.h> 66257251Skib#include <x86/iommu/busdma_dmar.h> 67257251Skib#include <x86/iommu/intel_dmar.h> 68257251Skib 69257251Skib/* 70257251Skib * Guest Address Space management. 71257251Skib */ 72257251Skib 73257251Skibstatic uma_zone_t dmar_map_entry_zone; 74257251Skib 75257251Skibstatic void 76257251Skibintel_gas_init(void) 77257251Skib{ 78257251Skib 79257251Skib dmar_map_entry_zone = uma_zcreate("DMAR_MAP_ENTRY", 80257251Skib sizeof(struct dmar_map_entry), NULL, NULL, 81257251Skib NULL, NULL, UMA_ALIGN_PTR, 0); 82257251Skib} 83257251SkibSYSINIT(intel_gas, SI_SUB_DRIVERS, SI_ORDER_FIRST, intel_gas_init, NULL); 84257251Skib 85257251Skibstruct dmar_map_entry * 86257251Skibdmar_gas_alloc_entry(struct dmar_ctx *ctx, u_int flags) 87257251Skib{ 88257251Skib struct dmar_map_entry *res; 89257251Skib 90257251Skib KASSERT((flags & ~(DMAR_PGF_WAITOK)) == 0, 91257251Skib ("unsupported flags %x", flags)); 92257251Skib 93257251Skib res = uma_zalloc(dmar_map_entry_zone, ((flags & DMAR_PGF_WAITOK) != 94257251Skib 0 ? M_WAITOK : M_NOWAIT) | M_ZERO); 95259512Skib if (res != NULL) { 96259512Skib res->ctx = ctx; 97257251Skib atomic_add_int(&ctx->entries_cnt, 1); 98259512Skib } 99257251Skib return (res); 100257251Skib} 101257251Skib 102257251Skibvoid 103257251Skibdmar_gas_free_entry(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 104257251Skib{ 105257251Skib 106259512Skib KASSERT(ctx == entry->ctx, 107259512Skib ("mismatched free ctx %p entry %p entry->ctx %p", ctx, 108259512Skib entry, entry->ctx)); 109257251Skib atomic_subtract_int(&ctx->entries_cnt, 1); 110257251Skib uma_zfree(dmar_map_entry_zone, entry); 111257251Skib} 112257251Skib 113257251Skibstatic int 114257251Skibdmar_gas_cmp_entries(struct dmar_map_entry *a, struct dmar_map_entry *b) 115257251Skib{ 116257251Skib 117257251Skib /* Last entry have zero size, so <= */ 118257251Skib KASSERT(a->start <= a->end, ("inverted entry %p (%jx, %jx)", 119257251Skib a, (uintmax_t)a->start, (uintmax_t)a->end)); 120257251Skib KASSERT(b->start <= b->end, ("inverted entry %p (%jx, %jx)", 121257251Skib b, (uintmax_t)b->start, (uintmax_t)b->end)); 122257251Skib KASSERT(a->end <= b->start || b->end <= a->start || 123257251Skib a->end == a->start || b->end == b->start, 124257251Skib ("overlapping entries %p (%jx, %jx) %p (%jx, %jx)", 125257251Skib a, (uintmax_t)a->start, (uintmax_t)a->end, 126257251Skib b, (uintmax_t)b->start, (uintmax_t)b->end)); 127257251Skib 128257251Skib if (a->end < b->end) 129257251Skib return (-1); 130257251Skib else if (b->end < a->end) 131257251Skib return (1); 132257251Skib return (0); 133257251Skib} 134257251Skib 135257251Skibstatic void 136257251Skibdmar_gas_augment_entry(struct dmar_map_entry *entry) 137257251Skib{ 138257251Skib struct dmar_map_entry *l, *r; 139257251Skib 140257251Skib for (; entry != NULL; entry = RB_PARENT(entry, rb_entry)) { 141257251Skib l = RB_LEFT(entry, rb_entry); 142257251Skib r = RB_RIGHT(entry, rb_entry); 143257251Skib if (l == NULL && r == NULL) { 144257251Skib entry->free_down = entry->free_after; 145257251Skib } else if (l == NULL && r != NULL) { 146257251Skib entry->free_down = MAX(entry->free_after, r->free_down); 147257251Skib } else if (/*l != NULL && */ r == NULL) { 148257251Skib entry->free_down = MAX(entry->free_after, l->free_down); 149257251Skib } else /* if (l != NULL && r != NULL) */ { 150257251Skib entry->free_down = MAX(entry->free_after, l->free_down); 151257251Skib entry->free_down = MAX(entry->free_down, r->free_down); 152257251Skib } 153257251Skib } 154257251Skib} 155257251Skib 156257251SkibRB_GENERATE(dmar_gas_entries_tree, dmar_map_entry, rb_entry, 157257251Skib dmar_gas_cmp_entries); 158257251Skib 159257251Skibstatic void 160257251Skibdmar_gas_fix_free(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 161257251Skib{ 162257251Skib struct dmar_map_entry *next; 163257251Skib 164257251Skib next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 165257251Skib entry->free_after = (next != NULL ? next->start : ctx->end) - 166257251Skib entry->end; 167257251Skib dmar_gas_augment_entry(entry); 168257251Skib} 169257251Skib 170257251Skib#ifdef INVARIANTS 171257251Skibstatic void 172257251Skibdmar_gas_check_free(struct dmar_ctx *ctx) 173257251Skib{ 174257251Skib struct dmar_map_entry *entry, *next, *l, *r; 175257251Skib dmar_gaddr_t v; 176257251Skib 177257251Skib RB_FOREACH(entry, dmar_gas_entries_tree, &ctx->rb_root) { 178259512Skib KASSERT(ctx == entry->ctx, 179259512Skib ("mismatched free ctx %p entry %p entry->ctx %p", ctx, 180259512Skib entry, entry->ctx)); 181257251Skib next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 182257251Skib if (next == NULL) { 183257251Skib MPASS(entry->free_after == ctx->end - entry->end); 184257251Skib } else { 185257251Skib MPASS(entry->free_after = next->start - entry->end); 186257251Skib MPASS(entry->end <= next->start); 187257251Skib } 188257251Skib l = RB_LEFT(entry, rb_entry); 189257251Skib r = RB_RIGHT(entry, rb_entry); 190257251Skib if (l == NULL && r == NULL) { 191257251Skib MPASS(entry->free_down == entry->free_after); 192257251Skib } else if (l == NULL && r != NULL) { 193257251Skib MPASS(entry->free_down = MAX(entry->free_after, 194257251Skib r->free_down)); 195257251Skib } else if (r == NULL) { 196257251Skib MPASS(entry->free_down = MAX(entry->free_after, 197257251Skib l->free_down)); 198257251Skib } else { 199257251Skib v = MAX(entry->free_after, l->free_down); 200257251Skib v = MAX(entry->free_down, r->free_down); 201257251Skib MPASS(entry->free_down == v); 202257251Skib } 203257251Skib } 204257251Skib} 205257251Skib#endif 206257251Skib 207257251Skibstatic bool 208257251Skibdmar_gas_rb_insert(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 209257251Skib{ 210257251Skib struct dmar_map_entry *prev, *found; 211257251Skib 212257251Skib found = RB_INSERT(dmar_gas_entries_tree, &ctx->rb_root, entry); 213257251Skib dmar_gas_fix_free(ctx, entry); 214257251Skib prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 215257251Skib if (prev != NULL) 216257251Skib dmar_gas_fix_free(ctx, prev); 217257251Skib return (found == NULL); 218257251Skib} 219257251Skib 220257251Skibstatic void 221257251Skibdmar_gas_rb_remove(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 222257251Skib{ 223257251Skib struct dmar_map_entry *prev; 224257251Skib 225257251Skib prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 226257251Skib RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 227257251Skib if (prev != NULL) 228257251Skib dmar_gas_fix_free(ctx, prev); 229257251Skib} 230257251Skib 231257251Skibvoid 232257251Skibdmar_gas_init_ctx(struct dmar_ctx *ctx) 233257251Skib{ 234257251Skib struct dmar_map_entry *begin, *end; 235257251Skib 236257251Skib begin = dmar_gas_alloc_entry(ctx, DMAR_PGF_WAITOK); 237257251Skib end = dmar_gas_alloc_entry(ctx, DMAR_PGF_WAITOK); 238257251Skib 239257251Skib DMAR_CTX_LOCK(ctx); 240257251Skib KASSERT(ctx->entries_cnt == 2, ("dirty ctx %p", ctx)); 241257251Skib KASSERT(RB_EMPTY(&ctx->rb_root), ("non-empty entries %p", ctx)); 242257251Skib 243257251Skib begin->start = 0; 244257251Skib begin->end = DMAR_PAGE_SIZE; 245257251Skib begin->free_after = ctx->end - begin->end; 246257251Skib begin->flags = DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_UNMAPPED; 247257251Skib dmar_gas_rb_insert(ctx, begin); 248257251Skib 249257251Skib end->start = ctx->end; 250257251Skib end->end = ctx->end; 251257251Skib end->free_after = 0; 252257251Skib end->flags = DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_UNMAPPED; 253257251Skib dmar_gas_rb_insert(ctx, end); 254257251Skib 255257251Skib ctx->first_place = begin; 256257251Skib ctx->last_place = end; 257257251Skib DMAR_CTX_UNLOCK(ctx); 258257251Skib} 259257251Skib 260257251Skibvoid 261257251Skibdmar_gas_fini_ctx(struct dmar_ctx *ctx) 262257251Skib{ 263257251Skib struct dmar_map_entry *entry, *entry1; 264257251Skib 265257251Skib DMAR_CTX_ASSERT_LOCKED(ctx); 266257251Skib KASSERT(ctx->entries_cnt == 2, ("ctx still in use %p", ctx)); 267257251Skib 268257251Skib entry = RB_MIN(dmar_gas_entries_tree, &ctx->rb_root); 269257251Skib KASSERT(entry->start == 0, ("start entry start %p", ctx)); 270257251Skib KASSERT(entry->end == DMAR_PAGE_SIZE, ("start entry end %p", ctx)); 271257251Skib KASSERT(entry->flags == DMAR_MAP_ENTRY_PLACE, 272257251Skib ("start entry flags %p", ctx)); 273257251Skib RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 274257251Skib dmar_gas_free_entry(ctx, entry); 275257251Skib 276257251Skib entry = RB_MAX(dmar_gas_entries_tree, &ctx->rb_root); 277257251Skib KASSERT(entry->start == ctx->end, ("end entry start %p", ctx)); 278257251Skib KASSERT(entry->end == ctx->end, ("end entry end %p", ctx)); 279257251Skib KASSERT(entry->free_after == 0, ("end entry free_after%p", ctx)); 280257251Skib KASSERT(entry->flags == DMAR_MAP_ENTRY_PLACE, 281257251Skib ("end entry flags %p", ctx)); 282257251Skib RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 283257251Skib dmar_gas_free_entry(ctx, entry); 284257251Skib 285257251Skib RB_FOREACH_SAFE(entry, dmar_gas_entries_tree, &ctx->rb_root, entry1) { 286257251Skib KASSERT((entry->flags & DMAR_MAP_ENTRY_RMRR) != 0, 287257251Skib ("non-RMRR entry left %p", ctx)); 288257251Skib RB_REMOVE(dmar_gas_entries_tree, &ctx->rb_root, entry); 289257251Skib dmar_gas_free_entry(ctx, entry); 290257251Skib } 291257251Skib} 292257251Skib 293257251Skibstruct dmar_gas_match_args { 294257251Skib struct dmar_ctx *ctx; 295257251Skib dmar_gaddr_t size; 296281545Skib int offset; 297257251Skib const struct bus_dma_tag_common *common; 298257251Skib u_int gas_flags; 299257251Skib struct dmar_map_entry *entry; 300257251Skib}; 301257251Skib 302257251Skibstatic bool 303257251Skibdmar_gas_match_one(struct dmar_gas_match_args *a, struct dmar_map_entry *prev, 304257251Skib dmar_gaddr_t end) 305257251Skib{ 306257251Skib dmar_gaddr_t bs, start; 307257251Skib 308257251Skib if (a->entry->start + a->size > end) 309257251Skib return (false); 310257251Skib 311257251Skib /* DMAR_PAGE_SIZE to create gap after new entry. */ 312257251Skib if (a->entry->start < prev->end + DMAR_PAGE_SIZE || 313281545Skib a->entry->start + a->size + a->offset + DMAR_PAGE_SIZE > 314281545Skib prev->end + prev->free_after) 315257251Skib return (false); 316257251Skib 317257251Skib /* No boundary crossing. */ 318281545Skib if (dmar_test_boundary(a->entry->start + a->offset, a->size, 319281545Skib a->common->boundary)) 320257251Skib return (true); 321257251Skib 322257251Skib /* 323281545Skib * The start + offset to start + offset + size region crosses 324281545Skib * the boundary. Check if there is enough space after the 325281545Skib * next boundary after the prev->end. 326257251Skib */ 327281545Skib bs = (a->entry->start + a->offset + a->common->boundary) & 328281545Skib ~(a->common->boundary - 1); 329257251Skib start = roundup2(bs, a->common->alignment); 330257251Skib /* DMAR_PAGE_SIZE to create gap after new entry. */ 331281545Skib if (start + a->offset + a->size + DMAR_PAGE_SIZE <= 332281545Skib prev->end + prev->free_after && 333281545Skib start + a->offset + a->size <= end && 334281545Skib dmar_test_boundary(start + a->offset, a->size, 335280425Skib a->common->boundary)) { 336257251Skib a->entry->start = start; 337257251Skib return (true); 338257251Skib } 339257251Skib 340257251Skib /* 341280425Skib * Not enough space to align at the requested boundary, or 342280425Skib * boundary is smaller than the size, but allowed to split. 343257251Skib * We already checked that start + size does not overlap end. 344257251Skib * 345257251Skib * XXXKIB. It is possible that bs is exactly at the start of 346257251Skib * the next entry, then we do not have gap. Ignore for now. 347257251Skib */ 348257251Skib if ((a->gas_flags & DMAR_GM_CANSPLIT) != 0) { 349257251Skib a->size = bs - a->entry->start; 350257251Skib return (true); 351257251Skib } 352257251Skib 353257251Skib return (false); 354257251Skib} 355257251Skib 356257251Skibstatic void 357257251Skibdmar_gas_match_insert(struct dmar_gas_match_args *a, 358257251Skib struct dmar_map_entry *prev) 359257251Skib{ 360257251Skib struct dmar_map_entry *next; 361257251Skib bool found; 362257251Skib 363257251Skib /* 364257251Skib * The prev->end is always aligned on the page size, which 365257251Skib * causes page alignment for the entry->start too. The size 366257251Skib * is checked to be multiple of the page size. 367257251Skib * 368257251Skib * The page sized gap is created between consequent 369257251Skib * allocations to ensure that out-of-bounds accesses fault. 370257251Skib */ 371257251Skib a->entry->end = a->entry->start + a->size; 372257251Skib 373257251Skib next = RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, prev); 374257251Skib KASSERT(next->start >= a->entry->end && 375280424Skib next->start - a->entry->start >= a->size && 376280424Skib prev->end <= a->entry->end, 377257251Skib ("dmar_gas_match_insert hole failed %p prev (%jx, %jx) " 378257251Skib "free_after %jx next (%jx, %jx) entry (%jx, %jx)", a->ctx, 379257251Skib (uintmax_t)prev->start, (uintmax_t)prev->end, 380257251Skib (uintmax_t)prev->free_after, 381257251Skib (uintmax_t)next->start, (uintmax_t)next->end, 382257251Skib (uintmax_t)a->entry->start, (uintmax_t)a->entry->end)); 383257251Skib 384257251Skib prev->free_after = a->entry->start - prev->end; 385257251Skib a->entry->free_after = next->start - a->entry->end; 386257251Skib 387257251Skib found = dmar_gas_rb_insert(a->ctx, a->entry); 388257251Skib KASSERT(found, ("found dup %p start %jx size %jx", 389257251Skib a->ctx, (uintmax_t)a->entry->start, (uintmax_t)a->size)); 390257251Skib a->entry->flags = DMAR_MAP_ENTRY_MAP; 391257251Skib 392257251Skib KASSERT(RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root, 393257251Skib a->entry) == prev, 394257251Skib ("entry %p prev %p inserted prev %p", a->entry, prev, 395257251Skib RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root, a->entry))); 396257251Skib KASSERT(RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, 397257251Skib a->entry) == next, 398257251Skib ("entry %p next %p inserted next %p", a->entry, next, 399257251Skib RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, a->entry))); 400257251Skib} 401257251Skib 402257251Skibstatic int 403257251Skibdmar_gas_lowermatch(struct dmar_gas_match_args *a, struct dmar_map_entry *prev) 404257251Skib{ 405257251Skib struct dmar_map_entry *l; 406257251Skib int ret; 407257251Skib 408257251Skib if (prev->end < a->common->lowaddr) { 409257251Skib a->entry->start = roundup2(prev->end + DMAR_PAGE_SIZE, 410257251Skib a->common->alignment); 411257251Skib if (dmar_gas_match_one(a, prev, a->common->lowaddr)) { 412257251Skib dmar_gas_match_insert(a, prev); 413257251Skib return (0); 414257251Skib } 415257251Skib } 416281545Skib if (prev->free_down < a->size + a->offset + DMAR_PAGE_SIZE) 417257251Skib return (ENOMEM); 418257251Skib l = RB_LEFT(prev, rb_entry); 419257251Skib if (l != NULL) { 420257251Skib ret = dmar_gas_lowermatch(a, l); 421257251Skib if (ret == 0) 422257251Skib return (0); 423257251Skib } 424257251Skib l = RB_RIGHT(prev, rb_entry); 425257251Skib if (l != NULL) 426257251Skib return (dmar_gas_lowermatch(a, l)); 427257251Skib return (ENOMEM); 428257251Skib} 429257251Skib 430257251Skibstatic int 431257251Skibdmar_gas_uppermatch(struct dmar_gas_match_args *a) 432257251Skib{ 433257251Skib struct dmar_map_entry *next, *prev, find_entry; 434257251Skib 435257251Skib find_entry.start = a->common->highaddr; 436257251Skib next = RB_NFIND(dmar_gas_entries_tree, &a->ctx->rb_root, &find_entry); 437257251Skib if (next == NULL) 438257251Skib return (ENOMEM); 439257251Skib prev = RB_PREV(dmar_gas_entries_tree, &a->ctx->rb_root, next); 440257251Skib KASSERT(prev != NULL, ("no prev %p %jx", a->ctx, 441257251Skib (uintmax_t)find_entry.start)); 442257251Skib for (;;) { 443257251Skib a->entry->start = prev->start + DMAR_PAGE_SIZE; 444257251Skib if (a->entry->start < a->common->highaddr) 445257251Skib a->entry->start = a->common->highaddr; 446257251Skib a->entry->start = roundup2(a->entry->start, 447257251Skib a->common->alignment); 448257251Skib if (dmar_gas_match_one(a, prev, a->ctx->end)) { 449257251Skib dmar_gas_match_insert(a, prev); 450257251Skib return (0); 451257251Skib } 452257251Skib 453257251Skib /* 454257251Skib * XXXKIB. This falls back to linear iteration over 455257251Skib * the free space in the high region. But high 456257251Skib * regions are almost unused, the code should be 457257251Skib * enough to cover the case, although in the 458257251Skib * non-optimal way. 459257251Skib */ 460257251Skib prev = next; 461257251Skib next = RB_NEXT(dmar_gas_entries_tree, &a->ctx->rb_root, prev); 462257251Skib KASSERT(next != NULL, ("no next %p %jx", a->ctx, 463257251Skib (uintmax_t)find_entry.start)); 464257251Skib if (next->end >= a->ctx->end) 465257251Skib return (ENOMEM); 466257251Skib } 467257251Skib} 468257251Skib 469257251Skibstatic int 470257251Skibdmar_gas_find_space(struct dmar_ctx *ctx, 471257251Skib const struct bus_dma_tag_common *common, dmar_gaddr_t size, 472281545Skib int offset, u_int flags, struct dmar_map_entry *entry) 473257251Skib{ 474257251Skib struct dmar_gas_match_args a; 475257251Skib int error; 476257251Skib 477257251Skib DMAR_CTX_ASSERT_LOCKED(ctx); 478257251Skib KASSERT(entry->flags == 0, ("dirty entry %p %p", ctx, entry)); 479257251Skib KASSERT((size & DMAR_PAGE_MASK) == 0, ("size %jx", (uintmax_t)size)); 480257251Skib 481257251Skib a.ctx = ctx; 482257251Skib a.size = size; 483281545Skib a.offset = offset; 484257251Skib a.common = common; 485257251Skib a.gas_flags = flags; 486257251Skib a.entry = entry; 487257251Skib 488257251Skib /* Handle lower region. */ 489257251Skib if (common->lowaddr > 0) { 490257251Skib error = dmar_gas_lowermatch(&a, RB_ROOT(&ctx->rb_root)); 491257251Skib if (error == 0) 492257251Skib return (0); 493257251Skib KASSERT(error == ENOMEM, 494257251Skib ("error %d from dmar_gas_lowermatch", error)); 495257251Skib } 496257251Skib /* Handle upper region. */ 497257251Skib if (common->highaddr >= ctx->end) 498257251Skib return (ENOMEM); 499257251Skib error = dmar_gas_uppermatch(&a); 500257251Skib KASSERT(error == ENOMEM, 501257251Skib ("error %d from dmar_gas_uppermatch", error)); 502257251Skib return (error); 503257251Skib} 504257251Skib 505257251Skibstatic int 506257251Skibdmar_gas_alloc_region(struct dmar_ctx *ctx, struct dmar_map_entry *entry, 507257251Skib u_int flags) 508257251Skib{ 509257251Skib struct dmar_map_entry *next, *prev; 510257251Skib bool found; 511257251Skib 512257251Skib DMAR_CTX_ASSERT_LOCKED(ctx); 513257251Skib 514257251Skib if ((entry->start & DMAR_PAGE_MASK) != 0 || 515257251Skib (entry->end & DMAR_PAGE_MASK) != 0) 516257251Skib return (EINVAL); 517257251Skib if (entry->start >= entry->end) 518257251Skib return (EINVAL); 519257251Skib if (entry->end >= ctx->end) 520257251Skib return (EINVAL); 521257251Skib 522257251Skib next = RB_NFIND(dmar_gas_entries_tree, &ctx->rb_root, entry); 523257251Skib KASSERT(next != NULL, ("next must be non-null %p %jx", ctx, 524257251Skib (uintmax_t)entry->start)); 525257251Skib prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, next); 526257251Skib /* prev could be NULL */ 527257251Skib 528257251Skib /* 529257251Skib * Adapt to broken BIOSes which specify overlapping RMRR 530257251Skib * entries. 531257251Skib * 532257251Skib * XXXKIB: this does not handle a case when prev or next 533257251Skib * entries are completely covered by the current one, which 534257251Skib * extends both ways. 535257251Skib */ 536257251Skib if (prev != NULL && prev->end > entry->start && 537257251Skib (prev->flags & DMAR_MAP_ENTRY_PLACE) == 0) { 538257251Skib if ((prev->flags & DMAR_MAP_ENTRY_RMRR) == 0) 539257251Skib return (EBUSY); 540257251Skib entry->start = prev->end; 541257251Skib } 542257251Skib if (next != NULL && next->start < entry->end && 543257251Skib (next->flags & DMAR_MAP_ENTRY_PLACE) == 0) { 544257251Skib if ((next->flags & DMAR_MAP_ENTRY_RMRR) == 0) 545257251Skib return (EBUSY); 546257251Skib entry->end = next->start; 547257251Skib } 548257251Skib if (entry->end == entry->start) 549257251Skib return (0); 550257251Skib 551257251Skib if (prev != NULL && prev->end > entry->start) { 552257251Skib /* This assumes that prev is the placeholder entry. */ 553257251Skib dmar_gas_rb_remove(ctx, prev); 554257251Skib prev = NULL; 555257251Skib } 556257251Skib if (next != NULL && next->start < entry->end) { 557257251Skib dmar_gas_rb_remove(ctx, next); 558257251Skib next = NULL; 559257251Skib } 560257251Skib 561257251Skib found = dmar_gas_rb_insert(ctx, entry); 562257251Skib KASSERT(found, ("found RMRR dup %p start %jx end %jx", 563257251Skib ctx, (uintmax_t)entry->start, (uintmax_t)entry->end)); 564257251Skib entry->flags = DMAR_MAP_ENTRY_RMRR; 565257251Skib 566257251Skib#ifdef INVARIANTS 567257251Skib struct dmar_map_entry *ip, *in; 568257251Skib ip = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 569257251Skib in = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 570257251Skib KASSERT(prev == NULL || ip == prev, 571257251Skib ("RMRR %p (%jx %jx) prev %p (%jx %jx) ins prev %p (%jx %jx)", 572257251Skib entry, entry->start, entry->end, prev, 573257251Skib prev == NULL ? 0 : prev->start, prev == NULL ? 0 : prev->end, 574257251Skib ip, ip == NULL ? 0 : ip->start, ip == NULL ? 0 : ip->end)); 575257251Skib KASSERT(next == NULL || in == next, 576257251Skib ("RMRR %p (%jx %jx) next %p (%jx %jx) ins next %p (%jx %jx)", 577257251Skib entry, entry->start, entry->end, next, 578257251Skib next == NULL ? 0 : next->start, next == NULL ? 0 : next->end, 579257251Skib in, in == NULL ? 0 : in->start, in == NULL ? 0 : in->end)); 580257251Skib#endif 581257251Skib 582257251Skib return (0); 583257251Skib} 584257251Skib 585257251Skibvoid 586257251Skibdmar_gas_free_space(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 587257251Skib{ 588257251Skib 589257251Skib DMAR_CTX_ASSERT_LOCKED(ctx); 590257251Skib KASSERT((entry->flags & (DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_RMRR | 591257251Skib DMAR_MAP_ENTRY_MAP)) == DMAR_MAP_ENTRY_MAP, 592257251Skib ("permanent entry %p %p", ctx, entry)); 593257251Skib 594257251Skib dmar_gas_rb_remove(ctx, entry); 595257251Skib entry->flags &= ~DMAR_MAP_ENTRY_MAP; 596257251Skib#ifdef INVARIANTS 597257251Skib if (dmar_check_free) 598257251Skib dmar_gas_check_free(ctx); 599257251Skib#endif 600257251Skib} 601257251Skib 602259512Skibvoid 603257251Skibdmar_gas_free_region(struct dmar_ctx *ctx, struct dmar_map_entry *entry) 604257251Skib{ 605257251Skib struct dmar_map_entry *next, *prev; 606257251Skib 607257251Skib DMAR_CTX_ASSERT_LOCKED(ctx); 608257251Skib KASSERT((entry->flags & (DMAR_MAP_ENTRY_PLACE | DMAR_MAP_ENTRY_RMRR | 609257251Skib DMAR_MAP_ENTRY_MAP)) == DMAR_MAP_ENTRY_RMRR, 610257251Skib ("non-RMRR entry %p %p", ctx, entry)); 611257251Skib 612257251Skib prev = RB_PREV(dmar_gas_entries_tree, &ctx->rb_root, entry); 613257251Skib next = RB_NEXT(dmar_gas_entries_tree, &ctx->rb_root, entry); 614257251Skib dmar_gas_rb_remove(ctx, entry); 615257251Skib entry->flags &= ~DMAR_MAP_ENTRY_RMRR; 616257251Skib 617257251Skib if (prev == NULL) 618257251Skib dmar_gas_rb_insert(ctx, ctx->first_place); 619257251Skib if (next == NULL) 620257251Skib dmar_gas_rb_insert(ctx, ctx->last_place); 621257251Skib} 622257251Skib 623257251Skibint 624257251Skibdmar_gas_map(struct dmar_ctx *ctx, const struct bus_dma_tag_common *common, 625281545Skib dmar_gaddr_t size, int offset, u_int eflags, u_int flags, vm_page_t *ma, 626257251Skib struct dmar_map_entry **res) 627257251Skib{ 628257251Skib struct dmar_map_entry *entry; 629257251Skib int error; 630257251Skib 631257251Skib KASSERT((flags & ~(DMAR_GM_CANWAIT | DMAR_GM_CANSPLIT)) == 0, 632257251Skib ("invalid flags 0x%x", flags)); 633257251Skib 634257251Skib entry = dmar_gas_alloc_entry(ctx, (flags & DMAR_GM_CANWAIT) != 0 ? 635257251Skib DMAR_PGF_WAITOK : 0); 636257251Skib if (entry == NULL) 637257251Skib return (ENOMEM); 638257251Skib DMAR_CTX_LOCK(ctx); 639281545Skib error = dmar_gas_find_space(ctx, common, size, offset, flags, entry); 640257251Skib if (error == ENOMEM) { 641257251Skib DMAR_CTX_UNLOCK(ctx); 642257251Skib dmar_gas_free_entry(ctx, entry); 643257251Skib return (error); 644257251Skib } 645257251Skib#ifdef INVARIANTS 646257251Skib if (dmar_check_free) 647257251Skib dmar_gas_check_free(ctx); 648257251Skib#endif 649257251Skib KASSERT(error == 0, 650257251Skib ("unexpected error %d from dmar_gas_find_entry", error)); 651257251Skib KASSERT(entry->end < ctx->end, ("allocated GPA %jx, max GPA %jx", 652257251Skib (uintmax_t)entry->end, (uintmax_t)ctx->end)); 653257251Skib entry->flags |= eflags; 654257251Skib DMAR_CTX_UNLOCK(ctx); 655257251Skib 656280874Skib error = ctx_map_buf(ctx, entry->start, entry->end - entry->start, ma, 657257251Skib ((eflags & DMAR_MAP_ENTRY_READ) != 0 ? DMAR_PTE_R : 0) | 658257251Skib ((eflags & DMAR_MAP_ENTRY_WRITE) != 0 ? DMAR_PTE_W : 0) | 659257251Skib ((eflags & DMAR_MAP_ENTRY_SNOOP) != 0 ? DMAR_PTE_SNP : 0) | 660257251Skib ((eflags & DMAR_MAP_ENTRY_TM) != 0 ? DMAR_PTE_TM : 0), 661257251Skib (flags & DMAR_GM_CANWAIT) != 0 ? DMAR_PGF_WAITOK : 0); 662257251Skib if (error == ENOMEM) { 663259512Skib dmar_ctx_unload_entry(entry, true); 664257251Skib return (error); 665257251Skib } 666257251Skib KASSERT(error == 0, 667257251Skib ("unexpected error %d from ctx_map_buf", error)); 668257251Skib 669257251Skib *res = entry; 670257251Skib return (0); 671257251Skib} 672257251Skib 673257251Skibint 674257251Skibdmar_gas_map_region(struct dmar_ctx *ctx, struct dmar_map_entry *entry, 675257251Skib u_int eflags, u_int flags, vm_page_t *ma) 676257251Skib{ 677257251Skib dmar_gaddr_t start; 678257251Skib int error; 679257251Skib 680257251Skib KASSERT(entry->flags == 0, ("used RMRR entry %p %p %x", ctx, 681257251Skib entry, entry->flags)); 682257251Skib KASSERT((flags & ~(DMAR_GM_CANWAIT)) == 0, 683257251Skib ("invalid flags 0x%x", flags)); 684257251Skib 685257251Skib start = entry->start; 686257251Skib DMAR_CTX_LOCK(ctx); 687257251Skib error = dmar_gas_alloc_region(ctx, entry, flags); 688257251Skib if (error != 0) { 689257251Skib DMAR_CTX_UNLOCK(ctx); 690257251Skib return (error); 691257251Skib } 692257251Skib entry->flags |= eflags; 693257251Skib DMAR_CTX_UNLOCK(ctx); 694257251Skib if (entry->end == entry->start) 695257251Skib return (0); 696257251Skib 697257251Skib error = ctx_map_buf(ctx, entry->start, entry->end - entry->start, 698257251Skib ma + OFF_TO_IDX(start - entry->start), 699257251Skib ((eflags & DMAR_MAP_ENTRY_READ) != 0 ? DMAR_PTE_R : 0) | 700257251Skib ((eflags & DMAR_MAP_ENTRY_WRITE) != 0 ? DMAR_PTE_W : 0) | 701257251Skib ((eflags & DMAR_MAP_ENTRY_SNOOP) != 0 ? DMAR_PTE_SNP : 0) | 702257251Skib ((eflags & DMAR_MAP_ENTRY_TM) != 0 ? DMAR_PTE_TM : 0), 703257251Skib (flags & DMAR_GM_CANWAIT) != 0 ? DMAR_PGF_WAITOK : 0); 704257251Skib if (error == ENOMEM) { 705259512Skib dmar_ctx_unload_entry(entry, false); 706257251Skib return (error); 707257251Skib } 708257251Skib KASSERT(error == 0, 709257251Skib ("unexpected error %d from ctx_map_buf", error)); 710257251Skib 711257251Skib return (0); 712257251Skib} 713257251Skib 714257251Skibint 715257251Skibdmar_gas_reserve_region(struct dmar_ctx *ctx, dmar_gaddr_t start, 716257251Skib dmar_gaddr_t end) 717257251Skib{ 718257251Skib struct dmar_map_entry *entry; 719257251Skib int error; 720257251Skib 721257251Skib entry = dmar_gas_alloc_entry(ctx, DMAR_PGF_WAITOK); 722257251Skib entry->start = start; 723257251Skib entry->end = end; 724257251Skib DMAR_CTX_LOCK(ctx); 725257251Skib error = dmar_gas_alloc_region(ctx, entry, DMAR_GM_CANWAIT); 726257251Skib if (error == 0) 727257251Skib entry->flags |= DMAR_MAP_ENTRY_UNMAPPED; 728257251Skib DMAR_CTX_UNLOCK(ctx); 729257251Skib if (error != 0) 730257251Skib dmar_gas_free_entry(ctx, entry); 731257251Skib return (error); 732257251Skib} 733