Lines Matching +full:use +full:- +full:guard +full:- +full:pages
1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
9 * Redistribution and use in source and binary forms, with or without
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
100 SLIST_INIT(&res->pgtbl_free);
102 res->domain = domain;
103 atomic_add_int(&domain->entries_cnt, 1);
115 n = vm_page_free_pages_toq(&entry->pgtbl_free, false);
119 domain = entry->domain;
121 atomic_subtract_int(&domain->entries_cnt, 1);
130 KASSERT(a->start <= a->end, ("inverted entry %p (%jx, %jx)",
131 a, (uintmax_t)a->start, (uintmax_t)a->end));
132 KASSERT(b->start <= b->end, ("inverted entry %p (%jx, %jx)",
133 b, (uintmax_t)b->start, (uintmax_t)b->end));
134 KASSERT(((a->flags | b->flags) & IOMMU_MAP_ENTRY_FAKE) != 0 ||
135 a->end <= b->start || b->end <= a->start ||
136 a->end == a->start || b->end == b->start,
139 a, (uintmax_t)a->start, (uintmax_t)a->end, a->flags,
140 b, (uintmax_t)b->start, (uintmax_t)b->end, b->flags,
141 a->domain, b->domain));
143 if (a->end < b->end)
144 return (-1);
145 else if (b->end < a->end)
161 bound = entry->start;
163 free_down = MAX(child->free_down, bound - child->last);
164 bound = child->first;
166 delta = bound - entry->first;
167 entry->first = bound;
168 bound = entry->end;
170 free_down = MAX(free_down, child->free_down);
171 free_down = MAX(free_down, child->first - bound);
172 bound = child->last;
174 delta += entry->last - bound;
176 delta = entry->free_down - free_down;
177 entry->last = bound;
178 entry->free_down = free_down;
181 * Return true either if the value of last-first changed,
197 RB_FOREACH(entry, iommu_gas_entries_tree, &domain->rb_root) {
198 KASSERT(domain == entry->domain,
199 ("mismatched free domain %p entry %p entry->domain %p",
200 domain, entry, entry->domain));
205 v = MAX(v, l->free_down);
206 v = MAX(v, entry->start - l->last);
209 v = MAX(v, r->free_down);
210 v = MAX(v, r->first - entry->end);
212 MPASS(entry->free_down == v);
222 /* Removing entry may open a new free gap before domain->start_gap. */
223 if (entry->end <= domain->start_gap->end) {
230 domain->start_gap = nbr;
232 RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry);
239 return (ctx->domain);
251 KASSERT(domain->entries_cnt == 2, ("dirty domain %p", domain));
252 KASSERT(RB_EMPTY(&domain->rb_root),
253 ("non-empty entries %p", domain));
255 end->start = domain->end;
256 end->end = domain->end;
257 end->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
258 RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, end);
260 begin->start = 0;
261 begin->end = 0;
262 begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
263 RB_INSERT_PREV(iommu_gas_entries_tree, &domain->rb_root, end, begin);
267 domain->start_gap = begin;
268 domain->first_place = begin;
269 domain->last_place = end;
270 domain->flags |= IOMMU_DOMAIN_GAS_INITED;
280 KASSERT(domain->entries_cnt == 2,
281 ("domain still in use %p", domain));
283 entry = RB_MIN(iommu_gas_entries_tree, &domain->rb_root);
284 KASSERT(entry->start == 0, ("start entry start %p", domain));
285 KASSERT(entry->end == IOMMU_PAGE_SIZE, ("start entry end %p", domain));
286 KASSERT(entry->flags ==
292 entry = RB_MAX(iommu_gas_entries_tree, &domain->rb_root);
293 KASSERT(entry->start == domain->end, ("end entry start %p", domain));
294 KASSERT(entry->end == domain->end, ("end entry end %p", domain));
295 KASSERT(entry->flags ==
325 * The prev->end is always aligned on the page size, which
326 * causes page alignment for the entry->start too.
329 * to ensure that out-of-bounds accesses fault.
332 start = roundup2(beg, a->common->alignment);
337 end = MIN(end - IOMMU_PAGE_SIZE - 1, ubound);
338 offset = a->offset;
339 size = a->size;
340 if (start + offset + size - 1 > end)
344 if (!vm_addr_bound_ok(start + offset, size, a->common->boundary)) {
351 beg = roundup2(start + offset + 1, a->common->boundary);
352 start = roundup2(beg, a->common->alignment);
354 if (start + offset + size - 1 > end ||
356 a->common->boundary)) {
367 if ((a->gas_flags & IOMMU_MF_CANSPLIT) == 0)
369 size = beg - first - offset;
373 entry = a->entry;
374 entry->start = start;
375 entry->end = start + roundup2(size + offset, IOMMU_PAGE_SIZE);
376 entry->flags = IOMMU_MAP_ENTRY_MAP;
380 /* Find the next entry that might abut a big-enough range. */
387 next->free_down >= min_free) {
392 next->free_down >= min_free);
394 /* Find next entry in a left-parent ancestor. */
404 * Address-ordered first-fit search of 'domain' for free space satisfying the
406 * bounded by guard pages to the left and right. The allocated space for
407 * 'domain' is described by an rb-tree of map entries at domain->rb_root, and
408 * domain->start_gap points to a map entry less than or adjacent to the first
409 * free-space of size at least 3 pages.
419 KASSERT(a->entry->flags == 0,
420 ("dirty entry %p %p", domain, a->entry));
425 * space big enough for a minimum allocation plus two guard pages.
428 first = domain->start_gap;
429 while (first != NULL && first->free_down < min_free)
434 first->last + min_free <= curr->start)
437 curr->end + min_free <= first->first)
440 domain->start_gap = curr;
444 * plus two guard pages, skip it.
447 roundup2(a->size + a->offset, IOMMU_PAGE_SIZE);
449 /* Climb to find a node in the subtree of big-enough ranges. */
451 while (first != NULL && first->free_down < min_free)
455 * Walk the big-enough ranges tree until one satisfies alignment
458 addr = a->common->lowaddr;
462 iommu_gas_match_one(a, first->last, curr->start,
465 &domain->rb_root, curr, a->entry);
468 if (curr->end >= addr) {
473 iommu_gas_match_one(a, curr->end, first->first,
476 &domain->rb_root, curr, a->entry);
484 * before highaddr that could abut a big-enough range.
486 addr = a->common->highaddr;
487 while (curr != NULL && curr->last < addr)
490 while (curr != NULL && curr->free_down >= min_free) {
491 if (addr < curr->end)
500 * Walk the remaining big-enough ranges until one satisfies alignment
506 iommu_gas_match_one(a, first->last, curr->start,
507 addr + 1, domain->end - 1)) {
509 &domain->rb_root, curr, a->entry);
513 iommu_gas_match_one(a, curr->end, first->first,
514 addr + 1, domain->end - 1)) {
516 &domain->rb_root, curr, a->entry);
532 if ((entry->start & IOMMU_PAGE_MASK) != 0 ||
533 (entry->end & IOMMU_PAGE_MASK) != 0)
535 if (entry->start >= entry->end)
537 if (entry->end >= domain->end)
540 entry->flags |= IOMMU_MAP_ENTRY_FAKE;
541 next = RB_NFIND(iommu_gas_entries_tree, &domain->rb_root, entry);
542 KASSERT(next != NULL, ("next must be non-null %p %jx", domain,
543 (uintmax_t)entry->start));
544 prev = RB_PREV(iommu_gas_entries_tree, &domain->rb_root, next);
546 entry->flags &= ~IOMMU_MAP_ENTRY_FAKE;
556 if (prev != NULL && prev->end > entry->start &&
557 (prev->flags & IOMMU_MAP_ENTRY_PLACE) == 0) {
559 (prev->flags & IOMMU_MAP_ENTRY_RMRR) == 0)
561 entry->start = prev->end;
563 if (next->start < entry->end &&
564 (next->flags & IOMMU_MAP_ENTRY_PLACE) == 0) {
566 (next->flags & IOMMU_MAP_ENTRY_RMRR) == 0)
568 entry->end = next->start;
570 if (entry->end == entry->start)
573 if (prev != NULL && prev->end > entry->start) {
579 &domain->rb_root, next, entry);
580 if (next->start < entry->end) {
586 entry->flags = IOMMU_MAP_ENTRY_RMRR;
590 ip = RB_PREV(iommu_gas_entries_tree, &domain->rb_root, entry);
591 in = RB_NEXT(iommu_gas_entries_tree, &domain->rb_root, entry);
594 entry, entry->start, entry->end, prev,
595 prev == NULL ? 0 : prev->start, prev == NULL ? 0 : prev->end,
596 ip, ip == NULL ? 0 : ip->start, ip == NULL ? 0 : ip->end));
599 entry, entry->start, entry->end, next,
600 next == NULL ? 0 : next->start, next == NULL ? 0 : next->end,
601 in, in == NULL ? 0 : in->start, in == NULL ? 0 : in->end));
612 domain = entry->domain;
613 KASSERT((entry->flags & (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_RMRR |
619 entry->flags &= ~IOMMU_MAP_ENTRY_MAP;
632 domain = entry->domain;
633 KASSERT((entry->flags & (IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_RMRR |
635 ("non-RMRR entry %p %p", domain, entry));
638 if (entry != domain->first_place &&
639 entry != domain->last_place)
641 entry->flags &= ~IOMMU_MAP_ENTRY_RMRR;
653 MPASS(end <= domain->end);
665 entry = RB_NFIND(iommu_gas_entries_tree, &domain->rb_root, &fentry);
667 if (entry->start >= start ||
668 (entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0)
674 res->start = entry->end = start;
677 &domain->rb_root, entry, res);
686 if (entry->start >= end || (entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0)
690 r->end = entry->start = end;
693 &domain->rb_root, entry, r);
703 if ((entry->flags & (IOMMU_MAP_ENTRY_UNMAPPED |
707 MPASS((entry->flags & IOMMU_MAP_ENTRY_PLACE) == 0);
708 entry->flags |= IOMMU_MAP_ENTRY_REMOVING;
727 if (entry->start >= end)
729 KASSERT(start <= entry->start,
731 entry->start, entry->end, start));
740 RB_FOREACH(entry, iommu_gas_entries_tree, &domain->rb_root) {
741 if ((entry->flags & (IOMMU_MAP_ENTRY_RMRR |
744 KASSERT(entry->end <= start || entry->start >= end,
747 entry->start, entry->end, start, end));
832 KASSERT(entry->end < domain->end, ("allocated GPA %jx, max GPA %jx",
833 (uintmax_t)entry->end, (uintmax_t)domain->end));
834 entry->flags |= eflags;
837 error = domain->ops->map(domain, entry, ma, eflags,
858 KASSERT(entry->domain == domain,
859 ("mismatched domain %p entry %p entry->domain %p", domain,
860 entry, entry->domain));
861 KASSERT(entry->flags == 0, ("used RMRR entry %p %p %x", domain,
862 entry, entry->flags));
866 start = entry->start;
873 entry->flags |= eflags;
875 if (entry->end == entry->start)
878 error = domain->ops->map(domain, entry,
879 ma + OFF_TO_IDX(start - entry->start), eflags,
900 entry->start = start;
901 entry->end = end;
904 entry->flags |= IOMMU_MAP_ENTRY_UNMAPPED;
940 end = ummin(end, domain->end);
949 next = RB_NFIND(iommu_gas_entries_tree, &domain->rb_root, &key);
951 "after %#jx", domain, (uintmax_t)domain->end,
953 entry_end = ummin(end, next->start);
954 prev = RB_PREV(iommu_gas_entries_tree, &domain->rb_root, next);
956 entry_start = ummax(start, prev->end);
959 start = next->end;
960 /* Reserve the region if non-empty. */
984 domain = ctx->domain;
985 entry = domain->msi_entry;
989 domain->ops->unmap(domain, entry, IOMMU_PGF_WAITOK);
995 domain->msi_entry = NULL;
996 domain->msi_base = 0;
997 domain->msi_phys = 0;
1009 domain = ctx->domain;
1013 entry = domain->msi_entry;
1017 error = iommu_gas_map(domain, &ctx->tag->common, size, offset,
1021 if (domain->msi_entry == NULL) {
1022 MPASS(domain->msi_base == 0);
1023 MPASS(domain->msi_phys == 0);
1025 domain->msi_entry = entry;
1026 domain->msi_base = entry->start;
1027 domain->msi_phys = VM_PAGE_TO_PHYS(ma[0]);
1035 } else if (domain->msi_entry != NULL) {
1052 *addr = (*addr - domain->msi_phys) + domain->msi_base;
1054 KASSERT(*addr >= domain->msi_entry->start,
1056 __func__, (uintmax_t)*addr, (uintmax_t)domain->msi_entry->start));
1058 KASSERT(*addr + sizeof(*addr) <= domain->msi_entry->end,
1060 __func__, (uintmax_t)*addr, (uintmax_t)domain->msi_entry->end));
1082 &domain->rb_root, domain->iommu, domain->flags);
1083 db_printf("iommu_domain %p tree %p\n", domain, &domain->rb_root);
1084 RB_FOREACH(entry, iommu_gas_entries_tree, &domain->rb_root) {
1087 entry, (uintmax_t)entry->start, (uintmax_t)entry->end,
1088 entry->flags,
1089 (uintmax_t)entry->first, (uintmax_t)entry->last,
1090 (uintmax_t)entry->free_down);
1091 if (entry == domain->start_gap)
1093 if (entry == domain->first_place)
1095 if (entry == domain->last_place)