( )⚙ D7411 dirs: resolve fuzzer OOM situation by disallowing deep directory hierarchies

This is an archive of the discontinued Mercurial Phabricator instance.

dirs: resolve fuzzer OOM situation by disallowing deep directory hierarchies
ClosedPublic

Authored by durin42 on Nov 14 2019, 4:22 PM.

Details

Summary

It seems like 2048 directories ought to be enough for any reasonable
use of Mercurial?

A previous version of this patch scanned for slashes before any allocations
occurred. That approach is slower than this in the happy path, but much faster
than this in the case that too many slashes are encountered. We may want to
revisit it in the future using memchr() so it'll be well-optimized by the libc
we're using.

.. bc:

Mercurial will now defend against OOMs by refusing to operate on
paths with 2048 or more components. This means that _extremely_
deep path hierarchies will be rejected, but we anticipate nobody
is using hierarchies this deep.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

durin42 created this revision.Nov 14 2019, 4:22 PM

I support this approach. But I'd feel better if we captured the performance implications. Especially since there is a comment just below talking about how important the loop is for performance.

Perhaps we should add this check to the loop below by checking how m

mercurial/cext/dirs.c
67

What code calls this function? Do we have any good perf numbers for introducing this loop?

I ask because the diffing code is surprisingly impacted by the the "find newlines" stage. Using an implementation that the compiler can expand to SSE/AVX instructions is substantially faster. FWIW glibc and other C implementations have assembly versions of strchr() and memchr(), which could be substantially faster if the compiler isn't smart enough to detect the "count occurrences of chars" pattern.

durin42 edited the summary of this revision. (Show Details)Nov 14 2019, 10:24 PM
durin42 updated this revision to Diff 18112.
durin42 marked an inline comment as done.Nov 14 2019, 10:26 PM
durin42 added inline comments.
mercurial/cext/dirs.c
67

I'd be happy to use memchr() but it occurred to me as I was failing to use memchr() effectively that we already find slashes in a loop here, and there's no risk of on-disk corruption so we can just count slashes as we populate the dict and stop. It's not nearly as fast in the fuzzer, but it does pass for the specific input that we're stuck on.

indygreg accepted this revision.Nov 14 2019, 11:04 PM

This is much better. Thanks.

This revision is now accepted and ready to land.Nov 14 2019, 11:04 PM
durin42 marked an inline comment as done.Nov 14 2019, 11:06 PM
This revision was automatically updated to reflect the committed changes.