1 2 /** 3 * Copyright (C) 2018-present MongoDB, Inc. 4 * 5 * This program is free software: you can redistribute it and/or modify 6 * it under the terms of the Server Side Public License, version 1, 7 * as published by MongoDB, Inc. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * Server Side Public License for more details. 13 * 14 * You should have received a copy of the Server Side Public License 15 * along with this program. If not, see 16 * <http://www.mongodb.com/licensing/server-side-public-license>. 17 * 18 * As a special exception, the copyright holders give permission to link the 19 * code of portions of this program with the OpenSSL library under certain 20 * conditions as described in each individual source file and distribute 21 * linked combinations including the program with the OpenSSL library. You 22 * must comply with the Server Side Public License in all respects for 23 * all of the code used other than as permitted herein. If you modify file(s) 24 * with this exception, you may extend this exception to your version of the 25 * file(s), but you are not obligated to do so. If you do not wish to do so, 26 * delete this exception statement from your version. If you delete this 27 * exception statement from all source files in the program, then also delete 28 * it in the license file. 29 */ 30 #pragma once 31 32 #include <boost/optional.hpp> 33 #include <vector> 34 35 #include "mongo/base/status.h" 36 #include "mongo/db/namespace_string.h" 37 #include "mongo/db/query/collation/collator_interface.h" 38 #include "mongo/stdx/unordered_map.h" 39 #include "mongo/stdx/unordered_set.h" 40 #include "mongo/util/string_map.h" 41 42 namespace mongo { 43 class ViewDefinition; 44 45 /** 46 * Represents the dependencies of views on other namespaces and validates that this graph is acyclic 47 * and smaller than the maximum diameter. It also checks that the views in each connected component 48 * have compatible collations, and that all possible view pipelines stay within the maximum size in 49 * bytes. 50 * 51 * This is owned and managed by the ViewCatalog. 52 */ 53 class ViewGraph { 54 MONGO_DISALLOW_COPYING(ViewGraph); 55 56 public: 57 static const int kMaxViewDepth; 58 static const int kMaxViewPipelineSizeBytes; 59 60 ViewGraph() = default; 61 62 /** 63 * Inserts a new node for 'view' in the graph, which must not already be present. 'refs' 64 * contains the list of namespaces referred to by the view in its "viewOn" or "pipeline". 65 * 'pipelineSize' is the size of the view's pipeline, in bytes. If inserting the view would 66 * violate one of the graph's validity properties, the insertion is reverted and a non-OK status 67 * is returned. 68 * 69 * This method is intended for validating a view that is created or modified by a user 70 * operation. 71 */ 72 Status insertAndValidate(const ViewDefinition& view, 73 const std::vector<NamespaceString>& refs, 74 int pipelineSize); 75 76 /** 77 * Like insertAndValidate(), inserts a new node for 'view' in the graph, which must not already 78 * be present. However, no validation is performed. The insertion is not rolled back even if it 79 * puts the graph into an invalid state. 80 * 81 * This method is intended for quickly repopulating the graph with view definitions that are 82 * assumed to be already valid. 83 */ 84 void insertWithoutValidating(const ViewDefinition& view, 85 const std::vector<NamespaceString>& refs, 86 int pipelineSize); 87 88 /** 89 * Called when a view is removed from the catalog. If the view does not exist in the graph it is 90 * a no-op. The view may also have a cycle or max diameter through it. 91 */ 92 void remove(const NamespaceString& viewNss); 93 94 /** 95 * Deletes the view graph and all references to namespaces. 96 */ 97 void clear(); 98 99 /** 100 * Returns the number of namespaces tracked by the view graph. Only exposed for testing. 101 */ 102 size_t size() const; 103 104 private: 105 // A graph node represents a namespace. We say that a node A is a parent of B if A is a view and 106 // it references B via its "viewOn" or $lookup/$graphLookup/$facet in its "pipeline". 107 // 108 // This node represents a view namespace if and only if 'children' is nonempty and 'collator' is 109 // set. 110 struct Node { 111 /** 112 * Returns true if this node represents a view. 113 */ isViewNode114 bool isView() const { 115 invariant(children.empty() == !static_cast<bool>(collator)); 116 return !children.empty(); 117 } 118 119 // The fully-qualified namespace that this node represents. 120 std::string ns; 121 122 // Represents the namespaces depended on by this view. A view may refer to the same child 123 // more than once, but we store the children as a set because each namespace need not be 124 // traversed more than once. 125 stdx::unordered_set<uint64_t> children; 126 127 // Represents the views that depend on this namespace. 128 stdx::unordered_set<uint64_t> parents; 129 130 // When set, this is an unowned pointer to the view's collation, or nullptr if the view has 131 // the binary collation. When not set, this namespace is not a view and we don't care about 132 // its collator. 133 boost::optional<const CollatorInterface*> collator; 134 135 // The size of this view's "pipeline", in bytes. 136 int size = 0; 137 }; 138 139 // Bookkeeping for graph traversals. 140 struct NodeStats { 141 bool checked = false; 142 int height = 0; 143 int cumulativeSize = 0; 144 }; 145 146 using StatsMap = stdx::unordered_map<uint64_t, NodeStats>; 147 148 /** 149 * Recursively validates the parents of 'currentId', filling out statistics about the node 150 * represented by that id in 'statsMap'. The recursion level is tracked in 'currentDepth' to 151 * limit recursive calls. 152 * 153 * A non-OK status is returned if 'currentId' or its parents violate any of the graph's 154 * validity properties. 155 */ 156 Status _validateParents(uint64_t currentId, int currentDepth, StatsMap* statsMap); 157 158 /** 159 * Recursively validates the children of 'currentId', filling out statistics about the node 160 * represented by that id in 'statsMap'. The recursion level is tracked in 'currentDepth' to 161 * limit recursive calls. Both 'startingId' and 'traversalIds' are used to detect cycles. 162 * 163 * A non-OK status is returned if 'currentId' or its children violate any of the graph's 164 * validity properties. 165 */ 166 Status _validateChildren(uint64_t startingId, 167 uint64_t currentId, 168 int currentDepth, 169 StatsMap* statsMap, 170 std::vector<uint64_t>* traversalIds); 171 172 /** 173 * Gets the id for this namespace, and creates an id if it doesn't exist. 174 */ 175 uint64_t _getNodeId(const NamespaceString& ns); 176 177 // Maps namespaces to an internal node id. A mapping exists for every namespace referenced, 178 // i.e. existing views, collections, and non-existing namespaces. 179 StringMap<uint64_t> _namespaceIds; 180 181 // Maps node ids to nodes. There is a 1-1 correspondence with _namespaceIds, hence the lifetime 182 // of a node is the same as the lifetime as its corresponding node id. 183 stdx::unordered_map<uint64_t, Node> _graph; 184 uint64_t _idCounter = 0; 185 }; 186 } // namespace mongo 187