[PATCH 1/2] XArray: make xa_dump output more friendly to read

[PATCH 1/2] XArray: make xa_dump output more friendly to read

[Wei Yang]

This patch helps to adjust xa_dump output by:

  * add an index to each entry
  * add indent to each entry

Then the output would look like:

[ 0]0-4095: node ffff938e16539b60 max 19 parent 0000000000000000 shift 6 count 48 values 48 array ffffffffc05e1280 list ffff938e16539b78 ffff938e16539b78 marks 0 0 0
  [ 0]0-63: value 0 (0x0) [0000000000000001]
  [ 1]64-127: sibling (slot 0)
  [ 2]128-191: sibling (slot 0)
  [ 3]192-255: sibling (slot 0)
  [ 4]256-319: sibling (slot 0)
  [ 5]320-383: sibling (slot 0)
  [ 6]384-447: sibling (slot 0)
  [ 7]448-511: sibling (slot 0)
  [ 8]512-575: sibling (slot 0)
  [ 9]576-639: sibling (slot 0)
  [10]640-703: sibling (slot 0)
  [11]704-767: sibling (slot 0)
  [12]768-831: sibling (slot 0)
  [13]832-895: sibling (slot 0)
  [14]896-959: sibling (slot 0)
  [15]960-1023: sibling (slot 0)
  [32]2048-2111: value 2048 (0x800) [0000000000001001]
  [33]2112-2175: sibling (slot 32)
  [34]2176-2239: sibling (slot 32)
  [35]2240-2303: sibling (slot 32)
  [36]2304-2367: sibling (slot 32)
  [37]2368-2431: sibling (slot 32)
  [38]2432-2495: sibling (slot 32)
  [39]2496-2559: sibling (slot 32)
  [40]2560-2623: sibling (slot 32)
  [41]2624-2687: sibling (slot 32)
  [42]2688-2751: sibling (slot 32)
  [43]2752-2815: sibling (slot 32)
  [44]2816-2879: sibling (slot 32)
  [45]2880-2943: sibling (slot 32)
  [46]2944-3007: sibling (slot 32)
  [47]3008-3071: sibling (slot 32)

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 lib/xarray.c | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index ea9ce1f0b386..326b73bb9811 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -2249,19 +2249,22 @@ void xa_dump_node(const struct xa_node *node)
 
 void xa_dump_index(unsigned long index, unsigned int shift)
 {
+	pr_cont("[%2lu]", (index >> shift) & XA_CHUNK_MASK);
 	if (!shift)
-		pr_info("%lu: ", index);
+		pr_cont("%lu: ", index);
 	else if (shift >= BITS_PER_LONG)
-		pr_info("0-%lu: ", ~0UL);
+		pr_cont("0-%lu: ", ~0UL);
 	else
-		pr_info("%lu-%lu: ", index, index | ((1UL << shift) - 1));
+		pr_cont("%lu-%lu: ", index, index | ((1UL << shift) - 1));
 }
 
-void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift)
+void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift,
+			int level)
 {
 	if (!entry)
 		return;
 
+	pr_info("%*s", level * 2, level ? " " : "");
 	xa_dump_index(index, shift);
 
 	if (xa_is_node(entry)) {
@@ -2273,7 +2276,8 @@ void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift)
 			xa_dump_node(node);
 			for (i = 0; i < XA_CHUNK_SIZE; i++)
 				xa_dump_entry(node->slots[i],
-				      index + (i << node->shift), node->shift);
+				      index + (i << node->shift), node->shift,
+				      level + 1);
 		}
 	} else if (xa_is_value(entry))
 		pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),
@@ -2300,6 +2304,6 @@ void xa_dump(const struct xarray *xa)
 			xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2));
 	if (xa_is_node(entry))
 		shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT;
-	xa_dump_entry(entry, 0, shift);
+	xa_dump_entry(entry, 0, shift, 0);
 }
 #endif
-- 
2.33.1

[PATCH 2/2] XArray: Fix xas_create_range() when lower multi-order entry present

[Wei Yang]

