gdb/dwarf2-frame-tailcall.c

   1 /* Virtual tail call frames unwinder for GDB.
   2
   3    Copyright (C) 2010, 2011 Free Software Foundation, Inc.
   4
   5    This file is part of GDB.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  19
  20 #include "defs.h"
  21 #include "gdb_assert.h"
  22 #include "frame.h"
  23 #include "dwarf2-frame-tailcall.h"
  24 #include "dwarf2loc.h"
  25 #include "frame-unwind.h"
  26 #include "block.h"
  27 #include "hashtab.h"
  28 #include "exceptions.h"
  29 #include "gdbtypes.h"
  30 #include "regcache.h"
  31 #include "value.h"
  32 #include "dwarf2-frame.h"
  33
  34 /* Contains struct tailcall_cache indexed by next_bottom_frame.  */
  35 static htab_t cache_htab;
  36
  37 /* Associate structure of the unwinder to call_site_chain.  Lifetime of this
  38    structure is maintained by REFC decremented by dealloc_cache, all of them
  39    get deleted during reinit_frame_cache.  */
  40 struct tailcall_cache
  41 {
  42   /* It must be the first one of this struct.  It is the furthest callee.  */
  43   struct frame_info *next_bottom_frame;
  44
  45   /* Reference count.  The whole chain of virtual tail call frames shares one
  46      tailcall_cache.  */
  47   int refc;
  48
  49   /* Associated found virtual taill call frames chain, it is never NULL.  */
  50   struct call_site_chain *chain;
  51
  52   /* Cached pretended_chain_levels result.  */
  53   int chain_levels;
  54
  55   /* Unwound PC from the top (caller) frame, as it is not contained
  56      in CHAIN.  */
  57   CORE_ADDR prev_pc;
  58
  59   /* Compensate SP in caller frames appropriately.  prev_sp and
  60      entry_cfa_sp_offset are valid only if PREV_SP_P.  PREV_SP is SP at the top
  61      (caller) frame.  ENTRY_CFA_SP_OFFSET is shift of SP in tail call frames
  62      against next_bottom_frame SP.  */
  63   unsigned prev_sp_p : 1;
  64   CORE_ADDR prev_sp;
  65   LONGEST entry_cfa_sp_offset;
  66 };
  67
  68 /* hash_f for htab_create_alloc of cache_htab.  */
  69
  70 static hashval_t
  71 cache_hash (const void *arg)
  72 {
  73   const struct tailcall_cache *cache = arg;
  74
  75   return htab_hash_pointer (cache->next_bottom_frame);
  76 }
  77
  78 /* eq_f for htab_create_alloc of cache_htab.  */
  79
  80 static int
  81 cache_eq (const void *arg1, const void *arg2)
  82 {
  83   const struct tailcall_cache *cache1 = arg1;
  84   const struct tailcall_cache *cache2 = arg2;
  85
  86   return cache1->next_bottom_frame == cache2->next_bottom_frame;
  87 }
  88
  89 /* Create new tailcall_cache for NEXT_BOTTOM_FRAME, NEXT_BOTTOM_FRAME must not
  90    yet have been indexed by cache_htab.  Caller holds one reference of the new
  91    tailcall_cache.  */
  92
  93 static struct tailcall_cache *
  94 cache_new_ref1 (struct frame_info *next_bottom_frame)
  95 {
  96   struct tailcall_cache *cache;
  97   void **slot;
  98
  99   cache = xzalloc (sizeof (*cache));
 100
 101   cache->next_bottom_frame = next_bottom_frame;
 102   cache->refc = 1;
 103
 104   slot = htab_find_slot (cache_htab, cache, INSERT);
 105   gdb_assert (*slot == NULL);
 106   *slot = cache;
 107
 108   return cache;
 109 }
 110
 111 /* Create new reference to CACHE.  */
 112
 113 static void
 114 cache_ref (struct tailcall_cache *cache)
 115 {
 116   gdb_assert (cache->refc > 0);
 117
 118   cache->refc++;
 119 }
 120
 121 /* Drop reference to CACHE, possibly fully freeing it and unregistering it from
 122    cache_htab.  */
 123
 124 static void
 125 cache_unref (struct tailcall_cache *cache)
 126 {
 127   gdb_assert (cache->refc > 0);
 128
 129   if (!--cache->refc)
 130     {
 131       gdb_assert (htab_find_slot (cache_htab, cache, NO_INSERT) != NULL);
 132       htab_remove_elt (cache_htab, cache);
 133
 134       xfree (cache->chain);
 135       xfree (cache);
 136     }
 137 }
 138
 139 /* Return 1 if FI is a non-bottom (not the callee) tail call frame.  Otherwise
 140    return 0.  */
 141
 142 static int
 143 frame_is_tailcall (struct frame_info *fi)
 144 {
 145   return frame_unwinder_is (fi, &dwarf2_tailcall_frame_unwind);
 146 }
 147
 148 /* Try to find tailcall_cache in cache_htab if FI is a part of its virtual tail
 149    call chain.  Otherwise return NULL.  No new reference is created.  */
 150
 151 static struct tailcall_cache *
 152 cache_find (struct frame_info *fi)
 153 {
 154   struct tailcall_cache *cache;
 155   void **slot;
 156
 157   while (frame_is_tailcall (fi))
 158     {
 159       fi = get_next_frame (fi);
 160       gdb_assert (fi != NULL);
 161     }
 162
 163   slot = htab_find_slot (cache_htab, &fi, NO_INSERT);
 164   if (slot == NULL)
 165     return NULL;
 166
 167   cache = *slot;
 168   gdb_assert (cache != NULL);
 169   return cache;
 170 }
 171
 172 /* Number of virtual frames between THIS_FRAME and CACHE->NEXT_BOTTOM_FRAME.
 173    If THIS_FRAME is CACHE-> NEXT_BOTTOM_FRAME return -1.  */
 174
 175 static int
 176 existing_next_levels (struct frame_info *this_frame,
 177                       struct tailcall_cache *cache)
 178 {
 179   int retval = (frame_relative_level (this_frame)
 180                 - frame_relative_level (cache->next_bottom_frame) - 1);
 181
 182   gdb_assert (retval >= -1);
 183
 184   return retval;
 185 }
 186
 187 /* The number of virtual tail call frames in CHAIN.  With no virtual tail call
 188    frames the function would return 0 (but CHAIN does not exist in such
 189    case).  */
 190
 191 static int
 192 pretended_chain_levels (struct call_site_chain *chain)
 193 {
 194   int chain_levels;
 195
 196   gdb_assert (chain != NULL);
 197
 198   if (chain->callers == chain->length && chain->callees == chain->length)
 199     return chain->length;
 200
 201   chain_levels = chain->callers + chain->callees;
 202   gdb_assert (chain_levels < chain->length);
 203
 204   return chain_levels;
 205 }
 206
 207 /* Implementation of frame_this_id_ftype.  THIS_CACHE must be already
 208    initialized with tailcall_cache, THIS_FRAME must be a part of THIS_CACHE.
 209
 210    Specific virtual tail call frames are tracked by INLINE_DEPTH.  */
 211
 212 static void
 213 tailcall_frame_this_id (struct frame_info *this_frame, void **this_cache,
 214                         struct frame_id *this_id)
 215 {
 216   struct tailcall_cache *cache = *this_cache;
 217   struct frame_info *next_frame;
 218
 219   /* Tail call does not make sense for a sentinel frame.  */
 220   next_frame = get_next_frame (this_frame);
 221   gdb_assert (next_frame != NULL);
 222
 223   *this_id = get_frame_id (next_frame);
 224   (*this_id).code_addr = get_frame_pc (this_frame);
 225   (*this_id).code_addr_p = 1;
 226   (*this_id).inline_depth = (cache->chain_levels
 227                              - existing_next_levels (this_frame, cache));
 228   gdb_assert ((*this_id).inline_depth > 0);
 229 }
 230
 231 /* Find PC to be unwound from THIS_FRAME.  THIS_FRAME must be a part of
 232    CACHE.  */
 233
 234 static CORE_ADDR
 235 pretend_pc (struct frame_info *this_frame, struct tailcall_cache *cache)
 236 {
 237   int next_levels = existing_next_levels (this_frame, cache);
 238   struct call_site_chain *chain = cache->chain;
 239   int caller_no;
 240
 241   gdb_assert (chain != NULL);
 242
 243   next_levels++;
 244   gdb_assert (next_levels >= 0);
 245
 246   if (next_levels < chain->callees)
 247     return chain->call_site[chain->length - next_levels - 1]->pc;
 248   next_levels -= chain->callees;
 249
 250   /* Otherwise CHAIN->CALLEES are already covered by CHAIN->CALLERS.  */
 251   if (chain->callees != chain->length)
 252     {
 253       if (next_levels < chain->callers)
 254         return chain->call_site[chain->callers - next_levels - 1]->pc;
 255       next_levels -= chain->callers;
 256     }
 257
 258   gdb_assert (next_levels == 0);
 259   return cache->prev_pc;
 260 }
 261
 262 /* Implementation of frame_prev_register_ftype.  If no specific register
 263    override is supplied NULL is returned (this is incompatible with
 264    frame_prev_register_ftype semantics).  next_bottom_frame and tail call
 265    frames unwind the NULL case differently.  */
 266
 267 struct value *
 268 dwarf2_tailcall_prev_register_first (struct frame_info *this_frame,
 269                                      void **tailcall_cachep, int regnum)
 270 {
 271   struct gdbarch *this_gdbarch = get_frame_arch (this_frame);
 272   struct tailcall_cache *cache = *tailcall_cachep;
 273   CORE_ADDR addr;
 274
 275   if (regnum == gdbarch_pc_regnum (this_gdbarch))
 276     addr = pretend_pc (this_frame, cache);
 277   else if (cache->prev_sp_p && regnum == gdbarch_sp_regnum (this_gdbarch))
 278     {
 279       int next_levels = existing_next_levels (this_frame, cache);
 280
 281       if (next_levels == cache->chain_levels - 1)
 282         addr = cache->prev_sp;
 283       else
 284         addr = dwarf2_frame_cfa (this_frame) - cache->entry_cfa_sp_offset;
 285     }
 286   else
 287     return NULL;
 288
 289   return frame_unwind_got_address (this_frame, regnum, addr);
 290 }
 291
 292 /* Implementation of frame_prev_register_ftype for tail call frames.  Register
 293    set of virtual tail call frames is assumed to be the one of the top (caller)
 294    frame - assume unchanged register value for NULL from
 295    dwarf2_tailcall_prev_register_first.  */
 296
 297 static struct value *
 298 tailcall_frame_prev_register (struct frame_info *this_frame,
 299                                void **this_cache, int regnum)
 300 {
 301   struct tailcall_cache *cache = *this_cache;
 302   struct value *val;
 303
 304   gdb_assert (this_frame != cache->next_bottom_frame);
 305
 306   val = dwarf2_tailcall_prev_register_first (this_frame, this_cache, regnum);
 307   if (val)
 308     return val;
 309
 310   return frame_unwind_got_register (this_frame, regnum, regnum);
 311 }
 312
 313 /* Implementation of frame_sniffer_ftype.  It will never find a new chain, use
 314    dwarf2_tailcall_sniffer_first for the bottom (callee) frame.  It will find
 315    all the predecessing virtual tail call frames, it will return false when
 316    there exist no more tail call frames in this chain.  */
 317
 318 static int
 319 tailcall_frame_sniffer (const struct frame_unwind *self,
 320                          struct frame_info *this_frame, void **this_cache)
 321 {
 322   struct frame_info *next_frame;
 323   int next_levels;
 324   struct tailcall_cache *cache;
 325
 326   /* Inner tail call element does not make sense for a sentinel frame.  */
 327   next_frame = get_next_frame (this_frame);
 328   if (next_frame == NULL)
 329     return 0;
 330
 331   cache = cache_find (next_frame);
 332   if (cache == NULL)
 333     return 0;
 334
 335   cache_ref (cache);
 336
 337   next_levels = existing_next_levels (this_frame, cache);
 338
 339   /* NEXT_LEVELS is -1 only in dwarf2_tailcall_sniffer_first.  */
 340   gdb_assert (next_levels >= 0);
 341   gdb_assert (next_levels <= cache->chain_levels);
 342
 343   if (next_levels == cache->chain_levels)
 344     {
 345       cache_unref (cache);
 346       return 0;
 347     }
 348
 349   *this_cache = cache;
 350   return 1;
 351 }
 352
 353 /* The initial "sniffer" whether THIS_FRAME is a bottom (callee) frame of a new
 354    chain to create.  Keep TAILCALL_CACHEP NULL if it did not find any chain,
 355    initialize it otherwise.  No tail call chain is created if there are no
 356    unambiguous virtual tail call frames to report.
 357
 358    ENTRY_CFA_SP_OFFSETP is NULL if no special SP handling is possible,
 359    otherwise *ENTRY_CFA_SP_OFFSETP is the number of bytes to subtract from tail
 360    call frames frame base to get the SP value there - to simulate return
 361    address pushed on the stack.  */
 362
 363 void
 364 dwarf2_tailcall_sniffer_first (struct frame_info *this_frame,
 365                                void **tailcall_cachep,
 366                                const LONGEST *entry_cfa_sp_offsetp)
 367 {
 368   CORE_ADDR prev_pc = 0, prev_sp = 0;   /* GCC warning.  */
 369   int prev_sp_p = 0;
 370   CORE_ADDR this_pc, pc;
 371   struct gdbarch *prev_gdbarch;
 372   struct call_site_chain *chain = NULL;
 373   struct frame_info *fi;
 374   struct tailcall_cache *cache;
 375   volatile struct gdb_exception except;
 376
 377   gdb_assert (*tailcall_cachep == NULL);
 378
 379   this_pc = get_frame_pc (this_frame);
 380
 381   /* Catch any unwinding errors.  */
 382   TRY_CATCH (except, RETURN_MASK_ERROR)
 383     {
 384       int sp_regnum;
 385
 386       prev_gdbarch = frame_unwind_arch (this_frame);
 387
 388       /* Simulate frame_unwind_pc without setting this_frame->prev_pc.p.  */
 389       prev_pc = gdbarch_unwind_pc (prev_gdbarch, this_frame);
 390
 391       /* call_site_find_chain can throw an exception.  */
 392       chain = call_site_find_chain (prev_gdbarch, prev_pc, this_pc);
 393
 394       if (entry_cfa_sp_offsetp == NULL)
 395         break;
 396       sp_regnum = gdbarch_sp_regnum (prev_gdbarch);
 397       if (sp_regnum == -1)
 398         break;
 399       prev_sp = frame_unwind_register_unsigned (this_frame, sp_regnum);
 400       prev_sp_p = 1;
 401     }
 402   if (except.reason < 0)
 403     {
 404       if (entry_values_debug)
 405         exception_print (gdb_stdout, except);
 406       return;
 407     }
 408
 409   /* Ambiguous unwind or unambiguous unwind verified as matching.  */
 410   if (chain == NULL || chain->length == 0)
 411     {
 412       xfree (chain);
 413       return;
 414     }
 415
 416   cache = cache_new_ref1 (this_frame);
 417   *tailcall_cachep = cache;
 418   cache->chain = chain;
 419   cache->prev_pc = prev_pc;
 420   cache->chain_levels = pretended_chain_levels (chain);
 421   cache->prev_sp_p = prev_sp_p;
 422   if (cache->prev_sp_p)
 423     {
 424       cache->prev_sp = prev_sp;
 425       cache->entry_cfa_sp_offset = *entry_cfa_sp_offsetp;
 426     }
 427   gdb_assert (cache->chain_levels > 0);
 428 }
 429
 430 /* Implementation of frame_dealloc_cache_ftype.  It can be called even for the
 431    bottom chain frame from dwarf2_frame_dealloc_cache which is not a real
 432    TAILCALL_FRAME.  */
 433
 434 static void
 435 tailcall_frame_dealloc_cache (struct frame_info *self, void *this_cache)
 436 {
 437   struct tailcall_cache *cache = this_cache;
 438
 439   cache_unref (cache);
 440 }
 441
 442 /* Implementation of frame_prev_arch_ftype.  We assume all the virtual tail
 443    call frames have gdbarch of the bottom (callee) frame.  */
 444
 445 static struct gdbarch *
 446 tailcall_frame_prev_arch (struct frame_info *this_frame,
 447                           void **this_prologue_cache)
 448 {
 449   struct tailcall_cache *cache = *this_prologue_cache;
 450
 451   return get_frame_arch (cache->next_bottom_frame);
 452 }
 453
 454 /* Virtual tail call frame unwinder if dwarf2_tailcall_sniffer_first finds
 455    a chain to create.  */
 456
 457 const struct frame_unwind dwarf2_tailcall_frame_unwind =
 458 {
 459   TAILCALL_FRAME,
 460   default_frame_unwind_stop_reason,
 461   tailcall_frame_this_id,
 462   tailcall_frame_prev_register,
 463   NULL,
 464   tailcall_frame_sniffer,
 465   tailcall_frame_dealloc_cache,
 466   tailcall_frame_prev_arch
 467 };
 468
 469 /* Provide a prototype to silence -Wmissing-prototypes.  */
 470 extern initialize_file_ftype _initialize_tailcall_frame;
 471
 472 void
 473 _initialize_tailcall_frame (void)
 474 {
 475   cache_htab = htab_create_alloc (50, cache_hash, cache_eq, NULL, xcalloc,
 476                                   xfree);
 477 }