From owner-freebsd-stable@FreeBSD.ORG Fri Jan 13 04:10:37 2012 Return-Path: Delivered-To: freebsd-stable@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id A6C8F106566C; Fri, 13 Jan 2012 04:10:37 +0000 (UTC) (envelope-from yanegomi@gmail.com) Received: from mail-iy0-f182.google.com (mail-iy0-f182.google.com [209.85.210.182]) by mx1.freebsd.org (Postfix) with ESMTP id 609D88FC0C; Fri, 13 Jan 2012 04:10:37 +0000 (UTC) Received: by iazz13 with SMTP id z13so5542621iaz.13 for ; Thu, 12 Jan 2012 20:10:36 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=b0z39GZiSxIOERzv1gZnvtYthyxAQGdRj/CgfNXSpxk=; b=bNpJUzEm1FQJ3eVx4PAwPX4l60QWKrzCU13aS0nv6hPEiv8FeL0KosuSpX0PIlPYbO Lpx1owq3s0KkDlYU8dzhSyyVnWDmEPNVv63D9FJpRCgtiIVz7wANRgH/wLtO+3h2clzg 3Fbvwz9GgYqIdy+/3sZx9TaUVbkRGkWWZz3Yw= MIME-Version: 1.0 Received: by 10.50.187.226 with SMTP id fv2mr4019198igc.20.1326427836748; Thu, 12 Jan 2012 20:10:36 -0800 (PST) Received: by 10.182.152.6 with HTTP; Thu, 12 Jan 2012 20:10:36 -0800 (PST) In-Reply-To: <4F0FA3C8.2020608@missouri.edu> References: <20120111161110.4258969c.rpclark@tds.net> <20120112200843.2a348d2f.rpclark@tds.net> <4F0F8E6F.8000909@FreeBSD.org> <4F0FA3C8.2020608@missouri.edu> Date: Thu, 12 Jan 2012 20:10:36 -0800 Message-ID: From: Garrett Cooper To: Stephen Montgomery-Smith Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Cc: Andre Goree , Doug Barton , freebsd-stable@freebsd.org, Rob Clark Subject: Re: GENERIC make buildkernel error / fails - posix_fadvise X-BeenThere: freebsd-stable@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Production branch of FreeBSD source code List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 13 Jan 2012 04:10:37 -0000 On Thu, Jan 12, 2012 at 7:23 PM, Stephen Montgomery-Smith wrote: > On 01/12/2012 09:11 PM, Garrett Cooper wrote: > >> +1. And it's faster yet when you can run parallel copies of rm on >> different portions of the directory tree (e.g. xargs, find [..] -exec) >> as rm is O(n). > > > I have always wondered about that! =A0I thought that the main bottleneck = in > "rm -r" might be deleting directories which are not in the disk cache, wh= ich > then have to be copied from the disk. =A0Copying two different parts of t= he > disk into cache - well it has to be done one at a time whether the jobs > asking for the copy of the disk are going concurrently or consecutively. > > And perhaps two instances of "rm -r" acting on different parts of the har= d > drive will cause disk thrashing, so that they might even slow each other > down. Not really. The problem is limited by the fact that rm(1) needs to dive into the kernel each time it does an unlink(1) syscall. Per Prof. McKusick's teaching and the way things are designed from libc to disk -- the process is artificially like: rm -> syscall -> top-half of the kernel -> vfs -> filesystem (in my case ZFS) -> geom -> scsi layer -> storage controller/disk driver. This is super expensive as n becomes large as the path is long, so the best to amortize the operation is to run more instances in parallel as there should be a relatively low chance of there being lock contention (assuming you're not consuming too many GIANT locks, you don't overprovision your system, etc). See the loop in .../bin/rm/rm.c:rm_tree(char**) if you're curious where things have issues. > But this is all guess work on my part. > > If I am wrong, and "rm -r" does work faster when working in parallel on > different parts, Yes. Less modifications to directory entries -> less vfs locking contention and less useless writing back to disk -> better. > then why doesn't someone write the "rm" command to fork > copies of itself that work on different parts of large trees? Perhaps. The point is that my systems can do more work in parallel with a larger number of rm's in order to improve throughput. I learned this the hard way when I started deleting a prepopulated directory with pjd's fstest: it took hours to prune directory entries the O(n) way by a small fraction (<10% of 4 mil. or 40 mil. files). When I did stuff in parallel (have 8 regular cores, 8 SMT cores), the process took less than an hour to complete. Thanks, -Garrett