v3merge: fix cache_entry use-after-free

> From: Keith McGuigan <kmcguigan@twitter.com>
>
> 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, and when a later call to add_to_index found them,
> they would be used after being freed.
>
> To prevent this, add a ref count for struct cache_entry.  Whenever
> a cache entry is added to a data structure, the ref count is incremented;
> when it is removed from the data structure, it is decremented.  When
> it hits zero, the cache_entry is freed.
>
> Signed-off-by: Keith McGuigan <kmcguigan@twitter.com>
> Signed-off-by: David Turner <dturner@twopensource.com>
> ---
>
> Fix type of ref_count (from unsigned int to int).
>
>
>   cache.h        | 27 +++++++++++++++++++++++++++
>   name-hash.c    |  7 ++++++-
>   read-cache.c   |  6 +++++-
>   split-index.c  | 13 ++++++++-----
>   unpack-trees.c |  6 ++++--
>   5 files changed, 50 insertions(+), 9 deletions(-)
>
> diff --git a/cache.h b/cache.h
> index 752031e..7906026 100644
> --- a/cache.h
> +++ b/cache.h
> @@ -149,6 +149,7 @@ struct stat_data {
>
>   struct cache_entry {
>   	struct hashmap_entry ent;
> +	int ref_count; /* count the number of refs to this in dir_hash */
>   	struct stat_data ce_stat_data;
>   	unsigned int ce_mode;
>   	unsigned int ce_flags;
> @@ -213,6 +214,32 @@ struct cache_entry {
>   struct pathspec;
>
>   /*
> + * Increment the cache_entry reference count.  Should be called
> + * whenever a pointer to a cache_entry is retained in a data structure,
> + * thus marking it as alive.
> + */
> +static inline void add_ce_ref(struct cache_entry *ce)
> +{
> +	assert(ce != NULL && ce->ref_count >= 0);
> +	ce->ref_count++;
> +}
> +
> +/*
> + * Decrement the cache_entry reference count.  Should be called whenever
> + * a pointer to a cache_entry is dropped.  Once the counter drops to 0
> + * the cache_entry memory will be safely freed.
> + */
> +static inline void drop_ce_ref(struct cache_entry *ce)
> +{
> +	if (ce != NULL) {
> +		assert(ce->ref_count >= 0);

> +		if (--ce->ref_count < 1) {
> +			free(ce);
> +		}
> +	}
> +}

> Am 15.10.2015 um 00:07 schrieb David Turner:
> > From: Keith McGuigan <kmcguigan@twitter.com>
> >
> > 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, and when a later call to add_to_index found them,
> > they would be used after being freed.
> >
> > To prevent this, add a ref count for struct cache_entry.  Whenever
> > a cache entry is added to a data structure, the ref count is incremented;
> > when it is removed from the data structure, it is decremented.  When
> > it hits zero, the cache_entry is freed.
> >
> > Signed-off-by: Keith McGuigan <kmcguigan@twitter.com>
> > Signed-off-by: David Turner <dturner@twopensource.com>
> > ---
> >
> > Fix type of ref_count (from unsigned int to int).
> >
> >
> >   cache.h        | 27 +++++++++++++++++++++++++++
> >   name-hash.c    |  7 ++++++-
> >   read-cache.c   |  6 +++++-
> >   split-index.c  | 13 ++++++++-----
> >   unpack-trees.c |  6 ++++--
> >   5 files changed, 50 insertions(+), 9 deletions(-)
> >
> > diff --git a/cache.h b/cache.h
> > index 752031e..7906026 100644
> > --- a/cache.h
> > +++ b/cache.h
> > @@ -149,6 +149,7 @@ struct stat_data {
> >
> >   struct cache_entry {
> >   	struct hashmap_entry ent;
> > +	int ref_count; /* count the number of refs to this in dir_hash */
> >   	struct stat_data ce_stat_data;
> >   	unsigned int ce_mode;
> >   	unsigned int ce_flags;
> > @@ -213,6 +214,32 @@ struct cache_entry {
> >   struct pathspec;
> >
> >   /*
> > + * Increment the cache_entry reference count.  Should be called
> > + * whenever a pointer to a cache_entry is retained in a data structure,
> > + * thus marking it as alive.
> > + */
> > +static inline void add_ce_ref(struct cache_entry *ce)
> > +{
> > +	assert(ce != NULL && ce->ref_count >= 0);
> > +	ce->ref_count++;
> > +}
> > +
> > +/*
> > + * Decrement the cache_entry reference count.  Should be called whenever
> > + * a pointer to a cache_entry is dropped.  Once the counter drops to 0
> > + * the cache_entry memory will be safely freed.
> > + */
> > +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?

> > +		if (--ce->ref_count < 1) {
> > +			free(ce);
> > +		}
> > +	}
> > +}
> 

> On Thu, 2015-10-15 at 05:35 +0200, René Scharfe wrote:
>> Am 15.10.2015 um 00:07 schrieb David Turner:
>>> From: Keith McGuigan <kmcguigan@twitter.com>
>>>
>>> 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, and when a later call to add_to_index found them,
>>> they would be used after being freed.
>>>
>>> To prevent this, add a ref count for struct cache_entry.  Whenever
>>> a cache entry is added to a data structure, the ref count is incremented;
>>> when it is removed from the data structure, it is decremented.  When
>>> it hits zero, the cache_entry is freed.
>>>
>>> Signed-off-by: Keith McGuigan <kmcguigan@twitter.com>
>>> Signed-off-by: David Turner <dturner@twopensource.com>
>>> ---
>>>
>>> Fix type of ref_count (from unsigned int to int).
>>>
>>>
>>>    cache.h        | 27 +++++++++++++++++++++++++++
>>>    name-hash.c    |  7 ++++++-
>>>    read-cache.c   |  6 +++++-
>>>    split-index.c  | 13 ++++++++-----
>>>    unpack-trees.c |  6 ++++--
>>>    5 files changed, 50 insertions(+), 9 deletions(-)
>>>
>>> diff --git a/cache.h b/cache.h
>>> index 752031e..7906026 100644
>>> --- a/cache.h
>>> +++ b/cache.h
>>> @@ -149,6 +149,7 @@ struct stat_data {
>>>
>>>    struct cache_entry {
>>>    	struct hashmap_entry ent;
>>> +	int ref_count; /* count the number of refs to this in dir_hash */
>>>    	struct stat_data ce_stat_data;
>>>    	unsigned int ce_mode;
>>>    	unsigned int ce_flags;
>>> @@ -213,6 +214,32 @@ struct cache_entry {
>>>    struct pathspec;
>>>
>>>    /*
>>> + * Increment the cache_entry reference count.  Should be called
>>> + * whenever a pointer to a cache_entry is retained in a data structure,
>>> + * thus marking it as alive.
>>> + */
>>> +static inline void add_ce_ref(struct cache_entry *ce)
>>> +{
>>> +	assert(ce != NULL && ce->ref_count >= 0);
>>> +	ce->ref_count++;
>>> +}
>>> +
>>> +/*
>>> + * Decrement the cache_entry reference count.  Should be called whenever
>>> + * a pointer to a cache_entry is dropped.  Once the counter drops to 0
>>> + * the cache_entry memory will be safely freed.
>>> + */
>>> +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);
>>> +		}
>>> +	}
>>> +}

>> > +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);
>> > +		}
>> > +	}
>> > +}