If there is already an lower order entry present, xas_create_range()
would face two problems:

  * When new_order is roundup(order, XA_CHUNK_SHIFT), it would go up and
    access root->parent
  * When there is holes in lower order range, no proper entry is created

This patch tries to fix this issue by adjust to proper next_index if we
found a multi-order entry. And then look up.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 lib/test_xarray.c | 54 +++++++++++++++++++++++++++++++++++++++++++++++
 lib/xarray.c      | 21 +++++++++++++++---
 2 files changed, 72 insertions(+), 3 deletions(-)

diff --git a/lib/test_xarray.c b/lib/test_xarray.c
index e77d4856442c..2cf2cd8471a8 100644
--- a/lib/test_xarray.c
+++ b/lib/test_xarray.c
@@ -1482,6 +1482,59 @@ static noinline void check_create_range_5(struct xarray *xa,
 	xa_destroy(xa);
 }
 
+static noinline void check_create_range_6(struct xarray *xa)
+{
+	unsigned long index = 0;
+	unsigned int order, next_order;
+
+	order = 2 * XA_CHUNK_SHIFT - 2;
+
+	for (next_order = order + 1; next_order <= roundup(order, XA_CHUNK_SHIFT) + 1;
+			next_order++) {
+		XA_STATE(load_xas, xa, 0);
+		XA_STATE_ORDER(xas, xa, 0, next_order);
+
+		for (index = 0; index < (1 << next_order); index += 1 << order) {
+			if (index == 0)
+				continue;
+			xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
+		}
+
+		// [0, (1 << order) - 1] is empty now
+		rcu_read_lock();
+		xas_load(&load_xas);
+		XA_BUG_ON(xa, load_xas.xa_node == NULL);
+		XA_BUG_ON(xa, load_xas.xa_node->shift == 0);
+		rcu_read_unlock();
+
+		xas_set(&load_xas, (1 << order) - 1);
+		rcu_read_lock();
+		xas_load(&load_xas);
+		XA_BUG_ON(xa, load_xas.xa_node == NULL);
+		XA_BUG_ON(xa, load_xas.xa_node->shift == 0);
+		rcu_read_unlock();
+
+		do {
+			xas_lock(&xas);
+			xas_create_range(&xas);
+			xas_unlock(&xas);
+		} while (xas_nomem(&xas, GFP_KERNEL));
+
+		// [0, (1 << order) - 1] is created now
+		xas_set(&load_xas, 0);
+		XA_BUG_ON(xa, xas_load(&load_xas) != NULL);
+		XA_BUG_ON(xa, load_xas.xa_node == NULL);
+		XA_BUG_ON(xa, load_xas.xa_node->shift != 0);
+
+		xas_set(&load_xas, (1 << order) - 1);
+		XA_BUG_ON(xa, xas_load(&load_xas) != NULL);
+		XA_BUG_ON(xa, load_xas.xa_node == NULL);
+		XA_BUG_ON(xa, load_xas.xa_node->shift != 0);
+
+		xa_destroy(xa);
+	}
+}
+
 static noinline void check_create_range(struct xarray *xa)
 {
 	unsigned int order;
@@ -1515,6 +1568,7 @@ static noinline void check_create_range(struct xarray *xa)
 	}
 
 	check_create_range_3();
+	check_create_range_6(xa);
 }
 
 static noinline void __check_store_range(struct xarray *xa, unsigned long first,
diff --git a/lib/xarray.c b/lib/xarray.c
index 326b73bb9811..3f9a630ef788 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -708,6 +708,7 @@ void xas_create_range(struct xa_state *xas)
 	unsigned long index = xas->xa_index;
 	unsigned char shift = xas->xa_shift;
 	unsigned char sibs = xas->xa_sibs;
+	struct xa_node *node;
 
 	xas->xa_index |= ((sibs + 1UL) << shift) - 1;
 	if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift)
@@ -723,14 +724,28 @@ void xas_create_range(struct xa_state *xas)
 			goto success;
 		xas->xa_index -= XA_CHUNK_SIZE;
 
