convert filepath into inode number?

[Peter Cheung]

Dear All
How an OS convert the filepath into an inode number? Because we have millions files, so i don't think normal OS will build a mapping table, so how they do it?

thanks
from Peter (cmk...@hotmail.com)

[Rod Pemberton]

"Peter Cheung" <mche...@gmail.com> wrote in message
news:f6c56ff6-a55f-419a...@googlegroups.com...

>
> How an OS convert the filepath into an inode number?
> Because we have millions files, so i don't think normal
> OS will build a mapping table, so how they do it?
>

"Each file is associated with an inode, which is identified
by an integer number, ..."
...
"Unix directories are lists of association structures, each
of which contains one filename and one inode number."
...

http://en.wikipedia.org/wiki/Inode


Read the two quoted sentences in reverse.
Read the 2nd sentence, then read the 1st.


Rod Pemberton

[Peter Cheung]

Rod Pemberton於 2012年11月4日星期日UTC+8下午1時32分33秒寫道：

In newlib stub, in the _read function stub, i can get an integer to represent the file, i think that is the inode number. But i need to file path to find out the location of that file in the FS, thats why i was asking the way to convert the inode number into a file path.
thanks
from Peter

[Rod Pemberton]

"Peter Cheung" <mche...@gmail.com> wrote in message

news:7d7088ef-bd9d-4bcf...@googlegroups.com...
> Rod Pemberton? 2012?11?4????UTC+8??1?32?33???:

> > "Peter Cheung" <mche...@gmail.com> wrote in message
> > news:f6c56ff6-a55f-419a...@googlegroups.com...
...

> > > How an OS convert the filepath into an inode number?
> > > Because we have millions files, so i don't think normal
> > > OS will build a mapping table, so how they do it?
> >
> >

> > [incorrect answer]

>
> In newlib stub, in the _read function stub, i can get an integer
> to represent the file, i think that is the inode number. But i
> need to file path to find out the location of that file in the FS,
> thats why i was asking the way to convert the inode number
> into a file path.
>

I don't know the answer to that.

For some filesystems, there is a function to get current directory. Or,
there is a function to get the full path for a file.

I don't see anything like that listed here at newlib's libc index:
http://sourceware.org/newlib/libc.html

I know POSIX libraries are more developed than newlib(). I'll provide links
to OpenGroup's webpages so you can compare newlib's functionality. This
will let you determine if something important is missing.

On POSIX operating systems, there are usually functions like closedir(),
opendir(), readdir(), rewinddir(), seekdir(), telldir(), closedir() and a
structure called 'dirent' (dirent.h). telldir() should do what you need. I
suspect that you are missing these functions.

POSIX telldir (links to dirent.h, dirent structure)
http://pubs.opengroup.org/onlinepubs/009695399/functions/telldir.html

There is a Public Domain (no copyrights) implementation of those directory
functions called 'libndir' by D.A. Gwyn. I believe it has to be customized
to your operating system. They are usually available on the Internet as
libndir.tar.Z and libndir-posix.tar.Z. They are also archived in old Usenet
posts.

This archive has them:
http://yahozna.dyndns.org/computers/software/3b2/misc/unix-c/languages/c/

Index of that archive:
http://yahozna.dyndns.org/computers/software/3b2/misc/unix-c/000-master-index.txt

You may also be able to use fstat() or stat() calls. These and other file
related calls have structures associated with them that contain information.
You may be able to use the items which are in the 'stat' structure (stat.h)
or 'FILE' structure (stdio.h) or even the 'dirent' structure (dirent.h), if
it's available.

POSIX fstat (links to stat.h, stat structure)
http://pubs.opengroup.org/onlinepubs/009695399/functions/fstat.html

POSIX stdio.h (FILE structure)
http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/stdio.h.html


Rod Pemberton

[Marven Lee]

"Peter Cheung" <mche...@gmail.com> wrote:
Rod Pemberton wrote:

"Peter Cheung" <mche...@gmail.com> wrote:
> > How an OS convert the filepath into an inode number?
>

>In newlib stub, in the _read function stub, i can get an integer to
> represent the file, i think that is the inode number.

No, that should be the fd "file descriptor" number returned by
the open() system call.

