xdiff: introduce memory allocation macros

This patch series introduces macros for allocating and growing arrays in xdiff. The macros are similar to ALLOC_ARRAY()/ALLOC_GROW() from the rest of the code base but return an error on failure to allow libgit2 to handle memory allocation failures gracefully rather than dying. The macros introduce overflow checks but these checks are currently redundant as we limit the maximum file size passed to xdiff and these checks alone are insufficient to safely remove the size limit. The aim of this series is to make the xdiff code more readable, there should be no change in behavior (as such I'm open to the argument that these are just churn and should be dropped).

From: Phillip Wood <[email protected]>

Add a helper to grow an array. This is analogous to ALLOC_GROW() in the rest of the codebase but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2.

Quoted 2 lines · Phillip Wood via GitGitGadget

From: Phillip Wood <[email protected]>

Quoted 3 lines

Add a helper to grow an array. This is analogous to ALLOC_GROW() in the rest of the codebase but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2.

Urm, does it? I just skimmed this, so maybe I missed something, but I don't see where you changed the definition of xdl_malloc(), xdl_realloc() etc.

And those are defined as:

	#define xdl_malloc(x) xmalloc(x)
	#define xdl_free(ptr) free(ptr)
	#define xdl_realloc(ptr,x) xrealloc(ptr,x)

And for e.g. xmalloc() we do:

         return do_xmalloc(size, 0);

Where that 0=gently, i.e. we'll die() instead of error(), the xrealloc() then has no "gently" option.

Is the (pretty glaring, if that's the case) unstated assumption here that this doesn't in fact return -1 on allocation failure, but you're expected to replace the underlying xmalloc() with an implementation that does?

If so I'm doubly confused by this, since you're providing alternatives to e.g.:

	#define ALLOC_ARRAY(x, alloc) (x) = xmalloc(st_mult(sizeof(*(x)), (alloc)))

So if that's the plan why would we need an XDL_ALLOC_ARRAY(), can't you just check that it returns non-NULL?

That's not possible with our current xmalloc(), but ditto for this series, and apparently the compiler isn't smart enough to yell at you about that...

I wondered if we were just missing the returns_nonnull attribute, but playing around with it I couldn't get GCC at least to warn about checking xmalloc()'s return value for non-NULL.

Quoted 5 lines · Ævar Arnfjörð Bjarmason

Quoted 2 lines · Phillip Wood via GitGitGadget

From: Phillip Wood <[email protected]>

Quoted 7 lines

Quoted 3 lines

Add a helper to grow an array. This is analogous to ALLOC_GROW() in the rest of the codebase but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2.

Urm, does it? I just skimmed this, so maybe I missed something, but I don't see where you changed the definition of xdl_malloc(), xdl_realloc() etc.

Quoted 6 lines · Phillip Wood

Quoted 5 lines · Ævar Arnfjörð Bjarmason

Quoted 2 lines · Phillip Wood via GitGitGadget

From: Phillip Wood <[email protected]>

Quoted 7 lines

Quoted 7 lines

Quoted 3 lines

Add a helper to grow an array. This is analogous to ALLOC_GROW() in the rest of the codebase but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2.

Urm, does it? I just skimmed this, so maybe I missed something, but I don't see where you changed the definition of xdl_malloc(), xdl_realloc() etc.

Oh I think I might have misunderstood your question. For git.git it will still die() but for other users that arrange for xdl_realloc() to return NULL on failure it will return -1. The same applies to the comments in the previous two patches about XDL_[CM]ALLOC_ARRAY() returning NULL on allocation failure.

xdiff/xmacros.h +0 -0

index 9fd3c5da91a..23db8e785d7 100644

xdiff/xmacros.h +5 -0

+/*
+ * Ensure array p can accommodate at least nr elements, growing the
+ * array and updating alloc (which is the number of allocated
+ * elements) as necessary. Frees p and returns -1 on failure, returns
+ * 0 on success

xdiff/xutils.c +12 -0

+	if (nr > n)
+		n = nr;
+	if (SIZE_MAX / size >= n)
+		tmp = xdl_realloc(p, n * size);
+	if (tmp) {
+		*alloc = n;
+	} else {
+		xdl_free(p);
+		*alloc = 0;
+	}
+	return tmp;
+}

Quoted 9 lines · Phillip Wood via GitGitGadget

xdiff/xmacros.h +9 -0

+/*
+ * Ensure array p can accommodate at least nr elements, growing the
+ * array and updating alloc (which is the number of allocated
+ * elements) as necessary. Frees p and returns -1 on failure, returns
+ * 0 on success
+ */
+#define XDL_ALLOC_GROW(p, nr, alloc)	\
+	(-!((nr) <= (alloc) ||		\
+	    ((p) = xdl_alloc_grow_helper((p), (nr), &(alloc), sizeof(*(p))))))

xdiff/xutils.c int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, · line 439

Quoted 6 lines

+ ...

xdiff/xutils.c +5 -0

+
+void* xdl_alloc_grow_helper(void *p, long nr, long *alloc, size_t size)
+{
+	void *tmp = NULL;
+	size_t n = ((LONG_MAX - 16) / 2 >= *alloc) ? 2 * *alloc + 16 : LONG_MAX;

Not counting in size_t but in long?

I assume that 16 mimics the ALLOW_GROW(), but ALLOW_GROW() grows by 1.5, not by 2, so these two are not exactly compatible.

The computation of 'n' tries to avoid arithmetic in "long" overflowing, but does it ensure that we actually grow if we truncate at LONG_MAX? After *alloc grew to LONG_MAX by calling this helper once, if we need to grow again and call this helper, 'n' will again get LONG_MAX and we end up not growing at all, no?

Quoted 12 lines

xdiff/xutils.c +12 -0

+	if (nr > n)
+		n = nr;
+	if (SIZE_MAX / size >= n)
+		tmp = xdl_realloc(p, n * size);
+	if (tmp) {
+		*alloc = n;
+	} else {
+		xdl_free(p);
+		*alloc = 0;
+	}
+	return tmp;
+}

Quoted 5 lines · Phillip Wood via GitGitGadget

xdiff/xmacros.h +0 -0

index 9fd3c5da91a..23db8e785d7 100644

xdiff/xmacros.h do { \ · line 63

Quoted 9 lines

xdiff/xmacros.h +6 -0

@@ -55,4 +55,10 @@ do { \
  		? xdl_malloc((nr) * sizeof(*(p)))	\
  		: NULL)
 
+/* Allocate an array of nr zeroed out elements, returns NULL on failure */
+#define XDL_CALLOC_ARRAY(p, nr)				\
+	(XDL_ALLOC_ARRAY((p), (nr))			\
+		? memset((p), 0, (nr) * sizeof(*(p)))	\
+		: NULL)
+

This implementation is somewhat dissapointing. Allocating and then clearing is conceptually different from allocating an already cleared buffer.

Wouldn't it make more sense to build on top of xcalloc() or its counterpart in xdl world by introducing xdl_calloc()? For that, this step would probably need to become two patches. The first patch introduces xdl_calloc(), which uses xcalloc() in our codebase, and turn the existing "alloc and clear" code to use it, and the second patch would wrap the use of xdl_calloc() in the size-safe macro XDL_CALLOC_ARRAY().

Quoted 15 lines · Phillip Wood

Quoted 6 lines · Phillip Wood

Quoted 5 lines · Ævar Arnfjörð Bjarmason

Quoted 2 lines · Phillip Wood via GitGitGadget

From: Phillip Wood <[email protected]>

Quoted 7 lines

Quoted 7 lines

Quoted 3 lines

Add a helper to grow an array. This is analogous to ALLOC_GROW() in the rest of the codebase but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2.

Urm, does it? I just skimmed this, so maybe I missed something, but I don't see where you changed the definition of xdl_malloc(), xdl_realloc() etc.

Quoted 5 lines

Oh I think I might have misunderstood your question. For git.git it will still die() but for other users that arrange for xdl_realloc() to return NULL on failure it will return -1. The same applies to the comments in the previous two patches about XDL_[CM]ALLOC_ARRAY() returning NULL on allocation failure.

Yes, I meant that the "but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2" is really more of a:

...but *allows for* dropping in another xmalloc(), xrealloc() etc. implementation that doesn't die on failure.

So I think the rest of my upthread question still stands, i.e.:

"So if that's the plan why would we need an XDL_ALLOC_ARRAY(), can't you just check that it [I mean ALLOC_ARRAY()] returns non-NULL?"

I.e. if the plan is to replace the underlying x*() functions with non-fatal variants can't you use ALLOC_ARRAY() instead? I haven't tried that, but I don't see a reason we couldn't do that in principle...

Anyway, I'm all for the end goal here, but the way to get there seems to be a bit of an exercise in running with scissors the more I think about it.

I.e. the reason we're using these x*alloc() wrappers at all is because we're lazy and want to write stuff like:

	struct stuff *foo = xmalloc(...);
	foo->bar = "baz";

Which the compiler is helpfully not yelling at us about, as opposed to doing the same with "malloc()", where it would spot the potential null pointer dereference.

(I'm using "compiler" here to be inclusive of extended gcc/clang options to detect this sort of thing, & other similar analyzers).

But re "scissors": if we're doing to be maintaining the xdiff code in-tree to be defined as our usual x*alloc() functions we're going to be carrying code that can't have test or analysis coverage.

Which I think brings me back to my suggestion of whether we can't just have non-fatal versions of these helper macros, define our own currently fatal versions in terms of those, and use the non-fatal versions in the xdiff/ code.

Hi Ævar

Quoted 22 lines · Ævar Arnfjörð Bjarmason

Quoted 15 lines · Phillip Wood

Quoted 6 lines · Phillip Wood

Quoted 5 lines · Ævar Arnfjörð Bjarmason

Quoted 2 lines · Phillip Wood via GitGitGadget

From: Phillip Wood <[email protected]>

Quoted 7 lines

Quoted 7 lines

Quoted 3 lines

Add a helper to grow an array. This is analogous to ALLOC_GROW() in the rest of the codebase but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2.

Urm, does it? I just skimmed this, so maybe I missed something, but I don't see where you changed the definition of xdl_malloc(), xdl_realloc() etc.

Quoted 5 lines

Oh I think I might have misunderstood your question. For git.git it will still die() but for other users that arrange for xdl_realloc() to return NULL on failure it will return -1. The same applies to the comments in the previous two patches about XDL_[CM]ALLOC_ARRAY() returning NULL on allocation failure.

Quoted 12 lines

Yes, I meant that the "but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2" is really more of a:
...but *allows for* dropping in another xmalloc(), xrealloc() etc. implementation that doesn't die on failure.
So I think the rest of my upthread question still stands, i.e.:
"So if that's the plan why would we need an XDL_ALLOC_ARRAY(), can't you just check that it [I mean ALLOC_ARRAY()] returns non-NULL?"
I.e. if the plan is to replace the underlying x*() functions with non-fatal variants can't you use ALLOC_ARRAY() instead? I haven't tried that, but I don't see a reason we couldn't do that in principle...

As the cover letter says, the aim of this series is not to replace xmalloc() etc with non-fatal variants, it is just to make the xdiff code more readable.

(One can already use a non-fatal allocation
function for xdl_malloc()) [...]

I don't think that using ALLOC_ARRAY() in
xdiff is helpful for other users as they would have to define their own array allocation macros, rather than just providing their own allocation functions. I would like to reduce the friction others have upstreaming xdiff patches to us, not increase it.

Quoted 38 lines · Phillip Wood

Hi Ævar

Quoted 22 lines · Ævar Arnfjörð Bjarmason

Quoted 15 lines · Phillip Wood

Quoted 6 lines · Phillip Wood

Quoted 5 lines · Ævar Arnfjörð Bjarmason

Quoted 2 lines · Phillip Wood via GitGitGadget

From: Phillip Wood <[email protected]>

Quoted 7 lines

Quoted 7 lines

Quoted 3 lines

Add a helper to grow an array. This is analogous to ALLOC_GROW() in the rest of the codebase but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2.

Urm, does it? I just skimmed this, so maybe I missed something, but I don't see where you changed the definition of xdl_malloc(), xdl_realloc() etc.

Quoted 5 lines

Oh I think I might have misunderstood your question. For git.git it will still die() but for other users that arrange for xdl_realloc() to return NULL on failure it will return -1. The same applies to the comments in the previous two patches about XDL_[CM]ALLOC_ARRAY() returning NULL on allocation failure.

Quoted 12 lines

Yes, I meant that the "but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2" is really more of a:
...but *allows for* dropping in another xmalloc(), xrealloc() etc. implementation that doesn't die on failure.
So I think the rest of my upthread question still stands, i.e.:
"So if that's the plan why would we need an XDL_ALLOC_ARRAY(), can't you just check that it [I mean ALLOC_ARRAY()] returns non-NULL?"
I.e. if the plan is to replace the underlying x*() functions with non-fatal variants can't you use ALLOC_ARRAY() instead? I haven't tried that, but I don't see a reason we couldn't do that in principle...

Quoted 3 lines

As the cover letter says, the aim of this series is not to replace xmalloc() etc with non-fatal variants, it is just to make the xdiff code more readable.

I don't think it's more readable to carry code in-tree that's unreachable except when combined with code out-of-tree. I.e. this series leaves us with the equivalent of:

	ptr = xmalloc(...);
         if (!ptr)
		/* unreachable in git.git ... */

I don't think it's more readable to have code that rather trivial analysis will show goes against the "__attribute__((noreturn))" we're placing on our die() function.

Which is what I'm pointing out with "running with scissors". I.e. I'm fully on-board with the end goal, but that can be accomplished in a way that doesn't confuse humans & analyzers alike.

Quoted 2 lines

(One can already use a non-fatal allocation
function for xdl_malloc()) [...]

That just seems inviting a segfault or undefined/untested behavior (whether in the sense of "undefined by C" or "untested by git.git's codebase logic"). Everything around xmalloc() now assumes "never returns NULL", and you want to:

* Make it return NULL when combined with out-of-tree-code

* Maintain the code in git.git, where it never returns NULL, but in a way where we won't have bugs when combined with a new macro that behaves differently, in a way we never even test ourselves.

Isn't that correct, or am I missing something?

Quoted 5 lines

I don't think that using ALLOC_ARRAY() in
xdiff is helpful for other users as they would have to define their own array allocation macros, rather than just providing their own allocation functions. I would like to reduce the friction others have upstreaming xdiff patches to us, not increase it.

Yes, I'm totally on-board with reducing the friction in others using xdiff, and would like to see more of that sort of out-of-tree use in general (although for things outside of xdiff GPL v.s. LGPL concerns come into play).

I'd even like for us to explicitly make that much easier. I.e. if you want to use xdiff now you search for it, and find the at this point unmaintained upstream, and if you find that git has a "newer" version you'll have some trouble extracting it already.

After this series you'll need to start writing & maintaining your own non-trivial alloc wrapper logic if you're doing that. If you get it subtly wrong you'll have a buggy xdiff, and most likely users will just copy/paste the git.git version from our git-compat-util.h & cache.h, which is rather silly.

Which is why I'm saying we could/should do this in a much easier way, i.e.:

* Factor out the now only-fatal-on-NULL ALLOC_GROW() such that we can have a non-fatal version (ALLOC_GROW) and a non-fatal one.

I don't know what we'd call it. we usually have X*() meaning "fatal", but these are fatal by default, maybe G* for gently? So GALLOC_GROW(). Urgh, anyway, continuing with that ugly name...

* Have xdiff/ use that GALLOC_GROW() & malloc(), not ALLOC_GROW() & xmalloc(), as we really want to have the appropriate code flow analysis etc. spot for us that we should handle NULL returns, otherwise combining this code with libgit2 will be buggy/broken.

This makes it much easier for libgit2 to use this, as it won't need to do anything special at all. Since our GALLOC_GROW() will eventualy use malloc() instead of xmalloc() you don't need to define anything that re-implements the GALLOC_GROW() or whatever other non-fatal versions of our only-fatal helpers we have.

This assumes that we'd move these macros out of git-compat-util.h and a new git-exernal-compat.h, or that instead of *just* copying the xdiff/ directory your import script would need to run some small bit of cc -E and or perl/sed to one-off extract the smell bits of git-exernal-compat.h or cache.h that we need.

Quoted 9 lines · Ævar Arnfjörð Bjarmason

I don't think it's more readable to carry code in-tree that's unreachable except when combined with code out-of-tree. I.e. this series leaves us with the equivalent of:

     ptr = xmalloc(...);
         if (!ptr)
             /* unreachable in git.git ... */

I don't think it's more readable to have code that rather trivial analysis will show goes against the "__attribute__((noreturn))" we're placing on our die() function.

We're already in this situation. The code in xdiff is written to handle allocation failures and we use an allocation function that dies instead. This patch series does nothing to alter that situation. [...]

Quoted 5 lines

That just seems inviting a segfault or undefined/untested behavior (whether in the sense of "undefined by C" or "untested by git.git's codebase logic"). Everything around xmalloc() now assumes "never returns NULL", and you want to:
* Make it return NULL when combined with out-of-tree-code

No I do not want to alter the behavior of xmalloc() at all, that is why this series does not alter the behavior of xmalloc() [...]
I think there is an argument that we should change our xdiff wrapper to use malloc() rather than xmalloc() so we're able to test the error handling. That then begs the question as to how we actually get the allocation functions to fail when they're being tested. I also think that is an orthogonal change that could happen with or without this patch series.

As noted in 36c83197249 (xdiff: use xmalloc/xrealloc, 2019-04-11) the reason we have xdl_malloc() in the first place was to make the xdiff code safer, it was not handling some allocation failures correctly at the time.

But as noted in that commit doing this was intended as a stopgap, as various code in xdiff/* did not correctly handle allocation failures, and would have segfaulted if malloc() returned NULL.

But since then and after preceding commits we can be confident that malloc() failures are handled correctly. All of these users of xdl_malloc() are checking their return values, and we're returning -1 (or similar ) to the top-level in case of failures.

This also has the big advantage of making the compiler and analysis tools less confused, and potentially avoiding undefined (compiler) behavior. I.e. we define our own xmalloc() to call die() on failure, and that function uses the non-standard "noreturn" attribute on our most common compiler targets.

But xdl_malloc()'s use conflicted with that, confusing both human readers of this code, and potentially compilers as well.

Signed-off-by Ævar Arnfjörð Bjarmason <[email protected]>

---
  xdiff/xdiff.h  |  1 -
  xdiff/xdiffi.c |  2 +-
  xdiff/xmerge.c | 10 +++++-----
  xdiff/xutils.c |  2 +-
  4 files changed, 7 insertions(+), 8 deletions(-)

xdiff/xdiff.h +0 -1

index 832cf9d977e..df048e0099b 100644
@@ -119,7 +119,6 @@ typedef struct s_bdiffparam {
  } bdiffparam_t;
 
 
-#define xdl_malloc(x) xmalloc(x)
  #define xdl_free(ptr) free(ptr)
 
  void *xdl_mmfile_first(mmfile_t *mmf, long *size);

xdiff/xdiffi.c +1 -1

index 077cc456087..6590811634f 100644
@@ -368,7 +368,7 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
  static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2) {
  	xdchange_t *xch;
 
-	if (!(xch = (xdchange_t *) xdl_malloc(sizeof(xdchange_t))))
+	if (!(xch = (xdchange_t *) malloc(sizeof(xdchange_t))))
  		return NULL;
 
  	xch->next = xscr;

xdiff/xmerge.c +5 -5

index ac0cf52f3be..676ad39020d 100644
@@ -60,7 +60,7 @@ static int xdl_append_merge(xdmerge_t **merge, int mode,
  		m->chg1 = i1 + chg1 - m->i1;
  		m->chg2 = i2 + chg2 - m->i2;
  	} else {
-		m = xdl_malloc(sizeof(xdmerge_t));
+		m = malloc(sizeof(xdmerge_t));
  		if (!m)
  			return -1;
  		m->next = NULL;

@@ -409,7 +409,7 @@ static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
  		m->i2 = xscr->i2 + i2;
  		m->chg2 = xscr->chg2;
  		while (xscr->next) {
-			xdmerge_t *m2 = xdl_malloc(sizeof(xdmerge_t));
+			xdmerge_t *m2 = malloc(sizeof(xdmerge_t));
  			if (!m2) {
  				xdl_free_env(&xe);
  				xdl_free_script(x);

@@ -670,7 +670,7 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
  						 ancestor_name,
  						 favor, changes, NULL, style,
  						 marker_size);
-		result->ptr = xdl_malloc(size);
+		result->ptr = malloc(size);
  		if (!result->ptr) {
  			xdl_cleanup_merge(changes);
  			return -1;

@@ -718,14 +718,14 @@ int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2,
  	}
  	status = 0;
  	if (!xscr1) {
-		result->ptr = xdl_malloc(mf2->size);
+		result->ptr = malloc(mf2->size);
  		if (!result->ptr)
  			goto out;
  		status = 0;
  		memcpy(result->ptr, mf2->ptr, mf2->size);
  		result->size = mf2->size;
  	} else if (!xscr2) {
-		result->ptr = xdl_malloc(mf1->size);
+		result->ptr = malloc(mf1->size);
  		if (!result->ptr)
  			goto out;
  		status = 0;

xdiff/xutils.c +1 -1

index c0cd5338c4e..865e08f0e93 100644
@@ -98,7 +98,7 @@ void *xdl_cha_alloc(chastore_t *cha) {
  	void *data;
 
  	if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {
-		if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {
+		if (!(ancur = (chanode_t *) malloc(sizeof(chanode_t) + cha->nsize))) {
 
  			return NULL;
  		}

Remove the xdl_free() wrapper macro in favor of using free() directly. The wrapper macro was brought in with the initial import of xdiff/ in 3443546f6ef (Use a *real* built-in diff generator, 2006-03-24).

As subsequent discussions on the topic[1] have made clear there's no reason to use this wrapper.

Both git itself as well as any external
users such as libgit2 compile the xdiff/* code as part of their own compilation, and can thus find the right malloc() and free() at link-time.

When compiling git we already find a custom malloc() and free() e.g. if compiled with USE_NED_ALLOCATOR=YesPlease.

1. https://lore.kernel.org/git/[email protected]/

Signed-off-by Ævar Arnfjörð Bjarmason <[email protected]>

---
  xdiff/xdiff.h      |  3 ---
  xdiff/xdiffi.c     |  4 ++--
  xdiff/xhistogram.c |  6 +++---
  xdiff/xpatience.c  |  8 ++++----
  xdiff/xprepare.c   | 28 ++++++++++++++--------------
  xdiff/xutils.c     |  2 +-
  6 files changed, 24 insertions(+), 27 deletions(-)

xdiff/xdiff.h +0 -3

index df048e0099b..a37d89fcdaf 100644
@@ -118,9 +118,6 @@ typedef struct s_bdiffparam {
  	long bsize;
  } bdiffparam_t;
 
-
-#define xdl_free(ptr) free(ptr)
-
  void *xdl_mmfile_first(mmfile_t *mmf, long *size);
  long xdl_mmfile_size(mmfile_t *mmf);
 

xdiff/xdiffi.c +2 -2

index 6590811634f..375bb81a8aa 100644
@@ -359,7 +359,7 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
  	res = xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,
  			   kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0,
  			   &xenv);
-	xdl_free(kvd);
+	free(kvd);
 
  	return res;
  }

@@ -960,7 +960,7 @@ void xdl_free_script(xdchange_t *xscr) {
 
  	while ((xch = xscr) != NULL) {
  		xscr = xscr->next;
-		xdl_free(xch);
+		free(xch);
  	}
  }
 

xdiff/xhistogram.c +3 -3

index f20592bfbdd..be35d9c9697 100644
@@ -240,9 +240,9 @@ static int fall_back_to_classic_diff(xpparam_t const *xpp, xdfenv_t *env,
 
  static inline void free_index(struct histindex *index)
  {
-	xdl_free(index->records);
-	xdl_free(index->line_map);
-	xdl_free(index->next_ptrs);
+	free(index->records);
+	free(index->line_map);
+	free(index->next_ptrs);
  	xdl_cha_free(&index->rcha);
  }
 

xdiff/xpatience.c +4 -4

index bb328d9f852..8fffd2b8297 100644
@@ -233,7 +233,7 @@ static int find_longest_common_sequence(struct hashmap *map, struct entry **res)
  	/* No common unique lines were found */
  	if (!longest) {
  		*res = NULL;
-		xdl_free(sequence);
+		free(sequence);
  		return 0;
  	}
 

@@ -245,7 +245,7 @@ static int find_longest_common_sequence(struct hashmap *map, struct entry **res)
  		entry = entry->previous;
  	}
  	*res = entry;
-	xdl_free(sequence);
+	free(sequence);
  	return 0;
  }
 

@@ -358,7 +358,7 @@ static int patience_diff(mmfile_t *file1, mmfile_t *file2,
  			env->xdf1.rchg[line1++ - 1] = 1;
  		while(count2--)
  			env->xdf2.rchg[line2++ - 1] = 1;
-		xdl_free(map.entries);
+		free(map.entries);
  		return 0;
  	}
 

@@ -372,7 +372,7 @@ static int patience_diff(mmfile_t *file1, mmfile_t *file2,
  		result = fall_back_to_classic_diff(&map,
  			line1, count1, line2, count2);
   out:
-	xdl_free(map.entries);
+	free(map.entries);
  	return result;
  }
 

xdiff/xprepare.c +14 -14

index 4182d9e1c0a..169629761c0 100644
@@ -89,7 +89,7 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
 
  	GALLOC_ARRAY(cf->rcrecs, cf->alloc);
  	if (!cf->rcrecs) {
-		xdl_free(cf->rchash);
+		free(cf->rchash);
  		xdl_cha_free(&cf->ncha);
  		return -1;
  	}

@@ -102,8 +102,8 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
 
  static void xdl_free_classifier(xdlclassifier_t *cf) {
 
-	xdl_free(cf->rcrecs);
-	xdl_free(cf->rchash);
+	free(cf->rcrecs);
+	free(cf->rchash);
  	xdl_cha_free(&cf->ncha);
  }
 

@@ -230,11 +230,11 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
  	return 0;
 
  abort:
-	xdl_free(ha);
-	xdl_free(rindex);
-	xdl_free(rchg);
-	xdl_free(rhash);
-	xdl_free(recs);
+	free(ha);
+	free(rindex);
+	free(rchg);
+	free(rhash);
+	free(recs);
  	xdl_cha_free(&xdf->rcha);
  	return -1;
  }

@@ -242,11 +242,11 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
 
  static void xdl_free_ctx(xdfile_t *xdf) {
 
-	xdl_free(xdf->rhash);
-	xdl_free(xdf->rindex);
-	xdl_free(xdf->rchg - 1);
-	xdl_free(xdf->ha);
-	xdl_free(xdf->recs);
+	free(xdf->rhash);
+	free(xdf->rindex);
+	free(xdf->rchg - 1);
+	free(xdf->ha);
+	free(xdf->recs);
  	xdl_cha_free(&xdf->rcha);
  }
 

@@ -424,7 +424,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
  	}
  	xdf2->nreff = nreff;
 
