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