Frame unwind functions

Frame unwind functions

[Michal Ludvig]

Hi all,
since there are different unwind mechanisms in different branches of GDB 
I got a bit lost. I need to sort my thoughts to understand the principles.

First my view of how things now work:

A) One pass to get frame-id:
- process hits a breakpoint and GDB takes control of it.
- it can get values of all registers by simply reading them, and is
   especially interested in PC (%eip on i386) and SP (%esp).
- GDB can somehow determine the frame address FP (ie. top of the stack),
   either by taking it from %ebp on i386 or by CFI unwinding of SP.
- PC and FP together makes a Frame-ID of the innermost frame.
   (Or is frame-id something else?)

B) Now how to do a backtrace:
- first call to get_prev_frame() passes as an argument a pre-filled
   struct frame_info as the 'next_frame' parameter. It only has
   next_frame->pc filled with current PC (%eip), next_frame->unwind
   pointing to sentinel unwinder and a level==-1, which describes
   a sentinel frame.
- GDB creates an empty prev_frame, and sets its level.
- to get current PC we call next_frame->unwind->pc(). In the case of a
   sentinel frame it just reads a PC register from the inferior.
- How to get current FP depends of type of the current frame
   (ie. prev_frame).
   - on i386 we read it from FP register (%ebp)
   - in a CFI frame we read the value of the SP register (by calling
     unwind->reg(SP_REGNUM) for the next_frame, which is a sentinel one,
     ie. we read the SP register directly) and unwind it to get it's
     value at the beginning of the function.
- PC and FP together make up frame id.

C) All subsequent calls to get_prev_frame() always pass next_frame as 
the parameter and:
- Create prev_frame with appropriate level.
- Get current PC in this frame by calling next_frame->unwind->pc()
   - in the case of the normal i386 frame it reads a return address from
     the stack where next_frame->frame points to (plus sizeof(PC)).
   - in the case of CFI frames we must ask the CFI engine to give us the
     return address of the next_frame.
   - if next_frame is a sigtramp frame, PC is read from the saved
     sigcontext on the stack.
- Get FP for this frame
   - in the case of the normal i386 frame it reads the saved %ebp at the
     address of next_frame->frame.
   - in the case of CFI frames we must obtain the SP first. This is
     basically next_frame->frame value (perhaps adjusted by an offset).
     Now we ask the engine to give us the value of SP at the time the
     function was entered, i.e. we must unwind it. This way we get FP.
   - If next_frame is a sigtramp, SP (or FP) is read from the stack
     similarly to PC.
- PC and FP together make up frame id.

So far so good, I hope. Or did I miss something?

But how about registers and parameters?
- In the innermost frame I know the values of all registers.
- By using a CFI engine I could unwind some of them to the state they've
   had when the frame was entered - do I save these values somewhere or
   are they generated on-the-fly when the given frame's unwind_reg() is
   called?
- In the backtrace the function's arguments are printed as well.
   - on i386 it's not a problem since they are on the stack
   - on x86-64 we pass some of them in registers
     - that's fine for the first frame (#0) - I know all registers and I
       can use location lists to find current position of a given arg.
     - for the second frame (#1) I could call
       next_frame->unwind->reg(regnum) to get the register I need and
       unwind it even more by calling this_frame->unwind->reg(regnum) to
       get it's value at the beginning of the frame.
     - but how about the next frames (#2,...)? I can always call
       next_frame->unwind->reg(regnum) and if the next_frame wouldn't
       know its "initial" value (ie. the value at the place of PC) it
       would recursively call next_frame->next_frame->unwind->register()
       untill it get's the value.
This is not desired I think. If I understand the MarkK's code from 
i386newframe branch he saves all known register's positions (stack 
addresses) to frame->unwind_cache (casted to struct i386_frame_cache). 
But it isn't a generic approach. Should all these registers be somehow 
written to the regcache instead? Or to frame->saved_regs? If so, then 
when and where? I think CFI uses it's own frame->context structure for 
this purpose, but I'd like to avoid using it for non-cfi frames.

If I would have all registers saved in each next_frame then I could only 
call next_frame->unwind->reg(regnum) and get the current value. Then 
store it somewhere in this_frame and use as if I just read it from the 
inferior. I believe there is something similar already implemented in 
the GDB but I don't know how. Could someone explain me this thing, please?

Well, long mail, isn't it? But I would like to know if I understand 
correctly what the new frame unwinding stuff does or if I'm missing 
something important.

Thanks for your time,

Michal Ludvig
-- 
* SuSE CR, s.r.o     * mludvig@suse.cz
* (+420) 296.545.373 * http://www.suse.cz

Re: Frame unwind functions

[Andrew Cagney]

> Hi all,
> since there are different unwind mechanisms in different branches of GDB I got a bit lost. I need to sort my thoughts to understand the principles.
> 
> First my view of how things now work:

To be honest, this a very good description of how GDB did work: special 
case on top of special case on top of ....

The first thing to discard is the assumption that the inner most frame 
is, in anyway special.

The introduction of a sentinel frame has ment the elimination of a 
special case code to handle the inner most frame.  Instead there is 
always a more inner frame.  As a consequence, a body of code can always 
use the frame unwind methods to get value of a register.

What was previously written:

	if (frame->level == 0)
	  return read_pc();
	else if (frame->type == DUMMY_FRAME)
	  return deprecated_read_dummy_register (frame, PC_REGNUM);
	else if (pc in sigtramp (...))
	  return something to do with a sigtramp;
	else
	  return get_saved_register (frame->prev, ...);

can now be written as simply:

	frame_unwind_register (frame, PC_REGNUM, ...);


> A) One pass to get frame-id:

The new way is:

- find prev's frame's PC using gdbarch_unwind_pc(this)
- use the PC to identify prev's frame's unwinder
- use prev's frame's unwinder's id method to find prev's frame's ID

this algorithm is used on any frame.

> - process hits a breakpoint and GDB takes control of it.
> - it can get values of all registers by simply reading them, and is
>   especially interested in PC (%eip on i386) and SP (%esp).

No matter what the frame, to obtain a value for that frame the code uses:

	frame_register_unwind (next, regnum, ...);

> - GDB can somehow determine the frame address FP (ie. top of the stack),
>   either by taking it from %ebp on i386 or by CFI unwinding of SP.

Right.  It get's the ID using that frame's ID method.

> - PC and FP together makes a Frame-ID of the innermost frame.
>   (Or is frame-id something else?)

That's it.

The key property being that the base is consant through out the lifetime 
of a frame (At some stage in the future PC may be replaced by function, 
and a second base might be added).

> B) Now how to do a backtrace:
> - first call to get_prev_frame() passes as an argument a pre-filled
>   struct frame_info as the 'next_frame' parameter. It only has
>   next_frame->pc filled with current PC (%eip), next_frame->unwind
>   pointing to sentinel unwinder and a level==-1, which describes
>   a sentinel frame.

All frames are created alike using get_prev_frame().  Even the inner 
most.  The only exception is the sentinel frame.

There is no `case b'.

> - GDB creates an empty prev_frame, and sets its level.
> - to get current PC we call next_frame->unwind->pc(). In the case of a
>   sentinel frame it just reads a PC register from the inferior.

GDB calls gdbarch_unwind_pc(this_frame) which is expected to use only 
unwind methods to compute the PC of this new frame.  The method must be 
frame agnostic - it works with any next_frame.

> - How to get current FP depends of type of the current frame
>   (ie. prev_frame).

Right.  But for get_prev_frame() it calls the frame's unwinder's get id 
method.  There are separate unwinders for each of the cases you mention, 
the correct unwinder being called by get_prev_frame().

>   - on i386 we read it from FP register (%ebp)
>   - in a CFI frame we read the value of the SP register (by calling
>     unwind->reg(SP_REGNUM) for the next_frame, which is a sentinel one,
>     ie. we read the SP register directly) and unwind it to get it's
>     value at the beginning of the function.
> - PC and FP together make up frame id.

> C) All subsequent calls to get_prev_frame() always pass next_frame as the parameter and:

But, all subsequent calls to get_prev_frame() are identical to the first.

There is no `case c'.

> So far so good, I hope. Or did I miss something?
> 
> But how about registers and parameters?
> - In the innermost frame I know the values of all registers.

No.  The code should never differentiate an inner most frame.  Instead, 
always obtain register values by unwinding them from the next frame.

> - By using a CFI engine I could unwind some of them to the state they've
>   had when the frame was entered - do I save these values somewhere or
>   are they generated on-the-fly when the given frame's unwind_reg() is
>   called?

You just need to compute those values on the fly.  Don't bother with 
efficiency smarts.

If performance is ever demonstrated to be a problem then the frame code 
can be tweaked to cache values.