-	xdl_free(dis);
+	free(dis);
 
  	return 0;
  }

xdiff/xutils.c +1 -1

index 865e08f0e93..00eeba452a5 100644
@@ -88,7 +88,7 @@ void xdl_cha_free(chastore_t *cha) {
 
  	for (cur = cha->head; (tmp = cur) != NULL;) {
  		cur = cur->next;
-		xdl_free(tmp);
+		free(tmp);
  	}
  }
 

As noted in 36c83197249 (xdiff: use xmalloc/xrealloc, 2019-04-11) the reason we have xdl_malloc() in the first place was to make the xdiff code safer, it was not handling some allocation failures correctly at the time.

But as noted in that commit doing this was intended as a stopgap, as various code in xdiff/* did not correctly handle allocation failures, and would have segfaulted if malloc() returned NULL.

But since then and after preceding commits we can be confident that malloc() failures are handled correctly. All of these users of xdl_malloc() are checking their return values, and we're returning -1 (or similar ) to the top-level in case of failures.

Hi Ævar

Quoted 6 lines · Ævar Arnfjörð Bjarmason

Remove the xdl_free() wrapper macro in favor of using free() directly. The wrapper macro was brought in with the initial import of xdiff/ in 3443546f6ef (Use a *real* built-in diff generator, 2006-03-24).
As subsequent discussions on the topic[1] have made clear there's no reason to use this wrapper.

That link is to a message where you assert that there is no reason for the wrapper, you seem to be the only person in that thread making that argument. The libgit2 maintainer and others are arguing that it is worth keeping to make it easy to swap the allocator.

Quoted 4 lines

Both git itself as well as any external
users such as libgit2 compile the xdiff/* code as part of their own compilation, and can thus find the right malloc() and free() at link-time.

I'm struggling to see how that is simpler than the current situation with xdl_malloc().

Perhaps you could show how you think libgit2 could easily make xdiff use git__malloc() instead of malloc() without changing the malloc() calls (the message you linked to essentially suggests they do a search and replace). If people cannot swap in another allocator without changing the code then you are imposing a barrier to them contributing patches back to git's xdiff.

Quoted 4 lines · Ævar Arnfjörð Bjarmason

As noted in 36c83197249 (xdiff: use xmalloc/xrealloc, 2019-04-11) the reason we have xdl_malloc() in the first place was to make the xdiff code safer, it was not handling some allocation failures correctly at the time.

This is untrue, we do not have xdl_malloc to make the xdiff code safer, that macro was introduced with the initial import of
xdiff. 36c83197249 just changed its definition, the entire commit
consists of

I can see the argument for reverting that change now that we have fixed the error checking but that is not a good reason to remove xdl_malloc().

Quoted 101 lines

But as noted in that commit doing this was intended as a stopgap, as various code in xdiff/* did not correctly handle allocation failures, and would have segfaulted if malloc() returned NULL.
But since then and after preceding commits we can be confident that malloc() failures are handled correctly. All of these users of xdl_malloc() are checking their return values, and we're returning -1 (or similar ) to the top-level in case of failures. This also has the big advantage of making the compiler and analysis tools less confused, and potentially avoiding undefined (compiler) behavior. I.e. we define our own xmalloc() to call die() on failure, and that function uses the non-standard "noreturn" attribute on our most common compiler targets.
But xdl_malloc()'s use conflicted with that, confusing both human readers of this code, and potentially compilers as well.

Signed-off-by Ævar Arnfjörð Bjarmason <[email protected]>

---
  xdiff/xdiff.h  |  1 -
  xdiff/xdiffi.c |  2 +-
  xdiff/xmerge.c | 10 +++++-----
  xdiff/xutils.c |  2 +-
  4 files changed, 7 insertions(+), 8 deletions(-)

xdiff/xdiff.h +0 -1

index 832cf9d977e..df048e0099b 100644
@@ -119,7 +119,6 @@ typedef struct s_bdiffparam {
  } bdiffparam_t;
 
-#define xdl_malloc(x) xmalloc(x)
  #define xdl_free(ptr) free(ptr)
    void *xdl_mmfile_first(mmfile_t *mmf, long *size);

xdiff/xdiffi.c +1 -0

index 077cc456087..6590811634f 100644
@@ -368,7 +368,7 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
  static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2) {
  	xdchange_t *xch;
  -	if (!(xch = (xdchange_t *) xdl_malloc(sizeof(xdchange_t))))
+	if (!(xch = (xdchange_t *) malloc(sizeof(xdchange_t))))
  		return NULL;
    	xch->next = xscr;

xdiff/xmerge.c +5 -5

index ac0cf52f3be..676ad39020d 100644
@@ -60,7 +60,7 @@ static int xdl_append_merge(xdmerge_t **merge, int mode,
  		m->chg1 = i1 + chg1 - m->i1;
  		m->chg2 = i2 + chg2 - m->i2;
  	} else {
-		m = xdl_malloc(sizeof(xdmerge_t));
+		m = malloc(sizeof(xdmerge_t));
  		if (!m)
  			return -1;
  		m->next = NULL;

@@ -409,7 +409,7 @@ static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,
  		m->i2 = xscr->i2 + i2;
  		m->chg2 = xscr->chg2;
  		while (xscr->next) {
-			xdmerge_t *m2 = xdl_malloc(sizeof(xdmerge_t));
+			xdmerge_t *m2 = malloc(sizeof(xdmerge_t));
  			if (!m2) {
  				xdl_free_env(&xe);
  				xdl_free_script(x);

@@ -670,7 +670,7 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1,
  						 ancestor_name,
  						 favor, changes, NULL, style,
  						 marker_size);
-		result->ptr = xdl_malloc(size);
+		result->ptr = malloc(size);
  		if (!result->ptr) {
  			xdl_cleanup_merge(changes);
  			return -1;

@@ -718,14 +718,14 @@ int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2,
  	}
  	status = 0;
  	if (!xscr1) {
-		result->ptr = xdl_malloc(mf2->size);
+		result->ptr = malloc(mf2->size);
  		if (!result->ptr)
  			goto out;
  		status = 0;
  		memcpy(result->ptr, mf2->ptr, mf2->size);
  		result->size = mf2->size;
  	} else if (!xscr2) {
-		result->ptr = xdl_malloc(mf1->size);
+		result->ptr = malloc(mf1->size);
  		if (!result->ptr)
  			goto out;
  		status = 0;

xdiff/xutils.c +1 -1

index c0cd5338c4e..865e08f0e93 100644
@@ -98,7 +98,7 @@ void *xdl_cha_alloc(chastore_t *cha) {
  	void *data;
    	if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {
-		if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {
+		if (!(ancur = (chanode_t *) malloc(sizeof(chanode_t) + cha->nsize))) {
    			return NULL;
  		}

Quoted 5 lines · Ævar Arnfjörð Bjarmason

As noted in 36c83197249 (xdiff: use xmalloc/xrealloc, 2019-04-11) the reason we have xdl_malloc() in the first place was to make the xdiff code safer, it was not handling some allocation failures correctly at the time.

Quoted 8 lines

But as noted in that commit doing this was intended as a stopgap, as various code in xdiff/* did not correctly handle allocation failures, and would have segfaulted if malloc() returned NULL.

But since then and after preceding commits we can be confident that malloc() failures are handled correctly. All of these users of xdl_malloc() are checking their return values, and we're returning -1 (or similar ) to the top-level in case of failures.

This is also losing the other parts mentioned in 36c83197249:
respecting GIT_ALLOC_LIMIT and any memory reclamation strategies.

I think you'd want an xmalloc_gently() instead of a raw malloc().

For the same reason, I suspect it's better to leave this with a layer of preprocessor indirection. Even if we chose to use malloc() here, libgit2 might not, and having the macro makes it easier to share the code.

From: Phillip Wood <[email protected]>

Add a helper to grow an array. This is analogous to ALLOC_GROW() in the rest of the codebase but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2. [...]

xdiff/xutils.c +7 -0

+		if (XDL_ALLOC_GROW(cf->rcrecs, cf->count, cf->alloc))
+void* xdl_alloc_grow_helper(void *p, long nr, long *alloc, size_t size)
+{
+	void *tmp = NULL;
+	size_t n = ((LONG_MAX - 16) / 2 >= *alloc) ? 2 * *alloc + 16 : LONG_MAX;
+	if (nr > n)
+		n = nr;

Quoted 10 lines · Phillip Wood

Hi Ævar

Quoted 6 lines · Ævar Arnfjörð Bjarmason

Remove the xdl_free() wrapper macro in favor of using free() directly. The wrapper macro was brought in with the initial import of xdiff/ in 3443546f6ef (Use a *real* built-in diff generator, 2006-03-24).
As subsequent discussions on the topic[1] have made clear there's no reason to use this wrapper.

Quoted 4 lines

That link is to a message where you assert that there is no reason for the wrapper, you seem to be the only person in that thread making that argument. The libgit2 maintainer and others are arguing that it is worth keeping to make it easy to swap the allocator.

Arguing that it's not needed for a technical reason, but an "aesthetic and ergonomic one", per:
https://lore.kernel.org/git/20220217225804.GC7@edef91d97c94/;

Perhaps I misread it, but I took this as Junio concurring with what I was pointing out there:
https://lore.kernel.org/git/[email protected]/

Quoted 7 lines

Quoted 4 lines

Both git itself as well as any external
users such as libgit2 compile the xdiff/* code as part of their own compilation, and can thus find the right malloc() and free() at link-time.

I'm struggling to see how that is simpler than the current situation with xdl_malloc().

It's simpler because when maintaining that code in git.git it's less of a special case, e.g. we have coccinelle rules that match free(), now every such rule needs to account for the xdiff special-case.

And it's less buggy because if you're relying on us always using a wrapper bugs will creep in, current master has this:

	$ git -P grep '\bfree\(' -- xdiff
	xdiff/xdiff.h:#define xdl_free(ptr) free(ptr)
	xdiff/xmerge.c:         free(c);
	xdiff/xmerge.c: free(next_m);

Quoted 6 lines

Perhaps you could show how you think libgit2 could easily make xdiff use git__malloc() instead of malloc() without changing the malloc() calls (the message you linked to essentially suggests they do a search and replace). If people cannot swap in another allocator without changing the code then you are imposing a barrier to them contributing patches back to git's xdiff.

I was suggesting that if libgit2 wanted to maintain a copy of xdiff that catered to the asthetic desires of the maintainer adjusting whatever import script you use to apply a trivial coccinelle transformation would give you what you wanted. Except without a maintenance burden on git.git, or the bugs you'd get now since you're not catching those two free() cases (or any future such cases).

But just having the code use malloc() and free() directly and getting you what you get now is easy, and doesn't require any such search-replacement.

Here's how:

I imported the xdiff/*.[ch] files at the tip of my branch into current libgit2.git's src/libgit2/xdiff/, and then applied this on top, which is partially re-applying libgit2's own monkeypatches, and partially adjusting for upstream changes (including this one):

	diff --git a/src/libgit2/xdiff/git-xdiff.h b/src/libgit2/xdiff/git-xdiff.h
	index b75dba819..2e00764d4 100644
	--- a/src/libgit2/xdiff/git-xdiff.h
	+++ b/src/libgit2/xdiff/git-xdiff.h
	@@ -14,6 +14,7 @@
	 #ifndef INCLUDE_git_xdiff_h__
	 #define INCLUDE_git_xdiff_h__
	
	+#include <regex.h>
	 #include "regexp.h"
	
	 /* Work around C90-conformance issues */
	@@ -27,11 +28,10 @@
	 # endif
	 #endif
	
	-#define xdl_malloc(x) git__malloc(x)
	-#define xdl_free(ptr) git__free(ptr)
	-#define xdl_realloc(ptr, x) git__realloc(ptr, x)
	+#define malloc(x) git__malloc(x)
	+#define free(ptr) git__free(ptr)
	
	-#define XDL_BUG(msg) GIT_ASSERT(msg)
	+#define BUG(msg) GIT_ASSERT(msg)
	
	 #define xdl_regex_t git_regexp
	 #define xdl_regmatch_t git_regmatch
	@@ -50,4 +50,17 @@ GIT_INLINE(int) xdl_regexec_buf(
	 	return -1;
	 }
	
	+static inline size_t st_mult(size_t a, size_t b)
	+{
	+	return a * b;
	+}
	+
	+static inline int regexec_buf(const regex_t *preg, const char *buf, size_t size,
	+			      size_t nmatch, regmatch_t pmatch[], int eflags)
	+{
	+	assert(nmatch > 0 && pmatch);
	+	pmatch[0].rm_so = 0;
	+	pmatch[0].rm_eo = size;
	+	return regexec(preg, buf, nmatch, pmatch, eflags | REG_STARTEND);
	+}
	 #endif
	diff --git a/src/libgit2/xdiff/xdiff.h b/src/libgit2/xdiff/xdiff.h
	index a37d89fcd..5e5b525c2 100644
	--- a/src/libgit2/xdiff/xdiff.h
	+++ b/src/libgit2/xdiff/xdiff.h
	@@ -23,6 +23,8 @@
	 #if !defined(XDIFF_H)
	 #define XDIFF_H
	
	+#include "git-xdiff.h"
	+
	 #ifdef __cplusplus
	 extern "C" {
	 #endif /* #ifdef __cplusplus */
	diff --git a/src/libgit2/xdiff/xinclude.h b/src/libgit2/xdiff/xinclude.h
	index a4285ac0e..79812ad8a 100644
	--- a/src/libgit2/xdiff/xinclude.h
	+++ b/src/libgit2/xdiff/xinclude.h
	@@ -23,7 +23,8 @@
	 #if !defined(XINCLUDE_H)
	 #define XINCLUDE_H
	
	-#include "git-compat-util.h"
	+#include "git-xdiff.h"
	+#include "git-shared-util.h"
	 #include "xmacros.h"
	 #include "xdiff.h"
	 #include "xtypes.h"

If you then build it and run e.g.:

gdb -args ./libgit2_tests -smerge::files

You'll get stack traces like this if you break on stdalloc__malloc (which it uses for me in its default configuration):

	(gdb) bt
	#0  stdalloc__malloc (len=144, file=0x87478d "/home/avar/g/libgit2/src/libgit2/xdiff/xutils.c", line=101) at /home/avar/g/libgit2/src/util/allocators/stdalloc.c:14
	#1  0x00000000006ec15c in xdl_cha_alloc (cha=0x7fffffffcaa8) at /home/avar/g/libgit2/src/libgit2/xdiff/xutils.c:101
	#2  0x00000000006eaee9 in xdl_prepare_ctx (pass=1, mf=0x7fffffffcc98, narec=13, xpp=0x7fffffffcca8, cf=0x7fffffffc7d0, xdf=0x7fffffffcaa8)
	    at /home/avar/g/libgit2/src/libgit2/xdiff/xprepare.c:194

IOW this was all seamlessly routed to your git__malloc() without us having to maintain an xdl_{malloc,free}().

Now, I think that's obviously worth adjusting, e.g. the series I've got here could make this easier for libgit2 by including st_mult() at least, I'm not sure what you want to do about regexec_buf().

For the monkeypatching you do now of creating a "git-xdiff.h" I think it would be very good to get a patch like what I managed to get sha1collisiondetection.git to accept for our own use-case, which allows us to use their upstream code as-is from a submodule:

https://github.com/cr-marcstevens/sha1collisiondetection/commit/b45fcef

But we also have a few other uses of malloc() in the codebase. I wonder if the right thing here isn't to just use malloc(), but to have git-compat-util.h override malloc() (similar to how we we override e.g. exit() now...), which would also catch those.

Quoted 7 lines

For the monkeypatching you do now of creating a "git-xdiff.h" I think it would be very good to get a patch like what I managed to get sha1collisiondetection.git to accept for our own use-case, which allows us to use their upstream code as-is from a submodule:

    https://github.com/cr-marcstevens/sha1collisiondetection/commit/b45fcef

Thanks for the link, That's a really good example where all the identifiers are namespaced and the public include file does not pollute the code that is including it. If you come up with something like that where the client code can set up same #defines for malloc, calloc, realloc and free that would be a good way forward.

I do not think we should require projects to be defining there own versions of [C]ALLOC_*() and BUG() just to use xdiff.

Best Wishes

Phillip

Quoted 13 lines · Phillip Wood via GitGitGadget

From: Phillip Wood <[email protected]>

Add a helper to grow an array. This is analogous to ALLOC_GROW() in the rest of the codebase but returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2. [...]

xdiff/xutils.c +7 -0

+		if (XDL_ALLOC_GROW(cf->rcrecs, cf->count, cf->alloc))
+void* xdl_alloc_grow_helper(void *p, long nr, long *alloc, size_t size)
+{
+	void *tmp = NULL;
+	size_t n = ((LONG_MAX - 16) / 2 >= *alloc) ? 2 * *alloc + 16 : LONG_MAX;
+	if (nr > n)
+		n = nr;

xdiff/xutils.c int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, · line 451

Quoted 10 lines

xdiff/xutils.c +10 -0

+	if (SIZE_MAX / size >= n)
+		tmp = xdl_realloc(p, n * size);
+	if (tmp) {
+		*alloc = n;
+	} else {
+		xdl_free(p);
+		*alloc = 0;
+	}
+	return tmp;
+}

Whether you agree with the entire approach in my series-on-top[1] or not (and it looks like not), this way of doing it seems needlessly complex.

I.e. the whole "pass the size" business is here because you're wanting to use this as an expression, which ALLOC_GROW() isn't able to do.

But you've also changed every single callsite anyway.

So why not just change:

     if (XDL_ALLOC_GROW(recs, ...))

To:

     XDL_ALLOC_GROW(recs, ...);
     if (!recs)

And do away with needing to pass this through a function where we get the size, and thus losing the type information before we can call sizeof().

Then, as that series shows the implementation here could be pretty much an exact line-for-line copy of what we have in cache.h, including the same alloc_nr(), all without casts etc.

All of which seems much simpler than trying to maintain the constraint that this must be usable in an expression.

Your commit message sort-of addresses this by mentioning that this "returns −1 on allocation failure to accommodate other users of libxdiff such as libgit2".

But since libgit2 won't use this, but only a copy of this xdiff code in libgit2 I don't see how that makes sense. We're only talking about using this in the xdiff code we maintain, and even if libgit2 wanted to use it it could deal with not being able to use it in an expression, no?

1. https://lore.kernel.org/git/[email protected]/

Add "gently" versions of ALLOC_ARRAY(), CALLOC_ARRAY() etc. using the naming convention G*() as a shorthand for "GENTLY_*()".

Nothing uses these functions yet, but as we'll see in subsequent commit(s) we're able to convert things that need e.g. non-fatal "ALLOC_GROW" behavior over to this.

Signed-off-by Ævar Arnfjörð Bjarmason <[email protected]>

---
  git-shared-util.h | 15 +++++++++++++--
  1 file changed, 13 insertions(+), 2 deletions(-)

git-shared-util.h +6 -0

index 7b4479a0f72..718a8e00732 100644
@@ -8,8 +8,11 @@
  #define FREE_AND_NULL(p) do { free(p); (p) = NULL; } while (0)
 
  #define ALLOC_ARRAY(x, alloc) (x) = xmalloc(st_mult(sizeof(*(x)), (alloc)))
+#define GALLOC_ARRAY(x, alloc) (x) = malloc(st_mult(sizeof(*(x)), (alloc)))
  #define CALLOC_ARRAY(x, alloc) (x) = xcalloc((alloc), sizeof(*(x)))
+#define GCALLOC_ARRAY(x, alloc) (x) = calloc((alloc), sizeof(*(x)))
  #define REALLOC_ARRAY(x, alloc) (x) = xrealloc((x), st_mult(sizeof(*(x)), (alloc)))
+#define GREALLOC_ARRAY(x, alloc) (x) = realloc((x), st_mult(sizeof(*(x)), (alloc)))
 
  #define COPY_ARRAY(dst, src, n) copy_array((dst), (src), (n), sizeof(*(dst)) + \
  	BUILD_ASSERT_OR_ZERO(sizeof(*(dst)) == sizeof(*(src))))

