[PATCH] git-fast-import possible memory corruption problem

[PATCH] git-fast-import possible memory corruption problem

[YONETANI Tomokazu]

[-- Attachment #1: Type: text/plain, Size: 919 bytes --]

Hello.
While trying to convert NetBSD CVS repository to Git, I've been
experiencing 100% reproducible crash of git-fast-import.  After
poking here and there and I noticed a dubious code fragment in
pool_alloc():
	:

        r = p->next_free;
        /* round out to a 'uintmax_t' alignment */
        if (len & (sizeof(uintmax_t) - 1))
                len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
        p->next_free += len;
        return r;

As the `round out' takes place AFTER it found the room in the mem_pool,
there's a small chance of p->next_free being set outside of the chosen
area, up to (sizeof(uintmax_t) - 1) bytes.  pool_strdup() is one of the
functions which can trigger the problem, when pool_alloc() finds a room
at the end of a pool entry and the requested length is not multiple of
size(uintmax_t).  I believe attached patch addresses this problem.

Best regards,
YONETANI Tomokazu.

[-- Attachment #2: git-fast-import.patch --]
[-- Type: text/plain, Size: 1489 bytes --]

diff --git a/fast-import.c b/fast-import.c
index 3c035a5..fb4367a 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -549,11 +549,15 @@ static unsigned int hc_str(const char *s, size_t len)
 	return r;
 }
 
-static void *pool_alloc(size_t len)
+static void *_pool_alloc(size_t len, int zero)
 {
 	struct mem_pool *p;
 	void *r;
 
+	/* round out to a 'uintmax_t' alignment */
+	if (len & (sizeof(uintmax_t) - 1))
+		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
+
 	for (p = mem_pool; p; p = p->next_pool)
 		if ((p->end - p->next_free >= len))
 			break;
@@ -561,7 +565,8 @@ static void *pool_alloc(size_t len)
 	if (!p) {
 		if (len >= (mem_pool_alloc/2)) {
 			total_allocd += len;
-			return xmalloc(len);
+			r = xmalloc(len);
+			goto out;
 		}
 		total_allocd += sizeof(struct mem_pool) + mem_pool_alloc;
 		p = xmalloc(sizeof(struct mem_pool) + mem_pool_alloc);
@@ -572,19 +577,22 @@ static void *pool_alloc(size_t len)
 	}
 
 	r = p->next_free;
-	/* round out to a 'uintmax_t' alignment */
-	if (len & (sizeof(uintmax_t) - 1))
-		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
 	p->next_free += len;
+out:
+	if (zero)
+		memset(r, 0, len);
 	return r;
 }
 
+static void *pool_alloc(size_t len)
+{
+	return _pool_alloc(len, 0);
+}
+
 static void *pool_calloc(size_t count, size_t size)
 {
 	size_t len = count * size;
-	void *r = pool_alloc(len);
-	memset(r, 0, len);
-	return r;
+	return _pool_alloc(len, 1);
 }
 
 static char *pool_strdup(const char *s)

Re: [PATCH] git-fast-import possible memory corruption problem

[Junio C Hamano]

YONETANI Tomokazu <qhwt+git@les.ath.cx> writes:

> While trying to convert NetBSD CVS repository to Git, I've been
> experiencing 100% reproducible crash of git-fast-import.  After
> poking here and there and I noticed a dubious code fragment in
> pool_alloc():
> 	:
>
>         r = p->next_free;
>         /* round out to a 'uintmax_t' alignment */
>         if (len & (sizeof(uintmax_t) - 1))
>                 len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
>         p->next_free += len;
>         return r;
>
> As the `round out' takes place AFTER it found the room in the mem_pool,
> there's a small chance of p->next_free being set outside of the chosen
> area, up to (sizeof(uintmax_t) - 1) bytes.  pool_strdup() is one of the
> functions which can trigger the problem, when pool_alloc() finds a room
> at the end of a pool entry and the requested length is not multiple of
> size(uintmax_t).  I believe attached patch addresses this problem.

Thanks -- do you mean your reproducible crash does not reproduce with the
patch anymore?

I think your change to move the "round up" logic up in the codepath makes
perfect sense.  But your patch seems to conflate totally unrelated change
to move memzero from the caller to callee into it, and I do not see the
reason why it should be that way.  If the caller asked 10 bytes to calloc
from the pool, and the underlying pool allocator gives you a 16-byte
block, you only have to guarantee that the first 10 bytes are cleared, and
can leave the trailing padding 6 bytes at the end untouched.

Re: [PATCH] git-fast-import possible memory corruption problem

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

>> As the `round out' takes place AFTER it found the room in the mem_pool,
>> there's a small chance of p->next_free being set outside of the chosen
>> area, up to (sizeof(uintmax_t) - 1) bytes.  pool_strdup() is one of the
>> functions which can trigger the problem, when pool_alloc() finds a room
>> at the end of a pool entry and the requested length is not multiple of
>> size(uintmax_t).  I believe attached patch addresses this problem.
>
> Thanks -- do you mean your reproducible crash does not reproduce with the
> patch anymore?
>
> I think your change to move the "round up" logic up in the codepath makes
> perfect sense.  But your patch seems to conflate totally unrelated change
> to move memzero from the caller to callee into it, and I do not see the
> reason why it should be that way.  If the caller asked 10 bytes to calloc
> from the pool, and the underlying pool allocator gives you a 16-byte
> block, you only have to guarantee that the first 10 bytes are cleared, and
> can leave the trailing padding 6 bytes at the end untouched.

That is, something like this...

 fast-import.c |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)

diff --git c/fast-import.c w/fast-import.c
index 3c035a5..3276d5d 100644
--- c/fast-import.c
+++ w/fast-import.c
@@ -554,6 +554,10 @@ static void *pool_alloc(size_t len)
 	struct mem_pool *p;
 	void *r;
 
+	/* round up to a 'uintmax_t' alignment */
+	if (len & (sizeof(uintmax_t) - 1))
+		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
+
 	for (p = mem_pool; p; p = p->next_pool)
 		if ((p->end - p->next_free >= len))
 			break;
@@ -572,9 +576,6 @@ static void *pool_alloc(size_t len)
 	}
 
 	r = p->next_free;
-	/* round out to a 'uintmax_t' alignment */
-	if (len & (sizeof(uintmax_t) - 1))
-		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));
 	p->next_free += len;
 	return r;
 }

Re: [PATCH] git-fast-import possible memory corruption problem

[YONETANI Tomokazu]

On Sat, Dec 13, 2008 at 09:53:55PM -0800, Junio C Hamano wrote:
> Junio C Hamano <gitster@pobox.com> writes:
> 
> >> As the `round out' takes place AFTER it found the room in the mem_pool,
> >> there's a small chance of p->next_free being set outside of the chosen
> >> area, up to (sizeof(uintmax_t) - 1) bytes.  pool_strdup() is one of the
> >> functions which can trigger the problem, when pool_alloc() finds a room
> >> at the end of a pool entry and the requested length is not multiple of
> >> size(uintmax_t).  I believe attached patch addresses this problem.
> >
> > Thanks -- do you mean your reproducible crash does not reproduce with the
> > patch anymore?
> >
> > I think your change to move the "round up" logic up in the codepath makes
> > perfect sense.  But your patch seems to conflate totally unrelated change
> > to move memzero from the caller to callee into it, and I do not see the
> > reason why it should be that way.  If the caller asked 10 bytes to calloc
> > from the pool, and the underlying pool allocator gives you a 16-byte
> > block, you only have to guarantee that the first 10 bytes are cleared, and
> > can leave the trailing padding 6 bytes at the end untouched.
> 
> That is, something like this...
> 
>  fast-import.c |    7 ++++---
>  1 files changed, 4 insertions(+), 3 deletions(-)
> 
> diff --git c/fast-import.c w/fast-import.c
> index 3c035a5..3276d5d 100644
[snip]
Yes, that was what it originally looked like, but after fixing the crash
I encountered another problem, and thought that I had to clear rounded up
area too.  It turned out that the second problem has nothing to do with
[the pool allocator, but the data fed to git-fast-import.  After fixing
the data, the git-fast-import with above patch finished successfully,
no more crashes.