Node occasionally gives multiple files/folders the same inode

@Fishrock123

Moderator's note (@Fishrock123): Off-topic comments have and will be deleted.

Version: v7.2.1
Platform: Windows 10 Pro 64bit, Windows 7 Enterprise 64bit (Both using NTFS)
Subsystem: File System

Node sometimes reports different files/folders to have identical ino values.
I can't reproduce this consistently and copying/reproducing a folder structure that contains dupes elsewhere doesn't replicate the issue.

I did encounter lots of duplicates under C:\Users\%USER%\AppData but it may be different for other people

Example

Specific example I encountered

# Structure
│   ServerStore.jsx
│
├───constants
│       Api.jsx
│
└───stores
        UserStore.jsx

> fs.lstatSync("stores").ino
5910974511014218
> fs.lstatSync("stores/UserStore.jsx").ino
24206847997202570
> fs.lstatSync("constants").ino //Duplicate
9851624184963316
> fs.lstatSync("constants/Api.jsx").ino //Duplicate
9851624184963316
> fs.lstatSync("ServerStore.jsx").ino
3659174697792238

Test Script

Here's a hacky node script to loop through a directory and look for duplicate inodes.
Running it on most of my other folders didn't yield a result, until I ran it on C:\Users\%USER%\AppData where I encounted loads of duplicates

Usage: node dupe.js [dir]

var fs = require('fs');
var path = require('path');
var process = require('process');

// Recursively walks a directory and looks for duplicate inodes
// loop from http://stackoverflow.com/questions/5827612/node-js-fs-readdir-recursive-directory-search

var dir = process.argv[2];
if (dir == undefined) {
    dir = '.';
}

var walk = function(dir, done) {

  var results = [];
  fs.readdir(dir, function(err, list) {

    if (err) return done(err);

    var pending = list.length;
    if (!pending) return done(null, results);

    list.forEach(function(file) {

      file = path.resolve(dir, file);
      fs.stat(file, function(err, stat) {
        if(stat && stat.ino) {
            results.push({
                file: file,
                ino: stat.ino
            });
        }

        if (stat && stat.isDirectory()) {
          walk(file, function(err, res) {
            if(res) {
               results = results.concat(res);
            }
            if (!--pending) done(null, results);
          });
        } 
        else {
          if (!--pending) done(null, results);
        }
      });
    });
  });
};

walk(dir, function(err, results) {
    var merge = {};
    results.forEach(function(it) {
        if (!merge[it.ino]) {
            merge[it.ino] = [];
        }
        merge[it.ino].push(it.file);
    });
    var dupes = Object.keys(merge).filter(key => merge[key].length > 1);

    dupes.forEach(it => console.log(it, merge[it]));
})

I suppose it could be either a Windows bug or quirk¹ but it could also be caused by node.js converting libuv's 64 bits st_ino field to a double, which won't be lossless for large numbers.

I expect it's the latter that is happening here. You should be able to verify that by instrumenting src/node_file.cc if you are so inclined. Grep for 'st_ino', it's used in only one location.

¹ The inode number is derived from NtQueryInformationFile(FileAllInformation). It has some documented quirks and probably a few undocumented as well, see e.g. the section 'Remarks' on this page.

