| |
| /*--------------------------------------------------------------------*/ |
| /*--- Storage, and equality on, execution contexts (backtraces). ---*/ |
| /*--- vg_execontext.c ---*/ |
| /*--------------------------------------------------------------------*/ |
| |
| /* |
| This file is part of Valgrind, an extensible x86 protected-mode |
| emulator for monitoring program execution on x86-Unixes. |
| |
| Copyright (C) 2000-2004 Julian Seward |
| jseward@acm.org |
| |
| This program is free software; you can redistribute it and/or |
| modify it under the terms of the GNU General Public License as |
| published by the Free Software Foundation; either version 2 of the |
| License, or (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, but |
| WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program; if not, write to the Free Software |
| Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 02111-1307, USA. |
| |
| The GNU General Public License is contained in the file COPYING. |
| */ |
| |
| #include "core.h" |
| |
| |
| /*------------------------------------------------------------*/ |
| /*--- Low-level ExeContext storage. ---*/ |
| /*------------------------------------------------------------*/ |
| |
| /* The idea is only to ever store any one context once, so as to save |
| space and make exact comparisons faster. */ |
| |
| static ExeContext* vg_ec_list[VG_N_EC_LISTS]; |
| |
| /* Stats only: the number of times the system was searched to locate a |
| context. */ |
| static UInt vg_ec_searchreqs; |
| |
| /* Stats only: the number of full context comparisons done. */ |
| static UInt vg_ec_searchcmps; |
| |
| /* Stats only: total number of stored contexts. */ |
| static UInt vg_ec_totstored; |
| |
| /* Number of 2, 4 and (fast) full cmps done. */ |
| static UInt vg_ec_cmp2s; |
| static UInt vg_ec_cmp4s; |
| static UInt vg_ec_cmpAlls; |
| |
| |
| /*------------------------------------------------------------*/ |
| /*--- Exported functions. ---*/ |
| /*------------------------------------------------------------*/ |
| |
| |
| /* Initialise this subsystem. */ |
| static void init_ExeContext_storage ( void ) |
| { |
| Int i; |
| static Bool init_done = False; |
| if (init_done) |
| return; |
| vg_ec_searchreqs = 0; |
| vg_ec_searchcmps = 0; |
| vg_ec_totstored = 0; |
| vg_ec_cmp2s = 0; |
| vg_ec_cmp4s = 0; |
| vg_ec_cmpAlls = 0; |
| for (i = 0; i < VG_N_EC_LISTS; i++) |
| vg_ec_list[i] = NULL; |
| init_done = True; |
| } |
| |
| |
| /* Print stats. */ |
| void VG_(print_ExeContext_stats) ( void ) |
| { |
| init_ExeContext_storage(); |
| VG_(message)(Vg_DebugMsg, |
| "exectx: %d lists, %d contexts (avg %d per list)", |
| VG_N_EC_LISTS, vg_ec_totstored, |
| vg_ec_totstored / VG_N_EC_LISTS |
| ); |
| VG_(message)(Vg_DebugMsg, |
| "exectx: %d searches, %d full compares (%d per 1000)", |
| vg_ec_searchreqs, vg_ec_searchcmps, |
| vg_ec_searchreqs == 0 |
| ? 0 |
| : (UInt)( (((ULong)vg_ec_searchcmps) * 1000) |
| / ((ULong)vg_ec_searchreqs )) |
| ); |
| VG_(message)(Vg_DebugMsg, |
| "exectx: %d cmp2, %d cmp4, %d cmpAll", |
| vg_ec_cmp2s, vg_ec_cmp4s, vg_ec_cmpAlls |
| ); |
| } |
| |
| |
| /* Print an ExeContext. */ |
| void VG_(pp_ExeContext) ( ExeContext* e ) |
| { |
| init_ExeContext_storage(); |
| VG_(mini_stack_dump) ( e->ips, VG_(clo_backtrace_size) ); |
| } |
| |
| |
| /* Compare two ExeContexts, comparing all callers. */ |
| Bool VG_(eq_ExeContext) ( VgRes res, ExeContext* e1, ExeContext* e2 ) |
| { |
| if (e1 == NULL || e2 == NULL) |
| return False; |
| switch (res) { |
| case Vg_LowRes: |
| /* Just compare the top two callers. */ |
| vg_ec_cmp2s++; |
| if (e1->ips[0] != e2->ips[0] |
| || e1->ips[1] != e2->ips[1]) return False; |
| return True; |
| |
| case Vg_MedRes: |
| /* Just compare the top four callers. */ |
| vg_ec_cmp4s++; |
| if (e1->ips[0] != e2->ips[0]) return False; |
| |
| if (VG_(clo_backtrace_size) < 2) return True; |
| if (e1->ips[1] != e2->ips[1]) return False; |
| |
| if (VG_(clo_backtrace_size) < 3) return True; |
| if (e1->ips[2] != e2->ips[2]) return False; |
| |
| if (VG_(clo_backtrace_size) < 4) return True; |
| if (e1->ips[3] != e2->ips[3]) return False; |
| return True; |
| |
| case Vg_HighRes: |
| vg_ec_cmpAlls++; |
| /* Compare them all -- just do pointer comparison. */ |
| if (e1 != e2) return False; |
| return True; |
| |
| default: |
| VG_(core_panic)("VG_(eq_ExeContext): unrecognised VgRes"); |
| } |
| } |
| |
| |
| /* Take a snapshot of the client's stack, putting the up to 'n_ips' IPs |
| into 'ips'. In order to be thread-safe, we pass in the thread's IP |
| and FP. Returns number of IPs put in 'ips'. */ |
| static UInt stack_snapshot2 ( Addr* ips, UInt n_ips, Addr ip, Addr fp, |
| Addr fp_min, Addr fp_max_orig ) |
| { |
| Int i; |
| Addr fp_max; |
| UInt n_found = 0; |
| |
| VGP_PUSHCC(VgpExeContext); |
| |
| /* First snaffle IPs from the client's stack into ips[0 .. n_ips-1], |
| putting zeroes in when the trail goes cold, which we guess to be when |
| FP is not a reasonable stack location. We also assert that FP |
| increases down the chain. */ |
| |
| // Gives shorter stack trace for tests/badjump.c |
| // JRS 2002-aug-16: I don't think this is a big deal; looks ok for |
| // most "normal" backtraces. |
| // NJN 2002-sep-05: traces for pthreaded programs are particularly bad. |
| |
| // JRS 2002-sep-17: hack, to round up fp_max to the end of the |
| // current page, at least. Dunno if it helps. |
| // NJN 2002-sep-17: seems to -- stack traces look like 1.0.X again |
| fp_max = (fp_max_orig + VKI_PAGE_SIZE - 1) & ~(VKI_PAGE_SIZE - 1); |
| fp_max -= sizeof(Addr); |
| |
| /* Assertion broken before main() is reached in pthreaded programs; the |
| * offending stack traces only have one item. --njn, 2002-aug-16 */ |
| /* vg_assert(fp_min <= fp_max);*/ |
| |
| if (fp_min + 4000000 <= fp_max) { |
| /* If the stack is ridiculously big, don't poke around ... but |
| don't bomb out either. Needed to make John Regehr's |
| user-space threads package work. JRS 20021001 */ |
| ips[0] = ip; |
| i = 1; |
| } else { |
| /* Get whatever we safely can ... */ |
| ips[0] = ip; |
| fp = FIRST_STACK_FRAME(fp); |
| for (i = 1; i < n_ips; i++) { |
| if (!(fp_min <= fp && fp <= fp_max)) { |
| //VG_(printf)("... out of range %p\n", fp); |
| break; /* fp gone baaaad */ |
| } |
| // NJN 2002-sep-17: monotonicity doesn't work -- gives wrong traces... |
| // if (fp >= ((UInt*)fp)[0]) { |
| // VG_(printf)("nonmonotonic\n"); |
| // break; /* fp gone nonmonotonic */ |
| // } |
| ips[i] = STACK_FRAME_RET(fp); /* ret addr */ |
| fp = STACK_FRAME_NEXT(fp); /* old fp */ |
| //VG_(printf)(" %p\n", ips[i]); |
| } |
| } |
| n_found = i; |
| |
| /* Put zeroes in the rest. */ |
| for (; i < n_ips; i++) { |
| ips[i] = 0; |
| } |
| VGP_POPCC(VgpExeContext); |
| |
| return n_found; |
| } |
| |
| /* This guy is the head honcho here. Take a snapshot of the client's |
| stack. Search our collection of ExeContexts to see if we already |
| have it, and if not, allocate a new one. Either way, return a |
| pointer to the context. If there is a matching context we |
| guarantee to not allocate a new one. Thus we never store |
| duplicates, and so exact equality can be quickly done as equality |
| on the returned ExeContext* values themselves. Inspired by Hugs's |
| Text type. |
| */ |
| ExeContext* VG_(get_ExeContext2) ( Addr ip, Addr fp, |
| Addr fp_min, Addr fp_max_orig ) |
| { |
| Int i; |
| Addr ips[VG_DEEPEST_BACKTRACE]; |
| Bool same; |
| UWord hash; |
| ExeContext* new_ec; |
| ExeContext* list; |
| |
| VGP_PUSHCC(VgpExeContext); |
| |
| init_ExeContext_storage(); |
| vg_assert(VG_(clo_backtrace_size) >= 1 |
| && VG_(clo_backtrace_size) <= VG_DEEPEST_BACKTRACE); |
| |
| stack_snapshot2( ips, VG_(clo_backtrace_size), |
| ip, fp, fp_min, fp_max_orig ); |
| |
| /* Now figure out if we've seen this one before. First hash it so |
| as to determine the list number. */ |
| |
| hash = 0; |
| for (i = 0; i < VG_(clo_backtrace_size); i++) { |
| hash ^= ips[i]; |
| hash = (hash << 29) | (hash >> 3); |
| } |
| hash = hash % VG_N_EC_LISTS; |
| |
| /* And (the expensive bit) look a matching entry in the list. */ |
| |
| vg_ec_searchreqs++; |
| |
| list = vg_ec_list[hash]; |
| |
| while (True) { |
| if (list == NULL) break; |
| vg_ec_searchcmps++; |
| same = True; |
| for (i = 0; i < VG_(clo_backtrace_size); i++) { |
| if (list->ips[i] != ips[i]) { |
| same = False; |
| break; |
| } |
| } |
| if (same) break; |
| list = list->next; |
| } |
| |
| if (list != NULL) { |
| /* Yay! We found it. */ |
| VGP_POPCC(VgpExeContext); |
| return list; |
| } |
| |
| /* Bummer. We have to allocate a new context record. */ |
| vg_ec_totstored++; |
| |
| new_ec = VG_(arena_malloc)( VG_AR_EXECTXT, |
| sizeof(struct _ExeContext *) |
| + VG_(clo_backtrace_size) * sizeof(Addr) ); |
| |
| for (i = 0; i < VG_(clo_backtrace_size); i++) |
| new_ec->ips[i] = ips[i]; |
| |
| new_ec->next = vg_ec_list[hash]; |
| vg_ec_list[hash] = new_ec; |
| |
| VGP_POPCC(VgpExeContext); |
| return new_ec; |
| } |
| |
| void get_needed_regs(ThreadId tid, Addr* ip, Addr* fp, Addr* sp, |
| Addr* stack_highest_word) |
| { |
| if (VG_(is_running_thread)(tid)) { |
| /* thread currently in baseblock */ |
| *ip = VG_(baseBlock)[VGOFF_INSTR_PTR]; |
| *fp = VG_(baseBlock)[VGOFF_FRAME_PTR]; |
| *sp = VG_(baseBlock)[VGOFF_STACK_PTR]; |
| *stack_highest_word = VG_(threads)[tid].stack_highest_word; |
| } else { |
| /* thread in thread table */ |
| ThreadState* tst = & VG_(threads)[ tid ]; |
| *ip = ARCH_INSTR_PTR(tst->arch); |
| *fp = ARCH_FRAME_PTR(tst->arch); |
| *sp = ARCH_STACK_PTR(tst->arch); |
| *stack_highest_word = tst->stack_highest_word; |
| } |
| |
| /* Nasty little hack to deal with sysinfo syscalls - if libc is |
| using the sysinfo page for syscalls (the TLS version does), then |
| ip will always appear to be in that page when doing a syscall, |
| not the actual libc function doing the syscall. This check sees |
| if IP is within the syscall code, and pops the return address |
| off the stack so that ip is placed within the library function |
| calling the syscall. This makes stack backtraces much more |
| useful. */ |
| if (*ip >= VG_(client_trampoline_code)+VG_(tramp_syscall_offset) && |
| *ip < VG_(client_trampoline_code)+VG_(trampoline_code_length) && |
| VG_(is_addressable)(*sp, sizeof(Addr))) { |
| *ip = *(Addr *)*sp; |
| *sp += sizeof(Addr); |
| } |
| } |
| |
| ExeContext* VG_(get_ExeContext) ( ThreadId tid ) |
| { |
| Addr ip, fp, sp, stack_highest_word; |
| |
| get_needed_regs(tid, &ip, &fp, &sp, &stack_highest_word); |
| return VG_(get_ExeContext2)(ip, fp, sp, stack_highest_word); |
| } |
| |
| /* Take a snapshot of the client's stack, putting the up to 'n_ips' |
| instruction pointers into 'ips'. In order to be thread-safe, we pass in |
| the thread's IP and FP. Returns number of IPs put in 'ips'. */ |
| UInt VG_(stack_snapshot) ( ThreadId tid, Addr* ips, UInt n_ips ) |
| { |
| Addr ip, fp, sp, stack_highest_word; |
| |
| get_needed_regs(tid, &ip, &fp, &sp, &stack_highest_word); |
| return stack_snapshot2(ips, n_ips, ip, fp, sp, stack_highest_word); |
| } |
| |
| |
| Addr VG_(get_EIP_from_ExeContext) ( ExeContext* e, UInt n ) |
| { |
| if (n > VG_(clo_backtrace_size)) return 0; |
| return e->ips[n]; |
| } |
| |
| Addr VG_(get_EIP) ( ThreadId tid ) |
| { |
| Addr ret; |
| |
| if (VG_(is_running_thread)(tid)) |
| ret = VG_(baseBlock)[VGOFF_INSTR_PTR]; |
| else |
| ret = ARCH_INSTR_PTR(VG_(threads)[ tid ].arch); |
| |
| return ret; |
| } |
| |
| /*--------------------------------------------------------------------*/ |
| /*--- end ---*/ |
| /*--------------------------------------------------------------------*/ |