From: =?iso-8859-1?Q?J=F6rn?= Engel Subject: Re: Expected getdents behaviour Date: Thu, 15 Sep 2005 19:46:58 +0200 Message-ID: <20050915174658.GA9974@wohnheim.fh-wedel.de> References: <1126793268.1676.9.camel@imp.csi.cam.ac.uk> <1126793558.1676.15.camel@imp.csi.cam.ac.uk> <1126797460.1676.23.camel@imp.csi.cam.ac.uk> <20050915164110.GA25573@hasse.suse.de> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE Cc: Anton Altaparmakov , miklos@szeredi.hu, aaranya@cs.sunysb.edu, linux-fsdevel@vger.kernel.org Return-path: Received: from mail.fh-wedel.de ([213.39.232.198]:52963 "EHLO moskovskaya.fh-wedel.de") by vger.kernel.org with ESMTP id S1030556AbVIORrX (ORCPT ); Thu, 15 Sep 2005 13:47:23 -0400 To: Jan Blunck Content-Disposition: inline In-Reply-To: <20050915164110.GA25573@hasse.suse.de> Sender: linux-fsdevel-owner@vger.kernel.org List-Id: linux-fsdevel.vger.kernel.org On Thu, 15 September 2005 18:41:10 +0200, Jan Blunck wrote: >=20 > No, thats not true. The file position in a regular (flat) file is com= pletely > up to the user. "Thanks" to the short-comings of POSIX on not definin= g the > functions on directories, the file position in a directory is complet= ely up to > the file system. Due to that fact, modern file systems don't need to = provide > a "flat" view (in terms of sequential access to a directory file) on > them. Although, the file system must guarantee, that readdir's must n= ot fail > because of changes directory contents. AFAIR ext2 is achieving this t= hrough > not shrinking directories while the filesystem is online. Correct. But you're missing half of the problem. The other half is getting O(1) or O(ln(n)) performance for lookup on a large directory. Solution to this half alone would be to use a balanced tree for directory entries. Now, using a self-balancing tree would not solve your half of the problem, so it is not a full solution. Ext2, as far as I understand it, solved both halves by having both a hashtree and the sequential list. Getdents is walking the list and ignoring entries with the "deleted" flag. Lookup is using the hashtree, which points to the list for actual data. J=F6rn --=20 All art is but imitation of nature. -- Lucius Annaeus Seneca - To unsubscribe from this list: send the line "unsubscribe linux-fsdevel= " in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html