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 	b.d = d;
114 	b.p = d->frame.data;
115 	b.ep = b.p + d->frame.len;
116 	b.addrsize = d->addrsize;
117 	if(b.addrsize == 0)
118 		b.addrsize = 4;	/* where should i find this? */
119 
120 	for(; b.p < b.ep; b.p = next){
121 		if((i = (b.p - d->frame.data) % b.addrsize))
122 			b.p += b.addrsize - i;
123 		len = dwarfget4(&b);
124 		if(len > b.ep-b.p){
125 			werrstr("bad length in cie/fde header");
126 			return -1;
127 		}
128 		next = b.p+len;
129 		id = dwarfget4(&b);
130 		if(id == 0xFFFFFFFF){	/* CIE */
131 			vers = dwarfget1(&b);
132 			if(vers != 1 && vers != 2 && vers != 3){
133 				if(++nbad == 1)
134 					fprint(2, "unknown cie version %d (wanted 1-3)\n", vers);
135 				continue;
136 			}
137 			aug = dwarfgetstring(&b);
138 			if(aug && *aug){
139 				if(++nbad == 1)
140 					fprint(2, "unknown augmentation: %s\n", aug);
141 				continue;
142 			}
143 			s->iquantum = dwarfget128(&b);
144 			s->dquantum = dwarfget128s(&b);
145 			s->rareg = dwarfget128(&b);
146 			if(s->rareg > s->nr){
147 				werrstr("return address is register %d but only have %d registers",
148 					s->rareg, s->nr);
149 				return -1;
150 			}
151 			s->init.p = b.p;
152 			s->init.ep = next;
153 		}else{	/* FDE */
154 			base = dwarfgetaddr(&b);
155 			size = dwarfgetaddr(&b);
156 			fde->p = b.p;
157 			fde->ep = next;
158 			s->loc = base;
159 			s->endloc = base+size;
160 			if(base <= pc && pc < base+size)
161 				return 0;
162 		}
163 	}
164 	werrstr("cannot find call frame information for pc 0x%lux", pc);
165 	return -1;
166 			
167 }
168 
169 static int
170 checkreg(State *s, long r)
171 {
172 	if(r < 0 || r >= s->nr){
173 		werrstr("bad register number 0x%lux", r);
174 		return -1;
175 	}
176 	return 0;
177 }
178 
179 static int
180 dexec(DwarfBuf *b, State *s, int locstop)
181 {
182 	int c;
183 	long arg1, arg2;
184 	DwarfExpr *e, **p;
185 
186 	for(;;){
187 		if(b->p == b->ep){
188 			if(s->initr)
189 				s->loc = s->endloc;
190 			return 0;
191 		}
192 		c = dwarfget1(b);
193 		if(b->p == nil){
194 			werrstr("ran out of instructions during cfa program");
195 			if(trace) fprint(2, "%r\n");
196 			return -1;
197 		}
198 		if(trace) fprint(2, "+ loc=0x%lux op 0x%ux ", s->loc, c);
199 		switch(c>>6){
200 		case 1:	/* advance location */
201 			arg1 = c&0x3F;
202 		advance:
203 			if(trace) fprint(2, "loc += %ld\n", arg1*s->iquantum);
204 			s->loc += arg1 * s->iquantum;
205 			if(locstop)
206 				return 0;
207 			continue;
208 		
209 		case 2:	/* offset rule */
210 			arg1 = c&0x3F;
211 			arg2 = dwarfget128(b);
212 		offset:
213 			if(trace) fprint(2, "r%ld += %ld\n", arg1, arg2*s->dquantum);
214 			if(checkreg(s, arg1) < 0)
215 				return -1;
216 			s->r[arg1].type = RuleCfaOffset;
217 			s->r[arg1].offset = arg2 * s->dquantum;
218 			continue;
219 
220 		case 3:	/* restore initial setting */
221 			arg1 = c&0x3F;
222 		restore:
223 			if(trace) fprint(2, "r%ld = init\n", arg1);
224 			if(checkreg(s, arg1) < 0)
225 				return -1;
226 			s->r[arg1] = s->initr[arg1];
227 			continue;
228 		}
229 
230 		switch(c){
231 		case 0:	/* nop */
232 			if(trace) fprint(2, "nop\n");
233 			continue;
234 
235 		case 0x01:	/* set location */
236 			s->loc = dwarfgetaddr(b);
237 			if(trace) fprint(2, "loc = 0x%lux\n", s->loc);
238 			if(locstop)
239 				return 0;
240 			continue;
241 
242 		case 0x02:	/* advance loc1 */
243 			arg1 = dwarfget1(b);
244 			goto advance;
245 
246 		case 0x03:	/* advance loc2 */
247 			arg1 = dwarfget2(b);
248 			goto advance;
249 
250 		case 0x04:	/* advance loc4 */
251 			arg1 = dwarfget4(b);
252 			goto advance;
253 
254 		case 0x05:	/* offset extended */
255 			arg1 = dwarfget128(b);
256 			arg2 = dwarfget128(b);
257 			goto offset;
258 
259 		case 0x06:	/* restore extended */
260 			arg1 = dwarfget128(b);
261 			goto restore;
262 
263 		case 0x07:	/* undefined */
264 			arg1 = dwarfget128(b);
265 			if(trace) fprint(2, "r%ld = undef\n", arg1);
266 			if(checkreg(s, arg1) < 0)
267 				return -1;
268 			s->r[arg1].type = RuleUndef;
269 			continue;
270 
271 		case 0x08:	/* same value */
272 			arg1 = dwarfget128(b);
273 			if(trace) fprint(2, "r%ld = same\n", arg1);
274 			if(checkreg(s, arg1) < 0)
275 				return -1;
276 			s->r[arg1].type = RuleSame;
277 			continue;
278 
279 		case 0x09:	/* register */
280 			arg1 = dwarfget128(b);
281 			arg2 = dwarfget128(b);
282 			if(trace) fprint(2, "r%ld = r%ld\n", arg1, arg2);
283 			if(checkreg(s, arg1) < 0 || checkreg(s, arg2) < 0)
284 				return -1;
285 			s->r[arg1].type = RuleRegister;
286 			s->r[arg1].reg = arg2;
287 			continue;
288 
289 		case 0x0A:	/* remember state */
290 			e = malloc(s->nr*sizeof(e[0]));
291 			if(trace) fprint(2, "push\n");
292 			if(e == nil)
293 				return -1;
294 			p = realloc(s->stack, (s->nstack+1)*sizeof(s->stack[0]));
295 			if(p == nil){
296 				free(e);
297 				return -1;
298 			}
299 			s->stack[s->nstack++] = e;
300 			memmove(e, s->r, s->nr*sizeof(e[0]));
301 			continue;
302 
303 		case 0x0B:	/* restore state */
304 			if(trace) fprint(2, "pop\n");
305 			if(s->nstack == 0){
306 				werrstr("restore state underflow");
307 				return -1;
308 			}
309 			e = s->stack[s->nstack-1];
310 			memmove(s->r, e, s->nr*sizeof(e[0]));
311 			p = realloc(s->stack, (s->nstack-1)*sizeof(s->stack[0]));
312 			if(p == nil)
313 				return -1;
314 			free(e);
315 			s->nstack--;
316 			continue;
317 
318 		case 0x0C:	/* def cfa */
319 			arg1 = dwarfget128(b);
320 			arg2 = dwarfget128(b);
321 		defcfa:
322 			if(trace) fprint(2, "cfa %ld(r%ld)\n", arg2, arg1);
323 			if(checkreg(s, arg1) < 0)
324 				return -1;
325 			s->cfa->type = RuleRegOff;
326 			s->cfa->reg = arg1;
327 			s->cfa->offset = arg2;
328 			continue;
329 
330 		case 0x0D:	/* def cfa register */	
331 			arg1 = dwarfget128(b);
332 			if(trace) fprint(2, "cfa reg r%ld\n", arg1);
333 			if(s->cfa->type != RuleRegOff){
334 				werrstr("change CFA register but CFA not in register+offset form");
335 				return -1;	
336 			}
337 			if(checkreg(s, arg1) < 0)
338 				return -1;
339 			s->cfa->reg = arg1;
340 			continue;
341 
342 		case 0x0E:	/* def cfa offset */
343 			arg1 = dwarfget128(b);
344 		cfaoffset:
345 			if(trace) fprint(2, "cfa off %ld\n", arg1);
346 			if(s->cfa->type != RuleRegOff){
347 				werrstr("change CFA offset but CFA not in register+offset form");
348 				return -1;
349 			}
350 			s->cfa->offset = arg1;
351 			continue;
352 
353 		case 0x0F:	/* def cfa expression */
354 			if(trace) fprint(2, "cfa expr\n");
355 			s->cfa->type = RuleLocation;
356 			s->cfa->loc.len = dwarfget128(b);
357 			s->cfa->loc.data = dwarfgetnref(b, s->cfa->loc.len);
358 			continue;
359 
360 		case 0x10:	/* def reg expression */
361 			arg1 = dwarfget128(b);
362 			if(trace) fprint(2, "reg expr r%ld\n", arg1);
363 			if(checkreg(s, arg1) < 0)
364 				return -1;
365 			s->r[arg1].type = RuleLocation;
366 			s->r[arg1].loc.len = dwarfget128(b);
367 			s->r[arg1].loc.data = dwarfgetnref(b, s->r[arg1].loc.len);
368 			continue;
369 
370 		case 0x11:	/* offset extended */
371 			arg1 = dwarfget128(b);
372 			arg2 = dwarfget128s(b);
373 			goto offset;
374 
375 		case 0x12:	/* cfa sf */
376 			arg1 = dwarfget128(b);
377 			arg2 = dwarfget128s(b);
378 			goto defcfa;
379 
380 		case 0x13:	/* cfa offset sf */
381 			arg1 = dwarfget128s(b);
382 			goto cfaoffset;
383 
384 		default:	/* unknown */
385 			werrstr("unknown opcode 0x%ux in cfa program", c);
386 			return -1;
387 		}
388 	}
389 	return -1;		/* not reached */		
390 }
391