* elf/dl-load.c (_dl_init_paths): Don't use strdupa in function
[kopensolaris-gnu/glibc.git] / elf / dl-profile.c
1 /* Profiling of shared libraries.
2    Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3    This file is part of the GNU C Library.
4    Contributed by Ulrich Drepper <drepper@cygnus.com>, 1997.
5    Based on the BSD mcount implementation.
6
7    The GNU C Library is free software; you can redistribute it and/or
8    modify it under the terms of the GNU Library General Public License as
9    published by the Free Software Foundation; either version 2 of the
10    License, or (at your option) any later version.
11
12    The GNU C Library 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 GNU
15    Library General Public License for more details.
16
17    You should have received a copy of the GNU Library General Public
18    License along with the GNU C Library; see the file COPYING.LIB.  If not,
19    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20    Boston, MA 02111-1307, USA.  */
21
22 #include <errno.h>
23 #include <fcntl.h>
24 #include <inttypes.h>
25 #include <limits.h>
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <unistd.h>
30 #include <ldsodefs.h>
31 #include <sys/gmon.h>
32 #include <sys/gmon_out.h>
33 #include <sys/mman.h>
34 #include <sys/param.h>
35 #include <sys/stat.h>
36 #include <atomicity.h>
37
38 /* The LD_PROFILE feature has to be implemented different to the
39    normal profiling using the gmon/ functions.  The problem is that an
40    arbitrary amount of processes simulataneously can be run using
41    profiling and all write the results in the same file.  To provide
42    this mechanism one could implement a complicated mechanism to merge
43    the content of two profiling runs or one could extend the file
44    format to allow more than one data set.  For the second solution we
45    would have the problem that the file can grow in size beyond any
46    limit and both solutions have the problem that the concurrency of
47    writing the results is a big problem.
48
49    Another much simpler method is to use mmap to map the same file in
50    all using programs and modify the data in the mmap'ed area and so
51    also automatically on the disk.  Using the MAP_SHARED option of
52    mmap(2) this can be done without big problems in more than one
53    file.
54
55    This approach is very different from the normal profiling.  We have
56    to use the profiling data in exactly the way they are expected to
57    be written to disk.  But the normal format used by gprof is not usable
58    to do this.  It is optimized for size.  It writes the tags as single
59    bytes but this means that the following 32/64 bit values are
60    unaligned.
61
62    Therefore we use a new format.  This will look like this
63
64                                         0  1  2  3      <- byte is 32 bit word
65         0000                            g  m  o  n
66         0004                            *version*       <- GMON_SHOBJ_VERSION
67         0008                            00 00 00 00
68         000c                            00 00 00 00
69         0010                            00 00 00 00
70
71         0014                            *tag*           <- GMON_TAG_TIME_HIST
72         0018                            ?? ?? ?? ??
73                                         ?? ?? ?? ??     <- 32/64 bit LowPC
74         0018+A                          ?? ?? ?? ??
75                                         ?? ?? ?? ??     <- 32/64 bit HighPC
76         0018+2*A                        *histsize*
77         001c+2*A                        *profrate*
78         0020+2*A                        s  e  c  o
79         0024+2*A                        n  d  s  \0
80         0028+2*A                        \0 \0 \0 \0
81         002c+2*A                        \0 \0 \0
82         002f+2*A                        s
83
84         0030+2*A                        ?? ?? ?? ??     <- Count data
85         ...                             ...
86         0030+2*A+K                      ?? ?? ?? ??
87
88         0030+2*A+K                      *tag*           <- GMON_TAG_CG_ARC
89         0034+2*A+K                      *lastused*
90         0038+2*A+K                      ?? ?? ?? ??
91                                         ?? ?? ?? ??     <- FromPC#1
92         0038+3*A+K                      ?? ?? ?? ??
93                                         ?? ?? ?? ??     <- ToPC#1
94         0038+4*A+K                      ?? ?? ?? ??     <- Count#1
95         ...                             ...                ...
96         0038+(2*(CN-1)+2)*A+(CN-1)*4+K  ?? ?? ?? ??
97                                         ?? ?? ?? ??     <- FromPC#CGN
98         0038+(2*(CN-1)+3)*A+(CN-1)*4+K  ?? ?? ?? ??
99                                         ?? ?? ?? ??     <- ToPC#CGN
100         0038+(2*CN+2)*A+(CN-1)*4+K      ?? ?? ?? ??     <- Count#CGN
101
102    We put (for now?) no basic block information in the file since this would
103    introduce rase conditions among all the processes who want to write them.
104
105    `K' is the number of count entries which is computed as
106
107                 textsize / HISTFRACTION
108
109    `CG' in the above table is the number of call graph arcs.  Normally,
110    the table is sparse and the profiling code writes out only the those
111    entries which are really used in the program run.  But since we must
112    not extend this table (the profiling file) we'll keep them all here.
113    So CN can be executed in advance as
114
115                 MINARCS <= textsize*(ARCDENSITY/100) <= MAXARCS
116
117    Now the remaining question is: how to build the data structures we can
118    work with from this data.  We need the from set and must associate the
119    froms with all the associated tos.  We will do this by constructing this
120    data structures at the program start.  To do this we'll simply visit all
121    entries in the call graph table and add it to the appropriate list.  */
122
123 extern int __profile_frequency (void);
124
125 /* We define a special type to address the elements of the arc table.
126    This is basically the `gmon_cg_arc_record' format but it includes
127    the room for the tag and it uses real types.  */
128 struct here_cg_arc_record
129   {
130     uintptr_t from_pc;
131     uintptr_t self_pc;
132     uint32_t count;
133   } __attribute__ ((packed));
134
135 static struct here_cg_arc_record *data;
136
137 /* This is the number of entry which have been incorporated in the toset.  */
138 static uint32_t narcs;
139 /* This is a pointer to the object representing the number of entries
140    currently in the mmaped file.  At no point of time this has to be the
141    same as NARCS.  If it is equal all entries from the file are in our
142    lists.  */
143 static volatile uint32_t *narcsp;
144
145 /* Description of the currently profiled object.  */
146 static long int state = GMON_PROF_OFF;
147
148 static volatile uint16_t *kcount;
149 static size_t kcountsize;
150
151 struct here_fromstruct
152   {
153     struct here_cg_arc_record volatile *here;
154     uint16_t link;
155   };
156
157 static volatile uint16_t *tos;
158
159 static struct here_fromstruct *froms;
160 static uint32_t fromlimit;
161 static volatile uint32_t fromidx;
162
163 static uintptr_t lowpc;
164 static size_t textsize;
165 static unsigned int hashfraction;
166 static unsigned int log_hashfraction;
167
168
169 \f
170 /* Set up profiling data to profile object desribed by MAP.  The output
171    file is found (or created) in OUTPUT_DIR.  */
172 void
173 internal_function
174 _dl_start_profile (struct link_map *map, const char *output_dir)
175 {
176   char *filename;
177   int fd;
178   struct stat64 st;
179   const ElfW(Phdr) *ph;
180   ElfW(Addr) mapstart = ~((ElfW(Addr)) 0);
181   ElfW(Addr) mapend = 0;
182   struct gmon_hdr gmon_hdr;
183   struct gmon_hist_hdr hist_hdr;
184   char *hist, *cp;
185   size_t idx;
186   size_t tossize;
187   size_t fromssize;
188   uintptr_t highpc;
189   struct gmon_hdr *addr = NULL;
190   off_t expected_size;
191   /* See profil(2) where this is described.  */
192   int s_scale;
193 #define SCALE_1_TO_1    0x10000L
194
195   /* Compute the size of the sections which contain program code.  */
196   for (ph = map->l_phdr; ph < &map->l_phdr[map->l_phnum]; ++ph)
197     if (ph->p_type == PT_LOAD && (ph->p_flags & PF_X))
198       {
199         ElfW(Addr) start = (ph->p_vaddr & ~(_dl_pagesize - 1));
200         ElfW(Addr) end = ((ph->p_vaddr + ph->p_memsz + _dl_pagesize - 1)
201                           & ~(_dl_pagesize - 1));
202
203         if (start < mapstart)
204           mapstart = start;
205         if (end > mapend)
206           mapend = end;
207       }
208
209   /* Now we can compute the size of the profiling data.  This is done
210      with the same formulars as in `monstartup' (see gmon.c).  */
211   state = GMON_PROF_OFF;
212   lowpc = ROUNDDOWN (mapstart + map->l_addr,
213                      HISTFRACTION * sizeof (HISTCOUNTER));
214   highpc = ROUNDUP (mapend + map->l_addr,
215                     HISTFRACTION * sizeof (HISTCOUNTER));
216   textsize = highpc - lowpc;
217   kcountsize = textsize / HISTFRACTION;
218   hashfraction = HASHFRACTION;
219   if ((HASHFRACTION & (HASHFRACTION - 1)) == 0)
220     /* If HASHFRACTION is a power of two, mcount can use shifting
221        instead of integer division.  Precompute shift amount.  */
222     log_hashfraction = __ffs (hashfraction * sizeof (*froms)) - 1;
223   else
224     log_hashfraction = -1;
225   tossize = textsize / HASHFRACTION;
226   fromlimit = textsize * ARCDENSITY / 100;
227   if (fromlimit < MINARCS)
228     fromlimit = MINARCS;
229   if (fromlimit > MAXARCS)
230     fromlimit = MAXARCS;
231   fromssize = fromlimit * sizeof (struct here_fromstruct);
232
233   expected_size = (sizeof (struct gmon_hdr)
234                    + 4 + sizeof (struct gmon_hist_hdr) + kcountsize
235                    + 4 + 4 + fromssize * sizeof (struct here_cg_arc_record));
236
237   /* Create the gmon_hdr we expect or write.  */
238   memset (&gmon_hdr, '\0', sizeof (struct gmon_hdr));
239   memcpy (&gmon_hdr.cookie[0], GMON_MAGIC, sizeof (gmon_hdr.cookie));
240   *(int32_t *) gmon_hdr.version = GMON_SHOBJ_VERSION;
241
242   /* Create the hist_hdr we expect or write.  */
243   *(char **) hist_hdr.low_pc = (char *) mapstart;
244   *(char **) hist_hdr.high_pc = (char *) mapend;
245   *(int32_t *) hist_hdr.hist_size = kcountsize / sizeof (HISTCOUNTER);
246   *(int32_t *) hist_hdr.prof_rate = __profile_frequency ();
247   strncpy (hist_hdr.dimen, "seconds", sizeof (hist_hdr.dimen));
248   hist_hdr.dimen_abbrev = 's';
249
250   /* First determine the output name.  We write in the directory
251      OUTPUT_DIR and the name is composed from the shared objects
252      soname (or the file name) and the ending ".profile".  */
253   filename = (char *) alloca (strlen (output_dir) + 1 + strlen (_dl_profile)
254                               + sizeof ".profile");
255   cp = __stpcpy (filename, output_dir);
256   *cp++ = '/';
257   __stpcpy (__stpcpy (cp, _dl_profile), ".profile");
258
259 #ifdef O_NOFOLLOW
260 # define EXTRA_FLAGS | O_NOFOLLOW
261 #else
262 # define EXTRA_FLAGS
263 #endif
264   fd = __open (filename, O_RDWR | O_CREAT EXTRA_FLAGS, 0666);
265   if (fd == -1)
266     {
267       /* We cannot write the profiling data so don't do anything.  */
268       char buf[400];
269       _dl_sysdep_message (filename, ": cannot open file: ",
270                           __strerror_r (errno, buf, sizeof buf),
271                           "\n", NULL);
272       return;
273     }
274
275   if (__fxstat64 (_STAT_VER, fd, &st) < 0 || !S_ISREG (st.st_mode))
276     {
277       /* Not stat'able or not a regular file => don't use it.  */
278       char buf[400];
279       int errnum = errno;
280       __close (fd);
281       _dl_sysdep_message (filename, ": cannot stat file: ",
282                           __strerror_r (errnum, buf, sizeof buf),
283                           "\n", NULL);
284       return;
285     }
286
287   /* Test the size.  If it does not match what we expect from the size
288      values in the map MAP we don't use it and warn the user.  */
289   if (st.st_size == 0)
290     {
291       /* We have to create the file.  */
292       char buf[_dl_pagesize];
293
294       memset (buf, '\0', _dl_pagesize);
295
296       if (__lseek (fd, expected_size & ~(_dl_pagesize - 1), SEEK_SET) == -1)
297         {
298           char buf[400];
299           int errnum;
300         cannot_create:
301           errnum = errno;
302           __close (fd);
303           _dl_sysdep_message (filename, ": cannot create file: ",
304                               __strerror_r (errnum, buf, sizeof buf),
305                               "\n", NULL);
306           return;
307         }
308
309       if (TEMP_FAILURE_RETRY (__libc_write (fd, buf, (expected_size
310                                                       & (_dl_pagesize - 1))))
311           < 0)
312         goto cannot_create;
313     }
314   else if (st.st_size != expected_size)
315     {
316       __close (fd);
317     wrong_format:
318
319       if (addr != NULL)
320         __munmap ((void *) addr, expected_size);
321
322       _dl_sysdep_message (filename,
323                           ": file is no correct profile data file for `",
324                           _dl_profile, "'\n", NULL);
325       return;
326     }
327
328   addr = (struct gmon_hdr *) __mmap (NULL, expected_size, PROT_READ|PROT_WRITE,
329                                      MAP_SHARED|MAP_FILE, fd, 0);
330   if (addr == (struct gmon_hdr *) MAP_FAILED)
331     {
332       char buf[400];
333       int errnum = errno;
334       __close (fd);
335       _dl_sysdep_message (filename, ": cannot map file: ",
336                           __strerror_r (errnum, buf, sizeof buf),
337                           "\n", NULL);
338       return;
339     }
340
341   /* We don't need the file desriptor anymore.  */
342   __close (fd);
343
344   /* Pointer to data after the header.  */
345   hist = (char *) (addr + 1);
346   kcount = (uint16_t *) ((char *) hist + sizeof (uint32_t)
347                          + sizeof (struct gmon_hist_hdr));
348
349   /* Compute pointer to array of the arc information.  */
350   narcsp = (uint32_t *) ((char *) kcount + kcountsize + sizeof (uint32_t));
351   data = (struct here_cg_arc_record *) ((char *) narcsp + sizeof (uint32_t));
352
353   if (st.st_size == 0)
354     {
355       /* Create the signature.  */
356       memcpy (addr, &gmon_hdr, sizeof (struct gmon_hdr));
357
358       *(uint32_t *) hist = GMON_TAG_TIME_HIST;
359       memcpy (hist + sizeof (uint32_t), &hist_hdr,
360               sizeof (struct gmon_hist_hdr));
361
362       narcsp[-1] = GMON_TAG_CG_ARC;
363     }
364   else
365     {
366       /* Test the signature in the file.  */
367       if (memcmp (addr, &gmon_hdr, sizeof (struct gmon_hdr)) != 0
368           || *(uint32_t *) hist != GMON_TAG_TIME_HIST
369           || memcmp (hist + sizeof (uint32_t), &hist_hdr,
370                      sizeof (struct gmon_hist_hdr)) != 0
371           || narcsp[-1] != GMON_TAG_CG_ARC)
372         goto wrong_format;
373     }
374
375   /* Allocate memory for the froms data and the pointer to the tos records.  */
376   tos = (uint16_t *) calloc (tossize + fromssize, 1);
377   if (tos == NULL)
378     {
379       __munmap ((void *) addr, expected_size);
380       _dl_sysdep_fatal ("Out of memory while initializing profiler\n", NULL);
381       /* NOTREACHED */
382     }
383
384   froms = (struct here_fromstruct *) ((char *) tos + tossize);
385   fromidx = 0;
386
387   /* Now we have to process all the arc count entries.  BTW: it is
388      not critical whether the *NARCSP value changes meanwhile.  Before
389      we enter a new entry in to toset we will check that everything is
390      available in TOS.  This happens in _dl_mcount.
391
392      Loading the entries in reverse order should help to get the most
393      frequently used entries at the front of the list.  */
394   for (idx = narcs = MIN (*narcsp, fromlimit); idx > 0; )
395     {
396       size_t to_index;
397       size_t newfromidx;
398       --idx;
399       to_index = (data[idx].self_pc / (hashfraction * sizeof (*tos)));
400       newfromidx = fromidx++;
401       froms[newfromidx].here = &data[idx];
402       froms[newfromidx].link = tos[to_index];
403       tos[to_index] = newfromidx;
404     }
405
406   /* Setup counting data.  */
407   if (kcountsize < highpc - lowpc)
408     {
409 #if 0
410       s_scale = ((double) kcountsize / (highpc - lowpc)) * SCALE_1_TO_1;
411 #else
412       size_t range = highpc - lowpc;
413       size_t quot = range / kcountsize;
414
415       if (quot >= SCALE_1_TO_1)
416         s_scale = 1;
417       else if (quot >= SCALE_1_TO_1 / 256)
418         s_scale = SCALE_1_TO_1 / quot;
419       else if (range > ULONG_MAX / 256)
420         s_scale = (SCALE_1_TO_1 * 256) / (range / (kcountsize / 256));
421       else
422         s_scale = (SCALE_1_TO_1 * 256) / ((range * 256) / kcountsize);
423 #endif
424     }
425   else
426     s_scale = SCALE_1_TO_1;
427
428   /* Start the profiler.  */
429   __profil ((void *) kcount, kcountsize, lowpc, s_scale);
430
431   /* Turn on profiling.  */
432   state = GMON_PROF_ON;
433 }
434
435
436 void
437 _dl_mcount (ElfW(Addr) frompc, ElfW(Addr) selfpc)
438 {
439   volatile uint16_t *topcindex;
440   size_t i, fromindex;
441   struct here_fromstruct *fromp;
442
443 #if 0
444   /* XXX I think this is now not necessary anymore.  */
445   if (! compare_and_swap (&state, GMON_PROF_ON, GMON_PROF_BUSY))
446     return;
447 #endif
448
449   /* Compute relative addresses.  The shared object can be loaded at
450      any address.  The value of frompc could be anything.  We cannot
451      restrict it in any way, just set to a fixed value (0) in case it
452      is outside the allowed range.  These calls show up as calls from
453      <external> in the gprof output.  */
454   frompc -= lowpc;
455   if (frompc >= textsize)
456     frompc = 0;
457   selfpc -= lowpc;
458   if (selfpc >= textsize)
459     goto done;
460
461   /* Getting here we now have to find out whether the location was
462      already used.  If yes we are lucky and only have to increment a
463      counter (this also has to be atomic).  If the entry is new things
464      are getting complicated...  */
465
466   /* Avoid integer divide if possible.  */
467   if ((HASHFRACTION & (HASHFRACTION - 1)) == 0)
468     i = selfpc >> log_hashfraction;
469   else
470     i = selfpc / (hashfraction * sizeof (*tos));
471
472   topcindex = &tos[i];
473   fromindex = *topcindex;
474
475   if (fromindex == 0)
476     goto check_new_or_add;
477
478   fromp = &froms[fromindex];
479
480   /* We have to look through the chain of arcs whether there is already
481      an entry for our arc.  */
482   while (fromp->here->from_pc != frompc)
483     {
484       if (fromp->link != 0)
485         do
486           fromp = &froms[fromp->link];
487         while (fromp->link != 0 && fromp->here->from_pc != frompc);
488
489       if (fromp->here->from_pc != frompc)
490         {
491           topcindex = &fromp->link;
492
493         check_new_or_add:
494           /* Our entry is not among the entries we read so far from the
495              data file.  Now see whether we have to update the list.  */
496           while (narcs != *narcsp && narcs < fromlimit)
497             {
498               size_t to_index;
499               size_t newfromidx;
500               to_index = (data[narcs].self_pc
501                           / (hashfraction * sizeof (*tos)));
502               newfromidx = exchange_and_add (&fromidx, 1) + 1;
503               froms[newfromidx].here = &data[narcs];
504               froms[newfromidx].link = tos[to_index];
505               tos[to_index] = newfromidx;
506               atomic_add (&narcs, 1);
507             }
508
509           /* If we still have no entry stop searching and insert.  */
510           if (*topcindex == 0)
511             {
512               uint_fast32_t newarc = 1 + exchange_and_add (narcsp, 1);
513
514               /* In rare cases it could happen that all entries in FROMS are
515                  occupied.  So we cannot count this anymore.  */
516               if (newarc >= fromlimit)
517                 goto done;
518
519               *topcindex = exchange_and_add (&fromidx, 1) + 1;
520               fromp = &froms[*topcindex];
521
522               fromp->here = &data[newarc];
523               data[newarc].from_pc = frompc;
524               data[newarc].self_pc = selfpc;
525               data[newarc].count = 0;
526               fromp->link = 0;
527               atomic_add (&narcs, 1);
528
529               break;
530             }
531
532           fromp = &froms[*topcindex];
533         }
534       else
535         /* Found in.  */
536         break;
537     }
538
539   /* Increment the counter.  */
540   atomic_add (&fromp->here->count, 1);
541
542  done:
543 #if 0
544   /* XXX See above,  Shouldn't be necessary anymore.  */
545   state = GMON_PROF_ON;
546 #else
547   ;
548 #endif
549 }