midpoint

Documentation

Overview

Package midpoint encapsulates all logic pertaining to determining the next candidate for bisection.

Bisection finds a culprit for some performance regression by continuously comparing two commits. The range of commits is reduced by half for every iteration, until one commit that causes a regression is identified.

As part of that search, the next "candidate" to compare against is found by calculating the midpoint between two commits. Once all options have been exhausted (specifically, when the starting and ending commits are adjacent to each other), the system assumes a DEPS roll and searches for the culprit in the range of commits rolled in.

Each iterative call to midpoint means that the bisection workflow is continuing to search for the culprit.

EXAMPLE:

Let's assume the most basic: Chromium @ commit hash 1 (C1) and C2. Gitiles Logs would return [C5, C4, C3, C2]. C5 is popped off, and we're left with [C4, C3, C2]. Because the ordering is from latest -> earliest, this is reversed, and thus becomes [C2, C3, C4]. The calculated midpoint would be at index 1, or C3.

The next set of iterations would be as follows: C1 - C3 and C3 - C5. For the range C1 - C3, Gitiles Logs would return [C3, C2] and removing C3 leaves C2, which would be the next midpoint for that pair. Following the same logic, C4 would be the midpoint for C3 - C5. This presents the bisection workflow with the following set of iterations to compare: (C1 - C2 | C2 - C3 | C3 - C4 | C4 - C5)

In this example, let's say C3 was a DEPS roll. A DEPS roll usually modifies the git hash for _one_ repository per roll in the DEPS file. That means if C2's DEPS file had V8 @ commit 1, a DEPS roll for the V8 repository would change C3 to V8 @ commit, say 3.

As bisection continues to search for the culprit, the start and end commits may be C2 and C3. In this case, Gitiles Logs would return [C3], which is our indicator that the two commits are adjacent. For adjacent changes, FindMidCombinedCommit assumes C3 to be a DEPS roll.

Note: FindMidCombinedCommit only supports git-based dependencies (no CIPD).

When a DEPS roll is assumed, FindMidCombinedCommit fetches the DEPS content for each of the files and finds the first different repository (different = git hash is different for the same repository url, which would indicate "the roll" happened. Following the example above, if V8 was rolled from V8@1 to V8@3, FindMidCombinedCommit would determine V8@2 as midpoint because Gitiles logs for V8 would return [V8@3, V8@2], popping off V8@3 and leaving V8@2.

If the two DEPS contents had been equal (meaning the DEPS roll assumption was wrong), FindMidCombinedCommit returns the former commit (C2), which is its indicator that there's nothing else to parse through.

All git-based dependencies need to build on some Chromium base. For when V8@2 is determined as midpoint, FindMidCombinedCommit would return a CombinedCommit with C2 as Main, and [V8@2] as its ModifiedDeps.

Continuing the example, let's assume bisect is still searching for the culprit. Since the last midpoint was C2 + V8@2, the comparisons then become (C2 - C2+V8@2 | C2+V8@2 - C3). On either arm of the comparison, ModifiedDeps is present, which is the indicator that the search is happening in some git-based dep repository (in this case V8).

To determine the range of commits to send to Gitiles, the implementation requires the start/end to be present for that git-based dep repository. So, for C2 - C2+V8@2, it'll fill the left CombinedCommit by searching DEP at Chromium@2, find V8 and fill it. So C2 becomes C2+V8@1, and now it can compare V8@1 to V8@2.

If V8@2 is a DEP roll as well, say rolled WebRTC (W for short in example) from commit 1 to 3, following the logic above, FindMidCombinedCommit would return a Combined Commit: Main: C2, Modified Deps: [V8@1, W@2].

EDGE CASES:

FindMidCombinedCommit will fill in the DEPS of commits and pass that information to a helper function to find the midpoint between two commits. This leads to a few edge cases when FindMidCombinedCommit compares commits with separate base hashes. Those edge cases are: - Given the second to last commit in a DEPS roll vs the DEPS roll, return the last commit in the DEPS roll. For example, given the commits: {C@1}; {C@1, skia@1}; {C@1, skia@2}; {C@1, skia@3}; {C@2}, we want to find midpoint of {C@1, skia@2} vs {C@2}. {C@2} fills in DEPS and becomes {C@2, skia@3}. Instead of returning {C@1, skia@2}, FindMidCombinedCommit returns {C@1, skia3}. - Given the last commit in a DEPS roll vs the DEPS roll, return the last commit. For example, {C@1, skia@3} vs {C@2}. {C@2} fills in DEPS and becomes {C@2, skia@3}. Instead of treating this as skia@3 vs skia@3, instead return {C@1, skia@3}. - Given the first commit in a DEPS roll vs the previous base commit, return the base commit. For example, {C@1} vs {C@1, skia@1} should return {C@1}, using similar logic as the previous edge case.

CAVEATS:

• The implementation does not support a DEPS roll that rolls more than 1 git-base dependency. The implementation today will start digging the first one it finds, even though the actual culprit could be in one of the other git-based dependencies that it rolls.
• From the example above, let's say V8@2 rolled W8 from 1 to 2 (meaning that's also adjacent). It is possible that the W8 roll is also a DEPS roll, but the implementation today does not dig further. It instead terminates that they're adjancent and is unable detemrine midpoint.
• FindMidCombinedCommit also does not support the scenario where there are more than 1 modified deps in the two commits provided. FindMidCombinedCommit was implemented expecting linear growth of modified dependencies, following the assumption that a DEPS roll only rolls one dependency at a time.

