[PATCH 0/1] merge: fix cache_entry use-after-free

[PATCH 0/1] merge: fix cache_entry use-after-free

[David Turner]

Keith diagnosed the problem and wrote the patch.  I wrote the commit
message and am sending it upstream with his OK.

Keith McGuigan (1):
  merge: fix cache_entry use-after-free

 cache.h        | 27 +++++++++++++++++++++++++++
 name-hash.c    |  7 ++++++-
 read-cache.c   |  5 ++++-
 split-index.c  | 12 +++++++-----
 unpack-trees.c |  6 ++++--
 5 files changed, 48 insertions(+), 9 deletions(-)

-- 
2.4.2.644.g97b850b-twtrsrc

[PATCH 0/1] merge: fix cache_entry use-after-free

[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: David Turner <dturner@twopensource.com>
Signed-off-by: Keith McGuigan <kmcguigan@twitter.com>
---
 cache.h        | 27 +++++++++++++++++++++++++++
 name-hash.c    |  7 ++++++-
 read-cache.c   |  5 ++++-
 split-index.c  | 12 +++++++-----
 unpack-trees.c |  6 ++++--
 5 files changed, 48 insertions(+), 9 deletions(-)

diff --git a/cache.h b/cache.h
index 752031e..7563658 100644
--- a/cache.h
+++ b/cache.h
@@ -149,6 +149,7 @@ struct stat_data {
 
 struct cache_entry {
 	struct hashmap_entry ent;
+	unsigned 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);
+		}
+	}
+}
+
+/*
  * Copy the sha1 and stat state of a cache entry from one to
  * another. But we never change the name, or the hash state!
  */
diff --git a/name-hash.c b/name-hash.c
index 702cd05..f12c919 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -66,6 +66,7 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,
 		dir = xcalloc(1, sizeof(struct dir_entry));
 		hashmap_entry_init(dir, memihash(ce->name, namelen));
 		dir->namelen = namelen;
+		add_ce_ref(ce);
 		dir->ce = ce;
 		hashmap_add(&istate->dir_hash, dir);
 
@@ -92,7 +93,9 @@ static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)
 	struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));
 	while (dir && !(--dir->nr)) {
 		struct dir_entry *parent = dir->parent;
-		hashmap_remove(&istate->dir_hash, dir, NULL);
+		struct dir_entry *removed = hashmap_remove(&istate->dir_hash, dir, NULL);
+		assert(removed == dir);
+		drop_ce_ref(dir->ce);
 		free(dir);
 		dir = parent;
 	}
@@ -105,6 +108,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
 	ce->ce_flags |= CE_HASHED;
 	hashmap_entry_init(ce, memihash(ce->name, ce_namelen(ce)));
 	hashmap_add(&istate->name_hash, ce);
+	add_ce_ref(ce);
 
 	if (ignore_case)
 		add_dir_entry(istate, ce);
@@ -147,6 +151,7 @@ void remove_name_hash(struct index_state *istate, struct cache_entry *ce)
 		return;
 	ce->ce_flags &= ~CE_HASHED;
 	hashmap_remove(&istate->name_hash, ce, ce);
+	drop_ce_ref(ce);
 
 	if (ignore_case)
 		remove_dir_entry(istate, ce);
diff --git a/read-cache.c b/read-cache.c
index 87204a5..442de34 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -53,6 +53,7 @@ static const char *alternate_index_output;
 static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
 {
 	istate->cache[nr] = ce;
+	add_ce_ref(ce);
 	add_name_hash(istate, ce);
 }
 
