Page MenuHomeFreeBSD
Files F133591996

D23189.id66849.diff
No OneTemporary
Actions

D23189.id66849.diff
View Options

Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -335,8 +335,12 @@
RB_COLOR(red, field) = RB_RED; \
} while (/*CONSTCOND*/ 0)
+/*
+ * 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.
+ */
#ifndef RB_AUGMENT
-#define RB_AUGMENT(x) do {} while (0)
+#define RB_AUGMENT(x) break
#endif
#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
@@ -344,7 +348,6 @@
if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
} \
- RB_AUGMENT(elm); \
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
@@ -354,9 +357,7 @@
(head)->rbh_root = (tmp); \
RB_LEFT(tmp, field) = (elm); \
RB_PARENT(elm, field) = (tmp); \
- RB_AUGMENT(tmp); \
- if ((RB_PARENT(tmp, field))) \
- RB_AUGMENT(RB_PARENT(tmp, field)); \
+ RB_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)
#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
@@ -364,7 +365,6 @@
if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
} \
- RB_AUGMENT(elm); \
if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
@@ -374,9 +374,7 @@
(head)->rbh_root = (tmp); \
RB_RIGHT(tmp, field) = (elm); \
RB_PARENT(elm, field) = (tmp); \
- RB_AUGMENT(tmp); \
- if ((RB_PARENT(tmp, field))) \
- RB_AUGMENT(RB_PARENT(tmp, field)); \
+ RB_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)
/* Generates prototypes and inline functions */
@@ -571,62 +569,49 @@
else if (RB_RIGHT(elm, field) == NULL) \
child = RB_LEFT(elm, field); \
else { \
- struct type *left; \
- elm = RB_RIGHT(elm, field); \
- while ((left = RB_LEFT(elm, field)) != NULL) \
- elm = left; \
- child = RB_RIGHT(elm, field); \
- parent = RB_PARENT(elm, field); \
- color = RB_COLOR(elm, field); \
- if (child) \
- RB_PARENT(child, field) = parent; \
- if (parent) { \
- if (RB_LEFT(parent, field) == elm) \
- RB_LEFT(parent, field) = child; \
+ elm = RB_RIGHT(old, field); \
+ if ((child = RB_LEFT(elm, field)) == NULL) { \
+ child = RB_RIGHT(elm, field); \
+ RB_RIGHT(old, field) = child; \
+ RB_PARENT(elm, field) = elm; \
+ } else { \
+ do \
+ elm = child; \
+ while ((child = RB_LEFT(elm, field)) != NULL); \
+ child = RB_RIGHT(elm, field); \
+ RB_PARENT(RB_RIGHT(old, field), field) = elm; \
+ } \
+ RB_PARENT(RB_LEFT(old, field), field) = elm; \
+ parent = RB_PARENT(old, field); \
+ if (parent != NULL) { \
+ if (RB_LEFT(parent, field) == old) \
+ RB_LEFT(parent, field) = elm; \
else \
- RB_RIGHT(parent, field) = child; \
- RB_AUGMENT(parent); \
+ RB_RIGHT(parent, field) = elm; \
} else \
- RB_ROOT(head) = child; \
- if (RB_PARENT(elm, field) == old) \
- parent = elm; \
- (elm)->field = (old)->field; \
- if (RB_PARENT(old, field)) { \
- if (RB_LEFT(RB_PARENT(old, field), field) == old)\
- RB_LEFT(RB_PARENT(old, field), field) = elm;\
- else \
- RB_RIGHT(RB_PARENT(old, field), field) = elm;\
- RB_AUGMENT(RB_PARENT(old, field)); \
- } else \
RB_ROOT(head) = elm; \
- RB_PARENT(RB_LEFT(old, field), field) = elm; \
- if (RB_RIGHT(old, field)) \
- RB_PARENT(RB_RIGHT(old, field), field) = elm; \
- if (parent) { \
- left = parent; \
- do { \
- RB_AUGMENT(left); \
- } while ((left = RB_PARENT(left, field)) != NULL); \
- } \
- goto color; \
} \
parent = RB_PARENT(elm, field); \
color = RB_COLOR(elm, field); \
- if (child) \
+ if (child != NULL) \
RB_PARENT(child, field) = parent; \
- if (parent) { \
+ if (parent != NULL) { \
if (RB_LEFT(parent, field) == elm) \
RB_LEFT(parent, field) = child; \
else \
RB_RIGHT(parent, field) = child; \
- RB_AUGMENT(parent); \
} else \
RB_ROOT(head) = child; \
-color: \
+ if (elm != old) \
+ (elm)->field = (old)->field; \
if (color == RB_BLACK) \
name##_RB_REMOVE_COLOR(head, parent, child); \
+ while (parent != NULL) { \
+ RB_AUGMENT(parent); \
+ parent = RB_PARENT(parent, field); \
+ } \
return (old); \
-} \
+}
#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \
/* Inserts a node into the RB tree */ \
@@ -653,10 +638,13 @@
RB_LEFT(parent, field) = elm; \
else \
RB_RIGHT(parent, field) = elm; \
- RB_AUGMENT(parent); \
} else \
RB_ROOT(head) = elm; \
name##_RB_INSERT_COLOR(head, elm); \
+ while (elm != NULL) { \
+ RB_AUGMENT(elm); \
+ elm = RB_PARENT(elm, field); \
+ } \
return (NULL); \
}
Index: sys/x86/iommu/intel_gas.c
===================================================================
--- sys/x86/iommu/intel_gas.c
+++ sys/x86/iommu/intel_gas.c
@@ -139,38 +139,20 @@
static void
dmar_gas_augment_entry(struct dmar_map_entry *entry)
{
- struct dmar_map_entry *l, *r;
+ struct dmar_map_entry *child;
+ dmar_gaddr_t free_down;
- for (; entry != NULL; entry = RB_PARENT(entry, rb_entry)) {
- l = RB_LEFT(entry, rb_entry);
- r = RB_RIGHT(entry, rb_entry);
- if (l == NULL && r == NULL) {
- entry->free_down = entry->free_after;
- } else if (l == NULL && r != NULL) {
- entry->free_down = MAX(entry->free_after, r->free_down);
- } else if (/*l != NULL && */ r == NULL) {
- entry->free_down = MAX(entry->free_after, l->free_down);
- } else /* if (l != NULL && r != NULL) */ {
- entry->free_down = MAX(entry->free_after, l->free_down);
- entry->free_down = MAX(entry->free_down, r->free_down);
- }
- }
+ free_down = entry->free_after;
+ if ((child = RB_LEFT(entry, rb_entry)) != NULL)
+ free_down = MAX(free_down, child->free_down);
+ if ((child = RB_RIGHT(entry, rb_entry)) != NULL)
+ free_down = MAX(free_down, child->free_down);
+ entry->free_down = free_down;
}
RB_GENERATE(dmar_gas_entries_tree, dmar_map_entry, rb_entry,
dmar_gas_cmp_entries);
-static void
-dmar_gas_fix_free(struct dmar_domain *domain, struct dmar_map_entry *entry)
-{
- struct dmar_map_entry *next;
-
- next = RB_NEXT(dmar_gas_entries_tree, &domain->rb_root, entry);
- entry->free_after = (next != NULL ? next->start : domain->end) -
- entry->end;
- dmar_gas_augment_entry(entry);
-}
-
#ifdef INVARIANTS
static void
dmar_gas_check_free(struct dmar_domain *domain)
@@ -211,13 +193,9 @@
static bool
dmar_gas_rb_insert(struct dmar_domain *domain, struct dmar_map_entry *entry)
{
- struct dmar_map_entry *prev, *found;
+ struct dmar_map_entry *found;
found = RB_INSERT(dmar_gas_entries_tree, &domain->rb_root, entry);
- dmar_gas_fix_free(domain, entry);
- prev = RB_PREV(dmar_gas_entries_tree, &domain->rb_root, entry);
- if (prev != NULL)
- dmar_gas_fix_free(domain, prev);
return (found == NULL);
}
@@ -228,8 +206,6 @@
prev = RB_PREV(dmar_gas_entries_tree, &domain->rb_root, entry);
RB_REMOVE(dmar_gas_entries_tree, &domain->rb_root, entry);
- if (prev != NULL)
- dmar_gas_fix_free(domain, prev);
}
void

File Metadata

Mime Type
text/plain
Expires
Mon, Oct 27, 9:29 PM (9 h, 33 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
24316848
Default Alt Text
D23189.id66849.diff (7 KB)

Event Timeline