{"thread":{"id":"51561","subject":"[PATCH 0/6] harden tree-walking against integer overflow","startedAt":"2019-07-31T04:37:02Z","lastAt":"2019-08-01T18:17:35Z","messageCount":8,"participants":["Jeff King","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"379640","messageId":"20190731043659.GA27028@sigill.intra.peff.net","threadId":"51561","inReplyTo":null,"subject":"[PATCH 0/6] harden tree-walking against integer overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-07-31T04:37:00Z","receivedAt":"2019-07-31T04:37:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I noticed that it's possible to get funny integer over/underflows with\ntree-walk's traverse_info (with specially-crafted absurdly-sized tree\npaths). I wasn't able to turn this into an actual buffer overflow\nbecause the funky sizes cause allocation failures way before we ever get\ninto make_traverse_path(). But it makes sense to protect ourselves\nanyway.\n\nThe first two patches are an unrelated memory problem I found (and\nthey're here in the same series because I build on the cleanups). I\ndon't think it's security-relevant, though; it involves reading from\nuninitialized heap memory, but we don't actually _do_ anything with the\nresult. We just copy uninitialized bytes from one heap buffer to the\nother, and then never look at them again.\n\n  [1/6]: setup_traverse_info(): stop copying oid\n  [2/6]: tree-walk: drop oid from traverse_info\n  [3/6]: tree-walk: use size_t consistently\n  [4/6]: tree-walk: accept a raw length for traverse_path_len()\n  [5/6]: tree-walk: add a strbuf wrapper for make_traverse_path()\n  [6/6]: tree-walk: harden make_traverse_path() length computations\n\n Documentation/technical/api-tree-walking.txt |  8 ++-\n builtin/merge-tree.c                         |  5 +-\n cache-tree.c                                 |  2 +-\n tree-walk.c                                  | 64 +++++++++++------\n tree-walk.h                                  | 18 +++--\n unpack-trees.c                               | 74 +++++++++++---------\n 6 files changed, 103 insertions(+), 68 deletions(-)\n\n-Peff\n"},{"id":"379641","messageId":"20190731043811.GA27170@sigill.intra.peff.net","threadId":"51561","inReplyTo":"20190731043659.GA27028@sigill.intra.peff.net","subject":"[PATCH 1/6] setup_traverse_info(): stop copying oid","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-07-31T04:38:11Z","receivedAt":"2019-07-31T04:38:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We assume that if setup_traverse_info() is passed a non-empty \"base\"\nstring, that string is pointing into a tree object and we can read the\nobject oid by skipping past the trailing NUL.\n\nAs it turns out, this is not true for either of the two calls, and we\nmay end up reading garbage bytes:\n\n  1. In git-merge-tree, our base string is either empty (in which case\n     we'd never run this code), or it comes from our traverse_path()\n     helper. The latter overallocates a buffer by the_hash_algo->rawsz\n     bytes, but then fills it with only make_traverse_path(), leaving\n     those extra bytes uninitialized (but part of a legitimate heap\n     buffer).\n\n  2. In unpack_trees(), we pass o->prefix, which is some arbitrary\n     string from the caller. In \"git read-tree --prefix=foo\", for\n     instance, it will point to the command-line parameter, and we'll\n     read 20 bytes past the end of the string.\n\nInterestingly, tools like ASan do not detect (2) because the process\nargv is part of a big pre-allocated buffer. So we're reading trash, but\nit's trash that's probably part of the next argument, or the\nenvironment.\n\nYou can convince it to fail by putting something like this at the\nbeginning of common-main.c's main() function:\n\n  {\n\tint i;\n\tfor (i = 0; i < argc; i++)\n\t\targv[i] = xstrdup_or_null(argv[i]);\n  }\n\nThat puts the arguments into their own heap buffers, so running:\n\n  make SANITIZE=address test\n\nwill find problems when \"read-tree --prefix\" is used (e.g., in t3030).\n\nDoubly interesting, even with the hackery above, this does not fail\nprior to ea82b2a085 (tree-walk: store object_id in a separate member,\n2019-01-15). That commit switched setup_traverse_info() to actually\ncopying the hash, rather than simply pointing to it. That pointer was\nalways pointing to garbage memory, but that commit started actually\ndereferencing the bytes, which is what triggers ASan.\n\nThat also implies that nobody actually cares about reading these oid\nbytes anyway (or at least no path covered by our tests). And manual\ninspection of the code backs that up (I'll follow this patch with some\ncleanups that show definitively this is the case, but they're quite\ninvasive, so it's worth doing this fix on its own).\n\nSo let's drop the bogus hashcpy(), along with the confusing oversizing\nin merge-tree.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n Documentation/technical/api-tree-walking.txt | 4 +---\n builtin/merge-tree.c                         | 2 +-\n tree-walk.c                                  | 4 +---\n 3 files changed, 3 insertions(+), 7 deletions(-)\n\ndiff --git a/Documentation/technical/api-tree-walking.txt b/Documentation/technical/api-tree-walking.txt\nindex bde18622a8..59d78e0362 100644\n--- a/Documentation/technical/api-tree-walking.txt\n+++ b/Documentation/technical/api-tree-walking.txt\n@@ -62,9 +62,7 @@ Initializing\n `setup_traverse_info`::\n \n \tInitialize a `traverse_info` given the pathname of the tree to start\n-\ttraversing from. The `base` argument is assumed to be the `path`\n-\tmember of the `name_entry` being recursed into unless the tree is a\n-\ttop-level tree in which case the empty string (\"\") is used.\n+\ttraversing from.\n \n Walking\n -------\ndiff --git a/builtin/merge-tree.c b/builtin/merge-tree.c\nindex 97b54caeb9..dccdaf7852 100644\n--- a/builtin/merge-tree.c\n+++ b/builtin/merge-tree.c\n@@ -180,7 +180,7 @@ static struct merge_list *create_entry(unsigned stage, unsigned mode, const stru\n \n static char *traverse_path(const struct traverse_info *info, const struct name_entry *n)\n {\n-\tchar *path = xmallocz(traverse_path_len(info, n) + the_hash_algo->rawsz);\n+\tchar *path = xmallocz(traverse_path_len(info, n));\n \treturn make_traverse_path(path, info, n);\n }\n \ndiff --git a/tree-walk.c b/tree-walk.c\nindex c20b62f49e..0de4d577bb 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -179,10 +179,8 @@ void setup_traverse_info(struct traverse_info *info, const char *base)\n \tinfo->pathlen = pathlen ? pathlen + 1 : 0;\n \tinfo->name.path = base;\n \tinfo->name.pathlen = pathlen;\n-\tif (pathlen) {\n-\t\thashcpy(info->name.oid.hash, (const unsigned char *)base + pathlen + 1);\n+\tif (pathlen)\n \t\tinfo->prev = &dummy;\n-\t}\n }\n \n char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)\n-- \n2.23.0.rc0.426.gbdee707ba7\n\n"},{"id":"379642","messageId":"20190731043815.GB27170@sigill.intra.peff.net","threadId":"51561","inReplyTo":"20190731043659.GA27028@sigill.intra.peff.net","subject":"[PATCH 2/6] tree-walk: drop oid from traverse_info","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-07-31T04:38:15Z","receivedAt":"2019-07-31T04:38:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"As the previous commit shows, the presence of an oid in each level of\nthe traverse_info is confusing and ultimately not necessary. Let's drop\nit to make it clear that it will not always be set (as well as convince\nus that it's unused, and let the compiler catch any merges with other\nbranches that do add new uses).\n\nSince the oid is part of name_entry, we'll actually stop embedding a\nname_entry entirely, and instead just separately hold the pathname, its\nlength, and the mode.\n\nThis makes the resulting code slightly more verbose as we have to pass\nthose elements around individually. But it also makes it more clear what\neach code path is going to use (and in most of the paths, we really only\ncare about the pathname itself).\n\nA few of these conversions are noisier than they need to be, as they\nalso take the opportunity to rename \"len\" to \"namelen\" for clarity\n(especially where we also have \"pathlen\" or \"ce_len\" alongside).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/merge-tree.c |  2 +-\n cache-tree.c         |  2 +-\n tree-walk.c          | 23 ++++++++++---------\n tree-walk.h          |  8 +++++--\n unpack-trees.c       | 53 ++++++++++++++++++++++++--------------------\n 5 files changed, 49 insertions(+), 39 deletions(-)\n\ndiff --git a/builtin/merge-tree.c b/builtin/merge-tree.c\nindex dccdaf7852..d8ace972c7 100644\n--- a/builtin/merge-tree.c\n+++ b/builtin/merge-tree.c\n@@ -181,7 +181,7 @@ static struct merge_list *create_entry(unsigned stage, unsigned mode, const stru\n static char *traverse_path(const struct traverse_info *info, const struct name_entry *n)\n {\n \tchar *path = xmallocz(traverse_path_len(info, n));\n-\treturn make_traverse_path(path, info, n);\n+\treturn make_traverse_path(path, info, n->path, n->pathlen);\n }\n \n static void resolve(const struct traverse_info *info, struct name_entry *ours, struct name_entry *result)\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 706ffcf188..c22161f987 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -713,7 +713,7 @@ static struct cache_tree *find_cache_tree_from_traversal(struct cache_tree *root\n \tif (!info->prev)\n \t\treturn root;\n \tour_parent = find_cache_tree_from_traversal(root, info->prev);\n-\treturn cache_tree_find(our_parent, info->name.path);\n+\treturn cache_tree_find(our_parent, info->name);\n }\n \n int cache_tree_matches_traversal(struct cache_tree *root,\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 0de4d577bb..130d9f32f2 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -177,27 +177,27 @@ void setup_traverse_info(struct traverse_info *info, const char *base)\n \tif (pathlen && base[pathlen-1] == '/')\n \t\tpathlen--;\n \tinfo->pathlen = pathlen ? pathlen + 1 : 0;\n-\tinfo->name.path = base;\n-\tinfo->name.pathlen = pathlen;\n+\tinfo->name = base;\n+\tinfo->namelen = pathlen;\n \tif (pathlen)\n \t\tinfo->prev = &dummy;\n }\n \n-char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)\n+char *make_traverse_path(char *path, const struct traverse_info *info,\n+\t\t\t const char *name, size_t namelen)\n {\n-\tint len = tree_entry_len(n);\n \tint pathlen = info->pathlen;\n \n-\tpath[pathlen + len] = 0;\n+\tpath[pathlen + namelen] = 0;\n \tfor (;;) {\n-\t\tmemcpy(path + pathlen, n->path, len);\n+\t\tmemcpy(path + pathlen, name, namelen);\n \t\tif (!pathlen)\n \t\t\tbreak;\n \t\tpath[--pathlen] = '/';\n-\t\tn = &info->name;\n-\t\tlen = tree_entry_len(n);\n+\t\tname = info->name;\n+\t\tnamelen = info->namelen;\n \t\tinfo = info->prev;\n-\t\tpathlen -= len;\n+\t\tpathlen -= namelen;\n \t}\n \treturn path;\n }\n@@ -399,12 +399,13 @@ int traverse_trees(struct index_state *istate,\n \n \tif (info->prev) {\n \t\tstrbuf_grow(&base, info->pathlen);\n-\t\tmake_traverse_path(base.buf, info->prev, &info->name);\n+\t\tmake_traverse_path(base.buf, info->prev, info->name,\n+\t\t\t\t   info->namelen);\n \t\tbase.buf[info->pathlen-1] = '/';\n \t\tstrbuf_setlen(&base, info->pathlen);\n \t\ttraverse_path = xstrndup(base.buf, info->pathlen);\n \t} else {\n-\t\ttraverse_path = xstrndup(info->name.path, info->pathlen);\n+\t\ttraverse_path = xstrndup(info->name, info->pathlen);\n \t}\n \tinfo->traverse_path = traverse_path;\n \tfor (;;) {\ndiff --git a/tree-walk.h b/tree-walk.h\nindex 2a5db29e8f..2c59caa38a 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -58,7 +58,10 @@ enum get_oid_result get_tree_entry_follow_symlinks(struct repository *r, struct\n struct traverse_info {\n \tconst char *traverse_path;\n \tstruct traverse_info *prev;\n-\tstruct name_entry name;\n+\tconst char *name;\n+\tsize_t namelen;\n+\tunsigned mode;\n+\n \tint pathlen;\n \tstruct pathspec *pathspec;\n \n@@ -69,7 +72,8 @@ struct traverse_info {\n };\n \n int get_tree_entry(struct repository *, const struct object_id *, const char *, struct object_id *, unsigned short *);\n-char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n);\n+char *make_traverse_path(char *path, const struct traverse_info *info,\n+\t\t\t const char *name, size_t namelen);\n void setup_traverse_info(struct traverse_info *info, const char *base);\n \n static inline int traverse_path_len(const struct traverse_info *info, const struct name_entry *n)\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 62276d4fef..63cbddead8 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -632,7 +632,7 @@ static int unpack_index_entry(struct cache_entry *ce,\n \treturn ret;\n }\n \n-static int find_cache_pos(struct traverse_info *, const struct name_entry *);\n+static int find_cache_pos(struct traverse_info *, const char *p, size_t len);\n \n static void restore_cache_bottom(struct traverse_info *info, int bottom)\n {\n@@ -651,7 +651,7 @@ static int switch_cache_bottom(struct traverse_info *info)\n \tif (o->diff_index_cached)\n \t\treturn 0;\n \tret = o->cache_bottom;\n-\tpos = find_cache_pos(info->prev, &info->name);\n+\tpos = find_cache_pos(info->prev, info->name, info->namelen);\n \n \tif (pos < -1)\n \t\to->cache_bottom = -2 - pos;\n@@ -690,7 +690,7 @@ static int index_pos_by_traverse_info(struct name_entry *names,\n \tchar *name = xmalloc(len + 1 /* slash */ + 1 /* NUL */);\n \tint pos;\n \n-\tmake_traverse_path(name, info, names);\n+\tmake_traverse_path(name, info, names->path, names->pathlen);\n \tname[len++] = '/';\n \tname[len] = '\\0';\n \tpos = index_name_pos(o->src_index, name, len);\n@@ -811,7 +811,9 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n \tnewinfo = *info;\n \tnewinfo.prev = info;\n \tnewinfo.pathspec = info->pathspec;\n-\tnewinfo.name = *p;\n+\tnewinfo.name = p->path;\n+\tnewinfo.namelen = p->pathlen;\n+\tnewinfo.mode = p->mode;\n \tnewinfo.pathlen += tree_entry_len(p) + 1;\n \tnewinfo.df_conflicts |= df_conflicts;\n \n@@ -863,14 +865,18 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n  * itself - the caller needs to do the final check for the cache\n  * entry having more data at the end!\n  */\n-static int do_compare_entry_piecewise(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)\n+static int do_compare_entry_piecewise(const struct cache_entry *ce,\n+\t\t\t\t      const struct traverse_info *info,\n+\t\t\t\t      const char *name, size_t namelen,\n+\t\t\t\t      unsigned mode)\n {\n-\tint len, pathlen, ce_len;\n+\tint pathlen, ce_len;\n \tconst char *ce_name;\n \n \tif (info->prev) {\n \t\tint cmp = do_compare_entry_piecewise(ce, info->prev,\n-\t\t\t\t\t\t     &info->name);\n+\t\t\t\t\t\t     info->name, info->namelen,\n+\t\t\t\t\t\t     info->mode);\n \t\tif (cmp)\n \t\t\treturn cmp;\n \t}\n@@ -884,15 +890,15 @@ static int do_compare_entry_piecewise(const struct cache_entry *ce, const struct\n \tce_len -= pathlen;\n \tce_name = ce->name + pathlen;\n \n-\tlen = tree_entry_len(n);\n-\treturn df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);\n+\treturn df_name_compare(ce_name, ce_len, S_IFREG, name, namelen, mode);\n }\n \n static int do_compare_entry(const struct cache_entry *ce,\n \t\t\t    const struct traverse_info *info,\n-\t\t\t    const struct name_entry *n)\n+\t\t\t    const char *name, size_t namelen,\n+\t\t\t    unsigned mode)\n {\n-\tint len, pathlen, ce_len;\n+\tint pathlen, ce_len;\n \tconst char *ce_name;\n \tint cmp;\n \n@@ -902,7 +908,7 @@ static int do_compare_entry(const struct cache_entry *ce,\n \t * it is quicker to use the precomputed version.\n \t */\n \tif (!info->traverse_path)\n-\t\treturn do_compare_entry_piecewise(ce, info, n);\n+\t\treturn do_compare_entry_piecewise(ce, info, name, namelen, mode);\n \n \tcmp = strncmp(ce->name, info->traverse_path, info->pathlen);\n \tif (cmp)\n@@ -917,13 +923,12 @@ static int do_compare_entry(const struct cache_entry *ce,\n \tce_len -= pathlen;\n \tce_name = ce->name + pathlen;\n \n-\tlen = tree_entry_len(n);\n-\treturn df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);\n+\treturn df_name_compare(ce_name, ce_len, S_IFREG, name, namelen, mode);\n }\n \n static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)\n {\n-\tint cmp = do_compare_entry(ce, info, n);\n+\tint cmp = do_compare_entry(ce, info, n->path, n->pathlen, n->mode);\n \tif (cmp)\n \t\treturn cmp;\n \n@@ -939,7 +944,8 @@ static int ce_in_traverse_path(const struct cache_entry *ce,\n {\n \tif (!info->prev)\n \t\treturn 1;\n-\tif (do_compare_entry(ce, info->prev, &info->name))\n+\tif (do_compare_entry(ce, info->prev,\n+\t\t\t     info->name, info->namelen, info->mode))\n \t\treturn 0;\n \t/*\n \t * If ce (blob) is the same name as the path (which is a tree\n@@ -964,7 +970,7 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,\n \tce->ce_flags = create_ce_flags(stage);\n \tce->ce_namelen = len;\n \toidcpy(&ce->oid, &n->oid);\n-\tmake_traverse_path(ce->name, info, n);\n+\tmake_traverse_path(ce->name, info, n->path, n->pathlen);\n \n \treturn ce;\n }\n@@ -1057,13 +1063,12 @@ static int unpack_failed(struct unpack_trees_options *o, const char *message)\n  * the directory.\n  */\n static int find_cache_pos(struct traverse_info *info,\n-\t\t\t  const struct name_entry *p)\n+\t\t\t  const char *p, size_t p_len)\n {\n \tint pos;\n \tstruct unpack_trees_options *o = info->data;\n \tstruct index_state *index = o->src_index;\n \tint pfxlen = info->pathlen;\n-\tint p_len = tree_entry_len(p);\n \n \tfor (pos = o->cache_bottom; pos < index->cache_nr; pos++) {\n \t\tconst struct cache_entry *ce = index->cache[pos];\n@@ -1099,7 +1104,7 @@ static int find_cache_pos(struct traverse_info *info,\n \t\t\tce_len = ce_slash - ce_name;\n \t\telse\n \t\t\tce_len = ce_namelen(ce) - pfxlen;\n-\t\tcmp = name_compare(p->path, p_len, ce_name, ce_len);\n+\t\tcmp = name_compare(p, p_len, ce_name, ce_len);\n \t\t/*\n \t\t * Exact match; if we have a directory we need to\n \t\t * delay returning it.\n@@ -1114,7 +1119,7 @@ static int find_cache_pos(struct traverse_info *info,\n \t\t * E.g.  ce_name == \"t-i\", and p->path == \"t\"; we may\n \t\t * have \"t/a\" in the index.\n \t\t */\n-\t\tif (p_len < ce_len && !memcmp(ce_name, p->path, p_len) &&\n+\t\tif (p_len < ce_len && !memcmp(ce_name, p, p_len) &&\n \t\t    ce_name[p_len] < '/')\n \t\t\tcontinue; /* keep looking */\n \t\tbreak;\n@@ -1125,7 +1130,7 @@ static int find_cache_pos(struct traverse_info *info,\n static struct cache_entry *find_cache_entry(struct traverse_info *info,\n \t\t\t\t\t    const struct name_entry *p)\n {\n-\tint pos = find_cache_pos(info, p);\n+\tint pos = find_cache_pos(info, p->path, p->pathlen);\n \tstruct unpack_trees_options *o = info->data;\n \n \tif (0 <= pos)\n@@ -1138,10 +1143,10 @@ static void debug_path(struct traverse_info *info)\n {\n \tif (info->prev) {\n \t\tdebug_path(info->prev);\n-\t\tif (*info->prev->name.path)\n+\t\tif (*info->prev->name)\n \t\t\tputchar('/');\n \t}\n-\tprintf(\"%s\", info->name.path);\n+\tprintf(\"%s\", info->name);\n }\n \n static void debug_name_entry(int i, struct name_entry *n)\n-- \n2.23.0.rc0.426.gbdee707ba7\n\n"},{"id":"379643","messageId":"20190731043818.GC27170@sigill.intra.peff.net","threadId":"51561","inReplyTo":"20190731043659.GA27028@sigill.intra.peff.net","subject":"[PATCH 3/6] tree-walk: use size_t consistently","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-07-31T04:38:18Z","receivedAt":"2019-07-31T04:38:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We store and manipulate the cumulative traverse_info.pathlen as an\n\"int\", which can overflow when we are fed ridiculously long pathnames\n(e.g., ones at the edge of 2GB or 4GB, even if the individual tree entry\nnames are smaller than that). The results can be confusing, though\nafter some prodding I was not able to use this integer overflow to cause\nan under-allocated buffer.\n\nLet's consistently use size_t to generarate and store these, and make\nsure our addition doesn't overflow.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n tree-walk.c    | 4 ++--\n tree-walk.h    | 6 +++---\n unpack-trees.c | 6 +++---\n 3 files changed, 8 insertions(+), 8 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 130d9f32f2..cf5af6a46b 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -170,7 +170,7 @@ int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)\n \n void setup_traverse_info(struct traverse_info *info, const char *base)\n {\n-\tint pathlen = strlen(base);\n+\tsize_t pathlen = strlen(base);\n \tstatic struct traverse_info dummy;\n \n \tmemset(info, 0, sizeof(*info));\n@@ -186,7 +186,7 @@ void setup_traverse_info(struct traverse_info *info, const char *base)\n char *make_traverse_path(char *path, const struct traverse_info *info,\n \t\t\t const char *name, size_t namelen)\n {\n-\tint pathlen = info->pathlen;\n+\tsize_t pathlen = info->pathlen;\n \n \tpath[pathlen + namelen] = 0;\n \tfor (;;) {\ndiff --git a/tree-walk.h b/tree-walk.h\nindex 2c59caa38a..95de0506c8 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -62,7 +62,7 @@ struct traverse_info {\n \tsize_t namelen;\n \tunsigned mode;\n \n-\tint pathlen;\n+\tsize_t pathlen;\n \tstruct pathspec *pathspec;\n \n \tunsigned long df_conflicts;\n@@ -76,9 +76,9 @@ char *make_traverse_path(char *path, const struct traverse_info *info,\n \t\t\t const char *name, size_t namelen);\n void setup_traverse_info(struct traverse_info *info, const char *base);\n \n-static inline int traverse_path_len(const struct traverse_info *info, const struct name_entry *n)\n+static inline size_t traverse_path_len(const struct traverse_info *info, const struct name_entry *n)\n {\n-\treturn info->pathlen + tree_entry_len(n);\n+\treturn st_add(info->pathlen, tree_entry_len(n));\n }\n \n /* in general, positive means \"kind of interesting\" */\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 63cbddead8..a014ae9907 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -686,7 +686,7 @@ static int index_pos_by_traverse_info(struct name_entry *names,\n \t\t\t\t      struct traverse_info *info)\n {\n \tstruct unpack_trees_options *o = info->data;\n-\tint len = traverse_path_len(info, names);\n+\tsize_t len = traverse_path_len(info, names);\n \tchar *name = xmalloc(len + 1 /* slash */ + 1 /* NUL */);\n \tint pos;\n \n@@ -814,7 +814,7 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n \tnewinfo.name = p->path;\n \tnewinfo.namelen = p->pathlen;\n \tnewinfo.mode = p->mode;\n-\tnewinfo.pathlen += tree_entry_len(p) + 1;\n+\tnewinfo.pathlen = st_add3(newinfo.pathlen, tree_entry_len(p), 1);\n \tnewinfo.df_conflicts |= df_conflicts;\n \n \t/*\n@@ -960,7 +960,7 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,\n \tstruct index_state *istate,\n \tint is_transient)\n {\n-\tint len = traverse_path_len(info, n);\n+\tsize_t len = traverse_path_len(info, n);\n \tstruct cache_entry *ce =\n \t\tis_transient ?\n \t\tmake_empty_transient_cache_entry(len) :\n-- \n2.23.0.rc0.426.gbdee707ba7\n\n"},{"id":"379644","messageId":"20190731043820.GD27170@sigill.intra.peff.net","threadId":"51561","inReplyTo":"20190731043659.GA27028@sigill.intra.peff.net","subject":"[PATCH 4/6] tree-walk: accept a raw length for traverse_path_len()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-07-31T04:38:20Z","receivedAt":"2019-07-31T04:38:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We take a \"struct name_entry\", but only care about the length of the\npath name. Let's just take that length directly, making it easier to use\nthe function from callers that sometimes do not have a name_entry at\nall.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n builtin/merge-tree.c | 2 +-\n tree-walk.h          | 5 +++--\n unpack-trees.c       | 6 +++---\n 3 files changed, 7 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/merge-tree.c b/builtin/merge-tree.c\nindex d8ace972c7..225460fe13 100644\n--- a/builtin/merge-tree.c\n+++ b/builtin/merge-tree.c\n@@ -180,7 +180,7 @@ static struct merge_list *create_entry(unsigned stage, unsigned mode, const stru\n \n static char *traverse_path(const struct traverse_info *info, const struct name_entry *n)\n {\n-\tchar *path = xmallocz(traverse_path_len(info, n));\n+\tchar *path = xmallocz(traverse_path_len(info, tree_entry_len(n)));\n \treturn make_traverse_path(path, info, n->path, n->pathlen);\n }\n \ndiff --git a/tree-walk.h b/tree-walk.h\nindex 95de0506c8..98580a6f0b 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -76,9 +76,10 @@ char *make_traverse_path(char *path, const struct traverse_info *info,\n \t\t\t const char *name, size_t namelen);\n void setup_traverse_info(struct traverse_info *info, const char *base);\n \n-static inline size_t traverse_path_len(const struct traverse_info *info, const struct name_entry *n)\n+static inline size_t traverse_path_len(const struct traverse_info *info,\n+\t\t\t\t       size_t namelen)\n {\n-\treturn st_add(info->pathlen, tree_entry_len(n));\n+\treturn st_add(info->pathlen, namelen);\n }\n \n /* in general, positive means \"kind of interesting\" */\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex a014ae9907..88e4e55a73 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -686,7 +686,7 @@ static int index_pos_by_traverse_info(struct name_entry *names,\n \t\t\t\t      struct traverse_info *info)\n {\n \tstruct unpack_trees_options *o = info->data;\n-\tsize_t len = traverse_path_len(info, names);\n+\tsize_t len = traverse_path_len(info, tree_entry_len(names));\n \tchar *name = xmalloc(len + 1 /* slash */ + 1 /* NUL */);\n \tint pos;\n \n@@ -936,7 +936,7 @@ static int compare_entry(const struct cache_entry *ce, const struct traverse_inf\n \t * Even if the beginning compared identically, the ce should\n \t * compare as bigger than a directory leading up to it!\n \t */\n-\treturn ce_namelen(ce) > traverse_path_len(info, n);\n+\treturn ce_namelen(ce) > traverse_path_len(info, tree_entry_len(n));\n }\n \n static int ce_in_traverse_path(const struct cache_entry *ce,\n@@ -960,7 +960,7 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,\n \tstruct index_state *istate,\n \tint is_transient)\n {\n-\tsize_t len = traverse_path_len(info, n);\n+\tsize_t len = traverse_path_len(info, tree_entry_len(n));\n \tstruct cache_entry *ce =\n \t\tis_transient ?\n \t\tmake_empty_transient_cache_entry(len) :\n-- \n2.23.0.rc0.426.gbdee707ba7\n\n"},{"id":"379645","messageId":"20190731043822.GE27170@sigill.intra.peff.net","threadId":"51561","inReplyTo":"20190731043659.GA27028@sigill.intra.peff.net","subject":"[PATCH 5/6] tree-walk: add a strbuf wrapper for make_traverse_path()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-07-31T04:38:23Z","receivedAt":"2019-07-31T04:38:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"All but one of the callers of make_traverse_path() allocate a new heap\nbuffer to store the path. Let's give them an easy way to write to a\nstrbuf, which saves them from computing the length themselves (which is\nespecially tricky when they want to add to the path). It will also make\nit easier for us to change the make_traverse_path() interface in a\nfuture patch to improve its bounds-checking.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n Documentation/technical/api-tree-walking.txt |  4 ++++\n builtin/merge-tree.c                         |  5 +++--\n tree-walk.c                                  | 21 ++++++++++++++------\n tree-walk.h                                  |  3 +++\n unpack-trees.c                               | 16 +++++++--------\n 5 files changed, 32 insertions(+), 17 deletions(-)\n\ndiff --git a/Documentation/technical/api-tree-walking.txt b/Documentation/technical/api-tree-walking.txt\nindex 59d78e0362..7962e32854 100644\n--- a/Documentation/technical/api-tree-walking.txt\n+++ b/Documentation/technical/api-tree-walking.txt\n@@ -138,6 +138,10 @@ same in the next callback invocation.\n \tThis utilizes the memory structure of a tree entry to avoid the\n \toverhead of using a generic strlen().\n \n+`strbuf_make_traverse_path`::\n+\n+\tConvenience wrapper to `make_traverse_path` into a strbuf.\n+\n Authors\n -------\n \ndiff --git a/builtin/merge-tree.c b/builtin/merge-tree.c\nindex 225460fe13..e72714a5a8 100644\n--- a/builtin/merge-tree.c\n+++ b/builtin/merge-tree.c\n@@ -180,8 +180,9 @@ static struct merge_list *create_entry(unsigned stage, unsigned mode, const stru\n \n static char *traverse_path(const struct traverse_info *info, const struct name_entry *n)\n {\n-\tchar *path = xmallocz(traverse_path_len(info, tree_entry_len(n)));\n-\treturn make_traverse_path(path, info, n->path, n->pathlen);\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tstrbuf_make_traverse_path(&buf, info, n->path, n->pathlen);\n+\treturn strbuf_detach(&buf, NULL);\n }\n \n static void resolve(const struct traverse_info *info, struct name_entry *ours, struct name_entry *result)\ndiff --git a/tree-walk.c b/tree-walk.c\nindex cf5af6a46b..313780f40c 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -202,6 +202,17 @@ char *make_traverse_path(char *path, const struct traverse_info *info,\n \treturn path;\n }\n \n+void strbuf_make_traverse_path(struct strbuf *out,\n+\t\t\t       const struct traverse_info *info,\n+\t\t\t       const char *name, size_t namelen)\n+{\n+\tsize_t len = traverse_path_len(info, namelen);\n+\n+\tstrbuf_grow(out, len);\n+\tmake_traverse_path(out->buf + out->len, info, name, namelen);\n+\tstrbuf_setlen(out, out->len + len);\n+}\n+\n struct tree_desc_skip {\n \tstruct tree_desc_skip *prev;\n \tconst void *ptr;\n@@ -398,12 +409,10 @@ int traverse_trees(struct index_state *istate,\n \t\ttx[i].d = t[i];\n \n \tif (info->prev) {\n-\t\tstrbuf_grow(&base, info->pathlen);\n-\t\tmake_traverse_path(base.buf, info->prev, info->name,\n-\t\t\t\t   info->namelen);\n-\t\tbase.buf[info->pathlen-1] = '/';\n-\t\tstrbuf_setlen(&base, info->pathlen);\n-\t\ttraverse_path = xstrndup(base.buf, info->pathlen);\n+\t\tstrbuf_make_traverse_path(&base, info->prev,\n+\t\t\t\t\t  info->name, info->namelen);\n+\t\tstrbuf_addch(&base, '/');\n+\t\ttraverse_path = xstrndup(base.buf, base.len);\n \t} else {\n \t\ttraverse_path = xstrndup(info->name, info->pathlen);\n \t}\ndiff --git a/tree-walk.h b/tree-walk.h\nindex 98580a6f0b..43b56fd8ff 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -74,6 +74,9 @@ struct traverse_info {\n int get_tree_entry(struct repository *, const struct object_id *, const char *, struct object_id *, unsigned short *);\n char *make_traverse_path(char *path, const struct traverse_info *info,\n \t\t\t const char *name, size_t namelen);\n+void strbuf_make_traverse_path(struct strbuf *out,\n+\t\t\t       const struct traverse_info *info,\n+\t\t\t       const char *name, size_t namelen);\n void setup_traverse_info(struct traverse_info *info, const char *base);\n \n static inline size_t traverse_path_len(const struct traverse_info *info,\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 88e4e55a73..b154f09547 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -686,21 +686,19 @@ static int index_pos_by_traverse_info(struct name_entry *names,\n \t\t\t\t      struct traverse_info *info)\n {\n \tstruct unpack_trees_options *o = info->data;\n-\tsize_t len = traverse_path_len(info, tree_entry_len(names));\n-\tchar *name = xmalloc(len + 1 /* slash */ + 1 /* NUL */);\n+\tstruct strbuf name = STRBUF_INIT;\n \tint pos;\n \n-\tmake_traverse_path(name, info, names->path, names->pathlen);\n-\tname[len++] = '/';\n-\tname[len] = '\\0';\n-\tpos = index_name_pos(o->src_index, name, len);\n+\tstrbuf_make_traverse_path(&name, info, names->path, names->pathlen);\n+\tstrbuf_addch(&name, '/');\n+\tpos = index_name_pos(o->src_index, name.buf, name.len);\n \tif (pos >= 0)\n \t\tBUG(\"This is a directory and should not exist in index\");\n \tpos = -pos - 1;\n-\tif (!starts_with(o->src_index->cache[pos]->name, name) ||\n-\t    (pos > 0 && starts_with(o->src_index->cache[pos-1]->name, name)))\n+\tif (!starts_with(o->src_index->cache[pos]->name, name.buf) ||\n+\t    (pos > 0 && starts_with(o->src_index->cache[pos-1]->name, name.buf)))\n \t\tBUG(\"pos must point at the first entry in this directory\");\n-\tfree(name);\n+\tstrbuf_release(&name);\n \treturn pos;\n }\n \n-- \n2.23.0.rc0.426.gbdee707ba7\n\n"},{"id":"379646","messageId":"20190731043825.GF27170@sigill.intra.peff.net","threadId":"51561","inReplyTo":"20190731043659.GA27028@sigill.intra.peff.net","subject":"[PATCH 6/6] tree-walk: harden make_traverse_path() length computations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-07-31T04:38:25Z","receivedAt":"2019-07-31T04:38:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The make_traverse_path() function isn't very careful about checking its\noutput buffer boundaries. In fact, it doesn't even _know_ the size of\nthe buffer it's writing to, and just assumes that the caller used\ntraverse_path_len() correctly. And even then we assume that our\ntraverse_info.pathlen components are all correct, and just blindly write\ninto the buffer.\n\nLet's improve this situation a bit:\n\n  - have the caller pass in their allocated buffer length, which we'll\n    check against our own computations\n\n  - check for integer underflow as we do our backwards-insertion of\n    pathnames into the buffer\n\n  - check that we do not run out items in our list to traverse before\n    we've filled the expected number of bytes\n\nNone of these should be triggerable in practice (especially since our\nswitch to size_t everywhere in a previous commit), but it doesn't hurt\nto check our assumptions.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n tree-walk.c    | 28 ++++++++++++++++++++--------\n tree-walk.h    |  2 +-\n unpack-trees.c |  3 ++-\n 3 files changed, 23 insertions(+), 10 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 313780f40c..bea819d826 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -183,21 +183,32 @@ void setup_traverse_info(struct traverse_info *info, const char *base)\n \t\tinfo->prev = &dummy;\n }\n \n-char *make_traverse_path(char *path, const struct traverse_info *info,\n+char *make_traverse_path(char *path, size_t pathlen,\n+\t\t\t const struct traverse_info *info,\n \t\t\t const char *name, size_t namelen)\n {\n-\tsize_t pathlen = info->pathlen;\n+\t/* Always points to the end of the name we're about to add */\n+\tsize_t pos = st_add(info->pathlen, namelen);\n \n-\tpath[pathlen + namelen] = 0;\n+\tif (pos >= pathlen)\n+\t\tBUG(\"too small buffer passed to make_traverse_path\");\n+\n+\tpath[pos] = 0;\n \tfor (;;) {\n-\t\tmemcpy(path + pathlen, name, namelen);\n-\t\tif (!pathlen)\n+\t\tif (pos < namelen)\n+\t\t\tBUG(\"traverse_info pathlen does not match strings\");\n+\t\tpos -= namelen;\n+\t\tmemcpy(path + pos, name, namelen);\n+\n+\t\tif (!pos)\n \t\t\tbreak;\n-\t\tpath[--pathlen] = '/';\n+\t\tpath[--pos] = '/';\n+\n+\t\tif (!info)\n+\t\t\tBUG(\"traverse_info ran out of list items\");\n \t\tname = info->name;\n \t\tnamelen = info->namelen;\n \t\tinfo = info->prev;\n-\t\tpathlen -= namelen;\n \t}\n \treturn path;\n }\n@@ -209,7 +220,8 @@ void strbuf_make_traverse_path(struct strbuf *out,\n \tsize_t len = traverse_path_len(info, namelen);\n \n \tstrbuf_grow(out, len);\n-\tmake_traverse_path(out->buf + out->len, info, name, namelen);\n+\tmake_traverse_path(out->buf + out->len, out->alloc - out->len,\n+\t\t\t   info, name, namelen);\n \tstrbuf_setlen(out, out->len + len);\n }\n \ndiff --git a/tree-walk.h b/tree-walk.h\nindex 43b56fd8ff..abe2caf4e0 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -72,7 +72,7 @@ struct traverse_info {\n };\n \n int get_tree_entry(struct repository *, const struct object_id *, const char *, struct object_id *, unsigned short *);\n-char *make_traverse_path(char *path, const struct traverse_info *info,\n+char *make_traverse_path(char *path, size_t pathlen, const struct traverse_info *info,\n \t\t\t const char *name, size_t namelen);\n void strbuf_make_traverse_path(struct strbuf *out,\n \t\t\t       const struct traverse_info *info,\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex b154f09547..50f257bd5c 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -968,7 +968,8 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,\n \tce->ce_flags = create_ce_flags(stage);\n \tce->ce_namelen = len;\n \toidcpy(&ce->oid, &n->oid);\n-\tmake_traverse_path(ce->name, info, n->path, n->pathlen);\n+\t/* len+1 because the cache_entry allocates space for NUL */\n+\tmake_traverse_path(ce->name, len + 1, info, n->path, n->pathlen);\n \n \treturn ce;\n }\n-- \n2.23.0.rc0.426.gbdee707ba7\n"},{"id":"379766","messageId":"b99561c9-cd7c-aca0-c7dd-a9916b7bd429@gmail.com","threadId":"51561","inReplyTo":"20190731043818.GC27170@sigill.intra.peff.net","subject":"Re: [PATCH 3/6] tree-walk: use size_t consistently","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-08-01T18:17:28Z","receivedAt":"2019-08-01T18:17:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 7/31/2019 12:38 AM, Jeff King wrote:\n> We store and manipulate the cumulative traverse_info.pathlen as an\n> \"int\", which can overflow when we are fed ridiculously long pathnames\n> (e.g., ones at the edge of 2GB or 4GB, even if the individual tree entry\n> names are smaller than that). The results can be confusing, though\n> after some prodding I was not able to use this integer overflow to cause\n> an under-allocated buffer.\n> \n> Let's consistently use size_t to generarate and store these, and make\n> sure our addition doesn't overflow.\n\nnit: s/generarate/generate\n\n-Stolee\n"}]}