@@ -62,7 +63,7 @@ static void replace_index_entry(struct index_state *istate, int nr, struct cache
 
 	replace_index_entry_in_base(istate, old, ce);
 	remove_name_hash(istate, old);
-	free(old);
+	drop_ce_ref(old);
 	set_index_entry(istate, nr, ce);
 	ce->ce_flags |= CE_UPDATE_IN_BASE;
 	istate->cache_changed |= CE_ENTRY_CHANGED;
@@ -75,6 +76,7 @@ void rename_index_entry_at(struct index_state *istate, int nr, const char *new_n
 
 	new = xmalloc(cache_entry_size(namelen));
 	copy_cache_entry(new, old);
+	new->ref_count = 0;
 	new->ce_flags &= ~CE_HASHED;
 	new->ce_namelen = namelen;
 	new->index = 0;
@@ -1426,6 +1428,7 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on
 {
 	struct cache_entry *ce = xmalloc(cache_entry_size(len));
 
+	ce->ref_count = 0;
 	ce->ce_stat_data.sd_ctime.sec = get_be32(&ondisk->ctime.sec);
 	ce->ce_stat_data.sd_mtime.sec = get_be32(&ondisk->mtime.sec);
 	ce->ce_stat_data.sd_ctime.nsec = get_be32(&ondisk->ctime.nsec);
diff --git a/split-index.c b/split-index.c
index 968b780..ad28f7b 100644
--- a/split-index.c
+++ b/split-index.c
@@ -124,7 +124,7 @@ static void replace_entry(size_t pos, void *data)
 	src->ce_flags |= CE_UPDATE_IN_BASE;
 	src->ce_namelen = dst->ce_namelen;
 	copy_cache_entry(dst, src);
-	free(src);
+	drop_ce_ref(src);
 	si->nr_replacements++;
 }
 
@@ -227,7 +227,7 @@ void prepare_to_write_split_index(struct index_state *istate)
 			base->ce_flags = base_flags;
 			if (ret)
 				ce->ce_flags |= CE_UPDATE_IN_BASE;
-			free(base);
+			drop_ce_ref(base);
 			si->base->cache[ce->index - 1] = ce;
 		}
 		for (i = 0; i < si->base->cache_nr; i++) {
@@ -302,7 +302,7 @@ void save_or_free_index_entry(struct index_state *istate, struct cache_entry *ce
 	    ce == istate->split_index->base->cache[ce->index - 1])
 		ce->ce_flags |= CE_REMOVE;
 	else
-		free(ce);
+		drop_ce_ref(ce);
 }
 
 void replace_index_entry_in_base(struct index_state *istate,
@@ -314,8 +314,10 @@ void replace_index_entry_in_base(struct index_state *istate,
 	    istate->split_index->base &&
 	    old->index <= istate->split_index->base->cache_nr) {
 		new->index = old->index;
-		if (old != istate->split_index->base->cache[new->index - 1])
-			free(istate->split_index->base->cache[new->index - 1]);
+		if (old != istate->split_index->base->cache[new->index - 1]) {
+			struct cache_entry *ce = istate->split_index->base->cache[new->index - 1];
+			drop_ce_ref(ce);
+		}
 		istate->split_index->base->cache[new->index - 1] = new;
 	}
 }
diff --git a/unpack-trees.c b/unpack-trees.c
index f932e80..1a0a637 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -606,8 +606,10 @@ static int unpack_nondirectories(int n, unsigned long mask,
 					o);
 		for (i = 0; i < n; i++) {
 			struct cache_entry *ce = src[i + o->merge];
-			if (ce != o->df_conflict_entry)
-				free(ce);
+			if (ce != o->df_conflict_entry) {
+				drop_ce_ref(ce);
+				src[i + o->merge] = NULL;
+			}
 		}
 		return rc;
 	}
-- 
2.4.2.644.g97b850b-twtrsrc

Re: [PATCH 0/1] merge: fix cache_entry use-after-free

[Junio C Hamano]

David Turner <dturner@twopensource.com> writes:

> 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: David Turner <dturner@twopensource.com>
> Signed-off-by: Keith McGuigan <kmcguigan@twitter.com>
> ---

Thanks.

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

We tend to prefer post-increment when the distinction between pre-
or post- does not make any difference, which is the case here.

