elf/dl-profile.c

   1 /* Profiling of shared libraries.
   2    Copyright (C) 1997,1998,1999,2000,2001,2002 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 <atomicity.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
 126 /* We define a special type to address the elements of the arc table.
 127    This is basically the `gmon_cg_arc_record' format but it includes
 128    the room for the tag and it uses real types.  */
 129 struct here_cg_arc_record
 130   {
 131     uintptr_t from_pc;
 132     uintptr_t self_pc;
 133     uint32_t count;
 134   } __attribute__ ((packed));
 135
 136 static struct here_cg_arc_record *data;
 137
 138 /* Nonzero if profiling is under way.  */
 139 static int running;
 140
 141 /* This is the number of entry which have been incorporated in the toset.  */
 142 static uint32_t narcs;
 143 /* This is a pointer to the object representing the number of entries
 144    currently in the mmaped file.  At no point of time this has to be the
 145    same as NARCS.  If it is equal all entries from the file are in our
 146    lists.  */
 147 static volatile uint32_t *narcsp;
 148
 149 static volatile uint16_t *kcount;
 150 static size_t kcountsize;
 151
 152 struct here_fromstruct
 153   {
 154     struct here_cg_arc_record volatile *here;
 155     uint16_t link;
 156   };
 157
 158 static volatile uint16_t *tos;
 159
 160 static struct here_fromstruct *froms;
 161 static uint32_t fromlimit;
 162 static volatile uint32_t fromidx;
 163
 164 static uintptr_t lowpc;
 165 static size_t textsize;
 166 static unsigned int hashfraction;
 167 static unsigned int log_hashfraction;
 168
 169
 170 \f
 171 /* Set up profiling data to profile object desribed by MAP.  The output
 172    file is found (or created) in OUTPUT_DIR.  */
 173 void
 174 internal_function
 175 _dl_start_profile (struct link_map *map, const char *output_dir)
 176 {
 177   char *filename;
 178   int fd;
 179   struct stat64 st;
 180   const ElfW(Phdr) *ph;
 181   ElfW(Addr) mapstart = ~((ElfW(Addr)) 0);
 182   ElfW(Addr) mapend = 0;
 183   struct gmon_hdr gmon_hdr;
 184   struct gmon_hist_hdr hist_hdr;
 185   char *hist, *cp;
 186   size_t idx;
 187   size_t tossize;
 188   size_t fromssize;
 189   uintptr_t highpc;
 190   struct gmon_hdr *addr = NULL;
 191   off_t expected_size;
 192   /* See profil(2) where this is described.  */
 193   int s_scale;
 194 #define SCALE_1_TO_1    0x10000L
 195
 196   /* Compute the size of the sections which contain program code.  */
 197   for (ph = map->l_phdr; ph < &map->l_phdr[map->l_phnum]; ++ph)
 198     if (ph->p_type == PT_LOAD && (ph->p_flags & PF_X))
 199       {
 200         ElfW(Addr) start = (ph->p_vaddr & ~(GL(dl_pagesize) - 1));
 201         ElfW(Addr) end = ((ph->p_vaddr + ph->p_memsz + GL(dl_pagesize) - 1)
 202                           & ~(GL(dl_pagesize) - 1));
 203
 204         if (start < mapstart)
 205           mapstart = start;
 206         if (end > mapend)
 207           mapend = end;
 208       }
 209
 210   /* Now we can compute the size of the profiling data.  This is done
 211      with the same formulars as in `monstartup' (see gmon.c).  */
 212   running = 0;
 213   lowpc = ROUNDDOWN (mapstart + map->l_addr,
 214                      HISTFRACTION * sizeof (HISTCOUNTER));
 215   highpc = ROUNDUP (mapend + map->l_addr,
 216                     HISTFRACTION * sizeof (HISTCOUNTER));
 217   textsize = highpc - lowpc;
 218   kcountsize = textsize / HISTFRACTION;
 219   hashfraction = HASHFRACTION;
 220   if ((HASHFRACTION & (HASHFRACTION - 1)) == 0)
 221     {
 222       /* If HASHFRACTION is a power of two, mcount can use shifting
 223          instead of integer division.  Precompute shift amount.
 224
 225          This is a constant but the compiler cannot compile the
 226          expression away since the __ffs implementation is not known
 227          to the compiler.  Help the compiler by precomputing the
 228          usual cases.  */
 229       assert (hashfraction == 2);
 230
 231       if (sizeof (*froms) == 8)
 232         log_hashfraction = 4;
 233       else if (sizeof (*froms) == 16)
 234         log_hashfraction = 5;
 235       else
 236         log_hashfraction = __ffs (hashfraction * sizeof (*froms)) - 1;
 237     }
 238   else
 239     log_hashfraction = -1;
 240   tossize = textsize / HASHFRACTION;
 241   fromlimit = textsize * ARCDENSITY / 100;
 242   if (fromlimit < MINARCS)
 243     fromlimit = MINARCS;
 244   if (fromlimit > MAXARCS)
 245     fromlimit = MAXARCS;
 246   fromssize = fromlimit * sizeof (struct here_fromstruct);
 247
 248   expected_size = (sizeof (struct gmon_hdr)
 249                    + 4 + sizeof (struct gmon_hist_hdr) + kcountsize
 250                    + 4 + 4 + fromssize * sizeof (struct here_cg_arc_record));
 251
 252   /* Create the gmon_hdr we expect or write.  */
 253   memset (&gmon_hdr, '\0', sizeof (struct gmon_hdr));
 254   memcpy (&gmon_hdr.cookie[0], GMON_MAGIC, sizeof (gmon_hdr.cookie));
 255   *(int32_t *) gmon_hdr.version = GMON_SHOBJ_VERSION;
 256
 257   /* Create the hist_hdr we expect or write.  */
 258   *(char **) hist_hdr.low_pc = (char *) mapstart;
 259   *(char **) hist_hdr.high_pc = (char *) mapend;
 260   *(int32_t *) hist_hdr.hist_size = kcountsize / sizeof (HISTCOUNTER);
 261   *(int32_t *) hist_hdr.prof_rate = __profile_frequency ();
 262   if (sizeof (hist_hdr.dimen) >= sizeof ("seconds"))
 263     {
 264       memcpy (hist_hdr.dimen, "seconds", sizeof ("seconds"));
 265       memset (hist_hdr.dimen + sizeof ("seconds"), '\0',
 266               sizeof (hist_hdr.dimen) - sizeof ("seconds"));
 267     }
 268   else
 269     strncpy (hist_hdr.dimen, "seconds", sizeof (hist_hdr.dimen));
 270   hist_hdr.dimen_abbrev = 's';
 271
 272   /* First determine the output name.  We write in the directory
 273      OUTPUT_DIR and the name is composed from the shared objects
 274      soname (or the file name) and the ending ".profile".  */
 275   filename = (char *) alloca (strlen (output_dir) + 1 + strlen (GL(dl_profile))
 276                               + sizeof ".profile");
 277   cp = __stpcpy (filename, output_dir);
 278   *cp++ = '/';
 279   __stpcpy (__stpcpy (cp, GL(dl_profile)), ".profile");
 280
 281 #ifdef O_NOFOLLOW
 282 # define EXTRA_FLAGS | O_NOFOLLOW
 283 #else
 284 # define EXTRA_FLAGS
 285 #endif
 286   fd = __open (filename, O_RDWR | O_CREAT EXTRA_FLAGS, DEFFILEMODE);
 287   if (fd == -1)
 288     {
 289       /* We cannot write the profiling data so don't do anything.  */
 290       char buf[400];
 291       _dl_error_printf ("%s: cannot open file: %s\n", filename,
 292                         __strerror_r (errno, buf, sizeof buf));
 293       return;
 294     }
 295
 296   if (__fxstat64 (_STAT_VER, fd, &st) < 0 || !S_ISREG (st.st_mode))
 297     {
 298       /* Not stat'able or not a regular file => don't use it.  */
 299       char buf[400];
 300       int errnum = errno;
 301       __close (fd);
 302       _dl_error_printf ("%s: cannot stat file: %s\n", filename,
 303                         __strerror_r (errnum, buf, sizeof buf));
 304       return;
 305     }
 306
 307   /* Test the size.  If it does not match what we expect from the size
 308      values in the map MAP we don't use it and warn the user.  */
 309   if (st.st_size == 0)
 310     {
 311       /* We have to create the file.  */
 312       char buf[GL(dl_pagesize)];
 313
 314       memset (buf, '\0', GL(dl_pagesize));
 315
 316       if (__lseek (fd, expected_size & ~(GL(dl_pagesize) - 1), SEEK_SET) == -1)
 317         {
 318           char buf[400];
 319           int errnum;
 320         cannot_create:
 321           errnum = errno;
 322           __close (fd);
 323           _dl_error_printf ("%s: cannot create file: %s\n", filename,
 324                             __strerror_r (errnum, buf, sizeof buf));
 325           return;
 326         }
 327
 328       if (TEMP_FAILURE_RETRY (__libc_write (fd, buf, (expected_size
 329                                                       & (GL(dl_pagesize)
 330                                                          - 1))))
 331           < 0)
 332         goto cannot_create;
 333     }
 334   else if (st.st_size != expected_size)
 335     {
 336       __close (fd);
 337     wrong_format:
 338
 339       if (addr != NULL)
 340         __munmap ((void *) addr, expected_size);
 341
 342       _dl_error_printf ("%s: file is no correct profile data file for `%s'\n",
 343                         filename, GL(dl_profile));
 344       return;
 345     }
 346
 347   addr = (struct gmon_hdr *) __mmap (NULL, expected_size, PROT_READ|PROT_WRITE,
 348                                      MAP_SHARED|MAP_FILE, fd, 0);
 349   if (addr == (struct gmon_hdr *) MAP_FAILED)
 350     {
 351       char buf[400];
 352       int errnum = errno;
 353       __close (fd);
 354       _dl_error_printf ("%s: cannot map file: %s\n", filename,
 355                         __strerror_r (errnum, buf, sizeof buf));
 356       return;
 357     }
 358
 359   /* We don't need the file desriptor anymore.  */
 360   __close (fd);
 361
 362   /* Pointer to data after the header.  */
 363   hist = (char *) (addr + 1);
 364   kcount = (uint16_t *) ((char *) hist + sizeof (uint32_t)
 365                          + sizeof (struct gmon_hist_hdr));
 366
 367   /* Compute pointer to array of the arc information.  */
 368   narcsp = (uint32_t *) ((char *) kcount + kcountsize + sizeof (uint32_t));
 369   data = (struct here_cg_arc_record *) ((char *) narcsp + sizeof (uint32_t));
 370
 371   if (st.st_size == 0)
 372     {
 373       /* Create the signature.  */
 374       memcpy (addr, &gmon_hdr, sizeof (struct gmon_hdr));
 375
 376       *(uint32_t *) hist = GMON_TAG_TIME_HIST;
 377       memcpy (hist + sizeof (uint32_t), &hist_hdr,
 378               sizeof (struct gmon_hist_hdr));
 379
 380       narcsp[-1] = GMON_TAG_CG_ARC;
 381     }
 382   else
 383     {
 384       /* Test the signature in the file.  */
 385       if (memcmp (addr, &gmon_hdr, sizeof (struct gmon_hdr)) != 0
 386           || *(uint32_t *) hist != GMON_TAG_TIME_HIST
 387           || memcmp (hist + sizeof (uint32_t), &hist_hdr,
 388                      sizeof (struct gmon_hist_hdr)) != 0
 389           || narcsp[-1] != GMON_TAG_CG_ARC)
 390         goto wrong_format;
 391     }
 392
 393   /* Allocate memory for the froms data and the pointer to the tos records.  */
 394   tos = (uint16_t *) calloc (tossize + fromssize, 1);
 395   if (tos == NULL)
 396     {
 397       __munmap ((void *) addr, expected_size);
 398       _dl_fatal_printf ("Out of memory while initializing profiler\n");
 399       /* NOTREACHED */
 400     }
 401
 402   froms = (struct here_fromstruct *) ((char *) tos + tossize);
 403   fromidx = 0;
 404
 405   /* Now we have to process all the arc count entries.  BTW: it is
 406      not critical whether the *NARCSP value changes meanwhile.  Before
 407      we enter a new entry in to toset we will check that everything is
 408      available in TOS.  This happens in _dl_mcount.
 409
 410      Loading the entries in reverse order should help to get the most
 411      frequently used entries at the front of the list.  */
 412   for (idx = narcs = MIN (*narcsp, fromlimit); idx > 0; )
 413     {
 414       size_t to_index;
 415       size_t newfromidx;
 416       --idx;
 417       to_index = (data[idx].self_pc / (hashfraction * sizeof (*tos)));
 418       newfromidx = fromidx++;
 419       froms[newfromidx].here = &data[idx];
 420       froms[newfromidx].link = tos[to_index];
 421       tos[to_index] = newfromidx;
 422     }
 423
 424   /* Setup counting data.  */
 425   if (kcountsize < highpc - lowpc)
 426     {
 427 #if 0
 428       s_scale = ((double) kcountsize / (highpc - lowpc)) * SCALE_1_TO_1;
 429 #else
 430       size_t range = highpc - lowpc;
 431       size_t quot = range / kcountsize;
 432
 433       if (quot >= SCALE_1_TO_1)
 434         s_scale = 1;
 435       else if (quot >= SCALE_1_TO_1 / 256)
 436         s_scale = SCALE_1_TO_1 / quot;
 437       else if (range > ULONG_MAX / 256)
 438         s_scale = (SCALE_1_TO_1 * 256) / (range / (kcountsize / 256));
 439       else
 440         s_scale = (SCALE_1_TO_1 * 256) / ((range * 256) / kcountsize);
 441 #endif
 442     }
 443   else
 444     s_scale = SCALE_1_TO_1;
 445
 446   /* Start the profiler.  */
 447   __profil ((void *) kcount, kcountsize, lowpc, s_scale);
 448
 449   /* Turn on profiling.  */
 450   running = 1;
 451 }
 452 INTDEF (_dl_start_profile)
 453
 454
 455 void
 456 _dl_mcount (ElfW(Addr) frompc, ElfW(Addr) selfpc)
 457 {
 458   volatile uint16_t *topcindex;
 459   size_t i, fromindex;
 460   struct here_fromstruct *fromp;
 461
 462   if (! running)
 463     return;
 464
 465   /* Compute relative addresses.  The shared object can be loaded at
 466      any address.  The value of frompc could be anything.  We cannot
 467      restrict it in any way, just set to a fixed value (0) in case it
 468      is outside the allowed range.  These calls show up as calls from
 469      <external> in the gprof output.  */
 470   frompc -= lowpc;
 471   if (frompc >= textsize)
 472     frompc = 0;
 473   selfpc -= lowpc;
 474   if (selfpc >= textsize)
 475     goto done;
 476
 477   /* Getting here we now have to find out whether the location was
 478      already used.  If yes we are lucky and only have to increment a
 479      counter (this also has to be atomic).  If the entry is new things
 480      are getting complicated...  */
 481
 482   /* Avoid integer divide if possible.  */
 483   if ((HASHFRACTION & (HASHFRACTION - 1)) == 0)
 484     i = selfpc >> log_hashfraction;
 485   else
 486     i = selfpc / (hashfraction * sizeof (*tos));
 487
 488   topcindex = &tos[i];
 489   fromindex = *topcindex;
 490
 491   if (fromindex == 0)
 492     goto check_new_or_add;
 493
 494   fromp = &froms[fromindex];
 495
 496   /* We have to look through the chain of arcs whether there is already
 497      an entry for our arc.  */
 498   while (fromp->here->from_pc != frompc)
 499     {
 500       if (fromp->link != 0)
 501         do
 502           fromp = &froms[fromp->link];
 503         while (fromp->link != 0 && fromp->here->from_pc != frompc);
 504
 505       if (fromp->here->from_pc != frompc)
 506         {
 507           topcindex = &fromp->link;
 508
 509         check_new_or_add:
 510           /* Our entry is not among the entries we read so far from the
 511              data file.  Now see whether we have to update the list.  */
 512           while (narcs != *narcsp && narcs < fromlimit)
 513             {
 514               size_t to_index;
 515               size_t newfromidx;
 516               to_index = (data[narcs].self_pc
 517                           / (hashfraction * sizeof (*tos)));
 518               newfromidx = exchange_and_add (&fromidx, 1) + 1;
 519               froms[newfromidx].here = &data[narcs];
 520               froms[newfromidx].link = tos[to_index];
 521               tos[to_index] = newfromidx;
 522               atomic_add (&narcs, 1);
 523             }
 524
 525           /* If we still have no entry stop searching and insert.  */
 526           if (*topcindex == 0)
 527             {
 528               uint_fast32_t newarc = exchange_and_add (narcsp, 1);
 529
 530               /* In rare cases it could happen that all entries in FROMS are
 531                  occupied.  So we cannot count this anymore.  */
 532               if (newarc >= fromlimit)
 533                 goto done;
 534
 535               *topcindex = exchange_and_add (&fromidx, 1) + 1;
 536               fromp = &froms[*topcindex];
 537
 538               fromp->here = &data[newarc];
 539               data[newarc].from_pc = frompc;
 540               data[newarc].self_pc = selfpc;
 541               data[newarc].count = 0;
 542               fromp->link = 0;
 543               atomic_add (&narcs, 1);
 544
 545               break;
 546             }
 547
 548           fromp = &froms[*topcindex];
 549         }
 550       else
 551         /* Found in.  */
 552         break;
 553     }
 554
 555   /* Increment the counter.  */
 556   atomic_add (&fromp->here->count, 1);
 557
 558  done:
 559   ;
 560 }