[PATCH/RFH 0/3] stable priority-queue
- From
Jeff King <peff@peff.net>
- Date
- Jul 14, 2014, 05:40 UTC
- Message-ID
- <20140714054021.GA4422@sigill.intra.peff.net>
As Junio and I discussed earlier in [1], this series makes the prio_queue struct stable with respect to object insertion (which in turn means we can use it to replace commit_list in more places).
I think everything here is correct, but the second commit fails the final test in t5539. I think the test is just flaky (hence the RFH and cc to Duy).
That test creates some unrelated commits in two separate repositories, and then fetches from one to the other. Since the commit creation happens in a subshell, the first commit in each ends up with the same test_tick value. When fetch-pack looks at the two root commits "unrelated1" and "new-too", the exact sequence of ACKs is different depending on which one it pulls out of the queue first.
With the current code, it happens to be "unrelated1" (though this is not at all guaranteed by the prio_queue data structure, it is deterministic for this particular sequence of input). We see the ready-ACK, and the test succeeds.
With the stable queue, we reliably get "new-too" out (since it is our local tip, it is added to the queue before we even talk to the remote). We never see a ready-ACK, and the test fails due to the grep on the TRACE_PACKET output at the end (the fetch itself succeeds as expected).
I'm really not quite clear on what's supposed to be going on in the test. I can make it pass with:
diff --git a/t/t5539-fetch-http-shallow.sh b/t/t5539-fetch-http-shallow.sh index 94553e1..b461188 100755 --- a/t/t5539-fetch-http-shallow.sh +++ b/t/t5539-fetch-http-shallow.sh @@ -54,6 +54,7 @@ EOF test_expect_success 'no shallow lines after receiving ACK ready' ' ( cd shallow && + test_tick && for i in $(test_seq 15) do git checkout --orphan unrelated$i && which just bumps the timestamp for the unrelated* commits (so that they are always more recent than "new-too" and get picked first). I'm not sure if that is too hacky, or if there's a more robust way to set up the test. Anyway, here are the patches. [1/3]: prio-queue: factor out compare and swap operations [2/3]: prio-queue: make output stable with respect to insertion [3/3]: paint_down_to_common: use prio_queue -Peff [1] http://thread.gmane.org/gmane.comp.version-control.git/252472/focus=252475