Re: [PATCH] Set hard limit on delta chain depth

Nguyễn Thái Ngọc Duy  [off-list ref] writes:

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.

Why should we treat this condition any differently from the case where the
sender of a pack used beefier machine than you have and stuffed a huge
object that the index-pack running on your box cannot hold in core,
causing xmalloc() to die on your machine?

I do not think this is the right way to handle the issue. Your other patch
to flatten the recursion to iteration looked a lot saner approach.

2011/12/6 Junio C Hamano [off-list ref]:

Nguyễn Thái Ngọc Duy  [off-list ref] writes:

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.

Why should we treat this condition any differently from the case where the
sender of a pack used beefier machine than you have and stuffed a huge
object that the index-pack running on your box cannot hold in core,
causing xmalloc() to die on your machine?

That's interesting. First of all xmalloc() is controlled by us while
index-pack code might lead to stack overflow exploit (never done it,
not sure if it's really pratical to do in this case).

But can I really use up all memory at server side by sending a huge pack?

I do not think this is the right way to handle the issue. Your other patch
to flatten the recursion to iteration looked a lot saner approach.

It may take me some time as I'm not really familar with this code.
Anybody is welcome to step up and flatten the function.
-- 
Duy

Revert the order of delta applying so that by the time a delta is
applied, its base is either non-delta or already inflated.
get_delta_base() is still recursive, but because base's data is always
ready, the inner get_delta_base() call never has any chance to call
itself again.

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 builtin/index-pack.c |   30 +++++++++++++++++++++---------
 1 files changed, 21 insertions(+), 9 deletions(-)

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

@@ -508,10 +508,25 @@ static void *get_base_data(struct base_data *c)
 {
 	if (!c->data) {
 		struct object_entry *obj = c->obj;
+		struct base_data **delta = NULL;
+		int delta_nr = 0, delta_alloc = 0;
 
-		if (is_delta_type(obj->type)) {
-			void *base = get_base_data(c->base);
-			void *raw = get_data_from_pack(obj);
+		for (; is_delta_type(c->obj->type); c = c->base) {
+			ALLOC_GROW(delta, delta_nr + 1, delta_alloc);
+			delta[delta_nr++] = c;
+		}
+		if (!delta_nr) {
+			c->data = get_data_from_pack(obj);
+			c->size = obj->size;
+			base_cache_used += c->size;
+			prune_base_data(c);
+		}
+		for (; delta_nr > 0; delta_nr--) {
+			void *base, *raw;
+			c = delta[delta_nr - 1];
+			obj = c->obj;
+			base = get_base_data(c->base);
+			raw = get_data_from_pack(obj);
 			c->data = patch_delta(
 				base, c->base->size,
 				raw, obj->size,

@@ -519,13 +534,10 @@ static void *get_base_data(struct base_data *c)
 			free(raw);
 			if (!c->data)
 				bad_object(obj->idx.offset, "failed to apply delta");
-		} else {
-			c->data = get_data_from_pack(obj);
-			c->size = obj->size;
+			base_cache_used += c->size;
+			prune_base_data(c);
 		}
-
-		base_cache_used += c->size;
-		prune_base_data(c);
+		free(delta);
 	}
 	return c->data;
 }

-- 
1.7.8.36.g69ee2

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

Revert the order of delta applying so that by the time a delta is
applied, its base is either non-delta or already inflated.
get_delta_base() is still recursive, but because base's data is always
ready, the inner get_delta_base() call never has any chance to call
itself again.

...

I think you missed the critical recursion. The real work is the
recursion within find_unresolved_deltas(). This little helper
get_base_data() shouldn't be tripping over these cases unless we have
run out of delta_base_cache_limit and released objects near the base
end of the delta chain, in which case this will restore them.

Maybe this is useful on its own, but in my opinion its not an
interesting patch to consider without first fixing
find_unresolved_deltas's recursion.

2011/12/8 Shawn Pearce [off-list ref]:

I think you missed the critical recursion. The real work is the
recursion within find_unresolved_deltas(). This little helper
get_base_data() shouldn't be tripping over these cases unless we have
run out of delta_base_cache_limit and released objects near the base
end of the delta chain, in which case this will restore them.

Maybe this is useful on its own, but in my opinion its not an
interesting patch to consider without first fixing
find_unresolved_deltas's recursion.

Thanks. I missed that function. Will try to fix it.
-- 
Duy

From: Nguyễn Thái Ngọc Duy <redacted>

The next patch puts most of the code in one level deeper. By indenting
separately, it'd be easier to see the actual changes.

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 builtin/index-pack.c |   47 +++++++++++++++++++++++------------------------
 1 files changed, 23 insertions(+), 24 deletions(-)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 103e19c..9855ada 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c

@@ -585,37 +585,36 @@ static void find_unresolved_deltas(struct base_data *base,
 		base_spec.offset = base->obj->idx.offset;
 		find_delta_children(&base_spec,
 				    &ofs_first, &ofs_last, OBJ_OFS_DELTA);
-	}
 
-	if (ref_last == -1 && ofs_last == -1) {
-		free(base->data);
-		return;
-	}
+		if (ref_last == -1 && ofs_last == -1) {
+			free(base->data);
+			return;
+		}
 
-	link_base_data(prev_base, base);
+		link_base_data(prev_base, base);
 
-	for (i = ref_first; i <= ref_last; i++) {
-		struct object_entry *child = objects + deltas[i].obj_no;
-		struct base_data result;
+		for (i = ref_first; i <= ref_last; i++) {
+			struct object_entry *child = objects + deltas[i].obj_no;
+			struct base_data result;
 
-		assert(child->real_type == OBJ_REF_DELTA);
-		resolve_delta(child, base, &result);
-		if (i == ref_last && ofs_last == -1)
-			free_base_data(base);
-		find_unresolved_deltas(&result, base);
-	}
+			assert(child->real_type == OBJ_REF_DELTA);
+			resolve_delta(child, base, &result);
+			if (i == ref_last && ofs_last == -1)
+				free_base_data(base);
+			find_unresolved_deltas(&result, base);
+		}
 
-	for (i = ofs_first; i <= ofs_last; i++) {
-		struct object_entry *child = objects + deltas[i].obj_no;
-		struct base_data result;
+		for (i = ofs_first; i <= ofs_last; i++) {
+			struct object_entry *child = objects + deltas[i].obj_no;
+			struct base_data result;
 
-		assert(child->real_type == OBJ_OFS_DELTA);
-		resolve_delta(child, base, &result);
-		if (i == ofs_last)
-			free_base_data(base);
-		find_unresolved_deltas(&result, base);
+			assert(child->real_type == OBJ_OFS_DELTA);
+			resolve_delta(child, base, &result);
+			if (i == ofs_last)
+				free_base_data(base);
+			find_unresolved_deltas(&result, base);
+		}
 	}
-
 	unlink_base_data(base);
 }
 

-- 
1.7.8.36.g69ee2

Nguyen Thai Ngoc Duy [off-list ref] writes:

That's interesting. First of all xmalloc() is controlled by us while
index-pack code might lead to stack overflow exploit (never done it,
not sure if it's really pratical to do in this case).

What do you exactly mean by "stack overflow exploit"?

If your callee has prepares a stackframe that is not sufficiently big but
carelessly tries to store more than it has space for, such a write can
overflow the stack (without hardware traps) and overwrite return address,
and instead of coming back to you, the control can be transferred to
random places.

But I do not think that is what we are talking about here.

You attempt to write parameters and return address to the area of memory
pointed by your stack pointer, advance the stack pointer to create a stack
frame and the callee attempts to write to its local variables in the newly
allocated stack frame. These memory accesses eventually attempt to touch
memory beyond the address range the kernel gave you page table entries to
be used as your stack space, and hardware traps. If you haven't run out of
the stack, a new page is lazily added to the page table and your attempted
access will succeed. If you are recursing too deeply, you won't be given a
new page and you will be killed by the kernel. That is a rather controlled
death of the process, unlike smashing the contents of the stack to jump to
a randomly chosen place, isn't it?

Of course, some platforms do not have an unwritable gap between the stack
segment that grow downwards and the heap that grow upwards, and also your
stackframe could be larger than such a gap (in this particular callchain I
do not think that is the case), so the above discussion does not apply
universally, though.