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