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

[Rasmus Villemoes <rv@xxxxxxxxxxxxxxxxxx>]

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 <rv@xxxxxxxxxxxxxxxxxx>
---
 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