Page MenuHomeFreeBSD
Files F151209762

D36001.id108790.diff
No OneTemporary
Actions

D36001.id108790.diff
View Options

diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3
--- a/share/man/man3/tree.3
+++ b/share/man/man3/tree.3
@@ -520,10 +520,25 @@
and
.Fn RB_NFIND
macros can be used to find a particular element in the tree.
+.Pp
+The
+.Fn RB_FIND
+macro returns the element in the tree equal to the provided
+key, or
+.Dv NULL
+if there is no such element.
+.Pp
+The
+.Fn RB_NFIND
+macro returns the least element greater than or equal to the provided
+key, or
+.Dv NULL
+if there is no such element.
.Bd -literal -offset indent
-struct TYPE find, *res;
+struct TYPE find, *res, *resn;
find.key = 30;
res = RB_FIND(NAME, head, &find);
+resn = RB_NFIND(NAME, head, &find);
.Ed
.Pp
The
diff --git a/sys/dev/iommu/iommu.h b/sys/dev/iommu/iommu.h
--- a/sys/dev/iommu/iommu.h
+++ b/sys/dev/iommu/iommu.h
@@ -171,6 +171,8 @@
u_int flags);
void iommu_gas_free_entry(struct iommu_map_entry *entry);
void iommu_gas_free_space(struct iommu_map_entry *entry);
+void iommu_gas_remove(struct iommu_domain *domain, iommu_gaddr_t start,
+ iommu_gaddr_t size);
int iommu_gas_map(struct iommu_domain *domain,
const struct bus_dma_tag_common *common, iommu_gaddr_t size, int offset,
u_int eflags, u_int flags, vm_page_t *ma, struct iommu_map_entry **res);
diff --git a/sys/dev/iommu/iommu_gas.c b/sys/dev/iommu/iommu_gas.c
--- a/sys/dev/iommu/iommu_gas.c
+++ b/sys/dev/iommu/iommu_gas.c
@@ -600,6 +600,153 @@
IOMMU_DOMAIN_UNLOCK(domain);
}
+static struct iommu_map_entry *
+iommu_gas_clip(struct iommu_domain *domain, struct iommu_map_entry *entry,
+ iommu_gaddr_t clip, struct iommu_map_entry **r)
+{
+ struct iommu_map_entry *nentry;
+
+ IOMMU_DOMAIN_ASSERT_LOCKED(domain);
+ nentry = *r;
+ *r = NULL;
+ iommu_gas_rb_remove(domain, entry);
+ *nentry = *entry;
+ nentry->start = entry->end = clip;
+ iommu_gas_rb_insert(domain, entry);
+ iommu_gas_rb_insert(domain, nentry);
+ return (nentry);
+}
+
+static struct iommu_map_entry *
+iommu_gas_left_clip(struct iommu_domain *domain, struct iommu_map_entry *entry,
+ iommu_gaddr_t start, struct iommu_map_entry **r)
+{
+
+ IOMMU_DOMAIN_ASSERT_LOCKED(domain);
+ KASSERT(start <= entry->end,
+ ("iommu_gas_left_clip entry (%#jx, %#jx) start %#jx",
+ entry->start, entry->end, start));
+#ifdef INVARIANTS
+ if (start <= entry->start) {
+ struct iommu_map_entry *aentry;
+ aentry = RB_PREV(iommu_gas_entries_tree, &domain->rb_root,
+ entry);
+ if (aentry != NULL) {
+ KASSERT(aentry->end <= start,
+ ("iommu_gas_left_clip entry (%#jx, %#jx) next "
+ "(%#jx, %#jx) start %#jx", entry->start, entry->end,
+ aentry->start, aentry->end, start));
+ }
+ }
+#endif
+
+ return (iommu_gas_clip(domain, entry, start, r));
+}
+
+static struct iommu_map_entry *
+iommu_gas_right_clip(struct iommu_domain *domain, struct iommu_map_entry *entry,
+ iommu_gaddr_t end, struct iommu_map_entry **r)
+{
+
+ IOMMU_DOMAIN_ASSERT_LOCKED(domain);
+ KASSERT(end <= entry->end,
+ ("iommu_gas_right_clip entry (%#jx, %#jx) trim %#jx",
+ entry->start, entry->end, end));
+#ifdef INVARIANTS
+ if (end <= entry->start) {
+ struct iommu_map_entry *aentry;
+ aentry = RB_PREV(iommu_gas_entries_tree, &domain->rb_root,
+ entry);
+ if (aentry != NULL) {
+ KASSERT(aentry->end <= end,
+ ("iommu_gas_left_clip entry (%#jx, %#jx) next "
+ "(%#jx, %#jx) start %#jx", entry->start, entry->end,
+ aentry->start, aentry->end, end));
+ }
+ }
+#endif
+
+ return (iommu_gas_clip(domain, entry, end, r));
+}
+
+static void
+iommu_gas_remove_locked(struct iommu_domain *domain, iommu_gaddr_t start,
+ iommu_gaddr_t end, struct iommu_map_entry **r1, struct iommu_map_entry **r2)
+{
+ struct iommu_map_entry *entry, fentry, *nentry, *lentry;
+
+ IOMMU_DOMAIN_ASSERT_LOCKED(domain);
+ MPASS(start <= end);
+ MPASS(end <= domain->last_place->end);
+
+ /*
+ * Find an entry which contains the supplied guest's address
+ * start, or the first entry after the start. Since we
+ * asserted that start is below domain end, lentry should
+ * exist. Then clip it if needed.
+ */
+ fentry.start = start + 1;
+ fentry.end = start + 1;
+ lentry = RB_NFIND(iommu_gas_entries_tree, &domain->rb_root, &fentry);
+ MPASS(start <= lentry->start || (lentry->start <= start &&
+ start <= lentry->end));
+ entry = start <= lentry->start ? lentry :
+ iommu_gas_left_clip(domain, lentry, start, r1);
+
+ for (; entry != NULL && entry->end < end; entry = nentry) {
+ KASSERT(start <= entry->start,
+ ("iommu_gas_remove entry (%#jx, %#jx) start %#jx",
+ entry->start, entry->end, start));
+ KASSERT(entry->end <= end,
+ ("iommu_gas_remove entry (%#jx, %#jx) end %#jx",
+ entry->start, entry->end, end));
+ nentry = RB_NEXT(iommu_gas_entries_tree, &domain->rb_root,
+ entry);
+ if ((entry->flags & IOMMU_MAP_ENTRY_RMRR) == 0) {
+ iommu_gas_free_space(entry);
+ domain->ops->unmap(domain, entry->start,
+ entry->end - entry->start, IOMMU_PGF_WAITOK);
+ if ((entry->flags & IOMMU_MAP_ENTRY_PLACE) == 0)
+ iommu_gas_free_entry(entry);
+ }
+ }
+
+ if (entry->start < end)
+ (void)iommu_gas_right_clip(domain, entry, end, r2);
+
+#ifdef INVARIANTS
+ for (entry = RB_MIN(iommu_gas_entries_tree, &domain->rb_root);
+ entry != NULL; entry = RB_NEXT(iommu_gas_entries_tree,
+ &domain->rb_root, entry)) {
+ if ((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0)
+ continue;
+ KASSERT(entry->end <= start || entry->start >= end,
+ ("iommu_gas_remove leftover entry (%#jx, %#jx) range "
+ "(%#jx, %#jx)",
+ entry->start, entry->end, start, end));
+ }
+#endif
+}
+
+void
+iommu_gas_remove(struct iommu_domain *domain, iommu_gaddr_t start,
+ iommu_gaddr_t size)
+{
+ struct iommu_map_entry *r1, *r2;
+ iommu_gaddr_t end;
+
+ end = start + size;
+ r1 = iommu_gas_alloc_entry(domain, IOMMU_PGF_WAITOK);
+ r2 = iommu_gas_alloc_entry(domain, IOMMU_PGF_WAITOK);
+ IOMMU_DOMAIN_LOCK(domain);
+ iommu_gas_remove_locked(domain, start, end, &r1, &r2);
+ IOMMU_DOMAIN_UNLOCK(domain);
+ if (r1 != NULL)
+ iommu_gas_free_entry(r1);
+ if (r2 != NULL)
+ iommu_gas_free_entry(r2);
+}
+
int
iommu_gas_map(struct iommu_domain *domain,
const struct bus_dma_tag_common *common, iommu_gaddr_t size, int offset,

File Metadata

Mime Type
text/plain
Expires
Tue, Apr 7, 8:49 PM (1 h, 1 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
31049125
Default Alt Text
D36001.id108790.diff (6 KB)

Event Timeline