makefs: Make cd9660 Rock Ridge inodes reproducible

Rock Ridge extensions include an inode field:

    "POSIX File Serial Number" shall have the same meaning as and may be
    used for the st_ino field of POSIX:5.6.1. This field shall be
    recorded according to ISO 9660:7.3.3. Directory Records which share
    the value of this field are defined as links (see POSIX:2.2.2.17)
    and, by definition, point to the same file or directory.

Previously we'd store the source file's st_ino (except that in metalog
mode we'd record 0 for files with nlink = 1).  This had two issues: the
generated ISO image was nonreproducible due to the arbitrary inode
numbers, and files without hard links would falsely be detected (by
certain tools) as hard links to each other.

Note that the kernel's cd9660(5) file system ignores the Rock Ridge
PX File Serial Number, so this issue isn't observed by mounting such a
file system.

Instead of using the source inode directly, assign target inode numbers
sequentially.  Use a map so that files with the same source inode (hard
links) still receive the same target inode number.

PR:		284795
PR:		285027
Reviewed by:	brooks
Sponsored by:	The FreeBSD Foundation
Differential Revision: https://reviews.freebsd.org/D49141

2 files changed, 59 insertions, 10 deletions

diff --git a/usr.sbin/makefs/cd9660/iso9660_rrip.c b/usr.sbin/makefs/cd9660/iso9660_rrip.c
index a4ce5c09b24b..e037f1db175f 100644
--- a/usr.sbin/makefs/cd9660/iso9660_rrip.c
+++ b/usr.sbin/makefs/cd9660/iso9660_rrip.c
@@ -47,7 +47,7 @@
 #include "iso9660_rrip.h"
 #include <util.h>
 
-static void cd9660_rrip_initialize_inode(cd9660node *);
+static void cd9660_rrip_initialize_inode(iso9660_disk *, cd9660node *);
 static int cd9660_susp_handle_continuation(iso9660_disk *, cd9660node *);
 static int cd9660_susp_handle_continuation_common(iso9660_disk *, cd9660node *,
     int);
@@ -70,6 +70,9 @@ cd9660_susp_initialize(iso9660_disk *diskStructure, cd9660node *node,
 	if (node->dot_dot_record != 0)
 		TAILQ_INIT(&(node->dot_dot_record->head));
 
+	RB_INIT(&diskStructure->rr_inode_map);
+	diskStructure->rr_inode_next = 1;
+
 	 /* SUSP specific entries here */
 	if ((r = cd9660_susp_initialize_node(diskStructure, node)) < 0)
 		return r;
@@ -101,6 +104,7 @@ int
 cd9660_susp_finalize(iso9660_disk *diskStructure, cd9660node *node)
 {
 	cd9660node *temp;
+	struct inode_map_node *mapnode, *mapnodetmp;
 	int r;
 
 	assert(node != NULL);
@@ -117,6 +121,12 @@ cd9660_susp_finalize(iso9660_disk *diskStructure, cd9660node *node)
 		if ((r = cd9660_susp_finalize(diskStructure, temp)) < 0)
 			return r;
 	}
+	RB_FOREACH_SAFE(mapnode, inode_map_tree,
+	    &(diskStructure->rr_inode_map), mapnodetmp) {
+		RB_REMOVE(inode_map_tree, &(diskStructure->rr_inode_map),
+		    mapnode);
+		free(mapnode);
+	}
 	return 1;
 }
 
@@ -323,7 +333,7 @@ cd9660_susp_initialize_node(iso9660_disk *diskStructure, cd9660node *node)
 }
 
 static void
