13024e8afSRuslan Bukin /*- 23024e8afSRuslan Bukin * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 33024e8afSRuslan Bukin * 43024e8afSRuslan Bukin * Copyright (c) 2013 The FreeBSD Foundation 53024e8afSRuslan Bukin * 63024e8afSRuslan Bukin * This software was developed by Konstantin Belousov <kib@FreeBSD.org> 73024e8afSRuslan Bukin * under sponsorship from the FreeBSD Foundation. 83024e8afSRuslan Bukin * 93024e8afSRuslan Bukin * Redistribution and use in source and binary forms, with or without 103024e8afSRuslan Bukin * modification, are permitted provided that the following conditions 113024e8afSRuslan Bukin * are met: 123024e8afSRuslan Bukin * 1. Redistributions of source code must retain the above copyright 133024e8afSRuslan Bukin * notice, this list of conditions and the following disclaimer. 143024e8afSRuslan Bukin * 2. Redistributions in binary form must reproduce the above copyright 153024e8afSRuslan Bukin * notice, this list of conditions and the following disclaimer in the 163024e8afSRuslan Bukin * documentation and/or other materials provided with the distribution. 173024e8afSRuslan Bukin * 183024e8afSRuslan Bukin * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 193024e8afSRuslan Bukin * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 203024e8afSRuslan Bukin * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 213024e8afSRuslan Bukin * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 223024e8afSRuslan Bukin * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 233024e8afSRuslan Bukin * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 243024e8afSRuslan Bukin * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 253024e8afSRuslan Bukin * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 263024e8afSRuslan Bukin * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 273024e8afSRuslan Bukin * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 283024e8afSRuslan Bukin * SUCH DAMAGE. 293024e8afSRuslan Bukin */ 303024e8afSRuslan Bukin 313024e8afSRuslan Bukin #include <sys/cdefs.h> 323024e8afSRuslan Bukin __FBSDID("$FreeBSD$"); 333024e8afSRuslan Bukin 343024e8afSRuslan Bukin #define RB_AUGMENT(entry) iommu_gas_augment_entry(entry) 353024e8afSRuslan Bukin 363024e8afSRuslan Bukin #include <sys/param.h> 373024e8afSRuslan Bukin #include <sys/systm.h> 383024e8afSRuslan Bukin #include <sys/malloc.h> 393024e8afSRuslan Bukin #include <sys/bus.h> 403024e8afSRuslan Bukin #include <sys/interrupt.h> 413024e8afSRuslan Bukin #include <sys/kernel.h> 423024e8afSRuslan Bukin #include <sys/ktr.h> 433024e8afSRuslan Bukin #include <sys/lock.h> 443024e8afSRuslan Bukin #include <sys/proc.h> 453024e8afSRuslan Bukin #include <sys/rwlock.h> 463024e8afSRuslan Bukin #include <sys/memdesc.h> 473024e8afSRuslan Bukin #include <sys/mutex.h> 483024e8afSRuslan Bukin #include <sys/sysctl.h> 493024e8afSRuslan Bukin #include <sys/rman.h> 503024e8afSRuslan Bukin #include <sys/taskqueue.h> 513024e8afSRuslan Bukin #include <sys/tree.h> 523024e8afSRuslan Bukin #include <sys/uio.h> 533024e8afSRuslan Bukin #include <sys/vmem.h> 543024e8afSRuslan Bukin #include <vm/vm.h> 553024e8afSRuslan Bukin #include <vm/vm_extern.h> 563024e8afSRuslan Bukin #include <vm/vm_kern.h> 573024e8afSRuslan Bukin #include <vm/vm_object.h> 583024e8afSRuslan Bukin #include <vm/vm_page.h> 593024e8afSRuslan Bukin #include <vm/vm_map.h> 603024e8afSRuslan Bukin #include <vm/uma.h> 61c8597a1fSRuslan Bukin #include <dev/pci/pcireg.h> 62c8597a1fSRuslan Bukin #include <dev/pci/pcivar.h> 63c8597a1fSRuslan Bukin #include <dev/iommu/iommu.h> 64f23f7d3aSRuslan Bukin #include <dev/iommu/iommu_gas.h> 65e707c8beSRuslan Bukin #include <dev/iommu/iommu_msi.h> 663024e8afSRuslan Bukin #include <machine/atomic.h> 673024e8afSRuslan Bukin #include <machine/bus.h> 683024e8afSRuslan Bukin #include <machine/md_var.h> 69c4cd6990SRuslan Bukin #include <machine/iommu.h> 70c8597a1fSRuslan Bukin #include <dev/iommu/busdma_iommu.h> 713024e8afSRuslan Bukin 723024e8afSRuslan Bukin /* 733024e8afSRuslan Bukin * Guest Address Space management. 743024e8afSRuslan Bukin */ 753024e8afSRuslan Bukin 763024e8afSRuslan Bukin static uma_zone_t iommu_map_entry_zone; 773024e8afSRuslan Bukin 789c843a40SRuslan Bukin #ifdef INVARIANTS 799c843a40SRuslan Bukin static int iommu_check_free; 809c843a40SRuslan Bukin #endif 819c843a40SRuslan Bukin 823024e8afSRuslan Bukin static void 833024e8afSRuslan Bukin intel_gas_init(void) 843024e8afSRuslan Bukin { 853024e8afSRuslan Bukin 863024e8afSRuslan Bukin iommu_map_entry_zone = uma_zcreate("IOMMU_MAP_ENTRY", 873024e8afSRuslan Bukin sizeof(struct iommu_map_entry), NULL, NULL, 883024e8afSRuslan Bukin NULL, NULL, UMA_ALIGN_PTR, UMA_ZONE_NODUMP); 893024e8afSRuslan Bukin } 903024e8afSRuslan Bukin SYSINIT(intel_gas, SI_SUB_DRIVERS, SI_ORDER_FIRST, intel_gas_init, NULL); 913024e8afSRuslan Bukin 923024e8afSRuslan Bukin struct iommu_map_entry * 933024e8afSRuslan Bukin iommu_gas_alloc_entry(struct iommu_domain *domain, u_int flags) 943024e8afSRuslan Bukin { 953024e8afSRuslan Bukin struct iommu_map_entry *res; 963024e8afSRuslan Bukin 9715f6baf4SRuslan Bukin KASSERT((flags & ~(IOMMU_PGF_WAITOK)) == 0, 983024e8afSRuslan Bukin ("unsupported flags %x", flags)); 993024e8afSRuslan Bukin 10015f6baf4SRuslan Bukin res = uma_zalloc(iommu_map_entry_zone, ((flags & IOMMU_PGF_WAITOK) != 1013024e8afSRuslan Bukin 0 ? M_WAITOK : M_NOWAIT) | M_ZERO); 10242736dc4SAlan Cox if (res != NULL && domain != NULL) { 1033024e8afSRuslan Bukin res->domain = domain; 1043024e8afSRuslan Bukin atomic_add_int(&domain->entries_cnt, 1); 1053024e8afSRuslan Bukin } 1063024e8afSRuslan Bukin return (res); 1073024e8afSRuslan Bukin } 1083024e8afSRuslan Bukin 1093024e8afSRuslan Bukin void 1104670f908SAlan Cox iommu_gas_free_entry(struct iommu_map_entry *entry) 1113024e8afSRuslan Bukin { 1124670f908SAlan Cox struct iommu_domain *domain; 1133024e8afSRuslan Bukin 1144670f908SAlan Cox domain = entry->domain; 11542736dc4SAlan Cox if (domain != NULL) 1163024e8afSRuslan Bukin atomic_subtract_int(&domain->entries_cnt, 1); 1173024e8afSRuslan Bukin uma_zfree(iommu_map_entry_zone, entry); 1183024e8afSRuslan Bukin } 1193024e8afSRuslan Bukin 1203024e8afSRuslan Bukin static int 1213024e8afSRuslan Bukin iommu_gas_cmp_entries(struct iommu_map_entry *a, struct iommu_map_entry *b) 1223024e8afSRuslan Bukin { 1233024e8afSRuslan Bukin 1243024e8afSRuslan Bukin /* Last entry have zero size, so <= */ 1253024e8afSRuslan Bukin KASSERT(a->start <= a->end, ("inverted entry %p (%jx, %jx)", 1263024e8afSRuslan Bukin a, (uintmax_t)a->start, (uintmax_t)a->end)); 1273024e8afSRuslan Bukin KASSERT(b->start <= b->end, ("inverted entry %p (%jx, %jx)", 1283024e8afSRuslan Bukin b, (uintmax_t)b->start, (uintmax_t)b->end)); 1293024e8afSRuslan Bukin KASSERT(a->end <= b->start || b->end <= a->start || 1303024e8afSRuslan Bukin a->end == a->start || b->end == b->start, 1313024e8afSRuslan Bukin ("overlapping entries %p (%jx, %jx) %p (%jx, %jx)", 1323024e8afSRuslan Bukin a, (uintmax_t)a->start, (uintmax_t)a->end, 1333024e8afSRuslan Bukin b, (uintmax_t)b->start, (uintmax_t)b->end)); 1343024e8afSRuslan Bukin 1353024e8afSRuslan Bukin if (a->end < b->end) 1363024e8afSRuslan Bukin return (-1); 1373024e8afSRuslan Bukin else if (b->end < a->end) 1383024e8afSRuslan Bukin return (1); 1393024e8afSRuslan Bukin return (0); 1403024e8afSRuslan Bukin } 1413024e8afSRuslan Bukin 1423024e8afSRuslan Bukin static void 1433024e8afSRuslan Bukin iommu_gas_augment_entry(struct iommu_map_entry *entry) 1443024e8afSRuslan Bukin { 1453024e8afSRuslan Bukin struct iommu_map_entry *child; 1463024e8afSRuslan Bukin iommu_gaddr_t free_down; 1473024e8afSRuslan Bukin 1483024e8afSRuslan Bukin free_down = 0; 1493024e8afSRuslan Bukin if ((child = RB_LEFT(entry, rb_entry)) != NULL) { 1503024e8afSRuslan Bukin free_down = MAX(free_down, child->free_down); 1513024e8afSRuslan Bukin free_down = MAX(free_down, entry->start - child->last); 1523024e8afSRuslan Bukin entry->first = child->first; 1533024e8afSRuslan Bukin } else 1543024e8afSRuslan Bukin entry->first = entry->start; 1553024e8afSRuslan Bukin 1563024e8afSRuslan Bukin if ((child = RB_RIGHT(entry, rb_entry)) != NULL) { 1573024e8afSRuslan Bukin free_down = MAX(free_down, child->free_down); 1583024e8afSRuslan Bukin free_down = MAX(free_down, child->first - entry->end); 1593024e8afSRuslan Bukin entry->last = child->last; 1603024e8afSRuslan Bukin } else 1613024e8afSRuslan Bukin entry->last = entry->end; 1623024e8afSRuslan Bukin entry->free_down = free_down; 1633024e8afSRuslan Bukin } 1643024e8afSRuslan Bukin 1653024e8afSRuslan Bukin RB_GENERATE(iommu_gas_entries_tree, iommu_map_entry, rb_entry, 1663024e8afSRuslan Bukin iommu_gas_cmp_entries); 1673024e8afSRuslan Bukin 1683024e8afSRuslan Bukin #ifdef INVARIANTS 1693024e8afSRuslan Bukin static void 1703024e8afSRuslan Bukin iommu_gas_check_free(struct iommu_domain *domain) 1713024e8afSRuslan Bukin { 1723024e8afSRuslan Bukin struct iommu_map_entry *entry, *l, *r; 1733024e8afSRuslan Bukin iommu_gaddr_t v; 1743024e8afSRuslan Bukin 1753024e8afSRuslan Bukin RB_FOREACH(entry, iommu_gas_entries_tree, &domain->rb_root) { 176b64dca2bSRuslan Bukin KASSERT(domain == entry->domain, 1773024e8afSRuslan Bukin ("mismatched free domain %p entry %p entry->domain %p", 1783024e8afSRuslan Bukin domain, entry, entry->domain)); 1793024e8afSRuslan Bukin l = RB_LEFT(entry, rb_entry); 1803024e8afSRuslan Bukin r = RB_RIGHT(entry, rb_entry); 1813024e8afSRuslan Bukin v = 0; 1823024e8afSRuslan Bukin if (l != NULL) { 1833024e8afSRuslan Bukin v = MAX(v, l->free_down); 1843024e8afSRuslan Bukin v = MAX(v, entry->start - l->last); 1853024e8afSRuslan Bukin } 1863024e8afSRuslan Bukin if (r != NULL) { 1873024e8afSRuslan Bukin v = MAX(v, r->free_down); 1883024e8afSRuslan Bukin v = MAX(v, r->first - entry->end); 1893024e8afSRuslan Bukin } 1903024e8afSRuslan Bukin MPASS(entry->free_down == v); 1913024e8afSRuslan Bukin } 1923024e8afSRuslan Bukin } 1933024e8afSRuslan Bukin #endif 1943024e8afSRuslan Bukin 1953024e8afSRuslan Bukin static bool 1963024e8afSRuslan Bukin iommu_gas_rb_insert(struct iommu_domain *domain, struct iommu_map_entry *entry) 1973024e8afSRuslan Bukin { 1983024e8afSRuslan Bukin struct iommu_map_entry *found; 1993024e8afSRuslan Bukin 200da33f6d7SAlan Cox found = RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, entry); 2013024e8afSRuslan Bukin return (found == NULL); 2023024e8afSRuslan Bukin } 2033024e8afSRuslan Bukin 2043024e8afSRuslan Bukin static void 2053024e8afSRuslan Bukin iommu_gas_rb_remove(struct iommu_domain *domain, struct iommu_map_entry *entry) 2063024e8afSRuslan Bukin { 2073024e8afSRuslan Bukin 2083024e8afSRuslan Bukin RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); 2093024e8afSRuslan Bukin } 2103024e8afSRuslan Bukin 211f5cafae1SRuslan Bukin struct iommu_domain * 212f5cafae1SRuslan Bukin iommu_get_ctx_domain(struct iommu_ctx *ctx) 213f5cafae1SRuslan Bukin { 214f5cafae1SRuslan Bukin 215f5cafae1SRuslan Bukin return (ctx->domain); 216f5cafae1SRuslan Bukin } 217f5cafae1SRuslan Bukin 2183024e8afSRuslan Bukin void 2193024e8afSRuslan Bukin iommu_gas_init_domain(struct iommu_domain *domain) 2203024e8afSRuslan Bukin { 2213024e8afSRuslan Bukin struct iommu_map_entry *begin, *end; 2223024e8afSRuslan Bukin 22315f6baf4SRuslan Bukin begin = iommu_gas_alloc_entry(domain, IOMMU_PGF_WAITOK); 22415f6baf4SRuslan Bukin end = iommu_gas_alloc_entry(domain, IOMMU_PGF_WAITOK); 2253024e8afSRuslan Bukin 2263024e8afSRuslan Bukin IOMMU_DOMAIN_LOCK(domain); 2273024e8afSRuslan Bukin KASSERT(domain->entries_cnt == 2, ("dirty domain %p", domain)); 2283024e8afSRuslan Bukin KASSERT(RB_EMPTY(&domain->rb_root), 2293024e8afSRuslan Bukin ("non-empty entries %p", domain)); 2303024e8afSRuslan Bukin 2313024e8afSRuslan Bukin begin->start = 0; 2323024e8afSRuslan Bukin begin->end = IOMMU_PAGE_SIZE; 2333024e8afSRuslan Bukin begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; 2343024e8afSRuslan Bukin iommu_gas_rb_insert(domain, begin); 2353024e8afSRuslan Bukin 2363024e8afSRuslan Bukin end->start = domain->end; 2373024e8afSRuslan Bukin end->end = domain->end; 2383024e8afSRuslan Bukin end->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED; 2393024e8afSRuslan Bukin iommu_gas_rb_insert(domain, end); 2403024e8afSRuslan Bukin 2413024e8afSRuslan Bukin domain->first_place = begin; 2423024e8afSRuslan Bukin domain->last_place = end; 24315f6baf4SRuslan Bukin domain->flags |= IOMMU_DOMAIN_GAS_INITED; 2443024e8afSRuslan Bukin IOMMU_DOMAIN_UNLOCK(domain); 2453024e8afSRuslan Bukin } 2463024e8afSRuslan Bukin 2473024e8afSRuslan Bukin void 2483024e8afSRuslan Bukin iommu_gas_fini_domain(struct iommu_domain *domain) 2493024e8afSRuslan Bukin { 2503024e8afSRuslan Bukin struct iommu_map_entry *entry, *entry1; 2513024e8afSRuslan Bukin 2523024e8afSRuslan Bukin IOMMU_DOMAIN_ASSERT_LOCKED(domain); 2533024e8afSRuslan Bukin KASSERT(domain->entries_cnt == 2, 2543024e8afSRuslan Bukin ("domain still in use %p", domain)); 2553024e8afSRuslan Bukin 2563024e8afSRuslan Bukin entry = RB_MIN(iommu_gas_entries_tree, &domain->rb_root); 2573024e8afSRuslan Bukin KASSERT(entry->start == 0, ("start entry start %p", domain)); 2583024e8afSRuslan Bukin KASSERT(entry->end == IOMMU_PAGE_SIZE, ("start entry end %p", domain)); 259dea8594fSRuslan Bukin KASSERT(entry->flags == 260dea8594fSRuslan Bukin (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED), 2613024e8afSRuslan Bukin ("start entry flags %p", domain)); 2623024e8afSRuslan Bukin RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); 2634670f908SAlan Cox iommu_gas_free_entry(entry); 2643024e8afSRuslan Bukin 2653024e8afSRuslan Bukin entry = RB_MAX(iommu_gas_entries_tree, &domain->rb_root); 2663024e8afSRuslan Bukin KASSERT(entry->start == domain->end, ("end entry start %p", domain)); 2673024e8afSRuslan Bukin KASSERT(entry->end == domain->end, ("end entry end %p", domain)); 268dea8594fSRuslan Bukin KASSERT(entry->flags == 269dea8594fSRuslan Bukin (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED), 2703024e8afSRuslan Bukin ("end entry flags %p", domain)); 2713024e8afSRuslan Bukin RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry); 2724670f908SAlan Cox iommu_gas_free_entry(entry); 2733024e8afSRuslan Bukin 2743024e8afSRuslan Bukin RB_FOREACH_SAFE(entry, iommu_gas_entries_tree, &domain->rb_root, 2753024e8afSRuslan Bukin entry1) { 2763024e8afSRuslan Bukin KASSERT((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0, 2773024e8afSRuslan Bukin ("non-RMRR entry left %p", domain)); 2783024e8afSRuslan Bukin RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, 2793024e8afSRuslan Bukin entry); 2804670f908SAlan Cox iommu_gas_free_entry(entry); 2813024e8afSRuslan Bukin } 2823024e8afSRuslan Bukin } 2833024e8afSRuslan Bukin 2843024e8afSRuslan Bukin struct iommu_gas_match_args { 2853024e8afSRuslan Bukin struct iommu_domain *domain; 2863024e8afSRuslan Bukin iommu_gaddr_t size; 2873024e8afSRuslan Bukin int offset; 2883024e8afSRuslan Bukin const struct bus_dma_tag_common *common; 2893024e8afSRuslan Bukin u_int gas_flags; 2903024e8afSRuslan Bukin struct iommu_map_entry *entry; 2913024e8afSRuslan Bukin }; 2923024e8afSRuslan Bukin 2933024e8afSRuslan Bukin /* 2943024e8afSRuslan Bukin * The interval [beg, end) is a free interval between two iommu_map_entries. 295e0e8d0c8SDoug Moore * Addresses can be allocated only in the range [lbound, ubound). Try to 296e0e8d0c8SDoug Moore * allocate space in the free interval, subject to the conditions expressed by 297e0e8d0c8SDoug Moore * a, and return 'true' if and only if the allocation attempt succeeds. 2983024e8afSRuslan Bukin */ 2993024e8afSRuslan Bukin static bool 3003024e8afSRuslan Bukin iommu_gas_match_one(struct iommu_gas_match_args *a, iommu_gaddr_t beg, 301e0e8d0c8SDoug Moore iommu_gaddr_t end, iommu_gaddr_t lbound, iommu_gaddr_t ubound) 3023024e8afSRuslan Bukin { 303e0e8d0c8SDoug Moore struct iommu_map_entry *entry; 304e0e8d0c8SDoug Moore iommu_gaddr_t first, size, start; 305e0e8d0c8SDoug Moore bool found __diagused; 306e0e8d0c8SDoug Moore int offset; 3073024e8afSRuslan Bukin 308da33f6d7SAlan Cox /* 309da33f6d7SAlan Cox * The prev->end is always aligned on the page size, which 310da33f6d7SAlan Cox * causes page alignment for the entry->start too. 311da33f6d7SAlan Cox * 312e0e8d0c8SDoug Moore * Create IOMMU_PAGE_SIZE gaps before, after new entry 313e0e8d0c8SDoug Moore * to ensure that out-of-bounds accesses fault. 314da33f6d7SAlan Cox */ 315e0e8d0c8SDoug Moore beg = MAX(beg + IOMMU_PAGE_SIZE, lbound); 316e0e8d0c8SDoug Moore start = roundup2(beg, a->common->alignment); 317e0e8d0c8SDoug Moore if (start < beg) 318e0e8d0c8SDoug Moore return (false); 319e0e8d0c8SDoug Moore end = MIN(end - IOMMU_PAGE_SIZE, ubound); 320e0e8d0c8SDoug Moore offset = a->offset; 321e0e8d0c8SDoug Moore size = a->size; 322e0e8d0c8SDoug Moore if (start + offset + size > end) 3233024e8afSRuslan Bukin return (false); 3243024e8afSRuslan Bukin 325e0e8d0c8SDoug Moore /* Check for and try to skip past boundary crossing. */ 326e0e8d0c8SDoug Moore if (!vm_addr_bound_ok(start + offset, size, a->common->boundary)) { 3273024e8afSRuslan Bukin /* 3283024e8afSRuslan Bukin * The start + offset to start + offset + size region crosses 329e0e8d0c8SDoug Moore * the boundary. Check if there is enough space after the next 330e0e8d0c8SDoug Moore * boundary after the beg. 3313024e8afSRuslan Bukin */ 332e0e8d0c8SDoug Moore first = start; 333e0e8d0c8SDoug Moore beg = roundup2(start + offset + 1, a->common->boundary); 334e0e8d0c8SDoug Moore start = roundup2(beg, a->common->alignment); 335e0e8d0c8SDoug Moore 336e0e8d0c8SDoug Moore if (start + offset + size > end || 337e0e8d0c8SDoug Moore !vm_addr_bound_ok(start + offset, size, 3383024e8afSRuslan Bukin a->common->boundary)) { 3393024e8afSRuslan Bukin /* 340e0e8d0c8SDoug Moore * Not enough space to align at the requested boundary, 341e0e8d0c8SDoug Moore * or boundary is smaller than the size, but allowed to 342e0e8d0c8SDoug Moore * split. We already checked that start + size does not 343e0e8d0c8SDoug Moore * overlap ubound. 3443024e8afSRuslan Bukin * 345e0e8d0c8SDoug Moore * XXXKIB. It is possible that beg is exactly at the 346e0e8d0c8SDoug Moore * start of the next entry, then we do not have gap. 347e0e8d0c8SDoug Moore * Ignore for now. 3483024e8afSRuslan Bukin */ 349e0e8d0c8SDoug Moore if ((a->gas_flags & IOMMU_MF_CANSPLIT) == 0) 350e0e8d0c8SDoug Moore return (false); 351e0e8d0c8SDoug Moore size = beg - first - offset; 352e0e8d0c8SDoug Moore start = first; 353e0e8d0c8SDoug Moore } 354e0e8d0c8SDoug Moore } 355e0e8d0c8SDoug Moore entry = a->entry; 356e0e8d0c8SDoug Moore entry->start = start; 357e0e8d0c8SDoug Moore entry->end = start + roundup2(size + offset, IOMMU_PAGE_SIZE); 358e0e8d0c8SDoug Moore entry->flags = IOMMU_MAP_ENTRY_MAP; 359e0e8d0c8SDoug Moore found = iommu_gas_rb_insert(a->domain, entry); 360e0e8d0c8SDoug Moore KASSERT(found, ("found dup %p start %jx size %jx", 361e0e8d0c8SDoug Moore a->domain, (uintmax_t)start, (uintmax_t)size)); 3623024e8afSRuslan Bukin return (true); 3633024e8afSRuslan Bukin } 3643024e8afSRuslan Bukin 365e0e8d0c8SDoug Moore /* Find the next entry that might abut a big-enough range. */ 366e0e8d0c8SDoug Moore static struct iommu_map_entry * 367e0e8d0c8SDoug Moore iommu_gas_next(struct iommu_map_entry *curr, iommu_gaddr_t min_free) 3683024e8afSRuslan Bukin { 369e0e8d0c8SDoug Moore struct iommu_map_entry *next; 3703024e8afSRuslan Bukin 371e0e8d0c8SDoug Moore if ((next = RB_RIGHT(curr, rb_entry)) != NULL && 372e0e8d0c8SDoug Moore next->free_down >= min_free) { 373e0e8d0c8SDoug Moore /* Find next entry in right subtree. */ 374e0e8d0c8SDoug Moore do 375e0e8d0c8SDoug Moore curr = next; 376e0e8d0c8SDoug Moore while ((next = RB_LEFT(curr, rb_entry)) != NULL && 377e0e8d0c8SDoug Moore next->free_down >= min_free); 378e0e8d0c8SDoug Moore } else { 379e0e8d0c8SDoug Moore /* Find next entry in a left-parent ancestor. */ 380e0e8d0c8SDoug Moore while ((next = RB_PARENT(curr, rb_entry)) != NULL && 381e0e8d0c8SDoug Moore curr == RB_RIGHT(next, rb_entry)) 382e0e8d0c8SDoug Moore curr = next; 383e0e8d0c8SDoug Moore curr = next; 384e0e8d0c8SDoug Moore } 385e0e8d0c8SDoug Moore return (curr); 3863024e8afSRuslan Bukin } 3873024e8afSRuslan Bukin 3883024e8afSRuslan Bukin static int 389e0e8d0c8SDoug Moore iommu_gas_find_space(struct iommu_gas_match_args *a) 3903024e8afSRuslan Bukin { 391e0e8d0c8SDoug Moore struct iommu_domain *domain; 392e0e8d0c8SDoug Moore struct iommu_map_entry *curr, *first; 393e0e8d0c8SDoug Moore iommu_gaddr_t addr, min_free; 394e0e8d0c8SDoug Moore 395e0e8d0c8SDoug Moore IOMMU_DOMAIN_ASSERT_LOCKED(a->domain); 396e0e8d0c8SDoug Moore KASSERT(a->entry->flags == 0, 397e0e8d0c8SDoug Moore ("dirty entry %p %p", a->domain, a->entry)); 3983024e8afSRuslan Bukin 399b831865fSDoug Moore /* 400b831865fSDoug Moore * If the subtree doesn't have free space for the requested allocation 401f979ad00SDoug Moore * plus two guard pages, skip it. 402b831865fSDoug Moore */ 403f979ad00SDoug Moore min_free = 2 * IOMMU_PAGE_SIZE + 404f979ad00SDoug Moore roundup2(a->size + a->offset, IOMMU_PAGE_SIZE); 405f979ad00SDoug Moore 406e0e8d0c8SDoug Moore /* 407e0e8d0c8SDoug Moore * Find the first entry in the lower region that could abut a big-enough 408e0e8d0c8SDoug Moore * range. 409e0e8d0c8SDoug Moore */ 410e0e8d0c8SDoug Moore curr = RB_ROOT(&a->domain->rb_root); 411f979ad00SDoug Moore first = NULL; 412e0e8d0c8SDoug Moore while (curr != NULL && curr->free_down >= min_free) { 413e0e8d0c8SDoug Moore first = curr; 414e0e8d0c8SDoug Moore curr = RB_LEFT(curr, rb_entry); 415f979ad00SDoug Moore } 416f979ad00SDoug Moore 417f979ad00SDoug Moore /* 418f979ad00SDoug Moore * Walk the big-enough ranges until one satisfies alignment 419f979ad00SDoug Moore * requirements, or violates lowaddr address requirement. 420f979ad00SDoug Moore */ 421e0e8d0c8SDoug Moore addr = a->common->lowaddr + 1; 422e0e8d0c8SDoug Moore for (curr = first; curr != NULL; 423e0e8d0c8SDoug Moore curr = iommu_gas_next(curr, min_free)) { 424e0e8d0c8SDoug Moore if ((first = RB_LEFT(curr, rb_entry)) != NULL && 425e0e8d0c8SDoug Moore iommu_gas_match_one(a, first->last, curr->start, 426e0e8d0c8SDoug Moore 0, addr)) 42730031172SDoug Moore return (0); 428e0e8d0c8SDoug Moore if (curr->end >= addr) { 429e0e8d0c8SDoug Moore /* All remaining ranges >= addr */ 430f979ad00SDoug Moore break; 431f979ad00SDoug Moore } 432e0e8d0c8SDoug Moore if ((first = RB_RIGHT(curr, rb_entry)) != NULL && 433e0e8d0c8SDoug Moore iommu_gas_match_one(a, curr->end, first->first, 434e0e8d0c8SDoug Moore 0, addr)) 4353024e8afSRuslan Bukin return (0); 4363024e8afSRuslan Bukin } 4373024e8afSRuslan Bukin 438b831865fSDoug Moore /* 439e0e8d0c8SDoug Moore * To resume the search at the start of the upper region, first climb to 440e0e8d0c8SDoug Moore * the nearest ancestor that spans highaddr. Then find the last entry 441e0e8d0c8SDoug Moore * before highaddr that could abut a big-enough range. 442b831865fSDoug Moore */ 443e0e8d0c8SDoug Moore addr = a->common->highaddr; 444e0e8d0c8SDoug Moore while (curr != NULL && curr->last < addr) 445e0e8d0c8SDoug Moore curr = RB_PARENT(curr, rb_entry); 446e0e8d0c8SDoug Moore first = NULL; 447e0e8d0c8SDoug Moore while (curr != NULL && curr->free_down >= min_free) { 448e0e8d0c8SDoug Moore if (addr < curr->end) 449e0e8d0c8SDoug Moore curr = RB_LEFT(curr, rb_entry); 450e0e8d0c8SDoug Moore else { 451e0e8d0c8SDoug Moore first = curr; 452e0e8d0c8SDoug Moore curr = RB_RIGHT(curr, rb_entry); 4533024e8afSRuslan Bukin } 4543024e8afSRuslan Bukin } 4553024e8afSRuslan Bukin 456e0e8d0c8SDoug Moore /* 457e0e8d0c8SDoug Moore * Walk the remaining big-enough ranges until one satisfies alignment 458e0e8d0c8SDoug Moore * requirements. 459e0e8d0c8SDoug Moore */ 460e0e8d0c8SDoug Moore domain = a->domain; 461e0e8d0c8SDoug Moore for (curr = first; curr != NULL; 462e0e8d0c8SDoug Moore curr = iommu_gas_next(curr, min_free)) { 463e0e8d0c8SDoug Moore if ((first = RB_LEFT(curr, rb_entry)) != NULL && 464e0e8d0c8SDoug Moore iommu_gas_match_one(a, first->last, curr->start, 465e0e8d0c8SDoug Moore addr + 1, domain->end)) 4663024e8afSRuslan Bukin return (0); 467e0e8d0c8SDoug Moore if ((first = RB_RIGHT(curr, rb_entry)) != NULL && 468e0e8d0c8SDoug Moore iommu_gas_match_one(a, curr->end, first->first, 469e0e8d0c8SDoug Moore addr + 1, domain->end)) 470e0e8d0c8SDoug Moore return (0); 4713024e8afSRuslan Bukin } 472e0e8d0c8SDoug Moore 4733024e8afSRuslan Bukin return (ENOMEM); 4743024e8afSRuslan Bukin } 4753024e8afSRuslan Bukin 4763024e8afSRuslan Bukin static int 4773024e8afSRuslan Bukin iommu_gas_alloc_region(struct iommu_domain *domain, struct iommu_map_entry *entry, 4783024e8afSRuslan Bukin u_int flags) 4793024e8afSRuslan Bukin { 4803024e8afSRuslan Bukin struct iommu_map_entry *next, *prev; 481661bd70bSKonstantin Belousov bool found __diagused; 4823024e8afSRuslan Bukin 4833024e8afSRuslan Bukin IOMMU_DOMAIN_ASSERT_LOCKED(domain); 4843024e8afSRuslan Bukin 4853024e8afSRuslan Bukin if ((entry->start & IOMMU_PAGE_MASK) != 0 || 4863024e8afSRuslan Bukin (entry->end & IOMMU_PAGE_MASK) != 0) 4873024e8afSRuslan Bukin return (EINVAL); 4883024e8afSRuslan Bukin if (entry->start >= entry->end) 4893024e8afSRuslan Bukin return (EINVAL); 4903024e8afSRuslan Bukin if (entry->end >= domain->end) 4913024e8afSRuslan Bukin return (EINVAL); 4923024e8afSRuslan Bukin 4933024e8afSRuslan Bukin next = RB_NFIND(iommu_gas_entries_tree, &domain->rb_root, entry); 4943024e8afSRuslan Bukin KASSERT(next != NULL, ("next must be non-null %p %jx", domain, 4953024e8afSRuslan Bukin (uintmax_t)entry->start)); 4963024e8afSRuslan Bukin prev = RB_PREV(iommu_gas_entries_tree, &domain->rb_root, next); 4973024e8afSRuslan Bukin /* prev could be NULL */ 4983024e8afSRuslan Bukin 4993024e8afSRuslan Bukin /* 5003024e8afSRuslan Bukin * Adapt to broken BIOSes which specify overlapping RMRR 5013024e8afSRuslan Bukin * entries. 5023024e8afSRuslan Bukin * 5033024e8afSRuslan Bukin * XXXKIB: this does not handle a case when prev or next 5043024e8afSRuslan Bukin * entries are completely covered by the current one, which 5053024e8afSRuslan Bukin * extends both ways. 5063024e8afSRuslan Bukin */ 5073024e8afSRuslan Bukin if (prev != NULL && prev->end > entry->start && 5083024e8afSRuslan Bukin (prev->flags & IOMMU_MAP_ENTRY_PLACE) == 0) { 5093024e8afSRuslan Bukin if ((flags & IOMMU_MF_RMRR) == 0 || 5103024e8afSRuslan Bukin (prev->flags & IOMMU_MAP_ENTRY_RMRR) == 0) 5113024e8afSRuslan Bukin return (EBUSY); 5123024e8afSRuslan Bukin entry->start = prev->end; 5133024e8afSRuslan Bukin } 5143024e8afSRuslan Bukin if (next->start < entry->end && 5153024e8afSRuslan Bukin (next->flags & IOMMU_MAP_ENTRY_PLACE) == 0) { 5163024e8afSRuslan Bukin if ((flags & IOMMU_MF_RMRR) == 0 || 5173024e8afSRuslan Bukin (next->flags & IOMMU_MAP_ENTRY_RMRR) == 0) 5183024e8afSRuslan Bukin return (EBUSY); 5193024e8afSRuslan Bukin entry->end = next->start; 5203024e8afSRuslan Bukin } 5213024e8afSRuslan Bukin if (entry->end == entry->start) 5223024e8afSRuslan Bukin return (0); 5233024e8afSRuslan Bukin 5243024e8afSRuslan Bukin if (prev != NULL && prev->end > entry->start) { 5253024e8afSRuslan Bukin /* This assumes that prev is the placeholder entry. */ 5263024e8afSRuslan Bukin iommu_gas_rb_remove(domain, prev); 5273024e8afSRuslan Bukin prev = NULL; 5283024e8afSRuslan Bukin } 5293024e8afSRuslan Bukin if (next->start < entry->end) { 5303024e8afSRuslan Bukin iommu_gas_rb_remove(domain, next); 5313024e8afSRuslan Bukin next = NULL; 5323024e8afSRuslan Bukin } 5333024e8afSRuslan Bukin 5343024e8afSRuslan Bukin found = iommu_gas_rb_insert(domain, entry); 5353024e8afSRuslan Bukin KASSERT(found, ("found RMRR dup %p start %jx end %jx", 5363024e8afSRuslan Bukin domain, (uintmax_t)entry->start, (uintmax_t)entry->end)); 5373024e8afSRuslan Bukin if ((flags & IOMMU_MF_RMRR) != 0) 5383024e8afSRuslan Bukin entry->flags = IOMMU_MAP_ENTRY_RMRR; 5393024e8afSRuslan Bukin 5403024e8afSRuslan Bukin #ifdef INVARIANTS 5413024e8afSRuslan Bukin struct iommu_map_entry *ip, *in; 5423024e8afSRuslan Bukin ip = RB_PREV(iommu_gas_entries_tree, &domain->rb_root, entry); 5433024e8afSRuslan Bukin in = RB_NEXT(iommu_gas_entries_tree, &domain->rb_root, entry); 5443024e8afSRuslan Bukin KASSERT(prev == NULL || ip == prev, 5453024e8afSRuslan Bukin ("RMRR %p (%jx %jx) prev %p (%jx %jx) ins prev %p (%jx %jx)", 5463024e8afSRuslan Bukin entry, entry->start, entry->end, prev, 5473024e8afSRuslan Bukin prev == NULL ? 0 : prev->start, prev == NULL ? 0 : prev->end, 5483024e8afSRuslan Bukin ip, ip == NULL ? 0 : ip->start, ip == NULL ? 0 : ip->end)); 5493024e8afSRuslan Bukin KASSERT(next == NULL || in == next, 5503024e8afSRuslan Bukin ("RMRR %p (%jx %jx) next %p (%jx %jx) ins next %p (%jx %jx)", 5513024e8afSRuslan Bukin entry, entry->start, entry->end, next, 5523024e8afSRuslan Bukin next == NULL ? 0 : next->start, next == NULL ? 0 : next->end, 5533024e8afSRuslan Bukin in, in == NULL ? 0 : in->start, in == NULL ? 0 : in->end)); 5543024e8afSRuslan Bukin #endif 5553024e8afSRuslan Bukin 5563024e8afSRuslan Bukin return (0); 5573024e8afSRuslan Bukin } 5583024e8afSRuslan Bukin 5593024e8afSRuslan Bukin void 5604670f908SAlan Cox iommu_gas_free_space(struct iommu_map_entry *entry) 5613024e8afSRuslan Bukin { 5624670f908SAlan Cox struct iommu_domain *domain; 5633024e8afSRuslan Bukin 5644670f908SAlan Cox domain = entry->domain; 5653024e8afSRuslan Bukin KASSERT((entry->flags & (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_RMRR | 5663024e8afSRuslan Bukin IOMMU_MAP_ENTRY_MAP)) == IOMMU_MAP_ENTRY_MAP, 5673024e8afSRuslan Bukin ("permanent entry %p %p", domain, entry)); 5683024e8afSRuslan Bukin 5694670f908SAlan Cox IOMMU_DOMAIN_LOCK(domain); 5703024e8afSRuslan Bukin iommu_gas_rb_remove(domain, entry); 5713024e8afSRuslan Bukin entry->flags &= ~IOMMU_MAP_ENTRY_MAP; 5723024e8afSRuslan Bukin #ifdef INVARIANTS 5733024e8afSRuslan Bukin if (iommu_check_free) 5743024e8afSRuslan Bukin iommu_gas_check_free(domain); 5753024e8afSRuslan Bukin #endif 5764670f908SAlan Cox IOMMU_DOMAIN_UNLOCK(domain); 5773024e8afSRuslan Bukin } 5783024e8afSRuslan Bukin 5793024e8afSRuslan Bukin void 5804670f908SAlan Cox iommu_gas_free_region(struct iommu_map_entry *entry) 5813024e8afSRuslan Bukin { 5824670f908SAlan Cox struct iommu_domain *domain; 5833024e8afSRuslan Bukin struct iommu_map_entry *next, *prev; 5843024e8afSRuslan Bukin 5854670f908SAlan Cox domain = entry->domain; 5863024e8afSRuslan Bukin KASSERT((entry->flags & (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_RMRR | 5873024e8afSRuslan Bukin IOMMU_MAP_ENTRY_MAP)) == IOMMU_MAP_ENTRY_RMRR, 5883024e8afSRuslan Bukin ("non-RMRR entry %p %p", domain, entry)); 5893024e8afSRuslan Bukin 5904670f908SAlan Cox IOMMU_DOMAIN_LOCK(domain); 5913024e8afSRuslan Bukin prev = RB_PREV(iommu_gas_entries_tree, &domain->rb_root, entry); 5923024e8afSRuslan Bukin next = RB_NEXT(iommu_gas_entries_tree, &domain->rb_root, entry); 5933024e8afSRuslan Bukin iommu_gas_rb_remove(domain, entry); 5943024e8afSRuslan Bukin entry->flags &= ~IOMMU_MAP_ENTRY_RMRR; 5953024e8afSRuslan Bukin 5963024e8afSRuslan Bukin if (prev == NULL) 5973024e8afSRuslan Bukin iommu_gas_rb_insert(domain, domain->first_place); 5983024e8afSRuslan Bukin if (next == NULL) 5993024e8afSRuslan Bukin iommu_gas_rb_insert(domain, domain->last_place); 6004670f908SAlan Cox IOMMU_DOMAIN_UNLOCK(domain); 6013024e8afSRuslan Bukin } 6023024e8afSRuslan Bukin 603c9e4d250SKonstantin Belousov static struct iommu_map_entry * 604c9e4d250SKonstantin Belousov iommu_gas_remove_clip_left(struct iommu_domain *domain, iommu_gaddr_t start, 605c9e4d250SKonstantin Belousov iommu_gaddr_t end, struct iommu_map_entry **r) 606c9e4d250SKonstantin Belousov { 607c9e4d250SKonstantin Belousov struct iommu_map_entry *entry, *res, fentry; 608c9e4d250SKonstantin Belousov 609c9e4d250SKonstantin Belousov IOMMU_DOMAIN_ASSERT_LOCKED(domain); 610c9e4d250SKonstantin Belousov MPASS(start <= end); 611c9e4d250SKonstantin Belousov MPASS(end <= domain->last_place->end); 612c9e4d250SKonstantin Belousov 613c9e4d250SKonstantin Belousov /* 614c9e4d250SKonstantin Belousov * Find an entry which contains the supplied guest's address 615c9e4d250SKonstantin Belousov * start, or the first entry after the start. Since we 616c9e4d250SKonstantin Belousov * asserted that start is below domain end, entry should 617c9e4d250SKonstantin Belousov * exist. Then clip it if needed. 618c9e4d250SKonstantin Belousov */ 619c9e4d250SKonstantin Belousov fentry.start = start + 1; 620c9e4d250SKonstantin Belousov fentry.end = start + 1; 621c9e4d250SKonstantin Belousov entry = RB_NFIND(iommu_gas_entries_tree, &domain->rb_root, &fentry); 622c9e4d250SKonstantin Belousov 623c9e4d250SKonstantin Belousov if (entry->start >= start || 624c9e4d250SKonstantin Belousov (entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0) 625c9e4d250SKonstantin Belousov return (entry); 626c9e4d250SKonstantin Belousov 627c9e4d250SKonstantin Belousov res = *r; 628c9e4d250SKonstantin Belousov *r = NULL; 629c9e4d250SKonstantin Belousov *res = *entry; 630c9e4d250SKonstantin Belousov res->start = entry->end = start; 631c9e4d250SKonstantin Belousov RB_UPDATE_AUGMENT(entry, rb_entry); 632c9e4d250SKonstantin Belousov iommu_gas_rb_insert(domain, res); 633c9e4d250SKonstantin Belousov return (res); 634c9e4d250SKonstantin Belousov } 635c9e4d250SKonstantin Belousov 636c9e4d250SKonstantin Belousov static bool 637c9e4d250SKonstantin Belousov iommu_gas_remove_clip_right(struct iommu_domain *domain, 638c9e4d250SKonstantin Belousov iommu_gaddr_t end, struct iommu_map_entry *entry, 639c9e4d250SKonstantin Belousov struct iommu_map_entry *r) 640c9e4d250SKonstantin Belousov { 641c9e4d250SKonstantin Belousov if (entry->start >= end || (entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0) 642c9e4d250SKonstantin Belousov return (false); 643c9e4d250SKonstantin Belousov 644c9e4d250SKonstantin Belousov *r = *entry; 645c9e4d250SKonstantin Belousov r->end = entry->start = end; 646c9e4d250SKonstantin Belousov RB_UPDATE_AUGMENT(entry, rb_entry); 647c9e4d250SKonstantin Belousov iommu_gas_rb_insert(domain, r); 648c9e4d250SKonstantin Belousov return (true); 649c9e4d250SKonstantin Belousov } 650c9e4d250SKonstantin Belousov 651c9e4d250SKonstantin Belousov static void 652c9e4d250SKonstantin Belousov iommu_gas_remove_unmap(struct iommu_domain *domain, 653c9e4d250SKonstantin Belousov struct iommu_map_entry *entry, struct iommu_map_entries_tailq *gcp) 654c9e4d250SKonstantin Belousov { 655c9e4d250SKonstantin Belousov IOMMU_DOMAIN_ASSERT_LOCKED(domain); 656c9e4d250SKonstantin Belousov 657c9e4d250SKonstantin Belousov if ((entry->flags & (IOMMU_MAP_ENTRY_UNMAPPED | 658c9e4d250SKonstantin Belousov IOMMU_MAP_ENTRY_REMOVING)) != 0) 659c9e4d250SKonstantin Belousov return; 660c9e4d250SKonstantin Belousov MPASS((entry->flags & IOMMU_MAP_ENTRY_PLACE) == 0); 661c9e4d250SKonstantin Belousov entry->flags |= IOMMU_MAP_ENTRY_REMOVING; 662c9e4d250SKonstantin Belousov TAILQ_INSERT_TAIL(gcp, entry, dmamap_link); 663c9e4d250SKonstantin Belousov } 664c9e4d250SKonstantin Belousov 665c9e4d250SKonstantin Belousov /* 666c9e4d250SKonstantin Belousov * Remove specified range from the GAS of the domain. Note that the 667c9e4d250SKonstantin Belousov * removal is not guaranteed to occur upon the function return, it 668c9e4d250SKonstantin Belousov * might be finalized some time after, when hardware reports that 669c9e4d250SKonstantin Belousov * (queued) IOTLB invalidation was performed. 670c9e4d250SKonstantin Belousov */ 671c9e4d250SKonstantin Belousov void 672c9e4d250SKonstantin Belousov iommu_gas_remove(struct iommu_domain *domain, iommu_gaddr_t start, 673c9e4d250SKonstantin Belousov iommu_gaddr_t size) 674c9e4d250SKonstantin Belousov { 675c9e4d250SKonstantin Belousov struct iommu_map_entry *entry, *nentry, *r1, *r2; 676c9e4d250SKonstantin Belousov struct iommu_map_entries_tailq gc; 677c9e4d250SKonstantin Belousov iommu_gaddr_t end; 678c9e4d250SKonstantin Belousov 679c9e4d250SKonstantin Belousov end = start + size; 680c9e4d250SKonstantin Belousov r1 = iommu_gas_alloc_entry(domain, IOMMU_PGF_WAITOK); 681c9e4d250SKonstantin Belousov r2 = iommu_gas_alloc_entry(domain, IOMMU_PGF_WAITOK); 682c9e4d250SKonstantin Belousov TAILQ_INIT(&gc); 683c9e4d250SKonstantin Belousov 684c9e4d250SKonstantin Belousov IOMMU_DOMAIN_LOCK(domain); 685c9e4d250SKonstantin Belousov 686c9e4d250SKonstantin Belousov nentry = iommu_gas_remove_clip_left(domain, start, end, &r1); 687c9e4d250SKonstantin Belousov RB_FOREACH_FROM(entry, iommu_gas_entries_tree, nentry) { 688c9e4d250SKonstantin Belousov if (entry->start >= end) 689c9e4d250SKonstantin Belousov break; 690c9e4d250SKonstantin Belousov KASSERT(start <= entry->start, 691c9e4d250SKonstantin Belousov ("iommu_gas_remove entry (%#jx, %#jx) start %#jx", 692c9e4d250SKonstantin Belousov entry->start, entry->end, start)); 693c9e4d250SKonstantin Belousov if ((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0) 694c9e4d250SKonstantin Belousov continue; 695c9e4d250SKonstantin Belousov iommu_gas_remove_unmap(domain, entry, &gc); 696c9e4d250SKonstantin Belousov } 697c9e4d250SKonstantin Belousov if (iommu_gas_remove_clip_right(domain, end, entry, r2)) { 698c9e4d250SKonstantin Belousov iommu_gas_remove_unmap(domain, r2, &gc); 699c9e4d250SKonstantin Belousov r2 = NULL; 700c9e4d250SKonstantin Belousov } 701c9e4d250SKonstantin Belousov 702c9e4d250SKonstantin Belousov #ifdef INVARIANTS 703c9e4d250SKonstantin Belousov RB_FOREACH(entry, iommu_gas_entries_tree, &domain->rb_root) { 704c9e4d250SKonstantin Belousov if ((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0) 705c9e4d250SKonstantin Belousov continue; 706c9e4d250SKonstantin Belousov KASSERT(entry->end <= start || entry->start >= end, 707c9e4d250SKonstantin Belousov ("iommu_gas_remove leftover entry (%#jx, %#jx) range " 708c9e4d250SKonstantin Belousov "(%#jx, %#jx)", 709c9e4d250SKonstantin Belousov entry->start, entry->end, start, end)); 710c9e4d250SKonstantin Belousov } 711c9e4d250SKonstantin Belousov #endif 712c9e4d250SKonstantin Belousov 713c9e4d250SKonstantin Belousov IOMMU_DOMAIN_UNLOCK(domain); 714c9e4d250SKonstantin Belousov if (r1 != NULL) 715c9e4d250SKonstantin Belousov iommu_gas_free_entry(r1); 716c9e4d250SKonstantin Belousov if (r2 != NULL) 717c9e4d250SKonstantin Belousov iommu_gas_free_entry(r2); 718c9e4d250SKonstantin Belousov iommu_domain_unload(domain, &gc, true); 719c9e4d250SKonstantin Belousov } 720c9e4d250SKonstantin Belousov 7213024e8afSRuslan Bukin int 7223024e8afSRuslan Bukin iommu_gas_map(struct iommu_domain *domain, 7233024e8afSRuslan Bukin const struct bus_dma_tag_common *common, iommu_gaddr_t size, int offset, 7243024e8afSRuslan Bukin u_int eflags, u_int flags, vm_page_t *ma, struct iommu_map_entry **res) 7253024e8afSRuslan Bukin { 726e0e8d0c8SDoug Moore struct iommu_gas_match_args a; 7273024e8afSRuslan Bukin struct iommu_map_entry *entry; 7283024e8afSRuslan Bukin int error; 7293024e8afSRuslan Bukin 7303024e8afSRuslan Bukin KASSERT((flags & ~(IOMMU_MF_CANWAIT | IOMMU_MF_CANSPLIT)) == 0, 7313024e8afSRuslan Bukin ("invalid flags 0x%x", flags)); 7323024e8afSRuslan Bukin 733e0e8d0c8SDoug Moore a.domain = domain; 734e0e8d0c8SDoug Moore a.size = size; 735e0e8d0c8SDoug Moore a.offset = offset; 736e0e8d0c8SDoug Moore a.common = common; 737e0e8d0c8SDoug Moore a.gas_flags = flags; 7383024e8afSRuslan Bukin entry = iommu_gas_alloc_entry(domain, 73915f6baf4SRuslan Bukin (flags & IOMMU_MF_CANWAIT) != 0 ? IOMMU_PGF_WAITOK : 0); 7403024e8afSRuslan Bukin if (entry == NULL) 7413024e8afSRuslan Bukin return (ENOMEM); 742e0e8d0c8SDoug Moore a.entry = entry; 7433024e8afSRuslan Bukin IOMMU_DOMAIN_LOCK(domain); 744e0e8d0c8SDoug Moore error = iommu_gas_find_space(&a); 7453024e8afSRuslan Bukin if (error == ENOMEM) { 7463024e8afSRuslan Bukin IOMMU_DOMAIN_UNLOCK(domain); 7474670f908SAlan Cox iommu_gas_free_entry(entry); 7483024e8afSRuslan Bukin return (error); 7493024e8afSRuslan Bukin } 7503024e8afSRuslan Bukin #ifdef INVARIANTS 7513024e8afSRuslan Bukin if (iommu_check_free) 7523024e8afSRuslan Bukin iommu_gas_check_free(domain); 7533024e8afSRuslan Bukin #endif 7543024e8afSRuslan Bukin KASSERT(error == 0, 7553024e8afSRuslan Bukin ("unexpected error %d from iommu_gas_find_entry", error)); 7563024e8afSRuslan Bukin KASSERT(entry->end < domain->end, ("allocated GPA %jx, max GPA %jx", 7573024e8afSRuslan Bukin (uintmax_t)entry->end, (uintmax_t)domain->end)); 7583024e8afSRuslan Bukin entry->flags |= eflags; 7593024e8afSRuslan Bukin IOMMU_DOMAIN_UNLOCK(domain); 7603024e8afSRuslan Bukin 7610eed04c8SRuslan Bukin error = domain->ops->map(domain, entry->start, 7620eed04c8SRuslan Bukin entry->end - entry->start, ma, eflags, 76315f6baf4SRuslan Bukin ((flags & IOMMU_MF_CANWAIT) != 0 ? IOMMU_PGF_WAITOK : 0)); 7643024e8afSRuslan Bukin if (error == ENOMEM) { 7658bc36738SAlan Cox iommu_domain_unload_entry(entry, true, 7668bc36738SAlan Cox (flags & IOMMU_MF_CANWAIT) != 0); 7673024e8afSRuslan Bukin return (error); 7683024e8afSRuslan Bukin } 7693024e8afSRuslan Bukin KASSERT(error == 0, 7703024e8afSRuslan Bukin ("unexpected error %d from domain_map_buf", error)); 7713024e8afSRuslan Bukin 7723024e8afSRuslan Bukin *res = entry; 7733024e8afSRuslan Bukin return (0); 7743024e8afSRuslan Bukin } 7753024e8afSRuslan Bukin 7763024e8afSRuslan Bukin int 7773024e8afSRuslan Bukin iommu_gas_map_region(struct iommu_domain *domain, struct iommu_map_entry *entry, 7783024e8afSRuslan Bukin u_int eflags, u_int flags, vm_page_t *ma) 7793024e8afSRuslan Bukin { 7803024e8afSRuslan Bukin iommu_gaddr_t start; 7813024e8afSRuslan Bukin int error; 7823024e8afSRuslan Bukin 7834670f908SAlan Cox KASSERT(entry->domain == domain, 7844670f908SAlan Cox ("mismatched domain %p entry %p entry->domain %p", domain, 7854670f908SAlan Cox entry, entry->domain)); 7863024e8afSRuslan Bukin KASSERT(entry->flags == 0, ("used RMRR entry %p %p %x", domain, 7873024e8afSRuslan Bukin entry, entry->flags)); 7883024e8afSRuslan Bukin KASSERT((flags & ~(IOMMU_MF_CANWAIT | IOMMU_MF_RMRR)) == 0, 7893024e8afSRuslan Bukin ("invalid flags 0x%x", flags)); 7903024e8afSRuslan Bukin 7913024e8afSRuslan Bukin start = entry->start; 7923024e8afSRuslan Bukin IOMMU_DOMAIN_LOCK(domain); 7933024e8afSRuslan Bukin error = iommu_gas_alloc_region(domain, entry, flags); 7943024e8afSRuslan Bukin if (error != 0) { 7953024e8afSRuslan Bukin IOMMU_DOMAIN_UNLOCK(domain); 7963024e8afSRuslan Bukin return (error); 7973024e8afSRuslan Bukin } 7983024e8afSRuslan Bukin entry->flags |= eflags; 7993024e8afSRuslan Bukin IOMMU_DOMAIN_UNLOCK(domain); 8003024e8afSRuslan Bukin if (entry->end == entry->start) 8013024e8afSRuslan Bukin return (0); 8023024e8afSRuslan Bukin 8030eed04c8SRuslan Bukin error = domain->ops->map(domain, entry->start, 8040eed04c8SRuslan Bukin entry->end - entry->start, ma + OFF_TO_IDX(start - entry->start), 8050eed04c8SRuslan Bukin eflags, ((flags & IOMMU_MF_CANWAIT) != 0 ? IOMMU_PGF_WAITOK : 0)); 8063024e8afSRuslan Bukin if (error == ENOMEM) { 8078bc36738SAlan Cox iommu_domain_unload_entry(entry, false, 8088bc36738SAlan Cox (flags & IOMMU_MF_CANWAIT) != 0); 8093024e8afSRuslan Bukin return (error); 8103024e8afSRuslan Bukin } 8113024e8afSRuslan Bukin KASSERT(error == 0, 8123024e8afSRuslan Bukin ("unexpected error %d from domain_map_buf", error)); 8133024e8afSRuslan Bukin 8143024e8afSRuslan Bukin return (0); 8153024e8afSRuslan Bukin } 8163024e8afSRuslan Bukin 817ee47a12aSRyan Libby static int 818ee47a12aSRyan Libby iommu_gas_reserve_region_locked(struct iommu_domain *domain, 819ee47a12aSRyan Libby iommu_gaddr_t start, iommu_gaddr_t end, struct iommu_map_entry *entry) 820ee47a12aSRyan Libby { 821ee47a12aSRyan Libby int error; 822ee47a12aSRyan Libby 823ee47a12aSRyan Libby IOMMU_DOMAIN_ASSERT_LOCKED(domain); 824ee47a12aSRyan Libby 825ee47a12aSRyan Libby entry->start = start; 826ee47a12aSRyan Libby entry->end = end; 827ee47a12aSRyan Libby error = iommu_gas_alloc_region(domain, entry, IOMMU_MF_CANWAIT); 828ee47a12aSRyan Libby if (error == 0) 829ee47a12aSRyan Libby entry->flags |= IOMMU_MAP_ENTRY_UNMAPPED; 830ee47a12aSRyan Libby return (error); 831ee47a12aSRyan Libby } 832ee47a12aSRyan Libby 8333024e8afSRuslan Bukin int 8343024e8afSRuslan Bukin iommu_gas_reserve_region(struct iommu_domain *domain, iommu_gaddr_t start, 83594dfb28eSRuslan Bukin iommu_gaddr_t end, struct iommu_map_entry **entry0) 8363024e8afSRuslan Bukin { 8373024e8afSRuslan Bukin struct iommu_map_entry *entry; 8383024e8afSRuslan Bukin int error; 8393024e8afSRuslan Bukin 84015f6baf4SRuslan Bukin entry = iommu_gas_alloc_entry(domain, IOMMU_PGF_WAITOK); 8413024e8afSRuslan Bukin IOMMU_DOMAIN_LOCK(domain); 842ee47a12aSRyan Libby error = iommu_gas_reserve_region_locked(domain, start, end, entry); 8433024e8afSRuslan Bukin IOMMU_DOMAIN_UNLOCK(domain); 8443024e8afSRuslan Bukin if (error != 0) 8454670f908SAlan Cox iommu_gas_free_entry(entry); 84694dfb28eSRuslan Bukin else if (entry0 != NULL) 84794dfb28eSRuslan Bukin *entry0 = entry; 8483024e8afSRuslan Bukin return (error); 8493024e8afSRuslan Bukin } 8503024e8afSRuslan Bukin 851ee47a12aSRyan Libby /* 852ee47a12aSRyan Libby * As in iommu_gas_reserve_region, reserve [start, end), but allow for existing 853ee47a12aSRyan Libby * entries. 854ee47a12aSRyan Libby */ 855ee47a12aSRyan Libby int 856ee47a12aSRyan Libby iommu_gas_reserve_region_extend(struct iommu_domain *domain, 857ee47a12aSRyan Libby iommu_gaddr_t start, iommu_gaddr_t end) 858ee47a12aSRyan Libby { 859ee47a12aSRyan Libby struct iommu_map_entry *entry, *next, *prev, key = {}; 860ee47a12aSRyan Libby iommu_gaddr_t entry_start, entry_end; 861ee47a12aSRyan Libby int error; 862ee47a12aSRyan Libby 863ee47a12aSRyan Libby error = 0; 864ee47a12aSRyan Libby entry = NULL; 865ee47a12aSRyan Libby end = ummin(end, domain->end); 866ee47a12aSRyan Libby while (start < end) { 867ee47a12aSRyan Libby /* Preallocate an entry. */ 868ee47a12aSRyan Libby if (entry == NULL) 869ee47a12aSRyan Libby entry = iommu_gas_alloc_entry(domain, 870ee47a12aSRyan Libby IOMMU_PGF_WAITOK); 871ee47a12aSRyan Libby /* Calculate the free region from here to the next entry. */ 872ee47a12aSRyan Libby key.start = key.end = start; 873ee47a12aSRyan Libby IOMMU_DOMAIN_LOCK(domain); 874ee47a12aSRyan Libby next = RB_NFIND(iommu_gas_entries_tree, &domain->rb_root, &key); 875ee47a12aSRyan Libby KASSERT(next != NULL, ("domain %p with end %#jx has no entry " 876ee47a12aSRyan Libby "after %#jx", domain, (uintmax_t)domain->end, 877ee47a12aSRyan Libby (uintmax_t)start)); 878ee47a12aSRyan Libby entry_end = ummin(end, next->start); 879ee47a12aSRyan Libby prev = RB_PREV(iommu_gas_entries_tree, &domain->rb_root, next); 880ee47a12aSRyan Libby if (prev != NULL) 881ee47a12aSRyan Libby entry_start = ummax(start, prev->end); 882ee47a12aSRyan Libby else 883ee47a12aSRyan Libby entry_start = start; 884ee47a12aSRyan Libby start = next->end; 885ee47a12aSRyan Libby /* Reserve the region if non-empty. */ 886ee47a12aSRyan Libby if (entry_start != entry_end) { 887ee47a12aSRyan Libby error = iommu_gas_reserve_region_locked(domain, 888ee47a12aSRyan Libby entry_start, entry_end, entry); 8890ba1d860SAlan Cox if (error != 0) { 8900ba1d860SAlan Cox IOMMU_DOMAIN_UNLOCK(domain); 891ee47a12aSRyan Libby break; 8920ba1d860SAlan Cox } 893ee47a12aSRyan Libby entry = NULL; 894ee47a12aSRyan Libby } 895ee47a12aSRyan Libby IOMMU_DOMAIN_UNLOCK(domain); 896ee47a12aSRyan Libby } 897ee47a12aSRyan Libby /* Release a preallocated entry if it was not used. */ 898ee47a12aSRyan Libby if (entry != NULL) 8994670f908SAlan Cox iommu_gas_free_entry(entry); 900ee47a12aSRyan Libby return (error); 901ee47a12aSRyan Libby } 902ee47a12aSRyan Libby 903f32f0095SRuslan Bukin void 904f32f0095SRuslan Bukin iommu_unmap_msi(struct iommu_ctx *ctx) 905f32f0095SRuslan Bukin { 906f32f0095SRuslan Bukin struct iommu_map_entry *entry; 907f32f0095SRuslan Bukin struct iommu_domain *domain; 908f32f0095SRuslan Bukin 909f32f0095SRuslan Bukin domain = ctx->domain; 910f32f0095SRuslan Bukin entry = domain->msi_entry; 911f32f0095SRuslan Bukin if (entry == NULL) 912f32f0095SRuslan Bukin return; 913f32f0095SRuslan Bukin 914f32f0095SRuslan Bukin domain->ops->unmap(domain, entry->start, entry->end - 915f32f0095SRuslan Bukin entry->start, IOMMU_PGF_WAITOK); 916f32f0095SRuslan Bukin 9174670f908SAlan Cox iommu_gas_free_space(entry); 918f32f0095SRuslan Bukin 9194670f908SAlan Cox iommu_gas_free_entry(entry); 920f32f0095SRuslan Bukin 921f32f0095SRuslan Bukin domain->msi_entry = NULL; 922f32f0095SRuslan Bukin domain->msi_base = 0; 923f32f0095SRuslan Bukin domain->msi_phys = 0; 924f32f0095SRuslan Bukin } 925f32f0095SRuslan Bukin 9263024e8afSRuslan Bukin int 927e707c8beSRuslan Bukin iommu_map_msi(struct iommu_ctx *ctx, iommu_gaddr_t size, int offset, 928e707c8beSRuslan Bukin u_int eflags, u_int flags, vm_page_t *ma) 929e707c8beSRuslan Bukin { 930e707c8beSRuslan Bukin struct iommu_domain *domain; 931e707c8beSRuslan Bukin struct iommu_map_entry *entry; 932e707c8beSRuslan Bukin int error; 933e707c8beSRuslan Bukin 934e707c8beSRuslan Bukin error = 0; 935e707c8beSRuslan Bukin domain = ctx->domain; 936e707c8beSRuslan Bukin 937e707c8beSRuslan Bukin /* Check if there is already an MSI page allocated */ 938e707c8beSRuslan Bukin IOMMU_DOMAIN_LOCK(domain); 939e707c8beSRuslan Bukin entry = domain->msi_entry; 940e707c8beSRuslan Bukin IOMMU_DOMAIN_UNLOCK(domain); 941e707c8beSRuslan Bukin 942e707c8beSRuslan Bukin if (entry == NULL) { 943e707c8beSRuslan Bukin error = iommu_gas_map(domain, &ctx->tag->common, size, offset, 944e707c8beSRuslan Bukin eflags, flags, ma, &entry); 945e707c8beSRuslan Bukin IOMMU_DOMAIN_LOCK(domain); 946e707c8beSRuslan Bukin if (error == 0) { 947e707c8beSRuslan Bukin if (domain->msi_entry == NULL) { 948e707c8beSRuslan Bukin MPASS(domain->msi_base == 0); 949e707c8beSRuslan Bukin MPASS(domain->msi_phys == 0); 950e707c8beSRuslan Bukin 951e707c8beSRuslan Bukin domain->msi_entry = entry; 952e707c8beSRuslan Bukin domain->msi_base = entry->start; 953e707c8beSRuslan Bukin domain->msi_phys = VM_PAGE_TO_PHYS(ma[0]); 954e707c8beSRuslan Bukin } else { 955e707c8beSRuslan Bukin /* 956e707c8beSRuslan Bukin * We lost the race and already have an 957e707c8beSRuslan Bukin * MSI page allocated. Free the unneeded entry. 958e707c8beSRuslan Bukin */ 9594670f908SAlan Cox iommu_gas_free_entry(entry); 960e707c8beSRuslan Bukin } 961e707c8beSRuslan Bukin } else if (domain->msi_entry != NULL) { 962e707c8beSRuslan Bukin /* 963e707c8beSRuslan Bukin * The allocation failed, but another succeeded. 964e707c8beSRuslan Bukin * Return success as there is a valid MSI page. 965e707c8beSRuslan Bukin */ 966e707c8beSRuslan Bukin error = 0; 967e707c8beSRuslan Bukin } 968e707c8beSRuslan Bukin IOMMU_DOMAIN_UNLOCK(domain); 969e707c8beSRuslan Bukin } 970e707c8beSRuslan Bukin 971e707c8beSRuslan Bukin return (error); 972e707c8beSRuslan Bukin } 973e707c8beSRuslan Bukin 974e707c8beSRuslan Bukin void 975e707c8beSRuslan Bukin iommu_translate_msi(struct iommu_domain *domain, uint64_t *addr) 976e707c8beSRuslan Bukin { 977e707c8beSRuslan Bukin 978e707c8beSRuslan Bukin *addr = (*addr - domain->msi_phys) + domain->msi_base; 979e707c8beSRuslan Bukin 980e707c8beSRuslan Bukin KASSERT(*addr >= domain->msi_entry->start, 981e707c8beSRuslan Bukin ("%s: Address is below the MSI entry start address (%jx < %jx)", 982e707c8beSRuslan Bukin __func__, (uintmax_t)*addr, (uintmax_t)domain->msi_entry->start)); 983e707c8beSRuslan Bukin 984e707c8beSRuslan Bukin KASSERT(*addr + sizeof(*addr) <= domain->msi_entry->end, 985e707c8beSRuslan Bukin ("%s: Address is above the MSI entry end address (%jx < %jx)", 986e707c8beSRuslan Bukin __func__, (uintmax_t)*addr, (uintmax_t)domain->msi_entry->end)); 987e707c8beSRuslan Bukin } 988e707c8beSRuslan Bukin 989357149f0SRuslan Bukin SYSCTL_NODE(_hw, OID_AUTO, iommu, CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, ""); 990357149f0SRuslan Bukin 9919c843a40SRuslan Bukin #ifdef INVARIANTS 9929c843a40SRuslan Bukin SYSCTL_INT(_hw_iommu, OID_AUTO, check_free, CTLFLAG_RWTUN, 9939c843a40SRuslan Bukin &iommu_check_free, 0, 9949c843a40SRuslan Bukin "Check the GPA RBtree for free_down and free_after validity"); 9959c843a40SRuslan Bukin #endif 996