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