diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/build.cc | 14 | ||||
-rw-r--r-- | src/build.h | 2 | ||||
-rw-r--r-- | src/build_log.cc | 64 | ||||
-rw-r--r-- | src/build_log.h | 7 | ||||
-rw-r--r-- | src/build_log_test.cc | 12 | ||||
-rw-r--r-- | src/build_test.cc | 6 | ||||
-rw-r--r-- | src/canon_perftest.cc | 38 | ||||
-rw-r--r-- | src/depfile_parser.cc | 16 | ||||
-rw-r--r-- | src/depfile_parser.h | 5 | ||||
-rw-r--r-- | src/depfile_parser.in.cc | 2 | ||||
-rw-r--r-- | src/depfile_parser_test.cc | 13 | ||||
-rw-r--r-- | src/explain.h | 5 | ||||
-rw-r--r-- | src/graph.cc | 20 | ||||
-rw-r--r-- | src/hash_collision_bench.cc | 43 | ||||
-rw-r--r-- | src/lexer.h | 4 | ||||
-rw-r--r-- | src/metrics.h | 5 | ||||
-rw-r--r-- | src/parsers.cc | 2 | ||||
-rw-r--r-- | src/parsers_test.cc | 17 | ||||
-rw-r--r-- | src/test.cc | 5 | ||||
-rw-r--r-- | src/test.h | 1 | ||||
-rw-r--r-- | src/util.h | 1 |
21 files changed, 236 insertions, 46 deletions
diff --git a/src/build.cc b/src/build.cc index 157442d..65aa6a9 100644 --- a/src/build.cc +++ b/src/build.cc @@ -16,6 +16,7 @@ #include <assert.h> #include <stdio.h> +#include <stdlib.h> #ifdef _WIN32 #include <windows.h> @@ -23,7 +24,6 @@ #include <unistd.h> #include <sys/ioctl.h> #include <sys/time.h> -#include <sys/termios.h> #endif #include "build_log.h" @@ -36,7 +36,6 @@ BuildStatus::BuildStatus(const BuildConfig& config) : config_(config), start_time_millis_(GetTimeMillis()), - last_update_millis_(start_time_millis_), started_edges_(0), finished_edges_(0), total_edges_(0), have_blank_line_(true), progress_status_format_(NULL) { #ifndef _WIN32 @@ -85,7 +84,6 @@ void BuildStatus::BuildEdgeFinished(Edge* edge, RunningEdgeMap::iterator i = running_edges_.find(edge); *start_time = i->second; *end_time = (int)(now - start_time_millis_); - int total_time = end_time - start_time; running_edges_.erase(i); if (config_.verbosity == BuildConfig::QUIET) @@ -94,15 +92,7 @@ void BuildStatus::BuildEdgeFinished(Edge* edge, if (smart_terminal_) PrintStatus(edge); - if (success && output.empty()) { - if (!smart_terminal_) { - if (total_time > 5*1000) { - printf("%.1f%% %d/%d\n", finished_edges_ * 100 / (float)total_edges_, - finished_edges_, total_edges_); - last_update_millis_ = now; - } - } - } else { + if (!success || !output.empty()) { if (smart_terminal_) printf("\n"); diff --git a/src/build.h b/src/build.h index 036325d..c9ee4ac 100644 --- a/src/build.h +++ b/src/build.h @@ -176,8 +176,6 @@ struct BuildStatus { /// Time the build started. int64_t start_time_millis_; - /// Time we last printed an update. - int64_t last_update_millis_; int started_edges_, finished_edges_, total_edges_; diff --git a/src/build_log.cc b/src/build_log.cc index 5803ada..97c3344 100644 --- a/src/build_log.cc +++ b/src/build_log.cc @@ -37,10 +37,57 @@ namespace { const char kFileSignature[] = "# ninja log v%d\n"; -const int kCurrentVersion = 4; +const int kCurrentVersion = 5; + +// 64bit MurmurHash2, by Austin Appleby +#if defined(_MSC_VER) +#define BIG_CONSTANT(x) (x) +#else // defined(_MSC_VER) +#define BIG_CONSTANT(x) (x##LLU) +#endif // !defined(_MSC_VER) +inline +uint64_t MurmurHash64A(const void* key, int len) { + static const uint64_t seed = 0xDECAFBADDECAFBADull; + const uint64_t m = BIG_CONSTANT(0xc6a4a7935bd1e995); + const int r = 47; + uint64_t h = seed ^ (len * m); + const uint64_t * data = (const uint64_t *)key; + const uint64_t * end = data + (len/8); + while(data != end) { + uint64_t k = *data++; + k *= m; + k ^= k >> r; + k *= m; + h ^= k; + h *= m; + } + const unsigned char* data2 = (const unsigned char*)data; + switch(len & 7) + { + case 7: h ^= uint64_t(data2[6]) << 48; + case 6: h ^= uint64_t(data2[5]) << 40; + case 5: h ^= uint64_t(data2[4]) << 32; + case 4: h ^= uint64_t(data2[3]) << 24; + case 3: h ^= uint64_t(data2[2]) << 16; + case 2: h ^= uint64_t(data2[1]) << 8; + case 1: h ^= uint64_t(data2[0]); + h *= m; + }; + h ^= h >> r; + h *= m; + h ^= h >> r; + return h; +} +#undef BIG_CONSTANT + } // namespace +// static +uint64_t BuildLog::LogEntry::HashCommand(StringPiece command) { + return MurmurHash64A(command.str_, command.len_); +} + BuildLog::BuildLog() : log_file_(NULL), config_(NULL), needs_recompaction_(false) {} @@ -95,7 +142,7 @@ void BuildLog::RecordCommand(Edge* edge, int start_time, int end_time, log_entry->output = path; log_.insert(Log::value_type(log_entry->output, log_entry)); } - log_entry->command = command; + log_entry->command_hash = LogEntry::HashCommand(command); log_entry->start_time = start_time; log_entry->end_time = end_time; log_entry->restat_mtime = restat_mtime; @@ -239,7 +286,14 @@ bool BuildLog::Load(const string& path, string* err) { entry->start_time = start_time; entry->end_time = end_time; entry->restat_mtime = restat_mtime; - entry->command = string(start, end - start); + if (log_version >= 5) { + char c = *end; *end = '\0'; + entry->command_hash = (uint64_t)strtoull(start, NULL, 10); + *end = c; + } + else + entry->command_hash = LogEntry::HashCommand(StringPiece(start, + end - start)); } // Decide whether it's time to rebuild the log: @@ -267,9 +321,9 @@ BuildLog::LogEntry* BuildLog::LookupByOutput(const string& path) { } void BuildLog::WriteEntry(FILE* f, const LogEntry& entry) { - fprintf(f, "%d\t%d\t%ld\t%s\t%s\n", + fprintf(f, "%d\t%d\t%ld\t%s\t%llu\n", entry.start_time, entry.end_time, (long) entry.restat_mtime, - entry.output.c_str(), entry.command.c_str()); + entry.output.c_str(), entry.command_hash); } bool BuildLog::Recompact(const string& path, string* err) { diff --git a/src/build_log.h b/src/build_log.h index da8e726..d3994ff 100644 --- a/src/build_log.h +++ b/src/build_log.h @@ -22,6 +22,7 @@ using namespace std; #include "hash_map.h" #include "timestamp.h" +#include "util.h" struct BuildConfig; struct Edge; @@ -49,14 +50,16 @@ struct BuildLog { struct LogEntry { string output; - string command; + uint64_t command_hash; int start_time; int end_time; TimeStamp restat_mtime; + static uint64_t HashCommand(StringPiece command); + // Used by tests. bool operator==(const LogEntry& o) { - return output == o.output && command == o.command && + return output == o.output && command_hash == o.command_hash && start_time == o.start_time && end_time == o.end_time && restat_mtime == o.restat_mtime; } diff --git a/src/build_log_test.cc b/src/build_log_test.cc index 199e016..afd3b81 100644 --- a/src/build_log_test.cc +++ b/src/build_log_test.cc @@ -110,7 +110,7 @@ TEST_F(BuildLogTest, DoubleEntry) { BuildLog::LogEntry* e = log.LookupByOutput("out"); ASSERT_TRUE(e); - ASSERT_EQ("command def", e->command); + ASSERT_NO_FATAL_FAILURE(AssertHash("command def", e->command_hash)); } TEST_F(BuildLogTest, Truncate) { @@ -164,7 +164,7 @@ TEST_F(BuildLogTest, UpgradeV3) { ASSERT_EQ(123, e->start_time); ASSERT_EQ(456, e->end_time); ASSERT_EQ(0, e->restat_mtime); - ASSERT_EQ("command", e->command); + ASSERT_NO_FATAL_FAILURE(AssertHash("command", e->command_hash)); } TEST_F(BuildLogTest, SpacesInOutputV4) { @@ -183,7 +183,7 @@ TEST_F(BuildLogTest, SpacesInOutputV4) { ASSERT_EQ(123, e->start_time); ASSERT_EQ(456, e->end_time); ASSERT_EQ(456, e->restat_mtime); - ASSERT_EQ("command", e->command); + ASSERT_NO_FATAL_FAILURE(AssertHash("command", e->command_hash)); } TEST_F(BuildLogTest, DuplicateVersionHeader) { @@ -207,14 +207,14 @@ TEST_F(BuildLogTest, DuplicateVersionHeader) { ASSERT_EQ(123, e->start_time); ASSERT_EQ(456, e->end_time); ASSERT_EQ(456, e->restat_mtime); - ASSERT_EQ("command", e->command); + ASSERT_NO_FATAL_FAILURE(AssertHash("command", e->command_hash)); e = log.LookupByOutput("out2"); ASSERT_TRUE(e); ASSERT_EQ(456, e->start_time); ASSERT_EQ(789, e->end_time); ASSERT_EQ(789, e->restat_mtime); - ASSERT_EQ("command2", e->command); + ASSERT_NO_FATAL_FAILURE(AssertHash("command2", e->command_hash)); } TEST_F(BuildLogTest, VeryLongInputLine) { @@ -242,5 +242,5 @@ TEST_F(BuildLogTest, VeryLongInputLine) { ASSERT_EQ(456, e->start_time); ASSERT_EQ(789, e->end_time); ASSERT_EQ(789, e->restat_mtime); - ASSERT_EQ("command2", e->command); + ASSERT_NO_FATAL_FAILURE(AssertHash("command2", e->command_hash)); } diff --git a/src/build_test.cc b/src/build_test.cc index c45f2b3..23f1909 100644 --- a/src/build_test.cc +++ b/src/build_test.cc @@ -953,8 +953,10 @@ TEST_F(BuildWithLogTest, RspFileCmdLineChange) { // (to simulate a change in the command line between 2 builds) BuildLog::LogEntry * log_entry = build_log_.LookupByOutput("out"); ASSERT_TRUE(NULL != log_entry); - ASSERT_EQ("cat out.rsp > out;rspfile=Original very long command", log_entry->command); - log_entry->command = "cat out.rsp > out;rspfile=Altered very long command"; + ASSERT_NO_FATAL_FAILURE(AssertHash( + "cat out.rsp > out;rspfile=Original very long command", + log_entry->command_hash)); + log_entry->command_hash++; // Change the command hash to something else. // Now expect the target to be rebuilt commands_ran_.clear(); state_.Reset(); diff --git a/src/canon_perftest.cc b/src/canon_perftest.cc new file mode 100644 index 0000000..aaec935 --- /dev/null +++ b/src/canon_perftest.cc @@ -0,0 +1,38 @@ +#include "util.h" + +const char kPath[] = + "../../third_party/WebKit/Source/WebCore/" + "platform/leveldb/LevelDBWriteBatch.cpp"; + +int main() { + vector<int> times; + string err; + + char buf[200]; + int len = strlen(kPath); + strcpy(buf, kPath); + + for (int j = 0; j < 5; ++j) { + const int kNumRepetitions = 2000000; + int64_t start = GetTimeMillis(); + for (int i = 0; i < kNumRepetitions; ++i) { + CanonicalizePath(buf, &len, &err); + } + int delta = (int)(GetTimeMillis() - start); + times.push_back(delta); + } + + int min = times[0]; + int max = times[0]; + float total = 0; + for (size_t i = 0; i < times.size(); ++i) { + total += times[i]; + if (times[i] < min) + min = times[i]; + else if (times[i] > max) + max = times[i]; + } + + printf("min %dms max %dms avg %.1fms\n", + min, max, total / times.size()); +} diff --git a/src/depfile_parser.cc b/src/depfile_parser.cc index 261893f..54b934c 100644 --- a/src/depfile_parser.cc +++ b/src/depfile_parser.cc @@ -54,7 +54,7 @@ bool DepfileParser::Parse(string* content, string* err) { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 128, 128, 128, 128, 128, + 128, 128, 0, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 0, 0, 0, 0, 0, 0, 128, 128, 128, 128, 128, 128, 128, @@ -84,18 +84,21 @@ bool DepfileParser::Parse(string* content, string* err) { }; yych = *in; - if (yych <= '\\') { - if (yych <= ':') { + if (yych <= '[') { + if (yych <= '*') { if (yych <= 0x00) goto yy6; - if (yych <= '*') goto yy8; - goto yy4; + if (yych <= '\'') goto yy8; + if (yych <= ')') goto yy4; + goto yy8; } else { + if (yych <= ':') goto yy4; if (yych <= '@') goto yy8; if (yych <= 'Z') goto yy4; - if (yych <= '[') goto yy8; + goto yy8; } } else { if (yych <= '`') { + if (yych <= '\\') goto yy2; if (yych == '_') goto yy4; goto yy8; } else { @@ -104,6 +107,7 @@ bool DepfileParser::Parse(string* content, string* err) { goto yy8; } } +yy2: ++in; if ((yych = *in) <= '$') { if (yych <= '\n') { diff --git a/src/depfile_parser.h b/src/depfile_parser.h index c900956..1e6ebb5 100644 --- a/src/depfile_parser.h +++ b/src/depfile_parser.h @@ -12,6 +12,9 @@ // See the License for the specific language governing permissions and // limitations under the License. +#ifndef NINJA_DEPFILE_PARSER_H_ +#define NINJA_DEPFILE_PARSER_H_ + #include <string> #include <vector> using namespace std; @@ -28,3 +31,5 @@ struct DepfileParser { StringPiece out_; vector<StringPiece> ins_; }; + +#endif // NINJA_DEPFILE_PARSER_H_ diff --git a/src/depfile_parser.in.cc b/src/depfile_parser.in.cc index 5e073df..8c415b9 100644 --- a/src/depfile_parser.in.cc +++ b/src/depfile_parser.in.cc @@ -68,7 +68,7 @@ bool DepfileParser::Parse(string* content, string* err) { *out++ = yych; continue; } - [a-zA-Z0-9+,/_:.~-]+ { + [a-zA-Z0-9+,/_:.~()-]+ { // Got a span of plain text. int len = in - start; // Need to shift it over if we're overwriting backslashes. diff --git a/src/depfile_parser_test.cc b/src/depfile_parser_test.cc index 9094283..fd76ae7 100644 --- a/src/depfile_parser_test.cc +++ b/src/depfile_parser_test.cc @@ -103,7 +103,18 @@ TEST_F(DepfileParserTest, Escapes) { ASSERT_EQ(0u, parser_.ins_.size()); } -TEST_F(DepfileParserTest, UnifyMultupleOutputs) { +TEST_F(DepfileParserTest, SpecialChars) { + string err; + EXPECT_TRUE(Parse( +"C:/Program\\ Files\\ (x86)/Microsoft\\ crtdefs.h:", + &err)); + ASSERT_EQ("", err); + EXPECT_EQ("C:/Program Files (x86)/Microsoft crtdefs.h", + parser_.out_.AsString()); + ASSERT_EQ(0u, parser_.ins_.size()); +} + +TEST_F(DepfileParserTest, UnifyMultipleOutputs) { // check that multiple duplicate targets are properly unified string err; EXPECT_TRUE(Parse("foo foo: x y z", &err)); diff --git a/src/explain.h b/src/explain.h index 021f0d4..d4f6a6c 100644 --- a/src/explain.h +++ b/src/explain.h @@ -12,6 +12,9 @@ // See the License for the specific language governing permissions and // limitations under the License. +#ifndef NINJA_EXPLAIN_H_ +#define NINJA_EXPLAIN_H_ + #include <stdio.h> #define EXPLAIN(fmt, ...) { \ @@ -20,3 +23,5 @@ } extern bool g_explaining; + +#endif // NINJA_EXPLAIN_H_ diff --git a/src/graph.cc b/src/graph.cc index 3531e86..5418ecf 100644 --- a/src/graph.cc +++ b/src/graph.cc @@ -157,7 +157,7 @@ bool Edge::RecomputeOutputDirty(BuildLog* build_log, // dirty. if (!rule_->generator() && build_log && (entry || (entry = build_log->LookupByOutput(output->path())))) { - if (command != entry->command) { + if (BuildLog::LogEntry::HashCommand(command) != entry->command_hash) { EXPLAIN("command line changed for %s", output->path().c_str()); return true; } @@ -183,34 +183,38 @@ struct EdgeEnv : public Env { /// Given a span of Nodes, construct a list of paths suitable for a command /// line. XXX here is where shell-escaping of e.g spaces should happen. string MakePathList(vector<Node*>::iterator begin, - vector<Node*>::iterator end); + vector<Node*>::iterator end, + char sep); Edge* edge_; }; string EdgeEnv::LookupVariable(const string& var) { - if (var == "in") { + if (var == "in" || var == "in_newline") { int explicit_deps_count = edge_->inputs_.size() - edge_->implicit_deps_ - edge_->order_only_deps_; return MakePathList(edge_->inputs_.begin(), - edge_->inputs_.begin() + explicit_deps_count); + edge_->inputs_.begin() + explicit_deps_count, + var == "in" ? ' ' : '\n'); } else if (var == "out") { return MakePathList(edge_->outputs_.begin(), - edge_->outputs_.end()); + edge_->outputs_.end(), + ' '); } else if (edge_->env_) { return edge_->env_->LookupVariable(var); } else { - // XXX shoudl we warn here? + // XXX should we warn here? return string(); } } string EdgeEnv::MakePathList(vector<Node*>::iterator begin, - vector<Node*>::iterator end) { + vector<Node*>::iterator end, + char sep) { string result; for (vector<Node*>::iterator i = begin; i != end; ++i) { if (!result.empty()) - result.push_back(' '); + result.push_back(sep); const string& path = (*i)->path(); if (path.find(" ") != string::npos) { result.append("\""); diff --git a/src/hash_collision_bench.cc b/src/hash_collision_bench.cc new file mode 100644 index 0000000..d9b09d9 --- /dev/null +++ b/src/hash_collision_bench.cc @@ -0,0 +1,43 @@ +#include "build_log.h" + +int random(int low, int high) { + return int(low + (rand() / double(RAND_MAX)) * (high - low) + 0.5); +} + +void RandomCommand(char** s) { + int len = random(5, 100); + *s = new char[len]; + for (int i = 0; i < len; ++i) + (*s)[i] = random(32, 127); +} + +int main() { + const int N = 20 * 1000 * 1000; + + // Leak these, else 10% of the runtime is spent destroying strings. + char** commands = new char*[N]; + pair<uint64_t, int>* hashes = new pair<uint64_t, int>[N]; + + srand(time(NULL)); + + for (int i = 0; i < N; ++i) { + RandomCommand(&commands[i]); + hashes[i] = make_pair(BuildLog::LogEntry::HashCommand(commands[i]), i); + } + + sort(hashes, hashes + N); + + int num_collisions = 0; + for (int i = 1; i < N; ++i) { + if (hashes[i - 1].first == hashes[i].first) { + if (strcmp(commands[hashes[i - 1].second], + commands[hashes[i].second]) != 0) { + printf("collision!\n string 1: '%s'\n string 2: '%s'\n", + commands[hashes[i - 1].second], + commands[hashes[i].second]); + num_collisions++; + } + } + } + printf("\n\n%d collisions after %d runs\n", num_collisions, N); +} diff --git a/src/lexer.h b/src/lexer.h index 75c1b2f..19008d7 100644 --- a/src/lexer.h +++ b/src/lexer.h @@ -12,6 +12,9 @@ // See the License for the specific language governing permissions and // limitations under the License. +#ifndef NINJA_LEXER_H_ +#define NINJA_LEXER_H_ + #include "string_piece.h" // Windows may #define ERROR. @@ -95,3 +98,4 @@ private: const char* last_token_; }; +#endif // NINJA_LEXER_H_ diff --git a/src/metrics.h b/src/metrics.h index 74f5f8f..af6e9a2 100644 --- a/src/metrics.h +++ b/src/metrics.h @@ -12,6 +12,9 @@ // See the License for the specific language governing permissions and // limitations under the License. +#ifndef NINJA_METRICS_H_ +#define NINJA_METRICS_H_ + #include <string> #include <vector> using namespace std; @@ -62,3 +65,5 @@ private: ScopedMetric metrics_h_scoped(metrics_h_metric); extern Metrics* g_metrics; + +#endif // NINJA_METRICS_H_ diff --git a/src/parsers.cc b/src/parsers.cc index c3844fb..bc76ba1 100644 --- a/src/parsers.cc +++ b/src/parsers.cc @@ -218,7 +218,7 @@ bool ManifestParser::ParseEdge(string* err) { ins.push_back(in); } - // Add all order-only deps, counting how many as we go. + // Add all implicit deps, counting how many as we go. int implicit = 0; if (lexer_.PeekToken(Lexer::PIPE)) { for (;;) { diff --git a/src/parsers_test.cc b/src/parsers_test.cc index c5151b8..fc83946 100644 --- a/src/parsers_test.cc +++ b/src/parsers_test.cc @@ -115,6 +115,23 @@ TEST_F(ParserTest, ResponseFiles) { EXPECT_EQ("[$in]", rule->rspfile_content().Serialize()); } +TEST_F(ParserTest, InNewline) { + ASSERT_NO_FATAL_FAILURE(AssertParse( +"rule cat_rsp\n" +" command = cat $in_newline > $out\n" +"\n" +"build out: cat_rsp in in2\n" +" rspfile=out.rsp\n")); + + ASSERT_EQ(2u, state.rules_.size()); + const Rule* rule = state.rules_.begin()->second; + EXPECT_EQ("cat_rsp", rule->name()); + EXPECT_EQ("[cat ][$in_newline][ > ][$out]", rule->command().Serialize()); + + Edge* edge = state.edges_[0]; + EXPECT_EQ("cat in\nin2 > out", edge->EvaluateCommand()); +} + TEST_F(ParserTest, Variables) { ASSERT_NO_FATAL_FAILURE(AssertParse( "l = one-letter-test\n" diff --git a/src/test.cc b/src/test.cc index 2fbb4df..afedd10 100644 --- a/src/test.cc +++ b/src/test.cc @@ -18,6 +18,7 @@ #include <errno.h> +#include "build_log.h" #include "parsers.h" #include "util.h" @@ -89,6 +90,10 @@ void AssertParse(State* state, const char* input) { ASSERT_EQ("", err); } +void AssertHash(const char* expected, uint64_t actual) { + ASSERT_EQ(BuildLog::LogEntry::HashCommand(expected), actual); +} + void VirtualFileSystem::Create(const string& path, int time, const string& contents) { files_[path].mtime = time; @@ -35,6 +35,7 @@ struct StateTestWithBuiltinRules : public testing::Test { }; void AssertParse(State* state, const char* input); +void AssertHash(const char* expected, uint64_t actual); /// An implementation of DiskInterface that uses an in-memory representation /// of disk state. It also logs file accesses and directory creations @@ -77,6 +77,7 @@ double GetLoadAverage(); #define fileno _fileno #define unlink _unlink #define chdir _chdir +#define strtoull _strtoui64 #endif #ifdef _WIN32 |