@@ -71,17 +74,25 @@ static inline void move_array(void *dst, const void *src, size_t n, size_t size)
   * added niceties.
   *
   * DO NOT USE any expression with side-effect for 'x', 'nr', or 'alloc'.
+ *
+ * GALLOC_GROW() behaves like ALLOC_GROW(), except that in malloc()
+ * failure we'll return NULL rather than dying.

git-shared-util.h +6 -0

+			if (gently) \
+				GREALLOC_ARRAY(x, alloc); \
+			else \
+				REALLOC_ARRAY(x, alloc); \
  		} \
  	} while (0)
+#define ALLOC_GROW(x, nr, alloc) ALLOC_GROW_1(x, nr, alloc, 0)
+#define GALLOC_GROW(x, nr, alloc) ALLOC_GROW_1(x, nr, alloc, 1)
 
  /*
   * Similar to ALLOC_GROW but handles updating of the nr value and

Use the newly created GCALLOC_ARRAY() helpers rather than the recently introduced XDL_[C]ALLOC_ARRAY().

As shown in this diff the calling convention differs, we cannot use GCALLOC_ARRAY() as an expression, but that's an advantage in not having to relay the "sizeof()" down via a wrapper function.

This also:

* Fixes long-standing potential overflow issues, as we're using st_mult() in the underlying G_[C]ALLOC(). Note that the

* Slightly optimizes the "XDL_CALLOC_ARRAY", as we'll now use calloc() rather than malloc() + memset() (although smart compilers will probably do the same for both...).

* Changes the "XDL_CALLOC_ARRAY" behavior where we'd shortcut if the size was already large enough, but this behavior was changed when XDL_ALLOC_ARRAY() was introduced, so this is safe.

Signed-off-by Ævar Arnfjörð Bjarmason <[email protected]>

---
  xdiff/xdiffi.c     |  3 ++-
  xdiff/xhistogram.c |  9 ++++++---
  xdiff/xmacros.h    | 12 ------------
  xdiff/xpatience.c  |  6 ++++--
  xdiff/xprepare.c   | 24 ++++++++++++++++--------
  5 files changed, 28 insertions(+), 26 deletions(-)

xdiff/xdiffi.c +2 -1

index 6fded43e87d..077cc456087 100644
@@ -333,7 +333,8 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
  	 * One is to store the forward path and one to store the backward path.
  	 */
  	ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
