Page MenuHomeFreeBSD
Files F111380942

D36001.id108783.diff
No OneTemporary
Actions

D36001.id108783.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,26 @@
and
.Fn RB_NFIND
macros can be used to find a particular element in the tree.
+.Pp
+The
+.Fn RB_FIND
+searches for the element which compares equal to the provided
+key element, with possible
+.Dv NULL
+result if no such element exists.
+.Pp
+The
+.Fn RB_NFIND
+searches for the least element which compares greater or equal
+to the provided key element (key is on the left side of comparision),
+again with possible
+.Dv NULL
+result if no such element exists.
.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,217 @@
IOMMU_DOMAIN_UNLOCK(domain);
}
+/*
+ * Find an entry which contains the supplied guest's address start,
+ * or the first entry after the start,
+ * or NULL if there is no any such entries.
+ */
+static struct iommu_map_entry *
+iommu_gas_find_left_clip_entry(struct iommu_domain *domain, iommu_gaddr_t start)
+{
+ struct iommu_map_entry *entry, *nentry, fentry;
+
+ IOMMU_DOMAIN_ASSERT_LOCKED(domain);
+
+ fentry.start = start - 1;
+ fentry.end = start - 1;
+ entry = RB_NFIND(iommu_gas_entries_tree, &domain->rb_root, &fentry);
+ if (entry == NULL)
+ entry = RB_MIN(iommu_gas_entries_tree, &domain->rb_root);
+ for (;;) {
+ if (entry->end <= start) {
+ entry = RB_NEXT(iommu_gas_entries_tree,
+ &domain->rb_root, entry);
+ if (entry == NULL || start <= entry->start)
+ break;
+ } else if (start < entry->start) {
+ nentry = RB_PREV(iommu_gas_entries_tree,
+ &domain->rb_root, entry);
+ if (nentry == NULL || nentry->end <= start)
+ break;
+ entry = nentry;
+ } else
+ break;
+ }
+ return (entry);
+}
+
+/*
+ * Find an entry which contains the supplied guest's address end,
+ * or the last entry before the end,
+ * or NULL if there is no any such entries.
+ */
+static struct iommu_map_entry *
+iommu_gas_find_right_clip_entry(struct iommu_domain *domain, iommu_gaddr_t end)
+{
+ struct iommu_map_entry *entry, *nentry, fentry;
+
+ IOMMU_DOMAIN_ASSERT_LOCKED(domain);
+
+ fentry.start = end - 1;
+ fentry.end = end - 1;
+ entry = RB_NFIND(iommu_gas_entries_tree, &domain->rb_root, &fentry);
+ if (entry == NULL)
+ entry = RB_MAX(iommu_gas_entries_tree, &domain->rb_root);
+ MPASS(entry != NULL);
+ for (;;) {
+ if (end < entry->end) {
+ nentry = RB_PREV(iommu_gas_entries_tree,
+ &domain->rb_root, entry);
+ if (nentry == NULL || nentry->end <= end)
+ break;
+ entry = nentry;
+ } else if (entry->end < end) {
+ entry = RB_NEXT(iommu_gas_entries_tree,
+ &domain->rb_root, entry);
+ if (entry == NULL || end <= nentry->end)
+ break;
+ } else
+ break;
+ }
+ return (entry);
+}
+
+static struct iommu_map_entry *
+iommu_gas_clip(struct iommu_domain *domain, struct iommu_map_entry *entry,
+ iommu_gaddr_t clip, bool left, struct iommu_map_entry **r)
+{
+ struct iommu_map_entry *nentry;
+
+ IOMMU_DOMAIN_ASSERT_LOCKED(domain);
+ if (left) {
+ if (clip <= entry->start)
+ return (entry);
+ } else {
+ if (entry->end <= clip)
+ return (entry);
+ }
+ 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, true, 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, false, 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, *nentry, *lentry, *rentry;
+
+ IOMMU_DOMAIN_ASSERT_LOCKED(domain);
+ lentry = iommu_gas_find_left_clip_entry(domain, start);
+ entry = iommu_gas_left_clip(domain, lentry, start, r1);
+ rentry = iommu_gas_find_right_clip_entry(domain, end);
+ (void)iommu_gas_right_clip(domain, rentry, end, r2);
+ for (; entry != NULL && entry->start < 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);
+ }
+ }
+#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;
+ MPASS(start <= end);
+ MPASS(end <= domain->last_place->end);
+
+ 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, Mar 4, 1:53 AM (10 h, 10 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
16958796
Default Alt Text
D36001.id108783.diff (7 KB)

Event Timeline