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