Web lists-archives.com

Re: [PATCH v2 1/2] refs/files-backend: add longer-scoped copy of string to list




On 08/28/2017 10:32 PM, Martin Ågren wrote:
> 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@xxxxxxxxxxxx>
> Signed-off-by: Martin Ågren <martin.agren@xxxxxxxxx>
> ---
> 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(-)
> 
> diff --git a/refs/files-backend.c b/refs/files-backend.c
> index 5cca55510..bdb0e22e5 100644
> --- a/refs/files-backend.c
> +++ b/refs/files-backend.c
> @@ -2140,13 +2140,12 @@ static int split_symref_update(struct files_ref_store *refs,
>  
>  	/*
>  	 * First make sure that referent is not already in the
> -	 * transaction. This insertion is O(N) in the transaction
> +	 * transaction. This check is O(N) in the transaction

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.

>  	 * size, but it happens at most once per symref in a
>  	 * transaction.
>  	 */
> -	item = string_list_insert(affected_refnames, referent);
> -	if (item->util) {
> -		/* An entry already existed */
> +	if (string_list_has_string(affected_refnames, referent)) {
> +		/* An entry already exists */
>  		strbuf_addf(err,
>  			    "multiple updates for '%s' (including one "
>  			    "via symref '%s') are not allowed",
> @@ -2181,6 +2180,15 @@ static int split_symref_update(struct files_ref_store *refs,
>  	update->flags |= REF_LOG_ONLY | REF_NODEREF;
>  	update->flags &= ~REF_HAVE_OLD;
>  
> +	/*
> +	 * Add the referent. This insertion is O(N) in the transaction
> +	 * size, but it happens at most once per symref in a
> +	 * transaction. Make sure to add new_update->refname, which will
> +	 * be valid as long as affected_refnames is in use, and NOT
> +	 * referent, which might soon be freed by our caller.
> +	 */
> +	item = string_list_insert(affected_refnames, new_update->refname);
> +	assert(!item->util);

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

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

>  	item->util = new_update;
>  
>  	return 0;
> 

Otherwise, looks good!

Michael