-cd9660_rrip_initialize_inode(cd9660node *node)
+cd9660_rrip_initialize_inode(iso9660_disk *diskStructure, cd9660node *node)
 {
 	struct ISO_SUSP_ATTRIBUTES *attr;
 
@@ -337,7 +347,7 @@ cd9660_rrip_initialize_inode(cd9660node *node)
 		/* PX - POSIX attributes */
 		attr = cd9660node_susp_create_node(SUSP_TYPE_RRIP,
 			SUSP_ENTRY_RRIP_PX, "PX", SUSP_LOC_ENTRY);
-		cd9660node_rrip_px(attr, node->node);
+		cd9660node_rrip_px(diskStructure, attr, node->node);
 
 		TAILQ_INSERT_TAIL(&node->head, attr, rr_ll);
 
@@ -390,7 +400,8 @@ cd9660_rrip_initialize_node(iso9660_disk *diskStructure, cd9660node *node,
 			/* PX - POSIX attributes */
 			current = cd9660node_susp_create_node(SUSP_TYPE_RRIP,
 				SUSP_ENTRY_RRIP_PX, "PX", SUSP_LOC_ENTRY);
-			cd9660node_rrip_px(current, parent->node);
+			cd9660node_rrip_px(diskStructure, current,
+			    parent->node);
 			TAILQ_INSERT_TAIL(&node->head, current, rr_ll);
 
 			/* TF - timestamp */
@@ -405,7 +416,8 @@ cd9660_rrip_initialize_node(iso9660_disk *diskStructure, cd9660node *node,
 			/* PX - POSIX attributes */
 			current = cd9660node_susp_create_node(SUSP_TYPE_RRIP,
 				SUSP_ENTRY_RRIP_PX, "PX", SUSP_LOC_ENTRY);
-			cd9660node_rrip_px(current, grandparent->node);
+			cd9660node_rrip_px(diskStructure, current,
+			    grandparent->node);
 			TAILQ_INSERT_TAIL(&node->head, current, rr_ll);
 
 			/* TF - timestamp */
@@ -422,7 +434,7 @@ cd9660_rrip_initialize_node(iso9660_disk *diskStructure, cd9660node *node,
 			TAILQ_INSERT_TAIL(&node->head, current, rr_ll);
 		}
 	} else {
-		cd9660_rrip_initialize_inode(node);
+		cd9660_rrip_initialize_inode(diskStructure, node);
 
 		if (node == diskStructure->rr_moved_dir) {
 			cd9660_rrip_add_NM(node, RRIP_DEFAULT_MOVE_DIR_NAME);
@@ -630,8 +642,45 @@ cd9660_createSL(cd9660node *node)
 	}
 }
 
+static int
+inode_map_node_cmp(struct inode_map_node *a, struct inode_map_node *b)
+{
+	if (a->key < b->key)
+		return (-1);
+	if (a->key > b->key)
+		return (1);
+	return (0);
+}
+
+RB_GENERATE(inode_map_tree, inode_map_node, entry, inode_map_node_cmp);
+
+static uint64_t
+inode_map(iso9660_disk *diskStructure, uint64_t in)
+{
+	struct inode_map_node lookup = { .key = in };
+	struct inode_map_node *node;
+
+	/*
+	 * Always assign an inode number if src inode unset.  mtree mode leaves
+	 * src inode unset for files with st_nlink == 1.
+	 */
+	if (in != 0) {
+		node = RB_FIND(inode_map_tree, &(diskStructure->rr_inode_map),
+		    &lookup);
+		if (node != 0)
+			return (node->value);
+	}
+
+	node = emalloc(sizeof(struct inode_map_node));
+	node->key = in;
+	node->value = diskStructure->rr_inode_next++;
+	RB_INSERT(inode_map_tree, &(diskStructure->rr_inode_map), node);
+	return (node->value);
+}
+
 int
-cd9660node_rrip_px(struct ISO_SUSP_ATTRIBUTES *v, fsnode *pxinfo)
+cd9660node_rrip_px(iso9660_disk *diskStructure, struct ISO_SUSP_ATTRIBUTES *v,
+    fsnode *pxinfo)
 {
 	v->attr.rr_entry.PX.h.length[0] = 44;
 	v->attr.rr_entry.PX.h.version[0] = 1;
@@ -643,8 +692,8 @@ cd9660node_rrip_px(struct ISO_SUSP_ATTRIBUTES *v, fsnode *pxinfo)
 	    v->attr.rr_entry.PX.uid);
 	cd9660_bothendian_dword(pxinfo->inode->st.st_gid,
 	    v->attr.rr_entry.PX.gid);
-	cd9660_bothendian_dword(pxinfo->inode->st.st_ino,
-	    v->attr.rr_entry.PX.serial);
+	cd9660_bothendian_dword(inode_map(diskStructure,
+	    pxinfo->inode->st.st_ino), v->attr.rr_entry.PX.serial);
 
 	return 1;
 }
diff --git a/usr.sbin/makefs/cd9660/iso9660_rrip.h b/usr.sbin/makefs/cd9660/iso9660_rrip.h
index 5e1e8b5130f0..4c738d27ba45 100644
--- a/usr.sbin/makefs/cd9660/iso9660_rrip.h
+++ b/usr.sbin/makefs/cd9660/iso9660_rrip.h
@@ -224,7 +224,7 @@ int cd9660_susp_finalize_node(iso9660_disk *, cd9660node *);
 int cd9660_rrip_finalize_node(cd9660node *);
 
 /* POSIX File attribute */
-int cd9660node_rrip_px(struct ISO_SUSP_ATTRIBUTES *, fsnode *);
+int cd9660node_rrip_px(iso9660_disk *, struct ISO_SUSP_ATTRIBUTES *, fsnode *);
 
 /* Device number */
 int cd9660node_rrip_pn(struct ISO_SUSP_ATTRIBUTES *, fsnode *);