Am 29.05.19 um 03:17 schrieb Jeff King: > On Wed, May 29, 2019 at 01:34:32AM +0200, René Scharfe wrote: >> Parsing trees with symlinks twice is not ideal, but keeps the set >> structure simple -- a standard oidset suffices. > > If blobs comes after trees (and they usually do in a pack), you can do > it in a single pass by marking the blob as a symlink target, and then > when we actually see that blob's contents, marking it as either OK or > problematic. And then the finish() step just correlates those with the > tree. Good idea. Is that ordering guaranteed? (Stumbling about the "usually" in your first sentence.) An ordering where dependent objects (like trees) follow the objects they reference would be better suited for these kinds of checks.. > It does require O(n) storage in the number of symlinked blobs, but also > O(n) in the number of symlinked tree entries (number of trees with > symlinks times the number of entries in each such tree, _even if they're > the same entry/blob as another tree). > > That makes it a lot worse than the existing gitmodules check. There we > only care about finding the .gitmodules blobs. So even though you have a > ton of trees that mention .gitmodules (basically every root tree), the > the .gitmodules file itself doesn't change much. So we only end up with > a small oidset (and a small worst case for looking at objects twice). > > But here the problem is in the tree, not the blob. So we're not finding > suspect blobs, but rather re-checking each tree. And no matter what we > do (whether it's visiting the object again, or creating a set or mapping > with the object names) is going to be linear there. And a repository > with a symlink in the root tree is going to revisit or put in our > mapping every single root tree. That's true, potentially it needs remember and/or reprocess all trees, meaning this check may double the run time of fsck in the worst case. Example from the wild: The kernel repo currently has 36 symlinks and 6+ million objects are checked in total, and the symlink check processes 18943 trees_with_symlinks entries there. > TBH, I'm not sure this fsck check was worth it even without the > implementation complexity. Hmm. git status reports such truncated symlinks as changed, so the issue *is* already detectable. René
