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) && !defined(__PASE__)
49 #include <libperfstat.h>
50 #elif defined(linux) || defined(__GLIBC__)
51 #include <sys/sysinfo.h>
52 #include <fstream>
53 #include <map>
54 #include "string_piece_util.h"
55 #endif
56 
57 #if defined(__FreeBSD__)
58 #include <sys/cpuset.h>
59 #endif
60 
61 #include "edit_distance.h"
62 
63 using namespace std;
64 
Fatal(const char* msg, ...)65 void Fatal(const char* msg, ...) {
66     va_list ap;
67     fprintf(stderr, "ninja: fatal: ");
68     va_start(ap, msg);
69     vfprintf(stderr, msg, ap);
70     va_end(ap);
71     fprintf(stderr, "\n");
72 #ifdef _WIN32
73     // On Windows, some tools may inject extra threads.
74     // exit() may block on locks held by those threads, so forcibly exit.
75     fflush(stderr);
76     fflush(stdout);
77     ExitProcess(1);
78 #else
79     exit(1);
80 #endif
81 }
82 
Warning(const char* msg, va_list ap)83 void Warning(const char* msg, va_list ap) {
84     fprintf(stderr, "ninja: warning: ");
85     vfprintf(stderr, msg, ap);
86     fprintf(stderr, "\n");
87 }
88 
Warning(const char* msg, ...)89 void Warning(const char* msg, ...) {
90     va_list ap;
91     va_start(ap, msg);
92     Warning(msg, ap);
93     va_end(ap);
94 }
95 
Error(const char* msg, va_list ap)96 void Error(const char* msg, va_list ap) {
97     fprintf(stderr, "ninja: error: ");
98     vfprintf(stderr, msg, ap);
99     fprintf(stderr, "\n");
100 }
101 
Error(const char* msg, ...)102 void Error(const char* msg, ...) {
103     va_list ap;
104     va_start(ap, msg);
105     Error(msg, ap);
106     va_end(ap);
107 }
108 
Info(const char* msg, va_list ap)109 void Info(const char* msg, va_list ap) {
110     fprintf(stdout, "ninja: ");
111     vfprintf(stdout, msg, ap);
112     fprintf(stdout, "\n");
113 }
114 
Info(const char* msg, ...)115 void Info(const char* msg, ...) {
116     va_list ap;
117     va_start(ap, msg);
118     Info(msg, ap);
119     va_end(ap);
120 }
121 
CanonicalizePath(string* path, uint64_t* slash_bits)122 void CanonicalizePath(string* path, uint64_t* slash_bits) {
123     size_t len = path->size();
124     char* str = 0;
125     if (len > 0)
126         str = &(*path)[0];
127     CanonicalizePath(str, &len, slash_bits);
128     path->resize(len);
129 }
130 
IsPathSeparator(char c)131 static bool IsPathSeparator(char c) {
132 #ifdef _WIN32
133     return c == '/' || c == '\\';
134 #else
135     return c == '/';
136 #endif
137 }
138 
CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits)139 void CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits) {
140     // WARNING: this function is performance-critical; please benchmark
141     // any changes you make to it.
142     if (*len == 0) {
143         return;
144     }
145 
146     char* start = path;
147     char* dst = start;
148     char* dst_start = dst;
149     const char* src = start;
150     const char* end = start + *len;
151     const char* src_next;
152 
153     // For absolute paths, skip the leading directory separator
154     // as this one should never be removed from the result.
155     if (IsPathSeparator(*src)) {
156 #ifdef _WIN32
157         // Windows network path starts with //
158         if (src + 2 <= end && IsPathSeparator(src[1])) {
159             src += 2;
160             dst += 2;
161         } else {
162             ++src;
163             ++dst;
164         }
165 #else
166         ++src;
167         ++dst;
168 #endif
169         dst_start = dst;
170     } else {
171         // For relative paths, skip any leading ../ as these are quite common
172         // to reference source files in build plans, and doing this here makes
173         // the loop work below faster in general.
174         while (src + 3 <= end && src[0] == '.' && src[1] == '.' &&
175                       IsPathSeparator(src[2])) {
176             src += 3;
177             dst += 3;
178         }
179     }
180 
181     // Loop over all components of the paths _except_ the last one, in
182     // order to simplify the loop's code and make it faster.
183     int component_count = 0;
184     char* dst0 = dst;
185     for (; src < end; src = src_next) {
186 #ifndef _WIN32
187         // Use memchr() for faster lookups thanks to optimized C library
188         // implementation. `hyperfine canon_perftest` shows a significant
189         // difference (e,g, 484ms vs 437ms).
190         const char* next_sep =
191                 static_cast<const char*>(::memchr(src, '/', end - src));
192         if (!next_sep) {
193             // This is the last component, will be handled out of the loop.
194             break;
195         }
196 #else
197         // Need to check for both '/' and '\\' so do not use memchr().
198         // Cannot use strpbrk() because end[0] can be \0 or something else!
199         const char* next_sep = src;
200         while (next_sep != end && !IsPathSeparator(*next_sep))
201             ++next_sep;
202         if (next_sep == end) {
203             // This is the last component, will be handled out of the loop.
204             break;
205         }
206 #endif
207         // Position for next loop iteration.
208         src_next = next_sep + 1;
209         // Length of the component, excluding trailing directory.
210         size_t component_len = next_sep - src;
211 
212         if (component_len <= 2) {
213             if (component_len == 0) {
214                 continue;  // Ignore empty component, e.g. 'foo//bar' -> 'foo/bar'.
215             }
216             if (src[0] == '.') {
217                 if (component_len == 1) {
218                     continue;  // Ignore '.' component, e.g. './foo' -> 'foo'.
219                 } else if (src[1] == '.') {
220                     // Process the '..' component if found. Back up if possible.
221                     if (component_count > 0) {
222                         // Move back to start of previous component.
223                         --component_count;
224                         while (--dst > dst0 && !IsPathSeparator(dst[-1])) {
225                             // nothing to do here, decrement happens before condition check.
226                         }
227                     } else {
228                         dst[0] = '.';
229                         dst[1] = '.';
230                         dst[2] = src[2];
231                         dst += 3;
232                     }
233                     continue;
234                 }
235             }
236         }
237         ++component_count;
238 
239         // Copy or skip component, including trailing directory separator.
240         if (dst != src) {
241             ::memmove(dst, src, src_next - src);
242         }
243         dst += src_next - src;
244     }
245 
246     // Handling the last component that does not have a trailing separator.
247     // The logic here is _slightly_ different since there is no trailing
248     // directory separator.
249     size_t component_len = end - src;
250     do {
251         if (component_len == 0)
252             break;  // Ignore empty component (e.g. 'foo//' -> 'foo/')
253         if (src[0] == '.') {
254             if (component_len == 1)
255                 break;  // Ignore trailing '.' (e.g. 'foo/.' -> 'foo/')
256             if (component_len == 2 && src[1] == '.') {
257                 // Handle '..'. Back up if possible.
258                 if (component_count > 0) {
259                     while (--dst > dst0 && !IsPathSeparator(dst[-1])) {
260                         // nothing to do here, decrement happens before condition check.
261                     }
262                 } else {
263                     dst[0] = '.';
264                     dst[1] = '.';
265                     dst += 2;
266                     // No separator to add here.
267                 }
268                 break;
269             }
270         }
271         // Skip or copy last component, no trailing separator.
272         if (dst != src) {
273             ::memmove(dst, src, component_len);
274         }
275         dst += component_len;
276     } while (0);
277 
278     // Remove trailing path separator if any, but keep the initial
279     // path separator(s) if there was one (or two on Windows).
280     if (dst > dst_start && IsPathSeparator(dst[-1]))
281         dst--;
282 
283     if (dst == start) {
284         // Handle special cases like "aa/.." -> "."
285         *dst++ = '.';
286     }
287 
288     *len = dst - start;  // dst points after the trailing char here.
289 #ifdef _WIN32
290     uint64_t bits = 0;
291     uint64_t bits_mask = 1;
292 
293     for (char* c = start; c < start + *len; ++c) {
294         switch (*c) {
295             case '\\':
296                 bits |= bits_mask;
297                 *c = '/';
298                 NINJA_FALLTHROUGH;
299             case '/':
300                 bits_mask <<= 1;
301         }
302     }
303 
304     *slash_bits = bits;
305 #else
306     *slash_bits = 0;
307 #endif
308 }
309 
IsKnownShellSafeCharacter(char ch)310 static inline bool IsKnownShellSafeCharacter(char ch) {
311     if ('A' <= ch && ch <= 'Z') return true;
312     if ('a' <= ch && ch <= 'z') return true;
313     if ('0' <= ch && ch <= '9') return true;
314 
315     switch (ch) {
316         case '_':
317         case '+':
318         case '-':
319         case '.':
320         case '/':
321             return true;
322         default:
323             return false;
324     }
325 }
326 
IsKnownWin32SafeCharacter(char ch)327 static inline bool IsKnownWin32SafeCharacter(char ch) {
328     switch (ch) {
329         case ' ':
330         case '"':
331             return false;
332         default:
333             return true;
334     }
335 }
336 
StringNeedsShellEscaping(const string& input)337 static inline bool StringNeedsShellEscaping(const string& input) {
338     for (size_t i = 0; i < input.size(); ++i) {
339         if (!IsKnownShellSafeCharacter(input[i])) return true;
340     }
341     return false;
342 }
343 
StringNeedsWin32Escaping(const string& input)344 static inline bool StringNeedsWin32Escaping(const string& input) {
345     for (size_t i = 0; i < input.size(); ++i) {
346         if (!IsKnownWin32SafeCharacter(input[i])) return true;
347     }
348     return false;
349 }
350 
GetShellEscapedString(const string& input, string* result)351 void GetShellEscapedString(const string& input, string* result) {
352     assert(result);
353 
354     if (!StringNeedsShellEscaping(input)) {
355         result->append(input);
356         return;
357     }
358 
359     const char kQuote = '\'';
360     const char kEscapeSequence[] = "'\\'";
361 
362     result->push_back(kQuote);
363 
364     string::const_iterator span_begin = input.begin();
365     for (string::const_iterator it = input.begin(), end = input.end(); it != end;
366               ++it) {
367         if (*it == kQuote) {
368             result->append(span_begin, it);
369             result->append(kEscapeSequence);
370             span_begin = it;
371         }
372     }
373     result->append(span_begin, input.end());
374     result->push_back(kQuote);
375 }
376 
377 
GetWin32EscapedString(const string& input, string* result)378 void GetWin32EscapedString(const string& input, string* result) {
379     assert(result);
380     if (!StringNeedsWin32Escaping(input)) {
381         result->append(input);
382         return;
383     }
384 
385     const char kQuote = '"';
386     const char kBackslash = '\\';
387 
388     result->push_back(kQuote);
389     size_t consecutive_backslash_count = 0;
390     string::const_iterator span_begin = input.begin();
391     for (string::const_iterator it = input.begin(), end = input.end(); it != end;
392               ++it) {
393         switch (*it) {
394             case kBackslash:
395                 ++consecutive_backslash_count;
396                 break;
397             case kQuote:
398                 result->append(span_begin, it);
399                 result->append(consecutive_backslash_count + 1, kBackslash);
400                 span_begin = it;
401                 consecutive_backslash_count = 0;
402                 break;
403             default:
404                 consecutive_backslash_count = 0;
405                 break;
406         }
407     }
408     result->append(span_begin, input.end());
409     result->append(consecutive_backslash_count, kBackslash);
410     result->push_back(kQuote);
411 }
412 
ReadFile(const string& path, string* contents, string* err)413 int ReadFile(const string& path, string* contents, string* err) {
414 #ifdef _WIN32
415     // This makes a ninja run on a set of 1500 manifest files about 4% faster
416     // than using the generic fopen code below.
417     err->clear();
418     HANDLE f = ::CreateFileA(path.c_str(), GENERIC_READ, FILE_SHARE_READ, NULL,
419                                                       OPEN_EXISTING, FILE_FLAG_SEQUENTIAL_SCAN, NULL);
420     if (f == INVALID_HANDLE_VALUE) {
421         err->assign(GetLastErrorString());
422         return -ENOENT;
423     }
424 
425     for (;;) {
426         DWORD len;
427         char buf[64 << 10];
428         if (!::ReadFile(f, buf, sizeof(buf), &len, NULL)) {
429             err->assign(GetLastErrorString());
430             contents->clear();
431             ::CloseHandle(f);
432             return -EIO;
433         }
434         if (len == 0)
435             break;
436         contents->append(buf, len);
437     }
438     ::CloseHandle(f);
439     return 0;
440 #else
441     FILE* f = fopen(path.c_str(), "rb");
442     if (!f) {
443         err->assign(strerror(errno));
444         return -errno;
445     }
446 
447 #ifdef __USE_LARGEFILE64
448     struct stat64 st;
449     if (fstat64(fileno(f), &st) < 0) {
450 #else
451     struct stat st;
452     if (fstat(fileno(f), &st) < 0) {
453 #endif
454         err->assign(strerror(errno));
455         fclose(f);
456         return -errno;
457     }
458 
459     // +1 is for the resize in ManifestParser::Load
460     contents->reserve(st.st_size + 1);
461 
462     char buf[64 << 10];
463     size_t len;
464     while (!feof(f) && (len = fread(buf, 1, sizeof(buf), f)) > 0) {
465         contents->append(buf, len);
466     }
467     if (ferror(f)) {
468         err->assign(strerror(errno));  // XXX errno?
469         contents->clear();
470         fclose(f);
471         return -errno;
472     }
473     fclose(f);
474     return 0;
475 #endif
476 }
477 
478 void SetCloseOnExec(int fd) {
479 #ifndef _WIN32
480     int flags = fcntl(fd, F_GETFD);
481     if (flags < 0) {
482         perror("fcntl(F_GETFD)");
483     } else {
484         if (fcntl(fd, F_SETFD, flags | FD_CLOEXEC) < 0)
485             perror("fcntl(F_SETFD)");
486     }
487 #else
488     HANDLE hd = (HANDLE) _get_osfhandle(fd);
489     if (! SetHandleInformation(hd, HANDLE_FLAG_INHERIT, 0)) {
490         fprintf(stderr, "SetHandleInformation(): %s", GetLastErrorString().c_str());
491     }
492 #endif  // ! _WIN32
493 }
494 
495 
496 const char* SpellcheckStringV(const string& text,
497                                                             const vector<const char*>& words) {
498     const bool kAllowReplacements = true;
499     const int kMaxValidEditDistance = 3;
500 
501     int min_distance = kMaxValidEditDistance + 1;
502     const char* result = NULL;
503     for (vector<const char*>::const_iterator i = words.begin();
504               i != words.end(); ++i) {
505         int distance = EditDistance(*i, text, kAllowReplacements,
506                                                                 kMaxValidEditDistance);
507         if (distance < min_distance) {
508             min_distance = distance;
509             result = *i;
510         }
511     }
512     return result;
513 }
514 
515 const char* SpellcheckString(const char* text, ...) {
516     // Note: This takes a const char* instead of a string& because using
517     // va_start() with a reference parameter is undefined behavior.
518     va_list ap;
519     va_start(ap, text);
520     vector<const char*> words;
521     const char* word;
522     while ((word = va_arg(ap, const char*)))
523         words.push_back(word);
524     va_end(ap);
525     return SpellcheckStringV(text, words);
526 }
527 
528 #ifdef _WIN32
529 string GetLastErrorString() {
530     DWORD err = GetLastError();
531 
532     char* msg_buf;
533     FormatMessageA(
534                 FORMAT_MESSAGE_ALLOCATE_BUFFER |
535                 FORMAT_MESSAGE_FROM_SYSTEM |
536                 FORMAT_MESSAGE_IGNORE_INSERTS,
537                 NULL,
538                 err,
539                 MAKELANGID(LANG_ENGLISH, SUBLANG_DEFAULT),
540                 (char*)&msg_buf,
541                 0,
542                 NULL);
543 
544     if (msg_buf == nullptr) {
545         char fallback_msg[128] = {0};
546         snprintf(fallback_msg, sizeof(fallback_msg), "GetLastError() = %d", err);
547         return fallback_msg;
548     }
549 
550     string msg = msg_buf;
551     LocalFree(msg_buf);
552     return msg;
553 }
554 
555 void Win32Fatal(const char* function, const char* hint) {
556     if (hint) {
557         Fatal("%s: %s (%s)", function, GetLastErrorString().c_str(), hint);
558     } else {
559         Fatal("%s: %s", function, GetLastErrorString().c_str());
560     }
561 }
562 #endif
563 
564 bool islatinalpha(int c) {
565     // isalpha() is locale-dependent.
566     return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
567 }
568 
569 string StripAnsiEscapeCodes(const string& in) {
570     string stripped;
571     stripped.reserve(in.size());
572 
573     for (size_t i = 0; i < in.size(); ++i) {
574         if (in[i] != '\33') {
575             // Not an escape code.
576             stripped.push_back(in[i]);
577             continue;
578         }
579 
580         // Only strip CSIs for now.
581         if (i + 1 >= in.size()) break;
582         if (in[i + 1] != '[') continue;  // Not a CSI.
583         i += 2;
584 
585         // Skip everything up to and including the next [a-zA-Z].
586         while (i < in.size() && !islatinalpha(in[i]))
587             ++i;
588     }
589     return stripped;
590 }
591 
592 #if defined(linux) || defined(__GLIBC__)
593 std::pair<int64_t, bool> readCount(const std::string& path) {
594     std::ifstream file(path.c_str());
595     if (!file.is_open())
596         return std::make_pair(0, false);
597     int64_t n = 0;
598     file >> n;
599     if (file.good())
600         return std::make_pair(n, true);
601     return std::make_pair(0, false);
602 }
603 
604 struct MountPoint {
605     int mountId;
606     int parentId;
607     StringPiece deviceId;
608     StringPiece root;
609     StringPiece mountPoint;
610     vector<StringPiece> options;
611     vector<StringPiece> optionalFields;
612     StringPiece fsType;
613     StringPiece mountSource;
614     vector<StringPiece> superOptions;
615     bool parse(const string& line) {
616         vector<StringPiece> pieces = SplitStringPiece(line, ' ');
617         if (pieces.size() < 10)
618             return false;
619         size_t optionalStart = 0;
620         for (size_t i = 6; i < pieces.size(); i++) {
621             if (pieces[i] == "-") {
622                 optionalStart = i + 1;
623                 break;
624             }
625         }
626         if (optionalStart == 0)
627             return false;
628         if (optionalStart + 3 != pieces.size())
629             return false;
630         mountId = atoi(pieces[0].AsString().c_str());
631         parentId = atoi(pieces[1].AsString().c_str());
632         deviceId = pieces[2];
633         root = pieces[3];
634         mountPoint = pieces[4];
635         options = SplitStringPiece(pieces[5], ',');
636         optionalFields =
637                 vector<StringPiece>(&pieces[6], &pieces[optionalStart - 1]);
638         fsType = pieces[optionalStart];
639         mountSource = pieces[optionalStart + 1];
640         superOptions = SplitStringPiece(pieces[optionalStart + 2], ',');
641         return true;
642     }
643     string translate(string& path) const {
644         // path must be sub dir of root
645         if (path.compare(0, root.len_, root.str_, root.len_) != 0) {
646             return string();
647         }
648         path.erase(0, root.len_);
649         if (path == ".." || (path.length() > 2 && path.compare(0, 3, "../") == 0)) {
650             return string();
651         }
652         return mountPoint.AsString() + "/" + path;
653     }
654 };
655 
656 struct CGroupSubSys {
657     int id;
658     string name;
659     vector<string> subsystems;
660     bool parse(string& line) {
661         size_t first = line.find(':');
662         if (first == string::npos)
663             return false;
664         line[first] = '\0';
665         size_t second = line.find(':', first + 1);
666         if (second == string::npos)
667             return false;
668         line[second] = '\0';
669         id = atoi(line.c_str());
670         name = line.substr(second + 1);
671         vector<StringPiece> pieces =
672                 SplitStringPiece(StringPiece(line.c_str() + first + 1), ',');
673         for (size_t i = 0; i < pieces.size(); i++) {
674             subsystems.push_back(pieces[i].AsString());
675         }
676         return true;
677     }
678 };
679 
680 map<string, string> ParseMountInfo(map<string, CGroupSubSys>& subsystems) {
681     map<string, string> cgroups;
682     ifstream mountinfo("/proc/self/mountinfo");
683     if (!mountinfo.is_open())
684         return cgroups;
685     while (!mountinfo.eof()) {
686         string line;
687         getline(mountinfo, line);
688         MountPoint mp;
689         if (!mp.parse(line))
690             continue;
691         if (mp.fsType != "cgroup")
692             continue;
693         for (size_t i = 0; i < mp.superOptions.size(); i++) {
694             string opt = mp.superOptions[i].AsString();
695             map<string, CGroupSubSys>::iterator subsys = subsystems.find(opt);
696             if (subsys == subsystems.end())
697                 continue;
698             string newPath = mp.translate(subsys->second.name);
699             if (!newPath.empty())
700                 cgroups.insert(make_pair(opt, newPath));
701         }
702     }
703     return cgroups;
704 }
705 
706 map<string, CGroupSubSys> ParseSelfCGroup() {
707     map<string, CGroupSubSys> cgroups;
708     ifstream cgroup("/proc/self/cgroup");
709     if (!cgroup.is_open())
710         return cgroups;
711     string line;
712     while (!cgroup.eof()) {
713         getline(cgroup, line);
714         CGroupSubSys subsys;
715         if (!subsys.parse(line))
716             continue;
717         for (size_t i = 0; i < subsys.subsystems.size(); i++) {
718             cgroups.insert(make_pair(subsys.subsystems[i], subsys));
719         }
720     }
721     return cgroups;
722 }
723 
724 int ParseCPUFromCGroup() {
725     map<string, CGroupSubSys> subsystems = ParseSelfCGroup();
726     map<string, string> cgroups = ParseMountInfo(subsystems);
727     map<string, string>::iterator cpu = cgroups.find("cpu");
728     if (cpu == cgroups.end())
729         return -1;
730     std::pair<int64_t, bool> quota = readCount(cpu->second + "/cpu.cfs_quota_us");
731     if (!quota.second || quota.first == -1)
732         return -1;
733     std::pair<int64_t, bool> period =
734             readCount(cpu->second + "/cpu.cfs_period_us");
735     if (!period.second)
736         return -1;
737     if (period.first == 0)
738         return -1;
739     return quota.first / period.first;
740 }
741 #endif
742 
743 int GetProcessorCount() {
744 #ifdef _WIN32
745     DWORD cpuCount = 0;
746 #ifndef _WIN64
747     // Need to use GetLogicalProcessorInformationEx to get real core count on
748     // machines with >64 cores. See https://stackoverflow.com/a/31209344/21475
749     DWORD len = 0;
750     if (!GetLogicalProcessorInformationEx(RelationProcessorCore, nullptr, &len)
751                 && GetLastError() == ERROR_INSUFFICIENT_BUFFER) {
752         std::vector<char> buf(len);
753         int cores = 0;
754         if (GetLogicalProcessorInformationEx(RelationProcessorCore,
755                     reinterpret_cast<PSYSTEM_LOGICAL_PROCESSOR_INFORMATION_EX>(
756                         buf.data()), &len)) {
757             for (DWORD i = 0; i < len; ) {
758                 auto info = reinterpret_cast<PSYSTEM_LOGICAL_PROCESSOR_INFORMATION_EX>(
759                         buf.data() + i);
760                 if (info->Relationship == RelationProcessorCore &&
761                         info->Processor.GroupCount == 1) {
762                     for (KAFFINITY core_mask = info->Processor.GroupMask[0].Mask;
763                               core_mask; core_mask >>= 1) {
764                         cores += (core_mask & 1);
765                     }
766                 }
767                 i += info->Size;
768             }
769             if (cores != 0) {
770                 cpuCount = cores;
771             }
772         }
773     }
774 #endif
775     if (cpuCount == 0) {
776         cpuCount = GetActiveProcessorCount(ALL_PROCESSOR_GROUPS);
777     }
778     JOBOBJECT_CPU_RATE_CONTROL_INFORMATION info;
779     // reference:
780     // https://docs.microsoft.com/en-us/windows/win32/api/winnt/ns-winnt-jobobject_cpu_rate_control_information
781     if (QueryInformationJobObject(NULL, JobObjectCpuRateControlInformation, &info,
782                                                                 sizeof(info), NULL)) {
783         if (info.ControlFlags & (JOB_OBJECT_CPU_RATE_CONTROL_ENABLE |
784                                                           JOB_OBJECT_CPU_RATE_CONTROL_HARD_CAP)) {
785             return cpuCount * info.CpuRate / 10000;
786         }
787     }
788     return cpuCount;
789 #else
790     int cgroupCount = -1;
791     int schedCount = -1;
792 #if defined(linux) || defined(__GLIBC__)
793     cgroupCount = ParseCPUFromCGroup();
794 #endif
795     // The number of exposed processors might not represent the actual number of
796     // processors threads can run on. This happens when a CPU set limitation is
797     // active, see https://github.com/ninja-build/ninja/issues/1278
798 #if defined(__FreeBSD__)
799     cpuset_t mask;
800     CPU_ZERO(&mask);
801     if (cpuset_getaffinity(CPU_LEVEL_WHICH, CPU_WHICH_TID, -1, sizeof(mask),
802         &mask) == 0) {
803         return CPU_COUNT(&mask);
804     }
805 #elif defined(CPU_COUNT)
806     cpu_set_t set;
807     if (sched_getaffinity(getpid(), sizeof(set), &set) == 0) {
808         schedCount = CPU_COUNT(&set);
809     }
810 #endif
811     if (cgroupCount >= 0 && schedCount >= 0) return std::min(cgroupCount, schedCount);
812     if (cgroupCount < 0 && schedCount < 0) return sysconf(_SC_NPROCESSORS_ONLN);
813     return std::max(cgroupCount, schedCount);
814 #endif
815 }
816 
817 #if defined(_WIN32) || defined(__CYGWIN__)
818 static double CalculateProcessorLoad(uint64_t idle_ticks, uint64_t total_ticks)
819 {
820     static uint64_t previous_idle_ticks = 0;
821     static uint64_t previous_total_ticks = 0;
822     static double previous_load = -0.0;
823 
824     uint64_t idle_ticks_since_last_time = idle_ticks - previous_idle_ticks;
825     uint64_t total_ticks_since_last_time = total_ticks - previous_total_ticks;
826 
827     bool first_call = (previous_total_ticks == 0);
828     bool ticks_not_updated_since_last_call = (total_ticks_since_last_time == 0);
829 
830     double load;
831     if (first_call || ticks_not_updated_since_last_call) {
832         load = previous_load;
833     } else {
834         // Calculate load.
835         double idle_to_total_ratio =
836                 ((double)idle_ticks_since_last_time) / total_ticks_since_last_time;
837         double load_since_last_call = 1.0 - idle_to_total_ratio;
838 
839         // Filter/smooth result when possible.
840         if(previous_load > 0) {
841             load = 0.9 * previous_load + 0.1 * load_since_last_call;
842         } else {
843             load = load_since_last_call;
844         }
845     }
846 
847     previous_load = load;
848     previous_total_ticks = total_ticks;
849     previous_idle_ticks = idle_ticks;
850 
851     return load;
852 }
853 
854 static uint64_t FileTimeToTickCount(const FILETIME & ft)
855 {
856     uint64_t high = (((uint64_t)(ft.dwHighDateTime)) << 32);
857     uint64_t low  = ft.dwLowDateTime;
858     return (high | low);
859 }
860 
861 double GetLoadAverage() {
862     FILETIME idle_time, kernel_time, user_time;
863     BOOL get_system_time_succeeded =
864             GetSystemTimes(&idle_time, &kernel_time, &user_time);
865 
866     double posix_compatible_load;
867     if (get_system_time_succeeded) {
868         uint64_t idle_ticks = FileTimeToTickCount(idle_time);
869 
870         // kernel_time from GetSystemTimes already includes idle_time.
871         uint64_t total_ticks =
872                 FileTimeToTickCount(kernel_time) + FileTimeToTickCount(user_time);
873 
874         double processor_load = CalculateProcessorLoad(idle_ticks, total_ticks);
875         posix_compatible_load = processor_load * GetProcessorCount();
876 
877     } else {
878         posix_compatible_load = -0.0;
879     }
880 
881     return posix_compatible_load;
882 }
883 #elif defined(__PASE__)
884 double GetLoadAverage() {
885     return -0.0f;
886 }
887 #elif defined(_AIX)
888 double GetLoadAverage() {
889     perfstat_cpu_total_t cpu_stats;
890     if (perfstat_cpu_total(NULL, &cpu_stats, sizeof(cpu_stats), 1) < 0) {
891         return -0.0f;
892     }
893 
894     // Calculation taken from comment in libperfstats.h
895     return double(cpu_stats.loadavg[0]) / double(1 << SBITS);
896 }
897 #elif defined(__UCLIBC__) || (defined(__BIONIC__) && __ANDROID_API__ < 29)
898 double GetLoadAverage() {
899     struct sysinfo si;
900     if (sysinfo(&si) != 0)
901         return -0.0f;
902     return 1.0 / (1 << SI_LOAD_SHIFT) * si.loads[0];
903 }
904 #elif defined(__HAIKU__)
905 double GetLoadAverage() {
906         return -0.0f;
907 }
908 #else
909 double GetLoadAverage() {
910     double loadavg[3] = { 0.0f, 0.0f, 0.0f };
911     if (getloadavg(loadavg, 3) < 0) {
912         // Maybe we should return an error here or the availability of
913         // getloadavg(3) should be checked when ninja is configured.
914         return -0.0f;
915     }
916     return loadavg[0];
917 }
918 #endif // _WIN32
919 
920 string ElideMiddle(const string& str, size_t width) {
921     switch (width) {
922             case 0: return "";
923             case 1: return ".";
924             case 2: return "..";
925             case 3: return "...";
926     }
927     const int kMargin = 3;  // Space for "...".
928     string result = str;
929     if (result.size() > width) {
930         size_t elide_size = (width - kMargin) / 2;
931         result = result.substr(0, elide_size)
932             + "..."
933             + result.substr(result.size() - elide_size, elide_size);
934     }
935     return result;
936 }
937 
938 bool Truncate(const string& path, size_t size, string* err) {
939 #ifdef _WIN32
940     int fh = _sopen(path.c_str(), _O_RDWR | _O_CREAT, _SH_DENYNO,
941                                     _S_IREAD | _S_IWRITE);
942     int success = _chsize(fh, size);
943     _close(fh);
944 #else
945     int success = truncate(path.c_str(), size);
946 #endif
947     // Both truncate() and _chsize() return 0 on success and set errno and return
948     // -1 on failure.
949     if (success < 0) {
950         *err = strerror(errno);
951         return false;
952     }
953     return true;
954 }
955