[Crash-utility] [PATCH] Speed up usage of a flat makedumpfile vmcore.

[Don Slutz]

Using a bubble sort is slow, switch to an insertion sort.

bubble sort:     real    3m45.168s

insertion sort:  real    0m3.164s

Signed-off-by: Don Slutz <dslutz at verizon.com>
---
I do have a big (32G sized file, that gzipped is 357M).
let me know if you want it.
It is the same as the xen rename of dom0

 makedumpfile.c | 56 +++++++++++++++++++++++++-------------------------------
 1 file changed, 25 insertions(+), 31 deletions(-)

diff --git a/makedumpfile.c b/makedumpfile.c
index f6834b9..c76e22c 100644
--- a/makedumpfile.c
+++ b/makedumpfile.c
@@ -56,8 +56,10 @@ store_flat_data_array(char *file, struct flat_data **fda)
 {
 	int			result = FALSE, fd;
 	int64_t			offset_fdh;
+	int64_t			offset_report = 0;
 	unsigned long long	num_allocated = 0;
 	unsigned long long	num_stored    = 0;
+	unsigned long long	sort_idx;
 	unsigned long long	size_allocated;
 	struct flat_data	*ptr = NULL, *cur, *new;
 	struct makedumpfile_data_header	fdh;
@@ -100,11 +102,34 @@ store_flat_data_array(char *file, struct flat_data **fda)
 			break;
 		}
 		cur = ptr + num_stored;
+		sort_idx = num_stored;
+		while (sort_idx) {
+			new = ptr + --sort_idx;
+			if (new->off_rearranged >= fdh.offset) {
+				cur->off_flattened = new->off_flattened;
+				cur->off_rearranged = new->off_rearranged;
+				cur->buf_size = new->buf_size;
+				cur = new;
+			} else {
+				if (CRASHDEBUG(1) && sort_idx + 1 != num_stored) {
+					fprintf(fp,
+						"makedumpfile: Moved from %lld to %lld\n",
+						num_stored, sort_idx + 1);
+				}
+				break;
+			}
+		}
 		cur->off_flattened  = offset_fdh + sizeof(fdh);
 		cur->off_rearranged = fdh.offset;
 		cur->buf_size       = fdh.buf_size;
 		num_stored++;
 
+		if (CRASHDEBUG(1) && (fdh.offset >> 30) > (offset_report >> 30)) {
+			fprintf(fp, "makedumpfile: At %lld GiB\n",
+			      fdh.offset >> 30);
+			offset_report = fdh.offset;
+		}
+
 		/* seek for next makedumpfile_data_header. */
 		if (lseek(fd, fdh.buf_size, SEEK_CUR) < 0) {
 			error(INFO, "%s: seek error (flat format)\n", file);
@@ -121,35 +146,6 @@ store_flat_data_array(char *file, struct flat_data **fda)
 	return num_stored;
 }
 
-static void
-sort_flat_data_array(struct flat_data **fda, unsigned long long num_fda)
-{
-	unsigned long long	i, j;
-	struct flat_data	tmp, *cur_i, *cur_j;
-
-	for (i = 0; i < num_fda - 1; i++) {
-		for (j = i + 1; j < num_fda; j++) {
-			cur_i = *fda + i;
-			cur_j = *fda + j;
-
-			if (cur_i->off_rearranged < cur_j->off_rearranged)
-				continue;
-
-			tmp.off_flattened  = cur_i->off_flattened;
-			tmp.off_rearranged = cur_i->off_rearranged;
-			tmp.buf_size       = cur_i->buf_size;
-
-			cur_i->off_flattened  = cur_j->off_flattened;
-			cur_i->off_rearranged = cur_j->off_rearranged;
-			cur_i->buf_size       = cur_j->buf_size;
-
-			cur_j->off_flattened  = tmp.off_flattened;
-			cur_j->off_rearranged = tmp.off_rearranged;
-			cur_j->buf_size       = tmp.buf_size;
-		}
-	}
-}
-
 static int
 read_all_makedumpfile_data_header(char *file)
 {
@@ -161,8 +157,6 @@ read_all_makedumpfile_data_header(char *file)
 	if (retval < 0)
 		return FALSE;
 
-	sort_flat_data_array(&fda, num);
-
 	afd.num_array = num;
 	afd.array     = fda;
 
-- 
1.8.4