*BSD News Article 64824


Return to BSD News archive

Path: euryale.cc.adfa.oz.au!newshost.anu.edu.au!newshost.telstra.net!act.news.telstra.net!vic.news.telstra.net!news.mira.net.au!harbinger.cc.monash.edu.au!news.rmit.EDU.AU!news.unimelb.EDU.AU!munnari.OZ.AU!news.ecn.uoknor.edu!news.cis.okstate.edu!newsfeed.ksu.ksu.edu!news.physics.uiowa.edu!math.ohio-state.edu!howland.reston.ans.net!newsfeed.internetmci.com!swrinde!sdd.hp.com!hamblin.math.byu.edu!park.uvsc.edu!usenet
From: Terry Lambert <terry@lambert.org>
Newsgroups: comp.os.linux.development.system,comp.unix.bsd.freebsd.misc
Subject: Re: Ideal filesystem
Date: 1 Apr 1996 21:54:46 GMT
Organization: Utah Valley State College, Orem, Utah
Lines: 119
Message-ID: <4jpjb6$77c@park.uvsc.edu>
References: <4hptj4$cf4@cville-srv.wam.umd.edu> <4j0bmo$ftv@park.uvsc.edu> <jlemonDoqBq5.1Bx@netcom.com> <4jerrj$f12@park.uvsc.edu> <jlemonDp1GFM.H4I@netcom.com>
NNTP-Posting-Host: hecate.artisoft.com
Xref: euryale.cc.adfa.oz.au comp.os.linux.development.system:20461 comp.unix.bsd.freebsd.misc:16444

jlemon@netcom.com (Jonathan Lemon) wrote:
] In article <4jerrj$f12@park.uvsc.edu>,
] Terry Lambert  <terry@lambert.org> wrote:
] >jlemon@netcom.com (Jonathan Lemon) wrote:
] >] Hm.  Shells just look at the inode to see if the file is executable,
] >] in order to add it to the hash list.  So what if there's some (unspecified)
] >] bit or combination of bits in the inode that indicates this directory
] >] is an "executable bundle"?  Then the search stops there.  When 'executed',
] >] the system runs "(directory_name)/a.out" or even "(directory_name)/a.out.arch".
] >
] >For a "binary" that was a directory, there is a need to search
] >every directory in every directory in the path for "a.out" or
] >whatever you call your actual non-fork binary.
] 
] Um, no.  If the directory has an 'executable' bit, then the search stops there,
] and the the actual binary within the directory is _assumed_.  This gives the 
] same behavior that we have today. (yes, the actual binary may not be present -
] this would be discovered when the user attempts to execute the program, and
] would be handled the same way as a corrupted binary)


Bzzzzzzzzzzzzzzzzzzt.$home/bin

% set path = ( $home/bin $path /usr/X11/bin)
% rehash
% /bin/ls $home/bin
foo             ls
% /bin/ls $home/bin/foo
a.out           icon             eattr1           eattr2
% /bin/ls $home/bin/ls
icon            eattr1
% ls
ls: Command not found


In other words, the hash will be true, but the search will be
false -- and the wrong ls will be given.

Whereas if you looked for the a.out, you would avoid this problem.

] >This is geometrically more time consuming than simply searching only
] >directories in the path, to a single iteration level.
] 
] no - see above.

Yes, see above (where an "executable" lives in the path and is
hashed, but is not 'executable').

> 
> >
> >Using directories as binaries has the singular benefit that
> >you can abuse the file system in the same way the terminfo
> >database abuses thefile system to use the directory structure
> >as an index.
> 
> The directory structure of a filesystem _is_ an index - an index of files.
> What's wrong with using an index as an index?

A real index would be searchable in O(log2(n)+1) compares for
a total of n entries, whereas a directory used as an index
varies by implementation, and is never better than that, and
is more frequently simply O(n/2+1).

] >Shell hashing is only one example.  Another example is that an
] >a.out from an "executable" could land in lost+found, losing
] >its association with the program it belongs to.  This is an
] >impossible situation with EA's, which have a single focal file
] >system object that is treated atmoically by the underlying FS
] >code -- unlike "a.out" files in "binary" directories.
] 
] Um.  My understanding of EA's, as being discussed, is something like an 
] inode list, eg, each 'fork' has its own inode, but only one 'root' inode 
] appears in the filesystem.  Or put another way, since we aren't imposing a 
] limit on the number of EA's, and we can't have an infinitely sized inode,
] there has to be some kind of extension mechanism.  Now, the only 'atomicity'
] is provided by disk blocks.  As soon as we start using these "extended" inodes,
] meaning they are scattered across the disk, that 'atomicity' is gone.
] 
] lost+found only comes into play when the filesystem is damaged.  What is to 
] prevent a 'sub-node' from getting lost? 

The fact that it is not stored as a subnode in a correct
implementation.

Specifically, if an entry is made in a directory, it is possible
for the imposition of heirarchy to lose tight binding with the
name space of the directory.

It doesn't matter if this is a real directory, in the classical
sense, or an index directory in an inode entry.

By restricting the allowable entry manipulations to not include
exposure in the FS namespace, the implementation can prevent it
from ever being possible to dissociated a fork from the node
that contains it.

The failure mode in the directories is from the lack of a parent
pointer due to its exposure in the FS name space, specifically,
the way in which hard links are currently implemented.

A fork is not a hard link, and if it is to not be limited by the
size of an on disk inode structure, it must not be associated
the same way inodes are associated with names.

To think of it another way, DOS, OS/2, NetWare, and NTFS can not
lose file names because they are not directory entries, they are
attributes of the file.  UNIX can, because logically names are
not attributes.

You are suggesting implementing attributes as "not attributes"
in the same sense.


					Regards,
                                        Terry Lambert
                                        terry@cs.weber.edu
---
Any opinions in this posting are my own and not those of my present
or previous employers.