linux-kernel - Re: what is necessary for directory hard links

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Date:	Tue, 25 Jul 2006 10:47:54 -0400
From:	"Horst H. von Brand" <vonbrand@....utfsm.cl>
To:	"Joshua Hudson" <joshudson@...il.com>
cc:	linux-kernel@...r.kernel.org
Subject: Re: what is necessary for directory hard links 

Joshua Hudson <joshudson@...il.com> wrote:

[...]

> Maybe someday I'll work out a system by which much less is locked.
> Conceptually, all that is requred to lock for the algorithm
> to work is creating hard-links to directories and renaming directories
> cross-directory.

Some 40 years of filesystem development without finding a solution to that
conundrum would make that quite unlikely, but you are certainly welcome to
try.

> > (which it isn't)
> Counterexample? I should swear that any cycle created by rename must
> pass through the new parent into the victim and back to the new
> parent.

Right. The problem is that the fan-out can be humongous. In the worst case
(which you /have/ to handle right!) you need to look over /all/ the
directories in the filesystem. Meanwhile, you can't allow any operation
that changes the graph. Have you run fsck(8) lately? That should give you
an order-of-magnitude estimate for the time it could take...

Yes, in the "avergage case" it will be much, much less, but that is little
comfort for people who get bitten by "not so average" cases.

Remember that one of the things that made Linus unhappy with Minix was
exactly that the filesystem was single-threaded. Today's requirements for
Linux filesystem performance are /much/ higer than the ones of a lone hobby
user...
-- 
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/