The file descriptor is usually an index into a table maintained
by each process. Each entry in the table may point to an
in-memory inode structure for a given file or indirectly through
an intermediate 'filp' structure which holds the descriptors's
file pointer/seek position and a pointer to the inode.
Multiple file descriptors can point to and share a single filp and
is used to duplicate file descriptors for dup() and fork() calls in Unix.

> But i need to file path to find out the location of that file
> in the FS, thats why i was asking the way to convert the
> inode number into a file path.

Inodes are on-disk structures that contain information about a file,
the sectors it used, file size, permissions etc. They are held in a
table on the disk either all in one place or spread across the disk.
In Unix the directories are like normal files and contain entries
with the filename and inode number as a pair. So the inode of
a file can be found.

Inodes are on-disk but when they are opened either a copy
or an in-kernel version of it is allocated within the kernel.

In Unix the open() and other system calls that have a pathname as an
argument use the function namei() to convert a pathname to a locked
inode. This looks up each component of a pathname, starting in the
current directory (it should hold a pointer to it's inode). For each
component it searches the directory to find the inode number
of the matching component. If the next component isn't the last
component and is a directory then the lookup is repeated with
the new inode.

inode = namei (pathname);
next_inode = lookup (directory_inode, component);

Of course now that we have VFSs and multiple file systems
inodes in memory are now vnodes.

Also namei() is a lot more complicated with the need to handle
different file system types as well as options to control what
is actually looked up.

For example to create a file you need to lookup the filename
to see if it exists and if not create it in the parent directory,
so namei() needs to return the opened file inode or the parent
directory's inode into which it can create it.

Also handling of symbolic links. Normally you'll want to
open whatever a symbolic link points to, but to delete a
symbolic link you actually want to open it so namei() needs
flags for that.

namei() may also be named as lookupname() or lookuppn()
depending on the OS.

From page 75 of Bach's, "The Design of The Unic Operating
System," namei() looks like this:


algorithm namei /* convert path name to inode */
input: path name
output: locked inode

if (path name starts from root)
working inode - root inode (algorithm iget);
else
working inode - current directory inode (algorithm iget):

while (there is more path name)
{
read next path name component from input;
verify that working inode is of directory, access permissions OK;

if (working inode is of root and component is \"..\")
continue; /* loop back to while */

read directory (working inode) by repeated use of algorithms
bmap, bread and brelse;

if (component matches an entry in directory (working inode))
{
get inode number for matched component;
release working inode (algorithm iput);

working inode - inode of matched component (algorithm iget);
}
else /* component not in directory */
return (no inode);
}

return (working inode);



--
Marv

[James Harris]

On Nov 4, 4:16 am, Peter Cheung <mcheun...@gmail.com> wrote:
> Dear All
>    How an OS convert the filepath into an inode number? Because we have millions files, so i don't think normal OS will build a mapping table, so how they do it?

I'm not sure whether you are asking about the mechanism or about how
to deal with the quantity of files.

For mechanism: Filesystems that use inodes have one inode per file.
The inode defines file attributes. File names are not stored in the
inode but exist in separate directories. The directory can be read
using the readdir() call (and others) and entries have a basic format
something like

- inode number
- entry length
- name length
- type
- name (as long as needed)
- padding (as needed)

The two lengths allow the management of internal space in directories
and, of course, the inode identifies which file this directory entry
refers to. A single file can have more than one name so there can be
more than one directory entry with a given inode number.

For quantity: The OS doesn't normally need to store in RAM mappings
for millions of files. When a person refers to /home/peter the
filesystem only needs to map the name components to inode numbers as
needed.

The only way I can think of to map the other way, from inode to name,
is to scan all directories to locate all the names of a given file.

HTH

James

[Rod Pemberton]

"James Harris" <james.h...@gmail.com> wrote in message
news:f310fd13-346e-4a35...@p22g2000vby.googlegroups.com...
...

> [in reply to Peter, inode based file system]

>
> For mechanism: Filesystems that use inodes have one inode per
> file. The inode defines file attributes. File names are not stored

> in the inode but exist in separate directories. [...]

I'm not as familiar with inode based filesystems. Why is it that the
filenames are _not_ in the inode too? Just wondering...

The directories of one filesystem I'm familiar with stores the filename,
starting track and sector, file type, and file size in the directory.
Another stores the filename, attributes, time and date stamp, starting
cluster, and file length in the directory.

I.e., it seems that *not* storing information directly in the directory, as
inode based filesystems seem to do, is the exact opposite of how various
other filesystems are implemented. So, why didn't Unix or POSIX go all the
way and put everything into the inode and eliminate the directory entirely?

> [...] A single file can have more than one name so there can be

> more than one directory entry with a given inode number.

> [...]

Interesting ...

Is that just for providing multiple names or is it used for symbolic links?

When you delete "a single file [with] more than one name" and a "given inode
number", how does the file system code make sure that the _multiple_
directory entries are all deleted? Does it search the entire directory to
find all files with the given inode? If it does, that could be very time
consuming. I've experienced the POSIX 'find' command taking enormous
amounts of time on simple file searches in the past. I don't understand
how the filesystem code could do it any faster.


Rod Pemberton

[James Harris]

On Nov 5, 7:32 pm, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
wrote:
> "James Harris" <james.harri...@gmail.com> wrote in message

>
> news:f310fd13-346e-4a35...@p22g2000vby.googlegroups.com...
> ...
>
> > [in reply to Peter, inode based file system]
>
> > For mechanism: Filesystems that use inodes have one inode per
> > file.  The inode defines file attributes. File names are not stored
> > in the inode but exist in separate directories. [...]
>
> I'm not as familiar with inode based filesystems.  Why is it that the
> filenames are _not_ in the inode too?  Just wondering...
>
> The directories of one filesystem I'm familiar with stores the filename,
> starting track and sector, file type, and file size in the directory.
> Another stores the filename, attributes, time and date stamp, starting
> cluster, and file length in the directory.
>
> I.e., it seems that *not* storing information directly in the directory, as
> inode based filesystems seem to do, is the exact opposite of how various
> other filesystems are implemented.  So, why didn't Unix or POSIX go all the
> way and put everything into the inode and eliminate the directory entirely?

I don't know the rationale but I can say why I think it is a good
idea. Two reasons:

1. If the name of a file were to be included in the inode then either
each inode would have to be big enough to include the longest name or
there could be problems as files were renamed. Making each inode a
fixed size allows inode N to be found easily and prevents one inode
running into the space set aside for another. I think the inode space
is reserved when the volume is formatted so that the volume contains
an array of inodes.

2. In Unix a file can have more than one name as long as both names
are on the same volume. Having multiple names each refer to the one
inode allows this. (These are hard links, not symbolic links.)

> > [...] A single file can have more than one name so there can be
> > more than one directory entry with a given inode number.
> > [...]
>
> Interesting ...
>
> Is that just for providing multiple names or is it used for symbolic links?

This is purely for hard links, i.e. multiple names for the same file
on the same volume.

Symbolic links are different. They are not extra links to the same
inode. I think they are purely textual references to another part of
the file system. Hard links are to real files and are equivalent to
the original names. If a hard link is moved to a new directory both
links still work.

Symbolic links are more flexible in that they can point to another
volume (which hard links cannot) but they are more vulnerable. If the
original file is renamed or deleted the symbolic link will still exist
but it won't point to anything valid.

> When you delete "a single file [with] more than one name" and a "given inode
> number", how does the file system code make sure that the _multiple_
> directory entries are all deleted?

For hard links the file system will only delete the one directory
entry you tell it to and leave any others in place. The inode has a
use count. It counts how many directory entries refer to that inode.
(The use count can be seen in the ls -l command.) Only when the use
count drops to zero does the space occupied by the file get recovered.
Until then the file content will still exist. So if you have two hard
links to a file (the original name and one other) then whichever you
delete will leave the other one in place. Although they have to be on
the same volume the two names can be in different directories.

I only started looking in to this a few weeks ago. Ben has been
dealing with file systems for years. If he is reading he may have some
comments.

James

[Rod Pemberton]

"James Harris" <james.h...@gmail.com> wrote in message

news:efdbc44e-bb4a-470a...@r5g2000yqo.googlegroups.com...

> On Nov 5, 7:32 pm, "Rod Pemberton" <do_not_h...@notemailnotz.cnm>
> wrote:

...

> > [snip]

> >
> 2. In Unix a file can have more than one name as long as both names
> are on the same volume. Having multiple names each refer to the one
> inode allows this. (These are hard links, not symbolic links.)

Ok.

So, that means a data pair is needed to keep track of each file: volume and
inode. I.e., the filesystem must keep track of both since inode numbering
is not unique to the entire filesystem, but is unique for the specific
volume.

> > When you delete "a single file [with] more than one name" and a
> > "given inode number", how does the file system code make sure
> > that the _multiple_ directory entries are all deleted?
>
> For hard links the file system will only delete the one directory
> entry you tell it to and leave any others in place.

So, I have to manually track down the other directory entries
and delete them too? ...

> The inode has a use count. It counts how many directory entries
> refer to that inode. (The use count can be seen in the ls -l command.)

Nifty...

I don't recall seeing that with 'ls -l', but it's been a while since I've
booted Linux.

I doubt I knew that you could set up multiple names for a file either.

> The inode has a use count. It counts how many directory entries
> refer to that inode. (The use count can be seen in the ls -l command.)
> Only when the use count drops to zero does the space occupied by
> the file get recovered. Until then the file content will still exist. So
> if you have two hard links to a file (the original name and one other)
> then whichever you delete will leave the other one in place. Although
> they have to be on the same volume the two names can be in different
> directories.
>

Wait a minute...

If I have two hard links (on the same volume) to the same file and I delete
one hard link, that just delete's the first directory entry to file? So,
the file still exists and the file's second directory entry still exists
until I delete the second hard link? I.e., I can't actually delete the file
until I delete all the hard links to it? That would seem to _preserve_
files that someone (me) is attempting to delete. What's the point of that?

I'm not sure I like that. It reminds me of Windows re-installing
deleted system files. I.e., how the ~$@! do I get the file to delete?

I can understand if a administrator set hard links to all the system files
in a hidden directory to prevent intentional or unintentional deletion.
That'd be useful for security. But, generally, if it's my computer, and I
choose to delete a file. I want it gone immediately. If I've chosen a system
file, I want it gone too, most likely because I want to replace it, but
maybe because it's causing a problem. I don't want to find out that the
file was preserved at a later date. I also don't want to waste time tracking
down an additional hard link to a file which I might not even remember the
name of.

I.e., when I tell the OS to delete a file, if the use count is non-zero, I
really want the OS to delete all other hard links and/or directory entries
to the file, and then do what I told it to do in the first place: delete the
file. Why would anyone construct a 'delete file' command that doesn't
_actually_ delete a file? ... That's what you're telling me happens.

Sorry, rant over ... I'll definately have to check this out at a later
date.


Rod Pemberton

[Peter Cheung]

Thanks everybody. I think Marven is correct, open() return the file descriptor ID, that is not an inode number.

God bless this group!

[Marven Lee]

"Rod Pemberton" <do_no...@notemailnotz.cnm> wrote:
> If I have two hard links (on the same volume) to the same file
> and I delete one hard link, that just delete's the first directory
> entry to file? So, the file still exists and the file's second directory
> entry still exists until I delete the second hard link? I.e., I can't
> actually delete the file until I delete all the hard links to it? That
> would seem to _preserve_ files that someone (me) is attempting
> to delete. What's the point of that?

No idea. I think I need to read some textbooks on the subject to
remind me of their use. Perhaps it was useful to have the same
executable but with different filenames to perform different actions?
But then can't that be done with symlinks?

Perhaps it is also useful for chroot() purposes, when the root
directory is changed but needs to still access executables outside
the new root directory tree.

> I.e., when I tell the OS to delete a file, if the use count is non-zero, I
> really want the OS to delete all other hard links and/or directory entries
> to the file, and then do what I told it to do in the first place: delete
> the file. Why would anyone construct a 'delete file' command that
> doesn't _actually_ delete a file? ... That's what you're telling me
> happens.

Also if a file is open and the file is deleted using unlink() then the
directory entry will be removed but the file contents and inode will
only be freed when the reference count of the open file reaches zero.

fd = open ("filename", O_RDWR);
unlink ("pathname");
// can continue reading and writing file

--
Marv