Infinite loop in cascade_filter_fn()

Hi.

My git repository walker just got bitten by what seems to be a reasonably 
new bug in convert.c:cascade_filter_fn() (git 1.7.8.rc3 (gentoo)).

How to reproduce:

   git clone git@github.com:pikelang/Pike.git

   git checkout -f 0e2080f838c6f0bc7d670ac7549676a353451dca^

   git checkout -f 0e2080f838c6f0bc7d670ac7549676a353451dca

The first two commands complete as expected, while the last hangs forever.
Performing the same with git 1.7.6.4 works as expected.

The problematic file seems to be /src/modules/_Crypto/rijndael_ecb_vt.txt 
which has the attributes: text ident eol=crlf

Thanks,

--
Henrik Grubbström					grubba@grubba.org
Roxen Internet Software AB				grubba@roxen.com

On Wed, Nov 23, 2011 at 06:40:47PM +0100, Henrik Grubbström wrote:

Hi.

My git repository walker just got bitten by what seems to be a
reasonably new bug in convert.c:cascade_filter_fn() (git 1.7.8.rc3
(gentoo)).

It looks like it's a bug between cascade_filter_fn and the actual
filter function lf_to_crlf_filter_fn that gets triggered when the
output buffer is too small. In this particular case, *isize_p=378 and
*osize_p=1 which causes cascade_filter_fn to feed the filter data
which it can't process because it doesn't have anywhere to put it.

I think that the function assumes that the output buffer is always
large enough, but there are many indirections, so it might be an
off-by-one.

How to reproduce:

  git clone git@github.com:pikelang/Pike.git

  git checkout -f 0e2080f838c6f0bc7d670ac7549676a353451dca^

  git checkout -f 0e2080f838c6f0bc7d670ac7549676a353451dca

The first two commands complete as expected, while the last hangs forever.
Performing the same with git 1.7.6.4 works as expected.

The problematic file seems to be
/src/modules/_Crypto/rijndael_ecb_vt.txt which has the attributes:
text ident eol=crlf

Thanks,

--
Henrik Grubbström					grubba@grubba.org
Roxen Internet Software AB				grubba@roxen.com

On Wed, Nov 23, 2011 at 06:40:47PM +0100, Henrik Grubbström wrote:

Hi.

My git repository walker just got bitten by what seems to be a
reasonably new bug in convert.c:cascade_filter_fn() (git 1.7.8.rc3
(gentoo)).

How to reproduce:

  git clone git@github.com:pikelang/Pike.git

  git checkout -f 0e2080f838c6f0bc7d670ac7549676a353451dca^

  git checkout -f 0e2080f838c6f0bc7d670ac7549676a353451dca

The first two commands complete as expected, while the last hangs forever.
Performing the same with git 1.7.6.4 works as expected.

The problematic file seems to be
/src/modules/_Crypto/rijndael_ecb_vt.txt which has the attributes:
text ident eol=crlf

It looks like you won the lottery. The problem was that the output
buffer only has one byte available when we see a LF. We check whether
there is enough space (two bytes) to store CRLF in the output buffer,
see that there isn't and return. cascade_filter_fn sees that the
buffer hasn't been written fully and calls lf_to_crlf_filter_fn with
the same output buffer, which we still can't fill, because it's too
short.

This patch fixes this, but I think it would still break if the LF is
at the end of the file. Changing the `if (!input)` to put the LF in
the output buffer may or may not be the right soulution. I feel like
this should be handled by cascade_filter_fn rather than the actual
filter somehow, but Junio's comment (4ae66704 'stream filter: add "no
more input" to the filters') suggests otherwise.

I'm working on a cleaner patch that takes care of a bit of state, but
this is the general idea.

   cmn

--- 8< ---

Subject: [PATCH] convert: don't loop indefintely if at LF-to-CRLF streaming

If we find a LF when the output buffer is only has one byte remaining,
cascade_filter_fn won't notice that we need more input and won't drain
the output buffer.

In such a case, store whether we've outputted the CR so we can retake
it from there.

