gcc/gcov-io.c

   1 /* File format for coverage information
   2    Copyright (C) 1996-2017 Free Software Foundation, Inc.
   3    Contributed by Bob Manson <manson@cygnus.com>.
   4    Completely remangled by Nathan Sidwell <nathan@codesourcery.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 Under Section 7 of GPL version 3, you are granted additional
  19 permissions described in the GCC Runtime Library Exception, version
  20 3.1, as published by the Free Software Foundation.
  21
  22 You should have received a copy of the GNU General Public License and
  23 a copy of the GCC Runtime Library Exception along with this program;
  24 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  25 <http://www.gnu.org/licenses/>.  */
  26
  27 /* Routines declared in gcov-io.h.  This file should be #included by
  28    another source file, after having #included gcov-io.h.  */
  29
  30 #if !IN_GCOV
  31 static void gcov_write_block (unsigned);
  32 static gcov_unsigned_t *gcov_write_words (unsigned);
  33 #endif
  34 static const gcov_unsigned_t *gcov_read_words (unsigned);
  35 #if !IN_LIBGCOV
  36 static void gcov_allocate (unsigned);
  37 #endif
  38
  39 /* Optimum number of gcov_unsigned_t's read from or written to disk.  */
  40 #define GCOV_BLOCK_SIZE (1 << 10)
  41
  42 struct gcov_var
  43 {
  44   FILE *file;
  45   gcov_position_t start;        /* Position of first byte of block */
  46   unsigned offset;              /* Read/write position within the block.  */
  47   unsigned length;              /* Read limit in the block.  */
  48   unsigned overread;            /* Number of words overread.  */
  49   int error;                    /* < 0 overflow, > 0 disk error.  */
  50   int mode;                     /* < 0 writing, > 0 reading */
  51 #if IN_LIBGCOV
  52   /* Holds one block plus 4 bytes, thus all coverage reads & writes
  53      fit within this buffer and we always can transfer GCOV_BLOCK_SIZE
  54      to and from the disk. libgcov never backtracks and only writes 4
  55      or 8 byte objects.  */
  56   gcov_unsigned_t buffer[GCOV_BLOCK_SIZE + 1];
  57 #else
  58   int endian;                   /* Swap endianness.  */
  59   /* Holds a variable length block, as the compiler can write
  60      strings and needs to backtrack.  */
  61   size_t alloc;
  62   gcov_unsigned_t *buffer;
  63 #endif
  64 } gcov_var;
  65
  66 /* Save the current position in the gcov file.  */
  67 /* We need to expose this function when compiling for gcov-tool.  */
  68 #ifndef IN_GCOV_TOOL
  69 static inline
  70 #endif
  71 gcov_position_t
  72 gcov_position (void)
  73 {
  74   gcov_nonruntime_assert (gcov_var.mode > 0);
  75   return gcov_var.start + gcov_var.offset;
  76 }
  77
  78 /* Return nonzero if the error flag is set.  */
  79 /* We need to expose this function when compiling for gcov-tool.  */
  80 #ifndef IN_GCOV_TOOL
  81 static inline
  82 #endif
  83 int
  84 gcov_is_error (void)
  85 {
  86   return gcov_var.file ? gcov_var.error : 1;
  87 }
  88
  89 #if IN_LIBGCOV
  90 /* Move to beginning of file and initialize for writing.  */
  91 GCOV_LINKAGE inline void
  92 gcov_rewrite (void)
  93 {
  94   gcov_var.mode = -1;
  95   gcov_var.start = 0;
  96   gcov_var.offset = 0;
  97   fseek (gcov_var.file, 0L, SEEK_SET);
  98 }
  99 #endif
 100
 101 static inline gcov_unsigned_t from_file (gcov_unsigned_t value)
 102 {
 103 #if !IN_LIBGCOV
 104   if (gcov_var.endian)
 105     {
 106       value = (value >> 16) | (value << 16);
 107       value = ((value & 0xff00ff) << 8) | ((value >> 8) & 0xff00ff);
 108     }
 109 #endif
 110   return value;
 111 }
 112
 113 /* Open a gcov file. NAME is the name of the file to open and MODE
 114    indicates whether a new file should be created, or an existing file
 115    opened. If MODE is >= 0 an existing file will be opened, if
 116    possible, and if MODE is <= 0, a new file will be created. Use
 117    MODE=0 to attempt to reopen an existing file and then fall back on
 118    creating a new one.  If MODE > 0, the file will be opened in
 119    read-only mode.  Otherwise it will be opened for modification.
 120    Return zero on failure, non-zero on success.  */
 121
 122 GCOV_LINKAGE int
 123 #if IN_LIBGCOV
 124 gcov_open (const char *name)
 125 #else
 126 gcov_open (const char *name, int mode)
 127 #endif
 128 {
 129 #if IN_LIBGCOV
 130   int mode = 0;
 131 #endif
 132 #if GCOV_LOCKED
 133   struct flock s_flock;
 134   int fd;
 135
 136   s_flock.l_whence = SEEK_SET;
 137   s_flock.l_start = 0;
 138   s_flock.l_len = 0; /* Until EOF.  */
 139   s_flock.l_pid = getpid ();
 140 #endif
 141
 142   gcov_nonruntime_assert (!gcov_var.file);
 143   gcov_var.start = 0;
 144   gcov_var.offset = gcov_var.length = 0;
 145   gcov_var.overread = -1u;
 146   gcov_var.error = 0;
 147 #if !IN_LIBGCOV
 148   gcov_var.endian = 0;
 149 #endif
 150 #if GCOV_LOCKED
 151   if (mode > 0)
 152     {
 153       /* Read-only mode - acquire a read-lock.  */
 154       s_flock.l_type = F_RDLCK;
 155       /* pass mode (ignored) for compatibility */
 156       fd = open (name, O_RDONLY, S_IRUSR | S_IWUSR);
 157     }
 158   else
 159      {
 160        /* Write mode - acquire a write-lock.  */
 161        s_flock.l_type = F_WRLCK;
 162        /* Truncate if force new mode.  */
 163        fd = open (name, O_RDWR | O_CREAT | (mode < 0 ? O_TRUNC : 0), 0666);
 164     }
 165   if (fd < 0)
 166     return 0;
 167
 168   while (fcntl (fd, F_SETLKW, &s_flock) && errno == EINTR)
 169     continue;
 170
 171   gcov_var.file = fdopen (fd, (mode > 0) ? "rb" : "r+b");
 172
 173   if (!gcov_var.file)
 174     {
 175       close (fd);
 176       return 0;
 177     }
 178 #else
 179   if (mode >= 0)
 180     /* Open an existing file.  */
 181     gcov_var.file = fopen (name, (mode > 0) ? "rb" : "r+b");
 182
 183   if (gcov_var.file)
 184     mode = 1;
 185   else if (mode <= 0)
 186     /* Create a new file.  */
 187     gcov_var.file = fopen (name, "w+b");
 188
 189   if (!gcov_var.file)
 190     return 0;
 191 #endif
 192
 193   gcov_var.mode = mode ? mode : 1;
 194
 195   setbuf (gcov_var.file, (char *)0);
 196
 197   return 1;
 198 }
 199
 200 /* Close the current gcov file. Flushes data to disk. Returns nonzero
 201    on failure or error flag set.  */
 202
 203 GCOV_LINKAGE int
 204 gcov_close (void)
 205 {
 206   if (gcov_var.file)
 207     {
 208 #if !IN_GCOV
 209       if (gcov_var.offset && gcov_var.mode < 0)
 210         gcov_write_block (gcov_var.offset);
 211 #endif
 212       fclose (gcov_var.file);
 213       gcov_var.file = 0;
 214       gcov_var.length = 0;
 215     }
 216 #if !IN_LIBGCOV
 217   free (gcov_var.buffer);
 218   gcov_var.alloc = 0;
 219   gcov_var.buffer = 0;
 220 #endif
 221   gcov_var.mode = 0;
 222   return gcov_var.error;
 223 }
 224
 225 #if !IN_LIBGCOV
 226 /* Check if MAGIC is EXPECTED. Use it to determine endianness of the
 227    file. Returns +1 for same endian, -1 for other endian and zero for
 228    not EXPECTED.  */
 229
 230 GCOV_LINKAGE int
 231 gcov_magic (gcov_unsigned_t magic, gcov_unsigned_t expected)
 232 {
 233   if (magic == expected)
 234     return 1;
 235   magic = (magic >> 16) | (magic << 16);
 236   magic = ((magic & 0xff00ff) << 8) | ((magic >> 8) & 0xff00ff);
 237   if (magic == expected)
 238     {
 239       gcov_var.endian = 1;
 240       return -1;
 241     }
 242   return 0;
 243 }
 244 #endif
 245
 246 #if !IN_LIBGCOV
 247 static void
 248 gcov_allocate (unsigned length)
 249 {
 250   size_t new_size = gcov_var.alloc;
 251
 252   if (!new_size)
 253     new_size = GCOV_BLOCK_SIZE;
 254   new_size += length;
 255   new_size *= 2;
 256
 257   gcov_var.alloc = new_size;
 258   gcov_var.buffer = XRESIZEVAR (gcov_unsigned_t, gcov_var.buffer, new_size << 2);
 259 }
 260 #endif
 261
 262 #if !IN_GCOV
 263 /* Write out the current block, if needs be.  */
 264
 265 static void
 266 gcov_write_block (unsigned size)
 267 {
 268   if (fwrite (gcov_var.buffer, size << 2, 1, gcov_var.file) != 1)
 269     gcov_var.error = 1;
 270   gcov_var.start += size;
 271   gcov_var.offset -= size;
 272 }
 273
 274 /* Allocate space to write BYTES bytes to the gcov file. Return a
 275    pointer to those bytes, or NULL on failure.  */
 276
 277 static gcov_unsigned_t *
 278 gcov_write_words (unsigned words)
 279 {
 280   gcov_unsigned_t *result;
 281
 282   gcov_nonruntime_assert (gcov_var.mode < 0);
 283 #if IN_LIBGCOV
 284   if (gcov_var.offset >= GCOV_BLOCK_SIZE)
 285     {
 286       gcov_write_block (GCOV_BLOCK_SIZE);
 287       if (gcov_var.offset)
 288         {
 289           memcpy (gcov_var.buffer, gcov_var.buffer + GCOV_BLOCK_SIZE, 4);
 290         }
 291     }
 292 #else
 293   if (gcov_var.offset + words > gcov_var.alloc)
 294     gcov_allocate (gcov_var.offset + words);
 295 #endif
 296   result = &gcov_var.buffer[gcov_var.offset];
 297   gcov_var.offset += words;
 298
 299   return result;
 300 }
 301
 302 /* Write unsigned VALUE to coverage file.  Sets error flag
 303    appropriately.  */
 304
 305 GCOV_LINKAGE void
 306 gcov_write_unsigned (gcov_unsigned_t value)
 307 {
 308   gcov_unsigned_t *buffer = gcov_write_words (1);
 309
 310   buffer[0] = value;
 311 }
 312
 313 /* Write counter VALUE to coverage file.  Sets error flag
 314    appropriately.  */
 315
 316 #if IN_LIBGCOV
 317 GCOV_LINKAGE void
 318 gcov_write_counter (gcov_type value)
 319 {
 320   gcov_unsigned_t *buffer = gcov_write_words (2);
 321
 322   buffer[0] = (gcov_unsigned_t) value;
 323   if (sizeof (value) > sizeof (gcov_unsigned_t))
 324     buffer[1] = (gcov_unsigned_t) (value >> 32);
 325   else
 326     buffer[1] = 0;
 327 }
 328 #endif /* IN_LIBGCOV */
 329
 330 #if !IN_LIBGCOV
 331 /* Write STRING to coverage file.  Sets error flag on file
 332    error, overflow flag on overflow */
 333
 334 GCOV_LINKAGE void
 335 gcov_write_string (const char *string)
 336 {
 337   unsigned length = 0;
 338   unsigned alloc = 0;
 339   gcov_unsigned_t *buffer;
 340
 341   if (string)
 342     {
 343       length = strlen (string);
 344       alloc = (length + 4) >> 2;
 345     }
 346
 347   buffer = gcov_write_words (1 + alloc);
 348
 349   buffer[0] = alloc;
 350   buffer[alloc] = 0;
 351   memcpy (&buffer[1], string, length);
 352 }
 353 #endif
 354
 355 #if !IN_LIBGCOV
 356 /* Write a tag TAG and reserve space for the record length. Return a
 357    value to be used for gcov_write_length.  */
 358
 359 GCOV_LINKAGE gcov_position_t
 360 gcov_write_tag (gcov_unsigned_t tag)
 361 {
 362   gcov_position_t result = gcov_var.start + gcov_var.offset;
 363   gcov_unsigned_t *buffer = gcov_write_words (2);
 364
 365   buffer[0] = tag;
 366   buffer[1] = 0;
 367
 368   return result;
 369 }
 370
 371 /* Write a record length using POSITION, which was returned by
 372    gcov_write_tag.  The current file position is the end of the
 373    record, and is restored before returning.  Returns nonzero on
 374    overflow.  */
 375
 376 GCOV_LINKAGE void
 377 gcov_write_length (gcov_position_t position)
 378 {
 379   unsigned offset;
 380   gcov_unsigned_t length;
 381   gcov_unsigned_t *buffer;
 382
 383   gcov_nonruntime_assert (gcov_var.mode < 0);
 384   gcov_nonruntime_assert (position + 2 <= gcov_var.start + gcov_var.offset);
 385   gcov_nonruntime_assert (position >= gcov_var.start);
 386   offset = position - gcov_var.start;
 387   length = gcov_var.offset - offset - 2;
 388   buffer = (gcov_unsigned_t *) &gcov_var.buffer[offset];
 389   buffer[1] = length;
 390   if (gcov_var.offset >= GCOV_BLOCK_SIZE)
 391     gcov_write_block (gcov_var.offset);
 392 }
 393
 394 #else /* IN_LIBGCOV */
 395
 396 /* Write a tag TAG and length LENGTH.  */
 397
 398 GCOV_LINKAGE void
 399 gcov_write_tag_length (gcov_unsigned_t tag, gcov_unsigned_t length)
 400 {
 401   gcov_unsigned_t *buffer = gcov_write_words (2);
 402
 403   buffer[0] = tag;
 404   buffer[1] = length;
 405 }
 406
 407 /* Write a summary structure to the gcov file.  Return nonzero on
 408    overflow.  */
 409
 410 GCOV_LINKAGE void
 411 gcov_write_summary (gcov_unsigned_t tag, const struct gcov_summary *summary)
 412 {
 413   unsigned ix, h_ix, bv_ix, h_cnt = 0;
 414   const struct gcov_ctr_summary *csum;
 415   unsigned histo_bitvector[GCOV_HISTOGRAM_BITVECTOR_SIZE];
 416
 417   /* Count number of non-zero histogram entries, and fill in a bit vector
 418      of non-zero indices. The histogram is only currently computed for arc
 419      counters.  */
 420   for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
 421     histo_bitvector[bv_ix] = 0;
 422   csum = &summary->ctrs[GCOV_COUNTER_ARCS];
 423   for (h_ix = 0; h_ix < GCOV_HISTOGRAM_SIZE; h_ix++)
 424     if (csum->histogram[h_ix].num_counters)
 425       {
 426         histo_bitvector[h_ix / 32] |= 1 << (h_ix % 32);
 427         h_cnt++;
 428       }
 429   gcov_write_tag_length (tag, GCOV_TAG_SUMMARY_LENGTH (h_cnt));
 430   gcov_write_unsigned (summary->checksum);
 431   for (csum = summary->ctrs, ix = GCOV_COUNTERS_SUMMABLE; ix--; csum++)
 432     {
 433       gcov_write_unsigned (csum->num);
 434       gcov_write_unsigned (csum->runs);
 435       gcov_write_counter (csum->sum_all);
 436       gcov_write_counter (csum->run_max);
 437       gcov_write_counter (csum->sum_max);
 438       if (ix != GCOV_COUNTER_ARCS)
 439         {
 440           for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
 441             gcov_write_unsigned (0);
 442           continue;
 443         }
 444       for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
 445         gcov_write_unsigned (histo_bitvector[bv_ix]);
 446       for (h_ix = 0; h_ix < GCOV_HISTOGRAM_SIZE; h_ix++)
 447         {
 448           if (!csum->histogram[h_ix].num_counters)
 449             continue;
 450           gcov_write_unsigned (csum->histogram[h_ix].num_counters);
 451           gcov_write_counter (csum->histogram[h_ix].min_value);
 452           gcov_write_counter (csum->histogram[h_ix].cum_value);
 453         }
 454     }
 455 }
 456 #endif /* IN_LIBGCOV */
 457
 458 #endif /*!IN_GCOV */
 459
 460 /* Return a pointer to read BYTES bytes from the gcov file. Returns
 461    NULL on failure (read past EOF).  */
 462
 463 static const gcov_unsigned_t *
 464 gcov_read_words (unsigned words)
 465 {
 466   const gcov_unsigned_t *result;
 467   unsigned excess = gcov_var.length - gcov_var.offset;
 468
 469   if (gcov_var.mode <= 0)
 470     return NULL;
 471
 472   if (excess < words)
 473     {
 474       gcov_var.start += gcov_var.offset;
 475       if (excess)
 476         {
 477 #if IN_LIBGCOV
 478           memcpy (gcov_var.buffer, gcov_var.buffer + gcov_var.offset, 4);
 479 #else
 480           memmove (gcov_var.buffer, gcov_var.buffer + gcov_var.offset,
 481                    excess * 4);
 482 #endif
 483         }
 484       gcov_var.offset = 0;
 485       gcov_var.length = excess;
 486 #if IN_LIBGCOV
 487       excess = GCOV_BLOCK_SIZE;
 488 #else
 489       if (gcov_var.length + words > gcov_var.alloc)
 490         gcov_allocate (gcov_var.length + words);
 491       excess = gcov_var.alloc - gcov_var.length;
 492 #endif
 493       excess = fread (gcov_var.buffer + gcov_var.length,
 494                       1, excess << 2, gcov_var.file) >> 2;
 495       gcov_var.length += excess;
 496       if (gcov_var.length < words)
 497         {
 498           gcov_var.overread += words - gcov_var.length;
 499           gcov_var.length = 0;
 500           return 0;
 501         }
 502     }
 503   result = &gcov_var.buffer[gcov_var.offset];
 504   gcov_var.offset += words;
 505   return result;
 506 }
 507
 508 /* Read unsigned value from a coverage file. Sets error flag on file
 509    error, overflow flag on overflow */
 510
 511 GCOV_LINKAGE gcov_unsigned_t
 512 gcov_read_unsigned (void)
 513 {
 514   gcov_unsigned_t value;
 515   const gcov_unsigned_t *buffer = gcov_read_words (1);
 516
 517   if (!buffer)
 518     return 0;
 519   value = from_file (buffer[0]);
 520   return value;
 521 }
 522
 523 /* Read counter value from a coverage file. Sets error flag on file
 524    error, overflow flag on overflow */
 525
 526 GCOV_LINKAGE gcov_type
 527 gcov_read_counter (void)
 528 {
 529   gcov_type value;
 530   const gcov_unsigned_t *buffer = gcov_read_words (2);
 531
 532   if (!buffer)
 533     return 0;
 534   value = from_file (buffer[0]);
 535   if (sizeof (value) > sizeof (gcov_unsigned_t))
 536     value |= ((gcov_type) from_file (buffer[1])) << 32;
 537   else if (buffer[1])
 538     gcov_var.error = -1;
 539
 540   return value;
 541 }
 542
 543 /* We need to expose the below function when compiling for gcov-tool.  */
 544
 545 #if !IN_LIBGCOV || defined (IN_GCOV_TOOL)
 546 /* Read string from coverage file. Returns a pointer to a static
 547    buffer, or NULL on empty string. You must copy the string before
 548    calling another gcov function.  */
 549
 550 GCOV_LINKAGE const char *
 551 gcov_read_string (void)
 552 {
 553   unsigned length = gcov_read_unsigned ();
 554
 555   if (!length)
 556     return 0;
 557
 558   return (const char *) gcov_read_words (length);
 559 }
 560 #endif
 561
 562 GCOV_LINKAGE void
 563 gcov_read_summary (struct gcov_summary *summary)
 564 {
 565   unsigned ix, h_ix, bv_ix, h_cnt = 0;
 566   struct gcov_ctr_summary *csum;
 567   unsigned histo_bitvector[GCOV_HISTOGRAM_BITVECTOR_SIZE];
 568   unsigned cur_bitvector;
 569
 570   summary->checksum = gcov_read_unsigned ();
 571   for (csum = summary->ctrs, ix = GCOV_COUNTERS_SUMMABLE; ix--; csum++)
 572     {
 573       csum->num = gcov_read_unsigned ();
 574       csum->runs = gcov_read_unsigned ();
 575       csum->sum_all = gcov_read_counter ();
 576       csum->run_max = gcov_read_counter ();
 577       csum->sum_max = gcov_read_counter ();
 578       memset (csum->histogram, 0,
 579               sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 580       for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
 581         {
 582           histo_bitvector[bv_ix] = gcov_read_unsigned ();
 583 #if IN_LIBGCOV
 584           /* When building libgcov we don't include system.h, which includes
 585              hwint.h (where popcount_hwi is declared). However, libgcov.a
 586              is built by the bootstrapped compiler and therefore the builtins
 587              are always available.  */
 588           h_cnt += __builtin_popcount (histo_bitvector[bv_ix]);
 589 #else
 590           h_cnt += popcount_hwi (histo_bitvector[bv_ix]);
 591 #endif
 592         }
 593       bv_ix = 0;
 594       h_ix = 0;
 595       cur_bitvector = 0;
 596       while (h_cnt--)
 597         {
 598           /* Find the index corresponding to the next entry we will read in.
 599              First find the next non-zero bitvector and re-initialize
 600              the histogram index accordingly, then right shift and increment
 601              the index until we find a set bit.  */
 602           while (!cur_bitvector)
 603             {
 604               h_ix = bv_ix * 32;
 605               if (bv_ix >= GCOV_HISTOGRAM_BITVECTOR_SIZE)
 606                 gcov_error ("corrupted profile info: summary histogram "
 607                             "bitvector is corrupt");
 608               cur_bitvector = histo_bitvector[bv_ix++];
 609             }
 610           while (!(cur_bitvector & 0x1))
 611             {
 612               h_ix++;
 613               cur_bitvector >>= 1;
 614             }
 615           if (h_ix >= GCOV_HISTOGRAM_SIZE)
 616             gcov_error ("corrupted profile info: summary histogram "
 617                         "index is corrupt");
 618
 619           csum->histogram[h_ix].num_counters = gcov_read_unsigned ();
 620           csum->histogram[h_ix].min_value = gcov_read_counter ();
 621           csum->histogram[h_ix].cum_value = gcov_read_counter ();
 622           /* Shift off the index we are done with and increment to the
 623              corresponding next histogram entry.  */
 624           cur_bitvector >>= 1;
 625           h_ix++;
 626         }
 627     }
 628 }
 629
 630 /* We need to expose the below function when compiling for gcov-tool.  */
 631
 632 #if !IN_LIBGCOV || defined (IN_GCOV_TOOL)
 633 /* Reset to a known position.  BASE should have been obtained from
 634    gcov_position, LENGTH should be a record length.  */
 635
 636 GCOV_LINKAGE void
 637 gcov_sync (gcov_position_t base, gcov_unsigned_t length)
 638 {
 639   gcov_nonruntime_assert (gcov_var.mode > 0);
 640   base += length;
 641   if (base - gcov_var.start <= gcov_var.length)
 642     gcov_var.offset = base - gcov_var.start;
 643   else
 644     {
 645       gcov_var.offset = gcov_var.length = 0;
 646       fseek (gcov_var.file, base << 2, SEEK_SET);
 647       gcov_var.start = ftell (gcov_var.file) >> 2;
 648     }
 649 }
 650 #endif
 651
 652 #if IN_LIBGCOV
 653 /* Move to a given position in a gcov file.  */
 654
 655 GCOV_LINKAGE void
 656 gcov_seek (gcov_position_t base)
 657 {
 658   if (gcov_var.offset)
 659     gcov_write_block (gcov_var.offset);
 660   fseek (gcov_var.file, base << 2, SEEK_SET);
 661   gcov_var.start = ftell (gcov_var.file) >> 2;
 662 }
 663 #endif
 664
 665 #if IN_GCOV > 0
 666 /* Return the modification time of the current gcov file.  */
 667
 668 GCOV_LINKAGE time_t
 669 gcov_time (void)
 670 {
 671   struct stat status;
 672
 673   if (fstat (fileno (gcov_var.file), &status))
 674     return 0;
 675   else
 676     return status.st_mtime;
 677 }
 678 #endif /* IN_GCOV */
 679
 680 #if !IN_GCOV
 681 /* Determine the index into histogram for VALUE. */
 682
 683 #if IN_LIBGCOV
 684 static unsigned
 685 #else
 686 GCOV_LINKAGE unsigned
 687 #endif
 688 gcov_histo_index (gcov_type value)
 689 {
 690   gcov_type_unsigned v = (gcov_type_unsigned)value;
 691   unsigned r = 0;
 692   unsigned prev2bits = 0;
 693
 694   /* Find index into log2 scale histogram, where each of the log2
 695      sized buckets is divided into 4 linear sub-buckets for better
 696      focus in the higher buckets.  */
 697
 698   /* Find the place of the most-significant bit set.  */
 699   if (v > 0)
 700     {
 701 #if IN_LIBGCOV
 702       /* When building libgcov we don't include system.h, which includes
 703          hwint.h (where floor_log2 is declared). However, libgcov.a
 704          is built by the bootstrapped compiler and therefore the builtins
 705          are always available.  */
 706       r = sizeof (long long) * __CHAR_BIT__ - 1 - __builtin_clzll (v);
 707 #else
 708       /* We use floor_log2 from hwint.c, which takes a HOST_WIDE_INT
 709          that is 64 bits and gcov_type_unsigned is 64 bits.  */
 710       r = floor_log2 (v);
 711 #endif
 712     }
 713
 714   /* If at most the 2 least significant bits are set (value is
 715      0 - 3) then that value is our index into the lowest set of
 716      four buckets.  */
 717   if (r < 2)
 718     return (unsigned)value;
 719
 720   gcov_nonruntime_assert (r < 64);
 721
 722   /* Find the two next most significant bits to determine which
 723      of the four linear sub-buckets to select.  */
 724   prev2bits = (v >> (r - 2)) & 0x3;
 725   /* Finally, compose the final bucket index from the log2 index and
 726      the next 2 bits. The minimum r value at this point is 2 since we
 727      returned above if r was 2 or more, so the minimum bucket at this
 728      point is 4.  */
 729   return (r - 1) * 4 + prev2bits;
 730 }
 731
 732 /* Merge SRC_HISTO into TGT_HISTO. The counters are assumed to be in
 733    the same relative order in both histograms, and are matched up
 734    and merged in reverse order. Each counter is assigned an equal portion of
 735    its entry's original cumulative counter value when computing the
 736    new merged cum_value.  */
 737
 738 static void gcov_histogram_merge (gcov_bucket_type *tgt_histo,
 739                                   gcov_bucket_type *src_histo)
 740 {
 741   int src_i, tgt_i, tmp_i = 0;
 742   unsigned src_num, tgt_num, merge_num;
 743   gcov_type src_cum, tgt_cum, merge_src_cum, merge_tgt_cum, merge_cum;
 744   gcov_type merge_min;
 745   gcov_bucket_type tmp_histo[GCOV_HISTOGRAM_SIZE];
 746   int src_done = 0;
 747
 748   memset (tmp_histo, 0, sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 749
 750   /* Assume that the counters are in the same relative order in both
 751      histograms. Walk the histograms from largest to smallest entry,
 752      matching up and combining counters in order.  */
 753   src_num = 0;
 754   src_cum = 0;
 755   src_i = GCOV_HISTOGRAM_SIZE - 1;
 756   for (tgt_i = GCOV_HISTOGRAM_SIZE - 1; tgt_i >= 0 && !src_done; tgt_i--)
 757     {
 758       tgt_num = tgt_histo[tgt_i].num_counters;
 759       tgt_cum = tgt_histo[tgt_i].cum_value;
 760       /* Keep going until all of the target histogram's counters at this
 761          position have been matched and merged with counters from the
 762          source histogram.  */
 763       while (tgt_num > 0 && !src_done)
 764         {
 765           /* If this is either the first time through this loop or we just
 766              exhausted the previous non-zero source histogram entry, look
 767              for the next non-zero source histogram entry.  */
 768           if (!src_num)
 769             {
 770               /* Locate the next non-zero entry.  */
 771               while (src_i >= 0 && !src_histo[src_i].num_counters)
 772                 src_i--;
 773               /* If source histogram has fewer counters, then just copy over the
 774                  remaining target counters and quit.  */
 775               if (src_i < 0)
 776                 {
 777                   tmp_histo[tgt_i].num_counters += tgt_num;
 778                   tmp_histo[tgt_i].cum_value += tgt_cum;
 779                   if (!tmp_histo[tgt_i].min_value ||
 780                       tgt_histo[tgt_i].min_value < tmp_histo[tgt_i].min_value)
 781                     tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value;
 782                   while (--tgt_i >= 0)
 783                     {
 784                       tmp_histo[tgt_i].num_counters
 785                           += tgt_histo[tgt_i].num_counters;
 786                       tmp_histo[tgt_i].cum_value += tgt_histo[tgt_i].cum_value;
 787                       if (!tmp_histo[tgt_i].min_value ||
 788                           tgt_histo[tgt_i].min_value
 789                           < tmp_histo[tgt_i].min_value)
 790                         tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value;
 791                     }
 792
 793                   src_done = 1;
 794                   break;
 795                 }
 796
 797               src_num = src_histo[src_i].num_counters;
 798               src_cum = src_histo[src_i].cum_value;
 799             }
 800
 801           /* The number of counters to merge on this pass is the minimum
 802              of the remaining counters from the current target and source
 803              histogram entries.  */
 804           merge_num = tgt_num;
 805           if (src_num < merge_num)
 806             merge_num = src_num;
 807
 808           /* The merged min_value is the sum of the min_values from target
 809              and source.  */
 810           merge_min = tgt_histo[tgt_i].min_value + src_histo[src_i].min_value;
 811
 812           /* Compute the portion of source and target entries' cum_value
 813              that will be apportioned to the counters being merged.
 814              The total remaining cum_value from each entry is divided
 815              equally among the counters from that histogram entry if we
 816              are not merging all of them.  */
 817           merge_src_cum = src_cum;
 818           if (merge_num < src_num)
 819             merge_src_cum = merge_num * src_cum / src_num;
 820           merge_tgt_cum = tgt_cum;
 821           if (merge_num < tgt_num)
 822             merge_tgt_cum = merge_num * tgt_cum / tgt_num;
 823           /* The merged cum_value is the sum of the source and target
 824              components.  */
 825           merge_cum = merge_src_cum + merge_tgt_cum;
 826
 827           /* Update the remaining number of counters and cum_value left
 828              to be merged from this source and target entry.  */
 829           src_cum -= merge_src_cum;
 830           tgt_cum -= merge_tgt_cum;
 831           src_num -= merge_num;
 832           tgt_num -= merge_num;
 833
 834           /* The merged counters get placed in the new merged histogram
 835              at the entry for the merged min_value.  */
 836           tmp_i = gcov_histo_index (merge_min);
 837           gcov_nonruntime_assert (tmp_i < GCOV_HISTOGRAM_SIZE);
 838           tmp_histo[tmp_i].num_counters += merge_num;
 839           tmp_histo[tmp_i].cum_value += merge_cum;
 840           if (!tmp_histo[tmp_i].min_value ||
 841               merge_min < tmp_histo[tmp_i].min_value)
 842             tmp_histo[tmp_i].min_value = merge_min;
 843
 844           /* Ensure the search for the next non-zero src_histo entry starts
 845              at the next smallest histogram bucket.  */
 846           if (!src_num)
 847             src_i--;
 848         }
 849     }
 850
 851   gcov_nonruntime_assert (tgt_i < 0);
 852
 853   /* In the case where there were more counters in the source histogram,
 854      accumulate the remaining unmerged cumulative counter values. Add
 855      those to the smallest non-zero target histogram entry. Otherwise,
 856      the total cumulative counter values in the histogram will be smaller
 857      than the sum_all stored in the summary, which will complicate
 858      computing the working set information from the histogram later on.  */
 859   if (src_num)
 860     src_i--;
 861   while (src_i >= 0)
 862     {
 863       src_cum += src_histo[src_i].cum_value;
 864       src_i--;
 865     }
 866   /* At this point, tmp_i should be the smallest non-zero entry in the
 867      tmp_histo.  */
 868   gcov_nonruntime_assert (tmp_i >= 0 && tmp_i < GCOV_HISTOGRAM_SIZE
 869                           && tmp_histo[tmp_i].num_counters > 0);
 870   tmp_histo[tmp_i].cum_value += src_cum;
 871
 872   /* Finally, copy the merged histogram into tgt_histo.  */
 873   memcpy (tgt_histo, tmp_histo,
 874           sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 875 }
 876 #endif /* !IN_GCOV */
 877
 878 /* This is used by gcov-dump (IN_GCOV == -1) and in the compiler
 879    (!IN_GCOV && !IN_LIBGCOV).  */
 880 #if IN_GCOV <= 0 && !IN_LIBGCOV
 881 /* Compute the working set information from the counter histogram in
 882    the profile summary. This is an array of information corresponding to a
 883    range of percentages of the total execution count (sum_all), and includes
 884    the number of counters required to cover that working set percentage and
 885    the minimum counter value in that working set.  */
 886
 887 GCOV_LINKAGE void
 888 compute_working_sets (const struct gcov_ctr_summary *summary,
 889                       gcov_working_set_t *gcov_working_sets)
 890 {
 891   gcov_type working_set_cum_values[NUM_GCOV_WORKING_SETS];
 892   gcov_type ws_cum_hotness_incr;
 893   gcov_type cum, tmp_cum;
 894   const gcov_bucket_type *histo_bucket;
 895   unsigned ws_ix, c_num, count;
 896   int h_ix;
 897
 898   /* Compute the amount of sum_all that the cumulative hotness grows
 899      by in each successive working set entry, which depends on the
 900      number of working set entries.  */
 901   ws_cum_hotness_incr = summary->sum_all / NUM_GCOV_WORKING_SETS;
 902
 903   /* Next fill in an array of the cumulative hotness values corresponding
 904      to each working set summary entry we are going to compute below.
 905      Skip 0% statistics, which can be extrapolated from the
 906      rest of the summary data.  */
 907   cum = ws_cum_hotness_incr;
 908   for (ws_ix = 0; ws_ix < NUM_GCOV_WORKING_SETS;
 909        ws_ix++, cum += ws_cum_hotness_incr)
 910     working_set_cum_values[ws_ix] = cum;
 911   /* The last summary entry is reserved for (roughly) 99.9% of the
 912      working set. Divide by 1024 so it becomes a shift, which gives
 913      almost exactly 99.9%.  */
 914   working_set_cum_values[NUM_GCOV_WORKING_SETS-1]
 915       = summary->sum_all - summary->sum_all/1024;
 916
 917   /* Next, walk through the histogram in decending order of hotness
 918      and compute the statistics for the working set summary array.
 919      As histogram entries are accumulated, we check to see which
 920      working set entries have had their expected cum_value reached
 921      and fill them in, walking the working set entries in increasing
 922      size of cum_value.  */
 923   ws_ix = 0; /* The current entry into the working set array.  */
 924   cum = 0; /* The current accumulated counter sum.  */
 925   count = 0; /* The current accumulated count of block counters.  */
 926   for (h_ix = GCOV_HISTOGRAM_SIZE - 1;
 927        h_ix >= 0 && ws_ix < NUM_GCOV_WORKING_SETS; h_ix--)
 928     {
 929       histo_bucket = &summary->histogram[h_ix];
 930
 931       /* If we haven't reached the required cumulative counter value for
 932          the current working set percentage, simply accumulate this histogram
 933          entry into the running sums and continue to the next histogram
 934          entry.  */
 935       if (cum + histo_bucket->cum_value < working_set_cum_values[ws_ix])
 936         {
 937           cum += histo_bucket->cum_value;
 938           count += histo_bucket->num_counters;
 939           continue;
 940         }
 941
 942       /* If adding the current histogram entry's cumulative counter value
 943          causes us to exceed the current working set size, then estimate
 944          how many of this histogram entry's counter values are required to
 945          reach the working set size, and fill in working set entries
 946          as we reach their expected cumulative value.  */
 947       for (c_num = 0, tmp_cum = cum;
 948            c_num < histo_bucket->num_counters && ws_ix < NUM_GCOV_WORKING_SETS;
 949            c_num++)
 950         {
 951           count++;
 952           /* If we haven't reached the last histogram entry counter, add
 953              in the minimum value again. This will underestimate the
 954              cumulative sum so far, because many of the counter values in this
 955              entry may have been larger than the minimum. We could add in the
 956              average value every time, but that would require an expensive
 957              divide operation.  */
 958           if (c_num + 1 < histo_bucket->num_counters)
 959             tmp_cum += histo_bucket->min_value;
 960           /* If we have reached the last histogram entry counter, then add
 961              in the entire cumulative value.  */
 962           else
 963             tmp_cum = cum + histo_bucket->cum_value;
 964
 965           /* Next walk through successive working set entries and fill in
 966              the statistics for any whose size we have reached by accumulating
 967              this histogram counter.  */
 968           while (ws_ix < NUM_GCOV_WORKING_SETS
 969                  && tmp_cum >= working_set_cum_values[ws_ix])
 970             {
 971               gcov_working_sets[ws_ix].num_counters = count;
 972               gcov_working_sets[ws_ix].min_counter
 973                   = histo_bucket->min_value;
 974               ws_ix++;
 975             }
 976         }
 977       /* Finally, update the running cumulative value since we were
 978          using a temporary above.  */
 979       cum += histo_bucket->cum_value;
 980     }
 981   gcov_nonruntime_assert (ws_ix == NUM_GCOV_WORKING_SETS);
 982 }
 983 #endif /* IN_GCOV <= 0 && !IN_LIBGCOV */