[lldb-dev] [RFC] Fast Conditional Breakpoints (FCB)
Pavel Labath via lldb-dev
lldb-dev at lists.llvm.org
Tue Aug 20 00:46:45 PDT 2019
On 20/08/2019 00:11, Ismail Bennani wrote:
>> On Aug 19, 2019, at 2:30 PM, Frédéric Riss <friss at apple.com> wrote:
>>
>>
>>
>>> On Aug 16, 2019, at 11:13 AM, Ismail Bennani via lldb-dev <lldb-dev at lists.llvm.org> wrote:
>>>
>>> Hi Pavel,
>>>
>>> Thanks for all your feedbacks.
>>>
>>> I’ve been following the discussion closely and find your approach quite interesting.
>>>
>>> As Jim explained, I’m also trying to have a conditional breakpoint, that is able to stop a specific thread (name or id) when the condition expression evaluates to true.
>>>
>>> I feel like stacking up options with your approach would imply doing more context switches.
>>> But it’s definitely a better fallback mechanism than the current one. I’ll try to make a prototype to see the performance difference for both approaches.
>>>
>>>
>>>> On Aug 15, 2019, at 10:10 AM, Pavel Labath <pavel at labath.sk> wrote:
>>>>
>>>> Hello Ismail, and wellcome to LLDB. You have a very interesting (and not entirely trivial) project, and I wish you the best of luck in your work. I think this will be a very useful addition to lldb.
>>>>
>>>> It sounds like you have researched the problem very well, and the overall direction looks good to me. However, I do have some ideas suggestions about possible tweaks/improvements that I would like to hear your thoughts on. Please find my comments inline.
>>>>
>>>> On 14/08/2019 22:52, Ismail Bennani via lldb-dev wrote:
>>>>> Hi everyone,
>>>>> I’m Ismail, a compiler engineer intern at Apple. As a part of my internship,
>>>>> I'm adding Fast Conditional Breakpoints to LLDB, using code patching.
>>>>> Currently, the expressions that power conditional breakpoints are lowered
>>>>> to LLVM IR and LLDB knows how to interpret a subset of it. If that fails,
>>>>> the debugger JIT-compiles the expression (compiled once, and re-run on each
>>>>> breakpoint hit). In both cases LLDB must collect all program state used in
>>>>> the condition and pass it to the expression.
>>>>> The goal of my internship project is to make conditional breakpoints faster by:
>>>>> 1. Compiling the expression ahead-of-time, when setting the breakpoint and
>>>>> inject into the inferior memory only once.
>>>>> 2. Re-route the inferior execution flow to run the expression and check whether
>>>>> it needs to stop, in-process.
>>>>> This saves the cost of having to do the context switch between debugger and
>>>>> the inferior program (about 10 times) to compile and evaluate the condition.
>>>>> This feature is described on the [LLDB Project page](https://lldb.llvm.org/status/projects.html#use-the-jit-to-speed-up-conditional-breakpoint-evaluation).
>>>>> The goal would be to have it working for most languages and architectures
>>>>> supported by LLDB, however my original implementation will be for C-based
>>>>> languages targeting x86_64. It will be extended to AArch64 afterwards.
>>>>> Note the way my prototype is implemented makes it fully extensible for other
>>>>> languages and architectures.
>>>>> ## High Level Design
>>>>> Every time a breakpoint that holds a condition is hit, multiple context
>>>>> switches are needed in order to compile and evaluate the condition.
>>>>> First, the breakpoint is hit and the control is given to the debugger.
>>>>> That's where LLDB wraps the condition expression into a UserExpression that
>>>>> will get compiled and injected into the program memory. Another round-trip
>>>>> between the inferior and the LLDB is needed to run the compiled expression
>>>>> and extract the expression results that will tell LLDB to stop or not.
>>>>> To get rid of those context switches, we will evaluate the condition inside
>>>>> the program, and only stop when the condition is true. LLDB will achieve this
>>>>> by inserting a jump from the breakpoint address to a code section that will
>>>>> be allocated into the program memory. It will save the thread state, run the
>>>>> condition expression, restore the thread state and then execute the copied
>>>>> instruction(s) before jumping back to the regular program flow.
>>>>> Then we only trap and return control to LLDB when the condition is true.
>>>>> ## Implementation Details
>>>>> To be able to evaluate a breakpoint condition without interacting with the
>>>>> debugger, LLDB changes the inferior program execution flow by overwriting
>>>>> the instruction at which the breakpoint was set with a branching instruction.
>>>>> The original instruction(s) are copied to a memory stub allocated in the
>>>>> inferior program memory called the __Fast Conditional Breakpoint Trampoline__
>>>>> or __FCBT__. The FCBT will allow us the re-route the program execution flow to
>>>>> check the condition in-process while preserving the original program behavior.
>>>>> This part is critical to setup Fast Conditional Breakpoints.
>>>>> ```
>>>>> Inferior Binary Trampoline
>>>>> | . | +-------------------------+
>>>>> | . | | |
>>>>> | . | +--------->+ Save RegisterContext |
>>>>> | . | | | |
>>>>> +-------------------------+ | +-------------------------+
>>>>> | | | | |
>>>>> | Instruction | | | Build Arguments Struct |
>>>>> | | | | |
>>>>> +-------------------------+ | +-------------------------+
>>>>> | +-----------+ | |
>>>>> | Branch to Trampoline | | Call Condition Checker |
>>>>> | +<----------+ | |
>>>>> +-------------------------+ | +-------------------------+
>>>>> | | | | |
>>>>> | Instruction | | | Restore RegisterContext |
>>>>> | | | | |
>>>>> +-------------------------+ | +-------------------------+
>>>>> | . | | | |
>>>>> | . | +----------+ Run Copied Instructions |
>>>>> | . | | |
>>>>> | . | +-------------------------+
>>>>> ```
>>>>> Once the execution reaches the Trampoline, several steps need to be taken.
>>>>> LLDB relies on its UserExpressions to JIT these more complex conditional
>>>>> expressions. However, since the execution will be handled by the debugged
>>>>> program, LLDB will generate some code ahead-of-time in theTrampoline that
>>>>> will allow the inferior to initialize the expression's argument structure.
>>>>> Generating the condition checker as well as the code to initialize
>>>>> the argument structure of each breakpoint hit is handled by
>>>>> __BreakpointInjectedSite__ class, which builds the conditional expression for
>>>>> all the BreakpointLocations, emits the `$__lldb_expr` function, and relocates
>>>>> variables in the `$__lldb_arg` structure.
>>>>> BreakpointInjectedSites are created in the __Process__ if the user enables
>>>>> the `-I | --inject-condition` flag when setting or modifying a breakpoint.
>>>>> Because the __FCBT__ is architecture specific, BreakpointInjectedSites will
>>>>> only be available when a target has added support to it, in the matching
>>>>> Architecture Plugin.
>>>>> Several parts of lldb have to be modified to implement this feature:
>>>>> - **Breakpoint**: Added BreakpointInjectedSite, and helper functions to the
>>>>> related class (Breakpoint, BreakpointLocation,
>>>>> BreakpointSite, BreakpointOptions)
>>>>> - **Plugins**: Added ObjectFileTrampoline for the unwinding
>>>>> Added x86_64 ABI support (FCBT setup & safety checks)
>>>>> - **Symbol**: Changed `FuncUnwinders` and `UnwindPlan` to support FCBT
>>>>> - **Target**: Added BreakpointInjectedSite creation to `Process` to insert
>>>>> the jump to the FCBT
>>>>> Added the Trampoline module creation to `ABI` for the
>>>>> unwinding
>>>>> ### Breakpoint Option
>>>>> Since Fast Conditional Breakpoints are still under development, they will not
>>>>> be on by default, but rather we will provide a flag to 'breakpoint set" and
>>>>> "breakpoint modify" to enable the feature. Note that the end-goal is to have
>>>>> them as a default and only fallback to regular conditional breakpoints on
>>>>> unsupported architectures.
>>>>> They can be enabled when using `-I | --inject-condition` option. These options
>>>>> can also be enabled using the Python Scripting Bridge public API, using the
>>>>> `InjectCondition(bool enable)` method on an __SBBreakpoint__ or
>>>>> __SBBreakpointLocation__ object.
>>>>> This feature is intended to be used with condition expression
>>>>> (`-c <expr> | --condition <expr>`), but also other conditions types such as:
>>>>> - Thread ID (`-t <thread-id> | --thread-id <thread-id>`)
>>>>> - Thread Index (`-x <thread-index> | --thread-index <thread-index>`)
>>>>> - Thread Queue Name
>>>>> ### Trampoline
>>>>> To be able to inject the condition, we need to re-route the debugged program's
>>>>> execution flow. This parts is handled in the __Trampoline__, a memory stub
>>>>> allocated in the inferior that will contain the condition check while
>>>>> preserving the program's original behavior.
>>>>> The trampoline is architecture specific and built by lldb. To have the
>>>>> condition evaluation work out-of-place, several steps need to be completed:
>>>>> 1. Save all the registers by pushing them to the stack
>>>>> 2. Build the `$__lldb_arg` structure by calling a injected UtilityFunction
>>>>> 3. Check the condition by calling the injected UserExpression and execute a
>>>>> trap if the condition is true.
>>>>> 4. Restore register context
>>>>> 5. Rewrite and run original copied instructions operands
>>>>> All the values needed for the steps can be computed ahead of time, when the
>>>>> breakpoint is set (i.e: size of the allocation, jump address, relocation ...).
>>>>> Since the x86_64 ISA has variable instruction size, LLDB moves enough
>>>>> instructions in the trampoline to be able to overwrite them with a jump to the
>>>>> trampoline. Also, the allocation region for the trampoline might be too far
>>>>> away for a single jump, so we might need to have several branch island before
>>>>> reaching the trampoline (WIP).
>>>>> ### BreakpointInjectedSite
>>>>> To handle the Fast Conditional Breakpoint setup, LLDB uses
>>>>> __BreakpointInjectedSites__ which is a sub-class of the BreakpointSite class.
>>>>> BreakpointInjectedSites uses different `UserExpression` to resolve variables
>>>>> and inject the condition checker.
>>>>> #### Condition Checker
>>>>> Because a BreakpointSite can have multiple BreakpointLocations with different
>>>>> conditions, LLDB need first iterate over each owner of the BreakpointSite and
>>>>> gather all the conditions. If one of the BreakpointLocations doesn't have a
>>>>> condition or the condition is not set to be injected, the
>>>>> BreakpointInjectedSite will behave as a regular BreakpointSite.
>>>>> Once all the conditions are fetched, LLDB will create a __UserExpression__
>>>>> with the injected trap instruction.
>>>>> When a trap is hit, LLDB uses the __BreakpointSiteList__, a map from a trap
>>>>> address to a BreakpointSite to identify where to stop. To allow LLDB to catch
>>>>> the injected trap at runtime, it will disassemble the compiled expression and
>>>>> scan for the trap address. The injected trap address is then added to LLDB's
>>>>> __BreakpointSiteList__.
>>>>> When generated, this is what the condition checker looks like:
>>>>> ```cpp
>>>>> void $__lldb_expr(void *$__lldb_arg)
>>>>> {
>>>>> /*lldb_BODY_START*/
>>>>> if (condition) {
>>>>> __builtin_debugtrap();
>>>>> };
>>>>> /*lldb_BODY_END*/
>>>>> }
>>>>> ```
>>>>> #### Argument Builder
>>>>> The conditional expression will often refer to local variables, and the
>>>>> references to these variables need to be tied to the instances of them in the
>>>>> current frame.
>>>>> Usually the expression evaluator invokes the __Materializer__ which fetches
>>>>> the variables values and fills the `$__lldb_arg` structure. But since we don't
>>>>> want to switch contexts, LLDB has to resolve used variables by generating code
>>>>> that will initialize the `$__lldb_arg` pointer, before running the condition
>>>>> checker.
>>>>> That's where the __Argument Builder__ comes in.
>>>>> The argument builder uses an `UtilityFunction` to generate the
>>>>> `$__lldb_create_args_struct` function. It is called by the Trampoline
>>>>> before the condition checker, in order to resolve variables used in the
>>>>> condition expression.
>>>>> `$__lldb_create_args_struct` will fill the `$__lldb_arg` in several steps:
>>>>> 1. It takes advantage of the fact that LLDB saved all the registers to the
>>>>> stack and map them in an `register_context` structure.
>>>>> ```cpp
>>>>> typedef struct {
>>>>> // General Purpose Registers
>>>>> } register_context;
>>>>> ```
>>>>> 2. Using information from the variable resolver, it allocates a memory stub
>>>>> that will contain the used variable addresses.
>>>>> 3. Then, it will use the register values and the collected metadata to
>>>>> compute the used variable address and write that into the
>>>>> newly allocated structure.
>>>>> 4. Finally the allocated structure is returned to the trampoline, which will
>>>>> pass it as an argument to the injected condition checker.
>>>> I am wondering whether we really need to involve the memory allocation functions here. What's the size of this address structure? I would expect it to be relatively small compared to the size of the entire register context that we have just saved to the stack. If that's the case, the case then maybe we could have the trampoline allocate some space on the stack and pass that as an argument to the $__lldb_arg building code.
>>>
>>> Allocating the $__lldb_arg struct in the stack is on my to-do list. This will change in the coming revisions.
>>>
>>>>
>>>>> Since `$__lldb_create_args_struct` uses the same JIT Engine as the
>>>>> UserExpression, LLDB will parse, build and insert it in the program memory.
>>>>> #### Variable Resolver
>>>>> When creating a Fast Conditional Breakpoint, the __debug info__ tells us
>>>>> where the used variables are located. Using this information and the saved
>>>>> register context, we can generate code that will resolve the variables at
>>>>> runtime (__Step 3 of the Argument Builder__).
>>>>> LLDB will first get the `DeclMap` from the condition UserExpression and pull a
>>>>> list of the used variables. While iterating on that list, LLDB extracts each
>>>>> variable's __DWARF Expression__.
>>>>> DWARF expressions explain how to reconstruct a variable's values using DWARF
>>>>> operations.
>>>>> The reason why LLDB needs the register context is because local variable are
>>>>> often at an offset of the __Stack Base Pointer register__ or written across
>>>>> one or multiple registers. This is why I've only focused on `DW_OP_fbreg`
>>>>> expressions since I could get the offset of the variable and add it to the
>>>>> base pointer register to get its address. The variable address, and other
>>>>> metadata such as its size, its identifier and the DWARF Expression are saved
>>>>> to an `ArgumentMetadata` vector that will be used by the `ArgumentBuilder`
>>>>> to create the `$__lldb_arg` structure.
>>>>> Since all the registers are already mapped to a structure, I should
>>>>> be able to support more __DWARF Operations__ in the future.
>>>>> After collecting some metrics on the __Clang__ binary, built at __-O0__,
>>>>> the debug info shows that __99%__ of the most used DWARF Operations are :
>>>>> |DWARF Operation| Occurrences |
>>>>> |---------------|---------------------------|
>>>>> |DW\_OP_fbreg | 2 114 612 |
>>>>> |DW\_OP_reg | 820 548 |
>>>>> |DW\_OP_constu | 267 450 |
>>>>> |DW\_OP_addr | 17 370 |
>>>>> | __Top 4__ | __3 219 980 Occurrences__ |
>>>>> |---------------|---------------------------|
>>>>> | __Total__ | __3 236 859 Occurrences__ |
>>>>> Those 4 operations are the one that I'll support for now.
>>>>> To support more complex expressions, we would need to JIT-compile
>>>>> a DWARF expression interpreter.
>>>>> ### Unwinders
>>>>> When the program hits the injected trap instruction, the execution stops
>>>>> inside the injected UserExpression.
>>>>> ```cpp
>>>>> * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
>>>>> * frame #0: 0x00000001001070b9 $__lldb_expr`$__lldb_expr($__lldb_arg=0x00000001f5671000) at lldb-33192c.expr:49
>>>>> frame #1: 0x0000000100105028
>>>>> ```
>>>>> This part of the program should be transparent to user. To allow LLDB to
>>>>> elide the condition checker and the FCBT frame, the Unwinder needs to be
>>>>> able to identify all of the frames, up to the user's source code frame.
>>>>> The injected UserExpression already has a valid stack frame, but it doesn't
>>>>> have any information about its caller, the Trampoline. In order to unwind to
>>>>> the user's code, LLDB needs symbolic information for the trampoline.
>>>>> This information is tied to LLDB modules, created using an ObjectFile
>>>>> representation, the __ObjectFileTrampoline__ in our case.
>>>>> It will contain several pieces of information such as, the module's name and
>>>>> description, but most importantly the module __Symbol Table__ that will have
>>>>> the trampoline symbol (`$__lldb_injected_conditional_bp_trampoline `) and a
>>>>> __Text Section__ that will tell the unwinder the trampoline bounds.
>>>>> Then, LLDB inserts a __Function Unwinder__ in the module UnwindTable and
>>>>> creates an __Unwind Plan__ pointing to the BreakpointLocation return address.
>>>>> This is done taking into consideration that the trampoline will alter the
>>>>> memory layout by spilling registers to the stack.
>>>>> Finally, the newly created module is appended to the target image list, which
>>>>> allows LLDB to move between the injected code and the user code seamlessly.
>>>>> This is what the backtrace looks like after hitting the injected trap:
>>>>> ```cpp
>>>>> * thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
>>>>> frame #0: 0x00000001001070b9 $__lldb_expr`$__lldb_expr($__lldb_arg=0x00000001f4c71000) at lldb-ca98b7.expr:49
>>>>> frame #1: 0x0000000100105028 $__lldb_injected_conditional_bp_trampoline`$__lldb_injected_conditional_bp_trampoline + 40
>>>>> * frame #2: 0x0000000100000f5b main`main at main.c:7:23
>>>>> ```
>>>>> For now, LLDB selects the user frame but the goal would be to mask all the
>>>>> frames introduced by the Fast Conditional Breakpoint.
>>>>> A `debug-injected-condition` setting will allow to stop at the FCBT and show
>>>>> all the elided frames.
>>>>
>>>> Regarding unwinding, I am wondering whether we really need to do anything really special. It sounds to me that if we try a little bit harder then we could make the trampoline code look very much like a signal handler, and have it be treated as such. Then the only special thing we would need to do is to hide the topmost trampoline code somewhere higher up in the presentation layer.
>>>>
>>>> I am imagining the trampoline code could look something like this (excuse my bad assembly, I haven't written that in a while):
>>>> pushq %rax
>>>> pushq %rbx
>>>> ...
>>>> leaq $SIZE_OF_REGISTER_CONTEXT(%rsp), %r10 # void *registers
>>>> movq %rsp, %r11 # void *args
>>>> subq $SIZE_OF_ARGS, %rsp
>>>> movq %r10, %rdi
>>>> movq %r11, %rsi
>>>> callq __build_args # __build_args(const void *registers, void *args)
>>>> movq %r11, %rdi
>>>> callq __lldb_expr # __lldb_expr(void *args)
>>>> test %al, %al
>>>> jz .Ldone
>>>> trap_opcode:
>>>> int3
>>>> .Ldone:
>>>> addq $SIZE_OF_ARGS, %rsp
>>>> pop everything, execute displaced instructions and jump back
>>>>
>>>> I think this trampoline is pretty similar to what you're proposing, but there are a couple of subtle differences:
>>>> - the args structure is allocated on the stack - I already spoke about that
>>>> - the testing of the condition happens inside the trampoline
>>>> I think this second item has several advantages. Firstly, this means that we hit the breakpoint, we only have one extra frame on the stack. So even if we don't do any extra work in the debugger to hide this stuff, we don't clutter the stack too much.
>>>>
>>>> Secondly, this means we can avoid the "dissasemble and scan for trap opcode" step, which is kind of a hack -- after all, we generated these instructions, so we should _know_ where the trap opcode is. This way, you can emit a special symbol (trap_opcode label in the example above), that lldb can then search for, and know it's location exactly.
>>>>
>>>
>>> I think testing the condition inside the trampoline might be very limiting:
>>> - The variable resolution would be need to be rethought to allow the condition check to happen in the trampoline.
>>> - To be able to support different condition types (expression / thread name / thread id …), the $__lldb_expr is a better option IMO. In the future, we might also inject logging code that would only be run according to the condition.
>>> - This feature requires at least one more frame (for your approach), that would still need to be hidden to the user. I don’t think hiding 2 frames is more work than hiding 1.
>>
>> I might be the one misunderstanding, but I think you missed Pavel’s point. In Pavel’s model, you still JIT the condition into __llldb_expr and pas it the argument structure. The difference is that you don’t have the trap inside of the JITed code, you have the JITed code return whether to stop or not and have the trampoline hit the trap depending in the return value. I agree this seems cleaner than scanning the output to find the trap.
>
> Inserting the trap in the trampoline would still require to fetch the $__lldb_expr's return value (architecture-specific) and write an assembly check statement (compare and jump).
> Right now, all of this is abstracted by the UserExpression.
>
> I do agree that it’s cleaner, and will take it into consideration for my next patches.
>
Note that this does not really have to be a proper "return value". If it
makes anything easier, the result can also be returned through the
__lldb_expr struct similar to how we "return" values from normal
expressions.
That said, I think the reason why fetching the return value by hand
sounds scary is because the current process of constructing the
trampoline is pretty clunky -- you need to memcpy opcodes and their
arguments around by hand. If we switched to creating the trampoline by
injecting file-level asm into the compiled expression, then the
trampoline would become pretty much a static string embedded into the
ABI plugin, and "fetching the return value" would mean writing something
like "testb %al, %al" into that string.
cheers,
pl
More information about the lldb-dev
mailing list