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