* [PATCH 0/1] segfault in cgit @ 2011-09-09 4:43 jamie.couture 2011-09-09 4:43 ` [PATCH 1/1] move LCS table away from the stack jamie.couture 0 siblings, 1 reply; 13+ messages in thread From: jamie.couture @ 2011-09-09 4:43 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 1/1] move LCS table away from the stack 2011-09-09 4:43 [PATCH 0/1] segfault in cgit jamie.couture @ 2011-09-09 4:43 ` jamie.couture 2011-09-11 0:44 ` jamie.couture 0 siblings, 1 reply; 13+ messages in thread From: jamie.couture @ 2011-09-09 4:43 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 1/1] move LCS table away from the stack 2011-09-09 4:43 ` [PATCH 1/1] move LCS table away from the stack jamie.couture @ 2011-09-11 0:44 ` jamie.couture 2011-09-11 0:44 ` [PATCH] " jamie.couture 0 siblings, 1 reply; 13+ messages in thread From: jamie.couture @ 2011-09-11 0:44 UTC (permalink / raw) resubmitting patch due to terrible grammar in commit message. ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH] move LCS table away from the stack 2011-09-11 0:44 ` jamie.couture @ 2011-09-11 0:44 ` jamie.couture 2011-09-14 6:38 ` hjemli 0 siblings, 1 reply; 13+ messages in thread From: jamie.couture @ 2011-09-11 0:44 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH] move LCS table away from the stack 2011-09-11 0:44 ` [PATCH] " jamie.couture @ 2011-09-14 6:38 ` hjemli 2011-09-17 22:25 ` [PATCH 1/1] " jamie.couture 0 siblings, 1 reply; 13+ messages in thread From: hjemli @ 2011-09-14 6:38 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 1/1] move LCS table away from the stack 2011-09-14 6:38 ` hjemli @ 2011-09-17 22:25 ` jamie.couture 2012-01-03 15:12 ` hjemli 0 siblings, 1 reply; 13+ messages in thread From: jamie.couture @ 2011-09-17 22:25 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 1/1] move LCS table away from the stack 2011-09-17 22:25 ` [PATCH 1/1] " jamie.couture @ 2012-01-03 15:12 ` hjemli 2012-01-04 8:59 ` normalperson 0 siblings, 1 reply; 13+ messages in thread From: hjemli @ 2012-01-03 15:12 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 1/1] move LCS table away from the stack 2012-01-03 15:12 ` hjemli @ 2012-01-04 8:59 ` normalperson 2012-01-04 16:57 ` jamie.couture 2012-01-12 3:38 ` jamie.couture 0 siblings, 2 replies; 13+ messages in thread From: normalperson @ 2012-01-04 8:59 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 1/1] move LCS table away from the stack 2012-01-04 8:59 ` normalperson @ 2012-01-04 16:57 ` jamie.couture 2012-01-12 3:38 ` jamie.couture 1 sibling, 0 replies; 13+ messages in thread From: jamie.couture @ 2012-01-04 16:57 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 1/1] move LCS table away from the stack 2012-01-04 8:59 ` normalperson 2012-01-04 16:57 ` jamie.couture @ 2012-01-12 3:38 ` jamie.couture 2012-01-12 3:38 ` [PATCH 1/2] correct length check for LCS table jamie.couture 2012-01-12 3:38 ` [PATCH 2/2] use correct type for sizeof jamie.couture 1 sibling, 2 replies; 13+ messages in thread From: jamie.couture @ 2012-01-12 3:38 UTC (permalink / raw) Tested the following patches on Ubuntu 10.10, CentOS 6, RedHat 6 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 1/2] correct length check for LCS table 2012-01-12 3:38 ` jamie.couture @ 2012-01-12 3:38 ` jamie.couture 2012-01-12 3:38 ` [PATCH 2/2] use correct type for sizeof jamie.couture 1 sibling, 0 replies; 13+ messages in thread From: jamie.couture @ 2012-01-12 3:38 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 2/2] use correct type for sizeof 2012-01-12 3:38 ` jamie.couture 2012-01-12 3:38 ` [PATCH 1/2] correct length check for LCS table jamie.couture @ 2012-01-12 3:38 ` jamie.couture 2012-03-18 9:22 ` hjemli 1 sibling, 1 reply; 13+ messages in thread From: jamie.couture @ 2012-01-12 3:38 UTC (permalink / raw) **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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH 2/2] use correct type for sizeof 2012-01-12 3:38 ` [PATCH 2/2] use correct type for sizeof jamie.couture @ 2012-03-18 9:22 ` hjemli 0 siblings, 0 replies; 13+ messages in thread From: hjemli @ 2012-03-18 9:22 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2012-03-18 9:22 UTC | newest] Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2011-09-09 4:43 [PATCH 0/1] segfault in cgit jamie.couture 2011-09-09 4:43 ` [PATCH 1/1] move LCS table away from the stack jamie.couture 2011-09-11 0:44 ` jamie.couture 2011-09-11 0:44 ` [PATCH] " jamie.couture 2011-09-14 6:38 ` hjemli 2011-09-17 22:25 ` [PATCH 1/1] " jamie.couture 2012-01-03 15:12 ` hjemli 2012-01-04 8:59 ` normalperson 2012-01-04 16:57 ` jamie.couture 2012-01-12 3:38 ` jamie.couture 2012-01-12 3:38 ` [PATCH 1/2] correct length check for LCS table jamie.couture 2012-01-12 3:38 ` [PATCH 2/2] use correct type for sizeof jamie.couture 2012-03-18 9:22 ` hjemli
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).