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).

Thanks to Junio and Ævar the feedback on V1 Changes since V1:

* Patch 2: new, it replaces xdl_malloc() followed by memset() with xdl_calloc() as suggested by Junio
* Patch 3: simplified by the new patch 2, the end result is unchanged
* Patch 4: added a note to the commit message explaining the choice to use long rather than size_t

Phillip Wood (4):
xdiff: introduce XDL_ALLOC_ARRAY()
xdiff: introduce xdl_calloc
xdiff: introduce XDL_CALLOC_ARRAY()
xdiff: introduce XDL_ALLOC_GROW()

 xdiff/xdiff.h      |  1 +
 xdiff/xdiffi.c     |  2 +-
 xdiff/xhistogram.c | 19 ++++++-------------
 xdiff/xmacros.h    | 18 ++++++++++++++++++
 xdiff/xpatience.c  |  9 +++------
 xdiff/xprepare.c   | 41 ++++++++++++-----------------------------
 xdiff/xutils.c     | 17 +++++++++++++++++
 xdiff/xutils.h     |  3 ++-
 8 files changed, 60 insertions(+), 50 deletions(-)

base-commit: e4a4b31577c7419497ac30cebe30d755b97752c5
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1272%2Fphillipwood%2Fwip%2Fxdiff-memory-allocation-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1272/phillipwood/wip/xdiff-memory-allocation-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1272

