Re: [PATCH] mv: prevent mismatched data when ignoring errors.

Junio C Hamano [off-list ref] writes:

Would it make sense to go one step further to introduce two macros
to make this kind of screw-up less likely?
...
After letting my eyes coast over hits from "git grep memmove", there
do seem to be some places that these would help readability, but not
very many.

I see quite a many hits that follow this pattern

	memmove(array + pos, array + pos + 1, sizeof(*array) * (nr - pos))

to make a single slot in a middle of array available, which would be
good candidates to use MOVE_DOWN().  Just to show a few:

builtin/mv.c:226:	memmove(source + i, source + i + 1,
builtin/mv.c-227-		(argc - i) * sizeof(char *));
builtin/mv.c:228:	memmove(destination + i,
builtin/mv.c-229-		destination + i + 1,
builtin/mv.c-230-		(argc - i) * sizeof(char *));
cache-tree.c:92:	memmove(it->down + pos + 1,
cache-tree.c-93-		it->down + pos,
cache-tree.c-94-		sizeof(down) * (it->subtree_nr - pos - 1));


Perhaps something like this patch to start off; I am not sure
MOVE_DOWN_BOUNDED is needed, though.

 cache.h | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/cache.h b/cache.h
index b66cb49..b2615ab 100644
--- a/cache.h
+++ b/cache.h

@@ -455,6 +455,39 @@ extern int daemonize(void);
 		} \
 	} while (0)
 
+/*
+ * With an array "array" that currently holds "nr" elements, move
+ * elements at "at" and later down by "count" elements to make room to
+ * add in new elements.  The caller is responsible for making sure
+ * that the array has enough room to hold "nr" + "count" slots.
+ */
+#define MOVE_DOWN(array, nr, at, count)			\
+	memmove((array) + (at) + (count),		\
+		(array) + (at),				\
+		sizeof((array)[0]) * ((nr) - (at)))
+
+/*
+ * With an array "array" that has enough memory to hold "alloc"
+ * elements allocated and currently holds "nr" elements, move elements
+ * at "at" and later down by "count" elements to make room to add in
+ * new elements.
+ */
+#define MOVE_DOWN_BOUNDED(array, nr, at, count, alloc)		     \
+	do {							     \
+		if ((alloc) <= (nr) + (count))			     \
+			BUG("MOVE_DOWN beyond the end of an array"); \
+		MOVE_DOWN((array), (nr), (at), (count));	     \
+	} while (0)
+
+/*
+ * With an array "array" that curently holds "nr" elements, move elements
+ * at "at" + "count" and later down by "count" elements, removing the
+ * elements between "at" and "at" + "count".
+ */
+#define MOVE_UP(array, nr, at, count)				\
+	memmove((array) + (at), (array) + (at) + (count),	\
+		sizeof((array)[0]) * ((nr) - ((at) + (count))))
+
 /* Initialize and use the cache information */
 extern int read_index(struct index_state *);
 extern int read_index_preload(struct index_state *, const struct pathspec *pathspec);

On 03/17/2014 07:33 AM, Junio C Hamano wrote:

I had recently been thinking along the same lines.  In many of the
potential callers that I noticed, ALLOC_GROW() was used immediately
before making space in the array for a new element.  So I suggest
something more like

+#define MOVE_DOWN(array, nr, at, count)	\
+	memmove((array) + (at) + (count),		\
+		(array) + (at),				\
+		sizeof((array)[0]) * ((nr) - (at)))
+#define ALLOC_INSERT_GAP(array, nr, at, count, alloc)		     \
+	do {							     \
+		ALLOC_GROW((array), (nr) + (count), (alloc));        \
+		MOVE_DOWN((array), (nr), (at), (count));	     \
+	} while (0)

Also, count==1 is so frequent that this special case might deserve its
own macro pair.

I'm not inspired by these macro names, though.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

On Mon, Mar 17, 2014 at 11:07 AM, Michael Haggerty [off-list ref] wrote:

On 03/17/2014 07:33 AM, Junio C Hamano wrote:

quoted

Junio C Hamano [off-list ref] writes:

quoted

Would it make sense to go one step further to introduce two macros
to make this kind of screw-up less likely?

potential callers that I noticed, ALLOC_GROW() was used immediately
before making space in the array for a new element.  So I suggest
something more like

+#define MOVE_DOWN(array, nr, at, count)        \
+       memmove((array) + (at) + (count),               \
+               (array) + (at),                         \
+               sizeof((array)[0]) * ((nr) - (at)))

Each time I read these, my brain (for whatever reason) interprets the
names UP and DOWN opposite of the intended meaning, which makes them
confusing. Perhaps INSERT_GAP and CLOSE_GAP would avoid such problems,
and be more consistent with Michael's proposed ALLOC_INSERT_GAP.

+#define ALLOC_INSERT_GAP(array, nr, at, count, alloc)               \
+       do {                                                         \
+               ALLOC_GROW((array), (nr) + (count), (alloc));        \
+               MOVE_DOWN((array), (nr), (at), (count));             \
+       } while (0)

Also, count==1 is so frequent that this special case might deserve its
own macro pair.

I'm not inspired by these macro names, though.

Michael

--
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

On Mon, Mar 17, 2014 at 03:06:02PM -0400, Eric Sunshine wrote:

On Mon, Mar 17, 2014 at 11:07 AM, Michael Haggerty [off-list ref] wrote:

quoted

On 03/17/2014 07:33 AM, Junio C Hamano wrote:

quoted

Junio C Hamano [off-list ref] writes:

quoted

Would it make sense to go one step further to introduce two macros
to make this kind of screw-up less likely?

potential callers that I noticed, ALLOC_GROW() was used immediately
before making space in the array for a new element.  So I suggest
something more like

+#define MOVE_DOWN(array, nr, at, count)        \
+       memmove((array) + (at) + (count),               \
+               (array) + (at),                         \
+               sizeof((array)[0]) * ((nr) - (at)))

Each time I read these, my brain (for whatever reason) interprets the
names UP and DOWN opposite of the intended meaning, which makes them
confusing. Perhaps INSERT_GAP and CLOSE_GAP would avoid such problems,
and be more consistent with Michael's proposed ALLOC_INSERT_GAP.

Yeah, the UP/DOWN are very confusing to me. Something like SHRINK/EXPAND
(with the latter handling the ALLOC_GROW for us) makes more sense to me.
Those terms do not explicitly specify that we are doing it in the middle
(whereas GAP does), but I think it is fairly obvious from the parameters
what each is used for.

Side note: I had _almost_ added something to my original email
suggesting more use of macros to embody common idioms. For example, in
the vast majority of malloc cases, you could using something like:

  #define ALLOC_OBJS(x,n) do { x = xmalloc(sizeof(*x) * (n)); } while(0)
  #define ALLOC_OBJ(x) ALLOC_OBJS(x,1)

That eliminates a whole possible class of errors. But it's also
un-idiomatic as hell, and the resulting confusion can cause its own
problems. So I refrained from suggesting it.

I think as long as a macro is expressing a more high-level intent,
though, paying that cost can be worth it. By itself, wrapping memmove
to use sizeof(*array) does not seem all that exciting. But wrapping a
few specific cases like shrink/expand probably does make the code more
readable.

-Peff