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// On AIX, inttypes.h gets indirectly included by build_log.h.
16// It's easiest just to ask for the printf format macros right away.
17#ifndef _WIN32
18#ifndef __STDC_FORMAT_MACROS
19#define __STDC_FORMAT_MACROS
20#endif
21#endif
22
23#include "build_log.h"
24#include "disk_interface.h"
25
26#include <cassert>
27#include <errno.h>
28#include <stdlib.h>
29#include <string.h>
30
31#ifndef _WIN32
32#include <inttypes.h>
33#include <unistd.h>
34#endif
35
36#include "build.h"
37#include "graph.h"
38#include "metrics.h"
39#include "util.h"
40#if defined(_MSC_VER) && (_MSC_VER < 1800)
41#define strtoll _strtoi64
42#endif
43
44using namespace std;
45
46// Implementation details:
47// Each run's log appends to the log file.
48// To load, we run through all log entries in series, throwing away
49// older runs.
50// Once the number of redundant entries exceeds a threshold, we write
51// out a new file and replace the existing one with it.
52
53namespace {
54
55const char kFileSignature[] = "# ninja log v%d\n";
56const int kOldestSupportedVersion = 4;
57const int kCurrentVersion = 5;
58
59// 64bit MurmurHash2, by Austin Appleby
60#if defined(_MSC_VER)
61#define BIG_CONSTANT(x) (x)
62#else // defined(_MSC_VER)
63#define BIG_CONSTANT(x) (x##LLU)
64#endif // !defined(_MSC_VER)
65inline
66uint64_t MurmurHash64A(const void* key, size_t len) {
67 static const uint64_t seed = 0xDECAFBADDECAFBADull;
68 const uint64_t m = BIG_CONSTANT(0xc6a4a7935bd1e995);
69 const int r = 47;
70 uint64_t h = seed ^ (len * m);
71 const unsigned char* data = (const unsigned char*)key;
72 while (len >= 8) {
73 uint64_t k;
74 memcpy(&k, data, sizeof k);
75 k *= m;
76 k ^= k >> r;
77 k *= m;
78 h ^= k;
79 h *= m;
80 data += 8;
81 len -= 8;
82 }
83 switch (len & 7)
84 {
85 case 7: h ^= uint64_t(data[6]) << 48;
86 NINJA_FALLTHROUGH;
87 case 6: h ^= uint64_t(data[5]) << 40;
88 NINJA_FALLTHROUGH;
89 case 5: h ^= uint64_t(data[4]) << 32;
90 NINJA_FALLTHROUGH;
91 case 4: h ^= uint64_t(data[3]) << 24;
92 NINJA_FALLTHROUGH;
93 case 3: h ^= uint64_t(data[2]) << 16;
94 NINJA_FALLTHROUGH;
95 case 2: h ^= uint64_t(data[1]) << 8;
96 NINJA_FALLTHROUGH;
97 case 1: h ^= uint64_t(data[0]);
98 h *= m;
99 };
100 h ^= h >> r;
101 h *= m;
102 h ^= h >> r;
103 return h;
104}
105#undef BIG_CONSTANT
106
107
108} // namespace
109
110// static
111uint64_t BuildLog::LogEntry::HashCommand(StringPiece command) {
112 return MurmurHash64A(command.str_, command.len_);
113}
114
115BuildLog::LogEntry::LogEntry(const string& output)
116 : output(output) {}
117
118BuildLog::LogEntry::LogEntry(const string& output, uint64_t command_hash,
119 int start_time, int end_time, TimeStamp mtime)
120 : output(output), command_hash(command_hash),
121 start_time(start_time), end_time(end_time), mtime(mtime)
122{}
123
124BuildLog::BuildLog()
125 : log_file_(NULL), needs_recompaction_(false) {}
126
127BuildLog::~BuildLog() {
128 Close();
129}
130
131bool BuildLog::OpenForWrite(const string& path, const BuildLogUser& user,
132 string* err) {
133 if (needs_recompaction_) {
134 if (!Recompact(path, user, err))
135 return false;
136 }
137
138 assert(!log_file_);
139 log_file_path_ = path; // we don't actually open the file right now, but will
140 // do so on the first write attempt
141 return true;
142}
143
144bool BuildLog::RecordCommand(Edge* edge, int start_time, int end_time,
145 TimeStamp mtime) {
146 string command = edge->EvaluateCommand(true);
147 uint64_t command_hash = LogEntry::HashCommand(command);
148 for (vector<Node*>::iterator out = edge->outputs_.begin();
149 out != edge->outputs_.end(); ++out) {
150 const string& path = (*out)->path();
151 Entries::iterator i = entries_.find(path);
152 LogEntry* log_entry;
153 if (i != entries_.end()) {
154 log_entry = i->second;
155 } else {
156 log_entry = new LogEntry(path);
157 entries_.insert(Entries::value_type(log_entry->output, log_entry));
158 }
159 log_entry->command_hash = command_hash;
160 log_entry->start_time = start_time;
161 log_entry->end_time = end_time;
162 log_entry->mtime = mtime;
163
164 if (!OpenForWriteIfNeeded()) {
165 return false;
166 }
167 if (log_file_) {
168 if (!WriteEntry(log_file_, *log_entry))
169 return false;
170 if (fflush(log_file_) != 0) {
171 return false;
172 }
173 }
174 }
175 return true;
176}
177
178void BuildLog::Close() {
179 OpenForWriteIfNeeded(); // create the file even if nothing has been recorded
180 if (log_file_)
181 fclose(log_file_);
182 log_file_ = NULL;
183}
184
185bool BuildLog::OpenForWriteIfNeeded() {
186 if (log_file_ || log_file_path_.empty()) {
187 return true;
188 }
189 log_file_ = fopen(log_file_path_.c_str(), "ab");
190 if (!log_file_) {
191 return false;
192 }
193 if (setvbuf(log_file_, NULL, _IOLBF, BUFSIZ) != 0) {
194 return false;
195 }
196 SetCloseOnExec(fileno(log_file_));
197
198 // Opening a file in append mode doesn't set the file pointer to the file's
199 // end on Windows. Do that explicitly.
200 fseek(log_file_, 0, SEEK_END);
201
202 if (ftell(log_file_) == 0) {
203 if (fprintf(log_file_, kFileSignature, kCurrentVersion) < 0) {
204 return false;
205 }
206 }
207 return true;
208}
209
210struct LineReader {
211 explicit LineReader(FILE* file)
212 : file_(file), buf_end_(buf_), line_start_(buf_), line_end_(NULL) {
213 memset(buf_, 0, sizeof(buf_));
214 }
215
216 // Reads a \n-terminated line from the file passed to the constructor.
217 // On return, *line_start points to the beginning of the next line, and
218 // *line_end points to the \n at the end of the line. If no newline is seen
219 // in a fixed buffer size, *line_end is set to NULL. Returns false on EOF.
220 bool ReadLine(char** line_start, char** line_end) {
221 if (line_start_ >= buf_end_ || !line_end_) {
222 // Buffer empty, refill.
223 size_t size_read = fread(buf_, 1, sizeof(buf_), file_);
224 if (!size_read)
225 return false;
226 line_start_ = buf_;
227 buf_end_ = buf_ + size_read;
228 } else {
229 // Advance to next line in buffer.
230 line_start_ = line_end_ + 1;
231 }
232
233 line_end_ = (char*)memchr(line_start_, '\n', buf_end_ - line_start_);
234 if (!line_end_) {
235 // No newline. Move rest of data to start of buffer, fill rest.
236 size_t already_consumed = line_start_ - buf_;
237 size_t size_rest = (buf_end_ - buf_) - already_consumed;
238 memmove(buf_, line_start_, size_rest);
239
240 size_t read = fread(buf_ + size_rest, 1, sizeof(buf_) - size_rest, file_);
241 buf_end_ = buf_ + size_rest + read;
242 line_start_ = buf_;
243 line_end_ = (char*)memchr(line_start_, '\n', buf_end_ - line_start_);
244 }
245
246 *line_start = line_start_;
247 *line_end = line_end_;
248 return true;
249 }
250
251 private:
252 FILE* file_;
253 char buf_[256 << 10];
254 char* buf_end_; // Points one past the last valid byte in |buf_|.
255
256 char* line_start_;
257 // Points at the next \n in buf_ after line_start, or NULL.
258 char* line_end_;
259};
260
261LoadStatus BuildLog::Load(const string& path, string* err) {
262 METRIC_RECORD(".ninja_log load");
263 FILE* file = fopen(path.c_str(), "r");
264 if (!file) {
265 if (errno == ENOENT)
266 return LOAD_NOT_FOUND;
267 *err = strerror(errno);
268 return LOAD_ERROR;
269 }
270
271 int log_version = 0;
272 int unique_entry_count = 0;
273 int total_entry_count = 0;
274
275 LineReader reader(file);
276 char* line_start = 0;
277 char* line_end = 0;
278 while (reader.ReadLine(&line_start, &line_end)) {
279 if (!log_version) {
280 sscanf(line_start, kFileSignature, &log_version);
281
282 if (log_version < kOldestSupportedVersion) {
283 *err = ("build log version invalid, perhaps due to being too old; "
284 "starting over");
285 fclose(file);
286 unlink(path.c_str());
287 // Don't report this as a failure. An empty build log will cause
288 // us to rebuild the outputs anyway.
289 return LOAD_SUCCESS;
290 }
291 }
292
293 // If no newline was found in this chunk, read the next.
294 if (!line_end)
295 continue;
296
297 const char kFieldSeparator = '\t';
298
299 char* start = line_start;
300 char* end = (char*)memchr(start, kFieldSeparator, line_end - start);
301 if (!end)
302 continue;
303 *end = 0;
304
305 int start_time = 0, end_time = 0;
306 TimeStamp mtime = 0;
307
308 start_time = atoi(start);
309 start = end + 1;
310
311 end = (char*)memchr(start, kFieldSeparator, line_end - start);
312 if (!end)
313 continue;
314 *end = 0;
315 end_time = atoi(start);
316 start = end + 1;
317
318 end = (char*)memchr(start, kFieldSeparator, line_end - start);
319 if (!end)
320 continue;
321 *end = 0;
322 mtime = strtoll(start, NULL, 10);
323 start = end + 1;
324
325 end = (char*)memchr(start, kFieldSeparator, line_end - start);
326 if (!end)
327 continue;
328 string output = string(start, end - start);
329
330 start = end + 1;
331 end = line_end;
332
333 LogEntry* entry;
334 Entries::iterator i = entries_.find(output);
335 if (i != entries_.end()) {
336 entry = i->second;
337 } else {
338 entry = new LogEntry(output);
339 entries_.insert(Entries::value_type(entry->output, entry));
340 ++unique_entry_count;
341 }
342 ++total_entry_count;
343
344 entry->start_time = start_time;
345 entry->end_time = end_time;
346 entry->mtime = mtime;
347 if (log_version >= 5) {
348 char c = *end; *end = '\0';
349 entry->command_hash = (uint64_t)strtoull(start, NULL, 16);
350 *end = c;
351 } else {
352 entry->command_hash = LogEntry::HashCommand(StringPiece(start,
353 end - start));
354 }
355 }
356 fclose(file);
357
358 if (!line_start) {
359 return LOAD_SUCCESS; // file was empty
360 }
361
362 // Decide whether it's time to rebuild the log:
363 // - if we're upgrading versions
364 // - if it's getting large
365 int kMinCompactionEntryCount = 100;
366 int kCompactionRatio = 3;
367 if (log_version < kCurrentVersion) {
368 needs_recompaction_ = true;
369 } else if (total_entry_count > kMinCompactionEntryCount &&
370 total_entry_count > unique_entry_count * kCompactionRatio) {
371 needs_recompaction_ = true;
372 }
373
374 return LOAD_SUCCESS;
375}
376
377BuildLog::LogEntry* BuildLog::LookupByOutput(const string& path) {
378 Entries::iterator i = entries_.find(path);
379 if (i != entries_.end())
380 return i->second;
381 return NULL;
382}
383
384bool BuildLog::WriteEntry(FILE* f, const LogEntry& entry) {
385 return fprintf(f, "%d\t%d\t%" PRId64 "\t%s\t%" PRIx64 "\n",
386 entry.start_time, entry.end_time, entry.mtime,
387 entry.output.c_str(), entry.command_hash) > 0;
388}
389
390bool BuildLog::Recompact(const string& path, const BuildLogUser& user,
391 string* err) {
392 METRIC_RECORD(".ninja_log recompact");
393
394 Close();
395 string temp_path = path + ".recompact";
396 FILE* f = fopen(temp_path.c_str(), "wb");
397 if (!f) {
398 *err = strerror(errno);
399 return false;
400 }
401
402 if (fprintf(f, kFileSignature, kCurrentVersion) < 0) {
403 *err = strerror(errno);
404 fclose(f);
405 return false;
406 }
407
408 vector<StringPiece> dead_outputs;
409 for (Entries::iterator i = entries_.begin(); i != entries_.end(); ++i) {
410 if (user.IsPathDead(i->first)) {
411 dead_outputs.push_back(i->first);
412 continue;
413 }
414
415 if (!WriteEntry(f, *i->second)) {
416 *err = strerror(errno);
417 fclose(f);
418 return false;
419 }
420 }
421
422 for (size_t i = 0; i < dead_outputs.size(); ++i)
423 entries_.erase(dead_outputs[i]);
424
425 fclose(f);
426 if (unlink(path.c_str()) < 0) {
427 *err = strerror(errno);
428 return false;
429 }
430
431 if (rename(temp_path.c_str(), path.c_str()) < 0) {
432 *err = strerror(errno);
433 return false;
434 }
435
436 return true;
437}
438
439bool BuildLog::Restat(const StringPiece path,
440 const DiskInterface& disk_interface,
441 const int output_count, char** outputs,
442 std::string* const err) {
443 METRIC_RECORD(".ninja_log restat");
444
445 Close();
446 std::string temp_path = path.AsString() + ".restat";
447 FILE* f = fopen(temp_path.c_str(), "wb");
448 if (!f) {
449 *err = strerror(errno);
450 return false;
451 }
452
453 if (fprintf(f, kFileSignature, kCurrentVersion) < 0) {
454 *err = strerror(errno);
455 fclose(f);
456 return false;
457 }
458 for (Entries::iterator i = entries_.begin(); i != entries_.end(); ++i) {
459 bool skip = output_count > 0;
460 for (int j = 0; j < output_count; ++j) {
461 if (i->second->output == outputs[j]) {
462 skip = false;
463 break;
464 }
465 }
466 if (!skip) {
467 const TimeStamp mtime = disk_interface.Stat(i->second->output, err);
468 if (mtime == -1) {
469 fclose(f);
470 return false;
471 }
472 i->second->mtime = mtime;
473 }
474
475 if (!WriteEntry(f, *i->second)) {
476 *err = strerror(errno);
477 fclose(f);
478 return false;
479 }
480 }
481
482 fclose(f);
483 if (unlink(path.str_) < 0) {
484 *err = strerror(errno);
485 return false;
486 }
487
488 if (rename(temp_path.c_str(), path.str_) < 0) {
489 *err = strerror(errno);
490 return false;
491 }
492
493 return true;
494}
495