From mboxrd@z Thu Jan 1 00:00:00 1970 From: Heiko Schocher denx Date: Tue, 30 Jun 2015 11:26:34 +0200 Subject: [U-Boot] [PATCH 8/8] JFFS2: Use merge sort when parsing filesystem In-Reply-To: <1435554149-18042-9-git-send-email-mark.tomlinson@alliedtelesis.co.nz> References: <1435554149-18042-1-git-send-email-mark.tomlinson@alliedtelesis.co.nz> <1435554149-18042-9-git-send-email-mark.tomlinson@alliedtelesis.co.nz> Message-ID: <559260CA.7000009@denx.de> List-Id: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: u-boot@lists.denx.de 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 > --- > > 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< > @@ -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 > +#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