Skip to contentSkip to conversation

xfs: Use xarray to track SB UUIDs instead of plain array.

PATCH New Lukas Herbolt 3 participants 10 messages Jan 30 – Feb 3 XFS filesystem

lore
Share & tools
lore
#0 lore raw

cover xfs: Use xarray to track SB UUIDs instead of plain array.

Hi,
It was discussed in previous thread [1]. Some older kernels (pre v6.12), complained doing allocation over 2xPAGE_SIZE in krealloc when mounting over 512 unique XFS.

The warning was removed in v6.12, but Christoph suggested to start using xrarray instead of plain array. So here it is.

[1]
- https://lore.kernel.org/linux-xfs/[email protected]/

Lukas Herbolt (1):
xfs: Use xarray to track SB UUIDs instead of plain array.

 fs/xfs/xfs_mount.c | 87 +++++++++++++++++++++++-----------------------
 fs/xfs/xfs_mount.h |  3 +-
 fs/xfs/xfs_super.c |  2 +-
 3 files changed, 46 insertions(+), 46 deletions(-)

base-commit: 63804fed149a6750ffd28610c5c1c98cce6bd377

Signature · 1 line
2.52.0
#1 lore raw

PATCH 1/1 xfs: Use xarray to track SB UUIDs instead of plain array.

Removing the plain array to track the UUIDs and switch xarray to make more readable.

---
 fs/xfs/xfs_mount.c | 87 +++++++++++++++++++++++-----------------------
 fs/xfs/xfs_mount.h |  3 +-
 fs/xfs/xfs_super.c |  2 +-
 3 files changed, 46 insertions(+), 46 deletions(-)
fs/xfs/xfs_mount.c +43 -44
index 0953f6ae94ab..35c0d411e0cb 100644
@@ -42,18 +42,48 @@
 #include "scrub/stats.h"
 #include "xfs_zone_alloc.h"
 
-static DEFINE_MUTEX(xfs_uuid_table_mutex);
-static int xfs_uuid_table_size;
-static uuid_t *xfs_uuid_table;
+static DEFINE_XARRAY_ALLOC(xfs_uuid_table);
+
+/*
+ * Helper fucntions to store UUID in xarray.
+ */
+STATIC int
+xfs_uuid_insert(uuid_t *uuid)
+{
+	uint32_t index = 0;
+
+	return xa_alloc(&xfs_uuid_table, &index, uuid,
+			xa_limit_32b, GFP_KERNEL);
+}
+
+STATIC uuid_t
+*xfs_uuid_search(uuid_t *new_uuid)
+{
+	unsigned long index = 0;
+	uuid_t *uuid = NULL;
+
+	xa_for_each(&xfs_uuid_table, index, uuid) {
+		if (uuid_equal(uuid, new_uuid))
+			return uuid;
+	}
+	return NULL;
+}
+
+STATIC void
+xfs_uuid_delete(uuid_t *uuid)
+{
+	unsigned long index = 0;
+
+	xa_for_each(&xfs_uuid_table, index, uuid) {
+		xa_erase(&xfs_uuid_table, index);
+	}
+}
 
 void
-xfs_uuid_table_free(void)
+xfs_uuid_table_destroy(void)
 {
-	if (xfs_uuid_table_size == 0)
-		return;
-	kfree(xfs_uuid_table);
-	xfs_uuid_table = NULL;
-	xfs_uuid_table_size = 0;
+	ASSERT(xa_empty(&xfs_uuid_table));
+	xa_destroy(&xfs_uuid_table);
 }
 
 /*
@@ -65,7 +95,6 @@ xfs_uuid_mount(
 	struct xfs_mount	*mp)
 {
 	uuid_t			*uuid = &mp->m_sb.sb_uuid;
-	int			hole, i;
 
 	/* Publish UUID in struct super_block */
 	super_set_uuid(mp->m_super, uuid->b, sizeof(*uuid));
@@ -78,29 +107,9 @@ xfs_uuid_mount(
 		return -EINVAL;
 	}
 
