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