Go 1.2 runtime symbol table format

[Russ Cox]

I started work on cleaning up the runtime symbol table so that it is less cumbersome and also more easily extensible to help with things like garbage collection metadata. Design at http://golang.org/s/go12symtab. CL in progress. Comments welcome here.

Russ

[Rémy Oudompheng]

Do you think it is possible to adjust the symbol table format so that
we can recover information about inlined routines?

Rémy.

[Russ Cox]

I think we could record that information in a separate FUNCDATA/PCDATA stream without having to change the format the linker knows about.

Russ

[Nigel Tao]

On Thu, Jul 11, 2013 at 3:46 AM, Russ Cox <r...@golang.org> wrote:
> Design at http://golang.org/s/go12symtab.

Struct Func has funcdata, nfuncdata and npcdata fields but no pcdata
field? I'm confused.

Also, the appendix says:

those bytes give the encoded table (in hexadecimal):
01 19 40 52 10 02 10 06 0f 01 0f 27 3f 01

The first 01 should be 02, right?

[Rob Pike]

There's a "metaata" that's missing a "d". Also in the zig-zag
description it says shift right when i think it means shift left.

Do you have any idea how much CPU time is spent decoding the symtab
stuff on startup?

-rob

[Daniel Morsing]

If I'm reading this right, the tables will be in contiguous memory
after the Func struct.

Won't pcsp always be sizeof(Func)? Also wondering why you use
nfuncdata instead of a pcdata delta. For consistency I'd say that
npcdata should be a pcdata end pointer rather than a length.

[Russ Cox]

Actually the pcdata offsets are at sizeof(Func), followed by 4 bytes of padding if needed to get pointer aligned, then the funcdata values, and then the pcsp etc tables. So pcsp is at a computable offset, but not a constant one. I don't quite understand your last sentence. See https://codereview.appspot.com/11085043 for details.

Russ

[Russ Cox]

Yes. The start value used to be 0, not -1, and I missed that byte. :-)

Russ

[Russ Cox]

In the godoc binary on my MacBook Pro, 14 ms.

Russ

[Daniel Morsing]

Was confusing PC-values and func/pc-data, and how exactly you find the
delimiter for a PC-value table. I don't have a problem with how it's
done in the CL.

Once this is in, we need to think about how to format -S output from
gc. I don't want to end up in a GCC like situation where you can't
read the assembly for all the metadata.

[Keith Randall]

Just a question about the opaque identifiers for funcdata/pcdata.  Are they going to be encoded sparsely or densely?  In other words, if a function just has

  FUNCDATA $0, $88

  FUNCDATA $9, $99

Does that mean we'll use 10 slots in the funcdata table?  Or does the table contain index/value pairs?  I'm thinking of some use cases that are pretty sparse (for example, extra info at vararg call sites) and we might not want to keep lots of null entries for all the functions that don't have any information for that identifier.

--

---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Russ Cox]

On Thu, Jul 11, 2013 at 7:21 PM, Keith Randall <k...@google.com> wrote:

Just a question about the opaque identifiers for funcdata/pcdata.  Are they going to be encoded sparsely or densely?  In other words, if a function just has

  FUNCDATA $0, $88

  FUNCDATA $9, $99

Does that mean we'll use 10 slots in the funcdata table?  Or does the table contain index/value pairs?  I'm thinking of some use cases that are pretty sparse (for example, extra info at vararg call sites) and we might not want to keep lots of null entries for all the functions that don't have any information for that identifier.

For now, the idea is that they will be sparse, so your example will have 10 slots. At least for the few things I have in mind, I think every function will have most or all of the defined things, so the sparse encoding is actually dense. If we end up with use cases for lots of rarely used ids then we can easily change that. The same is true for the PCDATA pieces.

Russ

[Ian Lance Taylor]

Why is the function name a pointer to a Go string rather than simply a
Go string?

There have been CLs for shared libraries. Let's support that clearly
here: the PC values should all be relative to the load address of the
module. The load address of a statically linked executable is 0.

Your doc implies a global table of all file names used in the program,
but doesn't spell out where that is found. Again let's make this
clear for shared libraries. It's a per-module table, and how does the
runtime find it?

You've got an npcdata field but no pcdata field. How does the runtime
find the pcdata tables? Actually I don't see why you need npcdata (or
pcdata). Since we are defining funcdata by convention, it seems that
it would suffice to say that funcdata $3 (say) is (by convention) a
pcdata table. That is, the value of funcdata $3 is the offset
(relative to the start of the Func structure) to a pcdata table. Then
it would be an error to use both FUNCDATA $3 and PCDATA $3.