-	mutex_lock(&xfs_uuid_table_mutex);
-	for (i = 0, hole = -1; i < xfs_uuid_table_size; i++) {
-		if (uuid_is_null(&xfs_uuid_table[i])) {
-			hole = i;
-			continue;
-		}
-		if (uuid_equal(uuid, &xfs_uuid_table[i]))
-			goto out_duplicate;
-	}
+	if (!xfs_uuid_search(uuid))
+		return xfs_uuid_insert(uuid);
 
-	if (hole < 0) {
-		xfs_uuid_table = krealloc(xfs_uuid_table,
-			(xfs_uuid_table_size + 1) * sizeof(*xfs_uuid_table),
-			GFP_KERNEL | __GFP_NOFAIL);
-		hole = xfs_uuid_table_size++;
-	}
-	xfs_uuid_table[hole] = *uuid;
-	mutex_unlock(&xfs_uuid_table_mutex);
-
-	return 0;
-
- out_duplicate:
-	mutex_unlock(&xfs_uuid_table_mutex);
 	xfs_warn(mp, "Filesystem has duplicate UUID %pU - can't mount", uuid);
 	return -EINVAL;
 }
@@ -110,22 +119,12 @@ xfs_uuid_unmount(
 	struct xfs_mount	*mp)
 {
 	uuid_t			*uuid = &mp->m_sb.sb_uuid;
-	int			i;
 
 	if (xfs_has_nouuid(mp))
 		return;
+	xfs_uuid_delete(uuid);
+	return;
 
-	mutex_lock(&xfs_uuid_table_mutex);
-	for (i = 0; i < xfs_uuid_table_size; i++) {
-		if (uuid_is_null(&xfs_uuid_table[i]))
-			continue;
-		if (!uuid_equal(uuid, &xfs_uuid_table[i]))
-			continue;
-		memset(&xfs_uuid_table[i], 0, sizeof(uuid_t));
-		break;
-	}
-	ASSERT(i < xfs_uuid_table_size);
-	mutex_unlock(&xfs_uuid_table_mutex);
 }
 
 /*
fs/xfs/xfs_mount.h +2 -1
index b871dfde372b..c3a5035c1fb6 100644
@@ -689,7 +689,8 @@ xfs_daddr_to_agbno(struct xfs_mount *mp, xfs_daddr_t d)
 	return (xfs_agblock_t) do_div(ld, mp->m_sb.sb_agblocks);
 }
 
-extern void	xfs_uuid_table_free(void);
+extern void xfs_uuid_table_destroy(void);
+
 uint64_t	xfs_default_resblks(struct xfs_mount *mp,
 			enum xfs_free_counter ctr);
 extern int	xfs_mountfs(xfs_mount_t *mp);
fs/xfs/xfs_super.c +1 -1
index bc71aa9dcee8..fc9d2e5acf96 100644
@@ -2723,7 +2723,7 @@ exit_xfs_fs(void)
 	xfs_mru_cache_uninit();
 	xfs_destroy_workqueues();
 	xfs_destroy_caches();
-	xfs_uuid_table_free();
+	xfs_uuid_table_destroy();
 }
 
 module_init(init_xfs_fs);

base-commit: 63804fed149a6750ffd28610c5c1c98cce6bd377

Signature · 1 line
2.52.0
#2 lore raw
Quoted 46 lines · Lukas Herbolt

Removing the plain array to track the UUIDs and switch xarray to make more readable.

---
 fs/xfs/xfs_mount.c | 87 +++++++++++++++++++++++-----------------------
 fs/xfs/xfs_mount.h |  3 +-
 fs/xfs/xfs_super.c |  2 +-
 3 files changed, 46 insertions(+), 46 deletions(-)
fs/xfs/xfs_mount.c +25 -3
index 0953f6ae94ab..35c0d411e0cb 100644
@@ -42,18 +42,48 @@
 #include "scrub/stats.h"
 #include "xfs_zone_alloc.h"
 
-static DEFINE_MUTEX(xfs_uuid_table_mutex);
-static int xfs_uuid_table_size;
-static uuid_t *xfs_uuid_table;
+static DEFINE_XARRAY_ALLOC(xfs_uuid_table);
+
+/*
+ * Helper fucntions to store UUID in xarray.
+ */
+STATIC int
+xfs_uuid_insert(uuid_t *uuid)
+{
+	uint32_t index = 0;
+
+	return xa_alloc(&xfs_uuid_table, &index, uuid,
+			xa_limit_32b, GFP_KERNEL);
+}
+
+STATIC uuid_t
+*xfs_uuid_search(uuid_t *new_uuid)
+{
+	unsigned long index = 0;
+	uuid_t *uuid = NULL;
+
+	xa_for_each(&xfs_uuid_table, index, uuid) {
+		if (uuid_equal(uuid, new_uuid))
+			return uuid;
+	}
+	return NULL;

fs/xfs/xfs_mount.c line 79

Quoted 10 lines
fs/xfs/xfs_mount.c +10 -0
+}
+
+STATIC void
+xfs_uuid_delete(uuid_t *uuid)
+{
+	unsigned long index = 0;
+
+	xa_for_each(&xfs_uuid_table, index, uuid) {
+		xa_erase(&xfs_uuid_table, index);
+	}

Why not store the xarray index in the xfs_mount so you can delete the entry directly without having to walk the entire array?

And while I'm on about it ... if you're going to change data structures, why not use rhashtable or something that can do a direct lookup?

Quoted 29 lines
fs/xfs/xfs_mount.c +4 -8
+}
 
 void
