1 /*
2 * Copyright (c) 2015-2016, Intel Corporation
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * * Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Intel Corporation nor the names of its contributors
13 * may be used to endorse or promote products derived from this software
14 * without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 /** \file
30 * \brief Add redundancy to graph to assist in SOM analysis.
31 *
32 * Currently patterns of the form:
33 *
34 * /(GET|POST).*foo/
35 *
36 * baffle our SOM analysis as the T's get merged into one by our graph
37 * reductions and they lose the fixed depth property. One way to solve this is
38 * to tell the T vertex to go fork itself before we do the main SOM pass.
39 *
40 * Overall plan:
41 *
42 * 1. build a topo ordering
43 * 2. walk vertices in topo order
44 * 3. fix up vertices where possible
45 * 4. go home
46 *
47 * Vertex fix up plan:
48 *
49 * 1. consider depth of vertex
50 * - if vertex is at fixed depth continue to next vertex
51 * - if vertex can be at an unbounded depth continue to next vertex
52 * - if vertex has a pred which is not a fixed depth continue to next vertex
53 * 2. group preds by their depth
54 * 3. for each group:
55 * - create a clone of the vertex (vertex props and out edges)
56 * - create edges from each vertex in the group to the clone
57 * - work out the depth for the clone
58 * 4. blow away original vertex
59 *
60 * Originally in UE-1862.
61 */
62 #include "ng_som_add_redundancy.h"
63
64 #include "ng_dump.h"
65 #include "ng_holder.h"
66 #include "ng_util.h"
67 #include "ue2common.h"
68 #include "util/container.h"
69 #include "util/depth.h"
70 #include "util/graph.h"
71 #include "util/graph_range.h"
72
73 using namespace std;
74
75 namespace ue2 {
76
77 /** \brief Hard limit on the maximum number of new vertices to create. */
78 static const size_t MAX_NEW_VERTICES = 32;
79
80 static
getDepth(NFAVertex v,const NGHolder & g,const vector<DepthMinMax> & depths)81 const DepthMinMax &getDepth(NFAVertex v, const NGHolder &g,
82 const vector<DepthMinMax> &depths) {
83 return depths.at(g[v].index);
84 }
85
86 static
hasFloatingPred(NFAVertex v,const NGHolder & g,const vector<DepthMinMax> & depths)87 bool hasFloatingPred(NFAVertex v, const NGHolder &g,
88 const vector<DepthMinMax> &depths) {
89 for (auto u : inv_adjacent_vertices_range(v, g)) {
90 const DepthMinMax &d = getDepth(u, g, depths);
91 if (d.min != d.max) {
92 return true;
93 }
94 }
95 return false;
96 }
97
98 static
forkVertex(NFAVertex v,NGHolder & g,vector<DepthMinMax> & depths,set<NFAVertex> & dead,size_t * numNewVertices)99 bool forkVertex(NFAVertex v, NGHolder &g, vector<DepthMinMax> &depths,
100 set<NFAVertex> &dead, size_t *numNewVertices) {
101 map<depth, vector<NFAEdge>> predGroups;
102 for (const auto &e : in_edges_range(v, g)) {
103 const DepthMinMax &d = getDepth(source(e, g), g, depths);
104 assert(d.min == d.max);
105 predGroups[d.min].push_back(e);
106 }
107
108 DEBUG_PRINTF("forking vertex with %zu pred groups\n", predGroups.size());
109
110 if (*numNewVertices + predGroups.size() > MAX_NEW_VERTICES) {
111 return false;
112 }
113 *numNewVertices += predGroups.size();
114
115 for (auto &group : predGroups) {
116 const depth &predDepth = group.first;
117 const vector<NFAEdge> &preds = group.second;
118
119 // Clone v for this depth with all its associated out-edges.
120 u32 clone_idx = depths.size(); // next index to be used
121 NFAVertex clone = add_vertex(g[v], g);
122 depth clone_depth = predDepth + 1;
123 g[clone].index = clone_idx;
124 depths.push_back(DepthMinMax(clone_depth, clone_depth));
125 DEBUG_PRINTF("cloned vertex %u with depth %s\n", clone_idx,
126 clone_depth.str().c_str());
127
128 // Add copies of the out-edges from v.
129 for (const auto &e : out_edges_range(v, g)) {
130 add_edge(clone, target(e, g), g[e], g);
131 }
132
133 // Add in-edges from preds in this group.
134 for (const auto &e : preds) {
135 add_edge(source(e, g), clone, g[e], g);
136 }
137 }
138
139 clear_vertex(v, g);
140 dead.insert(v);
141 return true;
142 }
143
addSomRedundancy(NGHolder & g,vector<DepthMinMax> & depths)144 bool addSomRedundancy(NGHolder &g, vector<DepthMinMax> &depths) {
145 DEBUG_PRINTF("entry\n");
146
147 const vector<NFAVertex> ordering = getTopoOrdering(g);
148
149 set<NFAVertex> dead;
150 size_t numNewVertices = 0;
151
152 for (auto it = ordering.rbegin(), ite = ordering.rend(); it != ite; ++it) {
153 NFAVertex v = *it;
154
155 if (is_special(v, g)) {
156 continue;
157 }
158 if (!in_degree(v, g)) {
159 continue; // unreachable, probably killed
160 }
161
162 const DepthMinMax &d = getDepth(v, g, depths);
163
164 DEBUG_PRINTF("vertex %zu has depths %s\n", g[v].index,
165 d.str().c_str());
166
167 if (d.min == d.max) {
168 DEBUG_PRINTF("fixed depth\n");
169 continue;
170 }
171
172 if (d.max.is_unreachable()) {
173 DEBUG_PRINTF("unbounded depth\n");
174 continue;
175 }
176
177 if (hasFloatingPred(v, g, depths)) {
178 DEBUG_PRINTF("has floating pred\n");
179 continue;
180 }
181
182 if (!forkVertex(v, g, depths, dead, &numNewVertices)) {
183 DEBUG_PRINTF("new vertex limit reached\n");
184 break;
185 }
186 }
187
188 assert(numNewVertices <= MAX_NEW_VERTICES);
189
190 if (dead.empty()) {
191 return false; // no changes made to the graph
192 }
193
194 remove_vertices(dead, g);
195 return true;
196 }
197
198 } // namespace ue2
199