From 173bcff7f6950a89ee398d6058b4df8e67cf8675 Mon Sep 17 00:00:00 2001
From: Eric Biggers <ebiggers3@gmail.com>
Date: Sat, 2 May 2015 10:41:47 -0500
Subject: [PATCH] NTFS-3g capture: sort attributes by starting LCN

---
 NEWS                     |  2 ++
 include/wimlib/ntfs_3g.h |  1 +
 src/blob_table.c         |  2 +-
 src/ntfs-3g_capture.c    | 28 ++++++++++++++++++++++++++++
 4 files changed, 32 insertions(+), 1 deletion(-)

diff --git a/NEWS b/NEWS
index 7645593a..ab71b7c8 100644
--- a/NEWS
+++ b/NEWS
@@ -28,6 +28,8 @@ Version 1.8.1-BETA:
 	In mounted WIM images, the disk usage provided for each file (st_blocks)
 	is now the compressed size rather than the uncompressed size.
 
+	The performance of NTFS-3g capture mode has been slightly improved.
+
 Version 1.8.0:
 	Improved the LZX compressor.  It is now 15-20% faster than before and
 	provides a slightly better compression ratio.
diff --git a/include/wimlib/ntfs_3g.h b/include/wimlib/ntfs_3g.h
index 7eda7c12..3d92dffc 100644
--- a/include/wimlib/ntfs_3g.h
+++ b/include/wimlib/ntfs_3g.h
@@ -15,6 +15,7 @@ struct ntfs_location {
 	utf16lechar *attr_name;
 	unsigned attr_name_nchars;
 	unsigned attr_type;
+	u64 sort_key;
 };
 #endif
 
diff --git a/src/blob_table.c b/src/blob_table.c
index 39dc865b..0ddd13ad 100644
--- a/src/blob_table.c
+++ b/src/blob_table.c
@@ -448,7 +448,7 @@ cmp_blobs_by_sequential_order(const void *p1, const void *p2)
 		return tstrcmp(blob1->file_on_disk, blob2->file_on_disk);
 #ifdef WITH_NTFS_3G
 	case BLOB_IN_NTFS_VOLUME:
-		return cmp_u64(blob1->ntfs_loc->mft_no, blob2->ntfs_loc->mft_no);
+		return cmp_u64(blob1->ntfs_loc->sort_key, blob2->ntfs_loc->sort_key);
 #endif
 	default:
 		/* No additional sorting order defined for this resource
diff --git a/src/ntfs-3g_capture.c b/src/ntfs-3g_capture.c
index 75690917..c0bd9076 100644
--- a/src/ntfs-3g_capture.c
+++ b/src/ntfs-3g_capture.c
@@ -168,6 +168,30 @@ attr_type_to_wimlib_stream_type(ATTR_TYPES type)
 	}
 }
 
+/* When sorting blobs located in NTFS volumes for sequential reading, we sort
+ * first by starting LCN of the attribute if available, otherwise no sort order
+ * is defined.  This usually results in better sequential access to the volume.
+ */
+static int
+set_attr_sort_key(ntfs_inode *ni, struct ntfs_location *loc)
+{
+	ntfs_attr *na;
+	runlist_element *rl;
+
+	na = open_ntfs_attr(ni, loc);
+	if (!na)
+		return WIMLIB_ERR_NTFS_3G;
+
+	rl = ntfs_attr_find_vcn(na, 0);
+	if (rl && rl->lcn != LCN_HOLE)
+		loc->sort_key = rl->lcn;
+	else
+		loc->sort_key = 0;
+
+	ntfs_attr_close(na);
+	return 0;
+}
+
 /* Save information about an NTFS attribute (stream) to a WIM inode.  */
 static int
 scan_ntfs_attr(struct wim_inode *inode,
@@ -225,6 +249,10 @@ scan_ntfs_attr(struct wim_inode *inode,
 			blob->ntfs_loc->attr_name_nchars = name_nchars;
 		}
 
+		ret = set_attr_sort_key(ni, blob->ntfs_loc);
+		if (ret)
+			goto out_cleanup;
+
 		if (unlikely(type == AT_REPARSE_POINT)) {
 			if (blob->size < REPARSE_DATA_OFFSET) {
 				ERROR("Reparse data of \"%s\" "
-- 
2.43.0