elf/dl-profile.c

   1 /* Profiling of shared libraries.
   2    Copyright (C) 1997, 1998, 1999, 2000 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 stat 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   fd = __open (filename, O_RDWR | O_CREAT, 0666);
 260   if (fd == -1)
 261     {
 262       /* We cannot write the profiling data so don't do anything.  */
 263       char buf[400];
 264       _dl_sysdep_message (filename, ": cannot open file: ",
 265                           __strerror_r (errno, buf, sizeof buf),
 266                           "\n", NULL);
 267       return;
 268     }
 269
 270   if (fstat (fd, &st) < 0 || !S_ISREG (st.st_mode))
 271     {
 272       /* Not stat'able or not a regular file => don't use it.  */
 273       char buf[400];
 274       int errnum = errno;
 275       __close (fd);
 276       _dl_sysdep_message (filename, ": cannot stat file: ",
 277                           __strerror_r (errnum, buf, sizeof buf),
 278                           "\n", NULL);
 279       return;
 280     }
 281
 282   /* Test the size.  If it does not match what we expect from the size
 283      values in the map MAP we don't use it and warn the user.  */
 284   if (st.st_size == 0)
 285     {
 286       /* We have to create the file.  */
 287       char buf[_dl_pagesize];
 288
 289       memset (buf, '\0', _dl_pagesize);
 290
 291       if (__lseek (fd, expected_size & ~(_dl_pagesize - 1), SEEK_SET) == -1)
 292         {
 293           char buf[400];
 294           int errnum;
 295         cannot_create:
 296           errnum = errno;
 297           __close (fd);
 298           _dl_sysdep_message (filename, ": cannot create file: ",
 299                               __strerror_r (errnum, buf, sizeof buf),
 300                               "\n", NULL);
 301           return;
 302         }
 303
 304       if (TEMP_FAILURE_RETRY (__libc_write (fd, buf, (expected_size
 305                                                       & (_dl_pagesize - 1))))
 306           < 0)
 307         goto cannot_create;
 308     }
 309   else if (st.st_size != expected_size)
 310     {
 311       __close (fd);
 312     wrong_format:
 313
 314       if (addr != NULL)
 315         __munmap ((void *) addr, expected_size);
 316
 317       _dl_sysdep_message (filename,
 318                           ": file is no correct profile data file for `",
 319                           _dl_profile, "'\n", NULL);
 320       return;
 321     }
 322
 323   addr = (struct gmon_hdr *) __mmap (NULL, expected_size, PROT_READ|PROT_WRITE,
 324                                      MAP_SHARED|MAP_FILE, fd, 0);
 325   if (addr == (struct gmon_hdr *) MAP_FAILED)
 326     {
 327       char buf[400];
 328       int errnum = errno;
 329       __close (fd);
 330       _dl_sysdep_message (filename, ": cannot map file: ",
 331                           __strerror_r (errnum, buf, sizeof buf),
 332                           "\n", NULL);
 333       return;
 334     }
 335
 336   /* We don't need the file desriptor anymore.  */
 337   __close (fd);
 338
 339   /* Pointer to data after the header.  */
 340   hist = (char *) (addr + 1);
 341   kcount = (uint16_t *) ((char *) hist + sizeof (uint32_t)
 342                          + sizeof (struct gmon_hist_hdr));
 343
 344   /* Compute pointer to array of the arc information.  */
 345   narcsp = (uint32_t *) ((char *) kcount + kcountsize + sizeof (uint32_t));
 346   data = (struct here_cg_arc_record *) ((char *) narcsp + sizeof (uint32_t));
 347
 348   if (st.st_size == 0)
 349     {
 350       /* Create the signature.  */
 351       memcpy (addr, &gmon_hdr, sizeof (struct gmon_hdr));
 352
 353       *(uint32_t *) hist = GMON_TAG_TIME_HIST;
 354       memcpy (hist + sizeof (uint32_t), &hist_hdr,
 355               sizeof (struct gmon_hist_hdr));
 356
 357       narcsp[-1] = GMON_TAG_CG_ARC;
 358     }
 359   else
 360     {
 361       /* Test the signature in the file.  */
 362       if (memcmp (addr, &gmon_hdr, sizeof (struct gmon_hdr)) != 0
 363           || *(uint32_t *) hist != GMON_TAG_TIME_HIST
 364           || memcmp (hist + sizeof (uint32_t), &hist_hdr,
 365                      sizeof (struct gmon_hist_hdr)) != 0
 366           || narcsp[-1] != GMON_TAG_CG_ARC)
 367         goto wrong_format;
 368     }
 369
 370   /* Allocate memory for the froms data and the pointer to the tos records.  */
 371   tos = (uint16_t *) calloc (tossize + fromssize, 1);
 372   if (tos == NULL)
 373     {
 374       __munmap ((void *) addr, expected_size);
 375       _dl_sysdep_fatal ("Out of memory while initializing profiler\n", NULL);
 376       /* NOTREACHED */
 377     }
 378
 379   froms = (struct here_fromstruct *) ((char *) tos + tossize);
 380   fromidx = 0;
 381
 382   /* Now we have to process all the arc count entries.  BTW: it is
 383      not critical whether the *NARCSP value changes meanwhile.  Before
 384      we enter a new entry in to toset we will check that everything is
 385      available in TOS.  This happens in _dl_mcount.
 386
 387      Loading the entries in reverse order should help to get the most
 388      frequently used entries at the front of the list.  */
 389   for (idx = narcs = MIN (*narcsp, fromlimit); idx > 0; )
 390     {
 391       size_t to_index;
 392       size_t newfromidx;
 393       --idx;
 394       to_index = (data[idx].self_pc / (hashfraction * sizeof (*tos)));
 395       newfromidx = fromidx++;
 396       froms[newfromidx].here = &data[idx];
 397       froms[newfromidx].link = tos[to_index];
 398       tos[to_index] = newfromidx;
 399     }
 400
 401   /* Setup counting data.  */
 402   if (kcountsize < highpc - lowpc)
 403     {
 404 #if 0
 405       s_scale = ((double) kcountsize / (highpc - lowpc)) * SCALE_1_TO_1;
 406 #else
 407       size_t range = highpc - lowpc;
 408       size_t quot = range / kcountsize;
 409
 410       if (quot >= SCALE_1_TO_1)
 411         s_scale = 1;
 412       else if (quot >= SCALE_1_TO_1 / 256)
 413         s_scale = SCALE_1_TO_1 / quot;
 414       else if (range > ULONG_MAX / 256)
 415         s_scale = (SCALE_1_TO_1 * 256) / (range / (kcountsize / 256));
 416       else
 417         s_scale = (SCALE_1_TO_1 * 256) / ((range * 256) / kcountsize);
 418 #endif
 419     }
 420   else
 421     s_scale = SCALE_1_TO_1;
 422
 423   /* Start the profiler.  */
 424   __profil ((void *) kcount, kcountsize, lowpc, s_scale);
 425
 426   /* Turn on profiling.  */
 427   state = GMON_PROF_ON;
 428 }
 429
 430
 431 void
 432 _dl_mcount (ElfW(Addr) frompc, ElfW(Addr) selfpc)
 433 {
 434   volatile uint16_t *topcindex;
 435   size_t i, fromindex;
 436   struct here_fromstruct *fromp;
 437
 438 #if 0
 439   /* XXX I think this is now not necessary anymore.  */
 440   if (! compare_and_swap (&state, GMON_PROF_ON, GMON_PROF_BUSY))
 441     return;
 442 #endif
 443
 444   /* Compute relative addresses.  The shared object can be loaded at
 445      any address.  The value of frompc could be anything.  We cannot
 446      restrict it in any way, just set to a fixed value (0) in case it
 447      is outside the allowed range.  These calls show up as calls from
 448      <external> in the gprof output.  */
 449   frompc -= lowpc;
 450   if (frompc >= textsize)
 451     frompc = 0;
 452   selfpc -= lowpc;
 453   if (selfpc >= textsize)
 454     goto done;
 455
 456   /* Getting here we now have to find out whether the location was
 457      already used.  If yes we are lucky and only have to increment a
 458      counter (this also has to be atomic).  If the entry is new things
 459      are getting complicated...  */
 460
 461   /* Avoid integer divide if possible.  */
 462   if ((HASHFRACTION & (HASHFRACTION - 1)) == 0)
 463     i = selfpc >> log_hashfraction;
 464   else
 465     i = selfpc / (hashfraction * sizeof (*tos));
 466
 467   topcindex = &tos[i];
 468   fromindex = *topcindex;
 469
 470   if (fromindex == 0)
 471     goto check_new_or_add;
 472
 473   fromp = &froms[fromindex];
 474
 475   /* We have to look through the chain of arcs whether there is already
 476      an entry for our arc.  */
 477   while (fromp->here->from_pc != frompc)
 478     {
 479       if (fromp->link != 0)
 480         do
 481           fromp = &froms[fromp->link];
 482         while (fromp->link != 0 && fromp->here->from_pc != frompc);
 483
 484       if (fromp->here->from_pc != frompc)
 485         {
 486           topcindex = &fromp->link;
 487
 488         check_new_or_add:
 489           /* Our entry is not among the entries we read so far from the
 490              data file.  Now see whether we have to update the list.  */
 491           while (narcs != *narcsp && narcs < fromlimit)
 492             {
 493               size_t to_index;
 494               size_t newfromidx;
 495               to_index = (data[narcs].self_pc
 496                           / (hashfraction * sizeof (*tos)));
 497               newfromidx = exchange_and_add (&fromidx, 1) + 1;
 498               froms[newfromidx].here = &data[narcs];
 499               froms[newfromidx].link = tos[to_index];
 500               tos[to_index] = newfromidx;
 501               atomic_add (&narcs, 1);
 502             }
 503
 504           /* If we still have no entry stop searching and insert.  */
 505           if (*topcindex == 0)
 506             {
 507               uint_fast32_t newarc = 1 + exchange_and_add (narcsp, 1);
 508
 509               /* In rare cases it could happen that all entries in FROMS are
 510                  occupied.  So we cannot count this anymore.  */
 511               if (newarc >= fromlimit)
 512                 goto done;
 513
 514               *topcindex = exchange_and_add (&fromidx, 1) + 1;
 515               fromp = &froms[*topcindex];
 516
 517               fromp->here = &data[newarc];
 518               data[newarc].from_pc = frompc;
 519               data[newarc].self_pc = selfpc;
 520               data[newarc].count = 0;
 521               fromp->link = 0;
 522               atomic_add (&narcs, 1);
 523
 524               break;
 525             }
 526
 527           fromp = &froms[*topcindex];
 528         }
 529       else
 530         /* Found in.  */
 531         break;
 532     }
 533
 534   /* Increment the counter.  */
 535   atomic_add (&fromp->here->count, 1);
 536
 537  done:
 538 #if 0
 539   /* XXX See above,  Shouldn't be necessary anymore.  */
 540   state = GMON_PROF_ON;
 541 #endif
 542 }