Read inlining info in NVIDIA extended line map

  --Apple-Mail=_EB22CA76-EC65-45E3-8A9F-E0830BF864E9
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8

As of CUDA 11.2, NVIDIA added extensions to the line map section
of CUDA binaries to represent inlined functions. These extensions
include

 - two new fields in a line table row to represent inline=20
   information: context, and functionname,

 - two new DWARF extended opcodes: DW_LNE_inlined_call,=20
   DW_LNE_set_function_name,

 - an additional word in the line table header that indicates=20
   the offset in the .debug_str function where the function=20
   names for this line table begin, and

 - two new functions in the libdw API: dwarf_linecontext and=20
   dwarf_linefunctionname, which return the new line table fields.

A line table row for an inlined function contains a non-zero
"context" value. The =E2=80=9Ccontext=E2=80=9D field indicates the index =
of the
line table row that serves as the call site for an inlined
context.

The "functionname" field in a line table row is only meaningful
if the "context" field of the row is non-zero. A meaningful
"functionname" field contains an index into the .debug_str
section relative to the base offset established in the line table
header; the position in the .debug_str section indicates the name
of the inlined function.

These extensions resemble the proposed DWARF extensions
(http://dwarfstd.org/ShowIssue.php?issue=3D140906.1) by Cary
Coutant, but are not identical.

This patch adds integrates support for handling NVIDIA's extended
line maps into elfutil's libdw library and the readelf command
line utility.

Since this support is a non-standard extension to DWARF, all code
that implements the extensions is implemented between markers =20
/* Begin NVIDIA_LINEMAP_INLINING_EXTENSIONS */ and=20
/* End NVIDIA_LINEMAP_INLINING_EXTENSIONS */.

The definition below

 #define NVIDIA_LINEMAP_INLINING_EXTENSIONS 1

is added to elfutils/version.h, which enables a client of elfutils=20
to test whether the NVIDIA line map extensions are present.=20

Note: The support for NVIDIA extended line maps adds two integer
fields (context and functionname) to struct Dwarf_Line_s, which
makes the structure about 30% larger.

The patch includes a binary testfile_nvidia_linemap.bz2 that
contains an NVIDIA extended linemap along with two tests that
read the line map.

 - A test script run-nvidia-extended-linemap-readelf.sh=20
   checks the output of readelf on the new test binary to=20
   validate its dump of the line op codes containing context=20
   and functionname entries.

 - A test program tests/nvidia_extended_linemap_libdw.c reads=20
   the extended line map with dwarf_next_lines and dumps the=20
   context and functionname fields of the line map where they=20
   are relevant, i.e. the value of context is non-zero. A test=20
   script run-nvidia-extended-linemap-libdw.sh runs this test=20
   and validates its output.

A patch with the new functionality described above is attached.
--
John Mellor-Crummey		Professor
Dept of Computer Science	Rice University
email: johnmc@rice.edu		phone: 713-348-5179

Signed-off-by: John M Mellor-Crummey <johnmc@rice.edu>
---
 ChangeLog                                    |   4 +
 config/version.h.in                          |   4 +
 libdw/Makefile.am                            |   1 +
 libdw/dwarf.h                                |   4 +
 libdw/dwarf_getsrclines.c                    |  52 ++++++-
 libdw/dwarf_linecontext.c                    |  47 ++++++
 libdw/dwarf_linefunctionname.c               |  47 ++++++
 libdw/libdw.h                                |  12 ++
 libdw/libdw.map                              |   2 +
 libdw/libdwP.h                               |   4 +
 src/readelf.c                                |  46 ++++++
 tests/Makefile.am                            |   3 +
 tests/nvidia_extended_linemap_libdw.c        | 153 +++++++++++++++++++
 tests/run-nvidia-extended-linemap-libdw.sh   |  41 +++++
 tests/run-nvidia-extended-linemap-readelf.sh | 114 ++++++++++++++
 tests/testfile_nvidia_linemap.bz2            | Bin 0 -> 2365 bytes
 16 files changed, 533 insertions(+), 1 deletion(-)
 create mode 100644 libdw/dwarf_linecontext.c
 create mode 100644 libdw/dwarf_linefunctionname.c
 create mode 100644 tests/nvidia_extended_linemap_libdw.c
 create mode 100755 tests/run-nvidia-extended-linemap-libdw.sh
 create mode 100755 tests/run-nvidia-extended-linemap-readelf.sh
 create mode 100644 tests/testfile_nvidia_linemap.bz2

GIT binary patch
literal 2365
zcmV-D3BvY5T4*^jL0KkKSq)>6PXG%lfB*mg|L^|i|Nqm@%YXm>|9|bF;0gptplMZb
z+z@oxek$MzA3=Le*sZ4QFf%t<T`QmfC=8JrjZZ;6N&1r>rk<(lJVeQ+CXEdl4WbN<
z003wJ222QOG|<yP27r2i7=%qUF)E&u)ENvDAT-IfH1#ls1k*qRBM``F02*iphK(5w
z0iZMnn3`cS28K;E(-R<Rp^>4JO$`Q^Ookzl7$XsrKr|R55rS!>07C#HCYdx~lTt}N
z38AT?G}BEz6Gx~S0Av6%G&D2~0017KWB>pLfCE4P28bFNG}BB>fu@E=hD|gy8euXR
zhCpD9Moj?FV2nlyri=j$0F0Vs(Sk(*1jt54hEjf{$kR~t(lp+b(<Xq(15E~jrk+q9
zqfHEkhL2EaGypVuhEG${Y^Ig~UxRRaEJ=4<WbwApGblg|mU#~?l+vLlQd5iQ9&V+j
zS6ewn1h^@)ItC<x_}SoALul#d(o~$6NV>p@T+?W=XfGcS<G97?76|H0A)#7}m4%D$
zl){2Ki-}g@dcI8OD<Vp$5F$Dwp_?`yv%mpFk<jL&xO6e{JpCKEpp6b1j2Z}5C7?OT
zNdc){{}xteZZ8SK01`yC9fd$h%1NwjvPDwV5G@H8Y@Ir;t|^E--yG)4tYPJ$Bwir|
zH1>&L5UbU0?35a#xs8L!r-U)TF1&F!__dKhBSQp!#+wj$%m9uMNR-G!K_M%dqZ6H;
zp6s^6LtA42tC>wzChpmB6xue3L}H1b<ePIc!X-KZgNKWWjf}zs{L8PiMA9T+r2yER
z#{&BqPz<p_ArB>!5<t@L_Le!M&YW<R2F0_EGcdiNHR-gzj<%``cqK9d;xR!J#XuVZ
z#uQ+Vm%M^RWdw*;1F`tQL`%eh(`q8EYatRzKX#pwocuB~oIdJ;zO|iCBg6duFXI9W
zFo8h=453TaHX|=AFfek2gOCjU>}H>R`jsiDJG5(on{65{32{>NRWayf(z@`1E`3y{
zl~q+m1VF!oZ8R<b+<2JonKJ294HBq!J2I&?M#u~{(5z2H)k=(oRtaYvtOB+r#Y3k;
zC7>)6HEO=U!CjHKL=i#lMp8Ugu|_5N>}!I}P<2H9jm?W|S`&9IL7fYl&9&Tajy_+U
zco?v~b4#nESGuIQ`WznwnVcDcvISVY32sJ@;zMlYbDE<_<YnWEy^6s~Akr65*7_x|
z=cGhyIbiK>Ci5dU5WJ7A^d;1t&%hFdjAKBEu4x*h0Wpf#4;~SW1h|NlaA3mRdio<%
zGpjR0sd)xQTDw99P<XZM0^$G-hw)*Dp{>Zxme&R|Hv~Sh-6jvSs*KAN5Z798xL3$;
z9FnOe=%tyNnVINO5fKqInrWo~+BvML@!#9pbEQiVVg!noOb1AemW7{KqN380XnRY1
z6{JWGivo+!W+h-4Y3?|6%5MW0g;{{xNZkBE)Ja^Fk<DfLOUuiGU|e;7DEHy&FTyC9
zw|@ElJs$fff7cGbVgpeTho{*g*|kHkokHMWV^Yqw$$NH5G4T8(xzbCN4SD<>-a=Dk
zS=wXMwrouPmhh`==%Vz67fDh|NyHUm+g!3v8g!M10QsMnf&`Qk+^IDn5Z;=Pj1~a5
zH&O@Dx5OLVo51JwnP)1TKRjw}r3i|mBC4vaL`EVgtVLB-h={~hRw5{<f-0)2s-h$1
z$kRYHs;aT68eDmjY!vQor*T(Q=XlE8YdDda9r-uO;Nkp-Ugd{*L9r+xqg-(@M@3W;
zDC8t_qJnLFArXM1;;4pCGBtyOBt;Vyh&;)~05=1ik9*E_DQ%T?tnGw&zTKOqIw1aW
zwnT<AmO#}`*(GvbI`=jT;Lk#Z2*>4IBBKH!Y!!n8(v!LfgK&f~C6?3$*akx+tT+~`
zQ&mt=O;aXEkO2drE@PBN-FLcr75GzJg+W0&@WT#_C_bl!Qmkb@<B?RrV`ti5ZFR$g
zCFUGX8|<!SUR_d9jWnPq1vMrXrl7eh0n1p~b!yuiSb4n8hoLl*Q@+TM%^dmj%_L)u
zq^FIRTb>|P;)P6=sVtW;lDLBoVZy4hQ58{8Mk=bRAgk!m5)flbxZQ3X+O!1lp@o(X
z+SMs00cDV_Ba9V5-r^D{G#CoWD#*P+kpPw8M6zZih>HSCTG3%@-dffX$!=A)MiVAu
zjx<?QS4~dMn;GkCB4sZx)5Nc`R7?8Au(ES4i1RJQZ7S?i^_SMjldfy0yGT+FA7z3G
z0!l4O$T4ul)*&IWS1}0$2oXpi(QC!X(G~F16;y3)yeVz>63v@7iqgAu&330$@?#DN
z6NEditP%rEZN^JA8Y?;mfGz=a@`QwllSz_F08}3)mY~3kP&Ps_ZMmM0c!-Q49`B4#
zcb+A-d|*WH1GzczT?Nf5cK!b{<D9hikOSD7ElCiJaX_p>F_9@3pgiJJ3pWL7W>gA4
zGiDm}BpCOl$LYMDSzZy{NiuK^^pSeEbtH;V1z?N>)ah6m1~G-bIK(87XT3qK5)l9x
z40mqd)(~-IuM57Vl3(pymwh1aNiBL67qdt&_v%@YFH69NQHiccgh3-{yq!_dYu|g@
z=@*8TomE+8s9{vLJ*R@(ZQtwkpx|qDhM_ZY0%9&mHga|(YR7p3b|5p@TdqM_Eg+-s
zLL!iMrX_|_A~gsaL?&2rselIk+iLV;pl>wLF0}Gs9l=WS)!Yq_pXg3`#*M}(Q-g2@
z1`~`<3%;7Tx%_a8V<Tz{&?L4+0hA(=M#z~Exmja+;7A%d0SX`pcKO0JV}Q^=-q$Wo
z!EI97Oj*lC>yAZl!6_V$UBw`=4iMR4eXP@L*K7((7gR*|jKtwYBx*=67Nb8((Hm10
zTeLcBi18~G1vRWQDD}RujxL{FF1l1;K}-aDVK9GC32vRua)mg)2*#^e6+Jh`NDdNs
zn#lrvt*a9C4j5hys&rMN&Pg;`(RCy8V3aTH7)tkQALtO<?Dk*^_65{eWYalsZm)fV
z&N@wqCZ`3Jqs$kY7Wv)oIMqYU>K1(%p_BZdf^uW4^<3GX)mdW&zZuC%MyCDnGxGg7
j?<uY9gnA3bP{k@Mli^~Jj?A#k|M<I-DZ+$+YaEJrhXo~*

literal 0
HcmV?d00001
  

My previous patch submission seems to have been overlooked as buildbot issues consumed several days this week. However, discussion in the mailing list now seems to have moved on beyond my submission and I would like my patch considered. Here, I echo my previous submission, except I improved my submission by including the prefix [PATCH] in the subject and I included the patch in the message body rather than as an attachment.

Regarding the DWARF proposal by Cary Coutant for two-level linemaps: I now believe that NVIDIA?s implementation is consistent with that proposal although NVIDIA uses a DWARF extended opcode for inlined calls whereas Cary?s proposal uses DW_LNS_inlined_call (a standard opcode), NVIDIA?s implementation uses DW_LNE_inlined_call (an extended opcode).

A note about the source code for the test case reading the extended linemap entries using libdw: this code was copied from another test that used dwarf_next_lines and extended with code that reads the new context and functionname fields of a line table entry.
--
John Mellor-Crummey		Professor
Dept of Computer Science	Rice University
email: johnmc@rice.edu		phone: 713-348-5179

> On Sep 5, 2021, at 7:07 PM, John Mellor-Crummey <johnmc@rice.edu> wrote:
> 
> As of CUDA 11.2, NVIDIA added extensions to the line map section
> of CUDA binaries to represent inlined functions. These extensions
> include
> 
> - two new fields in a line table row to represent inline 
>   information: context, and functionname,
> 
> - two new DWARF extended opcodes: DW_LNE_inlined_call, 
>   DW_LNE_set_function_name,
> 
> - an additional word in the line table header that indicates 
>   the offset in the .debug_str function where the function 
>   names for this line table begin, and
> 
> - two new functions in the libdw API: dwarf_linecontext and 
>   dwarf_linefunctionname, which return the new line table fields.
> 
> A line table row for an inlined function contains a non-zero
> "context" value. The ?context? field indicates the index of the
> line table row that serves as the call site for an inlined
> context.
> 
> The "functionname" field in a line table row is only meaningful
> if the "context" field of the row is non-zero. A meaningful
> "functionname" field contains an index into the .debug_str
> section relative to the base offset established in the line table
> header; the position in the .debug_str section indicates the name
> of the inlined function.
> 
> These extensions resemble the proposed DWARF extensions
> (http://dwarfstd.org/ShowIssue.php?issue=140906.1) by Cary
> Coutant, but are not identical.
> 
> This patch adds integrates support for handling NVIDIA's extended
> line maps into elfutil's libdw library and the readelf command
> line utility.
> 
> Since this support is a non-standard extension to DWARF, all code
> that implements the extensions is implemented between markers  
> /* Begin NVIDIA_LINEMAP_INLINING_EXTENSIONS */ and 
> /* End NVIDIA_LINEMAP_INLINING_EXTENSIONS */.
> 
> The definition below
> 
> #define NVIDIA_LINEMAP_INLINING_EXTENSIONS 1
> 
> is added to elfutils/version.h, which enables a client of elfutils 
> to test whether the NVIDIA line map extensions are present. 
> 
> Note: The support for NVIDIA extended line maps adds two integer
> fields (context and functionname) to struct Dwarf_Line_s, which
> makes the structure about 30% larger.
> 
> The patch includes a binary testfile_nvidia_linemap.bz2 that
> contains an NVIDIA extended linemap along with two tests that
> read the line map.
> 
> - A test script run-nvidia-extended-linemap-readelf.sh 
>   checks the output of readelf on the new test binary to 
>   validate its dump of the line op codes containing context 
>   and functionname entries.
> 
> - A test program tests/nvidia_extended_linemap_libdw.c reads 
>   the extended line map with dwarf_next_lines and dumps the 
>   context and functionname fields of the line map where they 
>   are relevant, i.e. the value of context is non-zero. A test 
>   script run-nvidia-extended-linemap-libdw.sh runs this test 
>   and validates its output.
> 
> A patch with the new functionality described above is attached.
> --
> John Mellor-Crummey		Professor
> Dept of Computer Science	Rice University
> email: johnmc@rice.edu		phone: 713-348-5179
  

Hi John,

On Fri, 2021-09-10 at 10:49 -0500, John Mellor-Crummey via Elfutils-
devel wrote:
> My previous patch submission seems to have been overlooked as
> buildbot issues consumed several days this week. However, discussion
> in the mailing list now seems to have moved on beyond my submission
> and I would like my patch considered. Here, I echo my previous
> submission, except I improved my submission by including the prefix
> [PATCH] in the subject and I included the patch in the message body
> rather than as an attachment.

Sorry for the buildbot noise, that was indeed a little painful. But a
buildbot that randomly fails is not much fun, so it took highest
priority to get it back to green.

Your submission is really nice, having extensive documentation, all
features implemented, a testcase. Well done.

There are however some concerns outside your control. It is somewhat
disappointing NVIDIA didn't document this themselves, or tried to
standardize this. You seems to have a good grasp of what was intended
though. We have to be careful not to extend the api in a way that makes
a better standard/implementation impossible. And the way we implemented
Dwarf_Lines isn't ideal, so this extension shows we should maybe change
it to be more efficient/compact. But maybe we can do that after adding
the extension, we should however have a plan.

> Regarding the DWARF proposal by Cary Coutant for two-level linemaps:
> I now believe that NVIDIA?s implementation is consistent with that
> proposal although NVIDIA uses a DWARF extended opcode for inlined
> calls whereas Cary?s proposal uses DW_LNS_inlined_call (a standard
> opcode), NVIDIA?s implementation uses DW_LNE_inlined_call (an
> extended opcode).

The naming is one of the concerns. It would be better to use a name
like DW_LNE_NVIDIA_inlined_call and DW_LNE_NVIDIA_set_function_name to
show they are vendor extensions and don't clash with possible future
standard opcode names.

That it mimics the two-level linemaps proposal is a good thing. But
lets make sure that the new accessor functions, dwarf_linecontext and
dwarf_linefunctionname, are generic enough that they can hopefully be
reused when two-level linemaps or a similar proposal becomes a
standard.

> A note about the source code for the test case reading the extended
> linemap entries using libdw: this code was copied from another test
> that used dwarf_next_lines and extended with code that reads the new
> context and functionname fields of a line table entry.

Thanks for the test case, it makes clear how the new functionality can
be used. How was the test binary, testfile_nvidia_linemap, generated?
That should probably be documented inside the testcase.

I won't be able to review all the code right now, but here are some
high-level comments, so you know what I am thinking.

On Sep 5, 2021, at 7:07 PM, John Mellor-Crummey <johnmc@rice.edu>
> > wrote:
> > 
> > As of CUDA 11.2, NVIDIA added extensions to the line map section
> > of CUDA binaries to represent inlined functions. These extensions
> > include
> > 
> > - two new fields in a line table row to represent inline 
> >   information: context, and functionname,

We didn't design the Dwarf_Line_s very well/compact. We already have
the op_index, isa and discriminator fields which are almost never used.
This adds two more. I wonder if we can split the struct up so that the
extra fields are only used when actually used.

Maybe this can be done with a flag in Dwarf_Lines_s indicating whether
the array contains only the basic line attributes or also some extended
values. Of course this makes dwarf_getsrclines even more complex
because it then has to expand the line state struct whenever it first
sees an extended attribute. But I really like to see if we can use less
memory here. If we agree on some way to make that possible we can
implement it afterwards.

> > - two new DWARF extended opcodes: DW_LNE_inlined_call, 
> >   DW_LNE_set_function_name,

Like I said above I think these names should contain the "vendor" name
DW_LNE_NVIDIA_...

> > - an additional word in the line table header that indicates 
> >   the offset in the .debug_str function where the function 
> >   names for this line table begin, and

This is the only part I think is somewhat tricky. I believe you
implement it cleverly by checking the header_length. And your
implementation should work, but it is also the part that no other tool
understands, which means any such binary cannot really be handled by
any other tool. And I don't really understand how this works when
linking objects with such a offset into .debug_str. Normally the
.debug_str section contains strings that can be merged, but that would
disrupt the order, so I don't fully understand how the function_name
indexes are kept correct. This would have been nicer as a DWARF5
extension, where there is already a .debug_str_offsets section (but
also confusing because there is also a special .debug_line_str section
where these strings should probably point at).

> > - two new functions in the libdw API: dwarf_linecontext and 
> >   dwarf_linefunctionname, which return the new line table fields.

I think it would be nice if we could make these functions return a
Dwarf_Line * and a const char * to make them future proof in case a
standard extension encodes these differently.

Cheers,

Mark
  

Mark,

Thanks for your feedback. I am working on a new version of the patch that changes
the interface for dwarf_linecontext and dwarf_linefunctionname to return a line pointer and a character pointer so it will be future proof.

See my other comments below, e.g. about an idea for reworking the Dwarf_line_s data structure.
--
John Mellor-Crummey		Professor
Dept of Computer Science	Rice University
email: johnmc@rice.edu		phone: 713-348-5179

> On Sep 10, 2021, at 12:11 PM, Mark Wielaard <mark@klomp.org> wrote:
> 
> Hi John,
> 
> On Fri, 2021-09-10 at 10:49 -0500, John Mellor-Crummey via Elfutils-
> devel wrote:
>> My previous patch submission seems to have been overlooked as
>> buildbot issues consumed several days this week. However, discussion
>> in the mailing list now seems to have moved on beyond my submission
>> and I would like my patch considered. Here, I echo my previous
>> submission, except I improved my submission by including the prefix
>> [PATCH] in the subject and I included the patch in the message body
>> rather than as an attachment.
> 
> Sorry for the buildbot noise, that was indeed a little painful. But a
> buildbot that randomly fails is not much fun, so it took highest
> priority to get it back to green.
> 
> Your submission is really nice, having extensive documentation, all
> features implemented, a testcase. Well done.
> 
> There are however some concerns outside your control. It is somewhat
> disappointing NVIDIA didn't document this themselves, or tried to
> standardize this. You seems to have a good grasp of what was intended
> though. We have to be careful not to extend the api in a way that makes
> a better standard/implementation impossible. And the way we implemented
> Dwarf_Lines isn't ideal, so this extension shows we should maybe change
> it to be more efficient/compact. But maybe we can do that after adding
> the extension, we should however have a plan.
> 
>> Regarding the DWARF proposal by Cary Coutant for two-level linemaps:
>> I now believe that NVIDIA?s implementation is consistent with that
>> proposal although NVIDIA uses a DWARF extended opcode for inlined
>> calls whereas Cary?s proposal uses DW_LNS_inlined_call (a standard
>> opcode), NVIDIA?s implementation uses DW_LNE_inlined_call (an
>> extended opcode).
> 
> The naming is one of the concerns. It would be better to use a name
> like DW_LNE_NVIDIA_inlined_call and DW_LNE_NVIDIA_set_function_name to
> show they are vendor extensions and don't clash with possible future
> standard opcode names.

I renamed the two new DWARF extended opcodes as you suggested.

> That it mimics the two-level linemaps proposal is a good thing. But
> lets make sure that the new accessor functions, dwarf_linecontext and
> dwarf_linefunctionname, are generic enough that they can hopefully be
> reused when two-level linemaps or a similar proposal becomes a
> standard.


>> A note about the source code for the test case reading the extended
>> linemap entries using libdw: this code was copied from another test
>> that used dwarf_next_lines and extended with code that reads the new
>> context and functionname fields of a line table entry.
> 
> Thanks for the test case, it makes clear how the new functionality can
> be used. How was the test binary, testfile_nvidia_linemap, generated?
> That should probably be documented inside the testcase.

I documented how the NVIDIA binary used in the two test cases was created
by adding comments to the two test cases.

> I won't be able to review all the code right now, but here are some
> high-level comments, so you know what I am thinking.
> 
> On Sep 5, 2021, at 7:07 PM, John Mellor-Crummey <johnmc@rice.edu>
>>> wrote:
>>> 
>>> As of CUDA 11.2, NVIDIA added extensions to the line map section
>>> of CUDA binaries to represent inlined functions. These extensions
>>> include
>>> 
>>> - two new fields in a line table row to represent inline 
>>>  information: context, and functionname,
> 
> We didn't design the Dwarf_Line_s very well/compact. We already have
> the op_index, isa and discriminator fields which are almost never used.
> This adds two more. I wonder if we can split the struct up so that the
> extra fields are only used when actually used.



> Maybe this can be done with a flag in Dwarf_Lines_s indicating whether
> the array contains only the basic line attributes or also some extended
> values. Of course this makes dwarf_getsrclines even more complex
> because it then has to expand the line state struct whenever it first
> sees an extended attribute. But I really like to see if we can use less
> memory here. If we agree on some way to make that possible we can
> implement it afterwards.

Here are my thoughts about that. 

I think the type for Dwarf_Lines should be opaque rather than simply
a pointer to a Dwarf_Line_s record. The dwarf_onesrcline or routine
requires constant time random access to line records for efficiency.
Here is how I think that could be preserved.

Let the Dwarf_Line_s structure be a  union type: a small record with a bit or two that indicates the record kind, e.g.
enum dwarf_line_type { dwarf_line_compact, dwarf_line_nvidia_inline, dwarf_line_extended2, ?}. 
All the fields for the compact record would be in one structure in the union. Other structures in the union
would just contain a pointer to an out-of-band extended record that is stored elsewhere. The storage could be managed as follows:
Have a buffer to store the lines. A sequence of compact Dwarf_Line_s records begin at the front of the buffer. Any time an extended record is needed, allocate it at the end of the buffer before the previous extended record. An extended record will have both a This could accommodate extended records of various lengths. Allocations in the buffer would manage the fact that compact line records are allocated at the front and the smaller number of larger extended line records are allocated at the back. When the the next allocation would cause the cursors to cross in the middle,  the buffer is full and another buffer is needed. The Dwarf_Lines type could have a pointer to a next Dwarf_Lines structure. If there is concern that finding a line would not really be constant time if there was a huge number of lines for a file line lookup could require following an unbounded chain of pointers to a next buffer, then the buffers could be managed in a splay tree or a skip list, which would give O(log n) time lookup of a line buffer followed by a constant time indexing into the buffer.

> 
>>> - two new DWARF extended opcodes: DW_LNE_inlined_call, 
>>>  DW_LNE_set_function_name,
> 
> Like I said above I think these names should contain the "vendor" name
> DW_LNE_NVIDIA_...

Done.

> 
>>> - an additional word in the line table header that indicates 
>>>  the offset in the .debug_str function where the function 
>>>  names for this line table begin, and
> 
> This is the only part I think is somewhat tricky. I believe you
> implement it cleverly by checking the header_length.

That strategy came from NVIDIA?s implementation in cuda-gdb . They check when there
is a gap between the end of the standard header and the header length.

> And your
> implementation should work, but it is also the part that no other tool
> understands, which means any such binary cannot really be handled by
> any other tool. And I don't really understand how this works when
> linking objects with such a offset into .debug_str. Normally the
> .debug_str section contains strings that can be merged, but that would
> disrupt the order, so I don't fully understand how the function_name
> indexes are kept correct. This would have been nicer as a DWARF5
> extension, where there is already a .debug_str_offsets section (but
> also confusing because there is also a special .debug_line_str section
> where these strings should probably point at).
> 
>>> - two new functions in the libdw API: dwarf_linecontext and 
>>>  dwarf_linefunctionname, which return the new line table fields.
> 
> I think it would be nice if we could make these functions return a
> Dwarf_Line * and a const char * to make them future proof in case a
> standard extension encodes these differently.

I will work on a patch that does just this as soon as I have time.
  

[We would really like this patch in the forthcoming release]

Attached is a new version of the patch for reading inlining information encoded in an enhanced line map format used in NVIDIA GPU binaries for CUDA 11.2+.

This is an updated version of a patch first submitted on Sept. 5. A copy of the original submission email is quoted below this note. 

Here I describe just the improvements to that patch that address Mark’s concerns:

(1) all of the code for handling NVIDIA DWARF extensions is always available; there is no special configuration switch needed.
(2) all changes are bracketed by comments that mark them NVIDIA extensions
(3) the DWARF extended opcodes have been renamed with names that include NVIDIA in them
(4) the two new API functions to surface the new information have been improved to separate the interface result from the internal representation (at Mark’s request)
	(4a) the API for extracting the name of an inlined function in a DWARF line now returns a const char * instead of a string table index
	(4b) the API for extracting an inline “context” now returns a pointer to a DWARF line where the code is inlined rather than returning an unsigned int (an index into the line table that one could use to compute the pointer)
(5) there are test cases for readelf and libdw that use a binary generated by NVIDIA’s compiler. the test cases include information about how the binary was generated
--
John Mellor-Crummey		Professor
Dept of Computer Science	Rice University
email: johnmc@rice.edu		phone: 713-348-5179

Description of the first version of the patch: 

> On Sep 5, 2021, at 7:07 PM, John Mellor-Crummey <johnmc@rice.edu <mailto:johnmc@rice.edu>> wrote:
> 
> As of CUDA 11.2, NVIDIA added extensions to the line map section
> of CUDA binaries to represent inlined functions. These extensions
> include
> 
> - two new fields in a line table row to represent inline 
>   information: context, and functionname,
> 
> - two new DWARF extended opcodes: DW_LNE_inlined_call, 
>   DW_LNE_set_function_name,
> 
> - an additional word in the line table header that indicates 
>   the offset in the .debug_str function where the function 
>   names for this line table begin, and
> 
> - two new functions in the libdw API: dwarf_linecontext and 
>   dwarf_linefunctionname, which return the new line table fields.
> 
> A line table row for an inlined function contains a non-zero
> "context" value. The “context” field indicates the index of the
> line table row that serves as the call site for an inlined
> context.
> 
> The "functionname" field in a line table row is only meaningful
> if the "context" field of the row is non-zero. A meaningful
> "functionname" field contains an index into the .debug_str
> section relative to the base offset established in the line table
> header; the position in the .debug_str section indicates the name
> of the inlined function.
> 
> These extensions resemble the proposed DWARF extensions
> (http://dwarfstd.org/ShowIssue.php?issue=140906.1 <http://dwarfstd.org/ShowIssue.php?issue=140906.1>) by Cary
> Coutant, but are not identical.
> 
> This patch adds integrates support for handling NVIDIA's extended
> line maps into elfutil's libdw library and the readelf command
> line utility.
> 
> Since this support is a non-standard extension to DWARF, all code
> that implements the extensions is implemented between markers  
> /* Begin NVIDIA_LINEMAP_INLINING_EXTENSIONS */ and 
> /* End NVIDIA_LINEMAP_INLINING_EXTENSIONS */.
> 
> The definition below
> 
> #define NVIDIA_LINEMAP_INLINING_EXTENSIONS 1
> 
> is added to elfutils/version.h, which enables a client of elfutils 
> to test whether the NVIDIA line map extensions are present. 
> 
> Note: The support for NVIDIA extended line maps adds two integer
> fields (context and functionname) to struct Dwarf_Line_s, which
> makes the structure about 30% larger.
> 
> The patch includes a binary testfile_nvidia_linemap.bz2 that
> contains an NVIDIA extended linemap along with two tests that
> read the line map.
> 
> - A test script run-nvidia-extended-linemap-readelf.sh 
>   checks the output of readelf on the new test binary to 
>   validate its dump of the line op codes containing context 
>   and functionname entries.
> 
> - A test program tests/nvidia_extended_linemap_libdw.c reads 
>   the extended line map with dwarf_next_lines and dumps the 
>   context and functionname fields of the line map where they 
>   are relevant, i.e. the value of context is non-zero. A test 
>   script run-nvidia-extended-linemap-libdw.sh runs this test 
>   and validates its output.
> 
> A patch with the new functionality described above is attached.

Discussion about the first version of the patch:

> On Sep 15, 2021, at 1:25 PM, John Mellor-Crummey <johnmc@rice.edu> wrote:
> 
> Mark,
> 
> Thanks for your feedback. I am working on a new version of the patch that changes
> the interface for dwarf_linecontext and dwarf_linefunctionname to return a line pointer and a character pointer so it will be future proof.
> 
> See my other comments below, e.g. about an idea for reworking the Dwarf_line_s data structure.
> --
> John Mellor-Crummey		Professor
> Dept of Computer Science	Rice University
> email: johnmc@rice.edu <mailto:johnmc@rice.edu>		phone: 713-348-5179
> 
>> On Sep 10, 2021, at 12:11 PM, Mark Wielaard <mark@klomp.org <mailto:mark@klomp.org>> wrote:
>> 
>> Hi John,
>> 
>> On Fri, 2021-09-10 at 10:49 -0500, John Mellor-Crummey via Elfutils-
>> devel wrote:
>>> My previous patch submission seems to have been overlooked as
>>> buildbot issues consumed several days this week. However, discussion
>>> in the mailing list now seems to have moved on beyond my submission
>>> and I would like my patch considered. Here, I echo my previous
>>> submission, except I improved my submission by including the prefix
>>> [PATCH] in the subject and I included the patch in the message body
>>> rather than as an attachment.
>> 
>> Sorry for the buildbot noise, that was indeed a little painful. But a
>> buildbot that randomly fails is not much fun, so it took highest
>> priority to get it back to green.
>> 
>> Your submission is really nice, having extensive documentation, all
>> features implemented, a testcase. Well done.
>> 
>> There are however some concerns outside your control. It is somewhat
>> disappointing NVIDIA didn't document this themselves, or tried to
>> standardize this. You seems to have a good grasp of what was intended
>> though. We have to be careful not to extend the api in a way that makes
>> a better standard/implementation impossible. And the way we implemented
>> Dwarf_Lines isn't ideal, so this extension shows we should maybe change
>> it to be more efficient/compact. But maybe we can do that after adding
>> the extension, we should however have a plan.
>> 
>>> Regarding the DWARF proposal by Cary Coutant for two-level linemaps:
>>> I now believe that NVIDIA’s implementation is consistent with that
>>> proposal although NVIDIA uses a DWARF extended opcode for inlined
>>> calls whereas Cary’s proposal uses DW_LNS_inlined_call (a standard
>>> opcode), NVIDIA’s implementation uses DW_LNE_inlined_call (an
>>> extended opcode).
>> 
>> The naming is one of the concerns. It would be better to use a name
>> like DW_LNE_NVIDIA_inlined_call and DW_LNE_NVIDIA_set_function_name to
>> show they are vendor extensions and don't clash with possible future
>> standard opcode names.
> 
> I renamed the two new DWARF extended opcodes as you suggested.
> 
>> That it mimics the two-level linemaps proposal is a good thing. But
>> lets make sure that the new accessor functions, dwarf_linecontext and
>> dwarf_linefunctionname, are generic enough that they can hopefully be
>> reused when two-level linemaps or a similar proposal becomes a
>> standard.
> 
> 
>>> A note about the source code for the test case reading the extended
>>> linemap entries using libdw: this code was copied from another test
>>> that used dwarf_next_lines and extended with code that reads the new
>>> context and functionname fields of a line table entry.
>> 
>> Thanks for the test case, it makes clear how the new functionality can
>> be used. How was the test binary, testfile_nvidia_linemap, generated?
>> That should probably be documented inside the testcase.
> 
> I documented how the NVIDIA binary used in the two test cases was created
> by adding comments to the two test cases.
> 
>> I won't be able to review all the code right now, but here are some
>> high-level comments, so you know what I am thinking.
>> 
>> On Sep 5, 2021, at 7:07 PM, John Mellor-Crummey <johnmc@rice.edu <mailto:johnmc@rice.edu>>
>>>> wrote:
>>>> 
>>>> As of CUDA 11.2, NVIDIA added extensions to the line map section
>>>> of CUDA binaries to represent inlined functions. These extensions
>>>> include
>>>> 
>>>> - two new fields in a line table row to represent inline 
>>>>  information: context, and functionname,
>> 
>> We didn't design the Dwarf_Line_s very well/compact. We already have
>> the op_index, isa and discriminator fields which are almost never used.
>> This adds two more. I wonder if we can split the struct up so that the
>> extra fields are only used when actually used.
> 
> 
> 
>> Maybe this can be done with a flag in Dwarf_Lines_s indicating whether
>> the array contains only the basic line attributes or also some extended
>> values. Of course this makes dwarf_getsrclines even more complex
>> because it then has to expand the line state struct whenever it first
>> sees an extended attribute. But I really like to see if we can use less
>> memory here. If we agree on some way to make that possible we can
>> implement it afterwards.
> 
> Here are my thoughts about that. 
> 
> I think the type for Dwarf_Lines should be opaque rather than simply
> a pointer to a Dwarf_Line_s record. The dwarf_onesrcline or routine
> requires constant time random access to line records for efficiency.
> Here is how I think that could be preserved.
> 
> Let the Dwarf_Line_s structure be a  union type: a small record with a bit or two that indicates the record kind, e.g.
> enum dwarf_line_type { dwarf_line_compact, dwarf_line_nvidia_inline, dwarf_line_extended2, …}. 
> All the fields for the compact record would be in one structure in the union. Other structures in the union
> would just contain a pointer to an out-of-band extended record that is stored elsewhere. The storage could be managed as follows:
> Have a buffer to store the lines. A sequence of compact Dwarf_Line_s records begin at the front of the buffer. Any time an extended record is needed, allocate it at the end of the buffer before the previous extended record. An extended record will have both a This could accommodate extended records of various lengths. Allocations in the buffer would manage the fact that compact line records are allocated at the front and the smaller number of larger extended line records are allocated at the back. When the the next allocation would cause the cursors to cross in the middle,  the buffer is full and another buffer is needed. The Dwarf_Lines type could have a pointer to a next Dwarf_Lines structure. If there is concern that finding a line would not really be constant time if there was a huge number of lines for a file line lookup could require following an unbounded chain of pointers to a next buffer, then the buffers could be managed in a splay tree or a skip list, which would give O(log n) time lookup of a line buffer followed by a constant time indexing into the buffer.
> 
>> 
>>>> - two new DWARF extended opcodes: DW_LNE_inlined_call, 
>>>>  DW_LNE_set_function_name,
>> 
>> Like I said above I think these names should contain the "vendor" name
>> DW_LNE_NVIDIA_...
> 
> Done.
> 
>> ...
> 
>> 
>>>> - two new functions in the libdw API: dwarf_linecontext and 
>>>>  dwarf_linefunctionname, which return the new line table fields.
>> 
>> I think it would be nice if we could make these functions return a
>> Dwarf_Line * and a const char * to make them future proof in case a standard extension encodes these differently.
  

Hi,

On Thu, 2021-11-04 at 16:41 -0500, John Mellor-Crummey via Elfutils-
devel wrote:
> [We would really like this patch in the forthcoming release]
> 
> Attached is a new version of the patch for reading inlining
> information encoded in an enhanced line map format used in NVIDIA GPU
> binaries for CUDA 11.2+.

It looks like the attachment is missing. Or the mailinglist removed it
for some reason, but I also didn't see it here:
https://sourceware.org/pipermail/elfutils-devel/2021q4/004307.html

Could you resent it?

Thanks,

Mark

> This is an updated version of a patch first submitted on Sept. 5. A
> copy of the original submission email is quoted below this note. 
> 
> Here I describe just the improvements to that patch that address
> Mark’s concerns:
> 
> (1) all of the code for handling NVIDIA DWARF extensions is always
> available; there is no special configuration switch needed.
> (2) all changes are bracketed by comments that mark them NVIDIA
> extensions
> (3) the DWARF extended opcodes have been renamed with names that
> include NVIDIA in them
> (4) the two new API functions to surface the new information have
> been improved to separate the interface result from the internal
> representation (at Mark’s request)
> 	(4a) the API for extracting the name of an inlined function in
> a DWARF line now returns a const char * instead of a string table
> index
> 	(4b) the API for extracting an inline “context” now returns a
> pointer to a DWARF line where the code is inlined rather than
> returning an unsigned int (an index into the line table that one
> could use to compute the pointer)
> (5) there are test cases for readelf and libdw that use a binary
> generated by NVIDIA’s compiler. the test cases include information
> about how the binary was generated
  

Hi John,

On Thu, Nov 04, 2021 at 04:41:58PM -0500, John Mellor-Crummey via Elfutils-devel wrote:
> Here I describe just the improvements to that patch that address Mark’s concerns:
>
> (1) all of the code for handling NVIDIA DWARF extensions is always
> available; there is no special configuration switch needed.
> (2) all changes are bracketed by comments that mark them NVIDIA
> extensions
> (3) the DWARF extended opcodes have been renamed with names that
> include NVIDIA in them
> (4) the two new API functions to surface the new information have
> been improved to separate the interface result from the internal
> representation (at Mark’s request)
>      (4a) the API for extracting the name of an inlined function in a
>         DWARF line now returns a const char * instead of a string
>         table index
>      (4b) the API for extracting an inline “context” now returns a
>         pointer to a DWARF line where the code is inlined rather
>         than returning an unsigned int (an index into the line table
>         that one could use to compute the pointer)
> (5) there are test cases for readelf and libdw that use a binary
> generated by NVIDIA’s compiler. the test cases include information
> about how the binary was generated

This is really nice. I did make a few tweaks:

- Added your original overview as commit message because it contains
  all the relevant context and pointers to more information.

- Added ChangeLog and NEWS entries, mainly for my own review.

- I removed the bracketed comments, I think they cluttered the code
  and made it seem like we wanted to remove it or disable at some
  point. I think it should just be considered part of the normal code
  now.

- I removed the NVIDIA_LINEMAP_INLINING_EXTENSIONS define from
  version.h. If people want they can have a configure check for the
  new dwarf_linecontext or dwarf_linefunctionname functions or the
  DW_LNE_NVIDIA_inlined_call or DW_LNE_NVIDIA_set_function_name
  constants.

- I made dwarf_linefunctionname always return NULL on error (not
  the magic string "???", which is still used in readelf).

- Changed the header check to be exactly 4 bytes, so we are sure to be
  able to read the str offset completely (if it is smaller or larger
  we cannot handle it).

- The new dwarf_linecontext and dwarf_linefunctionname get their own
  new ELFUTILS_0.186 section in libdw.map because they are introduced
  with verion 0.186.

- The new run-nvidia-extended-linemap-libdw.sh and
  run-nvidia-extended-linemap-readelf.sh sripts and
  testfile_nvidia_linemap.bz2 testfile were added to EXTRA_DIST so
  they show up in a dist tarball.

Patch as committed attached. Hope you don't mind the cleanups.

We still want to reduce the size of the Dwarf_Line_s and struct
line_state (independent of these extensions). I opened a new bug for
that: https://sourceware.org/bugzilla/show_bug.cgi?id=28574

Thanks,

Mark
  

Mark,

Your tweaks are fine. Many thanks for accepting our patch before 186!
--
John Mellor-Crummey		Professor
Dept of Computer Science	Rice University
email: johnmc@rice.edu		phone: 713-348-5179

> On Nov 10, 2021, at 4:16 AM, Mark Wielaard <mark@klomp.org> wrote:
> 
> Hi John,
> 
> On Thu, Nov 04, 2021 at 04:41:58PM -0500, John Mellor-Crummey via Elfutils-devel wrote:
>> Here I describe just the improvements to that patch that address Mark’s concerns:
>> 
>> (1) all of the code for handling NVIDIA DWARF extensions is always
>> available; there is no special configuration switch needed.
>> (2) all changes are bracketed by comments that mark them NVIDIA
>> extensions
>> (3) the DWARF extended opcodes have been renamed with names that
>> include NVIDIA in them
>> (4) the two new API functions to surface the new information have
>> been improved to separate the interface result from the internal
>> representation (at Mark’s request)
>>     (4a) the API for extracting the name of an inlined function in a
>>        DWARF line now returns a const char * instead of a string
>>        table index
>>     (4b) the API for extracting an inline “context” now returns a
>>        pointer to a DWARF line where the code is inlined rather
>>        than returning an unsigned int (an index into the line table
>>        that one could use to compute the pointer)
>> (5) there are test cases for readelf and libdw that use a binary
>> generated by NVIDIA’s compiler. the test cases include information
>> about how the binary was generated
> 
> This is really nice. I did make a few tweaks:
> 
> - Added your original overview as commit message because it contains
>  all the relevant context and pointers to more information.
> 
> - Added ChangeLog and NEWS entries, mainly for my own review.
> 
> - I removed the bracketed comments, I think they cluttered the code
>  and made it seem like we wanted to remove it or disable at some
>  point. I think it should just be considered part of the normal code
>  now.
> 
> - I removed the NVIDIA_LINEMAP_INLINING_EXTENSIONS define from
>  version.h. If people want they can have a configure check for the
>  new dwarf_linecontext or dwarf_linefunctionname functions or the
>  DW_LNE_NVIDIA_inlined_call or DW_LNE_NVIDIA_set_function_name
>  constants.
> 
> - I made dwarf_linefunctionname always return NULL on error (not
>  the magic string "???", which is still used in readelf).
> 
> - Changed the header check to be exactly 4 bytes, so we are sure to be
>  able to read the str offset completely (if it is smaller or larger
>  we cannot handle it).
> 
> - The new dwarf_linecontext and dwarf_linefunctionname get their own
>  new ELFUTILS_0.186 section in libdw.map because they are introduced
>  with verion 0.186.
> 
> - The new run-nvidia-extended-linemap-libdw.sh and
>  run-nvidia-extended-linemap-readelf.sh sripts and
>  testfile_nvidia_linemap.bz2 testfile were added to EXTRA_DIST so
>  they show up in a dist tarball.
> 
> Patch as committed attached. Hope you don't mind the cleanups.
> 
> We still want to reduce the size of the Dwarf_Line_s and struct
> line_state (independent of these extensions). I opened a new bug for
> that: https://sourceware.org/bugzilla/show_bug.cgi?id=28574
> 
> Thanks,
> 
> Mark<0001-libdw-readelf-Read-inlining-info-in-NVIDIA-extended-.patch>