{"thread":{"id":"40544","subject":"[PATCH v2] merge: fix cache_entry use-after-free","startedAt":"2015-10-12T22:03:33Z","lastAt":"2015-10-14T22:00:42Z","messageCount":6,"participants":["David Turner","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"271539","messageId":"1444687413-928-1-git-send-email-dturner@twitter.com","threadId":"40544","inReplyTo":null,"subject":"[PATCH v2] merge: fix cache_entry use-after-free","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-10-12T22:03:33Z","receivedAt":"2015-10-12T22:03:33Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"From: Keith McGuigan <kmcguigan@twitter.com>\n\nDuring merges, we would previously free entries that we no longer need\nin the destination index.  But those entries might also be stored in\nthe dir_entry cache, and when a later call to add_to_index found them,\nthey would be used after being freed.\n\nTo prevent this, add a ref count for struct cache_entry.  Whenever\na cache entry is added to a data structure, the ref count is incremented;\nwhen it is removed from the data structure, it is decremented.  When\nit hits zero, the cache_entry is freed.\n\nSigned-off-by: Keith McGuigan <kmcguigan@twitter.com>\n---\n\nThis version addresses Junio's comments on v1.  It adds a missing\nadd_ce_ref, and fixes a formatting nit.\n\n cache.h        | 27 +++++++++++++++++++++++++++\n name-hash.c    |  7 ++++++-\n read-cache.c   |  6 +++++-\n split-index.c  | 13 ++++++++-----\n unpack-trees.c |  6 ++++--\n 5 files changed, 50 insertions(+), 9 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 752031e..738f76d 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -149,6 +149,7 @@ struct stat_data {\n \n struct cache_entry {\n \tstruct hashmap_entry ent;\n+\tunsigned int ref_count; /* count the number of refs to this in dir_hash */\n \tstruct stat_data ce_stat_data;\n \tunsigned int ce_mode;\n \tunsigned int ce_flags;\n@@ -213,6 +214,32 @@ struct cache_entry {\n struct pathspec;\n \n /*\n+ * Increment the cache_entry reference count.  Should be called\n+ * whenever a pointer to a cache_entry is retained in a data structure,\n+ * thus marking it as alive.\n+ */\n+static inline void add_ce_ref(struct cache_entry *ce)\n+{\n+\tassert(ce != NULL && ce->ref_count >= 0);\n+\tce->ref_count++;\n+}\n+\n+/*\n+ * Decrement the cache_entry reference count.  Should be called whenever\n+ * a pointer to a cache_entry is dropped.  Once the counter drops to 0\n+ * the cache_entry memory will be safely freed.\n+ */\n+static inline void drop_ce_ref(struct cache_entry *ce)\n+{\n+\tif (ce != NULL) {\n+\t\tassert(ce->ref_count >= 0);\n+\t\tif (--ce->ref_count < 1) {\n+\t\t\tfree(ce);\n+\t\t}\n+\t}\n+}\n+\n+/*\n  * Copy the sha1 and stat state of a cache entry from one to\n  * another. But we never change the name, or the hash state!\n  */\ndiff --git a/name-hash.c b/name-hash.c\nindex 702cd05..f12c919 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -66,6 +66,7 @@ static struct dir_entry *hash_dir_entry(struct index_state *istate,\n \t\tdir = xcalloc(1, sizeof(struct dir_entry));\n \t\thashmap_entry_init(dir, memihash(ce->name, namelen));\n \t\tdir->namelen = namelen;\n+\t\tadd_ce_ref(ce);\n \t\tdir->ce = ce;\n \t\thashmap_add(&istate->dir_hash, dir);\n \n@@ -92,7 +93,9 @@ static void remove_dir_entry(struct index_state *istate, struct cache_entry *ce)\n \tstruct dir_entry *dir = hash_dir_entry(istate, ce, ce_namelen(ce));\n \twhile (dir && !(--dir->nr)) {\n \t\tstruct dir_entry *parent = dir->parent;\n-\t\thashmap_remove(&istate->dir_hash, dir, NULL);\n+\t\tstruct dir_entry *removed = hashmap_remove(&istate->dir_hash, dir, NULL);\n+\t\tassert(removed == dir);\n+\t\tdrop_ce_ref(dir->ce);\n \t\tfree(dir);\n \t\tdir = parent;\n \t}\n@@ -105,6 +108,7 @@ static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)\n \tce->ce_flags |= CE_HASHED;\n \thashmap_entry_init(ce, memihash(ce->name, ce_namelen(ce)));\n \thashmap_add(&istate->name_hash, ce);\n+\tadd_ce_ref(ce);\n \n \tif (ignore_case)\n \t\tadd_dir_entry(istate, ce);\n@@ -147,6 +151,7 @@ void remove_name_hash(struct index_state *istate, struct cache_entry *ce)\n \t\treturn;\n \tce->ce_flags &= ~CE_HASHED;\n \thashmap_remove(&istate->name_hash, ce, ce);\n+\tdrop_ce_ref(ce);\n \n \tif (ignore_case)\n \t\tremove_dir_entry(istate, ce);\ndiff --git a/read-cache.c b/read-cache.c\nindex 87204a5..8b685bb 100644\n--- a/read-cache.c\n+++ b/read-cache.c\n@@ -52,7 +52,9 @@ static const char *alternate_index_output;\n \n static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)\n {\n+\t/* istate->cache[nr] is assumed to not hold a live value */\n \tistate->cache[nr] = ce;\n+\tadd_ce_ref(ce);\n \tadd_name_hash(istate, ce);\n }\n \n@@ -62,7 +64,7 @@ static void replace_index_entry(struct index_state *istate, int nr, struct cache\n \n \treplace_index_entry_in_base(istate, old, ce);\n \tremove_name_hash(istate, old);\n-\tfree(old);\n+\tdrop_ce_ref(old);\n \tset_index_entry(istate, nr, ce);\n \tce->ce_flags |= CE_UPDATE_IN_BASE;\n \tistate->cache_changed |= CE_ENTRY_CHANGED;\n@@ -75,6 +77,7 @@ void rename_index_entry_at(struct index_state *istate, int nr, const char *new_n\n \n \tnew = xmalloc(cache_entry_size(namelen));\n \tcopy_cache_entry(new, old);\n+\tnew->ref_count = 0;\n \tnew->ce_flags &= ~CE_HASHED;\n \tnew->ce_namelen = namelen;\n \tnew->index = 0;\n@@ -1426,6 +1429,7 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on\n {\n \tstruct cache_entry *ce = xmalloc(cache_entry_size(len));\n \n+\tce->ref_count = 0;\n \tce->ce_stat_data.sd_ctime.sec = get_be32(&ondisk->ctime.sec);\n \tce->ce_stat_data.sd_mtime.sec = get_be32(&ondisk->mtime.sec);\n \tce->ce_stat_data.sd_ctime.nsec = get_be32(&ondisk->ctime.nsec);\ndiff --git a/split-index.c b/split-index.c\nindex 968b780..61b5631 100644\n--- a/split-index.c\n+++ b/split-index.c\n@@ -124,7 +124,7 @@ static void replace_entry(size_t pos, void *data)\n \tsrc->ce_flags |= CE_UPDATE_IN_BASE;\n \tsrc->ce_namelen = dst->ce_namelen;\n \tcopy_cache_entry(dst, src);\n-\tfree(src);\n+\tdrop_ce_ref(src);\n \tsi->nr_replacements++;\n }\n \n@@ -227,7 +227,7 @@ void prepare_to_write_split_index(struct index_state *istate)\n \t\t\tbase->ce_flags = base_flags;\n \t\t\tif (ret)\n \t\t\t\tce->ce_flags |= CE_UPDATE_IN_BASE;\n-\t\t\tfree(base);\n+\t\t\tdrop_ce_ref(base);\n \t\t\tsi->base->cache[ce->index - 1] = ce;\n \t\t}\n \t\tfor (i = 0; i < si->base->cache_nr; i++) {\n@@ -302,7 +302,7 @@ void save_or_free_index_entry(struct index_state *istate, struct cache_entry *ce\n \t    ce == istate->split_index->base->cache[ce->index - 1])\n \t\tce->ce_flags |= CE_REMOVE;\n \telse\n-\t\tfree(ce);\n+\t\tdrop_ce_ref(ce);\n }\n \n void replace_index_entry_in_base(struct index_state *istate,\n@@ -314,8 +314,11 @@ void replace_index_entry_in_base(struct index_state *istate,\n \t    istate->split_index->base &&\n \t    old->index <= istate->split_index->base->cache_nr) {\n \t\tnew->index = old->index;\n-\t\tif (old != istate->split_index->base->cache[new->index - 1])\n-\t\t\tfree(istate->split_index->base->cache[new->index - 1]);\n+\t\tif (old != istate->split_index->base->cache[new->index - 1]) {\n+\t\t\tstruct cache_entry *ce = istate->split_index->base->cache[new->index - 1];\n+\t\t\tdrop_ce_ref(ce);\n+\t\t}\n \t\tistate->split_index->base->cache[new->index - 1] = new;\n+\t\tadd_ce_ref(new);\n \t}\n }\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex f932e80..1a0a637 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -606,8 +606,10 @@ static int unpack_nondirectories(int n, unsigned long mask,\n \t\t\t\t\to);\n \t\tfor (i = 0; i < n; i++) {\n \t\t\tstruct cache_entry *ce = src[i + o->merge];\n-\t\t\tif (ce != o->df_conflict_entry)\n-\t\t\t\tfree(ce);\n+\t\t\tif (ce != o->df_conflict_entry) {\n+\t\t\t\tdrop_ce_ref(ce);\n+\t\t\t\tsrc[i + o->merge] = NULL;\n+\t\t\t}\n \t\t}\n \t\treturn rc;\n \t}\n-- \n2.4.2.644.g97b850b-twtrsrc\n"},{"id":"271543","messageId":"xmqqio6bbu2w.fsf@gitster.mtv.corp.google.com","threadId":"40544","inReplyTo":"1444687413-928-1-git-send-email-dturner@twitter.com","subject":"Re: [PATCH v2] merge: fix cache_entry use-after-free","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-10-12T22:28:07Z","receivedAt":"2015-10-12T22:28:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\n> From: Keith McGuigan <kmcguigan@twitter.com>\n>\n> During merges, we would previously free entries that we no longer need\n> in the destination index.  But those entries might also be stored in\n> the dir_entry cache, and when a later call to add_to_index found them,\n> they would be used after being freed.\n>\n> To prevent this, add a ref count for struct cache_entry.  Whenever\n> a cache entry is added to a data structure, the ref count is incremented;\n> when it is removed from the data structure, it is decremented.  When\n> it hits zero, the cache_entry is freed.\n>\n> Signed-off-by: Keith McGuigan <kmcguigan@twitter.com>\n> ---\n\nI'll forge your \"messenger's sign-off\" here ;-)\n\n> diff --git a/unpack-trees.c b/unpack-trees.c\n> index f932e80..1a0a637 100644\n> --- a/unpack-trees.c\n> +++ b/unpack-trees.c\n> @@ -606,8 +606,10 @@ static int unpack_nondirectories(int n, unsigned long mask,\n>  \t\t\t\t\to);\n>  \t\tfor (i = 0; i < n; i++) {\n>  \t\t\tstruct cache_entry *ce = src[i + o->merge];\n> -\t\t\tif (ce != o->df_conflict_entry)\n> -\t\t\t\tfree(ce);\n> +\t\t\tif (ce != o->df_conflict_entry) {\n> +\t\t\t\tdrop_ce_ref(ce);\n> +\t\t\t\tsrc[i + o->merge] = NULL;\n> +\t\t\t}\n\nThis one smelled iffy.  I think it is safe because the caller does\nnot look at src[] other than src[0] after this function returns, and\nthis setting to NULL happens only when o->merge is set to 1, so I do\nnot think this is buggy, but at the same time I do not think setting\nto NULL is necessary.\n\nOther than that, looks nice.  Thanks.\n"},{"id":"271590","messageId":"1444764167.7234.14.camel@twopensource.com","threadId":"40544","inReplyTo":"xmqqio6bbu2w.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2] merge: fix cache_entry use-after-free","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-10-13T19:22:47Z","receivedAt":"2015-10-13T19:22:47Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Mon, 2015-10-12 at 15:28 -0700, Junio C Hamano wrote:\n> David Turner <dturner@twopensource.com> writes:\n> \n> > From: Keith McGuigan <kmcguigan@twitter.com>\n> >\n> > During merges, we would previously free entries that we no longer need\n> > in the destination index.  But those entries might also be stored in\n> > the dir_entry cache, and when a later call to add_to_index found them,\n> > they would be used after being freed.\n> >\n> > To prevent this, add a ref count for struct cache_entry.  Whenever\n> > a cache entry is added to a data structure, the ref count is incremented;\n> > when it is removed from the data structure, it is decremented.  When\n> > it hits zero, the cache_entry is freed.\n> >\n> > Signed-off-by: Keith McGuigan <kmcguigan@twitter.com>\n> > ---\n> \n> I'll forge your \"messenger's sign-off\" here ;-)\n\nThanks.\n\n> > diff --git a/unpack-trees.c b/unpack-trees.c\n> > index f932e80..1a0a637 100644\n> > --- a/unpack-trees.c\n> > +++ b/unpack-trees.c\n> > @@ -606,8 +606,10 @@ static int unpack_nondirectories(int n, unsigned long mask,\n> >  \t\t\t\t\to);\n> >  \t\tfor (i = 0; i < n; i++) {\n> >  \t\t\tstruct cache_entry *ce = src[i + o->merge];\n> > -\t\t\tif (ce != o->df_conflict_entry)\n> > -\t\t\t\tfree(ce);\n> > +\t\t\tif (ce != o->df_conflict_entry) {\n> > +\t\t\t\tdrop_ce_ref(ce);\n> > +\t\t\t\tsrc[i + o->merge] = NULL;\n> > +\t\t\t}\n> \n> This one smelled iffy.  I think it is safe because the caller does\n> not look at src[] other than src[0] after this function returns, and\n> this setting to NULL happens only when o->merge is set to 1, so I do\n> not think this is buggy, but at the same time I do not think setting\n> to NULL is necessary.\n> \n> Other than that, looks nice.  Thanks.\n\nI like to set a pointer to NULL after I free the thing pointed to by it,\nbecause it helps make use-after-free bugs easier to detect.  \n"},{"id":"271593","messageId":"xmqqio6aa38e.fsf@gitster.mtv.corp.google.com","threadId":"40544","inReplyTo":"1444764167.7234.14.camel@twopensource.com","subject":"Re: [PATCH v2] merge: fix cache_entry use-after-free","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-10-13T21:05:37Z","receivedAt":"2015-10-13T21:05:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\n>> This one smelled iffy.  I think it is safe because the caller does\n>> not look at src[] other than src[0] after this function returns, and\n>> this setting to NULL happens only when o->merge is set to 1, so I do\n>> not think this is buggy, but at the same time I do not think setting\n>> to NULL is necessary.\n>> \n>> Other than that, looks nice.  Thanks.\n>\n> I like to set a pointer to NULL after I free the thing pointed to by it,\n> because it helps make use-after-free bugs easier to detect.  \n\nYes, but it also helps unintended bugs to creep in if done blindly,\nand that is why I vetted what happens in the codepath of the caller\nof this function after src[] entries are NULLed (the caller could be\nexpecting to do things only to NULLed fields, for example, in which\ncase clearing them like this patch would have changed the behaviour\nof the caller after this function returns).\n\nThanks.\n"},{"id":"271699","messageId":"xmqqk2qp6tg1.fsf@gitster.mtv.corp.google.com","threadId":"40544","inReplyTo":"1444687413-928-1-git-send-email-dturner@twitter.com","subject":"Re: [PATCH v2] merge: fix cache_entry use-after-free","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-10-14T21:17:34Z","receivedAt":"2015-10-14T21:17:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\n> +\tunsigned int ref_count; /* count the number of refs to this in dir_hash */\n\nMe makes a mental note of the type used...\n\n> @@ -213,6 +214,32 @@ struct cache_entry {\n>  struct pathspec;\n>  \n>  /*\n> + * Increment the cache_entry reference count.  Should be called\n> + * whenever a pointer to a cache_entry is retained in a data structure,\n> + * thus marking it as alive.\n> + */\n> +static inline void add_ce_ref(struct cache_entry *ce)\n> +{\n> +\tassert(ce != NULL && ce->ref_count >= 0);\n\n... and notices that ce->ref_count will always be non-negative here\n\n\n> +\tce->ref_count++;\n> +}\n> +\n> +/*\n> + * Decrement the cache_entry reference count.  Should be called whenever\n> + * a pointer to a cache_entry is dropped.  Once the counter drops to 0\n> + * the cache_entry memory will be safely freed.\n> + */\n> +static inline void drop_ce_ref(struct cache_entry *ce)\n> +{\n> +\tif (ce != NULL) {\n> +\t\tassert(ce->ref_count >= 0);\n\n... and here.\n\nBy not checking integer overflow/wraparound, the code is assuming\nthat a ce entry will never referenced more than 4 billion times on\n32-bit platform.  And that is a sensible assumption as there aren't\nthat many pointers in the address space to make that many reference\nanyway.\n\nPerhaps the code can assume the number won't be more than 2 billion\nand use a signed type instead for the reference counting?\n"},{"id":"271703","messageId":"1444860042.18742.13.camel@twopensource.com","threadId":"40544","inReplyTo":"xmqqk2qp6tg1.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2] merge: fix cache_entry use-after-free","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-10-14T22:00:42Z","receivedAt":"2015-10-14T22:00:42Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Wed, 2015-10-14 at 14:17 -0700, Junio C Hamano wrote:\n> David Turner <dturner@twopensource.com> writes:\n> \n> > +\tunsigned int ref_count; /* count the number of refs to this in dir_hash */\n> \n> Me makes a mental note of the type used...\n> \n> > @@ -213,6 +214,32 @@ struct cache_entry {\n> >  struct pathspec;\n> >  \n> >  /*\n> > + * Increment the cache_entry reference count.  Should be called\n> > + * whenever a pointer to a cache_entry is retained in a data structure,\n> > + * thus marking it as alive.\n> > + */\n> > +static inline void add_ce_ref(struct cache_entry *ce)\n> > +{\n> > +\tassert(ce != NULL && ce->ref_count >= 0);\n> \n> ... and notices that ce->ref_count will always be non-negative here\n> \n> \n> > +\tce->ref_count++;\n> > +}\n> > +\n> > +/*\n> > + * Decrement the cache_entry reference count.  Should be called whenever\n> > + * a pointer to a cache_entry is dropped.  Once the counter drops to 0\n> > + * the cache_entry memory will be safely freed.\n> > + */\n> > +static inline void drop_ce_ref(struct cache_entry *ce)\n> > +{\n> > +\tif (ce != NULL) {\n> > +\t\tassert(ce->ref_count >= 0);\n> \n> ... and here.\n> \n> By not checking integer overflow/wraparound, the code is assuming\n> that a ce entry will never referenced more than 4 billion times on\n> 32-bit platform.  And that is a sensible assumption as there aren't\n> that many pointers in the address space to make that many reference\n> anyway.\n> \n> Perhaps the code can assume the number won't be more than 2 billion\n> and use a signed type instead for the reference counting?\n\nWill do.\n"}]}