elf/dl-profile.c

   1 /* Profiling of shared libraries.
   2    Copyright (C) 1997-2002, 2003, 2004 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
 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 log_hashfraction;
 166
 167
 168 \f
 169 /* Set up profiling data to profile object desribed by MAP.  The output
 170    file is found (or created) in OUTPUT_DIR.  */
 171 void
 172 internal_function
 173 _dl_start_profile (void)
 174 {
 175   char *filename;
 176   int fd;
 177   struct stat64 st;
 178   const ElfW(Phdr) *ph;
 179   ElfW(Addr) mapstart = ~((ElfW(Addr)) 0);
 180   ElfW(Addr) mapend = 0;
 181   struct gmon_hdr gmon_hdr;
 182   struct gmon_hist_hdr hist_hdr;
 183   char *hist, *cp;
 184   size_t idx;
 185   size_t tossize;
 186   size_t fromssize;
 187   uintptr_t highpc;
 188   uint16_t *kcount;
 189   size_t kcountsize;
 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   const char *errstr = NULL;
 196
 197   /* Compute the size of the sections which contain program code.  */
 198   for (ph = GL(dl_profile_map)->l_phdr;
 199        ph < &GL(dl_profile_map)->l_phdr[GL(dl_profile_map)->l_phnum]; ++ph)
 200     if (ph->p_type == PT_LOAD && (ph->p_flags & PF_X))
 201       {
 202         ElfW(Addr) start = (ph->p_vaddr & ~(GLRO(dl_pagesize) - 1));
 203         ElfW(Addr) end = ((ph->p_vaddr + ph->p_memsz + GLRO(dl_pagesize) - 1)
 204                           & ~(GLRO(dl_pagesize) - 1));
 205
 206         if (start < mapstart)
 207           mapstart = start;
 208         if (end > mapend)
 209           mapend = end;
 210       }
 211
 212   /* Now we can compute the size of the profiling data.  This is done
 213      with the same formulars as in `monstartup' (see gmon.c).  */
 214   running = 0;
 215   lowpc = ROUNDDOWN (mapstart + GL(dl_profile_map)->l_addr,
 216                      HISTFRACTION * sizeof (HISTCOUNTER));
 217   highpc = ROUNDUP (mapend + GL(dl_profile_map)->l_addr,
 218                     HISTFRACTION * sizeof (HISTCOUNTER));
 219   textsize = highpc - lowpc;
 220   kcountsize = textsize / HISTFRACTION;
 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 (GLRO(dl_profile_output)) + 1
 277                               + strlen (GLRO(dl_profile)) + sizeof ".profile");
 278   cp = __stpcpy (filename, GLRO(dl_profile_output));
 279   *cp++ = '/';
 280   __stpcpy (__stpcpy (cp, GLRO(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       char buf[400];
 291       int errnum;
 292
 293       /* We cannot write the profiling data so don't do anything.  */
 294       errstr = "%s: cannot open file: %s\n";
 295     print_error:
 296       errnum = errno;
 297       if (fd != -1)
 298         __close (fd);
 299       _dl_error_printf (errstr, filename,
 300                         __strerror_r (errnum, buf, sizeof buf));
 301       return;
 302     }
 303
 304   if (__fxstat64 (_STAT_VER, fd, &st) < 0 || !S_ISREG (st.st_mode))
 305     {
 306       /* Not stat'able or not a regular file => don't use it.  */
 307       errstr = "%s: cannot stat file: %s\n";
 308       goto print_error;
 309     }
 310
 311   /* Test the size.  If it does not match what we expect from the size
 312      values in the map MAP we don't use it and warn the user.  */
 313   if (st.st_size == 0)
 314     {
 315       /* We have to create the file.  */
 316       char buf[GLRO(dl_pagesize)];
 317
 318       memset (buf, '\0', GLRO(dl_pagesize));
 319
 320       if (__lseek (fd, expected_size & ~(GLRO(dl_pagesize) - 1), SEEK_SET) == -1)
 321         {
 322         cannot_create:
 323           errstr = "%s: cannot create file: %s\n";
 324           goto print_error;
 325         }
 326
 327       if (TEMP_FAILURE_RETRY (__libc_write (fd, buf, (expected_size
 328                                                       & (GLRO(dl_pagesize)
 329                                                          - 1))))
 330           < 0)
 331         goto cannot_create;
 332     }
 333   else if (st.st_size != expected_size)
 334     {
 335       __close (fd);
 336     wrong_format:
 337
 338       if (addr != NULL)
 339         __munmap ((void *) addr, expected_size);
 340
 341       _dl_error_printf ("%s: file is no correct profile data file for `%s'\n",
 342                         filename, GLRO(dl_profile));
 343       return;
 344     }
 345
 346   addr = (struct gmon_hdr *) __mmap (NULL, expected_size, PROT_READ|PROT_WRITE,
 347                                      MAP_SHARED|MAP_FILE, fd, 0);
 348   if (addr == (struct gmon_hdr *) MAP_FAILED)
 349     {
 350       errstr = "%s: cannot map file: %s\n";
 351       goto print_error;
 352     }
 353
 354   /* We don't need the file descriptor anymore.  */
 355   __close (fd);
 356
 357   /* Pointer to data after the header.  */
 358   hist = (char *) (addr + 1);
 359   kcount = (uint16_t *) ((char *) hist + sizeof (uint32_t)
 360                          + sizeof (struct gmon_hist_hdr));
 361
 362   /* Compute pointer to array of the arc information.  */
 363   narcsp = (uint32_t *) ((char *) kcount + kcountsize + sizeof (uint32_t));
 364   data = (struct here_cg_arc_record *) ((char *) narcsp + sizeof (uint32_t));
 365
 366   if (st.st_size == 0)
 367     {
 368       /* Create the signature.  */
 369       memcpy (addr, &gmon_hdr, sizeof (struct gmon_hdr));
 370
 371       *(uint32_t *) hist = GMON_TAG_TIME_HIST;
 372       memcpy (hist + sizeof (uint32_t), &hist_hdr,
 373               sizeof (struct gmon_hist_hdr));
 374
 375       narcsp[-1] = GMON_TAG_CG_ARC;
 376     }
 377   else
 378     {
 379       /* Test the signature in the file.  */
 380       if (memcmp (addr, &gmon_hdr, sizeof (struct gmon_hdr)) != 0
 381           || *(uint32_t *) hist != GMON_TAG_TIME_HIST
 382           || memcmp (hist + sizeof (uint32_t), &hist_hdr,
 383                      sizeof (struct gmon_hist_hdr)) != 0
 384           || narcsp[-1] != GMON_TAG_CG_ARC)
 385         goto wrong_format;
 386     }
 387
 388   /* Allocate memory for the froms data and the pointer to the tos records.  */
 389   tos = (uint16_t *) calloc (tossize + fromssize, 1);
 390   if (tos == NULL)
 391     {
 392       __munmap ((void *) addr, expected_size);
 393       _dl_fatal_printf ("Out of memory while initializing profiler\n");
 394       /* NOTREACHED */
 395     }
 396
 397   froms = (struct here_fromstruct *) ((char *) tos + tossize);
 398   fromidx = 0;
 399
 400   /* Now we have to process all the arc count entries.  BTW: it is
 401      not critical whether the *NARCSP value changes meanwhile.  Before
 402      we enter a new entry in to toset we will check that everything is
 403      available in TOS.  This happens in _dl_mcount.
 404
 405      Loading the entries in reverse order should help to get the most
 406      frequently used entries at the front of the list.  */
 407   for (idx = narcs = MIN (*narcsp, fromlimit); idx > 0; )
 408     {
 409       size_t to_index;
 410       size_t newfromidx;
 411       --idx;
 412       to_index = (data[idx].self_pc / (HASHFRACTION * sizeof (*tos)));
 413       newfromidx = fromidx++;
 414       froms[newfromidx].here = &data[idx];
 415       froms[newfromidx].link = tos[to_index];
 416       tos[to_index] = newfromidx;
 417     }
 418
 419   /* Setup counting data.  */
 420   if (kcountsize < highpc - lowpc)
 421     {
 422 #if 0
 423       s_scale = ((double) kcountsize / (highpc - lowpc)) * SCALE_1_TO_1;
 424 #else
 425       size_t range = highpc - lowpc;
 426       size_t quot = range / kcountsize;
 427
 428       if (quot >= SCALE_1_TO_1)
 429         s_scale = 1;
 430       else if (quot >= SCALE_1_TO_1 / 256)
 431         s_scale = SCALE_1_TO_1 / quot;
 432       else if (range > ULONG_MAX / 256)
 433         s_scale = (SCALE_1_TO_1 * 256) / (range / (kcountsize / 256));
 434       else
 435         s_scale = (SCALE_1_TO_1 * 256) / ((range * 256) / kcountsize);
 436 #endif
 437     }
 438   else
 439     s_scale = SCALE_1_TO_1;
 440
 441   /* Start the profiler.  */
 442   __profil ((void *) kcount, kcountsize, lowpc, s_scale);
 443
 444   /* Turn on profiling.  */
 445   running = 1;
 446 }
 447
 448
 449 void
 450 _dl_mcount (ElfW(Addr) frompc, ElfW(Addr) selfpc)
 451 {
 452   volatile uint16_t *topcindex;
 453   size_t i, fromindex;
 454   struct here_fromstruct *fromp;
 455
 456   if (! running)
 457     return;
 458
 459   /* Compute relative addresses.  The shared object can be loaded at
 460      any address.  The value of frompc could be anything.  We cannot
 461      restrict it in any way, just set to a fixed value (0) in case it
 462      is outside the allowed range.  These calls show up as calls from
 463      <external> in the gprof output.  */
 464   frompc -= lowpc;
 465   if (frompc >= textsize)
 466     frompc = 0;
 467   selfpc -= lowpc;
 468   if (selfpc >= textsize)
 469     goto done;
 470
 471   /* Getting here we now have to find out whether the location was
 472      already used.  If yes we are lucky and only have to increment a
 473      counter (this also has to be atomic).  If the entry is new things
 474      are getting complicated...  */
 475
 476   /* Avoid integer divide if possible.  */
 477   if ((HASHFRACTION & (HASHFRACTION - 1)) == 0)
 478     i = selfpc >> log_hashfraction;
 479   else
 480     i = selfpc / (HASHFRACTION * sizeof (*tos));
 481
 482   topcindex = &tos[i];
 483   fromindex = *topcindex;
 484
 485   if (fromindex == 0)
 486     goto check_new_or_add;
 487
 488   fromp = &froms[fromindex];
 489
 490   /* We have to look through the chain of arcs whether there is already
 491      an entry for our arc.  */
 492   while (fromp->here->from_pc != frompc)
 493     {
 494       if (fromp->link != 0)
 495         do
 496           fromp = &froms[fromp->link];
 497         while (fromp->link != 0 && fromp->here->from_pc != frompc);
 498
 499       if (fromp->here->from_pc != frompc)
 500         {
 501           topcindex = &fromp->link;
 502
 503         check_new_or_add:
 504           /* Our entry is not among the entries we read so far from the
 505              data file.  Now see whether we have to update the list.  */
 506           while (narcs != *narcsp && narcs < fromlimit)
 507             {
 508               size_t to_index;
 509               size_t newfromidx;
 510               to_index = (data[narcs].self_pc
 511                           / (HASHFRACTION * sizeof (*tos)));
 512               newfromidx = atomic_exchange_and_add (&fromidx, 1) + 1;
 513               froms[newfromidx].here = &data[narcs];
 514               froms[newfromidx].link = tos[to_index];
 515               tos[to_index] = newfromidx;
 516               atomic_increment (&narcs);
 517             }
 518
 519           /* If we still have no entry stop searching and insert.  */
 520           if (*topcindex == 0)
 521             {
 522               uint_fast32_t newarc = atomic_exchange_and_add (narcsp, 1);
 523
 524               /* In rare cases it could happen that all entries in FROMS are
 525                  occupied.  So we cannot count this anymore.  */
 526               if (newarc >= fromlimit)
 527                 goto done;
 528
 529               *topcindex = atomic_exchange_and_add (&fromidx, 1) + 1;
 530               fromp = &froms[*topcindex];
 531
 532               fromp->here = &data[newarc];
 533               data[newarc].from_pc = frompc;
 534               data[newarc].self_pc = selfpc;
 535               data[newarc].count = 0;
 536               fromp->link = 0;
 537               atomic_increment (&narcs);
 538
 539               break;
 540             }
 541
 542           fromp = &froms[*topcindex];
 543         }
 544       else
 545         /* Found in.  */
 546         break;
 547     }
 548
 549   /* Increment the counter.  */
 550   atomic_increment (&fromp->here->count);
 551
 552  done:
 553   ;
 554 }
 555 INTDEF(_dl_mcount)