git: d8a88ec38149 - stable/13 - rb_tree: restore binary compat w/ 13
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Fri, 16 Dec 2022 09:18:51 UTC
The branch stable/13 has been updated by dougm:
URL: https://cgit.FreeBSD.org/src/commit/?id=d8a88ec381498f5942403088d28ee325b92e9a78
commit d8a88ec381498f5942403088d28ee325b92e9a78
Author: Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-12-16 09:15:28 +0000
Commit: Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-12-16 09:15:28 +0000
rb_tree: restore binary compat w/ 13
A change to RB_COLOR_INSERT, when merged into stable/13, broke binary
compatibility. For 13, call the new function RB_DO_COLOR_INSERT, and
restore the old function with the original name and parameters. Define
RB_COLOR_INSERT in tree.h, and remove changes to the linux rbtree
header.
Another change altered the order of pointers in the RB_ENTRY struct.
For 13, restore the original order.
Reported by: manu
Reviewed by: hselasky
Tested by: manu
Differential Revision: https://reviews.freebsd.org/D37716
---
sys/compat/linuxkpi/common/include/linux/rbtree.h | 11 ++----
sys/sys/tree.h | 46 ++++++++++++++++-------
2 files changed, 35 insertions(+), 22 deletions(-)
diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h
index 37537d4b2724..de21f0e4c613 100644
--- a/sys/compat/linuxkpi/common/include/linux/rbtree.h
+++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h
@@ -74,11 +74,8 @@ RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp);
#define RB_EMPTY_NODE(node) (RB_PARENT(node, __entry) == node)
#define RB_CLEAR_NODE(node) RB_SET_PARENT(node, node, __entry)
-#define rb_insert_color(node, root) do { \
- if (rb_parent(node)) \
- linux_root_RB_INSERT_COLOR((struct linux_root *)(root), \
- rb_parent(node), (node)); \
-} while (0)
+#define rb_insert_color(node, root) \
+ linux_root_RB_INSERT_COLOR((struct linux_root *)(root), (node))
#define rb_erase(node, root) \
linux_root_RB_REMOVE((struct linux_root *)(root), (node))
#define rb_next(node) RB_NEXT(linux_root, NULL, (node))
@@ -148,9 +145,7 @@ static inline void
rb_insert_color_cached(struct rb_node *node, struct rb_root_cached *root,
bool leftmost)
{
- if (rb_parent(node))
- linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root,
- rb_parent(node), node);
+ linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, node);
if (leftmost)
root->rb_leftmost = node;
}
diff --git a/sys/sys/tree.h b/sys/sys/tree.h
index 0fb3cf94eebc..d6408c045913 100644
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -331,7 +331,7 @@ struct { \
* that the left or right child of the tree node is "red".
*/
#define _RB_LINK(elm, dir, field) (elm)->field.rbe_link[dir]
-#define _RB_UP(elm, field) _RB_LINK(elm, 0, field)
+#define _RB_UP(elm, field) _RB_LINK(elm, 2, field)
#define _RB_L ((__uintptr_t)1)
#define _RB_R ((__uintptr_t)2)
#define _RB_LR ((__uintptr_t)3)
@@ -341,8 +341,8 @@ struct { \
((__uintptr_t)elm & ~_RB_LR)
#define RB_PARENT(elm, field) _RB_PTR(_RB_UP(elm, field))
-#define RB_LEFT(elm, field) _RB_LINK(elm, _RB_L, field)
-#define RB_RIGHT(elm, field) _RB_LINK(elm, _RB_R, field)
+#define RB_LEFT(elm, field) _RB_LINK(elm, _RB_L-1, field)
+#define RB_RIGHT(elm, field) _RB_LINK(elm, _RB_R-1, field)
#define RB_ROOT(head) (head)->rbh_root
#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
@@ -398,10 +398,10 @@ struct { \
* update the same pair of pointer fields with distinct values.
*/
#define RB_ROTATE(elm, tmp, dir, field) do { \
- if ((_RB_LINK(elm, dir ^ _RB_LR, field) = \
- _RB_LINK(tmp, dir, field)) != NULL) \
- RB_SET_PARENT(_RB_LINK(tmp, dir, field), elm, field); \
- _RB_LINK(tmp, dir, field) = (elm); \
+ if ((_RB_LINK(elm, (dir ^ _RB_LR)-1, field) = \
+ _RB_LINK(tmp, dir-1, field)) != NULL) \
+ RB_SET_PARENT(_RB_LINK(tmp, dir-1, field), elm, field); \
+ _RB_LINK(tmp, dir-1, field) = (elm); \
RB_SET_PARENT(elm, tmp, field); \
} while (/*CONSTCOND*/ 0)
@@ -412,6 +412,7 @@ struct { \
RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
RB_PROTOTYPE_RANK(name, type, attr) \
+ RB_PROTOTYPE_DO_INSERT_COLOR(name, type, attr); \
RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
RB_PROTOTYPE_INSERT_FINISH(name, type, attr); \
@@ -431,9 +432,11 @@ struct { \
#else
#define RB_PROTOTYPE_RANK(name, type, attr)
#endif
-#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
- attr struct type *name##_RB_INSERT_COLOR(struct name *, \
+#define RB_PROTOTYPE_DO_INSERT_COLOR(name, type, attr) \
+ attr struct type *name##_RB_DO_INSERT_COLOR(struct name *, \
struct type *, struct type *)
+#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
+ attr struct type *name##_RB_INSERT_COLOR(struct name *, struct type *)
#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
attr struct type *name##_RB_REMOVE_COLOR(struct name *, \
struct type *, struct type *)
@@ -472,6 +475,7 @@ struct { \
RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
RB_GENERATE_RANK(name, type, field, attr) \
+ RB_GENERATE_DO_INSERT_COLOR(name, type, field, attr) \
RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
RB_GENERATE_INSERT_FINISH(name, type, field, attr) \
@@ -522,9 +526,9 @@ name##_RB_RANK(struct type *elm) \
#define RB_GENERATE_RANK(name, type, field, attr)
#endif
-#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
+#define RB_GENERATE_DO_INSERT_COLOR(name, type, field, attr) \
attr struct type * \
-name##_RB_INSERT_COLOR(struct name *head, \
+name##_RB_DO_INSERT_COLOR(struct name *head, \
struct type *parent, struct type *elm) \
{ \
/* \
@@ -625,6 +629,20 @@ name##_RB_INSERT_COLOR(struct name *head, \
return (NULL); \
}
+#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
+attr struct type * \
+name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
+{ \
+ struct type *parent, *tmp; \
+ \
+ parent = RB_PARENT(elm, field); \
+ if (parent != NULL) \
+ tmp = name##_RB_DO_INSERT_COLOR(head, parent, elm); \
+ else \
+ tmp = NULL; \
+ return (tmp); \
+}
+
#ifndef RB_STRICT_HST
/*
* In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has
@@ -671,7 +689,7 @@ name##_RB_REMOVE_COLOR(struct name *head, \
continue; \
} \
sibdir = elmdir ^ _RB_LR; \
- sib = _RB_LINK(parent, sibdir, field); \
+ sib = _RB_LINK(parent, sibdir-1, field); \
up = _RB_UP(sib, field); \
_RB_BITS(up) ^= _RB_LR; \
if ((_RB_BITS(up) & _RB_LR) == 0) { \
@@ -700,7 +718,7 @@ name##_RB_REMOVE_COLOR(struct name *head, \
* / z \
* y \
*/ \
- elm = _RB_LINK(sib, elmdir, field); \
+ elm = _RB_LINK(sib, elmdir-1, field); \
/* elm is a 1-child. First rotate at elm. */ \
RB_ROTATE(sib, elm, sibdir, field); \
up = _RB_UP(elm, field); \
@@ -826,7 +844,7 @@ name##_RB_INSERT_FINISH(struct name *head, struct type *parent, \
RB_SET(elm, parent, field); \
*pptr = elm; \
if (parent != NULL) \
- tmp = name##_RB_INSERT_COLOR(head, parent, elm); \
+ tmp = name##_RB_DO_INSERT_COLOR(head, parent, elm); \
_RB_AUGMENT_WALK(elm, tmp, field); \
if (tmp != NULL) \
/* \