Node occasionally gives multiple files/folders the same inode

[alutman]

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]));
})

[bnoordhuis]

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.

[alutman]

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.

[bnoordhuis]

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.

[mscdex]

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.

[Fishrock123]

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

[addaleax]

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.

[mscdex]

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.

[addaleax]

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.

[mscdex]

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?

[addaleax]

@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).

[jorangreef]

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.

[kkoopa]

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

[jorangreef]

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.