summaryrefslogtreecommitdiff
path: root/fs
diff options
context:
space:
mode:
authorMark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>2015-07-01 16:38:29 +1200
committerTom Rini <trini@konsulko.com>2015-08-12 20:47:32 -0400
commit10d3ac346f54ab9526cd352239a5906ee2b92fee (patch)
treec3dc2f4c0df60a876aba4de9b962bd84d6b570e5 /fs
parent54a883840be500cbcda4903118dd571e4532e83f (diff)
JFFS2: Use merge sort when parsing filesystem
When building the file system the existing code does an insertion into a linked list. It attempts to speed this up by keeping a pointer to where the last entry was inserted but it's still slow. Now the nodes are just inserted into the list without searching through for the correct place. This unsorted list is then sorted once using mergesort after all the entries have been added to the list. This speeds up the scanning of the flash file system considerably. Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
Diffstat (limited to 'fs')
-rw-r--r--fs/jffs2/Makefile1
-rw-r--r--fs/jffs2/jffs2_1pass.c47
-rw-r--r--fs/jffs2/jffs2_private.h4
-rw-r--r--fs/jffs2/mergesort.c52
4 files changed, 69 insertions, 35 deletions
diff --git a/fs/jffs2/Makefile b/fs/jffs2/Makefile
index 4cb0600cf9b..3625d748d57 100644
--- a/fs/jffs2/Makefile
+++ b/fs/jffs2/Makefile
@@ -10,4 +10,5 @@ obj-y += compr_rtime.o
obj-y += compr_rubin.o
obj-y += compr_zlib.o
obj-y += jffs2_1pass.o
+obj-$(CONFIG_SYS_JFFS2_SORT_FRAGMENTS) += mergesort.o
obj-y += mini_inflate.o
diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 432579239d9..64f55425df5 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -545,49 +545,19 @@ static struct b_node *
insert_node(struct b_list *list, u32 offset)
{
struct b_node *new;
-#ifdef CONFIG_SYS_JFFS2_SORT_FRAGMENTS
- struct b_node *b, *prev;
-#endif
if (!(new = add_node(list))) {
putstr("add_node failed!\r\n");
return NULL;
}
new->offset = offset;
+ new->next = NULL;
-#ifdef CONFIG_SYS_JFFS2_SORT_FRAGMENTS
- if (list->listTail != NULL && list->listCompare(new, list->listTail))
- prev = list->listTail;
- else if (list->listLast != NULL && list->listCompare(new, list->listLast))
- prev = list->listLast;
+ if (list->listTail != NULL)
+ list->listTail->next = new;
else
- prev = NULL;
-
- for (b = (prev ? prev->next : list->listHead);
- b != NULL && list->listCompare(new, b);
- prev = b, b = b->next) {
- list->listLoops++;
- }
- if (b != NULL)
- list->listLast = prev;
-
- if (b != NULL) {
- new->next = b;
- if (prev != NULL)
- prev->next = new;
- else
- list->listHead = new;
- } else
-#endif
- {
- new->next = (struct b_node *) NULL;
- if (list->listTail != NULL) {
- list->listTail->next = new;
- list->listTail = new;
- } else {
- list->listTail = list->listHead = new;
- }
- }
+ list->listHead = new;
+ list->listTail = new;
return new;
}
@@ -1800,6 +1770,13 @@ jffs2_1pass_build_lists(struct part_info * part)
}
free(buf);
+#if defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS)
+ /*
+ * Sort the lists.
+ */
+ sort_list(&pL->frag);
+ sort_list(&pL->dir);
+#endif
putstr("\b\b done.\r\n"); /* close off the dots */
/* We don't care if malloc failed - then each read operation will
diff --git a/fs/jffs2/jffs2_private.h b/fs/jffs2/jffs2_private.h
index 658b3252190..06b6ca29194 100644
--- a/fs/jffs2/jffs2_private.h
+++ b/fs/jffs2/jffs2_private.h
@@ -98,4 +98,8 @@ data_crc(struct jffs2_raw_inode *node)
}
}
+#if defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS)
+/* External merge sort. */
+int sort_list(struct b_list *list);
+#endif
#endif /* jffs2_private.h */
diff --git a/fs/jffs2/mergesort.c b/fs/jffs2/mergesort.c
new file mode 100644
index 00000000000..6e633a11338
--- /dev/null
+++ b/fs/jffs2/mergesort.c
@@ -0,0 +1,52 @@
+/*
+ * This file is copyright 2001 Simon Tatham.
+ * Rewritten from original source 2006 by Dan Merillat for use in u-boot.
+ *
+ * Original code can be found at:
+ * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
+ *
+ * SPDX-License-Identifier: MIT
+ */
+
+#include <common.h>
+#include "jffs2_private.h"
+
+int sort_list(struct b_list *list)
+{
+ struct b_node *p, *q, *e, **tail;
+ int k, psize, qsize;
+
+ if (!list->listHead)
+ return 0;
+
+ for (k = 1; k < list->listCount; k *= 2) {
+ tail = &list->listHead;
+ for (p = q = list->listHead; p; p = q) {
+ /* step 'k' places from p; */
+ for (psize = 0; q && psize < k; psize++)
+ q = q->next;
+ qsize = k;
+
+ /* two lists, merge them. */
+ while (psize || (qsize && q)) {
+ /* merge the next element */
+ if (psize == 0 ||
+ ((qsize && q) &&
+ list->listCompare(p, q))) {
+ /* p is empty, or p > q, so q next */
+ e = q;
+ q = q->next;
+ qsize--;
+ } else {
+ e = p;
+ p = p->next;
+ psize--;
+ }
+ e->next = NULL; /* break accidental loops. */
+ *tail = e;
+ tail = &e->next;
+ }
+ }
+ }
+ return 0;
+}