record-btrace: start counting at one
[platform/upstream/binutils.git] / 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           level = min (level, end->level);
635
636           ftrace_update_insns (end, pc);
637           ftrace_update_lines (end, pc);
638
639           /* We're done once we pushed the instruction at the end.  */
640           if (block->end == pc)
641             break;
642
643           size = gdb_insn_length (gdbarch, pc);
644
645           /* Make sure we terminate if we fail to compute the size.  */
646           if (size <= 0)
647             {
648               warning (_("Recorded trace may be incomplete around %s."),
649                        core_addr_to_string_nz (pc));
650               break;
651             }
652
653           pc += size;
654         }
655     }
656
657   btinfo->begin = begin;
658   btinfo->end = end;
659
660   /* LEVEL is the minimal function level of all btrace function segments.
661      Define the global level offset to -LEVEL so all function levels are
662      normalized to start at zero.  */
663   btinfo->level = -level;
664 }
665
666 /* See btrace.h.  */
667
668 void
669 btrace_enable (struct thread_info *tp)
670 {
671   if (tp->btrace.target != NULL)
672     return;
673
674   if (!target_supports_btrace ())
675     error (_("Target does not support branch tracing."));
676
677   DEBUG ("enable thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
678
679   tp->btrace.target = target_enable_btrace (tp->ptid);
680 }
681
682 /* See btrace.h.  */
683
684 void
685 btrace_disable (struct thread_info *tp)
686 {
687   struct btrace_thread_info *btp = &tp->btrace;
688   int errcode = 0;
689
690   if (btp->target == NULL)
691     return;
692
693   DEBUG ("disable thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
694
695   target_disable_btrace (btp->target);
696   btp->target = NULL;
697
698   btrace_clear (tp);
699 }
700
701 /* See btrace.h.  */
702
703 void
704 btrace_teardown (struct thread_info *tp)
705 {
706   struct btrace_thread_info *btp = &tp->btrace;
707   int errcode = 0;
708
709   if (btp->target == NULL)
710     return;
711
712   DEBUG ("teardown thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
713
714   target_teardown_btrace (btp->target);
715   btp->target = NULL;
716
717   btrace_clear (tp);
718 }
719
720 /* See btrace.h.  */
721
722 void
723 btrace_fetch (struct thread_info *tp)
724 {
725   struct btrace_thread_info *btinfo;
726   VEC (btrace_block_s) *btrace;
727   struct cleanup *cleanup;
728
729   DEBUG ("fetch thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
730
731   btinfo = &tp->btrace;
732   if (btinfo->target == NULL)
733     return;
734
735   btrace = target_read_btrace (btinfo->target, BTRACE_READ_NEW);
736   cleanup = make_cleanup (VEC_cleanup (btrace_block_s), &btrace);
737
738   if (!VEC_empty (btrace_block_s, btrace))
739     {
740       btrace_clear (tp);
741       btrace_compute_ftrace (btinfo, btrace);
742     }
743
744   do_cleanups (cleanup);
745 }
746
747 /* See btrace.h.  */
748
749 void
750 btrace_clear (struct thread_info *tp)
751 {
752   struct btrace_thread_info *btinfo;
753   struct btrace_function *it, *trash;
754
755   DEBUG ("clear thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
756
757   btinfo = &tp->btrace;
758
759   it = btinfo->begin;
760   while (it != NULL)
761     {
762       trash = it;
763       it = it->flow.next;
764
765       xfree (trash);
766     }
767
768   btinfo->begin = NULL;
769   btinfo->end = NULL;
770
771   xfree (btinfo->insn_history);
772   xfree (btinfo->call_history);
773
774   btinfo->insn_history = NULL;
775   btinfo->call_history = NULL;
776 }
777
778 /* See btrace.h.  */
779
780 void
781 btrace_free_objfile (struct objfile *objfile)
782 {
783   struct thread_info *tp;
784
785   DEBUG ("free objfile");
786
787   ALL_THREADS (tp)
788     btrace_clear (tp);
789 }
790
791 #if defined (HAVE_LIBEXPAT)
792
793 /* Check the btrace document version.  */
794
795 static void
796 check_xml_btrace_version (struct gdb_xml_parser *parser,
797                           const struct gdb_xml_element *element,
798                           void *user_data, VEC (gdb_xml_value_s) *attributes)
799 {
800   const char *version = xml_find_attribute (attributes, "version")->value;
801
802   if (strcmp (version, "1.0") != 0)
803     gdb_xml_error (parser, _("Unsupported btrace version: \"%s\""), version);
804 }
805
806 /* Parse a btrace "block" xml record.  */
807
808 static void
809 parse_xml_btrace_block (struct gdb_xml_parser *parser,
810                         const struct gdb_xml_element *element,
811                         void *user_data, VEC (gdb_xml_value_s) *attributes)
812 {
813   VEC (btrace_block_s) **btrace;
814   struct btrace_block *block;
815   ULONGEST *begin, *end;
816
817   btrace = user_data;
818   block = VEC_safe_push (btrace_block_s, *btrace, NULL);
819
820   begin = xml_find_attribute (attributes, "begin")->value;
821   end = xml_find_attribute (attributes, "end")->value;
822
823   block->begin = *begin;
824   block->end = *end;
825 }
826
827 static const struct gdb_xml_attribute block_attributes[] = {
828   { "begin", GDB_XML_AF_NONE, gdb_xml_parse_attr_ulongest, NULL },
829   { "end", GDB_XML_AF_NONE, gdb_xml_parse_attr_ulongest, NULL },
830   { NULL, GDB_XML_AF_NONE, NULL, NULL }
831 };
832
833 static const struct gdb_xml_attribute btrace_attributes[] = {
834   { "version", GDB_XML_AF_NONE, NULL, NULL },
835   { NULL, GDB_XML_AF_NONE, NULL, NULL }
836 };
837
838 static const struct gdb_xml_element btrace_children[] = {
839   { "block", block_attributes, NULL,
840     GDB_XML_EF_REPEATABLE | GDB_XML_EF_OPTIONAL, parse_xml_btrace_block, NULL },
841   { NULL, NULL, NULL, GDB_XML_EF_NONE, NULL, NULL }
842 };
843
844 static const struct gdb_xml_element btrace_elements[] = {
845   { "btrace", btrace_attributes, btrace_children, GDB_XML_EF_NONE,
846     check_xml_btrace_version, NULL },
847   { NULL, NULL, NULL, GDB_XML_EF_NONE, NULL, NULL }
848 };
849
850 #endif /* defined (HAVE_LIBEXPAT) */
851
852 /* See btrace.h.  */
853
854 VEC (btrace_block_s) *
855 parse_xml_btrace (const char *buffer)
856 {
857   VEC (btrace_block_s) *btrace = NULL;
858   struct cleanup *cleanup;
859   int errcode;
860
861 #if defined (HAVE_LIBEXPAT)
862
863   cleanup = make_cleanup (VEC_cleanup (btrace_block_s), &btrace);
864   errcode = gdb_xml_parse_quick (_("btrace"), "btrace.dtd", btrace_elements,
865                                  buffer, &btrace);
866   if (errcode != 0)
867     {
868       do_cleanups (cleanup);
869       return NULL;
870     }
871
872   /* Keep parse results.  */
873   discard_cleanups (cleanup);
874
875 #else  /* !defined (HAVE_LIBEXPAT) */
876
877   error (_("Cannot process branch trace.  XML parsing is not supported."));
878
879 #endif  /* !defined (HAVE_LIBEXPAT) */
880
881   return btrace;
882 }
883
884 /* See btrace.h.  */
885
886 const struct btrace_insn *
887 btrace_insn_get (const struct btrace_insn_iterator *it)
888 {
889   const struct btrace_function *bfun;
890   unsigned int index, end;
891
892   index = it->index;
893   bfun = it->function;
894
895   /* The index is within the bounds of this function's instruction vector.  */
896   end = VEC_length (btrace_insn_s, bfun->insn);
897   gdb_assert (0 < end);
898   gdb_assert (index < end);
899
900   return VEC_index (btrace_insn_s, bfun->insn, index);
901 }
902
903 /* See btrace.h.  */
904
905 unsigned int
906 btrace_insn_number (const struct btrace_insn_iterator *it)
907 {
908   const struct btrace_function *bfun;
909
910   bfun = it->function;
911   return bfun->insn_offset + it->index;
912 }
913
914 /* See btrace.h.  */
915
916 void
917 btrace_insn_begin (struct btrace_insn_iterator *it,
918                    const struct btrace_thread_info *btinfo)
919 {
920   const struct btrace_function *bfun;
921
922   bfun = btinfo->begin;
923   if (bfun == NULL)
924     error (_("No trace."));
925
926   it->function = bfun;
927   it->index = 0;
928 }
929
930 /* See btrace.h.  */
931
932 void
933 btrace_insn_end (struct btrace_insn_iterator *it,
934                  const struct btrace_thread_info *btinfo)
935 {
936   const struct btrace_function *bfun;
937   unsigned int length;
938
939   bfun = btinfo->end;
940   if (bfun == NULL)
941     error (_("No trace."));
942
943   /* The last instruction in the last function is the current instruction.
944      We point to it - it is one past the end of the execution trace.  */
945   length = VEC_length (btrace_insn_s, bfun->insn);
946
947   it->function = bfun;
948   it->index = length - 1;
949 }
950
951 /* See btrace.h.  */
952
953 unsigned int
954 btrace_insn_next (struct btrace_insn_iterator *it, unsigned int stride)
955 {
956   const struct btrace_function *bfun;
957   unsigned int index, steps;
958
959   bfun = it->function;
960   steps = 0;
961   index = it->index;
962
963   while (stride != 0)
964     {
965       unsigned int end, space, adv;
966
967       end = VEC_length (btrace_insn_s, bfun->insn);
968
969       gdb_assert (0 < end);
970       gdb_assert (index < end);
971
972       /* Compute the number of instructions remaining in this segment.  */
973       space = end - index;
974
975       /* Advance the iterator as far as possible within this segment.  */
976       adv = min (space, stride);
977       stride -= adv;
978       index += adv;
979       steps += adv;
980
981       /* Move to the next function if we're at the end of this one.  */
982       if (index == end)
983         {
984           const struct btrace_function *next;
985
986           next = bfun->flow.next;
987           if (next == NULL)
988             {
989               /* We stepped past the last function.
990
991                  Let's adjust the index to point to the last instruction in
992                  the previous function.  */
993               index -= 1;
994               steps -= 1;
995               break;
996             }
997
998           /* We now point to the first instruction in the new function.  */
999           bfun = next;
1000           index = 0;
1001         }
1002
1003       /* We did make progress.  */
1004       gdb_assert (adv > 0);
1005     }
1006
1007   /* Update the iterator.  */
1008   it->function = bfun;
1009   it->index = index;
1010
1011   return steps;
1012 }
1013
1014 /* See btrace.h.  */
1015
1016 unsigned int
1017 btrace_insn_prev (struct btrace_insn_iterator *it, unsigned int stride)
1018 {
1019   const struct btrace_function *bfun;
1020   unsigned int index, steps;
1021
1022   bfun = it->function;
1023   steps = 0;
1024   index = it->index;
1025
1026   while (stride != 0)
1027     {
1028       unsigned int adv;
1029
1030       /* Move to the previous function if we're at the start of this one.  */
1031       if (index == 0)
1032         {
1033           const struct btrace_function *prev;
1034
1035           prev = bfun->flow.prev;
1036           if (prev == NULL)
1037             break;
1038
1039           /* We point to one after the last instruction in the new function.  */
1040           bfun = prev;
1041           index = VEC_length (btrace_insn_s, bfun->insn);
1042
1043           /* There is at least one instruction in this function segment.  */
1044           gdb_assert (index > 0);
1045         }
1046
1047       /* Advance the iterator as far as possible within this segment.  */
1048       adv = min (index, stride);
1049       stride -= adv;
1050       index -= adv;
1051       steps += adv;
1052
1053       /* We did make progress.  */
1054       gdb_assert (adv > 0);
1055     }
1056
1057   /* Update the iterator.  */
1058   it->function = bfun;
1059   it->index = index;
1060
1061   return steps;
1062 }
1063
1064 /* See btrace.h.  */
1065
1066 int
1067 btrace_insn_cmp (const struct btrace_insn_iterator *lhs,
1068                  const struct btrace_insn_iterator *rhs)
1069 {
1070   unsigned int lnum, rnum;
1071
1072   lnum = btrace_insn_number (lhs);
1073   rnum = btrace_insn_number (rhs);
1074
1075   return (int) (lnum - rnum);
1076 }
1077
1078 /* See btrace.h.  */
1079
1080 int
1081 btrace_find_insn_by_number (struct btrace_insn_iterator *it,
1082                             const struct btrace_thread_info *btinfo,
1083                             unsigned int number)
1084 {
1085   const struct btrace_function *bfun;
1086   unsigned int end;
1087
1088   for (bfun = btinfo->end; bfun != NULL; bfun = bfun->flow.prev)
1089     if (bfun->insn_offset <= number)
1090       break;
1091
1092   if (bfun == NULL)
1093     return 0;
1094
1095   end = bfun->insn_offset + VEC_length (btrace_insn_s, bfun->insn);
1096   if (end <= number)
1097     return 0;
1098
1099   it->function = bfun;
1100   it->index = number - bfun->insn_offset;
1101
1102   return 1;
1103 }
1104
1105 /* See btrace.h.  */
1106
1107 const struct btrace_function *
1108 btrace_call_get (const struct btrace_call_iterator *it)
1109 {
1110   return it->function;
1111 }
1112
1113 /* See btrace.h.  */
1114
1115 unsigned int
1116 btrace_call_number (const struct btrace_call_iterator *it)
1117 {
1118   const struct btrace_thread_info *btinfo;
1119   const struct btrace_function *bfun;
1120   unsigned int insns;
1121
1122   btinfo = it->btinfo;
1123   bfun = it->function;
1124   if (bfun != NULL)
1125     return bfun->number;
1126
1127   /* For the end iterator, i.e. bfun == NULL, we return one more than the
1128      number of the last function.  */
1129   bfun = btinfo->end;
1130   insns = VEC_length (btrace_insn_s, bfun->insn);
1131
1132   /* If the function contains only a single instruction (i.e. the current
1133      instruction), it will be skipped and its number is already the number
1134      we seek.  */
1135   if (insns == 1)
1136     return bfun->number;
1137
1138   /* Otherwise, return one more than the number of the last function.  */
1139   return bfun->number + 1;
1140 }
1141
1142 /* See btrace.h.  */
1143
1144 void
1145 btrace_call_begin (struct btrace_call_iterator *it,
1146                    const struct btrace_thread_info *btinfo)
1147 {
1148   const struct btrace_function *bfun;
1149
1150   bfun = btinfo->begin;
1151   if (bfun == NULL)
1152     error (_("No trace."));
1153
1154   it->btinfo = btinfo;
1155   it->function = bfun;
1156 }
1157
1158 /* See btrace.h.  */
1159
1160 void
1161 btrace_call_end (struct btrace_call_iterator *it,
1162                  const struct btrace_thread_info *btinfo)
1163 {
1164   const struct btrace_function *bfun;
1165
1166   bfun = btinfo->end;
1167   if (bfun == NULL)
1168     error (_("No trace."));
1169
1170   it->btinfo = btinfo;
1171   it->function = NULL;
1172 }
1173
1174 /* See btrace.h.  */
1175
1176 unsigned int
1177 btrace_call_next (struct btrace_call_iterator *it, unsigned int stride)
1178 {
1179   const struct btrace_function *bfun;
1180   unsigned int steps;
1181
1182   bfun = it->function;
1183   steps = 0;
1184   while (bfun != NULL)
1185     {
1186       const struct btrace_function *next;
1187       unsigned int insns;
1188
1189       next = bfun->flow.next;
1190       if (next == NULL)
1191         {
1192           /* Ignore the last function if it only contains a single
1193              (i.e. the current) instruction.  */
1194           insns = VEC_length (btrace_insn_s, bfun->insn);
1195           if (insns == 1)
1196             steps -= 1;
1197         }
1198
1199       if (stride == steps)
1200         break;
1201
1202       bfun = next;
1203       steps += 1;
1204     }
1205
1206   it->function = bfun;
1207   return steps;
1208 }
1209
1210 /* See btrace.h.  */
1211
1212 unsigned int
1213 btrace_call_prev (struct btrace_call_iterator *it, unsigned int stride)
1214 {
1215   const struct btrace_thread_info *btinfo;
1216   const struct btrace_function *bfun;
1217   unsigned int steps;
1218
1219   bfun = it->function;
1220   steps = 0;
1221
1222   if (bfun == NULL)
1223     {
1224       unsigned int insns;
1225
1226       btinfo = it->btinfo;
1227       bfun = btinfo->end;
1228       if (bfun == NULL)
1229         return 0;
1230
1231       /* Ignore the last function if it only contains a single
1232          (i.e. the current) instruction.  */
1233       insns = VEC_length (btrace_insn_s, bfun->insn);
1234       if (insns == 1)
1235         bfun = bfun->flow.prev;
1236
1237       if (bfun == NULL)
1238         return 0;
1239
1240       steps += 1;
1241     }
1242
1243   while (steps < stride)
1244     {
1245       const struct btrace_function *prev;
1246
1247       prev = bfun->flow.prev;
1248       if (prev == NULL)
1249         break;
1250
1251       bfun = prev;
1252       steps += 1;
1253     }
1254
1255   it->function = bfun;
1256   return steps;
1257 }
1258
1259 /* See btrace.h.  */
1260
1261 int
1262 btrace_call_cmp (const struct btrace_call_iterator *lhs,
1263                  const struct btrace_call_iterator *rhs)
1264 {
1265   unsigned int lnum, rnum;
1266
1267   lnum = btrace_call_number (lhs);
1268   rnum = btrace_call_number (rhs);
1269
1270   return (int) (lnum - rnum);
1271 }
1272
1273 /* See btrace.h.  */
1274
1275 int
1276 btrace_find_call_by_number (struct btrace_call_iterator *it,
1277                             const struct btrace_thread_info *btinfo,
1278                             unsigned int number)
1279 {
1280   const struct btrace_function *bfun;
1281
1282   for (bfun = btinfo->end; bfun != NULL; bfun = bfun->flow.prev)
1283     {
1284       unsigned int bnum;
1285
1286       bnum = bfun->number;
1287       if (number == bnum)
1288         {
1289           it->btinfo = btinfo;
1290           it->function = bfun;
1291           return 1;
1292         }
1293
1294       /* Functions are ordered and numbered consecutively.  We could bail out
1295          earlier.  On the other hand, it is very unlikely that we search for
1296          a nonexistent function.  */
1297   }
1298
1299   return 0;
1300 }
1301
1302 /* See btrace.h.  */
1303
1304 void
1305 btrace_set_insn_history (struct btrace_thread_info *btinfo,
1306                          const struct btrace_insn_iterator *begin,
1307                          const struct btrace_insn_iterator *end)
1308 {
1309   if (btinfo->insn_history == NULL)
1310     btinfo->insn_history = xzalloc (sizeof (*btinfo->insn_history));
1311
1312   btinfo->insn_history->begin = *begin;
1313   btinfo->insn_history->end = *end;
1314 }
1315
1316 /* See btrace.h.  */
1317
1318 void
1319 btrace_set_call_history (struct btrace_thread_info *btinfo,
1320                          const struct btrace_call_iterator *begin,
1321                          const struct btrace_call_iterator *end)
1322 {
1323   gdb_assert (begin->btinfo == end->btinfo);
1324
1325   if (btinfo->call_history == NULL)
1326     btinfo->call_history = xzalloc (sizeof (*btinfo->call_history));
1327
1328   btinfo->call_history->begin = *begin;
1329   btinfo->call_history->end = *end;
1330 }