[PATCH 14/29] radix-tree: Move rcu_head into a union with private_list

All of lore.kernel.org
 help / color / mirror / Atom feed

From: Matthew Wilcox <mawilcox@linuxonhyperv.com>
To: linux-kernel@vger.kernel.org,
	Andrew Morton <akpm@linux-foundation.org>,
	Konstantin Khlebnikov <koct9i@gmail.com>,
	Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: linux-fsdevel@vger.kernel.org,
	Matthew Wilcox <willy@infradead.org>,
	linux-mm@kvack.org,
	"Kirill A . Shutemov" <kirill.shutemov@linux.intel.com>
Subject: [PATCH 14/29] radix-tree: Move rcu_head into a union with private_list
Date: Wed, 16 Nov 2016 16:17:17 -0800	[thread overview]
Message-ID: <1479341856-30320-53-git-send-email-mawilcox@linuxonhyperv.com> (raw)
In-Reply-To: <1479341856-30320-1-git-send-email-mawilcox@linuxonhyperv.com>

From: Matthew Wilcox <willy@infradead.org>

I want to be able to reference node->parent after freeing node.
Currently node->parent is in a union with rcu_head, so it is overwritten
when the node is put on the RCU list.  We know that private_list is not
referenced after the node is freed, so it is safe for these two members
to share space.

Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
 include/linux/radix-tree.h | 14 ++++----------
 lib/radix-tree.c           |  1 +
 2 files changed, 5 insertions(+), 10 deletions(-)

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 8ffb051..66fb8c0 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -88,18 +88,12 @@ struct radix_tree_node {
 	unsigned char	shift;	/* Bits remaining in each slot */
 	unsigned char	offset;	/* Slot offset in parent */
 	unsigned int	count;
+	struct radix_tree_node *parent;		/* Used when ascending tree */
+	void *private_data;			/* For tree user */
 	union {
-		struct {
-			/* Used when ascending tree */
-			struct radix_tree_node *parent;
-			/* For tree user */
-			void *private_data;
-		};
-		/* Used when freeing node */
-		struct rcu_head	rcu_head;
+		struct list_head private_list;	/* For tree user */
+		struct rcu_head	rcu_head;	/* Used when freeing node */
 	};
-	/* For tree user */
-	struct list_head private_list;
 	void __rcu	*slots[RADIX_TREE_MAP_SIZE];
 	unsigned long	tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
 };
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index e917c56..baf4ba1 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -325,6 +325,7 @@ static void radix_tree_node_rcu_free(struct rcu_head *head)
 	 */
 	memset(node->slots, 0, sizeof(node->slots));
 	memset(node->tags, 0, sizeof(node->tags));
+	INIT_LIST_HEAD(&node->private_list);
 
 	kmem_cache_free(radix_tree_node_cachep, node);
 }
-- 
2.10.2

WARNING: multiple messages have this Message-ID (diff)

From: Matthew Wilcox <mawilcox@linuxonhyperv.com>
To: linux-kernel@vger.kernel.org,
	Andrew Morton <akpm@linux-foundation.org>,
	Konstantin Khlebnikov <koct9i@gmail.com>,
	Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: linux-fsdevel@vger.kernel.org,
	Matthew Wilcox <willy@infradead.org>,
	linux-mm@kvack.org,
	"Kirill A . Shutemov" <kirill.shutemov@linux.intel.com>
Subject: [PATCH 14/29] radix-tree: Move rcu_head into a union with private_list
Date: Wed, 16 Nov 2016 16:17:17 -0800	[thread overview]
Message-ID: <1479341856-30320-53-git-send-email-mawilcox@linuxonhyperv.com> (raw)
In-Reply-To: <1479341856-30320-1-git-send-email-mawilcox@linuxonhyperv.com>

From: Matthew Wilcox <willy@infradead.org>

I want to be able to reference node->parent after freeing node.
Currently node->parent is in a union with rcu_head, so it is overwritten
when the node is put on the RCU list.  We know that private_list is not
referenced after the node is freed, so it is safe for these two members
to share space.

