> (cue dchinner working out that 9 levels is 59 bazillion jillion items, and
> will never be hit?)
I don't know the XFS code and how it does B-trees. This is a very rough initial
estimate that would apply to any sort of tree. Since we want to know when we're
required to exceed a depth of 8, presume a full tree for simplicity. Say your
branching factor for the whole tree is equal to the maximum depth. If it's
higher, you have more room of course. But if it is equal, then you have 8**8
leaf nodes (calling the root node a depth of zero) before you have to add a
depth 9 (or increase your branching factor; if there is a limit that might be
hit, this would be the way to go to avoid more depth).
That gives you about 16 and three quarters million leaf nodes to work with. Of
course if you're storing multiple entries per node, that gives you a constant
factor on top.
In any event, sounds like it may be worth considering whether the limit could
ever be reached and how to extend it if so. Given the discussion that's
occurred about stack size, I could see where recursing on ever-deeper trees
could be problematic, although perhaps it would be possible to use
tail-recursion in anything which doesn't need to scan the full tree at least
(if that's not already done).
Given that XFS has a theoretical maximum filesystem size of 18 Exabytes, for a
hypothetical filesystem composed of 1k sized files (just to be maximally
difficult; worst-case analysis), that's about 2 x 10**16 inodes to store. I'm
sure this would make a lot of other things break first, but it would also blow
past the number of leaves you can have in a tree of maximum height of 8, unless
your branching factor goes above 50. And I doubt more than 100-1000 entries are
being squeezed into a leaf, if that.
Sorry, I don't normally jump into the discussions on here, just follow along,
since I'm not very familiar with the XFS code, but this seemed like an
interesting question which could be partially addressed without any familiarity
with the internals.
I will be curious to read what XFS is actually doing in this area in greater
detail. And I look forward to the XFS test (and rig) that can manage to break
it / exercise the limit...is there any known limit to the number of files?
just lists max file size and file system size. If nothing else, it would be
worth determining the limit and documenting it.