I had a little play with that Windows API and ran it directly against files that node reported with the same ino (Using C# DLL import)

Example

Node 
> fs.lstatSync('one.gif').ino
9851624185071828
> fs.lstatSync('two.gif').ino
9851624185071828

Windows 7 NTFS via NtQueryInformationFile
(QuadPart is what is used in libuv)

file: one.gif
type: LARGE_INTEGER
QuadPart: 9851624185071827

file: two.gif
type: LARGE_INTEGER
QuadPart: 9851624185071829

Looks like you were right about the problem being in the double conversion. Here's a C++ snippet highlighting it.

#include <iostream>

int main() {
    long long a = 9851624185071827;
    long long b = 9851624185071829;

    std::cout.precision(100);
    std::cout << a << std::endl; //9851624185071827
    double da = a;
    std::cout << da << std::endl; //9851624185071828

    std::cout << b << std::endl; //9851624185071829
    double db = b;
    std::cout << db << std::endl; //9851624185071828

    return 0;
}

Closest possible fix I could think of is to change the fs_stats_field_array type from double to long long but that sounds like it would just make more problems.

@mscdex

Yes, that wouldn't be a solution. JS doesn't have a 64 bits integral type, only a 64 bits floating-point type. Values >= 2⁵³ and <= -2⁵³ cannot be represented exactly and get rounded up or down.

We could detect such out-of-range values and present them as strings instead of numbers but it's an open question if a type change like that qualifies as a bug fix or a backwards-incompatible semver-major change.

cc @mscdex since you worked on that code recently.

There really is no good solution for this until JS gets 64-bit types. IIRC this isn't the only place where node hopes for the best by using a double for 64-bit integer values.

Best thing to do might be make a native module that copies the core part that you need but returns a string?

Alternatively we might think about having a second Stats constructor that treats the uint64_t fields returned by libuv faithfully… we’ve also had people asking for nanosecond resolution in the timer fields (that is otherwise lost by new Date()), this could be a good chance to tackle that, too.

Alternatively we might think about having a second Stats constructor

How would that work (having two different constructors at the same time)? Does someone opt-in to the new one with a flag passed to the fs.*stat*() methods or something?

that treats the uint64_t fields returned by libuv faithfully

Define 'faithfully.' Is this an array with the upper and lower 32-bits? A string? An 8-byte Buffer? A new BigInt class of our own? Something else?

we’ve also had people asking for nanosecond resolution in the timer fields (that is otherwise lost by new Date())

I am all for getting rid of the Date instances, it only adds more overhead if users just end up extracting the integer timestamp out of it anyway. At least if we just provide the number, end users could just pass it to new Date() if they need that kind of functionality and everyone else would get a speedup.

How would that work (having two different constructors at the same time)?

Yes, a flag (not a fan) or a new set of functions on fs (more of a fan because that won’t slow down any existing code).

Define 'faithfully.' Is this an array with the upper and lower 32-bits?

Something like that. It’s not actually important to me which of your suggestions – they all make sense – but generally something that people could reimplement the current Stats upon in any way they want.

something that people could reimplement the current Stats upon in any way they want

I still don't understand this, how they are changing/providing Stats? Are they monkey patching/overwriting fs.Stats with their own implementation? Should we really be encouraging that?

@mscdex

@mscdex Sorry, probably not expressing myself clearly. Basically, what I’d imagine is a 2nd API on Node’s side, not changing the current API’s behaviour. If somebody wanted, they could build the current API on top of that as a userland module – I’m not suggesting that they monkey-patch anything (or “change” fs.Stats at all).

@mscdex

Personally, I would prefer if Node fixed this properly going forward.

I think passing the inode as a String would be appropriate since an inode is in essence an identifier. It happens to look like an integer, but it may as well be hex for all intents and purposes. I'm not sure if passing the inode as a String would have any performance implications? AFAIK it's a minimum of 24 bytes allocation compared to an integer? I wouldn't mind a Buffer either if that's lighter.

Referring to @mscdex's comment, it would be terrific if we could do away with instantiating thousands of Date objects, when users really just need the timestamp.

Just split the 64-bit word into a high and low 32-bit word and leave arithmetic to the user.

Just another idea, the 64-bit inode integer returned by Windows could be remapped through a hash into the 53-bit address space supported by JS integers. This should give less collisions than the current folding.

@verdy-p

@verdy-p fs.stats can now return a struct of BigInt - https://nodejs.org/api/fs.html#fs_fs_stat_path_options_callback

Ref: #23821

Unfortunately, BigInts are easily mutable, and not suitable as atomic identifiers. And they suffer from serilization locking problem (performance cost) when all we need is an atomic store, which is what strings offer natively (Javascript strings do not have to be displayable or even valid UTF-16, they are just immutable vectors of unsigned 16-bit code units; if we want to display these identifiers, we can still reencode them easily into other valid UTF-16 strings). Strings are also faster to compare (at least for equality: this is almost immediate by comparing only the references, if they are stored in a hashtable). But you may argue that we'll suffer from the storage cost of the hastable to make them atomic if we want to manage large collections of inodes: they would slow down all the rest of the API using strings. In terms of memory management and garbage collection, their cost will be equivalent to BigInts which also need to be allocated (the hashing of inode strings is not absolutely necessary as these strings are short enough to be compared directly, without comparing first their hash then looking up their actual location in the hashtable).
I'm not sure that BigInts are solutions, it is largely possible and very likely that file identifiers will be strings with variable length, just like URIs: consider WebDav filesystems...

BigInts are primitives; how are they mutable?

Adding a string inode field will require some non trivial changes to our marshaling logic. ATM we pass the data as using a globaly mapped array of either double or BigInt:

node/src/node_file.h

Lines 193 to 219 in 9827858

    
           template <typename NativeT, typename V8T> 
        
           constexpr void FillStatsArray(AliasedBuffer<NativeT, V8T>* fields, 
        
                                         const uv_stat_t* s, const size_t offset = 0) { 
        
             fields->SetValue(offset + 0, s->st_dev); 
        
             fields->SetValue(offset + 1, s->st_mode); 
        
             fields->SetValue(offset + 2, s->st_nlink); 
        
             fields->SetValue(offset + 3, s->st_uid); 
        
             fields->SetValue(offset + 4, s->st_gid); 
        
             fields->SetValue(offset + 5, s->st_rdev); 
        
           #if defined(__POSIX__) 
        
             fields->SetValue(offset + 6, s->st_blksize); 
        
           #else 
        
             fields->SetValue(offset + 6, 0); 
        
           #endif 
        
             fields->SetValue(offset + 7, s->st_ino); 
        
             fields->SetValue(offset + 8, s->st_size); 
        
           #if defined(__POSIX__) 
        
             fields->SetValue(offset + 9, s->st_blocks); 
        
           #else 
        
             fields->SetValue(offset + 9, 0); 
        
           #endif 
        
           // Dates. 
        
             fields->SetValue(offset + 10, ToNative<NativeT>(s->st_atim)); 
        
             fields->SetValue(offset + 11, ToNative<NativeT>(s->st_mtim)); 
        
             fields->SetValue(offset + 12, ToNative<NativeT>(s->st_ctim)); 
        
             fields->SetValue(offset + 13, ToNative<NativeT>(s->st_birthtim)); 
        
           }

Adding another string value will also have a performance penalty.

We could add make this an opt-in new option, something like fs.stat({withStringINode: true})

fs.stat({withStringINode: true})
I see that more like:

fs.stat({as: {ino: 'string'}}), or
fs.stat({as: {ino: 'BigInt'}}), the default option being
fs.stat({as: {ino: 'Number'}})
notably if other fields will need to change size in the future (e.g. device numbers, mode, nlink, uid/gid, size/blksize/blocks, dates, ...)

As well some of the returned properties returned by fs.stat() may not be necessary, but costly to get from the underlying OS, and a script may just require a specific set of values, or just one, leaving others possibly unset in the returned Javascript object (also if these properties make no sense for the remote filesystem):

fs.stat({req: {ino: true}, as: {ino: 'Number'}})
If the filesystem returns signatures/hashes or version/view/transaction identifiers or other properties, we could as well request them:
fs.stat({req: {hash: 'SHA1', version: true}, as: {hash: 'string', version: 'Number'}})
And the set of properties that can be returned could be queried as well and returned as an array of strings (or as a single space-separated string):
fs.stat({req: {propset: true}, as: {propset: 'Array'}})
Another solution would be to pass an object prefilled with properties of the expected type:
props = {ino = newBigInt()}; fs.stat({into: props}); then use props.ino (if the query cannot be satisfied, the property would be unset).
Some properties may require passing an authorization token (to allow elevation of privilege), e.g. to query concurrent locks on a file, and some info about lockers. Though I still don't know how to get this token with fs.stat() itself, I can imagine that the "securityTokens" given below may work like a modifiable jar with getters/setters (allowing to first store before in it calling fs.stat, a token that will prompt the user securely like for UAC on windows, or similar prompts by webbrowsers, store the reply as another token in the jar to avoid asking the user repeatedly, and then use that accept/deny token to process further queries with the same tokens jar). Or specify a maximum timeout (if the costly query may be long to process):
props = {ino = newBigInt()}; fs.stat({into: props, with:{security: securityTokens, timeout: 1000}});

So I'm thinking iteratively.
ATM we have:

fs.stat() - regular (i.e. values as Number)
fs.stat({bigint}) - values as BigInt

What I'm suggesting is adding an independent { inodeString } option that will be orthogonal to bigint true or false, i.e.

fs.stat({bigint:true/false, inodeString}) - that returns the same old stat but with a new stat.inodeString.

This is a nice server-minor change. It's opt-in so those who don't want it don't pay for it.

As for unneeded fields, on POSIX we use stat syscall, so we get everything at the same price.
If we're considering backward compatibility, it's safer to keep that as it is.

Note that you speak about POSIX, not actual systems. Even if most OSes implement more or less the POSIX API, filling all the fields may be costly, and not enough to get file info for all filesystems. In the web context we can speak about virtual filesystems with web APIs that need security enforcement, and where getting all the infos at once may be costly or simply denied: under POSIX rules they would be set to pseudovalues like you do in your code by setting arbitrarily some fields arbitrarily to 0.
A file may itself have also several contents: a main content with size (all other fields are not relevant), and possibly an additional directory content which is enumeratable (in NTFS this could be a set of streams, on the web it would be roughly the same as adding a "/" to an URL) and you could query that content with fs.stat({props: "dir"}): the property "dir" returned would be a directory object, not a simple string or number. There can be potentially a lot of properties for files, like versions, views, streams; users/groups are not necessarily reduced to just a single integer; modes are not necesssarily limited to just a few bits and we may need to query modes for specific groups/users, or according to the securityTokens provided. Filesize and dates may eventually be not defined (for continuous live streams). Another info is if the file can be seeked to random positions or not, or if it can be seeked before its initial start position (a live stream may have a record of the last hour before the first position you get when opening it; file positions you can seek to are not necesssarily byte offsets but may be timestamps and two successive timestamps may be separated by unbreakable records with variable byte sizes.
Conceptually the POSIX rules just tries to mimic what was in the minimum common set of features implemented in the first filesystems for Unix; not taking into account new filesystems/data services that have appeared over time or those that existed since long in other systems like former mainframes, then VMS, and then NT, and the web (many of these are now integrable in Unix/Linux as well).

Why is there's a theoretical discussion about future and past file systems, and request for string option? The original issue was solved by introducing BigInt for inode numbers, which is good enough for existing file systems on all platforms supported by Node, in line with the purpose of fs module: "The fs module provides an API for interacting with the file system in a manner closely modeled around standard POSIX functions", can represent arbitrary data in an immutable value, and can be compared with ==. (The only downside compared to strings is that it can't currently be directly encoded with JSON.stringify, but that's a problem for those who encode them to solve.) I only proposed to use string or any other immutable object because we didn't have BigInt, but now that we have them, it's as good as anything else: a value referencing an inode.

fs: support BigInt in fs.*stat and fs.watchFile

fix(core,mcp): SMI-6732 round 8 -- dev/ino is not identity everywhere

Navigation Menu

Repository navigation

Node occasionally gives multiple files/folders the same inode #12115

Example

Test Script

Example

59 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	template <typename NativeT, typename V8T>
	constexpr void FillStatsArray(AliasedBuffer<NativeT, V8T>* fields,
	const uv_stat_t* s, const size_t offset = 0) {
	fields->SetValue(offset + 0, s->st_dev);
	fields->SetValue(offset + 1, s->st_mode);
	fields->SetValue(offset + 2, s->st_nlink);
	fields->SetValue(offset + 3, s->st_uid);
	fields->SetValue(offset + 4, s->st_gid);
	fields->SetValue(offset + 5, s->st_rdev);
	#if defined(__POSIX__)
	fields->SetValue(offset + 6, s->st_blksize);
	#else
	fields->SetValue(offset + 6, 0);
	#endif
	fields->SetValue(offset + 7, s->st_ino);
	fields->SetValue(offset + 8, s->st_size);
	#if defined(__POSIX__)
	fields->SetValue(offset + 9, s->st_blocks);
	#else
	fields->SetValue(offset + 9, 0);
	#endif
	// Dates.
	fields->SetValue(offset + 10, ToNative<NativeT>(s->st_atim));
	fields->SetValue(offset + 11, ToNative<NativeT>(s->st_mtim));
	fields->SetValue(offset + 12, ToNative<NativeT>(s->st_ctim));
	fields->SetValue(offset + 13, ToNative<NativeT>(s->st_birthtim));
	}

Node occasionally gives multiple files/folders the same inode #12115

Description

Example

Test Script

Activity

bnoordhuis commented on Mar 29, 2017

alutman commented on Mar 30, 2017

Example

bnoordhuis commented on Mar 30, 2017

mscdex commented on Mar 30, 2017

Fishrock123 commented on Mar 30, 2017

addaleax commented on Mar 30, 2017

mscdex commented on Mar 30, 2017

addaleax commented on Mar 30, 2017

mscdex commented on Mar 30, 2017

addaleax commented on Mar 30, 2017

jorangreef commented on Mar 31, 2017

kkoopa commented on Apr 2, 2017

jorangreef commented on Apr 3, 2017

59 remaining items

verdy-p commented on Nov 14, 2018

ljharb commented on Nov 14, 2018

refack commented on Nov 14, 2018

verdy-p commented on Nov 14, 2018

refack commented on Nov 14, 2018

verdy-p commented on Nov 14, 2018

dchest commented on Nov 14, 2018

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions