[PATCH 0/1] segfault in cgit

[PATCH 0/1] segfault in cgit

[jamie.couture]

From: Jamie Couture <jamie.couture at gmail.com>

I reproduced the problem reported by Arun Persaud on his version, 9900ac022,
and on 756e3ea6.  Based on the suggestions of others, here is a patch to help
avoid segfaults when calculating lcs when printing deferred changed lines.

Jamie Couture (1):
  move LCS table away from the stack

 cgit.h      |   12 ++++++++++++
 ui-ssdiff.c |   32 ++++++++++++++++++++++++++++++--
 2 files changed, 42 insertions(+), 2 deletions(-)

-- 
1.7.6

[PATCH 1/1] move LCS table away from the stack

[jamie.couture]

From: Jamie Couture <jamie.couture at gmail.com>

Minified files such as javascript, or something similar, where very long
single lines to compare when printing deferred line changes would have
caused segfaults.

Signed-off-by: Jamie Couture <jamie.couture at gmail.com>
---
 cgit.h      |   12 ++++++++++++
 ui-ssdiff.c |   32 ++++++++++++++++++++++++++++++--
 2 files changed, 42 insertions(+), 2 deletions(-)

diff --git a/cgit.h b/cgit.h
index bad66f0..1ff5cb3 100644
--- a/cgit.h
+++ b/cgit.h
@@ -47,6 +47,18 @@
  */
 #define PAGE_ENCODING "UTF-8"
 
+/*
+ * ssdiff line limits
+ */
+#ifndef MAX_SSDIFF_M
+#define MAX_SSDIFF_M 1024
+#endif
+
+#ifndef MAX_SSDIFF_N
+#define MAX_SSDIFF_N 1024
+#endif
+#define MAX_SSDIFF_SIZE ((MAX_SSDIFF_M) * (MAX_SSDIFF_N))
+
 typedef void (*configfn)(const char *name, const char *value);
 typedef void (*filepair_fn)(struct diff_filepair *pair);
 typedef void (*linediff_fn)(char *line, int len);
diff --git a/ui-ssdiff.c b/ui-ssdiff.c
index 2481585..4df01ed 100644
--- a/ui-ssdiff.c
+++ b/ui-ssdiff.c
@@ -16,16 +16,41 @@ struct deferred_lines {
 static struct deferred_lines *deferred_old, *deferred_old_last;
 static struct deferred_lines *deferred_new, *deferred_new_last;
 
+static int **create_lcs_table(size_t m, size_t n)
+{
+	int **L;
+	int i;
+
+	// xcalloc will die if we ran out of memory;
+	// not very helpful for debugging
+	L = (int**)xcalloc(m, sizeof(int *));
+	*L = (int*)xcalloc(m * n, sizeof(int));
+
+	for (i = 1; i < m; i++) {
+		L[i] = *L + i * n;
+	}
+
+	return L;
+}
+
 static char *longest_common_subsequence(char *A, char *B)
 {
 	int i, j, ri;
 	int m = strlen(A);
 	int n = strlen(B);
-	int L[m + 1][n + 1];
-	int tmp1, tmp2;
+	int **L;
+	int tmp1, tmp2, length;
 	int lcs_length;
 	char *result;
 
+	length = (m + 1) * (n + 1);
+
+	// We bail if the lines are too long
+	if (length > MAX_SSDIFF_SIZE)
+		return NULL;
+
+	L = create_lcs_table(m + 1, n + 1);
+
 	for (i = m; i >= 0; i--) {
 		for (j = n; j >= 0; j--) {
 			if (A[i] == '\0' || B[j] == '\0') {
@@ -59,6 +84,9 @@ static char *longest_common_subsequence(char *A, char *B)
 			j += 1;
 		}
 	}
+
+	free(*L);
+	free(L);
 	return result;
 }
 
-- 
1.7.6

[PATCH 1/1] move LCS table away from the stack

[jamie.couture]

resubmitting patch due to terrible grammar in commit message.

[PATCH] move LCS table away from the stack

[jamie.couture]

Printing deferred line changes for files containing long lines would
cause a segfault.  Set limitations and move lookup table out of the
stack.

Signed-off-by: Jamie Couture <jamie.couture at gmail.com>
---
 cgit.h      |   12 ++++++++++++
 ui-ssdiff.c |   32 ++++++++++++++++++++++++++++++--
 2 files changed, 42 insertions(+), 2 deletions(-)

diff --git a/cgit.h b/cgit.h
index bad66f0..1ff5cb3 100644
--- a/cgit.h
+++ b/cgit.h
@@ -47,6 +47,18 @@
  */
 #define PAGE_ENCODING "UTF-8"
 
+/*
+ * ssdiff line limits
+ */
+#ifndef MAX_SSDIFF_M
+#define MAX_SSDIFF_M 1024
+#endif
+
+#ifndef MAX_SSDIFF_N
+#define MAX_SSDIFF_N 1024
+#endif
+#define MAX_SSDIFF_SIZE ((MAX_SSDIFF_M) * (MAX_SSDIFF_N))
+
 typedef void (*configfn)(const char *name, const char *value);
 typedef void (*filepair_fn)(struct diff_filepair *pair);
 typedef void (*linediff_fn)(char *line, int len);
diff --git a/ui-ssdiff.c b/ui-ssdiff.c
index 2481585..4df01ed 100644
--- a/ui-ssdiff.c
+++ b/ui-ssdiff.c
@@ -16,16 +16,41 @@ struct deferred_lines {
 static struct deferred_lines *deferred_old, *deferred_old_last;
 static struct deferred_lines *deferred_new, *deferred_new_last;
 
+static int **create_lcs_table(size_t m, size_t n)
+{
+	int **L;
+	int i;
+
+	// xcalloc will die if we ran out of memory;
+	// not very helpful for debugging
+	L = (int**)xcalloc(m, sizeof(int *));
+	*L = (int*)xcalloc(m * n, sizeof(int));
+
+	for (i = 1; i < m; i++) {
+		L[i] = *L + i * n;
+	}
+
+	return L;
+}
+
 static char *longest_common_subsequence(char *A, char *B)
 {
 	int i, j, ri;
 	int m = strlen(A);
 	int n = strlen(B);
-	int L[m + 1][n + 1];
-	int tmp1, tmp2;
+	int **L;
+	int tmp1, tmp2, length;
 	int lcs_length;
 	char *result;
 
+	length = (m + 1) * (n + 1);
+
+	// We bail if the lines are too long
+	if (length > MAX_SSDIFF_SIZE)
+		return NULL;
+
+	L = create_lcs_table(m + 1, n + 1);
+
 	for (i = m; i >= 0; i--) {
 		for (j = n; j >= 0; j--) {
 			if (A[i] == '\0' || B[j] == '\0') {
@@ -59,6 +84,9 @@ static char *longest_common_subsequence(char *A, char *B)
 			j += 1;
 		}
 	}
+
+	free(*L);
+	free(L);
 	return result;
 }
 
-- 
1.7.6

[PATCH] move LCS table away from the stack

[hjemli]

On Sun, Sep 11, 2011 at 02:44, Jamie Couture <jamie.couture at gmail.com> wrote:
> +/*
> + * ssdiff line limits
> + */
> +#ifndef MAX_SSDIFF_M
> +#define MAX_SSDIFF_M 1024
> +#endif
> +
> +#ifndef MAX_SSDIFF_N
> +#define MAX_SSDIFF_N 1024
> +#endif
> +#define MAX_SSDIFF_SIZE ((MAX_SSDIFF_M) * (MAX_SSDIFF_N))

I think this limit should be more like 128*128 for a few reasons:
* ss-diff for lines longer than 128 chars probably isn't very useful
(you'd need a very wide monitor)
* cpu time spent in LCS() seems to be propotional to avg(linelength)^2


> ?static char *longest_common_subsequence(char *A, char *B)
> ?{
> ? ? ? ?int i, j, ri;
> ? ? ? ?int m = strlen(A);
> ? ? ? ?int n = strlen(B);
> - ? ? ? int L[m + 1][n + 1];
> - ? ? ? int tmp1, tmp2;
> + ? ? ? int **L;
> + ? ? ? int tmp1, tmp2, length;
> ? ? ? ?int lcs_length;
> ? ? ? ?char *result;
>
> + ? ? ? length = (m + 1) * (n + 1);
> +
> + ? ? ? // We bail if the lines are too long
> + ? ? ? if (length > MAX_SSDIFF_SIZE)
> + ? ? ? ? ? ? ? return NULL;
> +
> + ? ? ? L = create_lcs_table(m + 1, n + 1);
> +
> ? ? ? ?for (i = m; i >= 0; i--) {
> ? ? ? ? ? ? ? ?for (j = n; j >= 0; j--) {
> ? ? ? ? ? ? ? ? ? ? ? ?if (A[i] == '\0' || B[j] == '\0') {
> @@ -59,6 +84,9 @@ static char *longest_common_subsequence(char *A, char *B)
> ? ? ? ? ? ? ? ? ? ? ? ?j += 1;
> ? ? ? ? ? ? ? ?}
> ? ? ? ?}
> +
> + ? ? ? free(*L);
> + ? ? ? free(L);
> ? ? ? ?return result;
> ?}

This function is potentially invoked for each diff-line, right? If so,
why not prepare a "shared" lcs-table in the caller (expecting
worst-case linelength) to avoid the setup/teardown of the table for
each line?

--
larsh

[PATCH 1/1] move LCS table away from the stack

[jamie.couture]

From: Jamie Couture <jamie.couture at gmail.com>

Printing deferred line changes for files containing long lines would
cause a segfault.

- limit LCS table size: 128x128.
- move LCS table to global context: avoid allocating/freeing memory
  for every deferred line change.

Signed-off-by: Jamie Couture <jamie.couture at gmail.com>
---
 ui-ssdiff.c |   33 +++++++++++++++++++++++++++++++--
 ui-ssdiff.h |   12 ++++++++++++
 2 files changed, 43 insertions(+), 2 deletions(-)

diff --git a/ui-ssdiff.c b/ui-ssdiff.c
index 2481585..9fb5b11 100644
--- a/ui-ssdiff.c
+++ b/ui-ssdiff.c
@@ -2,10 +2,12 @@
 #include "html.h"
 #include "ui-shared.h"
 #include "ui-diff.h"
+#include "ui-ssdiff.h"
 
 extern int use_ssdiff;
 
 static int current_old_line, current_new_line;
+static int **L = NULL;
 
 struct deferred_lines {
 	int line_no;
@@ -16,16 +18,42 @@ struct deferred_lines {
 static struct deferred_lines *deferred_old, *deferred_old_last;
 static struct deferred_lines *deferred_new, *deferred_new_last;
 
+static void create_or_reset_lcs_table()
+{
+	int i;
+
+	if (L != NULL) {
+		memset(*L, 0, sizeof(*L) * MAX_SSDIFF_SIZE);
+		return;
+	}
+
+	// xcalloc will die if we ran out of memory;
+	// not very helpful for debugging
+	L = (int**)xcalloc(MAX_SSDIFF_M, sizeof(int *));
+	*L = (int*)xcalloc(MAX_SSDIFF_SIZE, sizeof(int));
+
+	for (i = 1; i < MAX_SSDIFF_M; i++) {
+		L[i] = *L + i * MAX_SSDIFF_N;
+	}
+}
+
 static char *longest_common_subsequence(char *A, char *B)
 {
 	int i, j, ri;
 	int m = strlen(A);
 	int n = strlen(B);
-	int L[m + 1][n + 1];
-	int tmp1, tmp2;
+	int tmp1, tmp2, length;
 	int lcs_length;
 	char *result;
 
+	length = (m + 1) * (n + 1);
+
+	// We bail if the lines are too long
+	if (length > MAX_SSDIFF_SIZE)
+		return NULL;
+
+	create_or_reset_lcs_table();
+
 	for (i = m; i >= 0; i--) {
 		for (j = n; j >= 0; j--) {
 			if (A[i] == '\0' || B[j] == '\0') {
@@ -59,6 +87,7 @@ static char *longest_common_subsequence(char *A, char *B)
 			j += 1;
 		}
 	}
+
 	return result;
 }
 
diff --git a/ui-ssdiff.h b/ui-ssdiff.h
index 64b4b12..88627e2 100644
--- a/ui-ssdiff.h
+++ b/ui-ssdiff.h
@@ -1,6 +1,18 @@
 #ifndef UI_SSDIFF_H
 #define UI_SSDIFF_H
 
+/*
+ * ssdiff line limits
+ */
+#ifndef MAX_SSDIFF_M
+#define MAX_SSDIFF_M 128
+#endif
+
+#ifndef MAX_SSDIFF_N
+#define MAX_SSDIFF_N 128
+#endif
+#define MAX_SSDIFF_SIZE ((MAX_SSDIFF_M) * (MAX_SSDIFF_N))
+
 extern void cgit_ssdiff_print_deferred_lines();
 
 extern void cgit_ssdiff_line_cb(char *line, int len);
-- 
1.7.6

[PATCH 1/1] move LCS table away from the stack

[hjemli]

On Sun, Sep 18, 2011 at 00:25, Jamie Couture <jamie.couture at gmail.com> wrote:
> - limit LCS table size: 128x128.
> - move LCS table to global context: avoid allocating/freeing memory
> ?for every deferred line change.

Thanks, finally applied (to stable).

--
larsh

[PATCH 1/1] move LCS table away from the stack

[normalperson]

Lars Hjemli <hjemli at gmail.com> wrote:
> On Sun, Sep 18, 2011 at 00:25, Jamie Couture <jamie.couture at gmail.com> wrote:
> > - limit LCS table size: 128x128.
> > - move LCS table to global context: avoid allocating/freeing memory
> > ?for every deferred line change.
> 
> Thanks, finally applied (to stable).

Hi, I got new segfaults with this patch, the following should
fix them.

From 2d9ae9c3369d537259822a6dd64a13963cc4fdbf Mon Sep 17 00:00:00 2001
From: Eric Wong <normalperson at yhbt.net>
Date: Wed, 04 Jan 2012 08:57:43 +0000
Subject: [PATCH 2/2] correct length check for LCS table

Each individual string may be too long for its respective
dimension of the LCS table.

Signed-off-by: Eric Wong <normalperson at yhbt.net>
---
 ui-ssdiff.c |    6 ++----
 1 files changed, 2 insertions(+), 4 deletions(-)

diff --git a/ui-ssdiff.c b/ui-ssdiff.c
index 9fb5b11..45770b1 100644
--- a/ui-ssdiff.c
+++ b/ui-ssdiff.c
@@ -42,14 +42,12 @@ static char *longest_common_subsequence(char *A, char *B)
 	int i, j, ri;
 	int m = strlen(A);
 	int n = strlen(B);
-	int tmp1, tmp2, length;
+	int tmp1, tmp2;
 	int lcs_length;
 	char *result;
 
-	length = (m + 1) * (n + 1);
-
 	// We bail if the lines are too long
-	if (length > MAX_SSDIFF_SIZE)
+	if (m >= MAX_SSDIFF_M || n >= MAX_SSDIFF_N)
 		return NULL;
 
 	create_or_reset_lcs_table();
-- 
Eric Wong

[PATCH 1/1] move LCS table away from the stack

[jamie.couture]

On Wed, Jan 4, 2012 at 3:59 AM, Eric Wong <normalperson at yhbt.net> wrote:

> Lars Hjemli <hjemli at gmail.com> wrote:
> > On Sun, Sep 18, 2011 at 00:25, Jamie Couture <jamie.couture at gmail.com>
> wrote:
> > > - limit LCS table size: 128x128.
> > > - move LCS table to global context: avoid allocating/freeing memory
> > >  for every deferred line change.
> >
> > Thanks, finally applied (to stable).
>
> Hi, I got new segfaults with this patch, the following should
> fix them.
>
> From 2d9ae9c3369d537259822a6dd64a13963cc4fdbf Mon Sep 17 00:00:00 2001
> From: Eric Wong <normalperson at yhbt.net>
> Date: Wed, 04 Jan 2012 08:57:43 +0000
> Subject: [PATCH 2/2] correct length check for LCS table
>
> Each individual string may be too long for its respective
> dimension of the LCS table.
>
> Signed-off-by: Eric Wong <normalperson at yhbt.net>
> ---
>  ui-ssdiff.c |    6 ++----
>  1 files changed, 2 insertions(+), 4 deletions(-)
>
> diff --git a/ui-ssdiff.c b/ui-ssdiff.c
> index 9fb5b11..45770b1 100644
> --- a/ui-ssdiff.c
> +++ b/ui-ssdiff.c
> @@ -42,14 +42,12 @@ static char *longest_common_subsequence(char *A, char
> *B)
>         int i, j, ri;
>        int m = strlen(A);
>        int n = strlen(B);
> -       int tmp1, tmp2, length;
> +       int tmp1, tmp2;
>         int lcs_length;
>        char *result;
>
> -       length = (m + 1) * (n + 1);
> -
>         // We bail if the lines are too long
> -       if (length > MAX_SSDIFF_SIZE)
> +       if (m >= MAX_SSDIFF_M || n >= MAX_SSDIFF_N)
>                return NULL;
>
>        create_or_reset_lcs_table();
> --
> Eric Wong
>

Tested and confirmed segfault fix

Thanks, Eric

[PATCH 1/1] move LCS table away from the stack

[jamie.couture]

Tested the following patches on Ubuntu 10.10, CentOS 6, RedHat 6

[PATCH 1/2] correct length check for LCS table

[jamie.couture]

From: Eric Wong <normalperson at yhbt.net>

Each individual string may be too long for its respective
dimension of the LCS table.

Signed-off-by: Eric Wong <normalperson at yhbt.net>
Signed-off-by: Jamie Couture <jamie.couture at gmail.com>
---
 ui-ssdiff.c |    6 ++----
 1 files changed, 2 insertions(+), 4 deletions(-)

diff --git a/ui-ssdiff.c b/ui-ssdiff.c
index 9fb5b11..45770b1 100644
--- a/ui-ssdiff.c
+++ b/ui-ssdiff.c
@@ -42,14 +42,12 @@ static char *longest_common_subsequence(char *A, char *B)
 	int i, j, ri;
 	int m = strlen(A);
 	int n = strlen(B);
-	int tmp1, tmp2, length;
+	int tmp1, tmp2;
 	int lcs_length;
 	char *result;
 
-	length = (m + 1) * (n + 1);
-
 	// We bail if the lines are too long
-	if (length > MAX_SSDIFF_SIZE)
+	if (m >= MAX_SSDIFF_M || n >= MAX_SSDIFF_N)
 		return NULL;
 
 	create_or_reset_lcs_table();
-- 
1.7.7.4

[PATCH 2/2] use correct type for sizeof

[jamie.couture]

**L would have worked well too.  Depending on the distribution sizeof *L
may return 8 instead of 4. **L is preferable, but since we don't expect
this datatype to change very often, sizeof int is less subtle and easier
to understand.

Signed-off-by: Jamie Couture <jamie.couture at gmail.com>
---
 ui-ssdiff.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/ui-ssdiff.c b/ui-ssdiff.c
index 45770b1..0cff4b8 100644
--- a/ui-ssdiff.c
+++ b/ui-ssdiff.c
@@ -23,7 +23,7 @@ static void create_or_reset_lcs_table()
 	int i;
 
 	if (L != NULL) {
-		memset(*L, 0, sizeof(*L) * MAX_SSDIFF_SIZE);
+		memset(*L, 0, sizeof(int) * MAX_SSDIFF_SIZE);
 		return;
 	}
 
-- 
1.7.7.4

[PATCH 2/2] use correct type for sizeof

[hjemli]

On Thu, Jan 12, 2012 at 04:38, Jamie Couture <jamie.couture at gmail.com> wrote:
> **L would have worked well too. ?Depending on the distribution sizeof *L
> may return 8 instead of 4. **L is preferable, but since we don't expect
> this datatype to change very often, sizeof int is less subtle and easier
> to understand.

Finally applied to stable

--
larsh