You say that the runtime should do a binary search in a PC-value
table. But then you describe an encoding that stores PC deltas. I
don't understand how to do a binary search on a table stored using
deltas. For that matter, a binary search doesn't seem to help much
since the values are deltas also.

In order to do a binary search, the runtime needs to know the number
of entries in a table. Where is that stored? Or, if the runtime is
not in fact doing a binary search, how does it know where the end of
the table is, so that it can know that it should stop looking for a PC
value that is out of range?

Ian

[Russ Cox]

On Fri, Jul 12, 2013 at 12:52 AM, Ian Lance Taylor <ia...@golang.org> wrote:

On Wed, Jul 10, 2013 at 10:46 AM, Russ Cox <r...@golang.org> wrote:
> I started work on cleaning up the runtime symbol table so that it is less
> cumbersome and also more easily extensible to help with things like garbage
> collection metadata. Design at http://golang.org/s/go12symtab. CL in
> progress. Comments welcome here.

Why is the function name a pointer to a Go string rather than simply a
Go string?

There have been CLs for shared libraries.  Let's support that clearly
here: the PC values should all be relative to the load address of the
module.  The load address of a statically linked executable is 0.

OK. Does that require any changes today?

 

Your doc implies a global table of all file names used in the program,
but doesn't spell out where that is found.  Again let's make this
clear for shared libraries.  It's a per-module table, and how does the
runtime find it?

How does the runtime even find the function table? It finds the file table the same way.

 

You've got an npcdata field but no pcdata field.  How does the runtime
find the pcdata tables?  Actually I don't see why you need npcdata (or
pcdata).  Since we are defining funcdata by convention, it seems that
it would suffice to say that funcdata $3 (say) is (by convention) a
pcdata table.  That is, the value of funcdata $3 is the offset
(relative to the start of the Func structure) to a pcdata table.  Then
it would be an error to use both FUNCDATA $3 and PCDATA $3.

The Func is followed immediately in memory by npcdata int32 offsets to pcdata tables, then by an int32 padding if needed to get to a uintptr boundary, then by nfuncdata pointers to funcdata values, then by actual pc-value tables (currently, pcsp, pcfile, pcln, and then the pcdata tables, although because we record offsets for all, the order is not assumed).

FUNCDATA turn into pointers to other data symbols, so they are 8 bytes on amd64. PCDATA turn into int32 offsets to tiny tables after the Func, so they are only 4 bytes. Merging the two would waste bytes in the PCDATA case.

You say that the runtime should do a binary search in a PC-value
table.  But then you describe an encoding that stores PC deltas.  I
don't understand how to do a binary search on a table stored using
deltas.  For that matter, a binary search doesn't seem to help much
since the values are deltas also.

The binary search is in the 

    pc0 func0 pc1 func1 pc2 func2 pcEND

table of functions, to find the appropriate Func structure. Interpreting the pc-value table is a linear scan.

 

In order to do a binary search, the runtime needs to know the number
of entries in a table.  Where is that stored?  Or, if the runtime is
not in fact doing a binary search, how does it know where the end of
the table is, so that it can know that it should stop looking for a PC
value that is out of range?

The pc-value tables all cover the entire size of the func, so if, say, pc0 <= pc < pc1, so that we're using func0, any pcvalue table it references should either be missing (offset==0) or have an entry giving the value at pc. Even so, all non-missing tables are all terminated by a final 0 byte, since a 0 value delta is not useful after the first row.

Russ

[Ian Lance Taylor]

On Thu, Jul 11, 2013 at 10:08 PM, Russ Cox <r...@golang.org> wrote:
> On Fri, Jul 12, 2013 at 12:52 AM, Ian Lance Taylor <ia...@golang.org> wrote:
>>
>> On Wed, Jul 10, 2013 at 10:46 AM, Russ Cox <r...@golang.org> wrote:
>> > I started work on cleaning up the runtime symbol table so that it is
>> > less
>> > cumbersome and also more easily extensible to help with things like
>> > garbage
>> > collection metadata. Design at http://golang.org/s/go12symtab. CL in
>> > progress. Comments welcome here.
>>
>> Why is the function name a pointer to a Go string rather than simply a
>> Go string?
>>
>> There have been CLs for shared libraries. Let's support that clearly
>> here: the PC values should all be relative to the load address of the
>> module. The load address of a statically linked executable is 0.
>
>
> OK. Does that require any changes today?

Only to the doc.

