3c0c349ef444c551963240e0a161dfc0600118dc
[reactos.git] / 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 "pe.h"
21 #include "dwarf.h"
22
23 #define trace 1
24
25 typedef struct State State;
26 struct State
27 {
28 ulong loc;
29 ulong endloc;
30 ulong iquantum;
31 ulong dquantum;
32 char *augmentation;
33 int version;
34 ulong rareg;
35 DwarfBuf init;
36 DwarfExpr *cfa;
37 DwarfExpr *ra;
38 DwarfExpr *r;
39 DwarfExpr *initr;
40 int nr;
41 DwarfExpr **stack;
42 int nstack;
43 };
44
45 static int findfde(Dwarf*, ulong, State*, DwarfBuf*);
46 static int dexec(DwarfBuf*, State*, int);
47
48 int
49 dwarfunwind(Dwarf *d, ulong pc, DwarfExpr *cfa, DwarfExpr *ra, DwarfExpr *r, int nr)
50 {
51 int i, ret;
52 DwarfBuf fde, b;
53 DwarfExpr *initr;
54 State s;
55
56 initr = mallocz(nr*sizeof(initr[0]), 1);
57 if(initr == 0)
58 return -1;
59
60 memset(&s, 0, sizeof s);
61 s.loc = 0;
62 s.cfa = cfa;
63 s.ra = ra;
64 s.r = r;
65 s.nr = nr;
66
67 if(findfde(d, pc, &s, &fde) < 0){
68 free(initr);
69 return -1;
70 }
71
72 memset(r, 0, nr*sizeof(r[0]));
73 for(i=0; i<nr; i++)
74 r[i].type = RuleSame;
75 if(trace) werrstr("s.init %p-%p, fde %p-%p", s.init.p, s.init.ep, fde.p, fde.ep);
76 b = s.init;
77 if(dexec(&b, &s, 0) < 0)
78 goto err;
79
80 s.initr = initr;
81 memmove(initr, r, nr*sizeof(initr[0]));
82
83 if(trace) werrstr("s.loc 0x%lx pc 0x%lx", s.loc, pc);
84 while(s.loc < pc){
85 if(trace) werrstr("s.loc 0x%lx pc 0x%lx", s.loc, pc);
86 if(dexec(&fde, &s, 1) < 0)
87 goto err;
88 }
89 *ra = s.r[s.rareg];
90
91 ret = 0;
92 goto out;
93
94 err:
95 ret = -1;
96 out:
97 free(initr);
98 for(i=0; i<s.nstack; i++)
99 free(s.stack[i]);
100 free(s.stack);
101 return ret;
102 }
103
104 /*
105 * XXX This turns out to be much more expensive than the actual
106 * running of the machine in dexec. It probably makes sense to
107 * cache the last 10 or so fde's we've found, since stack traces
108 * will keep asking for the same info over and over.
109 */
110 static int
111 findfde(Dwarf *d, ulong pc, State *s, DwarfBuf *fde)
112 {
113 static int nbad;
114 char *aug;
115 uchar *next;
116 int i, vers;
117 ulong len, id, base, size;
118 DwarfBuf b;
119
120 if(d->frame.data == nil){
121 werrstr("no frame debugging information");
122 return -1;
123 }
124 b.d = d;
125 b.p = d->frame.data;
126 b.ep = b.p + d->frame.len;
127 b.addrsize = d->addrsize;
128 if(b.addrsize == 0)
129 b.addrsize = 4; /* where should i find this? */
130
131 for(; b.p < b.ep; b.p = next){
132 if((i = (b.p - d->frame.data) % b.addrsize))
133 b.p += b.addrsize - i;
134 len = dwarfget4(&b);
135 if(len > b.ep-b.p){
136 werrstr("bad length in cie/fde header");
137 return -1;
138 }
139 next = b.p+len;
140 id = dwarfget4(&b);
141 if(id == 0xFFFFFFFF){ /* CIE */
142 vers = dwarfget1(&b);
143 if (trace) werrstr("CIE len %x id %x vers %x", len, id, vers);
144 if(vers != 1 && vers != 2 && vers != 3){
145 if(++nbad == 1)
146 werrstr("unknown cie version %d (wanted 1-3)", vers);
147 continue;
148 }
149 aug = dwarfgetstring(&b);
150 if(aug && *aug){
151 if(++nbad == 1)
152 werrstr("unknown augmentation: %s", aug);
153 continue;
154 }
155 s->iquantum = dwarfget128(&b);
156 s->dquantum = dwarfget128s(&b);
157 s->rareg = dwarfget128(&b);
158 if(s->rareg > s->nr){
159 werrstr("return address is register %d but only have %d registers",
160 s->rareg, s->nr);
161 return -1;
162 }
163 s->init.p = b.p;
164 s->init.ep = next;
165 }else{ /* FDE */
166 base = dwarfgetaddr(&b);
167 size = dwarfgetaddr(&b);
168 if (trace) werrstr("FDE: base %x-%x (want pc %x)", base, base+size, pc);
169 fde->p = b.p;
170 fde->ep = next;
171 s->loc = base;
172 s->endloc = base+size;
173 if(base <= pc && pc < base+size)
174 return 0;
175 }
176 }
177 werrstr("cannot find call frame information for pc 0x%lx", pc);
178 return -1;
179
180 }
181
182 static int
183 checkreg(State *s, long r)
184 {
185 if(r < 0 || r >= s->nr){
186 werrstr("bad register number 0x%lx", r);
187 return -1;
188 }
189 return 0;
190 }
191
192 static int
193 dexec(DwarfBuf *b, State *s, int locstop)
194 {
195 int c;
196 long arg1, arg2;
197 DwarfExpr *e;
198
199 for(;;){
200 if(b->p == b->ep){
201 if(s->initr)
202 s->loc = s->endloc;
203 werrstr("end dexec");
204 return 0;
205 }
206 c = dwarfget1(b);
207 if(b->p == nil){
208 werrstr("ran out of instructions during cfa program");
209 if(trace) werrstr("%r");
210 return -1;
211 }
212 if(trace) werrstr("+ loc=0x%x op 0x%x ", s->loc, c);
213 switch(c>>6){
214 case 1: /* advance location */
215 arg1 = c&0x3F;
216 advance:
217 if(trace) werrstr("loc += %ld", arg1*s->iquantum);
218 s->loc += arg1 * s->iquantum;
219 if(locstop)
220 return 0;
221 continue;
222
223 case 2: /* offset rule */
224 arg1 = c&0x3F;
225 arg2 = dwarfget128(b);
226 offset:
227 if(trace) werrstr("r%ld += %ld", arg1, arg2*s->dquantum);
228 if(checkreg(s, arg1) < 0)
229 return -1;
230 s->r[arg1].type = RuleCfaOffset;
231 s->r[arg1].offset = arg2 * s->dquantum;
232 continue;
233
234 case 3: /* restore initial setting */
235 arg1 = c&0x3F;
236 restore:
237 if(trace) werrstr("r%ld = init", arg1);
238 if(checkreg(s, arg1) < 0)
239 return -1;
240 s->r[arg1] = s->initr[arg1];
241 continue;
242 }
243
244 switch(c){
245 case 0: /* nop */
246 if(trace) werrstr("nop");
247 continue;
248
249 case 0x01: /* set location */
250 s->loc = dwarfgetaddr(b);
251 if(trace) werrstr("loc = 0x%lx", s->loc);
252 if(locstop)
253 return 0;
254 continue;
255
256 case 0x02: /* advance loc1 */
257 arg1 = dwarfget1(b);
258 goto advance;
259
260 case 0x03: /* advance loc2 */
261 arg1 = dwarfget2(b);
262 goto advance;
263
264 case 0x04: /* advance loc4 */
265 arg1 = dwarfget4(b);
266 goto advance;
267
268 case 0x05: /* offset extended */
269 arg1 = dwarfget128(b);
270 arg2 = dwarfget128(b);
271 goto offset;
272
273 case 0x06: /* restore extended */
274 arg1 = dwarfget128(b);
275 goto restore;
276
277 case 0x07: /* undefined */
278 arg1 = dwarfget128(b);
279 if(trace) werrstr("r%ld = undef", arg1);
280 if(checkreg(s, arg1) < 0)
281 return -1;
282 s->r[arg1].type = RuleUndef;
283 continue;
284
285 case 0x08: /* same value */
286 arg1 = dwarfget128(b);
287 if(trace) werrstr("r%ld = same", arg1);
288 if(checkreg(s, arg1) < 0)
289 return -1;
290 s->r[arg1].type = RuleSame;
291 continue;
292
293 case 0x09: /* register */
294 arg1 = dwarfget128(b);
295 arg2 = dwarfget128(b);
296 if(trace) werrstr("r%ld = r%ld", arg1, arg2);
297 if(checkreg(s, arg1) < 0 || checkreg(s, arg2) < 0)
298 return -1;
299 s->r[arg1].type = RuleRegister;
300 s->r[arg1].reg = arg2;
301 continue;
302
303 case 0x0A: /* remember state */
304 e = malloc(s->nr*sizeof(e[0]));
305 if(trace) werrstr("push");
306 if(e == nil)
307 return -1;
308 void *newstack = malloc(s->nstack*sizeof(s->stack[0]));
309 RtlMoveMemory(newstack, s->stack, s->nstack*sizeof(s->stack[0]));
310 if (newstack) {
311 free(s->stack);
312 s->stack = newstack;
313 } else {
314 free(e);
315 return -1;
316 }
317 if(b->p == nil){
318 free(e);
319 return -1;
320 }
321 s->stack[s->nstack++] = e;
322 memmove(e, s->r, s->nr*sizeof(e[0]));
323 continue;
324
325 case 0x0B: /* restore state */
326 if(trace) werrstr("pop");
327 if(s->nstack == 0){
328 werrstr("restore state underflow");
329 return -1;
330 }
331 e = s->stack[s->nstack-1];
332 memmove(s->r, e, s->nr*sizeof(e[0]));
333 free(e);
334 s->nstack--;
335 continue;
336
337 case 0x0C: /* def cfa */
338 arg1 = dwarfget128(b);
339 arg2 = dwarfget128(b);
340 defcfa:
341 if(trace) werrstr("cfa %ld(r%ld)", arg2, arg1);
342 if(checkreg(s, arg1) < 0)
343 return -1;
344 s->cfa->type = RuleRegOff;
345 s->cfa->reg = arg1;
346 s->cfa->offset = arg2;
347 continue;
348
349 case 0x0D: /* def cfa register */
350 arg1 = dwarfget128(b);
351 if(trace) werrstr("cfa reg r%ld", arg1);
352 if(s->cfa->type != RuleRegOff){
353 werrstr("change CFA register but CFA not in register+offset form");
354 return -1;
355 }
356 if(checkreg(s, arg1) < 0)
357 return -1;
358 s->cfa->reg = arg1;
359 continue;
360
361 case 0x0E: /* def cfa offset */
362 arg1 = dwarfget128(b);
363 cfaoffset:
364 if(trace) werrstr("cfa off %ld", arg1);
365 if(s->cfa->type != RuleRegOff){
366 werrstr("change CFA offset but CFA not in register+offset form");
367 return -1;
368 }
369 s->cfa->offset = arg1;
370 continue;
371
372 case 0x0F: /* def cfa expression */
373 if(trace) werrstr("cfa expr");
374 s->cfa->type = RuleLocation;
375 s->cfa->loc.len = dwarfget128(b);
376 s->cfa->loc.data = dwarfgetnref(b, s->cfa->loc.len);
377 continue;
378
379 case 0x10: /* def reg expression */
380 arg1 = dwarfget128(b);
381 if(trace) werrstr("reg expr r%ld", arg1);
382 if(checkreg(s, arg1) < 0)
383 return -1;
384 s->r[arg1].type = RuleLocation;
385 s->r[arg1].loc.len = dwarfget128(b);
386 s->r[arg1].loc.data = dwarfgetnref(b, s->r[arg1].loc.len);
387 continue;
388
389 case 0x11: /* offset extended */
390 arg1 = dwarfget128(b);
391 arg2 = dwarfget128s(b);
392 goto offset;
393
394 case 0x12: /* cfa sf */
395 arg1 = dwarfget128(b);
396 arg2 = dwarfget128s(b);
397 goto defcfa;
398
399 case 0x13: /* cfa offset sf */
400 arg1 = dwarfget128s(b);
401 goto cfaoffset;
402
403 default: /* unknown */
404 werrstr("unknown opcode 0x%x in cfa program", c);
405 return -1;
406 }
407 }
408 /* not reached */
409 }
410
411 int dwarfcomputecfa(Dwarf *d, DwarfExpr *cfa, PROSSYM_REGISTERS registers, ulong *cfaLocation)
412 {
413 switch (cfa->type) {
414 case RuleRegOff:
415 *cfaLocation = registers->Registers[cfa->reg] + cfa->offset;
416 werrstr("cfa reg %d (%x) offset %x = %x", cfa->reg, (ulong)registers->Registers[cfa->reg], cfa->offset, cfaLocation);
417 break;
418 default:
419 werrstr("cfa->type %x", cfa->type);
420 return -1;
421 }
422
423 return 0;
424 }
425
426 int dwarfregunwind(Dwarf *d, ulong pc, ulong fde, DwarfExpr *cfa, PROSSYM_REGISTERS registers)
427 {
428 int i;
429 State s = { };
430 DwarfExpr initr[sizeof(registers->Registers) / sizeof(registers->Registers[0])] = { };
431 DwarfExpr r[sizeof(registers->Registers) / sizeof(registers->Registers[0])] = { };
432 DwarfExpr ra;
433
434 int nr = s.nr = sizeof(registers->Registers) / sizeof(registers->Registers[0]);
435 s.initr = initr;
436 s.r = r;
437 for (i = 0; i < sizeof(r) / sizeof(r[0]); i++) {
438 r[i].type = RuleRegister;
439 r[i].offset = registers->Registers[i];
440 r[i].reg = i;
441 }
442
443 int res = dwarfunwind(d, pc, cfa, &ra, initr, sizeof(initr) / sizeof(initr[0]));
444 if (res == -1) return -1;
445
446 ulong cfaLocation;
447
448 if (dwarfcomputecfa(d, cfa, registers, &cfaLocation) == -1)
449 return -1;
450
451 for (i = 0; i < nr; i++) {
452 switch (r[i].type) {
453 case RuleUndef:
454 werrstr("Undefined register slot %d", i);
455 assert(FALSE);
456 break;
457 case RuleSame:
458 break;
459 case RuleRegister:
460 registers->Registers[i] = registers->Registers[r[i].reg];
461 break;
462 case RuleRegOff: {
463 BOOLEAN success =
464 RosSymCallbacks.MemGetProc
465 (d->pe->fd,
466 &registers->Registers[i],
467 r[i].offset + registers->Registers[r[i].reg],
468 d->addrsize);
469 if (!success) return -1;
470 } break;
471 case RuleCfaOffset:
472 {
473 BOOLEAN success =
474 RosSymCallbacks.MemGetProc
475 (d->pe->fd,
476 &registers->Registers[i],
477 r[i].offset + cfaLocation,
478 d->addrsize);
479 werrstr("reg[%d] = %x: cfa offset (cfa %x, offset %x) -> @%x", i, (ulong)registers->Registers[i], cfaLocation, initr[i].offset, r[i].offset + cfaLocation);
480 if (!success) return -1;
481 } break;
482 default:
483 werrstr("We don't yet support cfa rule %d in slot %d", r[i].type, i);
484 assert(FALSE);
485 break;
486 }
487 }
488
489 ulong cfaSpace[4];
490 for (i = 0; i < sizeof(cfaSpace) / sizeof(cfaSpace[0]); i++) {
491 RosSymCallbacks.MemGetProc
492 (d->pe->fd, &cfaSpace[i], cfaLocation + (i * 4), d->addrsize);
493 }
494 werrstr("CFA(%x) [%08x, %08x, %08x, %08x]",
495 cfaLocation, cfaSpace[0], cfaSpace[1], cfaSpace[2], cfaSpace[3]);
496
497 return 0;
498 }