From owner-freebsd-current@FreeBSD.ORG  Fri Sep  3 22:52:21 2004
Return-Path: <owner-freebsd-current@FreeBSD.ORG>
Delivered-To: freebsd-current@freebsd.org
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP id 67CE616A4CE
	for <freebsd-current@FreeBSD.org>;
	Fri,  3 Sep 2004 22:52:21 +0000 (GMT)
Received: from gw.catspoiler.org (217-ip-163.nccn.net [209.79.217.163])
	by mx1.FreeBSD.org (Postfix) with ESMTP id E210843D31
	for <freebsd-current@FreeBSD.org>;
	Fri,  3 Sep 2004 22:52:20 +0000 (GMT)
	(envelope-from truckman@FreeBSD.org)
Received: from FreeBSD.org (mousie.catspoiler.org [192.168.101.2])
	by gw.catspoiler.org (8.12.11/8.12.11) with ESMTP id i83MqBJl030297;
	Fri, 3 Sep 2004 15:52:15 -0700 (PDT)
	(envelope-from truckman@FreeBSD.org)
Message-Id: <200409032252.i83MqBJl030297@gw.catspoiler.org>
Date: Fri, 3 Sep 2004 15:52:11 -0700 (PDT)
From: Don Lewis <truckman@FreeBSD.org>
To: keramida@linux.gr
In-Reply-To: <20040903221628.GA51595@gothmog.gr>
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
cc: freebsd-current@FreeBSD.org
Subject: Re: what is fsck's "slowdown"?
X-BeenThere: freebsd-current@freebsd.org
X-Mailman-Version: 2.1.1
Precedence: list
List-Id: Discussions about the use of FreeBSD-current
	<freebsd-current.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>,
	<mailto:freebsd-current-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-current>
List-Post: <mailto:freebsd-current@freebsd.org>
List-Help: <mailto:freebsd-current-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>,
	<mailto:freebsd-current-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Fri, 03 Sep 2004 22:52:21 -0000

On  4 Sep, Giorgos Keramidas wrote:
> On 2004-09-03 14:58, Don Lewis <truckman@freebsd.org> wrote:

>> Using two CPUs would give you at best a 2x speedup, and in this case it
>> would be quite a bit less since both CPUs would be trying to access and
>> modify the same data structure.  Just using a better data structure is
>> likely to speed things up much more than 2x.  Something as simple as
>> building the list in reverse order in pass 1 is likely to make a huge
>> difference.
> 
> Holding both a head and tail pointer to the singly-linked list should
> probably make it easier to add nodes at the end of the list instead of
> the head.  I haven't read the source of fsck_ffs at all though, so I
> don't know if I can come up with a working patch in a reasonable amount
> of time.

Yes, if fsck used the <sys/queue.h> macros, this data structure should
probably be a STAILQ.  The code if fsck is all hand rolled and it would
be trivially easy to add a tail pointer.  The head of the list in
question is
	struct zlncnt *zlnhead;
The only modifications needed would be in the initialization code in
main.c, and the code that builds the list in pass1.c.