From: =?iso-8859-1?Q?J=F6rn?= Engel Subject: Re: Expected getdents behaviour Date: Thu, 15 Sep 2005 23:47:55 +0200 Message-ID: <20050915214755.GA17212@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> <20050915174658.GA9974@wohnheim.fh-wedel.de> <20050915181946.GH22503@thunk.org> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE Cc: Jan Blunck , 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]:7662 "EHLO moskovskaya.fh-wedel.de") by vger.kernel.org with ESMTP id S1030558AbVIOVsM (ORCPT ); Thu, 15 Sep 2005 17:48:12 -0400 To: Theodore Ts'o Content-Disposition: inline In-Reply-To: <20050915181946.GH22503@thunk.org> Sender: linux-fsdevel-owner@vger.kernel.org List-Id: linux-fsdevel.vger.kernel.org On Thu, 15 September 2005 14:19:47 -0400, Theodore Ts'o wrote: > On Thu, Sep 15, 2005 at 07:46:58PM +0200, J?rn Engel wrote: > > Correct. But you're missing half of the problem. > >=20 > > 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 t= ree > > would not solve your half of the problem, so it is not a full > > solution. > >=20 > > 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. >=20 > Actually, no. What we do is return the directory entries in hash sor= t > order, by walking the btree. And we use the hash as the offset > returned in d_off and via telldir(). The reason for this? So that i= f > we add files which causes a node to split, that we still only return > files in the directory once and only once. If we traversed the tree > in sequential order only, then some files could be returned multiple > times, and some files returned not at all after a node split > operation. You are right. I understood what ext2 was doing, saw a huge problem in lookup performance (O(n)) and was given a very brief explanation of hashtrees - which apparently did not match reality. Still wouldn't a hybrid design with both a list and a tree work? It appears to be just a different style of hair, not any prettier and just as sufficient to cover all bald spots. J=F6rn --=20 A quarrel is quickly settled when deserted by one party; there is no battle unless there be two. -- 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