src/deps_log.h

   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 using namespace std;
  21
  22 #include <stdio.h>
  23
  24 #include "load_status.h"
  25 #include "timestamp.h"
  26
  27 struct Node;
  28 struct State;
  29
  30 /// As build commands run they can output extra dependency information
  31 /// (e.g. header dependencies for C source) dynamically.  DepsLog collects
  32 /// that information at build time and uses it for subsequent builds.
  33 ///
  34 /// The on-disk format is based on two primary design constraints:
  35 /// - it must be written to as a stream (during the build, which may be
  36 ///   interrupted);
  37 /// - it can be read all at once on startup.  (Alternative designs, where
  38 ///   it contains indexing information, were considered and discarded as
  39 ///   too complicated to implement; if the file is small than reading it
  40 ///   fully on startup is acceptable.)
  41 /// Here are some stats from the Windows Chrome dependency files, to
  42 /// help guide the design space.  The total text in the files sums to
  43 /// 90mb so some compression is warranted to keep load-time fast.
  44 /// There's about 10k files worth of dependencies that reference about
  45 /// 40k total paths totalling 2mb of unique strings.
  46 ///
  47 /// Based on these stats, here's the current design.
  48 /// The file is structured as version header followed by a sequence of records.
  49 /// Each record is either a path string or a dependency list.
  50 /// Numbering the path strings in file order gives them dense integer ids.
  51 /// A dependency list maps an output id to a list of input ids.
  52 ///
  53 /// Concretely, a record is:
  54 ///    four bytes record length, high bit indicates record type
  55 ///      (but max record sizes are capped at 512kB)
  56 ///    path records contain the string name of the path, followed by up to 3
  57 ///      padding bytes to align on 4 byte boundaries, followed by the
  58 ///      one's complement of the expected index of the record (to detect
  59 ///      concurrent writes of multiple ninja processes to the log).
  60 ///    dependency records are an array of 4-byte integers
  61 ///      [output path id,
  62 ///       output path mtime (lower 4 bytes), output path mtime (upper 4 bytes),
  63 ///       input path id, input path id...]
  64 ///      (The mtime is compared against the on-disk output path mtime
  65 ///      to verify the stored data is up-to-date.)
  66 /// If two records reference the same output the latter one in the file
  67 /// wins, allowing updates to just be appended to the file.  A separate
  68 /// repacking step can run occasionally to remove dead records.
  69 struct DepsLog {
  70   DepsLog() : needs_recompaction_(false), file_(NULL) {}
  71   ~DepsLog();
  72
  73   // Writing (build-time) interface.
  74   bool OpenForWrite(const string& path, string* err);
  75   bool RecordDeps(Node* node, TimeStamp mtime, const vector<Node*>& nodes);
  76   bool RecordDeps(Node* node, TimeStamp mtime, int node_count, Node** nodes);
  77   void Close();
  78
  79   // Reading (startup-time) interface.
  80   struct Deps {
  81     Deps(int64_t mtime, int node_count)
  82         : mtime(mtime), node_count(node_count), nodes(new Node*[node_count]) {}
  83     ~Deps() { delete [] nodes; }
  84     TimeStamp mtime;
  85     int node_count;
  86     Node** nodes;
  87   };
  88   LoadStatus Load(const string& path, State* state, string* err);
  89   Deps* GetDeps(Node* node);
  90
  91   /// Rewrite the known log entries, throwing away old data.
  92   bool Recompact(const string& path, 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.
 103   const vector<Node*>& nodes() const { return nodes_; }
 104   const 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   vector<Node*> nodes_;
 123   /// Maps id -> deps of that id.
 124   vector<Deps*> deps_;
 125
 126   friend struct DepsLogTest;
 127 };
 128
 129 #endif  // NINJA_DEPS_LOG_H_