NetBSD Problem Report #30203

From he@smistad.uninett.no  Wed May 11 20:51:39 2005
Return-Path: <he@smistad.uninett.no>
Received: from smistad.uninett.no (smistad.uninett.no [158.38.62.77])
	by narn.netbsd.org (Postfix) with ESMTP id 6EA6F63B11C
	for <gnats-bugs@gnats.NetBSD.org>; Wed, 11 May 2005 20:51:38 +0000 (UTC)
Message-Id: <20050511205136.8848021DC7D@smistad.uninett.no>
Date: Wed, 11 May 2005 22:51:36 +0200 (CEST)
From: he@uninett.no
Reply-To: he@uninett.no
To: gnats-bugs@netbsd.org
Subject: restore has apparently n^2 or worse algorithms
X-Send-Pr-Version: 3.95

>Number:         30203
>Category:       bin
>Synopsis:       restore has apparently n^2 or worse algorithms
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    bin-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Wed May 11 20:52:00 +0000 2005
>Last-Modified:  Fri Dec 01 12:39:49 +0000 2006
>Originator:     Havard Eidnes <he@uninett.no>
>Release:        NetBSD 2.0
>Organization:
	UNINETT AS
>Environment:
System: NetBSD smistad.uninett.no 2.0 NetBSD 2.0 (GENERIC) #12: Thu Dec 2 12:00:22 CET 2004 he@splitter-pine.urc.uninett.no:/work/netbsd-2-0/i386/obj/sys/arch/i386/compile/GENERIC i386
Architecture: i386
Machine: i386
>Description:
	When I last updated my system (due to a progressive disk
	failure), I upgraded from 1.6.2_STABLE to 2.0.  At that time
	I restored my backups, starting with a level 0 dump.
	My home file system is of this size:

Filesystem  Size   Used   Avail Capacity  iused    ifree  %iused  Mounted on
/dev/wd0g    61G    24G     34G    41%  2299703 13548743    14%   /home

	Note, it contains approximately 2.3 million files.
	Overwhelmingly these files can be found in my MH folders, a
	few of which are relatively large, a few with more than
	100.000 entries.

	The behaviour I noticed when doing restore of the level 0 dump
	was that after an initial activity of transfer from the remote
	system, the restore process stopped transferring data and
	instead went into CPU-busy mode.  The thing is that it took
	literally *hours* (on a 1GHz P3 system) before ot continued
	with actually reading the rest of the dump and restoring the
	files.

	I conclude that there must be some algorithms in restore which
	do not scale particularly well with some of the properties of
	the contents in my file system.

>How-To-Repeat:
	Try to restore a dump with lots of files and/or directories
	with lots of files.

	Watch it take a very long time between start of restore until
	it actually starts restoring files.

>Fix:
	Sorry, none supplied.

>Release-Note:

>Audit-Trail:

>Unformatted:

Home	PR Database Search