Fix backtrace_list()'s wild read
[akaros.git] / kern / arch / x86 / kdebug.c
1 #include <stab.h>
2 #include <string.h>
3 #include <assert.h>
4 #include <kdebug.h>
5 #include <pmap.h>
6 #include <process.h>
7 #include <kmalloc.h>
8 #include <arch/uaccess.h>
9
10 #include <ros/memlayout.h>
11
12 /* The return address is right above ebp on the stack.  We subtract an
13  * additional 1 to make sure the eip we get is actually in the function
14  * that called us.  I had a couple cases early on where call was the last
15  * instruction in a function, and simply reading the retaddr would point
16  * into another function (the next one in the object).
17  */
18 #define GET_FRAME_START(ebp, eip)                                                       \
19         do {                                                                                                    \
20                 ebp = read_bp();                                                                        \
21                 eip = *(uintptr_t *) (ebp + sizeof(uintptr_t)) - 1; \
22                 ebp = *(uintptr_t *) ebp;                                                       \
23         } while (0)
24
25 // Beginning of stabs table
26 extern const stab_t __STAB_BEGIN__[];
27
28 // End of stabs table
29 extern const stab_t __STAB_END__[];
30
31 // Beginning of string table
32 extern const char __STABSTR_BEGIN__[];
33
34  // End of string table
35 extern const char __STABSTR_END__[];
36
37 typedef struct UserStabData {
38         const stab_t *stabs;
39         const stab_t *stab_end;
40         const char *stabstr;
41         const char *stabstr_end;
42 } user_stab_data_t;
43
44 /* We used to check for a null terminating byte for the entire strings section
45  * (due to JOS, I think), but that's not what the spec says: only that all
46  * strings are null terminated.  There might be random stuff tacked on at the
47  * end.  I had some stabs that seemed valid (lookups worked), that did not have
48  * the entire table be null terminated.  Still, something else might be jacked
49  * up.  If it turns out that's the case, put the checks in here. */
50 static bool stab_table_valid(const char *stabstr, const char *stabstr_end)
51 {
52         if (stabstr_end <= stabstr)
53                 return FALSE;
54         return TRUE;
55 }
56
57 // stab_binsearch(stabs, region_left, region_right, type, addr)
58 //
59 //      Some stab types are arranged in increasing order by instruction
60 //      address.  For example, N_FUN stabs (stab entries with n_type ==
61 //      N_FUN), which mark functions, and N_SO stabs, which mark source files.
62 //
63 //      Given an instruction address, this function finds the single stab
64 //      entry of type 'type' that contains that address.
65 //
66 //      The search takes place within the range [*region_left, *region_right].
67 //      Thus, to search an entire set of N stabs, you might do:
68 //
69 //              left = 0;
70 //              right = N - 1;     /* rightmost stab */
71 //              stab_binsearch(stabs, &left, &right, type, addr);
72 //
73 //      The search modifies *region_left and *region_right to bracket the
74 //      'addr'.  *region_left points to the matching stab that contains
75 //      'addr', and *region_right points just before the next stab.  If
76 //      *region_left > *region_right, then 'addr' is not contained in any
77 //      matching stab.
78 //
79 //      For example, given these N_SO stabs:
80 //              Index  Type   Address
81 //              0      SO     f0100000
82 //              13     SO     f0100040
83 //              117    SO     f0100176
84 //              118    SO     f0100178
85 //              555    SO     f0100652
86 //              556    SO     f0100654
87 //              657    SO     f0100849
88 //      this code:
89 //              left = 0, right = 657;
90 //              stab_binsearch(stabs, &left, &right, N_SO, 0xf0100184);
91 //      will exit setting left = 118, right = 554.
92 //
93 static void
94 stab_binsearch(const stab_t *stabs,
95                const stab_t *stab_end,
96                int *region_left, int *region_right,
97                int type, uintptr_t addr)
98 {
99         int l = *region_left, r = *region_right, any_matches = 0;
100
101         while (l <= r) {
102                 int true_m = (l + r) / 2, m = true_m;
103
104                 // search for earliest stab with right type
105                 while (m >= l && stabs[m].n_type != type)
106                         m--;
107                 if (m < l) {    // no match in [l, m]
108                         l = true_m + 1;
109                         continue;
110                 }
111
112                 // actual binary search
113                 any_matches = 1;
114                 if (stabs[m].n_value < addr) {
115                         *region_left = m;
116                         l = true_m + 1;
117                 } else if (stabs[m].n_value > addr) {
118                         *region_right = m - 1;
119                         r = m - 1;
120                 } else {
121                         // exact match for 'addr', but continue loop to find
122                         // *region_right
123                         *region_left = m;
124                         l = m;
125                         addr++;
126                 }
127         }
128
129         if (!any_matches)
130                 *region_right = *region_left - 1;
131         else {
132                 // find rightmost region containing 'addr'
133                 for (l = *region_right;
134                      l > *region_left && stabs[l].n_type != type;
135                      l--)
136                         /* do nothing */;
137                 *region_left = l;
138         }
139 }
140
141
142 // debuginfo_eip(addr, info)
143 //
144 //      Fill in the 'info' structure with information about the specified
145 //      instruction address, 'addr'.  Returns 0 if information was found, and
146 //      negative if not.  But even if it returns negative it has stored some
147 //      information into '*info'.
148 //
149 int
150 debuginfo_eip(uintptr_t addr, eipdebuginfo_t *info)
151 {
152         const stab_t *stab_end;
153         const stab_t *stabs;
154         const char *stabstr_end;
155         const char *stabstr;
156         int lfile, rfile, lfun, rfun, lline, rline;
157
158         // Initialize *info
159         info->eip_file = "<unknown>";
160         info->eip_line = 0;
161         info->eip_fn_name = "<unknown>";
162         info->eip_fn_namelen = 9;
163         info->eip_fn_addr = addr;
164         info->eip_fn_narg = 0;
165
166         // Find the relevant set of stabs
167         if (addr >= ULIM) {
168                 stab_end = __STAB_END__;
169                 stabs = __STAB_BEGIN__;
170                 stabstr_end = __STABSTR_END__;
171                 stabstr = __STABSTR_BEGIN__;
172         } else {
173                 /* TODO: short circuiting this, til our user space apps pack stab data
174                  * the kernel knows about */
175                 return -1;
176                 #if 0
177                 // The user-application linker script, user/user.ld,
178                 // puts information about the application's stabs (equivalent
179                 // to __STAB_BEGIN__, __STAB_END__, __STABSTR_BEGIN__, and
180                 // __STABSTR_END__) in a structure located at virtual address
181                 // USTABDATA.
182                 const user_stab_data_t *usd = (const user_stab_data_t *)USTABDATA;
183
184                 // Make sure this memory is valid.
185                 // Return -1 if it is not.  Hint: Call user_mem_check.
186                 // LAB 3: Your code here.
187
188                 stab_end = usd->stab_end;
189                 stabs = usd->stabs;
190                 stabstr_end = usd->stabstr_end;
191                 stabstr = usd->stabstr;
192
193                 // Make sure the STABS and string table memory is valid.
194                 // LAB 3: Your code here.
195                 #endif
196         }
197
198         if (!stab_table_valid(stabstr, stabstr_end))
199                 return -1;
200
201         // Now we find the right stabs that define the function containing
202         // 'eip'.  First, we find the basic source file containing 'eip'.
203         // Then, we look in that source file for the function.  Then we look
204         // for the line number.
205
206         // Search the entire set of stabs for the source file (type N_SO).
207         lfile = 0;
208         rfile = (stab_end - stabs) - 1;
209         stab_binsearch(stabs, stab_end, &lfile, &rfile, N_SO, addr);
210         if (lfile == 0)
211                 return -1;
212
213         // Search within that file's stabs for the function definition
214         // (N_FUN).
215         lfun = lfile;
216         rfun = rfile;
217         stab_binsearch(stabs, stab_end, &lfun, &rfun, N_FUN, addr);
218
219         if (lfun <= rfun) {
220                 // stabs[lfun] points to the function name
221                 // in the string table, but check bounds just in case.
222                 if (stabs[lfun].n_strx < stabstr_end - stabstr)
223                         info->eip_fn_name = stabstr + stabs[lfun].n_strx;
224                 info->eip_fn_addr = stabs[lfun].n_value;
225                 addr -= info->eip_fn_addr;
226                 // Search within the function definition for the line number.
227                 lline = lfun;
228                 rline = rfun;
229         } else {
230                 // Couldn't find function stab!  Maybe we're in an assembly
231                 // file.  Search the whole file for the line number.
232                 info->eip_fn_addr = addr;
233                 lline = lfile;
234                 rline = rfile;
235         }
236         // Ignore stuff after the colon.
237         info->eip_fn_namelen = strfind(info->eip_fn_name, ':') - info->eip_fn_name;
238
239         // Search within [lline, rline] for the line number stab.
240         // If found, set info->eip_line to the right line number.
241         // If not found, return -1.
242         //
243         // Hint:
244         //      There's a particular stabs type used for line numbers.
245         //      Look at the STABS documentation and <inc/stab.h> to find
246         //      which one.
247         // Your code here.
248
249         stab_binsearch(stabs, stab_end, &lline, &rline, N_SLINE, addr);
250         if (lline <= rline)
251                 // stabs[lline] points to the line number
252                 info->eip_line = stabs[lline].n_value;
253         else
254                 return -1;
255
256         // Search backwards from the line number for the relevant filename
257         // stab.
258         // We can't just use the "lfile" stab because inlined functions
259         // can interpolate code from a different file!
260         // Such included source files use the N_SOL stab type.
261         while (lline >= lfile
262                && stabs[lline].n_type != N_SOL
263                && (stabs[lline].n_type != N_SO || !stabs[lline].n_value))
264                 lline--;
265         if (lline >= lfile && stabs[lline].n_strx < stabstr_end - stabstr)
266                 info->eip_file = stabstr + stabs[lline].n_strx;
267
268         // Set eip_fn_narg to the number of arguments taken by the function,
269         // or 0 if there was no containing function.
270         // Your code here.
271         info->eip_fn_narg = 0;
272         if (lfun <= rfun) {
273                 lfun++;
274                 while (stabs[lfun++].n_type == N_PSYM)
275                         info->eip_fn_narg++;
276         }
277
278         return 0;
279 }
280
281 /* Returns a function pointer for a function name matching the given string. */
282 void *debug_get_fn_addr(char *fn_name)
283 {
284         const struct stab *stab_end = __STAB_END__;
285         const struct stab *stabs = __STAB_BEGIN__;
286         const char *stabstr_end = __STABSTR_END__;
287         const char *stabstr = __STABSTR_BEGIN__;
288
289         static int first_fn_idx = 0;
290         int i = first_fn_idx;
291         int len;
292         const char *stab_fn_name = 0;
293         void *retval = 0;
294
295         if (!stab_table_valid(stabstr, stabstr_end))
296                 return 0;
297
298         for (/* i set */; &stabs[i] < stab_end; i++) {
299                 if (stabs[i].n_type != N_FUN)
300                         continue;
301                 first_fn_idx = first_fn_idx ? first_fn_idx : i;
302                 /* broken stab, just keep going */
303                 if (!(stabs[i].n_strx < stabstr_end - stabstr))
304                         continue;
305                 stab_fn_name = stabstr + stabs[i].n_strx;
306                 len = strfind(stab_fn_name, ':') - stab_fn_name;
307                 if (!len)
308                         continue;
309                 /* we have a match. */
310                 if (!strncmp(stab_fn_name, fn_name, len)) {
311                         printd("FN name: %s, Addr: %p\n", stab_fn_name, stabs[i].n_value);
312                         retval = (void*)stabs[i].n_value;
313                         break;
314                 }
315         }
316         return retval;
317 }
318
319 void gen_backtrace(void (*pfunc)(void *, const char *), void *opaque)
320 {
321         uintptr_t ebp, eip;
322         uintptr_t pcs[MAX_BT_DEPTH];
323         size_t nr_pcs;
324
325         GET_FRAME_START(ebp, eip);
326         nr_pcs = backtrace_list(eip, ebp, pcs, MAX_BT_DEPTH);
327         print_backtrace_list(pcs, nr_pcs, pfunc, opaque);
328 }
329
330 static bool pc_is_asm_trampoline(uintptr_t pc)
331 {
332         extern char __asm_entry_points_start[], __asm_entry_points_end[];
333         extern char __asm_pop_hwtf_start[], __asm_pop_hwtf_end[];
334         extern char __asm_pop_swtf_start[], __asm_pop_swtf_end[];
335         extern char __asm_pop_vmtf_start[], __asm_pop_vmtf_end[];
336
337         if (((uintptr_t)__asm_entry_points_start <= pc) &&
338             (pc < (uintptr_t)__asm_entry_points_end))
339                 return TRUE;
340         if (((uintptr_t)__asm_pop_hwtf_start <= pc) &&
341             (pc < (uintptr_t)__asm_pop_hwtf_end))
342                 return TRUE;
343         if (((uintptr_t)__asm_pop_swtf_start <= pc) &&
344             (pc < (uintptr_t)__asm_pop_swtf_end))
345                 return TRUE;
346         if (((uintptr_t)__asm_pop_vmtf_start <= pc) &&
347             (pc < (uintptr_t)__asm_pop_vmtf_end))
348                 return TRUE;
349         return FALSE;
350 }
351
352 size_t backtrace_list(uintptr_t pc, uintptr_t fp, uintptr_t *pcs,
353                       size_t nr_slots)
354 {
355         size_t nr_pcs = 0;
356
357         while (nr_pcs < nr_slots) {
358                 pcs[nr_pcs++] = pc;
359                 printd("PC %p FP %p\n", pc, fp);
360                 if (pc_is_asm_trampoline(pc))
361                         break;
362                 if (!fp)
363                         break;
364                 assert(KERNBASE <= fp);
365                 /* We need to check the next FP before reading PC from beyond it.  FP
366                  * could be 0 and be at the top of the stack, and reading PC in that
367                  * case will be a wild read. */
368                 if (!*(uintptr_t*)fp)
369                         break;
370                 /* We used to set PC = retaddr - 1, where the -1 would put our PC back
371                  * inside the function that called us.  This was for obscure cases where
372                  * a no-return function calls another function and has no other code
373                  * after the function call.  Or something. */
374                 pc = *(uintptr_t*)(fp + sizeof(uintptr_t));
375                 fp = *(uintptr_t*)fp;
376         }
377         return nr_pcs;
378 }
379
380 size_t backtrace_user_list(uintptr_t pc, uintptr_t fp, uintptr_t *pcs,
381                                                    size_t nr_slots)
382 {
383         int error;
384         size_t nr_pcs = 0;
385         uintptr_t frame[2];
386
387         while (nr_pcs < nr_slots) {
388                 pcs[nr_pcs++] = pc;
389                 if (!fp)
390                         break;
391                 error = copy_from_user(frame, (const void *) fp, 2 * sizeof(uintptr_t));
392                 if (unlikely(error))
393                         break;
394                 pc = frame[1];
395                 fp = frame[0];
396         }
397         return nr_pcs;
398 }
399
400 /* Assumes 32-bit header */
401 void print_fpu_state(struct ancillary_state *fpu)
402 {
403         printk("fcw:        0x%04x\n", fpu->fp_head_n64.fcw);
404         printk("fsw:        0x%04x\n", fpu->fp_head_n64.fsw);
405         printk("ftw:          0x%02x\n", fpu->fp_head_n64.ftw);
406         printk("fop:        0x%04x\n", fpu->fp_head_n64.fop);
407         printk("fpu_ip: 0x%08x\n", fpu->fp_head_n64.fpu_ip);
408         printk("cs:         0x%04x\n", fpu->fp_head_n64.cs);
409         printk("fpu_dp: 0x%08x\n", fpu->fp_head_n64.fpu_dp);
410         printk("ds:         0x%04x\n", fpu->fp_head_n64.ds);
411         printk("mxcsr:  0x%08x\n", fpu->fp_head_n64.mxcsr);
412         printk("mxcsrm: 0x%08x\n", fpu->fp_head_n64.mxcsr_mask);
413
414         for (int i = 0; i < sizeof(struct ancillary_state); i++) {
415                 if (i % 20 == 0)
416                         printk("\n");
417                 printk("%02x ", *((uint8_t*)fpu + i));
418         }
419         printk("\n");
420 }