Page MenuHomeFreeBSD
Files F143243380

D36624.id110770.diff
No OneTemporary
Actions

D36624.id110770.diff
View Options

Index: sys/dev/iommu/iommu.h
===================================================================
--- sys/dev/iommu/iommu.h
+++ sys/dev/iommu/iommu.h
@@ -109,6 +109,7 @@
struct iommu_map_entries_tailq unload_entries; /* (d) Entries to
unload */
struct iommu_gas_entries_tree rb_root; /* (d) */
+ struct iommu_map_entry *start_gap; /* (d) */
iommu_gaddr_t end; /* (c) Highest address + 1 in
the guest AS */
struct iommu_map_entry *first_place, *last_place; /* (d) */
Index: sys/dev/iommu/iommu_gas.c
===================================================================
--- sys/dev/iommu/iommu_gas.c
+++ sys/dev/iommu/iommu_gas.c
@@ -219,6 +219,12 @@
iommu_gas_rb_remove(struct iommu_domain *domain, struct iommu_map_entry *entry)
{
+ /*
+ * The predecessor to the removed entry may become the new greatest
+ * lower bound on free gaps.
+ */
+ if (entry->end <= domain->start_gap->end)
+ domain->start_gap = iommu_gas_entries_tree_RB_PREV(entry);
RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry);
}
@@ -262,6 +268,7 @@
begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
iommu_gas_rb_insert(domain, begin);
+ domain->start_gap = begin;
domain->first_place = begin;
domain->last_place = end;
domain->flags |= IOMMU_DOMAIN_GAS_INITED;
@@ -283,7 +290,7 @@
KASSERT(entry->flags ==
(IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED),
("start entry flags %p", domain));
- RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry);
+ iommu_gas_rb_remove(domain, entry);
iommu_gas_free_entry(entry);
entry = RB_MAX(iommu_gas_entries_tree, &domain->rb_root);
@@ -292,15 +299,14 @@
KASSERT(entry->flags ==
(IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED),
("end entry flags %p", domain));
- RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry);
+ iommu_gas_rb_remove(domain, entry);
iommu_gas_free_entry(entry);
RB_FOREACH_SAFE(entry, iommu_gas_entries_tree, &domain->rb_root,
entry1) {
KASSERT((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0,
("non-RMRR entry left %p", domain));
- RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root,
- entry);
+ iommu_gas_rb_remove(domain, entry);
iommu_gas_free_entry(entry);
}
}
@@ -383,6 +389,9 @@
found = iommu_gas_rb_insert(a->domain, entry);
KASSERT(found, ("found dup %p start %jx size %jx",
a->domain, (uintmax_t)start, (uintmax_t)size));
+ /* The new entry may be a new, greater lower bound on free gaps. */
+ if (start == a->domain->start_gap->end)
+ a->domain->start_gap = entry;
return (true);
}
@@ -420,6 +429,26 @@
KASSERT(a->entry->flags == 0,
("dirty entry %p %p", a->domain, a->entry));
+ /* Make start_gap the greatest lower bound on free gaps. */
+ min_free = 3 * IOMMU_PAGE_SIZE;
+ first = a->domain->start_gap;
+ while (first != NULL && first->free_down < min_free)
+ first = RB_PARENT(first, rb_entry);
+ for (curr = first; curr != NULL;
+ curr = iommu_gas_next(curr, min_free)) {
+ if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
+ first->last < curr->start) {
+ a->domain->start_gap =
+ iommu_gas_entries_tree_RB_PREV(first);
+ break;
+ }
+ if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
+ curr->end < first->first) {
+ a->domain->start_gap = curr;
+ break;
+ }
+ }
+
/*
* If the subtree doesn't have free space for the requested allocation
* plus two guard pages, skip it.
@@ -431,12 +460,9 @@
* Find the first entry in the lower region that could abut a big-enough
* range.
*/
- curr = RB_ROOT(&a->domain->rb_root);
- first = NULL;
- while (curr != NULL && curr->free_down >= min_free) {
- first = curr;
- curr = RB_LEFT(curr, rb_entry);
- }
+ first = a->domain->start_gap;
+ while (first != NULL && first->free_down < min_free)
+ first = RB_PARENT(first, rb_entry);
/*
* Walk the big-enough ranges until one satisfies alignment

File Metadata

Mime Type
text/plain
Expires
Wed, Jan 28, 11:50 PM (2 h, 21 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
28069808
Default Alt Text
D36624.id110770.diff (3 KB)

Event Timeline