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
26struct Node;
27struct 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.
68struct DepsLog {
69 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 {
80 Deps(int64_t mtime, int node_count)
81 : mtime(mtime), node_count(node_count), nodes(new Node*[node_count]) {}
82 ~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 static bool IsDepsEntryLiveFor(const Node* node);
101
102 /// Used for tests.
103 const std::vector<Node*>& nodes() const { return nodes_; }
104 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