Subject: Re: [PATCH v3] merge: fix cache_entry use-after-free

From: David Turner <[email-masked]>
Date: Fri, 16 Oct 2015 03:05:40 -0400

On Thu, 2015-10-15 at 13:51 -0700, Junio C Hamano wrote:
> David Turner <[email-masked]> writes:
> 
> >> > +static inline void drop_ce_ref(struct cache_entry *ce)
> >> > +{
> >> > +	if (ce != NULL) {
> >> > +		assert(ce->ref_count >= 0);
> >> 
> >> Shouldn't this be "> 0" to prevent double frees?
> >
> > No.  If the ref_count is 1, then there is still some reference to the
> > ce.  If it is 0, there is no reference to it, and the next check (< 1)
> > will succeed and the ce will get freed.  
> >
> >> > +		if (--ce->ref_count < 1) {
> >> > +			free(ce);
> >> > +		}
> >> > +	}
> >> > +}
> 
> Hmm, but it still feels fuzzy, no?  I cannot tell from the above
> exchange if a ce with ref_count==0 upon entry to this function is
> supposed to have somebody pointing at it, somebody just assigned
> NULL (or another pointer) to the last pointer that was pointing at
> it, or what else.  If the expected calling sequence were:
> 
> 	drop_ce_ref(thing->ce);
> 	thing->ce = NULL;
> 
> and the original thing->ce were the last reference to the cache
> entry about to be freed, its refcnt is better be 1 not 0.  And when
> this function decrements refcnt down to 0, the cache entry is freed.
> 
> Admittedly, if the original refcnt were 0, with signed refcnt, it
> will decrement to -1 and it will be freed, too, but I do not think
> that is what was intended---refcnt is initialized to 0 upon creating
> an unreferenced cache entry, and set_index_entry() and friends that
> store a pointer to anything calls add_ce_ref(), so I read the code
> as intending to make "0 means no pointer points at it".
> 
> As far as I can tell, the only effect of this assert() that uses >=0
> not >0 is to avoid triggering it on this calling sequence:
> 
>     new_ce = new_cache_entry();
>     drop_ce_ref(new_ce);
> 
> that is, you create because you _might_ use it, and then later
> decide not to use it (and the free() part wouldn't have worked
> correctly with unsigned refcnt ;-).

You and René are right: there is an off-by-one here.  Will fix and
re-roll.  Thanks.

> By the way, the log message says "During merges, we would previously
> free entries that we no longer need in the destination index.  But
> those entries might also be stored in the dir_entry cache," as if
> this issue were present and waiting to trigger for all merges for
> all people.  Given that Linus does hundreds of merges in a day
> during the merge window (and I do several dozens a day), I am quite
> surprised that nobody noticed this issue.  If there is a more
> specific condition that allows this bug to trigger (e.g. "dir-entry
> cache is used only under such and such conditions") that the log
> message does not talk about to explain why this bug was not seen
> widely, it would be a good thing to add.  It is very puzzling
> otherwise.

We also do dozens or hundreds of merges per day and only saw this quite
rarely.  Interestingly, we could only trigger it with an alternate
hashing function for git's hashmap implementation, and only once a
certain bug in that implementation was *fixed*.  But that was just a
trigger; it was certainly not the cause.  The bug would, in general,
have caused more hash collisions due to worse mixing, but I believe it
is possible that some particular collision would have been present in
the non-bugged version of the code but not in the bugged version.

It may have also had something to do with a case-insensitive filesystem;
we never saw anyone reproduce it on anything but OS X, and even there it
was quite difficult to reproduce.

In short, I don't think we know why the bug was not seen widely.