Re: [BUG] resolved deltas

[Jeff King <peff@peff.net>]

On Thu, Aug 28, 2014 at 06:08:21PM -0400, Jeff King wrote:

> So we need some kind of mutual exclusion so that only one thread
> proceeds with resolving the delta. The "real_type" check sort-of
> functions in that way (except of course it is not actually thread safe).

Here's a patch which implements that. Since I couldn't replicate the
original problem with helgrind, I am just guessing at whether it
properly fixes it (well, it is more than just a guess; I used my brain
to analyze it, but that is far from foolproof).

It uses a single lock. I did a best-of-five timing of "git index-pack
--verify" on the kernel repo, both before and after. The results ended
up quite similar (both about 57s), though the run-to-run numbers are all
over the place (up to about 65s in the worst case). So maybe it is not
so bad.

As I implemented, I realized that even with the mutex, I really was just
implementing compare_and_swap (and I wrote it that way to make it more
obvious). So if we wanted to, it would be trivial to replace the
"claim_delta" function with a true compare-and-swap instruction if the
compiler and processor support it.

---
diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index f7dc5b0..ed9e253 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -112,6 +112,10 @@ static pthread_mutex_t deepest_delta_mutex;
 #define deepest_delta_lock()	lock_mutex(&deepest_delta_mutex)
 #define deepest_delta_unlock()	unlock_mutex(&deepest_delta_mutex)
 
+static pthread_mutex_t object_entry_mutex;
+#define object_entry_lock()	lock_mutex(&object_entry_mutex)
+#define object_entry_unlock()	unlock_mutex(&object_entry_mutex)
+
 static pthread_key_t key;
 
 static inline void lock_mutex(pthread_mutex_t *mutex)
@@ -135,6 +139,7 @@ static void init_thread(void)
 	init_recursive_mutex(&read_mutex);
 	pthread_mutex_init(&counter_mutex, NULL);
 	pthread_mutex_init(&work_mutex, NULL);
+	pthread_mutex_init(&object_entry_mutex, NULL);
 	if (show_stat)
 		pthread_mutex_init(&deepest_delta_mutex, NULL);
 	pthread_key_create(&key, NULL);
@@ -157,6 +162,7 @@ static void cleanup_thread(void)
 	pthread_mutex_destroy(&read_mutex);
 	pthread_mutex_destroy(&counter_mutex);
 	pthread_mutex_destroy(&work_mutex);
+	pthread_mutex_destroy(&object_entry_mutex);
 	if (show_stat)
 		pthread_mutex_destroy(&deepest_delta_mutex);
 	for (i = 0; i < nr_threads; i++)
@@ -862,7 +868,6 @@ static void resolve_delta(struct object_entry *delta_obj,
 {
 	void *base_data, *delta_data;
 
-	delta_obj->real_type = base->obj->real_type;
 	if (show_stat) {
 		delta_obj->delta_depth = base->obj->delta_depth + 1;
 		deepest_delta_lock();
@@ -888,6 +893,21 @@ static void resolve_delta(struct object_entry *delta_obj,
 	counter_unlock();
 }
 
+static int claim_delta(struct object_entry *delta_obj,
+		       enum object_type delta_type,
+		       enum object_type base_type)
+{
+	enum object_type old_type;
+
+	object_entry_lock();
+	old_type = delta_obj->real_type;
+	if (old_type == delta_type)
+		delta_obj->real_type = base_type;
+	object_entry_unlock();
+
+	return old_type == delta_type;
+}
+
 static struct base_data *find_unresolved_deltas_1(struct base_data *base,
 						  struct base_data *prev_base)
 {
@@ -914,7 +934,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,
 	if (base->ref_first <= base->ref_last) {
 		struct object_entry *child = objects + deltas[base->ref_first].obj_no;
 
-		if (child->real_type == OBJ_REF_DELTA) {
+		if (claim_delta(child, OBJ_REF_DELTA, base->obj->real_type)) {
 			struct base_data *result = alloc_base_data();
 
 			resolve_delta(child, base, result);
@@ -930,7 +950,7 @@ static struct base_data *find_unresolved_deltas_1(struct base_data *base,
 	if (base->ofs_first <= base->ofs_last) {
 		struct object_entry *child = objects + deltas[base->ofs_first].obj_no;
 
-		if (child->real_type == OBJ_OFS_DELTA) {
+		if (claim_delta(child, OBJ_OFS_DELTA, base->obj->real_type)) {
 			struct base_data *result = alloc_base_data();
 
 			resolve_delta(child, base, result);