-	if (!XDL_ALLOC_ARRAY(kvd, 2 * ndiags + 2))
+	GALLOC_ARRAY(kvd, 2 * ndiags + 2);
+	if (!kvd)
  		return -1;
  	kvdf = kvd;
  	kvdb = kvdf + ndiags;

xdiff/xhistogram.c +0 -0

index df909004c10..f20592bfbdd 100644

xdiff/xhistogram.c +4 -2

  		goto cleanup;
 
  	index.line_map_size = count1;
-	if (!XDL_CALLOC_ARRAY(index.line_map, index.line_map_size))
+	GCALLOC_ARRAY(index.line_map, index.line_map_size);
+	if (!index.line_map)
  		goto cleanup;
 
-	if (!XDL_CALLOC_ARRAY(index.next_ptrs, index.line_map_size))
+	GCALLOC_ARRAY(index.next_ptrs, index.line_map_size);
+	if (!index.next_ptrs)
  		goto cleanup;
 
  	/* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */

xdiff/xmacros.h +0 -12

index d13a6724629..75506bdf17e 100644
@@ -49,18 +49,6 @@ do { \
  		((unsigned long) __p[2]) << 16 | ((unsigned long) __p[3]) << 24; \
  } while (0)
 
-/* Allocate an array of nr elements, returns NULL on failure */
-#define XDL_ALLOC_ARRAY(p, nr)				\
-	((p) = SIZE_MAX / sizeof(*(p)) >= (size_t)(nr)	\
-		? xdl_malloc((nr) * sizeof(*(p)))	\
-		: NULL)
-
-/* Allocate an array of nr zeroed out elements, returns NULL on failure */
-#define XDL_CALLOC_ARRAY(p, nr)				\
-	(XDL_ALLOC_ARRAY((p), (nr))			\
-		? memset((p), 0, (nr) * sizeof(*(p)))	\
-		: NULL)
-
  /*
   * Ensure array p can accommodate at least nr elements, growing the
   * array and updating alloc (which is the number of allocated

xdiff/xpatience.c +4 -2

index fe39c2978cb..bb328d9f852 100644
@@ -151,7 +151,8 @@ static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,
 
  	/* We know exactly how large we want the hash map */
  	result->alloc = count1 * 2;
