Re: frame theory, was pointer madness

Jim Blandy
2006-01-26T23:16:25Z

I've read the conversation with Daniel, but I'm going to pick at your
use of terminology even more carefully, because I think that's
actually a central source of confusion.

As you've worked out, "the next frame" in GDB-speak means "the next
younger frame". The "next frame" of some frame F is the frame for the
function F called. There is no standard terminology for this that I
know of, which is one source of the confusion. It's worth pointing
out that 1) I got the terminology backwards the first time I typed
this paragraph, and 2) Daniel got it backwards too when he said:

>The innermost frame is always #0; it is the first frame "unwound"
>from the sentinel frame. Then the next frame is unwound from frame 0.

He should have said "the PREVIOUS frame is unwound from frame 0".

The frame chain in GDB is a doubly-linked list. Every frame points to
the next and previous frame. When you write things like this:

> prev->frame->next

that's not meaningful, because it isn't clear whether you're talking
about the chain as defined by the "next" pointers, or by the "prev"
pointers. Don't talk about what points to what; use the terms "next"
and "previous". (And check what you type. :) )

> level description
> -1 sentinal frame(virtual)
> 0 youngest frame (the deepest function call and current frame)
> 1 older
> 2 even older
> 3 oldest
>
> And the list should look like this
>
> prev->frame->next
>
> NULL->3->2->1->0->-1->-1->-1........
>
> I think, and I have yet to successfully verify this, that the highest level
> frame should have an id of zero, or at least should.

Don't confuse "level" with "id". The level is generally what the user
uses to identify frames when using the "frame" command; it's what
follows the # mark in "where" output. The frame ID, on the other
hand, is a pair (or on the IA-64, a triplet) of addresses that is
meant to identify a frame throughout its lifetime. They're usually a
code address and a stack address.

Every time the inferior runs, even for a single-step, GDB throws away
all its frame structures, and reconstructs them when the inferior
stops next. It constructs its own frame_info structures starting with
the *youngest* frame, at the top of the stack, and works its way
towards the bottom of the stack. GDB constructs frame_info structures
lazily; it doesn't bother to figure them out until you actually refer
to them (via "up" or "where"). So a NULL "prev" link in a frame_info
structure does not mean that the stack has ended; it simply means that
GDB hasn't produced the next frame yet. What *does* indicate that the
stack has ended is if frame_unwind_id returns the null_frame_id. Note
that, since 'struct frame_id' is a structure, it doesn't make sense to
talk about a "frame id of zero". It's not a number.

It's very good that GDB reconstructs the frame chain from scratch
every time the inferior stops. This avoids bugs caused by out-of-date
information. But it does mean that 'struct frame' objects are useless
for referring to a particular frame while the program runs. For
example, when we 'next' over a function call, we single-step into the
call, and then set a breakpoint at the return address and let the
program continue until we hit it. However, if there's recursion going
on, we might hit that breakpoint when we return to some recursive
invocation of the calling function --- but we're not through with the
call the user asked us to 'next' over. So in addition to setting the
breakpoint at the return address, we need to remember which *frame*
we're looking for a return to. Struct frame objects don't work here;
we throw them away while the inferior runs.

A frame ID is supposed to be a robust, lightweight way to refer to a
particular frame. It's usually the address of the base of the frame
(often, the value the SP had when we entered the function), and the
address of the function itself. When we produce frame_info
structures, we record a frame ID for each one. Then, commands like
"next" compare frame ID's to see whether they've found the frame they
need.

These comparisons can be fooled, of course. If you record a frame's
ID, and then the frame gets popped but the caller calls the same
function again, you're liable to get a new frame with the same ID as
the old frame. It's very difficult to avoid this, and GDB doesn't
bother.

So frame levels (user interface), frame id's (long-term frame
identification), and frame_info structures (detailed but transient
records) are all distinct things to keep track of.

> Normal gdb appears to work by caching the frame of the highest level to a NULL
> prev value,

I'm not sure what this means. GDB starts with the youngest (current)
frame, and then works towards the older frames, producing caller from
callee, until (if it's lucky) it reaches the oldest frame on the
stack.

> When frame 0 is the highest and lowest real
> level it will "unwind" frame zero by accessing -1. which should in turn
> actually read the registers from remote device. Then ->black magic - black
> magic -> gdb realizes there is no higher level frame and caches a NULL there.

You'll see GDB calling the "frame_unwind_register" functions all the
time, not just the first time it constructs the frame_info object.

A NULL "prev" pointer in a frame_info structure simply indicates that
GDB hasn't (yet) produced any older frames. This could be because
there are no older frames, or it could simply be that GDB hasn't
bothered to find them yet.

There isn't any master document defining all this, but I'll see if I
can pirate some of what's been written into this thread for
gdbint.texinfo.