Timer/src/ProcessCallGraph.cc

0001 /*
0002  *
0003  */
0004
0005 #include <cassert>
0006 #include <iostream>
0007 #include <string>
0008 #include <type_traits>
0009 #include <vector>
0010
0011 // boost optional (used by boost graph) results in some false positives with -Wmaybe-uninitialized
0012 #pragma GCC diagnostic push
0013 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
0014 #include <boost/graph/depth_first_search.hpp>
0015 #pragma GCC diagnostic pop
0016
0017 #include "DataFormats/Provenance/interface/ModuleDescription.h"
0018 #include "FWCore/Framework/interface/TriggerNamesService.h"
0019 #include "FWCore/MessageLogger/interface/MessageLogger.h"
0020 #include "FWCore/ParameterSet/interface/ConfigurationDescriptions.h"
0021 #include "FWCore/ParameterSet/interface/ParameterSet.h"
0022 #include "FWCore/ParameterSet/interface/ParameterSetDescription.h"
0023 #include "FWCore/ParameterSet/interface/Registry.h"
0024 #include "FWCore/ServiceRegistry/interface/ActivityRegistry.h"
0025 #include "FWCore/ServiceRegistry/interface/ConsumesInfo.h"
0026 #include "FWCore/ServiceRegistry/interface/PathsAndConsumesOfModulesBase.h"
0027 #include "FWCore/ServiceRegistry/interface/ProcessContext.h"
0028 #include "FWCore/ServiceRegistry/interface/Service.h"
0029 #include "FWCore/Utilities/interface/EDMException.h"
0030 #include "HLTrigger/Timer/interface/ProcessCallGraph.h"
0031
0032 // adaptor to use range-based for loops with boost::graph edges(...) and vertices(...) functions
0033 template <typename I>
0034 struct iterator_pair_as_a_range : std::pair<I, I> {
0035 public:
0036   using std::pair<I, I>::pair;
0037
0038   I begin() { return this->first; }
0039   I end() { return this->second; }
0040 };
0041
0042 template <typename I>
0043 iterator_pair_as_a_range<I> make_range(std::pair<I, I> p) {
0044   return iterator_pair_as_a_range<I>(p);
0045 }
0046
0047 void ProcessCallGraph::preSourceConstruction(edm::ModuleDescription const& module) {
0048   // check that the Source has not already been added
0049   assert(source_ == edm::ModuleDescription::invalidID());
0050
0051   // keep track of the Source module id
0052   source_ = module.id();
0053
0054   // create graph vertex for the source module
0055   boost::add_vertex(graph_);
0056   graph_.m_graph[module.id()] = {module, edm::EDMModuleType::kSource, true};
0057 }
0058
0059 // FIXME
0060 //  - check that all module ids are valid (e.g. subprocesses are not being added in
0061 //    the wrong order)
0062 void ProcessCallGraph::preBeginJob(edm::PathsAndConsumesOfModulesBase const& pathsAndConsumes,
0063                                    edm::ProcessContext const& context) {
0064   unsigned int pid = registerProcess(context);
0065
0066   // check that the Source has already been added
0067   assert(source_ != edm::ModuleDescription::invalidID());
0068
0069   // work on the full graph (for the main process) or a subgraph (for a subprocess)
0070   GraphType& graph = context.isSubProcess() ? graph_.create_subgraph() : graph_.root();
0071
0072   // set the graph name property to the process name
0073   boost::get_property(graph, boost::graph_name) = context.processName();
0074
0075   // create graph vertices associated to all modules in the process
0076   unsigned int size = pathsAndConsumes.largestModuleID() - boost::num_vertices(graph) + 1;
0077   for (size_t i = 0; i < size; ++i)
0078     boost::add_vertex(graph);
0079
0080   // set the vertices properties (use the module id as the global index into the graph)
0081   std::vector<unsigned int> modules;
0082   modules.reserve(size);
0083   for (edm::ModuleDescription const* module : pathsAndConsumes.allModules()) {
0084     modules.push_back(module->id());
0085     graph_.m_graph[module->id()] = {*module, edmModuleTypeEnum(*module), false};
0086   }
0087
0088   // add graph edges associated to module dependencies
0089   for (edm::ModuleDescription const* consumer : pathsAndConsumes.allModules()) {
0090     for (edm::ModuleDescription const* module : pathsAndConsumes.modulesWhoseProductsAreConsumedBy(consumer->id())) {
0091       // module `consumer' depends on module `module'
0092       boost::add_edge(consumer->id(), module->id(), graph_);
0093     }
0094   }
0095
0096   // extract path names from the TriggerNamesService
0097   edm::service::TriggerNamesService const& tns = *edm::Service<edm::service::TriggerNamesService>();
0098
0099   // extract the details of the paths and endpaths: name, modules on the path, and their dependencies
0100   size = pathsAndConsumes.paths().size();
0101   assert(tns.getTrigPaths().size() == size);
0102   std::vector<PathType> paths;
0103   paths.reserve(size);
0104   for (unsigned int i = 0; i < size; ++i) {
0105     std::vector<unsigned int> modules;
0106     for (edm::ModuleDescription const* module : pathsAndConsumes.modulesOnPath(i)) {
0107       modules.push_back(module->id());
0108       // mark the modules in the Paths as scheduled
0109       graph_.m_graph[module->id()].scheduled_ = true;
0110     }
0111     auto deps = dependencies(modules);
0112     paths.emplace_back(tns.getTrigPath(i), modules, deps.first, deps.second);
0113   }
0114   size = pathsAndConsumes.endPaths().size();
0115   std::vector<PathType> endPaths;
0116   endPaths.reserve(size);
0117   for (unsigned int i = 0; i < size; ++i) {
0118     std::vector<unsigned int> modules;
0119     for (edm::ModuleDescription const* module : pathsAndConsumes.modulesOnEndPath(i)) {
0120       modules.push_back(module->id());
0121       // mark the modules in the EndPaths as scheduled
0122       graph_.m_graph[module->id()].scheduled_ = true;
0123     }
0124     auto deps = dependencies(modules);
0125     endPaths.emplace_back(tns.getEndPath(i), modules, deps.first, deps.second);
0126   }
0127
0128   // store the description of process, modules and paths
0129   process_description_.emplace_back(context.processName(), graph, modules, paths, endPaths);
0130   assert(process_description_.size() == pid + 1);
0131
0132   // attach a subprocess to its parent
0133   if (context.isSubProcess()) {
0134     unsigned int parent_pid = processId(context.parentProcessContext());
0135     process_description_[parent_pid].subprocesses_.push_back(pid);
0136   }
0137 }
0138
0139 // number of modules stored in the call graph
0140 unsigned int ProcessCallGraph::size() const { return boost::num_vertices(graph_); }
0141
0142 // retrieve the ModuleDescriptio associated to the given id and vertex
0143 edm::ModuleDescription const& ProcessCallGraph::source() const { return graph_.m_graph[source_].module_; }
0144
0145 // retrieve the ModuleDescription associated to the given id and vertex
0146 edm::ModuleDescription const& ProcessCallGraph::module(unsigned int module) const {
0147   return graph_.m_graph[module].module_;
0148 }
0149
0150 // retrieve the full information for a given module
0151 ProcessCallGraph::NodeType const& ProcessCallGraph::operator[](unsigned int module) const {
0152   return graph_.m_graph[module];
0153 }
0154
0155 // find the dependencies of the given module
0156 std::vector<unsigned int> ProcessCallGraph::depends(unsigned int module) const {
0157   std::vector<unsigned int> colors(boost::num_vertices(graph_));
0158   auto colormap = boost::make_container_vertex_map(colors);
0159
0160   // depht-first visit all vertices starting from the given module
0161   boost::default_dfs_visitor visitor;
0162   boost::depth_first_visit(graph_, module, visitor, colormap);
0163
0164   // count the visited vertices (the `black' ones) in order to properly size the
0165   // output vector; then fill the dependencies with the list of visited nodes
0166   unsigned int size = 0;
0167   for (unsigned int color : colors)
0168     if (boost::black_color == color)
0169       ++size;
0170   std::vector<unsigned int> dependencies(size);
0171   unsigned j = 0;
0172   for (unsigned int i = 0; i < colors.size(); ++i)
0173     if (boost::black_color == colors[i])
0174       dependencies[j++] = i;
0175   assert(size == j);
0176
0177   return dependencies;
0178 }
0179
0180 // find the dependencies of all modules in the given path
0181 //
0182 // return two vector:
0183 //   - the first lists all the dependencies for the whole path
0184 //   - the second lists the one-after-the-last dependency index into the first vector for each module
0185 std::pair<std::vector<unsigned int>, std::vector<unsigned int>> ProcessCallGraph::dependencies(
0186     std::vector<unsigned int> const& path) {
0187   std::vector<unsigned int> colors(boost::num_vertices(graph_));
0188   auto colormap = boost::make_container_vertex_map(colors);
0189
0190   // first, find and count all the path's modules' dependencies
0191   boost::default_dfs_visitor visitor;
0192   for (unsigned int module : path)
0193     boost::depth_first_visit(graph_, module, visitor, colormap);
0194
0195   unsigned int size = 0;
0196   for (unsigned int color : colors)
0197     if (color == 0)
0198       ++size;
0199
0200   // allocate the output vectors
0201   std::vector<unsigned int> dependencies(size);
0202   dependencies.resize(0);
0203   std::vector<unsigned int> indices(path.size());
0204   indices.resize(0);
0205
0206   // reset the color map
0207   for (unsigned int& color : colors)
0208     color = 0;
0209
0210   // find again all the dependencies, and record those associated to each module
0211   struct record_vertices : boost::default_dfs_visitor {
0212     record_vertices(std::vector<unsigned int>& vertices) : vertices_(vertices) {}
0213
0214     void discover_vertex(unsigned int vertex, GraphType const& graph) { vertices_.push_back(vertex); }
0215
0216     std::vector<unsigned int>& vertices_;
0217   };
0218   record_vertices recorder(dependencies);
0219
0220   for (unsigned int module : path) {
0221     // skip modules that have already been added as dependencies
0222     if (colors[module] != boost::black_color)
0223       boost::depth_first_visit(graph_, module, recorder, colormap);
0224     indices.push_back(dependencies.size());
0225   }
0226
0227   return std::make_pair(dependencies, indices);
0228 }
0229
0230 // register a (sub)process and assigns it a "process id"
0231 // throws an exception if called with a duplicate process name
0232 unsigned int ProcessCallGraph::registerProcess(edm::ProcessContext const& context) {
0233   // registerProcess (called by preBeginJob) must be called for the parent process before its subprocess(es)
0234   if (context.isSubProcess() and process_id_.find(context.parentProcessContext().processName()) == process_id_.end()) {
0235     throw edm::Exception(edm::errors::LogicError)
0236         << "ProcessCallGraph::preBeginJob(): called for subprocess \"" << context.processName() << "\""
0237         << " before being called for its parent process \"" << context.parentProcessContext().processName() << "\"";
0238   }
0239
0240   // registerProcess (called by preBeginJob) should be called once or each (sub)process
0241   auto id = process_id_.find(context.processName());
0242   if (id != process_id_.end()) {
0243     throw edm::Exception(edm::errors::LogicError)
0244         << "ProcessCallGraph::preBeginJob(): called twice for the same "
0245         << (context.isSubProcess() ? "subprocess" : "process") << " " << context.processName();
0246   }
0247
0248   // this assumes that registerProcess (called by preBeginJob) is not called concurrently from different threads
0249   // otherwise, process_id_.size() should be replaces with an atomic counter
0250   std::tie(id, std::ignore) = process_id_.insert(std::make_pair(context.processName(), process_id_.size()));
0251   return id->second;
0252 }
0253
0254 // retrieve the "process id" of a process, given its ProcessContex
0255 // throws an exception if the (sub)process was not registered
0256 unsigned int ProcessCallGraph::processId(edm::ProcessContext const& context) const {
0257   auto id = process_id_.find(context.processName());
0258   if (id == process_id_.end())
0259     throw edm::Exception(edm::errors::LogicError)
0260         << "ProcessCallGraph::processId(): unexpected " << (context.isSubProcess() ? "subprocess" : "process") << " "
0261         << context.processName();
0262   return id->second;
0263 }
0264
0265 // retrieve the "process id" of a process, given its ProcessContex
0266 // throws an exception if the (sub)process was not registered
0267 unsigned int ProcessCallGraph::processId(std::string const& processName) const {
0268   auto id = process_id_.find(processName);
0269   if (id == process_id_.end())
0270     throw edm::Exception(edm::errors::LogicError)
0271         << "ProcessCallGraph::processId(): unexpected (sub)process " << processName;
0272   return id->second;
0273 }
0274
0275 // retrieve the number of processes
0276 std::vector<ProcessCallGraph::ProcessType> const& ProcessCallGraph::processes() const { return process_description_; }
0277
0278 // retrieve information about a process, given its "process id"
0279 ProcessCallGraph::ProcessType const& ProcessCallGraph::processDescription(unsigned int pid) const {
0280   return process_description_.at(pid);
0281 }
0282
0283 // retrieve information about a process, given its ProcessContex
0284 ProcessCallGraph::ProcessType const& ProcessCallGraph::processDescription(edm::ProcessContext const& context) const {
0285   unsigned int pid = processId(context);
0286   return process_description_[pid];
0287 }
0288
0289 // retrieve information about a process, given its ProcessContex
0290 ProcessCallGraph::ProcessType const& ProcessCallGraph::processDescription(std::string const& processName) const {
0291   unsigned int pid = processId(processName);
0292   return process_description_[pid];
0293 }