{"thread":{"id":"50485","subject":"[RFC PATCH 0/5] builtin/grep.c: fix a tiny logic flaw","startedAt":"2019-02-12T22:27:03Z","lastAt":"2019-02-12T22:27:19Z","messageCount":6,"participants":["Rasmus Villemoes"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"369185","messageId":"20190212222654.7432-1-rv@rasmusvillemoes.dk","threadId":"50485","inReplyTo":null,"subject":"[RFC PATCH 0/5] builtin/grep.c: fix a tiny logic flaw","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2019-02-12T22:26:49Z","receivedAt":"2019-02-12T22:27:03Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"Background: I noticed that the condition in add_work() for when the\nproducer could add a new item was oddly different from the other\nconditions on the todo_* bookkeeping variables - namely, in the other\ncases we want todo_a != todo_b, whereas in add_work the condition is\ntodo_a+1!=todo_b. Another hint that something is slightly off is that\nthe code would break down if TODO_SIZE was set to 1.\n\nThe practical effect is negligible, and fixing it seems to be a bit\ninvolved, hence probably not worth the churn - and if that's the\nverdict, I suggest adding a comment in add_work() for future readers\nand/or people who copy the producer/consumer logic to their own code.\n\nRasmus Villemoes (5):\n builtin/grep.c: change todo_* variables to unsigned\n builtin/grep.c: refactor loop in work_done() slightly\n builtin/grep.c: add shorthand for &todo[todo_end] in add_work()\n builtin/grep.c: add todo_item helper\n builtin/grep.c: fix fence-post error in add_work()\n\n builtin/grep.c | 40 ++++++++++++++++++++++++----------------\n 1 file changed, 24 insertions(+), 16 deletions(-)\n\n-- \n2.20.1\n\n"},{"id":"369186","messageId":"20190212222654.7432-2-rv@rasmusvillemoes.dk","threadId":"50485","inReplyTo":"20190212222654.7432-1-rv@rasmusvillemoes.dk","subject":"[RFC PATCH 1/5] builtin/grep.c: change todo_* variables to unsigned","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2019-02-12T22:26:50Z","receivedAt":"2019-02-12T22:27:03Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"In preparation for subsequent patches that make todo_* free-running\ninstead of reducing them mod TODO_SIZE, change their type to unsigned\nto avoid undefined behaviour in case anybody ever greps more than 2\nbillion files.\n\nSigned-off-by: Rasmus Villemoes \n---\n builtin/grep.c | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 580fd38f41..6c1e90d43b 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -58,9 +58,9 @@ struct work_item {\n */\n #define TODO_SIZE 128\n static struct work_item todo[TODO_SIZE];\n-static int todo_start;\n-static int todo_end;\n-static int todo_done;\n+static unsigned int todo_start;\n+static unsigned int todo_end;\n+static unsigned int todo_done;\n \n /* Has all work items been added? */\n static int all_work_added;\n@@ -132,7 +132,7 @@ static struct work_item *get_work(void)\n \n static void work_done(struct work_item *w)\n {\n-\tint old_done;\n+\tunsigned int old_done;\n \n \tgrep_lock();\n \tw->done = 1;\n-- \n2.20.1\n\n"},{"id":"369187","messageId":"20190212222654.7432-3-rv@rasmusvillemoes.dk","threadId":"50485","inReplyTo":"20190212222654.7432-1-rv@rasmusvillemoes.dk","subject":"[RFC PATCH 2/5] builtin/grep.c: refactor loop in work_done() slightly","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2019-02-12T22:26:51Z","receivedAt":"2019-02-12T22:27:06Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"As preparation for changing all accesses to the todo array to use a\nhelper function, do the .done check in the loop body.\n\nSigned-off-by: Rasmus Villemoes \n---\n builtin/grep.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 6c1e90d43b..211ae54222 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -137,9 +137,11 @@ static void work_done(struct work_item *w)\n \tgrep_lock();\n \tw->done = 1;\n \told_done = todo_done;\n-\tfor(; todo[todo_done].done && todo_done != todo_start;\n+\tfor(; todo_done != todo_start;\n \t todo_done = (todo_done+1) % ARRAY_SIZE(todo)) {\n \t\tw = &todo[todo_done];\n+\t\tif (!w->done)\n+\t\t\tbreak;\n \t\tif (w->out.len) {\n \t\t\tconst char *p = w->out.buf;\n \t\t\tsize_t len = w->out.len;\n-- \n2.20.1\n\n"},{"id":"369188","messageId":"20190212222654.7432-5-rv@rasmusvillemoes.dk","threadId":"50485","inReplyTo":"20190212222654.7432-1-rv@rasmusvillemoes.dk","subject":"[RFC PATCH 4/5] builtin/grep.c: add todo_item helper","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2019-02-12T22:26:53Z","receivedAt":"2019-02-12T22:27:11Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"Use a helper for indexing into the todo array with any of the todo_*\nvariables, in preparation for not keeping those reduced mod TODO_SIZE.\n\nSigned-off-by: Rasmus Villemoes \n---\n builtin/grep.c | 11 ++++++++---\n 1 file changed, 8 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 92b9e6198d..35ed79b0dd 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -62,6 +62,11 @@ static unsigned int todo_start;\n static unsigned int todo_end;\n static unsigned int todo_done;\n \n+static inline struct work_item *todo_item(unsigned int idx)\n+{\n+\treturn &todo[idx % ARRAY_SIZE(todo)];\n+}\n+\n /* Has all work items been added? */\n static int all_work_added;\n \n@@ -101,7 +106,7 @@ static void add_work(struct grep_opt *opt, const struct grep_source *gs)\n \t\tpthread_cond_wait(&cond_write, &grep_mutex);\n \t}\n \n-\tw = &todo[todo_end];\n+\tw = todo_item(todo_end);\n \tw->source = *gs;\n \tif (opt->binary != GREP_BINARY_TEXT)\n \t\tgrep_source_load_driver(&w->source, opt->repo->index);\n@@ -125,7 +130,7 @@ static struct work_item *get_work(void)\n \tif (todo_start == todo_end && all_work_added) {\n \t\tret = NULL;\n \t} else {\n-\t\tret = &todo[todo_start];\n+\t\tret = todo_item(todo_start);\n \t\ttodo_start = (todo_start + 1) % ARRAY_SIZE(todo);\n \t}\n \tgrep_unlock();\n@@ -141,7 +146,7 @@ static void work_done(struct work_item *w)\n \told_done = todo_done;\n \tfor(; todo_done != todo_start;\n \t todo_done = (todo_done+1) % ARRAY_SIZE(todo)) {\n-\t\tw = &todo[todo_done];\n+\t\tw = todo_item(todo_done);\n \t\tif (!w->done)\n \t\t\tbreak;\n \t\tif (w->out.len) {\n-- \n2.20.1\n\n"},{"id":"369189","messageId":"20190212222654.7432-6-rv@rasmusvillemoes.dk","threadId":"50485","inReplyTo":"20190212222654.7432-1-rv@rasmusvillemoes.dk","subject":"[RFC PATCH 5/5] builtin/grep.c: fix fence-post error in add_work()","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2019-02-12T22:26:54Z","receivedAt":"2019-02-12T22:27:12Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"We're only using 127 of the slots in todo[], which can easily be seen\nby adding this hack\n\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -93,6 +93,8 @@ static int skip_first_line;\n\n static void add_work(struct grep_opt *opt, const struct grep_source *gs)\n {\n+\tstatic int count;\n+\n \tgrep_lock();\n\n \twhile ((todo_end+1) % ARRAY_SIZE(todo) == todo_done) {\n@@ -108,6 +110,7 @@ static void add_work(struct grep_opt *opt, const struct grep_source *gs)\n \ttodo_end = (todo_end + 1) % ARRAY_SIZE(todo);\n\n \tpthread_cond_signal(&cond_add);\n+\tfprintf(stderr, \"added work item %3d\\n\", ++count);\n \tgrep_unlock();\n }\n\n@@ -173,6 +176,7 @@ static void *run(void *arg)\n \tint hit = 0;\n \tstruct grep_opt *opt = arg;\n\n+\tsleep(2);\n \twhile (1) {\n \t\tstruct work_item *w = get_work();\n \t\tif (!w)\n\nOf course, just removing the +1 after todo_end would be instant\ndeadlock, since nothing would ever change todo_end or todo_done from\n0.\n\nThe problem boils down to the fact that arithmetic mod 128 cannot\ncapture the 129 possible values of end-done (which\nis (end-start)+(start-done), i.e. the total number of items waiting to\nbe picked up or that have been picked up by a worker).\n\nTo fix this, don't keep the todo_* variables reduced mod 128, and only\ndo that when using them as indices into todo[]. Then we can rewrite\nthe condition in add_work() to the proper one: Wait until todo_end is\nnot a full round ahead of todo_done.\n\nSigned-off-by: Rasmus Villemoes \n---\n builtin/grep.c | 9 ++++-----\n 1 file changed, 4 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 35ed79b0dd..ce158cabbb 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -102,7 +102,7 @@ static void add_work(struct grep_opt *opt, const struct grep_source *gs)\n \n \tgrep_lock();\n \n-\twhile ((todo_end+1) % ARRAY_SIZE(todo) == todo_done) {\n+\twhile (todo_end - todo_done == ARRAY_SIZE(todo)) {\n \t\tpthread_cond_wait(&cond_write, &grep_mutex);\n \t}\n \n@@ -112,7 +112,7 @@ static void add_work(struct grep_opt *opt, const struct grep_source *gs)\n \t\tgrep_source_load_driver(&w->source, opt->repo->index);\n \tw->done = 0;\n \tstrbuf_reset(&w->out);\n-\ttodo_end = (todo_end + 1) % ARRAY_SIZE(todo);\n+\ttodo_end += 1;\n \n \tpthread_cond_signal(&cond_add);\n \tgrep_unlock();\n@@ -131,7 +131,7 @@ static struct work_item *get_work(void)\n \t\tret = NULL;\n \t} else {\n \t\tret = todo_item(todo_start);\n-\t\ttodo_start = (todo_start + 1) % ARRAY_SIZE(todo);\n+\t\ttodo_start += 1;\n \t}\n \tgrep_unlock();\n \treturn ret;\n@@ -144,8 +144,7 @@ static void work_done(struct work_item *w)\n \tgrep_lock();\n \tw->done = 1;\n \told_done = todo_done;\n-\tfor(; todo_done != todo_start;\n-\t todo_done = (todo_done+1) % ARRAY_SIZE(todo)) {\n+\tfor(; todo_done != todo_start; todo_done += 1) {\n \t\tw = todo_item(todo_done);\n \t\tif (!w->done)\n \t\t\tbreak;\n-- \n2.20.1\n\n"},{"id":"369190","messageId":"20190212222654.7432-4-rv@rasmusvillemoes.dk","threadId":"50485","inReplyTo":"20190212222654.7432-1-rv@rasmusvillemoes.dk","subject":"[RFC PATCH 3/5] builtin/grep.c: add shorthand for &todo[todo_end] in add_work()","fromName":"Rasmus Villemoes","fromEmail":"rv@rasmusvillemoes.dk","sentAt":"2019-02-12T22:26:52Z","receivedAt":"2019-02-12T22:27:19Z","isPatch":true,"sender":{"key":"rv@rasmusvillemoes.dk","avatar":"https://avatars.githubusercontent.com/u/4375908?v=4"},"body":"Signed-off-by: Rasmus Villemoes \n---\n builtin/grep.c | 12 +++++++-----\n 1 file changed, 7 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/grep.c b/builtin/grep.c\nindex 211ae54222..92b9e6198d 100644\n--- a/builtin/grep.c\n+++ b/builtin/grep.c\n@@ -93,18 +93,20 @@ static int skip_first_line;\n \n static void add_work(struct grep_opt *opt, const struct grep_source *gs)\n {\n+\tstruct work_item *w;\n+\n \tgrep_lock();\n \n \twhile ((todo_end+1) % ARRAY_SIZE(todo) == todo_done) {\n \t\tpthread_cond_wait(&cond_write, &grep_mutex);\n \t}\n \n-\ttodo[todo_end].source = *gs;\n+\tw = &todo[todo_end];\n+\tw->source = *gs;\n \tif (opt->binary != GREP_BINARY_TEXT)\n-\t\tgrep_source_load_driver(&todo[todo_end].source,\n-\t\t\t\t\topt->repo->index);\n-\ttodo[todo_end].done = 0;\n-\tstrbuf_reset(&todo[todo_end].out);\n+\t\tgrep_source_load_driver(&w->source, opt->repo->index);\n+\tw->done = 0;\n+\tstrbuf_reset(&w->out);\n \ttodo_end = (todo_end + 1) % ARRAY_SIZE(todo);\n \n \tpthread_cond_signal(&cond_add);\n-- \n2.20.1\n\n"}]}