patch, 2 partsrefs/files-backend: duplicate strings added to affected_refnames

files_transaction_prepare() and the functions it calls add strings to a string list without duplicating them, i.e., we keep the original raw pointers we were given. That is "ok", since we keep them only for a short-enough time, but we end up leaking some of them.

Switch to duplicating the strings, so that affected_refnames does not leak memory. The original strings might still leak, but at least that can now be addressed without worrying about these pointers.

No-one takes any pointers to the strings in the list (it is basically only used to check for set membership), so it is ok for string_list_clear to free them.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 refs/files-backend.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

We hand over the "referent" string (buffer) to several different functions, one of which would sometimes keep the raw pointer, referent.buf. (When split_symref_update calls string_list_insert.) The previous patch removed that behavior, so we can now safely release the string buffer before returning.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
I appreciate Git's stance on memory leaks ("if we're about to exit or
die, why bother?") but this one feels different since
lock_ref_for_update is called in a loop rather deep down the call stack.
Feel free to tell me I'm wrong. Patch 1/2 does introduce some
malloc-churning. An alternative would be to call strbuf_release only
when we know it's safe, but that feels really ugly.

 refs/files-backend.c | 31 ++++++++++++++++++++-----------
 1 file changed, 20 insertions(+), 11 deletions(-)

Martin Ågren <martin.agren@gmail.com> writes:

Sorry, but I do not understand this statement. If affected_refnames string list borrows strings from other structures who own them, and none of these strings are freed by clearing affected_refnames list, that is not "leaking"---we didn't acquire the ownership, so it is not our job to free them in the first place. Among the original owners of strings we borrow from, some may not properly free, in which case that is a leak.

What problem are you solving?

On 25 August 2017 at 23:00, Junio C Hamano <gitster@pobox.com> wrote:

