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