{"thread":{"id":"44151","subject":"[PATCH 1/2] add COPY_ARRAY","startedAt":"2016-09-25T07:16:05Z","lastAt":"2016-09-25T08:58:43Z","messageCount":5,"participants":["René Scharfe","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"302504","messageId":"6f402d35-b483-7552-2fb2-a5350112b8a6@web.de","threadId":"44151","inReplyTo":null,"subject":"[PATCH 1/2] add COPY_ARRAY","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-09-25T07:15:42Z","receivedAt":"2016-09-25T07:16:05Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add COPY_ARRAY, a safe and convenient helper for copying arrays,\ncomplementing ALLOC_ARRAY and REALLOC_ARRAY.  Users just specify source,\ndestination and the number of elements; the size of an element is\ninferred automatically.\n\nIt checks if the multiplication of size and element count overflows.\nThe inferred size is passed first to st_mult, which allows the division\nthere to be done at compilation time.\n\nAs a basic type safety check it makes sure the sizes of source and\ndestination elements are the same.  That's evaluated at compilation time\nas well.\n\nCOPY_ARRAY is safe to use with NULL as source pointer iff 0 elements are\nto be copied.  That convention is used in some cases for initializing\narrays.  Raw memcpy(3) does not support it -- compilers are allowed to\nassume that only valid pointers are passed to it and can optimize away\nNULL checks after such a call.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n git-compat-util.h | 8 ++++++++\n 1 file changed, 8 insertions(+)\n\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 37cce07..91775ce 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -801,6 +801,14 @@ extern FILE *fopen_for_writing(const char *path);\n #define ALLOC_ARRAY(x, alloc) (x) = xmalloc(st_mult(sizeof(*(x)), (alloc)))\n #define REALLOC_ARRAY(x, alloc) (x) = xrealloc((x), st_mult(sizeof(*(x)), (alloc)))\n \n+#define COPY_ARRAY(dst, src, n) copy_array((dst), (src), (n), sizeof(*(dst)) + \\\n+\tBUILD_ASSERT_OR_ZERO(sizeof(*(dst)) == sizeof(*(src))))\n+static inline void copy_array(void *dst, const void *src, size_t n, size_t size)\n+{\n+\tif (n)\n+\t\tmemcpy(dst, src, st_mult(size, n));\n+}\n+\n /*\n  * These functions help you allocate structs with flex arrays, and copy\n  * the data directly into the array. For example, if you had:\n-- \n2.10.0\n\n"},{"id":"302506","messageId":"869cff97-9e5f-ec17-6b64-bd1e4d9d1947@web.de","threadId":"44151","inReplyTo":"6f402d35-b483-7552-2fb2-a5350112b8a6@web.de","subject":"[PATCH 6/7] use COPY_ARRAY","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-09-25T07:24:03Z","receivedAt":"2016-09-25T07:24:35Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Add a semantic patch for converting certain calls of memcpy(3) to\nCOPY_ARRAY() and apply that transformation to the code base.  The result\nis\n shorter and safer code.  For now only consider calls where source and\ndestination have the same type, or in other words: easy cases.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n builtin/mv.c                   |  2 +-\n commit.c                       |  2 +-\n contrib/coccinelle/array.cocci | 26 ++++++++++++++++++++++++++\n pack-revindex.c                |  2 +-\n pathspec.c                     |  3 +--\n split-index.c                  |  6 ++----\n 6 files changed, 32 insertions(+), 9 deletions(-)\n create mode 100644 contrib/coccinelle/array.cocci\n\ndiff --git a/builtin/mv.c b/builtin/mv.c\nindex 446a316..2f43877 100644\n--- a/builtin/mv.c\n+++ b/builtin/mv.c\n@@ -26,7 +26,7 @@ static const char **internal_copy_pathspec(const char *prefix,\n \tint i;\n \tconst char **result;\n \tALLOC_ARRAY(result, count + 1);\n-\tmemcpy(result, pathspec, count * sizeof(const char *));\n+\tCOPY_ARRAY(result, pathspec, count);\n \tresult[count] = NULL;\n \tfor (i = 0; i < count; i++) {\n \t\tint length = strlen(result[i]);\ndiff --git a/commit.c b/commit.c\nindex ba6dee3..aada266 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -931,7 +931,7 @@ static int remove_redundant(struct commit **array, int cnt)\n \t}\n \n \t/* Now collect the result */\n-\tmemcpy(work, array, sizeof(*array) * cnt);\n+\tCOPY_ARRAY(work, array, cnt);\n \tfor (i = filled = 0; i < cnt; i++)\n \t\tif (!redundant[i])\n \t\t\tarray[filled++] = work[i];\ndiff --git a/contrib/coccinelle/array.cocci b/contrib/coccinelle/array.cocci\nnew file mode 100644\nindex 0000000..2d7f25d\n--- /dev/null\n+++ b/contrib/coccinelle/array.cocci\n@@ -0,0 +1,26 @@\n+@@\n+type T;\n+T *dst;\n+T *src;\n+expression n;\n+@@\n+- memcpy(dst, src, n * sizeof(*dst));\n++ COPY_ARRAY(dst, src, n);\n+\n+@@\n+type T;\n+T *dst;\n+T *src;\n+expression n;\n+@@\n+- memcpy(dst, src, n * sizeof(*src));\n++ COPY_ARRAY(dst, src, n);\n+\n+@@\n+type T;\n+T *dst;\n+T *src;\n+expression n;\n+@@\n+- memcpy(dst, src, n * sizeof(T));\n++ COPY_ARRAY(dst, src, n);\ndiff --git a/pack-revindex.c b/pack-revindex.c\nindex 96d51c3..6bc7c94 100644\n--- a/pack-revindex.c\n+++ b/pack-revindex.c\n@@ -107,7 +107,7 @@ static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max)\n \t * we have to move it back from the temporary storage.\n \t */\n \tif (from != entries)\n-\t\tmemcpy(entries, tmp, n * sizeof(*entries));\n+\t\tCOPY_ARRAY(entries, tmp, n);\n \tfree(tmp);\n \tfree(pos);\n \ndiff --git a/pathspec.c b/pathspec.c\nindex 24e0dd5..49a5360 100644\n--- a/pathspec.c\n+++ b/pathspec.c\n@@ -485,8 +485,7 @@ void copy_pathspec(struct pathspec *dst, const struct pathspec *src)\n {\n \t*dst = *src;\n \tALLOC_ARRAY(dst->items, dst->nr);\n-\tmemcpy(dst->items, src->items,\n-\t       sizeof(struct pathspec_item) * dst->nr);\n+\tCOPY_ARRAY(dst->items, src->items, dst->nr);\n }\n \n void clear_pathspec(struct pathspec *pathspec)\ndiff --git a/split-index.c b/split-index.c\nindex 3c75d4b..35da553 100644\n--- a/split-index.c\n+++ b/split-index.c\n@@ -83,8 +83,7 @@ void move_cache_to_base_index(struct index_state *istate)\n \tsi->base->timestamp = istate->timestamp;\n \tALLOC_GROW(si->base->cache, istate->cache_nr, si->base->cache_alloc);\n \tsi->base->cache_nr = istate->cache_nr;\n-\tmemcpy(si->base->cache, istate->cache,\n-\t       sizeof(*istate->cache) * istate->cache_nr);\n+\tCOPY_ARRAY(si->base->cache, istate->cache, istate->cache_nr);\n \tmark_base_index_entries(si->base);\n \tfor (i = 0; i < si->base->cache_nr; i++)\n \t\tsi->base->cache[i]->ce_flags &= ~CE_UPDATE_IN_BASE;\n@@ -141,8 +140,7 @@ void merge_base_index(struct index_state *istate)\n \tistate->cache\t    = NULL;\n \tistate->cache_alloc = 0;\n \tALLOC_GROW(istate->cache, istate->cache_nr, istate->cache_alloc);\n-\tmemcpy(istate->cache, si->base->cache,\n-\t       sizeof(*istate->cache) * istate->cache_nr);\n+\tCOPY_ARRAY(istate->cache, si->base->cache, istate->cache_nr);\n \n \tsi->nr_deletions = 0;\n \tsi->nr_replacements = 0;\n-- \n2.10.0\n\n"},{"id":"302507","messageId":"0428ceee-8761-1840-f769-26597c14f09b@web.de","threadId":"44151","inReplyTo":"869cff97-9e5f-ec17-6b64-bd1e4d9d1947@web.de","subject":"Re: [PATCH 6/7] use COPY_ARRAY","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-09-25T07:26:33Z","receivedAt":"2016-09-25T07:26:50Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Ha, can't count.  It should be [PATCH 2/2] of course.\n\nRené\n\n"},{"id":"302508","messageId":"20160925074144.44onzv5pub5dxuix@sigill.intra.peff.net","threadId":"44151","inReplyTo":"6f402d35-b483-7552-2fb2-a5350112b8a6@web.de","subject":"Re: [PATCH 1/2] add COPY_ARRAY","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-09-25T07:41:44Z","receivedAt":"2016-09-25T07:41:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Sep 25, 2016 at 09:15:42AM +0200, René Scharfe wrote:\n\n> Add COPY_ARRAY, a safe and convenient helper for copying arrays,\n> complementing ALLOC_ARRAY and REALLOC_ARRAY.  Users just specify source,\n> destination and the number of elements; the size of an element is\n> inferred automatically.\n\nSeems like a fairly readable construct to have.\n\n> It checks if the multiplication of size and element count overflows.\n> The inferred size is passed first to st_mult, which allows the division\n> there to be done at compilation time.\n\nI wonder if this actually stops any real overflows. My goal with\nALLOC_ARRAY, etc, was to catch these at the malloc stage (which is the\nreally dangerous part, because we don't want to under-allocate). So the\nfirst hunk of your patch is:\n\n        ALLOC_ARRAY(result, count + 1);\n-       memcpy(result, pathspec, count * sizeof(const char *));\n+       COPY_ARRAY(result, pathspec, count);\n\nwhich clearly cannot trigger the st_mult() check, because we would have\ndone so in the ALLOC_ARRAY call[1].\n\nOther calls are not so obvious, but in general I would expect the\nallocation step to be doing this check. If we missed one, then it's\npossible that this macro could detect it and prevent a problem. But it\nseems like the wrong time to check. The allocation is buggy, and we'd\nhave to just get lucky to be using COPY_ARRAY(). And I don't even mean\n\"lucky that we switched to COPY_ARRAY from memcpy for this callsite\".\nThere are lots of sites that allocate and then fill the array one by\none, without ever computing the full size again. So allocation is the\nonly sensible place to enforce integer overflow.\n\nSo I'm not sold on this providing any real integer overflow safety. But\nI do otherwise like it, as it drops the extra \"sizeof\" which has to\nrepeat either the variable name or the type).\n\n-Peff\n\n[1] Actually, this particular example probably should be using\n    st_add(count, 1), though it's likely not a problem in practice\n    (\"count\" is an int, so you cannot easily overflow it back to 0 by\n    incrementing 1, though of course overflowing it at all is undefined\n    behavior).\n"},{"id":"302510","messageId":"19dabb44-dba1-d1e0-7935-8e1aec0bf7b9@web.de","threadId":"44151","inReplyTo":"20160925074144.44onzv5pub5dxuix@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] add COPY_ARRAY","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-09-25T08:58:22Z","receivedAt":"2016-09-25T08:58:43Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 25.09.2016 um 09:41 schrieb Jeff King:\n> On Sun, Sep 25, 2016 at 09:15:42AM +0200, René Scharfe wrote:\n>> It checks if the multiplication of size and element count overflows.\n>> The inferred size is passed first to st_mult, which allows the division\n>> there to be done at compilation time.\n>\n> I wonder if this actually stops any real overflows. My goal with\n> ALLOC_ARRAY, etc, was to catch these at the malloc stage (which is the\n> really dangerous part, because we don't want to under-allocate). So the\n> first hunk of your patch is:\n>\n>         ALLOC_ARRAY(result, count + 1);\n> -       memcpy(result, pathspec, count * sizeof(const char *));\n> +       COPY_ARRAY(result, pathspec, count);\n>\n> which clearly cannot trigger the st_mult() check, because we would have\n> done so in the ALLOC_ARRAY call[1].\n>\n> Other calls are not so obvious, but in general I would expect the\n> allocation step to be doing this check. If we missed one, then it's\n> possible that this macro could detect it and prevent a problem. But it\n> seems like the wrong time to check. The allocation is buggy, and we'd\n> have to just get lucky to be using COPY_ARRAY(). And I don't even mean\n> \"lucky that we switched to COPY_ARRAY from memcpy for this callsite\".\n> There are lots of sites that allocate and then fill the array one by\n> one, without ever computing the full size again. So allocation is the\n> only sensible place to enforce integer overflow.\n>\n> So I'm not sold on this providing any real integer overflow safety. But\n> I do otherwise like it, as it drops the extra \"sizeof\" which has to\n> repeat either the variable name or the type).\n\nWell, yes, checking if the destination object is big enough requires \ncalculating the size of the source object and thus should include a \ncheck for multiplication overflow already.  Note the word \"should\". :) \nIf that's the case then a smart compiler could elide the duplicate \ncheck.  Keeping the check in COPY_ARRAY reduces the assumptions we have \nmake about its use as well as any previous checks and doesn't cost much.\n\nRené\n"}]}