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, uint64_t* 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 static bool IsPathSeparator(char c) {
 106 #ifdef _WIN32
 107   return c == '/' || c == '\\';
 108 #else
 109   return c == '/';
 110 #endif
 111 }
 112
 113 bool CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits,
 114                       string* err) {
 115   // WARNING: this function is performance-critical; please benchmark
 116   // any changes you make to it.
 117   METRIC_RECORD("canonicalize path");
 118   if (*len == 0) {
 119     *err = "empty path";
 120     return false;
 121   }
 122
 123   const int kMaxPathComponents = 60;
 124   char* components[kMaxPathComponents];
 125   int component_count = 0;
 126
 127   char* start = path;
 128   char* dst = start;
 129   const char* src = start;
 130   const char* end = start + *len;
 131
 132   if (IsPathSeparator(*src)) {
 133 #ifdef _WIN32
 134
 135     // network path starts with //
 136     if (*len > 1 && IsPathSeparator(*(src + 1))) {
 137       src += 2;
 138       dst += 2;
 139     } else {
 140       ++src;
 141       ++dst;
 142     }
 143 #else
 144     ++src;
 145     ++dst;
 146 #endif
 147   }
 148
 149   while (src < end) {
 150     if (*src == '.') {
 151       if (src + 1 == end || IsPathSeparator(src[1])) {
 152         // '.' component; eliminate.
 153         src += 2;
 154         continue;
 155       } else if (src[1] == '.' && (src + 2 == end || IsPathSeparator(src[2]))) {
 156         // '..' component.  Back up if possible.
 157         if (component_count > 0) {
 158           dst = components[component_count - 1];
 159           src += 3;
 160           --component_count;
 161         } else {
 162           *dst++ = *src++;
 163           *dst++ = *src++;
 164           *dst++ = *src++;
 165         }
 166         continue;
 167       }
 168     }
 169
 170     if (IsPathSeparator(*src)) {
 171       src++;
 172       continue;
 173     }
 174
 175     if (component_count == kMaxPathComponents)
 176       Fatal("path has too many components : %s", path);
 177     components[component_count] = dst;
 178     ++component_count;
 179
 180     while (src != end && !IsPathSeparator(*src))
 181       *dst++ = *src++;
 182     *dst++ = *src++;  // Copy '/' or final \0 character as well.
 183   }
 184
 185   if (dst == start) {
 186     *dst++ = '.';
 187     *dst++ = '\0';
 188   }
 189
 190   *len = dst - start - 1;
 191 #ifdef _WIN32
 192   uint64_t bits = 0;
 193   uint64_t bits_mask = 1;
 194
 195   for (char* c = start; c < start + *len; ++c) {
 196     switch (*c) {
 197       case '\\':
 198         bits |= bits_mask;
 199         *c = '/';
 200         // Intentional fallthrough.
 201       case '/':
 202         bits_mask <<= 1;
 203     }
 204   }
 205
 206   *slash_bits = bits;
 207 #else
 208   *slash_bits = 0;
 209 #endif
 210   return true;
 211 }
 212
 213 static inline bool IsKnownShellSafeCharacter(char ch) {
 214   if ('A' <= ch && ch <= 'Z') return true;
 215   if ('a' <= ch && ch <= 'z') return true;
 216   if ('0' <= ch && ch <= '9') return true;
 217
 218   switch (ch) {
 219     case '_':
 220     case '+':
 221     case '-':
 222     case '.':
 223     case '/':
 224       return true;
 225     default:
 226       return false;
 227   }
 228 }
 229
 230 static inline bool IsKnownWin32SafeCharacter(char ch) {
 231   switch (ch) {
 232     case ' ':
 233     case '"':
 234       return false;
 235     default:
 236       return true;
 237   }
 238 }
 239
 240 static inline bool StringNeedsShellEscaping(const string& input) {
 241   for (size_t i = 0; i < input.size(); ++i) {
 242     if (!IsKnownShellSafeCharacter(input[i])) return true;
 243   }
 244   return false;
 245 }
 246
 247 static inline bool StringNeedsWin32Escaping(const string& input) {
 248   for (size_t i = 0; i < input.size(); ++i) {
 249     if (!IsKnownWin32SafeCharacter(input[i])) return true;
 250   }
 251   return false;
 252 }
 253
 254 void GetShellEscapedString(const string& input, string* result) {
 255   assert(result);
 256
 257   if (!StringNeedsShellEscaping(input)) {
 258     result->append(input);
 259     return;
 260   }
 261
 262   const char kQuote = '\'';
 263   const char kEscapeSequence[] = "'\\'";
 264
 265   result->push_back(kQuote);
 266
 267   string::const_iterator span_begin = input.begin();
 268   for (string::const_iterator it = input.begin(), end = input.end(); it != end;
 269        ++it) {
 270     if (*it == kQuote) {
 271       result->append(span_begin, it);
 272       result->append(kEscapeSequence);
 273       span_begin = it;
 274     }
 275   }
 276   result->append(span_begin, input.end());
 277   result->push_back(kQuote);
 278 }
 279
 280
 281 void GetWin32EscapedString(const string& input, string* result) {
 282   assert(result);
 283   if (!StringNeedsWin32Escaping(input)) {
 284     result->append(input);
 285     return;
 286   }
 287
 288   const char kQuote = '"';
 289   const char kBackslash = '\\';
 290
 291   result->push_back(kQuote);
 292   size_t consecutive_backslash_count = 0;
 293   string::const_iterator span_begin = input.begin();
 294   for (string::const_iterator it = input.begin(), end = input.end(); it != end;
 295        ++it) {
 296     switch (*it) {
 297       case kBackslash:
 298         ++consecutive_backslash_count;
 299         break;
 300       case kQuote:
 301         result->append(span_begin, it);
 302         result->append(consecutive_backslash_count + 1, kBackslash);
 303         span_begin = it;
 304         consecutive_backslash_count = 0;
 305         break;
 306       default:
 307         consecutive_backslash_count = 0;
 308         break;
 309     }
 310   }
 311   result->append(span_begin, input.end());
 312   result->append(consecutive_backslash_count, kBackslash);
 313   result->push_back(kQuote);
 314 }
 315
 316 int ReadFile(const string& path, string* contents, string* err) {
 317 #ifdef _WIN32
 318   // This makes a ninja run on a set of 1500 manifest files about 4% faster
 319   // than using the generic fopen code below.
 320   err->clear();
 321   HANDLE f = ::CreateFile(path.c_str(),
 322                           GENERIC_READ,
 323                           FILE_SHARE_READ,
 324                           NULL,
 325                           OPEN_EXISTING,
 326                           FILE_FLAG_SEQUENTIAL_SCAN,
 327                           NULL);
 328   if (f == INVALID_HANDLE_VALUE) {
 329     err->assign(GetLastErrorString());
 330     return -ENOENT;
 331   }
 332
 333   for (;;) {
 334     DWORD len;
 335     char buf[64 << 10];
 336     if (!::ReadFile(f, buf, sizeof(buf), &len, NULL)) {
 337       err->assign(GetLastErrorString());
 338       contents->clear();
 339       return -1;
 340     }
 341     if (len == 0)
 342       break;
 343     contents->append(buf, len);
 344   }
 345   ::CloseHandle(f);
 346   return 0;
 347 #else
 348   FILE* f = fopen(path.c_str(), "rb");
 349   if (!f) {
 350     err->assign(strerror(errno));
 351     return -errno;
 352   }
 353
 354   char buf[64 << 10];
 355   size_t len;
 356   while ((len = fread(buf, 1, sizeof(buf), f)) > 0) {
 357     contents->append(buf, len);
 358   }
 359   if (ferror(f)) {
 360     err->assign(strerror(errno));  // XXX errno?
 361     contents->clear();
 362     fclose(f);
 363     return -errno;
 364   }
 365   fclose(f);
 366   return 0;
 367 #endif
 368 }
 369
 370 void SetCloseOnExec(int fd) {
 371 #ifndef _WIN32
 372   int flags = fcntl(fd, F_GETFD);
 373   if (flags < 0) {
 374     perror("fcntl(F_GETFD)");
 375   } else {
 376     if (fcntl(fd, F_SETFD, flags | FD_CLOEXEC) < 0)
 377       perror("fcntl(F_SETFD)");
 378   }
 379 #else
 380   HANDLE hd = (HANDLE) _get_osfhandle(fd);
 381   if (! SetHandleInformation(hd, HANDLE_FLAG_INHERIT, 0)) {
 382     fprintf(stderr, "SetHandleInformation(): %s", GetLastErrorString().c_str());
 383   }
 384 #endif  // ! _WIN32
 385 }
 386
 387
 388 const char* SpellcheckStringV(const string& text,
 389                               const vector<const char*>& words) {
 390   const bool kAllowReplacements = true;
 391   const int kMaxValidEditDistance = 3;
 392
 393   int min_distance = kMaxValidEditDistance + 1;
 394   const char* result = NULL;
 395   for (vector<const char*>::const_iterator i = words.begin();
 396        i != words.end(); ++i) {
 397     int distance = EditDistance(*i, text, kAllowReplacements,
 398                                 kMaxValidEditDistance);
 399     if (distance < min_distance) {
 400       min_distance = distance;
 401       result = *i;
 402     }
 403   }
 404   return result;
 405 }
 406
 407 const char* SpellcheckString(const char* text, ...) {
 408   // Note: This takes a const char* instead of a string& because using
 409   // va_start() with a reference parameter is undefined behavior.
 410   va_list ap;
 411   va_start(ap, text);
 412   vector<const char*> words;
 413   const char* word;
 414   while ((word = va_arg(ap, const char*)))
 415     words.push_back(word);
 416   va_end(ap);
 417   return SpellcheckStringV(text, words);
 418 }
 419
 420 #ifdef _WIN32
 421 string GetLastErrorString() {
 422   DWORD err = GetLastError();
 423
 424   char* msg_buf;
 425   FormatMessageA(
 426         FORMAT_MESSAGE_ALLOCATE_BUFFER |
 427         FORMAT_MESSAGE_FROM_SYSTEM |
 428         FORMAT_MESSAGE_IGNORE_INSERTS,
 429         NULL,
 430         err,
 431         MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),
 432         (char*)&msg_buf,
 433         0,
 434         NULL);
 435   string msg = msg_buf;
 436   LocalFree(msg_buf);
 437   return msg;
 438 }
 439
 440 void Win32Fatal(const char* function) {
 441   Fatal("%s: %s", function, GetLastErrorString().c_str());
 442 }
 443 #endif
 444
 445 bool islatinalpha(int c) {
 446   // isalpha() is locale-dependent.
 447   return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
 448 }
 449
 450 string StripAnsiEscapeCodes(const string& in) {
 451   string stripped;
 452   stripped.reserve(in.size());
 453
 454   for (size_t i = 0; i < in.size(); ++i) {
 455     if (in[i] != '\33') {
 456       // Not an escape code.
 457       stripped.push_back(in[i]);
 458       continue;
 459     }
 460
 461     // Only strip CSIs for now.
 462     if (i + 1 >= in.size()) break;
 463     if (in[i + 1] != '[') continue;  // Not a CSI.
 464     i += 2;
 465
 466     // Skip everything up to and including the next [a-zA-Z].
 467     while (i < in.size() && !islatinalpha(in[i]))
 468       ++i;
 469   }
 470   return stripped;
 471 }
 472
 473 int GetProcessorCount() {
 474 #ifdef _WIN32
 475   SYSTEM_INFO info;
 476   GetNativeSystemInfo(&info);
 477   return info.dwNumberOfProcessors;
 478 #else
 479   return sysconf(_SC_NPROCESSORS_ONLN);
 480 #endif
 481 }
 482
 483 #if defined(_WIN32) || defined(__CYGWIN__)
 484 static double CalculateProcessorLoad(uint64_t idle_ticks, uint64_t total_ticks)
 485 {
 486   static uint64_t previous_idle_ticks = 0;
 487   static uint64_t previous_total_ticks = 0;
 488   static double previous_load = -0.0;
 489
 490   uint64_t idle_ticks_since_last_time = idle_ticks - previous_idle_ticks;
 491   uint64_t total_ticks_since_last_time = total_ticks - previous_total_ticks;
 492
 493   bool first_call = (previous_total_ticks == 0);
 494   bool ticks_not_updated_since_last_call = (total_ticks_since_last_time == 0);
 495
 496   double load;
 497   if (first_call || ticks_not_updated_since_last_call) {
 498     load = previous_load;
 499   } else {
 500     // Calculate load.
 501     double idle_to_total_ratio =
 502         ((double)idle_ticks_since_last_time) / total_ticks_since_last_time;
 503     double load_since_last_call = 1.0 - idle_to_total_ratio;
 504
 505     // Filter/smooth result when possible.
 506     if(previous_load > 0) {
 507       load = 0.9 * previous_load + 0.1 * load_since_last_call;
 508     } else {
 509       load = load_since_last_call;
 510     }
 511   }
 512
 513   previous_load = load;
 514   previous_total_ticks = total_ticks;
 515   previous_idle_ticks = idle_ticks;
 516
 517   return load;
 518 }
 519
 520 static uint64_t FileTimeToTickCount(const FILETIME & ft)
 521 {
 522   uint64_t high = (((uint64_t)(ft.dwHighDateTime)) << 32);
 523   uint64_t low  = ft.dwLowDateTime;
 524   return (high | low);
 525 }
 526
 527 double GetLoadAverage() {
 528   FILETIME idle_time, kernel_time, user_time;
 529   BOOL get_system_time_succeeded =
 530       GetSystemTimes(&idle_time, &kernel_time, &user_time);
 531
 532   double posix_compatible_load;
 533   if (get_system_time_succeeded) {
 534     uint64_t idle_ticks = FileTimeToTickCount(idle_time);
 535
 536     // kernel_time from GetSystemTimes already includes idle_time.
 537     uint64_t total_ticks =
 538         FileTimeToTickCount(kernel_time) + FileTimeToTickCount(user_time);
 539
 540     double processor_load = CalculateProcessorLoad(idle_ticks, total_ticks);
 541     posix_compatible_load = processor_load * GetProcessorCount();
 542
 543   } else {
 544     posix_compatible_load = -0.0;
 545   }
 546
 547   return posix_compatible_load;
 548 }
 549 #elif defined(_AIX)
 550 double GetLoadAverage() {
 551   perfstat_cpu_total_t cpu_stats;
 552   if (perfstat_cpu_total(NULL, &cpu_stats, sizeof(cpu_stats), 1) < 0) {
 553     return -0.0f;
 554   }
 555
 556   // Calculation taken from comment in libperfstats.h
 557   return double(cpu_stats.loadavg[0]) / double(1 << SBITS);
 558 }
 559 #elif defined(__UCLIBC__)
 560 double GetLoadAverage() {
 561   struct sysinfo si;
 562   if (sysinfo(&si) != 0)
 563     return -0.0f;
 564   return 1.0 / (1 << SI_LOAD_SHIFT) * si.loads[0];
 565 }
 566 #else
 567 double GetLoadAverage() {
 568   double loadavg[3] = { 0.0f, 0.0f, 0.0f };
 569   if (getloadavg(loadavg, 3) < 0) {
 570     // Maybe we should return an error here or the availability of
 571     // getloadavg(3) should be checked when ninja is configured.
 572     return -0.0f;
 573   }
 574   return loadavg[0];
 575 }
 576 #endif // _WIN32
 577
 578 string ElideMiddle(const string& str, size_t width) {
 579   const int kMargin = 3;  // Space for "...".
 580   string result = str;
 581   if (result.size() + kMargin > width) {
 582     size_t elide_size = (width - kMargin) / 2;
 583     result = result.substr(0, elide_size)
 584       + "..."
 585       + result.substr(result.size() - elide_size, elide_size);
 586   }
 587   return result;
 588 }
 589
 590 bool Truncate(const string& path, size_t size, string* err) {
 591 #ifdef _WIN32
 592   int fh = _sopen(path.c_str(), _O_RDWR | _O_CREAT, _SH_DENYNO,
 593                   _S_IREAD | _S_IWRITE);
 594   int success = _chsize(fh, size);
 595   _close(fh);
 596 #else
 597   int success = truncate(path.c_str(), size);
 598 #endif
 599   // Both truncate() and _chsize() return 0 on success and set errno and return
 600   // -1 on failure.
 601   if (success < 0) {
 602     *err = strerror(errno);
 603     return false;
 604   }
 605   return true;
 606 }