From owner-freebsd-current@FreeBSD.ORG Fri Sep 3 22:31:17 2004 Return-Path: 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 12FAC16A5A1; Fri, 3 Sep 2004 22:31:17 +0000 (GMT) Received: from kane.otenet.gr (kane.otenet.gr [195.170.0.27]) by mx1.FreeBSD.org (Postfix) with ESMTP id 55CC843D46; Fri, 3 Sep 2004 22:31:15 +0000 (GMT) (envelope-from keramida@linux.gr) Received: from gothmog.gr (patr530-a148.otenet.gr [212.205.215.148]) i83MVBaF029519; Sat, 4 Sep 2004 01:31:12 +0300 Received: from gothmog.gr (gothmog [127.0.0.1]) by gothmog.gr (8.13.1/8.13.1) with ESMTP id i83MGSqa070798; Sat, 4 Sep 2004 01:16:28 +0300 (EEST) (envelope-from keramida@linux.gr) Received: (from giorgos@localhost) by gothmog.gr (8.13.1/8.13.1/Submit) id i83MGSkH070797; Sat, 4 Sep 2004 01:16:28 +0300 (EEST) (envelope-from keramida@linux.gr) Date: Sat, 4 Sep 2004 01:16:28 +0300 From: Giorgos Keramidas To: Don Lewis Message-ID: <20040903221628.GA51595@gothmog.gr> References: <20040903175434.A812@ganymede.hub.org> <200409032158.i83LwdWg030214@gw.catspoiler.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200409032158.i83LwdWg030214@gw.catspoiler.org> Phone: +30-2610-312145 Mobile: +30-6944-116520 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 03 Sep 2004 22:31:17 -0000 On 2004-09-03 14:58, Don Lewis wrote: > > Would the file system in question happen to be full of UNREF files that > fsck is deleting? > > I just took a look at the sparsely commented fsck code and it looks like > fsck builds a list of inodes that have a zero link count during pass 1. > During pass 4 fsck visits each inode that it has marked as being in > either the FSTATE or DFOUND states, and either adjusts the inodes link > count, or of the link count is zero, it removes the inode from the list > it constructed in pass 1 and clears the inode. > > Because this list is just a linear linked list and inodes are prepended > to the beginning in increasing inode order, and inodes are removed in > increasing inode order, it looks like the entire list needs to be > traversed each time an inode is removed. That would cause the run time > to increase as the square of the number of UNREF'ed inodes. > > 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.