From: Hauke Mehrtens <hauke@hauke-m.de>
To: Johannes Berg <johannes@sipsolutions.net>, backports@vger.kernel.org
Cc: Johannes Berg <johannes.berg@intel.com>
Subject: Re: [PATCH] backports: add rb_tree_cached
Date: Sat, 16 Oct 2021 14:06:42 +0200 [thread overview]
Message-ID: <72a11f8f-66d4-4410-854d-1988f97b3d49@hauke-m.de> (raw)
In-Reply-To: <20210715180046.6635727a182b.Id747625a81c1c87ae14145eff93436b94a122980@changeid>
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
next prev parent reply other threads:[~2021-10-16 12:06 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-07-15 16:00 [PATCH] backports: add rb_tree_cached Johannes Berg
2021-10-16 12:06 ` Hauke Mehrtens [this message]
2021-10-16 12:11 ` Johannes Berg
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=72a11f8f-66d4-4410-854d-1988f97b3d49@hauke-m.de \
--to=hauke@hauke-m.de \
--cc=backports@vger.kernel.org \
--cc=johannes.berg@intel.com \
--cc=johannes@sipsolutions.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).