{"thread":{"id":"54289","subject":"RFC - concurrency causes segfault in git grep since 2.26.0","startedAt":"2020-09-25T02:36:21Z","lastAt":"2020-10-02T20:07:00Z","messageCount":12,"participants":["Phil Hord","Matheus Tavares","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"406293","messageId":"CABURp0r_VPNeU5ugbJDQo=hV_aOit7W-pf9nhDF9Og=vVJG8tw@mail.gmail.com","threadId":"54289","inReplyTo":null,"subject":"RFC - concurrency causes segfault in git grep since 2.26.0","fromName":"Phil Hord","fromEmail":"phil.hord@gmail.com","sentAt":"2020-09-25T02:36:06Z","receivedAt":"2020-09-25T02:36:21Z","isPatch":false,"sender":{"key":"phil.hord@gmail.com","avatar":"https://avatars.githubusercontent.com/u/123908?v=4"},"body":"Hi list.  It's been a while.\n\nI can reliably reproduce a segfault in git grep when searching the\nobject DB. It is caused by a race when threads > 2.\n\nI have a patch that fixes the problem, but I don't know exactly why.\nCan someone else explain it and/or offer a better solution?\n\n====\n\ndiff --git packfile.c packfile.c\nindex e69012e7f2..52b7b54aeb 100644\n--- packfile.c\n+++ packfile.c\n@@ -1812,7 +1812,9 @@ void *unpack_entry(struct repository *r, struct\npacked_git *p, off_t obj_offset,\n                if (!base)\n                        continue;\n\n+               obj_read_lock();\n                delta_data = unpack_compressed_entry(p, &w_curs,\ncurpos, delta_size);\n+               obj_read_unlock();\n\n                if (!delta_data) {\n                        error(\"failed to unpack compressed delta \"\n\n====\n\nMy notes thus far:\n\nI have seen it fail with `--threads 3`, but it fails very reliably for\nme with `--threads 20`.\n\nMy repo is large (7GB) which gives grep enough to do. I'm not able to\nmake it fail on git.git; it seems like it's too small to run into this\nproblem.\n\nThe problem bisects to 1d1729caeb.  It was somewhat hard to find this,\nthough, because git grep disables --threads when reading from the\nobject store until another patch later in the same series.\n\n====\n\n$ git bisect run sh -c \\\n    \"sed -i -e 's/list.nr || cached || show_in_pager/list.nr ||\nshow_in_pager/' builtin/grep.c || exit 129;\n    make -j 30 || exit 125;\n    git checkout HEAD -- builtin/grep.c ;\n    ./bin-wrappers/git -C ~/git/purity grep --threads 20 --cached\n'target-regex' || exit 1\"\n\n1d1729caebd41b340dd8dd61057f613da4df526c is the first bad commit\ncommit 1d1729caebd41b340dd8dd61057f613da4df526c\nAuthor: Matheus Tavares <matheus.bernardino@usp.br>\nDate:   Wed Jan 15 23:39:54 2020 -0300\n\n    grep: replace grep_read_mutex by internal obj read lock\n\nHere's what I'm testing with:\n$ ./bin-wrappers/git --version\ngit version 2.28.0.585.ge1cfff6765\n\nI have found that the crash always happens in cache_or_unpack_entry.\nThe thread that segfaults is always in patch_delta, and there are\nalways at least two threads inside unpack_compressed_entry at the time\nof the failure.\n\nI was able to get it to crash with just three threads one time.  I\ncopied a log with the stack trace of all (4) threads during that run\nto a gist [1].\n\nAnother log showing four different segfaults when run with 40 threads\nis also in that gist [1].\n\n[1] https://gist.github.com/phord/02e84d003688baa493b978110225d443\n"},{"id":"406298","messageId":"20200925055258.79347-1-matheus.bernardino@usp.br","threadId":"54289","inReplyTo":"CABURp0r_VPNeU5ugbJDQo=hV_aOit7W-pf9nhDF9Og=vVJG8tw@mail.gmail.com","subject":"Re: RFC - concurrency causes segfault in git grep since 2.26.0","fromName":"Matheus Tavares","fromEmail":"matheus.bernardino@usp.br","sentAt":"2020-09-25T05:52:58Z","receivedAt":"2020-09-25T05:53:12Z","isPatch":false,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"Hi, Phil\n\nThanks for the bug report and for the crash logs.\n\nOn Thu, Sep 24, 2020 at 11:36 PM Phil Hord <phil.hord@gmail.com> wrote:\n>\n> Hi list.  It's been a while.\n>\n> I can reliably reproduce a segfault in git grep when searching the\n> object DB. It is caused by a race when threads > 2.\n>\n> I have a patch that fixes the problem, but I don't know exactly why.\n> Can someone else explain it and/or offer a better solution?\n>\n> ====\n>\n> diff --git packfile.c packfile.c\n> index e69012e7f2..52b7b54aeb 100644\n> --- packfile.c\n> +++ packfile.c\n> @@ -1812,7 +1812,9 @@ void *unpack_entry(struct repository *r, struct\n> packed_git *p, off_t obj_offset,\n>                 if (!base)\n>                         continue;\n>\n> +               obj_read_lock();\n>                 delta_data = unpack_compressed_entry(p, &w_curs,\n> curpos, delta_size);\n> +               obj_read_unlock();\n>\n>                 if (!delta_data) {\n>                         error(\"failed to unpack compressed delta \"\n>\n> ====\n\nHmm, obj_read_mutex is a recursive lock, so by adding the\nobj_read_lock() call here, we are incrementing the lock value to [at\nleast] 2 (because oid_object_info_extended() had already incremented\nonce). Therefore, when unpack_compressed_entry() calls obj_read_unlock()\nbefore inflating the entry, the lock is not actually released, only\ndecremented. So the effect of this change is that the phase III of\nunpack_entry() is performed entirely without releasing the lock.\n\nYour crash log shows us that the segfault happened when trying to\nmemcpy() the string `base` (in unpack_entry()). I.e., the same string\nthat we had previously added to the delta base cache, right before\ncalling unpack_compressed_entry() and releasing the lock. The\nproblematic sequence is:\n\tadd `base` to the cache -> release lock -> inflate ->\n\tacquire lock -> try to use `base`\n\nMaybe, when a thread X releases the lock to perform decompression,\nthread Y acquires the lock and tries to add another base to the cache.\nThe cache is full, so Y has to remove entries, and it ends up free()'ing\nthe base that was just inserted by X. Later, X tries to dereference\n`base` in patch_entry(), which would cause a segfault. It would also\nexplain why your change solves the segfault.\n\nI'm not sure, though, why this entry would be removed, since it was just\nadded... Maybe Y was adding a huge base to the cache, which required\nremoving all entries?\n\nAnyways, you mentioned you can reproduce the failure quite reliably in your\nrepo with 20 threads, right? Could you please check with the following patch\napplied? It adds a `base` copy to the cache instead of the original string,\nallowing us to keep running decompression in parallel but without the risk of\nhaving another thread free()'ing `base` in the mean time.\n\ndiff --git a/packfile.c b/packfile.c\nindex 9ef27508f2..79f83b6034 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1772,14 +1772,15 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n \twhile (delta_stack_nr) {\n \t\tvoid *delta_data;\n \t\tvoid *base = data;\n-\t\tvoid *external_base = NULL;\n \t\tunsigned long delta_size, base_size = size;\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\tif (base) {\n+\t\t\tchar *base_dup = memcpy(xmalloc(base_size), base, base_size);\n+\t\t\tadd_delta_base_cache(p, obj_offset, base_dup, base_size, type);\n+\t\t}\n \n \t\tif (!base) {\n \t\t\t/*\n@@ -1799,7 +1800,6 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n \t\t\t\t      p->pack_name);\n \t\t\t\tmark_bad_packed_object(p, base_oid.hash);\n \t\t\t\tbase = read_object(r, &base_oid, &type, &base_size);\n-\t\t\t\texternal_base = base;\n \t\t\t}\n \t\t}\n \n@@ -1818,7 +1818,7 @@ void *unpack_entry(struct repository *r, 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\tdata = NULL;\n-\t\t\tfree(external_base);\n+\t\t\tfree(base);\n \t\t\tcontinue;\n \t\t}\n \n@@ -1838,7 +1838,7 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n \t\t\terror(\"failed to apply delta\");\n \n \t\tfree(delta_data);\n-\t\tfree(external_base);\n+\t\tfree(base);\n \t}\n \n \tif (final_type)\n--\n"},{"id":"406392","messageId":"CABURp0puC324750dZUpeXBricWizy9Ldaz_=JzdvdOkUp8V4pA@mail.gmail.com","threadId":"54289","inReplyTo":"20200925055258.79347-1-matheus.bernardino@usp.br","subject":"Re: RFC - concurrency causes segfault in git grep since 2.26.0","fromName":"Phil Hord","fromEmail":"phil.hord@gmail.com","sentAt":"2020-09-25T19:53:03Z","receivedAt":"2020-09-25T20:38:22Z","isPatch":false,"sender":{"key":"phil.hord@gmail.com","avatar":"https://avatars.githubusercontent.com/u/123908?v=4"},"body":"Hi Matheus,\n\nThanks for the quick response.\n\nOn Thu, Sep 24, 2020 at 10:53 PM Matheus Tavares\n<matheus.bernardino@usp.br> wrote:\n>\n> Hi, Phil\n>\n> Thanks for the bug report and for the crash logs.\n>\n> On Thu, Sep 24, 2020 at 11:36 PM Phil Hord <phil.hord@gmail.com> wrote:\n> >\n> > Hi list.  It's been a while.\n> >\n> > I can reliably reproduce a segfault in git grep when searching the\n> > object DB. It is caused by a race when threads > 2.\n> >\n> > I have a patch that fixes the problem, but I don't know exactly why.\n> > Can someone else explain it and/or offer a better solution?\n> >\n> > ====\n> >\n> > diff --git packfile.c packfile.c\n> > index e69012e7f2..52b7b54aeb 100644\n> > --- packfile.c\n> > +++ packfile.c\n> > @@ -1812,7 +1812,9 @@ void *unpack_entry(struct repository *r, struct\n> > packed_git *p, off_t obj_offset,\n> >                 if (!base)\n> >                         continue;\n> >\n> > +               obj_read_lock();\n> >                 delta_data = unpack_compressed_entry(p, &w_curs,\n> > curpos, delta_size);\n> > +               obj_read_unlock();\n> >\n> >                 if (!delta_data) {\n> >                         error(\"failed to unpack compressed delta \"\n> >\n> > ====\n>\n> Hmm, obj_read_mutex is a recursive lock, so by adding the\n> obj_read_lock() call here, we are incrementing the lock value to [at\n> least] 2 (because oid_object_info_extended() had already incremented\n> once). Therefore, when unpack_compressed_entry() calls obj_read_unlock()\n> before inflating the entry, the lock is not actually released, only\n> decremented. So the effect of this change is that the phase III of\n> unpack_entry() is performed entirely without releasing the lock.\n\nAh, there's the piece I was missing.  I didn't realize we temporarily\ndrop the lock inside unpack_compressed_entry.  And obviously I also\ndidn't notice that we were already holding a lock before entering\nunpack_entry.  Thanks for the detailed explanation.\n\n> Your crash log shows us that the segfault happened when trying to\n> memcpy() the string `base` (in unpack_entry()). I.e., the same string\n> that we had previously added to the delta base cache, right before\n> calling unpack_compressed_entry() and releasing the lock. The\n> problematic sequence is:\n>         add `base` to the cache -> release lock -> inflate ->\n>         acquire lock -> try to use `base`\n>\n> Maybe, when a thread X releases the lock to perform decompression,\n> thread Y acquires the lock and tries to add another base to the cache.\n> The cache is full, so Y has to remove entries, and it ends up free()'ing\n> the base that was just inserted by X. Later, X tries to dereference\n> `base` in patch_entry(), which would cause a segfault. It would also\n> explain why your change solves the segfault.\n>\n> I'm not sure, though, why this entry would be removed, since it was just\n> added... Maybe Y was adding a huge base to the cache, which required\n> removing all entries?\n\nI think your theory is correct here on both counts.  The repo I am\nsearching has some sinfully large objects, and when there is a cache\nlimit, they are likely to exceed it.\n\n> Anyways, you mentioned you can reproduce the failure quite reliably in your\n> repo with 20 threads, right? Could you please check with the following patch\n> applied? It adds a `base` copy to the cache instead of the original string,\n> allowing us to keep running decompression in parallel but without the risk of\n> having another thread free()'ing `base` in the mean time.\n\n\nYes, your patch reliably solves the problem, too.  The performance is\nonly slightly improved over holding the lock during inflate in my\ncase, but it does save a bit of time.  Surprisingly, performance seems\nto peak between 5 and 10 threads for me in both cases.  It reliably\ngets slightly worse at 20 threads and 40 threads.\n\nIn all cases when threads > 2, this search appears to be 10%-20%\nslower than running without this change.  Even when threads=1, though,\nthe result is about 10% slower.  Perhaps it is worth avoiding the\nbase_dup when !!obj_read_use_lock.\n\n> diff --git a/packfile.c b/packfile.c\n> index 9ef27508f2..79f83b6034 100644\n> --- a/packfile.c\n> +++ b/packfile.c\n> @@ -1772,14 +1772,15 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n>         while (delta_stack_nr) {\n>                 void *delta_data;\n>                 void *base = data;\n> -               void *external_base = NULL;\n>                 unsigned long delta_size, base_size = size;\n>                 int i;\n>\n>                 data = NULL;\n>\n> -               if (base)\n> -                       add_delta_base_cache(p, obj_offset, base, base_size, type);\n> +               if (base) {\n> +                       char *base_dup = memcpy(xmalloc(base_size), base, base_size);\n> +                       add_delta_base_cache(p, obj_offset, base_dup, base_size, type);\n> +               }\n>\n>                 if (!base) {\n>                         /*\n> @@ -1799,7 +1800,6 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n>                                       p->pack_name);\n>                                 mark_bad_packed_object(p, base_oid.hash);\n>                                 base = read_object(r, &base_oid, &type, &base_size);\n> -                               external_base = base;\n>                         }\n>                 }\n>\n> @@ -1818,7 +1818,7 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n>                               \"at offset %\"PRIuMAX\" from %s\",\n>                               (uintmax_t)curpos, p->pack_name);\n>                         data = NULL;\n> -                       free(external_base);\n> +                       free(base);\n>                         continue;\n>                 }\n>\n> @@ -1838,7 +1838,7 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n>                         error(\"failed to apply delta\");\n>\n>                 free(delta_data);\n> -               free(external_base);\n> +               free(base);\n>         }\n>\n>         if (final_type)\n> --\n"},{"id":"406543","messageId":"cover.1601311803.git.matheus.bernardino@usp.br","threadId":"54289","inReplyTo":"CABURp0puC324750dZUpeXBricWizy9Ldaz_=JzdvdOkUp8V4pA@mail.gmail.com","subject":"[PATCH 0/2] Fix race condition and memory leak in delta base cache","fromName":"Matheus Tavares","fromEmail":"matheus.bernardino@usp.br","sentAt":"2020-09-28T16:50:33Z","receivedAt":"2020-09-28T16:51:05Z","isPatch":true,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"The first patch fixes the race condition problem reported by Phil, which\nocasionally caused a segmentation fault during git-grep executions. The\nsecond patch fixes a memory leak in the same code.\n\nMatheus Tavares (2):\n  packfile: fix race condition on unpack_entry()\n  packfile: fix memory leak in add_delta_base_cache()\n\n packfile.c | 51 +++++++++++++++++++++++++++++++--------------------\n 1 file changed, 31 insertions(+), 20 deletions(-)\n\n-- \n2.28.0\n\n"},{"id":"406544","messageId":"42a7948f94cb57ebd9c37c3850b46b1ac9813ec6.1601311803.git.matheus.bernardino@usp.br","threadId":"54289","inReplyTo":"cover.1601311803.git.matheus.bernardino@usp.br","subject":"[PATCH 1/2] packfile: fix race condition on unpack_entry()","fromName":"Matheus Tavares","fromEmail":"matheus.bernardino@usp.br","sentAt":"2020-09-28T16:50:34Z","receivedAt":"2020-09-28T16:51:09Z","isPatch":true,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"The third phase of unpack_entry() performs the following sequence in a\nloop, until all the deltas enumerated in phase one are applied and the\nentry is fully reconstructed:\n\n1. Add the current base entry to the delta base cache\n2. Unpack the next delta\n3. Patch the unpacked delta on top of the base\n\nWhen the optional object reading lock is enabled, the above steps will\nbe performed while holding the lock. However, step 2. momentarily\nreleases it so that inflation can be performed in parallel for increased\nperformance. Because the `base` buffer inserted in the cache at 1. is\nnot duplicated, another thread can potentially free() it while the lock\nis released at 2. (e.g. when there is no space left in the cache to\ninsert another entry). In this case, the later attempt to dereference\n`base` at 3. will cause a segmentation fault. This problem was observed\nduring a multithreaded git-grep execution on a repository with large\nobjects.\n\nTo fix the race condition (and later segmentation fault), let's reorder\nthe aforementioned steps so that the lock is not released between 1.\nand 3. An alternative solution which would not require the reordering\nwould be to duplicate `base` before inserting it in the cache.\nHowever, as Phil Hord mentioned, memcpy()'ing large bases can negatively\naffect performance: in his experiments, this alternative approach slowed\ngit-grep down by 10% to 20%.\n\nReported-by: Phil Hord <phil.hord@gmail.com>\nSigned-off-by: Matheus Tavares <matheus.bernardino@usp.br>\n---\n packfile.c | 41 ++++++++++++++++++++++++-----------------\n 1 file changed, 24 insertions(+), 17 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 9ef27508f2..0319418d88 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1775,12 +1775,10 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n \t\tvoid *external_base = NULL;\n \t\tunsigned long delta_size, base_size = size;\n \t\tint i;\n+\t\toff_t base_obj_offset = obj_offset;\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-\n \t\tif (!base) {\n \t\t\t/*\n \t\t\t * We're probably in deep shit, but let's try to fetch\n@@ -1818,24 +1816,33 @@ void *unpack_entry(struct repository *r, 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\tdata = NULL;\n-\t\t\tfree(external_base);\n-\t\t\tcontinue;\n-\t\t}\n+\t\t} else {\n+\t\t\tdata = patch_delta(base, base_size, delta_data,\n+\t\t\t\t\t   delta_size, &size);\n \n-\t\tdata = patch_delta(base, base_size,\n-\t\t\t\t   delta_data, delta_size,\n-\t\t\t\t   &size);\n+\t\t\t/*\n+\t\t\t * We could not apply the delta; warn the user, but\n+\t\t\t * keep going. Our failure will be noticed either in\n+\t\t\t * the next iteration of the loop, or if this is the\n+\t\t\t * final delta, in the caller when we return NULL.\n+\t\t\t * Those code paths will take care of making a more\n+\t\t\t * explicit warning and retrying with another copy of\n+\t\t\t * the object.\n+\t\t\t */\n+\t\t\tif (!data)\n+\t\t\t\terror(\"failed to apply delta\");\n+\t\t}\n \n \t\t/*\n-\t\t * We could not apply the delta; warn the user, but keep going.\n-\t\t * Our failure will be noticed either in the next iteration of\n-\t\t * the loop, or if this is the final delta, in the caller when\n-\t\t * we return NULL. Those code paths will take care of making\n-\t\t * a more explicit warning and retrying with another copy of\n-\t\t * the object.\n+\t\t * We delay adding `base` to the cache until the end of the loop\n+\t\t * because unpack_compressed_entry() momentarily releases the\n+\t\t * obj_read_mutex, giving another thread the chance to access\n+\t\t * the cache. Therefore, if `base` was already there, this other\n+\t\t * thread could free() it (e.g. to make space for another entry)\n+\t\t * before we are done using it.\n \t\t */\n-\t\tif (!data)\n-\t\t\terror(\"failed to apply delta\");\n+\t\tif (!external_base)\n+\t\t\tadd_delta_base_cache(p, base_obj_offset, base, base_size, type);\n \n \t\tfree(delta_data);\n \t\tfree(external_base);\n-- \n2.28.0\n\n"},{"id":"406545","messageId":"5b6e3019e08c6bccdee29018e99b0c6933fe05e0.1601311803.git.matheus.bernardino@usp.br","threadId":"54289","inReplyTo":"cover.1601311803.git.matheus.bernardino@usp.br","subject":"[PATCH 2/2] packfile: fix memory leak in add_delta_base_cache()","fromName":"Matheus Tavares","fromEmail":"matheus.bernardino@usp.br","sentAt":"2020-09-28T16:50:35Z","receivedAt":"2020-09-28T16:51:13Z","isPatch":true,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"When add_delta_base_cache() is called with a base that is already in the\ncache, no operation is performed. But the check is done after allocating\nspace for a new entry, so we end up leaking memory on the early return.\nAlso, the caller always expect that the base will be inserted, so it\nnever free()'s it. To fix both of these memory leaks, let's move the\nallocation of a new entry further down in add_delta_base_cache(), and\nmake the function return an integer to indicate whether the insertion\nwas performed or not. Then, make the caller free() the base when needed.\n\nSigned-off-by: Matheus Tavares <matheus.bernardino@usp.br>\n---\n packfile.c | 14 +++++++++-----\n 1 file changed, 9 insertions(+), 5 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 0319418d88..177793e01a 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1471,10 +1471,10 @@ void clear_delta_base_cache(void)\n \t}\n }\n \n-static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n+static int 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-\tstruct delta_base_cache_entry *ent = xmalloc(sizeof(*ent));\n+\tstruct delta_base_cache_entry *ent;\n \tstruct list_head *lru, *tmp;\n \n \t/*\n@@ -1483,7 +1483,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \t * and III might run concurrently across multiple threads).\n \t */\n \tif (in_delta_base_cache(p, base_offset))\n-\t\treturn;\n+\t\treturn 0;\n \n \tdelta_base_cached += base_size;\n \n@@ -1495,6 +1495,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \t\trelease_delta_base_cache(f);\n \t}\n \n+\tent = xmalloc(sizeof(*ent));\n \tent->key.p = p;\n \tent->key.base_offset = base_offset;\n \tent->type = type;\n@@ -1506,6 +1507,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \t\thashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, NULL, 0);\n \thashmap_entry_init(&ent->ent, pack_entry_hash(p, base_offset));\n \thashmap_add(&delta_base_cache, &ent->ent);\n+\treturn 1;\n }\n \n int packed_object_info(struct repository *r, struct packed_git *p,\n@@ -1841,8 +1843,10 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n \t\t * thread could free() it (e.g. to make space for another entry)\n \t\t * before we are done using it.\n \t\t */\n-\t\tif (!external_base)\n-\t\t\tadd_delta_base_cache(p, base_obj_offset, base, base_size, type);\n+\t\tif (!external_base && !add_delta_base_cache(p, base_obj_offset,\n+\t\t\t\t\t\tbase, base_size, type)) {\n+\t\t\tfree(base);\n+\t\t}\n \n \t\tfree(delta_data);\n \t\tfree(external_base);\n-- \n2.28.0\n\n"},{"id":"406549","messageId":"xmqqpn65n5dr.fsf@gitster.c.googlers.com","threadId":"54289","inReplyTo":"42a7948f94cb57ebd9c37c3850b46b1ac9813ec6.1601311803.git.matheus.bernardino@usp.br","subject":"Re: [PATCH 1/2] packfile: fix race condition on unpack_entry()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-09-28T18:05:52Z","receivedAt":"2020-09-28T18:06:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Matheus Tavares <matheus.bernardino@usp.br> writes:\n\n> To fix the race condition (and later segmentation fault), let's reorder\n> the aforementioned steps so that the lock is not released between 1.\n> and 3.\n\nIn other words, we hold the base in core only for ourselves without\nadding it to the base cache, apply the delta to produce the result\nand then place the base in the cache, and the reason why this change\nfixes the breakage is because the base we have locally and not in\ncache will not be seen by other people and will not be freed without\nour consent?  Which does make sense.\n\nBut I was confused by the explanation \"lock is not released\".  We do\nrelease the same lock when we call unpack_compressed_entry(), and\nreaquire it before the unpack_compressed_entry() returns.  What the\nreordering achieves is to protect the base from getting evicted when\nthe unlocking and relocing happens, no?\n\nThanks.\n"},{"id":"406550","messageId":"xmqqlfgtn4lo.fsf@gitster.c.googlers.com","threadId":"54289","inReplyTo":"5b6e3019e08c6bccdee29018e99b0c6933fe05e0.1601311803.git.matheus.bernardino@usp.br","subject":"Re: [PATCH 2/2] packfile: fix memory leak in add_delta_base_cache()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-09-28T18:22:43Z","receivedAt":"2020-09-28T18:22:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Matheus Tavares <matheus.bernardino@usp.br> writes:\n\n> When add_delta_base_cache() is called with a base that is already in the\n> cache, no operation is performed. But the check is done after allocating\n> space for a new entry, so we end up leaking memory on the early return.\n\nWow, that's so obvious a leak that it is surprising it has been\nunnoticed, especially given that the runtime inflation of the\npackfile was written so long time ago and was a central part of the\nsystem.\n\nI had to dig and find out that the breakage was fairly recent from\nearly this year, made in 31877c9a (object-store: allow threaded\naccess to object reading, 2020-01-15).\n\n> Also, the caller always expect that the base will be inserted, so it\n> never free()'s it. To fix both of these memory leaks, let's move the\n> allocation of a new entry further down in add_delta_base_cache(), and\n> make the function return an integer to indicate whether the insertion\n> was performed or not. Then, make the caller free() the base when needed.\n>\n> Signed-off-by: Matheus Tavares <matheus.bernardino@usp.br>\n\n> @@ -1841,8 +1843,10 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n>  \t\t * thread could free() it (e.g. to make space for another entry)\n>  \t\t * before we are done using it.\n>  \t\t */\n> -\t\tif (!external_base)\n> -\t\t\tadd_delta_base_cache(p, base_obj_offset, base, base_size, type);\n> +\t\tif (!external_base && !add_delta_base_cache(p, base_obj_offset,\n> +\t\t\t\t\t\tbase, base_size, type)) {\n> +\t\t\tfree(base);\n> +\t\t}\n\nWhen you have to wrap a long expression, try to split after an\noperator near the root of the parse tree, e.g.\n\n\t\tif (!external_base &&\n\t\t    !add_delta_base_cache(p, base_obj_offset, base, base_size, type)) {\n\nwould make the result easier to follow.\n\nI however suspect that it may be better let add_delta_base_cache()\ndo the freeing.  There is only one caller, and from its point of\nview, the timing when it throws the base at the cache (after the\nprevious patch) is when it is done with it.\n\nIn other words we can think of the call to add_delta_base_cache() as\nthe caller saying: \"I am done with this, but somebody else might\nwant to reuse it later, so do whatever you want to do with it\".  \n\nIf we were to go that route, it might even make sense to rename it\nto reflect that mentality from the viewpoint of the caller, but a\nsingle-caller helper like this one it may not matter all that much.\n\nThanks.\n\n\n"},{"id":"406598","messageId":"cover.1601337543.git.matheus.bernardino@usp.br","threadId":"54289","inReplyTo":"cover.1601311803.git.matheus.bernardino@usp.br","subject":"[PATCH v2 0/2] Fix race condition and memory leak in delta base cache","fromName":"Matheus Tavares","fromEmail":"matheus.bernardino@usp.br","sentAt":"2020-09-29T00:01:51Z","receivedAt":"2020-09-29T00:02:07Z","isPatch":true,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"Changes since v1:\n\n- Reworded patch one to remove misleading sentence about the locking\n  during step 2.\n- In patch two, let add_delta_base_cache() take full ownership of the\n  base, properly releasing it when the insertion is skipped.\n\nMatheus Tavares (2):\n  packfile: fix race condition on unpack_entry()\n  packfile: fix memory leak in add_delta_base_cache()\n\n packfile.c | 48 +++++++++++++++++++++++++++++-------------------\n 1 file changed, 29 insertions(+), 19 deletions(-)\n\nRange-diff against v1:\n1:  42a7948f94 ! 1:  948d07673f packfile: fix race condition on unpack_entry()\n    @@ Commit message\n         objects.\n     \n         To fix the race condition (and later segmentation fault), let's reorder\n    -    the aforementioned steps so that the lock is not released between 1.\n    -    and 3. An alternative solution which would not require the reordering\n    -    would be to duplicate `base` before inserting it in the cache.\n    -    However, as Phil Hord mentioned, memcpy()'ing large bases can negatively\n    -    affect performance: in his experiments, this alternative approach slowed\n    -    git-grep down by 10% to 20%.\n    +    the aforementioned steps so that `base` is only added to the cache at\n    +    the end. This will prevent the buffer from being released by another\n    +    thread while it is still in use. An alternative solution which would not\n    +    require the reordering would be to duplicate `base` before inserting it\n    +    in the cache. However, as Phil Hord mentioned, memcpy()'ing large bases\n    +    can negatively affect performance: in his experiments, this alternative\n    +    approach slowed git-grep down by 10% to 20%.\n     \n         Reported-by: Phil Hord <phil.hord@gmail.com>\n         Signed-off-by: Matheus Tavares <matheus.bernardino@usp.br>\n2:  5b6e3019e0 ! 2:  f15f0c82fd packfile: fix memory leak in add_delta_base_cache()\n    @@ Commit message\n         When add_delta_base_cache() is called with a base that is already in the\n         cache, no operation is performed. But the check is done after allocating\n         space for a new entry, so we end up leaking memory on the early return.\n    -    Also, the caller always expect that the base will be inserted, so it\n    -    never free()'s it. To fix both of these memory leaks, let's move the\n    +    In addition, the caller never free()'s the base as it expects the\n    +    function to take ownership of it. But the base is not released when we\n    +    skip insertion, so it also gets leaked. To fix these problems, move the\n         allocation of a new entry further down in add_delta_base_cache(), and\n    -    make the function return an integer to indicate whether the insertion\n    -    was performed or not. Then, make the caller free() the base when needed.\n    +    free() the base on early return.\n     \n         Signed-off-by: Matheus Tavares <matheus.bernardino@usp.br>\n     \n      ## packfile.c ##\n     @@ packfile.c: void clear_delta_base_cache(void)\n    - \t}\n    - }\n    - \n    --static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n    -+static int add_delta_base_cache(struct packed_git *p, off_t base_offset,\n    + static void 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     -\tstruct delta_base_cache_entry *ent = xmalloc(sizeof(*ent));\n    @@ packfile.c: void clear_delta_base_cache(void)\n      \n      \t/*\n     @@ packfile.c: static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n    + \t * is unpacking the same object, in unpack_entry() (since its phases I\n      \t * and III might run concurrently across multiple threads).\n      \t */\n    - \tif (in_delta_base_cache(p, base_offset))\n    --\t\treturn;\n    -+\t\treturn 0;\n    +-\tif (in_delta_base_cache(p, base_offset))\n    ++\tif (in_delta_base_cache(p, base_offset)) {\n    ++\t\tfree(base);\n    + \t\treturn;\n    ++\t}\n      \n      \tdelta_base_cached += base_size;\n      \n    @@ packfile.c: static void add_delta_base_cache(struct packed_git *p, off_t base_of\n      \tent->key.p = p;\n      \tent->key.base_offset = base_offset;\n      \tent->type = type;\n    -@@ packfile.c: static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n    - \t\thashmap_init(&delta_base_cache, delta_base_cache_hash_cmp, NULL, 0);\n    - \thashmap_entry_init(&ent->ent, pack_entry_hash(p, base_offset));\n    - \thashmap_add(&delta_base_cache, &ent->ent);\n    -+\treturn 1;\n    - }\n    - \n    - int packed_object_info(struct repository *r, struct packed_git *p,\n    -@@ packfile.c: void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n    - \t\t * thread could free() it (e.g. to make space for another entry)\n    - \t\t * before we are done using it.\n    - \t\t */\n    --\t\tif (!external_base)\n    --\t\t\tadd_delta_base_cache(p, base_obj_offset, base, base_size, type);\n    -+\t\tif (!external_base && !add_delta_base_cache(p, base_obj_offset,\n    -+\t\t\t\t\t\tbase, base_size, type)) {\n    -+\t\t\tfree(base);\n    -+\t\t}\n    - \n    - \t\tfree(delta_data);\n    - \t\tfree(external_base);\n-- \n2.28.0\n\n"},{"id":"406599","messageId":"948d07673f3b7eebf3d776ec2c785e65228ed185.1601337543.git.matheus.bernardino@usp.br","threadId":"54289","inReplyTo":"cover.1601337543.git.matheus.bernardino@usp.br","subject":"[PATCH v2 1/2] packfile: fix race condition on unpack_entry()","fromName":"Matheus Tavares","fromEmail":"matheus.bernardino@usp.br","sentAt":"2020-09-29T00:01:52Z","receivedAt":"2020-09-29T00:02:10Z","isPatch":true,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"The third phase of unpack_entry() performs the following sequence in a\nloop, until all the deltas enumerated in phase one are applied and the\nentry is fully reconstructed:\n\n1. Add the current base entry to the delta base cache\n2. Unpack the next delta\n3. Patch the unpacked delta on top of the base\n\nWhen the optional object reading lock is enabled, the above steps will\nbe performed while holding the lock. However, step 2. momentarily\nreleases it so that inflation can be performed in parallel for increased\nperformance. Because the `base` buffer inserted in the cache at 1. is\nnot duplicated, another thread can potentially free() it while the lock\nis released at 2. (e.g. when there is no space left in the cache to\ninsert another entry). In this case, the later attempt to dereference\n`base` at 3. will cause a segmentation fault. This problem was observed\nduring a multithreaded git-grep execution on a repository with large\nobjects.\n\nTo fix the race condition (and later segmentation fault), let's reorder\nthe aforementioned steps so that `base` is only added to the cache at\nthe end. This will prevent the buffer from being released by another\nthread while it is still in use. An alternative solution which would not\nrequire the reordering would be to duplicate `base` before inserting it\nin the cache. However, as Phil Hord mentioned, memcpy()'ing large bases\ncan negatively affect performance: in his experiments, this alternative\napproach slowed git-grep down by 10% to 20%.\n\nReported-by: Phil Hord <phil.hord@gmail.com>\nSigned-off-by: Matheus Tavares <matheus.bernardino@usp.br>\n---\n packfile.c | 41 ++++++++++++++++++++++++-----------------\n 1 file changed, 24 insertions(+), 17 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 9ef27508f2..0319418d88 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1775,12 +1775,10 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,\n \t\tvoid *external_base = NULL;\n \t\tunsigned long delta_size, base_size = size;\n \t\tint i;\n+\t\toff_t base_obj_offset = obj_offset;\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-\n \t\tif (!base) {\n \t\t\t/*\n \t\t\t * We're probably in deep shit, but let's try to fetch\n@@ -1818,24 +1816,33 @@ void *unpack_entry(struct repository *r, 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\tdata = NULL;\n-\t\t\tfree(external_base);\n-\t\t\tcontinue;\n-\t\t}\n+\t\t} else {\n+\t\t\tdata = patch_delta(base, base_size, delta_data,\n+\t\t\t\t\t   delta_size, &size);\n \n-\t\tdata = patch_delta(base, base_size,\n-\t\t\t\t   delta_data, delta_size,\n-\t\t\t\t   &size);\n+\t\t\t/*\n+\t\t\t * We could not apply the delta; warn the user, but\n+\t\t\t * keep going. Our failure will be noticed either in\n+\t\t\t * the next iteration of the loop, or if this is the\n+\t\t\t * final delta, in the caller when we return NULL.\n+\t\t\t * Those code paths will take care of making a more\n+\t\t\t * explicit warning and retrying with another copy of\n+\t\t\t * the object.\n+\t\t\t */\n+\t\t\tif (!data)\n+\t\t\t\terror(\"failed to apply delta\");\n+\t\t}\n \n \t\t/*\n-\t\t * We could not apply the delta; warn the user, but keep going.\n-\t\t * Our failure will be noticed either in the next iteration of\n-\t\t * the loop, or if this is the final delta, in the caller when\n-\t\t * we return NULL. Those code paths will take care of making\n-\t\t * a more explicit warning and retrying with another copy of\n-\t\t * the object.\n+\t\t * We delay adding `base` to the cache until the end of the loop\n+\t\t * because unpack_compressed_entry() momentarily releases the\n+\t\t * obj_read_mutex, giving another thread the chance to access\n+\t\t * the cache. Therefore, if `base` was already there, this other\n+\t\t * thread could free() it (e.g. to make space for another entry)\n+\t\t * before we are done using it.\n \t\t */\n-\t\tif (!data)\n-\t\t\terror(\"failed to apply delta\");\n+\t\tif (!external_base)\n+\t\t\tadd_delta_base_cache(p, base_obj_offset, base, base_size, type);\n \n \t\tfree(delta_data);\n \t\tfree(external_base);\n-- \n2.28.0\n\n"},{"id":"406600","messageId":"f15f0c82fd779656dc03ce196d7c29acd63fb6be.1601337543.git.matheus.bernardino@usp.br","threadId":"54289","inReplyTo":"cover.1601337543.git.matheus.bernardino@usp.br","subject":"[PATCH v2 2/2] packfile: fix memory leak in add_delta_base_cache()","fromName":"Matheus Tavares","fromEmail":"matheus.bernardino@usp.br","sentAt":"2020-09-29T00:01:53Z","receivedAt":"2020-09-29T00:02:13Z","isPatch":true,"sender":{"key":"matheus.tavb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/12701583?v=4"},"body":"When add_delta_base_cache() is called with a base that is already in the\ncache, no operation is performed. But the check is done after allocating\nspace for a new entry, so we end up leaking memory on the early return.\nIn addition, the caller never free()'s the base as it expects the\nfunction to take ownership of it. But the base is not released when we\nskip insertion, so it also gets leaked. To fix these problems, move the\nallocation of a new entry further down in add_delta_base_cache(), and\nfree() the base on early return.\n\nSigned-off-by: Matheus Tavares <matheus.bernardino@usp.br>\n---\n packfile.c | 7 +++++--\n 1 file changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 0319418d88..d31aaaeeaa 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1474,7 +1474,7 @@ void clear_delta_base_cache(void)\n static void 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-\tstruct delta_base_cache_entry *ent = xmalloc(sizeof(*ent));\n+\tstruct delta_base_cache_entry *ent;\n \tstruct list_head *lru, *tmp;\n \n \t/*\n@@ -1482,8 +1482,10 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \t * is unpacking the same object, in unpack_entry() (since its phases I\n \t * and III might run concurrently across multiple threads).\n \t */\n-\tif (in_delta_base_cache(p, base_offset))\n+\tif (in_delta_base_cache(p, base_offset)) {\n+\t\tfree(base);\n \t\treturn;\n+\t}\n \n \tdelta_base_cached += base_size;\n \n@@ -1495,6 +1497,7 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n \t\trelease_delta_base_cache(f);\n \t}\n \n+\tent = xmalloc(sizeof(*ent));\n \tent->key.p = p;\n \tent->key.base_offset = base_offset;\n \tent->type = type;\n-- \n2.28.0\n\n"},{"id":"406838","messageId":"CABURp0ovz0G-mYDv+CmL_pSu09WDJTxNQodpnyT3MrYjKjusEw@mail.gmail.com","threadId":"54289","inReplyTo":"948d07673f3b7eebf3d776ec2c785e65228ed185.1601337543.git.matheus.bernardino@usp.br","subject":"Re: [PATCH v2 1/2] packfile: fix race condition on unpack_entry()","fromName":"Phil Hord","fromEmail":"phil.hord@gmail.com","sentAt":"2020-10-02T20:06:46Z","receivedAt":"2020-10-02T20:07:00Z","isPatch":true,"sender":{"key":"phil.hord@gmail.com","avatar":"https://avatars.githubusercontent.com/u/123908?v=4"},"body":"On Mon, Sep 28, 2020 at 5:02 PM Matheus Tavares\n<matheus.bernardino@usp.br> wrote:\n>\n> The third phase of unpack_entry() performs the following sequence in a\n> loop, until all the deltas enumerated in phase one are applied and the\n> entry is fully reconstructed:\n>\n> 1. Add the current base entry to the delta base cache\n> 2. Unpack the next delta\n> 3. Patch the unpacked delta on top of the base\n>\n> When the optional object reading lock is enabled, the above steps will\n> be performed while holding the lock. However, step 2. momentarily\n> releases it so that inflation can be performed in parallel for increased\n> performance. Because the `base` buffer inserted in the cache at 1. is\n> not duplicated, another thread can potentially free() it while the lock\n> is released at 2. (e.g. when there is no space left in the cache to\n> insert another entry). In this case, the later attempt to dereference\n> `base` at 3. will cause a segmentation fault. This problem was observed\n> during a multithreaded git-grep execution on a repository with large\n> objects.\n>\n> To fix the race condition (and later segmentation fault), let's reorder\n> the aforementioned steps so that `base` is only added to the cache at\n> the end. This will prevent the buffer from being released by another\n> thread while it is still in use. An alternative solution which would not\n> require the reordering would be to duplicate `base` before inserting it\n> in the cache. However, as Phil Hord mentioned, memcpy()'ing large bases\n> can negatively affect performance: in his experiments, this alternative\n> approach slowed git-grep down by 10% to 20%.\n>\n> Reported-by: Phil Hord <phil.hord@gmail.com>\n> Signed-off-by: Matheus Tavares <matheus.bernardino@usp.br>\n> ---\n\nThanks for looking after this so quickly.  This all looks good to me,\nand I confirmed it does fix the problems I was seeing.\n\nPhil\n"}]}