{"thread":{"id":"3842","subject":"[PATCH] Implement --fuzz= option for git-apply.","startedAt":"2006-04-10T02:41:44Z","lastAt":"2006-04-13T12:02:51Z","messageCount":8,"participants":["Eric W. Biederman","Linus Torvalds","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"18525","messageId":"m1d5fqi23b.fsf@ebiederm.dsl.xmission.com","threadId":"3842","inReplyTo":null,"subject":"[PATCH] Implement --fuzz= option for git-apply.","fromName":"Eric W. Biederman","fromEmail":"ebiederm@xmission.com","sentAt":"2006-04-10T02:41:44Z","receivedAt":"2006-04-10T02:41:44Z","isPatch":true,"sender":{"key":"ebiederm@xmission.com","avatar":"https://avatars.githubusercontent.com/u/7477136?v=4"},"body":"\nCurrently to import the -mm tree I have to work around\ngit-apply by using patch.  Because some of Andrews\npatches in quilt will only apply with fuzz.\n\nAllow git-apply to handle fuzz makes it much easier to import\nthe -mm tree into git.  I am still only processing about 1.5 patch a\nsecond which for the 692 patches in 2.6.17-rc1-mm2 is still painful\nbut it does help.\n\nIf I just apply the patches and don't run git-mailinfo\ngit-write-tree, and git-write-commit I get about 4 patches\nper second.\n\nThis patch defaults to leaving fuzz processing off so if you don't\nwant patches that only apply with fuzz you won't get them.\n\nIf a patch does require fuzz to apply you will get a warning:\n> Fragment applied at offset: +-#lines (fuzz: #context_lines_deleted)\n\ndiff --git a/apply.c b/apply.c\nindex 33b4271..a07503f 100644\n--- a/apply.c\n+++ b/apply.c\n@@ -32,8 +32,9 @@ static int apply = 1;\n static int no_add = 0;\n static int show_index_info = 0;\n static int line_termination = '\\n';\n+static int p_fuzz = 0;\n static const char apply_usage[] =\n-\"git-apply [--stat] [--numstat] [--summary] [--check] [--index] [--apply] [--no-add] [--index-info] [--allow-binary-replacement] [-z] [-pNUM] [--whitespace=<nowarn|warn|error|error-all|strip>] <patch>...\";\n+\"git-apply [--stat] [--numstat] [--summary] [--check] [--index] [--apply] [--no-add] [--index-info] [--allow-binary-replacement] [-z] [-pNUM] [--fuzz=NUM] [--whitespace=<nowarn|warn|error|error-all|strip>] <patch>...\";\n \n static enum whitespace_eol {\n \tnowarn_whitespace,\n@@ -100,6 +101,7 @@ static int max_change, max_len;\n static int linenr = 1;\n \n struct fragment {\n+\tunsigned long context;\n \tunsigned long oldpos, oldlines;\n \tunsigned long newpos, newlines;\n \tconst char *patch;\n@@ -817,12 +819,15 @@ static int parse_fragment(char *line, un\n \tint added, deleted;\n \tint len = linelen(line, size), offset;\n \tunsigned long oldlines, newlines;\n+\tunsigned long leading, trailing;\n \n \toffset = parse_fragment_header(line, len, fragment);\n \tif (offset < 0)\n \t\treturn -1;\n \toldlines = fragment->oldlines;\n \tnewlines = fragment->newlines;\n+\tleading = 0;\n+\ttrailing = 0;\n \n \tif (patch->is_new < 0) {\n \t\tpatch->is_new =  !oldlines;\n@@ -860,10 +865,14 @@ static int parse_fragment(char *line, un\n \t\tcase ' ':\n \t\t\toldlines--;\n \t\t\tnewlines--;\n+\t\t\tif (!deleted && !added)\n+\t\t\t\tleading++;\n+\t\t\ttrailing++;\n \t\t\tbreak;\n \t\tcase '-':\n \t\t\tdeleted++;\n \t\t\toldlines--;\n+\t\t\ttrailing = 0;\n \t\t\tbreak;\n \t\tcase '+':\n \t\t\t/*\n@@ -887,6 +896,7 @@ static int parse_fragment(char *line, un\n \t\t\t}\n \t\t\tadded++;\n \t\t\tnewlines--;\n+\t\t\ttrailing = 0;\n \t\t\tbreak;\n \n                 /* We allow \"\\ No newline at end of file\". Depending\n@@ -904,6 +914,10 @@ static int parse_fragment(char *line, un\n \t}\n \tif (oldlines || newlines)\n \t\treturn -1;\n+\tfragment->context = leading;\n+\tif (leading > trailing)\n+\t\tfragment->context = trailing;\n+\n \t/* If a fragment ends with an incomplete line, we failed to include\n \t * it in the above loop because we hit oldlines == newlines == 0\n \t * before seeing it.\n@@ -1087,7 +1101,7 @@ static int read_old_data(struct stat *st\n \t}\n }\n \n-static int find_offset(const char *buf, unsigned long size, const char *fragment, unsigned long fragsize, int line)\n+static int find_offset(const char *buf, unsigned long size, const char *fragment, unsigned long fragsize, int line, int *lines)\n {\n \tint i;\n \tunsigned long start, backwards, forwards;\n@@ -1148,6 +1162,7 @@ static int find_offset(const char *buf, \n \t\tn = (i >> 1)+1;\n \t\tif (i & 1)\n \t\t\tn = -n;\n+\t\t*lines = n;\n \t\treturn try;\n \t}\n \n@@ -1155,6 +1170,31 @@ static int find_offset(const char *buf, \n \t * We should start searching forward and backward.\n \t */\n \treturn -1;\n+}\n+\n+static void reduce_context(char **buf, int *size)\n+{\n+\tchar *ctx = *buf;\n+\tunsigned long ctxsize = *size;\n+\tunsigned long offset;\n+\n+\t/* Remove the first line */\n+\toffset = 0;\n+\twhile (offset <= ctxsize) {\n+\t\tif (ctx[offset++] == '\\n')\n+\t\t\tbreak;\n+\t}\n+\tctxsize -= offset;\n+\tctx += offset;\n+\t/* Remove the last line */\n+\toffset = ctxsize - 1;\n+\twhile (offset > 0) {\n+\t\tif (ctx[--offset] == '\\n')\n+\t\t\tbreak;\n+\t}\n+\tctxsize = offset + 1;\n+\t*buf = ctx;\n+\t*size = ctxsize;\n }\n \n struct buffer_desc {\n@@ -1192,7 +1232,10 @@ static int apply_one_fragment(struct buf\n \tint offset, size = frag->size;\n \tchar *old = xmalloc(size);\n \tchar *new = xmalloc(size);\n-\tint oldsize = 0, newsize = 0;\n+\tchar *ctx;\n+\tint oldsize = 0, newsize = 0, ctxsize;\n+\tint lines;\n+\tint fuzz, max_fuzz;\n \n \twhile (size > 0) {\n \t\tint len = linelen(patch, size);\n@@ -1241,23 +1284,39 @@ #ifdef NO_ACCURATE_DIFF\n \t\tnewsize--;\n \t}\n #endif\n+\n+\toffset = -1; /* shutup gcc */\n+\tctx = old;\n+\tctxsize = oldsize;\n+\tlines = 0;\n+\tmax_fuzz = (p_fuzz < frag->context) ? p_fuzz : frag->context;\n+\tfor (fuzz = 0; fuzz <= max_fuzz; fuzz++) {\n+\t\t/* Reduce the number of context lines */\n+\t\tif (fuzz) \n+\t\t\treduce_context(&ctx, &ctxsize);\n+\t\toffset = find_offset(buf, desc->size, ctx, ctxsize, frag->newpos + fuzz, &lines);\n+\t\tif (offset >= 0) {\n+\t\t\tint diff = newsize - ctxsize;\n+\t\t\tunsigned long size = desc->size + diff;\n+\t\t\tunsigned long alloc = desc->alloc;\n+\n+\t\t\tif (fuzz)\n+\t\t\t\tfprintf(stderr, \"Fragment applied at offset: %d (fuzz: %d)\\n\",\n+\t\t\t\t\tlines, fuzz);\n+\n+\t\t\tif (size > alloc) {\n+\t\t\t\talloc = size + 8192;\n+\t\t\t\tdesc->alloc = alloc;\n+\t\t\t\tbuf = xrealloc(buf, alloc);\n+\t\t\t\tdesc->buffer = buf;\n+\t\t\t}\n+\t\t\tdesc->size = size;\n+\t\t\tmemmove(buf + offset + newsize, buf + offset + ctxsize, size - offset - newsize);\n+\t\t\tmemcpy(buf + offset, new, newsize);\n+\t\t\toffset = 0;\n \t\t\t\n-\toffset = find_offset(buf, desc->size, old, oldsize, frag->newpos);\n-\tif (offset >= 0) {\n-\t\tint diff = newsize - oldsize;\n-\t\tunsigned long size = desc->size + diff;\n-\t\tunsigned long alloc = desc->alloc;\n-\n-\t\tif (size > alloc) {\n-\t\t\talloc = size + 8192;\n-\t\t\tdesc->alloc = alloc;\n-\t\t\tbuf = xrealloc(buf, alloc);\n-\t\t\tdesc->buffer = buf;\n+\t\t\tbreak;\n \t\t}\n-\t\tdesc->size = size;\n-\t\tmemmove(buf + offset + newsize, buf + offset + oldsize, size - offset - newsize);\n-\t\tmemcpy(buf + offset, new, newsize);\n-\t\toffset = 0;\n \t}\n \n \tfree(old);\n@@ -1943,6 +2002,10 @@ int main(int argc, char **argv)\n \t\t}\n \t\tif (!strcmp(arg, \"-z\")) {\n \t\t\tline_termination = 0;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strncmp(arg, \"--fuzz=\", 7)) {\n+\t\t\tp_fuzz = atoi(arg + 7);\n \t\t\tcontinue;\n \t\t}\n \t\tif (!strncmp(arg, \"--whitespace=\", 13)) {\n"},{"id":"18530","messageId":"m13bgmht9v.fsf@ebiederm.dsl.xmission.com","threadId":"3842","inReplyTo":"m1d5fqi23b.fsf@ebiederm.dsl.xmission.com","subject":"Re: [PATCH] Implement --fuzz= option for git-apply.","fromName":"Eric W. Biederman","fromEmail":"ebiederm@xmission.com","sentAt":"2006-04-10T05:52:12Z","receivedAt":"2006-04-10T05:52:12Z","isPatch":true,"sender":{"key":"ebiederm@xmission.com","avatar":"https://avatars.githubusercontent.com/u/7477136?v=4"},"body":"ebiederm@xmission.com (Eric W. Biederman) writes:\n\n> Currently to import the -mm tree I have to work around\n> git-apply by using patch.  Because some of Andrews\n> patches in quilt will only apply with fuzz.\n>\n> Allow git-apply to handle fuzz makes it much easier to import\n> the -mm tree into git.  I am still only processing about 1.5 patch a\n> second which for the 692 patches in 2.6.17-rc1-mm2 is still painful\n> but it does help.\n>\n> If I just apply the patches and don't run git-mailinfo\n> git-write-tree, and git-write-commit I get about 4 patches\n> per second.\n>\n> This patch defaults to leaving fuzz processing off so if you don't\n> want patches that only apply with fuzz you won't get them.\n>\n> If a patch does require fuzz to apply you will get a warning:\n>> Fragment applied at offset: +-#lines (fuzz: #context_lines_deleted)\n\nBother I almost had it right the first time.\nI forgot to remove the context lines from the new lines that we\napply, in addition to the old lines that we remove.  This updated\npatch fixes that problem.\n\nContext lines patching themselves in is a weird bug.\n\nEric\n\n\ndiff --git a/apply.c b/apply.c\nindex 33b4271..4faf365 100644\n--- a/apply.c\n+++ b/apply.c\n@@ -32,8 +32,9 @@ static int apply = 1;\n static int no_add = 0;\n static int show_index_info = 0;\n static int line_termination = '\\n';\n+static int p_fuzz = 0;\n static const char apply_usage[] =\n-\"git-apply [--stat] [--numstat] [--summary] [--check] [--index] [--apply] [--no-add] [--index-info] [--allow-binary-replacement] [-z] [-pNUM] [--whitespace=<nowarn|warn|error|error-all|strip>] <patch>...\";\n+\"git-apply [--stat] [--numstat] [--summary] [--check] [--index] [--apply] [--no-add] [--index-info] [--allow-binary-replacement] [-z] [-pNUM] [--fuzz=NUM] [--whitespace=<nowarn|warn|error|error-all|strip>] <patch>...\";\n \n static enum whitespace_eol {\n \tnowarn_whitespace,\n@@ -100,6 +101,7 @@ static int max_change, max_len;\n static int linenr = 1;\n \n struct fragment {\n+\tunsigned long context;\n \tunsigned long oldpos, oldlines;\n \tunsigned long newpos, newlines;\n \tconst char *patch;\n@@ -817,12 +819,15 @@ static int parse_fragment(char *line, un\n \tint added, deleted;\n \tint len = linelen(line, size), offset;\n \tunsigned long oldlines, newlines;\n+\tunsigned long leading, trailing;\n \n \toffset = parse_fragment_header(line, len, fragment);\n \tif (offset < 0)\n \t\treturn -1;\n \toldlines = fragment->oldlines;\n \tnewlines = fragment->newlines;\n+\tleading = 0;\n+\ttrailing = 0;\n \n \tif (patch->is_new < 0) {\n \t\tpatch->is_new =  !oldlines;\n@@ -860,10 +865,14 @@ static int parse_fragment(char *line, un\n \t\tcase ' ':\n \t\t\toldlines--;\n \t\t\tnewlines--;\n+\t\t\tif (!deleted && !added)\n+\t\t\t\tleading++;\n+\t\t\ttrailing++;\n \t\t\tbreak;\n \t\tcase '-':\n \t\t\tdeleted++;\n \t\t\toldlines--;\n+\t\t\ttrailing = 0;\n \t\t\tbreak;\n \t\tcase '+':\n \t\t\t/*\n@@ -887,6 +896,7 @@ static int parse_fragment(char *line, un\n \t\t\t}\n \t\t\tadded++;\n \t\t\tnewlines--;\n+\t\t\ttrailing = 0;\n \t\t\tbreak;\n \n                 /* We allow \"\\ No newline at end of file\". Depending\n@@ -904,6 +914,10 @@ static int parse_fragment(char *line, un\n \t}\n \tif (oldlines || newlines)\n \t\treturn -1;\n+\tfragment->context = leading;\n+\tif (leading > trailing)\n+\t\tfragment->context = trailing;\n+\n \t/* If a fragment ends with an incomplete line, we failed to include\n \t * it in the above loop because we hit oldlines == newlines == 0\n \t * before seeing it.\n@@ -1087,7 +1101,7 @@ static int read_old_data(struct stat *st\n \t}\n }\n \n-static int find_offset(const char *buf, unsigned long size, const char *fragment, unsigned long fragsize, int line)\n+static int find_offset(const char *buf, unsigned long size, const char *fragment, unsigned long fragsize, int line, int *lines)\n {\n \tint i;\n \tunsigned long start, backwards, forwards;\n@@ -1148,6 +1162,7 @@ static int find_offset(const char *buf, \n \t\tn = (i >> 1)+1;\n \t\tif (i & 1)\n \t\t\tn = -n;\n+\t\t*lines = n;\n \t\treturn try;\n \t}\n \n@@ -1155,6 +1170,31 @@ static int find_offset(const char *buf, \n \t * We should start searching forward and backward.\n \t */\n \treturn -1;\n+}\n+\n+static void reduce_context(char **buf, int *size)\n+{\n+\tchar *ctx = *buf;\n+\tunsigned long ctxsize = *size;\n+\tunsigned long offset;\n+\n+\t/* Remove the first line */\n+\toffset = 0;\n+\twhile (offset <= ctxsize) {\n+\t\tif (ctx[offset++] == '\\n')\n+\t\t\tbreak;\n+\t}\n+\tctxsize -= offset;\n+\tctx += offset;\n+\t/* Remove the last line */\n+\toffset = ctxsize - 1;\n+\twhile (offset > 0) {\n+\t\tif (ctx[--offset] == '\\n')\n+\t\t\tbreak;\n+\t}\n+\tctxsize = offset + 1;\n+\t*buf = ctx;\n+\t*size = ctxsize;\n }\n \n struct buffer_desc {\n@@ -1192,7 +1232,10 @@ static int apply_one_fragment(struct buf\n \tint offset, size = frag->size;\n \tchar *old = xmalloc(size);\n \tchar *new = xmalloc(size);\n+\tchar *oldlines, *newlines;\n \tint oldsize = 0, newsize = 0;\n+\tint lines;\n+\tint fuzz, max_fuzz;\n \n \twhile (size > 0) {\n \t\tint len = linelen(patch, size);\n@@ -1241,23 +1284,42 @@ #ifdef NO_ACCURATE_DIFF\n \t\tnewsize--;\n \t}\n #endif\n+\n+\toffset = -1; /* shutup gcc */\n+\toldlines = old;\n+\tnewlines = new;\n+\tlines = 0;\n+\tmax_fuzz = (p_fuzz < frag->context) ? p_fuzz : frag->context;\n+\tfor (fuzz = 0; fuzz <= max_fuzz; fuzz++) {\n+\t\t/* Reduce the number of context lines */\n+\t\tif (fuzz) {\n+\t\t\treduce_context(&oldlines, &oldsize);\n+\t\t\treduce_context(&newlines, &newsize);\n+\t\t}\n \t\t\t\n-\toffset = find_offset(buf, desc->size, old, oldsize, frag->newpos);\n-\tif (offset >= 0) {\n-\t\tint diff = newsize - oldsize;\n-\t\tunsigned long size = desc->size + diff;\n-\t\tunsigned long alloc = desc->alloc;\n-\n-\t\tif (size > alloc) {\n-\t\t\talloc = size + 8192;\n-\t\t\tdesc->alloc = alloc;\n-\t\t\tbuf = xrealloc(buf, alloc);\n-\t\t\tdesc->buffer = buf;\n+\t\toffset = find_offset(buf, desc->size, oldlines, oldsize, frag->newpos + fuzz, &lines);\n+\t\tif (offset >= 0) {\n+\t\t\tint diff = newsize - oldsize;\n+\t\t\tunsigned long size = desc->size + diff;\n+\t\t\tunsigned long alloc = desc->alloc;\n+\n+\t\t\tif (fuzz)\n+\t\t\t\tfprintf(stderr, \"Fragment applied at offset: %d (fuzz: %d)\\n\",\n+\t\t\t\t\tlines, fuzz);\n+\n+\t\t\tif (size > alloc) {\n+\t\t\t\talloc = size + 8192;\n+\t\t\t\tdesc->alloc = alloc;\n+\t\t\t\tbuf = xrealloc(buf, alloc);\n+\t\t\t\tdesc->buffer = buf;\n+\t\t\t}\n+\t\t\tdesc->size = size;\n+\t\t\tmemmove(buf + offset + newsize, buf + offset + oldsize, size - offset - newsize);\n+\t\t\tmemcpy(buf + offset, newlines, newsize);\n+\t\t\toffset = 0;\n+\t\t\t\n+\t\t\tbreak;\n \t\t}\n-\t\tdesc->size = size;\n-\t\tmemmove(buf + offset + newsize, buf + offset + oldsize, size - offset - newsize);\n-\t\tmemcpy(buf + offset, new, newsize);\n-\t\toffset = 0;\n \t}\n \n \tfree(old);\n@@ -1943,6 +2005,10 @@ int main(int argc, char **argv)\n \t\t}\n \t\tif (!strcmp(arg, \"-z\")) {\n \t\t\tline_termination = 0;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strncmp(arg, \"--fuzz=\", 7)) {\n+\t\t\tp_fuzz = atoi(arg + 7);\n \t\t\tcontinue;\n \t\t}\n \t\tif (!strncmp(arg, \"--whitespace=\", 13)) {\n"},{"id":"18539","messageId":"m1irphhj1p.fsf_-_@ebiederm.dsl.xmission.com","threadId":"3842","inReplyTo":"m13bgmht9v.fsf@ebiederm.dsl.xmission.com","subject":"[PATCH] Implement limited context matching in git-apply.","fromName":"Eric W. Biederman","fromEmail":"ebiederm@xmission.com","sentAt":"2006-04-10T09:33:06Z","receivedAt":"2006-04-10T09:33:06Z","isPatch":true,"sender":{"key":"ebiederm@xmission.com","avatar":"https://avatars.githubusercontent.com/u/7477136?v=4"},"body":"\nOk this really should be the good version.  The option\nhandling has been reworked to be automation safe.\n\nCurrently to import the -mm tree I have to work around\ngit-apply by using patch.  Because some of Andrews\npatches in quilt will only apply with fuzz.\n\nI started out implementing a --fuzz option and then I realized\nfuzz is not a very safe concept for an automated system.  What\nyou really want is a minimum number of context lines that must\nmatch.  This allows policy to be set without knowing how many\nlines of context a patch actually provides.   By default\nthe policy remains to match all provided lines of context.\n\nAllowng git-apply to match a restricted set of context makes\nit much easier to import the -mm tree into git.  I am still only\nprocessing  1.5 to 1.6 patches a second for the 692 patches in\n2.6.17-rc1-mm2 is still painful but it does help.\n\nIf I just loop through all of Andrews patches in order\nand run git-apply --index -C1 I process the entire patchset\nin 1m53s or about 6 patches per second.  So running\ngit-mailinfo, git-write-tree, git-commit-tree, and\ngit-update-ref everytime has a measurable impact,\nand shows things can be speeded up even more.\n\nAll of these timings were taking on my poor 700Mhz Athlon\nwith 512MB of ram.  So people with fast machiens should\nsee much better performance.\n\nWhen a match is found after the number of context are reduced a\nwarning is generated.  Since this is a rare event and possibly\ndangerous this seems to make sense.  Unless you are patching\na single file the error message is a little bit terse at\nthe moment, but it should be easy to go back and fix.\n\nI have also updated the documentation for git-apply to reflect\nthe new -C option that sets the minimum number of context\nlines that must match.\n\nSigned-off-by: Eric W. Biederman <ebiederm@xmission.com>\n\n\n---\n\n Documentation/git-apply.txt |    8 ++-\n apply.c                     |  121 +++++++++++++++++++++++++++++++++++++------\n 2 files changed, 111 insertions(+), 18 deletions(-)\n\n6b3a4565b760664a9b72096dd5eea8be9e1d1311\ndiff --git a/Documentation/git-apply.txt b/Documentation/git-apply.txt\nindex 1c64a1a..e93ea1f 100644\n--- a/Documentation/git-apply.txt\n+++ b/Documentation/git-apply.txt\n@@ -11,7 +11,7 @@ SYNOPSIS\n [verse]\n 'git-apply' [--stat] [--numstat] [--summary] [--check] [--index] [--apply]\n \t  [--no-add] [--index-info] [--allow-binary-replacement] [-z] [-pNUM]\n-\t  [--whitespace=<nowarn|warn|error|error-all|strip>]\n+\t  [-CNUM] [--whitespace=<nowarn|warn|error|error-all|strip>]\n \t  [<patch>...]\n \n DESCRIPTION\n@@ -72,6 +72,12 @@ OPTIONS\n -p<n>::\n \tRemove <n> leading slashes from traditional diff paths. The\n \tdefault is 1.\n+\n+-C<n>::\n+\tEnsure at least <n> lines of surrounding context match before\n+\tand after each change.  When fewer lines of surrounding\n+\tcontext exist they all most match.  By default no context is\n+\tever ignored.\n \n --apply::\n \tIf you use any of the options marked ``Turns off\ndiff --git a/apply.c b/apply.c\nindex 33b4271..147a919 100644\n--- a/apply.c\n+++ b/apply.c\n@@ -32,8 +32,9 @@ static int apply = 1;\n static int no_add = 0;\n static int show_index_info = 0;\n static int line_termination = '\\n';\n+static unsigned long p_context = -1;\n static const char apply_usage[] =\n-\"git-apply [--stat] [--numstat] [--summary] [--check] [--index] [--apply] [--no-add] [--index-info] [--allow-binary-replacement] [-z] [-pNUM] [--whitespace=<nowarn|warn|error|error-all|strip>] <patch>...\";\n+\"git-apply [--stat] [--numstat] [--summary] [--check] [--index] [--apply] [--no-add] [--index-info] [--allow-binary-replacement] [-z] [-pNUM] [-CNUM] [--whitespace=<nowarn|warn|error|error-all|strip>] <patch>...\";\n \n static enum whitespace_eol {\n \tnowarn_whitespace,\n@@ -100,6 +101,7 @@ static int max_change, max_len;\n static int linenr = 1;\n \n struct fragment {\n+\tunsigned long leading, trailing;\n \tunsigned long oldpos, oldlines;\n \tunsigned long newpos, newlines;\n \tconst char *patch;\n@@ -817,12 +819,15 @@ static int parse_fragment(char *line, un\n \tint added, deleted;\n \tint len = linelen(line, size), offset;\n \tunsigned long oldlines, newlines;\n+\tunsigned long leading, trailing;\n \n \toffset = parse_fragment_header(line, len, fragment);\n \tif (offset < 0)\n \t\treturn -1;\n \toldlines = fragment->oldlines;\n \tnewlines = fragment->newlines;\n+\tleading = 0;\n+\ttrailing = 0;\n \n \tif (patch->is_new < 0) {\n \t\tpatch->is_new =  !oldlines;\n@@ -860,10 +865,14 @@ static int parse_fragment(char *line, un\n \t\tcase ' ':\n \t\t\toldlines--;\n \t\t\tnewlines--;\n+\t\t\tif (!deleted && !added)\n+\t\t\t\tleading++;\n+\t\t\ttrailing++;\n \t\t\tbreak;\n \t\tcase '-':\n \t\t\tdeleted++;\n \t\t\toldlines--;\n+\t\t\ttrailing = 0;\n \t\t\tbreak;\n \t\tcase '+':\n \t\t\t/*\n@@ -887,6 +896,7 @@ static int parse_fragment(char *line, un\n \t\t\t}\n \t\t\tadded++;\n \t\t\tnewlines--;\n+\t\t\ttrailing = 0;\n \t\t\tbreak;\n \n                 /* We allow \"\\ No newline at end of file\". Depending\n@@ -904,6 +914,9 @@ static int parse_fragment(char *line, un\n \t}\n \tif (oldlines || newlines)\n \t\treturn -1;\n+\tfragment->leading = leading;\n+\tfragment->trailing = trailing;\n+\n \t/* If a fragment ends with an incomplete line, we failed to include\n \t * it in the above loop because we hit oldlines == newlines == 0\n \t * before seeing it.\n@@ -1087,7 +1100,7 @@ static int read_old_data(struct stat *st\n \t}\n }\n \n-static int find_offset(const char *buf, unsigned long size, const char *fragment, unsigned long fragsize, int line)\n+static int find_offset(const char *buf, unsigned long size, const char *fragment, unsigned long fragsize, int line, int *lines)\n {\n \tint i;\n \tunsigned long start, backwards, forwards;\n@@ -1148,6 +1161,7 @@ static int find_offset(const char *buf, \n \t\tn = (i >> 1)+1;\n \t\tif (i & 1)\n \t\t\tn = -n;\n+\t\t*lines = n;\n \t\treturn try;\n \t}\n \n@@ -1155,6 +1169,33 @@ static int find_offset(const char *buf, \n \t * We should start searching forward and backward.\n \t */\n \treturn -1;\n+}\n+\n+static void remove_first_line(const char **rbuf, int *rsize)\n+{\n+\tconst char *buf = *rbuf;\n+\tint size = *rsize;\n+\tunsigned long offset;\n+\toffset = 0;\n+\twhile (offset <= size) {\n+\t\tif (buf[offset++] == '\\n')\n+\t\t\tbreak;\n+\t}\n+\t*rsize = size - offset;\n+\t*rbuf = buf + offset;\n+}\n+\n+static void remove_last_line(const char **rbuf, int *rsize)\n+{\n+\tconst char *buf = *rbuf;\n+\tint size = *rsize;\n+\tunsigned long offset;\n+\toffset = size - 1;\n+\twhile (offset > 0) {\n+\t\tif (buf[--offset] == '\\n')\n+\t\t\tbreak;\n+\t}\n+\t*rsize = offset + 1;\n }\n \n struct buffer_desc {\n@@ -1192,7 +1233,10 @@ static int apply_one_fragment(struct buf\n \tint offset, size = frag->size;\n \tchar *old = xmalloc(size);\n \tchar *new = xmalloc(size);\n+\tconst char *oldlines, *newlines;\n \tint oldsize = 0, newsize = 0;\n+\tunsigned long leading, trailing;\n+\tint pos, lines;\n \n \twhile (size > 0) {\n \t\tint len = linelen(patch, size);\n@@ -1241,23 +1285,59 @@ #ifdef NO_ACCURATE_DIFF\n \t\tnewsize--;\n \t}\n #endif\n+\n+\toldlines = old;\n+\tnewlines = new;\n+\tleading = frag->leading;\n+\ttrailing = frag->trailing;\n+\tlines = 0;\n+\tpos = frag->newpos;\n+\tfor (;;) {\n+\t\toffset = find_offset(buf, desc->size, oldlines, oldsize, pos, &lines);\n+\t\tif (offset >= 0) {\n+\t\t\tint diff = newsize - oldsize;\n+\t\t\tunsigned long size = desc->size + diff;\n+\t\t\tunsigned long alloc = desc->alloc;\n+\n+\t\t\t/* Warn if it was necessary to reduce the number \n+\t\t\t * of context lines.\n+\t\t\t */\n+\t\t\tif ((leading != frag->leading) || (trailing != frag->trailing))\n+\t\t\t\tfprintf(stderr, \"Context reduced to (%ld/%ld) to apply fragment at %d\\n\",\n+\t\t\t\t\tleading, trailing, pos + lines);\n+\n+\t\t\tif (size > alloc) {\n+\t\t\t\talloc = size + 8192;\n+\t\t\t\tdesc->alloc = alloc;\n+\t\t\t\tbuf = xrealloc(buf, alloc);\n+\t\t\t\tdesc->buffer = buf;\n+\t\t\t}\n+\t\t\tdesc->size = size;\n+\t\t\tmemmove(buf + offset + newsize, buf + offset + oldsize, size - offset - newsize);\n+\t\t\tmemcpy(buf + offset, newlines, newsize);\n+\t\t\toffset = 0;\n \t\t\t\n-\toffset = find_offset(buf, desc->size, old, oldsize, frag->newpos);\n-\tif (offset >= 0) {\n-\t\tint diff = newsize - oldsize;\n-\t\tunsigned long size = desc->size + diff;\n-\t\tunsigned long alloc = desc->alloc;\n-\n-\t\tif (size > alloc) {\n-\t\t\talloc = size + 8192;\n-\t\t\tdesc->alloc = alloc;\n-\t\t\tbuf = xrealloc(buf, alloc);\n-\t\t\tdesc->buffer = buf;\n+\t\t\tbreak;\n \t\t}\n-\t\tdesc->size = size;\n-\t\tmemmove(buf + offset + newsize, buf + offset + oldsize, size - offset - newsize);\n-\t\tmemcpy(buf + offset, new, newsize);\n-\t\toffset = 0;\n+\n+\t\t/* Am I at my context limits? */\n+\t\tif ((leading <= p_context) && (trailing <= p_context))\n+\t\t\tbreak;\n+\t\t/* Reduce the number of context lines\n+\t\t * Reduce both leading and trailing if they are equal\n+\t\t * otherwise just reduce the larger context.\n+\t\t */\n+\t\tif (leading >= trailing) {\n+\t\t\tremove_first_line(&oldlines, &oldsize);\n+\t\t\tremove_first_line(&newlines, &newsize);\n+\t\t\tpos--;\n+\t\t\tleading--;\n+\t\t}\n+\t\tif (trailing > leading) {\n+\t\t\tremove_last_line(&oldlines, &oldsize);\n+\t\t\tremove_last_line(&newlines, &newsize);\n+\t\t\ttrailing--;\n+\t\t}\n \t}\n \n \tfree(old);\n@@ -1882,6 +1962,7 @@ int main(int argc, char **argv)\n \n \tfor (i = 1; i < argc; i++) {\n \t\tconst char *arg = argv[i];\n+\t\tchar *end;\n \t\tint fd;\n \n \t\tif (!strcmp(arg, \"-\")) {\n@@ -1943,6 +2024,12 @@ int main(int argc, char **argv)\n \t\t}\n \t\tif (!strcmp(arg, \"-z\")) {\n \t\t\tline_termination = 0;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (!strncmp(arg, \"-C\", 2)) {\n+\t\t\tp_context = strtoul(arg + 2, &end, 0);\n+\t\t\tif (*end != '\\0')\n+\t\t\t\tdie(\"unrecognized context count '%s'\", arg + 2);\n \t\t\tcontinue;\n \t\t}\n \t\tif (!strncmp(arg, \"--whitespace=\", 13)) {\n-- \n1.3-rc3.GIT\n"},{"id":"18540","messageId":"Pine.LNX.4.64.0604100821340.9504@g5.osdl.org","threadId":"3842","inReplyTo":"m1irphhj1p.fsf_-_@ebiederm.dsl.xmission.com","subject":"Re: [PATCH] Implement limited context matching in git-apply.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-04-10T15:25:16Z","receivedAt":"2006-04-10T15:25:16Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 10 Apr 2006, Eric W. Biederman wrote:\n> \n> If I just loop through all of Andrews patches in order\n> and run git-apply --index -C1 I process the entire patchset\n> in 1m53s or about 6 patches per second.  So running\n> git-mailinfo, git-write-tree, git-commit-tree, and\n> git-update-ref everytime has a measurable impact,\n> and shows things can be speeded up even more.\n\ngit-write-tree is actually a fairly expensive operation on the kernel. It \nneeds to write the 1000+ tree objects - and while _most_ of them already \nexist (and thus don't actually need to be written out), we need to \ngenerate the tree object and its SHA1 in order to notice that that is the \ncase.\n\nI'm almost certain that 90%+ of the overhead you see is the tree writing, \nnot the rest of the scripting.\n\nYour patch looks ok from a quick read-through:\n\nAcked-by: Linus Torvalds <torvalds@osdl.org>\n\n\t\tLinus\n"},{"id":"18542","messageId":"m1k69xffcz.fsf@ebiederm.dsl.xmission.com","threadId":"3842","inReplyTo":"Pine.LNX.4.64.0604100821340.9504@g5.osdl.org","subject":"Re: [PATCH] Implement limited context matching in git-apply.","fromName":"Eric W. Biederman","fromEmail":"ebiederm@xmission.com","sentAt":"2006-04-10T18:35:40Z","receivedAt":"2006-04-10T18:35:40Z","isPatch":true,"sender":{"key":"ebiederm@xmission.com","avatar":"https://avatars.githubusercontent.com/u/7477136?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> On Mon, 10 Apr 2006, Eric W. Biederman wrote:\n>> \n>> If I just loop through all of Andrews patches in order\n>> and run git-apply --index -C1 I process the entire patchset\n>> in 1m53s or about 6 patches per second.  So running\n>> git-mailinfo, git-write-tree, git-commit-tree, and\n>> git-update-ref everytime has a measurable impact,\n>> and shows things can be speeded up even more.\n>\n> git-write-tree is actually a fairly expensive operation on the kernel. It \n> needs to write the 1000+ tree objects - and while _most_ of them already \n> exist (and thus don't actually need to be written out), we need to \n> generate the tree object and its SHA1 in order to notice that that is the \n> case.\n>\n> I'm almost certain that 90%+ of the overhead you see is the tree writing, \n> not the rest of the scripting.\n\nWell it is easy enough to time.  Looking at the timings\ngoing from just git-apply to git-apply && git-write-tree\ndoes seem to about the double the amount of time taken,\nor take me to about 4 minutes.  With everything else\nin there things happen in the 6-7 minute range with\nin the hot cache scenario.  So write-tree is closer\nto 50% of the overhead.\n\nIs it possible to cache the sha1 of unmodified directories?\n\nIf we did that we could probe to see if the hash already\nexisted before we attempted to look for the subdirectories.\n\nThe pain would is remembering which directory sha1 are\ncurrent.  If nothing else we can modify: \nremove_cache_entry, and add_file_to_cache to clear\nthe parent directories cached sha1 when we update an\nindex entry.  But I keep thinking there should\nbe something more elegant.  Like using ce_flags,\nor comparing mtime values.\n\n...\n\nOk taking a quick look at write-tree to see where\nthe bottle neck is:  \n\nI made two modified versions of write-tree. \n- git-write-tree-nowritetree which calls return just before calling\n    write_tree.\n- git-write-tree-nosha1write which does everything except call\n    sha1_file_write.\n\nWith just git-apply and git-write-tree-nosha1write it takes\nme about 3m:20s to process 2.6.17-rc1-mm2.\n\nWith just git-apply and git-write-tree-nowritetree it takes:\nreal    2m59.985s\nuser    1m38.353s\nsys     0m31.445s\n\nWith just git-apply and /bin/true it takes:\nreal    2m1.581s\nuser    1m3.169s\nsys     0m29.903s\n\n\nLooking at the individual numbers:\n$ time git-write-tree-nowritetree --missing-ok\n\nreal    0m0.158s\nuser    0m0.052s\nsys     0m0.008s\n$ time git-write-tree-nowritetree --missing-ok\n\nreal    0m0.155s\nuser    0m0.057s\nsys     0m0.003s\n$ time git-write-tree-nowritetree --missing-ok \nreal    0m0.065s\nuser    0m0.057s\nsys     0m0.002s\n$ time git-write-tree-nowritetree --missing-ok\n\nreal    0m0.159s\nuser    0m0.055s\nsys     0m0.005s\n$ time git-write-tree-nowritetree --missing-ok\n\nreal    0m0.151s\nuser    0m0.054s\nsys     0m0.007s\n$ time git-write-tree-nowritetree --missing-ok\n\nreal    0m0.154s\nuser    0m0.056s\nsys     0m0.005s\n\n$ time git-write-tree-nosha1write --missing-ok\n0000000000000000000000000000000000000000\n\nreal    0m0.199s\nuser    0m0.091s\nsys     0m0.008s\n$ time git-write-tree-nosha1write --missing-ok\n0000000000000000000000000000000000000000\n\nreal    0m0.195s\nuser    0m0.094s\nsys     0m0.007s\n$ time git-write-tree-nosha1write --missing-ok\n0000000000000000000000000000000000000000\n\nreal    0m0.198s\nuser    0m0.092s\nsys     0m0.009s\n\n$ time git-write-tree --missing-ok\n0ecfe3dbc2e65aa9638c62abf0cf05057c77f884\n\nreal    0m0.217s\nuser    0m0.113s\nsys     0m0.012s\n\n$ time git-write-tree\n0ecfe3dbc2e65aa9638c62abf0cf05057c77f884\n\nreal    0m0.276s\nuser    0m0.169s\nsys     0m0.008s\n\nSo at a quick inspection it looks to me like:\nAbout .059s to perform to check for missing files.\nAbout .019s to write the new tree.\nAbout .155s in start up overhead, read_cache, and sanity checks.\n\nSo at a first glance it looks like librification to\nallow the redundant work to be skipped, is where\nthe big speed win on my machine would be.\n\n> Your patch looks ok from a quick read-through:\n\nThanks.\n\nMy import of 2.6.17-rc1-mm2 gives exactly the same\nresult as simply applying Andrews patch.  Which while\nnot definitive hits a lot of interesting cases.\n\n> Acked-by: Linus Torvalds <torvalds@osdl.org>\n>\n> \t\tLinus\n"},{"id":"18543","messageId":"7vacat9qmb.fsf@assigned-by-dhcp.cox.net","threadId":"3842","inReplyTo":"m1irphhj1p.fsf_-_@ebiederm.dsl.xmission.com","subject":"Re: [PATCH] Implement limited context matching in git-apply.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-10T19:29:00Z","receivedAt":"2006-04-10T19:29:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"ebiederm@xmission.com (Eric W. Biederman) writes:\n\n> If I just loop through all of Andrews patches in order\n> and run git-apply --index -C1 I process the entire patchset\n> in 1m53s or about 6 patches per second.  So running\n> git-mailinfo, git-write-tree, git-commit-tree, and\n> git-update-ref everytime has a measurable impact,\n> and shows things can be speeded up even more.\n\nAlthough I haven't \"read\" it, but just only \"looked at\" it, the\npatch looks OK.  I haven't managed to start beating on it yet\nfor time constraints.\n\nIf you are dealing with the kernel tree, I suspect most time is\nspent on write-tree.  Statistically, a typical kernel patch (I\nhaven't counted the ones in -mm series, but only the ones\nactually reacheable from Linus tip) touches only 3 files on\naverage, so most of the 1,100 tree objects in a typical kernel\ntree are computed but found unchanged when write-tree happens.\n\nI suspect we could make a backward incompatible change to the\nindex file format to record the top-level tree object names\nsomewhere where normal cache-entry walker would not see.  Then\nwhen anybody makes a modification to invalidate that tree\nobject, mark that tree (or split that tree to read lower level\ntrees lazily) to force us recompute the tree object.\n\nTheoretically you could do that recursively to record all 1,100\ntree objects but that would make the cache slightly larger (say,\nby 100kB).\n"},{"id":"18568","messageId":"Pine.LNX.4.64.0604111100510.10745@g5.osdl.org","threadId":"3842","inReplyTo":"m1k69xffcz.fsf@ebiederm.dsl.xmission.com","subject":"Re: [PATCH] Implement limited context matching in git-apply.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-04-11T18:23:21Z","receivedAt":"2006-04-11T18:23:21Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 10 Apr 2006, Eric W. Biederman wrote:\n> \n> So at a quick inspection it looks to me like:\n> About .059s to perform to check for missing files.\n> About .019s to write the new tree.\n> About .155s in start up overhead, read_cache, and sanity checks.\n> \n> So at a first glance it looks like librification to\n> allow the redundant work to be skipped, is where\n> the big speed win on my machine would be.\n\nThat sounded wrong to me, so I did a stupid patch to datestamp the \ndifferent phases of git-write-tree, and here's what it says for me:\n\n     0.000479 setup_git_directory\n     0.008333 read_cache\n     0.000813 ce_stage check\n     0.001838 tree validity check\n     0.037233 write_tree itself\n\n\treal    0m0.051s\n\tuser    0m0.044s\n\tsys     0m0.008s\n\nall times are in seconds. \n\nThere is some overhead from the actual process startup (the timestamp \nnumbers add up to 0.048696 seconds, which is less than the 0.051 reported \nby \"time\" - since I didn't datestamp everything), but the biggest chunk by \nfar (about three quarters of the total time, including _all_ the setup \nlike executing the process) is the actual call to write_tree() itself.\n\nSo it probably wouldn't actually be that big a win performance-wise to \nmake write_tree() a library and call it directly from git-apply with some \nflag.\n\nTo really speed up write-tree, you'd have to know which trees to write, \nand just skip the rest (and know what SHA1's the ones you skipped had: \nit's not enough to just skip them, since you need the SHA1's of even the \ntrees you skipped to write the parent tree, and you _will_ change at \nleast the top parent tree if you had a valid patch).\n\nWhich would imply pretty major surgery - you'd have to add the tree entry \ninformation to the index file, and make sure they got invalidated properly \n(all the way to the root) whenever adding/deleting/updating a path in the \nindex file.\n\nQuite frankly, I don't think it's really worth it.\n\nYes, it would speed up applying of huge patch-sets, but it's not like \nwe're really slow at that even now, and I suspect you'd be better off \ntrying to either live with it, or trying to see if you could change your \nworkflow. There clearly _are_ tools that are better at handling pure \npatches, with quilt being the obvious example.\n\nI routinely apply 100-200 patches in a go, and that's fast enough to not \neven be an issue. Yes, I have reasonably fast hardware, but we're likely \ntalking thousands of patches in a series for it to be _really_ painful \neven on pretty basic developer hardware. Even a slow machine should do a \nfew hundred patches in a couple of minutes.\n\nMaybe enough time to get a cup of coffee, but no more than it would take \nto compile the project.\n\n\t\t\tLinus\n"},{"id":"18611","messageId":"m1mzep65uc.fsf@ebiederm.dsl.xmission.com","threadId":"3842","inReplyTo":"Pine.LNX.4.64.0604111100510.10745@g5.osdl.org","subject":"Re: [PATCH] Implement limited context matching in git-apply.","fromName":"Eric W. Biederman","fromEmail":"ebiederm@xmission.com","sentAt":"2006-04-13T12:02:51Z","receivedAt":"2006-04-13T12:02:51Z","isPatch":true,"sender":{"key":"ebiederm@xmission.com","avatar":"https://avatars.githubusercontent.com/u/7477136?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> On Mon, 10 Apr 2006, Eric W. Biederman wrote:\n>> \n>> So at a quick inspection it looks to me like:\n>> About .059s to perform to check for missing files.\n>> About .019s to write the new tree.\n>> About .155s in start up overhead, read_cache, and sanity checks.\n>> \n>> So at a first glance it looks like librification to\n>> allow the redundant work to be skipped, is where\n>> the big speed win on my machine would be.\n>\n> That sounded wrong to me, so I did a stupid patch to datestamp the \n> different phases of git-write-tree, and here's what it says for me:\n>\n>      0.000479 setup_git_directory\n>      0.008333 read_cache\n>      0.000813 ce_stage check\n>      0.001838 tree validity check\n>      0.037233 write_tree itself\n>\n> \treal    0m0.051s\n> \tuser    0m0.044s\n> \tsys     0m0.008s\n>\n> all times are in seconds. \n\nOk.  This is interesting and probably reveals what is different\nabout my setup.  For you user+sys = real.  For me there was\na significant gap.  So it looks like for some reason I was not\nsucceeding in keeping .git/index hot in the page cache.\n\nWhen you are I/O bound it does make sense for read_cache\nto be the dominate time.  I just need to track what is up\nwith my machine that makes me I/O bound.  Having too little\nram is an obvious candidate but it is too simple.  Currently\nout of 512M I only have 21M in the page cache which sounds\nreally low.  Something for me to look at.\n\n> Which would imply pretty major surgery - you'd have to add the tree entry \n> information to the index file, and make sure they got invalidated properly \n> (all the way to the root) whenever adding/deleting/updating a path in the \n> index file.\n>\n> Quite frankly, I don't think it's really worth it.\n\nFor the current size of the kernel tree I agree.\n\nIt is a potential scaling limitation and if someone starts\ntracking really big tress with git it may be worth revisiting.\n\n> Yes, it would speed up applying of huge patch-sets, but it's not like \n> we're really slow at that even now, and I suspect you'd be better off \n> trying to either live with it, or trying to see if you could change your \n> workflow. There clearly _are_ tools that are better at handling pure \n> patches, with quilt being the obvious example.\n\nProbably.  For my workflow not having to switch tool chains is\nthe biggest win.  Which is part of what the -C is about.\n\n\n> I routinely apply 100-200 patches in a go, and that's fast enough to not \n> even be an issue. Yes, I have reasonably fast hardware, but we're likely \n> talking thousands of patches in a series for it to be _really_ painful \n> even on pretty basic developer hardware. Even a slow machine should do a \n> few hundred patches in a couple of minutes.\n>\n> Maybe enough time to get a cup of coffee, but no more than it would take \n> to compile the project.\n\nAgreed.  I did the analysis so I could understand what was going on.\nIf the analysis revealed low hanging fruit I would have plucked it.\n\nEric\n"}]}