{"thread":{"id":"46395","subject":"[PATCH 1/2] add MOVE_ARRAY","startedAt":"2017-07-15T19:36:50Z","lastAt":"2017-07-16T10:31:38Z","messageCount":6,"participants":["René Scharfe","Ramsay Jones","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"324588","messageId":"ec78a849-36e4-4b1d-1ad6-46dcc39a1396@web.de","threadId":"46395","inReplyTo":null,"subject":"[PATCH 1/2] add MOVE_ARRAY","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-07-15T19:36:20Z","receivedAt":"2017-07-15T19:36:50Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Similar to COPY_ARRAY (introduced in 60566cbb58), add a safe and\nconvenient helper for moving potentially overlapping ranges of array\nentries. It infers the element size, multiplies automatically and\nsafely to get the size in bytes, does a basic type safety check by\ncomparing element sizes and unlike memmove(3) it supports NULL\npointers iff 0 elements are to be moved.\n\nAlso add a semantic patch to demonstrate the helper's intended usage.\n\nSigned-off-by: Rene Scharfe \n---\n contrib/coccinelle/array.cocci | 17 +++++++++++++++++\n git-compat-util.h | 8 ++++++++\n 2 files changed, 25 insertions(+)\n\ndiff --git a/contrib/coccinelle/array.cocci b/contrib/coccinelle/array.cocci\nindex 4ba98b7eaf..c61d1ca8dc 100644\n--- a/contrib/coccinelle/array.cocci\n+++ b/contrib/coccinelle/array.cocci\n@@ -27,6 +27,23 @@ expression n;\n \n @@\n type T;\n+T *dst;\n+T *src;\n+expression n;\n+@@\n+(\n+- memmove(dst, src, (n) * sizeof(*dst));\n++ MOVE_ARRAY(dst, src, n);\n+|\n+- memmove(dst, src, (n) * sizeof(*src));\n++ MOVE_ARRAY(dst, src, n);\n+|\n+- memmove(dst, src, (n) * sizeof(T));\n++ MOVE_ARRAY(dst, src, n);\n+)\n+\n+@@\n+type T;\n T *ptr;\n expression n;\n @@\ndiff --git a/git-compat-util.h b/git-compat-util.h\nindex 047172d173..159f82154a 100644\n--- a/git-compat-util.h\n+++ b/git-compat-util.h\n@@ -825,6 +825,14 @@ static inline void copy_array(void *dst, const void *src, size_t n, size_t size)\n \t\tmemcpy(dst, src, st_mult(size, n));\n }\n \n+#define MOVE_ARRAY(dst, src, n) move_array((dst), (src), (n), sizeof(*(dst)) + \\\n+\tBUILD_ASSERT_OR_ZERO(sizeof(*(dst)) == sizeof(*(src))))\n+static inline void move_array(void *dst, const void *src, size_t n, size_t size)\n+{\n+\tif (n)\n+\t\tmemmove(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.13.3\n"},{"id":"324589","messageId":"5f4f0479-8e77-bec4-e982-2c7f37e70e7c@web.de","threadId":"46395","inReplyTo":"ec78a849-36e4-4b1d-1ad6-46dcc39a1396@web.de","subject":"[PATCH 2/2] use MOVE_ARRAY","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-07-15T20:00:45Z","receivedAt":"2017-07-15T20:03:03Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Simplify the code for moving members inside of an array and make it more\nrobust by using the helper macro MOVE_ARRAY. It calculates the size\nbased on the specified number of elements for us and supports NULL\npointers when that number is zero. Raw memmove(3) calls with NULL can\ncause the compiler to (over-eagerly) optimize out later NULL checks.\n\nThis patch was generated with contrib/coccinelle/array.cocci and spatch\n(Coccinelle).\n\nSigned-off-by: Rene Scharfe \n---\nDownside: The one in builtin/ls-files.c papers over a report by UBSan\nfor the case of istate->cache being NULL. Technically we still try to\nadd pos to NULL if pruning an empty index, but we won't see it anymore.\nWill send a separate patch.\n\n builtin/ls-files.c | 3 +--\n builtin/merge.c | 2 +-\n builtin/pack-objects.c | 5 ++---\n cache-tree.c | 5 ++---\n commit.c | 5 ++---\n notes-merge.c | 3 +--\n read-cache.c | 5 ++---\n reflog-walk.c | 7 +++----\n string-list.c | 8 +++-----\n 9 files changed, 17 insertions(+), 26 deletions(-)\n\ndiff --git a/builtin/ls-files.c b/builtin/ls-files.c\nindex b8514a0029..dc4a6aa3d9 100644\n--- a/builtin/ls-files.c\n+++ b/builtin/ls-files.c\n@@ -378,8 +378,7 @@ static void prune_index(struct index_state *istate,\n \t\t}\n \t\tlast = next;\n \t}\n-\tmemmove(istate->cache, istate->cache + pos,\n-\t\t(last - pos) * sizeof(struct cache_entry *));\n+\tMOVE_ARRAY(istate->cache, istate->cache + pos, last - pos);\n \tistate->cache_nr = last - pos;\n }\n \ndiff --git a/builtin/merge.c b/builtin/merge.c\nindex 900bafdb45..d5797b8fe7 100644\n--- a/builtin/merge.c\n+++ b/builtin/merge.c\n@@ -537,7 +537,7 @@ static void parse_branch_merge_options(char *bmo)\n \t\tdie(_(\"Bad branch.%s.mergeoptions string: %s\"), branch,\n \t\t split_cmdline_strerror(argc));\n \tREALLOC_ARRAY(argv, argc + 2);\n-\tmemmove(argv + 1, argv, sizeof(*argv) * (argc + 1));\n+\tMOVE_ARRAY(argv + 1, argv, argc + 1);\n \targc++;\n \targv[0] = \"branch.*.mergeoptions\";\n \tparse_options(argc, argv, NULL, builtin_merge_options,\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex f4a8441fe9..e730b415bf 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1298,9 +1298,8 @@ static int check_pbase_path(unsigned hash)\n \t\t done_pbase_paths_alloc);\n \tdone_pbase_paths_num++;\n \tif (pos < done_pbase_paths_num)\n-\t\tmemmove(done_pbase_paths + pos + 1,\n-\t\t\tdone_pbase_paths + pos,\n-\t\t\t(done_pbase_paths_num - pos - 1) * sizeof(unsigned));\n+\t\tMOVE_ARRAY(done_pbase_paths + pos + 1, done_pbase_paths + pos,\n+\t\t\t done_pbase_paths_num - pos - 1);\n \tdone_pbase_paths[pos] = hash;\n \treturn 0;\n }\ndiff --git a/cache-tree.c b/cache-tree.c\nindex ec23d8c03d..2440d1dc89 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -131,9 +131,8 @@ static int do_invalidate_path(struct cache_tree *it, const char *path)\n \t\t\t * move 4 and 5 up one place (2 entries)\n \t\t\t * 2 = 6 - 3 - 1 = subtree_nr - pos - 1\n \t\t\t */\n-\t\t\tmemmove(it->down+pos, it->down+pos+1,\n-\t\t\t\tsizeof(struct cache_tree_sub *) *\n-\t\t\t\t(it->subtree_nr - pos - 1));\n+\t\t\tMOVE_ARRAY(it->down + pos, it->down + pos + 1,\n+\t\t\t\t it->subtree_nr - pos - 1);\n \t\t\tit->subtree_nr--;\n \t\t}\n \t\treturn 1;\ndiff --git a/commit.c b/commit.c\nindex cbfd689939..d3150d6270 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -223,9 +223,8 @@ int unregister_shallow(const struct object_id *oid)\n \tif (pos < 0)\n \t\treturn -1;\n \tif (pos + 1 < commit_graft_nr)\n-\t\tmemmove(commit_graft + pos, commit_graft + pos + 1,\n-\t\t\t\tsizeof(struct commit_graft *)\n-\t\t\t\t* (commit_graft_nr - pos - 1));\n+\t\tMOVE_ARRAY(commit_graft + pos, commit_graft + pos + 1,\n+\t\t\t commit_graft_nr - pos - 1);\n \tcommit_graft_nr--;\n \treturn 0;\n }\ndiff --git a/notes-merge.c b/notes-merge.c\nindex 70e3fbeefb..c12b354f10 100644\n--- a/notes-merge.c\n+++ b/notes-merge.c\n@@ -99,8 +99,7 @@ static struct notes_merge_pair *find_notes_merge_pair_pos(\n \telse {\n \t\t*occupied = 0;\n \t\tif (insert_new && i < len) {\n-\t\t\tmemmove(list + i + 1, list + i,\n-\t\t\t\t(len - i) * sizeof(struct notes_merge_pair));\n+\t\t\tMOVE_ARRAY(list + i + 1, list + i, len - i);\n \t\t\tmemset(list + i, 0, sizeof(struct notes_merge_pair));\n \t\t}\n \t}\ndiff --git a/read-cache.c b/read-cache.c\nindex 2121b6e7bb..acfb028f48 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -515,9 +515,8 @@ int remove_index_entry_at(struct index_state *istate, int pos)\n \tistate->cache_nr--;\n \tif (pos >= istate->cache_nr)\n \t\treturn 0;\n-\tmemmove(istate->cache + pos,\n-\t\tistate->cache + pos + 1,\n-\t\t(istate->cache_nr - pos) * sizeof(struct cache_entry *));\n+\tMOVE_ARRAY(istate->cache + pos, istate->cache + pos + 1,\n+\t\t istate->cache_nr - pos);\n \treturn 1;\n }\n \ndiff --git a/reflog-walk.c b/reflog-walk.c\nindex 081f89b70d..81bca2ed23 100644\n--- a/reflog-walk.c\n+++ b/reflog-walk.c\n@@ -111,10 +111,9 @@ static struct commit_info *get_commit_info(struct commit *commit,\n \t\t\tstruct commit_info *result = &lifo->items[i];\n \t\t\tif (pop) {\n \t\t\t\tif (i + 1 < lifo->nr)\n-\t\t\t\t\tmemmove(lifo->items + i,\n-\t\t\t\t\t\tlifo->items + i + 1,\n-\t\t\t\t\t\t(lifo->nr - i) *\n-\t\t\t\t\t\tsizeof(struct commit_info));\n+\t\t\t\t\tMOVE_ARRAY(lifo->items + i,\n+\t\t\t\t\t\t lifo->items + i + 1,\n+\t\t\t\t\t\t lifo->nr - i);\n \t\t\t\tlifo->nr--;\n \t\t\t}\n \t\t\treturn result;\ndiff --git a/string-list.c b/string-list.c\nindex c650500c6e..806b4c8723 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -43,9 +43,8 @@ static int add_entry(int insert_at, struct string_list *list, const char *string\n \n \tALLOC_GROW(list->items, list->nr+1, list->alloc);\n \tif (index < list->nr)\n-\t\tmemmove(list->items + index + 1, list->items + index,\n-\t\t\t\t(list->nr - index)\n-\t\t\t\t* sizeof(struct string_list_item));\n+\t\tMOVE_ARRAY(list->items + index + 1, list->items + index,\n+\t\t\t list->nr - index);\n \tlist->items[index].string = list->strdup_strings ?\n \t\txstrdup(string) : (char *)string;\n \tlist->items[index].util = NULL;\n@@ -77,8 +76,7 @@ void string_list_remove(struct string_list *list, const char *string,\n \t\t\tfree(list->items[i].util);\n \n \t\tlist->nr--;\n-\t\tmemmove(list->items + i, list->items + i + 1,\n-\t\t\t(list->nr - i) * sizeof(struct string_list_item));\n+\t\tMOVE_ARRAY(list->items + i, list->items + i + 1, list->nr - i);\n \t}\n }\n \n-- \n2.13.3\n"},{"id":"324591","messageId":"2b2c8a6b-b493-84b1-1e47-5ea4585610da@web.de","threadId":"46395","inReplyTo":"ec78a849-36e4-4b1d-1ad6-46dcc39a1396@web.de","subject":"[PATCH 3/2] apply: use COPY_ARRAY and MOVE_ARRAY in update_image()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-07-15T20:20:54Z","receivedAt":"2017-07-15T20:21:22Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Simplify the code by using the helper macros COPY_ARRAY and MOVE_ARRAY,\nwhich also makes them more robust in the case we copy or move no lines,\nas they allow using NULL points in that case, while memcpy(3) and\nmemmove(3) don't.\n\nFound with Clang's UBSan.\n\nSigned-off-by: Rene Scharfe \n---\nI don't know why the rules in contrib/coccinelle/array.cocci didn't\nmatch. :-?\n\n apply.c | 11 ++++-------\n 1 file changed, 4 insertions(+), 7 deletions(-)\n\ndiff --git a/apply.c b/apply.c\nindex f2d599141d..40707ca50c 100644\n--- a/apply.c\n+++ b/apply.c\n@@ -2809,13 +2809,10 @@ static void update_image(struct apply_state *state,\n \t\timg->line_allocated = img->line;\n \t}\n \tif (preimage_limit != postimage->nr)\n-\t\tmemmove(img->line + applied_pos + postimage->nr,\n-\t\t\timg->line + applied_pos + preimage_limit,\n-\t\t\t(img->nr - (applied_pos + preimage_limit)) *\n-\t\t\tsizeof(*img->line));\n-\tmemcpy(img->line + applied_pos,\n-\t postimage->line,\n-\t postimage->nr * sizeof(*img->line));\n+\t\tMOVE_ARRAY(img->line + applied_pos + postimage->nr,\n+\t\t\t img->line + applied_pos + preimage_limit,\n+\t\t\t img->nr - (applied_pos + preimage_limit));\n+\tCOPY_ARRAY(img->line + applied_pos, postimage->line, postimage->nr);\n \tif (!state->allow_overlap)\n \t\tfor (i = 0; i < postimage->nr; i++)\n \t\t\timg->line[applied_pos + i].flag |= LINE_PATCHED;\n-- \n2.13.3\n"},{"id":"324594","messageId":"636e2b70-2687-a925-e52d-32aa966ae9a9@ramsayjones.plus.com","threadId":"46395","inReplyTo":"2b2c8a6b-b493-84b1-1e47-5ea4585610da@web.de","subject":"Re: [PATCH 3/2] apply: use COPY_ARRAY and MOVE_ARRAY in update_image()","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2017-07-16T00:31:06Z","receivedAt":"2017-07-16T00:31:13Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 15/07/17 21:20, René Scharfe wrote:\n> Simplify the code by using the helper macros COPY_ARRAY and MOVE_ARRAY,\n> which also makes them more robust in the case we copy or move no lines,\n> as they allow using NULL points in that case, while memcpy(3) and\n> memmove(3) don't.\n> \n> Found with Clang's UBSan.\n> \n> Signed-off-by: Rene Scharfe \n> ---\n> I don't know why the rules in contrib/coccinelle/array.cocci didn't\n> match. :-?\n> \n> apply.c | 11 ++++-------\n> 1 file changed, 4 insertions(+), 7 deletions(-)\n> \n> diff --git a/apply.c b/apply.c\n> index f2d599141d..40707ca50c 100644\n> --- a/apply.c\n> +++ b/apply.c\n> @@ -2809,13 +2809,10 @@ static void update_image(struct apply_state *state,\n> \t\timg->line_allocated = img->line;\n> \t}\n> \tif (preimage_limit != postimage->nr)\n> -\t\tmemmove(img->line + applied_pos + postimage->nr,\n> -\t\t\timg->line + applied_pos + preimage_limit,\n> -\t\t\t(img->nr - (applied_pos + preimage_limit)) *\n> -\t\t\tsizeof(*img->line));\n> -\tmemcpy(img->line + applied_pos,\n> -\t postimage->line,\n> -\t postimage->nr * sizeof(*img->line));\n> +\t\tMOVE_ARRAY(img->line + applied_pos + postimage->nr,\n> +\t\t\t img->line + applied_pos + preimage_limit,\n> +\t\t\t img->nr - (applied_pos + preimage_limit));\n> +\tCOPY_ARRAY(img->line + applied_pos, postimage->line, postimage->nr);\n\nMy patch looks like:\n\n- memcpy(img->line + applied_pos,\n- postimage->line,\n- postimage->nr * sizeof(*img->line));\n+ if (postimage->line && postimage->nr)\n+ memcpy(img->line + applied_pos,\n+ postimage->line,\n+ postimage->nr * sizeof(*img->line));\n\n... which I think I prefer (slightly).\n\n\nATB,\nRamsay Jones\n\n> \tif (!state->allow_overlap)\n> \t\tfor (i = 0; i < postimage->nr; i++)\n> \t\t\timg->line[applied_pos + i].flag |= LINE_PATCHED;\n> \n"},{"id":"324597","messageId":"cfc122ac-bd43-99f4-395d-2607fc34370c@web.de","threadId":"46395","inReplyTo":"636e2b70-2687-a925-e52d-32aa966ae9a9@ramsayjones.plus.com","subject":"Re: [PATCH 3/2] apply: use COPY_ARRAY and MOVE_ARRAY in update_image()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-07-16T04:04:14Z","receivedAt":"2017-07-16T04:05:03Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 16.07.2017 um 02:31 schrieb Ramsay Jones:\n> \n> \n> On 15/07/17 21:20, René Scharfe wrote:\n>> Simplify the code by using the helper macros COPY_ARRAY and MOVE_ARRAY,\n>> which also makes them more robust in the case we copy or move no lines,\n>> as they allow using NULL points in that case, while memcpy(3) and\n>> memmove(3) don't.\n>>\n>> Found with Clang's UBSan.\n>>\n>> Signed-off-by: Rene Scharfe \n>> ---\n>> I don't know why the rules in contrib/coccinelle/array.cocci didn't\n>> match. :-?\n>>\n>> apply.c | 11 ++++-------\n>> 1 file changed, 4 insertions(+), 7 deletions(-)\n>>\n>> diff --git a/apply.c b/apply.c\n>> index f2d599141d..40707ca50c 100644\n>> --- a/apply.c\n>> +++ b/apply.c\n>> @@ -2809,13 +2809,10 @@ static void update_image(struct apply_state *state,\n>> \t\timg->line_allocated = img->line;\n>> \t}\n>> \tif (preimage_limit != postimage->nr)\n>> -\t\tmemmove(img->line + applied_pos + postimage->nr,\n>> -\t\t\timg->line + applied_pos + preimage_limit,\n>> -\t\t\t(img->nr - (applied_pos + preimage_limit)) *\n>> -\t\t\tsizeof(*img->line));\n>> -\tmemcpy(img->line + applied_pos,\n>> -\t postimage->line,\n>> -\t postimage->nr * sizeof(*img->line));\n>> +\t\tMOVE_ARRAY(img->line + applied_pos + postimage->nr,\n>> +\t\t\t img->line + applied_pos + preimage_limit,\n>> +\t\t\t img->nr - (applied_pos + preimage_limit));\n>> +\tCOPY_ARRAY(img->line + applied_pos, postimage->line, postimage->nr);\n> \n> My patch looks like:\n> \n> - memcpy(img->line + applied_pos,\n> - postimage->line,\n> - postimage->nr * sizeof(*img->line));\n> + if (postimage->line && postimage->nr)\n> + memcpy(img->line + applied_pos,\n> + postimage->line,\n> + postimage->nr * sizeof(*img->line));\n> \n> ... which I think I prefer (slightly).\n\nCan postimage->line be NULL when postimage->nr is bigger than 0? What\nwould that mean? The only ways to arrive at that point that I an come\nup with are bugs (we accidentally set ->line to NULL, or we forgot to\nclean ->line). We'd better notice them early by getting a nice\nshrieking segfault. Adding an assert would work as well.\n\nRené\n"},{"id":"324607","messageId":"20170716103132.z36audbi7wxot7e6@sigill.intra.peff.net","threadId":"46395","inReplyTo":"ec78a849-36e4-4b1d-1ad6-46dcc39a1396@web.de","subject":"Re: [PATCH 1/2] add MOVE_ARRAY","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-07-16T10:31:32Z","receivedAt":"2017-07-16T10:31:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jul 15, 2017 at 09:36:20PM +0200, René Scharfe wrote:\n\n> Similar to COPY_ARRAY (introduced in 60566cbb58), add a safe and\n> convenient helper for moving potentially overlapping ranges of array\n> entries. It infers the element size, multiplies automatically and\n> safely to get the size in bytes, does a basic type safety check by\n> comparing element sizes and unlike memmove(3) it supports NULL\n> pointers iff 0 elements are to be moved.\n> \n> Also add a semantic patch to demonstrate the helper's intended usage.\n\nIf we have COPY_ARRAY(), I think it's foolish not to provide the\nmatching MOVE_ARRAY(). If it were just the \"if (n)\", I might say we\ncould just do this inline in the few calls that care. But I really like\nthe size safety.\n\nI agree with your comments elsewhere that we don't need to worry about\nthe case where one of the arrays is NULL but the size is not zero.\nThat's a flat-out bug.\n\n-Peff\n"}]}