The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=d8a88ec381498f5942403088d28ee325b92e9a78
commit d8a88ec381498f5942403088d28ee325b92e9a78 Author: Doug Moore <[email protected]> AuthorDate: 2022-12-16 09:15:28 +0000 Commit: Doug Moore <[email protected]> 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) \ /* \
