Subject: Re: [PATCH 2/2] index-pack: kill union delta_base to save memory

From: Junio C Hamano <[email-masked]>
Date: Sat, 04 Jul 2015 15:24:48 -0700

Duy Nguyen <[email-masked]> writes:

>>> @@ -1282,28 +1344,25 @@ static void fix_unresolved_deltas(struct sha1file *f, int nr_unresolved)
>>>        * resolving deltas in the same order as their position in the pack.
>>>        */
>>>       sorted_by_pos = xmalloc(nr_unresolved * sizeof(*sorted_by_pos));
>>> -     for (i = 0; i < nr_deltas; i++) {
>>> -             if (objects[deltas[i].obj_no].real_type != OBJ_REF_DELTA)
>>> -                     continue;
>>> -             sorted_by_pos[n++] = &deltas[i];
>>> -     }
>>> +     for (i = 0; i < nr_ref_deltas; i++)
>>> +             sorted_by_pos[n++] = &ref_deltas[i];
>>>       qsort(sorted_by_pos, n, sizeof(*sorted_by_pos), delta_pos_compare);
>>
>> You allocate an array of nr_unresolved (which is the sum of
>> nr_ref_deltas and nr_ofs_deltas in the new world order with patch)
>> entries, fill only the first nr_ref_deltas entries of it, and then
>> sort that first n (= nr_ref_deltas) entries.  The qsort and the
>> subsequent loop only looks at the first n entries, so nothing is
>> filling or reading these nr_ofs_deltas entres at the end.
>>
>> I do not see any wrong behaviour other than temporary wastage of
>> nr_ofs_deltas pointers that would be caused by this, but this
>> allocation is misleading.
>>
>> Also, the old code before this change had to use 'i' and 'n' because
>> some of the things we see in the (old) deltas[] array we scanned
>> with 'i' would not make it into the sorted_by_pos[] array in the old
>> world order, but now because you have only ref delta in a separate
>> ref_deltas[] array, they increment lock&step.  That also puzzled me
>> while re-reading this code.
>>
>> Perhaps something like this is needed?
>
> Yeah I can see the confusion when reading the code without checking
> its history. You probably want to kill the argument nr_unresolved too
> because it's not needed anymore after your patch.
>
> So what's the bug you mentioned? All I got from the above was wastage
> and confusion, no bug.

Actually, the above is not analyzed correctly.  I thought
nr_unresolved was ref + ofs, but look at the caller in the
fix_thin_pack codepath:

	int nr_unresolved = nr_ofs_deltas + nr_ref_deltas - nr_resolved_deltas;
	int nr_objects_initial = nr_objects;
	if (nr_unresolved <= 0)
		die(_("confusion beyond insanity"));
	REALLOC_ARRAY(objects, nr_objects + nr_unresolved + 1);
	memset(objects + nr_objects + 1, 0,
	       nr_unresolved * sizeof(*objects));
	f = sha1fd(output_fd, curr_pack);
	fix_unresolved_deltas(f, nr_unresolved);

If there were tons of nr_resolved_deltas and only small number of
nr_ofs_deltas, then the allocation in question may actually be
under-allocating.

So...