Implement -c/--call-pairs option to emit list with
[kopensolaris-gnu/glibc.git] / elf / sprof.c
1 /* Read and display shared object profiling data.
2    Copyright (C) 1997, 1998 Free Software Foundation, Inc.
3    This file is part of the GNU C Library.
4    Contributed by Ulrich Drepper <drepper@cygnus.com>, 1997.
5
6    The GNU C Library is free software; you can redistribute it and/or
7    modify it under the terms of the GNU Library General Public License as
8    published by the Free Software Foundation; either version 2 of the
9    License, or (at your option) any later version.
10
11    The GNU C Library is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14    Library General Public License for more details.
15
16    You should have received a copy of the GNU Library General Public
17    License along with the GNU C Library; see the file COPYING.LIB.  If not,
18    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19    Boston, MA 02111-1307, USA.  */
20
21 #include <argp.h>
22 #include <dlfcn.h>
23 #include <elf.h>
24 #include <error.h>
25 #include <fcntl.h>
26 #include <inttypes.h>
27 #include <libintl.h>
28 #include <locale.h>
29 #include <obstack.h>
30 #include <search.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <unistd.h>
35 #include <elf/ldsodefs.h>
36 #include <sys/gmon.h>
37 #include <sys/gmon_out.h>
38 #include <sys/mman.h>
39 #include <sys/param.h>
40 #include <sys/stat.h>
41
42 /* Undefine the following line line in the production version.  */
43 /* #define _NDEBUG 1 */
44 #include <assert.h>
45
46 /* Get libc version number.  */
47 #include "../version.h"
48
49 #define PACKAGE _libc_intl_domainname
50
51
52 #include <endian.h>
53 #if BYTE_ORDER == BIG_ENDIAN
54 #define byteorder ELFDATA2MSB
55 #define byteorder_name "big-endian"
56 #elif BYTE_ORDER == LITTLE_ENDIAN
57 #define byteorder ELFDATA2LSB
58 #define byteorder_name "little-endian"
59 #else
60 #error "Unknown BYTE_ORDER " BYTE_ORDER
61 #define byteorder ELFDATANONE
62 #endif
63
64
65 extern int __profile_frequency __P ((void));
66
67 /* Name and version of program.  */
68 static void print_version (FILE *stream, struct argp_state *state);
69 void (*argp_program_version_hook) (FILE *, struct argp_state *) = print_version;
70
71 #define OPT_TEST        1
72
73 /* Definitions of arguments for argp functions.  */
74 static const struct argp_option options[] =
75 {
76   { NULL, 0, NULL, 0, N_("Output selection:") },
77   { "call-pairs", 'c', NULL, 0,
78     N_("print list of count paths and their number of use") },
79   { "flat-profile", 'p', NULL, 0,
80     N_("generate flat profile with counts and ticks") },
81   { "graph", 'q', NULL, 0, N_("generate call graph") },
82
83   { "test", OPT_TEST, NULL, OPTION_HIDDEN, NULL },
84   { NULL, 0, NULL, 0, NULL }
85 };
86
87 /* Short description of program.  */
88 static const char doc[] = N_("Read and display shared object profiling data");
89
90 /* Strings for arguments in help texts.  */
91 static const char args_doc[] = N_("SHOBJ [PROFDATA]");
92
93 /* Prototype for option handler.  */
94 static error_t parse_opt (int key, char *arg, struct argp_state *state);
95
96 /* Data structure to communicate with argp functions.  */
97 static struct argp argp =
98 {
99   options, parse_opt, args_doc, doc, NULL, NULL
100 };
101
102
103 /* Operation modes.  */
104 static enum
105 {
106   NONE = 0,
107   FLAT_MODE = 1 << 0,
108   CALL_GRAPH_MODE = 1 << 1,
109   CALL_PAIRS = 1 << 2,
110
111   DEFAULT_MODE = FLAT_MODE | CALL_GRAPH_MODE
112 } mode;
113
114 /* If nonzero the total number of invocations of a function is emitted.  */
115 int count_total;
116
117 /* Nozero for testing.  */
118 int do_test;
119
120 /* Strcuture describing calls.  */
121 struct here_fromstruct
122 {
123   struct here_cg_arc_record volatile *here;
124   uint16_t link;
125 };
126
127 /* We define a special type to address the elements of the arc table.
128    This is basically the `gmon_cg_arc_record' format but it includes
129    the room for the tag and it uses real types.  */
130 struct here_cg_arc_record
131 {
132   uintptr_t from_pc;
133   uintptr_t self_pc;
134   uint32_t count;
135 } __attribute__ ((packed));
136
137
138 struct known_symbol;
139 struct arc_list
140 {
141   size_t idx;
142   uintmax_t count;
143
144   struct arc_list *next;
145 };
146
147 static struct obstack ob_list;
148
149
150 struct known_symbol
151 {
152   const char *name;
153   uintptr_t addr;
154   size_t size;
155
156   uintmax_t ticks;
157   uintmax_t calls;
158
159   struct arc_list *froms;
160   struct arc_list *tos;
161 };
162
163
164 struct shobj
165 {
166   const char *name;             /* User-provided name.  */
167
168   struct link_map *map;
169   const char *dynstrtab;        /* Dynamic string table of shared object.  */
170   const char *soname;           /* Soname of shared object.  */
171
172   uintptr_t lowpc;
173   uintptr_t highpc;
174   unsigned long int kcountsize;
175   size_t expected_size;         /* Expected size of profiling file.  */
176   size_t tossize;
177   size_t fromssize;
178   size_t fromlimit;
179   unsigned int hashfraction;
180   int s_scale;
181
182   void *symbol_map;
183   size_t symbol_mapsize;
184   const ElfW(Sym) *symtab;
185   size_t symtab_size;
186   const char *strtab;
187
188   struct obstack ob_str;
189   struct obstack ob_sym;
190 };
191
192
193 struct profdata
194 {
195   void *addr;
196   off_t size;
197
198   char *hist;
199   struct gmon_hist_hdr *hist_hdr;
200   uint16_t *kcount;
201   uint32_t narcs;               /* Number of arcs in toset.  */
202   struct here_cg_arc_record *data;
203   uint16_t *tos;
204   struct here_fromstruct *froms;
205 };
206
207 /* Search tree for symbols.  */
208 void *symroot;
209 static struct known_symbol **sortsym;
210 static size_t symidx;
211 static uintmax_t total_ticks;
212
213 /* Prototypes for local functions.  */
214 static struct shobj *load_shobj (const char *name);
215 static void unload_shobj (struct shobj *shobj);
216 static struct profdata *load_profdata (const char *name, struct shobj *shobj);
217 static void unload_profdata (struct profdata *profdata);
218 static void count_total_ticks (struct shobj *shobj, struct profdata *profdata);
219 static void count_calls (struct shobj *shobj, struct profdata *profdata);
220 static void read_symbols (struct shobj *shobj);
221 static void add_arcs (struct profdata *profdata);
222 static void generate_flat_profile (struct profdata *profdata);
223 static void generate_call_graph (struct profdata *profdata);
224 static void generate_call_pair_list (struct profdata *profdata);
225
226
227 int
228 main (int argc, char *argv[])
229 {
230   const char *shobj;
231   const char *profdata;
232   struct shobj *shobj_handle;
233   struct profdata *profdata_handle;
234   int remaining;
235
236   setlocale (LC_ALL, "");
237
238   /* Initialize the message catalog.  */
239   textdomain (_libc_intl_domainname);
240
241   /* Parse and process arguments.  */
242   argp_parse (&argp, argc, argv, 0, &remaining, NULL);
243
244   if (argc - remaining == 0 || argc - remaining > 2)
245     {
246       /* We need exactly two non-option parameter.  */
247       argp_help (&argp, stdout, ARGP_HELP_SEE | ARGP_HELP_EXIT_ERR,
248                  program_invocation_short_name);
249       exit (1);
250     }
251
252   /* Get parameters.  */
253   shobj = argv[remaining];
254   if (argc - remaining == 2)
255     profdata = argv[remaining + 1];
256   else
257     /* No filename for the profiling data given.  We will determine it
258        from the soname of the shobj, later.  */
259     profdata = NULL;
260
261   /* First see whether we can load the shared object.  */
262   shobj_handle = load_shobj (shobj);
263   if (shobj_handle == NULL)
264     exit (1);
265
266   /* We can now determine the filename for the profiling data, if
267      nececessary.  */
268   if (profdata == NULL)
269     {
270       char *newp;
271
272       if (shobj_handle->soname == NULL)
273         {
274           unload_shobj (shobj_handle);
275
276           error (EXIT_FAILURE, 0, _("\
277 no filename for profiling data given and shared object `%s' has no soname"),
278                  shobj);
279         }
280
281       newp = (char *) alloca (strlen (shobj_handle->soname)
282                               + sizeof ".profile");
283       stpcpy (stpcpy (newp, shobj_handle->soname), ".profile");
284       profdata = newp;
285     }
286
287   /* Now see whether the profiling data file matches the given object.   */
288   profdata_handle = load_profdata (profdata, shobj_handle);
289   if (profdata_handle == NULL)
290     {
291       unload_shobj (shobj_handle);
292
293       exit (1);
294     }
295
296   read_symbols (shobj_handle);
297
298   /* Count the ticks.  */
299   count_total_ticks (shobj_handle, profdata_handle);
300
301   /* Count the calls.  */
302   count_calls (shobj_handle, profdata_handle);
303
304   /* Add the arc information.  */
305   add_arcs (profdata_handle);
306
307   /* If no mode is specified fall back to the default mode.  */
308   if (mode == NONE)
309     mode = DEFAULT_MODE;
310
311   /* Do some work.  */
312   if (mode & FLAT_MODE)
313     generate_flat_profile (profdata_handle);
314
315   if (mode & CALL_GRAPH_MODE)
316     generate_call_graph (profdata_handle);
317
318   if (mode & CALL_PAIRS)
319     generate_call_pair_list (profdata_handle);
320
321   /* Free the resources.  */
322   unload_shobj (shobj_handle);
323   unload_profdata (profdata_handle);
324
325   return 0;
326 }
327
328
329 /* Handle program arguments.  */
330 static error_t
331 parse_opt (int key, char *arg, struct argp_state *state)
332 {
333   switch (key)
334     {
335     case 'c':
336       mode |= CALL_PAIRS;
337       break;
338     case 'p':
339       mode |= FLAT_MODE;
340       break;
341     case 'q':
342       mode |= CALL_GRAPH_MODE;
343       break;
344     case OPT_TEST:
345       do_test = 1;
346       break;
347     default:
348       return ARGP_ERR_UNKNOWN;
349     }
350   return 0;
351 }
352
353
354 /* Print the version information.  */
355 static void
356 print_version (FILE *stream, struct argp_state *state)
357 {
358   fprintf (stream, "sprof (GNU %s) %s\n", PACKAGE, VERSION);
359   fprintf (stream, gettext ("\
360 Copyright (C) %s Free Software Foundation, Inc.\n\
361 This is free software; see the source for copying conditions.  There is NO\n\
362 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\
363 "),
364            "1997, 1998");
365   fprintf (stream, gettext ("Written by %s.\n"), "Ulrich Drepper");
366 }
367
368
369 /* Note that we must not use `dlopen' etc.  The shobj object must not
370    be loaded for use.  */
371 static struct shobj *
372 load_shobj (const char *name)
373 {
374   struct link_map *map = NULL;
375   struct shobj *result;
376   ElfW(Addr) mapstart = ~((ElfW(Addr)) 0);
377   ElfW(Addr) mapend = 0;
378   const ElfW(Phdr) *ph;
379   size_t textsize;
380   unsigned int log_hashfraction;
381   ElfW(Ehdr) *ehdr;
382   int fd;
383   ElfW(Shdr) *shdr;
384   void *ptr;
385   size_t pagesize = getpagesize ();
386   const char *shstrtab;
387   int idx;
388   ElfW(Shdr) *symtab_entry;
389
390   /* Since we use dlopen() we must be prepared to work around the sometimes
391      strange lookup rules for the shared objects.  If we have a file foo.so
392      in the current directory and the user specfies foo.so on the command
393      line (without specifying a directory) we should load the file in the
394      current directory even if a normal dlopen() call would read the other
395      file.  We do this by adding a directory portion to the name.  */
396   if (strchr (name, '/') == NULL)
397     {
398       char *load_name = (char *) alloca (strlen (name) + 3);
399       stpcpy (stpcpy (load_name, "./"), name);
400
401       map = (struct link_map *) dlopen (load_name, RTLD_LAZY);
402     }
403   if (map == NULL)
404     {
405       map = (struct link_map *) dlopen (name, RTLD_LAZY);
406       if (map == NULL)
407         {
408           error (0, errno, _("failed to load shared object `%s'"), name);
409           return NULL;
410         }
411     }
412
413   /* Prepare the result.  */
414   result = (struct shobj *) calloc (1, sizeof (struct shobj));
415   if (result == NULL)
416     {
417       error (0, errno, _("cannot create internal descriptors"));
418       dlclose (map);
419       return NULL;
420     }
421   result->name = name;
422   result->map = map;
423
424   /* Compute the size of the sections which contain program code.
425      This must match the code in dl-profile.c (_dl_start_profile).  */
426   for (ph = map->l_phdr; ph < &map->l_phdr[map->l_phnum]; ++ph)
427     if (ph->p_type == PT_LOAD && (ph->p_flags & PF_X))
428       {
429         ElfW(Addr) start = (ph->p_vaddr & ~(pagesize - 1));
430         ElfW(Addr) end = ((ph->p_vaddr + ph->p_memsz + pagesize - 1)
431                           & ~(pagesize - 1));
432
433         if (start < mapstart)
434           mapstart = start;
435         if (end > mapend)
436           mapend = end;
437       }
438
439   result->lowpc = ROUNDDOWN ((uintptr_t) (mapstart + map->l_addr),
440                              HISTFRACTION * sizeof (HISTCOUNTER));
441   result->highpc = ROUNDUP ((uintptr_t) (mapend + map->l_addr),
442                             HISTFRACTION * sizeof (HISTCOUNTER));
443   if (do_test)
444     printf ("load addr: %0#*" PRIxPTR "\n"
445             "lower bound PC: %0#*" PRIxPTR "\n"
446             "upper bound PC: %0#*" PRIxPTR "\n",
447             __ELF_NATIVE_CLASS == 32 ? 10 : 18, map->l_addr,
448             __ELF_NATIVE_CLASS == 32 ? 10 : 18, result->lowpc,
449             __ELF_NATIVE_CLASS == 32 ? 10 : 18, result->highpc);
450
451   textsize = result->highpc - result->lowpc;
452   result->kcountsize = textsize / HISTFRACTION;
453   result->hashfraction = HASHFRACTION;
454   if ((HASHFRACTION & (HASHFRACTION - 1)) == 0)
455     /* If HASHFRACTION is a power of two, mcount can use shifting
456        instead of integer division.  Precompute shift amount.  */
457     log_hashfraction = __builtin_ffs (result->hashfraction
458                                       * sizeof (struct here_fromstruct)) - 1;
459   else
460     log_hashfraction = -1;
461   if (do_test)
462     printf ("hashfraction = %d\ndivider = %Zu\n",
463             result->hashfraction,
464             result->hashfraction * sizeof (struct here_fromstruct));
465   result->tossize = textsize / HASHFRACTION;
466   result->fromlimit = textsize * ARCDENSITY / 100;
467   if (result->fromlimit < MINARCS)
468     result->fromlimit = MINARCS;
469   if (result->fromlimit > MAXARCS)
470     result->fromlimit = MAXARCS;
471   result->fromssize = result->fromlimit * sizeof (struct here_fromstruct);
472
473   result->expected_size = (sizeof (struct gmon_hdr)
474                            + 4 + sizeof (struct gmon_hist_hdr)
475                            + result->kcountsize
476                            + 4 + 4
477                            + (result->fromssize
478                               * sizeof (struct here_cg_arc_record)));
479
480   if (do_test)
481     printf ("expected size: %Zd\n", result->expected_size);
482
483 #define SCALE_1_TO_1    0x10000L
484
485   if (result->kcountsize < result->highpc - result->lowpc)
486     {
487       size_t range = result->highpc - result->lowpc;
488       size_t quot = range / result->kcountsize;
489
490       if (quot >= SCALE_1_TO_1)
491         result->s_scale = 1;
492       else if (quot >= SCALE_1_TO_1 / 256)
493         result->s_scale = SCALE_1_TO_1 / quot;
494       else if (range > ULONG_MAX / 256)
495         result->s_scale = ((SCALE_1_TO_1 * 256)
496                            / (range / (result->kcountsize / 256)));
497       else
498         result->s_scale = ((SCALE_1_TO_1 * 256)
499                            / ((range * 256) / result->kcountsize));
500     }
501   else
502     result->s_scale = SCALE_1_TO_1;
503
504   if (do_test)
505     printf ("s_scale: %d\n", result->s_scale);
506
507   /* Determine the dynamic string table.  */
508   if (map->l_info[DT_STRTAB] == NULL)
509     result->dynstrtab = NULL;
510   else
511     result->dynstrtab = (const char *) (map->l_addr
512                                         + map->l_info[DT_STRTAB]->d_un.d_ptr);
513   if (do_test)
514     printf ("string table: %p\n", result->dynstrtab);
515
516   /* Determine the soname.  */
517   if (map->l_info[DT_SONAME] == NULL)
518     result->soname = NULL;
519   else
520     result->soname = result->dynstrtab + map->l_info[DT_SONAME]->d_un.d_val;
521   if (do_test)
522     printf ("soname: %s\n", result->soname);
523
524   /* Now we have to load the symbol table.
525
526      First load the section header table.  */
527   ehdr = (ElfW(Ehdr) *) map->l_addr;
528
529   /* Make sure we are on the right party.  */
530   if (ehdr->e_shentsize != sizeof (ElfW(Shdr)))
531     abort ();
532
533   /* And we need the shared object file descriptor again.  */
534   fd = open (map->l_name, O_RDONLY);
535   if (fd == -1)
536     /* Dooh, this really shouldn't happen.  We know the file is available.  */
537     error (EXIT_FAILURE, errno, _("Reopening shared object `%s' failed"));
538
539   /* Now map the section header.  */
540   ptr = mmap (NULL, (ehdr->e_shnum * sizeof (ElfW(Shdr))
541                      + (ehdr->e_shoff & (pagesize - 1))), PROT_READ,
542               MAP_SHARED|MAP_FILE, fd, ehdr->e_shoff & ~(pagesize - 1));
543   if (ptr == MAP_FAILED)
544     error (EXIT_FAILURE, errno, _("mapping of section headers failed"));
545   shdr = (ElfW(Shdr) *) ((char *) ptr + (ehdr->e_shoff & (pagesize - 1)));
546
547   /* Get the section header string table.  */
548   ptr = mmap (NULL, (shdr[ehdr->e_shstrndx].sh_size
549                      + (shdr[ehdr->e_shstrndx].sh_offset & (pagesize - 1))),
550               PROT_READ, MAP_SHARED|MAP_FILE, fd,
551               shdr[ehdr->e_shstrndx].sh_offset & ~(pagesize - 1));
552   if (ptr == MAP_FAILED)
553     error (EXIT_FAILURE, errno,
554            _("mapping of section header string table failed"));
555   shstrtab = ((const char *) ptr
556               + (shdr[ehdr->e_shstrndx].sh_offset & (pagesize - 1)));
557
558   /* Search for the ".symtab" section.  */
559   symtab_entry = NULL;
560   for (idx = 0; idx < ehdr->e_shnum; ++idx)
561     if (shdr[idx].sh_type == SHT_SYMTAB
562         && strcmp (shstrtab + shdr[idx].sh_name, ".symtab") == 0)
563       {
564         symtab_entry = &shdr[idx];
565         break;
566       }
567
568   /* We don't need the section header string table anymore.  */
569   munmap (ptr, (shdr[ehdr->e_shstrndx].sh_size
570                 + (shdr[ehdr->e_shstrndx].sh_offset & (pagesize - 1))));
571
572   if (symtab_entry == NULL)
573     {
574       fprintf (stderr, _("\
575 *** The file `%s' is stripped: no detailed analysis possible\n"),
576               name);
577       result->symtab = NULL;
578       result->strtab = NULL;
579     }
580   else
581     {
582       ElfW(Off) min_offset, max_offset;
583       ElfW(Shdr) *strtab_entry;
584
585       strtab_entry = &shdr[symtab_entry->sh_link];
586
587       /* Find the minimum and maximum offsets that include both the symbol
588          table and the string table.  */
589       if (symtab_entry->sh_offset < strtab_entry->sh_offset)
590         {
591           min_offset = symtab_entry->sh_offset & ~(pagesize - 1);
592           max_offset = strtab_entry->sh_offset + strtab_entry->sh_size;
593         }
594       else
595         {
596           min_offset = strtab_entry->sh_offset & ~(pagesize - 1);
597           max_offset = symtab_entry->sh_offset + symtab_entry->sh_size;
598         }
599
600       result->symbol_map = mmap (NULL, max_offset - min_offset,
601                                  PROT_READ, MAP_SHARED|MAP_FILE, fd,
602                                  min_offset);
603       if (result->symbol_map == NULL)
604         error (EXIT_FAILURE, errno, _("failed to load symbol data"));
605
606       result->symtab
607         = (const ElfW(Sym) *) ((const char *) result->symbol_map
608                                + (symtab_entry->sh_offset - min_offset));
609       result->symtab_size = symtab_entry->sh_size;
610       result->strtab = ((const char *) result->symbol_map
611                         + (strtab_entry->sh_offset - min_offset));
612       result->symbol_mapsize = max_offset - min_offset;
613     }
614
615   /* Now we also don't need the section header table anymore.  */
616   munmap ((char *) shdr - (ehdr->e_shoff & (pagesize - 1)),
617           (ehdr->e_phnum * sizeof (ElfW(Shdr))
618            + (ehdr->e_shoff & (pagesize - 1))));
619
620   /* Free the descriptor for the shared object.  */
621   close (fd);
622
623   return result;
624 }
625
626
627 static void
628 unload_shobj (struct shobj *shobj)
629 {
630   munmap (shobj->symbol_map, shobj->symbol_mapsize);
631   dlclose (shobj->map);
632 }
633
634
635 static struct profdata *
636 load_profdata (const char *name, struct shobj *shobj)
637 {
638   struct profdata *result;
639   int fd;
640   struct stat st;
641   void *addr;
642   struct gmon_hdr gmon_hdr;
643   struct gmon_hist_hdr hist_hdr;
644   uint32_t *narcsp;
645   size_t fromlimit;
646   struct here_cg_arc_record *data;
647   struct here_fromstruct *froms;
648   uint16_t *tos;
649   size_t fromidx;
650   size_t idx;
651
652   fd = open (name, O_RDONLY);
653   if (fd == -1)
654     {
655       char *ext_name;
656
657       if (errno != ENOENT || strchr (name, '/') != NULL)
658         /* The file exists but we are not allowed to read it or the
659            file does not exist and the name includes a path
660            specification..  */
661         return NULL;
662
663       /* A file with the given name does not exist in the current
664          directory, try it in the default location where the profiling
665          files are created.  */
666       ext_name = (char *) alloca (strlen (name) + sizeof "/var/tmp/");
667       stpcpy (stpcpy (ext_name, "/var/tmp/"), name);
668       name = ext_name;
669
670       fd = open (ext_name, O_RDONLY);
671       if (fd == -1)
672         {
673           /* Even this file does not exist.  */
674           error (0, errno, _("cannot load profiling data"));
675           return NULL;
676         }
677     }
678
679   /* We have found the file, now make sure it is the right one for the
680      data file.  */
681   if (fstat (fd, &st) < 0)
682     {
683       error (0, errno, _("while stat'ing profiling data file"));
684       close (fd);
685       return NULL;
686     }
687
688   if (st.st_size != shobj->expected_size)
689     {
690       error (0, 0, _("profiling data file `%s' does match shared object `%s'"),
691              name, shobj->name);
692       close (fd);
693       return NULL;
694     }
695
696   /* The data file is most probably the right one for our shared
697      object.  Map it now.  */
698   addr = mmap (NULL, st.st_size, PROT_READ, MAP_SHARED|MAP_FILE, fd, 0);
699   if (addr == MAP_FAILED)
700     {
701       error (0, errno, _("failed to mmap the profiling data file"));
702       close (fd);
703       return NULL;
704     }
705
706   /* We don't need the file desriptor anymore.  */
707   if (close (fd) < 0)
708     {
709       error (0, errno, _("error while closing the profiling data file"));
710       munmap (addr, st.st_size);
711       return NULL;
712     }
713
714   /* Prepare the result.  */
715   result = (struct profdata *) calloc (1, sizeof (struct profdata));
716   if (result == NULL)
717     {
718       error (0, errno, _("cannot create internal descriptor"));
719       munmap (addr, st.st_size);
720       return NULL;
721     }
722
723   /* Store the address and size so that we can later free the resources.  */
724   result->addr = addr;
725   result->size = st.st_size;
726
727   /* Pointer to data after the header.  */
728   result->hist = (char *) ((struct gmon_hdr *) addr + 1);
729   result->hist_hdr = (struct gmon_hist_hdr *) ((char *) result->hist
730                                                + sizeof (uint32_t));
731   result->kcount = (uint16_t *) ((char *) result->hist + sizeof (uint32_t)
732                                  + sizeof (struct gmon_hist_hdr));
733
734   /* Compute pointer to array of the arc information.  */
735   narcsp = (uint32_t *) ((char *) result->kcount + shobj->kcountsize
736                          + sizeof (uint32_t));
737   result->narcs = *narcsp;
738   result->data = (struct here_cg_arc_record *) ((char *) narcsp
739                                                 + sizeof (uint32_t));
740
741   /* Create the gmon_hdr we expect or write.  */
742   memset (&gmon_hdr, '\0', sizeof (struct gmon_hdr));
743   memcpy (&gmon_hdr.cookie[0], GMON_MAGIC, sizeof (gmon_hdr.cookie));
744   *(int32_t *) gmon_hdr.version = GMON_SHOBJ_VERSION;
745
746   /* Create the hist_hdr we expect or write.  */
747   *(char **) hist_hdr.low_pc = (char *) shobj->lowpc - shobj->map->l_addr;
748   *(char **) hist_hdr.high_pc = (char *) shobj->highpc - shobj->map->l_addr;
749   if (do_test)
750     printf ("low_pc = %p\nhigh_pc = %p\n",
751             *(char **) hist_hdr.low_pc, *(char **) hist_hdr.high_pc);
752   *(int32_t *) hist_hdr.hist_size = shobj->kcountsize / sizeof (HISTCOUNTER);
753   *(int32_t *) hist_hdr.prof_rate = __profile_frequency ();
754   strncpy (hist_hdr.dimen, "seconds", sizeof (hist_hdr.dimen));
755   hist_hdr.dimen_abbrev = 's';
756
757   /* Test whether the header of the profiling data is ok.  */
758   if (memcmp (addr, &gmon_hdr, sizeof (struct gmon_hdr)) != 0
759       || *(uint32_t *) result->hist != GMON_TAG_TIME_HIST
760       || memcmp (result->hist_hdr, &hist_hdr,
761                  sizeof (struct gmon_hist_hdr)) != 0
762       || narcsp[-1] != GMON_TAG_CG_ARC)
763     {
764       free (result);
765       error (0, 0, _("`%s' is no correct profile data file for `%s'"),
766              name, shobj->name);
767       munmap (addr, st.st_size);
768       return NULL;
769     }
770
771   /* We are pretty sure now that this is a correct input file.  Set up
772      the remaining information in the result structure and return.  */
773   result->tos = (uint16_t *) calloc (shobj->tossize + shobj->fromssize, 1);
774   if (result->tos == NULL)
775     {
776       error (0, errno, _("cannot create internal descriptor"));
777       munmap (addr, st.st_size);
778       free (result);
779       return NULL;
780     }
781
782   result->froms = (struct here_fromstruct *) ((char *) result->tos
783                                               + shobj->tossize);
784   fromidx = 0;
785
786   /* Now we have to process all the arc count entries.  */
787   fromlimit = shobj->fromlimit;
788   data = result->data;
789   froms = result->froms;
790   tos = result->tos;
791   for (idx = 0; idx < MIN (*narcsp, fromlimit); ++idx)
792     {
793       size_t to_index;
794       size_t newfromidx;
795       to_index = (data[idx].self_pc / (shobj->hashfraction * sizeof (*tos)));
796       newfromidx = fromidx++;
797       froms[newfromidx].here = &data[idx];
798       froms[newfromidx].link = tos[to_index];
799       tos[to_index] = newfromidx;
800     }
801
802   return result;
803 }
804
805
806 static void
807 unload_profdata (struct profdata *profdata)
808 {
809   free (profdata->tos);
810   munmap (profdata->addr, profdata->size);
811   free (profdata);
812 }
813
814
815 static void
816 count_total_ticks (struct shobj *shobj, struct profdata *profdata)
817 {
818   volatile uint16_t *kcount = profdata->kcount;
819   size_t maxkidx = shobj->kcountsize;
820   size_t factor = 2 * (65536 / shobj->s_scale);
821   size_t kidx = 0;
822   size_t sidx = 0;
823
824   while (sidx < symidx)
825     {
826       uintptr_t start = sortsym[sidx]->addr;
827       uintptr_t end = start + sortsym[sidx]->size;
828
829       while (kidx < maxkidx && factor * kidx < start)
830         ++kidx;
831       if (kidx == maxkidx)
832         break;
833
834       while (kidx < maxkidx && factor * kidx < end)
835         sortsym[sidx]->ticks += kcount[kidx++];
836       if (kidx == maxkidx)
837         break;
838
839       total_ticks += sortsym[sidx++]->ticks;
840     }
841 }
842
843
844 static size_t
845 find_symbol (uintptr_t addr)
846 {
847   size_t sidx = 0;
848
849   while (sidx < symidx)
850     {
851       uintptr_t start = sortsym[sidx]->addr;
852       uintptr_t end = start + sortsym[sidx]->size;
853
854       if (addr >= start && addr < end)
855         return sidx;
856
857       if (addr < start)
858         break;
859
860       ++sidx;
861     }
862
863   return (size_t) -1l;
864 }
865
866
867 static void
868 count_calls (struct shobj *shobj, struct profdata *profdata)
869 {
870   struct here_cg_arc_record *data = profdata->data;
871   uint32_t narcs = profdata->narcs;
872   uint32_t cnt;
873
874   for (cnt = 0; cnt < narcs; ++cnt)
875     {
876       uintptr_t here = data[cnt].self_pc;
877       size_t symbol_idx;
878
879       /* Find the symbol for this address.  */
880       symbol_idx = find_symbol (here);
881       if (symbol_idx != (size_t) -1l)
882         sortsym[symbol_idx]->calls += data[cnt].count;
883     }
884 }
885
886
887 static int
888 symorder (const void *o1, const void *o2)
889 {
890   const struct known_symbol *p1 = (const struct known_symbol *) o1;
891   const struct known_symbol *p2 = (const struct known_symbol *) o2;
892
893   return p1->addr - p2->addr;
894 }
895
896
897 static void
898 printsym (const void *node, VISIT value, int level)
899 {
900   if (value == leaf || value == postorder)
901     sortsym[symidx++] = *(struct known_symbol **) node;
902 }
903
904
905 static void
906 read_symbols (struct shobj *shobj)
907 {
908   void *load_addr = (void *) shobj->map->l_addr;
909   int n = 0;
910
911   /* Initialize the obstacks.  */
912 #define obstack_chunk_alloc malloc
913 #define obstack_chunk_free free
914   obstack_init (&shobj->ob_str);
915   obstack_init (&shobj->ob_sym);
916   obstack_init (&ob_list);
917
918   /* Process the symbols.  */
919   if (shobj->symtab)
920     {
921       const ElfW(Sym) *sym = shobj->symtab;
922       const ElfW(Sym) *sym_end
923         = (const ElfW(Sym) *) ((const char *) sym + shobj->symtab_size);
924       for (; sym < sym_end; sym++)
925         if ((ELFW(ST_TYPE) (sym->st_info) == STT_FUNC
926              || ELFW(ST_TYPE) (sym->st_info) == STT_NOTYPE)
927             && sym->st_size != 0)
928           {
929             struct known_symbol **existp;
930             struct known_symbol *newsym
931               = (struct known_symbol *) obstack_alloc (&shobj->ob_sym,
932                                                        sizeof (*newsym));
933             if (newsym == NULL)
934               error (EXIT_FAILURE, errno, _("cannot allocate symbol data"));
935
936             newsym->name = &shobj->strtab[sym->st_name];
937             newsym->addr = sym->st_value;
938             newsym->size = sym->st_size;
939             newsym->ticks = 0;
940             newsym->calls = 0;
941
942             existp = tfind (newsym, &symroot, symorder);
943             if (existp == NULL)
944               {
945                 /* New function.  */
946                 tsearch (newsym, &symroot, symorder);
947                 ++n;
948               }
949             else
950               {
951                 /* The function is already defined.  See whether we have
952                    a better name here.  */
953                 if ((*existp)->name[0] == '_' && newsym->name[0] != '_')
954                   *existp = newsym;
955                 else
956                   /* We don't need the allocated memory.  */
957                   obstack_free (&shobj->ob_sym, newsym);
958               }
959           }
960     }
961   else
962     {
963       /* Blarg, the binary is stripped.  We have to rely on the
964          information contained in the dynamic section of the object.  */
965       const ElfW(Sym) *symtab = (load_addr
966                                  + shobj->map->l_info[DT_SYMTAB]->d_un.d_ptr);
967       const char *strtab = (load_addr
968                             + shobj->map->l_info[DT_STRTAB]->d_un.d_ptr);
969
970       /* We assume that the string table follows the symbol table,
971          because there is no way in ELF to know the size of the
972          dynamic symbol table!!  */
973       while ((void *) symtab < (void *) strtab)
974         {
975           if ((ELFW(ST_TYPE)(symtab->st_info) == STT_FUNC
976                || ELFW(ST_TYPE)(symtab->st_info) == STT_NOTYPE)
977               && symtab->st_size != 0)
978             {
979               struct known_symbol *newsym;
980               struct known_symbol **existp;
981
982               newsym =
983                 (struct known_symbol *) obstack_alloc (&shobj->ob_sym,
984                                                        sizeof (*newsym));
985               if (newsym == NULL)
986                 error (EXIT_FAILURE, errno, _("cannot allocate symbol data"));
987
988               newsym->name = &strtab[symtab->st_name];
989               newsym->addr = symtab->st_value;
990               newsym->size = symtab->st_size;
991               newsym->ticks = 0;
992               newsym->froms = NULL;
993               newsym->tos = NULL;
994
995               existp = tfind (newsym, &symroot, symorder);
996               if (existp == NULL)
997                 {
998                   /* New function.  */
999                   tsearch (newsym, &symroot, symorder);
1000                   ++n;
1001                 }
1002               else
1003                 {
1004                   /* The function is already defined.  See whether we have
1005                      a better name here.  */
1006                   if ((*existp)->name[0] == '_' && newsym->name[0] != '_')
1007                     *existp = newsym;
1008                   else
1009                     /* We don't need the allocated memory.  */
1010                     obstack_free (&shobj->ob_sym, newsym);
1011                 }
1012             }
1013         }
1014
1015       ++symtab;
1016     }
1017
1018   sortsym = malloc (n * sizeof (struct known_symbol *));
1019   if (sortsym == NULL)
1020     abort ();
1021
1022   twalk (symroot, printsym);
1023 }
1024
1025
1026 static void
1027 add_arcs (struct profdata *profdata)
1028 {
1029   uint32_t narcs = profdata->narcs;
1030   struct here_cg_arc_record *data = profdata->data;
1031   uint32_t cnt;
1032
1033   for (cnt = 0; cnt < narcs; ++cnt)
1034     {
1035       /* First add the incoming arc.  */
1036       size_t sym_idx = find_symbol (data[cnt].self_pc);
1037
1038       if (sym_idx != (size_t) -1l)
1039         {
1040           struct known_symbol *sym = sortsym[sym_idx];
1041           struct arc_list *runp = sym->froms;
1042
1043           while (runp != NULL
1044                  && ((data[cnt].from_pc == 0 && runp->idx != (size_t) -1l)
1045                      || (data[cnt].from_pc != 0
1046                          && (runp->idx == (size_t) -1l
1047                              || data[cnt].from_pc < sortsym[runp->idx]->addr
1048                              || (data[cnt].from_pc
1049                                  >= (sortsym[runp->idx]->addr
1050                                      + sortsym[runp->idx]->size))))))
1051             runp = runp->next;
1052
1053           if (runp == NULL)
1054             {
1055               /* We need a new entry.  */
1056               struct arc_list *newp = (struct arc_list *)
1057                 obstack_alloc (&ob_list, sizeof (struct arc_list));
1058
1059               if (data[cnt].from_pc == 0)
1060                 newp->idx = (size_t) -1l;
1061               else
1062                 newp->idx = find_symbol (data[cnt].from_pc);
1063               newp->count = data[cnt].count;
1064               newp->next = sym->froms;
1065               sym->froms = newp;
1066             }
1067           else
1068             /* Increment the counter for the found entry.  */
1069             runp->count += data[cnt].count;
1070         }
1071
1072       /* Now add it to the appropriate outgoing list.  */
1073       sym_idx = find_symbol (data[cnt].from_pc);
1074       if (sym_idx != (size_t) -1l)
1075         {
1076           struct known_symbol *sym = sortsym[sym_idx];
1077           struct arc_list *runp = sym->tos;
1078
1079           while (runp != NULL
1080                  && (runp->idx == (size_t) -1l
1081                      || data[cnt].self_pc < sortsym[runp->idx]->addr
1082                      || data[cnt].self_pc >= (sortsym[runp->idx]->addr
1083                                               + sortsym[runp->idx]->size)))
1084             runp = runp->next;
1085
1086           if (runp == NULL)
1087             {
1088               /* We need a new entry.  */
1089               struct arc_list *newp = (struct arc_list *)
1090                 obstack_alloc (&ob_list, sizeof (struct arc_list));
1091
1092               newp->idx = find_symbol (data[cnt].self_pc);
1093               newp->count = data[cnt].count;
1094               newp->next = sym->tos;
1095               sym->tos = newp;
1096             }
1097           else
1098             /* Increment the counter for the found entry.  */
1099             runp->count += data[cnt].count;
1100         }
1101     }
1102 }
1103
1104
1105 static int
1106 countorder (const void *p1, const void *p2)
1107 {
1108   struct known_symbol *s1 = (struct known_symbol *) p1;
1109   struct known_symbol *s2 = (struct known_symbol *) p2;
1110
1111   if (s1->ticks != s2->ticks)
1112     return (int) (s2->ticks - s1->ticks);
1113
1114   if (s1->calls != s2->calls)
1115     return (int) (s2->calls - s1->calls);
1116
1117   return strcmp (s1->name, s2->name);
1118 }
1119
1120
1121 static double tick_unit;
1122 static uintmax_t cumu_ticks;
1123
1124 static void
1125 printflat (const void *node, VISIT value, int level)
1126 {
1127   if (value == leaf || value == postorder)
1128     {
1129       struct known_symbol *s = *(struct known_symbol **) node;
1130
1131       cumu_ticks += s->ticks;
1132
1133       printf ("%6.2f%10.2f%9.2f%9" PRIdMAX "%9.2f           %s\n",
1134               total_ticks ? (100.0 * s->ticks) / total_ticks : 0.0,
1135               tick_unit * cumu_ticks,
1136               tick_unit * s->ticks,
1137               s->calls,
1138               s->calls ? (s->ticks * 1000000) * tick_unit / s->calls : 0,
1139               /* FIXME: don't know about called functions.  */
1140               s->name);
1141     }
1142 }
1143
1144
1145 /* ARGUSED */
1146 static void
1147 freenoop (void *p)
1148 {
1149 }
1150
1151
1152 static void
1153 generate_flat_profile (struct profdata *profdata)
1154 {
1155   size_t n;
1156   void *data = NULL;
1157
1158   tick_unit = 1.0 / *(uint32_t *) profdata->hist_hdr->prof_rate;
1159
1160   printf ("Flat profile:\n\n"
1161           "Each sample counts as %g %s.\n",
1162           tick_unit, profdata->hist_hdr->dimen);
1163   fputs ("  %   cumulative   self              self     total\n"
1164          " time   seconds   seconds    calls  us/call  us/call  name\n",
1165          stdout);
1166
1167   for (n = 0; n < symidx; ++n)
1168     if (sortsym[n]->calls != 0 || sortsym[n]->ticks != 0)
1169       tsearch (sortsym[n], &data, countorder);
1170
1171   twalk (data, printflat);
1172
1173   tdestroy (data, freenoop);
1174 }
1175
1176
1177 static void
1178 generate_call_graph (struct profdata *profdata)
1179 {
1180   size_t cnt;
1181
1182   puts ("\nindex % time    self  children    called     name\n");
1183
1184   for (cnt = 0; cnt < symidx; ++cnt)
1185     if (sortsym[cnt]->froms != NULL || sortsym[cnt]->tos != NULL)
1186       {
1187         struct arc_list *runp;
1188         size_t n;
1189
1190         /* First print the from-information.  */
1191         runp = sortsym[cnt]->froms;
1192         while (runp != NULL)
1193           {
1194             printf ("            %8.2f%8.2f%9" PRIdMAX "/%-9" PRIdMAX "   %s",
1195                     (runp->idx != (size_t) -1l
1196                      ? sortsym[runp->idx]->ticks * tick_unit : 0.0),
1197                     0.0, /* FIXME: what's time for the children, recursive */
1198                     runp->count, sortsym[cnt]->calls,
1199                     (runp->idx != (size_t) -1l ?
1200                      sortsym[runp->idx]->name : "<UNKNOWN>"));
1201
1202             if (runp->idx != (size_t) -1l)
1203               printf (" [%Zd]", runp->idx);
1204             putchar_unlocked ('\n');
1205
1206             runp = runp->next;
1207           }
1208
1209         /* Info abount the function itself.  */
1210         n = printf ("[%Zu]", cnt);
1211         printf ("%*s%5.1f%8.2f%8.2f%9" PRIdMAX "         %s [%Zd]\n",
1212                 7 - n, " ",
1213                 total_ticks ? (100.0 * sortsym[cnt]->ticks) / total_ticks : 0,
1214                 sortsym[cnt]->ticks * tick_unit,
1215                 0.0, /* FIXME: what's time for the children, recursive */
1216                 sortsym[cnt]->calls,
1217                 sortsym[cnt]->name, cnt);
1218
1219         /* Info about the functions this function calls.  */
1220         runp = sortsym[cnt]->tos;
1221         while (runp != NULL)
1222           {
1223             printf ("            %8.2f%8.2f%9" PRIdMAX "/",
1224                     (runp->idx != (size_t) -1l
1225                      ? sortsym[runp->idx]->ticks * tick_unit : 0.0),
1226                     0.0, /* FIXME: what's time for the children, recursive */
1227                     runp->count);
1228
1229             if (runp->idx != (size_t) -1l)
1230               printf ("%-9" PRIdMAX "   %s [%Zd]\n",
1231                       sortsym[runp->idx]->calls,
1232                       sortsym[runp->idx]->name,
1233                       runp->idx);
1234             else
1235               fputs ("???         <UNKNOWN>\n\n", stdout);
1236
1237             runp = runp->next;
1238           }
1239
1240         fputs ("-----------------------------------------------\n", stdout);
1241       }
1242 }
1243
1244
1245 static void
1246 generate_call_pair_list (struct profdata *profdata)
1247 {
1248   size_t cnt;
1249
1250   for (cnt = 0; cnt < symidx; ++cnt)
1251     if (sortsym[cnt]->froms != NULL || sortsym[cnt]->tos != NULL)
1252       {
1253         struct arc_list *runp;
1254
1255         /* First print the incoming arcs.  */
1256         runp = sortsym[cnt]->froms;
1257         while (runp != NULL)
1258           {
1259             if (runp->idx == (size_t) -1l)
1260               printf ("\
1261 <UNKNOWN>                          %-34s %9" PRIdMAX "\n",
1262                       sortsym[cnt]->name, runp->count);
1263             runp = runp->next;
1264           }
1265
1266         /* Next the outgoing arcs.  */
1267         runp = sortsym[cnt]->tos;
1268         while (runp != NULL)
1269           {
1270             printf ("%-34s %-34s %9" PRIdMAX "\n",
1271                     sortsym[cnt]->name,
1272                     (runp->idx != (size_t) -1l
1273                      ? sortsym[runp->idx]->name : "<UNKNOWN>"),
1274                     runp->count);
1275             runp = runp->next;
1276           }
1277       }
1278 }