reactos/lib/rossym/dwarfcfa.c

   1 /*
   2  * Dwarf call frame unwinding.
   3  *
   4  * The call frame unwinding values are encoded using a state machine
   5  * like the pc<->line mapping, but it's a different machine.
   6  * The expressions to generate the old values are similar in function to the
   7  * ``dwarf expressions'' used for locations in the code, but of course not
   8  * the same encoding.
   9  */
  10
  11 #define NTOSAPI
  12 #include <ntddk.h>
  13 #include <reactos/rossym.h>
  14 #include "rossympriv.h"
  15 #include <ntimage.h>
  16
  17 #define NDEBUG
  18 #include <debug.h>
  19
  20 #include "dwarf.h"
  21
  22 #define trace 0
  23
  24 typedef struct State State;
  25 struct State
  26 {
  27         ulong loc;
  28         ulong endloc;
  29         ulong iquantum;
  30         ulong dquantum;
  31         char *augmentation;
  32         int version;
  33         ulong rareg;
  34         DwarfBuf init;
  35         DwarfExpr *cfa;
  36         DwarfExpr *ra;
  37         DwarfExpr *r;
  38         DwarfExpr *initr;
  39         int nr;
  40         DwarfExpr **stack;
  41         int nstack;
  42 };
  43
  44 static int findfde(Dwarf*, ulong, State*, DwarfBuf*);
  45 static int dexec(DwarfBuf*, State*, int);
  46
  47 int
  48 dwarfunwind(Dwarf *d, ulong pc, DwarfExpr *cfa, DwarfExpr *ra, DwarfExpr *r, int nr)
  49 {
  50         int i, ret;
  51         DwarfBuf fde, b;
  52         DwarfExpr *initr;
  53         State s;
  54
  55         initr = mallocz(nr*sizeof(initr[0]), 1);
  56         if(initr == 0)
  57                 return -1;
  58
  59         memset(&s, 0, sizeof s);
  60         s.loc = 0;
  61         s.cfa = cfa;
  62         s.ra = ra;
  63         s.r = r;
  64         s.nr = nr;
  65
  66         if(findfde(d, pc, &s, &fde) < 0){
  67                 free(initr);
  68                 return -1;
  69         }
  70
  71         memset(r, 0, nr*sizeof(r[0]));
  72         for(i=0; i<nr; i++)
  73                 r[i].type = RuleSame;
  74         if(trace) werrstr("s.init %p-%p, fde %p-%p\n", s.init.p, s.init.ep, fde.p, fde.ep);
  75         b = s.init;
  76         if(dexec(&b, &s, 0) < 0)
  77                 goto err;
  78
  79         s.initr = initr;
  80         memmove(initr, r, nr*sizeof(initr[0]));
  81
  82         if(trace) werrstr("s.loc 0x%lux pc 0x%lux\n", s.loc, pc);
  83         while(s.loc < pc){
  84                 if(trace) werrstr("s.loc 0x%lux pc 0x%lux\n", s.loc, pc);
  85                 if(dexec(&fde, &s, 1) < 0)
  86                         goto err;
  87         }
  88         *ra = s.r[s.rareg];
  89
  90         ret = 0;
  91         goto out;
  92
  93 err:
  94         ret = -1;
  95 out:
  96         free(initr);
  97         for(i=0; i<s.nstack; i++)
  98                 free(s.stack[i]);
  99         free(s.stack);
 100         return ret;
 101 }
 102
 103 /*
 104  * XXX This turns out to be much more expensive than the actual
 105  * running of the machine in dexec.  It probably makes sense to
 106  * cache the last 10 or so fde's we've found, since stack traces
 107  * will keep asking for the same info over and over.
 108  */
 109 static int
 110 findfde(Dwarf *d, ulong pc, State *s, DwarfBuf *fde)
 111 {
 112         static int nbad;
 113         char *aug;
 114         uchar *next;
 115         int i, vers;
 116         ulong len, id, base, size;
 117         DwarfBuf b;
 118
 119         if(d->frame.data == nil){
 120                 werrstr("no frame debugging information");
 121                 return -1;
 122         }
 123         b.d = d;
 124         b.p = d->frame.data;
 125         b.ep = b.p + d->frame.len;
 126         b.addrsize = d->addrsize;
 127         if(b.addrsize == 0)
 128                 b.addrsize = 4; /* where should i find this? */
 129
 130         for(; b.p < b.ep; b.p = next){
 131                 if((i = (b.p - d->frame.data) % b.addrsize))
 132                         b.p += b.addrsize - i;
 133                 len = dwarfget4(&b);
 134                 if(len > b.ep-b.p){
 135                         werrstr("bad length in cie/fde header");
 136                         return -1;
 137                 }
 138                 next = b.p+len;
 139                 id = dwarfget4(&b);
 140                 if(id == 0xFFFFFFFF){   /* CIE */
 141                         vers = dwarfget1(&b);
 142                         if(vers != 1 && vers != 2 && vers != 3){
 143                                 if(++nbad == 1)
 144                                         werrstr("unknown cie version %d (wanted 1-3)\n", vers);
 145                                 continue;
 146                         }
 147                         aug = dwarfgetstring(&b);
 148                         if(aug && *aug){
 149                                 if(++nbad == 1)
 150                                         werrstr("unknown augmentation: %s\n", aug);
 151                                 continue;
 152                         }
 153                         s->iquantum = dwarfget128(&b);
 154                         s->dquantum = dwarfget128s(&b);
 155                         s->rareg = dwarfget128(&b);
 156                         if(s->rareg > s->nr){
 157                                 werrstr("return address is register %d but only have %d registers",
 158                                         s->rareg, s->nr);
 159                                 return -1;
 160                         }
 161                         s->init.p = b.p;
 162                         s->init.ep = next;
 163                 }else{  /* FDE */
 164                         base = dwarfgetaddr(&b);
 165                         size = dwarfgetaddr(&b);
 166                         fde->p = b.p;
 167                         fde->ep = next;
 168                         s->loc = base;
 169                         s->endloc = base+size;
 170                         if(base <= pc && pc < base+size)
 171                                 return 0;
 172                 }
 173         }
 174         werrstr("cannot find call frame information for pc 0x%lux", pc);
 175         return -1;
 176
 177 }
 178
 179 static int
 180 checkreg(State *s, long r)
 181 {
 182         if(r < 0 || r >= s->nr){
 183                 werrstr("bad register number 0x%lux", r);
 184                 return -1;
 185         }
 186         return 0;
 187 }
 188
 189 static int
 190 dexec(DwarfBuf *b, State *s, int locstop)
 191 {
 192         int c;
 193         long arg1, arg2;
 194         DwarfExpr *e;
 195
 196         for(;;){
 197                 if(b->p == b->ep){
 198                         if(s->initr)
 199                                 s->loc = s->endloc;
 200                         return 0;
 201                 }
 202                 c = dwarfget1(b);
 203                 if(b->p == nil){
 204                         werrstr("ran out of instructions during cfa program");
 205                         if(trace) werrstr("%r\n");
 206                         return -1;
 207                 }
 208                 if(trace) werrstr("+ loc=0x%lux op 0x%ux ", s->loc, c);
 209                 switch(c>>6){
 210                 case 1: /* advance location */
 211                         arg1 = c&0x3F;
 212                 advance:
 213                         if(trace) werrstr("loc += %ld\n", arg1*s->iquantum);
 214                         s->loc += arg1 * s->iquantum;
 215                         if(locstop)
 216                                 return 0;
 217                         continue;
 218
 219                 case 2: /* offset rule */
 220                         arg1 = c&0x3F;
 221                         arg2 = dwarfget128(b);
 222                 offset:
 223                         if(trace) werrstr("r%ld += %ld\n", arg1, arg2*s->dquantum);
 224                         if(checkreg(s, arg1) < 0)
 225                                 return -1;
 226                         s->r[arg1].type = RuleCfaOffset;
 227                         s->r[arg1].offset = arg2 * s->dquantum;
 228                         continue;
 229
 230                 case 3: /* restore initial setting */
 231                         arg1 = c&0x3F;
 232                 restore:
 233                         if(trace) werrstr("r%ld = init\n", arg1);
 234                         if(checkreg(s, arg1) < 0)
 235                                 return -1;
 236                         s->r[arg1] = s->initr[arg1];
 237                         continue;
 238                 }
 239
 240                 switch(c){
 241                 case 0: /* nop */
 242                         if(trace) werrstr("nop\n");
 243                         continue;
 244
 245                 case 0x01:      /* set location */
 246                         s->loc = dwarfgetaddr(b);
 247                         if(trace) werrstr("loc = 0x%lux\n", s->loc);
 248                         if(locstop)
 249                                 return 0;
 250                         continue;
 251
 252                 case 0x02:      /* advance loc1 */
 253                         arg1 = dwarfget1(b);
 254                         goto advance;
 255
 256                 case 0x03:      /* advance loc2 */
 257                         arg1 = dwarfget2(b);
 258                         goto advance;
 259
 260                 case 0x04:      /* advance loc4 */
 261                         arg1 = dwarfget4(b);
 262                         goto advance;
 263
 264                 case 0x05:      /* offset extended */
 265                         arg1 = dwarfget128(b);
 266                         arg2 = dwarfget128(b);
 267                         goto offset;
 268
 269                 case 0x06:      /* restore extended */
 270                         arg1 = dwarfget128(b);
 271                         goto restore;
 272
 273                 case 0x07:      /* undefined */
 274                         arg1 = dwarfget128(b);
 275                         if(trace) werrstr("r%ld = undef\n", arg1);
 276                         if(checkreg(s, arg1) < 0)
 277                                 return -1;
 278                         s->r[arg1].type = RuleUndef;
 279                         continue;
 280
 281                 case 0x08:      /* same value */
 282                         arg1 = dwarfget128(b);
 283                         if(trace) werrstr("r%ld = same\n", arg1);
 284                         if(checkreg(s, arg1) < 0)
 285                                 return -1;
 286                         s->r[arg1].type = RuleSame;
 287                         continue;
 288
 289                 case 0x09:      /* register */
 290                         arg1 = dwarfget128(b);
 291                         arg2 = dwarfget128(b);
 292                         if(trace) werrstr("r%ld = r%ld\n", arg1, arg2);
 293                         if(checkreg(s, arg1) < 0 || checkreg(s, arg2) < 0)
 294                                 return -1;
 295                         s->r[arg1].type = RuleRegister;
 296                         s->r[arg1].reg = arg2;
 297                         continue;
 298
 299                 case 0x0A:      /* remember state */
 300                         e = malloc(s->nr*sizeof(e[0]));
 301                         if(trace) werrstr("push\n");
 302                         if(e == nil)
 303                                 return -1;
 304                         void *newstack = malloc(s->nstack*sizeof(s->stack[0]));
 305                         RtlMoveMemory(newstack, s->stack, s->nstack*sizeof(s->stack[0]));
 306                         if (newstack) {
 307                                 free(s->stack);
 308                                 s->stack = newstack;
 309                         } else {
 310                                 free(e);
 311                                 return -1;
 312                         }
 313                         if(b->p == nil){
 314                                 free(e);
 315                                 return -1;
 316                         }
 317                         s->stack[s->nstack++] = e;
 318                         memmove(e, s->r, s->nr*sizeof(e[0]));
 319                         continue;
 320
 321                 case 0x0B:      /* restore state */
 322                         if(trace) werrstr("pop\n");
 323                         if(s->nstack == 0){
 324                                 werrstr("restore state underflow");
 325                                 return -1;
 326                         }
 327                         e = s->stack[s->nstack-1];
 328                         memmove(s->r, e, s->nr*sizeof(e[0]));
 329                         free(e);
 330                         s->nstack--;
 331                         continue;
 332
 333                 case 0x0C:      /* def cfa */
 334                         arg1 = dwarfget128(b);
 335                         arg2 = dwarfget128(b);
 336                 defcfa:
 337                         if(trace) werrstr("cfa %ld(r%ld)\n", arg2, arg1);
 338                         if(checkreg(s, arg1) < 0)
 339                                 return -1;
 340                         s->cfa->type = RuleRegOff;
 341                         s->cfa->reg = arg1;
 342                         s->cfa->offset = arg2;
 343                         continue;
 344
 345                 case 0x0D:      /* def cfa register */
 346                         arg1 = dwarfget128(b);
 347                         if(trace) werrstr("cfa reg r%ld\n", arg1);
 348                         if(s->cfa->type != RuleRegOff){
 349                                 werrstr("change CFA register but CFA not in register+offset form");
 350                                 return -1;
 351                         }
 352                         if(checkreg(s, arg1) < 0)
 353                                 return -1;
 354                         s->cfa->reg = arg1;
 355                         continue;
 356
 357                 case 0x0E:      /* def cfa offset */
 358                         arg1 = dwarfget128(b);
 359                 cfaoffset:
 360                         if(trace) werrstr("cfa off %ld\n", arg1);
 361                         if(s->cfa->type != RuleRegOff){
 362                                 werrstr("change CFA offset but CFA not in register+offset form");
 363                                 return -1;
 364                         }
 365                         s->cfa->offset = arg1;
 366                         continue;
 367
 368                 case 0x0F:      /* def cfa expression */
 369                         if(trace) werrstr("cfa expr\n");
 370                         s->cfa->type = RuleLocation;
 371                         s->cfa->loc.len = dwarfget128(b);
 372                         s->cfa->loc.data = dwarfgetnref(b, s->cfa->loc.len);
 373                         continue;
 374
 375                 case 0x10:      /* def reg expression */
 376                         arg1 = dwarfget128(b);
 377                         if(trace) werrstr("reg expr r%ld\n", arg1);
 378                         if(checkreg(s, arg1) < 0)
 379                                 return -1;
 380                         s->r[arg1].type = RuleLocation;
 381                         s->r[arg1].loc.len = dwarfget128(b);
 382                         s->r[arg1].loc.data = dwarfgetnref(b, s->r[arg1].loc.len);
 383                         continue;
 384
 385                 case 0x11:      /* offset extended */
 386                         arg1 = dwarfget128(b);
 387                         arg2 = dwarfget128s(b);
 388                         goto offset;
 389
 390                 case 0x12:      /* cfa sf */
 391                         arg1 = dwarfget128(b);
 392                         arg2 = dwarfget128s(b);
 393                         goto defcfa;
 394
 395                 case 0x13:      /* cfa offset sf */
 396                         arg1 = dwarfget128s(b);
 397                         goto cfaoffset;
 398
 399                 default:        /* unknown */
 400                         werrstr("unknown opcode 0x%ux in cfa program", c);
 401                         return -1;
 402                 }
 403         }
 404         /* not reached */
 405 }
 406
 407