> - In the backtrace the function's arguments are printed as well.
>   - on i386 it's not a problem since they are on the stack
>   - on x86-64 we pass some of them in registers
>     - that's fine for the first frame (#0) - I know all registers and I
>       can use location lists to find current position of a given arg.
>     - for the second frame (#1) I could call
>       next_frame->unwind->reg(regnum) to get the register I need and
>       unwind it even more by calling this_frame->unwind->reg(regnum) to
>       get it's value at the beginning of the frame.
>     - but how about the next frames (#2,...)? I can always call
>       next_frame->unwind->reg(regnum) and if the next_frame wouldn't
>       know its "initial" value (ie. the value at the place of PC) it
>       would recursively call next_frame->next_frame->unwind->register()
>       untill it get's the value.

The above is the desired and correct behavior.  This recursion is 
required for things to work (a stack is recursive by definition).

Have a look at the `info frames' `saved regs' output.

> This is not desired I think. If I understand the MarkK's code from i386newframe branch he saves all known register's positions (stack addresses) to frame->unwind_cache (casted to struct i386_frame_cache). But it isn't a generic approach. Should all these registers be somehow written to the regcache instead? Or to frame->saved_regs? If so, then when and where? I think CFI uses it's own frame->context structure for this purpose, but I'd like to avoid using it for non-cfi frames.

Mark is handling the simple prologue analysis case.  Consider a a stack 
frame consisting of:

(outer) cfi -> trad -> cfi -> sigtramp -> cfi -> sentinel (inner)

Even though the three CFI frames have different more inner frames, all 
three use an identical code base.  And none contain special case code 
such as:
	if (next is a sentinel, or sigtramp, or normal)
This is because all three CFI frames use pure recursion to obtain 
register values from their next frame.

> If I would have all registers saved in each next_frame then I could only call next_frame->unwind->reg(regnum) and get the current value. Then store it somewhere in this_frame and use as if I just read it from the inferior. I believe there is something similar already implemented in the GDB but I don't know how. Could someone explain me this thing, please?

No, you need to make recursive calls.

Per above, if the recursion ever becomes a problem (evidence?) then the 
generic frame code can do better caching.

> Well, long mail, isn't it? But I would like to know if I understand correctly what the new frame unwinding stuff does or if I'm missing something important.
> 
> Thanks for your time,

Andrew

Re: Frame unwind functions

[Michal Ludvig]

Andrew Cagney wrote:
>> Hi all,
>> since there are different unwind mechanisms in different branches of 
>> GDB I got a bit lost. I need to sort my thoughts to understand the 
>> principles.
>>
>> First my view of how things now work:
> 
> To be honest, this a very good description of how GDB did work: special 
> case on top of special case on top of ....

Thanks for appreciation :-)
But I'm afraid you didn't understand me. AFAIK these special cases are 
still in there, but now they're hidden in appropriate unwind function 
sets. You were talking about the interface (frame_unwind_register, 
frame_unwind_id, ...) while I was talking about the internals of these 
methods for different frame types. That's what I'm interested in if I 
should implement these methods for different x86-64 frames - I'm 
examining what other types of frame unwinders do to know what my ones 
should do.

>> - In the backtrace the function's arguments are printed as well.
>>   - on i386 it's not a problem since they are on the stack
>>   - on x86-64 we pass some of them in registers
>>     - that's fine for the first frame (#0) - I know all registers and I
>>       can use location lists to find current position of a given arg.
>>     - for the second frame (#1) I could call
>>       next_frame->unwind->reg(regnum) to get the register I need and
>>       unwind it even more by calling this_frame->unwind->reg(regnum) to
>>       get it's value at the beginning of the frame.
>>     - but how about the next frames (#2,...)? I can always call
>>       next_frame->unwind->reg(regnum) and if the next_frame wouldn't
>>       know its "initial" value (ie. the value at the place of PC) it
>>       would recursively call next_frame->next_frame->unwind->register()
>>       untill it get's the value.
> 
> 
> The above is the desired and correct behavior.  This recursion is 
> required for things to work (a stack is recursive by definition).

What if a desired register's value isn't available anymore? How do I 
report it to the caller of my_frame->unwind->reg()? By setting an 
optimizedp parameter?

Michal Ludvig
-- 
* SuSE CR, s.r.o     * mludvig@suse.cz
* (+420) 296.545.373 * http://www.suse.cz

Re: Frame unwind functions

[Andrew Cagney]

> Andrew Cagney wrote:
> Hi all,
> since there are different unwind mechanisms in different branches of GDB I got a bit lost. I need to sort my thoughts to understand the principles.
> 
> First my view of how things now work:
> 
> To be honest, this a very good description of how GDB did work: special case on top of special case on top of ....
> 
> Thanks for appreciation :-)
> But I'm afraid you didn't understand me. AFAIK these special cases are still in there, but now they're hidden in appropriate unwind function sets. You were talking about the interface (frame_unwind_register, frame_unwind_id, ...) while I was talking about the internals of these methods for different frame types. That's what I'm interested in if I should implement these methods for different x86-64 frames - I'm examining what other types of frame unwinders do to know what my ones should do.

Ah, ok.  An architecutre could potentially have the following unwinders:

- traditional (prologue based)
- sigtramp

The x86-64 GNU/Linux, appears to only have the second.  In addition, 
there is the generic:

- cfi

unwinder.

> - In the backtrace the function's arguments are printed as well.
>   - on i386 it's not a problem since they are on the stack
>   - on x86-64 we pass some of them in registers
>     - that's fine for the first frame (#0) - I know all registers and I
>       can use location lists to find current position of a given arg.
>     - for the second frame (#1) I could call
>       next_frame->unwind->reg(regnum) to get the register I need and
>       unwind it even more by calling this_frame->unwind->reg(regnum) to
>       get it's value at the beginning of the frame.
>     - but how about the next frames (#2,...)? I can always call
>       next_frame->unwind->reg(regnum) and if the next_frame wouldn't
>       know its "initial" value (ie. the value at the place of PC) it
>       would recursively call next_frame->next_frame->unwind->register()
>       untill it get's the value.
> 
> 
> The above is the desired and correct behavior.  This recursion is required for things to work (a stack is recursive by definition).
> 
> What if a desired register's value isn't available anymore? How do I report it to the caller of my_frame->unwind->reg()? By setting an optimizedp parameter?

Yes, at present setting optimized to non-zero is the best there is.  I 
noticed that the cfi unwinder is already doing this.

Andrew