Builder: file dump order does not match prefetch list

[hangvane]

Additional Information

The following information is very important in order to help us to help you. Omission of the following details may delay your support request or receive no attention at all.

The order of files/paths in the provided prefetch list is not used to guide the file dump order currently, since the dump order is built by iterating Tree and check if node is in the prefetch list;

nydus/builder/src/core/bootstrap.rs

Lines 160 to 167 in 767adcf

	if !child_node.is_dir() && ctx.fs_version.is_v6() {
	child_node.v6_set_offset(bootstrap_ctx, v6_hardlink_offset, block_size)?;
	}
	ctx.prefetch.insert_if_need(&child.node, child_node.deref());
	if child_node.is_dir() {
	dirs.push(child);
	}
	}

Besides, the tree is iterated at least two times. For the first time is to build prefetch.files:

nydus/builder/src/core/bootstrap.rs

Line 175 in 767adcf

Self::build_rafs(ctx, bootstrap_ctx, dir)?;

For the second time is to classify the nodes in tree into prefetch and non-prefetch, with the need of prefetch.files to be BTreeMap for supporting random searching:

nydus/builder/src/core/layout.rs

Lines 32 to 39 in 767adcf

	tree.walk_bfs(true, &mut |n| -> Result<()> {
	let node = n.lock_node();
	// Ignore lower layer node when dump blob
	if !prefetch.contains(node.deref()) && Self::should_dump_node(node.deref()) {
	inodes.push(n.node.clone());
	}
	Ok(())
	})?;

Seems it's better to iterate tree only once to build the prefetch Vec<Node> and non-prefetch Vec<Node> in build_rafs(), and then sort the prefetch Vec<Node> by the order of the provided prefetch list.