diff mbox series

[1/3] maple_tree: introduce mas_prealloc_calc()

Message ID 20231009201639.920512-2-sidhartha.kumar@oracle.com
State New
Headers
Series align maple tree write paths |

Commit Message

Sidhartha Kumar Oct. 9, 2023, 8:16 p.m. UTC 
  Abstract the calculation used to determine the number of nodes needed for
a store operation into a separate function: mas_prealloc_calc().

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 85 ++++++++++++++++++++++++++++--------------------
 1 file changed, 50 insertions(+), 35 deletions(-)

Comments

kernel test robot Oct. 9, 2023, 10:25 p.m. UTC | #1 
Hi Sidhartha,

kernel test robot noticed the following build warnings:

[auto build test WARNING on akpm-mm/mm-everything]
[also build test WARNING on linus/master v6.6-rc5 next-20231009]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Sidhartha-Kumar/maple_tree-introduce-mas_prealloc_calc/20231010-041859
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-everything
patch link:    https://lore.kernel.org/r/20231009201639.920512-2-sidhartha.kumar%40oracle.com
patch subject: [PATCH 1/3] maple_tree: introduce mas_prealloc_calc()
config: m68k-allyesconfig (https://download.01.org/0day-ci/archive/20231010/202310100603.qsn3ruBx-lkp@intel.com/config)
compiler: m68k-linux-gcc (GCC) 13.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20231010/202310100603.qsn3ruBx-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202310100603.qsn3ruBx-lkp@intel.com/

All warnings (new ones prefixed by >>):

>> lib/maple_tree.c:5428:5: warning: no previous prototype for 'mas_prealloc_calc' [-Wmissing-prototypes]
    5428 | int mas_prealloc_calc(struct ma_wr_state *wr_mas)
         |     ^~~~~~~~~~~~~~~~~


vim +/mas_prealloc_calc +5428 lib/maple_tree.c

  5420	
  5421	/**
  5422	 * mas_prealloc_calc() - Calculate number of nodes needed for a
  5423	 * store operation.
  5424	 * @wr_mas: The maple write state
  5425	 *
  5426	 * Return: Number of nodes required for preallocation.
  5427	 */
> 5428	int mas_prealloc_calc(struct ma_wr_state *wr_mas)
  5429	{
  5430		struct ma_state *mas = wr_mas->mas;
  5431		unsigned char node_size;
  5432	
  5433		if (unlikely(!mas->index && mas->last == ULONG_MAX))
  5434			return 1;
  5435	
  5436		/* Root expand */
  5437		if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
  5438			return 1;
  5439	
  5440		if (unlikely(!mas_wr_walk(wr_mas))) {
  5441			/* Spanning store, use worst case for now */
  5442			return 1 + mas_mt_height(mas) * 3;
  5443		}
  5444	
  5445		/* At this point, we are at the leaf node that needs to be altered. */
  5446		/* Exact fit, no nodes needed. */
  5447		if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last)
  5448			return 0;
  5449	
  5450		mas_wr_end_piv(wr_mas);
  5451		node_size = mas_wr_new_end(wr_mas);
  5452		if (node_size >= mt_slots[wr_mas->type]) {
  5453			/* Split, worst case for now. */
  5454			return 1 + mas_mt_height(mas) * 2;
  5455		}
  5456	
  5457		/* New root needs a singe node */
  5458		if (unlikely(mte_is_root(mas->node)))
  5459			return 1;
  5460	
  5461		/* Potential spanning rebalance collapsing a node, use worst-case */
  5462		if (node_size  - 1 <= mt_min_slots[wr_mas->type])
  5463			return mas_mt_height(mas) * 2 - 1;
  5464	
  5465		/* node store, slot store needs one node */
  5466		return 1;
  5467	}
  5468
kernel test robot Oct. 10, 2023, 11:06 a.m. UTC | #2 
Hi Sidhartha,

kernel test robot noticed the following build warnings:

