Merge pull request #5200 from pks-t/pks/memory-allocation-audit

Memory allocation audit

12 files changed, 197 insertions, 59 deletions

diff --git a/src/blame_git.c b/src/blame_git.c
index 06e7d648e..a9157c4ed 100644
--- a/src/blame_git.c
+++ b/src/blame_git.c
@@ -219,7 +219,7 @@ static void dup_entry(git_blame__entry *dst, git_blame__entry *src)
  * split_overlap() divided an existing blame e into up to three parts in split.
  * Adjust the linked list of blames in the scoreboard to reflect the split.
  */
-static void split_blame(git_blame *blame, git_blame__entry *split, git_blame__entry *e)
+static int split_blame(git_blame *blame, git_blame__entry *split, git_blame__entry *e)
 {
 	git_blame__entry *new_entry;
 
@@ -229,11 +229,13 @@ static void split_blame(git_blame *blame, git_blame__entry *split, git_blame__en
 
 		/* The last part -- me */
 		new_entry = git__malloc(sizeof(*new_entry));
+		GIT_ERROR_CHECK_ALLOC(new_entry);
 		memcpy(new_entry, &(split[2]), sizeof(git_blame__entry));
 		add_blame_entry(blame, new_entry);
 
 		/* ... and the middle part -- parent */
 		new_entry = git__malloc(sizeof(*new_entry));
+		GIT_ERROR_CHECK_ALLOC(new_entry);
 		memcpy(new_entry, &(split[1]), sizeof(git_blame__entry));
 		add_blame_entry(blame, new_entry);
 	} else if (!split[0].suspect && !split[2].suspect) {
@@ -246,15 +248,19 @@ static void split_blame(git_blame *blame, git_blame__entry *split, git_blame__en
 		/* me and then parent */
 		dup_entry(e, &split[0]);
 		new_entry = git__malloc(sizeof(*new_entry));
+		GIT_ERROR_CHECK_ALLOC(new_entry);
 		memcpy(new_entry, &(split[1]), sizeof(git_blame__entry));
 		add_blame_entry(blame, new_entry);
 	} else {
 		/* parent and then me */
 		dup_entry(e, &split[1]);
 		new_entry = git__malloc(sizeof(*new_entry));
+		GIT_ERROR_CHECK_ALLOC(new_entry);
 		memcpy(new_entry, &(split[2]), sizeof(git_blame__entry));
 		add_blame_entry(blame, new_entry);
 	}
+
+	return 0;
 }
 
 /*
@@ -272,7 +278,7 @@ static void decref_split(git_blame__entry *split)
  * Helper for blame_chunk(). blame_entry e is known to overlap with the patch
  * hunk; split it and pass blame to the parent.
  */
-static void blame_overlap(
+static int blame_overlap(
 		git_blame *blame,
 		git_blame__entry *e,
 		size_t tlno,
@@ -284,8 +290,11 @@ static void blame_overlap(
 
 	split_overlap(split, e, tlno, plno, same, parent);
 	if (split[1].suspect)
-		split_blame(blame, split, e);
+		if (split_blame(blame, split, e) < 0)
+			return -1;
 	decref_split(split);
+
+	return 0;
 }
 
 /*
@@ -293,7 +302,7 @@ static void blame_overlap(
  * e and its parent. Find and split the overlap, and pass blame to the
  * overlapping part to the parent.
  */
-static void blame_chunk(
+static int blame_chunk(
 		git_blame *blame,
 		size_t tlno,
 		size_t plno,
@@ -309,9 +318,12 @@ static void blame_chunk(
 		if (same <= e->s_lno)
 			continue;
 		if (tlno < e->s_lno + e->num_lines) {
-			blame_overlap(blame, e, tlno, plno, same, parent);
+			if (blame_overlap(blame, e, tlno, plno, same, parent) < 0)
+				return -1;
 		}
 	}
+
+	return 0;
 }
 
 static int my_emit(
@@ -321,7 +333,8 @@ static int my_emit(
 {
 	blame_chunk_cb_data *d = (blame_chunk_cb_data *)cb_data;
 
-	blame_chunk(d->blame, d->tlno, d->plno, start_b, d->target, d->parent);
+	if (blame_chunk(d->blame, d->tlno, d->plno, start_b, d->target, d->parent) < 0)
+		return -1;
 	d->plno = start_a + count_a;
 	d->tlno = start_b + count_b;
 
@@ -400,7 +413,8 @@ static int pass_blame_to_parent(
 		return -1;
 
 	/* The reset (i.e. anything after tlno) are the same as the parent */
-	blame_chunk(blame, d.tlno, d.plno, last_in_target, target, parent);
+	if (blame_chunk(blame, d.tlno, d.plno, last_in_target, target, parent) < 0)
+		return -1;
 
 	return 0;
 }
diff --git a/src/indexer.c b/src/indexer.c
index e7b3483fb..84b950d13 100644
--- a/src/indexer.c
+++ b/src/indexer.c
@@ -326,6 +326,7 @@ static int add_expected_oid(git_indexer *idx, const git_oid *oid)
 	    !git_oidmap_exists(idx->pack->idx_cache, oid) &&
 	    !git_oidmap_exists(idx->expected_oids, oid)) {
 		    git_oid *dup = git__malloc(sizeof(*oid));
+		    GIT_ERROR_CHECK_ALLOC(dup);
 		    git_oid_cpy(dup, oid);
 		    return git_oidmap_set(idx->expected_oids, dup, dup);
 	}
diff --git a/src/merge.c b/src/merge.c
index c1f1cc46a..657b0181b 100644
--- a/src/merge.c
+++ b/src/merge.c
@@ -310,46 +310,55 @@ static int interesting(git_pqueue *list)
 	return 0;
 }
 
-static void clear_commit_marks_1(git_commit_list **plist,
+static int clear_commit_marks_1(git_commit_list **plist,
 		git_commit_list_node *commit, unsigned int mark)
 {
 	while (commit) {
 		unsigned int i;
 
 		if (!(mark & commit->flags))
-			return;
+			return 0;
 
 		commit->flags &= ~mark;
 
 		for (i = 1; i < commit->out_degree; i++) {
 			git_commit_list_node *p = commit->parents[i];
-			git_commit_list_insert(p, plist);
+			if (git_commit_list_insert(p, plist) == NULL)
+				return -1;
 		}
 
 		commit = commit->out_degree ? commit->parents[0] : NULL;
 	}
+
+	return 0;
 }
 
-static void clear_commit_marks_many(git_vector *commits, unsigned int mark)
+static int clear_commit_marks_many(git_vector *commits, unsigned int mark)
 {
 	git_commit_list *list = NULL;
 	git_commit_list_node *c;
 	unsigned int i;
 
 	git_vector_foreach(commits, i, c) {
-		git_commit_list_insert(c, &list);
+		if (git_commit_list_insert(c, &list) == NULL)
+			return -1;
 	}
 
 	while (list)
-		clear_commit_marks_1(&list, git_commit_list_pop(&list), mark);
+		if (clear_commit_marks_1(&list, git_commit_list_pop(&list), mark) < 0)
+			return -1;
+	return 0;
 }
 
-static void clear_commit_marks(git_commit_list_node *commit, unsigned int mark)
+static int clear_commit_marks(git_commit_list_node *commit, unsigned int mark)
 {
 	git_commit_list *list = NULL;
-	git_commit_list_insert(commit, &list);
+	if (git_commit_list_insert(commit, &list) == NULL)
+		return -1;
 	while (list)
-		clear_commit_marks_1(&list, git_commit_list_pop(&list), mark);
+		if (clear_commit_marks_1(&list, git_commit_list_pop(&list), mark) < 0)
+			return -1;
+	return 0;
 }
 
 static int paint_down_to_common(
@@ -466,10 +475,11 @@ static int remove_redundant(git_revwalk *walk, git_vector *commits)
 				redundant[filled_index[j]] = 1;
 		}
 
-		clear_commit_marks(commit, ALL_FLAGS);
-		clear_commit_marks_many(&work, ALL_FLAGS);
-
 		git_commit_list_free(&common);
+
+		if ((error = clear_commit_marks(commit, ALL_FLAGS)) < 0 ||
+		    (error = clear_commit_marks_many(&work, ALL_FLAGS)) < 0)
+				goto done;
 	}
 
 	for (i = 0; i < commits->length; ++i) {
@@ -531,10 +541,9 @@ int git_merge__bases_many(git_commit_list **out, git_revwalk *walk, git_commit_l
 		while (result)
 			git_vector_insert(&redundant, git_commit_list_pop(&result));
 
-		clear_commit_marks(one, ALL_FLAGS);
-		clear_commit_marks_many(twos, ALL_FLAGS);
-
-		if ((error = remove_redundant(walk, &redundant)) < 0) {
+		if ((error = clear_commit_marks(one, ALL_FLAGS)) < 0 ||
+		    (error = clear_commit_marks_many(twos, ALL_FLAGS)) < 0 ||
+		    (error = remove_redundant(walk, &redundant)) < 0) {
 			git_vector_free(&redundant);
 			return error;
 		}
diff --git a/src/posix.c b/src/posix.c
index bffe02e05..1ea2ce54b 100644
--- a/src/posix.c
+++ b/src/posix.c
@@ -28,11 +28,11 @@ int p_getaddrinfo(
 
 	GIT_UNUSED(hints);
 
-	if ((ainfo = malloc(sizeof(struct addrinfo))) == NULL)
+	if ((ainfo = git__malloc(sizeof(struct addrinfo))) == NULL)
 		return -1;
 
 	if ((ainfo->ai_hostent = gethostbyname(host)) == NULL) {
-		free(ainfo);
+		git__free(ainfo);
 		return -2;
 	}
 
@@ -65,7 +65,7 @@ int p_getaddrinfo(
 	ai = ainfo;
 
 	for (p = 1; ainfo->ai_hostent->h_addr_list[p] != NULL; p++) {
-		if (!(ai->ai_next = malloc(sizeof(struct addrinfo)))) {
+		if (!(ai->ai_next = git__malloc(sizeof(struct addrinfo)))) {
 			p_freeaddrinfo(ainfo);
 			return -1;
 		}
@@ -89,7 +89,7 @@ void p_freeaddrinfo(struct addrinfo *info)
 
 	while(p != NULL) {
 		next = p->ai_next;
-		free(p);
+		git__free(p);
 		p = next;
 	}
 }
@@ -247,7 +247,7 @@ int p_mmap(git_map *out, size_t len, int prot, int flags, int fd, git_off_t offs
 		return -1;
 	}
 
-	out->data = malloc(len);
+	out->data = git__malloc(len);
 	GIT_ERROR_CHECK_ALLOC(out->data);
 
 	if (!git__is_ssizet(len) ||
@@ -264,7 +264,7 @@ int p_mmap(git_map *out, size_t len, int prot, int flags, int fd, git_off_t offs
 int p_munmap(git_map *map)
 {
 	assert(map != NULL);
-	free(map->data);
+	git__free(map->data);
 
 	return 0;
 }
diff --git a/src/trailer.c b/src/trailer.c
index f837c9754..ca81fd020 100644
--- a/src/trailer.c
+++ b/src/trailer.c
@@ -267,6 +267,9 @@ static char *extract_trailer_block(const char *message, size_t* len)
 	size_t trailer_len = trailer_end - trailer_start;
 
 	char *buffer = git__malloc(trailer_len + 1);
+	if (buffer == NULL)
+		return NULL;
+
 	memcpy(buffer, message + trailer_start, trailer_len);
 	buffer[trailer_len] = 0;
 
@@ -302,6 +305,8 @@ int git_message_trailers(git_message_trailer_array *trailer_arr, const char *mes
 
 	size_t trailer_len;
 	char *trailer = extract_trailer_block(message, &trailer_len);
+	if (trailer == NULL)
+		return -1;
 
 	for (ptr = trailer;;) {
 		switch (state) {
diff --git a/src/transports/http.c b/src/transports/http.c
index d727851b7..a55aec5d0 100644
--- a/src/transports/http.c
+++ b/src/transports/http.c
@@ -1337,8 +1337,10 @@ static int http_stream_write_chunked(
 		/* Append as much to the buffer as we can */
 		int count = min(CHUNK_SIZE - s->chunk_buffer_len, len);
 
-		if (!s->chunk_buffer)
+		if (!s->chunk_buffer) {
 			s->chunk_buffer = git__malloc(CHUNK_SIZE);
+			GIT_ERROR_CHECK_ALLOC(s->chunk_buffer);
+		}
 
 		memcpy(s->chunk_buffer + s->chunk_buffer_len, buffer, count);
 		s->chunk_buffer_len += count;
diff --git a/src/transports/winhttp.c b/src/transports/winhttp.c
index 7fc6b7059..3cab5d700 100644
--- a/src/transports/winhttp.c
+++ b/src/transports/winhttp.c
@@ -1011,6 +1011,7 @@ replay:
 			}
 
 			buffer = git__malloc(CACHED_POST_BODY_BUF_SIZE);
+			GIT_ERROR_CHECK_ALLOC(buffer);
 
 			while (len > 0) {
 				DWORD bytes_written;
@@ -1392,8 +1393,10 @@ static int winhttp_stream_write_chunked(
 		/* Append as much to the buffer as we can */
 		int count = (int)min(CACHED_POST_BODY_BUF_SIZE - s->chunk_buffer_len, len);
 
-		if (!s->chunk_buffer)
+		if (!s->chunk_buffer) {
 			s->chunk_buffer = git__malloc(CACHED_POST_BODY_BUF_SIZE);
+			GIT_ERROR_CHECK_ALLOC(s->chunk_buffer);
+		}
 
 		memcpy(s->chunk_buffer + s->chunk_buffer_len, buffer, count);
 		s->chunk_buffer_len += count;
diff --git a/src/util.c b/src/util.c
index 316a28973..fdd8e9afa 100644
--- a/src/util.c
+++ b/src/util.c
@@ -719,6 +719,32 @@ static int GIT_STDLIB_CALL git__qsort_r_glue_cmp(
 }
 #endif
 
+static void swap(uint8_t *a, uint8_t *b, size_t elsize)
+{
+	char tmp[256];
+
+	while (elsize) {
+		size_t n = elsize < sizeof(tmp) ? elsize : sizeof(tmp);
+		memcpy(tmp, a + elsize - n, n);
+		memcpy(a + elsize - n, b + elsize - n, n);
+		memcpy(b + elsize - n, tmp, n);
+		elsize -= n;
+	}
+}
+
+static void insertsort(
+	void *els, size_t nel, size_t elsize,
+	git__sort_r_cmp cmp, void *payload)
+{
+	uint8_t *base = els;
+	uint8_t *end = base + nel * elsize;
+	uint8_t *i, *j;
+
+	for (i = base + elsize; i < end; i += elsize)
+		for (j = i; j > base && cmp(j, j - elsize, payload) < 0; j -= elsize)
+			swap(j, j - elsize, elsize);
+}
+
 void git__qsort_r(
 	void *els, size_t nel, size_t elsize, git__sort_r_cmp cmp, void *payload)
 {
@@ -731,33 +757,10 @@ void git__qsort_r(
 	git__qsort_r_glue glue = { cmp, payload };
 	qsort_s(els, nel, elsize, git__qsort_r_glue_cmp, &glue);
 #else
-	git__insertsort_r(els, nel, elsize, NULL, cmp, payload);
+	insertsort(els, nel, elsize, cmp, payload);
 #endif
 }
 
-void git__insertsort_r(
-	void *els, size_t nel, size_t elsize, void *swapel,
-	git__sort_r_cmp cmp, void *payload)
-{
-	uint8_t *base = els;
-	uint8_t *end = base + nel * elsize;
-	uint8_t *i, *j;
-	bool freeswap = !swapel;
-
-	if (freeswap)
-		swapel = git__malloc(elsize);
-
-	for (i = base + elsize; i < end; i += elsize)
-		for (j = i; j > base && cmp(j, j - elsize, payload) < 0; j -= elsize) {
-			memcpy(swapel, j, elsize);
-			memcpy(j, j - elsize, elsize);
-			memcpy(j - elsize, swapel, elsize);
-		}
-
-	if (freeswap)
-		git__free(swapel);
-}
-
 /*
  * git__utf8_iterate is taken from the utf8proc project,
  * http://www.public-software-group.org/utf8proc
diff --git a/src/util.h b/src/util.h
index b9ab65273..792eba003 100644
--- a/src/util.h
+++ b/src/util.h
@@ -137,10 +137,6 @@ extern void git__tsort_r(
 extern void git__qsort_r(
 	void *els, size_t nel, size_t elsize, git__sort_r_cmp cmp, void *payload);
 
-extern void git__insertsort_r(
-	void *els, size_t nel, size_t elsize, void *swapel,
-	git__sort_r_cmp cmp, void *payload);
-
 /**
  * @param position If non-NULL, this will be set to the position where the
  * 		element is or would be inserted if not found.
diff --git a/src/xdiff/xmerge.c b/src/xdiff/xmerge.c
index e6eaf24b5..278cbe124 100644
--- a/src/xdiff/xmerge.c
+++ b/src/xdiff/xmerge.c
@@ -717,10 +717,22 @@ int xdl_merge(mmfile_t *orig, mmfile_t *mf1, mmfile_t *mf2,
 	status = 0;
 	if (!xscr1) {
 		result->ptr = xdl_malloc(mf2->size);
+		if (!result->ptr) {
+			xdl_free_script(xscr2);
+			xdl_free_env(&xe1);
+			xdl_free_env(&xe2);
+			return -1;
+		}
 		memcpy(result->ptr, mf2->ptr, mf2->size);
 		result->size = mf2->size;
 	} else if (!xscr2) {
 		result->ptr = xdl_malloc(mf1->size);
+		if (!result->ptr) {
+			xdl_free_script(xscr1);
+			xdl_free_env(&xe1);
+			xdl_free_env(&xe2);
+			return -1;
+		}
 		memcpy(result->ptr, mf1->ptr, mf1->size);
 		result->size = mf1->size;
 	} else {
diff --git a/src/xdiff/xpatience.c b/src/xdiff/xpatience.c
index cedf39cc3..53b7d5fd1 100644
--- a/src/xdiff/xpatience.c
+++ b/src/xdiff/xpatience.c
@@ -217,6 +217,9 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)
 	 */
 	int anchor_i = -1;
 
+	if (!sequence)
+		return NULL;
+
 	for (entry = map->first; entry; entry = entry->next) {
 		if (!entry->line2 || entry->line2 == NON_UNIQUE)
 			continue;
diff --git a/tests/core/qsort.c b/tests/core/qsort.c
new file mode 100644
index 000000000..efb79e6e9
--- /dev/null
+++ b/tests/core/qsort.c
@@ -0,0 +1,90 @@
+#include "clar_libgit2.h"
+
+#define assert_sorted(a, cmp) \
+	_assert_sorted(a, ARRAY_SIZE(a), sizeof(*a), cmp)
+
+struct big_entries {
+	char c[311];
+};
+
+static void _assert_sorted(void *els, size_t n, size_t elsize, git__sort_r_cmp cmp)
+{
+	int8_t *p = els;
+
+	git__qsort_r(p, n, elsize, cmp, NULL);
+	while (n-- > 1) {
+		cl_assert(cmp(p, p + elsize, NULL) <= 0);
+		p += elsize;
+	}
+}
+
+static int cmp_big(const void *_a, const void *_b, void *payload)
+{
+	const struct big_entries *a = (const struct big_entries *)_a, *b = (const struct big_entries *)_b;
+	GIT_UNUSED(payload);
+	return (a->c[0] < b->c[0]) ? -1 : (a->c[0] > b->c[0]) ? +1 : 0;
+}
+
+static int cmp_int(const void *_a, const void *_b, void *payload)
+{
+	int a = *(const int *)_a, b = *(const int *)_b;
+	GIT_UNUSED(payload);
+	return (a < b) ? -1 : (a > b) ? +1 : 0;
+}
+
+static int cmp_str(const void *_a, const void *_b, void *payload)
+{
+	GIT_UNUSED(payload);
+	return strcmp((const char *) _a, (const char *) _b);
+}
+
+void test_core_qsort__array_with_single_entry(void)
+{
+	int a[] = { 10 };
+	assert_sorted(a, cmp_int);
+}
+
+void test_core_qsort__array_with_equal_entries(void)
+{
+	int a[] = { 4, 4, 4, 4 };
+	assert_sorted(a, cmp_int);
+}
+
+void test_core_qsort__sorted_array(void)
+{
+	int a[] = { 1, 10 };
+	assert_sorted(a, cmp_int);
+}
+
+void test_core_qsort__unsorted_array(void)
+{
+	int a[] = { 123, 9, 412938, 10, 234, 89 };
+	assert_sorted(a, cmp_int);
+}
+
+void test_core_qsort__sorting_strings(void)
+{
+	char *a[] = { "foo", "bar", "baz" };
+	assert_sorted(a, cmp_str);
+}
+
+void test_core_qsort__sorting_big_entries(void)
+{
+	struct big_entries a[5];
+
+	memset(&a, 0, sizeof(a));
+
+	memset(a[0].c, 'w', sizeof(a[0].c) - 1);
+	memset(a[1].c, 'c', sizeof(a[1].c) - 1);
+	memset(a[2].c, 'w', sizeof(a[2].c) - 1);
+	memset(a[3].c, 'h', sizeof(a[3].c) - 1);
+	memset(a[4].c, 'a', sizeof(a[4].c) - 1);
+
+	assert_sorted(a, cmp_big);
+
+	cl_assert_equal_i(strspn(a[0].c, "a"), sizeof(a[0].c) - 1);
+	cl_assert_equal_i(strspn(a[1].c, "c"), sizeof(a[1].c) - 1);
+	cl_assert_equal_i(strspn(a[2].c, "h"), sizeof(a[2].c) - 1);
+	cl_assert_equal_i(strspn(a[3].c, "w"), sizeof(a[3].c) - 1);
+	cl_assert_equal_i(strspn(a[4].c, "w"), sizeof(a[4].c) - 1);
+}