Signed-off-by: Carlos Martín Nieto <redacted>
---
 convert.c |   11 ++++++++---
 1 files changed, 8 insertions(+), 3 deletions(-)

diff --git a/convert.c b/convert.c
index 86e9c29..4218f40 100644
--- a/convert.c
+++ b/convert.c

@@ -881,6 +881,7 @@ static int lf_to_crlf_filter_fn(struct stream_filter *filter,
 				char *output, size_t *osize_p)
 {
 	size_t count;
+	static int put_cr = 0;
 
 	if (!input)
 		return 0; /* we do not keep any states */

@@ -890,10 +891,14 @@ static int lf_to_crlf_filter_fn(struct stream_filter *filter,
 		for (i = o = 0; o < *osize_p && i < count; i++) {
 			char ch = input[i];
 			if (ch == '\n') {
-				if (o + 1 < *osize_p)
+				if (put_cr) {
+					put_cr = 0;
+				} else {
 					output[o++] = '\r';
-				else
-					break;
+					put_cr = 1;
+					i--;
+					continue;
+				}
 			}
 			output[o++] = ch;
 		}

-- 
1.7.8.rc3.31.g017d1

On Wed, 23 Nov 2011, Henrik Grubbström wrote:

Hi.

My git repository walker just got bitten by what seems to be a reasonably new 
bug in convert.c:cascade_filter_fn() (git 1.7.8.rc3 (gentoo)).

After some tracing, the problem is triggered by the variable "remaining"
being set to 1 in the beginning of the cascade_filter_fn() loop, which 
causes filter "two" to be called with an output buffer size of 1.
Filter "two" in this case is lf_to_crlf_filter_fn(), and the next input 
character is a "\n". lf_to_crlf_filter_fn() wants to convert this to 
"\r\n", but that doesn't fit into the buffer, so it breaks out and returns 
zero. Upon seing the zero cascade_filter_fn() thinks all is well, even 
though nothing has happened, and loops.

The bug is probably that lf_to_crlf_filter_fn() should return non-zero in 
this case (ie o and/or i being zero).

Thanks,

--
Henrik Grubbström					grubba@roxen.com
Roxen Internet Software AB

On Fri, Nov 25, 2011 at 04:43:41PM +0100, Henrik Grubbström wrote:

On Wed, 23 Nov 2011, Henrik Grubbström wrote:

quoted

Hi.

My git repository walker just got bitten by what seems to be a
reasonably new bug in convert.c:cascade_filter_fn() (git 1.7.8.rc3
(gentoo)).

After some tracing, the problem is triggered by the variable "remaining"
being set to 1 in the beginning of the cascade_filter_fn() loop,
which causes filter "two" to be called with an output buffer size of
1.
Filter "two" in this case is lf_to_crlf_filter_fn(), and the next
input character is a "\n". lf_to_crlf_filter_fn() wants to convert
this to "\r\n", but that doesn't fit into the buffer, so it breaks
out and returns zero. Upon seing the zero cascade_filter_fn() thinks
all is well, even though nothing has happened, and loops.

The bug is probably that lf_to_crlf_filter_fn() should return
non-zero in this case (ie o and/or i being zero).

non-zero? That would cause the filter to abort, which definitely not
what we want. Have you seen my other e-mails regarding this? I'm
trying to figure out which is the best way to go about this. The
solution is to keep track of the fact that we're missing a LF in the
output buffer.

   cmn

On Fri, 25 Nov 2011, Carlos Martín Nieto wrote:

On Fri, Nov 25, 2011 at 04:43:41PM +0100, Henrik Grubbström wrote:

quoted

The bug is probably that lf_to_crlf_filter_fn() should return
non-zero in this case (ie o and/or i being zero).

non-zero? That would cause the filter to abort, which definitely not
what we want. Have you seen my other e-mails regarding this? I'm
trying to figure out which is the best way to go about this. The
solution is to keep track of the fact that we're missing a LF in the
output buffer.

True, I misread the code.

Keeping track of the filter state is the way to go.

  cmn

--
Henrik Grubbström					grubba@roxen.com
Roxen Internet Software AB

On Fri, 25 Nov 2011, Carlos Martín Nieto wrote:

This patch fixes this, but I think it would still break if the LF is
at the end of the file. Changing the `if (!input)` to put the LF in
the output buffer may or may not be the right soulution. I feel like
this should be handled by cascade_filter_fn rather than the actual
filter somehow, but Junio's comment (4ae66704 'stream filter: add "no
more input" to the filters') suggests otherwise.

I'm working on a cleaner patch that takes care of a bit of state, but
this is the general idea.

Looks good to me (and seems to work in my case).
Typo in the commit subject though.

                                        ^^^^^^^^^^^
This should be either "infinitely", or "indefinitely", but since we know 
that the loop won't terminate "infinitely" is to be preferred.

Thanks,

--
Henrik Grubbström					grubba@roxen.com
Roxen Internet Software AB

On Fri, Nov 25, 2011 at 05:14:17PM +0100, Henrik Grubbström wrote:

On Fri, 25 Nov 2011, Carlos Martín Nieto wrote:

quoted

This patch fixes this, but I think it would still break if the LF is
at the end of the file. Changing the `if (!input)` to put the LF in
the output buffer may or may not be the right soulution. I feel like
this should be handled by cascade_filter_fn rather than the actual
filter somehow, but Junio's comment (4ae66704 'stream filter: add "no
more input" to the filters') suggests otherwise.

I'm working on a cleaner patch that takes care of a bit of state, but
this is the general idea.

Looks good to me (and seems to work in my case).

That patch would give wrong output if the same happened at the end of
a file. The attached patch should also cover this case.

Typo in the commit subject though.

quoted

 cmn

--- 8< ---

Subject: [PATCH] convert: don't loop indefintely if at LF-to-CRLF streaming

                                       ^^^^^^^^^^^
This should be either "infinitely", or "indefinitely", but since we
know that the loop won't terminate "infinitely" is to be preferred.

Thanks for noticing. I went with a different title in the end. Junio,
could you consider this one for inclusion in the next RC?

--- 8< ---

Subject: [PATCH] convert: track state in LF-to-CRLF filter

There may not be enough space to store CRLF in the output. If we don't
fill the buffer, then the filter will keep getting called with the same
short buffer and will loop forever.

Instead, always store the CR and record there's a missing LF if
necessary it so we store it in the output buffer the next time the
function gets called.

Reported-by: Henrik Grubbström <redacted>
Signed-off-by: Carlos Martín Nieto <redacted>
---
 convert.c |   23 ++++++++++++++++-------
 1 files changed, 16 insertions(+), 7 deletions(-)

diff --git a/convert.c b/convert.c
index 86e9c29..c050b86 100644
--- a/convert.c
+++ b/convert.c

@@ -880,20 +880,29 @@ static int lf_to_crlf_filter_fn(struct stream_filter *filter,
 				const char *input, size_t *isize_p,
 				char *output, size_t *osize_p)
 {
-	size_t count;
+	size_t count, o = 0;
+	static int want_lf = 0;
+
+	/* Output a pending LF if we need to */
+	if (want_lf) {
+		output[o++] = '\n';
+		want_lf = 0;
+	}
 
 	if (!input)
-		return 0; /* we do not keep any states */
+		return 0; /* We've already dealt with the state */
+
 	count = *isize_p;
 	if (count) {
-		size_t i, o;
-		for (i = o = 0; o < *osize_p && i < count; i++) {
+		size_t i;
+		for (i = 0; o < *osize_p && i < count; i++) {
 			char ch = input[i];
 			if (ch == '\n') {
-				if (o + 1 < *osize_p)
-					output[o++] = '\r';
-				else
+				output[o++] = '\r';
+				if (o >= *osize_p) {
+					want_lf = 1;
 					break;
+				}
 			}
 			output[o++] = ch;
 		}

-- 
1.7.8.rc3.31.g017d1