Re: [U-Boot] [PATCH 8/8] JFFS2: Use merge sort when parsing filesystem
Hello Mark,
Am 29.06.2015 um 07:02 schrieb Mark Tomlinson:
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.tomlin...@alliedtelesis.co.nz
---
fs/jffs2/Makefile| 1 +
fs/jffs2/jffs2_1pass.c | 47
fs/jffs2/jffs2_private.h | 4 +++
fs/jffs2/mergesort.c | 70
4 files changed, 86 insertions(+), 36 deletions(-)
create mode 100644 fs/jffs2/mergesort.c
diff --git a/fs/jffs2/Makefile b/fs/jffs2/Makefile
index 4cb0600..90524ba 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-y += mergesort.o
obj-y += mini_inflate.o
diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 26a748f..a456650 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -125,7 +125,6 @@
#include jffs2_private.h
-
This change has nothing to do with your commit message ...
#define NODE_CHUNK 1024/* size of memory allocation chunk in
b_nodes */
#define SPIN_BLKSIZE18 /* spin after having scanned 1BLKSIZE
bytes */
@@ -545,49 +544,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;
}
@@ -1788,6 +1757,12 @@ 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 658b325..06b6ca2 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 000..10ecc8d
--- /dev/null
+++ b/fs/jffs2/mergesort.c
@@ -0,0 +1,70 @@
+/*
+ * This file is copyright 2001 Simon Tatham.
+ * Rewritten from original source 2006 by Dan Merillat for use in u-boot.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the Software), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED AS IS, WITHOUT
[U-Boot] [PATCH 8/8] 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.tomlin...@alliedtelesis.co.nz
---
fs/jffs2/Makefile| 1 +
fs/jffs2/jffs2_1pass.c | 47
fs/jffs2/jffs2_private.h | 4 +++
fs/jffs2/mergesort.c | 70
4 files changed, 86 insertions(+), 36 deletions(-)
create mode 100644 fs/jffs2/mergesort.c
diff --git a/fs/jffs2/Makefile b/fs/jffs2/Makefile
index 4cb0600..90524ba 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-y += mergesort.o
obj-y += mini_inflate.o
diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c
index 26a748f..a456650 100644
--- a/fs/jffs2/jffs2_1pass.c
+++ b/fs/jffs2/jffs2_1pass.c
@@ -125,7 +125,6 @@
#include jffs2_private.h
-
#defineNODE_CHUNK 1024/* size of memory allocation chunk in
b_nodes */
#defineSPIN_BLKSIZE18 /* spin after having scanned 1BLKSIZE
bytes */
@@ -545,49 +544,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;
}
@@ -1788,6 +1757,12 @@ 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 658b325..06b6ca2 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 000..10ecc8d
--- /dev/null
+++ b/fs/jffs2/mergesort.c
@@ -0,0 +1,70 @@
+/*
+ * This file is copyright 2001 Simon Tatham.
+ * Rewritten from original source 2006 by Dan Merillat for use in u-boot.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the Software), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED AS IS, WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A