Sorry. Maybe this explains my intentions better:

    In lock_ref_for_update(), we populate a strbuf "referent" through
    lock_raw_ref(). If we don't have a symref, we don't use "referent"
    for anything (and it won't have allocated any memory). Otherwise, we
    hand over referent.buf to someone who uses it immediately
    (refs_read_ref_full) or to someone who holds on to the pointer
    (split_symref_update ends up adding it to a string list). Therefore,
    at the end of lock_ref_for_update() we can't unconditionally release
    the strbuf, so we end up leaking it.

    We could release the strbuf when we know that it's safe (possibly
    also only when we know that it's needed). Instead, in preparation
    for the next patch, make the string list not hold on to the raw
    pointers, i.e., make it duplicate the strings on insertion and
    manage its own resources.

Of course, the pointer-keeping and free-avoidance might be by design and/or wanted, e.g., to avoid excessive mallocing and freeing. I admit to not knowing what is a realistic number of iterations in the loop that calls lock_ref_for_update, i.e., how severe this leak might be. Maybe the "backend" nature of this code does not necessarily imply "this could be called any number of times throughout the process' lifetime".

On Sat, Aug 26, 2017 at 12:16 PM, Martin Ågren <martin.agren@gmail.com> wrote:

Good find, Martin.

First of all, you are right that we don't want any memory leaks here. Nobody promises that the program will end soon if a reference update fails. (In fact, there are invocations of `git` that trigger multiple reference updates.) This is a small leak, but we should fix it.

The problem (if I may take a stab at explaining it in my own words) is that `files_transaction_prepare()` uses a `string_list` called `affected_refnames` to ensure that the same reference name is not modified more than once in a single reference transaction. Currently, `affected_refnames` is configured *not* to duplicate the refnames that are fed to it, which also means that it doesn't free the refnames when it is cleared.

This is correct for most refnames, which are owned by entries in the `ref_transaction`, and therefore have a longer lifetime than `affected_refnames`.

But there is one code path that can add a refname to `affected_refnames` without making a provision for the refname ever to be freed:

* files_transaction_prepare()
  * lock_ref_for_update()
    * split_symref_update()
      * item = string_list_insert(affected_refnames, referent)

The `referent` in the last statement comes from a `strbuf` that is created in `lock_ref_for_update()` then passed to `lock_raw_ref()`, which fills it.

It would be a serious bug if `lock_ref_for_update()` would dispose of `referent`, because the pointer in `affected_refnames` would point at freed memory. But in fact we have the opposite problem; `lock_ref_for_update()` never frees the memory (it doesn't even `strbuf_detach()` it). So that memory is leaked.

Your proposed solution is to change `affected_refnames` to duplicate the strings that are stored in it, in which case `lock_ref_for_update()` can properly dispose of `referent`, fixing the leak. This works, but at the price of having to allocate memory for *all* references in the update, even though most of them are already fine.

But note that `split_symref_update()` *also* passes a copy of `referent` to `ref_transaction_add_update()`, which *already* makes a copy of the reference name and adds an entry containing the name to the `ref_transaction`. If we would store *that* copy to `affected_refnames`, then it would get freed when the `ref_transaction` is cleaned up, and we could fix the memory leak without allocating any new memory. This requires a little reorg of `split_symref_update()` but it's not too bad:

* Do the initial check using `string_list_has_string()` rather than
calling `string_list_insert()` already.
* After `new_update` has been created, call `string_list_insert()`,
passing it `new_update->refname` as the string.

If this is done in place of your first commit, then your second commit could be left unchanged.

Michael

On 28 August 2017 at 10:06, Michael Haggerty <mhagger@alum.mit.edu> wrote:

Thanks for this very well-written description. It matches my understanding completely, which is comforting.

Agreed.

I haven't looked at the code yet, but from what I remember, this would a) work and b) be a straightforward rearrangement as you say. I'll give this approach a try (unless you want to, of course; just holler).

Thanks a lot for your comments. I appreciate it.

Martin

split_symref_update() receives a string-pointer `referent` and adds it to the list of `affected_refnames`. The list simply holds on to the pointers it is given, it does not copy the strings and it never frees them. The `referent` string in split_symref_update() belongs to a string buffer in the caller. After we return, the string will be leaked.

In the next patch, we want to properly release the string buffer in the caller, but we can't safely do so until we've made sure that `affected_refnames` will not be holding on to a pointer to the string. We could configure the list to handle its own resources, but it would mean some alloc/free-churning. The list is already handling other strings (through other code paths) which we do not need to worry about, and we'd be memory-churning those strings too, completely unnecessary.

Observe that split_symref_update() creates a `new_update`-object and that `new_update->refname` is then a copy of `referent`. The difference is, this copy will be freed, and it will be freed *after* `affected_refnames` has been cleared.

Rearrange the handling of `referent`, so that we don't add it directly to `affected_refnames`. Instead, first just check whether `referent` exists in the string list, and later add `new_update->refname`.

Helped-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
Thanks Junio and Michael for your comments on the first version. This
first patch is now completely different and much much better (thanks
Michael!). The commit message should also be better (sorry Junio...).
The second one has a new commit message, but the diff is the same.

Martin

 refs/files-backend.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

On 08/28/2017 10:32 PM, Martin Ågren wrote:

The check is not O(N); it is O(lg N) because it is implemented via a binary search in the (sorted) `affected_refnames`. The insertion below is still O(N), because it has to shift entries later in the list to the right to make room for the new entry.

We generally avoid using `assert()`. It would be preferable to use

        if (item->util)
                BUG("%s unexpectedly found in affected_refnames",
new_update->refname);

Otherwise, looks good!

Michael

After the previous patch, none of the functions we call hold on to `referent.buf`, so we can safely release the string buffer before returning.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 refs/files-backend.c | 31 ++++++++++++++++++++-----------
 1 file changed, 20 insertions(+), 11 deletions(-)

On 08/28/2017 10:32 PM, Martin Ågren wrote:

This patch looks good to me, but I did notice a pre-existing problem in the area...

It is incorrect to return -1 here. First of all, stylistically, the return value should be a symbolic constant. But in fact, it should be returning `TRANSACTION_GENERIC_ERROR` here, whereas -1 is `TRANSACTION_NAME_CONFLICT`. So the code is not just stylistically wrong; it is functionally wrong.

I know that this is not your mistake, but would you like to add another patch to your series to fix this up? I'd do it myself, but it's a little bit awkward because the fix will conflict with your patch.

Thanks, Michael

On 29 August 2017 at 10:39, Michael Haggerty <mhagger@alum.mit.edu> wrote:

Sure. I'll send out a v3 later today. I'll fix this in a third patch, and I'll also address your comments on the first patch.

Thanks a lot.

Martin

split_symref_update() receives a string-pointer `referent` and adds it to the list of `affected_refnames`. The list simply holds on to the pointers it is given, it does not copy the strings and it does not ever free them. The `referent` string in split_symref_update() belongs to a string buffer in the caller. After we return, the string will be leaked.

In the next patch, we want to properly release the string buffer in the caller, but we can't safely do so until we've made sure that `affected_refnames` will not be holding on to a pointer to the string. We could configure the list to handle its own resources, but it would mean some alloc/free-churning. The list is already handling other strings (through other code paths) which we do not need to worry about, and we'd be memory-churning those strings too, completely unnecessary.

Observe that split_symref_update() creates a `new_update`-object through ref_transaction_add_update(), after which `new_update->refname` is a copy of `referent`. The difference is, this copy will be freed, and it will be freed *after* `affected_refnames` has been cleared.

Rearrange the handling of `referent`, so that we don't add it directly to `affected_refnames`. Instead, first just check whether `referent` exists in the string list, and later add `new_update->refname`.

Helped-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
v3: "O(lg N)" in comment; if-BUG() instead of assert()

 refs/files-backend.c | 18 ++++++++++++++----
 1 file changed, 14 insertions(+), 4 deletions(-)

v3 looks good to me. Thanks!

Reviewed-by: Michael Haggerty <mhagger@alum.mit.edu>

Michael

On 30 August 2017 at 04:52, Michael Haggerty <mhagger@alum.mit.edu> wrote:

Thank _you_ for very helpful feedback on the earlier versions.

Martin

Martin Ågren <martin.agren@gmail.com> writes:

Yes, the earlier attempt was sort-of barking up a wrong tree.  

Once we step back and observe other users of affected_refnames and realize that the list is meant to to point at a refname field of an existing instance of another structure by borrowing, the blame shifts from files_transaction_prepare() to the real culprit. Michael's review gave us a very good "let's step back a bit" that made the huge improvement between v1 and v2/v3.

I wonder if we should be tightening the use of affected_refnames even further, though.

It is may be sufficient to make sure that we do not throw anything that we would need to free as part of destroying affected_refnames into the string list, purely from the "leak prevention" perspective.

But stepping back a bit, the reason why the string list exists in the first place is to make sure we do not touch the same ref twice in a single transaction, the set of all possible updates in the single transaction exists somewhere, and each of these updates know what ref it wants to update.

And that is recorded in transaction->updates[]->refname no?

So it seems to me that logically any and all string that is registered in affected_refnames list must be the refname field of a ref_update structure in the transaction.

And from that point of view, doesn't split_head_update() wants a similar fix? It attempts to insert "HEAD", makes sure it hasn't been inserted and then hangs a new update transaction as its util. It is not wrong per-se from purely leak-prevention point of view, as that "HEAD" is a literal string we woudn't even want to free, but from logical/"what each data means" point of view, it still feels wrong.

On 5 September 2017 at 12:02, Junio C Hamano <gitster@pobox.com> wrote:

I'm with you up to here.

There is a "Special hack" comment related to this, and I don't feel particularly confident that I could make any meaningful contribution in this area. To be honest, I don't immediately see in which direction your suggestion/idea/thought is going, which tells me I should not be making a mess out of it. :-)

Martin

On Tue, Sep 05, 2017 at 07:24:18PM +0200, Martin Ågren wrote:

I noticed the HEAD funniness, too, when looking at this earlier. I agree with Junio that it's not quite consistent with the general rule of "string list items point to their refnames", but I don't think it matters in practice.

I think the fix, if we wanted to do one, would be similar to what you did in split_symref_update(). Like:

Jeff King <peff@peff.net> writes:

Yup, we are on the same page; the "fix" I was alluding to would look exactly like what you wrote below, but I agree the distinction does not matter in practice. IOW, I do not think the code after Martin's fix is wrong per-se.

Thanks.

On 5 September 2017 at 23:26, Junio C Hamano <gitster@pobox.com> wrote:

Well, "not wrong per-se" tells me you'd feel slightly more comfortable about the state of things if we did this. ;)

I'll take Peff's hint, tweak/add comments for correctness and symmetry with the previous patch and add an if-BUG for symmetry. Peff: Do I have your sign-off? (Do I need it?)

Junio: The topic is in pu as ma/split-symref-update-fix. Re-roll or new
topic or as a separate "patch 4/3" for you to place on top, any
preference?

If we re-roll, would you prefer Peff's much smaller take on patch 2 (strbuf_release where it matters, instead of sprinkling "goto out" all over)? I think me and him agreed that we'd be fine either way. I'd reuse my commit message, if I get his sign-off and "From:".

Obviously, if Michael or anyone else has any input, I'm open to that as well..

Martin

Martin Ågren <martin.agren@gmail.com> writes:

Until a topic hits 'next', you solely own it and it is mostly up to you how to go about improving it. My preference would be much less relevant than what the end result would require, i.e....

... if we take Peff's approach, then rerolling the whole thing would be the only approach that makes sense---incremental update would make the resulting history less readable. Between two approaches I do not have a strong preference either way---it's a choice that can be made between you and Peff.

Sure.

On Wed, Sep 06, 2017 at 08:12:24PM +0200, Martin Ågren wrote:

Yes, you have my sign-off. Probably it is not necessary for such a trivial patch, but it never hurts to be sure.

You are welcome to forge my sign-off there (but I really am OK with either approach).

-Peff

Here's a reroll of ma/split-symref-update-fix. The first three patches are v3 plus Michael's Reviewed-By.

The fourth is the conceptual fix of adding `refname` instead of "HEAD" into the list of affected refnames.

Thanks all for comments, suggestions and help along the way.

Martin

Martin Ågren (4):
  refs/files-backend: add longer-scoped copy of string to list
  refs/files-backend: fix memory leak in lock_ref_for_update
  refs/files-backend: correct return value in lock_ref_for_update
  refs/files-backend: add `refname`, not "HEAD", to list

 refs/files-backend.c | 62 +++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 44 insertions(+), 18 deletions(-)

split_symref_update() receives a string-pointer `referent` and adds it to the list of `affected_refnames`. The list simply holds on to the pointers it is given, it does not copy the strings and it does not ever free them. The `referent` string in split_symref_update() belongs to a string buffer in the caller. After we return, the string will be leaked.

In the next patch, we want to properly release the string buffer in the caller, but we can't safely do so until we've made sure that `affected_refnames` will not be holding on to a pointer to the string. We could configure the list to handle its own resources, but it would mean some alloc/free-churning. The list is already handling other strings (through other code paths) which we do not need to worry about, and we'd be memory-churning those strings too, completely unnecessary.

Observe that split_symref_update() creates a `new_update`-object through ref_transaction_add_update(), after which `new_update->refname` is a copy of `referent`. The difference is, this copy will be freed, and it will be freed *after* `affected_refnames` has been cleared.

Rearrange the handling of `referent`, so that we don't add it directly to `affected_refnames`. Instead, first just check whether `referent` exists in the string list, and later add `new_update->refname`.

Helped-by: Michael Haggerty <mhagger@alum.mit.edu>
Reviewed-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 refs/files-backend.c | 18 ++++++++++++++----
 1 file changed, 14 insertions(+), 4 deletions(-)

After the previous patch, none of the functions we call hold on to `referent.buf`, so we can safely release the string buffer before returning.

Reviewed-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 refs/files-backend.c | 31 ++++++++++++++++++++-----------
 1 file changed, 20 insertions(+), 11 deletions(-)

In one code path we return a literal -1 and not a symbolic constant. The value -1 would be interpreted as TRANSACTION_NAME_CONFLICT, which is wrong. Use TRANSACTION_GENERIC_ERROR instead (that is the only other return value we have to choose from).

Noticed-by: Michael Haggerty <mhagger@alum.mit.edu>
Reviewed-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 refs/files-backend.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

An earlier patch rewrote `split_symref_update()` to add a copy of a string to a string list instead of adding the original string. That was so that the original string could be freed in a later patch, but it is also conceptually cleaner, since now all calls to `string_list_insert()` and `string_list_append()` add `update->refname`. --- Except a literal "HEAD" is added in `split_head_update()`.

Restructure `split_head_update()` in the same way as the earlier patch did for `split_symref_update()`. This does not correct any practical problem, but makes things conceptually cleaner. The downside is a call to `string_list_has_string()`, which should be relatively cheap.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
 refs/files-backend.c | 13 ++++++++++---
 1 file changed, 10 insertions(+), 3 deletions(-)

On Sat, Sep 09, 2017 at 08:57:14AM +0200, Martin Ågren wrote:

This looks good to me, including the explanation in the new patch. Thanks!

-Peff

On Tue, Aug 29, 2017 at 07:18:22PM +0200, Martin Ågren wrote:

Coincidentally[1] I came across this same leak, and my solution ended up slightly different. I'll share it here in case it's of interest.

In your solution we end up searching the string list twice: once to see if we have the item, and then again to insert it. Whereas in the original we did both with a single search.

But we can observe that either:

  1. The item already existed, in which case our insert was a noop, and
     we're good.

or

  2. We inserted it, in which case we proceed with creating new_update.

     We can then in O(1) replace the pointer in the string list item
     with the storage in new_update. We know we're not violating any
     string_list invariants because the strings contain the same bytes.

I.e.:

On Tue, Sep 5, 2017 at 10:45 AM, Jeff King <peff@peff.net> wrote:

This is clever, but I don't like that it requires outside code to change internal `string_list` structures in a way that is not documented to be OK.

If we cared about getting rid of the extra `O(lg N)` search (and I agree with you that it doesn't matter in this case), I think the clean way to do it would be for `string_list` to expose a method like

    struct string_list_item *string_list_insert_at_index(struct
string_list *list, size_t index, const char *string);

and to use it, together with `string_list_find_insert_index()`, to avoid having to search twice.

Michael

On Tue, Sep 05, 2017 at 11:03:36AM +0200, Michael Haggerty wrote:

Yes, agreed on all counts.

-Peff

After the previous patch, none of the functions we call hold on to `referent.buf`, so we can safely release the string buffer before returning.

Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
v3: identical to v2

 refs/files-backend.c | 31 ++++++++++++++++++++-----------
 1 file changed, 20 insertions(+), 11 deletions(-)

On Tue, Aug 29, 2017 at 07:18:23PM +0200, Martin Ågren wrote:

I ended up doing this a little differently in my version:

On 5 September 2017 at 10:47, Jeff King <peff@peff.net> wrote:

Some time after I posted v3, I had the same thought. I did double-check and it does hold. But then I thought that even if it holds now, maybe it's a bit too brittle. On the other hand, my patch is quite noisy and maybe the connection between the two is obvious enough that it will hold in the future as well.

So would I...

Martin

In one code path we return a literal -1 and not a symbolic constant. The value -1 would be interpreted as TRANSACTION_NAME_CONFLICT, which is wrong. Use TRANSACTION_GENERIC_ERROR instead (that is the only other return value we have to choose from).

Noticed-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Martin Ågren <martin.agren@gmail.com>
---
v3: this is a new patch, as suggested by Michael

 refs/files-backend.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)