Signed-off-by: Matthew Wilcox <willy@infradead.org>
---
 include/linux/radix-tree.h | 14 ++++----------
 lib/radix-tree.c           |  1 +
 2 files changed, 5 insertions(+), 10 deletions(-)

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 8ffb051..66fb8c0 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -88,18 +88,12 @@ struct radix_tree_node {
 	unsigned char	shift;	/* Bits remaining in each slot */
 	unsigned char	offset;	/* Slot offset in parent */
 	unsigned int	count;
+	struct radix_tree_node *parent;		/* Used when ascending tree */
+	void *private_data;			/* For tree user */
 	union {
-		struct {
-			/* Used when ascending tree */
-			struct radix_tree_node *parent;
-			/* For tree user */
-			void *private_data;
-		};
-		/* Used when freeing node */
-		struct rcu_head	rcu_head;
+		struct list_head private_list;	/* For tree user */
+		struct rcu_head	rcu_head;	/* Used when freeing node */
 	};
-	/* For tree user */
-	struct list_head private_list;
 	void __rcu	*slots[RADIX_TREE_MAP_SIZE];
 	unsigned long	tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
 };
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index e917c56..baf4ba1 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -325,6 +325,7 @@ static void radix_tree_node_rcu_free(struct rcu_head *head)
 	 */
 	memset(node->slots, 0, sizeof(node->slots));
 	memset(node->tags, 0, sizeof(node->tags));
+	INIT_LIST_HEAD(&node->private_list);
 
 	kmem_cache_free(radix_tree_node_cachep, node);
 }
-- 
2.10.2

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

next prev parent reply	other threads:[~2016-11-16 22:27 UTC|newest]

