From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 22030 invoked by alias); 13 May 2013 15:25:12 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Received: (qmail 22020 invoked by uid 89); 13 May 2013 15:25:12 -0000 X-Spam-SWARE-Status: No, score=-6.5 required=5.0 tests=AWL,BAYES_00,RCVD_IN_HOSTKARMA_W,RCVD_IN_HOSTKARMA_WL,RP_MATCHES_RCVD,SPF_HELO_PASS,SPF_PASS,TW_BJ,TW_BM,TW_XZ autolearn=ham version=3.3.1 Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Mon, 13 May 2013 15:25:09 +0000 Received: from int-mx01.intmail.prod.int.phx2.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r4DFP7wK016310 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Mon, 13 May 2013 11:25:07 -0400 Received: from host2.jankratochvil.net (ovpn-116-26.ams2.redhat.com [10.36.116.26]) by int-mx01.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id r4DFOo3B013121 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Mon, 13 May 2013 11:24:53 -0400 Date: Mon, 13 May 2013 15:25:00 -0000 From: Jan Kratochvil To: Markus Metzger Cc: gdb-patches@sourceware.org, Christian Himpel Subject: Re: [PATCH 02/15] btrace: change branch trace data structure Message-ID: <20130513152450.GB29683@host2.jankratochvil.net> References: <1367496216-21217-1-git-send-email-markus.t.metzger@intel.com> <1367496216-21217-3-git-send-email-markus.t.metzger@intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1367496216-21217-3-git-send-email-markus.t.metzger@intel.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes X-SW-Source: 2013-05/txt/msg00441.txt.bz2 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); > } > } > [...]