elf/dl-profile.c

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