| Message ID | 20190925213718.231231-1-emilyshaffer@google.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | promisor-remote: skip move_to_tail when n=1 | expand |
On Wed, Sep 25, 2019 at 02:37:18PM -0700, Emily Shaffer wrote: > Previously, when promisor_remote_move_to_tail() is called for a > promisor_remote which is currently the *only* element in promisors, a > cycle is created in the promisors linked list. This cycle leads to a > double free later on in promisor_remote_clear(): promisors is set to > promisors->next (a no-op, as promisors->next == promisors); the previous > value of promisors is free()'d; then the new value of promisors (which > is equal to the previous value of promisors) is also free()'d. This > double-free error was unrecoverable for the user without removing the > filter or re-cloning the repo and hoping to miss this edge case. Nice clear description. Is the problem only when the remote is the only element of the list, or would it also happen when it's at the end? I think the problematic lines are: r->next = NULL; *promisors_tail = r; If our "r" is already the tail, then promisors_tail points to &r->next, and we create a cycle in the linked list. I think if you swap those two lines, the problem goes away. That said, it's subtle enough that I think covering the noop case at the start of the function is much clearer. Using that strategy, I think this: > + if (promisors == r && promisors->next == NULL) > + return; should probably just see if we're already at the end, which also covers the single-element case. Like: if (!r->next) return; /* we're already at the end */ or possibly: if (promisors_tail == &r->next) return; /* we're already at the end */ I also can't help but think this would all be a lot simpler using the implementation in list.h. Then we don't have to pass this weird "previous" pointer around (because it's a doubly-linked list). And functions like this one could go away in favor of list_move(). But that's obviously a bigger change. > This change showed up for us in a user bugreport; I'm actually fairly > unfamiliar with the codebase here but given the drastic nature of the > failure, I wanted to get a fix up quickly. I'm still working on how to > reproduce this exact case in the test suite (and actually would > appreciate any pointers). Specifically, it looks like we only really > break if we have a single promisor_remote in the linked list, call > move_to_tail() on it at least once, and then call clear() on it without > adding another promisor_remote first. The only call is in promisor_remote_init(), where we try to move whatever promisor we get from looking up repository_format_partial_clone. That name in turn comes from the extensions.partialclone config. The init function also creates elements in the list from any remotes marked with remote.XYZ.promisor in the config. So this is enough to create the cycle in the linked list: git init git remote add foo /wherever git config remote.foo.promisor true git config extensions.partialclone foo git fetch foo but it doesn't trigger the double-free because we don't ever free anything. We only call the clear() function during reinit(). And that only happens in partial_clone_register(). So if we take the commands above, and then try to actually do a partial clone with it (causing it to re-register), I get (building with ASan, but vanilla glibc seems to detect the double-free too): $ git fetch --filter=blob:none foo ==30356==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000001f90 at pc 0x559adb9a0919 bp 0x7ffeb7a52b30 sp 0x7ffeb7a52b28 READ of size 8 at 0x603000001f90 thread T0 #0 0x559adb9a0918 in promisor_remote_clear /home/peff/compile/git/promisor-remote.c:173 #1 0x559adb9a0918 in promisor_remote_reinit /home/peff/compile/git/promisor-remote.c:183 #2 0x559adb5856c0 in fetch_one_setup_partial builtin/fetch.c:1570 #3 0x559adb5856c0 in cmd_fetch builtin/fetch.c:1736 [...etc...] Another way to manifest the error: git remote add bar /does-not-matter git fetch --filter=blob:none bar Now we'll try to register "bar". But since it's _not_ already in the linked list, our search will go on forever, since the list loops back on itself. -Peff
On Thu, Sep 26, 2019 at 03:55:35AM -0400, Jeff King wrote: > On Wed, Sep 25, 2019 at 02:37:18PM -0700, Emily Shaffer wrote: > > > Previously, when promisor_remote_move_to_tail() is called for a > > promisor_remote which is currently the *only* element in promisors, a > > cycle is created in the promisors linked list. This cycle leads to a > > double free later on in promisor_remote_clear(): promisors is set to > > promisors->next (a no-op, as promisors->next == promisors); the previous > > value of promisors is free()'d; then the new value of promisors (which > > is equal to the previous value of promisors) is also free()'d. This > > double-free error was unrecoverable for the user without removing the > > filter or re-cloning the repo and hoping to miss this edge case. > > Nice clear description. > > Is the problem only when the remote is the only element of the list, or > would it also happen when it's at the end? It totally does. Nice catch, I wasn't seeing past my specific example. :) > > I think the problematic lines are: > > r->next = NULL; > *promisors_tail = r; > > If our "r" is already the tail, then promisors_tail points to &r->next, > and we create a cycle in the linked list. > > I think if you swap those two lines, the problem goes away. That said, > it's subtle enough that I think covering the noop case at the start of > the function is much clearer. > > Using that strategy, I think this: > > > + if (promisors == r && promisors->next == NULL) > > + return; > > should probably just see if we're already at the end, which also covers > the single-element case. Like: > > if (!r->next) > return; /* we're already at the end */ Hmm, I guess I wasn't familiar enough on the lifetime of a promisor_remote - I suppose I was expecting promisor_remote_move_to_tail() could be used for a first-time insert, too, although it looks like promisor_remote_new() actually does the insert for us every time. > > or possibly: > > if (promisors_tail == &r->next) > return; /* we're already at the end */ With the above concern I initially feel a little more comfortable with this, although now that I'm thinking through the case when 'r' isn't already in the list, I think it would replace the entire list by taking the 'else' branch, having a nulled r->next, and therefore replacing the head pointer 'promisors' with itself. So, considering that in the former approach incorrect usage (I calloc my own promisor_remote and call move_to_tail() on it) is a no-op, and in the latter approach the same incorrect use case is disastrous (we leak any promisor_remotes already in the list), I'll stick with the former. Thanks for the suggestions and for pointing out my edge case was wider than I thought! > > I also can't help but think this would all be a lot simpler using the > implementation in list.h. Then we don't have to pass this weird > "previous" pointer around (because it's a doubly-linked list). And > functions like this one could go away in favor of list_move(). But > that's obviously a bigger change. Agreed. I joked to my team that this was the first time I've needed to understand linked list manipulation outside of an interview setting, ever ;) > > > This change showed up for us in a user bugreport; I'm actually fairly > > unfamiliar with the codebase here but given the drastic nature of the > > failure, I wanted to get a fix up quickly. I'm still working on how to > > reproduce this exact case in the test suite (and actually would > > appreciate any pointers). Specifically, it looks like we only really > > break if we have a single promisor_remote in the linked list, call > > move_to_tail() on it at least once, and then call clear() on it without > > adding another promisor_remote first. > > The only call is in promisor_remote_init(), where we try to move > whatever promisor we get from looking up repository_format_partial_clone. > That name in turn comes from the extensions.partialclone config. > > The init function also creates elements in the list from any remotes > marked with remote.XYZ.promisor in the config. > > So this is enough to create the cycle in the linked list: > > git init > git remote add foo /wherever > git config remote.foo.promisor true > git config extensions.partialclone foo > git fetch foo > > but it doesn't trigger the double-free because we don't ever free > anything. We only call the clear() function during reinit(). And that > only happens in partial_clone_register(). So if we take the commands > above, and then try to actually do a partial clone with it (causing it > to re-register), I get (building with ASan, but vanilla glibc seems to > detect the double-free too): > > $ git fetch --filter=blob:none foo > ==30356==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000001f90 at pc 0x559adb9a0919 bp 0x7ffeb7a52b30 sp 0x7ffeb7a52b28 > READ of size 8 at 0x603000001f90 thread T0 > #0 0x559adb9a0918 in promisor_remote_clear /home/peff/compile/git/promisor-remote.c:173 > #1 0x559adb9a0918 in promisor_remote_reinit /home/peff/compile/git/promisor-remote.c:183 > #2 0x559adb5856c0 in fetch_one_setup_partial builtin/fetch.c:1570 > #3 0x559adb5856c0 in cmd_fetch builtin/fetch.c:1736 > [...etc...] > > Another way to manifest the error: > > git remote add bar /does-not-matter > git fetch --filter=blob:none bar > > Now we'll try to register "bar". But since it's _not_ already in the > linked list, our search will go on forever, since the list loops back on > itself. I really appreciate your coming up with these cases. I'll test-ify them and send another patch, plus the modified fix as discussed as above. - Emily
On Thu, Sep 26, 2019 at 10:53:08AM -0700, Emily Shaffer wrote: > > should probably just see if we're already at the end, which also covers > > the single-element case. Like: > > > > if (!r->next) > > return; /* we're already at the end */ > > Hmm, I guess I wasn't familiar enough on the lifetime of a > promisor_remote - I suppose I was expecting > promisor_remote_move_to_tail() could be used for a first-time insert, > too, although it looks like promisor_remote_new() actually does the > insert for us every time. Right, having to call move_to_tail at all is itself a special case, for when partialclone points to a remote which doesn't have its "remote.*.promisor" config set. I haven't followed the details of this promisor stuff enough to know what it means, but presumably that's what the non-multi-promisor case looks like. > > or possibly: > > > > if (promisors_tail == &r->next) > > return; /* we're already at the end */ > > With the above concern I initially feel a little more comfortable with > this, although now that I'm thinking through the case when 'r' isn't > already in the list, I think it would replace the entire list by taking > the 'else' branch, having a nulled r->next, and therefore replacing the > head pointer 'promisors' with itself. Yeah, I agree things get weird there. > > I also can't help but think this would all be a lot simpler using the > > implementation in list.h. Then we don't have to pass this weird > > "previous" pointer around (because it's a doubly-linked list). And > > functions like this one could go away in favor of list_move(). But > > that's obviously a bigger change. > > Agreed. I joked to my team that this was the first time I've needed to > understand linked list manipulation outside of an interview setting, > ever ;) I was curious how this would look, so I sketched it out. One of the annoying things about list.h is that there's a little extra boilerplate when iterating, since you have to cast back to the original type with list_entry() (in the kernel they use typeof() to avoid this, but it's not portable enough for us). The result _is_ shorter by lines. I don't know if it's worth the churn. --- promisor-remote.c | 75 ++++++++++++++++++++++++------------------------------- promisor-remote.h | 4 ++- 2 files changed, 35 insertions(+), 44 deletions(-) diff --git a/promisor-remote.c b/promisor-remote.c index 9bc296cdde..a158ac44e0 100644 --- a/promisor-remote.c +++ b/promisor-remote.c @@ -50,8 +50,7 @@ static int fetch_objects(const char *remote_name, return fetch_refs(remote_name, ref); } -static struct promisor_remote *promisors; -static struct promisor_remote **promisors_tail = &promisors; +static LIST_HEAD(promisors); static struct promisor_remote *promisor_remote_new(const char *remote_name) { @@ -64,40 +63,24 @@ static struct promisor_remote *promisor_remote_new(const char *remote_name) } FLEX_ALLOC_STR(r, name, remote_name); - - *promisors_tail = r; - promisors_tail = &r->next; - + list_add_tail(&r->list, &promisors); return r; } -static struct promisor_remote *promisor_remote_lookup(const char *remote_name, - struct promisor_remote **previous) +static struct promisor_remote *promisor_remote_lookup(const char *remote_name) { - struct promisor_remote *r, *p; + struct list_head *pos; - for (p = NULL, r = promisors; r; p = r, r = r->next) - if (!strcmp(r->name, remote_name)) { - if (previous) - *previous = p; + list_for_each(pos, &promisors) { + struct promisor_remote *r = + list_entry(pos, struct promisor_remote, list); + if (!strcmp(r->name, remote_name)) return r; - } + } return NULL; } -static void promisor_remote_move_to_tail(struct promisor_remote *r, - struct promisor_remote *previous) -{ - if (previous) - previous->next = r->next; - else - promisors = r->next ? r->next : r; - r->next = NULL; - *promisors_tail = r; - promisors_tail = &r->next; -} - static int promisor_remote_config(const char *var, const char *value, void *data) { const char *name; @@ -119,7 +102,7 @@ static int promisor_remote_config(const char *var, const char *value, void *data remote_name = xmemdupz(name, namelen); - if (!promisor_remote_lookup(remote_name, NULL)) + if (!promisor_remote_lookup(remote_name)) promisor_remote_new(remote_name); free(remote_name); @@ -129,7 +112,7 @@ static int promisor_remote_config(const char *var, const char *value, void *data struct promisor_remote *r; char *remote_name = xmemdupz(name, namelen); - r = promisor_remote_lookup(remote_name, NULL); + r = promisor_remote_lookup(remote_name); if (!r) r = promisor_remote_new(remote_name); @@ -155,26 +138,27 @@ static void promisor_remote_init(void) git_config(promisor_remote_config, NULL); if (repository_format_partial_clone) { - struct promisor_remote *o, *previous; + struct promisor_remote *o; - o = promisor_remote_lookup(repository_format_partial_clone, - &previous); - if (o) - promisor_remote_move_to_tail(o, previous); - else + o = promisor_remote_lookup(repository_format_partial_clone); + if (o) { + list_del(&o->list); + list_add_tail(&o->list, &promisors); + } else promisor_remote_new(repository_format_partial_clone); } } static void promisor_remote_clear(void) { - while (promisors) { - struct promisor_remote *r = promisors; - promisors = promisors->next; + struct list_head *pos, *tmp; + + list_for_each_safe(pos, tmp, &promisors) { + struct promisor_remote *r = + list_entry(pos, struct promisor_remote, list); + list_del(pos); free(r); } - - promisors_tail = &promisors; } void promisor_remote_reinit(void) @@ -189,9 +173,11 @@ struct promisor_remote *promisor_remote_find(const char *remote_name) promisor_remote_init(); if (!remote_name) - return promisors; + return list_empty(&promisors) ? + NULL : + list_first_entry(&promisors, struct promisor_remote, list); - return promisor_remote_lookup(remote_name, NULL); + return promisor_remote_lookup(remote_name); } int has_promisor_remote(void) @@ -235,15 +221,18 @@ int promisor_remote_get_direct(struct repository *repo, const struct object_id *oids, int oid_nr) { - struct promisor_remote *r; + struct list_head *pos; struct object_id *remaining_oids = (struct object_id *)oids; int remaining_nr = oid_nr; int to_free = 0; int res = -1; promisor_remote_init(); - for (r = promisors; r; r = r->next) { + list_for_each(pos, &promisors) { + struct promisor_remote *r = + list_entry(pos, struct promisor_remote, list); + if (fetch_objects(r->name, remaining_oids, remaining_nr) < 0) { if (remaining_nr == 1) continue; diff --git a/promisor-remote.h b/promisor-remote.h index 8200dfc940..e3ddc329ba 100644 --- a/promisor-remote.h +++ b/promisor-remote.h @@ -1,6 +1,8 @@ #ifndef PROMISOR_REMOTE_H #define PROMISOR_REMOTE_H +#include "list.h" + struct object_id; /* @@ -10,7 +12,7 @@ struct object_id; * from extensions.partialclone or core.partialclonefilter. */ struct promisor_remote { - struct promisor_remote *next; + struct list_head list; const char *partial_clone_filter; const char name[FLEX_ARRAY]; };
diff --git a/promisor-remote.c b/promisor-remote.c index 9bc296cdde..dccd697c2d 100644 --- a/promisor-remote.c +++ b/promisor-remote.c @@ -89,6 +89,9 @@ static struct promisor_remote *promisor_remote_lookup(const char *remote_name, static void promisor_remote_move_to_tail(struct promisor_remote *r, struct promisor_remote *previous) { + if (promisors == r && promisors->next == NULL) + return; + if (previous) previous->next = r->next; else
Previously, when promisor_remote_move_to_tail() is called for a promisor_remote which is currently the *only* element in promisors, a cycle is created in the promisors linked list. This cycle leads to a double free later on in promisor_remote_clear(): promisors is set to promisors->next (a no-op, as promisors->next == promisors); the previous value of promisors is free()'d; then the new value of promisors (which is equal to the previous value of promisors) is also free()'d. This double-free error was unrecoverable for the user without removing the filter or re-cloning the repo and hoping to miss this edge case. Now, when promisor_remote_move_to_tail() would be a no-op, just do a no-op. In cases of promisor_remote_move_to_tail() where n>1, it works correctly. Signed-off-by: Emily Shaffer <emilyshaffer@google.com> --- This change showed up for us in a user bugreport; I'm actually fairly unfamiliar with the codebase here but given the drastic nature of the failure, I wanted to get a fix up quickly. I'm still working on how to reproduce this exact case in the test suite (and actually would appreciate any pointers). Specifically, it looks like we only really break if we have a single promisor_remote in the linked list, call move_to_tail() on it at least once, and then call clear() on it without adding another promisor_remote first. promisor-remote.c | 3 +++ 1 file changed, 3 insertions(+)