[RFC PATCH 5/5] builtin/grep.c: fix fence-post error in add_work()

[Rasmus Villemoes]

We're only using 127 of the slots in todo[], which can easily be seen
by adding this hack

--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -93,6 +93,8 @@ static int skip_first_line;

 static void add_work(struct grep_opt *opt, const struct grep_source *gs)
 {
+       static int count;
+
        grep_lock();

        while ((todo_end+1) % ARRAY_SIZE(todo) == todo_done) {
@@ -108,6 +110,7 @@ static void add_work(struct grep_opt *opt, const struct 
grep_source *gs)
        todo_end = (todo_end + 1) % ARRAY_SIZE(todo);

        pthread_cond_signal(&cond_add);
+       fprintf(stderr, "added work item %3d\n", ++count);
        grep_unlock();
 }

@@ -173,6 +176,7 @@ static void *run(void *arg)
        int hit = 0;
        struct grep_opt *opt = arg;

+       sleep(2);
        while (1) {
                struct work_item *w = get_work();
                if (!w)

Of course, just removing the +1 after todo_end would be instant
deadlock, since nothing would ever change todo_end or todo_done from
0.

The problem boils down to the fact that arithmetic mod 128 cannot
capture the 129 possible values of end-done (which
is (end-start)+(start-done), i.e. the total number of items waiting to
be picked up or that have been picked up by a worker).

To fix this, don't keep the todo_* variables reduced mod 128, and only
do that when using them as indices into todo[]. Then we can rewrite
the condition in add_work() to the proper one: Wait until todo_end is
not a full round ahead of todo_done.

Signed-off-by: Rasmus Villemoes <r...@rasmusvillemoes.dk>
---
 builtin/grep.c | 9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)

diff --git a/builtin/grep.c b/builtin/grep.c
index 35ed79b0dd..ce158cabbb 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -102,7 +102,7 @@ static void add_work(struct grep_opt *opt, const struct 
grep_source *gs)
 
        grep_lock();
 
-       while ((todo_end+1) % ARRAY_SIZE(todo) == todo_done) {
+       while (todo_end - todo_done == ARRAY_SIZE(todo)) {
                pthread_cond_wait(&cond_write, &grep_mutex);
        }
 
@@ -112,7 +112,7 @@ static void add_work(struct grep_opt *opt, const struct 
grep_source *gs)
                grep_source_load_driver(&w->source, opt->repo->index);
        w->done = 0;
        strbuf_reset(&w->out);
-       todo_end = (todo_end + 1) % ARRAY_SIZE(todo);
+       todo_end += 1;
 
        pthread_cond_signal(&cond_add);
        grep_unlock();
@@ -131,7 +131,7 @@ static struct work_item *get_work(void)
                ret = NULL;
        } else {
                ret = todo_item(todo_start);
-               todo_start = (todo_start + 1) % ARRAY_SIZE(todo);
+               todo_start += 1;
        }
        grep_unlock();
        return ret;
@@ -144,8 +144,7 @@ static void work_done(struct work_item *w)
        grep_lock();
        w->done = 1;
        old_done = todo_done;
-       for(; todo_done != todo_start;
-           todo_done = (todo_done+1) % ARRAY_SIZE(todo)) {
+       for(; todo_done != todo_start; todo_done += 1) {
                w = todo_item(todo_done);
                if (!w->done)
                        break;
-- 
2.20.1