gdb/dwarf2-frame-tailcall.c

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