> diff --git a/name-hash.c b/name-hash.c
> index 702cd05..f12c919 100644
> --- a/name-hash.c
> +++ b/name-hash.c
> @@ -92,7 +93,9 @@ static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)
>  	struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));
>  	while (dir && !(--dir->nr)) {
>  		struct dir_entry *parent = dir->parent;
> -		hashmap_remove(&istate->dir_hash, dir, NULL);
> +		struct dir_entry *removed = hashmap_remove(&istate->dir_hash, dir, NULL);
> +		assert(removed == dir);
> +		drop_ce_ref(dir->ce);

This is curious.  In remove_name_hash() you do not have the
corresponding assert.  Why is it necessary here (or is it
unnecessary over there)?

> @@ -147,6 +151,7 @@ void remove_name_hash(struct index_state *istate, struct cache_entry *ce)
>  		return;
>  	ce->ce_flags &= ~CE_HASHED;
>  	hashmap_remove(&istate->name_hash, ce, ce);
> +	drop_ce_ref(ce);
>  
>  	if (ignore_case)
>  		remove_dir_entry(istate, ce);
> diff --git a/read-cache.c b/read-cache.c
> index 87204a5..442de34 100644
> --- a/read-cache.c
> +++ b/read-cache.c
> @@ -53,6 +53,7 @@ static const char *alternate_index_output;
>  static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
>  {
>  	istate->cache[nr] = ce;
> +	add_ce_ref(ce);
>  	add_name_hash(istate, ce);
>  }

What happens to the existing entry that used to be istate->cache[nr],
which may or may not be 'ce' that is replacing it?

It turns out that all three calling sites are safe, but it is not
immediately obvious why.  Perhaps some comment in front of the
function is in order, to warn those who may have to add a new caller
or restructure the existing calling chain, that istate->cache[nr] is
expected not to hold a live reference when the function is called,
or something?

> @@ -314,8 +314,10 @@ void replace_index_entry_in_base(struct index_state *istate,
>  	    istate->split_index->base &&
>  	    old->index <= istate->split_index->base->cache_nr) {
>  		new->index = old->index;
> -		if (old != istate->split_index->base->cache[new->index - 1])
> -			free(istate->split_index->base->cache[new->index - 1]);
> +		if (old != istate->split_index->base->cache[new->index - 1]) {
> +			struct cache_entry *ce = istate->split_index->base->cache[new->index - 1];
> +			drop_ce_ref(ce);
> +		}
>  		istate->split_index->base->cache[new->index - 1] = new;

Does 'new' already have the right refcount at this point?

Re: [PATCH 0/1] merge: fix cache_entry use-after-free

[David Turner]

+Duy Nguyen, who knows the split index better.

On Thu, 2015-10-08 at 13:00 -0700, Junio C Hamano wrote:
> David Turner <dturner@twopensource.com> writes:
> 
> > 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: David Turner <dturner@twopensource.com>
> > Signed-off-by: Keith McGuigan <kmcguigan@twitter.com>
> > ---
> 
> Thanks.
> 
> > @@ -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;
> > +}
> 
> We tend to prefer post-increment when the distinction between pre-
> or post- does not make any difference, which is the case here.

Will fix.

> > diff --git a/name-hash.c b/name-hash.c
> > index 702cd05..f12c919 100644
> > --- a/name-hash.c
> > +++ b/name-hash.c
> > @@ -92,7 +93,9 @@ static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)
> >  	struct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));
> >  	while (dir && !(--dir->nr)) {
> >  		struct dir_entry *parent = dir->parent;
> > -		hashmap_remove(&istate->dir_hash, dir, NULL);
> > +		struct dir_entry *removed = hashmap_remove(&istate->dir_hash, dir, NULL);
> > +		assert(removed == dir);
> > +		drop_ce_ref(dir->ce);
> 
> This is curious.  In remove_name_hash() you do not have the
> corresponding assert.  Why is it necessary here (or is it
> unnecessary over there)?

It is unnecessary in any case: it's an assert rather than a check for an
expected (or even unexpected) case.  That just happens to be where Keith
first managed to track down the use-after free, so that's where he
happened to put the assert while trying to debug it.  I'm in general in
favor of more asserts rather than fewer, so I would prefer to keep it
in.  But I can remove it if you like.

> > @@ -147,6 +151,7 @@ void remove_name_hash(struct index_state *istate, struct cache_entry *ce)
> >  		return;
> >  	ce->ce_flags &= ~CE_HASHED;
> >  	hashmap_remove(&istate->name_hash, ce, ce);
> > +	drop_ce_ref(ce);
> >  
> >  	if (ignore_case)
> >  		remove_dir_entry(istate, ce);
> > diff --git a/read-cache.c b/read-cache.c
> > index 87204a5..442de34 100644
> > --- a/read-cache.c
> > +++ b/read-cache.c
> > @@ -53,6 +53,7 @@ static const char *alternate_index_output;
> >  static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
> >  {
> >  	istate->cache[nr] = ce;
> > +	add_ce_ref(ce);
> >  	add_name_hash(istate, ce);
> >  }
> 
> What happens to the existing entry that used to be istate->cache[nr],
> which may or may not be 'ce' that is replacing it?
> 
> It turns out that all three calling sites are safe, but it is not
> immediately obvious why.  Perhaps some comment in front of the
> function is in order, to warn those who may have to add a new caller
> or restructure the existing calling chain, that istate->cache[nr] is
> expected not to hold a live reference when the function is called,
> or something?

Happy to add it if you want, but to me it was clear without because if
there were a value in istate->cache[nr], that old value would be leaked.
Let me know.

> > @@ -314,8 +314,10 @@ void replace_index_entry_in_base(struct index_state *istate,
> >  	    istate->split_index->base &&
> >  	    old->index <= istate->split_index->base->cache_nr) {
> >  		new->index = old->index;
> > -		if (old != istate->split_index->base->cache[new->index - 1])
> > -			free(istate->split_index->base->cache[new->index - 1]);
> > +		if (old != istate->split_index->base->cache[new->index - 1]) {
> > +			struct cache_entry *ce = istate->split_index->base->cache[new->index - 1];
> > +			drop_ce_ref(ce);
> > +		}
> >  		istate->split_index->base->cache[new->index - 1] = new;
> 
> Does 'new' already have the right refcount at this point?

I spoke to Keith, and he thinks we do need an add_ce_ref there. I'll fix
that on the reroll.  Duy, do you agree?

Re: [PATCH 0/1] merge: fix cache_entry use-after-free

[Junio C Hamano]

David Turner <dturner@twopensource.com> writes:

>> > +		assert(removed == dir);
>> > +		drop_ce_ref(dir->ce);
>> 
>> This is curious.  In remove_name_hash() you do not have the
>> corresponding assert.  Why is it necessary here (or is it
>> unnecessary over there)?
>
> It is unnecessary in any case: it's an assert rather than a check for an
> expected (or even unexpected) case.  That just happens to be where Keith
> first managed to track down the use-after free, so that's where he
> happened to put the assert while trying to debug it.  I'm in general in
> favor of more asserts rather than fewer, so I would prefer to keep it
> in.  But I can remove it if you like.

OK, it was just the inconsistency between the two made them look
curious, as if one of them is more likely to get broken, or the
patch author was not so sure about the assumption, or something.

>> > +	add_ce_ref(ce);
>> >  	add_name_hash(istate, ce);
>> >  }
>> 
>> What happens to the existing entry that used to be istate->cache[nr],
>> which may or may not be 'ce' that is replacing it?
>> 
>> It turns out that all three calling sites are safe, but it is not
>> immediately obvious why.  Perhaps some comment in front of the
>> function is in order, to warn those who may have to add a new caller
>> or restructure the existing calling chain, that istate->cache[nr] is
>> expected not to hold a live reference when the function is called,
>> or something?
>
> Happy to add it if you want, but to me it was clear without because if
> there were a value in istate->cache[nr], that old value would be leaked.

OK, that's sort-of-cheating, but is a sound short-cut ;-).

>> > +		if (old != istate->split_index->base->cache[new->index - 1]) {
>> > +			struct cache_entry *ce = istate->split_index->base->cache[new->index - 1];
>> > +			drop_ce_ref(ce);
>> > +		}
>> >  		istate->split_index->base->cache[new->index - 1] = new;
>> 
>> Does 'new' already have the right refcount at this point?
>
> I spoke to Keith, and he thinks we do need an add_ce_ref there. I'll fix
> that on the reroll.  Duy, do you agree?