Avoid some overflow cases:
[external/binutils.git] / gprof / sym_ids.c
1 #include <ctype.h>
2
3 #include "libiberty.h"
4 #include "cg_arcs.h"
5 #include "sym_ids.h"
6
7 struct sym_id
8   {
9     struct sym_id *next;
10     char *spec;                 /* parsing modifies this */
11     Table_Id which_table;
12     bool has_right;
13     struct match
14       {
15         int prev_index;         /* index of prev match */
16         Sym *prev_match;        /* previous match */
17         Sym *first_match;       /* chain of all matches */
18         Sym sym;
19       }
20     left, right;
21   }
22  *id_list;
23
24 Sym_Table syms[NUM_TABLES];
25
26 #ifdef DEBUG
27 const char *table_name[] =
28 {
29   "INCL_GRAPH", "EXCL_GRAPH",
30   "INCL_ARCS", "EXCL_ARCS",
31   "INCL_FLAT", "EXCL_FLAT",
32   "INCL_TIME", "EXCL_TIME",
33   "INCL_ANNO", "EXCL_ANNO",
34   "INCL_EXEC", "EXCL_EXEC"
35 };
36 #endif /* DEBUG */
37
38 /*
39  * This is the table in which we keep all the syms that match
40  * the right half of an arc id.  It is NOT sorted according
41  * to the addresses, because it is accessed only through
42  * the left half's CHILDREN pointers (so it's crucial not
43  * to reorder this table once pointers into it exist).
44  */
45 static Sym_Table right_ids;
46
47 static Source_File non_existent_file =
48 {
49   0, "<non-existent-file>"
50 };
51
52
53 void
54 DEFUN (sym_id_add, (spec, which_table),
55        const char *spec AND Table_Id which_table)
56 {
57   struct sym_id *id;
58   int len = strlen (spec);
59
60   id = (struct sym_id *) xmalloc (sizeof (*id) + len + 1);
61   memset (id, 0, sizeof (*id));
62
63   id->spec = (char *) id + sizeof (*id);
64   strcpy (id->spec, spec);
65   id->which_table = which_table;
66
67   id->next = id_list;
68   id_list = id;
69 }
70
71
72 /*
73  * A spec has the syntax FILENAME:(FUNCNAME|LINENUM).  As a convenience
74  * to the user, a spec without a colon is interpreted as:
75  *
76  *      (i)   a FILENAME if it contains a dot
77  *      (ii)  a FUNCNAME if it starts with a non-digit character
78  *      (iii) a LINENUM if it starts with a digit
79  *
80  * A FUNCNAME containing a dot can be specified by :FUNCNAME, a
81  * FILENAME not containing a dot can be specified by FILENAME:.
82  */
83 static void
84 DEFUN (parse_spec, (spec, sym), char *spec AND Sym * sym)
85 {
86   char *colon;
87
88   sym_init (sym);
89   colon = strrchr (spec, ':');
90   if (colon)
91     {
92       *colon = '\0';
93       if (colon > spec)
94         {
95           sym->file = source_file_lookup_name (spec);
96           if (!sym->file)
97             {
98               sym->file = &non_existent_file;
99             }
100         }
101       spec = colon + 1;
102       if (strlen (spec))
103         {
104           if (isdigit ((unsigned char) spec[0]))
105             {
106               sym->line_num = atoi (spec);
107             }
108           else
109             {
110               sym->name = spec;
111             }
112         }
113     }
114   else if (strlen (spec))
115     {
116       /* no colon: spec is a filename if it contains a dot: */
117       if (strchr (spec, '.'))
118         {
119           sym->file = source_file_lookup_name (spec);
120           if (!sym->file)
121             {
122               sym->file = &non_existent_file;
123             }
124         }
125       else if (isdigit ((unsigned char) *spec))
126         {
127           sym->line_num = atoi (spec);
128         }
129       else if (strlen (spec))
130         {
131           sym->name = spec;
132         }
133     }
134 }
135
136
137 /*
138  * A symbol id has the syntax SPEC[/SPEC], where SPEC is is defined
139  * by parse_spec().
140  */
141 static void
142 DEFUN (parse_id, (id), struct sym_id *id)
143 {
144   char *slash;
145
146   DBG (IDDEBUG, printf ("[parse_id] %s -> ", id->spec));
147
148   slash = strchr (id->spec, '/');
149   if (slash)
150     {
151       parse_spec (slash + 1, &id->right.sym);
152       *slash = '\0';
153       id->has_right = TRUE;
154     }
155   parse_spec (id->spec, &id->left.sym);
156
157 #ifdef DEBUG
158   if (debug_level & IDDEBUG)
159     {
160       printf ("%s:", id->left.sym.file ? id->left.sym.file->name : "*");
161       if (id->left.sym.name)
162         {
163           printf ("%s", id->left.sym.name);
164         }
165       else if (id->left.sym.line_num)
166         {
167           printf ("%d", id->left.sym.line_num);
168         }
169       else
170         {
171           printf ("*");
172         }
173       if (id->has_right)
174         {
175           printf ("/%s:",
176                   id->right.sym.file ? id->right.sym.file->name : "*");
177           if (id->right.sym.name)
178             {
179               printf ("%s", id->right.sym.name);
180             }
181           else if (id->right.sym.line_num)
182             {
183               printf ("%d", id->right.sym.line_num);
184             }
185           else
186             {
187               printf ("*");
188             }
189         }
190       printf ("\n");
191     }
192 #endif
193 }
194
195
196 /*
197  * Return TRUE iff PATTERN matches SYM.
198  */
199 static bool
200 DEFUN (match, (pattern, sym), Sym * pattern AND Sym * sym)
201 {
202   return (pattern->file ? pattern->file == sym->file : TRUE)
203     && (pattern->line_num ? pattern->line_num == sym->line_num : TRUE)
204     && (pattern->name ? strcmp (pattern->name, sym->name) == 0 : TRUE);
205 }
206
207
208 static void
209 DEFUN (extend_match, (m, sym, tab, second_pass),
210      struct match *m AND Sym * sym AND Sym_Table * tab AND bool second_pass)
211 {
212   if (m->prev_match != sym - 1)
213     {
214       /* discontinuity: add new match to table: */
215       if (second_pass)
216         {
217           tab->base[tab->len] = *sym;
218           m->prev_index = tab->len;
219
220           /* link match into match's chain: */
221           tab->base[tab->len].next = m->first_match;
222           m->first_match = &tab->base[tab->len];
223         }
224       ++tab->len;
225     }
226
227   /* extend match to include this symbol: */
228   if (second_pass)
229     {
230       tab->base[m->prev_index].end_addr = sym->end_addr;
231     }
232   m->prev_match = sym;
233 }
234
235
236 /*
237  * Go through sym_id list produced by option processing and fill
238  * in the various symbol tables indicating what symbols should
239  * be displayed or suppressed for the various kinds of outputs.
240  *
241  * This can potentially produce huge tables and in particulars
242  * tons of arcs, but this happens only if the user makes silly
243  * requests---you get what you ask for!
244  */
245 void
246 DEFUN_VOID (sym_id_parse)
247 {
248   Sym *sym, *left, *right;
249   struct sym_id *id;
250   Sym_Table *tab;
251
252   /*
253    * Convert symbol ids into Syms, so we can deal with them more easily:
254    */
255   for (id = id_list; id; id = id->next)
256     {
257       parse_id (id);
258     }
259
260   /* first determine size of each table: */
261
262   for (sym = symtab.base; sym < symtab.limit; ++sym)
263     {
264       for (id = id_list; id; id = id->next)
265         {
266           if (match (&id->left.sym, sym))
267             {
268               extend_match (&id->left, sym, &syms[id->which_table], FALSE);
269             }
270           if (id->has_right && match (&id->right.sym, sym))
271             {
272               extend_match (&id->right, sym, &right_ids, FALSE);
273             }
274         }
275     }
276
277   /* create tables of appropriate size and reset lengths: */
278
279   for (tab = syms; tab < &syms[NUM_TABLES]; ++tab)
280     {
281       if (tab->len)
282         {
283           tab->base = (Sym *) xmalloc (tab->len * sizeof (Sym));
284           tab->limit = tab->base + tab->len;
285           tab->len = 0;
286         }
287     }
288   if (right_ids.len)
289     {
290       right_ids.base = (Sym *) xmalloc (right_ids.len * sizeof (Sym));
291       right_ids.limit = right_ids.base + right_ids.len;
292       right_ids.len = 0;
293     }
294
295   /* make a second pass through symtab, creating syms as necessary: */
296
297   for (sym = symtab.base; sym < symtab.limit; ++sym)
298     {
299       for (id = id_list; id; id = id->next)
300         {
301           if (match (&id->left.sym, sym))
302             {
303               extend_match (&id->left, sym, &syms[id->which_table], TRUE);
304             }
305           if (id->has_right && match (&id->right.sym, sym))
306             {
307               extend_match (&id->right, sym, &right_ids, TRUE);
308             }
309         }
310     }
311
312   /* go through ids creating arcs as needed: */
313
314   for (id = id_list; id; id = id->next)
315     {
316       if (id->has_right)
317         {
318           for (left = id->left.first_match; left; left = left->next)
319             {
320               for (right = id->right.first_match; right; right = right->next)
321                 {
322                   DBG (IDDEBUG,
323                        printf (
324                                 "[sym_id_parse]: arc %s:%s(%lx-%lx) -> %s:%s(%lx-%lx) to %s\n",
325                                 left->file ? left->file->name : "*",
326                                 left->name ? left->name : "*", left->addr,
327                                 left->end_addr,
328                                 right->file ? right->file->name : "*",
329                                 right->name ? right->name : "*", right->addr,
330                                 right->end_addr,
331                                 table_name[id->which_table]));
332                   arc_add (left, right, (unsigned long) 0);
333                 }
334             }
335         }
336     }
337
338   /* finally, we can sort the tables and we're done: */
339
340   for (tab = &syms[0]; tab < &syms[NUM_TABLES]; ++tab)
341     {
342       DBG (IDDEBUG, printf ("[sym_id_parse] syms[%s]:\n",
343                             table_name[tab - &syms[0]]));
344       symtab_finalize (tab);
345     }
346 }
347
348
349 /*
350  * Symbol tables storing the FROM symbols of arcs do not necessarily
351  * have distinct address ranges.  For example, somebody might request
352  * -k /_mcount to suppress any arcs into _mcount, while at the same
353  * time requesting -k a/b.  Fortunately, those symbol tables don't get
354  * very big (the user has to type them!), so a linear search is probably
355  * tolerable.
356  */
357 bool
358 DEFUN (sym_id_arc_is_present, (symtab, from, to),
359        Sym_Table * symtab AND Sym * from AND Sym * to)
360 {
361   Sym *sym;
362
363   for (sym = symtab->base; sym < symtab->limit; ++sym)
364     {
365       if (from->addr >= sym->addr && from->addr <= sym->end_addr
366           && arc_lookup (sym, to))
367         {
368           return TRUE;
369         }
370     }
371   return FALSE;
372 }