[U-Boot] [PATCH 8/8] JFFS2: Use merge sort when parsing filesystem
Heiko Schocher denx
hs at denx.de
Tue Jun 30 11:26:34 CEST 2015
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.tomlinson at 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_BLKSIZE 18 /* spin after having scanned 1<<BLKSIZE 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 0000000..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 PARTICULAR PURPOSE AND
> + * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
> + * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
> + * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
> + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
> + * SOFTWARE.
> + */
Could you replace this license text with a SPDX-License-Identifier?
And a description from where this code comes?
See here:
http://www.denx.de/wiki/view/U-Boot/Patches#Attributing_Code_Copyrights_Sign
Thanks!
> +
> +#include <common.h>
> +#include "jffs2_private.h"
> +
> +#if defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS)
you can move this into fs/jffs2/Makefile
obj-$(CONFIG_SYS_JFFS2_SORT_FRAGMENTS) += mergesort.o
and remove this
"#if defined ..." here ...
bye,
Heiko
> +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;
> +}
> +#endif
>
--
DENX Software Engineering GmbH, Managing Director: Wolfgang Denk
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
More information about the U-Boot
mailing list