-	if (!XDL_CALLOC_ARRAY(result->entries, result->alloc))
+	GCALLOC_ARRAY(result->entries, result->alloc);
+	if (!result->entries)
  		return -1;
 
  	/* First, fill with entries from the first file */

@@ -208,7 +209,8 @@ static int find_longest_common_sequence(struct hashmap *map, struct entry **res)
  	 */
  	int anchor_i = -1;
 
-	if (!XDL_ALLOC_ARRAY(sequence, map->nr))
+	GALLOC_ARRAY(sequence, map->nr);
+	if (!sequence)
  		return -1;
 
  	for (entry = map->first; entry; entry = entry->next) {

xdiff/xprepare.c +16 -8

index c84549f6c50..d6cbee32a2a 100644
@@ -78,15 +78,17 @@ static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
 
  		return -1;
  	}
-	if (!XDL_CALLOC_ARRAY(cf->rchash, cf->hsize)) {
+	GCALLOC_ARRAY(cf->rchash, cf->hsize);
+	if (!cf->rchash) {
 
  		xdl_cha_free(&cf->ncha);
  		return -1;
  	}
 
  	cf->alloc = size;
-	if (!XDL_ALLOC_ARRAY(cf->rcrecs, cf->alloc)) {
 
+	GALLOC_ARRAY(cf->rcrecs, cf->alloc);
+	if (!cf->rcrecs) {
  		xdl_free(cf->rchash);
  		xdl_cha_free(&cf->ncha);
  		return -1;

@@ -170,12 +172,14 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
 
  	if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0)
  		goto abort;
-	if (!XDL_ALLOC_ARRAY(recs, narec))
+	GALLOC_ARRAY(recs, narec);
+	if (!recs)
  		goto abort;
 
  	hbits = xdl_hashbits((unsigned int) narec);
  	hsize = 1 << hbits;
-	if (!XDL_CALLOC_ARRAY(rhash, hsize))
+	GCALLOC_ARRAY(rhash, hsize);
+	if (!rhash)
  		goto abort;
 
  	nrec = 0;

@@ -196,14 +200,17 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
  		}
  	}
 
