Firmlinks on MacOS #153

gstan commented 2020年05月30日 18:42:01 +02:00 (Migrated from code.blicky.net)

ncdu 1.15 does not calculate the size of subdirectories (which was the default behaviour before).

Calling ncdu in a directory (let's call it D) only reports the size of the files in D but not of any subdirectories contained in D.

This was the key feature, which combined with speed made me use ncdu so far.

Is there a way for ncdu to calculate the size of all subdirectories in a given directory as was the case for the previous versions of ncdu? I have read the manual but couldn't find an option to call ncdu to do recursive size calculation.

ncdu 1.15 does not calculate the size of subdirectories (which was the default behaviour before). Calling ncdu in a directory (let's call it D) only reports the size of the files in D but not of any subdirectories contained in D. This was the key feature, which combined with speed made me use ncdu so far. Is there a way for ncdu to calculate the size of all subdirectories in a given directory as was the case for the previous versions of ncdu? I have read the manual but couldn't find an option to call ncdu to do recursive size calculation.

yorhel commented 2020年05月30日 18:48:36 +02:00 (Migrated from code.blicky.net)

Uhm, ncdu still calculates the size of subdirectories to me, no changes there. What OS are you on?

Uhm, ncdu still calculates the size of subdirectories to me, no changes there. What OS are you on?

gstan commented 2020年05月30日 19:41:04 +02:00 (Migrated from code.blicky.net)

I am on macos 10.15.5.

It was working before so I am not sure why it doesn't do it any more.

Also there is a "F" appearing on the first column now for everything (including directories)

I am on macos 10.15.5. It was working before so I am not sure why it doesn't do it any more. Also there is a "F" appearing on the first column now for everything (including directories)

yorhel commented 2020年05月30日 19:44:57 +02:00 (Migrated from code.blicky.net)

That means ncdu recognized it as a firmlink and excluded it, you can use --follow-firmlinks to disable that behavior. See #137 and #151 for more information.

Now the question is: are the missing directories indeed firmlinks or is this a case of false positives?

That means ncdu recognized it as a firmlink and excluded it, you can use `--follow-firmlinks` to disable that behavior. See #137 and #151 for more information. Now the question is: are the missing directories indeed firmlinks or is this a case of false positives?

gstan commented 2020年05月30日 20:54:57 +02:00 (Migrated from code.blicky.net)

Using the option --follow-firmlinks works perfectly. It seems it is a case of false positive as ncdu flags the content of any of my user data directories as 'F' (I have tried extensively in my directory structure). My understanding is that firmlinks should only be for Systems level directories, isn't it?

Using the option `--follow-firmlinks` works perfectly. It seems it is a case of false positive as ncdu flags the content of any of my user data directories as 'F' (I have tried extensively in my directory structure). My understanding is that firmlinks should only be for Systems level directories, isn't it?

yorhel commented 2020年05月30日 21:11:10 +02:00 (Migrated from code.blicky.net)

Hah, don't ask me, I know nothing about MacOS. I rely entirely on user reports and patches. :)

But from the previous bug report I see that /Users is listed as a firmlink, and it's possible that ncdu's detection method considers all directories inside a firmlink to be firmlinks as well. That may not be the most useful option.

Maybe @saagarjha has some ideas about this?

Hah, don't ask me, I know nothing about MacOS. I rely entirely on user reports and patches. :) But from the previous bug report I see that /Users is listed as a firmlink, and it's possible that ncdu's detection method considers all directories *inside* a firmlink to be firmlinks as well. That may not be the most useful option. Maybe @saagarjha has some ideas about this?

gstan commented 2020年05月30日 21:18:15 +02:00 (Migrated from code.blicky.net)

Cheers for your help.

Cheers for your help.

saagarjha commented 2020年06月06日 23:39:29 +02:00 (Migrated from code.blicky.net)

A bit late, but yes, that is currently how firmlink detection works. What I really want is API that tells me "this specific file is a firmlink" but the best I have found so far essentially just lets me determine "if I run firmlink resolution on this file it seems to give me something different so there must have been a firmlink somewhere along the chain". I'm still on the lookout for the former API as it's infinitely more useful, but until then I haven't found anything better :(

A bit late, but yes, that is currently how firmlink detection works. What I *really* want is API that tells me "this specific file is a firmlink" but the best I have found so far essentially just lets me determine "if I run firmlink resolution on this file it seems to give me something different so there must have been a firmlink somewhere along the chain". I'm still on the lookout for the former API as it's infinitely more useful, but until then I haven't found anything better :(

yorhel commented 2020年06月07日 09:31:43 +02:00 (Migrated from code.blicky.net)

I think I'll disable firmlink detection by default and replace --follow-firmlinks with --exclude-firmlinks for now, until we have a better solution that does what we want.

I'm curious what Baobab is doing, it was mentioned in #151 that it does handle firmlinks properly.

I think I'll disable firmlink detection by default and replace `--follow-firmlinks` with `--exclude-firmlinks` for now, until we have a better solution that does what we want. I'm curious what Baobab is doing, it was mentioned in #151 that it does handle firmlinks properly.

saagarjha commented 2020年06月09日 20:50:10 +02:00 (Migrated from code.blicky.net)

I'd guess that it's not calling chdir...

I'd guess that it's not calling `chdir`...

yorhel commented 2020年06月09日 20:54:56 +02:00 (Migrated from code.blicky.net)

Right, that makes sense. So I'm guessing the directories are simply scanned and counted twice. Better than crashing, but not ideal either.

Right, that makes sense. So I'm guessing the directories are simply scanned and counted twice. Better than crashing, but not ideal either.

saagarjha commented 2020年06月25日 00:23:56 +02:00 (Migrated from code.blicky.net)

Quick update: I got in touch with a (the?) firmlinks engineer at Apple and described the issue to him. I'll let you know if that goes anywhere; perhaps some new API might be added to support this usecase.

Quick update: I got in touch with a (the?) firmlinks engineer at Apple and described the issue to him. I'll let you know if that goes anywhere; perhaps some new API might be added to support this usecase.

mattsh commented 2020年06月27日 20:44:37 +02:00 (Migrated from code.blicky.net)

I think I found a workaround. I haven't tested it thoroughly, but perhaps it'll be a starting point to resolve this issue. Granted, if an Apple firmlinks engineer wants to chime in, that's better.

Insight:

realpath() returns the non-firmlinked path. (Technically, it produces the

Desired Behavior:

This is up for debate! I propose that, with --exclude-firmlinks, ncdu should avoid following firmlinks EXCEPT if they were part of the path provided on the command-line.

For example, when traversing, if ncdu runs across "/System/Volumes/Data/Users" (which is a firmlink), it should be:

• skipped if the command-line argument was "/System", but
• traversed into if the command-line argument was "/System/Volumes/Data/Users".

Proposed Solution:

argPath = {path}
argRealPath = realPath(argPath)
while traversing:
 visitPath = {path}
 
 ## NOTE: I don't think files can be firmlinks, but double-check
 if isDir(visitPath):
 chdir(visitPath)
 visitRealPath = realPath(".")
 
 ## since string replacement is more costly than a boolean check,
 ## you can optimize this by testing if "argPath != argRealPath"
 ## before traversal and set "comparison = visitPath" otherwise
 comparison = visitPath.replaceOnTheLeft(argPath, argRealPath)
 
 if comparison == visitRealPath:
 skip ## is a firm link

Examples:

argPath	argRealPath	visitPath	comparison	visitRealPath	skip?	reason
/Users/user	/Users/user	/Users/user/Library/Mail	/Users/user/Library/Mail	/Users/user/Library/Mail	no	not a firmlink
/System/Volumes/Data/Users/user	/Users/user	/System/Volumes/Data/Users/Library/Mail	/Users/user/Library/Mail	/Users/user/Library/Mail	no	firmlink is in argPath
/System	/System	/System/Volumes/Data/Users	/System/Volumes/Data/Users	/Users	yes	is a firmlink beneath argPath
/System/Volumes/Data/Users	/Users	/System/Volumes/Data/Users	/Users	/Users	no	firmlink is in argPath

I think I found a workaround. I haven't tested it thoroughly, but perhaps it'll be a starting point to resolve this issue. Granted, if an Apple firmlinks engineer wants to chime in, that's better. ## Insight: realpath() returns the non-firmlinked path. (Technically, it produces the ## Desired Behavior: This is up for debate! I propose that, with ```--exclude-firmlinks```, ncdu should avoid following firmlinks EXCEPT if they were part of the path provided on the command-line. For example, when traversing, if ncdu runs across "/System/Volumes/Data/Users" (which is a firmlink), it should be: - skipped if the command-line argument was "/System", but - traversed into if the command-line argument was "/System/Volumes/Data/Users". ## Proposed Solution: ``` argPath = {path} argRealPath = realPath(argPath) while traversing: visitPath = {path} ## NOTE: I don't think files can be firmlinks, but double-check if isDir(visitPath): chdir(visitPath) visitRealPath = realPath(".") ## since string replacement is more costly than a boolean check, ## you can optimize this by testing if "argPath != argRealPath" ## before traversal and set "comparison = visitPath" otherwise comparison = visitPath.replaceOnTheLeft(argPath, argRealPath) if comparison == visitRealPath: skip ## is a firm link ``` ## Examples: | argPath | argRealPath | visitPath | comparison | visitRealPath | skip? | reason | |--------------------------------- |------------- |----------------------------------------- |---------------------------- |-------------------------- |------- |------------------------------- | | /Users/user | /Users/user | /Users/user/Library/Mail | /Users/user/Library/Mail | /Users/user/Library/Mail | no | not a firmlink | | /System/Volumes/Data/Users/user | /Users/user | /System/Volumes/Data/Users/Library/Mail | /Users/user/Library/Mail | /Users/user/Library/Mail | no | firmlink is in argPath | | /System | /System | /System/Volumes/Data/Users | /System/Volumes/Data/Users | /Users | yes | is a firmlink beneath argPath | | /System/Volumes/Data/Users | /Users | /System/Volumes/Data/Users | /Users | /Users | no | firmlink is in argPath |

mattsh commented 2020年06月27日 20:49:20 +02:00 (Migrated from code.blicky.net)

Oops - I didn't mean to post yet.

I was going to clarify that technically /System/Volumes/Data/Users is the original path and /Users is the firmlink. However, I would presume most users' expected behavior (if one will be skipped) is to traverse /Users and skip /System/Volumes/Data/Users.

I'm not sure what you'd call the source of a firmlink (I guess "firmlink source" would work?), but for the sake of simplicity I just referred to it as a firmlink above since that's what most people will think of it as. ncdu's documentation might want to be more correct ;)

Oops - I didn't mean to post yet. I was going to clarify that technically ```/System/Volumes/Data/Users``` is the original path and ```/Users``` is the firmlink. However, I would presume most users' expected behavior (if one will be skipped) is to traverse ```/Users``` and skip ```/System/Volumes/Data/Users```. I'm not sure what you'd call the source of a firmlink (I guess "firmlink source" would work?), but for the sake of simplicity I just referred to it as a firmlink above since that's what most people will think of it as. ncdu's documentation might want to be more correct ;)

saagarjha commented 2020年06月27日 21:52:25 +02:00 (Migrated from code.blicky.net)

So just to update you with what I asked the engineer for: I wanted API that would essentially tell me if a file was a "firmlink source", so when we do our recursive descent we'd hit /System/Volumes/Data and see that we shouldn't go through that link. This would also mean that data appears at /Users instead of /System/Volumes/Data/Users, etc. I was told that this API does not exist and why it doesn't, although he seemed very interested in this use case so I personally think we might see something for this in the future. So until then we're basically stuck using the various APIs that get some other path to the file with/without firmlinks and comparing it to what we think the path should be as we chdir through the heirarchy and using that to determine whether we should we want to follow the link or not.

There is room to improve the behavior, as I agree it is nonobvious, but it is important that we never end up in a looping if the user puts in the wrong thing. (For example, in your case I believe specifying /System/Volumes/Data/ would lead to a loop.) Another concern is performance, which is one of the reasons I dropped a previous open/fcntl strategy that produced slightly better results: it was slow :(

Oh, and I should probably mention that all of these approaches (including the one currently in use) totally destory the meaning of symlinks, so I guess that will just have to be collateral damage we'll have to deal with until we get a real API for this kind of thing. As for firmlinks pointing to files: they don't currently, but I don't know where this will lead in the future. APFS does not allow hardlinking files, but it doesn't use hardlinks for firmlinks anyways, since they can't span volumes. They're really just some kernel-level magic replacement on vnodes. I was considering asking whether there might be more firmlinks added (so we could just hardcode the ones that already exist) or if users will be able to modify them at some point but decided against it because it probably wasn't worth wasting time on a question that wasn't going to be answered...

So just to update you with what I asked the engineer for: I wanted API that would essentially tell me if a file was a "firmlink source", so when we do our recursive descent we'd hit /System/Volumes/Data and see that we shouldn't go through that link. This would also mean that data appears at /Users instead of /System/Volumes/Data/Users, etc. I was told that this API does not exist and why it doesn't, although he seemed very interested in this use case so I personally think we might see something for this in the future. So until then we're basically stuck using the various APIs that get some other path to the file with/without firmlinks and comparing it to what we think the path should be as we `chdir` through the heirarchy and using that to determine whether we should we want to follow the link or not. There is room to improve the behavior, as I agree it is nonobvious, but it is important that we never end up in a looping if the user puts in the wrong thing. (For example, in your case I believe specifying `/System/Volumes/Data/` would lead to a loop.) Another concern is performance, which is one of the reasons I dropped a previous `open`/`fcntl` strategy that produced slightly better results: it was slow :( Oh, and I should probably mention that all of these approaches (including the one currently in use) totally destory the meaning of symlinks, so I guess that will just have to be collateral damage we'll have to deal with until we get a real API for this kind of thing. As for firmlinks pointing to files: they don't currently, but I don't know where this will lead in the future. APFS does not allow hardlinking files, but it doesn't use hardlinks for firmlinks anyways, since they can't span volumes. They're really just some kernel-level magic replacement on vnodes. I was considering asking whether there might be more firmlinks added (so we could just hardcode the ones that already exist) or if users will be able to modify them at some point but decided against it because it probably wasn't worth wasting time on a question that wasn't going to be answered...

mattsh commented 2020年06月27日 23:54:41 +02:00 (Migrated from code.blicky.net)

Hi @saagarjha,

Thanks for catching my typo! I meant "!=", not "==", a big difference :(. I was correct with my table of examples but not the pseudocode. With that fixed, I don't see how cycles could be left uncaught. It seems to work as expected. See example below.

argPath = "/System/Volumes/Data"
argRealPath is "/System/Volumes/Data" # { chdir argPath, realpath "." }
visitPath is "/System/Volumes/Data/Users"
comparison is "/System/Volumes/Data/Users" # the replace changes nothing
visitRealPath is "/Users" # realpath(visitPath)
comparison != visitRealPath is False # it's a firmlink source

Also, I'm not sure if you are aware, but /System/Volumes/Data is not a firmlink source. It is a mountpoint that holds a bunch of them, so realpath doesn't differ from the path until you traverse into one of its subdirectories. You can see a list of firmlink sources in the file /usr/share/firmlinks. Example:

-> cd /System/Volumes/Data/usr/libexec
-> realpath .
/System/Volumes/Data/usr/libexec
-> ls
cups
-> cd cups
-> realpath .
/usr/libexec/cups
-> cd /usr/libexec
-> ls
...a bunch of files and directories...

Lastly, this is a bit off-topic, but APFS definitely does allow hardlinking of files. Example:

-> echo -n a > a
-> ln a b
-> cat a b
aa
-> echo -n b >> b
abab

Do you see any remaining issues with this approach besides that it would be better to depend on an Apple-provided API?

Another (simpler) stop-gap solution would be to just skip traversal of /System/Volumes/Data or /System/Volumes if firmlinks are ignored since it (currently) is just a container for firmlink sources, and AFAIK there aren't any other firmlink sources in macOS. I haven't checked the macOS Big Sur Beta, though, and obviously this approach could break in the future if Apple adds more firmlinks.

Hi @saagarjha, Thanks for catching my typo! I meant "!=", not "==", a big difference :(. I was correct with my table of examples but not the pseudocode. With that fixed, I don't see how cycles could be left uncaught. It seems to work as expected. See example below. ```python argPath = "/System/Volumes/Data" argRealPath is "/System/Volumes/Data" # { chdir argPath, realpath "." } visitPath is "/System/Volumes/Data/Users" comparison is "/System/Volumes/Data/Users" # the replace changes nothing visitRealPath is "/Users" # realpath(visitPath) comparison != visitRealPath is False # it's a firmlink source ``` Also, I'm not sure if you are aware, but ```/System/Volumes/Data``` is **not** a firmlink source. It is a mountpoint that holds a bunch of them, so realpath doesn't differ from the path until you traverse into one of its subdirectories. You can see a list of firmlink sources in the file ```/usr/share/firmlinks```. Example: ```bash -> cd /System/Volumes/Data/usr/libexec -> realpath . /System/Volumes/Data/usr/libexec -> ls cups -> cd cups -> realpath . /usr/libexec/cups -> cd /usr/libexec -> ls ...a bunch of files and directories... ``` Lastly, this is a bit off-topic, but APFS definitely does allow hardlinking of files. Example: ```bash -> echo -n a > a -> ln a b -> cat a b aa -> echo -n b >> b abab ``` Do you see any remaining issues with this approach besides that it would be better to depend on an Apple-provided API? Another (simpler) stop-gap solution would be to just skip traversal of ```/System/Volumes/Data``` or ```/System/Volumes``` if firmlinks are ignored since it (currently) is just a container for firmlink sources, and AFAIK there aren't any other firmlink sources in macOS. I haven't checked the macOS Big Sur Beta, though, and obviously this approach could break in the future if Apple adds more firmlinks.

mattsh commented 2020年06月27日 23:58:02 +02:00 (Migrated from code.blicky.net)

Also, in case it helps, this is a list of all firmlinks currently specified in macOS 10.15.4:

/System/Volumes/Data/AppleInternal
/System/Volumes/Data/Applications
/System/Volumes/Data/Library
/System/Volumes/Data/System/Library/Caches
/System/Volumes/Data/System/Library/Assets
/System/Volumes/Data/System/Library/PreinstalledAssets
/System/Volumes/Data/System/Library/AssetsV2
/System/Volumes/Data/System/Library/PreinstalledAssetsV2
/System/Volumes/Data/System/Library/CoreServices/CoreTypes.bundle/Contents/Library
/System/Volumes/Data/System/Library/Speech
/System/Volumes/Data/Users
/System/Volumes/Data/Volumes
/System/Volumes/Data/cores
/System/Volumes/Data/opt
/System/Volumes/Data/private
/System/Volumes/Data/usr/local
/System/Volumes/Data/usr/libexec/cups
/System/Volumes/Data/usr/share/snmp

Also, in case it helps, this is a list of all firmlinks currently specified in macOS 10.15.4: ```text /System/Volumes/Data/AppleInternal /System/Volumes/Data/Applications /System/Volumes/Data/Library /System/Volumes/Data/System/Library/Caches /System/Volumes/Data/System/Library/Assets /System/Volumes/Data/System/Library/PreinstalledAssets /System/Volumes/Data/System/Library/AssetsV2 /System/Volumes/Data/System/Library/PreinstalledAssetsV2 /System/Volumes/Data/System/Library/CoreServices/CoreTypes.bundle/Contents/Library /System/Volumes/Data/System/Library/Speech /System/Volumes/Data/Users /System/Volumes/Data/Volumes /System/Volumes/Data/cores /System/Volumes/Data/opt /System/Volumes/Data/private /System/Volumes/Data/usr/local /System/Volumes/Data/usr/libexec/cups /System/Volumes/Data/usr/share/snmp ```

mattsh commented 2020年06月27日 23:58:31 +02:00 (Migrated from code.blicky.net)

Correction: a list of all firmlink sources.

Correction: a list of all firmlink sources.

yorhel commented 2021年07月24日 08:45:28 +02:00 (Migrated from code.blicky.net)

I'm curious how ncdu 2.0-beta1 fares with firmlinks, if anyone's willing to test (tbh, I'm not sure it even works on MacOS at all yet, that's worth testing too). It does not use the chdir() approach anymore, so it at least shouldn't get stuck in an infinite loop.

I'm curious how ncdu 2.0-beta1 fares with firmlinks, if anyone's willing to test (tbh, I'm not sure it even works on MacOS at all yet, that's worth testing too). It does not use the chdir() approach anymore, so it at least shouldn't get stuck in an infinite loop.

saagarjha commented 2021年07月24日 12:07:13 +02:00 (Migrated from code.blicky.net)

@yorhel I see that you've rewritten ncdu in Zig? An interesting surprise ;) For the most part, it seems to look and function the same as the old ncdu, so you've done a good job there.

To answer your question: no, ncdu no longer gets stuck in the firmlink loop anymore, so that's good. It is double-counting the directories, which is not surprising, but that should be fixable with one of the firmlink detection workarounds we were using before. (Perhaps we should "reverse" the check this time?)

---

For the other comments above: apparently I missed them in my inbox. Sorry about that! @mattsh, you're right about APFS supporting file hardlinks, I really meant directory hardlinks, which were a casualty of the HFS+ → APFS transition. I may have been a little confused about your "firmlink source" terminology, but I think we agree on the desirable behavior, let's see if it is possible to implement this time around.

@yorhel I see that you've rewritten ncdu in Zig? An interesting surprise ;) For the most part, it seems to look and function the same as the old ncdu, so you've done a good job there. To answer your question: no, ncdu no longer gets stuck in the firmlink loop anymore, so that's good. It is double-counting the directories, which is not surprising, but that should be fixable with one of the firmlink detection workarounds we were using before. (Perhaps we should "reverse" the check this time?) --- For the other comments above: apparently I missed them in my inbox. Sorry about that! @mattsh, you're right about APFS supporting file hardlinks, I really meant directory hardlinks, which were a casualty of the HFS+ → APFS transition. I may have been a little confused about your "firmlink source" terminology, but I think we agree on the desirable behavior, let's see if it is possible to implement this time around.

yorhel commented 2021年07月25日 08:28:35 +02:00 (Migrated from code.blicky.net)

So it works on MacOS? Cool!

As a way of preventing the double counting, I was just thinking of parallels to bind mounts on Linux. From my understanding, both firmlinks and bind mounts have a "source" and "target" directory. If both directories are children of the dir that ncdu is scanning, the "target" directory should be skipped. If the source dir is outside of ncdu's scanning scope, then the target dir should (probably?) be scanned anyway.

Rather than probing each directory with obscure system calls, I think a simpler approach might be to read /usr/share/firmlinks to get a full list of firmlinked paths, then do some path comparison magic against the path that the user asked to be scanned, and treat duplicated target directories as something of an exclude pattern. This approach should work equally well for bind mounts.

Thoughts?

So it works on MacOS? Cool! As a way of preventing the double counting, I was just thinking of parallels to bind mounts on Linux. From my understanding, both firmlinks and bind mounts have a "source" and "target" directory. If both directories are children of the dir that ncdu is scanning, the "target" directory should be skipped. If the source dir is outside of ncdu's scanning scope, then the target dir should (probably?) be scanned anyway. Rather than probing each directory with obscure system calls, I think a simpler approach might be to read `/usr/share/firmlinks` to get a full list of firmlinked paths, then do some path comparison magic against the path that the user asked to be scanned, and treat duplicated target directories as something of an exclude pattern. This approach should work equally well for bind mounts. Thoughts?

thrway commented 2022年03月11日 15:48:03 +01:00 (Migrated from code.blicky.net)

With the removal of the --exclude-firmlinks option I'm currently using the following command as work-around:

ncdu / $(cut -f1 /usr/share/firmlinks | while read DIR; do /bin/echo -n "--exclude $DIR "; done)

It would be useful if the firmlink exclusion could be restored as feature of ncdu.

With the removal of the `--exclude-firmlinks` option I'm currently using the following command as work-around: ```sh ncdu / $(cut -f1 /usr/share/firmlinks | while read DIR; do /bin/echo -n "--exclude $DIR "; done) ``` It would be useful if the firmlink exclusion could be restored as feature of `ncdu`.