Merge branch 'jk/tree-walk-overflow'

Codepaths to walk tree objects have been audited for integer
overflows and hardened.

* jk/tree-walk-overflow:
tree-walk: harden make_traverse_path() length computations
tree-walk: add a strbuf wrapper for make_traverse_path()
tree-walk: accept a raw length for traverse_path_len()
tree-walk: use size_t consistently
tree-walk: drop oid from traverse_info
setup_traverse_info(): stop copying oid

diff --git a/Documentation/technical/api-tree-walking.txt b/Documentation/technical/api-tree-walking.txt
index bde18622a87404fc258c60ecb87c43bfeb047f0c..7962e3285499aa10309b5c88ffdcc434d679a709 100644 (file)
--- a/Documentation/technical/api-tree-walking.txt
+++ b/Documentation/technical/api-tree-walking.txt
@@ -62,9 +62,7 @@ Initializing
 `setup_traverse_info`::
 
        Initialize a `traverse_info` given the pathname of the tree to start
-       traversing from. The `base` argument is assumed to be the `path`
-       member of the `name_entry` being recursed into unless the tree is a
-       top-level tree in which case the empty string ("") is used.
+       traversing from.
 
 Walking
 -------
@@ -140,6 +138,10 @@ same in the next callback invocation.
        This utilizes the memory structure of a tree entry to avoid the
        overhead of using a generic strlen().
 
+`strbuf_make_traverse_path`::
+
+       Convenience wrapper to `make_traverse_path` into a strbuf.
+
 Authors
 -------
 

diff --git a/builtin/merge-tree.c b/builtin/merge-tree.c
index 97b54caeb90085e0fb4a88898ac87c7a5cb45eed..e72714a5a87d02540f07fbbc65a86f66ed122cd8 100644 (file)
--- a/builtin/merge-tree.c
+++ b/builtin/merge-tree.c
@@ -180,8 +180,9 @@ static struct merge_list *create_entry(unsigned stage, unsigned mode, const stru
 
 static char *traverse_path(const struct traverse_info *info, const struct name_entry *n)
 {
-       char *path = xmallocz(traverse_path_len(info, n) + the_hash_algo->rawsz);
-       return make_traverse_path(path, info, n);
+       struct strbuf buf = STRBUF_INIT;
+       strbuf_make_traverse_path(&buf, info, n->path, n->pathlen);
+       return strbuf_detach(&buf, NULL);
 }
 
 static void resolve(const struct traverse_info *info, struct name_entry *ours, struct name_entry *result)

diff --git a/cache-tree.c b/cache-tree.c
index 706ffcf1883a01d1ac6f3e966f9d10ebc2e1d8dd..c22161f987152ea18715b00815e987847786c5ff 100644 (file)
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -713,7 +713,7 @@ static struct cache_tree *find_cache_tree_from_traversal(struct cache_tree *root
        if (!info->prev)
                return root;
        our_parent = find_cache_tree_from_traversal(root, info->prev);
-       return cache_tree_find(our_parent, info->name.path);
+       return cache_tree_find(our_parent, info->name);
 }
 
 int cache_tree_matches_traversal(struct cache_tree *root,

diff --git a/tree-walk.c b/tree-walk.c
index c20b62f49e4709253d71e18eea0a2472809d8e9d..bea819d826fb1c855a7b92dbe2605885c12f5c16 100644 (file)
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -170,40 +170,61 @@ int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)
 
 void setup_traverse_info(struct traverse_info *info, const char *base)
 {
-       int pathlen = strlen(base);
+       size_t pathlen = strlen(base);
        static struct traverse_info dummy;
 
        memset(info, 0, sizeof(*info));
        if (pathlen && base[pathlen-1] == '/')
                pathlen--;
        info->pathlen = pathlen ? pathlen + 1 : 0;
-       info->name.path = base;
-       info->name.pathlen = pathlen;
-       if (pathlen) {
-               hashcpy(info->name.oid.hash, (const unsigned char *)base + pathlen + 1);
+       info->name = base;
+       info->namelen = pathlen;
+       if (pathlen)
                info->prev = &dummy;
-       }
 }
 
-char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)
+char *make_traverse_path(char *path, size_t pathlen,
+                        const struct traverse_info *info,
+                        const char *name, size_t namelen)
 {
-       int len = tree_entry_len(n);
-       int pathlen = info->pathlen;
+       /* Always points to the end of the name we're about to add */
+       size_t pos = st_add(info->pathlen, namelen);
+
+       if (pos >= pathlen)
+               BUG("too small buffer passed to make_traverse_path");
 
-       path[pathlen + len] = 0;
+       path[pos] = 0;
        for (;;) {
-               memcpy(path + pathlen, n->path, len);
-               if (!pathlen)
+               if (pos < namelen)
+                       BUG("traverse_info pathlen does not match strings");
+               pos -= namelen;
+               memcpy(path + pos, name, namelen);
+
+               if (!pos)
                        break;
-               path[--pathlen] = '/';
-               n = &info->name;
-               len = tree_entry_len(n);
+               path[--pos] = '/';
+
+               if (!info)
+                       BUG("traverse_info ran out of list items");
+               name = info->name;
+               namelen = info->namelen;
                info = info->prev;
-               pathlen -= len;
        }
        return path;
 }
 