-	if (!XDL_CALLOC_ARRAY(rchg, nrec + 2))
+	GCALLOC_ARRAY(rchg, nrec + 2);
+	if (!rchg)
  		goto abort;
 
  	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
  	    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)) {
-		if (!XDL_ALLOC_ARRAY(rindex, nrec + 1))
+		GALLOC_ARRAY(rindex, nrec + 1);
+		if (!rindex)
  			goto abort;
-		if (!XDL_ALLOC_ARRAY(ha, nrec + 1))
+		GALLOC_ARRAY(ha, nrec + 1);
+		if (!ha)
  			goto abort;
  	}
 

@@ -369,7 +376,8 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
  	xdlclass_t *rcrec;
  	char *dis, *dis1, *dis2;
 
-	if (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2))
+	GCALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2);
+	if (!dis)
  		return -1;
  	dis1 = dis;
  	dis2 = dis1 + xdf1->nrec + 1;

Replace the recently introduced XDL_ALLOC_GROW() with invocations of the GALLOC_GROW() from git-shared-util.h.

As this change shows the macro + function indirection of XDL_ALLOC_GROW() is something we needed only because the two callsites we used it in wanted to use it as an expression, and we thus had to pass the "sizeof" down.

Let's just check the value afterwards instead, which allows us to use the shared macro, we can also remove xdl_reallo(), this was its last user.

Signed-off-by Ævar Arnfjörð Bjarmason <[email protected]>

---
  xdiff/xdiff.h    |  1 -
  xdiff/xmacros.h  | 11 -----------
  xdiff/xprepare.c |  8 +++++---
  xdiff/xutils.c   | 17 -----------------
  xdiff/xutils.h   |  2 --
  5 files changed, 5 insertions(+), 34 deletions(-)

xdiff/xdiff.h +0 -1

index 72e25a9ffa5..832cf9d977e 100644
@@ -121,7 +121,6 @@ typedef struct s_bdiffparam {
 
  #define xdl_malloc(x) xmalloc(x)
  #define xdl_free(ptr) free(ptr)
-#define xdl_realloc(ptr,x) xrealloc(ptr,x)
 
  void *xdl_mmfile_first(mmfile_t *mmf, long *size);
  long xdl_mmfile_size(mmfile_t *mmf);

xdiff/xmacros.h +0 -11

index 75506bdf17e..6a6b3057375 100644
@@ -48,15 +48,4 @@ do { \
  	(v) = (unsigned long) __p[0] | ((unsigned long) __p[1]) << 8 | \
  		((unsigned long) __p[2]) << 16 | ((unsigned long) __p[3]) << 24; \
  } while (0)
-
-/*
- * Ensure array p can accommodate at least nr elements, growing the
- * array and updating alloc (which is the number of allocated
- * elements) as necessary. Frees p and returns -1 on failure, returns
- * 0 on success
- */
-#define XDL_ALLOC_GROW(p, nr, alloc)	\
-	(-!((nr) <= (alloc) ||		\
-	    ((p) = xdl_alloc_grow_helper((p), (nr), &(alloc), sizeof(*(p))))))
-
  #endif /* #if !defined(XMACROS_H) */

xdiff/xprepare.c +5 -3

index d6cbee32a2a..4182d9e1c0a 100644
@@ -128,8 +128,9 @@ static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t
  			return -1;
  		}
  		rcrec->idx = cf->count++;
-		if (XDL_ALLOC_GROW(cf->rcrecs, cf->count, cf->alloc))
-				return -1;
+		GALLOC_GROW(cf->rcrecs, cf->count, cf->alloc);
+		if (!cf->rcrecs)
+			return -1;
  		cf->rcrecs[rcrec->idx] = rcrec;
  		rcrec->line = line;
  		rcrec->size = rec->size;

@@ -187,7 +188,8 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_
  		for (top = blk + bsize; cur < top; ) {
  			prev = cur;
  			hav = xdl_hash_record(&cur, top, xpp->flags);
-			if (XDL_ALLOC_GROW(recs, nrec + 1, narec))
+			GALLOC_GROW(recs, nrec + 1, narec);
+			if (!recs)
  				goto abort;
  			if (!(crec = xdl_cha_alloc(&xdf->rcha)))
  				goto abort;

xdiff/xutils.c +0 -17

index a6f10353cff..c0cd5338c4e 100644
@@ -436,20 +436,3 @@ int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
 
  	return status;
  }
-
-void* xdl_alloc_grow_helper(void *p, long nr, long *alloc, size_t size)
-{
-	void *tmp = NULL;
-	size_t n = ((LONG_MAX - 16) / 2 >= *alloc) ? 2 * *alloc + 16 : LONG_MAX;
-	if (nr > n)
-		n = nr;
-	if (SIZE_MAX / size >= n)
-		tmp = xdl_realloc(p, n * size);
-	if (tmp) {
-		*alloc = n;
-	} else {
-		xdl_free(p);
-		*alloc = 0;
-	}
-	return tmp;
-}

xdiff/xutils.h +0 -2

index fd0bba94e8b..7ae3f897bef 100644
@@ -42,7 +42,5 @@ int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
  int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
  		       int line1, int count1, int line2, int count2);
 
-/* Do not call this function, use XDL_ALLOC_GROW instead */
-void* xdl_alloc_grow_helper(void* p, long nr, long* alloc, size_t size);
 
  #endif /* #if !defined(XUTILS_H) */

Hi Ævar

Quoted 145 lines · Ævar Arnfjörð Bjarmason

Quoted 10 lines · Phillip Wood

Hi Ævar

Quoted 6 lines · Ævar Arnfjörð Bjarmason

Remove the xdl_free() wrapper macro in favor of using free() directly. The wrapper macro was brought in with the initial import of xdiff/ in 3443546f6ef (Use a *real* built-in diff generator, 2006-03-24).
As subsequent discussions on the topic[1] have made clear there's no reason to use this wrapper.

Quoted 4 lines

That link is to a message where you assert that there is no reason for the wrapper, you seem to be the only person in that thread making that argument. The libgit2 maintainer and others are arguing that it is worth keeping to make it easy to swap the allocator.

Arguing that it's not needed for a technical reason, but an "aesthetic
and ergonomic one", per:
https://lore.kernel.org/git/20220217225804.GC7@edef91d97c94/;
Perhaps I misread it, but I took this as Junio concurring with what I
was pointing out there:
https://lore.kernel.org/git/[email protected]/

