This is the mail archive of the
gdb-patches@sourceware.org
mailing list for the GDB project.
Re: [PATCH 02/15] btrace: change branch trace data structure
- From: Jan Kratochvil <jan dot kratochvil at redhat dot com>
- To: Markus Metzger <markus dot t dot metzger at intel dot com>
- Cc: gdb-patches at sourceware dot org, Christian Himpel <christian dot himpel at intel dot com>
- Date: Mon, 13 May 2013 17:24:50 +0200
- Subject: Re: [PATCH 02/15] btrace: change branch trace data structure
- References: <1367496216-21217-1-git-send-email-markus dot t dot metzger at intel dot com> <1367496216-21217-3-git-send-email-markus dot t dot metzger at intel dot com>
Hi Markus,
as mailed off-list you have an updated version so sending only a partial
review as I have done so far.
Thanks,
Jan
On Thu, 02 May 2013 14:03:23 +0200, Markus Metzger wrote:
> --- a/gdb/btrace.c
> +++ b/gdb/btrace.c
[...]
> -/* Initialize a recorded function segment. */
> +/* Print an ftrace debug status message. */
>
> static void
> -ftrace_init_func (struct btrace_func *bfun, struct minimal_symbol *mfun,
> - struct symbol *fun, unsigned int idx)
> +ftrace_debug (const struct btrace_function *bfun, const char *prefix)
> {
> - bfun->msym = mfun;
> - bfun->sym = fun;
> - bfun->lbegin = INT_MAX;
> - bfun->lend = 0;
> - bfun->ibegin = idx;
> - bfun->iend = idx;
> + const char *fun, *file;
> + unsigned int ibegin, iend;
> + int lbegin, lend, level;
> +
> + fun = ftrace_print_function_name (bfun);
> + file = ftrace_print_filename (bfun);
> + level = bfun->level;
> +
> + lbegin = bfun->lbegin;
> + lend = bfun->lend;
> +
> + ibegin = bfun->insn_offset;
> + iend = ibegin + VEC_length (btrace_insn_s, bfun->insn);
> +
> + DEBUG_FTRACE ("%s: fun = %s, file = %s, level = %d, lines = [%d; %d], "
> + "insn = [%u; %u)", prefix, fun, file, level, lbegin, lend,
> + ibegin, iend);
> }
>
> /* Check whether the function has changed. */
+ /* Return 1 if BFUN does not match MFUN and FUN, return 0 if they match. */
>
> static int
> -ftrace_function_switched (struct btrace_func *bfun,
> - struct minimal_symbol *mfun, struct symbol *fun)
> +ftrace_function_switched (const struct btrace_function *bfun,
> + const struct minimal_symbol *mfun,
> + const struct symbol *fun)
> {
> struct minimal_symbol *msym;
> struct symbol *sym;
>
> - /* The function changed if we did not have one before. */
> - if (bfun == NULL)
> - return 1;
> -
> msym = bfun->msym;
> sym = bfun->sym;
>
> @@ -228,6 +155,14 @@ ftrace_function_switched (struct btrace_func *bfun,
> return 1;
> }
>
> + /* If we lost symbol information, we switched functions. */
> + if (!(msym == NULL && sym == NULL) && mfun == NULL && fun == NULL)
> + return 1;
> +
> + /* If we gained symbol information, we switched functions. */
> + if (msym == NULL && sym == NULL && !(mfun == NULL && fun == NULL))
> + return 1;
> +
> return 0;
> }
>
> @@ -236,7 +171,7 @@ ftrace_function_switched (struct btrace_func *bfun,
> in another file is expanded in this function. */
>
> static int
> -ftrace_skip_file (struct btrace_func *bfun, const char *filename)
> +ftrace_skip_file (const struct btrace_function *bfun, const char *filename)
It was already there such way but please rename the parameter to "fullname",
it should be used together with symtab_to_fullname and not with
symtab_to_filename_for_display.
> {
> struct symbol *sym;
> const char *bfile;
> @@ -254,83 +189,458 @@ ftrace_skip_file (struct btrace_func *bfun, const char *filename)
> return (filename_cmp (bfile, filename) != 0);
> }
>
> -/* Compute the function trace from the instruction trace. */
> +/* Allocate and initialize a new branch trace function segment. */
Something like:
+/* If both FUN and MFUN are NULL it is marker of the end of trace. */
>
> -static VEC (btrace_func_s) *
> -compute_ftrace (VEC (btrace_inst_s) *itrace)
> +static struct btrace_function *
> +ftrace_new_function (struct btrace_function *prev,
> + struct minimal_symbol *mfun,
> + struct symbol *fun)
> {
> - VEC (btrace_func_s) *ftrace;
> - struct btrace_inst *binst;
> - struct btrace_func *bfun;
> - unsigned int idx;
> + struct btrace_function *bfun;
>
> - DEBUG ("compute ftrace");
> + bfun = xzalloc (sizeof (*bfun));
>
> - ftrace = NULL;
> - bfun = NULL;
> + bfun->msym = mfun;
> + bfun->sym = fun;
bfun->msym == NULL && bfun->sym == NULL is not allowed according to the
comments in struct btrace_function. It should be gdb_assert-ed here.
> + bfun->lbegin = INT_MAX;
It would be nice to comment here or at LBEGIN what does INT_MAX mean for it.
> + bfun->flow.prev = prev;
>
> - for (idx = 0; VEC_iterate (btrace_inst_s, itrace, idx, binst); ++idx)
> + if (prev != NULL)
> {
> - struct symtab_and_line sal;
> - struct bound_minimal_symbol mfun;
> - struct symbol *fun;
> - const char *filename;
> + gdb_assert (prev->flow.next == NULL);
> + prev->flow.next = bfun;
> +
> + bfun->number = prev->number + 1;
> + bfun->insn_offset = prev->insn_offset
> + + VEC_length (btrace_insn_s, prev->insn);
GNU Coding Standards require multi-line expressions to use parentheses,
therefore:
bfun->insn_offset = (prev->insn_offset
+ VEC_length (btrace_insn_s, prev->insn));
> + }
> +
> + return bfun;
> +}
> +
> +/* Update the UP field of a function segment. */
> +
> +static void
> +ftrace_update_caller (struct btrace_function *bfun,
> + struct btrace_function *caller)
> +{
> + if (bfun->up != NULL)
> + ftrace_debug (bfun, "updating caller");
> +
> + bfun->up = caller;
> +
> + ftrace_debug (bfun, "set caller");
> +}
> +
> +/* Fix up the caller for a function segment. */
> +
> +static void
> +ftrace_fixup_caller (struct btrace_function *bfun,
> + struct btrace_function *caller)
> +{
> + struct btrace_function *prev, *next;
> +
> + ftrace_update_caller (bfun, caller);
> +
> + /* Update all function segments belonging to the same function. */
> + for (prev = bfun->segment.prev; prev != NULL; prev = prev->segment.prev)
> + ftrace_update_caller (prev, caller);
> +
> + for (next = bfun->segment.next; next != NULL; next = next->segment.next)
> + ftrace_update_caller (next, caller);
> +}
> +
> +/* Add a new function segment for a call. */
> +
> +static struct btrace_function *
> +ftrace_new_call (struct btrace_function *caller,
> + struct minimal_symbol *mfun,
> + struct symbol *fun)
> +{
> + struct btrace_function *bfun;
> +
> + bfun = ftrace_new_function (caller, mfun, fun);
> + bfun->up = caller;
> + bfun->level = caller->level + 1;
> +
> + ftrace_debug (bfun, "new call");
> +
> + return bfun;
> +}
> +
> +/* Add a new function segment for a tail call. */
> +
> +static struct btrace_function *
> +ftrace_new_tailcall (struct btrace_function *caller,
> + struct minimal_symbol *mfun,
> + struct symbol *fun)
> +{
> + struct btrace_function *bfun;
> +
> + bfun = ftrace_new_function (caller, mfun, fun);
> + bfun->up = caller;
> + bfun->level = caller->level + 1;
> + bfun->flags |= bfun_up_links_to_tailcall;
> +
> + ftrace_debug (bfun, "new tail call");
> +
> + return bfun;
> +}
> +
> +/* Find the caller of BFUN.
> + This is the first function segment up the call stack from BFUN with
> + MFUN/FUN symbol information. */
Maybe if you find appropriate:
+ /* Try to find chronologically previous execution segment of the MFUN/FUN
function before the MFUN/FUN function did call BFUN. */
> +
> +static struct btrace_function *
> +ftrace_find_caller (struct btrace_function *bfun,
> + struct minimal_symbol *mfun,
> + struct symbol *fun)
> +{
> + for (; bfun != NULL; bfun = bfun->up)
> + {
> + /* Skip functions with incompatible symbol information. */
> + if (ftrace_function_switched (bfun, mfun, fun))
> + continue;
> +
> + /* This is the function segment we're looking for. */
> + break;
> + }
> +
> + return bfun;
> +}
> +
> +/* Find the last actual call in the back trace of BFUN. */
+ /* Generally skip any segments ending just with a jump. */
> +
> +static struct btrace_function *
> +ftrace_find_call (struct gdbarch *gdbarch, struct btrace_function *bfun)
> +{
> + if (!gdbarch_insn_call_p_p (gdbarch))
> + return NULL;
> +
> + for (; bfun != NULL; bfun = bfun->up)
> + {
> + struct btrace_insn *last;
> CORE_ADDR pc;
>
> - pc = binst->pc;
> + if (VEC_empty (btrace_insn_s, bfun->insn))
> + continue;
Shouldn't here be rather "return NULL" instead of continue? I do not
understand in which cases BFUN->INSN can be empty. Empty INSN case could be
also described in btrace_function->insn.
> +
> + last = VEC_last (btrace_insn_s, bfun->insn);
> + pc = last->pc;
> +
> + if (gdbarch_insn_call_p (gdbarch, pc))
> + break;
> + }
> +
> + return bfun;
> +}
> +
> +/* Add a new function segment for a return. */
It needs to comment the meaning of PREV, MFUN and FUN.
I was also missing here description of what this function does, not sure if
maybe helpful:
+ /* Connect the new execution segment BFUN with the previously executing
segment of the same function at the same caller level. */
> +
> +static struct btrace_function *
> +ftrace_new_return (struct gdbarch *gdbarch,
> + struct btrace_function *prev,
> + struct minimal_symbol *mfun,
> + struct symbol *fun)
> +{
> + struct btrace_function *bfun, *caller;
> +
> + bfun = ftrace_new_function (prev, mfun, fun);
> +
> + /* It is important to start at PREV's caller. Otherwise, we might find
> + PREV itself, if PREV is a recursive function. */
> + caller = ftrace_find_caller (prev->up, mfun, fun);
> + if (caller != NULL)
> + {
> + /* The caller of PREV is the preceding btrace function segment in this
> + function instance. */
> + gdb_assert (caller->segment.next == NULL);
> +
> + caller->segment.next = bfun;
> + bfun->segment.prev = caller;
> +
> + /* Maintain the function level. */
> + bfun->level = caller->level;
>
> - /* Try to determine the function we're in. We use both types of symbols
> - to avoid surprises when we sometimes get a full symbol and sometimes
> - only a minimal symbol. */
> - fun = find_pc_function (pc);
> - mfun = lookup_minimal_symbol_by_pc (pc);
> + /* Maintain the call stack. */
> + bfun->up = caller->up;
>
> - if (fun == NULL && mfun.minsym == NULL)
> + ftrace_debug (bfun, "new return");
> + }
> + else
> + {
> + /* We did not find a caller. This could mean that something went
> + wrong or that the call is simply not included in the trace. */
> +
> + /* Let's search for some actual call. */
> + caller = ftrace_find_call (gdbarch, prev->up);
> + if (caller == NULL)
> {
> - DEBUG_FTRACE ("no symbol at %u, pc=%s", idx,
> - core_addr_to_string_nz (pc));
> - continue;
> - }
> + /* There is no call in PREV's back trace. We assume that the
> + branch trace did not include it. */
> +
> + /* Let's find the topmost call function - this skips tail calls. */
> + while (prev->up != NULL)
> + prev = prev->up;
>
> - /* If we're switching functions, we start over. */
> - if (ftrace_function_switched (bfun, mfun.minsym, fun))
> + /* We maintain levels for a series of returns for which we have
> + not seen the calls, but we restart at level 0, otherwise. */
> + bfun->level = min (0, prev->level) - 1;
> +
> + /* Fix up the call stack for PREV. */
> + ftrace_fixup_caller (prev, bfun);
> + prev->flags |= bfun_up_links_to_ret;
> +
> + ftrace_debug (bfun, "new return - no caller");
> + }
> + else
> {
> - bfun = VEC_safe_push (btrace_func_s, ftrace, NULL);
> + /* There is a call in PREV's back trace to which we should have
> + returned. Let's remain at this level. */
> + bfun->level = prev->level;
>
> - ftrace_init_func (bfun, mfun.minsym, fun, idx);
> - ftrace_debug (bfun, "init");
> + ftrace_debug (bfun, "new return - unknown caller");
> }
> + }
> +
> + return bfun;
> +}
> +
> +/* Add a new function segment for a function switch. */
Describe what is "switch" and its relationhsip to MFUN/FUN.
Drop unused parameter INSN.
> +
> +static struct btrace_function *
> +ftrace_new_switch (struct btrace_function *prev,
> + struct minimal_symbol *mfun,
> + struct symbol *fun,
> + const struct btrace_insn *insn)
> +{
> + struct btrace_function *bfun;
> +
> + /* This is an unexplained function switch. The call stack will likely
> + be wrong at this point. */
> + bfun = ftrace_new_function (prev, mfun, fun);
> +
> + /* We keep the function level. */
> + bfun->level = prev->level;
> +
> + ftrace_debug (bfun, "new switch");
>
> - /* Update the instruction range. */
> - bfun->iend = idx;
> - ftrace_debug (bfun, "update insns");
> + return bfun;
> +}
> +
> +/* Update the branch trace function segment. Never returns NULL. */
What is the meaning of BFUN and PC? What and why does it update?
I would also call it more like "add", it creates new records.
> +
> +static struct btrace_function *
> +ftrace_update_function (struct gdbarch *gdbarch,
> + struct btrace_function *bfun, CORE_ADDR pc)
> +{
> + struct bound_minimal_symbol bmfun;
> + struct minimal_symbol *mfun;
> + struct symbol *fun;
> + struct btrace_insn *last;
> +
> + /* Try to determine the function we're in. We use both types of symbols
> + to avoid surprises when we sometimes get a full symbol and sometimes
> + only a minimal symbol. */
> + fun = find_pc_function (pc);
> + bmfun = lookup_minimal_symbol_by_pc (pc);
> + mfun = bmfun.minsym;
> +
> + if (fun == NULL && mfun == NULL)
> + DEBUG_FTRACE ("no symbol at %s", core_addr_to_string_nz (pc));
> +
> + /* If we didn't have a function before, we create one. */
> + if (bfun == NULL)
> + return ftrace_new_function (bfun, mfun, fun);
mfun == NULL && fun == NULL is not allowed according to the comments in struct
btrace_function. Already suggested gdb_assert for ftrace_new_function but it
seems it may happen here.
> +
> + /* Check the last instruction, if we have one.
> + We do this check first, since it allows us to fill in the call stack
> + links in addition to the normal flow links. */
> + last = NULL;
> + if (!VEC_empty (btrace_insn_s, bfun->insn))
> + last = VEC_last (btrace_insn_s, bfun->insn);
>
> - /* Let's see if we have source correlation, as well. */
> - sal = find_pc_line (pc, 0);
> - if (sal.symtab == NULL || sal.line == 0)
> + if (last != NULL)
This conditional is excessive, it is true iff !VEC_empty is true above.
> + {
> + CORE_ADDR lpc;
> +
> + lpc = last->pc;
> +
> + /* Check for returns. */
> + if (gdbarch_insn_ret_p_p (gdbarch) && gdbarch_insn_ret_p (gdbarch, lpc))
> + return ftrace_new_return (gdbarch, bfun, mfun, fun);
> +
> + /* Check for calls. */
> + if (gdbarch_insn_call_p_p (gdbarch) && gdbarch_insn_call_p (gdbarch, lpc))
> {
> - DEBUG_FTRACE ("no lines at %u, pc=%s", idx,
> - core_addr_to_string_nz (pc));
> - continue;
> + int size;
> +
> + size = gdb_insn_length (gdbarch, lpc);
> +
> + /* Ignore calls to the next instruction. They are used for PIC. */
> + if (lpc + size != pc)
> + return ftrace_new_call (bfun, mfun, fun);
> }
> + }
> +
> + /* Check if we're switching functions for some other reason. */
> + if (ftrace_function_switched (bfun, mfun, fun))
> + {
> + DEBUG_FTRACE ("switching from %s in %s at %s",
> + ftrace_print_insn_addr (last),
> + ftrace_print_function_name (bfun),
> + ftrace_print_filename (bfun));
>
> - /* Check if we switched files. This could happen if, say, a macro that
> - is defined in another file is expanded here. */
> - filename = symtab_to_fullname (sal.symtab);
> - if (ftrace_skip_file (bfun, filename))
> + if (last != NULL)
> {
> - DEBUG_FTRACE ("ignoring file at %u, pc=%s, file=%s", idx,
> - core_addr_to_string_nz (pc), filename);
> - continue;
> + CORE_ADDR start, lpc;
> +
> + /* If we have symbol information for our current location, use
> + it to check that we jump to the start of a function. */
> + if (fun != NULL || mfun != NULL)
> + start = get_pc_function_start (pc);
> + else
> + start = pc;
This goes into implementation detail of get_pc_function_start. Rather always
call get_pc_function_start but one should check if it failed anyway
- get_pc_function_start returns 0 if it has failed.
Or was the 'fun != NULL || mfun != NULL' check there for performance reasons?
> +
> + lpc = last->pc;
> +
> + /* Jumps indicate optimized tail calls. */
> + if (start == pc
> + && gdbarch_insn_jump_p_p (gdbarch)
> + && gdbarch_insn_jump_p (gdbarch, lpc))
> + return ftrace_new_tailcall (bfun, mfun, fun);
Cannot a plain intra-function jump be confused into a tailcall due to
a tripped binary? FUN and MFUN are NULL for stripped binary,
therefore "start = pc;" gets assigned above, which will call
ftrace_new_tailcall. I did not try to reproduce it, though.
> }
>
> - /* Update the line range. */
> - bfun->lbegin = min (bfun->lbegin, sal.line);
> - bfun->lend = max (bfun->lend, sal.line);
> - ftrace_debug (bfun, "update lines");
> + return ftrace_new_switch (bfun, mfun, fun, last);
> + }
> +
> + return bfun;
> +}
> +
> +/* Update the source correlation for a branch trace function segment. */
> +
> +static void
> +ftrace_update_lines (struct btrace_function *bfun, CORE_ADDR pc)
> +{
> + struct symtab_and_line sal;
> + const char *filename;
Please rename the variable to "fullname", it should be used together with
symtab_to_fullname and not with symtab_to_filename_for_display.
> +
> + sal = find_pc_line (pc, 0);
> + if (sal.symtab == NULL || sal.line == 0)
> + {
> + DEBUG_FTRACE ("no lines at %s", core_addr_to_string_nz (pc));
> + return;
> + }
> +
> + /* Check if we switched files. This could happen if, say, a macro that
> + is defined in another file is expanded here. */
> + filename = symtab_to_fullname (sal.symtab);
> + if (ftrace_skip_file (bfun, filename))
> + {
> + DEBUG_FTRACE ("ignoring file at %s, file=%s",
> + core_addr_to_string_nz (pc), filename);
> + return;
> }
>
> - return ftrace;
> + /* Update the line range. */
> + bfun->lbegin = min (bfun->lbegin, sal.line);
> + bfun->lend = max (bfun->lend, sal.line);
> +
> + if (record_debug > 1)
> + ftrace_debug (bfun, "update lines");
> +}
> +
> +/* Update the instructions for a branch trace function segment. */
It is more appropriate to call it "add", "append" or similar.
> +
> +static void
> +ftrace_update_insns (struct btrace_function *bfun, CORE_ADDR pc)
> +{
> + struct btrace_insn *insn;
> +
> + insn = VEC_safe_push (btrace_insn_s, bfun->insn, NULL);
> + insn->pc = pc;
> +
> + if (record_debug > 1)
> + ftrace_debug (bfun, "update insn");
> +}
> +
> +/* Compute the function branch trace. */
Describe the parameters.
> +
> +static void
> +btrace_compute_ftrace (struct btrace_thread_info *btinfo,
> + VEC (btrace_block_s) *btrace)
> +{
> + struct btrace_function *begin, *end;
> + struct gdbarch *gdbarch;
> + unsigned int blk;
> + int level;
> +
> + DEBUG ("compute ftrace");
> +
> + gdbarch = target_gdbarch ();
> + begin = NULL;
> + end = NULL;
> + level = INT_MAX;
> + blk = VEC_length (btrace_block_s, btrace);
> +
> + while (blk != 0)
> + {
> + btrace_block_s *block;
> + CORE_ADDR pc;
> +
> + blk -= 1;
> +
> + block = VEC_index (btrace_block_s, btrace, blk);
> + pc = block->begin;
> +
> + for (;;)
> + {
> + int size;
> +
> + /* We should hit the end of the block. Warn if we went too far. */
> + if (block->end < pc)
> + {
> + warning (_("Recorded trace may be corrupted."));
One could also print BEGIN and END to be more suggestive what could break.
> + break;
> + }
> +
> + end = ftrace_update_function (gdbarch, end, pc);
> + if (begin == NULL)
> + begin = end;
> +
> + /* Maintain the function level offset. */
> + level = min (level, end->level);
> +
> + ftrace_update_insns (end, pc);
> + ftrace_update_lines (end, pc);
> +
> + /* We're done once we pushed the instruction at the end. */
> + if (block->end == pc)
> + break;
> +
> + size = gdb_insn_length (gdbarch, pc);
> +
> + /* Make sure we terminate if we fail to compute the size. */
> + if (size <= 0)
> + {
> + warning (_("Recorded trace may be incomplete."));
One could also print PC to be more suggestive what could break.
> + break;
> + }
> +
> + pc += size;
> + }
> + }
> +
> + /* Add an empty dummy function to mark the end of the branch trace. */
> + end = ftrace_new_function (end, NULL, NULL);
> +
> + btinfo->begin = begin;
> + btinfo->end = end;
> +
> + /* LEVEL is the minimal function level of all btrace function segments.
> + Define the global level offset to -LEVEL so all function levels are
> + normalized to start at zero. */
> + btinfo->level = -level;
> }
>
> /* See btrace.h. */
> @@ -394,6 +704,7 @@ btrace_fetch (struct thread_info *tp)
> {
> struct btrace_thread_info *btinfo;
> VEC (btrace_block_s) *btrace;
> + struct cleanup *cleanup;
>
> DEBUG ("fetch thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
>
> @@ -402,18 +713,15 @@ btrace_fetch (struct thread_info *tp)
> return;
>
> btrace = target_read_btrace (btinfo->target, btrace_read_new);
> - if (VEC_empty (btrace_block_s, btrace))
> - return;
> -
> - btrace_clear (tp);
> + cleanup = make_cleanup (VEC_cleanup (btrace_block_s), &btrace);
>
> - btinfo->btrace = btrace;
> - btinfo->itrace = compute_itrace (btinfo->btrace);
> - btinfo->ftrace = compute_ftrace (btinfo->itrace);
> + if (!VEC_empty (btrace_block_s, btrace))
> + {
> + btrace_clear (tp);
> + btrace_compute_ftrace (btinfo, btrace);
> + }
If BTRACE is empty shouldn't TP's btrace be still cleared?
>
> - /* Initialize branch trace iterators. */
> - btrace_init_insn_iterator (btinfo);
> - btrace_init_func_iterator (btinfo);
> + do_cleanups (cleanup);
> }
>
> /* See btrace.h. */
> @@ -422,18 +730,29 @@ void
> btrace_clear (struct thread_info *tp)
> {
> struct btrace_thread_info *btinfo;
> + struct btrace_function *it, *trash;
>
> DEBUG ("clear thread %d (%s)", tp->num, target_pid_to_str (tp->ptid));
>
> btinfo = &tp->btrace;
>
> - VEC_free (btrace_block_s, btinfo->btrace);
> - VEC_free (btrace_inst_s, btinfo->itrace);
> - VEC_free (btrace_func_s, btinfo->ftrace);
> + it = btinfo->begin;
> + while (it != NULL)
> + {
> + trash = it;
> + it = it->flow.next;
> +
> + xfree (trash);
> + }
> +
> + btinfo->begin = NULL;
> + btinfo->end = NULL;
>
> - btinfo->btrace = NULL;
> - btinfo->itrace = NULL;
> - btinfo->ftrace = NULL;
> + xfree (btinfo->insn_history);
> + xfree (btinfo->call_history);
> +
> + btinfo->insn_history = NULL;
> + btinfo->call_history = NULL;
> }
>
> /* See btrace.h. */
> @@ -541,3 +860,301 @@ parse_xml_btrace (const char *buffer)
>
> return btrace;
> }
> +
> +/* See btrace.h. */
> +
> +const struct btrace_insn *
> +btrace_insn_get (const struct btrace_insn_iterator *it)
> +{
> + struct btrace_function *function;
> + unsigned int index, end;
> +
> + if (it == NULL)
> + return NULL;
> +
> + index = it->index;
> + function = it->function;
> + if (function == NULL)
> + return NULL;
> +
> + end = VEC_length (btrace_insn_s, function->insn);
> + if (end == 0)
> + return NULL;
> +
> + gdb_assert (index < end);
> +
> + return VEC_index (btrace_insn_s, function->insn, index);
> +}
> +
> +/* See btrace.h. */
> +
> +unsigned int
> +btrace_insn_number (const struct btrace_insn_iterator *it)
> +{
> + struct btrace_function *function;
> +
> + if (it == NULL)
> + return 0;
> +
> + function = it->function;
> + if (function == NULL)
> + return 0;
> +
> + return function->insn_offset + it->index;
> +}
> +
> +/* See btrace.h. */
> +
> +void
> +btrace_insn_begin (struct btrace_insn_iterator *it,
> + struct btrace_thread_info *btinfo)
> +{
> + struct btrace_function *begin;
> +
> + begin = btinfo->begin;
> + if (begin == NULL)
> + error (_("No trace."));
> +
> + it->function = begin;
> + it->index = 0;
> +}
> +
> +/* See btrace.h. */
> +
> +void
> +btrace_insn_end (struct btrace_insn_iterator *it,
> + struct btrace_thread_info *btinfo)
> +{
> + struct btrace_function *end;
> +
> + end = btinfo->end;
> + if (end == NULL)
> + error (_("No trace."));
> +
> + /* The last function is an empty dummy. */
> + it->function = end;
> + it->index = 0;
> +}
> +
> +/* See btrace.h. */
> +
> +unsigned int
> +btrace_insn_next (struct btrace_insn_iterator * it, unsigned int stride)
> +{
> + struct btrace_function *function;
> + unsigned int index, end, space, adv, steps;
Some of the declarations like 'end' and 'adv' can be moved to the more inner
block.
> +
> + if (it == NULL)
> + return 0;
> +
> + function = it->function;
> + if (function == NULL)
> + return 0;
> +
> + steps = 0;
> + index = it->index;
> +
> + while (stride != 0)
> + {
> + end = VEC_length (btrace_insn_s, function->insn);
> +
> + /* Compute the number of instructions remaining in this segment. */
> + gdb_assert ((end == 0 && index == 0) || index < end);
> + space = end - index;
> +
> + /* Advance the iterator as far as possible within this segment. */
> + adv = min (space, stride);
> + stride -= adv;
> + index += adv;
> + steps += adv;
> +
> + /* Move to the next function if we're at the end of this one. */
> + if (index == end)
> + {
> + struct btrace_function *next;
> +
> + next = function->flow.next;
> + if (next == NULL)
> + {
> + /* We stepped past the last function - an empty dummy. */
> + gdb_assert (adv == 0);
> + break;
> + }
> +
> + /* We now point to the first instruction in the new function. */
> + function = next;
> + index = 0;
> + }
> +
> + /* We did make progress. */
> + gdb_assert (adv > 0);
> + }
> +
> + /* Update the iterator. */
> + it->function = function;
> + it->index = index;
> +
> + return steps;
> +}
> +
> +/* See btrace.h. */
> +
> +unsigned int
> +btrace_insn_prev (struct btrace_insn_iterator * it, unsigned int stride)
> +{
> + struct btrace_function *function;
> + unsigned int index, adv, steps;
Some of the declarations like 'end' and 'adv' can be moved to the more inner
block.
> +
> + if (it == NULL)
> + return 0;
> +
> + function = it->function;
> + if (function == NULL)
> + return 0;
> +
> + steps = 0;
> + index = it->index;
> +
> + while (stride != 0)
> + {
> + /* Move to the previous function if we're at the start of this one. */
> + if (index == 0)
> + {
> + struct btrace_function *prev;
> +
> + prev = function->flow.prev;
> + if (prev == NULL)
> + break;
> +
> + /* We point to one after the last instruction in the new function. */
> + function = prev;
> + index = VEC_length (btrace_insn_s, function->insn);
> +
> + /* There is at least one instruction in this function segment. */
> + gdb_assert (index > 0);
> + }
> +
> + /* Advance the iterator as far as possible within this segment. */
> + adv = min (index, stride);
> + stride -= adv;
> + index -= adv;
> + steps += adv;
> +
> + /* We did make progress. */
> + gdb_assert (adv > 0);
> + }
> +
> + /* Update the iterator. */
> + it->function = function;
> + it->index = index;
> +
> + return steps;
> +}
> +
> +/* See btrace.h. */
> +
> +int
> +btrace_insn_cmp (const struct btrace_insn_iterator *lhs,
> + const struct btrace_insn_iterator *rhs)
> +{
> + unsigned int lnum, rnum;
> +
> + lnum = btrace_insn_number (lhs);
> + rnum = btrace_insn_number (rhs);
> +
> + return (int) (lnum - rnum);
> +}
> +
> +/* See btrace.h. */
> +
> +int
> +btrace_find_insn_by_number (struct btrace_insn_iterator *it,
> + const struct btrace_thread_info *btinfo,
> + unsigned int number)
> +{
> + struct btrace_function *bfun;
> + unsigned int last;
> +
> + for (bfun = btinfo->end; bfun != NULL; bfun = bfun->flow.prev)
> + if (bfun->insn_offset <= number)
> + break;
> +
> + if (bfun == NULL)
> + return 0;
> +
> + last = bfun->insn_offset + VEC_length (btrace_insn_s, bfun->insn);
I do not find 'last' as a right name, the number is right after the last
element.
> + if (last <= number)
> + return 0;
> +
> + it->function = bfun;
> + it->index = number - bfun->insn_offset;
> +
> + return 1;
> +}
> +
> +/* See btrace.h. */
> +
> +struct btrace_function *
> +btrace_find_function_by_number (const struct btrace_thread_info *btinfo,
> + unsigned int number)
> +{
> + struct btrace_function *bfun;
> +
> + if (btinfo == NULL)
> + return NULL;
> +
> + for (bfun = btinfo->end; bfun != NULL; bfun = bfun->flow.prev)
> + {
> + unsigned int bnum;
> +
> + bnum = bfun->number;
> + if (number == bnum)
> + return bfun;
> +
> + /* Functions are ordered and numbered consecutively. We could bail out
> + earlier. On the other hand, it is very unlikely that we search for
> + a nonexistent function. */
> + }
> +
> + return NULL;
> +}
> +
> +/* See btrace.h. */
> +
> +void
> +btrace_set_insn_history (struct btrace_thread_info *btinfo,
> + struct btrace_insn_iterator *begin,
> + struct btrace_insn_iterator *end)
> +{
> + struct btrace_insn_history *history;
> +
> + history = btinfo->insn_history;
> + if (history == NULL)
> + {
> + history = xzalloc (sizeof (*history));
> + btinfo->insn_history = history;
> + }
This seems slightly prone to errors to me, why not:
if (btinfo->insn_history == NULL)
btinfo->insn_history = xzalloc (sizeof (*btinfo->insn_history));
history = btinfo->insn_history;
> +
> + history->begin = *begin;
> + history->end = *end;
> +}
> +
> +/* See btrace.h. */
> +
> +void
> +btrace_set_call_history (struct btrace_thread_info *btinfo,
> + struct btrace_function *begin,
> + struct btrace_function *end)
> +{
> + struct btrace_call_history *history;
> +
> + history = btinfo->call_history;
> + if (history == NULL)
> + {
> + history = xzalloc (sizeof (*history));
> + btinfo->call_history = history;
> + }
Likewise.
> +
> + history->begin = begin;
> + history->end = end;
> +}
> diff --git a/gdb/btrace.h b/gdb/btrace.h
> index bd8425d..ac7acdb 100644
> --- a/gdb/btrace.h
> +++ b/gdb/btrace.h
> @@ -29,63 +29,106 @@
> #include "btrace-common.h"
>
> struct thread_info;
> +struct btrace_function;
>
> /* A branch trace instruction.
>
> This represents a single instruction in a branch trace. */
> -struct btrace_inst
> +struct btrace_insn
> {
> /* The address of this instruction. */
> CORE_ADDR pc;
> };
>
> -/* A branch trace function.
> +/* A vector of branch trace instructions. */
> +typedef struct btrace_insn btrace_insn_s;
> +DEF_VEC_O (btrace_insn_s);
> +
> +/* A doubly-linked list of branch trace function segments. */
> +struct btrace_func_link
> +{
> + struct btrace_function *prev;
> + struct btrace_function *next;
> +};
> +
> +/* Flags for btrace function segments. */
> +enum btrace_function_flag
> +{
> + /* The 'up' link interpretation.
> + If set, it points to the function segment we returned to.
> + If clear, it points to the function segment we called from. */
> + bfun_up_links_to_ret = (1 << 0),
> +
> + /* The 'up' link points to a tail call. This obviously only makes sense
> + if bfun_up_links_to_ret is clear. */
> + bfun_up_links_to_tailcall = (1 << 1)
enum values are uppercased in GDB.
But I do not see a reason to have the flags field and this enum. You can just
use something like
unsigned bfun_up_links_to_ret : 1;
unsigned bfun_up_links_to_tailcall : 1;
instead of the flags field in struct btrace_function. Sometimes one wants to
pass FLAGS as a function parameter but that is not the case here.
> +};
> +
> +/* A branch trace function segment.
>
> This represents a function segment in a branch trace, i.e. a consecutive
> number of instructions belonging to the same function. */
> -struct btrace_func
> +struct btrace_function
> {
> /* The full and minimal symbol for the function. One of them may be NULL. */
IIUC from the code rather:
+/* Iff both FUN and MFUN are NULL it is marker of the end of trace. */
> struct minimal_symbol *msym;
> struct symbol *sym;
>
> + /* The previous and next segment belonging to the same function. */
> + struct btrace_func_link segment;
> +
> + /* The previous and next function in control flow order. */
> + struct btrace_func_link flow;
> +
> + /* The directly preceding function segment in a (fake) call stack. */
> + struct btrace_function *up;
> +
> + /* The instructions in this function segment. */
> + VEC (btrace_insn_s) *insn;
> +
> + /* The instruction number offset for the first instruction in this
> + function segment. */
> + unsigned int insn_offset;
> +
> + /* The function number. */
It should have some better description, also it may help that it ordered
according to the 'flow' pointers.
> + unsigned int number;
> +
> + /* The function level. */
+ /* Callee has LEVEL value 1 higher than its caller. */
Also some comment how it is relative to btrace_thread_info>level.
> + int level;
> +
> /* The source line range of this function segment (both inclusive). */
> int lbegin, lend;
>
> - /* The instruction number range in the instruction trace corresponding
> - to this function segment (both inclusive). */
> - unsigned int ibegin, iend;
> + /* A bit-vector of btrace_function_flag. */
> + unsigned int flags;
> };
>
> -/* Branch trace may also be represented as a vector of:
> -
> - - branch trace instructions starting with the oldest instruction.
> - - branch trace functions starting with the oldest function. */
> -typedef struct btrace_inst btrace_inst_s;
> -typedef struct btrace_func btrace_func_s;
> +/* A branch trace instruction iterator. */
> +struct btrace_insn_iterator
> +{
> + /* The branch trace function segment containing the instruction. */
> + struct btrace_function *function;
>
> -/* Define functions operating on branch trace vectors. */
> -DEF_VEC_O (btrace_inst_s);
> -DEF_VEC_O (btrace_func_s);
> + /* The index into the function segment's instruction vector. */
> + unsigned int index;
> +};
>
> /* Branch trace iteration state for "record instruction-history". */
> -struct btrace_insn_iterator
> +struct btrace_insn_history
> {
> - /* The instruction index range from begin (inclusive) to end (exclusive)
> - that has been covered last time.
> - If end < begin, the branch trace has just been updated. */
> - unsigned int begin;
> - unsigned int end;
> + /* The branch trace instruction range from begin (inclusive) to
> + end (exclusive) that has been covered last time. */
> + struct btrace_insn_iterator begin;
> + struct btrace_insn_iterator end;
> };
>
> /* Branch trace iteration state for "record function-call-history". */
> -struct btrace_func_iterator
> +struct btrace_call_history
> {
> - /* The function index range from begin (inclusive) to end (exclusive)
> - that has been covered last time.
> - If end < begin, the branch trace has just been updated. */
> - unsigned int begin;
> - unsigned int end;
> + /* The branch trace function range from begin (inclusive) to end (exclusive)
> + that has been covered last time. */
> + struct btrace_function *begin;
> + struct btrace_function *end;
> };
>
> /* Branch trace information per thread.
> @@ -104,15 +147,19 @@ struct btrace_thread_info
> struct btrace_target_info *target;
>
> /* The current branch trace for this thread. */
> - VEC (btrace_block_s) *btrace;
> - VEC (btrace_inst_s) *itrace;
> - VEC (btrace_func_s) *ftrace;
> + struct btrace_function *begin;
> + struct btrace_function *end;
Note inclusivity/exclusivity. Maybe END always points to the dummy
MFUN==FUN==NULL record? May be BEGIN NULL (and if it is, is automatically
also END NULL?)?
> +
> + /* The function level offset. When added to each function's level,
> + this normalizes the function levels such that the smallest level
> + becomes zero. */
> + int level;
>
> /* The instruction history iterator. */
> - struct btrace_insn_iterator insn_iterator;
> + struct btrace_insn_history *insn_history;
>
> /* The function call history iterator. */
> - struct btrace_func_iterator func_iterator;
> + struct btrace_call_history *call_history;
> };
>
> /* Enable branch tracing for a thread. */
> @@ -139,4 +186,60 @@ extern void btrace_free_objfile (struct objfile *);
> /* Parse a branch trace xml document into a block vector. */
> extern VEC (btrace_block_s) *parse_xml_btrace (const char*);
>
> +/* Dereference a branch trace instruction iterator. Return a pointer to the
> + instruction the iterator points to or NULL if the interator does not point
> + to a valid instruction. */
> +extern const struct btrace_insn *
> +btrace_insn_get (const struct btrace_insn_iterator *);
The indentation should be:
extern const struct btrace_insn *
btrace_insn_get (const struct btrace_insn_iterator *);
so that various tools do not consider it a function definition.
> +
> +/* Return the instruction number for a branch trace iterator. Returns zero
s/the instruction number/index of the instruction relative to start of the
function/
> + if the iterator does not point to a valid instruction. */
> +extern unsigned int btrace_insn_number (const struct btrace_insn_iterator *);
> +
> +/* Initialize a branch trace instruction iterator to point to the begin/end of
> + the branch trace. Throws an error if there is no branch trace. */
> +extern void btrace_insn_begin (struct btrace_insn_iterator *,
> + struct btrace_thread_info *);
> +extern void btrace_insn_end (struct btrace_insn_iterator *,
> + struct btrace_thread_info *);
> +
> +/* Increment/decrement a branch trace instruction iterator. Return the number
> + of instructions by which the instruction iterator has been advanced.
> + Returns zero, if the operation failed. */
> +extern unsigned int btrace_insn_next (struct btrace_insn_iterator *,
> + unsigned int stride);
> +extern unsigned int btrace_insn_prev (struct btrace_insn_iterator *,
> + unsigned int stride);
> +
> +/* Compare two branch trace instruction iterators.
> + Return a negative number if LHS < RHS.
> + Return zero if LHS == RHS.
> + Return a positive number if LHS > RHS. */
> +extern int btrace_insn_cmp (const struct btrace_insn_iterator *lhs,
> + const struct btrace_insn_iterator *rhs);
> +
> +/* Find an instruction in the function branch trace by its number.
> + If the instruction is found, initialize the branch trace instruction
> + iterator to point to this instruction and return 1.
> + Return 0, otherwise. */
> +extern int btrace_find_insn_by_number (struct btrace_insn_iterator *,
> + const struct btrace_thread_info *,
> + unsigned int number);
> +
> +/* Find a function in the function branch trace by its number.
> + Return a pointer to that function or NULL if no such function is found. */
> +extern struct btrace_function *
> +btrace_find_function_by_number (const struct btrace_thread_info *,
> + unsigned int number);
The indentation should be:
extern struct btrace_function *
btrace_find_function_by_number (const struct btrace_thread_info *,
unsigned int number);
so that various tools do not consider it a function definition.
> +
> +/* Set the branch trace instruction history to [BEGIN; END). */
Please use words inclusive/exclusive instead of the parantheses types.
> +extern void btrace_set_insn_history (struct btrace_thread_info *,
> + struct btrace_insn_iterator *begin,
> + struct btrace_insn_iterator *end);
> +
> +/* Set the branch trace function call history to [BEGIN; END). */
Please use words inclusive/exclusive instead of the parantheses types.
> +extern void btrace_set_call_history (struct btrace_thread_info *,
> + struct btrace_function *begin,
> + struct btrace_function *end);
> +
> #endif /* BTRACE_H */
> diff --git a/gdb/record-btrace.c b/gdb/record-btrace.c
> index 8fb413e..e2506a8 100644
> --- a/gdb/record-btrace.c
> +++ b/gdb/record-btrace.c
> @@ -74,7 +74,7 @@ require_btrace (void)
>
> btinfo = &tp->btrace;
>
> - if (VEC_empty (btrace_inst_s, btinfo->itrace))
> + if (btinfo->begin == NULL)
> error (_("No trace."));
>
> return btinfo;
> @@ -205,6 +205,7 @@ static void
> record_btrace_info (void)
> {
> struct btrace_thread_info *btinfo;
> + struct btrace_function *bfun;
> struct thread_info *tp;
> unsigned int insts, funcs;
>
> @@ -217,8 +218,15 @@ record_btrace_info (void)
> btrace_fetch (tp);
>
> btinfo = &tp->btrace;
> - insts = VEC_length (btrace_inst_s, btinfo->itrace);
> - funcs = VEC_length (btrace_func_s, btinfo->ftrace);
> + bfun = btinfo->end;
> + insts = 0;
nitpick: You could call it 'insns' when standardizing on the 'insn'
abbreviation (instead of previous inst).
> + funcs = 0;
> +
> + if (bfun != NULL)
> + {
> + funcs = bfun->number;
> + insts = bfun->insn_offset + VEC_length (btrace_insn_s, bfun->insn);
If BFUN always points to the last MFUN==FUN==NULL marker maybe we should
rather gdb_assert (VEC_empty (btrace_insn_s, bfun->insn));
> + }
>
> printf_unfiltered (_("Recorded %u instructions in %u functions for thread "
> "%d (%s).\n"), insts, funcs, tp->num,
> @@ -236,27 +244,32 @@ ui_out_field_uint (struct ui_out *uiout, const char *fld, unsigned int val)
> /* Disassemble a section of the recorded instruction trace. */
>
> static void
> -btrace_insn_history (struct btrace_thread_info *btinfo, struct ui_out *uiout,
> - unsigned int begin, unsigned int end, int flags)
> +btrace_insn_history (struct ui_out *uiout,
> + const struct btrace_insn_iterator *begin,
> + const struct btrace_insn_iterator *end, int flags)
> {
> struct gdbarch *gdbarch;
> - struct btrace_inst *inst;
> - unsigned int idx;
> + struct btrace_insn *inst;
Dead variable 'inst'.
> + struct btrace_insn_iterator it;
>
> - DEBUG ("itrace (0x%x): [%u; %u[", flags, begin, end);
> + DEBUG ("itrace (0x%x): [%u; %u)", flags, btrace_insn_number (begin),
> + btrace_insn_number (end));
>
> gdbarch = target_gdbarch ();
>
> - for (idx = begin; VEC_iterate (btrace_inst_s, btinfo->itrace, idx, inst)
> - && idx < end; ++idx)
> + for (it = *begin; btrace_insn_cmp (&it, end) < 0; btrace_insn_next (&it, 1))
> {
> + const struct btrace_insn *insn;
> +
> + insn = btrace_insn_get (&it);
> +
> /* Print the instruction index. */
> - ui_out_field_uint (uiout, "index", idx);
> + ui_out_field_uint (uiout, "index", btrace_insn_number (&it));
> ui_out_text (uiout, "\t");
>
> /* Disassembly with '/m' flag may not produce the expected result.
> See PR gdb/11833. */
> - gdb_disassembly (gdbarch, uiout, NULL, flags, 1, inst->pc, inst->pc + 1);
> + gdb_disassembly (gdbarch, uiout, NULL, flags, 1, insn->pc, insn->pc + 1);
> }
> }
>
[...]