1

It surprises me to see find iterate/walk through the complete filesystem when I do a simple

find -inum 12345

Without background info it seems to me that there should be much easier ways for to tell all the files with this specific inode 12345 (which is simply a placeholder here)?

Is there maybe even a better way for this? One that does not require to check through all the directory structure of a filesystem simply to tell which filenames are related to an inode?

update

There is another question addressing the issue Quickly find which file(s) belongs to a specific inode number but with the intent to find a better (faster way).

This question is more directed to knowing why it is such a problem in the first place? Maybe there is a good reason related to permissions etc, which would try to make it intentionally difficult to the users to avoid traversing the directory structure to seek for all filenames to an inode.

Still, it seems quite strange that any filesystem would have such a problem telling all the filenames to an inode (at least to the privileged root) user

The filesystem I am most interested to have this question answered for (if it matters) is ext4.

Community
  • 1
humanityANDpeace
  • 14,392

3 Answers3

2

The very simple reason is that at least for the ext2/ext3/ext4 type filesystems the filenames are stored via the directory entries data stored in directory type files.

This means that those files that are from type directory have a more or less intricate system to store filenames (of the files inside of the directory) and the inodes which lead to the data of those files.

somewhat simplified (ext3/4 use hash-tables enhancements for speed up directory tree traversal etc...) it looks like such a listing:

## filenames ##    ## inode-numbers ##
filename1            0123
filename2            01242
anotherfilename      3313
yetanotherfilename   11233

Essentially the filenames only ever occurs inside of the data related to the direcotry files and are not stored anywhere in the metadata the filesystem stores for/of the inodes. Therefore the only way to get the filenames related to an inode number is via going through all the directory entries of all directory files.

humanityANDpeace
  • 14,392
1

You wrote:

It surprises me to see find iterate/walk through the complete filesystem when I do a simple find -inum 12345

find, by definition, does a tree walk starting at the given directory or directories, with a default starting directory of ..

find -inum 12345 will walk through the entire directory tree starting with the current working directory. It probably won't walk through an entire filesystem, unless . happens to contain a filesystem mount point.

There are more efficient ways to find all the files with a given inode number - fsdb, debugfs, and ncheck in the answer you linked to - but find has to do a tree walk because of standards. Note that if the inode you're looking for has just one link, you can give find the -quit option, if it supports it, to end the tree walk after the first match.

Even those other commands aren't always quick, in part because they must look through an entire filesystem rather than just a directory tree, but they do the best they can with the data they have available to work with. The basic problem is the structure of most Unix filesystems.

  • there are lots of pieces of information in a file's inode, but "the name or names of the file" and "the directory or directories containing the file" are not among them.
  • The structure of a directory on most Unix filesystems is very simple: it just contains a list of entries, each of them an (inode number, file name) pair.
  • To find the directory or directories containing inode 12345, and the name or names by which those directories refer to it, on most Unix filesystems these commands have to search through every entry of every directory on the filesystem until they have found all the matching entries. A file's inode does contain the number of directory entries that refer to it, so they can quit searching as soon as they have found that many entries.
  • By contrast, finding a directory's name is much more efficient, because every directory contains the inode number of its parent directory, .., so only that one directory needs to be searched for a matching entry. (There is one exception: the root directory of a filesystem has a .. entry that points to that same directory.)
Mark Plotnick
  • 25,413
  • 3
  • 64
  • 82
  • have many thanks for the answer which added some new detail. the options of fsdb or debugfs are indeed not really solving the issue too as internally they also have to look through all directories and its entries to find names for the inode number. Yet they may save some overhead which comes with using find. My initial misguided idea was that the inode<->filename(s) mapping in the fs was bidirectional and by this a tree-walk unecessary. – humanityANDpeace Oct 13 '14 at 06:49
  • why is it that "Luckily, finding a directory's name is much more efficient, because every directory contains the inode number of its containing directory"? – humanityANDpeace Oct 13 '14 at 06:50
  • @humanityANDpeace On almost all Unix filesystems, every directory contains an entry named .., which contains the inode number of its containing directory. So to find the name of directory inode 4519 is simple: you look through it for a .. entry, open the inode in that entry (which will be a directory), and look through it for an entry with inode 4519. The name in that entry is the directory's name. (If you want to find a full pathname, just repeat the process until you get to the root directory, which is special in that both . and .. refer to the same inode number.) – Mark Plotnick Oct 13 '14 at 18:26
1

A simpler answer might be by analogy.

Imagine searching a phone book for a phone number rather than a name.

Matthew Hannigan
  • 109