Quoted 7 lines

Quoted 4 lines

Both git itself as well as any external
users such as libgit2 compile the xdiff/* code as part of their own compilation, and can thus find the right malloc() and free() at link-time.

I'm struggling to see how that is simpler than the current situation with xdl_malloc().

It's simpler because when maintaining that code in git.git it's less of
a special case, e.g. we have coccinelle rules that match free(), now every such rule needs to account for the xdiff special-case. And it's less buggy because if you're relying on us always using a wrapper bugs will creep in, current master has this:

	$ git -P grep '\bfree\(' -- xdiff
	xdiff/xdiff.h:#define xdl_free(ptr) free(ptr)
	xdiff/xmerge.c:         free(c);
	xdiff/xmerge.c: free(next_m);

Quoted 6 lines

Perhaps you could show how you think libgit2 could easily make xdiff use git__malloc() instead of malloc() without changing the malloc() calls (the message you linked to essentially suggests they do a search and replace). If people cannot swap in another allocator without changing the code then you are imposing a barrier to them contributing patches back to git's xdiff.

I was suggesting that if libgit2 wanted to maintain a copy of xdiff that
catered to the asthetic desires of the maintainer adjusting whatever import script you use to apply a trivial coccinelle transformation would give you what you wanted. Except without a maintenance burden on git.git, or the bugs you'd get now since you're not catching those two free() cases (or any future such cases).
But just having the code use malloc() and free() directly and getting
you what you get now is easy, and doesn't require any such search-replacement.
Here's how:
I imported the xdiff/*.[ch] files at the tip of my branch into current
libgit2.git's src/libgit2/xdiff/, and then applied this on top, which is partially re-applying libgit2's own monkeypatches, and partially adjusting for upstream changes (including this one):

	diff --git a/src/libgit2/xdiff/git-xdiff.h b/src/libgit2/xdiff/git-xdiff.h
	index b75dba819..2e00764d4 100644
	--- a/src/libgit2/xdiff/git-xdiff.h
	+++ b/src/libgit2/xdiff/git-xdiff.h
	@@ -14,6 +14,7 @@
	 #ifndef INCLUDE_git_xdiff_h__
	 #define INCLUDE_git_xdiff_h__
	
	+#include <regex.h>
	 #include "regexp.h"
	
	 /* Work around C90-conformance issues */
	@@ -27,11 +28,10 @@
	 # endif
	 #endif
	
	-#define xdl_malloc(x) git__malloc(x)
	-#define xdl_free(ptr) git__free(ptr)
	-#define xdl_realloc(ptr, x) git__realloc(ptr, x)
	+#define malloc(x) git__malloc(x)
	+#define free(ptr) git__free(ptr)
	
	-#define XDL_BUG(msg) GIT_ASSERT(msg)
	+#define BUG(msg) GIT_ASSERT(msg)
	
	 #define xdl_regex_t git_regexp
	 #define xdl_regmatch_t git_regmatch
	@@ -50,4 +50,17 @@ GIT_INLINE(int) xdl_regexec_buf(
	 	return -1;
	 }
	
	+static inline size_t st_mult(size_t a, size_t b)
	+{
	+	return a * b;
	+}
	+
	+static inline int regexec_buf(const regex_t *preg, const char *buf, size_t size,
	+			      size_t nmatch, regmatch_t pmatch[], int eflags)
	+{
	+	assert(nmatch > 0 && pmatch);
	+	pmatch[0].rm_so = 0;
	+	pmatch[0].rm_eo = size;
	+	return regexec(preg, buf, nmatch, pmatch, eflags | REG_STARTEND);
	+}
	 #endif
	diff --git a/src/libgit2/xdiff/xdiff.h b/src/libgit2/xdiff/xdiff.h
	index a37d89fcd..5e5b525c2 100644
	--- a/src/libgit2/xdiff/xdiff.h
	+++ b/src/libgit2/xdiff/xdiff.h
	@@ -23,6 +23,8 @@
	 #if !defined(XDIFF_H)
	 #define XDIFF_H
	
	+#include "git-xdiff.h"
	+
	 #ifdef __cplusplus
	 extern "C" {
	 #endif /* #ifdef __cplusplus */
	diff --git a/src/libgit2/xdiff/xinclude.h b/src/libgit2/xdiff/xinclude.h
	index a4285ac0e..79812ad8a 100644
	--- a/src/libgit2/xdiff/xinclude.h
	+++ b/src/libgit2/xdiff/xinclude.h
	@@ -23,7 +23,8 @@
	 #if !defined(XINCLUDE_H)
	 #define XINCLUDE_H
	
	-#include "git-compat-util.h"
	+#include "git-xdiff.h"
	+#include "git-shared-util.h"
	 #include "xmacros.h"
	 #include "xdiff.h"
	 #include "xtypes.h"

If you then build it and run e.g.:
gdb -args ./libgit2_tests -smerge::files
You'll get stack traces like this if you break on stdalloc__malloc (which it uses for me in its default configuration):

Quoted 7 lines

	(gdb) bt
	#0  stdalloc__malloc (len=144, file=0x87478d "/home/avar/g/libgit2/src/libgit2/xdiff/xutils.c", line=101) at /home/avar/g/libgit2/src/util/allocators/stdalloc.c:14
	#1  0x00000000006ec15c in xdl_cha_alloc (cha=0x7fffffffcaa8) at /home/avar/g/libgit2/src/libgit2/xdiff/xutils.c:101
	#2  0x00000000006eaee9 in xdl_prepare_ctx (pass=1, mf=0x7fffffffcc98, narec=13, xpp=0x7fffffffcca8, cf=0x7fffffffc7d0, xdf=0x7fffffffcaa8)
	    at /home/avar/g/libgit2/src/libgit2/xdiff/xprepare.c:194

IOW this was all seamlessly routed to your git__malloc() without us having to maintain an xdl_{malloc,free}().

Thanks for showing this, it is really helpful to see a concrete example. I was especially interested to see how you went about the conversion without redefining standard library functions or introducing non-namespaced identifiers in files that included xdiff.h. Unfortunately you have not done that and so I don't think the
approach above is viable for a well behaved library.

Quoted 9 lines

Now, I think that's obviously worth adjusting, e.g. the series I've got here could make this easier for libgit2 by including st_mult() at least, I'm not sure what you want to do about regexec_buf().
For the monkeypatching you do now of creating a "git-xdiff.h" I think it
would be very good to get a patch like what I managed to get sha1collisiondetection.git to accept for our own use-case, which allows us to use their upstream code as-is from a submodule:
https://github.com/cr-marcstevens/sha1collisiondetection/commit/b45fcef

Thanks for the link, That's a really good example where all the identifiers are namespaced and the public include file does not pollute the code that is including it. If you come up with something like that where the client code can set up same #defines for malloc, calloc, realloc and free that would be a good way forward.

I do not think we should require projects to be defining there own versions of [C]ALLOC_*() and BUG() just to use xdiff.

Hi Ævar

Quoted 10 lines · Ævar Arnfjörð Bjarmason

Replace the recently introduced XDL_ALLOC_GROW() with invocations of the GALLOC_GROW() from git-shared-util.h.
As this change shows the macro + function indirection of XDL_ALLOC_GROW() is something we needed only because the two callsites we used it in wanted to use it as an expression, and we thus had to pass the "sizeof" down.
Let's just check the value afterwards instead, which allows us to use
the shared macro, we can also remove xdl_reallo(), this was its last user.

I don't think this expression->statement change is an improvement.

This change also removes the overflow checks that are present in XDL_ALLOC_GROW()[...]

and fails to free the old allocation when realloc() fails. It is not a like for like replacement.

Quoted 8 lines

But you've also changed every single callsite anyway.

So why not just change:

     if (XDL_ALLOC_GROW(recs, ...))

To:

Quoted 2 lines

     XDL_ALLOC_GROW(recs, ...);
     if (!recs)

Because I think it's ugly, we'd never define a function as void(int* result, args...) and I don't think we should do that for a macro where we can avoid it. The existing ALLOC_* macros make sense as statements because they die on failure.

Quoted 14 lines · Phillip Wood

Hi Ævar

Quoted 10 lines · Ævar Arnfjörð Bjarmason

Replace the recently introduced XDL_ALLOC_GROW() with invocations of the GALLOC_GROW() from git-shared-util.h.
As this change shows the macro + function indirection of XDL_ALLOC_GROW() is something we needed only because the two callsites we used it in wanted to use it as an expression, and we thus had to pass the "sizeof" down.
Let's just check the value afterwards instead, which allows us to use
the shared macro, we can also remove xdl_reallo(), this was its last user.

Quoted 2 lines

I don't think this expression->statement change is an improvement.

I think the use-as-statement is prettier too, but I think the uglyness of having to pass down the sizeof() & re-implementing the macro version of the alloc-or-die variant outweights that.

Quoted 2 lines

This change also removes the overflow checks that are present in XDL_ALLOC_GROW()[...]

We end up calling st_mult(), which does that overflow check. Do you mean that the POC shimmy layer I showed in another reply for libgit2 doesn't have an st_mult() that detects overflows?

That's true, but as noted downthread of that we can & could ship that as part of the shimmy layer, but that's unrelated to this change.

In your pre-image you use LONG_MAX instead of UINTMAX_MAX & I don't see (but maybe I haven't looked at it carefully enough) how it does the same dying on overflows. Doesn't it just fall back to LONG_MAX?

Part of this is that it's not clear to me from your commit(s) why you need to rewrite alloc_nr() and rewrite (or drop?) st_mult().

Quoted 2 lines

and fails to free the old allocation when realloc() fails. It is not a like for like replacement.

Yes, we should have a free() there. Wel spotted. But again, doing that as part of the "gently" branch seems preferrable to have duplicate versions for expression (non-fatal) v.s. statement (fatal) variants.

Quoted 8 lines · Phillip Wood

Quoted 8 lines

But you've also changed every single callsite anyway.

So why not just change:

      if (XDL_ALLOC_GROW(recs, ...))

