1 /*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 #define DEBUG false // STOPSHIP if true
17 #include "Log.h"
18
19 #include "frameworks/base/cmds/statsd/src/statsd_config.pb.h"
20 #include "matchers/LogMatchingTracker.h"
21 #include "matchers/matcher_util.h"
22 #include "stats_util.h"
23
24 using std::set;
25 using std::string;
26 using std::unordered_map;
27 using std::vector;
28
29 namespace android {
30 namespace os {
31 namespace statsd {
32
combinationMatch(const vector<int> & children,const LogicalOperation & operation,const vector<MatchingState> & matcherResults)33 bool combinationMatch(const vector<int>& children, const LogicalOperation& operation,
34 const vector<MatchingState>& matcherResults) {
35 bool matched;
36 switch (operation) {
37 case LogicalOperation::AND: {
38 matched = true;
39 for (const int childIndex : children) {
40 if (matcherResults[childIndex] != MatchingState::kMatched) {
41 matched = false;
42 break;
43 }
44 }
45 break;
46 }
47 case LogicalOperation::OR: {
48 matched = false;
49 for (const int childIndex : children) {
50 if (matcherResults[childIndex] == MatchingState::kMatched) {
51 matched = true;
52 break;
53 }
54 }
55 break;
56 }
57 case LogicalOperation::NOT:
58 matched = matcherResults[children[0]] == MatchingState::kNotMatched;
59 break;
60 case LogicalOperation::NAND:
61 matched = false;
62 for (const int childIndex : children) {
63 if (matcherResults[childIndex] != MatchingState::kMatched) {
64 matched = true;
65 break;
66 }
67 }
68 break;
69 case LogicalOperation::NOR:
70 matched = true;
71 for (const int childIndex : children) {
72 if (matcherResults[childIndex] == MatchingState::kMatched) {
73 matched = false;
74 break;
75 }
76 }
77 break;
78 case LogicalOperation::LOGICAL_OPERATION_UNSPECIFIED:
79 matched = false;
80 break;
81 }
82 return matched;
83 }
84
tryMatchString(const UidMap & uidMap,const Field & field,const Value & value,const string & str_match)85 bool tryMatchString(const UidMap& uidMap, const Field& field, const Value& value,
86 const string& str_match) {
87 if (isAttributionUidField(field, value)) {
88 int uid = value.int_value;
89 auto aidIt = UidMap::sAidToUidMapping.find(str_match);
90 if (aidIt != UidMap::sAidToUidMapping.end()) {
91 return ((int)aidIt->second) == uid;
92 }
93 std::set<string> packageNames = uidMap.getAppNamesFromUid(uid, true /* normalize*/);
94 return packageNames.find(str_match) != packageNames.end();
95 } else if (value.getType() == STRING) {
96 return value.str_value == str_match;
97 }
98 return false;
99 }
100
matchesSimple(const UidMap & uidMap,const FieldValueMatcher & matcher,const vector<FieldValue> & values,int start,int end,int depth)101 bool matchesSimple(const UidMap& uidMap, const FieldValueMatcher& matcher,
102 const vector<FieldValue>& values, int start, int end, int depth) {
103 if (depth > 2) {
104 ALOGE("Depth > 3 not supported");
105 return false;
106 }
107
108 if (start >= end) {
109 return false;
110 }
111
112 // Filter by entry field first
113 int newStart = -1;
114 int newEnd = end;
115 // because the fields are naturally sorted in the DFS order. we can safely
116 // break when pos is larger than the one we are searching for.
117 for (int i = start; i < end; i++) {
118 int pos = values[i].mField.getPosAtDepth(depth);
119 if (pos == matcher.field()) {
120 if (newStart == -1) {
121 newStart = i;
122 }
123 newEnd = i + 1;
124 } else if (pos > matcher.field()) {
125 break;
126 }
127 }
128
129 // Now we have zoomed in to a new range
130 start = newStart;
131 end = newEnd;
132
133 if (start == -1) {
134 // No such field found.
135 return false;
136 }
137
138 vector<pair<int, int>> ranges; // the ranges are for matching ANY position
139 if (matcher.has_position()) {
140 // Repeated fields position is stored as a node in the path.
141 depth++;
142 if (depth > 2) {
143 return false;
144 }
145 switch (matcher.position()) {
146 case Position::FIRST: {
147 for (int i = start; i < end; i++) {
148 int pos = values[i].mField.getPosAtDepth(depth);
149 if (pos != 1) {
150 // Again, the log elements are stored in sorted order. so
151 // once the position is > 1, we break;
152 end = i;
153 break;
154 }
155 }
156 ranges.push_back(std::make_pair(start, end));
157 break;
158 }
159 case Position::LAST: {
160 // move the starting index to the first LAST field at the depth.
161 for (int i = start; i < end; i++) {
162 if (values[i].mField.isLastPos(depth)) {
163 start = i;
164 break;
165 }
166 }
167 ranges.push_back(std::make_pair(start, end));
168 break;
169 }
170 case Position::ANY: {
171 // ANY means all the children matchers match in any of the sub trees, it's a match
172 newStart = start;
173 newEnd = end;
174 // Here start is guaranteed to be a valid index.
175 int currentPos = values[start].mField.getPosAtDepth(depth);
176 // Now find all sub trees ranges.
177 for (int i = start; i < end; i++) {
178 int newPos = values[i].mField.getPosAtDepth(depth);
179 if (newPos != currentPos) {
180 ranges.push_back(std::make_pair(newStart, i));
181 newStart = i;
182 currentPos = newPos;
183 }
184 }
185 ranges.push_back(std::make_pair(newStart, end));
186 break;
187 }
188 case Position::ALL:
189 ALOGE("Not supported: field matcher with ALL position.");
190 break;
191 case Position::POSITION_UNKNOWN:
192 break;
193 }
194 } else {
195 // No position
196 ranges.push_back(std::make_pair(start, end));
197 }
198 // start and end are still pointing to the matched range.
199 switch (matcher.value_matcher_case()) {
200 case FieldValueMatcher::kMatchesTuple: {
201 ++depth;
202 // If any range matches all matchers, good.
203 for (const auto& range : ranges) {
204 bool matched = true;
205 for (const auto& subMatcher : matcher.matches_tuple().field_value_matcher()) {
206 if (!matchesSimple(uidMap, subMatcher, values, range.first, range.second,
207 depth)) {
208 matched = false;
209 break;
210 }
211 }
212 if (matched) return true;
213 }
214 return false;
215 }
216 // Finally, we get to the point of real value matching.
217 // If the field matcher ends with ANY, then we have [start, end) range > 1.
218 // In the following, we should return true, when ANY of the values matches.
219 case FieldValueMatcher::ValueMatcherCase::kEqBool: {
220 for (int i = start; i < end; i++) {
221 if ((values[i].mValue.getType() == INT &&
222 (values[i].mValue.int_value != 0) == matcher.eq_bool()) ||
223 (values[i].mValue.getType() == LONG &&
224 (values[i].mValue.long_value != 0) == matcher.eq_bool())) {
225 return true;
226 }
227 }
228 return false;
229 }
230 case FieldValueMatcher::ValueMatcherCase::kEqString: {
231 for (int i = start; i < end; i++) {
232 if (tryMatchString(uidMap, values[i].mField, values[i].mValue,
233 matcher.eq_string())) {
234 return true;
235 }
236 }
237 return false;
238 }
239 case FieldValueMatcher::ValueMatcherCase::kNeqAnyString: {
240 const auto& str_list = matcher.neq_any_string();
241 for (int i = start; i < end; i++) {
242 bool notEqAll = true;
243 for (const auto& str : str_list.str_value()) {
244 if (tryMatchString(uidMap, values[i].mField, values[i].mValue, str)) {
245 notEqAll = false;
246 break;
247 }
248 }
249 if (notEqAll) {
250 return true;
251 }
252 }
253 return false;
254 }
255 case FieldValueMatcher::ValueMatcherCase::kEqAnyString: {
256 const auto& str_list = matcher.eq_any_string();
257 for (int i = start; i < end; i++) {
258 for (const auto& str : str_list.str_value()) {
259 if (tryMatchString(uidMap, values[i].mField, values[i].mValue, str)) {
260 return true;
261 }
262 }
263 }
264 return false;
265 }
266 case FieldValueMatcher::ValueMatcherCase::kEqInt: {
267 for (int i = start; i < end; i++) {
268 if (values[i].mValue.getType() == INT &&
269 (matcher.eq_int() == values[i].mValue.int_value)) {
270 return true;
271 }
272 // eq_int covers both int and long.
273 if (values[i].mValue.getType() == LONG &&
274 (matcher.eq_int() == values[i].mValue.long_value)) {
275 return true;
276 }
277 }
278 return false;
279 }
280 case FieldValueMatcher::ValueMatcherCase::kLtInt: {
281 for (int i = start; i < end; i++) {
282 if (values[i].mValue.getType() == INT &&
283 (values[i].mValue.int_value < matcher.lt_int())) {
284 return true;
285 }
286 // lt_int covers both int and long.
287 if (values[i].mValue.getType() == LONG &&
288 (values[i].mValue.long_value < matcher.lt_int())) {
289 return true;
290 }
291 }
292 return false;
293 }
294 case FieldValueMatcher::ValueMatcherCase::kGtInt: {
295 for (int i = start; i < end; i++) {
296 if (values[i].mValue.getType() == INT &&
297 (values[i].mValue.int_value > matcher.gt_int())) {
298 return true;
299 }
300 // gt_int covers both int and long.
301 if (values[i].mValue.getType() == LONG &&
302 (values[i].mValue.long_value > matcher.gt_int())) {
303 return true;
304 }
305 }
306 return false;
307 }
308 case FieldValueMatcher::ValueMatcherCase::kLtFloat: {
309 for (int i = start; i < end; i++) {
310 if (values[i].mValue.getType() == FLOAT &&
311 (values[i].mValue.float_value < matcher.lt_float())) {
312 return true;
313 }
314 }
315 return false;
316 }
317 case FieldValueMatcher::ValueMatcherCase::kGtFloat: {
318 for (int i = start; i < end; i++) {
319 if (values[i].mValue.getType() == FLOAT &&
320 (values[i].mValue.float_value > matcher.gt_float())) {
321 return true;
322 }
323 }
324 return false;
325 }
326 case FieldValueMatcher::ValueMatcherCase::kLteInt: {
327 for (int i = start; i < end; i++) {
328 if (values[i].mValue.getType() == INT &&
329 (values[i].mValue.int_value <= matcher.lte_int())) {
330 return true;
331 }
332 // lte_int covers both int and long.
333 if (values[i].mValue.getType() == LONG &&
334 (values[i].mValue.long_value <= matcher.lte_int())) {
335 return true;
336 }
337 }
338 return false;
339 }
340 case FieldValueMatcher::ValueMatcherCase::kGteInt: {
341 for (int i = start; i < end; i++) {
342 if (values[i].mValue.getType() == INT &&
343 (values[i].mValue.int_value >= matcher.gte_int())) {
344 return true;
345 }
346 // gte_int covers both int and long.
347 if (values[i].mValue.getType() == LONG &&
348 (values[i].mValue.long_value >= matcher.gte_int())) {
349 return true;
350 }
351 }
352 return false;
353 }
354 default:
355 return false;
356 }
357 }
358
matchesSimple(const UidMap & uidMap,const SimpleAtomMatcher & simpleMatcher,const LogEvent & event)359 bool matchesSimple(const UidMap& uidMap, const SimpleAtomMatcher& simpleMatcher,
360 const LogEvent& event) {
361 if (simpleMatcher.field_value_matcher_size() <= 0) {
362 return event.GetTagId() == simpleMatcher.atom_id();
363 }
364 for (const auto& matcher : simpleMatcher.field_value_matcher()) {
365 if (!matchesSimple(uidMap, matcher, event.getValues(), 0, event.getValues().size(), 0)) {
366 return false;
367 }
368 }
369 return true;
370 }
371
372 } // namespace statsd
373 } // namespace os
374 } // namespace android
375