[PATCH v2] erofs-utils: mkfs: emit an inode's xattrs in a canonical order

listxattr(2) makes no promise about the order it reports, and
filesystems disagree: tmpfs reports them in insertion order on recent
kernels (or in a random order on older ones), while ext4 and btrfs
report their own on-disk order.

mkfs.erofs stored an inode's attributes in exactly the order it received
them, so staging the same tree on different filesystems (or on older
kernels merely twice in the same place) produced images that differed
byte for byte. That made EROFS images unreproducible.

Insert into the inode's list ordered by attribute name instead, and move
inline attributes onto the on-stack list with list_add_tail() so the
emitted order matches. The shared attribute pool already sorts by the
same key, so generalize comp_shared_xattritem() into
erofs_comp_xattritem() and use it for both.

The length tiebreak previously returned only 0 or 1, never a negative
value; make it a proper three-way comparison with cmpsgn().

Suggested-by: Gao Xiang <[email protected]>
Signed-off-by: Martin Pitt <[email protected]>
---
v1: https://lore.kernel.org/linux-erofs/[email protected]

v2:
 - Reuse the shared pool's comparator for the per-inode list, as suggested by
   Gao Xiang, instead of adding a separate comp_inode_xattritem().
 - Use cmpsgn() for the length tiebreak, which returned only 0 or 1 before.
 - Reword the commit message: the order differs between filesystems, it is not
   specific to tmpfs varying it per inode. Measured with Fedora kernels,
   7.1.4-204.fc44 reports a random order per inode on tmpfs while
   7.1.5-201.fc44 reports insertion order.

Verified with a script that stages the same tree, with ten user.validatefs.*
attributes on the root inode, in /tmp (tmpfs) and /var/tmp (disk backed), and
compares the resulting images: 1.9.2 produces four distinct images from six
identical trees, this patch produces one. Three attributes are not enough to
expose an ordering bug, which is why the script sets ten.

 lib/xattr.c | 54 ++++++++++++++++++++++++++++++-----------------------
 1 file changed, 31 insertions(+), 23 deletions(-)

diff --git a/lib/xattr.c b/lib/xattr.c
index 051fdd8..f6bd8de 100644
--- a/lib/xattr.c
+++ b/lib/xattr.c
@@ -400,17 +400,43 @@ static struct erofs_xattritem *erofs_get_selabel_xattr(struct erofs_sb_info *sbi
 	return NULL;
 }
 
+static int erofs_comp_xattritem(const void *a, const void *b)
+{
+	const struct erofs_xattritem *ia, *ib;
+	unsigned int la, lb;
+	int ret;
+
+	ia = *((const struct erofs_xattritem **)a);
+	ib = *((const struct erofs_xattritem **)b);
+	la = EROFS_XATTR_KVSIZE(ia->len);
+	lb = EROFS_XATTR_KVSIZE(ib->len);
+
+	ret = memcmp(ia->kvbuf, ib->kvbuf, min(la, lb));
+	if (ret != 0)
+		return ret;
+	return cmpsgn(la, lb);
+}
+
 static int erofs_inode_xattr_add(struct list_head *hlist,
 				 struct erofs_xattritem *item)
 {
-	struct erofs_inode_xattr_node *node;
+	struct erofs_inode_xattr_node *node, *pos;
 
 	node = malloc(sizeof(*node));
 	if (!node)
 		return -ENOMEM;
 	init_list_head(&node->list);
 	node->item = item;
-	list_add(&node->list, hlist);
+
+	/*
+	 * Order each inode's xattrs by name so that images stay reproducible.
+	 * listxattr(2) makes no promise about the order it reports, and
+	 * filesystems disagree: insertion order, on-disk order, or random.
+	 */
+	list_for_each_entry(pos, hlist, list)
+		if (erofs_comp_xattritem(&item, &pos->item) < 0)
+			break;
+	list_add_tail(&node->list, &pos->list);
 	return 0;
 }
 
@@ -843,24 +869,6 @@ static unsigned int erofs_cleanxattrs(struct erofs_xattrmgr *xamgr,
 	return count;
 }
 
-static int comp_shared_xattritem(const void *a, const void *b)
-{
-	const struct erofs_xattritem *ia, *ib;
-	unsigned int la, lb;
-	int ret;
-
-	ia = *((const struct erofs_xattritem **)a);
-	ib = *((const struct erofs_xattritem **)b);
-	la = EROFS_XATTR_KVSIZE(ia->len);
-	lb = EROFS_XATTR_KVSIZE(ib->len);
-
-	ret = memcmp(ia->kvbuf, ib->kvbuf, min(la, lb));
-	if (ret != 0)
-		return ret;
-
-	return la > lb;
-}
-
 int erofs_xattr_flush_name_prefixes(struct erofs_importer *im, bool plain)
 {
 	const struct erofs_importer_params *params = im->params;
@@ -1010,7 +1018,7 @@ int erofs_load_shared_xattrs_from_path(struct erofs_sb_info *sbi, const char *pa
 	}
 	DBG_BUGON(i != sharedxattr_count);
 	sorted_n[i] = NULL;
-	qsort(sorted_n, sharedxattr_count, sizeof(n), comp_shared_xattritem);
+	qsort(sorted_n, sharedxattr_count, sizeof(n), erofs_comp_xattritem);
 
 	buf = calloc(1, shared_xattrs_size);
 	if (!buf) {
@@ -1091,10 +1099,10 @@ char *erofs_export_xattr_ibody(struct erofs_inode *inode)
 		item = node->item;
 		list_del(&node->list);
 
-		/* move inline xattrs to the onstack list */
+		/* move inline xattrs to the onstack list, order preserved */
 		if (item->shared_xattr_id < 0 ||
 		    header->h_shared_count >= UCHAR_MAX) {
-			list_add(&node->list, &ilst);
+			list_add_tail(&node->list, &ilst);
 			continue;
 		}
 
-- 
2.55.0