From patchwork Wed Jul 1 04:38:29 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mark Tomlinson X-Patchwork-Id: 489867 X-Patchwork-Delegate: trini@ti.com Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from theia.denx.de (theia.denx.de [85.214.87.163]) by ozlabs.org (Postfix) with ESMTP id 0A2DE140AF3 for ; Wed, 1 Jul 2015 14:40:05 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=alliedtelesis.co.nz header.i=@alliedtelesis.co.nz header.b=MxyjXopJ; dkim-atps=neutral Received: from localhost (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id 91DEA4B689; Wed, 1 Jul 2015 06:39:42 +0200 (CEST) Received: from theia.denx.de ([127.0.0.1]) by localhost (theia.denx.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 83Evl11fC0Di; Wed, 1 Jul 2015 06:39:42 +0200 (CEST) Received: from theia.denx.de (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id C3AE44B6A2; Wed, 1 Jul 2015 06:39:18 +0200 (CEST) Received: from localhost (localhost [127.0.0.1]) by theia.denx.de (Postfix) with ESMTP id 0AD7D4A039 for ; Wed, 1 Jul 2015 06:39:02 +0200 (CEST) Received: from theia.denx.de ([127.0.0.1]) by localhost (theia.denx.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 2l-Gag5NqiEU for ; Wed, 1 Jul 2015 06:39:01 +0200 (CEST) X-policyd-weight: NOT_IN_SBL_XBL_SPAMHAUS=-1.5 NOT_IN_SPAMCOP=-1.5 NOT_IN_BL_NJABL=-1.5 (only DNSBL check requested) Received: from gate2.alliedtelesis.co.nz (gate2.alliedtelesis.co.nz [202.36.163.20]) by theia.denx.de (Postfix) with ESMTPS id 33DE54A03A for ; Wed, 1 Jul 2015 06:39:00 +0200 (CEST) Received: from mmarshal3.atlnz.lc (mmarshal3.atlnz.lc [10.32.18.43]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by gate2.alliedtelesis.co.nz (Postfix) with ESMTPS id 8FA4D825A6; Wed, 1 Jul 2015 16:38:53 +1200 (NZST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=alliedtelesis.co.nz; s=mail; t=1435725533; bh=gDAmZwkPi/Wn5xuE4viyAkum/hWmMX92BqiSF3jVt6Y=; h=From:To:Cc:Subject:Date:In-Reply-To:References; b=MxyjXopJUoIp39A/Osd1nLpT7xpb4zYPacPW+SRTeHiMKt3JB4xuFiIKtYqaDUn7n a9KoWuER4UFN7AHDvb9csHSMC58TuPSweylFhe8SKv8P5ueu3G+bNnVVxSMOIiOgTX oTb/L2ddEQkmrGcs4Nv7qZq6AHZVlDz9LiWLMy2E= Received: from smtp (Not Verified[10.32.16.33]) by mmarshal3.atlnz.lc with Trustwave SEG (v7, 3, 0, 7277) id ; Wed, 01 Jul 2015 16:38:49 +1200 Received: from markto-dl.ws.atlnz.lc (markto-dl.ws.atlnz.lc [10.33.24.11]) by smtp (Postfix) with ESMTP id 5591913F08A; Wed, 1 Jul 2015 16:36:23 +1200 (NZST) Received: by markto-dl.ws.atlnz.lc (Postfix, from userid 1155) id 544DD2FFD11; Wed, 1 Jul 2015 16:38:45 +1200 (NZST) From: Mark Tomlinson To: u-boot@lists.denx.de Date: Wed, 1 Jul 2015 16:38:29 +1200 Message-Id: <1435725509-12300-9-git-send-email-mark.tomlinson@alliedtelesis.co.nz> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1435725509-12300-1-git-send-email-mark.tomlinson@alliedtelesis.co.nz> References: <1435725509-12300-1-git-send-email-mark.tomlinson@alliedtelesis.co.nz> Cc: trini@konsulko.com, Mark Tomlinson Subject: [U-Boot] [PATCH v2 8/8] JFFS2: Use merge sort when parsing filesystem X-BeenThere: u-boot@lists.denx.de X-Mailman-Version: 2.1.15 Precedence: list List-Id: U-Boot discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: u-boot-bounces@lists.denx.de Sender: "U-Boot" 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 --- Changes in v2: - Changed copyright notice to use SPDX-Licence-Identifier. - Added URL to original mergesort code. - Removed #ifdef, using Makefile change instead. fs/jffs2/Makefile | 1 + fs/jffs2/jffs2_1pass.c | 47 +++++++++++-------------------------------- fs/jffs2/jffs2_private.h | 4 ++++ fs/jffs2/mergesort.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 69 insertions(+), 35 deletions(-) create mode 100644 fs/jffs2/mergesort.c diff --git a/fs/jffs2/Makefile b/fs/jffs2/Makefile index 4cb0600..3625d74 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 4325792..64f5542 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 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..6e633a1 --- /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 +#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; +}