From: Matthew Wilcox <willy@infradead.org> To: linux-fsdevel@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Cc: Matthew Wilcox <mawilcox@microsoft.com> Subject: [PATCH 19/62] xarray: Define struct xa_node Date: Wed, 22 Nov 2017 13:06:56 -0800 [thread overview] Message-ID: <20171122210739.29916-20-willy@infradead.org> (raw) In-Reply-To: <20171122210739.29916-1-willy@infradead.org> From: Matthew Wilcox <mawilcox@microsoft.com> This is a direct replacement for struct radix_tree_node. Use a #define so that radix tree users continue to work without change. Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com> --- include/linux/radix-tree.h | 29 +++-------------------------- include/linux/xarray.h | 24 ++++++++++++++++++++++++ 2 files changed, 27 insertions(+), 26 deletions(-) diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 015bc1bdc3d2..1da1fb01e993 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -32,6 +32,7 @@ /* Keep unconverted code working */ #define radix_tree_root xarray +#define radix_tree_node xa_node /* * The bottom two bits of the slot determine how the remaining bits in the @@ -60,41 +61,17 @@ static inline bool radix_tree_is_internal_node(void *ptr) /*** radix-tree API starts here ***/ -#define RADIX_TREE_MAX_TAGS 3 - #define RADIX_TREE_MAP_SHIFT XA_CHUNK_SHIFT #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) -#define RADIX_TREE_TAG_LONGS \ - ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) +#define RADIX_TREE_MAX_TAGS XA_MAX_TAGS +#define RADIX_TREE_TAG_LONGS XA_TAG_LONGS #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \ RADIX_TREE_MAP_SHIFT)) -/* - * @count is the count of every non-NULL element in the ->slots array - * whether that is a data entry, a retry entry, a user pointer, - * a sibling entry or a pointer to the next level of the tree. - * @exceptional is the count of every element in ->slots which is - * either a data entry or a sibling entry for data. - */ -struct radix_tree_node { - unsigned char shift; /* Bits remaining in each slot */ - unsigned char offset; /* Slot offset in parent */ - unsigned char count; /* Total entry count */ - unsigned char exceptional; /* Exceptional entry count */ - struct radix_tree_node *parent; /* Used when ascending tree */ - struct radix_tree_root *root; /* The tree we belong to */ - union { - struct list_head private_list; /* For tree user */ - struct rcu_head rcu_head; /* Used when freeing node */ - }; - void __rcu *slots[RADIX_TREE_MAP_SIZE]; - unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; -}; - /* The top bits of xa_flags are used to store the root tags and the IDR flag */ #define ROOT_IS_IDR ((__force gfp_t)(1 << __GFP_BITS_SHIFT)) #define ROOT_TAG_SHIFT (__GFP_BITS_SHIFT + 1) diff --git a/include/linux/xarray.h b/include/linux/xarray.h index 03d430ec3bce..1513a9e85580 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -143,6 +143,30 @@ static inline bool xa_is_value(void *entry) #endif #define XA_CHUNK_SIZE (1UL << XA_CHUNK_SHIFT) #define XA_CHUNK_MASK (XA_CHUNK_SIZE - 1) +#define XA_MAX_TAGS 3 +#define XA_TAG_LONGS DIV_ROUND_UP(XA_CHUNK_SIZE, BITS_PER_LONG) + +/* + * @count is the count of every non-NULL element in the ->slots array + * whether that is a data entry, a retry entry, a user pointer, + * a sibling entry or a pointer to the next level of the tree. + * @exceptional is the count of every element in ->slots which is + * either a data entry or a sibling entry for data. + */ +struct xa_node { + unsigned char shift; /* Bits remaining in each slot */ + unsigned char offset; /* Slot offset in parent */ + unsigned char count; /* Total entry count */ + unsigned char exceptional; /* Exceptional entry count */ + struct xa_node *parent; /* Used when ascending tree */ + struct xarray * root; /* The tree we belong to */ + union { + struct list_head private_list; /* For tree user */ + struct rcu_head rcu_head; /* Used when freeing node */ + }; + void __rcu *slots[XA_CHUNK_SIZE]; + unsigned long tags[XA_MAX_TAGS][XA_TAG_LONGS]; +}; /* * Internal entries have the bottom two bits set to the value 10b. Most -- 2.15.0
WARNING: multiple messages have this Message-ID (diff)
From: Matthew Wilcox <willy@infradead.org> To: linux-fsdevel@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Cc: Matthew Wilcox <mawilcox@microsoft.com> Subject: [PATCH 19/62] xarray: Define struct xa_node Date: Wed, 22 Nov 2017 13:06:56 -0800 [thread overview] Message-ID: <20171122210739.29916-20-willy@infradead.org> (raw) In-Reply-To: <20171122210739.29916-1-willy@infradead.org> From: Matthew Wilcox <mawilcox@microsoft.com> This is a direct replacement for struct radix_tree_node. Use a #define so that radix tree users continue to work without change. Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com> --- include/linux/radix-tree.h | 29 +++-------------------------- include/linux/xarray.h | 24 ++++++++++++++++++++++++ 2 files changed, 27 insertions(+), 26 deletions(-) diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 015bc1bdc3d2..1da1fb01e993 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -32,6 +32,7 @@ /* Keep unconverted code working */ #define radix_tree_root xarray +#define radix_tree_node xa_node /* * The bottom two bits of the slot determine how the remaining bits in the @@ -60,41 +61,17 @@ static inline bool radix_tree_is_internal_node(void *ptr) /*** radix-tree API starts here ***/ -#define RADIX_TREE_MAX_TAGS 3 - #define RADIX_TREE_MAP_SHIFT XA_CHUNK_SHIFT #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) -#define RADIX_TREE_TAG_LONGS \ - ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) +#define RADIX_TREE_MAX_TAGS XA_MAX_TAGS +#define RADIX_TREE_TAG_LONGS XA_TAG_LONGS #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \ RADIX_TREE_MAP_SHIFT)) -/* - * @count is the count of every non-NULL element in the ->slots array - * whether that is a data entry, a retry entry, a user pointer, - * a sibling entry or a pointer to the next level of the tree. - * @exceptional is the count of every element in ->slots which is - * either a data entry or a sibling entry for data. - */ -struct radix_tree_node { - unsigned char shift; /* Bits remaining in each slot */ - unsigned char offset; /* Slot offset in parent */ - unsigned char count; /* Total entry count */ - unsigned char exceptional; /* Exceptional entry count */ - struct radix_tree_node *parent; /* Used when ascending tree */ - struct radix_tree_root *root; /* The tree we belong to */ - union { - struct list_head private_list; /* For tree user */ - struct rcu_head rcu_head; /* Used when freeing node */ - }; - void __rcu *slots[RADIX_TREE_MAP_SIZE]; - unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; -}; - /* The top bits of xa_flags are used to store the root tags and the IDR flag */ #define ROOT_IS_IDR ((__force gfp_t)(1 << __GFP_BITS_SHIFT)) #define ROOT_TAG_SHIFT (__GFP_BITS_SHIFT + 1) diff --git a/include/linux/xarray.h b/include/linux/xarray.h index 03d430ec3bce..1513a9e85580 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -143,6 +143,30 @@ static inline bool xa_is_value(void *entry) #endif #define XA_CHUNK_SIZE (1UL << XA_CHUNK_SHIFT) #define XA_CHUNK_MASK (XA_CHUNK_SIZE - 1) +#define XA_MAX_TAGS 3 +#define XA_TAG_LONGS DIV_ROUND_UP(XA_CHUNK_SIZE, BITS_PER_LONG) + +/* + * @count is the count of every non-NULL element in the ->slots array + * whether that is a data entry, a retry entry, a user pointer, + * a sibling entry or a pointer to the next level of the tree. + * @exceptional is the count of every element in ->slots which is + * either a data entry or a sibling entry for data. + */ +struct xa_node { + unsigned char shift; /* Bits remaining in each slot */ + unsigned char offset; /* Slot offset in parent */ + unsigned char count; /* Total entry count */ + unsigned char exceptional; /* Exceptional entry count */ + struct xa_node *parent; /* Used when ascending tree */ + struct xarray * root; /* The tree we belong to */ + union { + struct list_head private_list; /* For tree user */ + struct rcu_head rcu_head; /* Used when freeing node */ + }; + void __rcu *slots[XA_CHUNK_SIZE]; + unsigned long tags[XA_MAX_TAGS][XA_TAG_LONGS]; +}; /* * Internal entries have the bottom two bits set to the value 10b. Most -- 2.15.0 -- 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:[~2017-11-22 21:22 UTC|newest] Thread overview: 159+ messages / expand[flat|nested] mbox.gz Atom feed top 2017-11-22 21:06 [PATCH 00/62] XArray November 2017 Edition Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 01/62] tools: Make __test_and_clear_bit available Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 02/62] radix tree test suite: Remove ARRAY_SIZE Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 03/62] radix tree test suite: Check reclaim bit Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 04/62] idr test suite: Fix ida_test_random() Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 05/62] radix tree: Add a missing cast to gfp_t Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:28 ` Luc Van Oostenryck 2017-11-22 21:28 ` Luc Van Oostenryck 2017-11-22 22:24 ` Matthew Wilcox 2017-11-22 22:24 ` Matthew Wilcox 2017-11-22 22:35 ` Luc Van Oostenryck 2017-11-22 22:35 ` Luc Van Oostenryck 2017-11-22 21:06 ` [PATCH 06/62] idr: Make cursor explicit for cyclic allocation Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 07/62] idr: Rewrite extended IDR API Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 08/62] Explicitly include radix-tree.h Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 09/62] arm64: Turn flush_dcache_mmap_lock into a no-op Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 10/62] unicore32: " Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 11/62] Export __set_page_dirty Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 12/62] xfs: Rename xa_ elements to ail_ Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 13/62] fscache: Use appropriate radix tree accessors Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 14/62] xarray: Add the xa_lock to the radix_tree_root Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 15/62] page cache: Use xa_lock Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 16/62] xarray: Replace exceptional entries Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 17/62] xarray: Change definition of sibling entries Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 18/62] xarray: Add definition of struct xarray Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox [this message] 2017-11-22 21:06 ` [PATCH 19/62] xarray: Define struct xa_node Matthew Wilcox 2017-11-22 21:06 ` [PATCH 20/62] xarray: Add xa_load Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 21/62] xarray: Add xa_get_tag, xa_set_tag and xa_clear_tag Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:06 ` [PATCH 22/62] xarray: Add xa_store Matthew Wilcox 2017-11-22 21:06 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 23/62] xarray: Add xa_cmpxchg Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 24/62] xarray: Add xa_for_each Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 25/62] xarray: Add xa_init Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 26/62] xarray: Add xas_for_each_tag Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 27/62] xarray: Add xa_get_entries and xa_get_tagged Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 28/62] xarray: Add xa_destroy Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 29/62] xarray: Add xas_prev_any Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 30/62] xarray: Add xas_find_any / xas_next_any Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 31/62] Convert IDR to use xarray Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 32/62] ida: Convert to using xarray Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 33/62] page cache: Convert page_cache_next_hole to XArray Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 34/62] page cache: Use xarray for adding pages Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 35/62] page cache: Convert page_cache_tree_delete to xarray Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 36/62] page cache: Convert find_get_entry " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 37/62] shmem: Convert replace " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 38/62] shmem: Convert shmem_confirm_swap to XArray Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 39/62] shmem: Convert find_swap_entry " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 40/62] shmem: Convert shmem_tag_pins " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 41/62] shmem: Convert shmem_wait_for_pins " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 42/62] vmalloc: Convert to xarray Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 43/62] brd: Convert to XArray Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 44/62] xfs: Convert m_perag_tree " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 45/62] xfs: Convert pag_ici_root " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 46/62] xfs: Convert xfs dquot " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 47/62] xfs: Convert mru cache " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 48/62] block: Remove IDR preloading Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 49/62] rxrpc: " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 50/62] cgroup: Remove IDR wrappers Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 51/62] dca: Remove idr_preload calls Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 52/62] ipc: Remove call to idr_preload Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 53/62] irq: " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 54/62] scsi: Remove idr_preload in st driver Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 55/62] firewire: Remove call to idr_preload Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 56/62] drm: Remove drm_minor_lock and idr_preload Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 57/62] drm: Remove drm_syncobj_fd_to_handle Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 58/62] drm: Remove qxl driver IDR locks Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 59/62] drm: Replace virtio IDRs with IDAs Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 60/62] drm: Replace vmwgfx " Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 61/62] net: Redesign act_api use of IDR Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-22 21:07 ` [PATCH 62/62] mm: Convert page-writeback to XArray Matthew Wilcox 2017-11-22 21:07 ` Matthew Wilcox 2017-11-23 1:25 ` [PATCH 00/62] XArray November 2017 Edition Dave Chinner 2017-11-23 1:25 ` Dave Chinner 2017-11-23 2:46 ` Matthew Wilcox 2017-11-23 2:46 ` Matthew Wilcox 2017-11-24 1:16 ` XArray documentation Matthew Wilcox 2017-11-24 1:16 ` Matthew Wilcox 2017-11-24 4:30 ` Andreas Dilger 2017-11-24 17:17 ` Matthew Wilcox 2017-11-24 17:17 ` Matthew Wilcox 2017-11-24 16:50 ` Martin Steigerwald 2017-11-24 16:50 ` Martin Steigerwald 2017-11-24 17:03 ` Matthew Wilcox 2017-11-24 17:03 ` Matthew Wilcox 2017-11-24 17:03 ` Matthew Wilcox 2017-11-24 18:01 ` Martin Steigerwald 2017-11-24 18:01 ` Martin Steigerwald 2017-11-24 19:48 ` Shakeel Butt 2017-11-24 19:48 ` Shakeel Butt 2017-11-24 19:56 ` Matthew Wilcox 2017-11-24 19:56 ` Matthew Wilcox 2017-11-24 21:18 ` Matthew Wilcox 2017-11-24 21:18 ` Matthew Wilcox 2017-11-24 21:18 ` Matthew Wilcox 2017-11-24 22:02 ` Martin Steigerwald 2017-11-24 22:02 ` Martin Steigerwald 2017-11-24 22:08 ` Matthew Wilcox 2017-11-24 22:08 ` Matthew Wilcox
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=20171122210739.29916-20-willy@infradead.org \ --to=willy@infradead.org \ --cc=linux-fsdevel@vger.kernel.org \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=mawilcox@microsoft.com \ /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: linkBe 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.