Ninja
build_log.cc
Go to the documentation of this file.
00001 // Copyright 2011 Google Inc. All Rights Reserved.
00002 //
00003 // Licensed under the Apache License, Version 2.0 (the "License");
00004 // you may not use this file except in compliance with the License.
00005 // You may obtain a copy of the License at
00006 //
00007 //     http://www.apache.org/licenses/LICENSE-2.0
00008 //
00009 // Unless required by applicable law or agreed to in writing, software
00010 // distributed under the License is distributed on an "AS IS" BASIS,
00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00012 // See the License for the specific language governing permissions and
00013 // limitations under the License.
00014 
00015 #include "build_log.h"
00016 
00017 #include <errno.h>
00018 #include <stdlib.h>
00019 #include <string.h>
00020 
00021 #ifndef _WIN32
00022 #define __STDC_FORMAT_MACROS
00023 #include <inttypes.h>
00024 #include <unistd.h>
00025 #endif
00026 
00027 #include "build.h"
00028 #include "graph.h"
00029 #include "metrics.h"
00030 #include "util.h"
00031 
00032 // Implementation details:
00033 // Each run's log appends to the log file.
00034 // To load, we run through all log entries in series, throwing away
00035 // older runs.
00036 // Once the number of redundant entries exceeds a threshold, we write
00037 // out a new file and replace the existing one with it.
00038 
00039 namespace {
00040 
00041 const char kFileSignature[] = "# ninja log v%d\n";
00042 const int kOldestSupportedVersion = 4;
00043 const int kCurrentVersion = 5;
00044 
00045 // 64bit MurmurHash2, by Austin Appleby
00046 #if defined(_MSC_VER)
00047 #define BIG_CONSTANT(x) (x)
00048 #else   // defined(_MSC_VER)
00049 #define BIG_CONSTANT(x) (x##LLU)
00050 #endif // !defined(_MSC_VER)
00051 inline
00052 uint64_t MurmurHash64A(const void* key, size_t len) {
00053   static const uint64_t seed = 0xDECAFBADDECAFBADull;
00054   const uint64_t m = BIG_CONSTANT(0xc6a4a7935bd1e995);
00055   const int r = 47;
00056   uint64_t h = seed ^ (len * m);
00057   const unsigned char* data = (const unsigned char*)key;
00058   while (len >= 8) {
00059     uint64_t k;
00060     memcpy(&k, data, sizeof k);
00061     k *= m;
00062     k ^= k >> r;
00063     k *= m;
00064     h ^= k;
00065     h *= m;
00066     data += 8;
00067     len -= 8;
00068   }
00069   switch (len & 7)
00070   {
00071   case 7: h ^= uint64_t(data[6]) << 48;
00072   case 6: h ^= uint64_t(data[5]) << 40;
00073   case 5: h ^= uint64_t(data[4]) << 32;
00074   case 4: h ^= uint64_t(data[3]) << 24;
00075   case 3: h ^= uint64_t(data[2]) << 16;
00076   case 2: h ^= uint64_t(data[1]) << 8;
00077   case 1: h ^= uint64_t(data[0]);
00078           h *= m;
00079   };
00080   h ^= h >> r;
00081   h *= m;
00082   h ^= h >> r;
00083   return h;
00084 }
00085 #undef BIG_CONSTANT
00086 
00087 
00088 }  // namespace
00089 
00090 // static
00091 uint64_t BuildLog::LogEntry::HashCommand(StringPiece command) {
00092   return MurmurHash64A(command.str_, command.len_);
00093 }
00094 
00095 BuildLog::LogEntry::LogEntry(const string& output)
00096   : output(output) {}
00097 
00098 BuildLog::LogEntry::LogEntry(const string& output, uint64_t command_hash,
00099   int start_time, int end_time, TimeStamp restat_mtime)
00100   : output(output), command_hash(command_hash),
00101     start_time(start_time), end_time(end_time), restat_mtime(restat_mtime)
00102 {}
00103 
00104 BuildLog::BuildLog()
00105   : log_file_(NULL), needs_recompaction_(false) {}
00106 
00107 BuildLog::~BuildLog() {
00108   Close();
00109 }
00110 
00111 bool BuildLog::OpenForWrite(const string& path, const BuildLogUser& user,
00112                             string* err) {
00113   if (needs_recompaction_) {
00114     if (!Recompact(path, user, err))
00115       return false;
00116   }
00117 
00118   log_file_ = fopen(path.c_str(), "ab");
00119   if (!log_file_) {
00120     *err = strerror(errno);
00121     return false;
00122   }
00123   setvbuf(log_file_, NULL, _IOLBF, BUFSIZ);
00124   SetCloseOnExec(fileno(log_file_));
00125 
00126   // Opening a file in append mode doesn't set the file pointer to the file's
00127   // end on Windows. Do that explicitly.
00128   fseek(log_file_, 0, SEEK_END);
00129 
00130   if (ftell(log_file_) == 0) {
00131     if (fprintf(log_file_, kFileSignature, kCurrentVersion) < 0) {
00132       *err = strerror(errno);
00133       return false;
00134     }
00135   }
00136 
00137   return true;
00138 }
00139 
00140 bool BuildLog::RecordCommand(Edge* edge, int start_time, int end_time,
00141                              TimeStamp restat_mtime) {
00142   string command = edge->EvaluateCommand(true);
00143   uint64_t command_hash = LogEntry::HashCommand(command);
00144   for (vector<Node*>::iterator out = edge->outputs_.begin();
00145        out != edge->outputs_.end(); ++out) {
00146     const string& path = (*out)->path();
00147     Entries::iterator i = entries_.find(path);
00148     LogEntry* log_entry;
00149     if (i != entries_.end()) {
00150       log_entry = i->second;
00151     } else {
00152       log_entry = new LogEntry(path);
00153       entries_.insert(Entries::value_type(log_entry->output, log_entry));
00154     }
00155     log_entry->command_hash = command_hash;
00156     log_entry->start_time = start_time;
00157     log_entry->end_time = end_time;
00158     log_entry->restat_mtime = restat_mtime;
00159 
00160     if (log_file_) {
00161       if (!WriteEntry(log_file_, *log_entry))
00162         return false;
00163     }
00164   }
00165   return true;
00166 }
00167 
00168 void BuildLog::Close() {
00169   if (log_file_)
00170     fclose(log_file_);
00171   log_file_ = NULL;
00172 }
00173 
00174 struct LineReader {
00175   explicit LineReader(FILE* file)
00176     : file_(file), buf_end_(buf_), line_start_(buf_), line_end_(NULL) {
00177       memset(buf_, 0, sizeof(buf_));
00178   }
00179 
00180   // Reads a \n-terminated line from the file passed to the constructor.
00181   // On return, *line_start points to the beginning of the next line, and
00182   // *line_end points to the \n at the end of the line. If no newline is seen
00183   // in a fixed buffer size, *line_end is set to NULL. Returns false on EOF.
00184   bool ReadLine(char** line_start, char** line_end) {
00185     if (line_start_ >= buf_end_ || !line_end_) {
00186       // Buffer empty, refill.
00187       size_t size_read = fread(buf_, 1, sizeof(buf_), file_);
00188       if (!size_read)
00189         return false;
00190       line_start_ = buf_;
00191       buf_end_ = buf_ + size_read;
00192     } else {
00193       // Advance to next line in buffer.
00194       line_start_ = line_end_ + 1;
00195     }
00196 
00197     line_end_ = (char*)memchr(line_start_, '\n', buf_end_ - line_start_);
00198     if (!line_end_) {
00199       // No newline. Move rest of data to start of buffer, fill rest.
00200       size_t already_consumed = line_start_ - buf_;
00201       size_t size_rest = (buf_end_ - buf_) - already_consumed;
00202       memmove(buf_, line_start_, size_rest);
00203 
00204       size_t read = fread(buf_ + size_rest, 1, sizeof(buf_) - size_rest, file_);
00205       buf_end_ = buf_ + size_rest + read;
00206       line_start_ = buf_;
00207       line_end_ = (char*)memchr(line_start_, '\n', buf_end_ - line_start_);
00208     }
00209 
00210     *line_start = line_start_;
00211     *line_end = line_end_;
00212     return true;
00213   }
00214 
00215  private:
00216   FILE* file_;
00217   char buf_[256 << 10];
00218   char* buf_end_;  // Points one past the last valid byte in |buf_|.
00219 
00220   char* line_start_;
00221   // Points at the next \n in buf_ after line_start, or NULL.
00222   char* line_end_;
00223 };
00224 
00225 bool BuildLog::Load(const string& path, string* err) {
00226   METRIC_RECORD(".ninja_log load");
00227   FILE* file = fopen(path.c_str(), "r");
00228   if (!file) {
00229     if (errno == ENOENT)
00230       return true;
00231     *err = strerror(errno);
00232     return false;
00233   }
00234 
00235   int log_version = 0;
00236   int unique_entry_count = 0;
00237   int total_entry_count = 0;
00238 
00239   LineReader reader(file);
00240   char* line_start = 0;
00241   char* line_end = 0;
00242   while (reader.ReadLine(&line_start, &line_end)) {
00243     if (!log_version) {
00244       sscanf(line_start, kFileSignature, &log_version);
00245 
00246       if (log_version < kOldestSupportedVersion) {
00247         *err = ("build log version invalid, perhaps due to being too old; "
00248                 "starting over");
00249         fclose(file);
00250         unlink(path.c_str());
00251         // Don't report this as a failure.  An empty build log will cause
00252         // us to rebuild the outputs anyway.
00253         return true;
00254       }
00255     }
00256 
00257     // If no newline was found in this chunk, read the next.
00258     if (!line_end)
00259       continue;
00260 
00261     const char kFieldSeparator = '\t';
00262 
00263     char* start = line_start;
00264     char* end = (char*)memchr(start, kFieldSeparator, line_end - start);
00265     if (!end)
00266       continue;
00267     *end = 0;
00268 
00269     int start_time = 0, end_time = 0;
00270     TimeStamp restat_mtime = 0;
00271 
00272     start_time = atoi(start);
00273     start = end + 1;
00274 
00275     end = (char*)memchr(start, kFieldSeparator, line_end - start);
00276     if (!end)
00277       continue;
00278     *end = 0;
00279     end_time = atoi(start);
00280     start = end + 1;
00281 
00282     end = (char*)memchr(start, kFieldSeparator, line_end - start);
00283     if (!end)
00284       continue;
00285     *end = 0;
00286     restat_mtime = atol(start);
00287     start = end + 1;
00288 
00289     end = (char*)memchr(start, kFieldSeparator, line_end - start);
00290     if (!end)
00291       continue;
00292     string output = string(start, end - start);
00293 
00294     start = end + 1;
00295     end = line_end;
00296 
00297     LogEntry* entry;
00298     Entries::iterator i = entries_.find(output);
00299     if (i != entries_.end()) {
00300       entry = i->second;
00301     } else {
00302       entry = new LogEntry(output);
00303       entries_.insert(Entries::value_type(entry->output, entry));
00304       ++unique_entry_count;
00305     }
00306     ++total_entry_count;
00307 
00308     entry->start_time = start_time;
00309     entry->end_time = end_time;
00310     entry->restat_mtime = restat_mtime;
00311     if (log_version >= 5) {
00312       char c = *end; *end = '\0';
00313       entry->command_hash = (uint64_t)strtoull(start, NULL, 16);
00314       *end = c;
00315     } else {
00316       entry->command_hash = LogEntry::HashCommand(StringPiece(start,
00317                                                               end - start));
00318     }
00319   }
00320   fclose(file);
00321 
00322   if (!line_start) {
00323     return true; // file was empty
00324   }
00325 
00326   // Decide whether it's time to rebuild the log:
00327   // - if we're upgrading versions
00328   // - if it's getting large
00329   int kMinCompactionEntryCount = 100;
00330   int kCompactionRatio = 3;
00331   if (log_version < kCurrentVersion) {
00332     needs_recompaction_ = true;
00333   } else if (total_entry_count > kMinCompactionEntryCount &&
00334              total_entry_count > unique_entry_count * kCompactionRatio) {
00335     needs_recompaction_ = true;
00336   }
00337 
00338   return true;
00339 }
00340 
00341 BuildLog::LogEntry* BuildLog::LookupByOutput(const string& path) {
00342   Entries::iterator i = entries_.find(path);
00343   if (i != entries_.end())
00344     return i->second;
00345   return NULL;
00346 }
00347 
00348 bool BuildLog::WriteEntry(FILE* f, const LogEntry& entry) {
00349   return fprintf(f, "%d\t%d\t%d\t%s\t%" PRIx64 "\n",
00350           entry.start_time, entry.end_time, entry.restat_mtime,
00351           entry.output.c_str(), entry.command_hash) > 0;
00352 }
00353 
00354 bool BuildLog::Recompact(const string& path, const BuildLogUser& user,
00355                          string* err) {
00356   METRIC_RECORD(".ninja_log recompact");
00357   printf("Recompacting log...\n");
00358 
00359   Close();
00360   string temp_path = path + ".recompact";
00361   FILE* f = fopen(temp_path.c_str(), "wb");
00362   if (!f) {
00363     *err = strerror(errno);
00364     return false;
00365   }
00366 
00367   if (fprintf(f, kFileSignature, kCurrentVersion) < 0) {
00368     *err = strerror(errno);
00369     fclose(f);
00370     return false;
00371   }
00372 
00373   vector<StringPiece> dead_outputs;
00374   for (Entries::iterator i = entries_.begin(); i != entries_.end(); ++i) {
00375     if (user.IsPathDead(i->first)) {
00376       dead_outputs.push_back(i->first);
00377       continue;
00378     }
00379 
00380     if (!WriteEntry(f, *i->second)) {
00381       *err = strerror(errno);
00382       fclose(f);
00383       return false;
00384     }
00385   }
00386 
00387   for (size_t i = 0; i < dead_outputs.size(); ++i)
00388     entries_.erase(dead_outputs[i]);
00389 
00390   fclose(f);
00391   if (unlink(path.c_str()) < 0) {
00392     *err = strerror(errno);
00393     return false;
00394   }
00395 
00396   if (rename(temp_path.c_str(), path.c_str()) < 0) {
00397     *err = strerror(errno);
00398     return false;
00399   }
00400 
00401   return true;
00402 }