+		node = xas->xa_node;
+		if (node->shift) {
+			unsigned long next_index = xas->xa_index >> node->shift;
+
+			next_index &= ~XA_CHUNK_MASK;
+			next_index += xas->xa_offset;
+			next_index <<= node->shift;
+
+			if (next_index <= (index & ~XA_CHUNK_MASK))
+				goto success;
+
+			xas->xa_index = next_index - 1;
+		}
+
 		for (;;) {
-			struct xa_node *node = xas->xa_node;
-			if (node->shift >= shift)
-				break;
 			xas->xa_node = xa_parent_locked(xas->xa, node);
+			if (!xas->xa_node)
+				break;
 			xas->xa_offset = node->offset - 1;
 			if (node->offset != 0)
 				break;
+			node = xas->xa_node;
 		}
 	}
 
-- 
2.33.1

Re: [PATCH 1/2] XArray: make xa_dump output more friendly to read

[Matthew Wilcox]

On Mon, Sep 12, 2022 at 12:46:46PM +0000, Wei Yang wrote:
> This patch helps to adjust xa_dump output by:

Thanks for the patches.  I'm at Plumbers right now, and then I'm taking
a week off, so I don't really have time to look at them properly.
I'll try to remember to look at them when I'm back on the 26th.  If I
haven't responded by the beginning of October, please remind me.

[Patch v2 1/2] XArray: make xa_dump output more friendly to read

[Wei Yang]

This patch helps to adjust xa_dump output by:

  * add an index to each entry
  * add indent to each entry

Then the output would look like:

[ 0]0-4095: node ffff938e16539b60 max 19 parent 0000000000000000 shift 6 count 48 values 48 array ffffffffc05e1280 list ffff938e16539b78 ffff938e16539b78 marks 0 0 0
  [ 0]0-63: value 0 (0x0) [0000000000000001]
  [ 1]64-127: sibling (slot 0)
  [ 2]128-191: sibling (slot 0)
  [ 3]192-255: sibling (slot 0)
  [ 4]256-319: sibling (slot 0)
  [ 5]320-383: sibling (slot 0)
  [ 6]384-447: sibling (slot 0)
  [ 7]448-511: sibling (slot 0)
  [ 8]512-575: sibling (slot 0)
  [ 9]576-639: sibling (slot 0)
  [10]640-703: sibling (slot 0)
  [11]704-767: sibling (slot 0)
  [12]768-831: sibling (slot 0)
  [13]832-895: sibling (slot 0)
  [14]896-959: sibling (slot 0)
  [15]960-1023: sibling (slot 0)
  [32]2048-2111: value 2048 (0x800) [0000000000001001]
  [33]2112-2175: sibling (slot 32)
  [34]2176-2239: sibling (slot 32)
  [35]2240-2303: sibling (slot 32)
  [36]2304-2367: sibling (slot 32)
  [37]2368-2431: sibling (slot 32)
  [38]2432-2495: sibling (slot 32)
  [39]2496-2559: sibling (slot 32)
  [40]2560-2623: sibling (slot 32)
  [41]2624-2687: sibling (slot 32)
  [42]2688-2751: sibling (slot 32)
  [43]2752-2815: sibling (slot 32)
  [44]2816-2879: sibling (slot 32)
  [45]2880-2943: sibling (slot 32)
  [46]2944-3007: sibling (slot 32)
  [47]3008-3071: sibling (slot 32)

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 lib/xarray.c | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index 1ddcfa8c86ac..ed50a26d97a3 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -2235,19 +2235,22 @@ void xa_dump_node(const struct xa_node *node)
 
 void xa_dump_index(unsigned long index, unsigned int shift)
 {
+	pr_cont("[%2lu]", (index >> shift) & XA_CHUNK_MASK);
 	if (!shift)
-		pr_info("%lu: ", index);
+		pr_cont("%lu: ", index);
 	else if (shift >= BITS_PER_LONG)
-		pr_info("0-%lu: ", ~0UL);
+		pr_cont("0-%lu: ", ~0UL);
 	else
-		pr_info("%lu-%lu: ", index, index | ((1UL << shift) - 1));
+		pr_cont("%lu-%lu: ", index, index | ((1UL << shift) - 1));
 }
 
