Massive reorganizing and making all the makefiles consistent.
[akaros.git] / kern / src / kdebug.c
1 #ifdef __DEPUTY__
2 #pragma nodeputy
3 #endif
4
5 #include <inc/stab.h>
6 #include <inc/string.h>
7 #include <inc/memlayout.h>
8 #include <inc/assert.h>
9
10 #include <kern/kdebug.h>
11 #include <kern/pmap.h>
12 #include <kern/env.h>
13
14 extern const stab_t __STAB_BEGIN__[];   // Beginning of stabs table
15 extern const stab_t __STAB_END__[];     // End of stabs table
16 extern const char __STABSTR_BEGIN__[];          // Beginning of string table
17 extern const char __STABSTR_END__[];            // End of string table
18
19 typedef struct UserStabData {
20         const stab_t *stabs;
21         const stab_t *stab_end;
22         const char *stabstr;
23         const char *stabstr_end;
24 } user_stab_data_t;
25
26
27 // stab_binsearch(stabs, region_left, region_right, type, addr)
28 //
29 //      Some stab types are arranged in increasing order by instruction
30 //      address.  For example, N_FUN stabs (stab entries with n_type ==
31 //      N_FUN), which mark functions, and N_SO stabs, which mark source files.
32 //
33 //      Given an instruction address, this function finds the single stab
34 //      entry of type 'type' that contains that address.
35 //
36 //      The search takes place within the range [*region_left, *region_right].
37 //      Thus, to search an entire set of N stabs, you might do:
38 //
39 //              left = 0;
40 //              right = N - 1;     /* rightmost stab */
41 //              stab_binsearch(stabs, &left, &right, type, addr);
42 //
43 //      The search modifies *region_left and *region_right to bracket the
44 //      'addr'.  *region_left points to the matching stab that contains
45 //      'addr', and *region_right points just before the next stab.  If
46 //      *region_left > *region_right, then 'addr' is not contained in any
47 //      matching stab.
48 //
49 //      For example, given these N_SO stabs:
50 //              Index  Type   Address
51 //              0      SO     f0100000
52 //              13     SO     f0100040
53 //              117    SO     f0100176
54 //              118    SO     f0100178
55 //              555    SO     f0100652
56 //              556    SO     f0100654
57 //              657    SO     f0100849
58 //      this code:
59 //              left = 0, right = 657;
60 //              stab_binsearch(stabs, &left, &right, N_SO, 0xf0100184);
61 //      will exit setting left = 118, right = 554.
62 //
63 static void
64 stab_binsearch(const stab_t *stabs, int *region_left, int *region_right,
65                int type, uintptr_t addr)
66 {
67         int l = *region_left, r = *region_right, any_matches = 0;
68         
69         while (l <= r) {
70                 int true_m = (l + r) / 2, m = true_m;
71                 
72                 // search for earliest stab with right type
73                 while (m >= l && stabs[m].n_type != type)
74                         m--;
75                 if (m < l) {    // no match in [l, m]
76                         l = true_m + 1;
77                         continue;
78                 }
79
80                 // actual binary search
81                 any_matches = 1;
82                 if (stabs[m].n_value < addr) {
83                         *region_left = m;
84                         l = true_m + 1;
85                 } else if (stabs[m].n_value > addr) {
86                         *region_right = m - 1;
87                         r = m - 1;
88                 } else {
89                         // exact match for 'addr', but continue loop to find
90                         // *region_right
91                         *region_left = m;
92                         l = m;
93                         addr++;
94                 }
95         }
96
97         if (!any_matches)
98                 *region_right = *region_left - 1;
99         else {
100                 // find rightmost region containing 'addr'
101                 for (l = *region_right;
102                      l > *region_left && stabs[l].n_type != type;
103                      l--)
104                         /* do nothing */;
105                 *region_left = l;
106         }
107 }
108
109
110 // debuginfo_eip(addr, info)
111 //
112 //      Fill in the 'info' structure with information about the specified
113 //      instruction address, 'addr'.  Returns 0 if information was found, and
114 //      negative if not.  But even if it returns negative it has stored some
115 //      information into '*info'.
116 //
117 int
118 debuginfo_eip(uintptr_t addr, eipdebuginfo_t *info)
119 {
120         const stab_t *stabs, *stab_end;
121         const char *stabstr, *stabstr_end;
122         int lfile, rfile, lfun, rfun, lline, rline;
123
124         // Initialize *info
125         info->eip_file = "<unknown>";
126         info->eip_line = 0;
127         info->eip_fn_name = "<unknown>";
128         info->eip_fn_namelen = 9;
129         info->eip_fn_addr = addr;
130         info->eip_fn_narg = 0;
131
132         // Find the relevant set of stabs
133         if (addr >= ULIM) {
134                 stabs = __STAB_BEGIN__;
135                 stab_end = __STAB_END__;
136                 stabstr = __STABSTR_BEGIN__;
137                 stabstr_end = __STABSTR_END__;
138         } else {
139                 // The user-application linker script, user/user.ld,
140                 // puts information about the application's stabs (equivalent
141                 // to __STAB_BEGIN__, __STAB_END__, __STABSTR_BEGIN__, and
142                 // __STABSTR_END__) in a structure located at virtual address
143                 // USTABDATA.
144                 const user_stab_data_t *usd = (const user_stab_data_t *) USTABDATA;
145
146                 // Make sure this memory is valid.
147                 // Return -1 if it is not.  Hint: Call user_mem_check.
148                 // LAB 3: Your code here.
149                 
150                 stabs = usd->stabs;
151                 stab_end = usd->stab_end;
152                 stabstr = usd->stabstr;
153                 stabstr_end = usd->stabstr_end;
154
155                 // Make sure the STABS and string table memory is valid.
156                 // LAB 3: Your code here.
157         }
158
159         // String table validity checks
160         if (stabstr_end <= stabstr || stabstr_end[-1] != 0)
161                 return -1;
162
163         // Now we find the right stabs that define the function containing
164         // 'eip'.  First, we find the basic source file containing 'eip'.
165         // Then, we look in that source file for the function.  Then we look
166         // for the line number.
167         
168         // Search the entire set of stabs for the source file (type N_SO).
169         lfile = 0;
170         rfile = (stab_end - stabs) - 1;
171         stab_binsearch(stabs, &lfile, &rfile, N_SO, addr);
172         if (lfile == 0)
173                 return -1;
174
175         // Search within that file's stabs for the function definition
176         // (N_FUN).
177         lfun = lfile;
178         rfun = rfile;
179         stab_binsearch(stabs, &lfun, &rfun, N_FUN, addr);
180
181         if (lfun <= rfun) {
182                 // stabs[lfun] points to the function name
183                 // in the string table, but check bounds just in case.
184                 if (stabs[lfun].n_strx < stabstr_end - stabstr)
185                         info->eip_fn_name = stabstr + stabs[lfun].n_strx;
186                 info->eip_fn_addr = stabs[lfun].n_value;
187                 addr -= info->eip_fn_addr;
188                 // Search within the function definition for the line number.
189                 lline = lfun;
190                 rline = rfun;
191         } else {
192                 // Couldn't find function stab!  Maybe we're in an assembly
193                 // file.  Search the whole file for the line number.
194                 info->eip_fn_addr = addr;
195                 lline = lfile;
196                 rline = rfile;
197         }
198         // Ignore stuff after the colon.
199         info->eip_fn_namelen = strfind(info->eip_fn_name, ':') - info->eip_fn_name;
200         
201         // Search within [lline, rline] for the line number stab.
202         // If found, set info->eip_line to the right line number.
203         // If not found, return -1.
204         //
205         // Hint:
206         //      There's a particular stabs type used for line numbers.
207         //      Look at the STABS documentation and <inc/stab.h> to find
208         //      which one.
209         // Your code here.
210
211         stab_binsearch(stabs, &lline, &rline, N_SLINE, addr);
212         if (lline <= rline) 
213                 // stabs[lline] points to the line number
214                 info->eip_line = stabs[lline].n_value;
215         else
216                 return -1;
217         
218         // Search backwards from the line number for the relevant filename
219         // stab.
220         // We can't just use the "lfile" stab because inlined functions
221         // can interpolate code from a different file!
222         // Such included source files use the N_SOL stab type.
223         while (lline >= lfile
224                && stabs[lline].n_type != N_SOL
225                && (stabs[lline].n_type != N_SO || !stabs[lline].n_value))
226                 lline--;
227         if (lline >= lfile && stabs[lline].n_strx < stabstr_end - stabstr)
228                 info->eip_file = stabstr + stabs[lline].n_strx;
229
230         // Set eip_fn_narg to the number of arguments taken by the function,
231         // or 0 if there was no containing function.
232         // Your code here.
233         info->eip_fn_narg = 0;
234         if (lfun <= rfun) {
235                 lfun++;
236                 while (stabs[lfun++].n_type == N_PSYM)
237                         info->eip_fn_narg++;
238         }
239         
240         return 0;
241 }