From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-kernel-owner+willy=40w.ods.org-S262712AbVGHQzm@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
	id S262712AbVGHQzm (ORCPT <rfc822;willy@w.ods.org>);
	Fri, 8 Jul 2005 12:55:42 -0400
Received: (majordomo@vger.kernel.org) by vger.kernel.org id S262722AbVGHQzl
	(ORCPT <rfc822;linux-kernel-outgoing>);
	Fri, 8 Jul 2005 12:55:41 -0400
Received: from [65.98.19.108] ([65.98.19.108]:56070 "EHLO esquilax.uhoreg.ca")
	by vger.kernel.org with ESMTP id S262712AbVGHQx0 (ORCPT
	<rfc822;linux-kernel@vger.kernel.org>);
	Fri, 8 Jul 2005 12:53:26 -0400
Date: Fri, 08 Jul 2005 12:53:11 -0400
Subject: Re: reiser4 plugins
Message-ID: <150cae2e8f3b35d4979f2d999c715089@evinrude>
MIME-Version: 1.0 (Generated by Pantomime 1.2.0)
From: Hubert Chan <hubert@uhoreg.ca>
To: Horst von Brand <vonbrand@inf.utfsm.cl>
Cc: linux-kernel@vger.kernel.org, reiserfs-list@namesys.com
In-Reply-To: <200507062150.j66Lo7UW012493@laptop11.inf.utfsm.cl>
X-Mailer: GNUMail (Version 1.2.0)
Content-Type: text/plain; charset="us-ascii"; format="flowed"
X-SA-Exim-Connect-IP: <locally generated>
X-SA-Exim-Rcpt-To: vonbrand@inf.utfsm.cl, linux-kernel@vger.kernel.org, reiserfs-list@namesys.com
X-SA-Exim-Mail-From: hubert@uhoreg.ca
X-SA-Exim-Scanned: No (on esquilax.uhoreg.ca); SAEximRunCond expanded to false
Sender: linux-kernel-owner@vger.kernel.org
X-Mailing-List: linux-kernel@vger.kernel.org

Did you mean to reply to the list?  I'm taking the liberty of sending 
my reply to the list.

On 2005-07-06 17:50:07 -0400 Horst von Brand <vonbrand@inf.utfsm.cl> 
wrote:

> Hubert Chan <hubert@uhoreg.ca> wrote:
>> On Wed, 06 Jul 2005 16:33:23 -0400, Horst von Brand 
>> <vonbrand@inf.utfsm.cl> 
>> said:
>>> Hubert Chan <hubert@uhoreg.ca> wrote:
>>>> If you can store the parents, then finding cycles (relatively)
>>>> quickly is pretty easy: before you try to make A the parent of B,
>>>> walk up the parent pointers starting from A.  If you ever reach B,
>>>> you have a cycle.  If not, you don't have a cycle.  (Hmmm.  Do I 
>>>> need
>>>> a proof of correctness for this?  It's just depth-first-search, 
>>>> which
>>>> everybody learned in their first algorithms course.)
> 
>>> Correct. And you need space for potentially a huge lot of up 
>>> pointers
>>> for each file.

Which space are you talking about?  Disk space, or memory space?

Anyways, for disk space, you're basically just doubling the size of 
the tree -- two pointers per link instead of one.

As for memory space, the DFS only takes a couple of words times the 
depth of the tree.

>> People (that I know of) don't normally have a huge lot of hardlinks 
>> to a
>> single file.
> 
> Can't rely on that...
> 
>>> And then there is the (very minor) problem is that meanwhile 
>>> /nothing/
>>> can touch the filesystem to do any change...
> 
>> If the DFS is quick, it shouldn't make much difference.
> 
>> Lock nodes as you walk up the tree, and people can change unlocked 
>> nodes
>> without harming anything.  All you need to do is make sure that no up
>> pointers get added to nodes that you've already looked at.
> 
> If somebody meanwhile tries to link an ancestor of (one of) your 
> node(s) to
> a descendent, you've got two DFSes going at once through the same 
> paths...
> a single lock won't help.

Good point.  You would need to use a counter instead of just a flag 
for the lock.

There's another problem with my proposal though (finding it is left as 
an exercise for the reader ;-) ).  I think it can be avoided, but I 
don't have the time right now to properly write it up.  (No time to 
properly write out what the problem is either.  I'm already behind on 
my work as it is!)  Maybe next week...  (Out of town this weekend.)

Anyways, you only really need to prevent creating other hard links 
while doing the DFS.  Unliking won't cause a problem -- worst that can 
happen is that the DFS gives you a false positive.  (OK, you need to 
make sure that the new parent that you're linking the child node to 
doesn't disappear from under you.)  Creating new files/directories 
won't case a problem -- they're new files/directories; they can't 
cause cycles.

> Besides, you lost the nice property of top-down lock ordering that 
> makes
> the traversal of Unix filesystems naturally deadlock-free.

Yes, I don't know much about what locks the filesystem/VFS does 
already.  I'll need to look into that.

-- 
Hubert Chan <hubert@uhoreg.ca> - http://www.uhoreg.ca/
PGP/GnuPG key: 1024D/124B61FA
Fingerprint: 96C5 012F 5F74 A5F7 1FF7  5291 AF29 C719 124B 61FA
Key available at wwwkeys.pgp.net.   Encrypted e-mail preferred.