linuxkpi: Include <linux/rbtree.h> from <linux/hrtimer.h> and <linux/mm_types.h>

[dumbbell]

Summary

Why

Some files in DRM rely on this indirect include to use struct rb_*.

This is part of the update of the DRM drivers to Linux 5.18.

sys/compat/linuxkpi/common/include/linux/hrtimer.h

RB_FOREACH(entry, iommu_gas_entries_tree, &domain->rb_root) {
                 MPASS(entry->free_down == v);
         }
 }
 #endif
 
 static void
 iommu_gas_rb_remove(struct iommu_domain *domain, struct iommu_map_entry *entry)
 {
+        struct iommu_map_entry *nbr;
 
+        /* Removing entry may open a new free gap before domain->start_gap. */
+        if (entry->end <= domain->start_gap->end) {
+                if (RB_RIGHT(entry, rb_entry) != NULL)
+                        nbr = iommu_gas_entries_tree_RB_NEXT(entry);
+                else if (RB_LEFT(entry, rb_entry) != NULL)
+                        nbr = RB_LEFT(entry, rb_entry);
+                else
+                        nbr = RB_PARENT(entry, rb_entry);
+                domain->start_gap = nbr;
+        }
         RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry);
 }
 
 struct iommu_domain *
 iommu_get_ctx_domain(struct iommu_ctx *ctx)
 {
 
         return (ctx->domain);
iommu_gas_init_domain(struct iommu_domain *domain)
         end->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
         RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, end);
 
         begin->start = 0;
         begin->end = IOMMU_PAGE_SIZE;
         begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
         RB_INSERT_PREV(iommu_gas_entries_tree, &domain->rb_root, end, begin);
 
+        domain->start_gap = end;
         domain->first_place = begin;
         domain->last_place = end;
         domain->flags |= IOMMU_DOMAIN_GAS_INITED;
         IOMMU_DOMAIN_UNLOCK(domain);
 }
 
 void
 iommu_gas_fini_domain(struct iommu_domain *domain)
RB_FOREACH_SAFE(entry, iommu_gas_entries_tree, &domain->rb_root,
                 KASSERT((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0,
                     ("non-RMRR entry left %p", domain));
                 iommu_gas_rb_remove(domain, entry);
                 iommu_gas_free_entry(entry);
         }
 }
 
 struct iommu_gas_match_args {
-        struct iommu_domain *domain;
         iommu_gaddr_t size;
         int offset;
         const struct bus_dma_tag_common *common;
         u_int gas_flags;
         struct iommu_map_entry *entry;
 };
 
 /*
if ((next = RB_RIGHT(curr, rb_entry)) != NULL &&
                 while ((next = RB_PARENT(curr, rb_entry)) != NULL &&
                     curr == RB_RIGHT(next, rb_entry))
                         curr = next;
                 curr = next;
         }
         return (curr);
 }
 
+/*
+ * Address-ordered first-fit search of 'domain' for free space satisfying the
+ * conditions of 'a'.  The space allocated is at least one page big, and is
+ * bounded by guard pages to left and right.  The allocated space for 'domain'
+ * is described by an rb-tree of map entries at domain->rb_root, and
+ * domain->start_gap points a map entry less than or adjacent to the first
+ * free-space of size at least 3 pages.
+ */
 static int
-iommu_gas_find_space(struct iommu_gas_match_args *a)
+iommu_gas_find_space(struct iommu_domain *domain,
+    struct iommu_gas_match_args *a)
 {
-        struct iommu_domain *domain;
         struct iommu_map_entry *curr, *first;
         iommu_gaddr_t addr, min_free;
 
-        IOMMU_DOMAIN_ASSERT_LOCKED(a->domain);
+        IOMMU_DOMAIN_ASSERT_LOCKED(domain);
         KASSERT(a->entry->flags == 0,
-            ("dirty entry %p %p", a->domain, a->entry));
+            ("dirty entry %p %p", domain, a->entry));
 
         /*
+         * start_gap may point to an entry adjacent to gaps too small for any
+         * new allocation.  In that case, advance start_gap to the first free
+         * space big enough for a minimum allocation plus two guard pages.
+         */
+        min_free = 3 * IOMMU_PAGE_SIZE;
+        first = 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 + min_free <= curr->start)
+                        break;
+                if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
+                    curr->end + min_free <= first->first)
+                        break;
+        }
+        domain->start_gap = curr;
+
+        /*
          * If the subtree doesn't have free space for the requested allocation
          * plus two guard pages, skip it.
          */
         min_free = 2 * IOMMU_PAGE_SIZE +
             roundup2(a->size + a->offset, IOMMU_PAGE_SIZE);
 
