From: Christian Weisgerber <naddy@mips.inka.de>
Subject: realloc_ids(): stop overallocating
To: gameoftrees@openbsd.org
Date: Sun, 29 Aug 2021 14:21:02 +0200

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:

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