Subject: Re: The Joys of Linux

From: Russell King - ARM Linux Admin <[email-masked]>
Date: Mon, 19 Oct 1998 22:00:16 +0100 (BST)

Simon Glass / Linux writes:
> I think you just maintain a table of all the changes, and consult it before
> using the heuristic already used for read-only.
> 
> After all, DOS works!

I know dos works, but DOS doesn't have the entries in it's directories moving
position randomly when you delete files.  DOS uses the location of the directory
and the position within the directory to calculate an inode number.

In read-only ADFS, I do the same thing - an inode number of a file consists of
the parent (directory) object id and it's location within the object.  This
works because the directory entries are static when the filesystem is readonly.

You add write support, and this blows it right out of the water - eg, you look
up a file and it turns out to be the 15th entry of directory.  You generate
an inode number based on this information.  You then delete a file preceeding
the 15th entry in that directory.  This causes the 15th entry to now be the 14th
entry.

You search for what was originally the 16th entry and find it in the 15th, and
as before you generate an inode number for this based in this information.
Now for the crunch: this inode number is the same as the inode number you
generated for what is now the 14th entry (which could still be in use) and
hey presto - you're accessing the inode structure for the wrong file!

The current system of inode allocation only works *because it is read-only*.
If someone can think up a way of allocating inode numbers to a totally
dynamic filesystem without any concept of inodes, I'd be happy to hear them.

About the only thing that I can think of doing to make ADFS writable under
Linux is to ensure that when you have an inode in use which belongs to a
directory to *lock the directory against any changes* until all inodes in
that directory /and/ their cached versions have been unused/flushed.  This
means that if you have a file in use, you can't delete or rename anything
in the directory, and I think that this is far too restrictive to warrant
implementation.
   _____
  |_____| ------------------------------------------------- ---+---+-
  |   |        Russell King       [email-masked]      --- ---
  | | | |  http://www.arm.uk.linux.org/~rmk/armlinux.html    /  /  |
  | +-+-+                                                     --- -+-
  /   |               THE developer of ARM Linux              |+| /|\
 /  | | |                                                     ---  |
    +-+-+ -------------------------------------------------  /\\\  |