Index

• Constants
• type CommitRange
• type MidpointHandler
  • func New(ctx context.Context, c *http.Client) *MidpointHandler
  • func (m *MidpointHandler) Equal(ctx context.Context, first, second *common.CombinedCommit) (bool, error)
  • func (m *MidpointHandler) FindMidCombinedCommit(ctx context.Context, startCommit, endCommit *common.CombinedCommit) (*common.CombinedCommit, error)
  • func (m *MidpointHandler) WithRepo(url string, r gitiles.GitilesRepo) *MidpointHandler

Constants

const (
	GitilesEmptyResponseErr = "Gitiles returned 0 commits, which should not happen."
	ChromiumSrcGit          = "https://chromium.googlesource.com/chromium/src.git"
)

Types

type CommitRange

type CommitRange struct {
	Left  *common.CombinedCommit
	Right *common.CombinedCommit
}

CommitRange provides information about the left and right commits used to determine the next commit to bisect against.

type MidpointHandler

type MidpointHandler struct {
	// contains filtered or unexported fields
}

MidpointHandler encapsulates all logic to determine the next potential candidate for Bisection.

func New

func New(ctx context.Context, c *http.Client) *MidpointHandler

New returns a new MidpointHandler.

func (*MidpointHandler) Equal

func (m *MidpointHandler) Equal(ctx context.Context, first, second *common.CombinedCommit) (bool, error)

Equal takes two combined commits and returns whether they are equal.

Modified deps affects the equality of two combined commits. If the length of both modified deps are not equal between first and second, this check will backfill modified deps information from DEPS files such that they are equal before calculating and comparing the key.

func (*MidpointHandler) FindMidCombinedCommit

func (m *MidpointHandler) FindMidCombinedCommit(ctx context.Context, startCommit, endCommit *common.CombinedCommit) (*common.CombinedCommit, error)

FindMidCombinedCommit searches for the median commit between two combined commits.

The search takes place through Main if no ModifiedDeps are present. When ModifiedDeps are defined, it first searches for the repository that has different git hashes. It then uses those two git hashes as the range to determine the median.

In both scenarios, if the two commits are adjacent, a DEPS roll is assumed. This will parse the content of DEPS files at the two commits and try to look for which git-based dependency might've been rolled. Once identified, it searches for a median from the base to rolled git hash.

See midpoint/doc.go for examples and details.

func (*MidpointHandler) WithRepo

func (m *MidpointHandler) WithRepo(url string, r gitiles.GitilesRepo) *MidpointHandler

WithRepo returns a MidpointHandler with the repository url mapped to a GitilesRepo object.