RFC: Stable inodes for inode-less filesystems (was: Finding hardlinks)
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 8 lines · Pavel Machek
Quoted 3 lines
Another idea is to export the filesystem internal ID as an arbitray length cookie through the extended attribute interface. That could be stored/compared by the filesystem quite efficiently.
How will that work for FAT?
Or maybe we can relax that "inode may not change over rename" and "zero length files need unique inode numbers"...
I didn't look into the code, and I'm not experienced in writing (linux) fs, but I have an Idea I'd like to share. Maybe it's not that bad ...
(I'm going to type about inode numbers, since having constant inodes
is desired and the extended attribute would only be an aid if the inode is too small.)
IIRC, no cluster is reserved for empty files on FAT; if I'm wrong, it'll be much easier, you would just use the cluster-number (less than 32 bit).
The basic idea is to use a different inode range for non-empty and empty files. This will result in the inode possibly changing after close()* or on rename(empty1, empty2). OTOH it will keep a stable inode for non-empty files and for newly written files** if they aren't stat()ed before writing the first byte. I'm not sure if it's better than changing inodes after $randomtime, but I just made a quick strace on gtar, rsync and cp -a; they don't look at the dest inode before it would change (or at all).
(If this idea is applied to iso9660, the hard problem will be finding the
number of hardlinked files for one location)
Changing the inode# on the last close* can be done by purging the cache if the file is empty XOR the file has an inode# from the empty-range. (That should be the same operation as done by unlink()?)
A new open(), stat() or readdir should create the correct kind of inode#.
*) You can optionally just wait for the inode to expire, but you need to
keep the associated reservation(s) until then. I don't expect any visible effect from doing this, but see ** from the next paragraph on how to minimize the effect. The reserved directory entry (see far below in this text) is 32 Bytes, but the fragmentation may be bad.
**) which are empty on open() and therefore don't yet have a stable inode#
Those inode numbers will apear to be stable because nobody saw them change. It's safe to change the inode# because by reserving disk space, we got a unique inode#. I hope the kernel side allows this ...
For non-empty files, you can use the cluster-number (start address), it's unique, and won't change on rename. It will, however, change on emptying or writing to an empty file. If you write to an empty file, no special handling is required, all reservations are implicit*. If you empty a file, you'll have to keep the first cluster reserved** untill it's closed, otherwise you'd risk an inode collision.
*) since the inode# doesn't change yet, you'll still have to treat it like
an empty file while unlinking or renaming.
**) It's OK to reuse it if it's in the middle of a file, so you may
optionally keep a list of these clusters and not start files there instead of reserving the space. OTOH, it's more work.
Empty files will be a PITA with 32-bit-inodes, since a full-sized FAT32 can have about 2^38 empty files*. (The extended attribute would work as described below.) You can, however, generate inode numbers for empty files, risking collisions. This requires all generated inode numbers to be above 0x40000000 (or above the number of clusters on disk).
*) 8 TB divided by 32 B / directory entry
With 64-bit-values, you can generate an unique inode for empty files using cluster#-of-dir | 0x80000000 | index_in_dir << 32. The downside is, it will change on cross-directory-renames and may change on in- directory-renames. If this happens to an open file, you'll need to make sure the old inode# is not reused by reserving that directory entry, since the inode# can't change for open files.
extra operations on final close:
if "empty" inode:
if !empty
unreserve_directory_entry(inode & 0x7fffffff, inode >> 32) uncache inode (will change inode#)
stop
if unreserve_directory_entry(inode & 0x7fffffff, inode >> 32)
uncache inode
if "non-empty" inode
if empty
free start cluster
uncache inode
extra operations on unlink/rename:
if "empty" inode:
if can_use_current_inode#_for_dest
do it
unreserve_directory_entry(inode & 0x7fffffff, inode >> 32) // because of "mv a/empty b/empty; mv b/empty a/empty"
else if is_open_file
// the current inode won't fit the new location:
reserve_directory_entry(old_inode & 0x7fffffff, inode >> 32)
extra operations on truncate
if "non-empty" inode && empty_after_truncate
exempt start cluster from being freed,
or put it on a list of non-startclusters
extra operation on extend
if "empty" inode && nobody did e.g. stat() after opening this file
silently change inode, nobody will notice. Racy? Possible?
Required data in filehandle:
Location of directory entry (d.e. contains inode information)
(this shouldn't be new data?)
stat-flag (possibly one per filesystem is enough)
Directories additionally:
Pointer to a list of reserved directory entries (usurally NULL)
Required data in Superblock:
->Optional List of non-startclusters
Signature · 4 lines
Ich danke GMX dafür, die Verwendung meiner Adressen mittels per SPF verbreiteten Lügen zu sabotieren. http://david.woodhou.se/why-not-spf.html
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: Finding hardlinks
Quoted 14 lines · Miklos Szeredi
Quoted 6 lines
Quoted 3 lines
Well, sort of. Samefile without keeping fds open doesn't have any protection against the tree changing underneath between first registering a file and later opening it. The inode number is more
You only need to keep one-file-per-hardlink-group open during final verification, checking that inode hashing produced reasonable results.
What final verification? I wasn't just talking about 'tar' but all cases where
st_inomight be used to check the identity of two files at possibly different points in time.Time A: remember identity of file X Time B: check if identity of file Y matches that of file X
Quoted 7 lines
With
samefile()if you open X at A, and keep it open till B, you can accumulate large numbers of open files and the application can fail.If you don't keep an open file, just remember the path, then renaming X will foil the later identity check. Changing the file at this path between A and B can even give you a false positive. This applies to 'tar' as well as the other uses.
If you open Y, this open file descriptor will guarantee that no distinct file will have the same inode number while all hardliked files must have the same inode number. (AFAIK)
Now you will check this against the list of hardlink candidates using the stored inode number. If the inode number has changed, this will result in a false negative. If you removed X, recreated it with the same inode number and linked that to Y, you'll get a false positive (which could be identified by the [mc]time changes).
Samefile without keeping the files open will result in the same false positive as open+fstat+stat, while samefile with keeping the files open will occasionally overflow the files table, Therefore I think it's not worth while introducing samefile as long as the inode is unique for open files. OTOH you'll want to keep the inode number as stable as possible, since it's the only sane way to find sets of hardlinked files and some important programs may depend on it.
Signature · 8 lines
Ich danke GMX dafür, die Verwendung meiner Adressen mittels per SPF verbreiteten Lügen zu sabotieren. http://david.woodhou.se/why-not-spf.html - To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html