+void strbuf_make_traverse_path(struct strbuf *out,
+                              const struct traverse_info *info,
+                              const char *name, size_t namelen)
+{
+       size_t len = traverse_path_len(info, namelen);
+
+       strbuf_grow(out, len);
+       make_traverse_path(out->buf + out->len, out->alloc - out->len,
+                          info, name, namelen);
+       strbuf_setlen(out, out->len + len);
+}
+
 struct tree_desc_skip {
        struct tree_desc_skip *prev;
        const void *ptr;
@@ -400,13 +421,12 @@ int traverse_trees(struct index_state *istate,
                tx[i].d = t[i];
 
        if (info->prev) {
-               strbuf_grow(&base, info->pathlen);
-               make_traverse_path(base.buf, info->prev, &info->name);
-               base.buf[info->pathlen-1] = '/';
-               strbuf_setlen(&base, info->pathlen);
-               traverse_path = xstrndup(base.buf, info->pathlen);
+               strbuf_make_traverse_path(&base, info->prev,
+                                         info->name, info->namelen);
+               strbuf_addch(&base, '/');
+               traverse_path = xstrndup(base.buf, base.len);
        } else {
-               traverse_path = xstrndup(info->name.path, info->pathlen);
+               traverse_path = xstrndup(info->name, info->pathlen);
        }
        info->traverse_path = traverse_path;
        for (;;) {

diff --git a/tree-walk.h b/tree-walk.h
index 2a5db29e8f196f535c75fbf84dcae8f45ca5c4a3..abe2caf4e0faae271967787b02137505a22ac5ff 100644 (file)
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -58,8 +58,11 @@ enum get_oid_result get_tree_entry_follow_symlinks(struct repository *r, struct
 struct traverse_info {
        const char *traverse_path;
        struct traverse_info *prev;
-       struct name_entry name;
-       int pathlen;
+       const char *name;
+       size_t namelen;
+       unsigned mode;
+
+       size_t pathlen;
        struct pathspec *pathspec;
 
        unsigned long df_conflicts;
@@ -69,12 +72,17 @@ struct traverse_info {
 };
 
 int get_tree_entry(struct repository *, const struct object_id *, const char *, struct object_id *, unsigned short *);
-char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n);
+char *make_traverse_path(char *path, size_t pathlen, const struct traverse_info *info,
+                        const char *name, size_t namelen);
+void strbuf_make_traverse_path(struct strbuf *out,
+                              const struct traverse_info *info,
+                              const char *name, size_t namelen);
 void setup_traverse_info(struct traverse_info *info, const char *base);
 
-static inline int traverse_path_len(const struct traverse_info *info, const struct name_entry *n)
+static inline size_t traverse_path_len(const struct traverse_info *info,
+                                      size_t namelen)
 {
-       return info->pathlen + tree_entry_len(n);
+       return st_add(info->pathlen, namelen);
 }
 
 /* in general, positive means "kind of interesting" */

diff --git a/unpack-trees.c b/unpack-trees.c
index 62276d4fef5f67e7147377f16e24e30abca0906a..50f257bd5c768ae87f8e526c587fa11afad98ad6 100644 (file)
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -632,7 +632,7 @@ static int unpack_index_entry(struct cache_entry *ce,
        return ret;
 }
 
-static int find_cache_pos(struct traverse_info *, const struct name_entry *);
+static int find_cache_pos(struct traverse_info *, const char *p, size_t len);
 
 static void restore_cache_bottom(struct traverse_info *info, int bottom)
 {
@@ -651,7 +651,7 @@ static int switch_cache_bottom(struct traverse_info *info)
        if (o->diff_index_cached)
                return 0;
        ret = o->cache_bottom;
-       pos = find_cache_pos(info->prev, &info->name);
+       pos = find_cache_pos(info->prev, info->name, info->namelen);
 
        if (pos < -1)
                o->cache_bottom = -2 - pos;
@@ -686,21 +686,19 @@ static int index_pos_by_traverse_info(struct name_entry *names,
                                      struct traverse_info *info)
 {
        struct unpack_trees_options *o = info->data;
-       int len = traverse_path_len(info, names);
-       char *name = xmalloc(len + 1 /* slash */ + 1 /* NUL */);
+       struct strbuf name = STRBUF_INIT;
        int pos;
 
-       make_traverse_path(name, info, names);
-       name[len++] = '/';
-       name[len] = '\0';
-       pos = index_name_pos(o->src_index, name, len);
+       strbuf_make_traverse_path(&name, info, names->path, names->pathlen);
+       strbuf_addch(&name, '/');
+       pos = index_name_pos(o->src_index, name.buf, name.len);
        if (pos >= 0)
                BUG("This is a directory and should not exist in index");
        pos = -pos - 1;
-       if (!starts_with(o->src_index->cache[pos]->name, name) ||
-           (pos > 0 && starts_with(o->src_index->cache[pos-1]->name, name)))
+       if (!starts_with(o->src_index->cache[pos]->name, name.buf) ||
+           (pos > 0 && starts_with(o->src_index->cache[pos-1]->name, name.buf)))
                BUG("pos must point at the first entry in this directory");
-       free(name);
+       strbuf_release(&name);
        return pos;
 }
 
@@ -811,8 +809,10 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,
        newinfo = *info;
        newinfo.prev = info;
        newinfo.pathspec = info->pathspec;
-       newinfo.name = *p;
-       newinfo.pathlen += tree_entry_len(p) + 1;
+       newinfo.name = p->path;
+       newinfo.namelen = p->pathlen;
+       newinfo.mode = p->mode;
+       newinfo.pathlen = st_add3(newinfo.pathlen, tree_entry_len(p), 1);
        newinfo.df_conflicts |= df_conflicts;
 
        /*
@@ -863,14 +863,18 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,
  * itself - the caller needs to do the final check for the cache
  * entry having more data at the end!
  */
-static int do_compare_entry_piecewise(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)
+static int do_compare_entry_piecewise(const struct cache_entry *ce,
+                                     const struct traverse_info *info,
+                                     const char *name, size_t namelen,
+                                     unsigned mode)
 {
-       int len, pathlen, ce_len;
+       int pathlen, ce_len;
        const char *ce_name;
 
        if (info->prev) {
                int cmp = do_compare_entry_piecewise(ce, info->prev,
-                                                    &info->name);
+                                                    info->name, info->namelen,
+                                                    info->mode);
                if (cmp)
                        return cmp;
        }
@@ -884,15 +888,15 @@ static int do_compare_entry_piecewise(const struct cache_entry *ce, const struct
        ce_len -= pathlen;
        ce_name = ce->name + pathlen;
 
-       len = tree_entry_len(n);
-       return df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);
+       return df_name_compare(ce_name, ce_len, S_IFREG, name, namelen, mode);
 }
 
 static int do_compare_entry(const struct cache_entry *ce,
                            const struct traverse_info *info,
-                           const struct name_entry *n)
+                           const char *name, size_t namelen,
+                           unsigned mode)
 {
-       int len, pathlen, ce_len;
+       int pathlen, ce_len;
        const char *ce_name;
        int cmp;
 
@@ -902,7 +906,7 @@ static int do_compare_entry(const struct cache_entry *ce,
         * it is quicker to use the precomputed version.
         */
        if (!info->traverse_path)
-               return do_compare_entry_piecewise(ce, info, n);
+               return do_compare_entry_piecewise(ce, info, name, namelen, mode);
 
        cmp = strncmp(ce->name, info->traverse_path, info->pathlen);
        if (cmp)
@@ -917,13 +921,12 @@ static int do_compare_entry(const struct cache_entry *ce,
        ce_len -= pathlen;
        ce_name = ce->name + pathlen;
 
-       len = tree_entry_len(n);
-       return df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);
+       return df_name_compare(ce_name, ce_len, S_IFREG, name, namelen, mode);
 }
 
 static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)
 {
-       int cmp = do_compare_entry(ce, info, n);
+       int cmp = do_compare_entry(ce, info, n->path, n->pathlen, n->mode);
        if (cmp)
                return cmp;
 
@@ -931,7 +934,7 @@ static int compare_entry(const struct cache_entry *ce, const struct traverse_inf
         * Even if the beginning compared identically, the ce should
         * compare as bigger than a directory leading up to it!
         */
-       return ce_namelen(ce) > traverse_path_len(info, n);
+       return ce_namelen(ce) > traverse_path_len(info, tree_entry_len(n));
 }
 
 static int ce_in_traverse_path(const struct cache_entry *ce,
@@ -939,7 +942,8 @@ static int ce_in_traverse_path(const struct cache_entry *ce,
 {
        if (!info->prev)
                return 1;
-       if (do_compare_entry(ce, info->prev, &info->name))
+       if (do_compare_entry(ce, info->prev,
+                            info->name, info->namelen, info->mode))
                return 0;
        /*
         * If ce (blob) is the same name as the path (which is a tree
@@ -954,7 +958,7 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,
        struct index_state *istate,
        int is_transient)
 {
-       int len = traverse_path_len(info, n);
+       size_t len = traverse_path_len(info, tree_entry_len(n));
        struct cache_entry *ce =
                is_transient ?
                make_empty_transient_cache_entry(len) :
@@ -964,7 +968,8 @@ static struct cache_entry *create_ce_entry(const struct traverse_info *info,
        ce->ce_flags = create_ce_flags(stage);
        ce->ce_namelen = len;
        oidcpy(&ce->oid, &n->oid);
-       make_traverse_path(ce->name, info, n);
+       /* len+1 because the cache_entry allocates space for NUL */
+       make_traverse_path(ce->name, len + 1, info, n->path, n->pathlen);
 
        return ce;
 }
@@ -1057,13 +1062,12 @@ static int unpack_failed(struct unpack_trees_options *o, const char *message)
  * the directory.
  */
 static int find_cache_pos(struct traverse_info *info,
-                         const struct name_entry *p)
+                         const char *p, size_t p_len)
 {
        int pos;
        struct unpack_trees_options *o = info->data;
        struct index_state *index = o->src_index;
        int pfxlen = info->pathlen;
-       int p_len = tree_entry_len(p);
 
        for (pos = o->cache_bottom; pos < index->cache_nr; pos++) {
                const struct cache_entry *ce = index->cache[pos];
@@ -1099,7 +1103,7 @@ static int find_cache_pos(struct traverse_info *info,
                        ce_len = ce_slash - ce_name;
                else
                        ce_len = ce_namelen(ce) - pfxlen;
-               cmp = name_compare(p->path, p_len, ce_name, ce_len);
+               cmp = name_compare(p, p_len, ce_name, ce_len);
                /*
                 * Exact match; if we have a directory we need to
                 * delay returning it.
@@ -1114,7 +1118,7 @@ static int find_cache_pos(struct traverse_info *info,
                 * E.g.  ce_name == "t-i", and p->path == "t"; we may
                 * have "t/a" in the index.
                 */
-               if (p_len < ce_len && !memcmp(ce_name, p->path, p_len) &&
+               if (p_len < ce_len && !memcmp(ce_name, p, p_len) &&
                    ce_name[p_len] < '/')
                        continue; /* keep looking */
                break;
@@ -1125,7 +1129,7 @@ static int find_cache_pos(struct traverse_info *info,
 static struct cache_entry *find_cache_entry(struct traverse_info *info,
                                            const struct name_entry *p)
 {
-       int pos = find_cache_pos(info, p);
+       int pos = find_cache_pos(info, p->path, p->pathlen);
        struct unpack_trees_options *o = info->data;
 
        if (0 <= pos)
@@ -1138,10 +1142,10 @@ static void debug_path(struct traverse_info *info)
 {
        if (info->prev) {
                debug_path(info->prev);
-               if (*info->prev->name.path)
+               if (*info->prev->name)
                        putchar('/');
        }
-       printf("%s", info->name.path);
+       printf("%s", info->name);
 }
 
 static void debug_name_entry(int i, struct name_entry *n)