unsubscribe: body of `unsubscribe linux-arm' to [email-masked]

---

From: Philip Blundell <[email-masked]>
Date: Tue, 20 Oct 1998 09:26:53 +0200

>dynamic filesystem without any concept of inodes, I'd be happy to hear them.

Inode numbers don't have to mean anything at all, you can just make them up 
out of thin air.  I think the dcache makes this even easier because you can 
always have a dentry in your hand for anything that has an inode attached.

The SMB code does precisely this.  Look at linux/fs/smbfs/
inode.c:smb_invent_inos().  I imagine ADFS could be made to work with some 
similar scheme.  I'll think about it later.

p.

---

From: Toby Haynes <[email-masked]>
Date: Tue, 20 Oct 1998 12:32:51 +0100 (BST)

In programs like xpaint, xfig and freeciv (most critically!), writable
text icons don't work. Specifically, if I say load up xfig and click on
Zoom at the bottom, it produces a sub window with a '1' in it, plus OK and
cancel boxes (or something like that!). Normally I would click on this,
delete the 1 and put in a new zoom scale, but this doesn't work on my
RiscPC SA110 ARM Linux 2.0.34 system. It was installed from a set of rpms
slurped off the ARM linux distribution sometime in June or thereabouts by
droppping all the rpms onto hda3 (my linux partition) and using the
installer normally. I should stress that these writable icons have never
worked. I do note that it is possible to paste from the mouse into these
icons, but they never pick up keyboard entry. Additionally, I note that
the windows are not getting the 'focus' from FVWM - I use
focus-follows-cursor mode, and the windows are not highlighted as I would
expect. 

My suspicions lie with libXaw, but I'd like to have someone tell me that
this is the case before I reach for my SRPM collection and start
recompiling from the redhat 5.0 distribution. Or should I try a different
window manager?

Thanks,
	Toby

_______________________________________________________________________
Toby Haynes       | "Alarm clock? Oh, you mean the sad pile of
Rm 965, MRAO      |  cogs and twisted springs under that dent
Uni. of Cambridge |  in the wall?"

---

From: "Neil A. Carson" <[email-masked]>
Date: Tue, 20 Oct 1998 12:54:54 +0100

> in the directory, and I think that this is far too restrictive to warrant

Okay, so if the naame of the file is the only thing that's constant...
Can you basically use a hash table to convert between file name
(including path without leading /) and i-node number? Or given the FS
lasyersis this impossible to do?

Or maybe a combination of object ID and hashed name?

	Neil

-- 
Neil A. Carson

---

From: Philip Blundell <[email-masked]>
Date: Tue, 20 Oct 1998 14:49:48 +0200

Russell King wrote:

>My point is that there is no fixed why to generate an inode number for a file
>that you can guarantee will always refer to the file during that files
>lifetime.

Yes, I'm aware of that - *my* point was that it doesn't matter because there's 
actually no need to be able to do this.  All you need to do is invent an inode 
number, completely arbitrarily, when the VFS asks you for one.  The dcache 
will keep track of the binding between this and the filename for as long as it 
matters.

The "lifetime" of a file is a somewhat nebulous concept and as far as I know 
there is nothing that says that inode numbers have to be valid once you've let 
go of all references to the file.  If you've closed everything and the dcache 
entry has been pruned then next time you open the file you will just get a 
new, equally arbitrary, inode number which will do just as well.

p.

---

From: Russell King <[email-masked]>
Date: Tue, 20 Oct 1998 13:55:27 +0100 (BST)

My point is that there is no fixed why to generate an inode number for a file
that you can guarantee will always refer to the file during that files lifetime.

It seems to me that most people aren't reading exactly what I'm saying about
this.

--
Russell King ([email-masked])

---

From: Alan Cox <[email-masked]>
Date: Tue, 20 Oct 1998 14:42:55 +0100 (BST)

> Or maybe a combination of object ID and hashed name?

All overkill, just number them 1 2 3 4 as you open them and don't reuse
numbers already still open. 

Alan

---

From: "Neil A. Carson" <[email-masked]>
Date: Tue, 20 Oct 1998 15:14:45 +0100

> It seems to me that most people aren't reading exactly what I'm saying about

Yeah, obviously my name thing was crap because you might rename the file
:-)

-- 
Neil A. Carson

---

From: Paul Koning <[email-masked]>
Date: Tue, 20 Oct 1998 10:30:44 -0400

>>>>> "Neil" == Neil A Carson <[email-masked]> writes:

> Okay, so if the naame of the file is the only thing that's
> constant...  Can you basically use a hash table to convert
> between file name (including path without leading /) and i-node
> number? Or given the FS lasyersis this impossible to do?

> Or maybe a combination of object ID and hashed name?

Inode numbers are 32 bits, right?  So by the birtday paradox, you'd
have about a 50% chance of a hash collision when you have 64k files.
That assumes a top quality hash (say, MD5); many hashes would do worse.

	paul

---

From: Phil Norman <[email-masked]>
Date: Tue, 20 Oct 1998 17:22:53 +0100

In message <[email-masked]>

> That assumes a top quality hash (say, MD5); many hashes would do worse.

Note quite 50%.  Working on the following algorithm and applying some
probability...

---
space = 65536*65536

start% = 1
end% = 65536

prob = 100

FOR c%=start% TO end%
  prob = prob * ((space - c%) / space)
NEXT

PRINT "Final probability is "+STR$(100-prob)
---

space is the possible number of hash values possible in 32 bits; start% and
end% are the (integer) counter bounds for the hash values we're summing over;
c% is the counter; prob is the probability (in %).

This comes out with a value of 39.35%, which is somewhat different from 50%
and is the /real/ probability of any two of the 65536 currently-used hash
values out of the 1<<32 hash space being the same.  This is assuming you have
a perfect hashing algorithm.

However, this doesn't negate your point that this isn't the ideal way to do
it.  Personally, I'd go with the 'start at zero and count your way up'
approach.  However, personally I don't see the point in writing a read/write
filecore fs, since it's going to be a pain to do (the filecore format is
really quite interesting), and there isn't really enough call for it. 
Personally, I'd rather use the two read-only filesystems on each architecture
rather than using dodgy developmental read/write filing systems ;-).

Phil --pedantic

---

From: Matthew Wilcox <[email-masked]>
Date: Tue, 20 Oct 1998 18:37:14 +0200

> new, equally arbitrary, inode number which will do just as well.

Except for NFS.  But surely no one is planning on serving their RISC
OS filesystem by NFS are they?!  You're not able to export your SMB
filesystem by NFS for similar reasons.

-- 
Matthew Wilcox <[email-masked]>
"I decry the current tendency to seek patents on algorithms.  There are
better ways to earn a living than to prevent other people from making use of
one's contributions to computer science."  -- Donald E. Knuth, TAoCP vol 3
unsubscribe: body of `unsubscribe linux-arm' to [email-masked]

