src/util.cc

   1 // Copyright 2011 Google Inc. All Rights Reserved.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 #include "util.h"
  16
  17 #ifdef __CYGWIN__
  18 #include <windows.h>
  19 #include <io.h>
  20 #elif defined( _WIN32)
  21 #include <windows.h>
  22 #include <io.h>
  23 #include <share.h>
  24 #endif
  25
  26 #include <assert.h>
  27 #include <errno.h>
  28 #include <fcntl.h>
  29 #include <stdarg.h>
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33 #include <sys/stat.h>
  34 #include <sys/types.h>
  35
  36 #ifndef _WIN32
  37 #include <unistd.h>
  38 #include <sys/time.h>
  39 #endif
  40
  41 #include <vector>
  42
  43 #if defined(__APPLE__) || defined(__FreeBSD__)
  44 #include <sys/sysctl.h>
  45 #elif defined(__SVR4) && defined(__sun)
  46 #include <unistd.h>
  47 #include <sys/loadavg.h>
  48 #elif defined(_AIX)
  49 #include <libperfstat.h>
  50 #elif defined(linux) || defined(__GLIBC__)
  51 #include <sys/sysinfo.h>
  52 #endif
  53
  54 #include "edit_distance.h"
  55 #include "metrics.h"
  56
  57 void Fatal(const char* msg, ...) {
  58   va_list ap;
  59   fprintf(stderr, "ninja: fatal: ");
  60   va_start(ap, msg);
  61   vfprintf(stderr, msg, ap);
  62   va_end(ap);
  63   fprintf(stderr, "\n");
  64 #ifdef _WIN32
  65   // On Windows, some tools may inject extra threads.
  66   // exit() may block on locks held by those threads, so forcibly exit.
  67   fflush(stderr);
  68   fflush(stdout);
  69   ExitProcess(1);
  70 #else
  71   exit(1);
  72 #endif
  73 }
  74
  75 void Warning(const char* msg, ...) {
  76   va_list ap;
  77   fprintf(stderr, "ninja: warning: ");
  78   va_start(ap, msg);
  79   vfprintf(stderr, msg, ap);
  80   va_end(ap);
  81   fprintf(stderr, "\n");
  82 }
  83
  84 void Error(const char* msg, ...) {
  85   va_list ap;
  86   fprintf(stderr, "ninja: error: ");
  87   va_start(ap, msg);
  88   vfprintf(stderr, msg, ap);
  89   va_end(ap);
  90   fprintf(stderr, "\n");
  91 }
  92
  93 bool CanonicalizePath(string* path, unsigned int* slash_bits, string* err) {
  94   METRIC_RECORD("canonicalize str");
  95   size_t len = path->size();
  96   char* str = 0;
  97   if (len > 0)
  98     str = &(*path)[0];
  99   if (!CanonicalizePath(str, &len, slash_bits, err))
 100     return false;
 101   path->resize(len);
 102   return true;
 103 }
 104
 105 #ifdef _WIN32
 106 static unsigned int ShiftOverBit(int offset, unsigned int bits) {
 107   // e.g. for |offset| == 2:
 108   // | ... 9 8 7 6 5 4 3 2 1 0 |
 109   // \_________________/   \_/
 110   //        above         below
 111   // So we drop the bit at offset and move above "down" into its place.
 112   unsigned int above = bits & ~((1 << (offset + 1)) - 1);
 113   unsigned int below = bits & ((1 << offset) - 1);
 114   return (above >> 1) | below;
 115 }
 116 #endif
 117
 118 bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits,
 119                       string* err) {
 120   // WARNING: this function is performance-critical; please benchmark
 121   // any changes you make to it.
 122   METRIC_RECORD("canonicalize path");
 123   if (*len == 0) {
 124     *err = "empty path";
 125     return false;
 126   }
 127
 128   const int kMaxPathComponents = 30;
 129   char* components[kMaxPathComponents];
 130   int component_count = 0;
 131
 132   char* start = path;
 133   char* dst = start;
 134   const char* src = start;
 135   const char* end = start + *len;
 136
 137 #ifdef _WIN32
 138   unsigned int bits = 0;
 139   unsigned int bits_mask = 1;
 140   int bits_offset = 0;
 141   // Convert \ to /, setting a bit in |bits| for each \ encountered.
 142   for (char* c = path; c < end; ++c) {
 143     switch (*c) {
 144       case '\\':
 145         bits |= bits_mask;
 146         *c = '/';
 147         // Intentional fallthrough.
 148       case '/':
 149         bits_mask <<= 1;
 150         bits_offset++;
 151     }
 152   }
 153   if (bits_offset > 32) {
 154     *err = "too many path components";
 155     return false;
 156   }
 157   bits_offset = 0;
 158 #endif
 159
 160   if (*src == '/') {
 161 #ifdef _WIN32
 162     bits_offset++;
 163     // network path starts with //
 164     if (*len > 1 && *(src + 1) == '/') {
 165       src += 2;
 166       dst += 2;
 167       bits_offset++;
 168     } else {
 169       ++src;
 170       ++dst;
 171     }
 172 #else
 173     ++src;
 174     ++dst;
 175 #endif
 176   }
 177
 178   while (src < end) {
 179     if (*src == '.') {
 180       if (src + 1 == end || src[1] == '/') {
 181         // '.' component; eliminate.
 182         src += 2;
 183 #ifdef _WIN32
 184         bits = ShiftOverBit(bits_offset, bits);
 185 #endif
 186         continue;
 187       } else if (src[1] == '.' && (src + 2 == end || src[2] == '/')) {
 188         // '..' component.  Back up if possible.
 189         if (component_count > 0) {
 190           dst = components[component_count - 1];
 191           src += 3;
 192           --component_count;
 193 #ifdef _WIN32
 194           bits = ShiftOverBit(bits_offset, bits);
 195           bits_offset--;
 196           bits = ShiftOverBit(bits_offset, bits);
 197 #endif
 198         } else {
 199           *dst++ = *src++;
 200           *dst++ = *src++;
 201           *dst++ = *src++;
 202         }
 203         continue;
 204       }
 205     }
 206
 207     if (*src == '/') {
 208       src++;
 209 #ifdef _WIN32
 210       bits = ShiftOverBit(bits_offset, bits);
 211 #endif
 212       continue;
 213     }
 214
 215     if (component_count == kMaxPathComponents)
 216       Fatal("path has too many components : %s", path);
 217     components[component_count] = dst;
 218     ++component_count;
 219
 220     while (*src != '/' && src != end)
 221       *dst++ = *src++;
 222 #ifdef _WIN32
 223     bits_offset++;
 224 #endif
 225     *dst++ = *src++;  // Copy '/' or final \0 character as well.
 226   }
 227
 228   if (dst == start) {
 229     *dst++ = '.';
 230     *dst++ = '\0';
 231   }
 232
 233   *len = dst - start - 1;
 234 #ifdef _WIN32
 235   *slash_bits = bits;
 236 #else
 237   *slash_bits = 0;
 238 #endif
 239   return true;
 240 }
 241
 242 static inline bool IsKnownShellSafeCharacter(char ch) {
 243   if ('A' <= ch && ch <= 'Z') return true;
 244   if ('a' <= ch && ch <= 'z') return true;
 245   if ('0' <= ch && ch <= '9') return true;
 246
 247   switch (ch) {
 248     case '_':
 249     case '+':
 250     case '-':
 251     case '.':
 252     case '/':
 253       return true;
 254     default:
 255       return false;
 256   }
 257 }
 258
 259 static inline bool IsKnownWin32SafeCharacter(char ch) {
 260   switch (ch) {
 261     case ' ':
 262     case '"':
 263       return false;
 264     default:
 265       return true;
 266   }
 267 }
 268
 269 static inline bool StringNeedsShellEscaping(const string& input) {
 270   for (size_t i = 0; i < input.size(); ++i) {
 271     if (!IsKnownShellSafeCharacter(input[i])) return true;
 272   }
 273   return false;
 274 }
 275
 276 static inline bool StringNeedsWin32Escaping(const string& input) {
 277   for (size_t i = 0; i < input.size(); ++i) {
 278     if (!IsKnownWin32SafeCharacter(input[i])) return true;
 279   }
 280   return false;
 281 }
 282
 283 void GetShellEscapedString(const string& input, string* result) {
 284   assert(result);
 285
 286   if (!StringNeedsShellEscaping(input)) {
 287     result->append(input);
 288     return;
 289   }
 290
 291   const char kQuote = '\'';
 292   const char kEscapeSequence[] = "'\\'";
 293
 294   result->push_back(kQuote);
 295
 296   string::const_iterator span_begin = input.begin();
 297   for (string::const_iterator it = input.begin(), end = input.end(); it != end;
 298        ++it) {
 299     if (*it == kQuote) {
 300       result->append(span_begin, it);
 301       result->append(kEscapeSequence);
 302       span_begin = it;
 303     }
 304   }
 305   result->append(span_begin, input.end());
 306   result->push_back(kQuote);
 307 }
 308
 309
 310 void GetWin32EscapedString(const string& input, string* result) {
 311   assert(result);
 312   if (!StringNeedsWin32Escaping(input)) {
 313     result->append(input);
 314     return;
 315   }
 316
 317   const char kQuote = '"';
 318   const char kBackslash = '\\';
 319
 320   result->push_back(kQuote);
 321   size_t consecutive_backslash_count = 0;
 322   string::const_iterator span_begin = input.begin();
 323   for (string::const_iterator it = input.begin(), end = input.end(); it != end;
 324        ++it) {
 325     switch (*it) {
 326       case kBackslash:
 327         ++consecutive_backslash_count;
 328         break;
 329       case kQuote:
 330         result->append(span_begin, it);
 331         result->append(consecutive_backslash_count + 1, kBackslash);
 332         span_begin = it;
 333         consecutive_backslash_count = 0;
 334         break;
 335       default:
 336         consecutive_backslash_count = 0;
 337         break;
 338     }
 339   }
 340   result->append(span_begin, input.end());
 341   result->append(consecutive_backslash_count, kBackslash);
 342   result->push_back(kQuote);
 343 }
 344
 345 int ReadFile(const string& path, string* contents, string* err) {
 346 #ifdef _WIN32
 347   // This makes a ninja run on a set of 1500 manifest files about 4% faster
 348   // than using the generic fopen code below.
 349   err->clear();
 350   HANDLE f = ::CreateFile(path.c_str(),
 351                           GENERIC_READ,
 352                           FILE_SHARE_READ,
 353                           NULL,
 354                           OPEN_EXISTING,
 355                           FILE_FLAG_SEQUENTIAL_SCAN,
 356                           NULL);
 357   if (f == INVALID_HANDLE_VALUE) {
 358     err->assign(GetLastErrorString());
 359     return -ENOENT;
 360   }
 361
 362   for (;;) {
 363     DWORD len;
 364     char buf[64 << 10];
 365     if (!::ReadFile(f, buf, sizeof(buf), &len, NULL)) {
 366       err->assign(GetLastErrorString());
 367       contents->clear();
 368       return -1;
 369     }
 370     if (len == 0)
 371       break;
 372     contents->append(buf, len);
 373   }
 374   ::CloseHandle(f);
 375   return 0;
 376 #else
 377   FILE* f = fopen(path.c_str(), "rb");
 378   if (!f) {
 379     err->assign(strerror(errno));
 380     return -errno;
 381   }
 382
 383   char buf[64 << 10];
 384   size_t len;
 385   while ((len = fread(buf, 1, sizeof(buf), f)) > 0) {
 386     contents->append(buf, len);
 387   }
 388   if (ferror(f)) {
 389     err->assign(strerror(errno));  // XXX errno?
 390     contents->clear();
 391     fclose(f);
 392     return -errno;
 393   }
 394   fclose(f);
 395   return 0;
 396 #endif
 397 }
 398
 399 void SetCloseOnExec(int fd) {
 400 #ifndef _WIN32
 401   int flags = fcntl(fd, F_GETFD);
 402   if (flags < 0) {
 403     perror("fcntl(F_GETFD)");
 404   } else {
 405     if (fcntl(fd, F_SETFD, flags | FD_CLOEXEC) < 0)
 406       perror("fcntl(F_SETFD)");
 407   }
 408 #else
 409   HANDLE hd = (HANDLE) _get_osfhandle(fd);
 410   if (! SetHandleInformation(hd, HANDLE_FLAG_INHERIT, 0)) {
 411     fprintf(stderr, "SetHandleInformation(): %s", GetLastErrorString().c_str());
 412   }
 413 #endif  // ! _WIN32
 414 }
 415
 416
 417 const char* SpellcheckStringV(const string& text,
 418                               const vector<const char*>& words) {
 419   const bool kAllowReplacements = true;
 420   const int kMaxValidEditDistance = 3;
 421
 422   int min_distance = kMaxValidEditDistance + 1;
 423   const char* result = NULL;
 424   for (vector<const char*>::const_iterator i = words.begin();
 425        i != words.end(); ++i) {
 426     int distance = EditDistance(*i, text, kAllowReplacements,
 427                                 kMaxValidEditDistance);
 428     if (distance < min_distance) {
 429       min_distance = distance;
 430       result = *i;
 431     }
 432   }
 433   return result;
 434 }
 435
 436 const char* SpellcheckString(const char* text, ...) {
 437   // Note: This takes a const char* instead of a string& because using
 438   // va_start() with a reference parameter is undefined behavior.
 439   va_list ap;
 440   va_start(ap, text);
 441   vector<const char*> words;
 442   const char* word;
 443   while ((word = va_arg(ap, const char*)))
 444     words.push_back(word);
 445   va_end(ap);
 446   return SpellcheckStringV(text, words);
 447 }
 448
 449 #ifdef _WIN32
 450 string GetLastErrorString() {
 451   DWORD err = GetLastError();
 452
 453   char* msg_buf;
 454   FormatMessageA(
 455         FORMAT_MESSAGE_ALLOCATE_BUFFER |
 456         FORMAT_MESSAGE_FROM_SYSTEM |
 457         FORMAT_MESSAGE_IGNORE_INSERTS,
 458         NULL,
 459         err,
 460         MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),
 461         (char*)&msg_buf,
 462         0,
 463         NULL);
 464   string msg = msg_buf;
 465   LocalFree(msg_buf);
 466   return msg;
 467 }
 468
 469 void Win32Fatal(const char* function) {
 470   Fatal("%s: %s", function, GetLastErrorString().c_str());
 471 }
 472 #endif
 473
 474 static bool islatinalpha(int c) {
 475   // isalpha() is locale-dependent.
 476   return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
 477 }
 478
 479 string StripAnsiEscapeCodes(const string& in) {
 480   string stripped;
 481   stripped.reserve(in.size());
 482
 483   for (size_t i = 0; i < in.size(); ++i) {
 484     if (in[i] != '\33') {
 485       // Not an escape code.
 486       stripped.push_back(in[i]);
 487       continue;
 488     }
 489
 490     // Only strip CSIs for now.
 491     if (i + 1 >= in.size()) break;
 492     if (in[i + 1] != '[') continue;  // Not a CSI.
 493     i += 2;
 494
 495     // Skip everything up to and including the next [a-zA-Z].
 496     while (i < in.size() && !islatinalpha(in[i]))
 497       ++i;
 498   }
 499   return stripped;
 500 }
 501
 502 int GetProcessorCount() {
 503 #ifdef _WIN32
 504   SYSTEM_INFO info;
 505   GetNativeSystemInfo(&info);
 506   return info.dwNumberOfProcessors;
 507 #else
 508   return sysconf(_SC_NPROCESSORS_ONLN);
 509 #endif
 510 }
 511
 512 #if defined(_WIN32) || defined(__CYGWIN__)
 513 static double CalculateProcessorLoad(uint64_t idle_ticks, uint64_t total_ticks)
 514 {
 515   static uint64_t previous_idle_ticks = 0;
 516   static uint64_t previous_total_ticks = 0;
 517   static double previous_load = -0.0;
 518
 519   uint64_t idle_ticks_since_last_time = idle_ticks - previous_idle_ticks;
 520   uint64_t total_ticks_since_last_time = total_ticks - previous_total_ticks;
 521
 522   bool first_call = (previous_total_ticks == 0);
 523   bool ticks_not_updated_since_last_call = (total_ticks_since_last_time == 0);
 524
 525   double load;
 526   if (first_call || ticks_not_updated_since_last_call) {
 527     load = previous_load;
 528   } else {
 529     // Calculate load.
 530     double idle_to_total_ratio =
 531         ((double)idle_ticks_since_last_time) / total_ticks_since_last_time;
 532     double load_since_last_call = 1.0 - idle_to_total_ratio;
 533
 534     // Filter/smooth result when possible.
 535     if(previous_load > 0) {
 536       load = 0.9 * previous_load + 0.1 * load_since_last_call;
 537     } else {
 538       load = load_since_last_call;
 539     }
 540   }
 541
 542   previous_load = load;
 543   previous_total_ticks = total_ticks;
 544   previous_idle_ticks = idle_ticks;
 545
 546   return load;
 547 }
 548
 549 static uint64_t FileTimeToTickCount(const FILETIME & ft)
 550 {
 551   uint64_t high = (((uint64_t)(ft.dwHighDateTime)) << 32);
 552   uint64_t low  = ft.dwLowDateTime;
 553   return (high | low);
 554 }
 555
 556 double GetLoadAverage() {
 557   FILETIME idle_time, kernel_time, user_time;
 558   BOOL get_system_time_succeeded =
 559       GetSystemTimes(&idle_time, &kernel_time, &user_time);
 560
 561   double posix_compatible_load;
 562   if (get_system_time_succeeded) {
 563     uint64_t idle_ticks = FileTimeToTickCount(idle_time);
 564
 565     // kernel_time from GetSystemTimes already includes idle_time.
 566     uint64_t total_ticks =
 567         FileTimeToTickCount(kernel_time) + FileTimeToTickCount(user_time);
 568
 569     double processor_load = CalculateProcessorLoad(idle_ticks, total_ticks);
 570     posix_compatible_load = processor_load * GetProcessorCount();
 571
 572   } else {
 573     posix_compatible_load = -0.0;
 574   }
 575
 576   return posix_compatible_load;
 577 }
 578 #elif defined(_AIX)
 579 double GetLoadAverage() {
 580   perfstat_cpu_total_t cpu_stats;
 581   if (perfstat_cpu_total(NULL, &cpu_stats, sizeof(cpu_stats), 1) < 0) {
 582     return -0.0f;
 583   }
 584
 585   // Calculation taken from comment in libperfstats.h
 586   return double(cpu_stats.loadavg[0]) / double(1 << SBITS);
 587 }
 588 #else
 589 double GetLoadAverage() {
 590   double loadavg[3] = { 0.0f, 0.0f, 0.0f };
 591   if (getloadavg(loadavg, 3) < 0) {
 592     // Maybe we should return an error here or the availability of
 593     // getloadavg(3) should be checked when ninja is configured.
 594     return -0.0f;
 595   }
 596   return loadavg[0];
 597 }
 598 #endif // _WIN32
 599
 600 string ElideMiddle(const string& str, size_t width) {
 601   const int kMargin = 3;  // Space for "...".
 602   string result = str;
 603   if (result.size() + kMargin > width) {
 604     size_t elide_size = (width - kMargin) / 2;
 605     result = result.substr(0, elide_size)
 606       + "..."
 607       + result.substr(result.size() - elide_size, elide_size);
 608   }
 609   return result;
 610 }
 611
 612 bool Truncate(const string& path, size_t size, string* err) {
 613 #ifdef _WIN32
 614   int fh = _sopen(path.c_str(), _O_RDWR | _O_CREAT, _SH_DENYNO,
 615                   _S_IREAD | _S_IWRITE);
 616   int success = _chsize(fh, size);
 617   _close(fh);
 618 #else
 619   int success = truncate(path.c_str(), size);
 620 #endif
 621   // Both truncate() and _chsize() return 0 on success and set errno and return
 622   // -1 on failure.
 623   if (success < 0) {
 624     *err = strerror(errno);
 625     return false;
 626   }
 627   return true;
 628 }