gdb/dwarf2-frame-tailcall.c

   1 /* Virtual tail call frames unwinder for GDB.
   2
   3    Copyright (C) 2010-2014 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 "frame.h"
  22 #include "dwarf2-frame-tailcall.h"
  23 #include "dwarf2loc.h"
  24 #include "frame-unwind.h"
  25 #include "block.h"
  26 #include "hashtab.h"
  27 #include "exceptions.h"
  28 #include "gdbtypes.h"
  29 #include "regcache.h"
  30 #include "value.h"
  31 #include "dwarf2-frame.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).artificial_depth = (cache->chain_levels
 226                                  - existing_next_levels (this_frame, cache));
 227   gdb_assert ((*this_id).artificial_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
 239   gdb_assert (chain != NULL);
 240
 241   next_levels++;
 242   gdb_assert (next_levels >= 0);
 243
 244   if (next_levels < chain->callees)
 245     return chain->call_site[chain->length - next_levels - 1]->pc;
 246   next_levels -= chain->callees;
 247
 248   /* Otherwise CHAIN->CALLEES are already covered by CHAIN->CALLERS.  */
 249   if (chain->callees != chain->length)
 250     {
 251       if (next_levels < chain->callers)
 252         return chain->call_site[chain->callers - next_levels - 1]->pc;
 253       next_levels -= chain->callers;
 254     }
 255
 256   gdb_assert (next_levels == 0);
 257   return cache->prev_pc;
 258 }
 259
 260 /* Implementation of frame_prev_register_ftype.  If no specific register
 261    override is supplied NULL is returned (this is incompatible with
 262    frame_prev_register_ftype semantics).  next_bottom_frame and tail call
 263    frames unwind the NULL case differently.  */
 264
 265 struct value *
 266 dwarf2_tailcall_prev_register_first (struct frame_info *this_frame,
 267                                      void **tailcall_cachep, int regnum)
 268 {
 269   struct gdbarch *this_gdbarch = get_frame_arch (this_frame);
 270   struct tailcall_cache *cache = *tailcall_cachep;
 271   CORE_ADDR addr;
 272
 273   if (regnum == gdbarch_pc_regnum (this_gdbarch))
 274     addr = pretend_pc (this_frame, cache);
 275   else if (cache->prev_sp_p && regnum == gdbarch_sp_regnum (this_gdbarch))
 276     {
 277       int next_levels = existing_next_levels (this_frame, cache);
 278
 279       if (next_levels == cache->chain_levels - 1)
 280         addr = cache->prev_sp;
 281       else
 282         addr = dwarf2_frame_cfa (this_frame) - cache->entry_cfa_sp_offset;
 283     }
 284   else
 285     return NULL;
 286
 287   return frame_unwind_got_address (this_frame, regnum, addr);
 288 }
 289
 290 /* Implementation of frame_prev_register_ftype for tail call frames.  Register
 291    set of virtual tail call frames is assumed to be the one of the top (caller)
 292    frame - assume unchanged register value for NULL from
 293    dwarf2_tailcall_prev_register_first.  */
 294
 295 static struct value *
 296 tailcall_frame_prev_register (struct frame_info *this_frame,
 297                                void **this_cache, int regnum)
 298 {
 299   struct tailcall_cache *cache = *this_cache;
 300   struct value *val;
 301
 302   gdb_assert (this_frame != cache->next_bottom_frame);
 303
 304   val = dwarf2_tailcall_prev_register_first (this_frame, this_cache, regnum);
 305   if (val)
 306     return val;
 307
 308   return frame_unwind_got_register (this_frame, regnum, regnum);
 309 }
 310
 311 /* Implementation of frame_sniffer_ftype.  It will never find a new chain, use
 312    dwarf2_tailcall_sniffer_first for the bottom (callee) frame.  It will find
 313    all the predecessing virtual tail call frames, it will return false when
 314    there exist no more tail call frames in this chain.  */
 315
 316 static int
 317 tailcall_frame_sniffer (const struct frame_unwind *self,
 318                          struct frame_info *this_frame, void **this_cache)
 319 {
 320   struct frame_info *next_frame;
 321   int next_levels;
 322   struct tailcall_cache *cache;
 323
 324   /* Inner tail call element does not make sense for a sentinel frame.  */
 325   next_frame = get_next_frame (this_frame);
 326   if (next_frame == NULL)
 327     return 0;
 328
 329   cache = cache_find (next_frame);
 330   if (cache == NULL)
 331     return 0;
 332
 333   cache_ref (cache);
 334
 335   next_levels = existing_next_levels (this_frame, cache);
 336
 337   /* NEXT_LEVELS is -1 only in dwarf2_tailcall_sniffer_first.  */
 338   gdb_assert (next_levels >= 0);
 339   gdb_assert (next_levels <= cache->chain_levels);
 340
 341   if (next_levels == cache->chain_levels)
 342     {
 343       cache_unref (cache);
 344       return 0;
 345     }
 346
 347   *this_cache = cache;
 348   return 1;
 349 }
 350
 351 /* The initial "sniffer" whether THIS_FRAME is a bottom (callee) frame of a new
 352    chain to create.  Keep TAILCALL_CACHEP NULL if it did not find any chain,
 353    initialize it otherwise.  No tail call chain is created if there are no
 354    unambiguous virtual tail call frames to report.
 355
 356    ENTRY_CFA_SP_OFFSETP is NULL if no special SP handling is possible,
 357    otherwise *ENTRY_CFA_SP_OFFSETP is the number of bytes to subtract from tail
 358    call frames frame base to get the SP value there - to simulate return
 359    address pushed on the stack.  */
 360
 361 void
 362 dwarf2_tailcall_sniffer_first (struct frame_info *this_frame,
 363                                void **tailcall_cachep,
 364                                const LONGEST *entry_cfa_sp_offsetp)
 365 {
 366   CORE_ADDR prev_pc = 0, prev_sp = 0;   /* GCC warning.  */
 367   int prev_sp_p = 0;
 368   CORE_ADDR this_pc;
 369   struct gdbarch *prev_gdbarch;
 370   struct call_site_chain *chain = NULL;
 371   struct tailcall_cache *cache;
 372   volatile struct gdb_exception except;
 373
 374   gdb_assert (*tailcall_cachep == NULL);
 375
 376   /* PC may be after the function if THIS_FRAME calls noreturn function,
 377      get_frame_address_in_block will decrease it by 1 in such case.  */
 378   this_pc = get_frame_address_in_block (this_frame);
 379
 380   /* Catch any unwinding errors.  */
 381   TRY_CATCH (except, RETURN_MASK_ERROR)
 382     {
 383       int sp_regnum;
 384
 385       prev_gdbarch = frame_unwind_arch (this_frame);
 386
 387       /* Simulate frame_unwind_pc without setting this_frame->prev_pc.p.  */
 388       prev_pc = gdbarch_unwind_pc (prev_gdbarch, this_frame);
 389
 390       /* call_site_find_chain can throw an exception.  */
 391       chain = call_site_find_chain (prev_gdbarch, prev_pc, this_pc);
 392
 393       if (entry_cfa_sp_offsetp == NULL)
 394         break;
 395       sp_regnum = gdbarch_sp_regnum (prev_gdbarch);
 396       if (sp_regnum == -1)
 397         break;
 398       prev_sp = frame_unwind_register_unsigned (this_frame, sp_regnum);
 399       prev_sp_p = 1;
 400     }
 401   if (except.reason < 0)
 402     {
 403       if (entry_values_debug)
 404         exception_print (gdb_stdout, except);
 405       return;
 406     }
 407
 408   /* Ambiguous unwind or unambiguous unwind verified as matching.  */
 409   if (chain == NULL || chain->length == 0)
 410     {
 411       xfree (chain);
 412       return;
 413     }
 414
 415   cache = cache_new_ref1 (this_frame);
 416   *tailcall_cachep = cache;
 417   cache->chain = chain;
 418   cache->prev_pc = prev_pc;
 419   cache->chain_levels = pretended_chain_levels (chain);
 420   cache->prev_sp_p = prev_sp_p;
 421   if (cache->prev_sp_p)
 422     {
 423       cache->prev_sp = prev_sp;
 424       cache->entry_cfa_sp_offset = *entry_cfa_sp_offsetp;
 425     }
 426   gdb_assert (cache->chain_levels > 0);
 427 }
 428
 429 /* Implementation of frame_dealloc_cache_ftype.  It can be called even for the
 430    bottom chain frame from dwarf2_frame_dealloc_cache which is not a real
 431    TAILCALL_FRAME.  */
 432
 433 static void
 434 tailcall_frame_dealloc_cache (struct frame_info *self, void *this_cache)
 435 {
 436   struct tailcall_cache *cache = this_cache;
 437
 438   cache_unref (cache);
 439 }
 440
 441 /* Implementation of frame_prev_arch_ftype.  We assume all the virtual tail
 442    call frames have gdbarch of the bottom (callee) frame.  */
 443
 444 static struct gdbarch *
 445 tailcall_frame_prev_arch (struct frame_info *this_frame,
 446                           void **this_prologue_cache)
 447 {
 448   struct tailcall_cache *cache = *this_prologue_cache;
 449
 450   return get_frame_arch (cache->next_bottom_frame);
 451 }
 452
 453 /* Virtual tail call frame unwinder if dwarf2_tailcall_sniffer_first finds
 454    a chain to create.  */
 455
 456 const struct frame_unwind dwarf2_tailcall_frame_unwind =
 457 {
 458   TAILCALL_FRAME,
 459   default_frame_unwind_stop_reason,
 460   tailcall_frame_this_id,
 461   tailcall_frame_prev_register,
 462   NULL,
 463   tailcall_frame_sniffer,
 464   tailcall_frame_dealloc_cache,
 465   tailcall_frame_prev_arch
 466 };
 467
 468 /* Provide a prototype to silence -Wmissing-prototypes.  */
 469 extern initialize_file_ftype _initialize_tailcall_frame;
 470
 471 void
 472 _initialize_tailcall_frame (void)
 473 {
 474   cache_htab = htab_create_alloc (50, cache_hash, cache_eq, NULL, xcalloc,
 475                                   xfree);
 476 }