[PATCH] Set hard limit on delta chain depth

Too deep delta chains can cause stack overflow in get_base_data(). Set
a hard limit so that index-pack does not run out of stack. Also stop
people from producing such a long delta chains using "pack-object
--depth=<too large>"

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 I used to make very long delta chains and triggered this in index-pack.
 I did not care reporting because it's my fault anyway. Think again,
 index-pack is called at server side and a malicious client can
 trigger this. This patch does not improve the situation much, but at
 least we won't get sigsegv at server side.

 builtin/index-pack.c   |   12 ++++++++++--
 builtin/pack-objects.c |    3 +++
 pack.h                 |    2 ++
 3 files changed, 15 insertions(+), 2 deletions(-)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 0945adb..cfb8cb2 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c

@@ -504,13 +504,16 @@ static int is_delta_type(enum object_type type)
 	return (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA);
 }
 
-static void *get_base_data(struct base_data *c)
+static void *get_base_data_1(struct base_data *c, int depth)
 {
+	if (depth > MAX_DELTA_DEPTH)
+		die("index-pack: too long delta chain");
+
 	if (!c->data) {
 		struct object_entry *obj = c->obj;
 
 		if (is_delta_type(obj->type)) {
-			void *base = get_base_data(c->base);
+			void *base = get_base_data_1(c->base, depth + 1);
 			void *raw = get_data_from_pack(obj);
 			c->data = patch_delta(
 				base, c->base->size,

@@ -530,6 +533,11 @@ static void *get_base_data(struct base_data *c)
 	return c->data;
 }
 
+static void *get_base_data(struct base_data *c)
+{
+	return get_base_data_1(c, 0);
+}
+
 static void resolve_delta(struct object_entry *delta_obj,
 			  struct base_data *base, struct base_data *result)
 {

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 824ecee..85ee04b 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c

@@ -2508,6 +2508,9 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 	if (keep_unreachable && unpack_unreachable)
 		die("--keep-unreachable and --unpack-unreachable are incompatible.");
 
+	if (depth > MAX_DELTA_DEPTH)
+		die("--depth exceeds %d", MAX_DELTA_DEPTH);
+
 	if (progress && all_progress_implied)
 		progress = 2;
 

diff --git a/pack.h b/pack.h
index 722a54e..b8f60c3 100644
--- a/pack.h
+++ b/pack.h

@@ -3,6 +3,8 @@
 
 #include "object.h"
 
+#define MAX_DELTA_DEPTH 128
+
 /*
  * Packed object header
  */

-- 
1.7.8.36.g69ee2

2011/12/5 Nguyễn Thái Ngọc Duy [off-list ref]:

Too deep delta chains can cause stack overflow in get_base_data(). Set
a hard limit so that index-pack does not run out of stack. Also stop
people from producing such a long delta chains using "pack-object
--depth=<too large>"

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 I used to make very long delta chains and triggered this in index-pack.
 I did not care reporting because it's my fault anyway. Think again,
 index-pack is called at server side and a malicious client can
 trigger this. This patch does not improve the situation much, but at
 least we won't get sigsegv at server side.

Wouldn't it make more sense to make the limit a config option rather
than a hard-coded value of 128 (which seems arbitrary to me)? After
all, different platforms have different stack-limitations...

2011/12/6 Erik Faye-Lund [off-list ref]:

2011/12/5 Nguyễn Thái Ngọc Duy [off-list ref]:

quoted

Too deep delta chains can cause stack overflow in get_base_data(). Set
a hard limit so that index-pack does not run out of stack. Also stop
people from producing such a long delta chains using "pack-object
--depth=<too large>"

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 I used to make very long delta chains and triggered this in index-pack.
 I did not care reporting because it's my fault anyway. Think again,
 index-pack is called at server side and a malicious client can
 trigger this. This patch does not improve the situation much, but at
 least we won't get sigsegv at server side.

Wouldn't it make more sense to make the limit a config option rather
than a hard-coded value of 128 (which seems arbitrary to me)? After
all, different platforms have different stack-limitations...

Then it'd make more sense to make a compile time config based on
platform. We could have a config option that can override the default,
but I really don't see the point of making long delta chains.
-- 
Duy

On Tue, Dec 6, 2011 at 1:32 PM, Nguyen Thai Ngoc Duy [off-list ref] wrote:

2011/12/6 Erik Faye-Lund [off-list ref]:

quoted

2011/12/5 Nguyễn Thái Ngọc Duy [off-list ref]:

quoted

Too deep delta chains can cause stack overflow in get_base_data(). Set
a hard limit so that index-pack does not run out of stack. Also stop
people from producing such a long delta chains using "pack-object
--depth=<too large>"

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 I used to make very long delta chains and triggered this in index-pack.
 I did not care reporting because it's my fault anyway. Think again,
 index-pack is called at server side and a malicious client can
 trigger this. This patch does not improve the situation much, but at
 least we won't get sigsegv at server side.

Wouldn't it make more sense to make the limit a config option rather
than a hard-coded value of 128 (which seems arbitrary to me)? After
all, different platforms have different stack-limitations...

Then it'd make more sense to make a compile time config based on
platform.

Can how much stack each recursion use be calculated at compile-time?
If so, I agree with you.

We could have a config option that can override the default,
but I really don't see the point of making long delta chains.

Aha, I figured you _did_ see a point in this, because 128 seemed
excessive to me already. I was thinking more that some platforms can
have a much smaller stack than (I would expect to) fit in 128
recursions (I've worked relatively recently with platforms with as
small as a static 2k stack per process), so you might not be fixing
the issue for such platforms. But that's not really your
responsibility either ;)

On Tue, Dec 6, 2011 at 7:41 PM, Erik Faye-Lund [off-list ref] wrote:

quoted

quoted

Wouldn't it make more sense to make the limit a config option rather
than a hard-coded value of 128 (which seems arbitrary to me)? After
all, different platforms have different stack-limitations...

Then it'd make more sense to make a compile time config based on
platform.

Can how much stack each recursion use be calculated at compile-time?
If so, I agree with you.

No, but at least we know default stack size of each platform and can
make pretty good limit based on that.

quoted

We could have a config option that can override the default,
but I really don't see the point of making long delta chains.

Aha, I figured you _did_ see a point in this, because 128 seemed
excessive to me already. I was thinking more that some platforms can
have a much smaller stack than (I would expect to) fit in 128
recursions (I've worked relatively recently with platforms with as
small as a static 2k stack per process), so you might not be fixing
the issue for such platforms. But that's not really your
responsibility either ;)

Ah, I was thinking of an option that extends the limit, not shortens
it. Yes it makes sense in this case.
-- 
Duy

On 12/06/2011 01:17 PM, Erik Faye-Lund wrote:

2011/12/5 Nguyễn Thái Ngọc Duy [off-list ref]:

quoted

Too deep delta chains can cause stack overflow in get_base_data(). Set
a hard limit so that index-pack does not run out of stack. Also stop
people from producing such a long delta chains using "pack-object
--depth=<too large>"

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 I used to make very long delta chains and triggered this in index-pack.
 I did not care reporting because it's my fault anyway. Think again,
 index-pack is called at server side and a malicious client can
 trigger this. This patch does not improve the situation much, but at
 least we won't get sigsegv at server side.

Wouldn't it make more sense to make the limit a config option rather
than a hard-coded value of 128 (which seems arbitrary to me)? After
all, different platforms have different stack-limitations...

I'm confused: is the data only ever read by the same host that generated
it?  Because if not, then the "creator" had better never be configured
to use a chain depth that the "reader" cannot handle.  This in turn
imply that there should be a common limit that is supported by all git
clients and is a documented part of the protocol.  (Or the code has to
be rewritten to use an explicit stack instead of recursion.)

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

2011/12/6 Michael Haggerty [off-list ref]:

On 12/06/2011 01:17 PM, Erik Faye-Lund wrote:

quoted

2011/12/5 Nguyễn Thái Ngọc Duy [off-list ref]:

quoted

Too deep delta chains can cause stack overflow in get_base_data(). Set
a hard limit so that index-pack does not run out of stack. Also stop
people from producing such a long delta chains using "pack-object
--depth=<too large>"

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 I used to make very long delta chains and triggered this in index-pack.
 I did not care reporting because it's my fault anyway. Think again,
 index-pack is called at server side and a malicious client can
 trigger this. This patch does not improve the situation much, but at
 least we won't get sigsegv at server side.

Wouldn't it make more sense to make the limit a config option rather
than a hard-coded value of 128 (which seems arbitrary to me)? After
all, different platforms have different stack-limitations...

I'm confused: is the data only ever read by the same host that generated
it?

index-pack is called at server side as part of a push. So in theory
the sending side can generate very long delta chains and bring down
the server side.

 Because if not, then the "creator" had better never be configured
to use a chain depth that the "reader" cannot handle.

Normal creators (i.e. C Git) use default depth 50 so we should be safe.

 This in turn
imply that there should be a common limit that is supported by all git
clients and is a documented part of the protocol.  (Or the code has to
be rewritten to use an explicit stack instead of recursion.)

It's the implementation limitation, not the protocol. If the server
propagates error messages from index-pack back to client (I'm not
sure), then users can adjust --depth to be accepted by server. We
could negotiate the limit over the protocol but not sure we would want
to go that route.

The troubled code could be rewritten to avoid recursion. However long
delta chains may degrade performance, I'd rather have support to split
long chains (which can be done with --depth at client already) instead
of just recursion elimination. This patch is simpler, so it would be
easier to back port it if someone wants to do so.
-- 
Duy

On Tue, Dec 6, 2011 at 07:30, Nguyen Thai Ngoc Duy [off-list ref] wrote:

index-pack is called at server side as part of a push. So in theory
the sending side can generate very long delta chains and bring down
the server side.

It is also called at client side during fetch. So in theory the server
can produce very long delta chains and take down a client.

quoted

 Because if not, then the "creator" had better never be configured
to use a chain depth that the "reader" cannot handle.

Normal creators (i.e. C Git) use default depth 50 so we should be safe.

JGit is also a "normal creator", and it sometimes produces chains
deeper than 50. Junio identified a 255 deep chain a week or two ago.
Some people have repacked their repositories very aggressively with
deeper chains when they are trying to optimize for space and don't
access historical revisions very often. I doubt anyone has packed
deeper than 120ish intentionally... but we shouldn't assume that in
the code.

quoted

 This in turn
imply that there should be a common limit that is supported by all git
clients and is a documented part of the protocol.  (Or the code has to
be rewritten to use an explicit stack instead of recursion.)

It's the implementation limitation, not the protocol. If the server
propagates error messages from index-pack back to client (I'm not
sure), then users can adjust --depth to be accepted by server. We
could negotiate the limit over the protocol but not sure we would want
to go that route.

What about clients fetching from a server? The client can't change the
depth the server sends it.

The troubled code could be rewritten to avoid recursion. However long
delta chains may degrade performance, I'd rather have support to split
long chains (which can be done with --depth at client already) instead
of just recursion elimination. This patch is simpler, so it would be
easier to back port it if someone wants to do so.

JGit long ago changed its IndexPack routine to use a manually managed
heap based stack instead of recursion, making it immune from
overrunning the stack due to a long delta chain. That is probably the
cleaner route. But you also have to fix sha1_file.c and its recursion
based unpacking of a delta chain... again which JGit fixed a long time
ago.

On Tue, Dec 06, 2011 at 10:12:54AM -0800, Shawn O. Pearce wrote:

quoted

Normal creators (i.e. C Git) use default depth 50 so we should be safe.

JGit is also a "normal creator", and it sometimes produces chains
deeper than 50. Junio identified a 255 deep chain a week or two ago.
Some people have repacked their repositories very aggressively with
deeper chains when they are trying to optimize for space and don't
access historical revisions very often. I doubt anyone has packed
deeper than 120ish intentionally... but we shouldn't assume that in
the code.

"git gc --aggressive" will set the depth to 250.

-Peff