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