{"thread":{"id":"33678","subject":"[PATCH] unpack_entry: invalidate newly added cache entry in case of error","startedAt":"2013-04-30T02:29:52Z","lastAt":"2013-04-30T22:39:42Z","messageCount":6,"participants":["Nguyễn Thái Ngọc Duy","Thomas Rast","Duy Nguyen","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"215947","messageId":"1367288992-14979-1-git-send-email-pclouds@gmail.com","threadId":"33678","inReplyTo":null,"subject":"[PATCH] unpack_entry: invalidate newly added cache entry in case of error","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-04-30T02:29:52Z","receivedAt":"2013-04-30T02:29:52Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"In this particular code path, we add \"base\" to the delta base\ncache. Then decide to free it, but we forgot about a dangling pointer\nin the cache. Invalidate that entry when we free \"base\".\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n Some of my changes triggered a double free fault at \"free(base);\" in\n t5303. This looks like a correct thing to do, but I may be missing\n something (I'm not even sure how it happened). Please check.\n\n sha1_file.c | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 64228a2..99ead7c 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1912,7 +1912,8 @@ void clear_delta_base_cache(void)\n \t\trelease_delta_base_cache(&delta_base_cache[p]);\n }\n \n-static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n+static struct delta_base_cache_entry *\n+add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \tvoid *base, unsigned long base_size, enum object_type type)\n {\n \tunsigned long hash = pack_entry_hash(p, base_offset);\n@@ -1947,6 +1948,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \tent->lru.prev = delta_base_cache_lru.prev;\n \tdelta_base_cache_lru.prev->next = &ent->lru;\n \tdelta_base_cache_lru.prev = &ent->lru;\n+\treturn ent;\n }\n \n static void *read_object(const unsigned char *sha1, enum object_type *type,\n@@ -2086,12 +2088,13 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \t\tvoid *delta_data;\n \t\tvoid *base = data;\n \t\tunsigned long delta_size, base_size = size;\n+\t\tstruct delta_base_cache_entry *ent = NULL;\n \t\tint i;\n \n \t\tdata = NULL;\n \n \t\tif (base)\n-\t\t\tadd_delta_base_cache(p, obj_offset, base, base_size, type);\n+\t\t\tent = add_delta_base_cache(p, obj_offset, base, base_size, type);\n \n \t\tif (!base) {\n \t\t\t/*\n@@ -2129,6 +2132,8 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \t\t\t \"at offset %\"PRIuMAX\" from %s\",\n \t\t\t (uintmax_t)curpos, p->pack_name);\n \t\t\tfree(base);\n+\t\t\tif (ent)\n+\t\t\t\tent->data = NULL;\n \t\t\tdata = NULL;\n \t\t\tcontinue;\n \t\t}\n-- \n1.8.2.83.gc99314b\n"},{"id":"215974","messageId":"87ppxcxw1i.fsf@linux-k42r.v.cablecom.net","threadId":"33678","inReplyTo":"1367288992-14979-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] unpack_entry: invalidate newly added cache entry in case of error","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-04-30T08:27:53Z","receivedAt":"2013-04-30T08:27:53Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Nguyễn Thái Ngọc Duy writes:\n\n> In this particular code path, we add \"base\" to the delta base\n> cache. Then decide to free it, but we forgot about a dangling pointer\n> in the cache. Invalidate that entry when we free \"base\".\n>\n> Signed-off-by: Nguyễn Thái Ngọc Duy \n> ---\n> Some of my changes triggered a double free fault at \"free(base);\" in\n> t5303. This looks like a correct thing to do, but I may be missing\n> something (I'm not even sure how it happened). Please check.\n\nCan you describe how you triggered it?\n\nI ran all of origin/pu through valgrind tests just yesterday, and it\nfound nothing (yay!), so it doesn't seem to reproduce here?\n\n> sha1_file.c | 9 +++++++--\n> 1 file changed, 7 insertions(+), 2 deletions(-)\n>\n> diff --git a/sha1_file.c b/sha1_file.c\n> index 64228a2..99ead7c 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -1912,7 +1912,8 @@ void clear_delta_base_cache(void)\n> \t\trelease_delta_base_cache(&delta_base_cache[p]);\n> }\n> \n> -static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n> +static struct delta_base_cache_entry *\n> +add_delta_base_cache(struct packed_git *p, off_t base_offset,\n> \tvoid *base, unsigned long base_size, enum object_type type)\n> {\n> \tunsigned long hash = pack_entry_hash(p, base_offset);\n> @@ -1947,6 +1948,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n> \tent->lru.prev = delta_base_cache_lru.prev;\n> \tdelta_base_cache_lru.prev->next = &ent->lru;\n> \tdelta_base_cache_lru.prev = &ent->lru;\n> +\treturn ent;\n> }\n> \n> static void *read_object(const unsigned char *sha1, enum object_type *type,\n> @@ -2086,12 +2088,13 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n> \t\tvoid *delta_data;\n> \t\tvoid *base = data;\n> \t\tunsigned long delta_size, base_size = size;\n> +\t\tstruct delta_base_cache_entry *ent = NULL;\n> \t\tint i;\n> \n> \t\tdata = NULL;\n> \n> \t\tif (base)\n> -\t\t\tadd_delta_base_cache(p, obj_offset, base, base_size, type);\n> +\t\t\tent = add_delta_base_cache(p, obj_offset, base, base_size, type);\n> \n> \t\tif (!base) {\n> \t\t\t/*\n> @@ -2129,6 +2132,8 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n> \t\t\t \"at offset %\"PRIuMAX\" from %s\",\n> \t\t\t (uintmax_t)curpos, p->pack_name);\n> \t\t\tfree(base);\n> +\t\t\tif (ent)\n> +\t\t\t\tent->data = NULL;\n> \t\t\tdata = NULL;\n> \t\t\tcontinue;\n> \t\t}\n\nWhy not clear_delta_base_cache_entry(), which also handles updating the\nlru pointers?\n\nAlso I wonder if removing free(base) is the right fix: since the failure\nis in decompressing the delta, the base might again be useful and we\nshould keep it cached.\n\nEither way, one of those needs to be done. I think the mistake happened\nin my abe601b (sha1_file: remove recursion in unpack_entry, 2013-03-27).\nThe change concerning this section was roughly:\n\n- base = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);\n- if (!base) {\n[...snip error path...]\n- }\n-\n- delta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);\n- if (!delta_data) {\n- error(\"failed to unpack compressed delta \"\n- \"at offset %\"PRIuMAX\" from %s\",\n- (uintmax_t)curpos, p->pack_name);\n- free(base);\n- return NULL;\n- }\n[...]\n- add_delta_base_cache(p, base_offset, base, base_size, *type);\n\ntransforms into\n\n+ if (base)\n+ add_delta_base_cache(p, obj_offset, base, base_size, type);\n+\n+ if (!base) {\n[...snip error path...]\n+ }\n+\n+ i = --delta_stack_nr;\n+ obj_offset = delta_stack[i].obj_offset;\n+ curpos = delta_stack[i].curpos;\n+ delta_size = delta_stack[i].size;\n+\n+ if (!base)\n+ continue;\n+\n+ delta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);\n+\n+ if (!delta_data) {\n+ error(\"failed to unpack compressed delta \"\n+ \"at offset %\"PRIuMAX\" from %s\",\n+ (uintmax_t)curpos, p->pack_name);\n+ free(base);\n+ data = NULL;\n+ continue;\n+ }\n\nSo it's not your mistake at all. I propose this explanation for the\ncommit message of whatever fix you make:\n\nIn the !delta_data error path of unpack_entry(), we run free(base).\nThis became a window for use-after-free() in abe601b (sha1_file: remove\nrecursion in unpack_entry, 2013-03-27), as follows:\n\nBefore abe601b, we got the 'base' from cache_or_unpack_entry(..., 0);\nkeep_cache=0 tells it to also remove that entry. So the 'base' is at\nthis point not cached, and freeing it in the error path is the right\nthing.\n\nAfter abe601b, the structure changed: we use a three-phase approach\nwhere phase 1 finds the innermost base or a base that is already in the\ncache. In phase 3 we therefore know that all bases we unpack are not\npart of the delta cache yet. (Observe that we pop from the cache in\nphase 1, so this is also true for the very first base.) So we make no\nfurther attempts to look up the bases in the cache, and just call\nadd_delta_base_cache() on every base object we have assembled.\n\nBut the !delta_data error path remained unchanged, and now calls free()\non a base that has already been entered in the cache. This means that\nthere is a use-after-free if we later use the same base again.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"215979","messageId":"CACsJy8Bi6UpfA-0BCFY6H=BAKMmWYgwbf-94yJXEn5Zi4gwPCA@mail.gmail.com","threadId":"33678","inReplyTo":"87ppxcxw1i.fsf@linux-k42r.v.cablecom.net","subject":"Re: [PATCH] unpack_entry: invalidate newly added cache entry in case of error","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-04-30T10:25:05Z","receivedAt":"2013-04-30T10:25:05Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Apr 30, 2013 at 3:27 PM, Thomas Rast wrote:\n> Nguyễn Thái Ngọc Duy writes:\n>\n>> In this particular code path, we add \"base\" to the delta base\n>> cache. Then decide to free it, but we forgot about a dangling pointer\n>> in the cache. Invalidate that entry when we free \"base\".\n>>\n>> Signed-off-by: Nguyễn Thái Ngọc Duy \n>> ---\n>> Some of my changes triggered a double free fault at \"free(base);\" in\n>> t5303. This looks like a correct thing to do, but I may be missing\n>> something (I'm not even sure how it happened). Please check.\n>\n> Can you describe how you triggered it?\n>\n> I ran all of origin/pu through valgrind tests just yesterday, and it\n> found nothing (yay!), so it doesn't seem to reproduce here?\n\nApply this patch on top of master (no need to apply full series) and run t5303\n\nhttp://article.gmane.org/gmane.comp.version-control.git/222895\n\n>> @@ -2129,6 +2132,8 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n>> \"at offset %\"PRIuMAX\" from %s\",\n>> (uintmax_t)curpos, p->pack_name);\n>> free(base);\n>> + if (ent)\n>> + ent->data = NULL;\n>> data = NULL;\n>> continue;\n>> }\n>\n> Why not clear_delta_base_cache_entry(), which also handles updating the\n> lru pointers?\n\nSimple. I didn't know about clear_de..entry().\n\n> Also I wonder if removing free(base) is the right fix: since the failure\n> is in decompressing the delta, the base might again be useful and we\n> should keep it cached.\n\nOK since you know this code much better than me, I withdraw my patch\n(consider it a bug report) and let you work on a proper fix. I see you\nalready have the commit message ready :) Happy to test it for you if\nthe above instruction is still not reproducible for you.\n--\nDuy\n"},{"id":"215987","messageId":"87d2tcw571.fsf@linux-k42r.v.cablecom.net","threadId":"33678","inReplyTo":"CACsJy8Bi6UpfA-0BCFY6H=BAKMmWYgwbf-94yJXEn5Zi4gwPCA@mail.gmail.com","subject":"Re: [PATCH] unpack_entry: invalidate newly added cache entry in case of error","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-04-30T12:53:06Z","receivedAt":"2013-04-30T12:53:06Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Duy Nguyen writes:\n\n> Apply this patch on top of master (no need to apply full series) and run t5303\n>\n> http://article.gmane.org/gmane.comp.version-control.git/222895\n[...]\n> OK since you know this code much better than me, I withdraw my patch\n> (consider it a bug report) and let you work on a proper fix. I see you\n> already have the commit message ready :) Happy to test it for you if\n> the above instruction is still not reproducible for you.\n\nOk. So I really think just dropping the free() is the way to go. Can\nyou test this? Your series didn't apply cleanly on anything I had\nlocally, and 'am -3' doesn't work. A simpler reproducer, and using\nvalgrind to detect the use-after-free, didn't get me anywhere either.\n\n-- >8 --\nSubject: [PATCH] unpack_entry: avoid freeing objects in base cache\nMIME-Version: 1.0\nContent-Type: text/plain; charset=UTF-8\nContent-Transfer-Encoding: 8bit\n\nIn the !delta_data error path of unpack_entry(), we run free(base).\nThis became a window for use-after-free() in abe601b (sha1_file:\nremove recursion in unpack_entry, 2013-03-27), as follows:\n\nBefore abe601b, we got the 'base' from cache_or_unpack_entry(..., 0);\nkeep_cache=0 tells it to also remove that entry. So the 'base' is at\nthis point not cached, and freeing it in the error path is the right\nthing.\n\nAfter abe601b, the structure changed: we use a three-phase approach\nwhere phase 1 finds the innermost base or a base that is already in\nthe cache. In phase 3 we therefore know that all bases we unpack are\nnot part of the delta cache yet. (Observe that we pop from the cache\nin phase 1, so this is also true for the very first base.) So we make\nno further attempts to look up the bases in the cache, and just call\nadd_delta_base_cache() on every base object we have assembled.\n\nBut the !delta_data error path remained unchanged, and now calls\nfree() on a base that has already been entered in the cache. This\nmeans that there is a use-after-free if we later use the same base\nagain.\n\nSo remove that free().\n\nReported-by: Nguyễn Thái Ngọc Duy \nSigned-off-by: Thomas Rast \n---\n sha1_file.c | 1 -\n 1 file changed, 1 deletion(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 64228a2..67e815b 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2128,7 +2128,6 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n \t\t\terror(\"failed to unpack compressed delta \"\n \t\t\t \"at offset %\"PRIuMAX\" from %s\",\n \t\t\t (uintmax_t)curpos, p->pack_name);\n-\t\t\tfree(base);\n \t\t\tdata = NULL;\n \t\t\tcontinue;\n \t\t}\n-- \n1.8.3.rc0.333.gdb39496\n"},{"id":"215989","messageId":"CACsJy8DewY=fW+sF9Nrs1A7zEPzdVXr52kwCgnjAvaQy7qq3EQ@mail.gmail.com","threadId":"33678","inReplyTo":"87d2tcw571.fsf@linux-k42r.v.cablecom.net","subject":"Re: [PATCH] unpack_entry: invalidate newly added cache entry in case of error","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-04-30T13:01:30Z","receivedAt":"2013-04-30T13:01:30Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Apr 30, 2013 at 7:53 PM, Thomas Rast wrote:\n> Duy Nguyen writes:\n>\n>> Apply this patch on top of master (no need to apply full series) and run t5303\n>>\n>> http://article.gmane.org/gmane.comp.version-control.git/222895\n> [...]\n>> OK since you know this code much better than me, I withdraw my patch\n>> (consider it a bug report) and let you work on a proper fix. I see you\n>> already have the commit message ready :) Happy to test it for you if\n>> the above instruction is still not reproducible for you.\n>\n> Ok. So I really think just dropping the free() is the way to go. Can\n> you test this? Your series didn't apply cleanly on anything I had\n> locally, and 'am -3' doesn't work. A simpler reproducer, and using\n> valgrind to detect the use-after-free, didn't get me anywhere either.\n\nConfirmed the double free is gone. I also run it under valgrind and\nfound nothing special.\n\n> -- >8 --\n> Subject: [PATCH] unpack_entry: avoid freeing objects in base cache\n> MIME-Version: 1.0\n> Content-Type: text/plain; charset=UTF-8\n> Content-Transfer-Encoding: 8bit\n>\n> In the !delta_data error path of unpack_entry(), we run free(base).\n> This became a window for use-after-free() in abe601b (sha1_file:\n> remove recursion in unpack_entry, 2013-03-27), as follows:\n>\n> Before abe601b, we got the 'base' from cache_or_unpack_entry(..., 0);\n> keep_cache=0 tells it to also remove that entry. So the 'base' is at\n> this point not cached, and freeing it in the error path is the right\n> thing.\n>\n> After abe601b, the structure changed: we use a three-phase approach\n> where phase 1 finds the innermost base or a base that is already in\n> the cache. In phase 3 we therefore know that all bases we unpack are\n> not part of the delta cache yet. (Observe that we pop from the cache\n> in phase 1, so this is also true for the very first base.) So we make\n> no further attempts to look up the bases in the cache, and just call\n> add_delta_base_cache() on every base object we have assembled.\n>\n> But the !delta_data error path remained unchanged, and now calls\n> free() on a base that has already been entered in the cache. This\n> means that there is a use-after-free if we later use the same base\n> again.\n>\n> So remove that free().\n>\n> Reported-by: Nguyễn Thái Ngọc Duy \n> Signed-off-by: Thomas Rast \n> ---\n> sha1_file.c | 1 -\n> 1 file changed, 1 deletion(-)\n>\n> diff --git a/sha1_file.c b/sha1_file.c\n> index 64228a2..67e815b 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -2128,7 +2128,6 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n> error(\"failed to unpack compressed delta \"\n> \"at offset %\"PRIuMAX\" from %s\",\n> (uintmax_t)curpos, p->pack_name);\n> - free(base);\n> data = NULL;\n> continue;\n> }\n> --\n> 1.8.3.rc0.333.gdb39496\n\n\n\n--\nDuy\n"},{"id":"216087","messageId":"7vfvy7abip.fsf@alter.siamese.dyndns.org","threadId":"33678","inReplyTo":"87d2tcw571.fsf@linux-k42r.v.cablecom.net","subject":"Re: [PATCH] unpack_entry: invalidate newly added cache entry in case of error","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-04-30T22:39:42Z","receivedAt":"2013-04-30T22:39:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Duy Nguyen writes:\n>\n>> Apply this patch on top of master (no need to apply full series) and run t5303\n>>\n>> http://article.gmane.org/gmane.comp.version-control.git/222895\n> [...]\n>> OK since you know this code much better than me, I withdraw my patch\n>> (consider it a bug report) and let you work on a proper fix. I see you\n>> already have the commit message ready :) Happy to test it for you if\n>> the above instruction is still not reproducible for you.\n>\n> Ok. So I really think just dropping the free() is the way to go. Can\n> you test this? Your series didn't apply cleanly on anything I had\n> locally, and 'am -3' doesn't work. A simpler reproducer, and using\n> valgrind to detect the use-after-free, didn't get me anywhere either.\n>\n> -- >8 --\n> Subject: [PATCH] unpack_entry: avoid freeing objects in base cache\n> MIME-Version: 1.0\n> Content-Type: text/plain; charset=UTF-8\n> Content-Transfer-Encoding: 8bit\n\nI see you used \"git-pu format-patch --inline-single\" here, and the\nabove is the reason why it is marked as \"not ready for public\nconsumption\" ;-).\n\n> In the !delta_data error path of unpack_entry(), we run free(base).\n> This became a window for use-after-free() in abe601b (sha1_file:\n> remove recursion in unpack_entry, 2013-03-27), as follows:\n>\n> Before abe601b, we got the 'base' from cache_or_unpack_entry(..., 0);\n> keep_cache=0 tells it to also remove that entry. So the 'base' is at\n> this point not cached, and freeing it in the error path is the right\n> thing.\n>\n> After abe601b, the structure changed: we use a three-phase approach\n> where phase 1 finds the innermost base or a base that is already in\n> the cache. In phase 3 we therefore know that all bases we unpack are\n> not part of the delta cache yet. (Observe that we pop from the cache\n> in phase 1, so this is also true for the very first base.) So we make\n> no further attempts to look up the bases in the cache, and just call\n> add_delta_base_cache() on every base object we have assembled.\n>\n> But the !delta_data error path remained unchanged, and now calls\n> free() on a base that has already been entered in the cache. This\n> means that there is a use-after-free if we later use the same base\n> again.\n>\n> So remove that free().\n\nI wish I saw \"We are still going to use it, and it will be freed\nafter we are done\" or something like that after this sentence.\n\nBut other than that, I think the logic is correct.\n\n> Reported-by: Nguyễn Thái Ngọc Duy \n> Signed-off-by: Thomas Rast \n> ---\n> sha1_file.c | 1 -\n> 1 file changed, 1 deletion(-)\n>\n> diff --git a/sha1_file.c b/sha1_file.c\n> index 64228a2..67e815b 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -2128,7 +2128,6 @@ void *unpack_entry(struct packed_git *p, off_t obj_offset,\n> \t\t\terror(\"failed to unpack compressed delta \"\n> \t\t\t \"at offset %\"PRIuMAX\" from %s\",\n> \t\t\t (uintmax_t)curpos, p->pack_name);\n> -\t\t\tfree(base);\n> \t\t\tdata = NULL;\n> \t\t\tcontinue;\n> \t\t}\n"}]}