gcc/gcov-io.c

   1 /* File format for coverage information
   2    Copyright (C) 1996-2018 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
 351   if (alloc > 0)
 352     {
 353       buffer[alloc] = 0; /* place nul terminators.  */
 354       memcpy (&buffer[1], string, length);
 355     }
 356 }
 357 #endif
 358
 359 #if !IN_LIBGCOV
 360 /* Write FILENAME to coverage file.  Sets error flag on file
 361    error, overflow flag on overflow */
 362
 363 GCOV_LINKAGE void
 364 gcov_write_filename (const char *filename)
 365 {
 366   if (profile_abs_path_flag && filename && filename[0]
 367       && !(IS_DIR_SEPARATOR (filename[0])
 368 #if HAVE_DOS_BASED_FILE_SYSTEM
 369            || filename[1] == ':'
 370 #endif
 371           ))
 372     {
 373       char *buf = getcwd (NULL, 0);
 374       if (buf != NULL && buf[0])
 375         {
 376           size_t len = strlen (buf);
 377           buf = (char*)xrealloc (buf, len + strlen (filename) + 2);
 378           if (!IS_DIR_SEPARATOR (buf[len - 1]))
 379             strcat (buf, "/");
 380           strcat (buf, filename);
 381           gcov_write_string (buf);
 382           free (buf);
 383           return;
 384         }
 385     }
 386
 387   gcov_write_string (filename);
 388 }
 389 #endif
 390
 391 #if !IN_LIBGCOV
 392 /* Write a tag TAG and reserve space for the record length. Return a
 393    value to be used for gcov_write_length.  */
 394
 395 GCOV_LINKAGE gcov_position_t
 396 gcov_write_tag (gcov_unsigned_t tag)
 397 {
 398   gcov_position_t result = gcov_var.start + gcov_var.offset;
 399   gcov_unsigned_t *buffer = gcov_write_words (2);
 400
 401   buffer[0] = tag;
 402   buffer[1] = 0;
 403
 404   return result;
 405 }
 406
 407 /* Write a record length using POSITION, which was returned by
 408    gcov_write_tag.  The current file position is the end of the
 409    record, and is restored before returning.  Returns nonzero on
 410    overflow.  */
 411
 412 GCOV_LINKAGE void
 413 gcov_write_length (gcov_position_t position)
 414 {
 415   unsigned offset;
 416   gcov_unsigned_t length;
 417   gcov_unsigned_t *buffer;
 418
 419   gcov_nonruntime_assert (gcov_var.mode < 0);
 420   gcov_nonruntime_assert (position + 2 <= gcov_var.start + gcov_var.offset);
 421   gcov_nonruntime_assert (position >= gcov_var.start);
 422   offset = position - gcov_var.start;
 423   length = gcov_var.offset - offset - 2;
 424   buffer = (gcov_unsigned_t *) &gcov_var.buffer[offset];
 425   buffer[1] = length;
 426   if (gcov_var.offset >= GCOV_BLOCK_SIZE)
 427     gcov_write_block (gcov_var.offset);
 428 }
 429
 430 #else /* IN_LIBGCOV */
 431
 432 /* Write a tag TAG and length LENGTH.  */
 433
 434 GCOV_LINKAGE void
 435 gcov_write_tag_length (gcov_unsigned_t tag, gcov_unsigned_t length)
 436 {
 437   gcov_unsigned_t *buffer = gcov_write_words (2);
 438
 439   buffer[0] = tag;
 440   buffer[1] = length;
 441 }
 442
 443 /* Write a summary structure to the gcov file.  Return nonzero on
 444    overflow.  */
 445
 446 GCOV_LINKAGE void
 447 gcov_write_summary (gcov_unsigned_t tag, const struct gcov_summary *summary)
 448 {
 449   unsigned h_ix, bv_ix, h_cnt = 0;
 450   unsigned histo_bitvector[GCOV_HISTOGRAM_BITVECTOR_SIZE];
 451
 452   /* Count number of non-zero histogram entries, and fill in a bit vector
 453      of non-zero indices. The histogram is only currently computed for arc
 454      counters.  */
 455   for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
 456     histo_bitvector[bv_ix] = 0;
 457   for (h_ix = 0; h_ix < GCOV_HISTOGRAM_SIZE; h_ix++)
 458     if (summary->histogram[h_ix].num_counters)
 459       {
 460         histo_bitvector[h_ix / 32] |= 1 << (h_ix % 32);
 461         h_cnt++;
 462       }
 463   gcov_write_tag_length (tag, GCOV_TAG_SUMMARY_LENGTH (h_cnt));
 464   gcov_write_unsigned (summary->checksum);
 465
 466   gcov_write_unsigned (summary->num);
 467   gcov_write_unsigned (summary->runs);
 468   gcov_write_counter (summary->sum_all);
 469   gcov_write_counter (summary->run_max);
 470   gcov_write_counter (summary->sum_max);
 471   for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
 472     gcov_write_unsigned (histo_bitvector[bv_ix]);
 473   for (h_ix = 0; h_ix < GCOV_HISTOGRAM_SIZE; h_ix++)
 474     {
 475       if (!summary->histogram[h_ix].num_counters)
 476         continue;
 477       gcov_write_unsigned (summary->histogram[h_ix].num_counters);
 478       gcov_write_counter (summary->histogram[h_ix].min_value);
 479       gcov_write_counter (summary->histogram[h_ix].cum_value);
 480     }
 481 }
 482 #endif /* IN_LIBGCOV */
 483
 484 #endif /*!IN_GCOV */
 485
 486 /* Return a pointer to read BYTES bytes from the gcov file. Returns
 487    NULL on failure (read past EOF).  */
 488
 489 static const gcov_unsigned_t *
 490 gcov_read_words (unsigned words)
 491 {
 492   const gcov_unsigned_t *result;
 493   unsigned excess = gcov_var.length - gcov_var.offset;
 494
 495   if (gcov_var.mode <= 0)
 496     return NULL;
 497
 498   if (excess < words)
 499     {
 500       gcov_var.start += gcov_var.offset;
 501       if (excess)
 502         {
 503 #if IN_LIBGCOV
 504           memcpy (gcov_var.buffer, gcov_var.buffer + gcov_var.offset, 4);
 505 #else
 506           memmove (gcov_var.buffer, gcov_var.buffer + gcov_var.offset,
 507                    excess * 4);
 508 #endif
 509         }
 510       gcov_var.offset = 0;
 511       gcov_var.length = excess;
 512 #if IN_LIBGCOV
 513       excess = GCOV_BLOCK_SIZE;
 514 #else
 515       if (gcov_var.length + words > gcov_var.alloc)
 516         gcov_allocate (gcov_var.length + words);
 517       excess = gcov_var.alloc - gcov_var.length;
 518 #endif
 519       excess = fread (gcov_var.buffer + gcov_var.length,
 520                       1, excess << 2, gcov_var.file) >> 2;
 521       gcov_var.length += excess;
 522       if (gcov_var.length < words)
 523         {
 524           gcov_var.overread += words - gcov_var.length;
 525           gcov_var.length = 0;
 526           return 0;
 527         }
 528     }
 529   result = &gcov_var.buffer[gcov_var.offset];
 530   gcov_var.offset += words;
 531   return result;
 532 }
 533
 534 /* Read unsigned value from a coverage file. Sets error flag on file
 535    error, overflow flag on overflow */
 536
 537 GCOV_LINKAGE gcov_unsigned_t
 538 gcov_read_unsigned (void)
 539 {
 540   gcov_unsigned_t value;
 541   const gcov_unsigned_t *buffer = gcov_read_words (1);
 542
 543   if (!buffer)
 544     return 0;
 545   value = from_file (buffer[0]);
 546   return value;
 547 }
 548
 549 /* Read counter value from a coverage file. Sets error flag on file
 550    error, overflow flag on overflow */
 551
 552 GCOV_LINKAGE gcov_type
 553 gcov_read_counter (void)
 554 {
 555   gcov_type value;
 556   const gcov_unsigned_t *buffer = gcov_read_words (2);
 557
 558   if (!buffer)
 559     return 0;
 560   value = from_file (buffer[0]);
 561   if (sizeof (value) > sizeof (gcov_unsigned_t))
 562     value |= ((gcov_type) from_file (buffer[1])) << 32;
 563   else if (buffer[1])
 564     gcov_var.error = -1;
 565
 566   return value;
 567 }
 568
 569 /* Mangle filename path of BASE and output new allocated pointer with
 570    mangled path.  */
 571
 572 char *
 573 mangle_path (char const *base)
 574 {
 575   /* Convert '/' to '#', convert '..' to '^',
 576      convert ':' to '~' on DOS based file system.  */
 577   const char *probe;
 578   char *buffer = (char *)xmalloc (strlen (base) + 10);
 579   char *ptr = buffer;
 580
 581 #if HAVE_DOS_BASED_FILE_SYSTEM
 582   if (base[0] && base[1] == ':')
 583     {
 584       ptr[0] = base[0];
 585       ptr[1] = '~';
 586       ptr += 2;
 587       base += 2;
 588     }
 589 #endif
 590   for (; *base; base = probe)
 591     {
 592       size_t len;
 593
 594       for (probe = base; *probe; probe++)
 595         if (*probe == '/')
 596           break;
 597       len = probe - base;
 598       if (len == 2 && base[0] == '.' && base[1] == '.')
 599         *ptr++ = '^';
 600       else
 601         {
 602           memcpy (ptr, base, len);
 603           ptr += len;
 604         }
 605       if (*probe)
 606         {
 607           *ptr++ = '#';
 608           probe++;
 609         }
 610     }
 611
 612   /* Terminate the string.  */
 613   *ptr = '\0';
 614
 615   return buffer;
 616 }
 617
 618 /* We need to expose the below function when compiling for gcov-tool.  */
 619
 620 #if !IN_LIBGCOV || defined (IN_GCOV_TOOL)
 621 /* Read string from coverage file. Returns a pointer to a static
 622    buffer, or NULL on empty string. You must copy the string before
 623    calling another gcov function.  */
 624
 625 GCOV_LINKAGE const char *
 626 gcov_read_string (void)
 627 {
 628   unsigned length = gcov_read_unsigned ();
 629
 630   if (!length)
 631     return 0;
 632
 633   return (const char *) gcov_read_words (length);
 634 }
 635 #endif
 636
 637 GCOV_LINKAGE void
 638 gcov_read_summary (struct gcov_summary *summary)
 639 {
 640   unsigned h_ix, bv_ix, h_cnt = 0;
 641   unsigned histo_bitvector[GCOV_HISTOGRAM_BITVECTOR_SIZE];
 642   unsigned cur_bitvector;
 643
 644   summary->checksum = gcov_read_unsigned ();
 645   summary->num = gcov_read_unsigned ();
 646   summary->runs = gcov_read_unsigned ();
 647   summary->sum_all = gcov_read_counter ();
 648   summary->run_max = gcov_read_counter ();
 649   summary->sum_max = gcov_read_counter ();
 650   memset (summary->histogram, 0,
 651           sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 652   for (bv_ix = 0; bv_ix < GCOV_HISTOGRAM_BITVECTOR_SIZE; bv_ix++)
 653     {
 654       histo_bitvector[bv_ix] = gcov_read_unsigned ();
 655 #if IN_LIBGCOV
 656       /* When building libgcov we don't include system.h, which includes
 657          hwint.h (where popcount_hwi is declared). However, libgcov.a
 658          is built by the bootstrapped compiler and therefore the builtins
 659          are always available.  */
 660       h_cnt += __builtin_popcount (histo_bitvector[bv_ix]);
 661 #else
 662       h_cnt += popcount_hwi (histo_bitvector[bv_ix]);
 663 #endif
 664     }
 665   bv_ix = 0;
 666   h_ix = 0;
 667   cur_bitvector = 0;
 668   while (h_cnt--)
 669     {
 670       /* Find the index corresponding to the next entry we will read in.
 671          First find the next non-zero bitvector and re-initialize
 672          the histogram index accordingly, then right shift and increment
 673          the index until we find a set bit.  */
 674       while (!cur_bitvector)
 675         {
 676           h_ix = bv_ix * 32;
 677           if (bv_ix >= GCOV_HISTOGRAM_BITVECTOR_SIZE)
 678             gcov_error ("corrupted profile info: summary histogram "
 679                         "bitvector is corrupt");
 680           cur_bitvector = histo_bitvector[bv_ix++];
 681         }
 682       while (!(cur_bitvector & 0x1))
 683         {
 684           h_ix++;
 685           cur_bitvector >>= 1;
 686         }
 687       if (h_ix >= GCOV_HISTOGRAM_SIZE)
 688         gcov_error ("corrupted profile info: summary histogram "
 689                     "index is corrupt");
 690
 691       summary->histogram[h_ix].num_counters = gcov_read_unsigned ();
 692       summary->histogram[h_ix].min_value = gcov_read_counter ();
 693       summary->histogram[h_ix].cum_value = gcov_read_counter ();
 694       /* Shift off the index we are done with and increment to the
 695          corresponding next histogram entry.  */
 696       cur_bitvector >>= 1;
 697       h_ix++;
 698     }
 699 }
 700
 701 /* We need to expose the below function when compiling for gcov-tool.  */
 702
 703 #if !IN_LIBGCOV || defined (IN_GCOV_TOOL)
 704 /* Reset to a known position.  BASE should have been obtained from
 705    gcov_position, LENGTH should be a record length.  */
 706
 707 GCOV_LINKAGE void
 708 gcov_sync (gcov_position_t base, gcov_unsigned_t length)
 709 {
 710   gcov_nonruntime_assert (gcov_var.mode > 0);
 711   base += length;
 712   if (base - gcov_var.start <= gcov_var.length)
 713     gcov_var.offset = base - gcov_var.start;
 714   else
 715     {
 716       gcov_var.offset = gcov_var.length = 0;
 717       fseek (gcov_var.file, base << 2, SEEK_SET);
 718       gcov_var.start = ftell (gcov_var.file) >> 2;
 719     }
 720 }
 721 #endif
 722
 723 #if IN_LIBGCOV
 724 /* Move to a given position in a gcov file.  */
 725
 726 GCOV_LINKAGE void
 727 gcov_seek (gcov_position_t base)
 728 {
 729   if (gcov_var.offset)
 730     gcov_write_block (gcov_var.offset);
 731   fseek (gcov_var.file, base << 2, SEEK_SET);
 732   gcov_var.start = ftell (gcov_var.file) >> 2;
 733 }
 734 #endif
 735
 736 #if IN_GCOV > 0
 737 /* Return the modification time of the current gcov file.  */
 738
 739 GCOV_LINKAGE time_t
 740 gcov_time (void)
 741 {
 742   struct stat status;
 743
 744   if (fstat (fileno (gcov_var.file), &status))
 745     return 0;
 746   else
 747     return status.st_mtime;
 748 }
 749 #endif /* IN_GCOV */
 750
 751 #if !IN_GCOV
 752 /* Determine the index into histogram for VALUE. */
 753
 754 #if IN_LIBGCOV
 755 static unsigned
 756 #else
 757 GCOV_LINKAGE unsigned
 758 #endif
 759 gcov_histo_index (gcov_type value)
 760 {
 761   gcov_type_unsigned v = (gcov_type_unsigned)value;
 762   unsigned r = 0;
 763   unsigned prev2bits = 0;
 764
 765   /* Find index into log2 scale histogram, where each of the log2
 766      sized buckets is divided into 4 linear sub-buckets for better
 767      focus in the higher buckets.  */
 768
 769   /* Find the place of the most-significant bit set.  */
 770   if (v > 0)
 771     {
 772 #if IN_LIBGCOV
 773       /* When building libgcov we don't include system.h, which includes
 774          hwint.h (where floor_log2 is declared). However, libgcov.a
 775          is built by the bootstrapped compiler and therefore the builtins
 776          are always available.  */
 777       r = sizeof (long long) * __CHAR_BIT__ - 1 - __builtin_clzll (v);
 778 #else
 779       /* We use floor_log2 from hwint.c, which takes a HOST_WIDE_INT
 780          that is 64 bits and gcov_type_unsigned is 64 bits.  */
 781       r = floor_log2 (v);
 782 #endif
 783     }
 784
 785   /* If at most the 2 least significant bits are set (value is
 786      0 - 3) then that value is our index into the lowest set of
 787      four buckets.  */
 788   if (r < 2)
 789     return (unsigned)value;
 790
 791   gcov_nonruntime_assert (r < 64);
 792
 793   /* Find the two next most significant bits to determine which
 794      of the four linear sub-buckets to select.  */
 795   prev2bits = (v >> (r - 2)) & 0x3;
 796   /* Finally, compose the final bucket index from the log2 index and
 797      the next 2 bits. The minimum r value at this point is 2 since we
 798      returned above if r was 2 or more, so the minimum bucket at this
 799      point is 4.  */
 800   return (r - 1) * 4 + prev2bits;
 801 }
 802
 803 /* Merge SRC_HISTO into TGT_HISTO. The counters are assumed to be in
 804    the same relative order in both histograms, and are matched up
 805    and merged in reverse order. Each counter is assigned an equal portion of
 806    its entry's original cumulative counter value when computing the
 807    new merged cum_value.  */
 808
 809 static void gcov_histogram_merge (gcov_bucket_type *tgt_histo,
 810                                   gcov_bucket_type *src_histo)
 811 {
 812   int src_i, tgt_i, tmp_i = 0;
 813   unsigned src_num, tgt_num, merge_num;
 814   gcov_type src_cum, tgt_cum, merge_src_cum, merge_tgt_cum, merge_cum;
 815   gcov_type merge_min;
 816   gcov_bucket_type tmp_histo[GCOV_HISTOGRAM_SIZE];
 817   int src_done = 0;
 818
 819   memset (tmp_histo, 0, sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 820
 821   /* Assume that the counters are in the same relative order in both
 822      histograms. Walk the histograms from largest to smallest entry,
 823      matching up and combining counters in order.  */
 824   src_num = 0;
 825   src_cum = 0;
 826   src_i = GCOV_HISTOGRAM_SIZE - 1;
 827   for (tgt_i = GCOV_HISTOGRAM_SIZE - 1; tgt_i >= 0 && !src_done; tgt_i--)
 828     {
 829       tgt_num = tgt_histo[tgt_i].num_counters;
 830       tgt_cum = tgt_histo[tgt_i].cum_value;
 831       /* Keep going until all of the target histogram's counters at this
 832          position have been matched and merged with counters from the
 833          source histogram.  */
 834       while (tgt_num > 0 && !src_done)
 835         {
 836           /* If this is either the first time through this loop or we just
 837              exhausted the previous non-zero source histogram entry, look
 838              for the next non-zero source histogram entry.  */
 839           if (!src_num)
 840             {
 841               /* Locate the next non-zero entry.  */
 842               while (src_i >= 0 && !src_histo[src_i].num_counters)
 843                 src_i--;
 844               /* If source histogram has fewer counters, then just copy over the
 845                  remaining target counters and quit.  */
 846               if (src_i < 0)
 847                 {
 848                   tmp_histo[tgt_i].num_counters += tgt_num;
 849                   tmp_histo[tgt_i].cum_value += tgt_cum;
 850                   if (!tmp_histo[tgt_i].min_value ||
 851                       tgt_histo[tgt_i].min_value < tmp_histo[tgt_i].min_value)
 852                     tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value;
 853                   while (--tgt_i >= 0)
 854                     {
 855                       tmp_histo[tgt_i].num_counters
 856                           += tgt_histo[tgt_i].num_counters;
 857                       tmp_histo[tgt_i].cum_value += tgt_histo[tgt_i].cum_value;
 858                       if (!tmp_histo[tgt_i].min_value ||
 859                           tgt_histo[tgt_i].min_value
 860                           < tmp_histo[tgt_i].min_value)
 861                         tmp_histo[tgt_i].min_value = tgt_histo[tgt_i].min_value;
 862                     }
 863
 864                   src_done = 1;
 865                   break;
 866                 }
 867
 868               src_num = src_histo[src_i].num_counters;
 869               src_cum = src_histo[src_i].cum_value;
 870             }
 871
 872           /* The number of counters to merge on this pass is the minimum
 873              of the remaining counters from the current target and source
 874              histogram entries.  */
 875           merge_num = tgt_num;
 876           if (src_num < merge_num)
 877             merge_num = src_num;
 878
 879           /* The merged min_value is the sum of the min_values from target
 880              and source.  */
 881           merge_min = tgt_histo[tgt_i].min_value + src_histo[src_i].min_value;
 882
 883           /* Compute the portion of source and target entries' cum_value
 884              that will be apportioned to the counters being merged.
 885              The total remaining cum_value from each entry is divided
 886              equally among the counters from that histogram entry if we
 887              are not merging all of them.  */
 888           merge_src_cum = src_cum;
 889           if (merge_num < src_num)
 890             merge_src_cum = merge_num * src_cum / src_num;
 891           merge_tgt_cum = tgt_cum;
 892           if (merge_num < tgt_num)
 893             merge_tgt_cum = merge_num * tgt_cum / tgt_num;
 894           /* The merged cum_value is the sum of the source and target
 895              components.  */
 896           merge_cum = merge_src_cum + merge_tgt_cum;
 897
 898           /* Update the remaining number of counters and cum_value left
 899              to be merged from this source and target entry.  */
 900           src_cum -= merge_src_cum;
 901           tgt_cum -= merge_tgt_cum;
 902           src_num -= merge_num;
 903           tgt_num -= merge_num;
 904
 905           /* The merged counters get placed in the new merged histogram
 906              at the entry for the merged min_value.  */
 907           tmp_i = gcov_histo_index (merge_min);
 908           gcov_nonruntime_assert (tmp_i < GCOV_HISTOGRAM_SIZE);
 909           tmp_histo[tmp_i].num_counters += merge_num;
 910           tmp_histo[tmp_i].cum_value += merge_cum;
 911           if (!tmp_histo[tmp_i].min_value ||
 912               merge_min < tmp_histo[tmp_i].min_value)
 913             tmp_histo[tmp_i].min_value = merge_min;
 914
 915           /* Ensure the search for the next non-zero src_histo entry starts
 916              at the next smallest histogram bucket.  */
 917           if (!src_num)
 918             src_i--;
 919         }
 920     }
 921
 922   gcov_nonruntime_assert (tgt_i < 0);
 923
 924   /* In the case where there were more counters in the source histogram,
 925      accumulate the remaining unmerged cumulative counter values. Add
 926      those to the smallest non-zero target histogram entry. Otherwise,
 927      the total cumulative counter values in the histogram will be smaller
 928      than the sum_all stored in the summary, which will complicate
 929      computing the working set information from the histogram later on.  */
 930   if (src_num)
 931     src_i--;
 932   while (src_i >= 0)
 933     {
 934       src_cum += src_histo[src_i].cum_value;
 935       src_i--;
 936     }
 937   /* At this point, tmp_i should be the smallest non-zero entry in the
 938      tmp_histo.  */
 939   gcov_nonruntime_assert (tmp_i >= 0 && tmp_i < GCOV_HISTOGRAM_SIZE
 940                           && tmp_histo[tmp_i].num_counters > 0);
 941   tmp_histo[tmp_i].cum_value += src_cum;
 942
 943   /* Finally, copy the merged histogram into tgt_histo.  */
 944   memcpy (tgt_histo, tmp_histo,
 945           sizeof (gcov_bucket_type) * GCOV_HISTOGRAM_SIZE);
 946 }
 947 #endif /* !IN_GCOV */
 948
 949 /* This is used by gcov-dump (IN_GCOV == -1) and in the compiler
 950    (!IN_GCOV && !IN_LIBGCOV).  */
 951 #if IN_GCOV <= 0 && !IN_LIBGCOV
 952 /* Compute the working set information from the counter histogram in
 953    the profile summary. This is an array of information corresponding to a
 954    range of percentages of the total execution count (sum_all), and includes
 955    the number of counters required to cover that working set percentage and
 956    the minimum counter value in that working set.  */
 957
 958 GCOV_LINKAGE void
 959 compute_working_sets (const gcov_summary *summary,
 960                       gcov_working_set_t *gcov_working_sets)
 961 {
 962   gcov_type working_set_cum_values[NUM_GCOV_WORKING_SETS];
 963   gcov_type ws_cum_hotness_incr;
 964   gcov_type cum, tmp_cum;
 965   const gcov_bucket_type *histo_bucket;
 966   unsigned ws_ix, c_num, count;
 967   int h_ix;
 968
 969   /* Compute the amount of sum_all that the cumulative hotness grows
 970      by in each successive working set entry, which depends on the
 971      number of working set entries.  */
 972   ws_cum_hotness_incr = summary->sum_all / NUM_GCOV_WORKING_SETS;
 973
 974   /* Next fill in an array of the cumulative hotness values corresponding
 975      to each working set summary entry we are going to compute below.
 976      Skip 0% statistics, which can be extrapolated from the
 977      rest of the summary data.  */
 978   cum = ws_cum_hotness_incr;
 979   for (ws_ix = 0; ws_ix < NUM_GCOV_WORKING_SETS;
 980        ws_ix++, cum += ws_cum_hotness_incr)
 981     working_set_cum_values[ws_ix] = cum;
 982   /* The last summary entry is reserved for (roughly) 99.9% of the
 983      working set. Divide by 1024 so it becomes a shift, which gives
 984      almost exactly 99.9%.  */
 985   working_set_cum_values[NUM_GCOV_WORKING_SETS-1]
 986       = summary->sum_all - summary->sum_all/1024;
 987
 988   /* Next, walk through the histogram in decending order of hotness
 989      and compute the statistics for the working set summary array.
 990      As histogram entries are accumulated, we check to see which
 991      working set entries have had their expected cum_value reached
 992      and fill them in, walking the working set entries in increasing
 993      size of cum_value.  */
 994   ws_ix = 0; /* The current entry into the working set array.  */
 995   cum = 0; /* The current accumulated counter sum.  */
 996   count = 0; /* The current accumulated count of block counters.  */
 997   for (h_ix = GCOV_HISTOGRAM_SIZE - 1;
 998        h_ix >= 0 && ws_ix < NUM_GCOV_WORKING_SETS; h_ix--)
 999     {
1000       histo_bucket = &summary->histogram[h_ix];
1001
1002       /* If we haven't reached the required cumulative counter value for
1003          the current working set percentage, simply accumulate this histogram
1004          entry into the running sums and continue to the next histogram
1005          entry.  */
1006       if (cum + histo_bucket->cum_value < working_set_cum_values[ws_ix])
1007         {
1008           cum += histo_bucket->cum_value;
1009           count += histo_bucket->num_counters;
1010           continue;
1011         }
1012
1013       /* If adding the current histogram entry's cumulative counter value
1014          causes us to exceed the current working set size, then estimate
1015          how many of this histogram entry's counter values are required to
1016          reach the working set size, and fill in working set entries
1017          as we reach their expected cumulative value.  */
1018       for (c_num = 0, tmp_cum = cum;
1019            c_num < histo_bucket->num_counters && ws_ix < NUM_GCOV_WORKING_SETS;
1020            c_num++)
1021         {
1022           count++;
1023           /* If we haven't reached the last histogram entry counter, add
1024              in the minimum value again. This will underestimate the
1025              cumulative sum so far, because many of the counter values in this
1026              entry may have been larger than the minimum. We could add in the
1027              average value every time, but that would require an expensive
1028              divide operation.  */
1029           if (c_num + 1 < histo_bucket->num_counters)
1030             tmp_cum += histo_bucket->min_value;
1031           /* If we have reached the last histogram entry counter, then add
1032              in the entire cumulative value.  */
1033           else
1034             tmp_cum = cum + histo_bucket->cum_value;
1035
1036           /* Next walk through successive working set entries and fill in
1037              the statistics for any whose size we have reached by accumulating
1038              this histogram counter.  */
1039           while (ws_ix < NUM_GCOV_WORKING_SETS
1040                  && tmp_cum >= working_set_cum_values[ws_ix])
1041             {
1042               gcov_working_sets[ws_ix].num_counters = count;
1043               gcov_working_sets[ws_ix].min_counter
1044                   = histo_bucket->min_value;
1045               ws_ix++;
1046             }
1047         }
1048       /* Finally, update the running cumulative value since we were
1049          using a temporary above.  */
1050       cum += histo_bucket->cum_value;
1051     }
1052   gcov_nonruntime_assert (ws_ix == NUM_GCOV_WORKING_SETS);
1053 }
1054 #endif /* IN_GCOV <= 0 && !IN_LIBGCOV */