Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fix slow execution when many breakpoints are used #14953

Merged
merged 8 commits into from
May 23, 2023
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Original file line number Diff line number Diff line change
Expand Up @@ -482,9 +482,6 @@ internal bool TrySetBreakpoint(string scriptFile, FunctionContext functionContex
{
Diagnostics.Assert(SequencePointIndex == -1, "shouldn't be trying to set on a pending breakpoint");

if (!scriptFile.Equals(this.Script, StringComparison.OrdinalIgnoreCase))
Copy link
Contributor Author

Choose a reason for hiding this comment

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

This is only called from a single place after we took them out from collection that linked to the current file. So we are sure those belong to the current file. So this is just unnecessary overhead.

return false;

// A quick check to see if the breakpoint is within the scriptblock.
bool couldBeInNestedScriptBlock;
var scriptBlock = functionContext._scriptBlock;
Expand Down Expand Up @@ -595,11 +592,11 @@ internal override bool RemoveSelf(ScriptDebugger debugger)
var boundBreakPoints = debugger.GetBoundBreakpoints(this.SequencePoints);
if (boundBreakPoints != null)
{
Diagnostics.Assert(boundBreakPoints.Contains(this),
Diagnostics.Assert(boundBreakPoints[this.SequencePointIndex].Contains(this),
"If we set _scriptBlock, we should have also added the breakpoint to the bound breakpoint list");
boundBreakPoints.Remove(this);
boundBreakPoints[this.SequencePointIndex].Remove(this);

if (boundBreakPoints.All(breakpoint => breakpoint.SequencePointIndex != this.SequencePointIndex))
if (boundBreakPoints[this.SequencePointIndex].All(breakpoint => breakpoint.SequencePointIndex != this.SequencePointIndex))
{
// No other line breakpoints are at the same sequence point, so disable the breakpoint so
// we don't go looking for breakpoints the next time we hit the sequence point.
Expand Down
109 changes: 72 additions & 37 deletions src/System.Management.Automation/engine/debugger/debugger.cs
Original file line number Diff line number Diff line change
Expand Up @@ -971,7 +971,8 @@ internal ScriptDebugger(ExecutionContext context)
_context = context;
_inBreakpoint = false;
_idToBreakpoint = new ConcurrentDictionary<int, Breakpoint>();
_pendingBreakpoints = new ConcurrentDictionary<int, LineBreakpoint>();
// The string key is function context file path. The int key is sequencePoint index.
_pendingBreakpoints = new ConcurrentDictionary<string, ConcurrentDictionary<int, LineBreakpoint>>();
nohwnd marked this conversation as resolved.
Show resolved Hide resolved
_boundBreakpoints = new ConcurrentDictionary<string, Tuple<WeakReference, ConcurrentDictionary<int, LineBreakpoint>>>(StringComparer.OrdinalIgnoreCase);
_commandBreakpoints = new ConcurrentDictionary<int, CommandBreakpoint>();
_variableBreakpoints = new ConcurrentDictionary<string, ConcurrentDictionary<int, VariableBreakpoint>>(StringComparer.OrdinalIgnoreCase);
Expand Down Expand Up @@ -1174,7 +1175,7 @@ internal void EnterScriptFunction(FunctionContext functionContext)
private void SetupBreakpoints(FunctionContext functionContext)
{
var scriptDebugData = _mapScriptToBreakpoints.GetValue(functionContext._sequencePoints,
_ => Tuple.Create(new List<LineBreakpoint>(),
_ => Tuple.Create(new Dictionary<int, List<LineBreakpoint>>(),
nohwnd marked this conversation as resolved.
Show resolved Hide resolved
new BitArray(functionContext._sequencePoints.Length)));
functionContext._boundBreakpoints = scriptDebugData.Item1;
functionContext._breakPoints = scriptDebugData.Item2;
Expand Down Expand Up @@ -1254,10 +1255,19 @@ private CommandBreakpoint AddCommandBreakpoint(CommandBreakpoint breakpoint)
private LineBreakpoint AddLineBreakpoint(LineBreakpoint breakpoint)
{
AddBreakpointCommon(breakpoint);
_pendingBreakpoints[breakpoint.Id] = breakpoint;
AddPendingBreakpoint(breakpoint);

return breakpoint;
}

private void AddPendingBreakpoint(LineBreakpoint breakpoint)
{
_pendingBreakpoints.AddOrUpdate(
breakpoint.Script,
new ConcurrentDictionary<int, LineBreakpoint> { [breakpoint.Id] = breakpoint },
daxian-dbw marked this conversation as resolved.
Show resolved Hide resolved
(_, dictionary) => { dictionary.TryAdd(breakpoint.Id, breakpoint); return dictionary; });
}

private void AddNewBreakpoint(Breakpoint breakpoint)
{
LineBreakpoint lineBreakpoint = breakpoint as LineBreakpoint;
Expand Down Expand Up @@ -1310,13 +1320,9 @@ private void UpdateBreakpoints(FunctionContext functionContext)
return;
}

foreach ((int breakpointId, LineBreakpoint item) in _pendingBreakpoints)
if (_pendingBreakpoints.TryGetValue(functionContext._file, out var dictionary) && !dictionary.IsEmpty)
{
if (item.IsScriptBreakpoint && item.Script.Equals(functionContext._file, StringComparison.OrdinalIgnoreCase))
{
SetPendingBreakpoints(functionContext);
break;
}
SetPendingBreakpoints(functionContext);
}
}
}
Expand All @@ -1342,7 +1348,11 @@ private void OnBreakpointUpdated(BreakpointUpdatedEventArgs e)

internal bool RemoveLineBreakpoint(LineBreakpoint breakpoint)
{
bool removed = _pendingBreakpoints.Remove(breakpoint.Id, out _);
bool removed = false;
if (_pendingBreakpoints.TryGetValue(breakpoint.Script, out var dictionary))
{
removed = dictionary.Remove(breakpoint.Id, out _);
}

Tuple<WeakReference, ConcurrentDictionary<int, LineBreakpoint>> value;
if (_boundBreakpoints.TryGetValue(breakpoint.Script, out value))
Expand All @@ -1360,8 +1370,8 @@ internal bool RemoveLineBreakpoint(LineBreakpoint breakpoint)
// The bit array is used to detect if a breakpoint is set or not for a given scriptblock. This bit array
// is checked when hitting sequence points. Enabling/disabling a line breakpoint is as simple as flipping
// the bit.
private readonly ConditionalWeakTable<IScriptExtent[], Tuple<List<LineBreakpoint>, BitArray>> _mapScriptToBreakpoints =
new ConditionalWeakTable<IScriptExtent[], Tuple<List<LineBreakpoint>, BitArray>>();
private readonly ConditionalWeakTable<IScriptExtent[], Tuple<Dictionary<int, List<LineBreakpoint>>, BitArray>> _mapScriptToBreakpoints =
new ConditionalWeakTable<IScriptExtent[], Tuple<Dictionary<int, List<LineBreakpoint>>, BitArray>>();

/// <summary>
/// Checks for command breakpoints.
Expand Down Expand Up @@ -1462,9 +1472,9 @@ internal void TriggerVariableBreakpoints(List<VariableBreakpoint> breakpoints)

// Return the line breakpoints bound in a specific script block (used when a sequence point
// is hit, to find which breakpoints are set on that sequence point.)
internal List<LineBreakpoint> GetBoundBreakpoints(IScriptExtent[] sequencePoints)
internal Dictionary<int, List<LineBreakpoint>> GetBoundBreakpoints(IScriptExtent[] sequencePoints)
{
Tuple<List<LineBreakpoint>, BitArray> tuple;
Tuple<Dictionary<int, List<LineBreakpoint>>, BitArray> tuple;
if (_mapScriptToBreakpoints.TryGetValue(sequencePoints, out tuple))
{
return tuple.Item1;
Expand Down Expand Up @@ -1550,16 +1560,25 @@ internal void OnSequencePointHit(FunctionContext functionContext)
{
if (functionContext._breakPoints[functionContext._currentSequencePointIndex])
{
var breakpoints = (from breakpoint in functionContext._boundBreakpoints
where
breakpoint.SequencePointIndex == functionContext._currentSequencePointIndex &&
breakpoint.Enabled
select breakpoint).ToList<Breakpoint>();

breakpoints = TriggerBreakpoints(breakpoints);
if (breakpoints.Count > 0)
if (functionContext._boundBreakpoints.TryGetValue(functionContext._currentSequencePointIndex, out var sequencePointBreakpoints))
{
StopOnSequencePoint(functionContext, breakpoints);
var enabledBreakpoints = new List<Breakpoint>();
foreach (Breakpoint breakpoint in sequencePointBreakpoints)
{
if (breakpoint.Enabled)
{
enabledBreakpoints.Add(breakpoint);
}
}

if (enabledBreakpoints.Count > 0)
{
enabledBreakpoints = TriggerBreakpoints(enabledBreakpoints);
if (enabledBreakpoints.Count > 0)
{
StopOnSequencePoint(functionContext, enabledBreakpoints);
}
}
}
}
}
Expand Down Expand Up @@ -1673,7 +1692,7 @@ internal void Clear()
}

private readonly ExecutionContext _context;
private ConcurrentDictionary<int, LineBreakpoint> _pendingBreakpoints;
private readonly ConcurrentDictionary<string, ConcurrentDictionary<int, LineBreakpoint>> _pendingBreakpoints;
private readonly ConcurrentDictionary<string, Tuple<WeakReference, ConcurrentDictionary<int, LineBreakpoint>>> _boundBreakpoints;
private readonly ConcurrentDictionary<int, CommandBreakpoint> _commandBreakpoints;
private readonly ConcurrentDictionary<string, ConcurrentDictionary<int, VariableBreakpoint>> _variableBreakpoints;
Expand Down Expand Up @@ -1981,48 +2000,53 @@ private void UnbindBoundBreakpoints(List<LineBreakpoint> boundBreakpoints)
foreach (var breakpoint in boundBreakpoints)
{
// Also remove unbound breakpoints from the script to breakpoint map.
Tuple<List<LineBreakpoint>, BitArray> lineBreakTuple;
Tuple<Dictionary<int, List<LineBreakpoint>>, BitArray> lineBreakTuple;
if (_mapScriptToBreakpoints.TryGetValue(breakpoint.SequencePoints, out lineBreakTuple))
{
lineBreakTuple.Item1.Remove(breakpoint);
if (lineBreakTuple.Item1.TryGetValue(breakpoint.SequencePointIndex, out var lineBreakList))
{
lineBreakList.Remove(breakpoint);
}
}

breakpoint.SequencePoints = null;
breakpoint.SequencePointIndex = -1;
breakpoint.BreakpointBitArray = null;
_pendingBreakpoints[breakpoint.Id] = breakpoint;

AddPendingBreakpoint(breakpoint);
}

boundBreakpoints.Clear();
}

private void SetPendingBreakpoints(FunctionContext functionContext)
{
if (_pendingBreakpoints.IsEmpty)
return;

var newPendingBreakpoints = new Dictionary<int, LineBreakpoint>();
var currentScriptFile = functionContext._file;

// If we're not in a file, we can't have any line breakpoints.
if (currentScriptFile == null)
return;

if (!_pendingBreakpoints.TryGetValue(currentScriptFile, out var breakpoints) || breakpoints.IsEmpty)
{
return;
}

// Normally we register a script file when the script is run or the module is imported,
// but if there weren't any breakpoints when the script was run and the script was dotted,
// we will end up here with pending breakpoints, but we won't have cached the list of
// breakpoints in the script.
RegisterScriptFile(currentScriptFile, functionContext.CurrentPosition.StartScriptPosition.GetFullScript());

Tuple<List<LineBreakpoint>, BitArray> tuple;
Tuple<Dictionary<int, List<LineBreakpoint>>, BitArray> tuple;
if (!_mapScriptToBreakpoints.TryGetValue(functionContext._sequencePoints, out tuple))
{
Diagnostics.Assert(false, "If the script block is still alive, the entry should not be collected.");
}

Diagnostics.Assert(tuple.Item1 == functionContext._boundBreakpoints, "What's up?");

foreach ((int breakpointId, LineBreakpoint breakpoint) in _pendingBreakpoints)
foreach ((int breakpointId, LineBreakpoint breakpoint) in breakpoints)
{
bool bound = false;
if (breakpoint.TrySetBreakpoint(currentScriptFile, functionContext))
Expand All @@ -2033,21 +2057,32 @@ private void SetPendingBreakpoints(FunctionContext functionContext)
}

bound = true;
tuple.Item1.Add(breakpoint);

if (tuple.Item1.TryGetValue(breakpoint.SequencePointIndex, out var list))
{
list.Add(breakpoint);
}
else
{
tuple.Item1.Add(breakpoint.SequencePointIndex, new List<LineBreakpoint> { breakpoint });
}

// We need to keep track of any breakpoints that are bound in each script because they may
// need to be rebound if the script changes.
var boundBreakpoints = _boundBreakpoints[currentScriptFile].Item2;
boundBreakpoints[breakpoint.Id] = breakpoint;
}

if (!bound)
if (bound)
{
newPendingBreakpoints.Add(breakpoint.Id, breakpoint);
breakpoints.TryRemove(breakpointId, out _);
}
}

_pendingBreakpoints = new ConcurrentDictionary<int, LineBreakpoint>(newPendingBreakpoints);
// Here could check if all breakpoints for the current functionContext were bound, but because there is no atomic
Copy link
Contributor Author

Choose a reason for hiding this comment

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

How would you want this solved? This should happen rarely so I might lock here. Or just keep it as is and don't clean up the dictionary of files.

Copy link
Collaborator

Choose a reason for hiding this comment

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

I don't fully understand the problem we're trying to solve here, but if you/@PaulHigin is able to explain it to me, I can try to weigh in

Copy link
Contributor Author

Choose a reason for hiding this comment

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

This is pending breakpoints:

_pendingBreakpoints = new ConcurrentDictionary<string, ConcurrentDictionary<int, LineBreakpoint>>()

Pending breakpoints is a dictionary keyed by filepath, that contains a dictionary keyed by sequence point. When all pending breakpoints were bound, it would be nice to remove the key from the _pendingBreakpoints dictionary.

Something like this:

if (_pendingBreakpoints.TryGetValue(currentScriptFile, out var bpsInThisScript) && bpsInThisScript.IsEmpty) {
    _pendingBreakpoints.TryRemoveValue(currentScriptFile, out _);
}

Unfortunately the first line is not atomic, so there is a race condition between the first line and the second. If someone added breakpoint right after we checked the count, in theory we could lose breakpoints.

This seems like a rare condition and can be solved in few ways.

What I did here is that I simply leave the key in the dictionary. This means 1 extra string + empty concurrent dictionary is left in memory, for each file that had breakpoints. I am guessing there are rarely more than 100 distinct files with breakpoints per powershell session, so this seems okay-ish. But still dirty.

The race condition seems very rare, and simply checking if we removed a dictionary in which an item was added and they try to merge it back in might reduce the possibility of removing a breakpoint even further. We would add another race condition, but the possibility of timing both of them exactly right seems infinitely small. Something like this:

if (_pendingBreakpoints.TryGetValue(currentScriptFile, out var bpsInThisScript) && bpsInThisScript.IsEmpty) {
    if (_pendingBreakpoints.TryRemoveValue(currentScriptFile, out var removedBps) && !removedBps.IsEmpty) {
        // someone added a breakpoint after we counted but before we removed
        // merge it back into _pendingBreakpoints
        // this would happen extremely rarely
    }
}

Copy link
Contributor

Choose a reason for hiding this comment

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

The race condition needs to be better defined here. How is setting a breakpoint subject to a race here, via API? PowerShell scripts run on a single thread.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

That is why I was asking how you want this solved because I don't know enough about the interaction of pending breakpoints and code execution. Maybe there is no way that pending breakpoints collection would be changed while this code is running, because it all runs on a single thread, or maybe adding a breakpoint in vscode UI calls into the PowerShell process and sets the breakpoint from a different thread.

I just assumed it is the latter, which is why ConcurrentDictionary was used in the original code and also in the new code.

// api for conditional removal we either need to lock, or do some trickery that has possibility of race conditions.
// Instead we keep the item in the dictionary with 0 breakpoint count. This should not be a big issue,
// because it is single entry per file that had breakpoints, so there won't be thousands of files in a session.
}

private void StopOnSequencePoint(FunctionContext functionContext, List<Breakpoint> breakpoints)
Expand Down
Original file line number Diff line number Diff line change
Expand Up @@ -782,7 +782,7 @@ internal class FunctionContext
internal ExecutionContext _executionContext;
internal Pipe _outputPipe;
internal BitArray _breakPoints;
internal List<LineBreakpoint> _boundBreakpoints;
internal Dictionary<int, List<LineBreakpoint>> _boundBreakpoints;
internal int _currentSequencePointIndex;
internal MutableTuple _localsTuple;
internal List<Tuple<Type[], Action<FunctionContext>[], Type[]>> _traps = new List<Tuple<Type[], Action<FunctionContext>[], Type[]>>();
Expand Down