-xfs_uuid_table_free(void)
+xfs_uuid_table_destroy(void)
 {
-	if (xfs_uuid_table_size == 0)
-		return;
-	kfree(xfs_uuid_table);
-	xfs_uuid_table = NULL;
-	xfs_uuid_table_size = 0;
+	ASSERT(xa_empty(&xfs_uuid_table));
+	xa_destroy(&xfs_uuid_table);
 }
 
 /*
@@ -65,7 +95,6 @@ xfs_uuid_mount(
 	struct xfs_mount	*mp)
 {
 	uuid_t			*uuid = &mp->m_sb.sb_uuid;
-	int			hole, i;
 
 	/* Publish UUID in struct super_block */
 	super_set_uuid(mp->m_super, uuid->b, sizeof(*uuid));
@@ -78,29 +107,9 @@ xfs_uuid_mount(
 		return -EINVAL;
 	}
 
-	mutex_lock(&xfs_uuid_table_mutex);

fs/xfs/xfs_mount.c xfs_uuid_mount( · line 111

Quoted 10 lines
fs/xfs/xfs_mount.c +2 -8
-	for (i = 0, hole = -1; i < xfs_uuid_table_size; i++) {
-		if (uuid_is_null(&xfs_uuid_table[i])) {
-			hole = i;
-			continue;
-		}
-		if (uuid_equal(uuid, &xfs_uuid_table[i]))
-			goto out_duplicate;
-	}
+	if (!xfs_uuid_search(uuid))
+		return xfs_uuid_insert(uuid);

xfs_uuid_table_mutex went away, so what's protecting the lookup and insert from racing to insert the same uuid twice?

--D

Quoted 75 lines
fs/xfs/xfs_mount.c +2 -25
-	if (hole < 0) {
-		xfs_uuid_table = krealloc(xfs_uuid_table,
-			(xfs_uuid_table_size + 1) * sizeof(*xfs_uuid_table),
-			GFP_KERNEL | __GFP_NOFAIL);
-		hole = xfs_uuid_table_size++;
-	}
-	xfs_uuid_table[hole] = *uuid;
-	mutex_unlock(&xfs_uuid_table_mutex);
-
-	return 0;
-
- out_duplicate:
-	mutex_unlock(&xfs_uuid_table_mutex);
 	xfs_warn(mp, "Filesystem has duplicate UUID %pU - can't mount", uuid);
 	return -EINVAL;
 }