-void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift)
+void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift,
+			int level)
 {
 	if (!entry)
 		return;
 
+	pr_info("%*s", level * 2, level ? " " : "");
 	xa_dump_index(index, shift);
 
 	if (xa_is_node(entry)) {
@@ -2259,7 +2262,8 @@ void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift)
 			xa_dump_node(node);
 			for (i = 0; i < XA_CHUNK_SIZE; i++)
 				xa_dump_entry(node->slots[i],
-				      index + (i << node->shift), node->shift);
+				      index + (i << node->shift), node->shift,
+				      level + 1);
 		}
 	} else if (xa_is_value(entry))
 		pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),
@@ -2286,6 +2290,6 @@ void xa_dump(const struct xarray *xa)
 			xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2));
 	if (xa_is_node(entry))
 		shift = xa_to_node(entry)->shift + XA_CHUNK_SHIFT;
-	xa_dump_entry(entry, 0, shift);
+	xa_dump_entry(entry, 0, shift, 0);
 }
 #endif
-- 
2.33.1

[Patch v2 2/2] XArray: Fix xas_create_range() when lower multi-order entry present

[Wei Yang]

If there is already an lower order entry present, xas_create_range()
would face two problems:

  * When new_order is roundup(order, XA_CHUNK_SHIFT), it would go up and
    access root->parent
  * When there is holes in lower order range, no proper entry is created

This patch tries to fix this issue by adjust to proper next_index if we
found a multi-order entry.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>

---
v2:
  * guard result check with rcu lock
  * instead of continue the iteration on multi-order entry, xas_set() the
    index to let xas_create() restart
  * put hole in each possible position
---
 lib/test_xarray.c | 65 +++++++++++++++++++++++++++++++++++++++++++++++
 lib/xarray.c      | 22 +++++++++++++---
 2 files changed, 84 insertions(+), 3 deletions(-)

diff --git a/lib/test_xarray.c b/lib/test_xarray.c
index e77d4856442c..5ec9c19ad65e 100644
--- a/lib/test_xarray.c
+++ b/lib/test_xarray.c
@@ -1482,6 +1482,70 @@ static noinline void check_create_range_5(struct xarray *xa,
 	xa_destroy(xa);
 }
 
+static noinline void check_create_range_6(struct xarray *xa)
+{
+	unsigned long index = 0;
+	unsigned int order, next_order;
+
+	order = 2 * XA_CHUNK_SHIFT - 2;
+
+	for (next_order = order + 1; next_order <= roundup(order, XA_CHUNK_SHIFT) + 1;
+			next_order++) {
+		unsigned long hole;
+
+		for (hole = 0; hole < (1 << next_order); hole += 1 << order) {
+			XA_STATE(load_xas, xa, 0);
+			XA_STATE_ORDER(xas, xa, 0, next_order);
+
+			for (index = 0; index < (1 << next_order);
+					index += 1 << order) {
+				if (index == hole)
+					continue;
+				xa_store_order(xa, index, order,
+					xa_mk_index(index), GFP_KERNEL);
+			}
+
+			// [hole, hole + (1 << order) - 1] is empty now
+			xas_set(&load_xas, hole);
+			rcu_read_lock();
+			xas_load(&load_xas);
+			XA_BUG_ON(xa, load_xas.xa_node == NULL);
+			XA_BUG_ON(xa, load_xas.xa_node->shift == 0);
+			rcu_read_unlock();
+
+			xas_set(&load_xas, hole + (1 << order) - 1);
+			rcu_read_lock();
+			xas_load(&load_xas);
+			XA_BUG_ON(xa, load_xas.xa_node == NULL);
+			XA_BUG_ON(xa, load_xas.xa_node->shift == 0);
+			rcu_read_unlock();
+
+			do {
+				xas_lock(&xas);
+				xas_create_range(&xas);
+				xas_unlock(&xas);
+			} while (xas_nomem(&xas, GFP_KERNEL));
+
+			// [hole, hole + (1 << order) - 1] is created now
+			xas_set(&load_xas, hole);
+			rcu_read_lock();
+			xas_load(&load_xas);
+			XA_BUG_ON(xa, load_xas.xa_node == NULL);
+			XA_BUG_ON(xa, load_xas.xa_node->shift != 0);
+			rcu_read_unlock();
+
+			xas_set(&load_xas, hole + (1 << order) - 1);
+			rcu_read_lock();
+			xas_load(&load_xas);
+			XA_BUG_ON(xa, load_xas.xa_node == NULL);
+			XA_BUG_ON(xa, load_xas.xa_node->shift != 0);
+			rcu_read_unlock();
+
+			xa_destroy(xa);
+		}
+	}
+}
+
 static noinline void check_create_range(struct xarray *xa)
 {
 	unsigned int order;
@@ -1515,6 +1579,7 @@ static noinline void check_create_range(struct xarray *xa)
 	}
 
 	check_create_range_3();
