git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 10/10] name-rev: release unused name strings

From
Derrick Stolee <stolee@gmail.com>
Date
Feb 5, 2020, 15:19 UTC
Message-ID
<35b282f8-c3a9-e7e3-5ea8-0542e7ce24ac@gmail.com>
In-Reply-To
<4eddc458-6294-9b9c-857b-50ba484a7168@web.de>
On 2/4/2020 4:26 PM, René Scharfe wrote:
Show 20 quoted lines
> The runtime actually increases slightly from:
> 
> Benchmark #1: ./git -C ../linux/ name-rev --all
>   Time (mean ± σ):     828.8 ms ±   5.0 ms    [User: 797.2 ms, System: 31.6 ms]
>   Range (min … max):   824.1 ms … 838.9 ms    10 runs
> 
> ... to:
> 
> Benchmark #1: ./git -C ../linux/ name-rev --all
>   Time (mean ± σ):     847.6 ms ±   3.4 ms    [User: 807.9 ms, System: 39.6 ms]
>   Range (min … max):   843.4 ms … 854.3 ms    10 runs
> 
> Why is that?  In the Chromium repo, ca. 44000 free(3) calls in
> create_or_update_name() release almost 1GB, while in the Linux repo
> 240000+ calls release a bit more than 5MB, so the average discarded
> name is ca.  1000x longer in the latter.
> 
> Overall I think it's the right tradeoff to make, as it helps curb the
> memory usage in repositories with big discarded names, and the added
> overhead is small.

I agree this trade-off is worth it. Your reasoning for why it is happening makes sense, too.

Show 14 quoted lines
> +	if (is_valid_rev_name(name)) {
> +		if (!is_better_name(name, taggerdate, distance, from_tag))
> +			return NULL;
> +
> +		/*
> +		 * This string might still be shared with ancestors
> +		 * (generation > 0).  We can release it here regardless,
> +		 * because the new name that has just won will be better
> +		 * for them as well, so name_rev() will replace these
> +		 * stale pointers when it processes the parents.
> +		 */
> +		if (!name->generation)
> +			free(name->tip_name);
> +	}

And here, this idea of "still be shared with ancestors" is confusing without the additional context that the name-rev algorithm is using depth-first-search to find the "best" name. At this point, we are trying to replace the existing name with a better one, and use "generation == 0" to declare "I am the initial owner of tip_name". The rest of the ancestors will replace their tip_name pointer with the new name, all while not accessing this freed memory.

Keeping such dangling references to freed memory is certainly dangerous, but these references are short-lived within the name_rev() method. That limits the possible ways this could cause issues in the future.

Thanks, -Stolee

Previous: René ScharfeNext: Derrick Stolee
Message 21 of 27 in “name-rev: improve memory usage”
  1. 00/10 name-rev: improve memory usageRené Scharfe, Feb 4, 2020
  2. 01/10 name-rev: rewrite create_or_update_name()René Scharfe, Feb 4, 2020
  3. Derrick StoleeFeb 5, 2020
  4. Taylor BlauFeb 5, 2020
  5. Andrei RybakFeb 5, 2020
  6. René ScharfeFeb 5, 2020
  7. 02/10 name-rev: remove unused typedefRené Scharfe, Feb 4, 2020
  8. 03/10 name-rev: respect const qualifierRené Scharfe, Feb 4, 2020
  9. 04/10 name-rev: don't leak path copy in name_ref()René Scharfe, Feb 4, 2020
  10. Derrick StoleeFeb 5, 2020
  11. 05/10 name-rev: don't _peek() in create_or_update_name()René Scharfe, Feb 4, 2020
  12. 06/10 name-rev: put struct rev_name into commit slabRené Scharfe, Feb 4, 2020
  13. 07/10 name-rev: factor out get_parent_name()René Scharfe, Feb 4, 2020
  14. 08/10 name-rev: pre-size buffer in get_parent_name()René Scharfe, Feb 4, 2020
  15. Derrick StoleeFeb 5, 2020
  16. René ScharfeFeb 5, 2020
  17. 09/10 name-rev: generate name strings only if they are betterRené Scharfe, Feb 4, 2020
  18. Derrick StoleeFeb 5, 2020
  19. René ScharfeFeb 5, 2020
  20. 10/10 name-rev: release unused name stringsRené Scharfe, Feb 4, 2020
  21. Derrick StoleeFeb 5, 2020
  22. Derrick StoleeFeb 5, 2020
  23. Derrick StoleeFeb 5, 2020
  24. 01/10 name-rev: rewrite create_or_update_name()René Scharfe, Feb 5, 2020
  25. 11/10 name-rev: sort tip names before applyingRené Scharfe, Feb 5, 2020
  26. Junio C HamanoFeb 5, 2020
  27. René ScharfeFeb 5, 2020

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.