From: Stefan Sperling <stsp@stsp.name>
Subject: Re: realloc_ids(): stop overallocating
To: Christian Weisgerber <naddy@mips.inka.de>
Cc: gameoftrees@openbsd.org
Date: Sun, 29 Aug 2021 14:38:43 +0200

On Sun, Aug 29, 2021 at 02:21:02PM +0200, Christian Weisgerber wrote:
> realloc_ids() harmlessly but confusingly allocates too much memory.
> 
> realloc_ids() grows the allocated array as needed.  To limit the
> number of reallocs, it grows the size by chunks.  The argument n
> is the highest index in use, so we need space for n + 1 elements.
> 
> Currently we provide space for n + chunksz elements, which means
> we consistently overallocate by one chunk if n % chunksz != 0.
> E.g. for n=1 we allocate a second chunk.
> 
> Fix (but see below):
> 
> ------------------------------------------------------------------------
> diff refs/heads/main refs/heads/n
> blob - cce652c329299014337427f1496d995ff9e59954
> blob + 7d91e606f8924a8938ecfbf7e7e3995898035325
> --- lib/send.c
> +++ lib/send.c
> @@ -320,7 +320,7 @@ realloc_ids(struct got_object_id ***ids, size_t *nallo
>  	struct got_object_id **new;
>  	const size_t alloc_chunksz = 256;
>  
> -	if (*nalloc >= n + alloc_chunksz)
> +	if (*nalloc >= n + 1)
>  		return NULL;
>  
>  	new = recallocarray(*ids, *nalloc, *nalloc + alloc_chunksz,
> ------------------------------------------------------------------------
> 
> However, I think it would be less confusing if realloc_ids() behaved
> like a malloc-style function and took the number of elements as
> argument instead of the highest index:

Agreed. I prefer your second patch, too.
Thanks!

> ------------------------------------------------------------------------
> diff refs/heads/main refs/heads/n+1
> blob - cce652c329299014337427f1496d995ff9e59954
> blob + 6c977a92f5e574ca78d050e9d534527d8b10d122
> --- lib/send.c
> +++ lib/send.c
> @@ -320,7 +320,7 @@ realloc_ids(struct got_object_id ***ids, size_t *nallo
>  	struct got_object_id **new;
>  	const size_t alloc_chunksz = 256;
>  
> -	if (*nalloc >= n + alloc_chunksz)
> +	if (*nalloc >= n)
>  		return NULL;
>  
>  	new = recallocarray(*ids, *nalloc, *nalloc + alloc_chunksz,
> @@ -596,7 +596,7 @@ got_send_pack(const char *remote_name, struct got_path
>  		 * Also prepare the array of our object IDs which
>  		 * will be needed for generating a pack file.
>  		 */
> -		err = realloc_ids(&our_ids, &nalloc_ours, nours);
> +		err = realloc_ids(&our_ids, &nalloc_ours, nours + 1);
>  		if (err)
>  			goto done;
>  		our_ids[nours] = id;
> @@ -676,7 +676,7 @@ got_send_pack(const char *remote_name, struct got_path
>  			have_their_id = 1;
>  		}
>  
> -		err = realloc_ids(&their_ids, &nalloc_theirs, ntheirs);
> +		err = realloc_ids(&their_ids, &nalloc_theirs, ntheirs + 1);
>  		if (err)
>  			goto done;
>  
> ------------------------------------------------------------------------
> 
> -- 
> Christian "naddy" Weisgerber                          naddy@mips.inka.de
> 
>