[CachePruning] Clarify the per-directory entry limit on Linux ext4.

[MaskRay]

Summary

508 root node entries (root_limit)
510 internal node entries (node_limit)

For a filename with 40 bytes, its sizeof(ext4_dir_entry_2) = 48, a linear directory can contain at most floor(4096/48)=85 of them.
The real per-directory entry limit should be 508*510*85 = 22021800
The limit varies with the average length of filenames.

However, the Linux ext4 code does not try rebalancing the htree, so we will not be able to create filenames in a full leaf node. This is demonstrated with the following example, certain filenames cannot be used while others can:

% touch d/0000000000000000000000000000000000816a6f
touch: cannot touch 'd/0000000000000000000000000000000000816a6f': No
space left on device
% touch d/0000000000000000000000000000000000816a70
# succeeded

[pcc]

include/llvm/Support/CachePruning.h

55–61

Update this bit.

56

My first instinct is not to add this much detail, but I guess it might dissuade the next person who comes along to try to "correct" this comment.

[MaskRay]

include/llvm/Support/CachePruning.h

55–61

Change to what?

56

Yeah I did not want to write the comment but you asked me to do so..

[pcc]

include/llvm/Support/CachePruning.h

55–61

The second sentence does not follow from the first because the second is about files in a directory and the first is about total files. I might just say something like "some file systems have a limit on the total number of files, and some also limit the number of files per directory, such as ext4, which has a default limit of about 10M."

56

If you write something like the above, it should probably be enough.

[MaskRay]

reword

[pcc]

Close enough.

include/llvm/Support/CachePruning.h

55

Remove sentence as it is duplicated below.

include/llvm/Support/CachePruning.h

struct CachePruningPolicy {
   /// of available space on the disk will be reduced to the amount of available
   /// space. A value of 0 disables the absolute size-based pruning.
   uint64_t MaxSizeBytes = 0;
 
   /// The maximum number of files in the cache directory. A value of 0 disables
   /// the number of files based pruning.
   ///
   /// This defaults to 1000000 because with that many files there are
-  /// diminishing returns on the effectiveness of the cache, and file
-  /// systems have a limit on total number of files.
+  /// diminishing returns on the effectiveness of the cache. Some systems have
+  /// a limit on total number of files.
+  /// Some file systems have a limit on the total number of files, and some also
+  /// limit the number of files per directory, such as Linux ext4, with the
+  /// default setting (block size is 4096 and large_dir disabled), there is a
+  /// per-directory entry limit of 508*510*floor(4096/(40+8))~=20M for average
+  /// filename length of 40.
   uint64_t MaxSizeFiles = 1000000;
 };
 
 /// Parse the given string as a cache pruning policy. Defaults are taken from a
 /// default constructed CachePruningPolicy object.
 /// For example: "prune_interval=30s:prune_after=24h:cache_size=50%"
 /// which means a pruning interval of 30 seconds, expiration time of 24 hours
 /// and maximum cache size of 50% of available disk space.