elf/dl-profile.c

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