---

From: Philip Blundell <[email-masked]>
Date: Tue, 20 Oct 1998 18:12:18 +0100

>filesystem by NFS for similar reasons.

Can't unfsd cope with this?  I thought it manufactured its own inodes as well 
but I could be wrong.

p.

---

From: Alan Cox <[email-masked]>
Date: Tue, 20 Oct 1998 19:42:13 +0100 (BST)

> that you can guarantee will always refer to the file during that files lifetime.

My point is you dont need it
unsubscribe: body of `unsubscribe linux-arm' to [email-masked]

---

From: Matthew Wilcox <[email-masked]>
Date: Tue, 20 Oct 1998 21:30:48 +0200

> Note quite 50%.  Working on the following algorithm and applying some
[brutal snippage]
> a perfect hashing algorithm.

This is interesting.  That's the standard quoted approximation to the
birthday paradox.  I never knew it was so far out.

---

From: Richard Atterer <[email-masked]>
Date: Wed, 21 Oct 1998 00:56:47 +0200

In article <[email-masked]>
    Russell King - ARM Linux Admin <[email-masked]> wrote:

> The current system of inode allocation only works *because it is
> read-only*. If someone can think up a way of allocating inode numbers
> to a totally dynamic filesystem without any concept of inodes, I'd be
> happy to hear them.

For each directory, store a unique number in the objects' directory
entries - somewhere in the upper 24 bits of the object attributes. This
means you have to write to the ADFS partition even if there are just
read accesses, but what can you do... I doubt altering those bits would
break many RiscOS programs (does FilerPro make use of them?).

Cheers,

  Richard

-- 
  __   _
  |_) /|  Richard Atterer
  | \/¯|  http://home.augsburg.baynet.de/richard.atterer/      raFS V1.14
  ¯ ´` ¯
unsubscribe: body of `unsubscribe linux-arm' to [email-masked]

---

From: Alan Cox <[email-masked]>
Date: Wed, 21 Oct 1998 00:48:33 +0100 (BST)

> Can't unfsd cope with this?  I thought it manufactured its own inodes as well 

UNFSD can sort of but dont rely on it

---

From: Rob Davis <[email-masked]>
Date: Sat, 24 Oct 1998 18:55:13 +0100

In message <Pine.SOL.3.96.981020121216.1679A-100000@mraoss>
          Toby Haynes <[email-masked]> wrote:

> RiscPC SA110 ARM Linux 2.0.34 system. 

I seem to remember this.. Ah yes.. Paul Vigay's Notes.  

"If you can't type text in X Window text boxes, you may need to edit the
.Xdefaults file which is in your root directory.....  Just before the
emacs section add the following line:

*input: true

and save the file."

Hope that helps
-- 
Rob Davis                OAC Ministries, British Registered Charity, 295432
---------------------------------------------------------------------------
Homepage: http://www.oac.u-net.com    Mobile: 0973 359577 (SMS welcome)
[email-masked] (Rob.. At the house)
unsubscribe: body of `unsubscribe linux-arm' to [email-masked]