1: /* Profiling of shared libraries.
    2:    Copyright (C) 1997-2002, 2003, 2004, 2006 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: ^L
  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 = catomic_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:               catomic_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 = catomic_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 = catomic_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:               catomic_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:   catomic_increment (&fromp->here->count);
  551: 
  552:  done:
  553:   ;
  554: }
  555: INTDEF(_dl_mcount)