>> You've got an npcdata field but no pcdata field. How does the runtime
>> find the pcdata tables? Actually I don't see why you need npcdata (or
>> pcdata). Since we are defining funcdata by convention, it seems that
>> it would suffice to say that funcdata $3 (say) is (by convention) a
>> pcdata table. That is, the value of funcdata $3 is the offset
>> (relative to the start of the Func structure) to a pcdata table. Then
>> it would be an error to use both FUNCDATA $3 and PCDATA $3.
>
>
> The Func is followed immediately in memory by npcdata int32 offsets to
> pcdata tables, then by an int32 padding if needed to get to a uintptr
> boundary, then by nfuncdata pointers to funcdata values, then by actual
> pc-value tables (currently, pcsp, pcfile, pcln, and then the pcdata tables,
> although because we record offsets for all, the order is not assumed).
>
> FUNCDATA turn into pointers to other data symbols, so they are 8 bytes on
> amd64. PCDATA turn into int32 offsets to tiny tables after the Func, so they
> are only 4 bytes. Merging the two would waste bytes in the PCDATA case.

OK, just needs to be explained in the doc.

>> You say that the runtime should do a binary search in a PC-value
>> table. But then you describe an encoding that stores PC deltas. I
>> don't understand how to do a binary search on a table stored using
>> deltas. For that matter, a binary search doesn't seem to help much
>> since the values are deltas also.
>
>
> The binary search is in the
>
> pc0 func0 pc1 func1 pc2 func2 pcEND
>
> table of functions, to find the appropriate Func structure. Interpreting the
> pc-value table is a linear scan.

Thanks, my confusion.

Ian

[Russ Cox]

I updated the doc to address these points.

You also asked why the tables use *string instead of string. That was just easier in the linker and perhaps a bit more compact (but perhaps not). I don't think it matters much either way.

Russ

[Nigel Tao]

On Fri, Jul 12, 2013 at 3:08 PM, Russ Cox <r...@golang.org> wrote:
> Even so, all non-missing tables are all terminated by a final 0 byte,
> since a 0 value delta is not useful after the first row.

Out of curiousity, why does the value delta-encoding start at -1, not
0, given that you have to allow a 0 value delta anyway?

[minux]

On Thu, Jul 11, 2013 at 1:46 AM, Russ Cox <r...@golang.org> wrote:

I started work on cleaning up the runtime symbol table so that it is less cumbersome and also more easily extensible to help with things like garbage collection metadata. Design at http://golang.org/s/go12symtab. CL in progress. Comments welcome here.

a general question: why not just use DWARF so that we get better DWARF pcln table

as a by product?

[Ian Lance Taylor]

I would say that DWARF is aimed more toward a compact representation
that can be expanded into lookup tables by a debugger. I think the
goal here is to produce tables that can be used directly and
efficiently without being expanded.

Ian

[minux]

it seems it has to be expanded anyway because of the delta encoding.

[Russ Cox]

The delta encoding can be interpreted directly, just like we always have (see the pcvalue function in https://codereview.appspot.com/11085043/diff/23001/src/pkg/runtime/symtab.c). DWARF cannot be interpreted directly, because of all the abstraction: you need to malloc at least a copy of the DWARF "microcode" tables in order to evaluate the real ones. 

This is at least 1000x simpler than DWARF.

Russ

[Dmitry Vyukov]

+1
This would especially help the race detector to report precise stacks.

[Dmitry Vyukov]

Looks great generally.

Why the pc-value's value is int32? It's intended to be extensible and
it's using variable length encoding, so declaring it as intptr is a
clear win (int64 won't increase binary size but will slowdown ARM).

Why pcsp/pcfile/pcln are embed in Func and not using general pcdata?
However, it does not matter too much. name/entry can be funcdata as
well... but it's probably too general...

Wrt "The new table, being a C struct, is not as compact as the current
Plan 9 symtab encoding". Can you obtain sizes of different parts of
pc/sym info?
For GC we don't want to do any unpacking/allocation. But it is fine
for crash/race reporting, this is where func/file info is needed. If
we use "element index sequences" for func/file, we may not do any
unpacking/allocation, just dump all the parts to runtime.printf.
Go binaries are fat, so any reduction in size is welcome.
Can we make go tool nm/addr2line use this new format later?

Why do we need Func.pcfile? AFAIR currently we have single file for func.

Can we store inlining info in Func.pcdata later?

I also have some concerns about consequences on GC pause. The following change:
https://codereview.appspot.com/9406046/
on the following program:
http://play.golang.org/p/c6M1jwuO8h
changed GC pause from 55ms to 359ms:
before:
gc5(1): 48+0+7 ms, 12 -> 12 MB
after:
gc5(1): 243+0+116 ms, 12 -> 12 MB

Unwinding directly affects GC pause, and it can not be easily recovered.
Do you have any thoughts on how it can affect unwinding performance?
Can we make it faster?

[Carl Shapiro]

On Mon, Jul 15, 2013 at 2:32 PM, Dmitry Vyukov <dvy...@google.com> wrote:

Unwinding directly affects GC pause, and it can not be easily recovered.
Do you have any thoughts on how it can affect unwinding performance?
Can we make it faster?

A fast unwind is possible when there is fast access to the function metadata.  The pause times in Go are unsually high.  A very commonly used scheme in systems that perform better is to store a pointer to the function metadata in the frame.

I have suggested to a few people that we store a pointer to the Func structure at the top of the stack.  This will require a small calling convention change but it will eliminate the need to binary search through a table.  Furthermore, this can eliminate the need for the table in the first place, thereby resolving the shared library issue.

[Russ Cox]

On Mon, Jul 15, 2013 at 5:32 PM, Dmitry Vyukov <dvy...@google.com> wrote:

Why the pc-value's value is int32? It's intended to be extensible and

it's using variable length encoding, so declaring it as intptr is a
clear win (int64 won't increase binary size but will slowdown ARM).

It is easy to make intptr later if that's needed. I expect the values to be small (typically indexes into funcdata tables).

 

Why pcsp/pcfile/pcln are embed in Func and not using general pcdata?
However, it does not matter too much. name/entry can be funcdata as
well... but it's probably too general...

The general things come from the PCDATA/FUNCDATA instructions. The specific things are always there.

 

Wrt "The new table, being a C struct, is not as compact as the current
Plan 9 symtab encoding". Can you obtain sizes of different parts of
pc/sym info?

I did include overall sizes in the doc. I haven't broken it down further.

 

For GC we don't want to do any unpacking/allocation. But it is fine
for crash/race reporting, this is where func/file info is needed. If
we use "element index sequences" for func/file, we may not do any
unpacking/allocation, just dump all the parts to runtime.printf.

That doesn't help runtime.Caller, which today returns file names without per-call allocations.

 

Go binaries are fat, so any reduction in size is welcome.
Can we make go tool nm/addr2line use this new format later?

Yes, that's the plan. The binaries will get smaller overall.

 

Why do we need Func.pcfile? AFAIR currently we have single file for func.

The generated init func for each package jumps around between files. Also use of //line xxx.go:123 annotations can insert any number of file names.

Can we store inlining info in Func.pcdata later?

Yes, but not for Go 1.2.

 

I also have some concerns about consequences on GC pause. The following change:
https://codereview.appspot.com/9406046/
on the following program:
http://play.golang.org/p/c6M1jwuO8h
changed GC pause from 55ms to 359ms:
before:
gc5(1): 48+0+7 ms, 12 -> 12 MB
after:
gc5(1): 243+0+116 ms, 12 -> 12 MB

Unwinding directly affects GC pause, and it can not be easily recovered.
Do you have any thoughts on how it can affect unwinding performance?
Can we make it faster?

300 ms for half a million stack frames doesn't seem so bad to me. That's only 600ns per stack frame. Carl and I have discussed ways to make stack unwinding possibly cheaper, but I am much more interested in achieving correctness (meaning precise GC) first.

This CL should not appreciably affect the time taken by unwinding. But again, this CL is about correctness. It gets line numbers right and it also fixes the preemption bugs you reported.

Russ

[Russ Cox]

Storing a Func at a known offset from the SP would eliminate the lookup from the non-leaves. It would not eliminate the lookup in the leaves, since a profiling signal might arrive before the frame was initialized, and so it would not eliminate the need for the table.

Russ

[Dmitry Vyukov]

To find the frame boundaries you need pcsp table...

[Carl Shapiro]

On Mon, Jul 15, 2013 at 3:50 PM, Russ Cox <r...@golang.org> wrote:

Storing a Func at a known offset from the SP would eliminate the lookup from the non-leaves. It would not eliminate the lookup in the leaves, since a profiling signal might arrive before the frame was initialized, and so it would not eliminate the need for the table.

This is not strictly true.  In such an implementation, when a signal arrives the function at the top most state will have either stored a pointer at the top of the stack or it is in the process of storing the pointer at the top of the stack.  The operations to adjust the stack pointer and write a value of the top of the stack are short (about a couple of instructions), will not appear in any other context, and can be easily pattern matched.

[Carl Shapiro]

On Mon, Jul 15, 2013 at 3:50 PM, Dmitry Vyukov <dvy...@google.com> wrote:

To find the frame boundaries you need pcsp table...

I actually do not know what a pcsp table is.  It is not explained in the design document.

I am also not sure what boundary you are referring to.  Do you mean the frame size?  The pointer map will tell you how many values and what offsets need to be scanned irrespective of the frame size.

[Russ Cox]

The pcsp table maps PC to delta-SP since the function entry. There are a few places in Go functions (notably in the implementation of go and defer statements) where it changes, but mostly it is either 0 or the frame size. If we eliminate the few cases that are not, then we could use the "0 or frame size" assumption more directly. We've been doing that already but it's wrong sometimes and now that the stack trace routines are pickier we're starting to see where those arise in practice.

Russ

[Carl Shapiro]

On Mon, Jul 15, 2013 at 4:18 PM, Russ Cox <r...@golang.org> wrote:

The pcsp table maps PC to delta-SP since the function entry. There are a few places in Go functions (notably in the implementation of go and defer statements) where it changes, but mostly it is either 0 or the frame size. If we eliminate the few cases that are not, then we could use the "0 or frame size" assumption more directly. We've been doing that already but it's wrong sometimes and now that the stack trace routines are pickier we're starting to see where those arise in practice.

Thanks for the clarification.  It would also be helpful to add a description of what pcsp is to the design document.

[Carl Shapiro]

On Mon, Jul 15, 2013 at 3:50 PM, Dmitry Vyukov <dvy...@google.com> wrote:

To find the frame boundaries you need pcsp table...

In light of what the pcsp table is, there should be no issue retrieving this information when an entirely local approach to mapping to a Func structure is used.  I would be interested in knowing of any special cases that might indicate the contrary.

[Dmitry Vyukov]

This may probably have some issues with nosplit functions. Frame of
each function will be increased by uintptr (including all assembly and
nosplit functions), this can make some stack traces not fitting into
128 bytes. Not that it's unsolvable.

[Russ Cox]

On Tue, Jul 16, 2013 at 1:36 AM, Dmitry Vyukov <dvy...@google.com> wrote:

This may probably have some issues with nosplit functions. Frame of

each function will be increased by uintptr (including all assembly and
nosplit functions), this can make some stack traces not fitting into
128 bytes. Not that it's unsolvable.

I did an experiment adding a word to every stack frame a few weeks ago. The only significant issue was that the hash map routines were using a bit too much stack, and I removed a few words there. I don't anticipate space problems.

Russ

[Russ Cox]

A few more CLs are on the way related to the new symbol table. I've tweaked where it sits in memory so that all the relevant pieces (including the two big tables and the many Func structs and the strings) are collected into a single data symbol, and all offsets are relative to the start of that symbol. This means that a debugger can read that one symbol and have a blob that can be interpreted by itself. I've also removed one of the two legacy tables.

In order to ease the transition, this symbol is named pclntab; that is, it replaces the current whole-program Plan 9 pc-line table. It's not entirely a misnomer, because it does contain primarily a pc-line table; it just happens to have a little more than that too.

Putting everything in one symbol means that both libmach and debug/gosym can still treat the metadata as a single blob to load.

There are three CLs on their way:

11485044 libmach: update for Go 1.2 pcln table

11495043 debug/gosym: update for Go 1.2 pcln table

11494043  cmd/ld, runtime: use new contiguous pcln table

The first two update libmach and debug/gosym to be able to read the new table, since it replaces the old pclntab. The final CL actually starts using it.

After these CLs, all that will remain for the transition is to move the Plan 9 symtab into unmapped memory, and then the footprint of a Go binary should actually be a little smaller than a few weeks ago.

Russ

[Dave Cheney]

Apart from a small issue in traceback_arm.c, everything looks good on ARM.

[Dave Cheney]

Also, i'm seeing a lot of strange behaviour during panics around nil
ptrs on arm, this might be related to the missing traceback_arm.c
file. I don't think it is a blocker on this set of changes, but might
need attention afterwards.

[Carl Shapiro]

On Wed, Jul 17, 2013 at 9:22 PM, Russ Cox <r...@golang.org> wrote:

After these CLs, all that will remain for the transition is to move the Plan 9 symtab into unmapped memory, and then the footprint of a Go binary should actually be a little smaller than a few weeks ago.

Are there be changes to follow that provide an interface for and example of how to use the new funcdata operations?

[Russ Cox]

On Thu, Jul 18, 2013 at 2:04 PM, Carl Shapiro <csha...@google.com> wrote:

Are there be changes to follow that provide an interface for and example of how to use the new funcdata operations?

Sure. CL 11406044 moves the LOCALS, PTRS, and NPTRS instructions into a new data structure known only to the runtime and the compilers. The linker is officially out of the loop.

Russ