Range-diff vs v1:

 1:  55fd62dc27d = 1:  55fd62dc27d xdiff: introduce XDL_ALLOC_ARRAY()
 2:  8bead9856be ! 2:  ea8993a57ef xdiff: introduce XDL_CALLOC_ARRAY()
     @@ Metadata
      Author: Phillip Wood <[email protected]>
      
       ## Commit message ##
     -    xdiff: introduce XDL_CALLOC_ARRAY()
     +    xdiff: introduce xdl_calloc
      
     -    Add a helper for allocating an array and initialize the elements to
     -    zero. This is analogous to CALLOC_ARRAY() in the rest of the codebase
     -    but it returns NULL on allocation failures rather than dying to
     -    accommodate other users of libxdiff such as libgit2.
     +    In preparation for introducing XDL_CALLOC_ARRAY() use calloc() to
     +    obtain zeroed out memory rather than malloc() followed by memset(). To
     +    try and keep the lines a reasonable length this commit also stops
     +    casting the pointer returned by calloc() as this is unnecessary.
      
          Signed-off-by: Phillip Wood <[email protected]>
      
     + ## xdiff/xdiff.h ##
     +@@ xdiff/xdiff.h: typedef struct s_bdiffparam {
     + 
     + 
     + #define xdl_malloc(x) xmalloc(x)
     ++#define xdl_calloc(n, sz) xcalloc(n, sz)
     + #define xdl_free(ptr) free(ptr)
     + #define xdl_realloc(ptr,x) xrealloc(ptr,x)
     + 
     +
       ## xdiff/xhistogram.c ##
      @@ xdiff/xhistogram.c: static int find_lcs(xpparam_t const *xpp, xdfenv_t *env,
       		    int line1, int count1, int line2, int count2)
     @@ xdiff/xhistogram.c: static int find_lcs(xpparam_t const *xpp, xdfenv_t *env,
      -	sz *= sizeof(struct record *);
      -	if (!(index.records = (struct record **) xdl_malloc(sz)))
      +	index.records_size = 1 << index.table_bits;
     -+	if (!XDL_CALLOC_ARRAY(index.records, index.records_size))
     ++	if (!(index.records = xdl_calloc(index.records_size,
     ++					 sizeof(*index.records))))
       		goto cleanup;
      -	memset(index.records, 0, sz);
       
     @@ xdiff/xhistogram.c: static int find_lcs(xpparam_t const *xpp, xdfenv_t *env,
      -	sz *= sizeof(struct record *);
      -	if (!(index.line_map = (struct record **) xdl_malloc(sz)))
      +	index.line_map_size = count1;
     -+	if (!XDL_CALLOC_ARRAY(index.line_map, index.line_map_size))
     ++	if (!(index.line_map = xdl_calloc(index.line_map_size,
     ++					  sizeof(*index.line_map))))
       		goto cleanup;
      -	memset(index.line_map, 0, sz);
       
      -	sz = index.line_map_size;
      -	sz *= sizeof(unsigned int);
      -	if (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz)))
     -+	if (!XDL_CALLOC_ARRAY(index.next_ptrs, index.line_map_size))
     ++	if (!(index.next_ptrs = xdl_calloc(index.line_map_size,
     ++					   sizeof(*index.next_ptrs))))
       		goto cleanup;
      -	memset(index.next_ptrs, 0, sz);
       
       	/* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */
       	if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)
      
     - ## xdiff/xmacros.h ##
     -@@ xdiff/xmacros.h: 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)
     -+
     - #endif /* #if !defined(XMACROS_H) */
     -
       ## xdiff/xpatience.c ##
      @@ xdiff/xpatience.c: static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,
       
     @@ xdiff/xpatience.c: static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,
       	result->alloc = count1 * 2;
      -	result->entries = (struct entry *)
      -		xdl_malloc(result->alloc * sizeof(struct entry));
     --	if (!result->entries)
     -+	if (!XDL_CALLOC_ARRAY(result->entries, result->alloc))
     ++	result->entries = xdl_calloc(result->alloc, sizeof(*result->entries));
     + 	if (!result->entries)
       		return -1;
      -	memset(result->entries, 0, result->alloc * sizeof(struct entry));
       
     @@ xdiff/xprepare.c: static int xdl_init_classifier(xdlclassifier_t *cf, long size,
       		return -1;
       	}
      -	if (!(cf->rchash = (xdlclass_t **) xdl_malloc(cf->hsize * sizeof(xdlclass_t *)))) {
     -+	if (!XDL_CALLOC_ARRAY(cf->rchash, cf->hsize)) {
     ++	if (!(cf->rchash = xdl_calloc(cf->hsize, sizeof(*cf->rchash)))) {
       
       		xdl_cha_free(&cf->ncha);
       		return -1;
     @@ xdiff/xprepare.c: static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, lo
       	hbits = xdl_hashbits((unsigned int) narec);
       	hsize = 1 << hbits;
      -	if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
     -+	if (!XDL_CALLOC_ARRAY(rhash, hsize))
     ++	if (!(rhash = xdl_calloc(hsize, sizeof(*rhash))))
       		goto abort;
      -	memset(rhash, 0, hsize * sizeof(xrecord_t *));
       
     @@ xdiff/xprepare.c: static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, lo
       	}
       
      -	if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char))))
     -+	if (!XDL_CALLOC_ARRAY(rchg, nrec + 2))
     ++	if (!(rchg = xdl_calloc((nrec + 2), sizeof(*rchg))))
       		goto abort;
      -	memset(rchg, 0, (nrec + 2) * sizeof(char));
       
     @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
       	char *dis, *dis1, *dis2;
       
      -	if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {
     --
     -+	if (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2))
     ++	if (!(dis = xdl_calloc(xdf1->nrec + xdf2->nrec + 2, sizeof(*dis)))) {
     + 
       		return -1;
     --	}
     + 	}
      -	memset(dis, 0, xdf1->nrec + xdf2->nrec + 2);
       	dis1 = dis;
       	dis2 = dis1 + xdf1->nrec + 1;
 -:  ----------- > 3:  5490fd22579 xdiff: introduce XDL_CALLOC_ARRAY()
 3:  da996677f07 ! 4:  8c24cd7737b xdiff: introduce XDL_ALLOC_GROW()

@@ Commit message
of adding a small amount to the new allocation to avoid a lot of reallocations at small sizes.

+ Note that xdl_alloc_grow_helper() uses long rather than size_t for
+ nr and alloc to match the existing code.
+

## xdiff/xmacros.h ##
@@ xdiff/xmacros.h: do { \
- ? memset((p), 0, (nr) * sizeof(*(p))) \
- : NULL)
+ /* Allocate an array of nr zeroed out elements, returns NULL on failure */
+ #define XDL_CALLOC_ARRAY(p, nr) ((p) = xdl_calloc(nr, sizeof(*(p))))

+/*
+ * Ensure array p can accommodate at least nr elements, growing the

gitgitgadget