libdw/dwarf_getsrclines.c

   1 /* Return line number information of CU.
   2    Copyright (C) 2004-2010, 2013, 2014, 2015, 2016, 2018 Red Hat, Inc.
   3    This file is part of elfutils.
   4
   5    This file is free software; you can redistribute it and/or modify
   6    it under the terms of either
   7
   8      * the GNU Lesser General Public License as published by the Free
   9        Software Foundation; either version 3 of the License, or (at
  10        your option) any later version
  11
  12    or
  13
  14      * the GNU General Public License as published by the Free
  15        Software Foundation; either version 2 of the License, or (at
  16        your option) any later version
  17
  18    or both in parallel, as here.
  19
  20    elfutils is distributed in the hope that it will be useful, but
  21    WITHOUT ANY WARRANTY; without even the implied warranty of
  22    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  23    General Public License for more details.
  24
  25    You should have received copies of the GNU General Public License and
  26    the GNU Lesser General Public License along with this program.  If
  27    not, see <http://www.gnu.org/licenses/>.  */
  28
  29 #ifdef HAVE_CONFIG_H
  30 # include <config.h>
  31 #endif
  32
  33 #include <assert.h>
  34 #include <stdlib.h>
  35 #include <string.h>
  36 #include <search.h>
  37
  38 #include "dwarf.h"
  39 #include "libdwP.h"
  40
  41
  42 struct filelist
  43 {
  44   Dwarf_Fileinfo info;
  45   struct filelist *next;
  46 };
  47
  48 struct linelist
  49 {
  50   Dwarf_Line line;
  51   struct linelist *next;
  52   size_t sequence;
  53 };
  54
  55
  56 /* Compare by Dwarf_Line.addr, given pointers into an array of pointers.  */
  57 static int
  58 compare_lines (const void *a, const void *b)
  59 {
  60   struct linelist *const *p1 = a;
  61   struct linelist *const *p2 = b;
  62   struct linelist *list1 = *p1;
  63   struct linelist *list2 = *p2;
  64   Dwarf_Line *line1 = &list1->line;
  65   Dwarf_Line *line2 = &list2->line;
  66
  67   if (line1->addr != line2->addr)
  68     return (line1->addr < line2->addr) ? -1 : 1;
  69
  70   /* An end_sequence marker precedes a normal record at the same address.  */
  71   if (line1->end_sequence != line2->end_sequence)
  72     return line2->end_sequence - line1->end_sequence;
  73
  74   /* Otherwise, the linelist sequence maintains a stable sort.  */
  75   return (list1->sequence < list2->sequence) ? -1
  76     : (list1->sequence > list2->sequence) ? 1
  77     : 0;
  78 }
  79
  80 struct line_state
  81 {
  82   Dwarf_Word addr;
  83   unsigned int op_index;
  84   unsigned int file;
  85   int64_t line;
  86   unsigned int column;
  87   uint_fast8_t is_stmt;
  88   bool basic_block;
  89   bool prologue_end;
  90   bool epilogue_begin;
  91   unsigned int isa;
  92   unsigned int discriminator;
  93   struct linelist *linelist;
  94   size_t nlinelist;
  95   unsigned int end_sequence;
  96   unsigned int context;
  97   unsigned int function_name;
  98 };
  99
 100 static inline void
 101 run_advance_pc (struct line_state *state, unsigned int op_advance,
 102                 uint_fast8_t minimum_instr_len, uint_fast8_t max_ops_per_instr)
 103 {
 104   state->addr += minimum_instr_len * ((state->op_index + op_advance)
 105                                       / max_ops_per_instr);
 106   state->op_index = (state->op_index + op_advance) % max_ops_per_instr;
 107 }
 108
 109 static inline bool
 110 add_new_line (struct line_state *state, struct linelist *new_line)
 111 {
 112   /* Set the line information.  For some fields we use bitfields,
 113      so we would lose information if the encoded values are too large.
 114      Check just for paranoia, and call the data "invalid" if it
 115      violates our assumptions on reasonable limits for the values.  */
 116   new_line->next = state->linelist;
 117   new_line->sequence = state->nlinelist;
 118   state->linelist = new_line;
 119   ++(state->nlinelist);
 120
 121   /* Set the line information.  For some fields we use bitfields,
 122      so we would lose information if the encoded values are too large.
 123      Check just for paranoia, and call the data "invalid" if it
 124      violates our assumptions on reasonable limits for the values.  */
 125 #define SET(field)                                                    \
 126   do {                                                                \
 127      new_line->line.field = state->field;                             \
 128      if (unlikely (new_line->line.field != state->field))             \
 129        return true;                                                   \
 130    } while (0)
 131
 132   SET (addr);
 133   SET (op_index);
 134   SET (file);
 135   SET (line);
 136   SET (column);
 137   SET (is_stmt);
 138   SET (basic_block);
 139   SET (end_sequence);
 140   SET (prologue_end);
 141   SET (epilogue_begin);
 142   SET (isa);
 143   SET (discriminator);
 144   SET (context);
 145   SET (function_name);
 146
 147 #undef SET
 148
 149   return false;
 150 }
 151
 152 static int
 153 read_srclines (Dwarf *dbg,
 154                const unsigned char *linep, const unsigned char *lineendp,
 155                const char *comp_dir, unsigned address_size,
 156                Dwarf_Lines **linesp, Dwarf_Files **filesp)
 157 {
 158   int res = -1;
 159
 160   struct filelist *filelist = NULL;
 161   size_t nfilelist = 0;
 162   size_t ndirlist = 0;
 163
 164   /* If there are a large number of lines, files or dirs don't blow up
 165      the stack.  Stack allocate some entries, only dynamically malloc
 166      when more than MAX.  */
 167 #define MAX_STACK_ALLOC 4096
 168 #define MAX_STACK_LINES (MAX_STACK_ALLOC / 2)
 169 #define MAX_STACK_FILES (MAX_STACK_ALLOC / 4)
 170 #define MAX_STACK_DIRS  (MAX_STACK_ALLOC / 16)
 171
 172   /* Initial statement program state (except for stmt_list, see below).  */
 173   struct line_state state =
 174     {
 175       .linelist = NULL,
 176       .nlinelist = 0,
 177       .addr = 0,
 178       .op_index = 0,
 179       .file = 1,
 180       /* We only store int but want to check for overflow (see SET above).  */
 181       .line = 1,
 182       .column = 0,
 183       .basic_block = false,
 184       .prologue_end = false,
 185       .epilogue_begin = false,
 186       .isa = 0,
 187       .discriminator = 0,
 188       .context = 0,
 189       .function_name = 0
 190     };
 191
 192   /* The dirs normally go on the stack, but if there are too many
 193      we alloc them all.  Set up stack storage early, so we can check on
 194      error if we need to free them or not.  */
 195   struct dirlist
 196   {
 197     const char *dir;
 198     size_t len;
 199   };
 200   struct dirlist dirstack[MAX_STACK_DIRS];
 201   struct dirlist *dirarray = dirstack;
 202
 203   if (unlikely (linep + 4 > lineendp))
 204     {
 205     invalid_data:
 206       __libdw_seterrno (DWARF_E_INVALID_DEBUG_LINE);
 207       goto out;
 208     }
 209
 210   Dwarf_Word unit_length = read_4ubyte_unaligned_inc (dbg, linep);
 211   unsigned int length = 4;
 212   if (unlikely (unit_length == DWARF3_LENGTH_64_BIT))
 213     {
 214       if (unlikely (linep + 8 > lineendp))
 215         goto invalid_data;
 216       unit_length = read_8ubyte_unaligned_inc (dbg, linep);
 217       length = 8;
 218     }
 219
 220   /* Check whether we have enough room in the section.  */
 221   if (unlikely (unit_length > (size_t) (lineendp - linep)))
 222     goto invalid_data;
 223   lineendp = linep + unit_length;
 224
 225   /* The next element of the header is the version identifier.  */
 226   if ((size_t) (lineendp - linep) < 2)
 227     goto invalid_data;
 228   uint_fast16_t version = read_2ubyte_unaligned_inc (dbg, linep);
 229   if (unlikely (version < 2) || unlikely (version > 5))
 230     {
 231       __libdw_seterrno (DWARF_E_VERSION);
 232       goto out;
 233     }
 234
 235   /* DWARF5 explicitly lists address and segment_selector sizes.  */
 236   if (version >= 5)
 237     {
 238       if ((size_t) (lineendp - linep) < 2)
 239         goto invalid_data;
 240       size_t line_address_size = *linep++;
 241       size_t segment_selector_size = *linep++;
 242       if (line_address_size != address_size || segment_selector_size != 0)
 243         goto invalid_data;
 244     }
 245
 246   /* Next comes the header length.  */
 247   Dwarf_Word header_length;
 248   if (length == 4)
 249     {
 250       if ((size_t) (lineendp - linep) < 4)
 251         goto invalid_data;
 252       header_length = read_4ubyte_unaligned_inc (dbg, linep);
 253     }
 254   else
 255     {
 256       if ((size_t) (lineendp - linep) < 8)
 257         goto invalid_data;
 258       header_length = read_8ubyte_unaligned_inc (dbg, linep);
 259     }
 260   const unsigned char *header_start = linep;
 261
 262   /* Next the minimum instruction length.  */
 263   uint_fast8_t minimum_instr_len = *linep++;
 264
 265   /* Next the maximum operations per instruction, in version 4 format.  */
 266   uint_fast8_t max_ops_per_instr = 1;
 267   if (version >= 4)
 268     {
 269       if (unlikely ((size_t) (lineendp - linep) < 1))
 270         goto invalid_data;
 271       max_ops_per_instr = *linep++;
 272       if (unlikely (max_ops_per_instr == 0))
 273         goto invalid_data;
 274     }
 275
 276   /* 4 more bytes, is_stmt, line_base, line_range and opcode_base.  */
 277   if ((size_t) (lineendp - linep) < 4)
 278     goto invalid_data;
 279
 280   /* Then the flag determining the default value of the is_stmt
 281      register.  */
 282   uint_fast8_t default_is_stmt = *linep++;
 283
 284   /* Now the line base.  */
 285   int_fast8_t line_base = (int8_t) *linep++;
 286
 287   /* And the line range.  */
 288   uint_fast8_t line_range = *linep++;
 289
 290   /* The opcode base.  */
 291   uint_fast8_t opcode_base = *linep++;
 292
 293   /* Remember array with the standard opcode length (-1 to account for
 294      the opcode with value zero not being mentioned).  */
 295   const uint8_t *standard_opcode_lengths = linep - 1;
 296   if (unlikely (lineendp - linep < opcode_base - 1))
 297     goto invalid_data;
 298   linep += opcode_base - 1;
 299
 300   /* To read DWARF5 dir and file lists we need to know the forms.  For
 301      now we skip everything, except the DW_LNCT_path and
 302      DW_LNCT_directory_index.  */
 303   uint16_t forms[256];
 304   unsigned char nforms = 0;
 305   unsigned char form_path = -1; /* Which forms is DW_LNCT_path.  */
 306   unsigned char form_idx = -1;  /* And which is DW_LNCT_directory_index.  */
 307
 308   /* To read/skip form data.  */
 309   Dwarf_CU fake_cu = {
 310     .dbg = dbg,
 311     .sec_idx = IDX_debug_line,
 312     .version = 5,
 313     .offset_size = length,
 314     .address_size = address_size,
 315     .startp = (void *) linep,
 316     .endp = (void *) lineendp,
 317   };
 318
 319   /* First count the entries.  */
 320   size_t ndirs = 0;
 321   if (version < 5)
 322     {
 323       const unsigned char *dirp = linep;
 324       while (dirp < lineendp && *dirp != 0)
 325         {
 326           uint8_t *endp = memchr (dirp, '\0', lineendp - dirp);
 327           if (endp == NULL)
 328             goto invalid_data;
 329           ++ndirs;
 330           dirp = endp + 1;
 331         }
 332       if (dirp >= lineendp || *dirp != '\0')
 333         goto invalid_data;
 334       ndirs = ndirs + 1; /* There is always the "unknown" dir.  */
 335     }
 336   else
 337     {
 338       if ((size_t) (lineendp - linep) < 1)
 339         goto invalid_data;
 340       nforms = *linep++;
 341       for (int i = 0; i < nforms; i++)
 342         {
 343           uint16_t desc, form;
 344           if ((size_t) (lineendp - linep) < 1)
 345             goto invalid_data;
 346           get_uleb128 (desc, linep, lineendp);
 347           if ((size_t) (lineendp - linep) < 1)
 348             goto invalid_data;
 349           get_uleb128 (form, linep, lineendp);
 350
 351           if (! libdw_valid_user_form (form))
 352             goto invalid_data;
 353
 354           forms[i] = form;
 355           if (desc == DW_LNCT_path)
 356             form_path = i;
 357         }
 358
 359       if (nforms > 0 && form_path == (unsigned char) -1)
 360         goto invalid_data;
 361
 362       if ((size_t) (lineendp - linep) < 1)
 363         goto invalid_data;
 364       get_uleb128 (ndirs, linep, lineendp);
 365
 366       if (nforms == 0 && ndirs != 0)
 367         goto invalid_data;
 368
 369       /* Assume there is at least 1 byte needed per form to describe
 370          the directory.  Filters out insanely large ndirs.  */
 371       if (nforms != 0 && ndirs > (size_t) (lineendp - linep) / nforms)
 372         goto invalid_data;
 373     }
 374
 375   /* Arrange the list in array form.  */
 376   ndirlist = ndirs;
 377   if (ndirlist >= MAX_STACK_DIRS)
 378     {
 379       if (ndirlist > SIZE_MAX / sizeof (*dirarray))
 380         goto no_mem;
 381       dirarray = malloc (ndirlist * sizeof (*dirarray));
 382       if (unlikely (dirarray == NULL))
 383         {
 384         no_mem:
 385           __libdw_seterrno (DWARF_E_NOMEM);
 386           goto out;
 387         }
 388     }
 389
 390   /* Entry zero is implicit for older versions, but explicit for 5+.  */
 391   struct dirlist comp_dir_elem;
 392   if (version < 5)
 393     {
 394       /* First comes the list of directories.  Add the compilation
 395          directory first since the index zero is used for it.  */
 396       comp_dir_elem.dir = comp_dir;
 397       comp_dir_elem.len = comp_dir ? strlen (comp_dir) : 0,
 398       dirarray[0] = comp_dir_elem;
 399       for (unsigned int n = 1; n < ndirlist; n++)
 400         {
 401           dirarray[n].dir = (char *) linep;
 402           uint8_t *endp = memchr (linep, '\0', lineendp - linep);
 403           assert (endp != NULL); // Checked above when calculating ndirlist.
 404           dirarray[n].len = endp - linep;
 405           linep = endp + 1;
 406         }
 407       /* Skip the final NUL byte.  */
 408       assert (*linep == '\0'); // Checked above when calculating ndirlist.
 409       ++linep;
 410     }
 411   else
 412     {
 413       Dwarf_Attribute attr;
 414       attr.code = DW_AT_name;
 415       attr.cu = &fake_cu;
 416       for (unsigned int n = 0; n < ndirlist; n++)
 417         {
 418           const char *dir = NULL;
 419           for (unsigned char m = 0; m < nforms; m++)
 420             {
 421               if (m == form_path)
 422                 {
 423                   attr.form = forms[m];
 424                   attr.valp = (void *) linep;
 425                   dir = dwarf_formstring (&attr);
 426                 }
 427
 428               size_t len = __libdw_form_val_len (&fake_cu, forms[m], linep);
 429               if ((size_t) (lineendp - linep) < len)
 430                 goto invalid_data;
 431
 432               linep += len;
 433             }
 434
 435           if (dir == NULL)
 436             goto invalid_data;
 437
 438           dirarray[n].dir = dir;
 439           dirarray[n].len = strlen (dir);
 440         }
 441     }
 442
 443   /* File index zero doesn't exist for DWARF < 5.  Files are indexed
 444      starting from 1.  But for DWARF5 they are indexed starting from
 445      zero, but the default index is still 1.  In both cases the
 446      "first" file is special and refers to the main compile unit file,
 447      equal to the DW_AT_name of the DW_TAG_compile_unit.  */
 448   struct filelist null_file =
 449     {
 450       .info =
 451       {
 452         .name = "???",
 453         .mtime = 0,
 454         .length = 0
 455       },
 456       .next = NULL
 457     };
 458   filelist = &null_file;
 459   nfilelist = 1;
 460
 461   /* Allocate memory for a new file.  For the first MAX_STACK_FILES
 462      entries just return a slot in the preallocated stack array.
 463      This is slightly complicated because in DWARF < 5 new files could
 464      be defined with DW_LNE_define_file after the normal file list was
 465      read.  */
 466   struct filelist flstack[MAX_STACK_FILES];
 467 #define NEW_FILE() ({                                                   \
 468   struct filelist *fl = (nfilelist < MAX_STACK_FILES                    \
 469                            ? &flstack[nfilelist]                        \
 470                            : malloc (sizeof (struct filelist)));        \
 471   if (unlikely (fl == NULL))                                            \
 472     goto no_mem;                                                        \
 473   ++nfilelist;                                                          \
 474   fl->next = filelist;                                                  \
 475   filelist = fl;                                                        \
 476   fl; })
 477
 478   /* Now read the files.  */
 479   if (version < 5)
 480     {
 481       if (unlikely (linep >= lineendp))
 482         goto invalid_data;
 483       while (linep < lineendp && *linep != '\0')
 484         {
 485           struct filelist *new_file = NEW_FILE ();
 486
 487           /* First comes the file name.  */
 488           char *fname = (char *) linep;
 489           uint8_t *endp = memchr (fname, '\0', lineendp - linep);
 490           if (endp == NULL)
 491             goto invalid_data;
 492           size_t fnamelen = endp - (uint8_t *) fname;
 493           linep = endp + 1;
 494
 495           /* Then the index.  */
 496           Dwarf_Word diridx;
 497           if (unlikely (linep >= lineendp))
 498             goto invalid_data;
 499           get_uleb128 (diridx, linep, lineendp);
 500           if (unlikely (diridx >= ndirlist))
 501             {
 502               __libdw_seterrno (DWARF_E_INVALID_DIR_IDX);
 503               goto out;
 504             }
 505
 506           if (*fname == '/')
 507             /* It's an absolute path.  */
 508             new_file->info.name = fname;
 509           else
 510             {
 511               new_file->info.name = libdw_alloc (dbg, char, 1,
 512                                                  dirarray[diridx].len + 1
 513                                                  + fnamelen + 1);
 514               char *cp = new_file->info.name;
 515
 516               if (dirarray[diridx].dir != NULL)
 517                 {
 518                   /* This value could be NULL in case the DW_AT_comp_dir
 519                      was not present.  We cannot do much in this case.
 520                      Just keep the file relative.  */
 521                   cp = stpcpy (cp, dirarray[diridx].dir);
 522                   *cp++ = '/';
 523                 }
 524               strcpy (cp, fname);
 525               assert (strlen (new_file->info.name)
 526                       < dirarray[diridx].len + 1 + fnamelen + 1);
 527             }
 528
 529           /* Next comes the modification time.  */
 530           if (unlikely (linep >= lineendp))
 531             goto invalid_data;
 532           get_uleb128 (new_file->info.mtime, linep, lineendp);
 533
 534           /* Finally the length of the file.  */
 535           if (unlikely (linep >= lineendp))
 536             goto invalid_data;
 537           get_uleb128 (new_file->info.length, linep, lineendp);
 538         }
 539       if (linep >= lineendp || *linep != '\0')
 540         goto invalid_data;
 541       /* Skip the final NUL byte.  */
 542       ++linep;
 543     }
 544   else
 545     {
 546       if ((size_t) (lineendp - linep) < 1)
 547         goto invalid_data;
 548       nforms = *linep++;
 549       form_path = form_idx = -1;
 550       for (int i = 0; i < nforms; i++)
 551         {
 552           uint16_t desc, form;
 553           if ((size_t) (lineendp - linep) < 1)
 554             goto invalid_data;
 555           get_uleb128 (desc, linep, lineendp);
 556           if ((size_t) (lineendp - linep) < 1)
 557             goto invalid_data;
 558           get_uleb128 (form, linep, lineendp);
 559
 560           if (! libdw_valid_user_form (form))
 561             goto invalid_data;
 562
 563           forms[i] = form;
 564           if (desc == DW_LNCT_path)
 565             form_path = i;
 566           else if (desc == DW_LNCT_directory_index)
 567             form_idx = i;
 568         }
 569
 570       if (nforms > 0 && (form_path == (unsigned char) -1
 571                          || form_idx == (unsigned char) -1))
 572         goto invalid_data;
 573
 574       size_t nfiles;
 575       get_uleb128 (nfiles, linep, lineendp);
 576
 577       if (nforms == 0 && nfiles != 0)
 578         goto invalid_data;
 579
 580       /* Assume there is at least 1 byte needed per form to describe
 581          the file.  Filters out insanely large nfiles.  */
 582       if (nforms != 0 && nfiles > (size_t) (lineendp - linep) / nforms)
 583         goto invalid_data;
 584
 585       Dwarf_Attribute attr;
 586       attr.cu = &fake_cu;
 587       for (unsigned int n = 0; n < nfiles; n++)
 588         {
 589           const char *fname = NULL;
 590           Dwarf_Word diridx = (Dwarf_Word) -1;
 591           for (unsigned char m = 0; m < nforms; m++)
 592             {
 593               if (m == form_path)
 594                 {
 595                   attr.code = DW_AT_name;
 596                   attr.form = forms[m];
 597                   attr.valp = (void *) linep;
 598                   fname = dwarf_formstring (&attr);
 599                 }
 600               else if (m == form_idx)
 601                 {
 602                   attr.code = DW_AT_decl_file; /* Close enough.  */
 603                   attr.form = forms[m];
 604                   attr.valp = (void *) linep;
 605                   if (dwarf_formudata (&attr, &diridx) != 0)
 606                     diridx = (Dwarf_Word) -1;
 607                 }
 608
 609               size_t len = __libdw_form_val_len (&fake_cu, forms[m], linep);
 610               if ((size_t) (lineendp - linep) < len)
 611                 goto invalid_data;
 612
 613               linep += len;
 614             }
 615
 616           if (fname == NULL || diridx == (Dwarf_Word) -1)
 617             goto invalid_data;
 618
 619           size_t fnamelen = strlen (fname);
 620
 621           if (unlikely (diridx >= ndirlist))
 622             {
 623               __libdw_seterrno (DWARF_E_INVALID_DIR_IDX);
 624               goto out;
 625             }
 626
 627           /* Yes, weird.  Looks like an off-by-one in the spec.  */
 628           struct filelist *new_file = n == 0 ? &null_file : NEW_FILE ();
 629
 630           /* We follow the same rules as above for DWARF < 5, even
 631              though the standard doesn't explicitly mention absolute
 632              paths and ignoring the dir index.  */
 633           if (*fname == '/')
 634             /* It's an absolute path.  */
 635             new_file->info.name = (char *) fname;
 636           else
 637             {
 638               new_file->info.name = libdw_alloc (dbg, char, 1,
 639                                                  dirarray[diridx].len + 1
 640                                                  + fnamelen + 1);
 641               char *cp = new_file->info.name;
 642
 643               /* In the DWARF >= 5 case, dir can never be NULL.  */
 644               cp = stpcpy (cp, dirarray[diridx].dir);
 645               *cp++ = '/';
 646               strcpy (cp, fname);
 647               assert (strlen (new_file->info.name)
 648                       < dirarray[diridx].len + 1 + fnamelen + 1);
 649             }
 650
 651           /* For now we just ignore the modification time and file length.  */
 652           new_file->info.mtime = 0;
 653           new_file->info.length = 0;
 654         }
 655     }
 656
 657   unsigned int debug_str_offset = 0;
 658   if (unlikely (linep == header_start + header_length - 4))
 659     {
 660       /* CUBINs contain an unsigned 4-byte offset */
 661       debug_str_offset = read_4ubyte_unaligned_inc (dbg, linep);
 662     }
 663
 664   /* Consistency check.  */
 665   if (unlikely (linep != header_start + header_length))
 666     {
 667       __libdw_seterrno (DWARF_E_INVALID_DWARF);
 668       goto out;
 669     }
 670
 671   /* We are about to process the statement program.  Most state machine
 672      registers have already been initialize above.  Just add the is_stmt
 673      default. See 6.2.2 in the v2.1 specification.  */
 674   state.is_stmt = default_is_stmt;
 675
 676   /* Apply the "operation advance" from a special opcode or
 677      DW_LNS_advance_pc (as per DWARF4 6.2.5.1).  */
 678 #define advance_pc(op_advance) \
 679   run_advance_pc (&state, op_advance, minimum_instr_len, max_ops_per_instr)
 680
 681   /* Process the instructions.  */
 682
 683   /* Adds a new line to the matrix.  For the first MAX_STACK_LINES
 684      entries just return a slot in the preallocated stack array.  */
 685   struct linelist llstack[MAX_STACK_LINES];
 686 #define NEW_LINE(end_seq)                                               \
 687   do {                                                          \
 688     struct linelist *ll = (state.nlinelist < MAX_STACK_LINES    \
 689                            ? &llstack[state.nlinelist]          \
 690                            : malloc (sizeof (struct linelist)));        \
 691     if (unlikely (ll == NULL))                                  \
 692       goto no_mem;                                              \
 693     state.end_sequence = end_seq;                               \
 694     if (unlikely (add_new_line (&state, ll)))                   \
 695       goto invalid_data;                                                \
 696   } while (0)
 697
 698   while (linep < lineendp)
 699     {
 700       unsigned int opcode;
 701       unsigned int u128;
 702       int s128;
 703
 704       /* Read the opcode.  */
 705       opcode = *linep++;
 706
 707       /* Is this a special opcode?  */
 708       if (likely (opcode >= opcode_base))
 709         {
 710           if (unlikely (line_range == 0))
 711             goto invalid_data;
 712
 713           /* Yes.  Handling this is quite easy since the opcode value
 714              is computed with
 715
 716              opcode = (desired line increment - line_base)
 717                        + (line_range * address advance) + opcode_base
 718           */
 719           int line_increment = (line_base
 720                                 + (opcode - opcode_base) % line_range);
 721
 722           /* Perform the increments.  */
 723           state.line += line_increment;
 724           advance_pc ((opcode - opcode_base) / line_range);
 725
 726           /* Add a new line with the current state machine values.  */
 727           NEW_LINE (0);
 728
 729           /* Reset the flags.  */
 730           state.basic_block = false;
 731           state.prologue_end = false;
 732           state.epilogue_begin = false;
 733           state.discriminator = 0;
 734         }
 735       else if (opcode == 0)
 736         {
 737           /* This an extended opcode.  */
 738           if (unlikely (lineendp - linep < 2))
 739             goto invalid_data;
 740
 741           /* The length.  */
 742           uint_fast8_t len = *linep++;
 743
 744           if (unlikely ((size_t) (lineendp - linep) < len))
 745             goto invalid_data;
 746
 747           /* The sub-opcode.  */
 748           opcode = *linep++;
 749
 750           switch (opcode)
 751             {
 752             case DW_LNE_end_sequence:
 753               /* Add a new line with the current state machine values.
 754                  The is the end of the sequence.  */
 755               NEW_LINE (1);
 756
 757               /* Reset the registers.  */
 758               state.addr = 0;
 759               state.op_index = 0;
 760               state.file = 1;
 761               state.line = 1;
 762               state.column = 0;
 763               state.is_stmt = default_is_stmt;
 764               state.basic_block = false;
 765               state.prologue_end = false;
 766               state.epilogue_begin = false;
 767               state.isa = 0;
 768               state.discriminator = 0;
 769               state.context = 0;
 770               state.function_name = 0;
 771               break;
 772
 773             case DW_LNE_set_address:
 774               /* The value is an address.  The size is defined as
 775                  appropriate for the target machine.  We use the
 776                  address size field from the CU header.  */
 777               state.op_index = 0;
 778               if (unlikely (lineendp - linep < (uint8_t) address_size))
 779                 goto invalid_data;
 780               if (__libdw_read_address_inc (dbg, IDX_debug_line, &linep,
 781                                             address_size, &state.addr))
 782                 goto out;
 783               break;
 784
 785             case DW_LNE_define_file:
 786               {
 787                 char *fname = (char *) linep;
 788                 uint8_t *endp = memchr (linep, '\0', lineendp - linep);
 789                 if (endp == NULL)
 790                   goto invalid_data;
 791                 size_t fnamelen = endp - linep;
 792                 linep = endp + 1;
 793
 794                 unsigned int diridx;
 795                 if (unlikely (linep >= lineendp))
 796                   goto invalid_data;
 797                 get_uleb128 (diridx, linep, lineendp);
 798                 if (unlikely (diridx >= ndirlist))
 799                   {
 800                     __libdw_seterrno (DWARF_E_INVALID_DIR_IDX);
 801                     goto invalid_data;
 802                   }
 803                 Dwarf_Word mtime;
 804                 if (unlikely (linep >= lineendp))
 805                   goto invalid_data;
 806                 get_uleb128 (mtime, linep, lineendp);
 807                 Dwarf_Word filelength;
 808                 if (unlikely (linep >= lineendp))
 809                   goto invalid_data;
 810                 get_uleb128 (filelength, linep, lineendp);
 811
 812                 struct filelist *new_file = NEW_FILE ();
 813                 if (fname[0] == '/')
 814                   new_file->info.name = fname;
 815                 else
 816                   {
 817                     new_file->info.name =
 818                       libdw_alloc (dbg, char, 1, (dirarray[diridx].len + 1
 819                                                   + fnamelen + 1));
 820                     char *cp = new_file->info.name;
 821
 822                     if (dirarray[diridx].dir != NULL)
 823                       /* This value could be NULL in case the
 824                          DW_AT_comp_dir was not present.  We
 825                          cannot do much in this case.  Just
 826                          keep the file relative.  */
 827                       {
 828                         cp = stpcpy (cp, dirarray[diridx].dir);
 829                         *cp++ = '/';
 830                       }
 831                     strcpy (cp, fname);
 832                   }
 833
 834                 new_file->info.mtime = mtime;
 835                 new_file->info.length = filelength;
 836               }
 837               break;
 838
 839             case DW_LNE_set_discriminator:
 840               /* Takes one ULEB128 parameter, the discriminator.  */
 841               if (unlikely (standard_opcode_lengths[opcode] != 1))
 842                 goto invalid_data;
 843
 844               if (unlikely (linep >= lineendp))
 845                 goto invalid_data;
 846               get_uleb128 (state.discriminator, linep, lineendp);
 847               break;
 848
 849             case DW_LNE_NVIDIA_inlined_call:
 850               if (unlikely (linep >= lineendp))
 851                 goto invalid_data;
 852               get_uleb128 (state.context, linep, lineendp);
 853               if (unlikely (linep >= lineendp))
 854                 goto invalid_data;
 855               get_uleb128 (state.function_name, linep, lineendp);
 856               state.function_name += debug_str_offset;
 857               break;
 858
 859             case DW_LNE_NVIDIA_set_function_name:
 860               if (unlikely (linep >= lineendp))
 861                 goto invalid_data;
 862               get_uleb128 (state.function_name, linep, lineendp);
 863               state.function_name += debug_str_offset;
 864               break;
 865
 866             default:
 867               /* Unknown, ignore it.  */
 868               if (unlikely ((size_t) (lineendp - (linep - 1)) < len))
 869                 goto invalid_data;
 870               linep += len - 1;
 871               break;
 872             }
 873         }
 874       else if (opcode <= DW_LNS_set_isa)
 875         {
 876           /* This is a known standard opcode.  */
 877           switch (opcode)
 878             {
 879             case DW_LNS_copy:
 880               /* Takes no argument.  */
 881               if (unlikely (standard_opcode_lengths[opcode] != 0))
 882                 goto invalid_data;
 883
 884               /* Add a new line with the current state machine values.  */
 885               NEW_LINE (0);
 886
 887               /* Reset the flags.  */
 888               state.basic_block = false;
 889               state.prologue_end = false;
 890               state.epilogue_begin = false;
 891               state.discriminator = 0;
 892               break;
 893
 894             case DW_LNS_advance_pc:
 895               /* Takes one uleb128 parameter which is added to the
 896                  address.  */
 897               if (unlikely (standard_opcode_lengths[opcode] != 1))
 898                 goto invalid_data;
 899
 900               if (unlikely (linep >= lineendp))
 901                 goto invalid_data;
 902               get_uleb128 (u128, linep, lineendp);
 903               advance_pc (u128);
 904               break;
 905
 906             case DW_LNS_advance_line:
 907               /* Takes one sleb128 parameter which is added to the
 908                  line.  */
 909               if (unlikely (standard_opcode_lengths[opcode] != 1))
 910                 goto invalid_data;
 911
 912               if (unlikely (linep >= lineendp))
 913                 goto invalid_data;
 914               get_sleb128 (s128, linep, lineendp);
 915               state.line += s128;
 916               break;
 917
 918             case DW_LNS_set_file:
 919               /* Takes one uleb128 parameter which is stored in file.  */
 920               if (unlikely (standard_opcode_lengths[opcode] != 1))
 921                 goto invalid_data;
 922
 923               if (unlikely (linep >= lineendp))
 924                 goto invalid_data;
 925               get_uleb128 (u128, linep, lineendp);
 926               state.file = u128;
 927               break;
 928
 929             case DW_LNS_set_column:
 930               /* Takes one uleb128 parameter which is stored in column.  */
 931               if (unlikely (standard_opcode_lengths[opcode] != 1))
 932                 goto invalid_data;
 933
 934               if (unlikely (linep >= lineendp))
 935                 goto invalid_data;
 936               get_uleb128 (u128, linep, lineendp);
 937               state.column = u128;
 938               break;
 939
 940             case DW_LNS_negate_stmt:
 941               /* Takes no argument.  */
 942               if (unlikely (standard_opcode_lengths[opcode] != 0))
 943                 goto invalid_data;
 944
 945               state.is_stmt = 1 - state.is_stmt;
 946               break;
 947
 948             case DW_LNS_set_basic_block:
 949               /* Takes no argument.  */
 950               if (unlikely (standard_opcode_lengths[opcode] != 0))
 951                 goto invalid_data;
 952
 953               state.basic_block = true;
 954               break;
 955
 956             case DW_LNS_const_add_pc:
 957               /* Takes no argument.  */
 958               if (unlikely (standard_opcode_lengths[opcode] != 0))
 959                 goto invalid_data;
 960
 961               if (unlikely (line_range == 0))
 962                 goto invalid_data;
 963
 964               advance_pc ((255 - opcode_base) / line_range);
 965               break;
 966
 967             case DW_LNS_fixed_advance_pc:
 968               /* Takes one 16 bit parameter which is added to the
 969                  address.  */
 970               if (unlikely (standard_opcode_lengths[opcode] != 1)
 971                   || unlikely (lineendp - linep < 2))
 972                 goto invalid_data;
 973
 974               state.addr += read_2ubyte_unaligned_inc (dbg, linep);
 975               state.op_index = 0;
 976               break;
 977
 978             case DW_LNS_set_prologue_end:
 979               /* Takes no argument.  */
 980               if (unlikely (standard_opcode_lengths[opcode] != 0))
 981                 goto invalid_data;
 982
 983               state.prologue_end = true;
 984               break;
 985
 986             case DW_LNS_set_epilogue_begin:
 987               /* Takes no argument.  */
 988               if (unlikely (standard_opcode_lengths[opcode] != 0))
 989                 goto invalid_data;
 990
 991               state.epilogue_begin = true;
 992               break;
 993
 994             case DW_LNS_set_isa:
 995               /* Takes one uleb128 parameter which is stored in isa.  */
 996               if (unlikely (standard_opcode_lengths[opcode] != 1))
 997                 goto invalid_data;
 998
 999               if (unlikely (linep >= lineendp))
1000                 goto invalid_data;
1001               get_uleb128 (state.isa, linep, lineendp);
1002               break;
1003             }
1004         }
1005       else
1006         {
1007           /* This is a new opcode the generator but not we know about.
1008              Read the parameters associated with it but then discard
1009              everything.  Read all the parameters for this opcode.  */
1010           for (int n = standard_opcode_lengths[opcode]; n > 0; --n)
1011             {
1012               if (unlikely (linep >= lineendp))
1013                 goto invalid_data;
1014               get_uleb128 (u128, linep, lineendp);
1015             }
1016
1017           /* Next round, ignore this opcode.  */
1018           continue;
1019         }
1020     }
1021
1022   /* Put all the files in an array.  */
1023   Dwarf_Files *files = libdw_alloc (dbg, Dwarf_Files,
1024                                     sizeof (Dwarf_Files)
1025                                     + nfilelist * sizeof (Dwarf_Fileinfo)
1026                                     + (ndirlist + 1) * sizeof (char *),
1027                                     1);
1028   const char **dirs = (void *) &files->info[nfilelist];
1029
1030   struct filelist *fileslist = filelist;
1031   files->nfiles = nfilelist;
1032   for (size_t n = nfilelist; n > 0; n--)
1033     {
1034       files->info[n - 1] = fileslist->info;
1035       fileslist = fileslist->next;
1036     }
1037   assert (fileslist == NULL);
1038
1039   /* Put all the directory strings in an array.  */
1040   files->ndirs = ndirlist;
1041   for (unsigned int i = 0; i < ndirlist; ++i)
1042     dirs[i] = dirarray[i].dir;
1043   dirs[ndirlist] = NULL;
1044
1045   /* Pass the file data structure to the caller.  */
1046   if (filesp != NULL)
1047     *filesp = files;
1048
1049   size_t buf_size = (sizeof (Dwarf_Lines)
1050                      + (sizeof (Dwarf_Line) * state.nlinelist));
1051   void *buf = libdw_alloc (dbg, Dwarf_Lines, buf_size, 1);
1052
1053   /* First use the buffer for the pointers, and sort the entries.
1054      We'll write the pointers in the end of the buffer, and then
1055      copy into the buffer from the beginning so the overlap works.  */
1056   assert (sizeof (Dwarf_Line) >= sizeof (struct linelist *));
1057   struct linelist **sortlines = (buf + buf_size
1058                                  - sizeof (struct linelist **) * state.nlinelist);
1059
1060   /* The list is in LIFO order and usually they come in clumps with
1061      ascending addresses.  So fill from the back to probably start with
1062      runs already in order before we sort.  */
1063   struct linelist *lineslist = state.linelist;
1064   for (size_t i = state.nlinelist; i-- > 0; )
1065     {
1066       sortlines[i] = lineslist;
1067       lineslist = lineslist->next;
1068     }
1069   assert (lineslist == NULL);
1070
1071   /* Sort by ascending address.  */
1072   qsort (sortlines, state.nlinelist, sizeof sortlines[0], &compare_lines);
1073
1074   /* Now that they are sorted, put them in the final array.
1075      The buffers overlap, so we've clobbered the early elements
1076      of SORTLINES by the time we're reading the later ones.  */
1077   Dwarf_Lines *lines = buf;
1078   lines->nlines = state.nlinelist;
1079   for (size_t i = 0; i < state.nlinelist; ++i)
1080     {
1081       lines->info[i] = sortlines[i]->line;
1082       lines->info[i].files = files;
1083     }
1084
1085   /* Make sure the highest address for the CU is marked as end_sequence.
1086      This is required by the DWARF spec, but some compilers forget and
1087      dwfl_module_getsrc depends on it.  */
1088   if (state.nlinelist > 0)
1089     lines->info[state.nlinelist - 1].end_sequence = 1;
1090
1091   /* Pass the line structure back to the caller.  */
1092   if (linesp != NULL)
1093     *linesp = lines;
1094
1095   /* Success.  */
1096   res = 0;
1097
1098  out:
1099   /* Free malloced line records, if any.  */
1100   for (size_t i = MAX_STACK_LINES; i < state.nlinelist; i++)
1101     {
1102       struct linelist *ll = state.linelist->next;
1103       free (state.linelist);
1104       state.linelist = ll;
1105     }
1106   if (dirarray != dirstack)
1107     free (dirarray);
1108   for (size_t i = MAX_STACK_FILES; i < nfilelist; i++)
1109     {
1110       struct filelist *fl = filelist->next;
1111       free (filelist);
1112       filelist = fl;
1113     }
1114
1115   return res;
1116 }
1117
1118 static int
1119 files_lines_compare (const void *p1, const void *p2)
1120 {
1121   const struct files_lines_s *t1 = p1;
1122   const struct files_lines_s *t2 = p2;
1123
1124   if (t1->debug_line_offset < t2->debug_line_offset)
1125     return -1;
1126   if (t1->debug_line_offset > t2->debug_line_offset)
1127     return 1;
1128
1129   return 0;
1130 }
1131
1132 int
1133 internal_function
1134 __libdw_getsrclines (Dwarf *dbg, Dwarf_Off debug_line_offset,
1135                      const char *comp_dir, unsigned address_size,
1136                      Dwarf_Lines **linesp, Dwarf_Files **filesp)
1137 {
1138   struct files_lines_s fake = { .debug_line_offset = debug_line_offset };
1139   struct files_lines_s **found = tfind (&fake, &dbg->files_lines,
1140                                         files_lines_compare);
1141   if (found == NULL)
1142     {
1143       Elf_Data *data = __libdw_checked_get_data (dbg, IDX_debug_line);
1144       if (data == NULL
1145           || __libdw_offset_in_section (dbg, IDX_debug_line,
1146                                         debug_line_offset, 1) != 0)
1147         return -1;
1148
1149       const unsigned char *linep = data->d_buf + debug_line_offset;
1150       const unsigned char *lineendp = data->d_buf + data->d_size;
1151
1152       struct files_lines_s *node = libdw_alloc (dbg, struct files_lines_s,
1153                                                 sizeof *node, 1);
1154
1155       if (read_srclines (dbg, linep, lineendp, comp_dir, address_size,
1156                          &node->lines, &node->files) != 0)
1157         return -1;
1158
1159       node->debug_line_offset = debug_line_offset;
1160
1161       found = tsearch (node, &dbg->files_lines, files_lines_compare);
1162       if (found == NULL)
1163         {
1164           __libdw_seterrno (DWARF_E_NOMEM);
1165           return -1;
1166         }
1167     }
1168
1169   if (linesp != NULL)
1170     *linesp = (*found)->lines;
1171
1172   if (filesp != NULL)
1173     *filesp = (*found)->files;
1174
1175   return 0;
1176 }
1177
1178 /* Get the compilation directory, if any is set.  */
1179 const char *
1180 __libdw_getcompdir (Dwarf_Die *cudie)
1181 {
1182   Dwarf_Attribute compdir_attr_mem;
1183   Dwarf_Attribute *compdir_attr = INTUSE(dwarf_attr) (cudie,
1184                                                       DW_AT_comp_dir,
1185                                                       &compdir_attr_mem);
1186   return INTUSE(dwarf_formstring) (compdir_attr);
1187 }
1188
1189 int
1190 dwarf_getsrclines (Dwarf_Die *cudie, Dwarf_Lines **lines, size_t *nlines)
1191 {
1192   if (cudie == NULL)
1193     return -1;
1194   if (! is_cudie (cudie))
1195     {
1196       __libdw_seterrno (DWARF_E_NOT_CUDIE);
1197       return -1;
1198     }
1199
1200   /* Get the information if it is not already known.  */
1201   struct Dwarf_CU *const cu = cudie->cu;
1202   if (cu->lines == NULL)
1203     {
1204       /* For split units always pick the lines from the skeleton.  */
1205       if (cu->unit_type == DW_UT_split_compile
1206           || cu->unit_type == DW_UT_split_type)
1207         {
1208           /* We tries, assume we fail...  */
1209           cu->lines = (void *) -1l;
1210
1211           Dwarf_CU *skel = __libdw_find_split_unit (cu);
1212           if (skel != NULL)
1213             {
1214               Dwarf_Die skeldie = CUDIE (skel);
1215               int res = INTUSE(dwarf_getsrclines) (&skeldie, lines, nlines);
1216               if (res == 0)
1217                 {
1218                   cu->lines = skel->lines;
1219                   *lines = cu->lines;
1220                   *nlines = cu->lines->nlines;
1221                 }
1222               return res;
1223             }
1224
1225           __libdw_seterrno (DWARF_E_NO_DEBUG_LINE);
1226           return -1;
1227         }
1228
1229       /* Failsafe mode: no data found.  */
1230       cu->lines = (void *) -1l;
1231       cu->files = (void *) -1l;
1232
1233       /* The die must have a statement list associated.  */
1234       Dwarf_Attribute stmt_list_mem;
1235       Dwarf_Attribute *stmt_list = INTUSE(dwarf_attr) (cudie, DW_AT_stmt_list,
1236                                                        &stmt_list_mem);
1237
1238       /* Get the offset into the .debug_line section.  NB: this call
1239          also checks whether the previous dwarf_attr call failed.  */
1240       Dwarf_Off debug_line_offset;
1241       if (__libdw_formptr (stmt_list, IDX_debug_line, DWARF_E_NO_DEBUG_LINE,
1242                            NULL, &debug_line_offset) == NULL)
1243         return -1;
1244
1245       if (__libdw_getsrclines (cu->dbg, debug_line_offset,
1246                                __libdw_getcompdir (cudie),
1247                                cu->address_size, &cu->lines, &cu->files) < 0)
1248         return -1;
1249     }
1250   else if (cu->lines == (void *) -1l)
1251     return -1;
1252
1253   *lines = cu->lines;
1254   *nlines = cu->lines->nlines;
1255
1256   // XXX Eventually: unlocking here.
1257
1258   return 0;
1259 }
1260 INTDEF(dwarf_getsrclines)