Skip to content
This repository was archived by the owner on Sep 30, 2024. It is now read-only.

Batch changes: make window ranges exclusive to avoid infinite loop#62597

Merged
camdencheek merged 6 commits into
mainfrom
cc/fix-inclusive-range
May 10, 2024
Merged

Batch changes: make window ranges exclusive to avoid infinite loop#62597
camdencheek merged 6 commits into
mainfrom
cc/fix-inclusive-range

Conversation

@camdencheek

@camdencheek camdencheek commented May 10, 2024

Copy link
Copy Markdown
Member

This fixes an issue where we can potentially make no progress in the main loop of Estimate. Commentary inline.

Related Slack thread

Test plan

Added unit test for this case and fuzz test to search for other edge cases.

@cla-bot cla-bot Bot added the cla-signed label May 10, 2024
Comment thread internal/batches/types/scheduler/window/config.go Outdated
@camdencheek camdencheek changed the title wip make time ranges exclusive Batch changes: make window ranges exclusive to avoid infinite loop May 10, 2024
Comment on lines 54 to 61

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Struggling to put this in words that make sense, but the gist of what happened is:

  • schedule.ValidUntil() returns its end time
  • that end time can match (exactly) the end time of the active window
  • whether a time is considered "in" a window is based on inclusive start and end times
  • we detect that the end time of the window is "in" the window, even though there is zero time left in the window
  • since there is zero time left, we make no progress that iteration (schedule.total() == 0)
  • but since schedule.ValidUntil() returns the same end time, we do not make it past the window that we are at the end at.

To solve this, I:

  1. made the end time of a window exclusive so we can not end up in a situation where we make zero progress and also do not progress the interval
  2. because this is a complex loop condition, I also added a failsafe which returns early if we make no progress

Comment on lines 176 to 180

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This previously looped forever. Now it does not loop forever, and the non-nil check validates that we are not hitting the failsafe

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Becuase I was still uncomfortable with this loop, I added a fuzz test which I ran for ~10 minutes. It found no issues, but was able to surface the issues this PR fixes.

@camdencheek camdencheek marked this pull request as ready for review May 10, 2024 21:22
@camdencheek camdencheek requested a review from peterguy May 10, 2024 21:22
@camdencheek camdencheek force-pushed the cc/fix-inclusive-range branch from 51b1937 to e7f3615 Compare May 10, 2024 21:24
@camdencheek camdencheek requested a review from a team May 10, 2024 21:25

@peterguy peterguy left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ran some of my own tests using other time values. Ensured that each piece of the solution does what it's supposed to do. Looks good. It's a pretty complex algorithm, so there will probably be other issues with it.

@camdencheek camdencheek merged commit 750012b into main May 10, 2024
@camdencheek camdencheek deleted the cc/fix-inclusive-range branch May 10, 2024 21:41

@BolajiOlajide BolajiOlajide left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice. Thank you @camdencheek

@BolajiOlajide BolajiOlajide added the backport 5.4.0 label used to backport PRs to the 5.4.0 release branch label May 13, 2024
sourcegraph-release-bot pushed a commit that referenced this pull request May 13, 2024
…62597)

This fixes an issue where we can potentially make no progress in the main loop of Estimate

(cherry picked from commit 750012b)
BolajiOlajide pushed a commit that referenced this pull request May 13, 2024
… infinite loop (#62626)

Batch changes: make window ranges exclusive to avoid infinite loop (#62597)

This fixes an issue where we can potentially make no progress in the main loop of Estimate

(cherry picked from commit 750012b)

Co-authored-by: Camden Cheek <camden@ccheek.com>
camdencheek added a commit that referenced this pull request May 21, 2024
camdencheek added a commit that referenced this pull request May 21, 2024
Adds a changelog entry for the backported fix to batch changes scheduling in #62597
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

backport 5.4.0 label used to backport PRs to the 5.4.0 release branch cla-signed

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants