1 // Copyright 2012 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 #ifndef NINJA_DEPS_LOG_H_ 16 #define NINJA_DEPS_LOG_H_ 17 18 #include <string> 19 #include <vector> 20 21 #include <stdio.h> 22 23 #include "load_status.h" 24 #include "timestamp.h" 25 26 struct Node; 27 struct State; 28 29 /// As build commands run they can output extra dependency information 30 /// (e.g. header dependencies for C source) dynamically. DepsLog collects 31 /// that information at build time and uses it for subsequent builds. 32 /// 33 /// The on-disk format is based on two primary design constraints: 34 /// - it must be written to as a stream (during the build, which may be 35 /// interrupted); 36 /// - it can be read all at once on startup. (Alternative designs, where 37 /// it contains indexing information, were considered and discarded as 38 /// too complicated to implement; if the file is small than reading it 39 /// fully on startup is acceptable.) 40 /// Here are some stats from the Windows Chrome dependency files, to 41 /// help guide the design space. The total text in the files sums to 42 /// 90mb so some compression is warranted to keep load-time fast. 43 /// There's about 10k files worth of dependencies that reference about 44 /// 40k total paths totalling 2mb of unique strings. 45 /// 46 /// Based on these stats, here's the current design. 47 /// The file is structured as version header followed by a sequence of records. 48 /// Each record is either a path string or a dependency list. 49 /// Numbering the path strings in file order gives them dense integer ids. 50 /// A dependency list maps an output id to a list of input ids. 51 /// 52 /// Concretely, a record is: 53 /// four bytes record length, high bit indicates record type 54 /// (but max record sizes are capped at 512kB) 55 /// path records contain the string name of the path, followed by up to 3 56 /// padding bytes to align on 4 byte boundaries, followed by the 57 /// one's complement of the expected index of the record (to detect 58 /// concurrent writes of multiple ninja processes to the log). 59 /// dependency records are an array of 4-byte integers 60 /// [output path id, 61 /// output path mtime (lower 4 bytes), output path mtime (upper 4 bytes), 62 /// input path id, input path id...] 63 /// (The mtime is compared against the on-disk output path mtime 64 /// to verify the stored data is up-to-date.) 65 /// If two records reference the same output the latter one in the file 66 /// wins, allowing updates to just be appended to the file. A separate 67 /// repacking step can run occasionally to remove dead records. 68 struct DepsLog { DepsLogDepsLog69 DepsLog() : needs_recompaction_(false), file_(NULL) {} 70 ~DepsLog(); 71 72 // Writing (build-time) interface. 73 bool OpenForWrite(const std::string& path, std::string* err); 74 bool RecordDeps(Node* node, TimeStamp mtime, const std::vector<Node*>& nodes); 75 bool RecordDeps(Node* node, TimeStamp mtime, int node_count, Node** nodes); 76 void Close(); 77 78 // Reading (startup-time) interface. 79 struct Deps { DepsDepsLog::Deps80 Deps(int64_t mtime, int node_count) 81 : mtime(mtime), node_count(node_count), nodes(new Node*[node_count]) {} ~DepsDepsLog::Deps82 ~Deps() { delete [] nodes; } 83 TimeStamp mtime; 84 int node_count; 85 Node** nodes; 86 }; 87 LoadStatus Load(const std::string& path, State* state, std::string* err); 88 Deps* GetDeps(Node* node); 89 Node* GetFirstReverseDepsNode(Node* node); 90 91 /// Rewrite the known log entries, throwing away old data. 92 bool Recompact(const std::string& path, std::string* err); 93 94 /// Returns if the deps entry for a node is still reachable from the manifest. 95 /// 96 /// The deps log can contain deps entries for files that were built in the 97 /// past but are no longer part of the manifest. This function returns if 98 /// this is the case for a given node. This function is slow, don't call 99 /// it from code that runs on every build. 100 bool IsDepsEntryLiveFor(Node* node); 101 102 /// Used for tests. nodesDepsLog103 const std::vector<Node*>& nodes() const { return nodes_; } depsDepsLog104 const std::vector<Deps*>& deps() const { return deps_; } 105 106 private: 107 // Updates the in-memory representation. Takes ownership of |deps|. 108 // Returns true if a prior deps record was deleted. 109 bool UpdateDeps(int out_id, Deps* deps); 110 // Write a node name record, assigning it an id. 111 bool RecordId(Node* node); 112 113 /// Should be called before using file_. When false is returned, errno will 114 /// be set. 115 bool OpenForWriteIfNeeded(); 116 117 bool needs_recompaction_; 118 FILE* file_; 119 std::string file_path_; 120 121 /// Maps id -> Node. 122 std::vector<Node*> nodes_; 123 /// Maps id -> deps of that id. 124 std::vector<Deps*> deps_; 125 126 friend struct DepsLogTest; 127 }; 128 129 #endif // NINJA_DEPS_LOG_H_ 130