@@ -110,22 +119,12 @@ xfs_uuid_unmount(
 	struct xfs_mount	*mp)
 {
 	uuid_t			*uuid = &mp->m_sb.sb_uuid;
-	int			i;
 
 	if (xfs_has_nouuid(mp))
 		return;
+	xfs_uuid_delete(uuid);
+	return;
 
-	mutex_lock(&xfs_uuid_table_mutex);
-	for (i = 0; i < xfs_uuid_table_size; i++) {
-		if (uuid_is_null(&xfs_uuid_table[i]))
-			continue;
-		if (!uuid_equal(uuid, &xfs_uuid_table[i]))
-			continue;
-		memset(&xfs_uuid_table[i], 0, sizeof(uuid_t));
-		break;
-	}
-	ASSERT(i < xfs_uuid_table_size);
-	mutex_unlock(&xfs_uuid_table_mutex);
 }
 
 /*
fs/xfs/xfs_mount.h +2 -1
index b871dfde372b..c3a5035c1fb6 100644
@@ -689,7 +689,8 @@ xfs_daddr_to_agbno(struct xfs_mount *mp, xfs_daddr_t d)
 	return (xfs_agblock_t) do_div(ld, mp->m_sb.sb_agblocks);
 }
 
-extern void	xfs_uuid_table_free(void);
+extern void xfs_uuid_table_destroy(void);
+
 uint64_t	xfs_default_resblks(struct xfs_mount *mp,
 			enum xfs_free_counter ctr);
 extern int	xfs_mountfs(xfs_mount_t *mp);
fs/xfs/xfs_super.c +1 -1
index bc71aa9dcee8..fc9d2e5acf96 100644
@@ -2723,7 +2723,7 @@ exit_xfs_fs(void)
 	xfs_mru_cache_uninit();
 	xfs_destroy_workqueues();
 	xfs_destroy_caches();
-	xfs_uuid_table_free();
+	xfs_uuid_table_destroy();
 }
 
 module_init(init_xfs_fs);

base-commit: 63804fed149a6750ffd28610c5c1c98cce6bd377

Signature · 1 line
2.52.0
#3 lore raw
Quoted 5 lines · Darrick J. Wong

Review

Quoted 2 lines
(quoted diff) +2 -0
+		xa_erase(&xfs_uuid_table, index);
+	}

Why not store the xarray index in the xfs_mount so you can delete the entry directly without having to walk the entire array?

Yeah, that makes a lot of sense.

Quoted 2 lines

And while I'm on about it ... if you're going to change data structures, why not use rhashtable or something that can do a direct lookup?

rhashtables require quite a bit of boilerplate. Probably not worth if for a single lookup in a relatively small colletion once per mount. But yeah, if only we had a data structure that allows directly lookups without all that boilerplate..

#4 lore raw
Quoted 9 lines · Christoph Hellwig
Quoted 5 lines · Darrick J. Wong

Review

Quoted 2 lines
(quoted diff) +2 -0
+		xa_erase(&xfs_uuid_table, index);
+	}

Why not store the xarray index in the xfs_mount so you can delete the entry directly without having to walk the entire array?

Yeah, that makes a lot of sense.

I did not want to touch the xfs_mount but if there is no objection against, I will add the index there.

Quoted 7 lines
Quoted 2 lines

And while I'm on about it ... if you're going to change data structures, why not use rhashtable or something that can do a direct lookup?

rhashtables require quite a bit of boilerplate. Probably not worth if for a single lookup in a relatively small colletion once per mount. But yeah, if only we had a data structure that allows directly lookups without all that boilerplate..

I do not have strong preference here.

Signature · 1 line
-lhe
#5 lore raw
Quoted 17 lines · Lukas Herbolt
Quoted 9 lines · Christoph Hellwig
Quoted 5 lines · Darrick J. Wong

Review

Quoted 2 lines
(quoted diff) +2 -0
+		xa_erase(&xfs_uuid_table, index);
+	}

Why not store the xarray index in the xfs_mount so you can delete the entry directly without having to walk the entire array?

Yeah, that makes a lot of sense.

I did not want to touch the xfs_mount but if there is no objection against, I will add the index there.

Quoted 4 lines
Quoted 3 lines

And while I'm on about it ... if you're going to change data structures,
why not use rhashtable or something that can do a direct lookup?

Quoted 6 lines
Quoted 4 lines

rhashtables require quite a bit of boilerplate. Probably not worth if for a single lookup in a relatively small colletion once per mount. But yeah, if only we had a data structure that allows directly lookups without all that boilerplate..

I do not have strong preference here.

<shrug> Since the original message said "krealloc prints out warning if allocation is bigger than 2x PAGE_SIZE", I figured that meant you were trying to mount more than (2 * 4096) / 16 == 512 different xfs filesystems on the same host.

I don't have a particular problem with the array search and large memory allocation since I never mount that many filesystems, but you would appear to be the first user to complain about a scaling limit there...

:)

--D

Quoted 3 lines
Signature · 1 line
-lhe
#6 lore raw
Quoted 6 lines · Darrick J. Wong
Quoted 1 line

I do not have strong preference here.

<shrug> Since the original message said "krealloc prints out warning if allocation is bigger than 2x PAGE_SIZE", I figured that meant you were trying to mount more than (2 * 4096) / 16 == 512 different xfs filesystems on the same host.

I don't remember any such message. But array or xarray iterations should still scale well enough for a single mount time operation into the 10.000nds of entries.

Quoted 3 lines

I don't have a particular problem with the array search and large memory allocation since I never mount that many filesystems, but you would appear to be the first user to complain about a scaling limit there...

I was really just concerned about a single large allocation. But yeah, it's not that large... That beind said I think the xarray version will also look nicer than the original one.

#7 lore raw
Quoted 12 lines · Christoph Hellwig
Quoted 6 lines · Darrick J. Wong
Quoted 1 line

I do not have strong preference here.

<shrug> Since the original message said "krealloc prints out warning if allocation is bigger than 2x PAGE_SIZE", I figured that meant you were trying to mount more than (2 * 4096) / 16 == 512 different xfs filesystems on the same host.

I don't remember any such message. But array or xarray iterations should still scale well enough for a single mount time operation into the 10.000nds of entries.

Quoted 7 lines
Quoted 3 lines

I don't have a particular problem with the array search and large memory allocation since I never mount that many filesystems, but you would appear to be the first user to complain about a scaling limit there...

I was really just concerned about a single large allocation. But yeah, it's not that large... That beind said I think the xarray version will also look nicer than the original one.

It's better than the raw kvalloc'd blob we have now :)

--D

#8 lore raw
In reply to Lukas Herbolt
Quoted 1 line

+STATIC int

We're phasing out the magic STATIC, so pleae just use plain static here.

Quoted 1 line

+xfs_uuid_insert(uuid_t *uuid)

The somewhat unique XFS coding style uses separate lines for each argument:

static int
xfs_uuid_insert(

	uuid_t			*uuid)

fs/xfs/xfs_mount.c line 53

Quoted 2 lines
fs/xfs/xfs_mount.c +2 -0
+{
+	uint32_t index = 0;

.. and aligns the variables the same way:

{
	uint32_t		index = 0;

Although this one will go away with Darrick's suggestion anyway.

fs/xfs/xfs_mount.c line 60

Quoted 7 lines
fs/xfs/xfs_mount.c +7 -0
+
+	return xa_alloc(&xfs_uuid_table, &index, uuid,
+			xa_limit_32b, GFP_KERNEL);
+}
+
+STATIC uuid_t
+*xfs_uuid_search(uuid_t *new_uuid)

The * for pointers goes with the type:

static uuid_t *
xfs_uuid_search(

	uuid_t			*new_uuid)

fs/xfs/xfs_mount.c line 63

Quoted 1 line
fs/xfs/xfs_mount.c +1 -0
+	uuid_t *uuid = NULL;

no need to initialize the iterator to NULL before xa_for_each.

fs/xfs/xfs_mount.c line 79

Quoted 8 lines
fs/xfs/xfs_mount.c +8 -0
+STATIC void
+xfs_uuid_delete(uuid_t *uuid)
+{
+	unsigned long index = 0;
+
+	xa_for_each(&xfs_uuid_table, index, uuid) {
+		xa_erase(&xfs_uuid_table, index);
+	}

I don't think this works as expected, as it just erases all uuids in the table.

fs/xfs/xfs_mount.c line 83

Quoted 5 lines
fs/xfs/xfs_mount.c +2 -1
+}
 
 void
-xfs_uuid_table_free(void)
+xfs_uuid_table_destroy(void)

I'd drop this rename. Free works just fine here as a name.

fs/xfs/xfs_mount.c xfs_uuid_mount( · line 114

Quoted 5 lines
fs/xfs/xfs_mount.c +2 -0
+	if (!xfs_uuid_search(uuid))
+		return xfs_uuid_insert(uuid);
 
 	xfs_warn(mp, "Filesystem has duplicate UUID %pU - can't mount", uuid);
 	return -EINVAL;

Just return an error here if xfs_uuid_search finds something, and then open code the insert in the straight line path.

fs/xfs/xfs_mount.c xfs_uuid_unmount( · line 126

Quoted 9 lines
fs/xfs/xfs_mount.c +2 -0
@@ -110,22 +119,12 @@ xfs_uuid_unmount(
 	struct xfs_mount	*mp)
 {
 	uuid_t			*uuid = &mp->m_sb.sb_uuid;
 
 	if (xfs_has_nouuid(mp))
 		return;
+	xfs_uuid_delete(uuid);
+	return;

No need for the last return. Also I think you can just open code xfs_uuid_delete here.

#9 lore raw
Quoted 77 lines · Christoph Hellwig
Quoted 1 line

+STATIC int

We're phasing out the magic STATIC, so pleae just use plain static here.

Quoted 1 line

+xfs_uuid_insert(uuid_t *uuid)

The somewhat unique XFS coding style uses separate lines for each argument:

static int
xfs_uuid_insert(

	uuid_t			*uuid)

fs/xfs/xfs_mount.c line 53

Quoted 2 lines
fs/xfs/xfs_mount.c +2 -0
+{
+	uint32_t index = 0;

.. and aligns the variables the same way:

{
	uint32_t		index = 0;

Although this one will go away with Darrick's suggestion anyway.

fs/xfs/xfs_mount.c line 60

Quoted 7 lines
fs/xfs/xfs_mount.c +7 -0
+
+	return xa_alloc(&xfs_uuid_table, &index, uuid,
+			xa_limit_32b, GFP_KERNEL);
+}
+
+STATIC uuid_t
+*xfs_uuid_search(uuid_t *new_uuid)

The * for pointers goes with the type:

static uuid_t *
xfs_uuid_search(

	uuid_t			*new_uuid)

fs/xfs/xfs_mount.c line 63

Quoted 1 line
fs/xfs/xfs_mount.c +1 -0
+	uuid_t *uuid = NULL;

no need to initialize the iterator to NULL before xa_for_each.

fs/xfs/xfs_mount.c line 79

Quoted 8 lines
fs/xfs/xfs_mount.c +8 -0
+STATIC void
+xfs_uuid_delete(uuid_t *uuid)
+{
+	unsigned long index = 0;
+
+	xa_for_each(&xfs_uuid_table, index, uuid) {
+		xa_erase(&xfs_uuid_table, index);
+	}

I don't think this works as expected, as it just erases all uuids in the table.

fs/xfs/xfs_mount.c line 83

Quoted 5 lines
fs/xfs/xfs_mount.c +2 -1
+}
 
 void
-xfs_uuid_table_free(void)
+xfs_uuid_table_destroy(void)

I'd drop this rename. Free works just fine here as a name.

Quoted 6 lines
fs/xfs/xfs_mount.c +2 -0
+	if (!xfs_uuid_search(uuid))
+		return xfs_uuid_insert(uuid);
 
 	xfs_warn(mp, "Filesystem has duplicate UUID %pU - can't mount", 

uuid);
return -EINVAL;

Just return an error here if xfs_uuid_search finds something, and then open code the insert in the straight line path.

Quoted 5 lines
fs/xfs/xfs_mount.c +0 -0
@@ -110,22 +119,12 @@ xfs_uuid_unmount(
 	struct xfs_mount	*mp)
 {
 	uuid_t			*uuid = &mp->m_sb.sb_uuid;
 
Quoted 7 lines

fs/xfs/xfs_mount.c xfs_uuid_unmount( · line 126

Quoted 4 lines
fs/xfs/xfs_mount.c +2 -0
 	if (xfs_has_nouuid(mp))
 		return;
+	xfs_uuid_delete(uuid);
+	return;

No need for the last return. Also I think you can just open code xfs_uuid_delete here.

Thank you for all the comments! I will do all the changes.

Signature · 1 line
-lhe