Thread overview: 152+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-11-17  0:16 [PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox
2016-11-17  0:16 ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 01/29] tools: Add WARN_ON_ONCE Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 03/29] radix tree test suite: Track preempt_count Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 04/29] radix tree test suite: Free preallocated nodes Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 05/29] radix tree test suite: Make runs more reproducible Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 06/28] Add benchmark Matthew Wilcox
2016-11-17  0:16 ` [PATCH 06/29] radix tree test suite: benchmark for iterator Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 07/29] radix tree test suite: Use rcu_barrier Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 07/28] test suite: Switch to rcu_barrier from sleep Matthew Wilcox
2016-11-17  0:16 ` [PATCH 08/29] tools: Add more bitmap functions Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 09/29] radix tree test suite: Use common find-bit code Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 10/29] radix-tree: Add radix_tree_join Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 11/29] radix-tree: Add radix_tree_split Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 12/29] radix-tree: Add radix_tree_split_preload() Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 13/29] radix-tree: Fix typo Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 14/29] radix-tree: Move rcu_head into a union with private_list Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 15/29] radix-tree: Create node_tag_set() Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 17/29] radix-tree: Improve dump output Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 18/29] btrfs: Fix race in btrfs_free_dummy_fs_info() Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 19/29] radix tree test suite: iteration test misuses RCU Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 22/29] radix-tree: Delete radix_tree_range_tag_if_tagged() Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 23/29] idr: Add ida_is_empty Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-18 11:56   ` Konstantin Khlebnikov
2016-11-18 11:56     ` Konstantin Khlebnikov
2016-11-17  0:16 ` [PATCH 24/29] tpm: Use idr_find(), not idr_find_slowpath() Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 25/28] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox
2016-11-17  0:16 ` [PATCH 25/29] rxrpc: Abstract away knowledge of IDR internals Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 26/28] radix tree test suite: Add some more functionality Matthew Wilcox
2016-11-17  0:16 ` [PATCH 27/28] radix-tree: Create all_tag_set Matthew Wilcox
2016-11-17  0:16 ` [PATCH 27/29] radix tree test suite: Add some more functionality Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:16 ` [PATCH 28/28] Reimplement IDR and IDA using the radix tree Matthew Wilcox
2016-11-17  0:16 ` [PATCH 28/29] radix-tree: Create all_tag_set Matthew Wilcox
2016-11-17  0:16   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 29/29] Reimplement IDR and IDA using the radix tree Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 00/29] Improve radix tree for 4.10 Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17 19:38   ` Matthew Wilcox
2016-11-17 19:38     ` Matthew Wilcox
2016-11-17 22:17   ` Ross Zwisler
2016-11-17 22:17     ` Ross Zwisler
2016-11-18  4:24     ` Matthew Wilcox
2016-11-18  4:24       ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 01/29] tools: Add WARN_ON_ONCE Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 02/29] radix tree test suite: Allow GFP_ATOMIC allocations to fail Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 03/29] radix tree test suite: Track preempt_count Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 04/29] radix tree test suite: Free preallocated nodes Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 05/29] radix tree test suite: Make runs more reproducible Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 06/28] Add benchmark Matthew Wilcox
2016-11-17  0:17 ` [PATCH 06/29] radix tree test suite: benchmark for iterator Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 07/29] radix tree test suite: Use rcu_barrier Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 07/28] test suite: Switch to rcu_barrier from sleep Matthew Wilcox
2016-11-17  0:17 ` [PATCH 08/29] tools: Add more bitmap functions Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 09/29] radix tree test suite: Use common find-bit code Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 10/29] radix-tree: Add radix_tree_join Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 11/29] radix-tree: Add radix_tree_split Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 12/29] radix-tree: Add radix_tree_split_preload() Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 13/29] radix-tree: Fix typo Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` Matthew Wilcox [this message]
2016-11-17  0:17   ` [PATCH 14/29] radix-tree: Move rcu_head into a union with private_list Matthew Wilcox
2016-11-17  0:17 ` [PATCH 15/29] radix-tree: Create node_tag_set() Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 16/29] radix-tree: Make radix_tree_find_next_bit more useful Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 17/29] radix-tree: Improve dump output Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 18/29] btrfs: Fix race in btrfs_free_dummy_fs_info() Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 19/29] radix tree test suite: iteration test misuses RCU Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 20/29] radix tree: Improve multiorder iterators Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-18 11:47   ` Konstantin Khlebnikov
2016-11-18 11:47     ` Konstantin Khlebnikov
2016-11-18 16:31     ` Matthew Wilcox
2016-11-18 16:31       ` Matthew Wilcox
2016-11-18 17:56       ` Konstantin Khlebnikov
2016-11-18 17:56         ` Konstantin Khlebnikov
2016-11-18 20:23         ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 21/29] radix-tree: Delete radix_tree_locate_item() Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-18 11:50   ` Konstantin Khlebnikov
2016-11-18 11:50     ` Konstantin Khlebnikov
2016-11-18 16:34     ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 22/29] radix-tree: Delete radix_tree_range_tag_if_tagged() Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 23/29] idr: Add ida_is_empty Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 24/29] tpm: Use idr_find(), not idr_find_slowpath() Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 25/28] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox
2016-11-17  0:17 ` [PATCH 25/29] rxrpc: Abstract away knowledge of IDR internals Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 26/29] idr: Reduce the number of bits per level from 8 to 6 Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 26/28] radix tree test suite: Add some more functionality Matthew Wilcox
2016-11-17  0:17 ` [PATCH 27/28] radix-tree: Create all_tag_set Matthew Wilcox
2016-11-17  0:17 ` [PATCH 27/29] radix tree test suite: Add some more functionality Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 28/28] Reimplement IDR and IDA using the radix tree Matthew Wilcox
2016-11-18 11:52   ` Konstantin Khlebnikov
2016-11-18 13:43     ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 28/29] radix-tree: Create all_tag_set Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox
2016-11-17  0:17 ` [PATCH 29/29] Reimplement IDR and IDA using the radix tree Matthew Wilcox
2016-11-17  0:17   ` Matthew Wilcox

find likely ancestor, descendant, or conflicting patches for this message:
dfblob:8ffb051 dfblob:e917c56 dfblob:8ffb051 dfblob:e917c56
dfblob:66fb8c0 dfblob:baf4ba1 dfblob:66fb8c0 dfblob:baf4ba1
	(help)

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=1479341856-30320-53-git-send-email-mawilcox@linuxonhyperv.com \
    --to=mawilcox@linuxonhyperv.com \
    --cc=akpm@linux-foundation.org \
    --cc=kirill.shutemov@linux.intel.com \
    --cc=koct9i@gmail.com \
    --cc=linux-fsdevel@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=ross.zwisler@linux.intel.com \
    --cc=willy@infradead.org \
    /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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.