[PATCH] backports: add rb_tree_cached

[PATCH] backports: add rb_tree_cached

[Johannes Berg]

From: Johannes Berg <johannes.berg@intel.com>

We just map them to the normal rb_tree, losing the efficiency
gain in this case.

ticket=none

Signed-off-by: Johannes Berg <johannes.berg@intel.com>
---
 backport/backport-include/linux/rbtree.h | 25 ++++++++++++++++++++++++
 patches/0104-rb-tree-cached.cocci        |  5 +++++
 2 files changed, 30 insertions(+)
 create mode 100644 backport/backport-include/linux/rbtree.h
 create mode 100644 patches/0104-rb-tree-cached.cocci

diff --git a/backport/backport-include/linux/rbtree.h b/backport/backport-include/linux/rbtree.h
new file mode 100644
index 000000000000..feccff36e7dd
--- /dev/null
+++ b/backport/backport-include/linux/rbtree.h
@@ -0,0 +1,25 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+/*
+ * Copyright (C) 2021 Intel Corporation
+ */
+#ifndef __BACKPORT_RBTREE_H
+#define __BACKPORT_RBTREE_H
+#include_next <linux/rbtree.h>
+
+#if LINUX_VERSION_IS_LESS(4,14,0)
+#define rb_root_cached rb_root
+#define rb_first_cached rb_first
+static inline void rb_insert_color_cached(struct rb_node *node,
+					  struct rb_root_cached *root,
+					  bool leftmost)
+{
+	rb_insert_color(node, root);
+}
+#define rb_erase_cached rb_erase
+#define RB_ROOT_CACHED RB_ROOT
+#define rb_root_node(root) (root)->rb_node
+#else
+#define rb_root_node(root) (root)->rb_root.rb_node
+#endif
+
+#endif /* __BACKPORT_RBTREE_H */
diff --git a/patches/0104-rb-tree-cached.cocci b/patches/0104-rb-tree-cached.cocci
new file mode 100644
index 000000000000..a8388c847a5a
--- /dev/null
+++ b/patches/0104-rb-tree-cached.cocci
@@ -0,0 +1,5 @@
+@@
+struct rb_root_cached *root;
+@@
+-root->rb_root.rb_node
++rb_root_node(root)
-- 
2.31.1

--
To unsubscribe from this list: send the line "unsubscribe backports" in

Re: [PATCH] backports: add rb_tree_cached

[Hauke Mehrtens]

On 7/15/21 6:00 PM, Johannes Berg wrote:
> From: Johannes Berg <johannes.berg@intel.com>
> 
> We just map them to the normal rb_tree, losing the efficiency
> gain in this case.
> 
> ticket=none
> 
> Signed-off-by: Johannes Berg <johannes.berg@intel.com>

I had a look at this too and the cached optimization seams to be 
completely in the header file now, initially the in kernel rb lib code 
was changed too.

Sine this commit we should be able to fully backport this easily:
https://git.kernel.org/linus/9f973cb38088e0cf42e0bae97ff140813e623f13

Hauke

> ---
>   backport/backport-include/linux/rbtree.h | 25 ++++++++++++++++++++++++
>   patches/0104-rb-tree-cached.cocci        |  5 +++++
>   2 files changed, 30 insertions(+)
>   create mode 100644 backport/backport-include/linux/rbtree.h
>   create mode 100644 patches/0104-rb-tree-cached.cocci
> 
> diff --git a/backport/backport-include/linux/rbtree.h b/backport/backport-include/linux/rbtree.h
> new file mode 100644
> index 000000000000..feccff36e7dd
> --- /dev/null
> +++ b/backport/backport-include/linux/rbtree.h
> @@ -0,0 +1,25 @@
> +/* SPDX-License-Identifier: GPL-2.0-only */
> +/*
> + * Copyright (C) 2021 Intel Corporation
> + */
> +#ifndef __BACKPORT_RBTREE_H
> +#define __BACKPORT_RBTREE_H
> +#include_next <linux/rbtree.h>
> +
> +#if LINUX_VERSION_IS_LESS(4,14,0)
> +#define rb_root_cached rb_root
> +#define rb_first_cached rb_first
> +static inline void rb_insert_color_cached(struct rb_node *node,
> +					  struct rb_root_cached *root,
> +					  bool leftmost)
> +{
> +	rb_insert_color(node, root);
> +}
> +#define rb_erase_cached rb_erase
> +#define RB_ROOT_CACHED RB_ROOT
> +#define rb_root_node(root) (root)->rb_node
> +#else
> +#define rb_root_node(root) (root)->rb_root.rb_node
> +#endif
> +
> +#endif /* __BACKPORT_RBTREE_H */
> diff --git a/patches/0104-rb-tree-cached.cocci b/patches/0104-rb-tree-cached.cocci
> new file mode 100644
> index 000000000000..a8388c847a5a
> --- /dev/null
> +++ b/patches/0104-rb-tree-cached.cocci
> @@ -0,0 +1,5 @@
> +@@
> +struct rb_root_cached *root;
> +@@
> +-root->rb_root.rb_node
> ++rb_root_node(root)
> 

--
To unsubscribe from this list: send the line "unsubscribe backports" in

Re: [PATCH] backports: add rb_tree_cached

[Johannes Berg]

On 16 October 2021 14:06:42 CEST, Hauke Mehrtens <hauke@hauke-m.de> wrote:
>On 7/15/21 6:00 PM, Johannes Berg wrote:
>> From: Johannes Berg <johannes.berg@intel.com>
>> 
>> We just map them to the normal rb_tree, losing the efficiency
>> gain in this case.
>> 
>> ticket=none
>> 
>> Signed-off-by: Johannes Berg <johannes.berg@intel.com>
>
>I had a look at this too and the cached optimization seams to be 
>completely in the header file now, initially the in kernel rb lib code 
>was changed too.
>
>Sine this commit we should be able to fully backport this easily:
>https://git.kernel.org/linus/9f973cb38088e0cf42e0bae97ff140813e623f13
>

I guess I could've always done it that way, just didn't bother as it didn't seem so important, at least not to iwlwifi.

johannes 
-- 
Sent from my phone.
--
To unsubscribe from this list: send the line "unsubscribe backports" in