-        /*
-         * Find the first entry in the lower region that could abut a big-enough
-         * range.
-         */
-        domain = a->domain;
-        curr = RB_ROOT(&domain->rb_root);
-        first = NULL;
-        while (curr != NULL && curr->free_down >= min_free) {
-                first = curr;
-                curr = RB_LEFT(curr, rb_entry);
-        }
+        /* Climb to find a node in the subtree of big-enough ranges. */
+        while (first != NULL && first->free_down < min_free)
+                first = RB_PARENT(first, rb_entry);
 
         /*
-         * Walk the big-enough ranges until one satisfies alignment
+         * Walk the big-enough ranges tree until one satisfies alignment
          * requirements, or violates lowaddr address requirement.
          */
         addr = a->common->lowaddr + 1;
         for (curr = first; curr != NULL;
             curr = iommu_gas_next(curr, min_free)) {
                 if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
                     iommu_gas_match_one(a, first->last, curr->start,
                     0, addr)) {

 {
         struct iommu_gas_match_args a;
         struct iommu_map_entry *entry;
         int error;
 
         KASSERT((flags & ~(IOMMU_MF_CANWAIT | IOMMU_MF_CANSPLIT)) == 0,
             ("invalid flags 0x%x", flags));
 
-        a.domain = domain;
         a.size = size;
         a.offset = offset;
         a.common = common;
         a.gas_flags = flags;
         entry = iommu_gas_alloc_entry(domain,
             (flags & IOMMU_MF_CANWAIT) != 0 ? IOMMU_PGF_WAITOK : 0);
         if (entry == NULL)
                 return (ENOMEM);
         a.entry = entry;
         IOMMU_DOMAIN_LOCK(domain);
-        error = iommu_gas_find_space(&a);
+        error = iommu_gas_find_space(domain, &a);
         if (error == ENOMEM) {
                 IOMMU_DOMAIN_UNLOCK(domain);
                 iommu_gas_free_entry(entry);
                 return (error);
         }
 #ifdef INVARIANTS
         if (iommu_check_free)
                 iommu_gas_check_free(domain);

sys/compat/linuxkpi/common/include/linux/mm_types.h

RB_FOREACH(entry, iommu_gas_entries_tree, &domain->rb_root) {
                 MPASS(entry->free_down == v);
         }
 }
 #endif
 
 static void
 iommu_gas_rb_remove(struct iommu_domain *domain, struct iommu_map_entry *entry)
 {
+        struct iommu_map_entry *nbr;
 
+        /* Removing entry may open a new free gap before domain->start_gap. */
+        if (entry->end <= domain->start_gap->end) {
+                if (RB_RIGHT(entry, rb_entry) != NULL)
+                        nbr = iommu_gas_entries_tree_RB_NEXT(entry);
+                else if (RB_LEFT(entry, rb_entry) != NULL)
+                        nbr = RB_LEFT(entry, rb_entry);
+                else
+                        nbr = RB_PARENT(entry, rb_entry);
+                domain->start_gap = nbr;
+        }
         RB_REMOVE(iommu_gas_entries_tree, &domain->rb_root, entry);
 }
 
 struct iommu_domain *
 iommu_get_ctx_domain(struct iommu_ctx *ctx)
 {
 
         return (ctx->domain);
iommu_gas_init_domain(struct iommu_domain *domain)
         end->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
         RB_INSERT(iommu_gas_entries_tree, &domain->rb_root, end);
 
         begin->start = 0;
         begin->end = IOMMU_PAGE_SIZE;
         begin->flags = IOMMU_MAP_ENTRY_PLACE | IOMMU_MAP_ENTRY_UNMAPPED;
         RB_INSERT_PREV(iommu_gas_entries_tree, &domain->rb_root, end, begin);
 
+        domain->start_gap = end;
         domain->first_place = begin;
         domain->last_place = end;
         domain->flags |= IOMMU_DOMAIN_GAS_INITED;
         IOMMU_DOMAIN_UNLOCK(domain);
 }
 
 void
 iommu_gas_fini_domain(struct iommu_domain *domain)
RB_FOREACH_SAFE(entry, iommu_gas_entries_tree, &domain->rb_root,
                 KASSERT((entry->flags & IOMMU_MAP_ENTRY_RMRR) != 0,
                     ("non-RMRR entry left %p", domain));
                 iommu_gas_rb_remove(domain, entry);
                 iommu_gas_free_entry(entry);
         }
 }
 
 struct iommu_gas_match_args {
-        struct iommu_domain *domain;
         iommu_gaddr_t size;
         int offset;
         const struct bus_dma_tag_common *common;
         u_int gas_flags;
         struct iommu_map_entry *entry;
 };
 
 /*
if ((next = RB_RIGHT(curr, rb_entry)) != NULL &&
                 while ((next = RB_PARENT(curr, rb_entry)) != NULL &&
                     curr == RB_RIGHT(next, rb_entry))
                         curr = next;
                 curr = next;
         }
         return (curr);
 }
 
+/*
+ * Address-ordered first-fit search of 'domain' for free space satisfying the
+ * conditions of 'a'.  The space allocated is at least one page big, and is
+ * bounded by guard pages to left and right.  The allocated space for 'domain'
+ * is described by an rb-tree of map entries at domain->rb_root, and
+ * domain->start_gap points a map entry less than or adjacent to the first
+ * free-space of size at least 3 pages.
+ */
 static int
