gdb/btrace.c

   1 /* Branch trace support for GDB, the GNU debugger.
   2
   3    Copyright (C) 2013-2014 Free Software Foundation, Inc.
   4
   5    Contributed by Intel Corp. <markus.t.metzger@intel.com>
   6
   7    This file is part of GDB.
   8
   9    This program is free software; you can redistribute it and/or modify
  10    it under the terms of the GNU General Public License as published by
  11    the Free Software Foundation; either version 3 of the License, or
  12    (at your option) any later version.
  13
  14    This program is distributed in the hope that it will be useful,
  15    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17    GNU General Public License for more details.
  18
  19    You should have received a copy of the GNU General Public License
  20    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  21
  22 #include "btrace.h"
  23 #include "gdbthread.h"
  24 #include "exceptions.h"
  25 #include "inferior.h"
  26 #include "target.h"
  27 #include "record.h"
  28 #include "symtab.h"
  29 #include "disasm.h"
  30 #include "source.h"
  31 #include "filenames.h"
  32 #include "xml-support.h"
  33
  34 /* Print a record debug message.  Use do ... while (0) to avoid ambiguities
  35    when used in if statements.  */
  36
  37 #define DEBUG(msg, args...)                                             \
  38   do                                                                    \
  39     {                                                                   \
  40       if (record_debug != 0)                                            \
  41         fprintf_unfiltered (gdb_stdlog,                                 \
  42                             "[btrace] " msg "\n", ##args);              \
  43     }                                                                   \
  44   while (0)
  45
  46 #define DEBUG_FTRACE(msg, args...) DEBUG ("[ftrace] " msg, ##args)
  47
  48 /* Return the function name of a recorded function segment for printing.
  49    This function never returns NULL.  */
  50
  51 static const char *
  52 ftrace_print_function_name (const struct btrace_function *bfun)
  53 {
  54   struct minimal_symbol *msym;
  55   struct symbol *sym;
  56
  57   msym = bfun->msym;
  58   sym = bfun->sym;
  59
  60   if (sym != NULL)
  61     return SYMBOL_PRINT_NAME (sym);
  62
  63   if (msym != NULL)
  64     return SYMBOL_PRINT_NAME (msym);
  65
  66   return "<unknown>";
  67 }
  68
  69 /* Return the file name of a recorded function segment for printing.
  70    This function never returns NULL.  */
  71
  72 static const char *
  73 ftrace_print_filename (const struct btrace_function *bfun)
  74 {
  75   struct symbol *sym;
  76   const char *filename;
  77
  78   sym = bfun->sym;
  79
  80   if (sym != NULL)
  81     filename = symtab_to_filename_for_display (sym->symtab);
  82   else
  83     filename = "<unknown>";
  84
  85   return filename;
  86 }
  87
  88 /* Return a string representation of the address of an instruction.
  89    This function never returns NULL.  */
  90
  91 static const char *
  92 ftrace_print_insn_addr (const struct btrace_insn *insn)
  93 {
  94   if (insn == NULL)
  95     return "<nil>";
  96
  97   return core_addr_to_string_nz (insn->pc);
  98 }
  99
 100 /* Print an ftrace debug status message.  */
 101
 102 static void
 103 ftrace_debug (const struct btrace_function *bfun, const char *prefix)
 104 {
 105   const char *fun, *file;
 106   unsigned int ibegin, iend;
 107   int lbegin, lend, level;
 108
 109   fun = ftrace_print_function_name (bfun);
 110   file = ftrace_print_filename (bfun);
 111   level = bfun->level;
 112
 113   lbegin = bfun->lbegin;
 114   lend = bfun->lend;
 115
 116   ibegin = bfun->insn_offset;
 117   iend = ibegin + VEC_length (btrace_insn_s, bfun->insn);
 118
 119   DEBUG_FTRACE ("%s: fun = %s, file = %s, level = %d, lines = [%d; %d], "
 120                 "insn = [%u; %u)", prefix, fun, file, level, lbegin, lend,
 121                 ibegin, iend);
 122 }
 123
 124 /* Return non-zero if BFUN does not match MFUN and FUN,
 125    return zero otherwise.  */
 126
 127 static int
 128 ftrace_function_switched (const struct btrace_function *bfun,
 129                           const struct minimal_symbol *mfun,
 130                           const struct symbol *fun)
 131 {
 132   struct minimal_symbol *msym;
 133   struct symbol *sym;
 134
 135   msym = bfun->msym;
 136   sym = bfun->sym;
 137
 138   /* If the minimal symbol changed, we certainly switched functions.  */
 139   if (mfun != NULL && msym != NULL
 140       && strcmp (SYMBOL_LINKAGE_NAME (mfun), SYMBOL_LINKAGE_NAME (msym)) != 0)
 141     return 1;
 142
 143   /* If the symbol changed, we certainly switched functions.  */
 144   if (fun != NULL && sym != NULL)
 145     {
 146       const char *bfname, *fname;
 147
 148       /* Check the function name.  */
 149       if (strcmp (SYMBOL_LINKAGE_NAME (fun), SYMBOL_LINKAGE_NAME (sym)) != 0)
 150         return 1;
 151
 152       /* Check the location of those functions, as well.  */
 153       bfname = symtab_to_fullname (sym->symtab);
 154       fname = symtab_to_fullname (fun->symtab);
 155       if (filename_cmp (fname, bfname) != 0)
 156         return 1;
 157     }
 158
 159   /* If we lost symbol information, we switched functions.  */
 160   if (!(msym == NULL && sym == NULL) && mfun == NULL && fun == NULL)
 161     return 1;
 162
 163   /* If we gained symbol information, we switched functions.  */
 164   if (msym == NULL && sym == NULL && !(mfun == NULL && fun == NULL))
 165     return 1;
 166
 167   return 0;
 168 }
 169
 170 /* Return non-zero if we should skip this file when generating the function
 171    call history, zero otherwise.
 172    We would want to do that if, say, a macro that is defined in another file
 173    is expanded in this function.  */
 174
 175 static int
 176 ftrace_skip_file (const struct btrace_function *bfun, const char *fullname)
 177 {
 178   struct symbol *sym;
 179   const char *bfile;
 180
 181   sym = bfun->sym;
 182   if (sym == NULL)
 183     return 1;
 184
 185   bfile = symtab_to_fullname (sym->symtab);
 186
 187   return (filename_cmp (bfile, fullname) != 0);
 188 }
 189
 190 /* Allocate and initialize a new branch trace function segment.
 191    PREV is the chronologically preceding function segment.
 192    MFUN and FUN are the symbol information we have for this function.  */
 193
 194 static struct btrace_function *
 195 ftrace_new_function (struct btrace_function *prev,
 196                      struct minimal_symbol *mfun,
 197                      struct symbol *fun)
 198 {
 199   struct btrace_function *bfun;
 200
 201   bfun = xzalloc (sizeof (*bfun));
 202
 203   bfun->msym = mfun;
 204   bfun->sym = fun;
 205   bfun->flow.prev = prev;
 206
 207   /* We start with the identities of min and max, respectively.  */
 208   bfun->lbegin = INT_MAX;
 209   bfun->lend = INT_MIN;
 210
 211   if (prev == NULL)
 212     {
 213       /* Start counting at one.  */
 214       bfun->number = 1;
 215       bfun->insn_offset = 1;
 216     }
 217   else
 218     {
 219       gdb_assert (prev->flow.next == NULL);
 220       prev->flow.next = bfun;
 221
 222       bfun->number = prev->number + 1;
 223       bfun->insn_offset = (prev->insn_offset
 224                            + VEC_length (btrace_insn_s, prev->insn));
 225     }
 226
 227   return bfun;
 228 }
 229
 230 /* Update the UP field of a function segment.  */
 231
 232 static void
 233 ftrace_update_caller (struct btrace_function *bfun,
 234                       struct btrace_function *caller,
 235                       enum btrace_function_flag flags)
 236 {
 237   if (bfun->up != NULL)
 238     ftrace_debug (bfun, "updating caller");
 239
 240   bfun->up = caller;
 241   bfun->flags = flags;
 242
 243   ftrace_debug (bfun, "set caller");
 244 }
 245
 246 /* Fix up the caller for all segments of a function.  */
 247
 248 static void
 249 ftrace_fixup_caller (struct btrace_function *bfun,
 250                      struct btrace_function *caller,
 251                      enum btrace_function_flag flags)
 252 {
 253   struct btrace_function *prev, *next;
 254
 255   ftrace_update_caller (bfun, caller, flags);
 256
 257   /* Update all function segments belonging to the same function.  */
 258   for (prev = bfun->segment.prev; prev != NULL; prev = prev->segment.prev)
 259     ftrace_update_caller (prev, caller, flags);
 260
 261   for (next = bfun->segment.next; next != NULL; next = next->segment.next)
 262     ftrace_update_caller (next, caller, flags);
 263 }
 264
 265 /* Add a new function segment for a call.
 266    CALLER is the chronologically preceding function segment.
 267    MFUN and FUN are the symbol information we have for this function.  */
 268
 269 static struct btrace_function *
 270 ftrace_new_call (struct btrace_function *caller,
 271                  struct minimal_symbol *mfun,
 272                  struct symbol *fun)
 273 {
 274   struct btrace_function *bfun;
 275
 276   bfun = ftrace_new_function (caller, mfun, fun);
 277   bfun->up = caller;
 278   bfun->level = caller->level + 1;
 279
 280   ftrace_debug (bfun, "new call");
 281
 282   return bfun;
 283 }
 284
 285 /* Add a new function segment for a tail call.
 286    CALLER is the chronologically preceding function segment.
 287    MFUN and FUN are the symbol information we have for this function.  */
 288
 289 static struct btrace_function *
 290 ftrace_new_tailcall (struct btrace_function *caller,
 291                      struct minimal_symbol *mfun,
 292                      struct symbol *fun)
 293 {
 294   struct btrace_function *bfun;
 295
 296   bfun = ftrace_new_function (caller, mfun, fun);
 297   bfun->up = caller;
 298   bfun->level = caller->level + 1;
 299   bfun->flags |= BFUN_UP_LINKS_TO_TAILCALL;
 300
 301   ftrace_debug (bfun, "new tail call");
 302
 303   return bfun;
 304 }
 305
 306 /* Find the innermost caller in the back trace of BFUN with MFUN/FUN
 307    symbol information.  */
 308
 309 static struct btrace_function *
 310 ftrace_find_caller (struct btrace_function *bfun,
 311                     struct minimal_symbol *mfun,
 312                     struct symbol *fun)
 313 {
 314   for (; bfun != NULL; bfun = bfun->up)
 315     {
 316       /* Skip functions with incompatible symbol information.  */
 317       if (ftrace_function_switched (bfun, mfun, fun))
 318         continue;
 319
 320       /* This is the function segment we're looking for.  */
 321       break;
 322     }
 323
 324   return bfun;
 325 }
 326
 327 /* Find the innermost caller in the back trace of BFUN, skipping all
 328    function segments that do not end with a call instruction (e.g.
 329    tail calls ending with a jump).  */
 330
 331 static struct btrace_function *
 332 ftrace_find_call (struct gdbarch *gdbarch, struct btrace_function *bfun)
 333 {
 334   for (; bfun != NULL; bfun = bfun->up)
 335     {
 336       struct btrace_insn *last;
 337       CORE_ADDR pc;
 338
 339       /* We do not allow empty function segments.  */
 340       gdb_assert (!VEC_empty (btrace_insn_s, bfun->insn));
 341
 342       last = VEC_last (btrace_insn_s, bfun->insn);
 343       pc = last->pc;
 344
 345       if (gdbarch_insn_is_call (gdbarch, pc))
 346         break;
 347     }
 348
 349   return bfun;
 350 }
 351
 352 /* Add a continuation segment for a function into which we return.
 353    PREV is the chronologically preceding function segment.
 354    MFUN and FUN are the symbol information we have for this function.  */
 355
 356 static struct btrace_function *
 357 ftrace_new_return (struct gdbarch *gdbarch,
 358                    struct btrace_function *prev,
 359                    struct minimal_symbol *mfun,
 360                    struct symbol *fun)
 361 {
 362   struct btrace_function *bfun, *caller;
 363
 364   bfun = ftrace_new_function (prev, mfun, fun);
 365
 366   /* It is important to start at PREV's caller.  Otherwise, we might find
 367      PREV itself, if PREV is a recursive function.  */
 368   caller = ftrace_find_caller (prev->up, mfun, fun);
 369   if (caller != NULL)
 370     {
 371       /* The caller of PREV is the preceding btrace function segment in this
 372          function instance.  */
 373       gdb_assert (caller->segment.next == NULL);
 374
 375       caller->segment.next = bfun;
 376       bfun->segment.prev = caller;
 377
 378       /* Maintain the function level.  */
 379       bfun->level = caller->level;
 380
 381       /* Maintain the call stack.  */
 382       bfun->up = caller->up;
 383       bfun->flags = caller->flags;
 384
 385       ftrace_debug (bfun, "new return");
 386     }
 387   else
 388     {
 389       /* We did not find a caller.  This could mean that something went
 390          wrong or that the call is simply not included in the trace.  */
 391
 392       /* Let's search for some actual call.  */
 393       caller = ftrace_find_call (gdbarch, prev->up);
 394       if (caller == NULL)
 395         {
 396           /* There is no call in PREV's back trace.  We assume that the
 397              branch trace did not include it.  */
 398
 399           /* Let's find the topmost call function - this skips tail calls.  */
 400           while (prev->up != NULL)
 401             prev = prev->up;
 402
 403           /* We maintain levels for a series of returns for which we have
 404              not seen the calls.
 405              We start at the preceding function's level in case this has
 406              already been a return for which we have not seen the call.
 407              We start at level 0 otherwise, to handle tail calls correctly.  */
 408           bfun->level = min (0, prev->level) - 1;
 409
 410           /* Fix up the call stack for PREV.  */
 411           ftrace_fixup_caller (prev, bfun, BFUN_UP_LINKS_TO_RET);
 412
 413           ftrace_debug (bfun, "new return - no caller");
 414         }
 415       else
 416         {
 417           /* There is a call in PREV's back trace to which we should have
 418              returned.  Let's remain at this level.  */
 419           bfun->level = prev->level;
 420
 421           ftrace_debug (bfun, "new return - unknown caller");
 422         }
 423     }
 424
 425   return bfun;
 426 }
 427
 428 /* Add a new function segment for a function switch.
 429    PREV is the chronologically preceding function segment.
 430    MFUN and FUN are the symbol information we have for this function.  */
 431
 432 static struct btrace_function *
 433 ftrace_new_switch (struct btrace_function *prev,
 434                    struct minimal_symbol *mfun,
 435                    struct symbol *fun)
 436 {
 437   struct btrace_function *bfun;
 438
 439   /* This is an unexplained function switch.  The call stack will likely
 440      be wrong at this point.  */
 441   bfun = ftrace_new_function (prev, mfun, fun);
 442
 443   /* We keep the function level.  */
 444   bfun->level = prev->level;
 445
 446   ftrace_debug (bfun, "new switch");
 447
 448   return bfun;
 449 }
 450
 451 /* Update BFUN with respect to the instruction at PC.  This may create new
 452    function segments.
 453    Return the chronologically latest function segment, never NULL.  */
 454
 455 static struct btrace_function *
 456 ftrace_update_function (struct gdbarch *gdbarch,
 457                         struct btrace_function *bfun, CORE_ADDR pc)
 458 {
 459   struct bound_minimal_symbol bmfun;
 460   struct minimal_symbol *mfun;
 461   struct symbol *fun;
 462   struct btrace_insn *last;
 463
 464   /* Try to determine the function we're in.  We use both types of symbols
 465      to avoid surprises when we sometimes get a full symbol and sometimes
 466      only a minimal symbol.  */
 467   fun = find_pc_function (pc);
 468   bmfun = lookup_minimal_symbol_by_pc (pc);
 469   mfun = bmfun.minsym;
 470
 471   if (fun == NULL && mfun == NULL)
 472     DEBUG_FTRACE ("no symbol at %s", core_addr_to_string_nz (pc));
 473
 474   /* If we didn't have a function before, we create one.  */
 475   if (bfun == NULL)
 476     return ftrace_new_function (bfun, mfun, fun);
 477
 478   /* Check the last instruction, if we have one.
 479      We do this check first, since it allows us to fill in the call stack
 480      links in addition to the normal flow links.  */
 481   last = NULL;
 482   if (!VEC_empty (btrace_insn_s, bfun->insn))
 483     last = VEC_last (btrace_insn_s, bfun->insn);
 484
 485   if (last != NULL)
 486     {
 487       CORE_ADDR lpc;
 488
 489       lpc = last->pc;
 490
 491       /* Check for returns.  */
 492       if (gdbarch_insn_is_ret (gdbarch, lpc))
 493         return ftrace_new_return (gdbarch, bfun, mfun, fun);
 494
 495       /* Check for calls.  */
 496       if (gdbarch_insn_is_call (gdbarch, lpc))
 497         {
 498           int size;
 499
 500           size = gdb_insn_length (gdbarch, lpc);
 501
 502           /* Ignore calls to the next instruction.  They are used for PIC.  */
 503           if (lpc + size != pc)
 504             return ftrace_new_call (bfun, mfun, fun);
 505         }
 506     }
 507
 508   /* Check if we're switching functions for some other reason.  */
 509   if (ftrace_function_switched (bfun, mfun, fun))
 510     {
 511       DEBUG_FTRACE ("switching from %s in %s at %s",
 512                     ftrace_print_insn_addr (last),
 513                     ftrace_print_function_name (bfun),
 514                     ftrace_print_filename (bfun));
 515
 516       if (last != NULL)
 517         {
 518           CORE_ADDR start, lpc;
 519
 520           start = get_pc_function_start (pc);
 521
 522           /* If we can't determine the function for PC, we treat a jump at
 523              the end of the block as tail call.  */
 524           if (start == 0)
 525             start = pc;
 526
 527           lpc = last->pc;
 528
 529           /* Jumps indicate optimized tail calls.  */
 530           if (start == pc && gdbarch_insn_is_jump (gdbarch, lpc))
 531             return ftrace_new_tailcall (bfun, mfun, fun);
 532         }
 533
 534       return ftrace_new_switch (bfun, mfun, fun);
 535     }
 536
 537   return bfun;
 538 }
 539
 540 /* Update BFUN's source range with respect to the instruction at PC.  */
 541
 542 static void
 543 ftrace_update_lines (struct btrace_function *bfun, CORE_ADDR pc)
 544 {
 545   struct symtab_and_line sal;
 546   const char *fullname;
 547
 548   sal = find_pc_line (pc, 0);
 549   if (sal.symtab == NULL || sal.line == 0)
 550     {
 551       DEBUG_FTRACE ("no lines at %s", core_addr_to_string_nz (pc));
 552       return;
 553     }
 554
 555   /* Check if we switched files.  This could happen if, say, a macro that
 556      is defined in another file is expanded here.  */
 557   fullname = symtab_to_fullname (sal.symtab);
 558   if (ftrace_skip_file (bfun, fullname))
 559     {
 560       DEBUG_FTRACE ("ignoring file at %s, file=%s",
 561                     core_addr_to_string_nz (pc), fullname);
 562       return;
 563     }
 564
 565   /* Update the line range.  */
 566   bfun->lbegin = min (bfun->lbegin, sal.line);
 567   bfun->lend = max (bfun->lend, sal.line);
 568
 569   if (record_debug > 1)
 570     ftrace_debug (bfun, "update lines");
 571 }
 572
 573 /* Add the instruction at PC to BFUN's instructions.  */
 574
 575 static void
 576 ftrace_update_insns (struct btrace_function *bfun, CORE_ADDR pc)
 577 {
 578   struct btrace_insn *insn;
 579
 580   insn = VEC_safe_push (btrace_insn_s, bfun->insn, NULL);
 581   insn->pc = pc;
 582
 583   if (record_debug > 1)
 584     ftrace_debug (bfun, "update insn");
 585 }
 586
 587 /* Compute the function branch trace from a block branch trace BTRACE for
 588    a thread given by BTINFO.  */
 589
 590 static void
 591 btrace_compute_ftrace (struct btrace_thread_info *btinfo,
 592                        VEC (btrace_block_s) *btrace)
 593 {
 594   struct btrace_function *begin, *end;
 595   struct gdbarch *gdbarch;
 596   unsigned int blk;
 597   int level;
 598
 599   DEBUG ("compute ftrace");
 600
 601   gdbarch = target_gdbarch ();
 602   begin = NULL;
 603   end = NULL;
 604   level = INT_MAX;
 605   blk = VEC_length (btrace_block_s, btrace);
 606
 607   while (blk != 0)
 608     {
 609       btrace_block_s *block;
 610       CORE_ADDR pc;
 611
 612       blk -= 1;
 613
 614       block = VEC_index (btrace_block_s, btrace, blk);
 615       pc = block->begin;
 616
 617       for (;;)
 618         {
 619           int size;
 620
 621           /* We should hit the end of the block.  Warn if we went too far.  */
 622           if (block->end < pc)
 623             {
 624               warning (_("Recorded trace may be corrupted around %s."),
 625                        core_addr_to_string_nz (pc));
 626               break;
 627             }
 628
 629           end = ftrace_update_function (gdbarch, end, pc);
 630           if (begin == NULL)
 631             begin = end;
 632
 633           /* Maintain the function level offset.
 634              For all but the last block, we do it here.  */
 635           if (blk != 0)
 636             level = min (level, end->level);
 637
 638           ftrace_update_insns (end, pc);
 639           ftrace_update_lines (end, pc);
 640
 641           /* We're done once we pushed the instruction at the end.  */
 642           if (block->end == pc)
 643             break;
 644
 645           size = gdb_insn_length (gdbarch, pc);
 646
 647           /* Make sure we terminate if we fail to compute the size.  */
 648           if (size <= 0)
 649             {
 650               warning (_("Recorded trace may be incomplete around %s."),
 651                        core_addr_to_string_nz (pc));
 652               break;
 653             }
 654
 655           pc += size;
 656
 657           /* Maintain the function level offset.
 658              For the last block, we do it here to not consider the last
 659              instruction.
 660              Since the last instruction corresponds to the current instruction
 661              and is not really part of the execution history, it shouldn't
 662              affect the level.  */
 663           if (blk == 0)
 664             level = min (level, end->level);
 665         }
 666     }
 667
 668   btinfo->begin = begin;
 669   btinfo->end = end;
 670
 671   /* LEVEL is the minimal function level of all btrace function segments.
 672      Define the global level offset to -LEVEL so all function levels are
 673      normalized to start at zero.  */
 674   btinfo->level = -level;
 675 }
 676
 677 /* See btrace.h.  */
 678
 679 void
 680 btrace_enable (struct thread_info *tp)
 681 {
 682   if (tp->btrace.target != NULL)
 683     return;
 684
 685   if (!target_supports_btrace ())
 686     error (_("Target does not support branch tracing."));
 687
 688   DEBUG ("enable thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
 689
 690   tp->btrace.target = target_enable_btrace (tp->ptid);
 691 }
 692
 693 /* See btrace.h.  */
 694
 695 void
 696 btrace_disable (struct thread_info *tp)
 697 {
 698   struct btrace_thread_info *btp = &tp->btrace;
 699   int errcode = 0;
 700
 701   if (btp->target == NULL)
 702     return;
 703
 704   DEBUG ("disable thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
 705
 706   target_disable_btrace (btp->target);
 707   btp->target = NULL;
 708
 709   btrace_clear (tp);
 710 }
 711
 712 /* See btrace.h.  */
 713
 714 void
 715 btrace_teardown (struct thread_info *tp)
 716 {
 717   struct btrace_thread_info *btp = &tp->btrace;
 718   int errcode = 0;
 719
 720   if (btp->target == NULL)
 721     return;
 722
 723   DEBUG ("teardown thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
 724
 725   target_teardown_btrace (btp->target);
 726   btp->target = NULL;
 727
 728   btrace_clear (tp);
 729 }
 730
 731 /* See btrace.h.  */
 732
 733 void
 734 btrace_fetch (struct thread_info *tp)
 735 {
 736   struct btrace_thread_info *btinfo;
 737   VEC (btrace_block_s) *btrace;
 738   struct cleanup *cleanup;
 739
 740   DEBUG ("fetch thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
 741
 742   btinfo = &tp->btrace;
 743   if (btinfo->target == NULL)
 744     return;
 745
 746   btrace = target_read_btrace (btinfo->target, BTRACE_READ_NEW);
 747   cleanup = make_cleanup (VEC_cleanup (btrace_block_s), &btrace);
 748
 749   if (!VEC_empty (btrace_block_s, btrace))
 750     {
 751       btrace_clear (tp);
 752       btrace_compute_ftrace (btinfo, btrace);
 753     }
 754
 755   do_cleanups (cleanup);
 756 }
 757
 758 /* See btrace.h.  */
 759
 760 void
 761 btrace_clear (struct thread_info *tp)
 762 {
 763   struct btrace_thread_info *btinfo;
 764   struct btrace_function *it, *trash;
 765
 766   DEBUG ("clear thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
 767
 768   btinfo = &tp->btrace;
 769
 770   it = btinfo->begin;
 771   while (it != NULL)
 772     {
 773       trash = it;
 774       it = it->flow.next;
 775
 776       xfree (trash);
 777     }
 778
 779   btinfo->begin = NULL;
 780   btinfo->end = NULL;
 781
 782   xfree (btinfo->insn_history);
 783   xfree (btinfo->call_history);
 784   xfree (btinfo->replay);
 785
 786   btinfo->insn_history = NULL;
 787   btinfo->call_history = NULL;
 788   btinfo->replay = NULL;
 789 }
 790
 791 /* See btrace.h.  */
 792
 793 void
 794 btrace_free_objfile (struct objfile *objfile)
 795 {
 796   struct thread_info *tp;
 797
 798   DEBUG ("free objfile");
 799
 800   ALL_THREADS (tp)
 801     btrace_clear (tp);
 802 }
 803
 804 #if defined (HAVE_LIBEXPAT)
 805
 806 /* Check the btrace document version.  */
 807
 808 static void
 809 check_xml_btrace_version (struct gdb_xml_parser *parser,
 810                           const struct gdb_xml_element *element,
 811                           void *user_data, VEC (gdb_xml_value_s) *attributes)
 812 {
 813   const char *version = xml_find_attribute (attributes, "version")->value;
 814
 815   if (strcmp (version, "1.0") != 0)
 816     gdb_xml_error (parser, _("Unsupported btrace version: \"%s\""), version);
 817 }
 818
 819 /* Parse a btrace "block" xml record.  */
 820
 821 static void
 822 parse_xml_btrace_block (struct gdb_xml_parser *parser,
 823                         const struct gdb_xml_element *element,
 824                         void *user_data, VEC (gdb_xml_value_s) *attributes)
 825 {
 826   VEC (btrace_block_s) **btrace;
 827   struct btrace_block *block;
 828   ULONGEST *begin, *end;
 829
 830   btrace = user_data;
 831   block = VEC_safe_push (btrace_block_s, *btrace, NULL);
 832
 833   begin = xml_find_attribute (attributes, "begin")->value;
 834   end = xml_find_attribute (attributes, "end")->value;
 835
 836   block->begin = *begin;
 837   block->end = *end;
 838 }
 839
 840 static const struct gdb_xml_attribute block_attributes[] = {
 841   { "begin", GDB_XML_AF_NONE, gdb_xml_parse_attr_ulongest, NULL },
 842   { "end", GDB_XML_AF_NONE, gdb_xml_parse_attr_ulongest, NULL },
 843   { NULL, GDB_XML_AF_NONE, NULL, NULL }
 844 };
 845
 846 static const struct gdb_xml_attribute btrace_attributes[] = {
 847   { "version", GDB_XML_AF_NONE, NULL, NULL },
 848   { NULL, GDB_XML_AF_NONE, NULL, NULL }
 849 };
 850
 851 static const struct gdb_xml_element btrace_children[] = {
 852   { "block", block_attributes, NULL,
 853     GDB_XML_EF_REPEATABLE | GDB_XML_EF_OPTIONAL, parse_xml_btrace_block, NULL },
 854   { NULL, NULL, NULL, GDB_XML_EF_NONE, NULL, NULL }
 855 };
 856
 857 static const struct gdb_xml_element btrace_elements[] = {
 858   { "btrace", btrace_attributes, btrace_children, GDB_XML_EF_NONE,
 859     check_xml_btrace_version, NULL },
 860   { NULL, NULL, NULL, GDB_XML_EF_NONE, NULL, NULL }
 861 };
 862
 863 #endif /* defined (HAVE_LIBEXPAT) */
 864
 865 /* See btrace.h.  */
 866
 867 VEC (btrace_block_s) *
 868 parse_xml_btrace (const char *buffer)
 869 {
 870   VEC (btrace_block_s) *btrace = NULL;
 871   struct cleanup *cleanup;
 872   int errcode;
 873
 874 #if defined (HAVE_LIBEXPAT)
 875
 876   cleanup = make_cleanup (VEC_cleanup (btrace_block_s), &btrace);
 877   errcode = gdb_xml_parse_quick (_("btrace"), "btrace.dtd", btrace_elements,
 878                                  buffer, &btrace);
 879   if (errcode != 0)
 880     {
 881       do_cleanups (cleanup);
 882       return NULL;
 883     }
 884
 885   /* Keep parse results.  */
 886   discard_cleanups (cleanup);
 887
 888 #else  /* !defined (HAVE_LIBEXPAT) */
 889
 890   error (_("Cannot process branch trace.  XML parsing is not supported."));
 891
 892 #endif  /* !defined (HAVE_LIBEXPAT) */
 893
 894   return btrace;
 895 }
 896
 897 /* See btrace.h.  */
 898
 899 const struct btrace_insn *
 900 btrace_insn_get (const struct btrace_insn_iterator *it)
 901 {
 902   const struct btrace_function *bfun;
 903   unsigned int index, end;
 904
 905   index = it->index;
 906   bfun = it->function;
 907
 908   /* The index is within the bounds of this function's instruction vector.  */
 909   end = VEC_length (btrace_insn_s, bfun->insn);
 910   gdb_assert (0 < end);
 911   gdb_assert (index < end);
 912
 913   return VEC_index (btrace_insn_s, bfun->insn, index);
 914 }
 915
 916 /* See btrace.h.  */
 917
 918 unsigned int
 919 btrace_insn_number (const struct btrace_insn_iterator *it)
 920 {
 921   const struct btrace_function *bfun;
 922
 923   bfun = it->function;
 924   return bfun->insn_offset + it->index;
 925 }
 926
 927 /* See btrace.h.  */
 928
 929 void
 930 btrace_insn_begin (struct btrace_insn_iterator *it,
 931                    const struct btrace_thread_info *btinfo)
 932 {
 933   const struct btrace_function *bfun;
 934
 935   bfun = btinfo->begin;
 936   if (bfun == NULL)
 937     error (_("No trace."));
 938
 939   it->function = bfun;
 940   it->index = 0;
 941 }
 942
 943 /* See btrace.h.  */
 944
 945 void
 946 btrace_insn_end (struct btrace_insn_iterator *it,
 947                  const struct btrace_thread_info *btinfo)
 948 {
 949   const struct btrace_function *bfun;
 950   unsigned int length;
 951
 952   bfun = btinfo->end;
 953   if (bfun == NULL)
 954     error (_("No trace."));
 955
 956   /* The last instruction in the last function is the current instruction.
 957      We point to it - it is one past the end of the execution trace.  */
 958   length = VEC_length (btrace_insn_s, bfun->insn);
 959
 960   it->function = bfun;
 961   it->index = length - 1;
 962 }
 963
 964 /* See btrace.h.  */
 965
 966 unsigned int
 967 btrace_insn_next (struct btrace_insn_iterator *it, unsigned int stride)
 968 {
 969   const struct btrace_function *bfun;
 970   unsigned int index, steps;
 971
 972   bfun = it->function;
 973   steps = 0;
 974   index = it->index;
 975
 976   while (stride != 0)
 977     {
 978       unsigned int end, space, adv;
 979
 980       end = VEC_length (btrace_insn_s, bfun->insn);
 981
 982       gdb_assert (0 < end);
 983       gdb_assert (index < end);
 984
 985       /* Compute the number of instructions remaining in this segment.  */
 986       space = end - index;
 987
 988       /* Advance the iterator as far as possible within this segment.  */
 989       adv = min (space, stride);
 990       stride -= adv;
 991       index += adv;
 992       steps += adv;
 993
 994       /* Move to the next function if we're at the end of this one.  */
 995       if (index == end)
 996         {
 997           const struct btrace_function *next;
 998
 999           next = bfun->flow.next;
1000           if (next == NULL)
1001             {
1002               /* We stepped past the last function.
1003
1004                  Let's adjust the index to point to the last instruction in
1005                  the previous function.  */
1006               index -= 1;
1007               steps -= 1;
1008               break;
1009             }
1010
1011           /* We now point to the first instruction in the new function.  */
1012           bfun = next;
1013           index = 0;
1014         }
1015
1016       /* We did make progress.  */
1017       gdb_assert (adv > 0);
1018     }
1019
1020   /* Update the iterator.  */
1021   it->function = bfun;
1022   it->index = index;
1023
1024   return steps;
1025 }
1026
1027 /* See btrace.h.  */
1028
1029 unsigned int
1030 btrace_insn_prev (struct btrace_insn_iterator *it, unsigned int stride)
1031 {
1032   const struct btrace_function *bfun;
1033   unsigned int index, steps;
1034
1035   bfun = it->function;
1036   steps = 0;
1037   index = it->index;
1038
1039   while (stride != 0)
1040     {
1041       unsigned int adv;
1042
1043       /* Move to the previous function if we're at the start of this one.  */
1044       if (index == 0)
1045         {
1046           const struct btrace_function *prev;
1047
1048           prev = bfun->flow.prev;
1049           if (prev == NULL)
1050             break;
1051
1052           /* We point to one after the last instruction in the new function.  */
1053           bfun = prev;
1054           index = VEC_length (btrace_insn_s, bfun->insn);
1055
1056           /* There is at least one instruction in this function segment.  */
1057           gdb_assert (index > 0);
1058         }
1059
1060       /* Advance the iterator as far as possible within this segment.  */
1061       adv = min (index, stride);
1062       stride -= adv;
1063       index -= adv;
1064       steps += adv;
1065
1066       /* We did make progress.  */
1067       gdb_assert (adv > 0);
1068     }
1069
1070   /* Update the iterator.  */
1071   it->function = bfun;
1072   it->index = index;
1073
1074   return steps;
1075 }
1076
1077 /* See btrace.h.  */
1078
1079 int
1080 btrace_insn_cmp (const struct btrace_insn_iterator *lhs,
1081                  const struct btrace_insn_iterator *rhs)
1082 {
1083   unsigned int lnum, rnum;
1084
1085   lnum = btrace_insn_number (lhs);
1086   rnum = btrace_insn_number (rhs);
1087
1088   return (int) (lnum - rnum);
1089 }
1090
1091 /* See btrace.h.  */
1092
1093 int
1094 btrace_find_insn_by_number (struct btrace_insn_iterator *it,
1095                             const struct btrace_thread_info *btinfo,
1096                             unsigned int number)
1097 {
1098   const struct btrace_function *bfun;
1099   unsigned int end;
1100
1101   for (bfun = btinfo->end; bfun != NULL; bfun = bfun->flow.prev)
1102     if (bfun->insn_offset <= number)
1103       break;
1104
1105   if (bfun == NULL)
1106     return 0;
1107
1108   end = bfun->insn_offset + VEC_length (btrace_insn_s, bfun->insn);
1109   if (end <= number)
1110     return 0;
1111
1112   it->function = bfun;
1113   it->index = number - bfun->insn_offset;
1114
1115   return 1;
1116 }
1117
1118 /* See btrace.h.  */
1119
1120 const struct btrace_function *
1121 btrace_call_get (const struct btrace_call_iterator *it)
1122 {
1123   return it->function;
1124 }
1125
1126 /* See btrace.h.  */
1127
1128 unsigned int
1129 btrace_call_number (const struct btrace_call_iterator *it)
1130 {
1131   const struct btrace_thread_info *btinfo;
1132   const struct btrace_function *bfun;
1133   unsigned int insns;
1134
1135   btinfo = it->btinfo;
1136   bfun = it->function;
1137   if (bfun != NULL)
1138     return bfun->number;
1139
1140   /* For the end iterator, i.e. bfun == NULL, we return one more than the
1141      number of the last function.  */
1142   bfun = btinfo->end;
1143   insns = VEC_length (btrace_insn_s, bfun->insn);
1144
1145   /* If the function contains only a single instruction (i.e. the current
1146      instruction), it will be skipped and its number is already the number
1147      we seek.  */
1148   if (insns == 1)
1149     return bfun->number;
1150
1151   /* Otherwise, return one more than the number of the last function.  */
1152   return bfun->number + 1;
1153 }
1154
1155 /* See btrace.h.  */
1156
1157 void
1158 btrace_call_begin (struct btrace_call_iterator *it,
1159                    const struct btrace_thread_info *btinfo)
1160 {
1161   const struct btrace_function *bfun;
1162
1163   bfun = btinfo->begin;
1164   if (bfun == NULL)
1165     error (_("No trace."));
1166
1167   it->btinfo = btinfo;
1168   it->function = bfun;
1169 }
1170
1171 /* See btrace.h.  */
1172
1173 void
1174 btrace_call_end (struct btrace_call_iterator *it,
1175                  const struct btrace_thread_info *btinfo)
1176 {
1177   const struct btrace_function *bfun;
1178
1179   bfun = btinfo->end;
1180   if (bfun == NULL)
1181     error (_("No trace."));
1182
1183   it->btinfo = btinfo;
1184   it->function = NULL;
1185 }
1186
1187 /* See btrace.h.  */
1188
1189 unsigned int
1190 btrace_call_next (struct btrace_call_iterator *it, unsigned int stride)
1191 {
1192   const struct btrace_function *bfun;
1193   unsigned int steps;
1194
1195   bfun = it->function;
1196   steps = 0;
1197   while (bfun != NULL)
1198     {
1199       const struct btrace_function *next;
1200       unsigned int insns;
1201
1202       next = bfun->flow.next;
1203       if (next == NULL)
1204         {
1205           /* Ignore the last function if it only contains a single
1206              (i.e. the current) instruction.  */
1207           insns = VEC_length (btrace_insn_s, bfun->insn);
1208           if (insns == 1)
1209             steps -= 1;
1210         }
1211
1212       if (stride == steps)
1213         break;
1214
1215       bfun = next;
1216       steps += 1;
1217     }
1218
1219   it->function = bfun;
1220   return steps;
1221 }
1222
1223 /* See btrace.h.  */
1224
1225 unsigned int
1226 btrace_call_prev (struct btrace_call_iterator *it, unsigned int stride)
1227 {
1228   const struct btrace_thread_info *btinfo;
1229   const struct btrace_function *bfun;
1230   unsigned int steps;
1231
1232   bfun = it->function;
1233   steps = 0;
1234
1235   if (bfun == NULL)
1236     {
1237       unsigned int insns;
1238
1239       btinfo = it->btinfo;
1240       bfun = btinfo->end;
1241       if (bfun == NULL)
1242         return 0;
1243
1244       /* Ignore the last function if it only contains a single
1245          (i.e. the current) instruction.  */
1246       insns = VEC_length (btrace_insn_s, bfun->insn);
1247       if (insns == 1)
1248         bfun = bfun->flow.prev;
1249
1250       if (bfun == NULL)
1251         return 0;
1252
1253       steps += 1;
1254     }
1255
1256   while (steps < stride)
1257     {
1258       const struct btrace_function *prev;
1259
1260       prev = bfun->flow.prev;
1261       if (prev == NULL)
1262         break;
1263
1264       bfun = prev;
1265       steps += 1;
1266     }
1267
1268   it->function = bfun;
1269   return steps;
1270 }
1271
1272 /* See btrace.h.  */
1273
1274 int
1275 btrace_call_cmp (const struct btrace_call_iterator *lhs,
1276                  const struct btrace_call_iterator *rhs)
1277 {
1278   unsigned int lnum, rnum;
1279
1280   lnum = btrace_call_number (lhs);
1281   rnum = btrace_call_number (rhs);
1282
1283   return (int) (lnum - rnum);
1284 }
1285
1286 /* See btrace.h.  */
1287
1288 int
1289 btrace_find_call_by_number (struct btrace_call_iterator *it,
1290                             const struct btrace_thread_info *btinfo,
1291                             unsigned int number)
1292 {
1293   const struct btrace_function *bfun;
1294
1295   for (bfun = btinfo->end; bfun != NULL; bfun = bfun->flow.prev)
1296     {
1297       unsigned int bnum;
1298
1299       bnum = bfun->number;
1300       if (number == bnum)
1301         {
1302           it->btinfo = btinfo;
1303           it->function = bfun;
1304           return 1;
1305         }
1306
1307       /* Functions are ordered and numbered consecutively.  We could bail out
1308          earlier.  On the other hand, it is very unlikely that we search for
1309          a nonexistent function.  */
1310   }
1311
1312   return 0;
1313 }
1314
1315 /* See btrace.h.  */
1316
1317 void
1318 btrace_set_insn_history (struct btrace_thread_info *btinfo,
1319                          const struct btrace_insn_iterator *begin,
1320                          const struct btrace_insn_iterator *end)
1321 {
1322   if (btinfo->insn_history == NULL)
1323     btinfo->insn_history = xzalloc (sizeof (*btinfo->insn_history));
1324
1325   btinfo->insn_history->begin = *begin;
1326   btinfo->insn_history->end = *end;
1327 }
1328
1329 /* See btrace.h.  */
1330
1331 void
1332 btrace_set_call_history (struct btrace_thread_info *btinfo,
1333                          const struct btrace_call_iterator *begin,
1334                          const struct btrace_call_iterator *end)
1335 {
1336   gdb_assert (begin->btinfo == end->btinfo);
1337
1338   if (btinfo->call_history == NULL)
1339     btinfo->call_history = xzalloc (sizeof (*btinfo->call_history));
1340
1341   btinfo->call_history->begin = *begin;
1342   btinfo->call_history->end = *end;
1343 }
1344
1345 /* See btrace.h.  */
1346
1347 int
1348 btrace_is_replaying (struct thread_info *tp)
1349 {
1350   return tp->btrace.replay != NULL;
1351 }