elf/dl-profile.c

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