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

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D7411

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

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

Details

Reviewers
indygreg
Group Reviewers
hg-reviewers
Commits
rHG0796e266d26b: dirs: resolve fuzzer OOM situation by disallowing deep directory hierarchies
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
indygreg added a subscriber: indygreg.Nov 14 2019, 10:04 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
durin42 added a commit: rHG0796e266d26b: dirs: resolve fuzzer OOM situation by disallowing deep directory hierarchies.
Closed by commit rHG0796e266d26b: dirs: resolve fuzzer OOM situation by disallowing deep directory hierarchies (authored by durin42). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mmercurial/cext/dirs.c (14 lines)

Diff 18143

mercurial/cext/dirs.c

/* /*
dirs.c - dynamic directory diddling for dirstates dirs.c - dynamic directory diddling for dirstates
Copyright 2013 Facebook Copyright 2013 Facebook
This software may be used and distributed according to the terms of This software may be used and distributed according to the terms of
the GNU General Public License, incorporated herein by reference. the GNU General Public License, incorporated herein by reference.
*/ */
#define PY_SSIZE_T_CLEAN #define PY_SSIZE_T_CLEAN
#include <Python.h> #include <Python.h>
#include <string.h>
#include "util.h" #include "util.h"
#ifdef IS_PY3K #ifdef IS_PY3K
#define PYLONG_VALUE(o) ((PyLongObject *)o)->ob_digit[1] #define PYLONG_VALUE(o) ((PyLongObject *)o)->ob_digit[1]
#else #else
#define PYLONG_VALUE(o) PyInt_AS_LONG(o) #define PYLONG_VALUE(o) PyInt_AS_LONG(o)
#endif #endif
} }
if (pos == -1) { if (pos == -1) {
return 0; return 0;
} }
return pos; return pos;
} }
/* Mercurial will fail to run on directory hierarchies deeper than
* this constant, so we should try and keep this constant as big as
* possible.
*/
#define MAX_DIRS_DEPTH 2048
static int _addpath(PyObject *dirs, PyObject *path) static int _addpath(PyObject *dirs, PyObject *path)
{ {
const char *cpath = PyBytes_AS_STRING(path); const char *cpath = PyBytes_AS_STRING(path);
Py_ssize_t pos = PyBytes_GET_SIZE(path); Py_ssize_t pos = PyBytes_GET_SIZE(path);
PyObject *key = NULL; PyObject *key = NULL;
int ret = -1; int ret = -1;
size_t num_slashes = 0;
/* This loop is super critical for performance. That's why we inline /* This loop is super critical for performance. That's why we inline
* access to Python structs instead of going through a supported API. * access to Python structs instead of going through a supported API.
indygregUnsubmitted
Done

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.

indygreg: What code calls this function? Do we have any good perf numbers for introducing this loop? I…
durin42AuthorUnsubmitted
Done

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.

durin42: I'd be happy to use memchr() but it occurred to me as I was failing to use memchr()…
* The implementation, therefore, is heavily dependent on CPython * The implementation, therefore, is heavily dependent on CPython
* implementation details. We also commit violations of the Python * implementation details. We also commit violations of the Python
* "protocol" such as mutating immutable objects. But since we only * "protocol" such as mutating immutable objects. But since we only
* mutate objects created in this function or in other well-defined * mutate objects created in this function or in other well-defined
* locations, the references are known so these violations should go * locations, the references are known so these violations should go
* unnoticed. */ * unnoticed. */
while ((pos = _finddir(cpath, pos - 1)) != -1) { while ((pos = _finddir(cpath, pos - 1)) != -1) {
PyObject *val; PyObject *val;
++num_slashes;
if (num_slashes > MAX_DIRS_DEPTH) {
PyErr_SetString(PyExc_ValueError,
"Directory hierarchy too deep.");
goto bail;
}
/* Sniff for trailing slashes, a marker of an invalid input. */ /* Sniff for trailing slashes, a marker of an invalid input. */
if (pos > 0 && cpath[pos - 1] == '/') { if (pos > 0 && cpath[pos - 1] == '/') {
PyErr_SetString( PyErr_SetString(
PyExc_ValueError, PyExc_ValueError,
"found invalid consecutive slashes in path"); "found invalid consecutive slashes in path");
goto bail; goto bail;
} }