From: Phillip Wood <phillip.wood123@gmail.com>
Date: Mon, 25 Nov 2019 14:43:07 GMT
Subject: Re: [PATCH] t3429: try to protect against a potential racy todo file problem
Message-ID: <5a43a071-a3c2-770e-bca4-3e73aff96e48@gmail.com>
In-Reply-To: <20191125131833.GD23183@szeder.dev>

On 25/11/2019 13:18, SZEDER Gábor wrote:
> On Sun, Nov 24, 2019 at 10:10:21PM +0100, SZEDER Gábor wrote:
>> To notice a changed todo file the sequencer stores the file's stat
>> data in its 'struct todo_list' instance, and compares it with the
>> file's current stat data after 'reword', 'squash' and 'exec'
>> instructions.  If the two stat data doesn't match, it re-reads the
>> todo file.
>>
>> Sounds simple, but there are some subtleties going on here:
>>
>>    - The 'struct todo_list' holds the stat data from the time when the
>>      todo file was last read.
>>
>>    - This stat data in 'struct todo_list' is not updated when the
>>      sequencer itself writes the todo file.
>>
>>    - Before executing each instruction during an interactive rebase,
>>      the sequencer always updates the todo file by removing the
>>      just-about-to-be-executed instruction.  This changes the file's
>>      size and inode [1].
>>
>> Consequently, when the sequencer looks at the stat data after a
>> 'reword', 'squash' or 'exec' instruction, it most likely finds that
>> they differ, even when the user didn't modify the todo list at all!
>> This is not an issue in practice, it just wastes a few cycles on
>> re-reading the todo list that matches what the sequencer already has
>> in memory anyway.
> 
> It can be much more than just a few cycles, because the total number
> of parsed instructions from all the todo file re-reads can go
> quadratic with the number of rebased commits.
> 
> The simple test below runs 'git rebase -i -x' on 1000 commits, which
> takes over 14seconds to run.  If it doesn't re-read the todo file at
> all (I simply deleted the whole condition block checking the stat data
> and re-reading) it runs for only ~2.5secs.
> 
> Just another angle to consider...

I know dscho was keen to avoid re-parsing the list all the time [1] 
presumably because of the quadratic behavior. (He also assumed most 
people were using ns stat times [2] but that appears not to be the case) 
Could we just compare the text of the todo list on disk to whats in 
todo->buf.buf (with an appropriate offset)? That would avoid parsing the 
text and looking up all the commits with get_oid()

Best Wishes

Phillip

[1] 
https://public-inbox.org/git/alpine.DEB.2.20.1703021617510.3767@virtualbox/
[2] 
https://public-inbox.org/git/alpine.DEB.2.20.1704131526500.2135@virtualbox/

> 
>    ---  >8  ---
> 
> test_expect_success 'test' '
> 	num_commits=1000 &&
> 	test_commit_bulk --filename=file $num_commits &&
> 
> 	/usr/bin/time -f "Elapsed time: %e" \
> 		git rebase -i --root -x true 2>out &&
> 
> 	grep "Executing: true" out >actual &&
> 	test_line_count = $num_commits actual &&
> 
> 	# show the elapsed time
> 	tail -n2 out
> '
> 
>    ---  >8  ---
>