> David Turner <dturner@twopensource.com> 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 ;-).

> 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.

> David Turner <dturner@twopensource.com> writes:
> 
> > 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.
> 
> It has been a long time since I looked at name-hash.c and I am fuzzy
> on what the four functions (cache|index)_(file|dir)_exists are meant
> for, but I have this feeling that the original premise of the patch,
> "we may free a ce because we no longer use it in the index, but it
> may still need to keep a reference to it in name-hash" may be wrong
> in the first place.  The proposed "fix" conceptually feels wrong.
>
> The whole point of the name-hash is so that we can detect collisions
> in two names, one of which wants to have a file in one place while
> the other wants to have a directory, at the same path in the index.
> The pathnames and cache entries registered in the name-hash have to
> be the ones that are relevant to the index in quesition.  If a new
> ce will be added to the index, the name-hash will have to know about
> its path (and that is what CE_HASHED bit is about).  On the other
> hand, if you are going to remove an existing ce from the index, its
> sub-paths should no longer prevent other cache entries to be there.
> 
> E.g. if you have "a/b", it must prevent "A" from entering the index
> and the name-hash helps you to do so; when you remove "a/b", then
> name-hash must now allow "A" to enter the index.  So "a/b" must be
> removed from the name-hash by calling remove_name_hash() and normal
> codepaths indeed do so.
>
> I do not doubt the existence of "use-after-free bug" you observed,
> but I am not convinced that refcounting is "fixing" the problem; it
> smells like papering over a different bug that is the root cause of
> the use-after-free.
> 
> For example, if we forget to "unhash" a ce from name-hash when we
> remove a ce from the index (or after we "hashed" it, expecting to
> add it to the index, but in the end decided not to add to the index,
> perhaps), we would see a now-freed ce still in the name-hash.
> Checking a path against the name-hash in such a state would have to
> use the ce->name from that stale ce, which is a use-after-free bug.
> 
> In such a situation, isn't the real cause of the bug the fact that
> the stale ce that is no longer relevant to the true index contents
> still in name-hash?  The refcounting does not fix the fact that a
> ce->name of a stale ce that is no longer relevant being used for D/F
> collision checking.
> 
> I am not saying that I found such a codepath that forgets to unhash,
> but from the overall design and purpose of the name-hash subsystem,
> anything that deliberately _allows_ a stale ce that does not exist
> in the index in there smells like a workaround going in a wrong
> direction.

> The problem is not the name_hash, but with the dir_hash.  The dir_hash
> is only even populated on case-insensitive filesystems (which is why you
> and Linus don't see this bug).  The dir_hash is not designed to catch
> d/f conflicts, but rather case conflicts (one side of a merge has
> foo/bar; the other has FOO/bar).  For each directory, it maintains a
> pointer to a cache_entry.  Then add_to_index uses that cache_entry to 
> rewrite incoming entries' parent directories to the expected case.
> Weirdly, that part of add_to_index is, so far as I can tell, never
> called during a merge.  So where's are we using the freed value?
> Probably in dir_entry_cmp, while adding another entry to the hashmap;
> that's where our crash seems to have happened.  And our failure depended
> on the details of the hash function as well; if a certain collision did
> not happen, we would not see it.
>
> There is, I think, another way to handle this: we could *copy* the path
> into the struct dir_entry instead of pointing to a cache_entry.  But
> this seems like a bunch of extra work; the refcounting is simpler.