[v2,0/4] xdiff: introduce memory allocation macros

Message

Koji Nakamaru via GitGitGadget July 8, 2022, 4:25 p.m. UTC

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 <[e-mail]>
      
       ## 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 <[e-mail]>
      
     + ## 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.
     +
          Signed-off-by: Phillip Wood <[e-mail]>
      
       ## 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