1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
/*
* Copyright 2022 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "packet_dependency.h"
#include <algorithm>
#include <list>
#include <set>
PacketDependency::PacketDependency(const ParentDef* root) {
std::map<std::string, std::set<std::string>> initial_parse_and_match_fields;
std::vector<std::string> available_fields;
CollectInitialParseAndMatchFields(root, initial_parse_and_match_fields);
FinalizeParseAndMatchFields(root, initial_parse_and_match_fields, available_fields);
}
std::vector<std::string>& PacketDependency::GetDependencies(const std::string& packet_name) {
return dependencies[packet_name];
}
std::vector<std::string>& PacketDependency::GetChildrenDependencies(
const std::string& packet_name) {
return children_dependencies[packet_name];
}
std::set<std::string> PacketDependency::CollectInitialParseAndMatchFields(
const ParentDef* parent,
std::map<std::string, std::set<std::string>>& initial_parse_and_match_fields) const {
// Case Leaf Packet: Return all of its constraints
if (parent->children_.empty()) {
auto constraints = parent->GetAllConstraints();
auto constraints_set = std::set<std::string>{};
for (auto& c : constraints) {
constraints_set.insert(c.first);
}
return constraints_set;
}
auto children_constraints = std::set<std::string>{};
auto parent_constraints = parent->GetAllConstraints();
auto parent_fields = parent->fields_;
for (const auto child : parent->children_) {
auto constraints = CollectInitialParseAndMatchFields(child, initial_parse_and_match_fields);
auto child_only_constraints = std::set<std::string>{};
for (auto c : constraints) {
// __PARENT__
// c1/ c2| \c3
// / | \.
// CH1 CH2 CH3
// c4|
// |
// CH11
// GetAllConstraints on leaf packet CH11 will return (C4, c1)
// GetAllConstraints on packet CH1 will return C1
// Thus CH11 only constraint is: (C4, C1) - (C1) => (C4)
if (parent_constraints.find(c) == parent_constraints.end()) {
child_only_constraints.insert(c);
}
// If the constraint can be satisfied by the immediate parent, no need to accumulate it
if (parent_fields.GetField(c) != nullptr) {
continue;
}
// Accumulate constraints from all the children so parent packet can accurately
// figure out which constraints it should be getting from its parents.
children_constraints.insert(c);
}
// child_only_constraints contains the variables required to be passed in when calling parse
initial_parse_and_match_fields[child->name_] = child_only_constraints;
}
return children_constraints;
}
void PacketDependency::FinalizeParseAndMatchFields(
const ParentDef* parent,
std::map<std::string, std::set<std::string>>& initial_parse_and_match_fields,
std::vector<std::string>& available_fields) {
// Root does not have any constraints on anything
if (parent->parent_ == nullptr) {
dependencies[parent->name_] = std::vector<std::string>{};
children_dependencies[parent->name_] = std::vector<std::string>{};
}
// Collect the available fields, required to fix the order of pass and match vectors
for (auto& pf : parent->fields_) {
available_fields.push_back(pf->GetName());
}
auto children_constraints_to_me = std::set<std::string>{};
children_dependencies[parent->name_] = std::vector<std::string>{};
// Accumulate direct constraints from all the children to parent
// __PARENT__
// c1/ c2| \c3
// / | \.
// CH1 CH2 CH3
// c4|
// |
// CH11
// For this case: children_constraints_to_me = (c1, c2, c3)
for (auto& child : parent->children_) {
for (auto pcons : child->parent_constraints_) {
children_constraints_to_me.insert(pcons.first);
}
}
// If children constraints to the parent are (c1, c2, c3) and so far parent has
// fields (c1, c2) available, then parent will match its children on (c1, c2)
for (auto avf : available_fields) {
if (children_constraints_to_me.find(avf) != children_constraints_to_me.end()) {
auto& match_variables = children_dependencies[parent->name_];
if (std::find(match_variables.begin(), match_variables.end(), avf) == match_variables.end()) {
match_variables.push_back(avf);
}
}
}
for (auto& child : parent->children_) {
auto child_initial_parse_params = initial_parse_and_match_fields[child->name_];
auto child_actual_parse_params = std::vector<std::string>{};
// Remove all the params from parse method of this child
// if these variables are the ones parent will match its children.
for (auto pcons : child->parent_constraints_) {
child_initial_parse_params.erase(pcons.first);
}
// Store unique vars from child_initial_parse_params to child_actual_parse_params
// in the same order as fields are defined in the packets
for (auto avf : available_fields) {
if (child_initial_parse_params.find(avf) != child_initial_parse_params.end()) {
child_actual_parse_params.push_back(avf);
}
}
dependencies[child->name_] = child_actual_parse_params;
FinalizeParseAndMatchFields(child, initial_parse_and_match_fields, available_fields);
}
}
|