-iommu_gas_find_space(struct iommu_gas_match_args *a)
+iommu_gas_find_space(struct iommu_domain *domain,
+    struct iommu_gas_match_args *a)
 {
-        struct iommu_domain *domain;
         struct iommu_map_entry *curr, *first;
         iommu_gaddr_t addr, min_free;
 
-        IOMMU_DOMAIN_ASSERT_LOCKED(a->domain);
+        IOMMU_DOMAIN_ASSERT_LOCKED(domain);
         KASSERT(a->entry->flags == 0,
-            ("dirty entry %p %p", a->domain, a->entry));
+            ("dirty entry %p %p", domain, a->entry));
 
         /*
+         * start_gap may point to an entry adjacent to gaps too small for any
+         * new allocation.  In that case, advance start_gap to the first free
+         * space big enough for a minimum allocation plus two guard pages.
+         */
+        min_free = 3 * IOMMU_PAGE_SIZE;
+        first = 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 + min_free <= curr->start)
+                        break;
+                if ((first = RB_RIGHT(curr, rb_entry)) != NULL &&
+                    curr->end + min_free <= first->first)
+                        break;
+        }
+        domain->start_gap = curr;
+
+        /*
          * If the subtree doesn't have free space for the requested allocation
          * plus two guard pages, skip it.
          */
         min_free = 2 * IOMMU_PAGE_SIZE +
             roundup2(a->size + a->offset, IOMMU_PAGE_SIZE);
 
-        /*
-         * Find the first entry in the lower region that could abut a big-enough
-         * range.
-         */
-        domain = a->domain;
-        curr = RB_ROOT(&domain->rb_root);
-        first = NULL;
-        while (curr != NULL && curr->free_down >= min_free) {
-                first = curr;
-                curr = RB_LEFT(curr, rb_entry);
-        }
+        /* Climb to find a node in the subtree of big-enough ranges. */
+        while (first != NULL && first->free_down < min_free)
+                first = RB_PARENT(first, rb_entry);
 
         /*
-         * Walk the big-enough ranges until one satisfies alignment
+         * Walk the big-enough ranges tree until one satisfies alignment
          * requirements, or violates lowaddr address requirement.
          */
         addr = a->common->lowaddr + 1;
         for (curr = first; curr != NULL;
             curr = iommu_gas_next(curr, min_free)) {
                 if ((first = RB_LEFT(curr, rb_entry)) != NULL &&
                     iommu_gas_match_one(a, first->last, curr->start,
                     0, addr)) {

 {
         struct iommu_gas_match_args a;
         struct iommu_map_entry *entry;
         int error;
 
         KASSERT((flags & ~(IOMMU_MF_CANWAIT | IOMMU_MF_CANSPLIT)) == 0,
             ("invalid flags 0x%x", flags));
 
-        a.domain = domain;
         a.size = size;
         a.offset = offset;
         a.common = common;
         a.gas_flags = flags;
         entry = iommu_gas_alloc_entry(domain,
             (flags & IOMMU_MF_CANWAIT) != 0 ? IOMMU_PGF_WAITOK : 0);
         if (entry == NULL)
                 return (ENOMEM);
         a.entry = entry;
         IOMMU_DOMAIN_LOCK(domain);
-        error = iommu_gas_find_space(&a);
+        error = iommu_gas_find_space(domain, &a);
         if (error == ENOMEM) {
                 IOMMU_DOMAIN_UNLOCK(domain);
                 iommu_gas_free_entry(entry);
                 return (error);
         }
 #ifdef INVARIANTS
         if (iommu_check_free)
                 iommu_gas_check_free(domain);