{"thread":{"id":"33359","subject":"[PATCH 0/2] Fixes for undefined behaviour","startedAt":"2013-04-02T19:50:30Z","lastAt":"2013-04-03T19:24:05Z","messageCount":9,"participants":["John Keeping","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"212974","messageId":"cover.1364931627.git.john@keeping.me.uk","threadId":"33359","inReplyTo":null,"subject":"[PATCH 0/2] Fixes for undefined behaviour","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-04-02T19:50:30Z","receivedAt":"2013-04-02T19:50:30Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"I've been playing with Clang's undefined behaviour sanitizer, which\npoints out a few potential issues in Git when running the test suite\n(it's a runtime analysis that is compiled in by setting suitable\nCFLAGS).\n\nThese patches fix one issue that I think we need to worry about and one\nthat's trivial to fix.\n\nThe remaining warnings are:\n\nrefs.c:2426:17: runtime error: index -1 out of bounds for type 'char [8192]'\n\n Caused by a loop walking backwards over the reflog which sets its scan\n pointer to be one before the start of the buffer in order to break out\n of the loop. It seems unlikely that the (stack allocated) buffer will\n be at address zero so I don't think any sane compiler will cause us\n problems here.\n\ntag.c:104:40: runtime error: member access within null pointer of type\n'struct commit'\n\n This does \"&lookup_commit(sha1)->object\" which ends up being okay\n because \"object\" is the first item in struct commit. I'm not sure\n it's worth the churn to change this.\n\nxdiff/xutils.c:308:7: runtime error: load of misaligned address for type\n'unsigned long', which requires 8 byte alignment\n\n This is in the XDL_FAST_HASH code, which should only be used on\n architectures where this is likely to be reasonably fast. The commit\n introducing this code points at an LKML thread[1] discussing a similar\n implementation in the kernel, which discusses the impact of the\n unaligned access, the conclusion being that it's faster than any\n alternative.\n\n[1] https://lkml.org/lkml/2012/3/2/452\n\nJohn Keeping (2):\n diffcore-break: don't divide by zero\n bisect: avoid signed integer overflow\n\n bisect.c | 2 +-\n diffcore-break.c | 3 ++-\n 2 files changed, 3 insertions(+), 2 deletions(-)\n\n-- \n1.8.2.540.gf023cfe\n"},{"id":"212975","messageId":"a2b6c61371ac6ff1e180c6600e57499ff94b2fd2.1364931627.git.john@keeping.me.uk","threadId":"33359","inReplyTo":"cover.1364931627.git.john@keeping.me.uk","subject":"[PATCH 1/2] diffcore-break: don't divide by zero","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-04-02T19:50:31Z","receivedAt":"2013-04-02T19:50:31Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"When the source file is empty, the calculation of the merge score\nresults in a division by zero. Since the merge score is initialized to\nzero, it makes sense to just leave it as it is if the source size is\nzero. This means that we still use the extent of damage metric to\ndecide whether to break the filepair.\n\nSigned-off-by: John Keeping \n---\n diffcore-break.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/diffcore-break.c b/diffcore-break.c\nindex 44f8678..37d8d05 100644\n--- a/diffcore-break.c\n+++ b/diffcore-break.c\n@@ -90,7 +90,8 @@ static int should_break(struct diff_filespec *src,\n \t * merge the surviving pair together if the score is\n \t * less than the minimum, after rename/copy runs.\n \t */\n-\t*merge_score_p = (int)(src_removed * MAX_SCORE / src->size);\n+\tif (src->size)\n+\t\t*merge_score_p = (int)(src_removed * MAX_SCORE / src->size);\n \tif (*merge_score_p > break_score)\n \t\treturn 1;\n \n-- \n1.8.2.540.gf023cfe\n"},{"id":"212976","messageId":"0cb4456948b0874a1cedc5679a7b23b82e755e94.1364931627.git.john@keeping.me.uk","threadId":"33359","inReplyTo":"cover.1364931627.git.john@keeping.me.uk","subject":"[PATCH 2/2] bisect: avoid signed integer overflow","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-04-02T19:50:32Z","receivedAt":"2013-04-02T19:50:32Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"Signed-off-by: John Keeping \n---\n bisect.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex bd1b7b5..0d33c6f 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -526,7 +526,7 @@ struct commit_list *filter_skipped(struct commit_list *list,\n * for this application.\n */\n static int get_prn(int count) {\n-\tcount = count * 1103515245 + 12345;\n+\tcount = ((unsigned) count) * 1103515245 + 12345;\n \treturn ((unsigned)(count/65536) % PRN_MODULO);\n }\n \n-- \n1.8.2.540.gf023cfe\n"},{"id":"212993","messageId":"7vzjxgabd6.fsf@alter.siamese.dyndns.org","threadId":"33359","inReplyTo":"0cb4456948b0874a1cedc5679a7b23b82e755e94.1364931627.git.john@keeping.me.uk","subject":"Re: [PATCH 2/2] bisect: avoid signed integer overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-02T21:09:09Z","receivedAt":"2013-04-02T21:09:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"John Keeping writes:\n\n> Signed-off-by: John Keeping \n> ---\n> bisect.c | 2 +-\n> 1 file changed, 1 insertion(+), 1 deletion(-)\n>\n> diff --git a/bisect.c b/bisect.c\n> index bd1b7b5..0d33c6f 100644\n> --- a/bisect.c\n> +++ b/bisect.c\n> @@ -526,7 +526,7 @@ struct commit_list *filter_skipped(struct commit_list *list,\n> * for this application.\n> */\n> static int get_prn(int count) {\n> -\tcount = count * 1103515245 + 12345;\n> +\tcount = ((unsigned) count) * 1103515245 + 12345;\n> \treturn ((unsigned)(count/65536) % PRN_MODULO);\n\nI wonder\n\n\tstatic int get_prn(unsigned);\n\nor even\n\n\tstatic unsigned get_prn(unsigned);\n\nto lose the existing cast may be a better alternative.\n"},{"id":"212994","messageId":"7vvc84ab2y.fsf@alter.siamese.dyndns.org","threadId":"33359","inReplyTo":"a2b6c61371ac6ff1e180c6600e57499ff94b2fd2.1364931627.git.john@keeping.me.uk","subject":"Re: [PATCH 1/2] diffcore-break: don't divide by zero","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-02T21:15:17Z","receivedAt":"2013-04-02T21:15:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"John Keeping writes:\n\n> When the source file is empty, the calculation of the merge score\n> results in a division by zero. Since the merge score is initialized to\n> zero, it makes sense to just leave it as it is if the source size is\n> zero. This means that we still use the extent of damage metric to\n> decide whether to break the filepair.\n\nWell spotted. An empty blob to another blob that is larger than 400\nbytes will trigger div0, and it makes sense to leave merge-score to\n0 (i.e. do not show as whole-delete-then-whole-add after rename\ndetection is done and the broken filepair is merged back).\n\nActually, if src->size is 0, we probably shouldn't break the filepair\nin the first place. That is, if your preimage and postimage looked\nlike these:\n\n\n == preimage ==\t\t== postimage ==\n\n F (empty file)\t\tF (a large file)\n\t\t\t E (a new empty file)\n\ndo we want to see F renamed to E and then a new file created as F\nwhile running \"git diff -B -M\"? I doubt it.\n\nSo in that sense, this might be a better solution. I dunno.\n\n diffcore-break.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/diffcore-break.c b/diffcore-break.c\nindex 44f8678..eabafd5 100644\n--- a/diffcore-break.c\n+++ b/diffcore-break.c\n@@ -67,6 +67,8 @@ static int should_break(struct diff_filespec *src,\n \tmax_size = ((src->size > dst->size) ? src->size : dst->size);\n \tif (max_size < MINIMUM_BREAK_SIZE)\n \t\treturn 0; /* we do not break too small filepair */\n+\tif (src->size == 0)\n+\t\treturn 0; /* we do not let empty files get renamed */\n \n \tif (diffcore_count_changes(src, dst,\n \t\t\t\t &src->cnt_data, &dst->cnt_data,\n"},{"id":"212997","messageId":"20130402213651.GG2222@serenity.lan","threadId":"33359","inReplyTo":"7vvc84ab2y.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 1/2] diffcore-break: don't divide by zero","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-04-02T21:36:51Z","receivedAt":"2013-04-02T21:36:51Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"On Tue, Apr 02, 2013 at 02:15:17PM -0700, Junio C Hamano wrote:\n> John Keeping writes:\n> \n> > When the source file is empty, the calculation of the merge score\n> > results in a division by zero. Since the merge score is initialized to\n> > zero, it makes sense to just leave it as it is if the source size is\n> > zero. This means that we still use the extent of damage metric to\n> > decide whether to break the filepair.\n> \n> Well spotted. An empty blob to another blob that is larger than 400\n> bytes will trigger div0, and it makes sense to leave merge-score to\n> 0 (i.e. do not show as whole-delete-then-whole-add after rename\n> detection is done and the broken filepair is merged back).\n> \n> Actually, if src->size is 0, we probably shouldn't break the filepair\n> in the first place. That is, if your preimage and postimage looked\n> like these:\n> \n> \n> == preimage ==\t\t== postimage ==\n> \n> F (empty file)\t\tF (a large file)\n> \t\t\t E (a new empty file)\n> \n> do we want to see F renamed to E and then a new file created as F\n> while running \"git diff -B -M\"? I doubt it.\n> \n> So in that sense, this might be a better solution. I dunno.\n\nI considered this, but didn't quite understand the code well enough to\nbe sure that was the right thing to do. Does it make sense to bail out\nearly if dst->size is zero as well?\n\nThe message for commit 6dd4b66 (Fix diffcore-break total breakage)\nindicates that \"don't bother to break small files\" is wrong in some\ncases, but it I wonder if \"don't bother to break empty files\" is okay.\n\n> diffcore-break.c | 2 ++\n> 1 file changed, 2 insertions(+)\n> \n> diff --git a/diffcore-break.c b/diffcore-break.c\n> index 44f8678..eabafd5 100644\n> --- a/diffcore-break.c\n> +++ b/diffcore-break.c\n> @@ -67,6 +67,8 @@ static int should_break(struct diff_filespec *src,\n> \tmax_size = ((src->size > dst->size) ? src->size : dst->size);\n> \tif (max_size < MINIMUM_BREAK_SIZE)\n> \t\treturn 0; /* we do not break too small filepair */\n> +\tif (src->size == 0)\n> +\t\treturn 0; /* we do not let empty files get renamed */\n> \n> \tif (diffcore_count_changes(src, dst,\n> \t\t\t\t &src->cnt_data, &dst->cnt_data,\n"},{"id":"213007","messageId":"7va9pga73t.fsf@alter.siamese.dyndns.org","threadId":"33359","inReplyTo":"20130402213651.GG2222@serenity.lan","subject":"Re: [PATCH 1/2] diffcore-break: don't divide by zero","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-02T22:41:10Z","receivedAt":"2013-04-02T22:41:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"John Keeping writes:\n\n> The message for commit 6dd4b66 (Fix diffcore-break total breakage)\n> indicates that \"don't bother to break small files\" is wrong in some\n> cases, but it I wonder if \"don't bother to break empty files\" is okay.\n\nThis has a rather subtle ramifications, and we would need to think\ncarefully. \"break\" does two very different things, and the criteria\nyou would want to use to decide to \"break\" a filepair depends on\nwhich one you are interested in.\n\nThe very original motivation of \"break\" was to show a patch that\nrewrites an existing file completely in a way different from the\nusual \"diff -u\" output, which will try to minimize the output by\nfinding (rare) lines that happen to be the same between the preimage\nand postimage, intersparsed in many lines of \"-\" (deletion) and \"+\"\n(addition). Such a change is often easier to understand when shown\nas a single block of \"-\" (deletion) of the entire original contents,\nfollowed by a single block of \"+\" (addition) of the entire new\ncontents.\n\nA totally separate motivation of \"break\" is the one Linus talks\nabout in the log message of the said commit. A path filename.h was\nmoved to filename_32.h, and a new (and much smaller) filename.h was\nintroduced, that \"#include\"s filename_32.h. \"diff -M\" that pairs\ndeleted files with created files to compute renames in such a case\nwould not consider the original filename.h as a possible source of\nfilename_32.h that was created. You want to break modification of\nfilename.h into (virtual) deletion and addition of filename.h.\n\nFor the purpose of the former, you would want not to break a file\ntoo aggressively. If you started from a file with 1000 lines in it,\nand deleted 910 lines and added 10 lines to result in a file with\n100 lines, you still have 90 lines of shared contents between the\npreimage and the postimage, and you do not want to show it as\n\"delete 1000 lines and add 100 lines\". You would want to base your\ndecision on how much common material exists between the two.\n\nFor the purpose of the latter, however, it is better to err on the\nside of breaking than not breaking. After breaking a suspicious\nmodification into addition and deletion, if rename comparison does\nnot find a suitable destination for the virtual deletion, the broken\nhalves will be merged back, so breaking too little can hurt by\nmissing potential renames, but breaking too much will not. You do\nwant to break the \"900 deleted out of 1000 and then added 10\" case,\nas that 900 lines may have gone to another file that was created in\nthe same commit. \"But we have 90 lines of common material\" does not\nmatter for the decision to break.\n\nIn today's code, the return value of should_break() is about the\nlatter, while the score it stores in *merge_score is about the\nformer.\n"},{"id":"213058","messageId":"20130403191755.GI2222@serenity.lan","threadId":"33359","inReplyTo":"7vzjxgabd6.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 2/2] bisect: avoid signed integer overflow","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-04-03T19:17:55Z","receivedAt":"2013-04-03T19:17:55Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"\nSigned-off-by: John Keeping \n---\nChanges since v1:\n- Change the function signature instead of casting a value in the\n function.\n- This lets us remove an existing cast.\n\n bisect.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex bd1b7b5..374d9e2 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -525,9 +525,9 @@ struct commit_list *filter_skipped(struct commit_list *list,\n * is increased by one between each call, but that should not matter\n * for this application.\n */\n-static int get_prn(int count) {\n+static unsigned get_prn(unsigned count) {\n \tcount = count * 1103515245 + 12345;\n-\treturn ((unsigned)(count/65536) % PRN_MODULO);\n+\treturn (count/65536) % PRN_MODULO;\n }\n \n /*\n-- \n1.8.2.540.gf023cfe\n"},{"id":"213059","messageId":"20130403192405.GJ2222@serenity.lan","threadId":"33359","inReplyTo":"7va9pga73t.fsf@alter.siamese.dyndns.org","subject":"[PATCH v2] diffcore-break: don't divide by zero","fromName":"John Keeping","fromEmail":"john@keeping.me.uk","sentAt":"2013-04-03T19:24:05Z","receivedAt":"2013-04-03T19:24:05Z","isPatch":true,"sender":{"key":"john@keeping.me.uk","avatar":"https://avatars.githubusercontent.com/u/1702081?v=4"},"body":"When the source file is empty, the calculation of the merge score\nresults in a division by zero. In the situation:\n\n == preimage == == postimage ==\n\n F (empty file) F (a large file)\n E (a new empty file)\n\nit does not make sense to consider F->E as a rename, so it is better not\nto break the pre- and post-image of F.\n\nBail out early in this case to avoid hitting the divide-by-zero. This\ncauses the merge score to be left at zero.\n\nSigned-off-by: John Keeping \n---\nOn Tue, Apr 02, 2013 at 03:41:10PM -0700, Junio C Hamano wrote:\n> John Keeping writes:\n> \n> > The message for commit 6dd4b66 (Fix diffcore-break total breakage)\n> > indicates that \"don't bother to break small files\" is wrong in some\n> > cases, but it I wonder if \"don't bother to break empty files\" is okay.\n> \n> This has a rather subtle ramifications, and we would need to think\n> carefully. \"break\" does two very different things, and the criteria\n> you would want to use to decide to \"break\" a filepair depends on\n> which one you are interested in.\n> \n> The very original motivation of \"break\" was to show a patch that\n> rewrites an existing file completely in a way different from the\n> usual \"diff -u\" output, which will try to minimize the output by\n> finding (rare) lines that happen to be the same between the preimage\n> and postimage, intersparsed in many lines of \"-\" (deletion) and \"+\"\n> (addition). Such a change is often easier to understand when shown\n> as a single block of \"-\" (deletion) of the entire original contents,\n> followed by a single block of \"+\" (addition) of the entire new\n> contents.\n> \n> A totally separate motivation of \"break\" is the one Linus talks\n> about in the log message of the said commit. A path filename.h was\n> moved to filename_32.h, and a new (and much smaller) filename.h was\n> introduced, that \"#include\"s filename_32.h. \"diff -M\" that pairs\n> deleted files with created files to compute renames in such a case\n> would not consider the original filename.h as a possible source of\n> filename_32.h that was created. You want to break modification of\n> filename.h into (virtual) deletion and addition of filename.h.\n> \n> For the purpose of the former, you would want not to break a file\n> too aggressively. If you started from a file with 1000 lines in it,\n> and deleted 910 lines and added 10 lines to result in a file with\n> 100 lines, you still have 90 lines of shared contents between the\n> preimage and the postimage, and you do not want to show it as\n> \"delete 1000 lines and add 100 lines\". You would want to base your\n> decision on how much common material exists between the two.\n> \n> For the purpose of the latter, however, it is better to err on the\n> side of breaking than not breaking. After breaking a suspicious\n> modification into addition and deletion, if rename comparison does\n> not find a suitable destination for the virtual deletion, the broken\n> halves will be merged back, so breaking too little can hurt by\n> missing potential renames, but breaking too much will not. You do\n> want to break the \"900 deleted out of 1000 and then added 10\" case,\n> as that 900 lines may have gone to another file that was created in\n> the same commit. \"But we have 90 lines of common material\" does not\n> matter for the decision to break.\n> \n> In today's code, the return value of should_break() is about the\n> latter, while the score it stores in *merge_score is about the\n> former.\n\nThanks for this explanation. Following it through, it seems that\nbailing out early when the destination is empty will do the wrong thing,\nwhereas letting the code carry on should result in a merge score of\nMAX_SCORE and the function returning 1.\n\nSo it seems that the patch you proposed is the best way to handle this.\n\n diffcore-break.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/diffcore-break.c b/diffcore-break.c\nindex 44f8678..1d9e530 100644\n--- a/diffcore-break.c\n+++ b/diffcore-break.c\n@@ -68,6 +68,9 @@ static int should_break(struct diff_filespec *src,\n \tif (max_size < MINIMUM_BREAK_SIZE)\n \t\treturn 0; /* we do not break too small filepair */\n \n+\tif (!src->size)\n+\t\treturn 0; /* we do not let empty files get renamed */\n+\n \tif (diffcore_count_changes(src, dst,\n \t\t\t\t &src->cnt_data, &dst->cnt_data,\n \t\t\t\t 0,\n-- \n1.8.2.540.gf023cfe\n"}]}