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 |
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 |
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 |
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 | |
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 | |