To:

Quoted 7 lines

Quoted 2 lines

      XDL_ALLOC_GROW(recs, ...);
      if (!recs)

Because I think it's ugly, we'd never define a function as void(int* result, args...) and I don't think we should do that for a macro where we can avoid it. The existing ALLOC_* macros make sense as statements because they die on failure.

Those macros are already unlike functions, though. They take a variable _name_, not a pointer to a variable, and assign to it. A version which looked like a function would have to be:

   if (XDL_ALLOC_GROW(&recs, ...))

So in my head I read them as assignment statements already, making the expression-like form a bit jarring.

Just my two cents. I don't care _too_ much either way, but I'd probably be swayed if one implementation is much simpler than the other.

Hi Ævar

Quoted 16 lines · Ævar Arnfjörð Bjarmason

Quoted 14 lines · Phillip Wood

Hi Ævar

Quoted 10 lines · Ævar Arnfjörð Bjarmason

Replace the recently introduced XDL_ALLOC_GROW() with invocations of the GALLOC_GROW() from git-shared-util.h.
As this change shows the macro + function indirection of XDL_ALLOC_GROW() is something we needed only because the two callsites we used it in wanted to use it as an expression, and we thus had to pass the "sizeof" down.
Let's just check the value afterwards instead, which allows us to use
the shared macro, we can also remove xdl_reallo(), this was its last user.

Quoted 6 lines

Quoted 2 lines

I don't think this expression->statement change is an improvement.

I think the use-as-statement is prettier too, but I think the uglyness
of having to pass down the sizeof() & re-implementing the macro version of the alloc-or-die variant outweights that.

I think this is partly a choice between prioritizing ease of implementation or ease of use for callers.

Quoted 6 lines

Quoted 2 lines

This change also removes the overflow checks that are present in XDL_ALLOC_GROW()[...]

We end up calling st_mult(), which does that overflow check. Do you mean
that the POC shimmy layer I showed in another reply for libgit2 doesn't have an st_mult() that detects overflows?

I was referring to

#define alloc_nr(x) (((x)+16)*3/2)

in cache.h. XDL_ALLOC_GROW() detects overflows when growing the number of items as well as when calculating the number of bytes to allocate.

Quoted 6 lines

That's true, but as noted downthread of that we can & could ship that as part of the shimmy layer, but that's unrelated to this change. In your pre-image you use LONG_MAX instead of UINTMAX_MAX & I don't see
(but maybe I haven't looked at it carefully enough) how it does the same dying on overflows. Doesn't it just fall back to LONG_MAX?

It does not die on overflow as we want to return errors rather than die in the xdiff code. It uses long to match the existing code.

Quoted 2 lines

Part of this is that it's not clear to me from your commit(s) why you need to rewrite alloc_nr() and rewrite (or drop?) st_mult().

So that we don't die on overflow and so that the xdiff code is self contained.

I'm a bit disappointed that this patch seems to have been written without really taking the time to understand exactly what the code it is replacing is doing.

Quoted 156 lines · Phillip Wood

Hi Ævar

Quoted 145 lines · Ævar Arnfjörð Bjarmason

Quoted 10 lines · Phillip Wood

Hi Ævar

Quoted 6 lines · Ævar Arnfjörð Bjarmason

Remove the xdl_free() wrapper macro in favor of using free() directly. The wrapper macro was brought in with the initial import of xdiff/ in 3443546f6ef (Use a *real* built-in diff generator, 2006-03-24).
As subsequent discussions on the topic[1] have made clear there's no reason to use this wrapper.

Quoted 4 lines

That link is to a message where you assert that there is no reason for the wrapper, you seem to be the only person in that thread making that argument. The libgit2 maintainer and others are arguing that it is worth keeping to make it easy to swap the allocator.

Arguing that it's not needed for a technical reason, but an "aesthetic
and ergonomic one", per:
https://lore.kernel.org/git/20220217225804.GC7@edef91d97c94/;
Perhaps I misread it, but I took this as Junio concurring with what I
was pointing out there:
https://lore.kernel.org/git/[email protected]/

Quoted 7 lines

Quoted 4 lines

Both git itself as well as any external
users such as libgit2 compile the xdiff/* code as part of their own compilation, and can thus find the right malloc() and free() at link-time.

I'm struggling to see how that is simpler than the current situation with xdl_malloc().

It's simpler because when maintaining that code in git.git it's less of
a special case, e.g. we have coccinelle rules that match free(), now every such rule needs to account for the xdiff special-case. And it's less buggy because if you're relying on us always using a wrapper bugs will creep in, current master has this:

	$ git -P grep '\bfree\(' -- xdiff
	xdiff/xdiff.h:#define xdl_free(ptr) free(ptr)
	xdiff/xmerge.c:         free(c);
	xdiff/xmerge.c: free(next_m);

Quoted 6 lines

Perhaps you could show how you think libgit2 could easily make xdiff use git__malloc() instead of malloc() without changing the malloc() calls (the message you linked to essentially suggests they do a search and replace). If people cannot swap in another allocator without changing the code then you are imposing a barrier to them contributing patches back to git's xdiff.

I was suggesting that if libgit2 wanted to maintain a copy of xdiff that
catered to the asthetic desires of the maintainer adjusting whatever import script you use to apply a trivial coccinelle transformation would give you what you wanted. Except without a maintenance burden on git.git, or the bugs you'd get now since you're not catching those two free() cases (or any future such cases).
But just having the code use malloc() and free() directly and getting
you what you get now is easy, and doesn't require any such search-replacement.
Here's how:
I imported the xdiff/*.[ch] files at the tip of my branch into current
libgit2.git's src/libgit2/xdiff/, and then applied this on top, which is partially re-applying libgit2's own monkeypatches, and partially adjusting for upstream changes (including this one):

	diff --git a/src/libgit2/xdiff/git-xdiff.h b/src/libgit2/xdiff/git-xdiff.h
	index b75dba819..2e00764d4 100644
	--- a/src/libgit2/xdiff/git-xdiff.h
	+++ b/src/libgit2/xdiff/git-xdiff.h
	@@ -14,6 +14,7 @@
	 #ifndef INCLUDE_git_xdiff_h__
	 #define INCLUDE_git_xdiff_h__
	
	+#include <regex.h>
	 #include "regexp.h"
	
	 /* Work around C90-conformance issues */
	@@ -27,11 +28,10 @@
	 # endif
	 #endif
	
	-#define xdl_malloc(x) git__malloc(x)
	-#define xdl_free(ptr) git__free(ptr)
	-#define xdl_realloc(ptr, x) git__realloc(ptr, x)
	+#define malloc(x) git__malloc(x)
	+#define free(ptr) git__free(ptr)
	
	-#define XDL_BUG(msg) GIT_ASSERT(msg)
	+#define BUG(msg) GIT_ASSERT(msg)
	
	 #define xdl_regex_t git_regexp
	 #define xdl_regmatch_t git_regmatch
	@@ -50,4 +50,17 @@ GIT_INLINE(int) xdl_regexec_buf(
	 	return -1;
	 }
	
	+static inline size_t st_mult(size_t a, size_t b)
	+{
	+	return a * b;
	+}
	+
	+static inline int regexec_buf(const regex_t *preg, const char *buf, size_t size,
	+			      size_t nmatch, regmatch_t pmatch[], int eflags)
	+{
	+	assert(nmatch > 0 && pmatch);
	+	pmatch[0].rm_so = 0;
	+	pmatch[0].rm_eo = size;
	+	return regexec(preg, buf, nmatch, pmatch, eflags | REG_STARTEND);
	+}
	 #endif
	diff --git a/src/libgit2/xdiff/xdiff.h b/src/libgit2/xdiff/xdiff.h
	index a37d89fcd..5e5b525c2 100644
	--- a/src/libgit2/xdiff/xdiff.h
	+++ b/src/libgit2/xdiff/xdiff.h
	@@ -23,6 +23,8 @@
	 #if !defined(XDIFF_H)
	 #define XDIFF_H
	
	+#include "git-xdiff.h"
	+
	 #ifdef __cplusplus
	 extern "C" {
	 #endif /* #ifdef __cplusplus */
	diff --git a/src/libgit2/xdiff/xinclude.h b/src/libgit2/xdiff/xinclude.h
	index a4285ac0e..79812ad8a 100644
	--- a/src/libgit2/xdiff/xinclude.h
	+++ b/src/libgit2/xdiff/xinclude.h
	@@ -23,7 +23,8 @@
	 #if !defined(XINCLUDE_H)
	 #define XINCLUDE_H
	
	-#include "git-compat-util.h"
	+#include "git-xdiff.h"
	+#include "git-shared-util.h"
	 #include "xmacros.h"
	 #include "xdiff.h"
	 #include "xtypes.h"

If you then build it and run e.g.:
gdb -args ./libgit2_tests -smerge::files
You'll get stack traces like this if you break on stdalloc__malloc (which it uses for me in its default configuration):

Quoted 7 lines

	(gdb) bt
	#0  stdalloc__malloc (len=144, file=0x87478d "/home/avar/g/libgit2/src/libgit2/xdiff/xutils.c", line=101) at /home/avar/g/libgit2/src/util/allocators/stdalloc.c:14
	#1  0x00000000006ec15c in xdl_cha_alloc (cha=0x7fffffffcaa8) at /home/avar/g/libgit2/src/libgit2/xdiff/xutils.c:101
	#2  0x00000000006eaee9 in xdl_prepare_ctx (pass=1, mf=0x7fffffffcc98, narec=13, xpp=0x7fffffffcca8, cf=0x7fffffffc7d0, xdf=0x7fffffffcaa8)
	    at /home/avar/g/libgit2/src/libgit2/xdiff/xprepare.c:194

IOW this was all seamlessly routed to your git__malloc() without us having to maintain an xdl_{malloc,free}().

Quoted 6 lines

Thanks for showing this, it is really helpful to see a concrete example. I was especially interested to see how you went about the conversion without redefining standard library functions or introducing non-namespaced identifiers in files that included xdiff.h. Unfortunately you have not done that and so I don't think the
approach above is viable for a well behaved library.