+	check_create_range_6(xa);
 }
 
 static noinline void __check_store_range(struct xarray *xa, unsigned long first,
diff --git a/lib/xarray.c b/lib/xarray.c
index ed50a26d97a3..8b3df256b407 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -694,6 +694,7 @@ void xas_create_range(struct xa_state *xas)
 	unsigned long index = xas->xa_index;
 	unsigned char shift = xas->xa_shift;
 	unsigned char sibs = xas->xa_sibs;
+	struct xa_node *node;
 
 	xas->xa_index |= ((sibs + 1UL) << shift) - 1;
 	if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift)
@@ -709,14 +710,29 @@ void xas_create_range(struct xa_state *xas)
 			goto success;
 		xas->xa_index -= XA_CHUNK_SIZE;
 
+		node = xas->xa_node;
+		if (node->shift) {
+			unsigned long next_index = xas->xa_index >> node->shift;
+
+			next_index &= ~XA_CHUNK_MASK;
+			next_index += xas->xa_offset;
+			next_index <<= node->shift;
+
+			if (next_index <= (index & ~XA_CHUNK_MASK))
+				goto success;
+
+			xas_set(xas, next_index - 1);
+			continue;
+		}
+
 		for (;;) {
-			struct xa_node *node = xas->xa_node;
-			if (node->shift >= shift)
-				break;
 			xas->xa_node = xa_parent_locked(xas->xa, node);
+			if (!xas->xa_node)
+				break;
 			xas->xa_offset = node->offset - 1;
 			if (node->offset != 0)
 				break;
+			node = xas->xa_node;
 		}
 	}
 
-- 
2.33.1

Re: [PATCH 1/2] XArray: make xa_dump output more friendly to read

[Wei Yang]

On Mon, Sep 12, 2022 at 06:43:34PM +0100, Matthew Wilcox wrote:
>On Mon, Sep 12, 2022 at 12:46:46PM +0000, Wei Yang wrote:
>> This patch helps to adjust xa_dump output by:
>
>Thanks for the patches.  I'm at Plumbers right now, and then I'm taking
>a week off, so I don't really have time to look at them properly.
>I'll try to remember to look at them when I'm back on the 26th.  If I
>haven't responded by the beginning of October, please remind me.

Hi, Matthew

Do you get time slot for this?

-- 
Wei Yang
Help you, Help me

Re: [PATCH 1/2] XArray: make xa_dump output more friendly to read

[Wei Yang]

On Mon, Sep 12, 2022 at 06:43:34PM +0100, Matthew Wilcox wrote:
>On Mon, Sep 12, 2022 at 12:46:46PM +0000, Wei Yang wrote:
>> This patch helps to adjust xa_dump output by:
>
>Thanks for the patches.  I'm at Plumbers right now, and then I'm taking
>a week off, so I don't really have time to look at them properly.
>I'll try to remember to look at them when I'm back on the 26th.  If I
>haven't responded by the beginning of October, please remind me.

Hello, Matthew

Do you get some time for this?

-- 
Wei Yang
Help you, Help me