[auto build test WARNING on akpm-mm/mm-everything]
[also build test WARNING on linus/master v6.6-rc5 next-20231010]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Sidhartha-Kumar/maple_tree-introduce-mas_prealloc_calc/20231010-041859
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-everything
patch link:    https://lore.kernel.org/r/20231009201639.920512-2-sidhartha.kumar%40oracle.com
patch subject: [PATCH 1/3] maple_tree: introduce mas_prealloc_calc()
config: um-allnoconfig (https://download.01.org/0day-ci/archive/20231010/202310101854.kMSUyzOr-lkp@intel.com/config)
compiler: clang version 17.0.0 (https://github.com/llvm/llvm-project.git 4a5ac14ee968ff0ad5d2cc1ffa0299048db4c88a)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20231010/202310101854.kMSUyzOr-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202310101854.kMSUyzOr-lkp@intel.com/

All warnings (new ones prefixed by >>):

>> lib/maple_tree.c:5428:5: warning: no previous prototype for function 'mas_prealloc_calc' [-Wmissing-prototypes]
    5428 | int mas_prealloc_calc(struct ma_wr_state *wr_mas)
         |     ^
   lib/maple_tree.c:5428:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
    5428 | int mas_prealloc_calc(struct ma_wr_state *wr_mas)
         | ^
         | static 
   lib/maple_tree.c:348:21: warning: unused function 'mte_set_full' [-Wunused-function]
     348 | static inline void *mte_set_full(const struct maple_enode *node)
         |                     ^
   lib/maple_tree.c:353:21: warning: unused function 'mte_clear_full' [-Wunused-function]
     353 | static inline void *mte_clear_full(const struct maple_enode *node)
         |                     ^
   lib/maple_tree.c:358:20: warning: unused function 'mte_has_null' [-Wunused-function]
     358 | static inline bool mte_has_null(const struct maple_enode *node)
         |                    ^
   lib/maple_tree.c:689:29: warning: unused function 'mas_pivot' [-Wunused-function]
     689 | static inline unsigned long mas_pivot(struct ma_state *mas, unsigned char piv)
         |                             ^
   lib/maple_tree.c:4201:20: warning: stack frame size (1032) exceeds limit (1024) in 'mas_wr_modify' [-Wframe-larger-than]
    4201 | static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
         |                    ^
   6 warnings generated.


vim +/mas_prealloc_calc +5428 lib/maple_tree.c

  5420	
  5421	/**
  5422	 * mas_prealloc_calc() - Calculate number of nodes needed for a
  5423	 * store operation.
  5424	 * @wr_mas: The maple write state
  5425	 *
  5426	 * Return: Number of nodes required for preallocation.
  5427	 */
> 5428	int mas_prealloc_calc(struct ma_wr_state *wr_mas)
  5429	{
  5430		struct ma_state *mas = wr_mas->mas;
  5431		unsigned char node_size;
  5432	
  5433		if (unlikely(!mas->index && mas->last == ULONG_MAX))
  5434			return 1;
  5435	
  5436		/* Root expand */
  5437		if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
  5438			return 1;
  5439	
  5440		if (unlikely(!mas_wr_walk(wr_mas))) {
  5441			/* Spanning store, use worst case for now */
  5442			return 1 + mas_mt_height(mas) * 3;
  5443		}
  5444	
  5445		/* At this point, we are at the leaf node that needs to be altered. */
  5446		/* Exact fit, no nodes needed. */
  5447		if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last)
  5448			return 0;
  5449	
  5450		mas_wr_end_piv(wr_mas);
  5451		node_size = mas_wr_new_end(wr_mas);
  5452		if (node_size >= mt_slots[wr_mas->type]) {
  5453			/* Split, worst case for now. */
  5454			return 1 + mas_mt_height(mas) * 2;
  5455		}
  5456	
  5457		/* New root needs a singe node */
  5458		if (unlikely(mte_is_root(mas->node)))
  5459			return 1;
  5460	
  5461		/* Potential spanning rebalance collapsing a node, use worst-case */
  5462		if (node_size  - 1 <= mt_min_slots[wr_mas->type])
  5463			return mas_mt_height(mas) * 2 - 1;
  5464	
  5465		/* node store, slot store needs one node */
  5466		return 1;
  5467	}
  5468
Sidhartha Kumar Oct. 10, 2023, 10:13 p.m. UTC | #3 
On 10/9/23 3:25 PM, kernel test robot wrote:
> Hi Sidhartha,
> 
> kernel test robot noticed the following build warnings:
> 
> [auto build test WARNING on akpm-mm/mm-everything]
> [also build test WARNING on linus/master v6.6-rc5 next-20231009]
> [If your patch is applied to the wrong git tree, kindly drop us a note.
> And when submitting patch, we suggest to use '--base' as documented in
> https://git-scm.com/docs/git-format-patch#_base_tree_information]
> 
> url:    https://github.com/intel-lab-lkp/linux/commits/Sidhartha-Kumar/maple_tree-introduce-mas_prealloc_calc/20231010-041859
> base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-everything
> patch link:    https://lore.kernel.org/r/20231009201639.920512-2-sidhartha.kumar%40oracle.com
> patch subject: [PATCH 1/3] maple_tree: introduce mas_prealloc_calc()
> config: m68k-allyesconfig (https://download.01.org/0day-ci/archive/20231010/202310100603.qsn3ruBx-lkp@intel.com/config)
> compiler: m68k-linux-gcc (GCC) 13.2.0
> reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20231010/202310100603.qsn3ruBx-lkp@intel.com/reproduce)
> 
> If you fix the issue in a separate patch/commit (i.e. not just a new version of
> the same patch/commit), kindly add following tags
> | Reported-by: kernel test robot <lkp@intel.com>
> | Closes: https://lore.kernel.org/oe-kbuild-all/202310100603.qsn3ruBx-lkp@intel.com/
> 
> All warnings (new ones prefixed by >>):
> 
>>> lib/maple_tree.c:5428:5: warning: no previous prototype for 'mas_prealloc_calc' [-Wmissing-prototypes]
>      5428 | int mas_prealloc_calc(struct ma_wr_state *wr_mas)
>           |     ^~~~~~~~~~~~~~~~~
> 
> 
> vim +/mas_prealloc_calc +5428 lib/maple_tree.c
> 
>    5420	
>    5421	/**
>    5422	 * mas_prealloc_calc() - Calculate number of nodes needed for a
>    5423	 * store operation.
>    5424	 * @wr_mas: The maple write state
>    5425	 *
>    5426	 * Return: Number of nodes required for preallocation.
>    5427	 */
>> 5428	int mas_prealloc_calc(struct ma_wr_state *wr_mas)

Adding static inline should fix this compilation error.

>    5429	{
>    5430		struct ma_state *mas = wr_mas->mas;
>    5431		unsigned char node_size;
>    5432	
>    5433		if (unlikely(!mas->index && mas->last == ULONG_MAX))
>    5434			return 1;
>    5435	
>    5436		/* Root expand */
>    5437		if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
>    5438			return 1;
>    5439	
>    5440		if (unlikely(!mas_wr_walk(wr_mas))) {
>    5441			/* Spanning store, use worst case for now */
>    5442			return 1 + mas_mt_height(mas) * 3;
>    5443		}
>    5444	
>    5445		/* At this point, we are at the leaf node that needs to be altered. */
>    5446		/* Exact fit, no nodes needed. */
>    5447		if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last)
>    5448			return 0;
>    5449	
>    5450		mas_wr_end_piv(wr_mas);
>    5451		node_size = mas_wr_new_end(wr_mas);
>    5452		if (node_size >= mt_slots[wr_mas->type]) {
>    5453			/* Split, worst case for now. */
>    5454			return 1 + mas_mt_height(mas) * 2;
>    5455		}
>    5456	
>    5457		/* New root needs a singe node */
>    5458		if (unlikely(mte_is_root(mas->node)))
>    5459			return 1;
>    5460	
>    5461		/* Potential spanning rebalance collapsing a node, use worst-case */
>    5462		if (node_size  - 1 <= mt_min_slots[wr_mas->type])
>    5463			return mas_mt_height(mas) * 2 - 1;
>    5464	
>    5465		/* node store, slot store needs one node */
>    5466		return 1;
>    5467	}
>    5468	
>
kernel test robot Oct. 18, 2023, 2:53 a.m. UTC | #4 
Hi Sidhartha,

kernel test robot noticed the following build warnings:

[auto build test WARNING on akpm-mm/mm-everything]
[also build test WARNING on linus/master v6.6-rc6 next-20231017]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Sidhartha-Kumar/maple_tree-introduce-mas_prealloc_calc/20231010-041859
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-everything
patch link:    https://lore.kernel.org/r/20231009201639.920512-2-sidhartha.kumar%40oracle.com
patch subject: [PATCH 1/3] maple_tree: introduce mas_prealloc_calc()
config: i386-randconfig-061-20231018 (https://download.01.org/0day-ci/archive/20231018/202310181030.sYP91twn-lkp@intel.com/config)
compiler: gcc-12 (Debian 12.2.0-14) 12.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20231018/202310181030.sYP91twn-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202310181030.sYP91twn-lkp@intel.com/

sparse warnings: (new ones prefixed by >>)
>> lib/maple_tree.c:5428:5: sparse: sparse: symbol 'mas_prealloc_calc' was not declared. Should it be static?
diff mbox series

Patch

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 0e00a84e8e8f..e239197a57fc 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5418,6 +5418,54 @@  void *mas_store(struct ma_state *mas, void *entry)
 }
 EXPORT_SYMBOL_GPL(mas_store);
 
+/**
+ * mas_prealloc_calc() - Calculate number of nodes needed for a
+ * store operation.
+ * @wr_mas: The maple write state
+ *
+ * Return: Number of nodes required for preallocation.
+ */
+int mas_prealloc_calc(struct ma_wr_state *wr_mas)
+{
+	struct ma_state *mas = wr_mas->mas;
+	unsigned char node_size;
+
+	if (unlikely(!mas->index && mas->last == ULONG_MAX))
+		return 1;
+
+	/* Root expand */
+	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
+		return 1;
+
+	if (unlikely(!mas_wr_walk(wr_mas))) {
+		/* Spanning store, use worst case for now */
+		return 1 + mas_mt_height(mas) * 3;
+	}
+
+	/* At this point, we are at the leaf node that needs to be altered. */
+	/* Exact fit, no nodes needed. */
+	if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last)
+		return 0;
+
+	mas_wr_end_piv(wr_mas);
+	node_size = mas_wr_new_end(wr_mas);
+	if (node_size >= mt_slots[wr_mas->type]) {
+		/* Split, worst case for now. */
+		return 1 + mas_mt_height(mas) * 2;
+	}
+
+	/* New root needs a singe node */
+	if (unlikely(mte_is_root(mas->node)))
+		return 1;
+
+	/* Potential spanning rebalance collapsing a node, use worst-case */
+	if (node_size  - 1 <= mt_min_slots[wr_mas->type])
+		return mas_mt_height(mas) * 2 - 1;
+
+	/* node store, slot store needs one node */
+	return 1;
+}
+
 /**
  * mas_store_gfp() - Store a value into the tree.
  * @mas: The maple state
@@ -5474,49 +5522,16 @@  EXPORT_SYMBOL_GPL(mas_store_prealloc);
 int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 {
 	MA_WR_STATE(wr_mas, mas, entry);
-	unsigned char node_size;
 	int request = 1;
 	int ret;
 
-
-	if (unlikely(!mas->index && mas->last == ULONG_MAX))
-		goto ask_now;
-
 	mas_wr_store_setup(&wr_mas);
 	wr_mas.content = mas_start(mas);
-	/* Root expand */
-	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
-		goto ask_now;
 
-	if (unlikely(!mas_wr_walk(&wr_mas))) {
-		/* Spanning store, use worst case for now */
-		request = 1 + mas_mt_height(mas) * 3;
-		goto ask_now;
-	}
-
-	/* At this point, we are at the leaf node that needs to be altered. */
-	/* Exact fit, no nodes needed. */
-	if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
+	request = mas_prealloc_calc(&wr_mas);
+	if (!request)
 		return 0;
 
-	mas_wr_end_piv(&wr_mas);
-	node_size = mas_wr_new_end(&wr_mas);
-	if (node_size >= mt_slots[wr_mas.type]) {
-		/* Split, worst case for now. */
-		request = 1 + mas_mt_height(mas) * 2;
-		goto ask_now;
-	}
-
-	/* New root needs a singe node */
-	if (unlikely(mte_is_root(mas->node)))
-		goto ask_now;
-
-	/* Potential spanning rebalance collapsing a node, use worst-case */
-	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
-		request = mas_mt_height(mas) * 2 - 1;
-
-	/* node store, slot store needs one node */
-ask_now:
 	mas_node_count_gfp(mas, request, gfp);
 	mas->mas_flags |= MA_STATE_PREALLOC;
 	if (likely(!mas_is_err(mas)))