Page MenuHomeFreeBSD
Files F111659816

D35502.id107010.diff
No OneTemporary
Actions

D35502.id107010.diff
View Options

Index: sys/dev/iommu/iommu_gas.c
===================================================================
--- sys/dev/iommu/iommu_gas.c
+++ sys/dev/iommu/iommu_gas.c
@@ -31,10 +31,11 @@
#include <sys/cdefs.h>
__FBSDID("$FreeBSD$");
-#define RB_AUGMENT(entry) iommu_gas_augment_entry(entry)
+#define RB_AUGMENT_CHECK(entry) iommu_gas_augment_entry(entry)
#include <sys/param.h>
#include <sys/systm.h>
+#include <sys/counter.h>
#include <sys/malloc.h>
#include <sys/bus.h>
#include <sys/interrupt.h>
@@ -139,27 +140,42 @@
return (0);
}
-static void
+static COUNTER_U64_DEFINE_EARLY(gas_augments);
+SYSCTL_COUNTER_U64(_hw_iommu, OID_AUTO, gas_augments, CTLFLAG_RD,
+ &gas_augments,
+ "Number of gas tree augmentations");
+
+static bool
iommu_gas_augment_entry(struct iommu_map_entry *entry)
{
struct iommu_map_entry *child;
- iommu_gaddr_t free_down;
+ iommu_gaddr_t free_left, free_right;
+ iommu_gaddr_t first, last, free_down;
- free_down = 0;
+ counter_u64_add(gas_augments, 1);
if ((child = RB_LEFT(entry, rb_entry)) != NULL) {
- free_down = MAX(free_down, child->free_down);
- free_down = MAX(free_down, entry->start - child->last);
- entry->first = child->first;
- } else
- entry->first = entry->start;
-
+ free_left = MAX(child->free_down, entry->start - child->last);
+ first = child->first;
+ } else {
+ free_left = 0;
+ first = entry->start;
+ }
if ((child = RB_RIGHT(entry, rb_entry)) != NULL) {
- free_down = MAX(free_down, child->free_down);
- free_down = MAX(free_down, child->first - entry->end);
- entry->last = child->last;
- } else
- entry->last = entry->end;
+ free_right = MAX(child->free_down, child->first - entry->end);
+ last = child->last;
+ } else {
+ free_right = 0;
+ last = entry->end;
+ }
+ free_down = MAX(free_left, free_right);
+ if (free_down == entry->free_down &&
+ first == entry->first &&
+ last == entry->last)
+ return (false);
+ entry->first = first;
+ entry->last = last;
entry->free_down = free_down;
+ return (true);
}
RB_GENERATE(iommu_gas_entries_tree, iommu_map_entry, rb_entry,
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -362,12 +362,20 @@
RB_RED_LEFT(RB_PARENT(elm, field), field) : \
RB_RED_RIGHT(RB_PARENT(elm, field), field))
+
/*
- * Something to be invoked in a loop at the root of every modified subtree,
- * from the bottom up to the root, to update augmented node data.
+ * Either RB_AUGMENT or RB_AUGMENT_CHECK is invoked in a loop at the root of
+ * every modified subtree, from the bottom up to the root, to update augmented
+ * node data. RB_AUGMENT_CHECK returns true only when the update changes the
+ * node data, so that updating can be stopped short of the root when it returns
+ * false.
*/
+#ifndef RB_AUGMENT_CHECK
#ifndef RB_AUGMENT
-#define RB_AUGMENT(x) break
+#define RB_AUGMENT_CHECK(x) false
+#else
+#define RB_AUGMENT_CHECK(x) (RB_AUGMENT(x), true)
+#endif
#endif
#define RB_SWAP_CHILD(head, out, in, field) do { \
@@ -388,7 +396,7 @@
RB_SWAP_CHILD(head, elm, tmp, field); \
RB_LEFT(tmp, field) = (elm); \
RB_SET_PARENT(elm, tmp, field); \
- RB_AUGMENT(elm); \
+ RB_AUGMENT_CHECK(elm); \
} while (/*CONSTCOND*/ 0)
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
@@ -400,7 +408,7 @@
RB_SWAP_CHILD(head, elm, tmp, field); \
RB_RIGHT(tmp, field) = (elm); \
RB_SET_PARENT(elm, tmp, field); \
- RB_AUGMENT(elm); \
+ RB_AUGMENT_CHECK(elm); \
} while (/*CONSTCOND*/ 0)
/* Generates prototypes and inline functions */
@@ -465,17 +473,18 @@
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
{ \
struct type *child, *parent; \
- while ((parent = RB_PARENT(elm, field)) != NULL) { \
+ bool changed; \
+ for (changed = true; \
+ (parent = RB_PARENT(elm, field)) != NULL; \
+ changed = changed && RB_AUGMENT_CHECK(elm), elm = parent) { \
if (RB_LEFT(parent, field) == elm) { \
if (RB_RED_LEFT(parent, field)) { \
RB_FLIP_LEFT(parent, field); \
- return; \
+ break; \
} \
RB_FLIP_RIGHT(parent, field); \
- if (RB_RED_RIGHT(parent, field)) { \
- elm = parent; \
+ if (RB_RED_RIGHT(parent, field)) \
continue; \
- } \
if (!RB_RED_RIGHT(elm, field)) { \
RB_FLIP_LEFT(elm, field); \
RB_ROTATE_LEFT(head, elm, child, field);\
@@ -489,13 +498,11 @@
} else { \
if (RB_RED_RIGHT(parent, field)) { \
RB_FLIP_RIGHT(parent, field); \
- return; \
+ break; \
} \
RB_FLIP_LEFT(parent, field); \
- if (RB_RED_LEFT(parent, field)) { \
- elm = parent; \
+ if (RB_RED_LEFT(parent, field)) \
continue; \
- } \
if (!RB_RED_LEFT(elm, field)) { \
RB_FLIP_RIGHT(elm, field); \
RB_ROTATE_RIGHT(head, elm, child, field);\
@@ -508,8 +515,14 @@
RB_ROTATE_LEFT(head, parent, elm, field); \
} \
RB_BITS(elm, field) &= ~RB_RED_MASK; \
+ RB_AUGMENT_CHECK(elm); \
+ elm = RB_PARENT(elm, field); \
break; \
} \
+ if (changed) { \
+ while (elm != NULL && RB_AUGMENT_CHECK(elm)) \
+ elm = RB_PARENT(elm, field); \
+ } \
}
#define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
@@ -518,9 +531,11 @@
struct type *parent, struct type *elm) \
{ \
struct type *sib; \
+ bool changed = true; \
if (RB_LEFT(parent, field) == elm && \
RB_RIGHT(parent, field) == elm) { \
RB_BITS(parent, field) &= ~RB_RED_MASK; \
+ changed = RB_AUGMENT_CHECK(parent); \
elm = parent; \
parent = RB_PARENT(elm, field); \
if (parent == NULL) \
@@ -530,17 +545,15 @@
if (RB_LEFT(parent, field) == elm) { \
if (!RB_RED_LEFT(parent, field)) { \
RB_FLIP_LEFT(parent, field); \
- return; \
+ break; \
} \
if (RB_RED_RIGHT(parent, field)) { \
RB_FLIP_RIGHT(parent, field); \
- elm = parent; \
continue; \
} \
sib = RB_RIGHT(parent, field); \
if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\
RB_BITS(sib, field) &= ~RB_RED_MASK; \
- elm = parent; \
continue; \
} \
RB_FLIP_RIGHT(sib, field); \
@@ -560,17 +573,15 @@
} else { \
if (!RB_RED_RIGHT(parent, field)) { \
RB_FLIP_RIGHT(parent, field); \
- return; \
+ break; \
} \
if (RB_RED_LEFT(parent, field)) { \
RB_FLIP_LEFT(parent, field); \
- elm = parent; \
continue; \
} \
sib = RB_LEFT(parent, field); \
if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\
RB_BITS(sib, field) &= ~RB_RED_MASK; \
- elm = parent; \
continue; \
} \
RB_FLIP_LEFT(sib, field); \
@@ -588,8 +599,16 @@
} \
RB_ROTATE_RIGHT(head, parent, sib, field); \
} \
+ RB_AUGMENT_CHECK(sib); \
+ parent = RB_PARENT(sib, field); \
break; \
- } while ((parent = RB_PARENT(elm, field)) != NULL); \
+ } while (elm = parent, \
+ changed = changed && RB_AUGMENT_CHECK(elm), \
+ (parent = RB_PARENT(elm, field)) != NULL); \
+ if (changed) { \
+ while (parent != NULL && RB_AUGMENT_CHECK(parent)) \
+ parent = RB_PARENT(parent, field); \
+ } \
}
#define RB_GENERATE_REMOVE(name, type, field, attr) \
@@ -627,10 +646,6 @@
RB_SET_PARENT(child, parent, field); \
if (parent != NULL) \
name##_RB_REMOVE_COLOR(head, parent, child); \
- while (parent != NULL) { \
- RB_AUGMENT(parent); \
- parent = RB_PARENT(parent, field); \
- } \
return (old); \
}
@@ -661,10 +676,6 @@
else \
RB_RIGHT(parent, field) = elm; \
name##_RB_INSERT_COLOR(head, elm); \
- while (elm != NULL) { \
- RB_AUGMENT(elm); \
- elm = RB_PARENT(elm, field); \
- } \
return (NULL); \
}

File Metadata

Mime Type
text/plain
Expires
Fri, Mar 7, 3:53 PM (19 h, 8 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
17034667
Default Alt Text
D35502.id107010.diff (7 KB)

Event Timeline